Spectral graph neural networks process a graph signal by breaking it into "graph frequencies," the eigenvectors of the graph Laplacian, and then rescaling each frequency with a learned curve. When several eigenvectors share the same eigenvalue, the curve must give all of them the same scale. Real graphs have many such repeated eigenvalues, mostly at 0 and 1 in the normalized Laplacian, so whole blocks of the signal are forced to move together. Recent fixes push repeated eigenvalues apart by perturbing the graph. They do this with a uniform grid, random reflections, or learned self-loops. The trouble is that a repeated eigenspace has no preferred basis, so any split that ignores the signal is arbitrary. In at least one method that arbitrariness appears to depend directly on the order in which the eigensolver happens to return the eigenvectors.
We propose leaving the graph's spectrum untouched and instead filtering within each repeated eigenspace, using directions defined by the node features projected into that eigenspace. Inside the degenerate block, the filter's response depends on two things: the eigenvalue, and how much feature energy a direction carries. This gives a canonical, permutation-equivariant way to unlock the missing filter "knobs." It needs no full eigendecomposition, because only the few high-multiplicity eigenspaces have to be extracted, and those can be found with sparse null-space solvers. The claim is testable and could fail. If the gains of existing multiplicity fixes come from expressivity rather than from regularization noise, a signal-defined, basis-free split should match or beat them. It should do so specifically on graphs where a measurable share of label-relevant feature energy lives in degenerate eigenspaces.
Core Claim
Write the normalized Laplacian as a sum over distinct eigenvalues $\lambda$, with $P_\lambda$ the orthogonal projector onto the eigenspace of multiplicity $m_\lambda$. A polynomial filter computes $\sum_\lambda p(\lambda) P_\lambda X$, where $X$ is the node feature matrix. Improving Expressive Power of Spectral Graph Neural Networks with Eigenvalue Correction proves that such a filter has at most as many distinct coefficients as there are distinct eigenvalues. Enhancing Spectral GNNs: From Topology and Perturbation Perspectives proves that stacking nonlinearities between layers does not lift this bound.
Our operator keeps $p(\lambda)$ on eigenvalues of multiplicity one. For each repeated eigenvalue it replaces the single scalar with a learned matrix function of the projected, channel-mixed features $Z_\lambda = P_\lambda X W$, where $W$ is a learned $d \times d'$ channel mixing:
$$Y = \sum_{m_\lambda = 1} p(\lambda)\, P_\lambda X W \;+\; \sum_{m_\lambda > 1} Z_\lambda\, h_\theta\!\left(\lambda,\; \frac{Z_\lambda^\top Z_\lambda}{\lVert Z_\lambda \rVert_F^2}\right).$$
Here $h_\theta(\lambda, \cdot)$ is a small network applied as a spectral function to the $d' \times d'$ normalized Gram matrix. It acts on that matrix's eigenvalues and keeps its eigenvectors. Equivalently, if $Z_\lambda = \sum_r s_r a_r b_r^\top$ is the singular value decomposition, each feature-defined direction $a_r$ inside the eigenspace gets its own gain $g_\theta(\lambda, s_r^2/\lVert Z_\lambda\rVert_F^2)$.
The construction has three properties. First, $P_\lambda$ does not depend on which basis the eigensolver returns. Second, $Z_\lambda$ is permutation-equivariant. Third, the output depends only on the Gram matrix's spectrum and eigenvectors, so sign and rotation ambiguities in the singular vectors cancel. The number of independent responses rises from the number of distinct eigenvalues to as many as $\sum_\lambda \min(m_\lambda, \operatorname{rank} Z_\lambda)$. This makes concrete the quantity that AdaSpec: Adaptive Spectrum for Enhanced Node Distinguishability bounds as min(distinct eigenvalues, non-zero feature components). The response also depends on the input, which links this work to adaptive frequency filtering, where filter coefficients are generated from the input rather than fixed for the whole dataset. Here that adaptivity is aimed at the one place where the scalar-curve model provably runs out of freedom.
Research Program
Theory. We will prove equivariance and basis invariance of the operator. We will then prove a tight capacity statement: the dimension of the set of reachable outputs as a function of eigenvalue multiplicities and projected feature rank. This exact count is what AdaSpec leaves open, since it gives only a lower bound.
Diagnostic. We will define and measure "degenerate energy": the fraction of feature energy, and of label-indicator energy, lying in eigenspaces with $m_\lambda > 1$. We will report it for every benchmark. This turns the multiplicity story into a falsifiable prediction: gains should track degenerate label energy, not the raw count of repeated eigenvalues.
Scalability. In real graphs, high multiplicity at $\lambda = 0$ and $\lambda = 1$ comes largely from local structure such as twin nodes, pendant vertices, and star motifs. Those eigenspaces are null spaces of the sparse matrices $L$ and $L - I$. We will extract them with sparse rank-revealing or Lanczos-style null-space methods. The rest of the spectrum will be filtered with ordinary polynomials that need no decomposition. This avoids the full $O(n^3)$ eigendecomposition that limits Improving Expressive Power of Spectral Graph Neural Networks with Eigenvalue Correction and Rethinking Spectral Graph Neural Networks with Spatially Adaptive Filtering to roughly 20,000 nodes. We will test it up to ogbn-arxiv.
Integration. The module plugs into GPR-GNN, BernNet, and ChebNet backbones, the same plug-in protocol the multiplicity papers use.
Related work, sorted by role. Three papers motivate the work: EC, PSL, and AdaSpec establish the bottleneck. EC spreads eigenvalues toward an equidistant grid, PSL perturbs sheaf restriction maps with Householder reflections at a tuned scale $\eta$, and AdaSpec learns per-node self-loops and feature-weighted edges. All three change the operator for every frequency. We change nothing outside the degenerate blocks, so non-degenerate structure is preserved exactly and there is no $\eta$-style trade-off between topology and spectral diversity.
The node- and channel-adaptive filters show that input-conditioned responses help, but they never touch multiplicity:
- AdaGNN learns a smoothness scalar per channel.
- Graph Neural Networks with Diverse Spectral Filtering generates per-node filter weights from positional encodings.
- Node-oriented Spectral Filtering for Graph Neural Networks generates per-node filter weights from node features.
All three still scale each eigenspace uniformly within a channel. SLOG supplies real-valued filter orders and subgraph sampling but stays a scalar function of $\lambda$.
One paper constrains how we evaluate. A critical look at the evaluation of GNNs under heterophily shows that more than half of the nodes in squirrel and chameleon are duplicates. Duplicate nodes are exactly the twin structures that create $\lambda = 1$ multiplicity, so gains on those datasets may reflect memorization. We therefore treat its duplicate-free suite as primary.
Baselines
Unmodified backbone. The do-nothing reference is the unmodified backbone (GPR-GNN, BernNet, ChebNet) on the plain normalized Laplacian. Every method shares the same backbone, splits, hidden size, and polynomial order. Each method gets an equal hyperparameter search budget, the same number of trials over its own hyperparameters ($\beta$ for EC, $\eta$ for PSL, the width of $h_\theta$ for ours), with 10 seeds each.
Existing multiplicity fixes. These are the strongest competitors on the exact question, and the comparison is direct.
- Eigenvalue Correction (EC) interpolates eigenvalues with an equidistant grid. It reports a 77.9% reduction in average loss on synthetic comb and band filter fitting and a 17% average improvement over base models on Squirrel.
- The Perturbed Sheaf Laplacian (PSL) raises Pubmed's distinct eigenvalue count from roughly 7,647 to over 9,000. No absolute accuracies were found on Lacuna for it.
- AdaSpec reports an average ROC AUC improvement of 1.27% on large heterophilic datasets and +12.49% for ChebNet on Texas.
No reported absolute result was found on Lacuna for any of these methods on roman-empire, minesweeper, amazon-ratings, tolokers, or questions. We will therefore rerun all three ourselves. Beating them means a higher mean than the best of the three on the duplicate-free suite, outside seed standard error, on at least two backbones, with lower variance across eigensolver basis choices.
Strongest general method on clean heterophily. Following A critical look at the evaluation of GNNs under heterophily, this is a GAT or graph transformer with separate self and neighbor embeddings, which took 13 of the top 15 places on that suite. That paper reports rankings rather than numbers in the file, so no reported value was found on Lacuna. We run it under the same budget. Our honest target is to close the gap between spectral backbones and this model, not necessarily to pass it on every dataset.
Ablations isolating the key ingredient. We run three:
- Setting $h_\theta$ to a constant per eigenvalue recovers a scalar filter. This tests whether within-eigenspace splitting matters at all.
- Applying $h_\theta$ to all eigenspaces rather than only degenerate ones. This tests whether the benefit is generic feature-conditioned filtering or specific to multiplicity.
- Replacing the feature-defined directions with a random orthonormal split of each degenerate eigenspace. This tests whether signal-defined splitting beats arbitrary splitting.
Why not just…?
Why not just use Eigenvalue Correction, PSL, or AdaSpec, which already split eigenvalues? EC assigns distinct grid values to eigenvectors by index. Inside a repeated eigenspace that index order is whatever the eigensolver returned, so the learned model depends on an arbitrary basis choice. PSL's split depends on random Householder parameters and a sensitive $\eta$, a dependence its authors acknowledge. All three also change the response at every frequency, not just at degenerate ones. Our first decisive check below measures how much EC's accuracy moves under random rotations within eigenspaces. If it barely moves and EC matches our method, the arbitrariness is harmless in practice and our contribution reduces to theory plus scalability. We would report that outcome.
Why not just give nodes random features or positional encodings to break symmetry? Random features do separate twin nodes, but they break permutation equivariance, add noise that must be averaged over, and do not transfer to unseen graphs. Positional encodings from Laplacian eigenvectors inherit the same basis ambiguity inside degenerate eigenspaces. We include random-feature and Laplacian-eigenvector-encoding variants of the backbone under the same budget. If they match us on the duplicate-free suite, that is a real threat, and it would suggest the bottleneck is symmetry rather than filter capacity.
Why not just use a spatial model with separate self and neighbor embeddings? This is the most serious alternative. The self path already preserves the twin-difference signal that a scalar filter at $\lambda = 1$ cannot weight, and such models dominate clean heterophily benchmarks per A critical look at the evaluation of GNNs under heterophily. Our counter-claim is narrow. Preserving a signal is not the same as scaling different directions of it differently, which is what comb-like responses need. BernNet shows GCN reaching only 0.2977 R² on a comb filter versus 0.9868 for BernNet. The degenerate-energy diagnostic settles which view is right. If the spatial model wins precisely where degenerate label energy is high, the eigenspace story is wrong for real tasks.
Proposed Experiments
Synthetic filter fitting. We start on synthetic 2D grids, which have very high multiplicity, using the low-pass, high-pass, band-pass, and comb targets from BernNet and EC. Here we also add targets that depend on direction within a degenerate eigenspace, which no scalar filter can represent even in principle. Success means matching EC on scalar targets and fitting the within-eigenspace targets where EC and BernNet cannot.
Node classification. Real-graph evaluation uses the duplicate-free heterophilic suite (roman-empire, amazon-ratings, minesweeper, tolokers, questions; accuracy or ROC AUC as specified there), plus Texas, Wisconsin, and Cornell. It also uses Cora, Citeseer, and Pubmed, where the method should do no harm, and ogbn-arxiv for runtime and memory against EC's full decomposition.
Decisive check: basis sensitivity. We retrain EC with the eigenvectors inside each repeated eigenspace randomly rotated, and report the spread in accuracy across rotations against the spread across seeds. Our method's spread is zero by construction.
Decisive check: does the gain track degenerate label energy? We plot each method's gain over the backbone against degenerate label energy across datasets. The proposal predicts a positive relationship for our method and a weaker one for EC and PSL.
Decisive check: leakage. Squirrel and chameleon are run both raw and with duplicates removed. If the multiplicity fixes, ours included, lose most of their advantage after deduplication, then the published heterophily gains were largely twin memorization. That outcome would itself be a result worth reporting.
References
- Improving Expressive Power of Spectral Graph Neural Networks with Eigenvalue Correction
- Enhancing Spectral GNNs: From Topology and Perturbation Perspectives
- AdaSpec: Adaptive Spectrum for Enhanced Node Distinguishability
- Rethinking Spectral Graph Neural Networks with Spatially Adaptive Filtering
- AdaGNN: Graph Neural Networks with Adaptive Frequency Response Filter
- Graph Neural Networks with Diverse Spectral Filtering
- Node-Oriented Spectral Filtering for Graph Neural Networks
- SLOG: An Inductive Spectral Graph Neural Network Beyond Polynomial Filter
- A critical look at the evaluation of GNNs under heterophily: are we really making progress?
- BernNet: Learning Arbitrary Graph Spectral Filters via Bernstein Approximation