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

• URL: http://arxiv.org/abs/2609.13920v1
• Date: Sat, 12 Sep 2026 13:06:41 GMT
• Title: Finite-Time Node Separation in Recurrent Graph Neural Networks with Persistent Gaussian Perturbations
• Abstract summary: We provide a complementary finite-time analysis of the same persistent-noise architecture.<n>We first prove an exact second-moment decomposition for the expected squared distance between any two node representations.
• Score: 2.8427946758947304
• License: http://creativecommons.org/licenses/by/4.0/
• 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.

Related papers

• Fugacity-Resolved Stabilizer Entropy in Critical Quantum Chains: Discrete Selberg Sums and Exactly Solvable Rényi Indices [0.0]
  We introduce a fugacity-resolved partition function for the critical transverse-field Ising chain.<n>We map the fugacity-resolved all-minors sum, for every positive Rényi index, to a checkerboard-weighted discrete Selberg ensemble.
  arXiv  Detail & Related papers  (2026-08-07T09:12:41Z)
• Finite-size reliability of homothetic quantum Otto engines [0.0]
  Homothetic quantum Otto engines provide a reference model in which the quasistatic efficiency is trajectory-independent while work remains fluctuating.<n>Specializing to a uniformly spaced ladder gives closed finite-$N$ expressions for the full work distribution, mean work, variance, and signal-to-width reliability.
  arXiv  Detail & Related papers  (2026-07-31T06:09:15Z)
• Persistent Gaussian Perturbations Prevent Oversmoothing in Recurrent Graph Neural Networks [2.8427946758947304]
  We study a recurrent graph neural network in which independent Gaussian noise is injected after every propagation step.<n>We prove that the hidden representations form a geometrically ergodic Markov chain admitting a unique invariant probability measure.<n>Our analysis reveals persistent perturbations as a fundamentally different mechanism for combating oversmoothing.
  arXiv  Detail & Related papers  (2026-07-30T13:21:18Z)
• Decentralized Proximal Stochastic Gradient Langevin Dynamics [4.385194124090593]
  Decentralized Proximal Gradient Langevin Dynamics (DE-PSGLD) for sampling from a log-concave probability distribution constrained to a convex domain.<n>As the first decentralized approach for constrained domains, our algorithm exhibits fast posterior concentration and high predictive accuracy.
  arXiv  Detail & Related papers  (2026-05-01T15:11:06Z)
• Stability and Generalization of Push-Sum Based Decentralized Optimization over Directed Graphs [55.77845440440496]
  Push-based decentralized communication enables optimization over communication networks, where information exchange may be asymmetric.<n>We develop a unified uniform-stability framework for the Gradient Push (SGP) algorithm.<n>A key technical ingredient is an imbalance-aware generalization bound through two quantities.
  arXiv  Detail & Related papers  (2026-02-24T05:32:03Z)
• Finite-Sample Wasserstein Error Bounds and Concentration Inequalities for Nonlinear Stochastic Approximation [6.800624963330628]
  We derive non-asymptotic error bounds for nonlinear approximation algorithms in the Wasserstein-$p$ distance.<n>We show that the normalized last iterates converge to a Gaussian distribution in the $p$-Wasserstein distance at a rate of order $_n1/6$, where $_n$ is the step size.<n>These distributional guarantees imply high-probability concentration inequalities that improve upon those derived from moment bounds and Markovs inequality.
  arXiv  Detail & Related papers  (2026-02-02T18:41:06Z)
• Revisiting Zeroth-Order Optimization: Minimum-Variance Two-Point Estimators and Directionally Aligned Perturbations [57.179679246370114]
  We identify the distribution of random perturbations that minimizes the estimator's variance as the perturbation stepsize tends to zero.<n>Our findings reveal that such desired perturbations can align directionally with the true gradient, instead of maintaining a fixed length.
  arXiv  Detail & Related papers  (2025-10-22T19:06:39Z)
• Localization with non-Hermitian off-diagonal disorder [0.0]
  We discuss a non-Hermitian system governed by random nearest-neighbour tunnellings.<n>A physical situation of completely real eigenspectrum arises owing to the Hamiltonian's tridiagonal matrix structure.<n>The off-diagonal disorder leads the non-Hermitian system to a delocalization-localization crossover in finite systems.
  arXiv  Detail & Related papers  (2023-10-20T18:02:01Z)
• Nonconvex Stochastic Scaled-Gradient Descent and Generalized Eigenvector Problems [98.34292831923335]
  Motivated by the problem of online correlation analysis, we propose the emphStochastic Scaled-Gradient Descent (SSD) algorithm. We bring these ideas together in an application to online correlation analysis, deriving for the first time an optimal one-time-scale algorithm with an explicit rate of local convergence to normality.
  arXiv  Detail & Related papers  (2021-12-29T18:46:52Z)
• Lifting the Convex Conjugate in Lagrangian Relaxations: A Tractable Approach for Continuous Markov Random Fields [53.31927549039624]
  We show that a piecewise discretization preserves better contrast from existing discretization problems. We apply this theory to the problem of matching two images.
  arXiv  Detail & Related papers  (2021-07-13T12:31:06Z)
• Spectral clustering under degree heterogeneity: a case for the random walk Laplacian [83.79286663107845]
  This paper shows that graph spectral embedding using the random walk Laplacian produces vector representations which are completely corrected for node degree. In the special case of a degree-corrected block model, the embedding concentrates about K distinct points, representing communities.
  arXiv  Detail & Related papers  (2021-05-03T16:36:27Z)
• Uncertainty quantification for nonconvex tensor completion: Confidence intervals, heteroscedasticity and optimality [92.35257908210316]
  We study the problem of estimating a low-rank tensor given incomplete and corrupted observations. We find that it attains unimprovable rates $ell-2$ accuracy.
  arXiv  Detail & Related papers  (2020-06-15T17:47:13Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.