Research map / Graph learning / GNN architectures

Weisfeiler-Leman Is Incomplete on Simple Spectrum Graphs, so Canonicalize Them

NeurIPS 2026 · Graph learning › GNN architectures · approach: Substructure-aware GNN expressivity · 0 citations (OpenAlex)

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.

Shows k-WL cannot distinguish all simple-spectrum multigraphs for any k, then proposes PRiSM, a complete sign canonicalization of simple-spectrum eigendecompositions that yields universal approximation when composed with DeepSets or Transformers.

Problem

Whether WL hierarchy and GNNs can distinguish all non-isomorphic graphs with a simple Laplacian/adjacency spectrum, and how to canonicalize eigenvector sign ambiguity completely in that setting.

Approach

Encodes CFI graph adjacency patterns as an orthogonal integral eigenbasis with distinct integer eigenvalues to get simple-spectrum multigraphs that k-WL fails on; then a four-stage PRiSM canonicalization (Partition, Refine, Solve over Z2, Match) gives a globally complete sign canonicalization, unlike per-eigenvector MAP/OAP.

Key results

• PRiSM distinguishes 212/360 BREC pairs vs 199/360 for MAP and OAP with a matched DeepSets backbone.
• On ZINC with GatedGCN, PRiSM achieves MAE 0.110 vs 0.123 for MAP and 0.126 for OAP.
• With a Transformer backbone on Alchemy, PRiSM reaches MAE 0.11956 vs 0.13058 for MAP and 0.13216 for OAP.

Measured effects reported in the paper

Surprising findings

• Per-eigenvector canonicalizations MAP and OAP cannot assign canonical signs to some eigenvectors (uncanonicalizable eigenvectors), even on simple-spectrum graphs.
• The incompleteness of the entire WL hierarchy holds on simple-spectrum multigraphs, not only on simple graphs.

Limitations

• Completeness is not addressed for higher-order eigenmultiplicities; the extension to repeated eigenvalues is heuristic.
• The canonicalization is discontinuous.
• The incompleteness result is for multigraphs rather than simple combinatorial graphs.

Experimental setup

Datasets: BREC ZINC 12K OGB MolTox21 OGB MolPCBA OGB MolHIV OGB MolClinTox OGB MolBBBP Alchemy

Benchmarks: BREC ZINC 12K OGB MolTox21 OGB MolPCBA OGB MolHIV OGB MolClinTox OGB MolBBBP Alchemy

Metrics: number of distinguished pairs MAE ROC-AUC AP

Baselines: MAP OAP SignNet LPE

Builds on: Cai-Fürer-Immerman construction MAP OAP SignNet DeepSets

Closest papers by meaning

• Spectral Graph Neural Networks are Incomplete on Graphs with a Simple Spectrum (NeurIPS 2025 · similarity 0.91)
• Homomorphism Expressivity of Spectral Invariant Graph Neural Networks (ICLR 2025 · similarity 0.90)
• Position: Spectral GNNs Rely Less on Graph Fourier Basis than Conceived (ICML 2025 · similarity 0.89)
• On the Expressive Power of Spectral Invariant Graph Neural Networks (ICML 2024 · similarity 0.89)
• Weisfeiler-Leman at the margin: When more expressivity matters (ICML 2024 · similarity 0.89)
• Weisfeiler and Leman Go Loopy: A New Hierarchy for Graph Representational Learning (NeurIPS 2024 · similarity 0.88)