Finite-Time Node Separation in Recurrent Graph Neural Networks with Persistent Gaussian Perturbations

Mostafa Haghir Chehreghani

cs.LGSep 12, 2026

Finite-Time Node Separation in Recurrent Graph Neural Networks with Persistent Gaussian Perturbations

Authors: Mostafa Haghir Chehreghani

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

Abstract

Persistent Gaussian perturbations have been shown to prevent asymptotic oversmoothing in recurrent Graph Neural Networks (GNNs) by ensuring a positive stationary Dirichlet energy. However, this global energy bound does not guarantee that individual node representations remain distinct at finite depths. In this paper, we provide a complementary finite-time analysis of the same persistent-noise architecture. Let $d$ denote the representation dimension and $σ$ the noise standard deviation. We first prove an exact second-moment decomposition for the expected squared distance between any two node representations, yielding the universal lower bound $2σ^2 d$ at every positive time step without contraction or stationarity assumptions. More precisely, conditional pairwise distances have a noncentral chi-square characterization: the noncentrality parameter is the deterministic message-passing separation normalized by $2σ^2$ . This yields dynamics-aware fixed-time and finite-horizon near-collision bounds that retain information discarded by the central worst-case analysis. The earlier central Gaussian bound is recovered as the worst-case zero-separation case. We additionally prove almost-sure pairwise noncollision, derive a uniform finite-horizon guarantee, and establish permutation equivariance in distribution for the stochastic dynamics and permutation-invariant graph outputs. Our results complement the asymptotic energy analysis of prior work and provide rigorous finite-time guarantees on node-level representation separation.

Figures & tables

Property	Prior stationary persistent-noise analysis [ 1 ]	Present work
Architecture	Persistent post-update Gaussian noise	Same architecture
Primary regime	Stationary / asymptotic	Every finite $t\geq 1$
Primary quantity	Dirichlet energy	Pairwise representation distance
Spatial scope	Graph edges / global energy	All node pairs
Contraction	Required for stationary theory	Not required for finite-time results
Exact collision	Not the focus	Probability zero

Table 1: Scope of the prior stationary analysis [ 1 ] and the present finite-time refinement.

Figure 1: Empirical verification of the exact pairwise second-moment identity. The plotted quantity is

\widehat{L}^{(t)}

from eq. 60 ; the dashed horizontal line is the theoretical value

2\sigma^{2}d=0.32

. Each curve averages over

R=300

independent noise trajectories.

Graph	Mean $\widehat{L}^{(t)}$	Max. abs. error	RMSE
Cycle	0.31987	0.01302	0.00299
Erdős–Rényi	0.31875	0.00799	0.00342
Barabási–Albert	0.32012	0.02578	0.00501

Table 2: Empirical verification of the

2\sigma^{2}d

identity over 40 recurrent steps.

Figure 2: Minimum pairwise distance versus recurrent depth. Curves show the empirical median over 300 noise trajectories; shaded regions denote the 5th–95th percentile interval.

Graph	Med. final	5% final	Med. horizon	5% horizon
Cycle	0.3803	0.3006	0.2907	0.2434
Erdős–Rényi	0.3835	0.2985	0.2830	0.2380
Barabási–Albert	0.3753	0.3026	0.2804	0.2383

Table 3: Minimum pairwise distance statistics at

T=40

and over the complete 40-step horizon.

Figure 3: Empirical finite-horizon near-collision probability compared with the exact Gaussian small-ball/union-bound prediction. The empirical probabilities are estimated from 300 independent noise trajectories over

T=40

recurrent steps.

$\varepsilon$	Graph	Fixed bound	Horizon bound	Emp. horizon
0.18	Cycle	0.0010	0.0391	0.0000
	Erdős–Rényi	0.0010	0.0391	0.0000
	Barabási–Albert	0.0010	0.0391	0.0000
0.20	Cycle	0.0045	0.1783	0.0000
	Erdős–Rényi	0.0045	0.1783	0.0067
	Barabási–Albert	0.0045	0.1783	0.0033

Table 4: Empirical near-collision probabilities and theoretical bounds. The fixed-time bound is

\binom{n}{2}q_{d}(\varepsilon,\sigma)

and the finite-horizon bound is

T\binom{n}{2}q_{d}(\varepsilon,\sigma)

with

T=40

Figure 4: Permutation-distributional invariance. The histograms show the graph-level readout

\rho(H)=\sum_{i}\|h_{i}\|^{2}

over

K=2000

independent noise trajectories for the original and randomly permuted cycle graph.

Quantity	Original graph	Permuted graph
Mean output	12.2916	12.2800
Standard deviation	1.6587	1.6665
Absolute difference of means		0.0116
Mean absolute paired difference		1.4682
KS statistic		0.0210
KS $p$ -value		0.7700

Table 5: Permutation-distributional invariance experiment using

K=2000

independent noise trajectories.

Figure 5: Sensitivity of finite-horizon separation to representation dimension

d

, noise scale

\sigma

, and horizon

T

. Each point represents one of

27

configurations on the cycle graph. The horizontal axis is the theoretical

\varepsilon_{\delta,T}

with

\delta=0.05

; the vertical axis is the empirical

5\%

quantile of

\min_{1\leq t\leq T}D_{\min}^{(t)}

. The diagonal marks equality between the empirical quantile and the theoretical guarantee.

$d$	$\sigma$	$T$	Empirical $5\%$	Theory $\varepsilon_{\delta,T}$	Ratio
8	0.05	10	0.069	0.036	1.93
8	0.05	20	0.053	0.033	1.62
8	0.05	40	0.049	0.030	1.61
8	0.10	10	0.115	0.072	1.60
8	0.10	20	0.104	0.066	1.58
8	0.10	40	0.089	0.060	1.47

Table 6: Sensitivity study of the finite-horizon separation scale. The empirical column reports the estimated

5\%

quantile of

\min_{1\leq t\leq T}D_{\min}^{(t)}

over

R=200

trajectories on the cycle graph. The theoretical column reports

\varepsilon_{\delta,T}

from eq. 45 with

\delta=0.05

Over-Smoothing in GNNs

See all 20 papers

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
Universality and Approximation Rates of Graph Neural Networks with Random Features
Jul 29, 2026Lukas Gonon, Thilo Meyer-Brandis, Niklas WeberGraph Neural Networks Equivariant Neural Networks
School of Computer Science University of St. Gallen St. Gallen, 9000, Switzerland · Department of Mathematics LMU Munich Munich, 80333, Germany
Beyond ReLU: Bifurcation, Oversmoothing, and Topological Priors
Feb 17, 2026Erkan Turan, Gaspard Abel, Maysam Behmanesh +2GNN Oversmoothing Graph Neural Networks
LIX, Ecole Polytechnique, IP Paris · Université Paris Saclay, Université Paris Cité, ENS Paris Saclay, CNRS, SSA, INSERM, Centre Borelli, F-91190, Gif-sur-Yvette, France · Centre d’Analyse et de Mathématique Sociales, EHESS, CNRS, 75006 Paris, France..

Jul 30, 2026J/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 GNN Oversmoothing Over-Smoothing in GNNs

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

Over-Smoothing in GNNs

Explore similar work

Persistent Gaussian Perturbations Prevent Oversmoothing in Recurrent Graph Neural Networks

Universality and Approximation Rates of Graph Neural Networks with Random Features

Beyond ReLU: Bifurcation, Oversmoothing, and Topological Priors