Persistent noise keeps node data distinct in recurrent graph networks
Finite-Time Node Separation in Recurrent Graph Neural Networks with Persistent Gaussian Perturbations
Machine LearningArtificial Intelligence
Summary
Graph neural networks sometimes make different nodes look too similar over time, which can cause problems when trying to understand their unique information. This paper shows that by adding a constant random noise (Gaussian noise), nodes stay different from each other after any number of processing steps. The authors provide exact mathematical formulas describing how far apart node representations remain at any finite time, not just in the long run. This helps ensure that the network keeps useful distinctions between nodes during processing.
What this means in practice
- •For machine learning engineers: Design GNNs that maintain distinct node features during iterative computations to avoid information loss in graph-based models.
- •For network security teams: Develop anomaly detection systems on network graphs where node separation guarantees prevent convergence of distinct event signatures.
A theory result. No direct application yet.
Authors
Mostafa Haghir Chehreghani
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.