analiza aiqbench
This research establishes the universal consistency of $k$-nearest neighbors classifiers when applied to Gromov--Wasserstein and fused Gromov--Wasserstein distances, enabling robust graph comparison without requiring node embeddings. Theoretical proofs confirm that these metric-based classifiers maintain performance across varying graph sizes and structures, while empirical results validate their efficacy on multiple datasets. This advancement offers a rigorous foundation for using intrinsic metric spaces in graph machine learning tasks where structural alignment is critical.
$k$-Nearest Neighbors in Gromov--Wasserstein Space
arXiv:2606.10295v1 Announce Type: cross Abstract: 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.
Abstract: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.
Machine Learning (stat.ML); Machine Learning (cs.LG); Statistics Theory (math.ST)
arXiv:2606.10295 [stat.ML]
(or arXiv:2606.10295v1 [stat.ML] for this version)
https://doi.org/10.48550/arXiv.2606.10295 Focus to learn more arXiv-issued DOI via DataCite (pending registration)
arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.
Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.
Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.
Text integral sub licența deschisă a publicației · 312 cuvinte
Subiecte conexe
A Topological Characterization of Graph Neural Networks via Stochastic Block Model Embeddings on the n-Sphere
arXiv · 9 iun. 2026
Thermodynamic sampling of disordered materials with an analog Hamiltonian Rydberg simulator
AWS · 23 iul. 2026
Presentation: Postgres for Production Agents: Your Relational Foundation for Enterprise AI
InfoQ · 15 iul. 2026
Constant-Curvature Sliced Gromov-Wasserstein for Heterogeneous Cross-Curvature Alignment
arXiv · 7 oct. 2026