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.

通过引入图测地线距离（GGD）度量，本文提出了一种用于评估图神经网络（GNNs）泛化性和稳定性的光谱框架。通过引入光谱图匹配过程找到节点对应关系并计算其测地线距离，通过减小较大图的尺寸但保留原始光谱特性的阻抗型光谱图粗化方案降低了图的大小。实验证明，所提出的 GGD 度量能够有效量化两个图之间的差异，包括节点之间的有效电阻、切割、随机行走的混合时间等结构（光谱）属性，与最新的 Tree-Mover's Distance（TMD）度量相比，提出的 GGD 度量在仅有部分节点特征可用时，对 GNN 的稳定性评估表现出显著改进。

图之间的测地距离：一种用于评估图神经网络稳定性的谱度量

Geodesic Distance Between Graphs: A Spectral Metric for Assessing the  Stability of Graph Neural Networks

State-of-the-art hypergraph partitioners follow the multilevel paradigm,
constructing multiple levels of coarser hypergraphs to drive cutsize
refinement. These partitioners face limitations: (i) coarsening processes
depend on local neighborhood structure, ignoring global hypergraph structure;
(ii) refinement heuristics risk entrapment in local minima. We introduce
K-SpecPart, a supervised spectral framework addressing these limitations by
solving a generalized eigenvalue problem, capturing balanced partitioning
objectives and global hypergraph structure in a low-dimensional vertex
embedding while leveraging high-quality multilevel partitioning solutions as
hints. In multi-way partitioning, K-SpecPart derives multiple bipartitioning
solutions from a multi-way hint partitioning solution. It integrates these
solutions into the generalized eigenvalue problem to compute eigenvectors,
creating a large-dimensional embedding. Linear Discriminant Analysis (LDA) is
used to transform this into a lower-dimensional embedding. K-SpecPart
constructs a family of trees from the vertex embedding and partitions them
using a tree-sweeping algorithm. We extend SpecPart's tree partitioning
algorithm for multi-way partitioning. The multiple tree-based partitioning
solutions are overlaid, followed by lifting to a clustered hypergraph where an
integer linear programming (ILP) partitioning problem is solved. Empirical
studies show K-SpecPart's benefits. For bipartitioning, K-SpecPart outperforms
SpecPart with improvements up to 30%. For multi-way partitioning, K-SpecPart
surpasses hMETIS and KaHyPar, with improvements up to 20% in some cases.

本文提出 K-SpecPart，一个基于监督的谱框架，通过解决广义特征值问题，捕捉低维度顶点嵌入中的平衡分区和全局超图结构，从而缓解现有超图划分方法所面临的局部结构和局部最小值问题。数个实验研究显示，K-SpecPart 在双划分和多划分任务中表现优异，特别是在多划分任务中，K-SpecPart 的性能较之 hMETIS 和 KaHyPar 提升高达 20%。