Nadav Dym

Finite Probes Suffice: Identifiability and Universality for Weight-Space Learning

Soutrik Sarangi, Yonatan Sverdlov, Adir Dayan +2

Learning properties of neural networks has recently attracted growing interest, with existing approaches operating either directly on network parameters or through probe-based repr…

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 $k$ , the $k$ -Weisfeiler-Leman ( $k$ -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…

Transport, Don't Generate: Deterministic Geometric Flows for Combinatorial Optimization

Benjy Friedmann, Nadav Dym

Recent advances in Neural Combinatorial Optimization (NCO) have been dominated by diffusion models that treat the Euclidean Traveling Salesman Problem (TSP) as a stochastic $N \tim…

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…

Short-Range Oversquashing

Yaaqov Mishayev, Yonatan Sverdlov, Tal Amir +1

Message Passing Neural Networks (MPNNs) are widely used for learning on graphs, but their ability to process long-range information is limited by the phenomenon of oversquashing. T…

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…

Quantitative Bounds for Sorting-Based Permutation-Invariant Embeddings

Nadav Dym, Matthias Wellershoff, Efstratios Tsoukanis +2

We study permutation-invariant embeddings of $d$ -dimensional point sets, which are defined by sorting $D$ independent one-dimensional projections of the input. Such embeddings aris…

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…

On the (Non) Injectivity of Piecewise Linear Janossy Pooling

Ilai Reshef, Nadav Dym

Multiset functions, which are functions that map multisets to vectors, are a fundamental tool in the construction of neural networks for multisets and graphs. To guarantee that the…

Fourier Sliced-Wasserstein Embedding for Multisets and Measures

Tal Amir, Nadav Dym

We present the Fourier Sliced-Wasserstein (FSW) embedding - a novel method to embed multisets and measures over $R^{d}$ into Euclidean space. Our proposed embedding approxim…

Bi-Lipschitz Ansatz for Anti-Symmetric Functions

Nadav Dym, Jianfeng Lu, Matan Mizrachi

Motivated by applications to the simulation of quantum many-body systems by neural networks, researchers have suggested several models which are antisymmetric by construction, and…

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…

Revisiting Multi-Permutation Equivariance through the Lens of Irreducible Representations

Yonatan Sverdlov, Ido Springer, Nadav Dym

This paper explores the characterization of equivariant linear layers for representations of permutations and related groups. Unlike traditional approaches, which address these pro…

On the Expressive Power of Sparse Geometric MPNNs

Yonatan Sverdlov, Nadav Dym

Motivated by applications in chemistry and other sciences, we study the expressive power of message-passing neural networks for geometric graphs, whose node features correspond to…

On the Hölder Stability of Multiset and Graph Neural Networks

Yair Davidson, Nadav Dym

Extensive research efforts have been put into characterizing and constructing maximally separating multiset and graph neural networks. However, recent empirical evidence suggests t…

Fourier Sliced-Wasserstein Embedding for Multisets and Measures

Tal Amir, Nadav Dym

We present the Fourier Sliced-Wasserstein (FSW) embedding - a novel method to embed multisets and measures over R^d into Euclidean space. Our proposed embedding approximately prese…

cs.LG2024★ 1 cited

Equivariant Frames and the Impossibility of Continuous Canonicalization

Nadav Dym, Hannah Lawrence, Jonathan W. Siegel

Canonicalization provides an architecture-agnostic method for enforcing equivariance, with generalizations such as frame-averaging recently gaining prominence as a lightweight and…

Weisfeiler Leman for Euclidean Equivariant Machine Learning

Snir Hordan, Tal Amir, Nadav Dym

The $k$ -Weisfeiler-Leman ( $k$ -WL) graph isomorphism test hierarchy is a common method for assessing the expressive power of graph neural networks (GNNs). Recently, GNNs whose expre…