Research map / Graph learning / GNN architectures
Enhancing Spectral GNNs: From Topology and Perturbation Perspectives
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.
Proposes a perturbed sheaf Laplacian (PSL) built by slightly perturbing orthogonal restriction maps of the block normalized graph Laplacian, increasing distinct eigenvalues and improving spectral GNNs (GCN, APPNP, GPRGNN, BernNet, etc.) on node classification.
Problem
Repeated eigenvalues of the normalized graph Laplacian limit the expressiveness of spectral GNNs, both linear and nonlinear, causing loss of frequency components and restricted frequency processing.
Approach
Replace the block normalized Laplacian with a sheaf Laplacian whose orthogonal restriction maps are reflection matrices slightly deviating from identity (learnable, bounded by eta), which raises the number of distinct eigenvalues while keeping topological structure; supported by expressiveness results and eigenvalue perturbation bounds.
Key results
- PSL-GNN variants improve accuracy over their base spectral GNNs on all 7 datasets, e.g. PSL-GCN averages +1.93 HAG-style gain over GCN with Texas/Cornell gains of about 2-10 points.
- Learned PSL matrices have many more distinct eigenvalues than the normalized Laplacian, e.g. Cora 2389 vs 2262 and Pubmed 9031 vs 7647 for PSL-GCN.
- PSL-GNN performance is comparable to the general sheaf Laplacian GSL-GNN in the ablation study.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Apply PSL to BernNet | BernNet · Cora | accuracy: 88.29±0.63 -> 89.67±1.79 | Helped |
| Apply PSL to BernNet | BernNet · Pubmed | accuracy: 88.50±1.19 -> 89.54±2.40 | Helped |
| Apply PSL to Jacobi | Jacobi · Citeseer | accuracy: 76.89±1.84 -> 77.71±2.50 | Helped |
| Apply PSL to Jacobi | Jacobi · Photo | accuracy: 93.72±1.53 -> 94.43±0.96 | Helped |
| Apply PSL to Jacobi | Jacobi · Cornell | accuracy: 87.11±2.07 -> 88.98±2.42 | Helped |
| Apply PSL to BernNet | BernNet · Texas | accuracy: 85.67±1.99 -> 86.89±2.32 | Helped |
| Apply PSL to Jacobi | Jacobi · Actor | accuracy: 36.56±1.78 -> 37.78±2.05 | Helped |
| Replace the normalized graph Laplacian with a general sheaf Laplacian (ablation) | Vanilla GNNs · Node classification across seven datasets | accuracy | Helped |
| Use PSL instead of a general sheaf Laplacian (ablation) | GCN · Node classification across seven datasets | accuracy | Mixed |
Surprising findings
- Authors report that GCN benefits most (highest average gain), attributed to the high multiplicity of eigenvalue 1 that GCN's fixed filter 1-lambda discards.
- Theorem 3.2 shows that nonlinear activations do not escape the repeated-eigenvalue limit on the number of distinct filter coefficients.
Limitations
- Gains depend on eta perturbation size, tuned over {1e-1,...,1e-4}; the paper states further exploration is needed to fully reduce eigenvalue multiplicity and refine construction.
- Only node classification evaluated; graph-level tasks not investigated.
- Improvements on some datasets are within overlapping confidence intervals.
Experimental setup
Datasets: Cora Pubmed Citeseer Photo Cornell Texas Actor
Benchmarks: Cora Pubmed Citeseer Photo Cornell Texas Actor
Metrics: accuracy vertical average gain horizontal average gain number of distinct eigenvalues
Baselines: GCN APPNP Graph-Heat BernNet GPRGNN Jacobi GSL-GNN Lu et al. 2024 eigenvalue correction
Builds on: sheaf neural networks GPRGNN GCN BernNet Wang and Zhang 2022 Jacobi basis
Closest papers by meaning
- Improving Expressive Power of Spectral Graph Neural Networks with Eigenvalue Correction (AAAI 2024 · similarity 0.91)
- On the Expressive Power of Spectral Invariant Graph Neural Networks (ICML 2024 · similarity 0.91)
- Position: Spectral GNNs Rely Less on Graph Fourier Basis than Conceived (ICML 2025 · similarity 0.91)
- Spectral Graph Neural Networks are Incomplete on Graphs with a Simple Spectrum (NeurIPS 2025 · similarity 0.90)
- Graph Neural Networks Are More Than Filters: Revisiting and Benchmarking from A Spectral Perspective (ICLR 2025 · similarity 0.90)
- SLOG: An Inductive Spectral Graph Neural Network Beyond Polynomial Filter (ICML 2024 · similarity 0.90)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.