谱图稀疏化能保持GNN嵌入的几何结构,提升可解释性。
Spectral Graph Sparsification Preserves Representation Geometry in Graph Neural Networks
- 用谱稀疏化控制嵌入空间的几何扰动
- 实验证明嵌入相似度与类别中心稳定
- 适合关注GNN可解释性的研究者
谱图稀疏化是一种经典方法,可在保留拉普拉斯二次型的前提下降低图复杂度。在图神经网络(GNN)中,常用于加速计算并维持预测性能。本文研究了一个互补问题:稀疏化是否保持学习到的嵌入几何?对于多项式滤波类GNN,我们证明任意ε-谱稀疏化会引入O(ε)量级的多项式图滤波、多层隐藏表示及其格拉姆矩阵的扰动。这些保证意味着嵌入空间中平方距离、类别均值和协方差结构的稳定性。进一步,在平滑性和有界性假设下,梯度下降在稠密与稀疏图上产生的权重轨迹分离增长不超过稀疏化失真比例。实验表明,有效电阻稀疏化在合成图上验证了预测的扰动链,并在真实数据集上保持隐藏表示的几何结构。在显著稀疏化下,格拉姆矩阵与训练动态仍显示低发散,与理论预测一致。隐藏格拉姆矩阵的保持强烈预测了在FashionMNIST、Cora和Paul15上的邻域保持与类别中心稳定性。结果表明,谱稀疏化不仅保持图算子,还保留支持下游解释任务的表示几何。
原文摘要 · Abstract (English)
Spectral graph sparsification is a classical tool for reducing graph complexity while preserving Laplacian quadratic forms. In graph neural networks (GNNs), sparsification is often used to accelerate computation while maintaining predictive performance. In this work, we study a complementary representation-level question: does sparsification preserve the geometry of learned embeddings? For polynomial-filter GNNs, we prove that any $ε$-spectral sparsifier induces $O(ε)$ perturbations in polynomial graph filters, multilayer hidden representations, and their Gram matrices. These guarantees imply stability of squared pairwise distances, class means, and covariance structure in embedding space. We further establish finite-time training stability: under smoothness and boundedness assumptions, gradient descent on dense and sparsified graphs produces weight trajectories whose separation grows at most proportionally to the sparsification distortion. Empirically, effective-resistance sparsification validates the predicted perturbation chain on synthetic graphs and preserves hidden representation geometry on real datasets. In our experiments, the gram matrix and training dynamics show low divergence even under substantial sparsification, consistent with the predicted stability under spectral sparsification. Hidden Gram preservation strongly predicts neighborhood preservation and class-centroid stability across FashionMNIST, Cora, and Paul15. Together, these results show that spectral sparsification preserves not only graph operators, but also the representation geometry that supports downstream use of GNN embeddings for interpretability.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。