Research map / Graph learning / GNN architectures
On the Hölder Stability of Multiset and Graph Neural Networks
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Introduces "Hölder in expectation" stability analysis for parametric permutation-invariant functions and MPNNs, showing sort-based aggregation (SortMPNN) is bi-Lipschitz in expectation while sum-based ReLU/smooth MPNNs have deteriorating lower-Hölder exponents with depth.
Problem
Existing separation guarantees for multiset and graph neural networks (MPNNs) say nothing about separation quality; embeddings of theoretically separable objects can be nearly identical in finite precision, and sum-based models have unclear lower-Lipschitz/Hölder stability.
Approach
Define lower-Hölder stability in expectation over random parameters (rather than uniformly), prove exponents for ReLU-sum, smooth-sum, adaptive ReLU, and sort-based multiset functions, lift these to MPNNs w.r.t. the Tree Mover's Distance, and propose SortMPNN, which is lower-Lipschitz in expectation even at width 1.
Key results
- SortMPNN and AdaptMPNN reach 1.0 accuracy on the epsilon-Tree binary classification task, while GIN, GCN, GAT, ReluMPNN and SmoothMPNN stay at 0.5.
- On TUDatasets SortMPNN reaches 90.99% on MUTAG and 83.55% on NCI1, outperforming GIN (89.4% and 82.7%).
- On ZINC12K with ESAN, SortMPNN beats GIN in five of eight settings, e.g. DS-GNN (EGO) MAE 0.104 vs 0.126 for GIN.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use SortMPNN instead of standard MPNNs or sum-based MPNNs | ε-Tree binary classification · ε-Tree | accuracy: 0.5 -> 1.0 | Helped |
| Use AdaptMPNN instead of standard MPNNs or sum-based MPNNs | ε-Tree binary classification · ε-Tree | accuracy: 0.5 -> 1.0 | Helped |
| Replace GIN with SortMPNN | TU graph classification · Mutag | accuracy: 89.4$\pm$5.6 -> 90.99$\pm$6.2 | Helped |
| Replace GIN with AdaptMPNN | TU graph classification · Proteins | accuracy: 76.2$\pm$2.8 -> 75.12$\pm$3.64 | Hurt |
| Replace GIN with SortMPNN | TU graph classification · Proteins | accuracy: 76.2$\pm$2.8 -> 76.46$\pm$3.68 | Helped |
| Replace GIN with SortMPNN | TU graph classification · PTC | accuracy: 64.6$\pm$7 -> 66.31$\pm$6.73 | Helped |
| Replace GIN with AdaptMPNN | TU graph classification · PTC | accuracy: 64.6$\pm$7 -> 66.87$\pm$5.37 | Helped |
| Replace GIN with SortMPNN | TU graph classification · NCI1 | accuracy: 82.7$\pm$1.7 -> 83.55$\pm$1.82 | Helped |
| Replace GIN with AdaptMPNN | TU graph classification · NCI109 | accuracy: 82.2$\pm$1.6 -> 83.26$\pm$0.86 | Helped |
| Use SortMPNN instead of GCN | LRGB graph classification · peptides-func | AP: 0.6860$\pm$0.0050 -> 0.6940$\pm$0.0049 | Helped |
| Use AdaptMPNN instead of GCN | LRGB graph classification · peptides-func | AP: 0.6860$\pm$0.0050 -> 0.6934$\pm$0.0099 | Helped |
| Use SortMPNN instead of GCN | LRGB graph regression · peptides-struct | MAE: 0.2460$\pm$0.0007 -> 0.2464$\pm$0.0024 | Hurt |
Surprising findings
- Sum-based ReLU and smooth-activation MPNNs fail completely (0.5 accuracy) on the epsilon-Tree task despite being theoretically able to separate those graphs.
- The authors found and corrected an error in a previous version's claim that lower-Hölder-in-expectation properties compose through MPNN layers.
Limitations
- SortMPNN requires prior knowledge of maximal multiset size for augmentation.
- Lower-Hölder guarantees for wide ReluMPNN are conjectured but not proven.
- Analysis is with respect to TMD, not other graph metrics.
Experimental setup
Datasets: TUDatasets LRGB peptides-func LRGB peptides-struct ZINC12K epsilon-Tree dataset
Benchmarks: epsilon-Tree binary classification TUDatasets peptides-func peptides-struct ZINC12K
Metrics: accuracy AP MAE embedding distance vs TMD scaling exponent
Baselines: GIN GCN GAT GraphSage GINE GatedGCN ReluMPNN SmoothMPNN
Builds on: GIN Tree Mover's Distance Deep Sets
Closest papers by meaning
- On the Stability of Graph Convolutional Neural Networks: A Probabilistic Perspective (NeurIPS 2025 · similarity 0.86)
- Almost Surely Asymptotically Constant Graph Neural Networks (NeurIPS 2024 · similarity 0.85)
- On Vanishing Gradients, Over-Smoothing, and Over-Squashing in GNNs: Bridging Recurrent and Graph Learning (NeurIPS 2025 · similarity 0.85)
- Higher-Order Graphon Neural Networks: Approximation and Cut Distance (ICLR 2025 · similarity 0.85)
- On the Expressive Power of Sparse Geometric MPNNs (ICLR 2025 · similarity 0.85)
- Separation Power of Equivariant Neural Networks (ICLR 2025 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.