Research map / Graph learning / GNN architectures

Spectral Graph Sparsification Preserves Representation Geometry in Graph Neural Networks

NeurIPS 2026 · Graph learning › GNN architectures · approach: Spectral GNN design · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Proves that epsilon-spectral sparsifiers induce O(epsilon) perturbations in polynomial-filter GNN embeddings, Gram matrices, class statistics and training trajectories, and validates empirically with effective-resistance sparsification on synthetic graphs, FashionMNIST, Cora and Paul15.

Problem

Whether spectral graph sparsification, which is used to accelerate GNNs while preserving accuracy, also preserves the geometry of learned hidden representations (pairwise distances, class means, covariances) and training dynamics.

Approach

Chains operator-level spectral sparsifier guarantees through polynomial filters, multilayer nonlinear forward maps, and Gram matrices to show O(epsilon) stability of embedding geometry and finite-time gradient descent trajectories, framing sparsification evaluation around representation geometry rather than accuracy alone.

Key results

• On real datasets, 20-NN overlap is strongly anti-correlated with hidden Gram distortion (Spearman -0.92 FashionMNIST, -0.90 Cora, -0.92 Paul15).
• On synthetic graphs, relative representation and Gram distortions stay small (0.03-0.08) even at empirical spectral distortion around 0.7 where roughly half the edges remain.
• Relative parameter gap between dense and sparse training grows smoothly over training and increases approximately linearly with empirical spectral distortion, though absolute gaps remain small.

Surprising findings

• Hidden representation and Gram distortions are substantially smaller than the underlying graph-level spectral distortion, which the authors note in conclusions.
• Much of the dense-sparse embedding discrepancy is explained by an approximately rigid (Procrustes) transformation.

Limitations

• Assumes epsilon-spectral approximation which may hold only approximately in practice
• Analysis relies on boundedness, Lipschitz and smoothness assumptions; training guarantees limited to finite-time full-batch settings
• Experiments are small-scale; larger benchmarks and more aggressive compression not tested

Experimental setup

Datasets: FashionMNIST Cora Paul15 weighted SBM (synthetic) geometric k-NN graph (synthetic)

Benchmarks: FashionMNIST Cora Paul15 synthetic SBM synthetic geometric graph

Metrics: empirical spectral distortion relative hidden Gram distortion relative representation error 20-NN overlap relative parameter gap Spearman correlation KD student accuracy

Baselines: GCN teacher (dense graph)

Builds on: spectral graph sparsification (Spielman-Srivastava effective resistance sampling GCN Chebyshev spectral GNN GNN transferability and stability analyses

Closest papers by meaning

• Mitigating Over-Squashing in Graph Neural Networks by Spectrum-Preserving Sparsification (ICML 2025 · similarity 0.90)
• Position: Spectral GNNs Rely Less on Graph Fourier Basis than Conceived (ICML 2025 · similarity 0.90)
• Enhancing Spectral GNNs: From Topology and Perturbation Perspectives (ICML 2025 · similarity 0.88)
• Graph Coarsening with Message-Passing Guarantees (NeurIPS 2024 · similarity 0.88)
• On the Expressive Power of Spectral Invariant Graph Neural Networks (ICML 2024 · similarity 0.88)
• Distilling Graph Geometry: Knowledge Gap from GNNs to MLPs (NeurIPS 2026 · similarity 0.87)