Signed Residuals for Streaming Heterophily-Aware Graph Embeddings

Many fast graph neural networks work by "decoupling": they spread node features across the graph once, as a preprocessing step, and then train an ordinary neural network on the resulting vectors. On a graph that changes over time, those precomputed vectors go stale. The best current fix updates them locally with a "push" procedure, which moves leftover correction mass only through the neighborhoods an edge change touched. This fix has two weaknesses. It handles edge insertions but treats deletions as an open problem, and it only supports the smoothing (low-pass) operators that assume neighbors are alike. Deleting an edge, and computing the "neighbor-difference" (high-pass) features that graphs of unlike neighbors (heterophily) need, cause the same difficulty: the correction mass becomes signed, with positive and negative parts that should largely cancel. Random-walk sampling is the usual cheap way to finish an estimate. With signed mass it does badly, because its noise grows with the total absolute mass rather than with the small net amount left after cancellation.

We propose a hybrid estimator that combines deterministic push with random-walk sampling and is built around signed correction mass. Its central rule is to push deterministically wherever nearby positive and negative mass is about to cancel, and to sample only mass whose sign is locally consistent. The rule is cheap to evaluate in advance. It replaces the fixed global threshold that decides when to stop pushing and start sampling. We would use it to keep a bank of multi-hop feature propagations current on sliding-window graph streams, which have constant insertions and deletions. Those propagations feed a heterophily-aware classifier in the style of LD2. The claim to be tested is concrete: under edge churn, the cancellation-aware rule matches the accuracy of full recomputation at a fraction of the cost of either pure push or pure sampling. It should also beat fixed-threshold hybrids, whose error rises as churn accumulates.

Core Claim

The claim rests on one standard identity and one observation about it. For personalized-PageRank-style propagation with restart probability $\alpha$, a push algorithm keeps an estimate $\hat\pi$ and a residual vector $r$, the correction mass not yet spread. They satisfy the exact invariant

$$\pi(s,\cdot) = \hat\pi(s,\cdot) + \sum_u r(u)\,\pi(u,\cdot),$$

where $\pi(u,\cdot)$ is the true propagation vector from node $u$. The same identity holds column by column when node features replace the source indicator. FORA (Efficient Algorithms for Approximate Single-Source Personalized PageRank Queries) and GBP (Scalable Graph Neural Networks via Bidirectional Propagation) estimate the residual sum by starting walks from residual nodes. When residuals can be negative, the natural unbiased estimator starts walks in proportion to $|r(u)|$ and weights each walk by the sign of $r(u)$. Its variance scales as $R^2/n_w$, where $R=\sum_u |r(u)|$ is the total absolute residual and $n_w$ is the number of walks.

The observation is that sampling cannot cancel mass but push can. When an edge is inserted and later deleted, or when the high-pass operator $I-P$ is applied (with $P$ the random-walk transition matrix), the result is positive residual at some nodes and negative residual at their neighbors. Their net effect on $\pi$ is small, but $R$ stays large, so sampling has to fight the full $R$. A single push step moves both signs onto shared neighbors, where they cancel exactly in storage. The quantity that should decide whether to push or sample is therefore the local cancellation gain. For a node $u$ with out-degree $d_u$, this is the drop in $R$ that pushing $u$ would cause:

$$\Delta_u = |r(u)| - \sum_{v \in N(u)} \Big( \big|r(v) + (1-\alpha)\,r(u)/d_u\big| - |r(v)| \Big).$$

It costs $O(d_u)$ to compute. We push greedily while $\Delta_u/d_u$ exceeds the marginal cost of the extra walks that $|r(u)|$ would otherwise require. The remainder goes to signed sampling. When all residuals are nonnegative, the rule reduces to a FORA-style balance. It differs from FORA exactly in the regime created by deletions and high-pass filters.

Research Program

The work has three parts.

The first part is the estimator. We will build signed forward and reverse push with the cancellation-gain rule and signed Monte Carlo completion. We will prove an error bound in terms of $R$ at the point where sampling starts. We will also prove that the greedy rule never leaves a larger $R$ than a fixed-threshold push with the same push budget.

The second part is dynamic maintenance. On each edge event we apply the standard local residual correction used by Decoupled Graph Neural Networks for Large Dynamic Graphs. We extend it to deletions by letting the correction be negative, and we run the consolidation rule lazily, only when $R$ at a node crosses a budget. Random walks are stored in an index as in FORA+. Walks that traverse a deleted edge are invalidated and resampled, and we measure that cost directly.

The third part is the heterophily layer. Here the design choice follows from the skeptic's strongest objection, discussed below. We will not write a special signed estimator for each high-pass filter. Instead we maintain a bank of hop-wise propagations $P^jX$ for $j=0,\dots,K$ and let the downstream network learn signed combinations of them. This is the monomial-sum form of Linear Graph Convolutional Networks. It can express LD2's inverse-Laplacian high-pass channel and its 2-hop channel (LD2), as well as FB-GNN's low-pass plus high-pass pair (Complete the Missing Half). One signed walk supplies estimates for every hop at once, so errors across hops are positively correlated. They partly cancel in the difference terms that high-pass combinations form, and we will measure how much. Because only the learned combination weights encode homophily, the model can respond to local homophily drift by cheap refitting of the last layer rather than by recomputing propagation. We test this directly.

Baselines

The naive reference is an MLP on raw node features with no propagation. CLP (Simplifying Node Classification on Heterophilous Graphs with Compatible Label Propagation) and LD2 report that MLPs trail structure-aware models on heterophilous graphs. We run it with the same tuning budget as every other model, and any method that fails to beat it has no case.

The accuracy ceiling is LD2 recomputed from scratch after every snapshot, with its exact A2Prop power iteration. It represents what freshness costs if cost is ignored. No reported result found on Lacuna for LD2's per-dataset accuracy. The file gives only LD2's efficiency figures: training on wiki in under one minute with under 5GB of GPU memory. We therefore rerun it ourselves on each benchmark. Beating it means matching its accuracy within one standard deviation across seeds at a small fraction of its total update wall-clock.

The strongest dynamic competitor is the incremental deterministic push of Zheng et al., Decoupled Graph Neural Networks for Large Dynamic Graphs. We extend it to allow negative residuals so that it can process deletions, and give it the same monomial bank and downstream model. That paper reports an F1-Micro gain of 13.6% over the next best baseline on GDELT, a 41% MRR gain over ROLAND on Bitcoin-OTC, and 2 seconds per epoch on Wikipedia, against 12 seconds for TGN and 147 seconds for TGAT. These are relative figures, and the file gives no absolute accuracies, so we reproduce the method under our protocol. Beating it means lower update cost at equal accuracy under deletion-heavy windows, or equal cost with lower drift in estimation error over time.

Two further estimation baselines complete the comparison. One is pure signed Monte Carlo. The other is a FORA/GBP-style hybrid with a fixed global $r_{\max}$ tuned once on the first window. The key ablation swaps our cancellation-gain rule for that fixed threshold and keeps everything else identical. This isolates the one new ingredient.

All methods get the same machine, the same walk and push budgets expressed in edge touches, and the same hyperparameter search for the downstream network. Estimation error is scored against exact recomputation on sampled checkpoints.

Why not just…?

Why not just use deterministic incremental push with negative residuals and skip sampling entirely? This is the real threat, and it is the baseline we most expect to be competitive. Deterministic push cancels mass exactly, so on small or low-degree graphs it may simply win. Its weakness is cost when deletions touch hubs, since push work scales with degree times residual mass. This is the same "state explosion" that motivated FORA's move to sampling on scale-free graphs. The fixed-budget experiments on skewed-degree streams will settle it. If deterministic push matches our cost on the large streams as well, the sampling component is not justified, and we would report that.

Why not just maintain low-pass propagations and form high-pass features as linear combinations? We adopted this; it is the monomial bank in the third part of the program. What it does not remove is signed residuals from deletions, which occur regardless of the filter. It also inherits error amplification when combination weights alternate in sign, which is why we measure hop-correlated error rather than assume it is harmless.

Why not just recompute periodically? LD2's full pass is $O(m)$ per refresh. The staleness-versus-cost curve (accuracy on fresh nodes against refresh interval) directly shows whether any refresh rate matches incremental maintenance at equal compute.

Why not just sample walks on the fly? FORA shows that pure sampling is slower by a factor of $1/\epsilon$ on scale-free graphs even without signs. With signed mass its variance grows with $R^2$. The pure signed Monte Carlo baseline measures this directly.

Proposed Experiments

Streams are built from the file's benchmarks. We use arxiv-year and snap-patents, whose heterophily comes from year labels, streamed by node timestamp. We use sliding windows over Bitcoin-OTC, GDELT and Wikipedia, where edges expire and so give real insertion–deletion churn. We also run a large-scale stress test on a windowed stream derived from MAG, following Zheng et al., and a scalability check on Friendster with synthetic churn. Metrics are accuracy or F1-Micro for node classification and MRR for link prediction, together with update latency, total edge touches, and relative $\ell_1$ estimation error against exact propagation.

The decisive check has two parts. First, as window churn rises, the fixed-$r_{\max}$ hybrid's estimation error should grow roughly with accumulated $R$ while ours stays flat. Second, a plot of $R$ before sampling against realized error should follow the predicted $R/\sqrt{n_w}$ scaling.

A second check targets heterophily drift. We synthetically rewire a fraction of edges across classes midway through a stream. We then ask whether refitting only the combination weights, on top of maintained propagations, recovers the accuracy of full LD2 retraining. If it does not, homophily drift requires changing the propagation itself, and the design of the third part would need revisiting.