20 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…
Monotone and Separable Set Functions: Characterizations and Neural Models
Soutrik Sarangi, Yonatan Sverdlov, Nadav Dym +1
Motivated by applications for set containment problems, we consider the following fundamental problem: can we design set-to-vector functions so that the natural partial order on se…
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…
Quantitative Bounds for Sorting-Based Permutation-Invariant Embeddings
Nadav Dym, Matthias Wellershoff, Efstratios Tsoukanis +2
We study permutation-invariant embeddings of -dimensional point sets, which are defined by sorting independent one-dimensional projections of the input. Such embeddings aris…
FSW-GNN: A Bi-Lipschitz WL-Equivalent Graph Neural Network
Yonatan Sverdlov, Yair Davidson, Nadav Dym +1
Famously, the ability of Message Passing Neural Networks (MPNN) to distinguish between graphs is limited to graphs separable by the Weisfeiler-Lemann (WL) graph isomorphism test, a…