Deep graph neural networks repeatedly average each node's features with its neighbors'. After enough rounds, every node looks the same. This failure is called over-smoothing. One of the cleanest known fixes adds "repulsive" negative edges that push dissimilar nodes apart. The fix only works if the repulsion strength sits inside a narrow band: too weak and features still collapse to a constant, too strong and they blow up. That band is a property of the graph. Real graphs, such as interaction networks, citation streams and sensor grids, gain and lose edges continuously. This proposal asks whether a repulsion strength that was correctly set on yesterday's graph drifts out of the safe band on today's, and whether a cheap incremental procedure can keep it inside.
The core claim fits in two sentences. Signed anti-smoothing operators tuned on one snapshot of an evolving graph go stale, so a deep model either re-collapses or diverges as edits accumulate. Tracking the operator's leading spectral quantities with warm-started iterative eigensolvers, and re-linking negative edges only around edited nodes, should keep deep models discriminative at a small fraction of the cost of rebuilding from scratch. The proposal treats over-smoothing as the core mechanism and dynamic graph maintenance as the setting. Topology sensitivity serves as the stress test: we ask how errors in the initial or maintained graph push the operator toward instability.
What exists and what is missing
A Signed Graph Approach to Understanding and Mitigating Oversmoothing supplies the method we build on. It shows that BatchNorm, PairNorm and residual connections implicitly add negative edges. It then proposes Structural Balanced Propagation (SBP), a parameter-free scheme whose negative edges come from class labels (Label-SBP) or initial feature cosine similarity (Feature-SBP). It also proves a critical repulsion value, with collapse below it and blow-up above it, and keeps nodes distinguishable at 300 layers. The method is entirely static, and recomputing Feature-SBP's negative edges after the graph changes costs quadratic time. Hierarchical Multi Scale Graph Neural Networks (HMH) reaches 64 stable layers using signed affinities and Haar wavelets built on a clustering hierarchy. Its authors state that updating that hierarchy on the fly for dynamic graphs is open.
On the dynamic side, Adapting to Evolving Graphs maintains coarsened graphs incrementally. It describes an "error lock-in" effect: assignments that are frozen early keep their mistakes. The paper retains 98–99% of static node-classification accuracy, but only with shallow GNNs, and it never measures smoothing. Temporal Graph Rewiring with Expander Graphs adds a fixed, precomputed expander graph to temporal GNN memory. It targets under-reaching and bottlenecked information flow, not feature collapse, and it leaves adaptive rewiring as future work.
None of these papers asks whether the stability conditions of anti-smoothing operators survive graph edits. Our proposal differs from SBP and HMH by making the signed operator a maintained object. It differs from dynamic coarsening and temporal rewiring because the quantity being maintained is a spectral stability margin, not coarsening fidelity or reachability.
Two further lines of work constrain the design. Unsupervised Graph Embedding via Adaptive Graph Learning learns adjacency by minimizing a Dirichlet energy term, a measure of how much features differ across edges. Any structure learner that only minimizes this term pushes toward collapse, so we do not learn edges that way. Temporal Graph Benchmark (TGB) finds that simple non-learning heuristics often beat deep temporal GNNs. This is a warning that depth may not pay on many dynamic tasks, and the experiments must confront it rather than assume otherwise.
Core Claim
Write the signed propagation operator at time $t$ as
$$P_t = \hat{A}^{+}_t - \lambda_t \hat{A}^{-}_t,$$
where $\hat{A}^{+}_t$ is the normalized positive adjacency of the current graph, $\hat{A}^{-}_t$ is the normalized matrix of repulsive edges, and $\lambda_t$ is the repulsion strength.
For linear propagation of the form $H \leftarrow P_t H$, two conditions keep features stable and distinct. The spectral radius of $P_t$ must stay near one, so features do not explode. The gap between its top eigenvalue and its next few eigenvalues must stay small, so features do not collapse onto one direction. We use this as an operational stand-in for SBP's critical value. Part of the work is checking it against their theorem.
Edits change both $\hat{A}^{+}_t$ and the set of nodes that should repel one another. We hypothesize that on real streaming graphs a fixed $\lambda$ leaves the safe band within a modest number of edits, and that the drift is fastest where the graph's degree distribution or community structure shifts.
Research Program
The work has three stages.
The first is a measurement study. On streaming graphs, we tune Feature-SBP and HMH on the first snapshot, freeze them, and track three things over time: the spectral radius and gap of the frozen operator, accuracy at depths of 2, 16, 64 and 128 layers, and collapse measured with the rank-based metrics of Rethinking Oversmoothing in Graph Neural Networks: A Rank-Based Perspective. Are we measuring oversmoothing in graph neural networks correctly? argues that energy-based metrics mislead, which is why we use rank-based ones. If drift turns out to be negligible, the project stops here and reports that negative result.
The second stage builds the maintenance procedure. After each batch of edits, we warm-start a few Lanczos or power iterations from the previous leading eigenvectors to re-estimate the spectral radius and gap. We then adjust $\lambda_t$ to restore a target margin. Cost scales with the number of edges times a small number of iterations.
Negative edges are updated only for nodes within one or two hops of an edit. Their dissimilar partners come from an approximate-nearest-neighbor index queried for least-similar candidates, so no quadratic comparison is needed. That index is maintained with the lazy consolidation used in The DiskANN library. To avoid the coarsening paper's lock-in effect, a full rebuild runs only when accumulated spectral drift exceeds a threshold, not on a fixed schedule. Rebuild frequency becomes a reported quantity.
The third stage is the topology-sensitivity probe. We corrupt the initial k-nearest-neighbor or interaction graph with random edge additions and deletions, then measure how much faster the frozen operator leaves the safe band than the tracked one. Prior work suggests that misspecified graphs break spectral methods: Stationary Signal Processing on Graphs shows this for graph Wiener estimators and Local and Global Optimization Techniques in Graph-Based Clustering shows it for spectral clustering. Our probe asks whether the stability margin is the specific channel through which this happens in deep GNNs.
Baselines
The naive reference is SBP, or a deep graph convolutional network with residual connections, tuned once on the first snapshot and never updated. It costs nothing to maintain. If the proposal cannot beat it at depth, the drift hypothesis is false. A shallow two-layer graph convolutional network is also reported at every time step, because a deep model that cannot beat it has no reason to exist.
The strongest competitor is SBP, and separately HMH, rebuilt from scratch at every snapshot. It is the accuracy ceiling for our approach, and it shares our signed-operator mechanism. Both methods get identical data splits, identical depth grids and identical hyperparameter search budgets per snapshot. Wall-clock time and memory are recorded on the same hardware. No reported result was found on Lacuna for SBP or HMH on any dynamic benchmark. The static reports are 300 stable layers for SBP and 64 for HMH, not accuracies on streaming data. Beating this baseline means matching its accuracy within one standard deviation across seeds at depth 64 or more while using under a tenth of its update time.
The same matching criterion applies against residual-connected deep GNNs, which Residual connections provably mitigate oversmoothing in graph neural networks shows prevent collapse with no graph-dependent tuning at all.
For continuous-time streams, we compare against Temporal Graph Rewiring with Expander Graphs and against EdgeBank and moving-average heuristics under TGB's ranking protocol. The file reports no specific TGB numbers for these, so all of them are rerun.
Two ablations isolate the key ingredient. The first tracks $\lambda_t$ only, with negative edges frozen. The second updates negative edges locally with $\lambda$ frozen. This separates the contribution of spectral calibration from that of topology maintenance.
Why not just…?
Why not just use residual connections, which need no maintenance at all? This is the most serious threat. If residual connections already keep deep models discriminative on changing graphs, calibrated signed operators add only complexity. SBP's analysis shows that residuals act as implicit, untuned negative edges. That suggests residuals offer a fixed and possibly mismatched amount of repulsion, but it is not evidence that they fail on dynamic graphs. The measurement study runs residual GNNs at every depth on every stream. If they match tracked SBP, we report that, and the contribution narrows to the cost and stability diagnostics.
Why not just rebuild the signed operator at every snapshot? On small graphs this is fine, and it is our accuracy ceiling. The question is cost. Feature-SBP's negative-edge construction is quadratic, and HMH's hierarchy rebuild is heavy enough that its own authors flag it as open. We report the graph size at which rebuilding becomes impractical relative to edit rate. If that crossover lies beyond realistic benchmark sizes, the incremental method is unnecessary, and we will say so.
Why not just stay shallow, given that TGB finds simple heuristics competitive? Many temporal tasks may not reward depth, and TGB's finding supports that. Depth matters only where labels depend on information many hops away. We therefore report, for each dataset, the accuracy gain from depth under the rebuild-from-scratch oracle. The central claim applies only to datasets where that gain is positive. Datasets where shallow models win are reported as outside the method's scope.
Proposed Experiments
We use two types of data. Discrete-snapshot node classification follows the protocol of the dynamic coarsening paper. Continuous-time streams come from TGB and from the temporal clustering datasets of Deep Temporal Graph Clustering, the latter evaluated with ARI, NMI and accuracy, the standard clustering-quality scores.
The decisive first check is the drift curve: the frozen operator's stability margin and its 64-layer accuracy, plotted against the number of edits. A flat curve falsifies the premise.
The second check is whether tracked SBP stays within one standard deviation of rebuild-from-scratch accuracy at depths of 64 and 128, while running at least ten times faster per update and outperforming residual GNNs on depth-favorable datasets.
The third check is the edge-noise sweep. If topology errors act through the stability margin, the gap between tracked and frozen operators should widen as corruption increases. Throughout, we report rank-based collapse metrics alongside accuracy, so that a model whose accuracy holds up while its features silently collapse is not counted as a success.
References
- A Signed Graph Approach to Understanding and Mitigating Oversmoothing
- Hierarchical Multi Scale Graph Neural Networks: Scalable Heterophilous Learning with Oversmoothing and Oversquashing Mitigation
- Adapting to Evolving Graphs: A Scalable Framework for Dynamic Coarsening
- Temporal Graph Rewiring with Expander Graphs
- Unsupervised Graph Embedding via Adaptive Graph Learning
- Temporal Graph Benchmark for Machine Learning on Temporal Graphs
- Rethinking Oversmoothing in Graph Neural Networks: A Rank-Based Perspective
- Are we measuring oversmoothing in graph neural networks correctly?
- The DiskANN library: Graph-Based Indices for Fast, Fresh and Filtered Vector Search
- Stationary signal processing on graphs
- Local and Global Optimization Techniques in Graph-Based Clustering
- Residual connections provably mitigate oversmoothing in graph neural networks
- Deep Temporal Graph Clustering: A Comprehensive Benchmark and Datasets