A new duality rule allows comparing discrete datasets across different structures.

Comparing data like networks or graphs is hard because they can look different while sharing the exact same structure. A tool called the Gromov-Wasserstein distanceGromov-Wasserstein distanceA method to compare the internal structures of two datasets without aligning them point-by-point. matches these spaces by looking only at their internal shapes. However, calculating it and understanding its statistics across discrete spaces has remained challenging. To solve this, researchers developed a new dualitydualityA mathematical relationship that simplifies a complex problem by expressing it in a different, often easier-to-solve form. formula for this distance, with and without entropic regularizationentropic regularizationA technique that adds a smoothing term to an optimization problem to make it computationally easier to solve., that works for all finitely supported spaces. Duality works by rephrasing a difficult matching problem into a simpler optimization problem from another angle. With this tool, the team determined the sample complexitysample complexityThe amount of data needed from a population to make reliable estimates about the whole. and limit distributions when estimating distances from data. They also built new algorithms with guaranteed convergence and created an efficient method to test if graph distributions are isomorphic.

Why it matters

This helps researchers compare complex networks like those in biology or social science without needing direct matches. It provides a way to test if two network patterns are essentially the same, which could speed up discovery in these fields.

Questions answered