  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\"{o}lder continuity
to parametric functions. We prove that common sum-based models are
lower-H\"{o}lder continuous, with a H\"{o}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.
