# On the H"older Stability of Multiset and Graph Neural Networks

arXiv: https://arxiv.org/abs/2406.06984 · HTML: https://mlsanity.com/paper/2406.06984/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 35 of its 53 references that are in the map.
- First posted on arXiv 11 Jun 2024.

## Builds on (most cited first, 30 of 35)

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Neural Message Passing for Quantum Chemistry](https://mlsanity.com/paper/1704.01212/) (2017)
- [Deep Sets](https://mlsanity.com/paper/1703.06114/) (2017)
- [Strategies for Pre-training Graph Neural Networks](https://mlsanity.com/paper/1905.12265/) (2019)
- [Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networks](https://mlsanity.com/paper/1810.02244/) (2018)
- [Representation Learning on Graphs with Jumping Knowledge Networks](https://mlsanity.com/paper/1806.03536/) (2018)
- [Convolutional Networks on Graphs for Learning Molecular Fingerprints](https://mlsanity.com/paper/1509.09292/) (2015)
- [TUDataset: A collection of benchmark datasets for learning with graphs](https://mlsanity.com/paper/2007.08663/) (2020)
- [A Generalization of Transformer Networks to Graphs](https://mlsanity.com/paper/2012.09699/) (2020)
- [Residual Gated Graph ConvNets](https://mlsanity.com/paper/1711.07553/) (2017)
- [Graph Neural Networks with Learnable Structural and Positional Representations](https://mlsanity.com/paper/2110.07875/) (2021)
- [Long Range Graph Benchmark](https://mlsanity.com/paper/2206.08164/) (2022)
- [Equivariant Subgraph Aggregation Networks](https://mlsanity.com/paper/2110.02910/) (2021)
- [A Survey of Graph Neural Networks for Recommender Systems: Challenges, Methods, and Directions](https://mlsanity.com/paper/2109.12843/) (2021)
- [Stability Properties of Graph Neural Networks](https://mlsanity.com/paper/1905.04497/) (2019)
- [On the Limitations of Representing Functions on Sets](https://mlsanity.com/paper/1901.09006/) (2019)
- [Where Did the Gap Go? Reassessing the Long-Range Graph Benchmark](https://mlsanity.com/paper/2309.00367/) (2023)
- [FSPool: Learning Set Representations with Featurewise Sort Pooling](https://mlsanity.com/paper/1906.02795/) (2019)
- [A Short Tutorial on The Weisfeiler-Lehman Test And Its Variants](https://mlsanity.com/paper/2201.07083/) (2022)
- [Tree Mover's Distance: Bridging Graph Metrics and Stability of Graph Neural Networks](https://mlsanity.com/paper/2210.01906/) (2022)
- [word2vec, node2vec, graph2vec, X2vec: Towards a Theory of Vector Embeddings of Structured Data](https://mlsanity.com/paper/2003.12590/) (2020)
- [Low Dimensional Invariant Embeddings for Universal Geometric Learning](https://mlsanity.com/paper/2205.02956/) (2022)
- [Neural Injective Functions for Multisets, Measures and Graphs via a Finite Witness Theorem](https://mlsanity.com/paper/2306.06529/) (2023)
- [LiGNN: Graph Neural Networks at LinkedIn](https://mlsanity.com/paper/2402.11139/) (2024)
- [Fine-grained Expressivity of Graph Neural Networks](https://mlsanity.com/paper/2306.03698/) (2023)
- [Permutation Invariant Representations with Applications to Graph Deep Learning](https://mlsanity.com/paper/2203.07546/) (2022)
- [Group-invariant max filtering](https://mlsanity.com/paper/2205.14039/) (2022)

## Built on by (most cited first, 6 of 6)

- [On Universality Classes of Equivariant Networks](https://mlsanity.com/paper/2506.02293/) (2025)
- [Short-Range Oversquashing](https://mlsanity.com/paper/2511.20406/) (2025)
- [On the (Non) Injectivity of Piecewise Linear Janossy Pooling](https://mlsanity.com/paper/2505.20150/) (2025)
- [Energy Guided smoothness to improve Robustness in Graph Classification](https://mlsanity.com/paper/2412.08419/) (2024)
- [Monotone and Separable Set Functions: Characterizations and Neural Models](https://mlsanity.com/paper/2510.23634/) (2025)
- [Towards Metric-Faithful Neural Graph Matching](https://mlsanity.com/paper/2605.06588/) (2026)

## Abstract (arXiv)

Extensive research efforts have been put into characterizing and constructing maximally separating multiset and graph neural networks. However, recent empirical evidence suggests the notion of separation itself doesn't capture several interesting phenomena. On the one hand, the quality of this separation may be very weak, to the extent that the embeddings of "separable" objects might even be considered identical when using fixed finite precision. On the other hand, architectures which aren't capable of separation in theory, somehow achieve separation when taking the network to be wide enough. In this work, we address both of these issues, by proposing a novel pair-wise separation quality analysis framework which is based on an adaptation of Lipschitz and Holder stability to parametric functions. The proposed framework, which we name emphHolder in expectation, allows for separation quality analysis, without restricting the analysis to embeddings that can separate all the input space simultaneously. We prove that common sum-based models are lower-Holder in expectation, with an 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 Message Passing Neural Networks (MPNNs). To remedy this, we propose two novel MPNNs with improved separation quality, one of which is lower Lipschitz in expectation. We show these MPNNs can easily classify our adversarial examples, and compare favorably with standard MPNNs on standard graph learning tasks.