Geodesic Distance Between Graphs: A Spectral Metric for Assessing the Stability of Graph Neural Networks
This paper presents a spectral framework for assessing the generalization and stability of Graph Neural Networks (GNNs) by introducing a Graph Geodesic Distance (GGD) metric. 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 with different sizes, a resistance-based spectral graph coarsening scheme is introduced to reduce the size of the bigger 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, the mixing time of random walks, etc. Through extensive experiments comparing with the state-of-the-art metrics, such as the latest Tree-Mover's Distance (TMD) metric, the proposed GGD metric shows significantly improved performance for stability evaluation of GNNs especially when only partial node features are available.
Code (0)
등록된 구현이 없습니다.
Tasks
Graph MatchingSimilar Papers 제목 키워드 기반
Graph Generation with Spectral Geodesic Flow Matching
Graph generation is a fundamental task with wide applications in modeling complex systems. Although existing methods align the spectrum or degree profile of the target graph, they often ignore the geometry induced by eig…
Graph GenerationGeodesic Semantic Search: Cartographic Navigation of Citation Graphs with Learned Local Riemannian Maps
We present Geodesic Semantic Search (GSS), a retrieval system that learns node-specific Riemannian metrics on citation graphs to enable geometry-aware semantic search. Unlike standard embedding-based retrieval that relie…
Matrix factorisation and the interpretation of geodesic distance
Given a graph or similarity matrix, we consider the problem of recovering a notion of true distance between the nodes, and so their true positions. We show that this can be accomplished in two steps: matrix factorisation…
Dimensionality ReductionScribble-Based Interactive Segmentation of Medical Hyperspectral Images
Hyperspectral imaging (HSI) is an advanced medical imaging modality that captures optical data across a broad spectral range, providing novel insights into the biochemical composition of tissues. HSI may enable precise d…
Deep LearningInteractive SegmentationSegmentationCurvature-Aware PCA with Geodesic Tangent Space Aggregation for Semi-Supervised Learning
Principal Component Analysis (PCA) is a fundamental tool for representation learning, but its global linear formulation fails to capture the structure of data supported on curved manifolds. In contrast, manifold learning…
Dimensionality ReductionRepresentation Learning