A graph neural network (GNN) labels each node by repeatedly averaging information from its neighbors. When such a model runs on a graph that keeps changing, such as a transaction network or a citation graph, every inserted or deleted edge can in principle change the predictions of every node within a few hops. Keeping predictions exactly current means recomputing that whole region for each batch of edits. This proposal starts from a simple observation that streaming graph systems have already exploited for classical algorithms: most edits do not matter. The key question is which ones do. Our claim is that, for a trained GNN, one cheap quantity predicts how much an edge edit will move the model's outputs. That quantity is how different the edge's two endpoints look to the model, divided by how well-connected the receiving endpoint already is. Edits with a low score can be buffered and applied lazily in large batches. Edits with a high score are propagated immediately.
The second half of the claim is less comfortable, and it is the scientific point of the work. Architectures designed to stop over-smoothing (the collapse of node representations toward a single uniform state as layers are stacked) and to handle heterophily (graphs where linked nodes tend to differ) do so by refusing to average away differences between neighbors. That same property should make them more sensitive to each structural edit. The ordinary low-pass GCN smooths perturbations away, so it is cheap to keep current, but it is inaccurate on heterophilous graphs. Signed or high-pass models are more accurate, but many more of their incoming edges are "unsafe." We propose to measure this trade-off directly and to build the lazy-batching policy that exploits it.
Core Claim
Consider an $L$-layer message-passing model $f$ deployed on graph $G$. For an edge edit $e=(u,v)$, define the deferral error $\delta_e = \max_{w} \lVert f(G \oplus e)_w - f(G)_w \rVert$, the largest change the edit causes in any node's output. We hypothesize that $\delta_e$ is well predicted by
$$s_e = \gamma_f \left( \frac{\lVert z_u - z_v \rVert}{d_u + 1} + \frac{\lVert z_v - z_u \rVert}{d_v + 1} \right),$$
where $z_u$ is node $u$'s cached first-layer representation, $d_u$ is its current degree, and $\gamma_f$ is a single model-specific gain. The gain is calibrated once on a held-out set of edits and captures how much the architecture amplifies or damps a one-hop perturbation across its remaining layers.
The form of the bracketed term comes from the degree-normalized aggregation step. Adding one neighbor to a node of degree $d$ shifts its aggregated input by roughly the neighbor's feature difference divided by $d+1$. The ratio of discordance to degree is not arbitrary. It is the edge-level counterpart of the two node quantities that Two Sides of the Same Coin shows jointly govern GCN failure: local homophily and relative degree. That paper proves that nodes with high homophily but low relative degree drift across decision boundaries and then act as heterophilous neighbors to others, a cascade the authors call "pseudo-heterophily." We read this as a prediction about dynamics. Discordant edges landing on weakly supported nodes are exactly the edits that start such cascades, so they are the ones that cannot wait.
The over-smoothing half of the claim is that $\gamma_f$ is small for plain GCNs and large for models that preserve high-frequency signal. Complete the Missing Half adds a high-pass "diversification" channel. GGCN adds signed messages and degree corrections. Ordered GNN gates hidden dimensions by neighborhood depth. All three keep neighbor differences alive through depth, and that is why they survive 64 layers. We therefore expect that, at matched prediction freshness, the fraction of edits that must be processed eagerly rises with the model's resistance to over-smoothing. We also expect it to track the effective rank (an entropy measure of how many directions the representations spread across) of the final-layer representations. Are we measuring oversmoothing in graph neural networks correctly? introduced effective rank as a diagnostic that correlates with accuracy at 0.91, where Dirichlet energy fails. We would add a second reading: effective rank also indicates how expensive a model is to keep current.
Where This Sits
The mechanism for splitting edits comes from RisGraph. That system separates "safe" updates, which leave an algorithm's dependency tree unchanged and can run in parallel, from "unsafe" ones that must be handled carefully, and it reports that fewer than 20% of real streaming updates are unsafe. RisGraph's split is exact and applies only to monotone algorithms like breadth-first search. Ours is approximate, learned-model-specific, and applies to continuous representations, which RisGraph does not attempt. The case for large batches comes from Parallel Batch-Dynamic Graph Connectivity, which shows that amortized work per edge falls as $O(\log n \log(1+n/\Delta))$ as the batch size $\Delta$ grows. Low-score edits are exactly those we can afford to hold until a batch is large. Dynamical SimRank search on time-varying networks suggests a further saving: edits sharing a destination can be coalesced. We reuse that idea by grouping buffered edits by receiving node, so each affected region is recomputed once per flush.
Several papers constrain the design rather than supply it. The research file frames batch size as being in tension with rank collapse. That framing is misleading, and correcting it is part of the contribution. If each batch is recomputed exactly, batch size changes only cost, not predictions, because the final receptive field is the same. Batch size affects accuracy only when some edits are deferred. The real trade-off is therefore staleness against work, and our score is what governs it. Spectral Graph Pruning Against Over-Squashing and Over-Smoothing shows that deleting inter-class edges once at initialization with PROXYDELETE can raise GCN accuracy on Roman-Empire from about 70% to about 78%. This matters for us because a discordant incoming edge is both high-score and a candidate for pruning, so a policy could drop such edges rather than propagate them. We treat dropping as a separate arm and do not assume it. Temporal Graph Benchmark is a warning. On streaming node-affinity tasks, a moving average beats TGN, so any learned streaming method must be compared against trivial heuristics. HarmonyGNNs documents duplicate-node leakage in unfiltered Chameleon and Squirrel, so we use only filtered versions.
Research Program
The work has three parts.
The first is a measurement study. We train six architectures on each static graph: a plain GCN at depths 2, 8 and 32, the filterbank model, GGCN, and Ordered GNN. We then replay the graph as an edit stream. Streams are built by holding out a portion of edges and re-inserting them, mixed with deletions, in batches of size $\Delta$ ranging from 1 to $10^5$. Where edges carry timestamps, as with arXiv-year, we replay them in real order. For a large sample of individual edits we compute the exact $\delta_e$ and ask two questions. First, how heavy-tailed is the distribution? Second, how much of its variance does $s_e$ explain, compared with discordance alone, degree alone, and the size of the $L$-hop affected region? We also relate each model's calibrated $\gamma_f$ and its eager-edit fraction to its final-layer effective rank and to its accuracy, which tests the trade-off claim across architectures.
The second part is the policy. Arriving edits are scored against cached first-layer representations. Edits above a threshold $\tau$ trigger an immediate recomputation of their $L$-hop region. Edits below it enter a buffer that is flushed and coalesced by destination either when the buffer reaches a size limit or when the accumulated score of its edits exceeds a budget. Summing scores is a first-order bound on combined drift, and we check that it stays valid when many small edits hit the same node. Cached representations are refreshed only for recomputed regions. We also verify that the score stays predictive when caches are themselves stale. A third arm replaces "propagate immediately" with "drop" for inserted edges whose score comes mostly from discordance, which gives a streaming analogue of pruning.
The third part is a small theoretical piece. For a linear GCN we bound $\delta_e$ by $s_e$ times the product of the layer operators' norms restricted to the affected region. This shows why $\gamma_f$ is below one for contracting low-pass models. We then characterize when adding a high-pass channel pushes it above one. We do not expect a tight bound for nonlinear signed models and will not claim one.
Baselines
The naive reference point is a frozen model with never-updated predictions: the graph changes but outputs are left as they were at deployment. It costs nothing and shows how much staleness actually hurts on each stream. If it is already close to fresh predictions, the problem is not worth solving on that dataset, and we will say so.
The accuracy ceiling is exact recomputation of the $L$-hop affected region for every batch. We run it with the same trained weights, on the same hardware, and with the same coalescing. Every policy is scored by prediction agreement with this ceiling and by accuracy against labels, plotted against total node-layer recomputations and wall-clock latency. For which architectures to use, the strongest static models in the file are the right anchors. Ordered GNN reports 89.10% accuracy on Cora at 64 layers, against 52% for a standard GCN, and 62.44% on Squirrel. The Squirrel figure is on the unfiltered version, so we will re-run it on filtered Squirrel rather than quote it. GGCN reports the best average rank across nine datasets (1.78). For incremental GNN inference cost on any of these benchmarks, no reported result was found on Lacuna, so the exact-recomputation ceiling is established within this project.
The ablations isolate the key ingredient, the combination of discordance and degree in one score. We compare deferral by discordance alone, by inverse degree alone, by affected-region size, and uniformly at random, each at matched recomputation budget. The proposal beats these ablations if, at 99% agreement with the ceiling, it needs clearly fewer recomputations than every alternative, and if that advantage is largest on heterophilous graphs, where discordance varies most. The pruning arm is compared against running PROXYDELETE on the initial graph and freezing the result.
For the TGB node-affinity tasks, the strongest competitor is the moving-average heuristic, which reports NDCG@10 of 0.559 on tgbn-reddit versus 0.315 for TGN in Temporal Graph Benchmark. Beating it is not the goal of this proposal. We include it so that any claim about keeping a GNN fresh is placed next to a method that needs no freshness at all.
Why not just…?
Why not just recompute the affected region for every batch, since large batches already make that cheap? This is the most serious threat. The amortization result in Parallel Batch-Dynamic Graph Connectivity implies that when latency does not matter, one should take huge batches and recompute everything. Our policy matters only where small batches are forced by latency needs, such as fraud scoring at millisecond scales, the regime RisGraph targets. The batch-size sweep will locate the crossover explicitly. If exact recomputation at the smallest acceptable $\Delta$ already fits the budget, we report that lazy deferral is unnecessary for that workload.
Why not just use a model that ignores the graph, like a node-wise MLP or a moving average? Such models have zero update cost and cannot over-smooth. Two Sides of the Same Coin reports that GGCN was the only model it tested to consistently beat an MLP on heterophilous graphs, and the filterbank paper reports gains of roughly 10% over a plain GCN on Texas and Cornell. So graph structure does carry signal. Still, we train an MLP on every dataset. Wherever it matches the heterophily-aware models on filtered benchmarks, the trade-off we study disappears, and that result is reported as such.
Why not just use a shallow two-layer model so each edit touches few nodes? Depth is one axis of our sweep, and a two-layer GCN will be among the cheapest models to keep current. The question is whether shallow models give up accuracy on heterophilous graphs. The file suggests they do, since plain GCNs fail on Texas and Cornell even at two layers. The measured curve of freshness cost against accuracy across depths settles this, not assertion.
Why not just defer every edit outside a fixed hop radius, or defer uniformly at random? These are the ablations above. If affected-region size predicts $\delta_e$ as well as our score, the homophily-based part of the proposal is unnecessary, and we would reduce the method to region-size scheduling.
Proposed Experiments
We run on filtered Chameleon and Squirrel, Roman-Empire, and Amazon-Ratings as heterophilous graphs; on Cora, PubMed and ogbn-arxiv as homophilous graphs; on arXiv-year as a real-time-ordered heterophilous stream; and on tgbn-reddit and tgbn-trade as TGB streams. Four outcomes are decisive.
The first is whether $s_e$ explains substantially more of the variance in exact deferral error than any single-factor score, across all six architectures. The second is whether the calibrated gain $\gamma_f$ and the eager-edit fraction at 99% agreement rise from GCN to filterbank, GGCN and Ordered GNN, and whether they correlate with final-layer effective rank. If they do not, the "cost of resisting over-smoothing" claim is false and we will report that. The third is whether, on arXiv-year and the TGB streams, the policy reaches 99% agreement with exact recomputation using a small fraction of its node-layer work at small batch sizes, and whether that advantage shrinks toward zero as $\Delta$ grows, as amortization predicts. The fourth is whether edits landing on nodes with high homophily and low relative degree account for a disproportionate share of the edits that flip predictions, which would give direct streaming evidence for the pseudo-heterophily cascade proposed in Two Sides of the Same Coin.
References
- Two Sides of the Same Coin: Heterophily and Oversmoothing in Graph Convolutional Neural Networks
- Complete the Missing Half: Augmenting Aggregation Filtering with Diversification for Graph Convolutional Networks
- Ordered GNN: Ordering Message Passing to Deal with Heterophily and Over-smoothing
- Are we measuring oversmoothing in graph neural networks correctly?
- RisGraph: A Real-Time Streaming System for Evolving Graphs to Support Sub-millisecond Per-update Analysis at Millions Ops/s
- Parallel Batch-Dynamic Graph Connectivity
- Dynamical SimRank search on time-varying networks
- Spectral Graph Pruning Against Over-Squashing and Over-Smoothing
- Temporal Graph Benchmark for Machine Learning on Temporal Graphs
- HarmonyGNNs: Harmonizing Heterophily and Homophily in GNNs via Self-Supervised Node Encoding