Research map / Graph learning / GNN architectures
Homomorphism Expressivity of Spectral Invariant Graph Neural Networks
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.
Characterizes the homomorphism expressivity of spectral invariant GNNs as exactly the parallel trees of bounded depth, and uses this to build a hierarchy versus MPNNs, subgraph GNNs, local 2-GNNs and 2-FWL, plus cycle/subgraph counting results.
Problem
Prior analyses of spectral invariant GNNs relied only on Weisfeiler-Lehman tests, which are coarse; there was no fine-grained, quantitative characterization of their expressive power, nor of their substructure counting and iteration-depth requirements.
Approach
Shows that the homomorphism expressivity of d-iteration spectral invariant GNNs exists and equals the family of parallel trees with parallel tree depth at most d, proven via a walk-encoding equivalence (Cayley-Hamilton) and a pebble game on Furer graphs.
Key results
- Spectral invariant GNN can count all cycles and paths up to 7 vertices; 1 iteration suffices for cycles up to 6 vertices.
- On ZINC-subset, spectral invariant GNN achieves MAE .103 vs MPNN .138 and Subgraph GNN .110 (under 500K parameter budget).
- Spectral invariant GNNs with d+1 iterations are strictly more powerful than with d iterations, answering an open conjecture about constant iterations.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use Spectral Invariant GNN instead of MPNN | GNNs · ZINC-subset | MAE: $.138\pm.006$ -> $.103\pm.006$ | Helped |
| Use Spectral Invariant GNN instead of MPNN | GNNs · ZINC-full | MAE: $.030\pm.002$ -> $.028\pm.003$ | Helped |
| Use Spectral Invariant GNN instead of Local 2-GNN | GNNs · ZINC-subset | MAE: $.069\pm.001$ -> $.103\pm.006$ | Hurt |
| Use Spectral Invariant GNN instead of Local 2-GNN | GNNs · ZINC-full | MAE: $.024\pm.002$ -> $.028\pm.003$ | Hurt |
| Use Spectral Invariant GNN instead of MPNN | GNNs · Homomorphism count, substructures 1 and 2 | normalized MAE: $.300$ -> $.045$; $.261$ -> $.046$ | Helped |
| Use Spectral Invariant GNN instead of MPNN | GNNs · Homomorphism count, substructures 3 and 4 | normalized MAE: $.276$ -> $.053$; $.233$ -> $.048$ | Helped |
| Use Spectral Invariant GNN instead of MPNN | GNNs · Homomorphism count, substructure 5 | normalized MAE: $.341$ -> $.303$ | Helped |
| Use Spectral Invariant GNN instead of Local 2-GNN | GNNs · Homomorphism count, substructures 1–4 | normalized MAE: $.008$ -> $.045$; $.006$ -> $.046$; $.008$ -> $.053$; $.008$ -> $.048$ | Hurt |
| Use Spectral Invariant GNN instead of Local 2-GNN | GNNs · Homomorphism count, substructure 5 | normalized MAE: $.112$ -> $.303$ | Hurt |
| Use Spectral Invariant GNN instead of MPNN | GNNs · Substructure counting tasks 1–6 | normalized MAE: $.358$ -> $.072$; $.208$ -> $.072$; $.188$ -> $.089$; $.146$ -> $.089$; $.261$ -> $.060$; $.205$ -> $.099$ | Helped |
| Use Spectral Invariant GNN instead of Local 2-GNN | GNNs · Substructure counting tasks 1–6 | normalized MAE: $.008$ -> $.072$; $.011$ -> $.072$; $.017$ -> $.089$; $.034$ -> $.089$; $.007$ -> $.060$; $.016$ -> $.099$ | Hurt |
| Increase spectral-invariant GNN iterations from d to d+1 | Spectral Invariant GNN · Homomorphism expressivity | expressive power | Helped |
Surprising findings
- Spectral invariant GNNs with 2 iterations are incomparable to subgraph GNNs, contrary to the earlier belief that the 1-iteration result extends to all iterations.
- Spectral invariant GNN with 1 iteration (Furer's weak spectral invariant) cannot count 7-cycles, yet counts 6-cycles.
Limitations
- Experiments are small-scale and aimed at validating theory rather than achieving SOTA on ZINC.
- Theory is restricted to connected graphs; disconnected case deferred to prior work.
- Higher-order results are stated informally in the main text with proofs deferred to the appendix.
Experimental setup
Datasets: ZINC-subset ZINC-full
Benchmarks: ZINC-subset ZINC-full homomorphism count benchmark substructure (cycle) count benchmark
Metrics: MAE
Baselines: MPNN Subgraph GNN Local 2-GNN 2-FWL BasisNet
Builds on: homomorphism expressivity (Joshi et al.) Furer graphs Cayley-Hamilton theorem pebble game for k-FWL
Closest papers by meaning
- On the Expressive Power of Spectral Invariant Graph Neural Networks (ICML 2024 · similarity 0.94)
- Spectral Graph Neural Networks are Incomplete on Graphs with a Simple Spectrum (NeurIPS 2025 · similarity 0.92)
- Beyond Weisfeiler-Lehman: A Quantitative Framework for GNN Expressiveness (ICLR 2024 · similarity 0.92)
- Homomorphism Counts for Graph Neural Networks: All About That Basis (ICML 2024 · similarity 0.92)
- Schur Nets: exploiting local structure for equivariance in higher order graph neural networks (NeurIPS 2024 · similarity 0.91)
- Weisfeiler-Leman Is Incomplete on Simple Spectrum Graphs, so Canonicalize Them (NeurIPS 2026 · 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.