New k-NN classification method leverages Gromov-Wasserstein distance for graphs
Comparing graphs of different sizes just got a mathematically rigorous boost...
A team of researchers—Kaitlyn Hohmeier, Nicolas Fraiman, and Caroline Moosmueller—has published a paper on arXiv demonstrating how to perform $k$-nearest neighbors ($k$-NN) classification using the Gromov–Wasserstein (GW) distance. This distance allows direct comparison of metric measure spaces (like graphs) even when they have different numbers of nodes, without needing embeddings or feature engineering. The team also extended the approach to incorporate node features via a variant called fused Gromov–Wasserstein (fGW).
Their theoretical contribution is significant: they prove universal consistency for GW-$k$-NN classifiers on the space of equivalence classes of metric measure spaces with finite support and uniform probability. This means the classifier is guaranteed to converge to the Bayes optimal risk as the training set grows, a gold standard in statistical learning theory. Numerical experiments on several graph datasets show that GW-$k$-NN and fGW-$k$-NN perform consistently well, suggesting that metric-based classifiers are a natural fit for graph comparison problems.
- Uses Gromov–Wasserstein distance to compare graphs with different numbers of nodes directly.
- Proves universal consistency (Bayes optimal) for k-NN on metric measure spaces and node-attributed graphs.
- Numerical experiments show strong performance across multiple graph datasets with both GW and fused GW variants.
Why It Matters
Enables robust graph classification without preprocessing, with rigorous theoretical guarantees for real-world network data.