Skip to content (access key 's')
Logo of Technion
Logo of CS Department
Logo of CS4People
Events

The Taub Faculty of Computer Science Events and Talks

On the Hölder Stability of Multiset and Graph Neural Networks
event speaker icon
Yair Davidson (M.Sc. Thesis Seminar)
event date icon
Tuesday, 30.07.2024, 10:00
event speaker icon
Advisor: Dr. Nadav Dym

Famously, multiset neural networks based on sum-pooling can separate all distinct multisets, and as a result can be used by message passing neural networks (MPNNs) to separate all pairs of graphs that can be separated by the 1-WL graph isomorphism test. 
However, the quality of this separation may be very weak, to the extent that the embeddings of "separable" multisets and graphs might even be considered identical when using fixed finite precision.

In this work, we propose to fully analyze the separation quality of multiset models and MPNNs via a novel adaptation of Lipschitz and Hölder continuity to parametric functions. 
We prove that common sum-based models are lower-Hölder continuous, with a Hölder exponent that decays rapidly with the network's depth. 
Our analysis leads to adversarial examples of graphs which can be separated by three 1-WL iterations, but cannot be separated in practice by standard maximally powerful MPNNs. 
To remedy this, we propose two novel MPNNs with improved separation quality, one of which is lower Lipschitz continuous. 
We show these MPNNs can easily classify our adversarial examples, and compare favorably with standard MPNNs on standard graph learning tasks.