PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Mostafa Haghir Chehreghani

arXiv:2609.13920v1cs.LGcs.AI

TL;DR

Persistent-noise GNN theory establishes positive asymptotic energy, but that global result does not characterize arbitrary node pairs at finite depth. This paper analyzes finite-time pairwise separation, showing dynamics-aware near-collision bounds alongside exact noncollision and finite-horizon guarantees.

  • Problem

    Positive stationary Dirichlet energy does not directly characterize whether arbitrary node pairs remain distinct at finite depth.

    Source: §1 · p. 2

  • Method

    The analysis uses the noncentral-χ2 characterization to retain deterministic separation generated by message-passing dynamics.

    Source: §8 · p. 28, §11 · p. 35

  • Results

    Across all 27 sensitivity configurations, the empirical 5% separation scale exceeded the analytical guarantee, with median ratio 1.44.

    Source: §7.7 · p. 27

  • Takeaways & Limitations

    The result characterizes a finite-time representation-separation property that complements stationary oversmoothing analysis, without claiming universal graph-level expressivity.

    Source: §9 · p. 32

    The experiments retain the universal central benchmark and do not empirically quantify the additional tightening from the noncentral refinement.

    Source: §9 · p. 31

Abstract

from arXiv · show

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 \(\sigma\) 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\sigma^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\sigma^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.

1 Introduction

The paper extends persistent-noise GNN analysis from asymptotic global energy to finite-time pairwise representation separation. It derives expectation, probability, and permutation-equivariance guarantees for the stochastic dynamics.

1 Introduction

  • Prior stationary Dirichlet-energy results do not determine whether arbitrary node pairs remain distinct at finite depth.A positive global energy can coexist with individual pairs that are equal or arbitrarily close.Source: §1 · p. 2
  • For finite graphs, all node pairs are distinct almost surely at every positive integer time simultaneously.This exact noncollision result does not itself guarantee a numerically large minimum distance.Source: §1 · p. 3
  • The analysis also gives a uniform high-probability separation guarantee over a finite depth horizon.The bound accounts for all pair-time events through a union bound.Source: §1 · p. 3
  • With a permutation-equivariant deterministic update, exchangeable Gaussian noise makes the stochastic dynamics permutation equivariant in distribution.A fixed noise realization need not transform equivariantly when its numerical array is held fixed.Source: §1 · p. 3
  • At every positive time, the expected squared distance between any distinct node pair is at least 2σ^2d, without contraction or stationarity assumptions.The exact second-moment decomposition separates deterministic message-passing distance from the contribution of fresh Gaussian noise.Source: §1 · p. 4
  • Conditional pairwise distances have a noncentral chi-square characterization whose noncentrality captures deterministic message-passing separation.The resulting fixed-time and finite-horizon bounds retain this separation; the central bound is recovered at zero separation.Source: §1 · pp. 3–4

4. Distributional permutation equivariance.

The paper distinguishes sample-wise behavior from distributional symmetry in stochastic GNNs. Its separation results do not establish universal graph-level expressivity.

4. Distributional permutation equivariance

  • Invariant graph readouts yield permutation-invariant output distributions under the stochastic dynamics.This is a distribution-level guarantee, not a claim that individual noise realizations are sample-wise equivariant.Source: §4 · p. 4
  • Controlled synthetic experiments examine the pairwise decomposition, minimum-distance behavior, finite-horizon scaling, parameter dependence, and permutation behavior.The experiments distinguish sample-wise variability from distributional equivariance.Source: §4 · p. 4
  • Persistent Gaussian noise does not imply that pairwise node separation yields universal graph-level expressivity.The paper characterizes a finite-time representation property that complements stationary oversmoothing analysis.Source: §4 · p. 4

2 Preliminaries

The preliminaries define a recurrent message-passing model with independent Gaussian perturbations and distinguish three meanings of node separation. They also set up the paper’s treatment of oversmoothing and permutation symmetry.

2.1 Graph Notation and Recurrent GNN Architecture

  • The recurrent architecture adds independent Gaussian noise after a deterministic measurable node update, and the results apply beyond the displayed update form when expectations exist.The noise standard deviation is σ; the same post-update architecture was analyzed in [1].Source: §2.1 · p. 5

2.2 Dirichlet Energy and Oversmoothing

  • Oversmoothing is framed as increasing agreement of representations along graph edges, while prior stationary analysis establishes positive expected Dirichlet energy under contraction assumptions.The prior result concerns the invariant regime rather than finite-time arbitrary node pairs.Source: §2.2 · p. 5

2.3 Notions of Representation Separation

  • Expected pairwise separation, almost-sure noncollision, and uniform ε-separation are distinct second-moment, exact-equality, and finite-margin properties.The Gaussian recurrence permits all three to be analyzed explicitly.Source: §2.3 · pp. 5–6

2.4 Permutation Actions and Equivariance

  • A deterministic update is permutation equivariant when permuting node representations and graph structure commutes with the update; Gaussian noise is exchangeable under node permutations.The setup distinguishes sample-wise from distributional equivariance.Source: §2.4 · p. 6

2.5 Randomness and GNN Expressivity

  • The paper characterizes finite-time node separation and stochastic-dynamics equivariance without claiming that persistent Gaussian noise gives universal graph-level expressivity.Other randomness-based approaches cited include random node features, DropGNN, and EN-GNN [21] [22] [23] [24].Source: §2.5 · p. 6

3 Main Analysis: Finite-Time Pairwise Separation

The analysis establishes finite-time pairwise separation from the persistent Gaussian update, then strengthens expectation guarantees into exact noncollision and dynamics-aware near-collision bounds. The refined bounds cover fixed times and finite horizons.

3.1 Exact Pairwise Second-Moment Identity

  • The exact pairwise second-moment identity decomposes expected squared distance into deterministic separation and a Gaussian contribution.The identity is stated for distinct node pairs and assumes the relevant expectations are finite.Source: §3.1 · p. 7

3.2 Finite-Time Pairwise Lower Bound

  • At every positive time, expected squared pairwise distance is at least 2σ^2d, independently of graph topology, activation, or weight matrix.Those model choices affect the deterministic term; fresh independent Gaussian perturbations contribute 2σ^2d.Source: §3.2 · pp. 7–8

3.3 Almost-Sure Pairwise Noncollision

  • For σ > 0, finite graphs have pairwise-distinct representations almost surely at each positive time and simultaneously across all positive integer times.This is exact noncollision, not a numerical margin guarantee; the minimum distance can be arbitrarily small.Source: §3.3 · pp. 8–9

3.4 Noncentral-chi-square Characterization of Pairwise Distances

  • Conditional pairwise distances admit a noncentral chi-square characterization that retains deterministic message-passing separation.The central small-ball bound is the worst case at zero deterministic separation; positive separation gives a sharper conditional near-collision probability.Source: §3.4 · p. 10

3.5 Refined Fixed-Time High-Probability Separation

  • The fixed-time high-probability bound refines the architecture-agnostic central bound while requiring neither contraction nor stationarity.Under a deterministic separation floor, a positive noncentrality yields a strictly smaller bound than the central case.Source: §3.5 · pp. 10–11

3.6 Refined Finite-Horizon Separation

  • The noncentral formulation extends separation guarantees over a finite horizon, with the central guarantee recovered when the separation floor is zero.The refined separation scale can be expressed using a noncentral chi-square quantile; the central case also has a simpler conservative closed-form corollary.Source: §3.6 · pp. 11–13

4 Comparison with Prior Persistent-Noise Analysis

The prior stationary analysis and this paper study the same stochastic recurrence but address different scales of behavior. The present work provides finite-time pairwise separation results that complement the prior global, asymptotic energy guarantee.

4 Comparison with Prior Persistent-Noise Analysis

  • The prior analysis establishes a positive stationary lower bound for expected Dirichlet energy under contraction assumptions, while this paper studies finite-time pairwise separation.The comparison is one of scope: the former concerns long-run graph-edge energy; the latter concerns individual node pairs across finite depths.Source: §4 · p. 13
  • The present results provide almost-sure, fixed-time high-probability, and finite-horizon separation guarantees for every distinct node pair.Table 1 summarizes the scope of the prior stationary analysis [1] and the present finite-time refinement.Source: §4 · p. 14, Table 1 · p. 14
  • The stationary global-energy guarantee and finite-time pairwise results are complementary, not an architectural extension.The prior result concerns long-run graph-level energy under contraction; the present results describe separation immediately and throughout a prescribed finite-depth horizon without contraction.Source: §4 · p. 14

5 Node-Level Separation and Graph-Level Expressivity

The paper establishes stochastic separation properties for node representations at finite depths, while distinguishing those properties from graph-level expressivity guarantees. It also frames the results as a probabilistic characterization relevant to, but not a replacement for, randomized expressivity methods.

5.1 Representation Separation

  • On a finite graph, all node representations are pairwise distinct almost surely, simultaneously across all positive time steps.The representation-separation results also provide fixed-time and finite-horizon high-probability margins when their stated conditions hold.Source: §5.1 · p. 15

5.2 Why the Results Do Not Prove Graph-Level Universality

  • Node-level injectivity alone does not establish graph universality: different representation multisets may yield the same readout, and graph classification need not require distinct within-graph node representations.The theorems establish finite-time representation separation, not universal graph discrimination.Source: §5.2 · p. 15

5.3 Relation to Randomized Expressivity Methods

  • The analysis complements randomized expressivity methods by characterizing separation from repeatedly injected independent Gaussian noise, without replacing those methods.Connecting persistent stochastic dynamics to graph-level expressivity remains open; one proposed direction is characterizing representation distributions with invariant readouts.Source: §5.3 · pp. 15–16

6 Distributional Permutation Equivariance

A fixed noise realization can break sample-wise permutation equivariance, even when the deterministic update is equivariant. With exchangeable fresh Gaussian noise, the stochastic dynamics are equivariant in distribution, and invariant readouts yield invariant output distributions.

6 Distributional Permutation Equivariance

  • The relevant equivariance property is distributional: relabeling may change a particular sampled output while leaving its distribution unchanged.This distinction separates the behavior of one numerical noise realization from the law of the stochastic mapping.Source: §6 · p. 16, §6.1 · p. 16

6.2 One-Step Distributional Equivariance

  • For one step, deterministic permutation equivariance combined with exchangeable Gaussian noise gives equality in distribution after relabeling.The stated one-step relation is F(PAP^T, PH) + σΞ d= P(F(A, H) + σΞ).Source: §6.2 · p. 17
  • Across multiple steps, distributional equivariance follows when the deterministic update and initial state are equivariant and fresh i.i.d. Gaussian noise is independently sampled at each step.The proof proceeds by induction, applying the one-step result conditionally on the current state.Source: §6.2 · p. 17

6.3 Permutation-Invariant Graph Outputs

  • A permutation-invariant graph readout maps distributionally equivariant node dynamics to permutation-invariant graph-output distributions.The result concerns output distributions, not equality of a particular sampled output.Source: §6.3 · p. 18

6.4 Expected Outputs and Monte Carlo Approximation

  • Under the stated integrability assumptions, Monte Carlo averaging approximates an expected output that is already invariant under graph relabeling.The invariance follows from exchangeability of the underlying noise law, rather than being created by averaging.Source: §6.4 · p. 18

7 Experimental Validation

Controlled synthetic experiments test the predicted stochastic geometry in representative recurrent message-passing systems, rather than establishing behavior across all architectures or trained models. Across the reported experiments, the observed separation patterns broadly agree with the finite-time theory, while the analytical guarantees can be conservative.

7 Experimental Validation

  • The controlled study tests the theory’s pairwise identity, minimum-distance behavior, near-collision probabilities, permutation behavior, and sensitivity to n, d, σ, and T.It uses synthetic graph families and an explicit recurrent message-passing update with no learned parameters.Source: §7 · p. 19, §7.1 · p. 19

7.2 Experiment 1: Exact Pairwise Second-Moment Identity

  • Across three graph topologies, the empirical pairwise second-moment contribution closely matched the theoretical 2σ2d = 0.32 within Monte Carlo error.Figure 1 plots bL(t) against the theoretical value over the recurrent steps.Source: Figure 1 · p. 20, §7.2 · p. 20, Table 2 · p. 20

7.3 Experiment 2: Minimum Pairwise Distance Versus Depth

  • At t = 40, median minimum distances were 0.3803, 0.3835, and 0.3753 for the cycle, Erdős–Rényi, and Barabási–Albert graphs; the all-horizon medians were lower.Figure 2 shows medians and 5th–95th percentile intervals; for the full horizon, the medians were 0.2907, 0.2830, and 0.2804, respectively.Source: Figure 2 · p. 21, §7.3 · p. 21, Table 3 · p. 22

7.4 Experiment 3: Fixed-Time and Finite-Horizon Near-Collision Probabilities

  • At ε = 0.18, no near-collision occurred in 300 trajectories over 40 steps, against a theoretical finite-horizon upper bound of 0.0391.For larger thresholds, the temporal union bound becomes vacuous at ε = 0.24 and 0.26.Source: §7.4 · p. 22, Table 4 · p. 24

7.5 Experiment 4: Distributional Permutation Equivariance

  • The relabeled and original graph-readout distributions showed no statistically detectable discrepancy, although paired outputs using the same numerical noise could differ substantially.The two-sample Kolmogorov–Smirnov test gave statistic 0.021 and p = 0.770; this finite-sample nonrejection is consistent with, but does not prove, distributional equivariance.Source: §7.5 · p. 23, Figure 4 · p. 25

7.6 Experiment 5: Sensitivity to Representation Dimension, Noise Scale, and Horizon

  • Empirical separation generally increased with d and σ and decreased with T, while its decline with T was milder than the theoretical benchmark’s T^-1/d scaling.At d = 16 and T = 40, the empirical 5% quantile rose from 0.123 at σ = 0.05 to 0.239 at σ = 0.10 and 0.479 at σ = 0.20.Source: §7.6 · pp. 24–26, Figure 5 · p. 26

7.7 Experimental Summary and Interpretation

  • Across the experiments, minimum distances stayed positive over the tested horizon and empirical near-collision probabilities stayed below non-vacuous universal central bounds.The study supports the stated stochastic predictions for its explicit recurrent system, not universal empirical behavior across architectures, datasets, or trained models.Source: §7.7 · pp. 26–27
  • Across 27 configurations, empirical 5% separation quantiles exceeded the analytical guarantee, with a median ratio of 1.44; the controlled study does not establish behavior across architectures or trained models.The sensitivity study is shown against the theoretical benchmark in Figure 5 and summarized in Table 6.Source: Figure 5 · p. 26, §7.7 · p. 27, Table 6 · p. 27

8 Discussion

The principal refinement is a noncentral characterization that retains deterministic message-passing separation, making near-collision bounds more informative than the central worst-case analysis. The discussion distinguishes universal guarantees from dynamics-dependent behavior and states limits on what the analysis and experiments establish.

8 Discussion

  • For λ(t) > 0, the dynamics-aware near-collision bound is strictly smaller than the central bound and remains valid without contraction or stationarity assumptions.The central result is recovered when deterministic separation is zero.Source: §8 · p. 28
  • The exact second-moment identity gives a universal pairwise lower bound, while the noncentral χ² analysis shows how deterministic separation changes near-collision probabilities.The identity separates deterministic and stochastic contributions; the noncentral characterization provides the probabilistic interpretation of the deterministic term.Source: §8 · pp. 28–29
  • The universal expected lower bound and central worst-case bound have no explicit depth dependence, but deterministic separation can change practical near-collision probabilities with depth.The depth-independent guarantee reflects fresh Gaussian noise at every recurrent update; it does not mean the full representation distribution is depth-independent.Source: §8 · pp. 29–30
  • Almost-sure noncollision rules out exact equality but gives no numerical margin; central and noncentral small-ball bounds quantify near-collisions, with the latter tighter when separation is established.The noncentral refinement depends on realized or provable noncentrality parameters, which the reported experiments do not directly validate.Source: §8 · p. 30
  • The sensitivity study uses the central λ = 0 benchmark because it requires no additional deterministic-separation assumption; experiments validate this universal baseline, while the noncentral theorem provides sharper problem-specific bounds.Source: §8 · p. 30
  • The stochastic dynamics are permutation equivariant in distribution, but these symmetry and separation results do not establish universal graph-level expressivity.With permutation-invariant readouts, graph-level output distributions are permutation invariant; a universality theorem would require a stronger characterization and an appropriate readout.Source: §8 · pp. 30–31

9 Limitations and Open Questions

The finite-horizon guarantees are conservative because they use union bounds and the dynamics-aware bounds require noncentrality information for graph-wide numerical guarantees. The paper also limits its claims to finite-time separation under Gaussian noise, without establishing graph-level universality or ergodicity.

Conservative Uniform-Separation Bound

  • Union bounds over node pairs and time steps leave dependencies unused, while graph-wide numerical guarantees require information about the noncentrality parameters λ(t).The conditional noncentral formulation is exact, but sharper bounds may exploit joint Gaussian geometry, packing, temporal dependence, or graph structure.Source: §9 · p. 31
  • The experiments retain the universal central benchmark and do not empirically quantify the additional tightening available from the noncentral refinement.This reflects the absence of an assumed, verified deterministic-separation floor in those experiments.Source: §9 · p. 31
  • In 27 tested configurations, the empirical-to-theoretical ratio had median 1.44 and ranged from 1.36 to 1.93, but this controlled result is not a universal estimate of theorem tightness.The empirical 5% quantile of the all-horizon minimum distance exceeded the analytical scale in every tested configuration.Source: §9 · p. 31

Genericity of the Probabilistic Mechanism

  • The proofs depend mainly on additive nondegenerate Gaussian noise rather than graph details, so their mechanism is generic beyond GNNs.Its GNN-specific significance is a depth-independent finite-time separation guarantee for recurrent message passing.Source: §9 · pp. 31–32

No Direct Graph-Level Universality Result

  • The paper does not show that non-isomorphic graphs produce different stochastic representation distributions; that requires a graph-level invariant, suitable readout, and stronger dynamics characterization.Source: §9 · p. 32

No Ergodicity Without Additional Assumptions

  • Finite-time results do not imply an invariant distribution exists or is unique; the cited stationary analysis establishes ergodicity under contraction conditions.The paper identifies weaker assumptions and stationary graph-level information as open questions.Source: §9 · p. 32

Gaussian Noise Assumption

  • Gaussian noise supplies explicit covariance, smooth full-dimensional density, small-ball probabilities, and permutation exchangeability; broader noise distributions remain a direction for study.The open question is which minimal conditions preserve the separation guarantees.Source: §9 · p. 32

10 Related Work

The related work spans persistent noise and other approaches to oversmoothing, over-squashing, stochastic expressivity, stochastic GNN methods, and generalization. This paper positions its contribution as a narrower, finite-time characterization of pairwise representation geometry.

10.1 Persistent Noise and Oversmoothing

  • Prior persistent-noise work [1] studies contraction and ergodicity for an asymptotic stationary Dirichlet-energy bound; other oversmoothing approaches use residual connections, normalization, or graph rewiring.The present paper retains the persistent-noise architecture and supplies finite-time pairwise guarantees.Source: §10.1 · pp. 32–33

10.2 Over-Squashing and Information Bottlenecks

  • Over-squashing work addresses information bottlenecks and long-range dependencies through sparsification, expander propagation, rewiring, and neighborhood extension; this paper instead studies stochastic node separation.The authors suggest their finite-time guarantees may complement neighborhood-extension approaches to information flow.Source: §10.2 · pp. 33–34

10.3 Randomness for GNN Expressivity

  • Random-node initialization, random features, DropGNN, and equivariant noise target GNN expressivity, while this paper quantifies separation without asserting universal graph expressivity.Source: §10.3 · p. 34

10.4 Stochasticity in GNNs

  • Other stochastic GNN work addresses oversmoothing, over-squashing, and expressive limits; this analysis complements stochastic aggregation and dropout with explicit probabilistic guarantees.Source: §10.4 · p. 34

10.5 Generalization and Expressivity Trade-offs

  • Research on GNN generalization and expressivity motivates a possible connection: the paper’s characterization of noise-driven representation geometry may inform future study of that trade-off.Source: §10.5 · pp. 34–35

11 Conclusion

The paper develops finite-time separation guarantees for persistent-noise recurrent GNNs without contraction or stationarity assumptions. Its results include exact and probabilistic pairwise separation, distributional permutation equivariance, and controlled experimental support; sharper graph-wide bounds and graph-level characterizations remain open.

11 Conclusion

  • The same post-update Gaussian-noise architecture as [1] yields a finite-time analysis without contraction or stationarity assumptions.Source: §11 · p. 35
  • The exact identity gives a topology-independent pairwise lower bound at every positive depth.Source: §11 · p. 35
  • The conditional noncentral-χ2 characterization retains deterministic message-passing separation and gives dynamics-aware fixed-time and finite-horizon near-collision bounds.The central bound is recovered as the zero-noncentrality case.Source: §11 · p. 35
  • Exact pairwise collisions have probability zero at every positive time, and finite graphs remain pairwise distinct almost surely across all positive integer times.Central and noncentral small-ball bounds also yield quantitative fixed-time and finite-horizon separation statements.Source: §11 · p. 35
  • The dynamics are permutation equivariant in distribution, so invariant readouts have permutation-invariant graph-level output distributions despite possible sample-wise non-equivariance.Source: §11 · p. 35
  • Controlled experiments support the predicted stochastic geometry, while sharper dependence-aware graph-wide bounds, noncentrality estimates, and graph-level characterizations remain open.The noncentral refinement is analytically exact conditionally, but its potential empirical tightening remains to be studied.Source: §11 · pp. 35–36

Declaration of generative AI and AI-assisted technologies in the writing process

  • The author reports using AI tools for manuscript drafting, exposition, argument formulation, and presentation, with results and data independently reviewed and verified by the author.Source: Declaration of generative AI and… · p. 36
Loading 2609.13920v1…