Graph neural networks are commonly analyzed through their ability to distinguish non-isomorphic graphs. In this talk, I will study two complementary aspects of this question, moving from binary expressivity to quantitative separation.

First, I will consider message-passing neural networks for geometric graphs. For generic node positions, we characterize exactly which sparse geometric graphs can be identified by invariant and equivariant architectures. We show that invariant models can identify precisely the generically globally rigid graphs, whereas equivariant models can identify every connected graph. We also present EGenNet, an equivariant architecture that generically achieves this maximal expressive power. In the second part, I will argue that distinguishability alone is not sufficient: two graphs may receive different representations while being mapped arbitrarily close to one another. Motivated by long-range message-passing tasks, we introduce FSW-GNN, which uses bi-Lipschitz multiset embeddings for neighborhood aggregation. We construct a pseudometric whose zero set coincides with 1-WL equivalence and show that FSW-GNN is both 1-WL equivalent and bi-Lipschitz with respect to this metric. Empirically, this improved quantitative separation leads to substantially better performance on long-range graph tasks.   Advisor: Dr. Nadav Dym