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

CREATORSnir Hordan, Nadav Dym, Tim Seppelt
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE149507
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.23446

Browse the full library · About the Tower of Babel