Technical Summary: Weisfeiler–Leman Is Incomplete on Simple Spectrum Graphs, so Canonicalize Them

Problem Statement

Graph Neural Networks (GNNs) are widely used for learning on graph-structured data, yet their expressive power is often bounded by the Weisfeiler–Leman (WL) hierarchy. It is a known result that the $k$-dimensional WL test ($k$-WL) cannot distinguish all non-isomorphic graphs. However, a specific class of graphs—those with a simple spectrum (where the adjacency matrix has distinct eigenvalues)—admits cubic-time isomorphism testing. Despite this theoretical tractability, it remained an open question whether the WL hierarchy, which upper-bounds the expressivity of many GNNs, could distinguish all simple-spectrum graphs.

Furthermore, while spectral positional encodings (e.g., Laplacian eigenvectors) are commonly integrated into GNNs to enhance expressivity, they suffer from inherent ambiguities: sign ambiguity for simple spectra and basis ambiguity for repeated eigenvalues. Existing methods to resolve these ambiguities (such as SignNet, MAP, and OAP) are provably incomplete on simple-spectrum graphs, failing to distinguish certain non-isomorphic pairs. This incompleteness limits the ability of spectral GNNs to achieve universal approximation on this class of graphs.

Methodology

1. Proof of WL Incompleteness on Simple Spectra

The authors first establish that the entire WL hierarchy is incomplete on simple-spectrum graphs.

• Construction: They utilize the Cai–Fürer–Immerman (CFI) construction, which generates pairs of non-isomorphic graphs indistinguishable by $k$-WL.
• Encoding: Since standard CFI graphs do not possess a simple spectrum, the authors introduce a novel integral encoding mechanism. They map the CFI adjacency patterns into an orthogonal matrix $\tilde{X}$ composed of integer entries.
• Multigraph Formation: Using this orthogonal matrix and a diagonal matrix of distinct integer eigenvalues, they construct a pair of symmetric multigraphs ($A_{G,0}$ and $A_{G,1}$) with simple spectra.
• Result: They prove that these constructed simple-spectrum multigraphs remain indistinguishable by the $k$-WL test, demonstrating that no level of the WL hierarchy can solve the isomorphism problem for this class, despite the problem being solvable in cubic time.

2. PRiSM: A Complete Canonicalization

To address the limitations of existing spectral methods, the authors propose PRiSM (Partition, Refine, Solve, Match), a provably complete canonicalization procedure for eigendecompositions of simple-spectrum graphs.

• Input: A column-wise orthonormal matrix $U$ of eigenvectors.
• Ambiguity Group: The procedure handles the ambiguity group $S_n \times \{-1, 1\}^k$ (permutations and sign flips).
• Four Stages:
  1. Partition: Vertices are grouped based on their sign-invariant signatures (absolute values of eigenvector entries).
  2. Refine: A spectral variant of the WL color refinement procedure is applied to the partition. This iteratively refines the vertex classes using the multiset of edge features defined by element-wise products of eigenvector entries ($U_v \odot U_u$) until the partition stabilizes.
  3. Solve: The stable partition defines a system of linear equations over the field $\mathbb{Z}_2$. The system enforces that each partition class contains at least one row with non-negative entries. Solving this system determines the unique canonical signs for the eigenvectors (up to graph automorphisms).
  4. Match: Once signs are fixed, rows are sorted lexicographically to resolve the permutation ambiguity, yielding a unique canonical matrix.
• Extension: For graphs with repeated eigenvalues (non-simple spectrum), PRiSM is extended heuristically. It applies the base procedure to the simple-spectrum block ($m=1$) and uses QR decomposition and pivot selection to resolve higher-order eigenspaces ($m > 1$).

3. Theoretical Guarantees

• Completeness: PRiSM is proven to be a valid canonicalization, meaning it produces the same output for isomorphic graphs and different outputs for non-isomorphic simple-spectrum graphs.
• Universal Approximation: By composing PRiSM with a universal set network (e.g., DeepSets or Transformers), the resulting model achieves universal approximation for any isomorphism-invariant function on simple-spectrum graphs. This resolves the open problem of achieving completeness for spectral GNNs on this class.

Key Results

Theoretical Findings

• Theorem 1: For every natural number $k$, there exist non-isomorphic simple-spectrum multigraphs with $\Theta(k)$ nodes that are not distinguished by the $k$-WL algorithm. This implies that all $k$-WL-aligned GNN families (including PPGN, $k$-GNNs, and Graph Transformers) are incomplete on simple-spectrum graphs.
• Theorem 2: PRiSM provides a valid canonicalization for simple-spectrum eigendecompositions.
• Theorem 3: Models composed of PRiSM and universal set networks achieve universal approximation on simple-spectrum graphs.

Empirical Performance

The authors evaluated PRiSM on three benchmarks:

1. BREC Expressivity Benchmark: PRiSM outperformed competing canonicalizations (MAP, OAP) in distinguishing non-isomorphic graph pairs, particularly on Regular and Extension categories. It correctly distinguished 212/360 pairs compared to 199/360 for MAP/OAP.
2. Molecular Property Prediction (ZINC, OGB-Mol): PRiSM achieved state-of-the-art or tied-best performance on molecular regression (ZINC) and classification (MOLTOX21, MOLPCBA) tasks using both GatedGCN and PNA backbones.
3. Transformer Backbones (OGB, Alchemy): When used as a positional encoding for Graph Transformers, PRiSM outperformed all baselines (LPE, MAP, OAP) across all four datasets (MOLHIV, MOLCLINTOX, MOLBBBP, ALCHEMY). The authors attribute this to PRiSM providing a deterministic vertex ordering in addition to sign-corrected eigenvectors, which is crucial for Transformer attention mechanisms.

Significance and Claims

The paper claims to resolve a fundamental gap in the theoretical understanding of GNN expressivity and spectral methods:

1. Incompleteness of WL: It definitively proves that the WL hierarchy, despite its increasing power, cannot distinguish all simple-spectrum graphs, a class where isomorphism is theoretically easy.
2. First Complete Canonicalization: PRiSM is presented as the first provably complete sign canonicalization for simple-spectrum eigendecompositions, overcoming the limitations of previous methods like MAP and OAP which are incomplete on this class.
3. Universal Approximation: The work establishes that spectral GNNs can achieve universal approximation on simple-spectrum graphs if paired with a complete canonicalization like PRiSM, justifying the use of canonicalized Laplacian positional encodings.
4. Practical Utility: Empirically, the method demonstrates that resolving spectral ambiguities completely leads to tangible improvements in downstream tasks, outperforming existing sign-invariant and canonicalization approaches.

The authors note limitations, specifically that the completeness guarantee applies strictly to simple-spectrum graphs (or multigraphs constructed in the proof) and that the canonicalization procedure is discontinuous, a property they argue is mathematically unavoidable for complete sign canonicalizations. They also leave the extension of the incompleteness proof to simple combinatorial graphs (without multiple edges) as future work.