📊 statistics

$k$ -Nearest Neighbors in Gromov--Wasserstein Space

This paper implements $k$ -nearest neighbors classification using Gromov--Wasserstein and fused Gromov--Wasserstein distances to compare graphs and node-attributed graphs, respectively, and proves the universal consistency of these classifiers while demonstrating their strong empirical performance across multiple datasets.

Original authors: Kaitlyn Hohmeier, Nicolas Fraiman, Caroline Moosmueller

Published 2026-06-10

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Kaitlyn Hohmeier, Nicolas Fraiman, Caroline Moosmueller

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to sort a massive pile of different objects. Some are simple shapes, others are complex networks like subway maps or social circles. Your goal is to figure out what category a new, unseen object belongs to by looking at the objects you already know. This is the job of a $k$ -Nearest Neighbors ( $k$ -NN) classifier.

Think of $k$ -NN like a "popularity contest" among your neighbors. If you drop a new object into a room of known objects, you look at the $k$ closest ones. If most of those neighbors are "cats," you guess the new object is a cat too.

The problem is: How do you measure "closeness" when the objects are complex networks (graphs) with no standard size or shape? You can't just measure the distance between two points on a map.

This paper introduces a clever new way to measure that distance using something called Gromov–Wasserstein (GW) and Fused Gromov–Wasserstein (fGW). Here is the breakdown in simple terms:

1. The Problem: Comparing Apples to Oranges (and Oranges to Airplanes)

Usually, to compare two things, they need to be the same size. If you want to compare two graphs (networks of dots and lines), traditional methods often force them to be the same size or turn them into a single list of numbers (an "embedding"). This is like trying to compare a small family tree to a massive corporate org chart by squishing them both into the same tiny box. You lose information.

2. The Solution: The "Shape-Shifting" Ruler

The authors use a mathematical tool called Gromov–Wasserstein distance.

The Analogy: Imagine you have two different cities. One is a grid (like Manhattan), and the other is a web of winding roads (like San Francisco). They look totally different.
The GW Magic: Instead of comparing the streets directly, GW asks: "If I could magically rearrange the people in City A to match the population density of City B, how much would the 'relationship distance' between neighbors change?"
It doesn't care if the cities have 100 people or 1,000 people. It only cares about the pattern of relationships. If City A has a "hub" with many connections and City B has a similar "hub," GW says, "These two cities are structurally similar," even if they look different on a map.

3. Adding "Features": The Fused Version

Sometimes, the dots in your network have extra information. For example, in a molecule graph, each atom has a specific type (Carbon, Oxygen). In a social graph, each person has a job title.

The Analogy: Imagine comparing two cities again. GW looks at the road patterns. But what if you also want to compare the types of buildings?
The fGW Magic: The Fused Gromov–Wasserstein (fGW) distance does both at once. It checks if the road patterns match and if the buildings in similar spots are the same type. It's like a ruler that measures both the shape of the city and the color of the houses.

4. The Big Claim: "It Always Works" (Universal Consistency)

The authors didn't just build a new ruler; they proved mathematically that using this ruler with the $k$ -NN method always works in the long run.

The Guarantee: They proved that if you keep adding more and more training data (more examples of graphs), your $k$ -NN classifier using these new distances will eventually become as accurate as theoretically possible.
The Catch: This proof holds true for graphs of any size, as long as you follow specific rules about how you choose your "neighbor count" ( $k$ ) as your data grows. They showed that the space of all possible graphs behaves nicely enough for this math to hold up.

5. The Experiment: Does it actually help?

The authors tested their method on real-world data:

Molecules: Sorting chemicals based on their structure and atom types.
Social Networks: Sorting movie collaboration networks (e.g., "Action" movies vs. "Romance" movies).
Synthetic Data: Made-up networks to test the limits.

The Results:

Their method (GW- $k$ -NN and fGW- $k$ -NN) performed very well, often beating or matching other popular methods like Graph Neural Networks (GCNs) and complex graph kernels.
Key Finding: For molecules with extra data (atom types), the "Fused" version (fGW) was the clear winner. It showed that looking at both the structure and the features together is better than looking at just one.
Efficiency: While the math is heavy, the method was surprisingly fast and efficient compared to some other complex methods, especially for non-attributed graphs.

Summary

The paper says: "We found a way to measure how similar two complex networks are, regardless of their size or shape. We proved that if you use this measurement to sort new networks based on their closest neighbors, the method is mathematically guaranteed to get better and better as you feed it more data. Our tests show it works great on real-world problems like identifying molecules and movie genres."

What they did NOT claim:

They did not claim this works for every possible type of data (only graphs and structured objects).
They did not claim it is the fastest method in the world (they noted it can be computationally heavy, though they showed it's competitive).
They did not apply this to medical diagnoses or clinical uses; they stuck strictly to graph classification tasks.

Technical Summary: $k$ -Nearest Neighbors in Gromov–Wasserstein Space

Problem Statement
The paper addresses the challenge of classifying graph-structured data, including both non-attributed graphs and node-attributed graphs, within a rigorous metric learning framework. Traditional $k$ -nearest neighbors ( $k$ -NN) classifiers rely on distance functions defined in Euclidean or standard metric spaces. However, graphs often possess complex structures where direct comparison is difficult, particularly when graphs have different numbers of nodes or lack a canonical embedding. While the Gromov–Wasserstein (GW) distance provides a framework for comparing metric measure spaces (mm-spaces) and the fused Gromov–Wasserstein (fGW) distance extends this to include node features, the theoretical properties of $k$ -NN classifiers operating within these specific metric spaces were previously unknown. Specifically, it was unclear whether $k$ -NN is universally consistent (converging to the optimal Bayes risk) when the underlying space is the space of graphs equipped with GW or fGW distances.

Methodology
The authors implement $k$ -NN classification using GW and fGW distances and investigate their theoretical consistency. The core of their methodology involves establishing the topological properties of the metric spaces in question to satisfy conditions required for universal consistency.

Metric Space Definitions:
- GW Space ( $\mathbb{X}$ ): The space of equivalence classes of mm-spaces with finite support and uniform probability measure, equipped with the $p=2$ Gromov–Wasserstein distance. This models non-attributed graphs.
- fGW Space ( $\mathbb{Y}^f$ ): The space of weak isomorphism classes of structured objects (mm-spaces with feature maps into $\mathbb{R}^d$ ), equipped with the fused Gromov–Wasserstein distance ( $p=1, q=2$ ). This models node-attributed graphs.
Theoretical Framework:
The authors rely on established results in learning theory (specifically Chaudhuri and Dasgupta [9]) which state that $k$ -NN is universally consistent on a separable metric space if the space possesses $\sigma$ -finite metric dimension (a property related to the Lebesgue differentiation condition). To prove this for GW and fGW spaces, the authors:
- Construct finite-dimensional models for $n$ -point spaces within these frameworks.
- Demonstrate the existence of bi-Lipschitz maps between the space of $n$ -point graphs and specific quotient spaces of Euclidean matrices (for GW) and product spaces of matrices and feature vectors (for fGW).
- Prove that these quotient spaces have finite Assouad-Nagata dimension.
- Utilize Lemma 2.4 to show that the existence of bi-Lipschitz maps to spaces with finite dimension implies the target spaces ( $\mathbb{X}$ and $\mathbb{Y}^f$ ) have $\sigma$ -finite metric dimension.
Numerical Experiments:
The authors evaluate the performance of GW- $k_n$ -NN and fGW- $k_n$ -NN on seven benchmark datasets:
- Attributed Graphs: BZR, COX-2, and PROTEINS (molecular datasets).
- Non-attributed Graphs: IMDb-B, IMDb-M (social networks), and two synthetic datasets (ERSBM1, ERSBM2).
- Baselines: Comparisons are made against Graph Convolutional Networks (GCN), various graph kernel methods (Shortest Path, Graphlet, HOPPER, Propagation), and SVMs using GW/fGW kernels.

Key Contributions
The primary contribution of this work is the proof of universal consistency for $k$ -NN classifiers in the context of graph classification using GW and fGW distances.

Theoretical Results:
- Theorem 1.8: Proves that the GW- $k_n$ -NN classifier is universally weakly consistent on the space of graphs $(\mathbb{X}, GW_2)$ under the conditions $k \to \infty$ and $k/n \to 0$ . It is universally strongly consistent if $k/\log(n) \to \infty$ .
- Theorem 1.9: Proves the same consistency results for the fGW- $k_n$ -NN classifier on the space of node-attributed graphs $(\mathbb{Y}^f, fGW_{\alpha,1,2})$ .
- These results are established by showing that both spaces are separable and possess $\sigma$ -finite metric dimension, a property derived via bi-Lipschitz embeddings into quotient spaces of Euclidean spaces.
Empirical Results:
- On attributed graph datasets (BZR, COX-2, PROTEINS), fGW- $k_n$ -NN consistently achieved the highest average accuracy, outperforming GCNs and other kernel-based methods. GW- $k_n$ -NN also performed competitively.
- On non-attributed datasets, GW- $k_n$ -NN achieved perfect accuracy (100%) on the ERSBM2 synthetic dataset and strong performance on IMDb-B, often outperforming graph kernels and GCNs.
- The authors note that while GW/fGW methods are interpretable (small distances imply structural similarity), they can be computationally intensive compared to some kernel methods, though they offer efficiency improvements over SVMs using GW kernels in certain contexts.

Significance and Claims
The paper claims to establish a theoretical foundation for using metric classifiers like $k$ -NN within the Gromov–Wasserstein framework. By proving universal consistency, the authors argue that these methods are not merely heuristic but are theoretically sound for graph classification tasks.

The significance lies in bridging the gap between optimal transport theory and statistical learning theory for structured data. The authors emphasize that their approach offers a "highly interpretable framework" where the distance between graphs directly measures structural similarity (isomorphism implies zero distance). They explicitly state that, to their knowledge, this is the first application of GW- $k$ -NN to graph classification and the first theoretical proof of its consistency.

The paper remains modest regarding future generalizations. It acknowledges that while consistency is proven for specific parameters ( $p=2$ for GW, $p=1, q=2$ for fGW), it remains an open problem whether these results hold for other parameter choices or in the most general Z-Gromov–Wasserstein settings. The authors conjecture that, similar to the Wasserstein space, universal consistency may not hold in full generality without specific restrictions on the spaces of interest.