Research map / Graph learning / GNN architectures
Improving Expressive Power of Spectral Graph Neural Networks with Eigenvalue Correction
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 an eigenvalue correction strategy that blends repeated normalized-Laplacian eigenvalues with equidistant eigenvalues on [0,2] so polynomial spectral GNN filters can fit more distinct responses, integrated into GPR-GNN, BernNet and JacobiConv.
Problem
Polynomial spectral GNNs assign identical filter outputs to repeated normalized-Laplacian eigenvalues, which real-world graphs have in abundance (especially near 1), limiting their expressive power and fitting ability.
Approach
Linearly combine the original eigenvalues with equally spaced eigenvalues from [0,2] via a hyperparameter beta, producing strictly distinct corrected eigenvalues that plug into existing polynomial filters with the same order-K cost, and compute filters via eigenvalue polynomials for speed.
Key results
- EC-GPR improves GPR-GNN on the Chameleon dataset from 67.28% to 74.20% accuracy and on Squirrel from 50.15% to 62.43%.
- On synthetic band/comb/reject filters, EC-Bern reduces MSE versus BernNet, e.g., comb from 0.9982 to 0.3302.
- Reported average gains over base models are 4.2% for GPR-GNN, 3.7% for BernNet and 0.68% for JacobiConv; EC-Bern training is about 75.5% faster than BernNet.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Apply eigenvalue correction to GPR-GNN | GPR-GNN · Real-world node classification datasets | accuracy (%): 4.2% improvement | Helped |
| Apply eigenvalue correction to BernNet | BernNet · Real-world node classification datasets | accuracy (%): 3.7% improvement | Helped |
| Apply eigenvalue correction to JacobiConv | JacobiConv · Real-world node classification datasets | accuracy (%): 0.68% improvement | Helped |
| Apply eigenvalue correction | GPR-GNN, BernNet, and JacobiConv · Synthetic graph-filter learning | mean squared error: 12.9%; 77.9% | Helped |
| Replace the mixed corrected eigenvalues with equidistant eigenvalues only (β=0) (ablation) | EC-GPR, EC-Bern, and EC-Jacobi · Cora, Photo, Chameleon, and Squirrel | accuracy | Hurt |
| Replace the mixed corrected eigenvalues with original eigenvalues only (β=1) (ablation) | EC-GPR, EC-Bern, and EC-Jacobi · Cora, Photo, Chameleon, and Squirrel | accuracy | Hurt |
| Use equidistant eigenvalues instead of original eigenvalues (ablation) | EC-GPR, EC-Bern, and EC-Jacobi · Chameleon and Squirrel versus Cora and Photo | accuracy | Mixed |
| Increase β (ablation) | EC-GPR, EC-Bern, and EC-Jacobi · Cora | model performance | Mixed |
| Increase β above 0.6 (ablation) | EC-GPR, EC-Bern, and EC-Jacobi · Chameleon and Squirrel | model performance: 0.6 | Hurt |
Surprising findings
- Heterophilic and homophilic graphs differ: EC-x-B (original eigenvalues only) drops more on heterophilic graphs, indicating they need more frequency information.
- Eigenvalue distributions of real-world graphs cluster near 1, and random-graph eigenvalues concentrate near 1 as average degree grows.
Limitations
- Requires full eigen-decomposition (precomputation), which may be costly for large graphs; the paper suggests partial eigendecomposition as a workaround without evaluating it.
- Hyperparameter beta must be tuned per dataset and model (tuned over a grid), with no principled selection rule.
- Gains on Photo and some datasets are marginal or within confidence intervals (e.g., JacobiConv 0.68% average).
Experimental setup
Datasets: Cora Citeseer Pubmed Computers Photo Chameleon Actor Squirrel Texas Cornell 50 real images converted to 4-neighbor grid graphs
Benchmarks: Cora Citeseer Pubmed Computers Photo Chameleon Actor Squirrel Texas Cornell synthetic filter learning (low/high/band/reject/comb)
Metrics: mean squared error classification accuracy (%) 95% confidence interval per-epoch time total training time eigen-decomposition time
Baselines: GCN APPNP ChebyNet GAT ARMA GPR-GNN BernNet JacobiConv
Builds on: GPR-GNN BernNet JacobiConv ChebNet
Closest papers by meaning
- Enhancing Spectral GNNs: From Topology and Perturbation Perspectives (ICML 2025 · similarity 0.91)
- Spectral Graph Neural Networks are Incomplete on Graphs with a Simple Spectrum (NeurIPS 2025 · similarity 0.91)
- How Universal Polynomial Bases Enhance Spectral Graph Neural Networks: Heterophily, Over-smoothing, and Over-squashing (ICML 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.90)
- Unifying Homophily and Heterophily for Spectral Graph Neural Networks via Triple Filter Ensembles (NeurIPS 2024 · similarity 0.89)
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.