# A Spectral Framework for Evaluating Geodesic Distances Between Graphs

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 29 of its 75 references that are in the map.
- First posted on arXiv 15 Jun 2024.

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

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Neural Message Passing for Quantum Chemistry](https://mlsanity.com/paper/1704.01212/) (2017)
- [Geometric deep learning: going beyond Euclidean data](https://mlsanity.com/paper/1611.08097/) (2016)
- [Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networks](https://mlsanity.com/paper/1810.02244/) (2018)
- [Convolutional Networks on Graphs for Learning Molecular Fingerprints](https://mlsanity.com/paper/1509.09292/) (2015)
- [TUDataset: A collection of benchmark datasets for learning with graphs](https://mlsanity.com/paper/2007.08663/) (2020)
- [Generalization and Representational Limits of Graph Neural Networks](https://mlsanity.com/paper/2002.06157/) (2020)
- [Optimal Transport for structured data with application on graphs](https://mlsanity.com/paper/1805.09114/) (2018)
- [Geometric Dataset Distances via Optimal Transport](https://mlsanity.com/paper/2002.02923/) (2020)
- [Wasserstein Weisfeiler-Lehman Graph Kernels](https://mlsanity.com/paper/1906.01277/) (2019)
- [Graph Kernels: State-of-the-Art and Future Challenges](https://mlsanity.com/paper/2011.03854/) (2020)
- [On the Unreasonable Effectiveness of Feature propagation in Learning on Graphs with Missing Node Features](https://mlsanity.com/paper/2111.12128/) (2021)
- [Estimating Generalization under Distribution Shifts via Domain-Invariant Representations](https://mlsanity.com/paper/2007.03511/) (2020)
- [Learning on Attribute-Missing Graphs](https://mlsanity.com/paper/2011.01623/) (2020)
- [Tree Mover's Distance: Bridging Graph Metrics and Stability of Graph Neural Networks](https://mlsanity.com/paper/2210.01906/) (2022)
- [Fewer is More: A Deep Graph Metric Learning Perspective Using Fewer Proxies](https://mlsanity.com/paper/2010.13636/) (2020)
- [Spectral Graph Matching and Regularized Quadratic Relaxations I: The Gaussian Model](https://mlsanity.com/paper/1907.08880/) (2019)
- [Adaptive Log-Euclidean Metrics for SPD Matrix Learning](https://mlsanity.com/paper/2303.15477/) (2023)
- [A Survey of Algorithms for Geodesic Paths and Distances](https://mlsanity.com/paper/2007.10430/) (2020)
- [A Topology-aware Graph Coarsening Framework for Continual Graph Learning](https://mlsanity.com/paper/2401.03077/) (2024)
- [Geodesic Distance Descriptors](https://mlsanity.com/paper/1611.07360/) (2016)
- [Riemannian Metric Learning for Symmetric Positive Definite Matrices](https://mlsanity.com/paper/1501.02393/) (2015)
- [Graph Sparsification, Spectral Sketches, and Faster Resistance Computation, via Short Cycle Decompositions](https://mlsanity.com/paper/1805.12051/) (2018)
- [GRASS: Graph Spectral Sparsification Leveraging Scalable Spectral Perturbation Analysis](https://mlsanity.com/paper/1911.04382/) (2019)
- [HyperEF: Spectral Hypergraph Coarsening by Effective-Resistance Clustering](https://mlsanity.com/paper/2210.14813/) (2022)
- [SGL: Spectral Graph Learning from Measurements](https://mlsanity.com/paper/2104.07867/) (2021)
- [Multiscale Graph Comparison via the Embedded Laplacian Discrepancy](https://mlsanity.com/paper/2201.12064/) (2022)
- [SAGMAN: Stability Analysis of Graph Neural Networks on the Manifolds](https://mlsanity.com/paper/2402.08653/) (2024)

## Abstract (arXiv)

This paper presents a spectral framework for quantifying the differentiation between graph data samples by introducing a novel metric named Graph Geodesic Distance (GGD). For two different graphs with the same number of nodes, our framework leverages a spectral graph matching procedure to find node correspondence so that the geodesic distance between them can be subsequently computed by solving a generalized eigenvalue problem associated with their Laplacian matrices. For graphs of different sizes, a resistance-based spectral graph coarsening scheme is introduced to reduce the size of the larger graph while preserving the original spectral properties. We show that the proposed GGD metric can effectively quantify dissimilarities between two graphs by encapsulating their differences in key structural (spectral) properties, such as effective resistances between nodes, cuts, and the mixing time of random walks. Through extensive experiments comparing with state-of-the-art metrics, such as the latest Tree-Mover's Distance (TMD), the proposed GGD metric demonstrates significantly improved performance for graph classification, particularly when only partial node features are available. Furthermore, we extend the application of GGD beyond graph classification to stability analysis of GNNs and the quantification of distances between datasets, highlighting its versatility in broader machine learning contexts.