4 papers
Weisfeiler-Leman Is Incomplete on Simple Spectrum Graphs, so Canonicalize Them
Snir Hordan, Nadav Dym, Tim Seppelt
Graphs with a simple spectrum admit cubic-time isomorphism testing, yet we prove that for every natural number , the -Weisfeiler-Leman (-WL) test cannot distinguish all no…
When and How to Canonize: A Generalization Perspective
Yonatan Sverdlov, Benjamin Friedman, Snir Hordan +1
While invariant architectures are standard for processing symmetric data, there is growing interest in achieving invariance by applying group averaging or canonization to non-invar…
Quantitative Approximation Rates for Group Equivariant Learning
Jonathan W. Siegel, Snir Hordan, Hannah Lawrence +2
The universal approximation theorem establishes that neural networks can approximate any continuous function on a compact set. Later works in approximation theory provide quantitat…
Spectral Graph Neural Networks are Incomplete on Graphs with a Simple Spectrum
Snir Hordan, Maya Bechler-Speicher, Gur Lifshitz +1
Spectral features are widely incorporated within Graph Neural Networks (GNNs) to improve their expressive power, or their ability to distinguish among non-isomorphic graphs. One po…