Research map / Graph learning / GNN architectures
How Universal Polynomial Bases Enhance Spectral Graph Neural Networks: Heterophily, Over-smoothing, and Over-squashing
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 UniBasis, a universal polynomial basis that mixes a homophily basis with an adaptive heterophily basis whose angles are set from an estimated homophily ratio, yielding the UniFilter spectral GNN that resists over-smoothing and over-squashing.
Problem
Fixed predefined polynomial bases in spectral GNNs ignore varying graph heterophily degrees, leading to suboptimal performance on heterophilous graphs, and polynomial propagation suffers from over-smoothing and over-squashing.
Approach
Construct an adaptive heterophily basis whose vectors are mutually separated by an angle (pi/2)(1-h) via an orthogonal-polynomial-style recurrence, and combine it with the homophily basis through a mixing parameter tau, so the basis adapts to the graph's homophily ratio estimated from training labels.
Key results
- UniFilter reaches 75.75% on Chameleon and 67.40% on Squirrel among polynomial filters, the best there, beating Specformer on Squirrel by about 2.8 points.
- Against model-optimized methods, UniFilter reaches 64.26% on Squirrel vs 57.88% for GloGNN++ (up to 6.38-point gain), and is best on 5 of 6 datasets.
- Estimated homophily ratios from training labels stay within about 2% of true h on all datasets except Citeseer.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| replace the fixed polynomial basis with the adaptive universal basis | UniFilter vs. JacobiConv · Cora (60%/20%/20% split) | accuracy (%): 88.98 $\pm$ 0.72 -> 89.49 $\pm$ 1.35 | Helped |
| replace the fixed polynomial basis with the adaptive universal basis | UniFilter vs. Specformer · Citeseer (60%/20%/20% split) | accuracy (%): 81.49 $\pm$ 0.94 -> 81.39 $\pm$ 1.32 | Hurt |
| replace the fixed polynomial basis with the adaptive universal basis | UniFilter vs. EvenNet · Pubmed (60%/20%/20% split) | accuracy (%): 90.87 $\pm$ 0.34 -> 91.44 $\pm$ 0.50 | Helped |
| replace the fixed polynomial basis with the adaptive universal basis | UniFilter vs. OptBasisGNN · Actor (60%/20%/20% split) | accuracy (%): 42.39 $\pm$ 0.52 -> 40.84 $\pm$ 1.21 | Hurt |
| replace the fixed polynomial basis with the adaptive universal basis | UniFilter vs. Specformer · Chameleon (60%/20%/20% split) | accuracy (%): 74.72 $\pm$ 1.29 -> 75.75 $\pm$ 1.65 | Helped |
| replace the fixed polynomial basis with the adaptive universal basis | UniFilter vs. Specformer · Squirrel (60%/20%/20% split) | accuracy (%): 64.64 $\pm$ 0.81 -> 67.40 $\pm$ 1.25 | Helped |
| replace the model-optimized baseline with UniFilter | UniFilter vs. GCNII · Cora (48%/32%/20% split) | accuracy (%): 88.37 $\pm$ 1.25 -> 89.12 $\pm$ 0.87 | Helped |
| replace the model-optimized baseline with UniFilter | UniFilter vs. GCNII · Citeseer (48%/32%/20% split) | accuracy (%): 77.33 $\pm$ 1.48 -> 80.28 $\pm$ 1.31 | Helped |
| replace the model-optimized baseline with UniFilter | UniFilter vs. GCNII · Pubmed (48%/32%/20% split) | accuracy (%): 90.15 $\pm$ 0.43 -> 90.19 $\pm$ 0.41 | Helped |
| replace the model-optimized baseline with UniFilter | UniFilter vs. GloGNN++ · Actor (48%/32%/20% split) | accuracy (%): 37.70 $\pm$ 1.40 -> 37.79 $\pm$ 1.11 | Helped |
| replace the model-optimized baseline with UniFilter | UniFilter vs. GloGNN++ · Chameleon (48%/32%/20% split) | accuracy (%): 71.21 $\pm$ 1.84 -> 73.66 $\pm$ 2.44 | Helped |
| replace the model-optimized baseline with UniFilter | UniFilter vs. LINKX · Squirrel (48%/32%/20% split) | accuracy (%): 61.81 $\pm$ 1.80 -> 64.26 $\pm$ 1.46 | Helped |
Surprising findings
- On Actor, UniFilter (40.84%) is not the top polynomial filter; OptBasisGNN (42.39%) is higher, so UniFilter is not best on every dataset.
Limitations
- Homophily ratio must be estimated from training labels, and the angle choice theta=(pi/2)(1-h) is set empirically rather than derived.
- The over-squashing analysis shows Jacobian independence from k, which is a weak and loosely argued notion rather than a rigorous bound.
- Sensitivity to tau requires tuning; performance drops sharply at tau=1 on heterophily graphs.
Experimental setup
Datasets: Cora Citeseer Pubmed Actor Chameleon Squirrel
Benchmarks: Cora Citeseer Pubmed Actor Chameleon Squirrel
Metrics: accuracy Dirichlet energy
Baselines: SGC SIGN ASGC GPR-GNN EvenNet ChebNet ChebNetII BernNet JacobiConv OptBasisGNN Specformer GCN
Builds on: ChebNet BernNet JacobiConv GPR-GNN OptBasisGNN
Closest papers by meaning
- Unifying Homophily and Heterophily for Spectral Graph Neural Networks via Triple Filter Ensembles (NeurIPS 2024 · similarity 0.93)
- Position: Spectral GNNs Rely Less on Graph Fourier Basis than Conceived (ICML 2025 · similarity 0.93)
- Improving Expressive Power of Spectral Graph Neural Networks with Eigenvalue Correction (AAAI 2024 · similarity 0.91)
- SLOG: An Inductive Spectral Graph Neural Network Beyond Polynomial Filter (ICML 2024 · similarity 0.90)
- HeroFilter: Adaptive Spectral Graph Filter for Varying Heterophilic Relations (NeurIPS 2025 · similarity 0.90)
- WaveNet: Tackling Non-stationary Graph Signals via Graph Spectral Wavelets (AAAI 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.