{"id":"arxiv/2605.23446","url":"https://arxiv.org/abs/2605.23446","tags":["cs.LG","math.CO"],"score":0,"title":"Weisfeiler-Leman Is Incomplete on Simple Spectrum Graphs, so Canonicalize Them","domain":"cs.LG","source":"arxiv","authors":["Snir Hordan","Nadav Dym","Tim Seppelt"],"reviews":0,"subject":"cs.LG","summary":"Graphs with a simple spectrum admit cubic-time isomorphism testing, yet we prove that for every natural number $k$, the $k$-Weisfeiler-Leman ($k$-WL) test cannot distinguish all non-isomorphic graphs with a simple spectrum. As the WL hierarchy upper-bounds the distinguishing power of widely-used Graph Neural Networks (GNNs), this incompleteness applies to all such GNNs, ruling out completeness for every $k$-WL-aligned GNN family. To close this gap, we introduce PRiSM (Partition, Refine, Solve, Match), the first provably complete canonicalization of simple-spectrum eigendecompositions. PRiSM…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-05-22","reactions":{}}