mlsanityData to 14 Oct 2026

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

arXiv 2609.13920 ↗First posted 12 Sep 2026cs.LG cs.AIcited by 0

Not on the map. Why?

Abstract (arXiv)

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.

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Builds on 22 of its 38 references that are in the map. First posted on arXiv 12 Sep 2026.

Builds on

22 of 38 references.

References · 22

  1. 2018How Powerful are Graph Neural Networks?cited by 4,393
  2. 2019A Comprehensive Survey on Graph Neural Networkscited by 2,919
  3. 2018Graph Neural Networks: A Review of Methods and Applicationscited by 1,576
  4. 2018Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networkscited by 881
  5. 2020DeeperGCN: All You Need to Train Deeper GCNscited by 250
  6. 2023A Survey on Oversmoothing in Graph Neural Networkscited by 247
  7. 2020The Surprising Power of Graph Neural Networks with Random Node Initializationcited by 198
  8. 2020Random Features Strengthen Graph Neural Networkscited by 186
  9. 2021DropGNN: Random Dropouts Increase the Expressiveness of Graph Neural Networkscited by 118
  10. 2022Expander Graph Propagationcited by 75
  11. 2023How does over-squashing affect the power of GNNs?cited by 53
  12. 2024Residual Connections and Normalization Can Provably Prevent Oversmoothing in GNNscited by 34
10 more
  1. 2023Over-Squashing in Graph Neural Networks: A Comprehensive surveycited by 23
  2. 2024Generalization, Expressivity, and Universality of Graph Neural Networks on Attributed Graphscited by 14
  3. 2024Towards Bridging Generalization and Expressivity of Graph Neural Networkscited by 12
  4. 2024Understanding Oversmoothing in Diffusion-Based GNNs From the Perspective of Operator Semigroup Theorycited by 8
  5. 2025Mitigating Over-Squashing in Graph Neural Networks by Spectrum-Preserving Sparsificationcited by 8
  6. 2024Oversmoothing Alleviation in Graph Neural Networks: A Survey and Unified Viewcited by 4
  7. 2024Is uniform expressivity too restrictive? Towards efficient expressivity of graph neural networkscited by 2
  8. 2025Using Random Noise Equivariantly to Boost Graph Neural Networks Universallycited by 2
  9. 2026Effective Resistance Rewiring: A Simple Topological Correction for Over-Squashingcited by 1
  10. 2026Persistent Gaussian Perturbations Prevent Oversmoothing in Recurrent Graph Neural Networkscited by 1

Built on by

Not cited yet.