Weisfeiler–Leman Is Incomplete on Simple Spectrum Graphs, so Canonicalize Them
Snir Hordan, Nadav Dym, Tim Seppelt · 2026
Read Weisfeiler–Leman Is Incomplete on Simple Spectrum Graphs, so Canonicalize Them by Snir Hordan, Nadav Dym, Tim Seppelt (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-23446.txt.
Introduction
Hordan, Dym, and Seppelt prove that the Weisfeiler-Leman test cannot tell apart all non-isomorphic graphs with a simple spectrum, no matter how high its order k runs. Since that test caps the power of widely used graph neural networks, the gap hits every such network family. Their PRiSM method, short for Partition, Refine, Solve, Match, gives the first provably complete canonicalization of simple-spectrum eigendecompositions. Paired with DeepSets or a Transformer, it achieves universal approximation on these graphs, and tests match or beat prior spectral methods.
Catalog record
| CREATOR | Snir Hordan, Nadav Dym, Tim Seppelt |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 149507 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.23446