TL;DR
Graph Neural Networks often use spectral features (like Laplacian eigenvectors) to boost their expressive power, but how much do they actually help? This paper reveals a surprising theoretical blind spot: popular spectral GNNs fail to distinguish certain graphs even when they have entirely distinct eigenvalues (a simple spectrum). To fix this, the authors introduce equiEPNN, a novel architecture that borrows from rotation-equivariant point cloud networks to dramatically boost expressivity and achieve perfect eigenvector canonicalization.
What Problem Does This Paper Address?
Standard Message Passing Graph Neural Networks (MPNNs) are fundamentally limited in their ability to tell non-isomorphic graphs apart (bounded by the 1-WL isomorphism test). To break through this wall, researchers frequently inject spectral features—such as graph Laplacian eigenvectors and eigenvalues—as positional encodings.
However, analyzing the true expressive power of these Spectrally-enhanced GNNs (SGNNs) has been difficult. Traditional tools like the $k$-WL hierarchy or homomorphism counting don't map cleanly to spectral properties. This paper tackles the problem using a classic paradigm from spectral graph theory: classifying graphs by their eigenvalue multiplicity. The authors ask a fundamental question: Can spectral GNNs perfectly distinguish graphs that have a "simple spectrum" (where every eigenvalue is unique)? Surprisingly, the answer is no.
Methods
The authors approach the problem through both theoretical counterexamples and architectural innovation:
- Proving Incompleteness: The authors mathematically construct a pair of non-isomorphic graphs with identical, distinct eigenvalues that the generalized Eigenspace Projection GNN (EPNN) framework cannot tell apart.
- Sparsity Conditions for Success: They prove that standard EPNN is actually complete (can distinguish the graphs) if the eigenvectors are dense enough—specifically, if the eigenvector matrix has strictly less than $n$ zero entries.
- The equiEPNN Architecture: To mitigate the failure on sparse graphs, the authors introduce equiEPNN. They draw an elegant analogy between the sign-flip ambiguity of eigenvectors ($\pm v$) and the rotation equivariance ($O(d)$) of geometric point clouds.
equiEPNNtracks both invariant node features ($h_i$) and sign-equivariant features ($v_i$) in parallel, updating them via Euclidean message passing.
[Standard 1-WL] ⊂ [EPNN (Spectral Invariant)] ⊂ [equiEPNN (Spectral Invariant + Equivariant)]
Datasets
The authors evaluated their claims on three distinct types of datasets:
- MNIST Superpixel: An image classification dataset where images are converted into graphs based on pixel clusters.
- ZINC (and Zinc12K): A standard molecular dataset used for graph property regression and evaluating eigenvector canonicalization.
- BREC: A rigorous graph expressivity benchmark containing highly regular and symmetric graphs.
Key Insights and Ideas
- Spectral GNNs aren't as powerful as we thought: Even when a graph has the cleanest possible spectrum (all distinct eigenvalues), standard spectral GNNs can still get tripped up if the eigenvectors contain specific zero-value (sparsity) patterns.
- The Point Cloud Connection: Eigenvector sign ambiguity ($v$ vs $-v$) can be treated mathematically like coordinate rotations in 3D point cloud networks. By treating eigenvectors as geometric coordinates and enforcing sign equivariance, we unlock hidden expressive power.
- Data Density Matters: Real-world datasets like MNIST Superpixels are naturally "dense" (96.9% of its graphs have no zero entries in their rows), meaning standard EPNN is practically complete there. However, for sparse molecular graphs like ZINC, the incompleteness becomes a real issue.
Key Results
MNIST Superpixel Classification
When the number of known eigenvectors ($k$) is severely truncated, equiEPNN significantly outperforms standard EPNN, demonstrating its superior expressivity when spectral information is scarce.
- At $k=3$ eigenvectors:
equiEPNNachieves 60.95% ± 0.9% accuracy vs. EPNN's 48.45% ± 1.2%. - At $k=16$, both models converge to ~91% accuracy because the dataset's graphs satisfy the density conditions required for completeness.
ZINC Molecular Regression
On the ZINC dataset, equiEPNN achieves a test Mean Absolute Error (MAE) of 0.099 ± 0.001, outperforming standard EPNN (0.103) and placing it among the top-performing architectures within its parameter budget (~500K parameters).
Eigenvector Canonicalization
Traditional spectral methods fail to canonicalize eigenvectors that possess internal self-symmetries (about 10.93% of eigenvectors in ZINC are uncanonicalizable). By leveraging the equivariant output of equiEPNN, the authors achieved 0.0% uncanonicalizable eigenvectors, resolving the sign ambiguity problem perfectly.
Limitations and Future Work
While equiEPNN provably fixes the expressivity gaps for graphs with a simple spectrum, the proof of completeness does not yet extend to graphs with higher eigenvalue multiplicities (i.e., graphs with repeated eigenvalues, often caused by high structural symmetry).
The authors note that testing each eigenspace as a separate entity inherently limits universality. A promising direction for future work is to design higher-order point cloud networks that can process the entire graph eigendecomposition as a single entity while remaining invariant to both sign and basis symmetries.
Summary updated