Introduction
Theoretical "separability" in Graph Neural Networks (GNNs) doesn't always guarantee practical performance. If two distinct graphs result in nearly identical embeddings, a computer's finite precision will treat them as the same. This paper introduces a framework called Hölder stability in expectation to measure the quality of separation and proposes SortMPNN, a novel architecture that maintains high separation quality even as networks get deeper.
The Gap Between Theory and Practice
In the world of Graph Neural Networks, the "gold standard" for expressive power is the 1-dimensional Weisfeiler-Lehman (1-WL) isomorphism test. If a GNN is "maximally expressive," it should be able to distinguish any two graphs that the 1-WL test can.
However, the authors point out a major gap between theory and practice:
- Weak Separation: Even if a network can theoretically separate two graphs, the resulting embeddings might be so close (e.g., a difference of $10^{-15}$) that they are indistinguishable on a standard computer.
- The Depth Trap: As Message Passing Neural Networks (MPNNs) get deeper, the quality of this separation often collapses, making it nearly impossible for the model to learn to classify different structures.
The paper seeks to quantify this "separation quality" using mathematical stability tools—specifically Hölder and Lipschitz continuity—to understand why standard models fail on certain tasks and how to build better ones.
Methods and Innovations
The authors propose a probabilistic framework called Hölder stability in expectation. Instead of requiring a network to separate all possible inputs perfectly (which is often impossible), they measure the expected distance between embeddings relative to the distance between the input objects.
- Mathematical Analysis: They prove that standard sum-based aggregators (like those in GIN) have a "lower-Hölder exponent" that decays rapidly with depth. This means the deeper the network, the more "squashed" the embeddings become.
- SortMPNN: They introduce an MPNN variant where the aggregation step involves sorting node features. They prove this architecture is lower Lipschitz in expectation (an exponent of $\alpha=1$), meaning it preserves distances much better than sum-based models.
- AdaptMPNN: They propose an "Adaptive ReLU" summation that adjusts its bias based on the range of features in the multiset, helping to mitigate the vanishing separation issue found in standard ReLUs.
Key Insights
- Smoothness is a Double-Edged Sword: Surprisingly, while smooth activations (like Sigmoid or Tanh) make a network theoretically injective (capable of unique mapping), they actually result in worse separation quality than ReLU. The Hölder exponent for smooth activations depends on the number of elements $n$, leading to extremely poor practical separation.
- The Power of Sorting: Sorting is often overlooked in GNNs due to computational cost or non-differentiability concerns. However, this paper shows that sorting provides the most stable separation quality (Lipschitz stability), which is crucial for robust learning.
- Width vs. Depth: While increasing network width can help "theoretical" non-separable networks achieve separation in practice, it doesn't fix the fundamental decay in separation quality caused by depth.
Experimental Results
The paper evaluates these concepts using a mix of adversarial and standard benchmarks, including TUdatasets, LRGB (Long Range Graph Benchmark), and ZINC12K. To specifically test separation quality, they introduce $\epsilon$-Trees, a newly constructed adversarial dataset of pairs of trees that are easily separated by 1-WL but cause standard MPNNs to produce nearly identical embeddings.
- Adversarial Success: On the $\epsilon$-Tree dataset, standard models like GIN and GCN failed completely (50% accuracy, equivalent to random guessing). In contrast, SortMPNN and AdaptMPNN achieved 100% accuracy, proving that separation quality is a bottleneck for standard architectures.
- Benchmark Performance: SortMPNN and AdaptMPNN consistently outperformed or matched standard MPNNs on TUdatasets.
- Efficiency in Scale: On the LRGB
peptides-functask, SortMPNN achieved the highest Average Precision (0.6940). Interestingly, the advantage of SortMPNN became even more pronounced as the model size (parameter budget) was reduced, suggesting it is more "feature-efficient." - ZINC12K: When used as a backbone for ESAN, SortMPNN outperformed the standard GIN backbone in 5 out of 8 tested scenarios.
Limitations and Future Work
- Augmentation Knowledge: SortMPNN requires prior knowledge of the maximum multiset size to perform proper "augmentation" (padding with a "blank" vector), which might not always be known in dynamic graph settings.
- Computational Cost: Sorting is marginally slower than simple summation. While the authors note it's only about 1.1x to 1.8x slower than GCN, this could scale poorly on massive graphs.
- Metric Expansion: The current analysis relies heavily on the Tree Mover’s Distance (TMD). Future work could explore Hölder stability with respect to other graph metrics.
- Training Dynamics: The study focuses primarily on stability at initialization. Exploring how these properties evolve during the training process remains an open question.
Summary updated