Stability-Shaped Deep Graph Learning

Junyou Zhu; Langzhou He; Fenying Cai; Christian Nauck; Ping Xiong; Chao Gao; Philip S. Yu; Klaus-Robert Müller

cs.LGOct 5, 2026

Stability-Shaped Deep Graph Learning

Authors: Junyou Zhu, Langzhou He, Fenying Cai, Christian Nauck, Ping Xiong, Chao Gao, Philip S. Yu, Klaus-Robert Müller, +2 more

Organizations: Department of Complexity Science, Potsdam Institute for Climate Impact Research, 14473 Potsdam, Germany · Machine Learning Group, Technical University of Berlin, 10587 Berlin, Germany · Department of Computer Science, University of Illinois at Chicago, Chicago, IL 60607, USA · School of Artificial Intelligence, Optics and Electronics (iOPEN), Northwestern Polytechnical University, Xi’an 710072, China · Berlin Institute for the Foundations of Learning and Data (BIFOLD), 10587 Berlin, Germany · Department of Artificial Intelligence, Korea University, Seoul 136-713, South Korea · Max Planck Institute for Informatics, 66123 Saarbrücken, Germany · Research Institute of Intelligent Complex Systems, Fudan University, Shanghai 200433, China · Department of Physics, Humboldt University Berlin, 12489 Berlin, Germany

Abstract

In deep graph neural networks, increasing depth enlarges the receptive field but often leads to over-smoothing, where node representations tend to align. We develop a unified, mode-wise stability framework for deep GNN propagation that provides a principled characterization of over-smoothing. By interpreting layer depth as time and layer updates as graph-coupled dynamics, over-smoothing can be understood as an undesirable dynamical synchronization of features, for which the master stability curve provides a theoretical tool to assess the stability of synchrony. Guided by this theory, we further propose Stability-Shaped Deep Graph Learning (SDGL) to mitigate over-smoothing in deep GNNs. SDGL has two complementary instantiations: one induces controlled Turing instability to replace synchronization with spatial pattern formation, and the other maintains stable near-critical propagation. Experiments on diverse node- and graph-level benchmarks demonstrate the improved depth scaling and consistent accuracy gains over strong baselines, including graphs exhibiting long-range dependencies.

Figures & tables

Fig. 1: (a) Over-smoothing as synchronization: node representations $\mathbf{H}$ collapse toward a shared state and deviations from synchrony shrink in the middle panel. (b) Our master-stability view: the curve $\Lambda(\mu)$ shows how each graph frequency $\mu$ is damped or amplified. Heat-kernel diffusion is strongly contractive at high frequencies (I), our SDGL-DI opens a band-limited amplification window (II), and SDGL-NC remains stable but near-critical (III).

Fig. 2: Overview of our theory. (a) A deep GNN can be viewed as local update $f$ coupled by graph mixing $\mathbf{G}$ . (b) We study over-smoothing by tracking the deviation from an all-nodes-equal state $\mathbf{H}^{\star}$ : $\Delta\mathbf{H}(t)=\mathbf{H}(t)-\mathbf{H}^{\star}$ ; over-smoothing means $\|\Delta\mathbf{H}(t)\|\to 0$ as depth grows. (c) Linearizing at $\mathbf{H}^{\star}$ and diagonalizing $\mathbf{G}$ turn the coupled system into independent graph-frequency modes $\dot{\bm{\xi}}_{k}=(\mathbf{J}-\mu_{k}\mathbf{C})\bm{\xi}_{k}$ . (d) The master stability curve $\Lambda(\mu)$ predicts per-mode growth/decay and highlights three behaviors: (I) strong decay (diffusion over-smoothing), (II) band-limited growth (patterning), and (III) weak decay (near-critical, deep but stable).

Fig. 3: Qualitative dynamics analysis. Starting from random noise, we run $150$ layers and visualize the resulting scalar field with a shared color scale. GCN collapses toward a near-constant field (over-smoothing). Our SDGL-DI produces sharp Turing-like patterns via diffusion-induced instability. SDGL-NC preserves non-trivial variation under stable near-critical propagation.

Dataset	Cora	CiteSeer	PubMed	Coauthor-CS	Computers	Photo
GAT	$83.03\pm 0.72$	$72.53\pm 0.54$	$79.0\pm 0.30$	$89.51\pm 0.54$	$86.90\pm 0.32$	$92.56\pm 0.40$
GCN	$81.53\pm 0.53$	$70.32\pm 0.58$	$79.04\pm 0.37$	$90.98\pm 0.42$	$86.49\pm 0.51$	$92.42\pm 0.23$
GraphSAGE	$79.37\pm 1.70$	$67.31\pm 1.63$	$75.52\pm 2.19$	$90.62\pm 0.42$	$76.42\pm 7.60$	$88.71\pm 2.68$
SAN	$77.98\pm 1.31$	$66.30\pm 0.88$	$74.68\pm 0.81$	$94.51\pm 0.15$	$89.93\pm 0.16$	$94.86\pm 0.10$
GTN	$78.60\pm 1.72$	$68.80\pm 1.69$	$76.90\pm 0.77$	$-$	$-$	$-$
GRAND	$82.83\pm 1.31$	$70.26\pm 1.46$	$78.89\pm 1.96$	$90.10\pm 0.78$	$82.79\pm 0.54$	$91.51\pm 0.41$

TABLE I: Classification accuracy (%) on homophilic datasets. We report mean

\pm

std. Best in bold, second-best underlined. “–” denotes data that is out of memory or not included in the original paper

Dataset	#V	#E	#Features	#Classes
Transductive node classification
Cora	2,708	10,556	1,433	7
CiteSeer	3,327	9,104	3,703	6
PubMed	19,717	88,648	500	3
Amazon-Computers	13,752	491,722	767	10
Amazon-Photo	7,650	238,162	745	8

TABLE II: Dataset statistics. For node classification, we report the number of nodes (#V), edges (#E), input feature dimension, and classes. For FakeNewsNet graph classification, we report the corresponding statistics after preprocessing.

Dataset	Actor	Squirrel	Chameleon
GAT	$29.05\pm 0.80$	$30.08\pm 1.03$	$53.22\pm 1.56$
GCN	$28.38\pm 0.96$	$28.87\pm 1.55$	$49.32\pm 1.88$
GraphSAGE	$34.88\pm 1.19$	$36.90\pm 1.03$	$48.03\pm 2.22$
SAN	$32.94\pm 0.92$	$37.00\pm 1.28$	$51.80\pm 1.95$
GTN	$35.42\pm 1.50$	$36.45\pm 1.72$	$55.84\pm 4.08$
GCNII	$33.80\pm 1.41$	$38.74\pm 1.20$	$59.14\pm 3.49$

TABLE III: Classification accuracy (%) on heterophilic datasets. We report mean

\pm

std.

	Methods	ACC	Pre	Rec	F1
M1	CSI	0.734	0.672	0.550	0.688
	Bert-MLP	0.853	0.892	0.833	0.825
	SpaCy-MLP	0.375	0.124	0.136	0.272
	UniPF	0.760	0.783	0.800	0.754
	ChatGLM2-6B	0.856	0.847	0.856	0.850
M2	GCN	0.833	0.958	0.766	0.831

TABLE IV: Performance comparison on PolitiFact (M1: Content-based, M2: Propagation-structure-based methods).

	Methods	ACC	Pre	Rec	F1
M1	CSI	0.866	0.892	0.840	0.866
	Bert-MLP	0.962	0.968	0.954	0.961
	SpaCy-MLP	0.501	0.498	0.534	0.333
	UniPF	0.933	0.932	0.933	0.932
	ChatGLM2-6B	0.892	0.902	0.892	0.892
M2	GCN	0.957	0.931	0.984	0.957

TABLE V: Performance comparison on GossipCop (M1: Content-based, M2: Propagation-structure-based methods).

Fig. 4: Accuracy as a function of layer number on two representative node classification benchmarks. (a) Homophilic dataset: Photo. (b) Heterophilic dataset: Chameleon. GCN and GAT degrade substantially as depth increases, whereas both SDGL variants remain stable and competitive even at 30–60 layers. This supports our claim that stability shaping improves depth scaling under both homophilic and heterophilic graph conditions.

Fig. 5: Depth evolution of Dirichlet energy

E(\mathbf{H}^{(n)})

in log scale from random initialization over 100 layers. GCN and GAT rapidly drive

E(\mathbf{H}^{(n)})

toward

0

, indicating over-smoothing, while our SDGL-NC keeps

E

nearly constant and our SDGL-DI increases

E

and then levels off, consistent with near critical propagation and band-limited amplification.

Fig. 6: Validation of near critical propagation. Spectral gain profiles of our SDGL-NC compared with a diffusion-only heat kernel on Actor and Cora. Left panels plot the spectral radius

\rho(T(\mu))

, and right panels plot the depth-amplified gain

\rho(T(\mu))^{L}

with

L=15

. Our SDGL-NC stays closer to the critical boundary

\rho=1

and retains substantially larger deep gain across frequencies, while the heat kernel rapidly suppresses nontrivial modes.

Layers	SDGL-NC (Ours)	SDGL-DI (Ours)	GCN	GAT
3	0.196	0.195	0.113	1.826
10	0.203	0.201	0.229	9.187
30	0.224	0.216	0.559	30.220
60	0.255	0.239	1.054	61.770

TABLE VI: Trainable parameter counts (in millions) as a function of depth on Photo. For all models, we fix the hidden width (and the number of attention heads for GAT) and vary only the number of propagation layers.

Appendix figures & tables1 asset

Supplementary material from the paper’s appendix.

Appendix

	SDGL-DI				SDGL-NC
Dataset	Number of layers $L$	$d$	Dropout $p$	$\mathrm{lr}$	Number of layers $L$	$d$	Dropout $p$	$\mathrm{lr}$
Node classification (homophilic)
Cora	15	128	0.39	0.0031	15	128	0.39	0.0094
CiteSeer	10	512	0.40	0.0026	8	64	0.40	0.0020
PubMed	10	256	0.36	0.0044	10	128	0.39	0.0031
Coauthor-CS	8	128	0.52	0.0020	8	128	0.40	0.0020

Appendix

TABLE VII: Hyperparameter disclosure for SDGL across datasets.

L

is the number of layers,

d

is the hidden width per field (so the output width is

2d

p

is the dropout rate, and

\mathrm{lr}

is the learning rate.

Explore similar work

Persistent Gaussian Perturbations Prevent Oversmoothing in Recurrent Graph Neural Networks
Jul 30, 2026Mostafa Haghir ChehreghaniGraph Neural Networks Stochastic Linear Dynamical Systems
Department of Computer Engineering Amirkabir University of Technology (Tehran Polytechnic) Tehran, Iran
Deep Neural Sheaf Diffusion
May 18, 2026Rémi Bourgerie, Šarūnas Girdzijauskas, Viktoria FodorGraph Neural Networks Sheaf Neural Networks
School of Electrical Engineering and Computer Science, KTH Royal Institute of Technology, Stockholm, Sweden.
From Diffusion to Reaction-Diffusion: A Dynamical-Systems View of Oversmoothing in Hypergraph Neural Networks
Jul 17, 2026Zhiheng Zhou, Mengyao Zhou, Yancheng Chen +3Hypergraph Neural Networks Hypergraph Learning
School of Mathematics and Statistics, Shandong University, Weihai, Shandong 264209, China · Academy of Mathematics and Systems Science, Chinese Academy of Sciences and also with the University of Chinese Academy of Sciences, Beijing 100190, China

Jul 30, 2026, cs.LGJ/K move · Enter open · S save

Persistent Gaussian Perturbations Prevent Oversmoothing in Recurrent Graph Neural Networks

Mostafa Haghir Chehreghani

Department of Computer Engineering Amirkabir University of Technology (Tehran Polytechnic) Tehran, Iran

Graph Neural Networks Stochastic Linear Dynamical Systems

Open paper AskPDF arXiv

Oversmoothing is a fundamental limitation of deep graph neural networks (GNNs), where repeated message passing causes node representations to become increasingly similar, eventually collapsing toward a low-dimensional subspace. This phenomenon limits the effective depth of message-passing architectures and motivates the search for mechanisms that preserve representation diversity. In this paper, we study a recurrent graph neural network in which independent Gaussian noise is injected after every propagation step and analyze the resulting architecture as a stochastic dynamical system. Under a standard global contraction assumption on the deterministic update, we prove that the hidden representations form a geometrically ergodic Markov chain admitting a unique invariant probability measure. Our main theoretical result establishes an explicit positive lower bound on the expected stationary Dirichlet energy, proportional to both the noise variance and the spectral gap of the underlying graph. Consequently, the stationary representations cannot collapse onto the constant manifold, providing a rigorous guarantee that asymptotic oversmoothing is prevented in the sense of non-vanishing Dirichlet energy. Our analysis reveals persistent stochastic perturbations as a fundamentally different mechanism for combating oversmoothing, complementing existing deterministic approaches based on residual connections, normalization, and graph rewiring. Finally, numerical experiments on both linear and nonlinear recurrent graph neural networks closely match the theoretical predictions, illustrating the emergence of a stationary distribution and the predicted dependence of the limiting Dirichlet energy on the noise intensity.

Abstract

Explore similar work

Persistent Gaussian Perturbations Prevent Oversmoothing in Recurrent Graph Neural Networks

Deep Neural Sheaf Diffusion

From Diffusion to Reaction-Diffusion: A Dynamical-Systems View of Oversmoothing in Hypergraph Neural Networks