Cover Image

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

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Hordan, Snir, Dym, Nadav, Seppelt, Tim
Format:	Preprint
Published:	2026
Subjects:	Machine Learning Combinatorics
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Weisfeiler Leman for Euclidean Equivariant Machine Learning
by: Hordan, Snir, et al.
Published: (2024)

Spectral Graph Neural Networks are Incomplete on Graphs with a Simple Spectrum
by: Hordan, Snir, et al.
Published: (2025)

Complete Neural Networks for Complete Euclidean Graphs
by: Hordan, Snir, et al.
Published: (2023)

When and How to Canonize: A Generalization Perspective
by: Sverdlov, Yonatan, et al.
Published: (2026)

Quantitative Approximation Rates for Group Equivariant Learning
by: Siegel, Jonathan W., et al.
Published: (2026)

Equivariant Frames and the Impossibility of Continuous Canonicalization
by: Dym, Nadav, et al.
Published: (2024)

Aligning Transformers with Weisfeiler-Leman
by: Müller, Luis, et al.
Published: (2024)

On the Power of the Weisfeiler-Leman Test for Graph Motif Parameters
by: Lanzinger, Matthias, et al.
Published: (2023)

An Upper Bound on the Weisfeiler-Leman Dimension
by: Schneider, Thomas, et al.
Published: (2024)

On the Hölder Stability of Multiset and Graph Neural Networks
by: Davidson, Yair, et al.
Published: (2024)

Weisfeiler and Leman Go Loopy: A New Hierarchy for Graph Representational Learning
by: Paolino, Raffaele, et al.
Published: (2024)

On the Weisfeiler-Leman dimension of circulant graphs
by: Wu, Yulai, et al.
Published: (2024)

Weisfeiler-Leman on graphs of small twin-width
by: Heinrich, Irene, et al.
Published: (2026)

A lower bound for the Weisfeiler-Leman dimension of circulant graphs
by: Wu, Yulai, et al.
Published: (2025)

Weisfeiler and Leman Follow the Arrow of Time: Expressive Power of Message Passing in Temporal Event Graphs
by: Heeg, Franziska, et al.
Published: (2025)

Logarithmic Weisfeiler--Leman and Treewidth
by: Levet, Michael, et al.
Published: (2023)

Weisfeiler and Leman Go Gambling: Why Expressive Lottery Tickets Win
by: Kummer, Lorenz, et al.
Published: (2025)

Empowering GNNs via Edge-Aware Weisfeiler-Leman Algorithm
by: Liu, Meng, et al.
Published: (2022)

Weisfeiler-Leman at the margin: When more expressivity matters
by: Franks, Billy J., et al.
Published: (2024)

Distinguishing Graphs by Counting Homomorphisms from Sparse Graphs
by: Neuen, Daniel, et al.
Published: (2026)

Distance-Restricted Folklore Weisfeiler-Leman GNNs with Provable Cycle Counting Power
by: Zhou, Junru, et al.
Published: (2023)

Fourier Sliced-Wasserstein Embedding for Multisets and Measures
by: Amir, Tal, et al.
Published: (2024)

Weisfeiler and Leman Go Measurement Modeling: Probing the Validity of the WL Test
by: Subramonian, Arjun, et al.
Published: (2023)

Fine-Grained Expressive Power of Weisfeiler-Leman: A Homomorphism Counting Perspective
by: Zhou, Junru, et al.
Published: (2024)

Beyond Weisfeiler-Lehman: A Quantitative Framework for GNN Expressiveness
by: Zhang, Bohang, et al.
Published: (2024)

Bounding the Weisfeiler-Leman Dimension via a Depth Analysis of I/R-Trees
by: Kiefer, Sandra, et al.
Published: (2024)

Fourier Sliced-Wasserstein Embedding for Multisets and Measures
by: Amir, Tal, et al.
Published: (2025)

On the (Non) Injectivity of Piecewise Linear Janossy Pooling
by: Reshef, Ilai, et al.
Published: (2025)

On the Expressive Power of Sparse Geometric MPNNs
by: Sverdlov, Yonatan, et al.
Published: (2024)

An Algorithmic Meta Theorem for Homomorphism Indistinguishability
by: Seppelt, Tim
Published: (2024)

Logical Equivalences, Homomorphism Indistinguishability, and Forbidden Minors
by: Seppelt, Tim
Published: (2023)

A method for the systematic generation of graph XAI benchmarks via Weisfeiler-Leman coloring
by: Fontanesi, Michele, et al.
Published: (2025)

Canonizing Graphs of Bounded Rank-Width in Parallel via Weisfeiler--Leman
by: Levet, Michael, et al.
Published: (2023)

Lasserre Hierarchy for Graph Isomorphism and Homomorphism Indistinguishability
by: Roberson, David E., et al.
Published: (2023)

FSW-GNN: A Bi-Lipschitz WL-Equivalent Graph Neural Network
by: Sverdlov, Yonatan, et al.
Published: (2024)

Revisiting Multi-Permutation Equivariance through the Lens of Irreducible Representations
by: Sverdlov, Yonatan, et al.
Published: (2024)

Theoretical Insights into Line Graph Transformation on Graph Learning
by: Yang, Fan, et al.
Published: (2024)

Incomplete U-Statistics of Equireplicate Designs: Berry-Esseen Bound and Efficient Construction
by: Miglioli, Cesare, et al.
Published: (2025)

Transport, Don't Generate: Deterministic Geometric Flows for Combinatorial Optimization
by: Friedmann, Benjy, et al.
Published: (2026)

Invariant-Based Diagnostics for Graph Benchmarks
by: von Moos, Richard, et al.
Published: (2026)