  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.
