When designing neural networks for relational data, we routinely run into a fundamental mathematical wall. On one side sits expressivity: the model's capacity to distinguish between distinct topological structures, capture high-frequency details, and tell non-isomorphic graphs apart. On the other side sits stability: the model's ability to produce consistent representations when the underlying graph is subjected to noise, edge perturbations, or distribution shifts.
In standard Euclidean deep learning, we often enjoy both high capacity and robust generalization. In the graph domain, however, these two forces pull in opposite directions. If you make a Graph Neural Network (GNN) powerful enough to detect subtle structural nuances, it becomes hyper-sensitive to tiny topological changes. If you force it to be stable against noise, it becomes blind to complex patterns. Understanding why this trade-off occurs—and how to navigate it—is central to modern graph representation learning.
Why Expressivity Breeds Instability
To understand why this tension exists, we can look at how models attempt to bypass the structural limitations of standard message-passing GNNs (which cannot distinguish certain non-isomorphic graphs beyond the 1-Weisfeiler-Leman limit). Two common strategies for maximizing expressivity are Positional Encodings (PEs) derived from Laplacian eigenvectors, and Graph Canonization. Both reveal how extreme discriminative power inherently invites fragility.
The Spectral View: Eigenvector Sensitivity
To give a GNN a sense of global geometry, researchers often inject the top $k$ eigenvectors of the graph Laplacian as node features. As Yinan Huang et al. explain, a fundamental trade-off exists here: increasing the number of spectral features allows for more detailed structural representations, but it simultaneously makes the model highly sensitive to small perturbations.
Why does this happen? The spectrum of a graph Laplacian is notoriously brittle. A single added or deleted edge can cause eigenvalues to shift and eigenvectors to flip or rotate. If a model relies heavily on these eigenvectors to distinguish complex structures, a minor topological perturbation will radically alter the input space. As a result, Jiajun Zhu et al. demonstrate that this sensitivity causes severe performance degradation when transferring Graph Foundation Models across domains, as the model perceives slightly different topologies as entirely unrelated spaces.
The Combinatorial View: The Chaos of Canonization
An alternative way to achieve maximum expressivity is graph canonization, which labels nodes based on a rigid, deterministic structural ordering. While this completely solves the problem of structural discriminability, Zehao Dong et al. show that standard canonization algorithms introduce massive instability.
[Graph A] ---> Canonization ---> Node Order: 1, 2, 3, 4
|
(Add 1 Edge)
v
[Graph B] ---> Canonization ---> Node Order: 4, 1, 3, 2 (Complete Shuffle!)
Because the canonization mapping is discontinuous, a minor perturbation to a single edge can completely shuffle the node encodings. The neural network is forced to view two nearly identical graphs as completely distinct entities, destroying its ability to generalize.
The Sampling Noise and Dissipation Dilemma
The stability-expressivity trade-off also manifests during optimization and scaling. When a graph model is highly expressive, it possesses the mathematical freedom to fit highly complex patterns. However, Chen Cai et al. discovered that highly expressive architectures (like Invariant Graph Networks) often fail to converge on discrete 0-1 graphs. Instead of learning the underlying continuous probability distribution of the graph, the model's high sensitivity causes it to overfit to the random sampling noise of individual edges.
Conversely, trying to enforce stability through aggressive smoothing or low-pass filtering creates the opposite problem. As Fernando Gama demonstrates using diffusion scattering transforms, while low-pass operators like average neighborhood pooling are perfectly stable against node permutations, they fail to capture the high-frequency details necessary for discriminative tasks.
Furthermore, trying to preserve information over long distances often breaks numerical stability. As Alessio Gravina et al. note, deep graph architectures constantly struggle with a trade-off between numerical stability and information preservation: systems either suffer from exploding gradients or dissipate the signal entirely over successive layers. This challenge scales poorly; Mohammad Sabbaqi et al. show that a model's sensitivity to structural noise increases proportionally with both the size of the spatial network and the length of the temporal window.
Designing for the Pareto Frontier
How do we build graph models that sit on an optimal trade-off between expressivity and stability? Recent architectures achieve this by introducing structural constraints that bound stability constants without sacrificing representational capacity.
1. Smooth Spectral Augmentation
Instead of raw Laplacian eigenvectors, Junru Zhou et al. propose a framework called OGE-Aug. By combining orthogonal group equivariant layers with a "smooth" approach to processing eigenvalues, they create a representation that is theoretically capable of distinguishing non-isomorphic graphs while remaining provably stable against structural perturbations. The smoothness dampens the chaotic shifts caused by edge noise.
2. Isolating Filter Selectivity
Can we enjoy the benefits of deep aggregation without the stability penalty? Alejandro Parada-Mayorga et al. analyzed Aggregation Graph Neural Networks (Agg-GNNs) and proved a surprising mathematical property: the stability of the entire network is determined solely by the filters in the first layer. This allows subsequent layers to remain highly selective and expressive without causing the entire system's stability constant to explode.
3. Explicit Multi-Objective Optimization
Rather than hoping stability emerges naturally, frameworks can optimize for it directly. Yuangang Pan et al. introduce architectures that explicitly balance "stability" (invariance to slight input changes) and "identifiability" (the ability to distinguish nodes with different underlying structures) alongside traditional smoothness criteria.
Similarly, in spatial learning, Xiuyuan Cheng et al. utilize low-rank learnable local filters to bridge the gap between spatial and spectral methods, preventing the overfitting typical of high-capacity spatial layers on irregular grids.
4. Removing Excess Parameters
Sometimes, less is more. In shallow architectures designed for cross-graph tasks like entity alignment, Max Berrendorf et al. discovered that including learnable transformation weights can paradoxically reduce accuracy. Eliminating these weights and relying on weightless neighborhood aggregation stabilizes the cross-graph embedding space, proving that constraining a model's expressivity can directly prevent it from fracturing under structural variations.
Ultimately, navigating the stability-expressivity trade-off requires moving away from the philosophy of "maximum expressivity at all costs." By understanding where structural noise enters our models—whether through eigenvector flips, canonization shuffles, or edge sampling noise—we can design targeted mathematical constraints that keep graph representations stable, robust, and discriminative.
Key Foundational Work
Graph Convolution with Low-rank Learnable Local Filters (2021) — contributed 1 concept elements to this direction.
Diffusion Scattering Transforms on Graphs (2019) — contributed 1 concept elements to this direction.
Knowledge Graph Entity Alignment with Graph Convolutional Networks: Lessons Learned (2019) — contributed 1 concept elements to this direction.