# k-Nearest Neighbors in Gromov--Wasserstein Space

arXiv: https://arxiv.org/abs/2606.10295 · HTML: https://mlsanity.com/paper/2606.10295/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 8 of its 36 references that are in the map.
- First posted on arXiv 9 Jun 2026.

## Builds on (most cited first, 8 of 8)

- [Fused Gromov-Wasserstein distance for structured objects: theoretical foundations and mathematical properties](https://mlsanity.com/paper/1811.02834/) (2018)
- [Propagation Kernels](https://mlsanity.com/paper/1410.3314/) (2014)
- [Rates of Convergence for Nearest Neighbor Classification](https://mlsanity.com/paper/1407.0067/) (2014)
- [On a linear Gromov-Wasserstein distance](https://mlsanity.com/paper/2112.11964/) (2021)
- [The Z-Gromov-Wasserstein Distance](https://mlsanity.com/paper/2408.08233/) (2024)
- [A Novel Sliced Fused Gromov-Wasserstein Distance](https://mlsanity.com/paper/2508.02364/) (2025)
- [Universal consistency of the k-NN rule in metric spaces and Nagata dimension](https://mlsanity.com/paper/2003.00894/) (2020)
- [Topics in Random Matrices and Statistical Machine Learning](https://mlsanity.com/paper/1807.09419/) (2018)

## Abstract (arXiv)

The Gromov--Wasserstein (GW) distance provides a framework for comparing metric measure spaces, regardless of their underlying structure or geometry. For network-based data, it enables direct comparisons of graphs with different numbers of nodes, without requiring an embedding or other abstraction. Furthermore, through a variant of GW known as fused Gromov--Wasserstein (fGW), it is also possible to incorporate node features in addition to graph structure. In this work, we implement k-nearest neighbors (k-NN) classification using the GW and fGW distances. We prove the universal consistency of the GW-k-NN classifier on the space of equivalence classes of metric measure spaces with finite support and uniform probability measure. By viewing graphs as finitely supported metric measure spaces equipped with the pairwise distance metric and a uniform probability measure on the nodes, we obtain universal consistency of GW-k-NN for the space of graphs. Likewise for fGW-k-NN, we prove universal consistency on the space of weak isomorphism classes of structured objects consisting of metric measure spaces with finite support and uniform probability measure and feature maps into Euclidean space, thus establishing universal consistency on the space of node-attributed graphs. Our numerical experiments show that GW-k-NN and fGW-k-NN consistently perform well across multiple graph datasets, suggesting that metric classifiers such as k-NN work well in the GW framework.