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

arXiv: https://arxiv.org/abs/2609.13920 · HTML: https://mlsanity.com/paper/2609.13920/

## 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 (most cited first, 22 of 22)

- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [A Comprehensive Survey on Graph Neural Networks](https://mlsanity.com/paper/1901.00596/) (2019)
- [Graph Neural Networks: A Review of Methods and Applications](https://mlsanity.com/paper/1812.08434/) (2018)
- [Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networks](https://mlsanity.com/paper/1810.02244/) (2018)
- [DeeperGCN: All You Need to Train Deeper GCNs](https://mlsanity.com/paper/2006.07739/) (2020)
- [A Survey on Oversmoothing in Graph Neural Networks](https://mlsanity.com/paper/2303.10993/) (2023)
- [The Surprising Power of Graph Neural Networks with Random Node Initialization](https://mlsanity.com/paper/2010.01179/) (2020)
- [Random Features Strengthen Graph Neural Networks](https://mlsanity.com/paper/2002.03155/) (2020)
- [DropGNN: Random Dropouts Increase the Expressiveness of Graph Neural Networks](https://mlsanity.com/paper/2111.06283/) (2021)
- [Expander Graph Propagation](https://mlsanity.com/paper/2210.02997/) (2022)
- [How does over-squashing affect the power of GNNs?](https://mlsanity.com/paper/2306.03589/) (2023)
- [Residual Connections and Normalization Can Provably Prevent Oversmoothing in GNNs](https://mlsanity.com/paper/2406.02997/) (2024)
- [Over-Squashing in Graph Neural Networks: A Comprehensive survey](https://mlsanity.com/paper/2308.15568/) (2023)
- [Generalization, Expressivity, and Universality of Graph Neural Networks on Attributed Graphs](https://mlsanity.com/paper/2411.05464/) (2024)
- [Towards Bridging Generalization and Expressivity of Graph Neural Networks](https://mlsanity.com/paper/2410.10051/) (2024)
- [Understanding Oversmoothing in Diffusion-Based GNNs From the Perspective of Operator Semigroup Theory](https://mlsanity.com/paper/2402.15326/) (2024)
- [Mitigating Over-Squashing in Graph Neural Networks by Spectrum-Preserving Sparsification](https://mlsanity.com/paper/2506.16110/) (2025)
- [Oversmoothing Alleviation in Graph Neural Networks: A Survey and Unified View](https://mlsanity.com/paper/2405.01663/) (2024)
- [Is uniform expressivity too restrictive? Towards efficient expressivity of graph neural networks](https://mlsanity.com/paper/2410.01910/) (2024)
- [Using Random Noise Equivariantly to Boost Graph Neural Networks Universally](https://mlsanity.com/paper/2502.02479/) (2025)
- [Effective Resistance Rewiring: A Simple Topological Correction for Over-Squashing](https://mlsanity.com/paper/2603.11944/) (2026)
- [Persistent Gaussian Perturbations Prevent Oversmoothing in Recurrent Graph Neural Networks](https://mlsanity.com/paper/2607.28185/) (2026)

## 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.