Topology-Consistent Curvature for Online Graph Learners

Quasi-Newton optimizers speed up training by learning the shape of the loss surface. They do this from pairs of gradients: how much the gradient changed when the parameters moved. In streaming data that signal is easily drowned by noise, because the two gradients are usually computed on different data. On a growing graph there is a second source of noise that the optimization literature has not named. Between two steps, new edges arrive. They change the neighborhoods, and therefore the inputs, of the very nodes used to measure curvature. We propose to separate this "topological noise" from real curvature. The method computes both gradients of each curvature pair on the same nodes and under the same frozen snapshot of their neighborhoods. The fixed set of nodes comes from the replay buffer that online graph learners already keep to avoid forgetting. The result is a cheap, stable quasi-Newton optimizer for streaming node classification, and a direct test of whether second-order methods help at all in this setting.

The setting is unusually favorable for a clean test. Online Continual Graph Learning showed that on node-arrival streams a single-hop feature average followed by a linear classifier with reservoir replay (LINEAR) matches or beats deep graph neural networks under the requirement that the model can be queried accurately at any moment. LINEAR's loss is convex logistic regression on aggregated features. That is exactly the regime where online quasi-Newton methods have guarantees and reported wins. Here, though, the inputs move underneath the optimizer as the graph grows.

Core Claim

Let $w_k$ be the parameters at step $k$, $V$ a set of nodes, $\mathcal{E}_k$ the edge set at step $k$, and $g(w; V, \mathcal{E})$ the gradient on nodes $V$ with features aggregated over edges $\mathcal{E}$. The curvature vector that a streaming quasi-Newton method would compute splits into three parts:

$$y_k = \underbrace{g(w_{k+1}; V, \mathcal{E}_{k}) - g(w_k; V, \mathcal{E}_k)}_{\text{curvature}} + \underbrace{g(w_{k+1}; V, \mathcal{E}_{k+1}) - g(w_{k+1}; V, \mathcal{E}_k)}_{\text{topological noise}} + \text{(batch noise if } V \text{ changes)}.$$

Existing consistency mechanisms only address the third term. A Stochastic Quasi-Newton Method for Online Convex Optimization (oBFGS/oLBFGS) evaluates both gradients on the same mini-batch. A Multi-Batch L-BFGS Method for Machine Learning computes curvature on the overlap between consecutive batches. Both assume samples are independent vectors. On a graph, keeping the node set fixed does not keep the inputs fixed.

Our claim has three parts. First, the middle term is large exactly where streams are hard: near high-degree hubs and during bursts of arrivals. Second, it is what drives curvature pairs to fail the positivity check $s_k^\top y_k > 0$, where $s_k = w_{k+1}-w_k$. Third, removing it is nearly free. For each replay-buffer node we cache its aggregated feature at step $k$ and reuse that cached feature for the second gradient. The buffer then acts as a standing overlap set. This addresses the "overlap bottleneck" the multi-batch line leaves open, because overlap no longer depends on consecutive stream batches sharing samples. The extra cost is one gradient on the buffer per curvature update, not a second pass over fresh data.

Research Program

The work has three parts.

The first is measurement. On real node streams we log, for every step, the three terms above separately. This is possible because the cached and refreshed aggregated features are both available. We relate the size of the topological term to how many new edges arrived inside the receptive field and to node degree. We also measure the condition number of LINEAR's loss Hessian on each stream. This tells us honestly whether there is ill-conditioning for a second-order method to fix.

The second is the optimizer. It is oLBFGS with two changes. The parameter step uses fresh stream nodes plus replay, as LINEAR does. Curvature pairs are computed only on buffer nodes under their cached neighborhood snapshot. We keep the cautious-update threshold from the multi-batch work, so any remaining non-positive pairs are skipped rather than damped heuristically. When reservoir sampling evicts buffer nodes, the curvature set shrinks for that step. We study how the size of the curvature set trades variance against cost.

The third is a small theory piece. It is a regret bound for this optimizer on a convex loss whose inputs drift. It should show that topology-consistent pairs keep the inverse-Hessian estimate bounded and positive definite under bounded edge-arrival rates. The naive pairs only get there through skipping, at a rate that grows with churn.

We deliberately do not attach second-order machinery to deep temporal graph networks. The problem there is non-convex, and the curvature pairs are already unstable without any churn. That would confound the question.

Baselines

The naive reference point is LINEAR exactly as specified in Online Continual Graph Learning, trained with its first-order optimizer. That paper reports an Average Anytime Performance of 87.75% on Reddit, against 86.66% for the deeper PDGNN model. That 87.75% is the number to beat on Reddit. For the heterophilous Roman Empire stream, where the same paper says LINEAR struggles, no reported result found on Lacuna for LINEAR's accuracy. We will rerun it ourselves.

The strongest first-order competitor is LINEAR with a tuned Adam optimizer. To make the comparison fair, Adam gets the extra compute our method spends on curvature, as a larger replay mini-batch. Both methods receive the same hyperparameter search budget over learning rate and buffer size on a held-out prefix of each stream.

The strongest existing second-order competitor is the multi-batch L-BFGS idea applied directly. Curvature is computed on the same buffer nodes, but with features re-aggregated on the current graph. This uses the cautious-skip rule from A Multi-Batch L-BFGS Method for Machine Learning. This baseline is the key ablation. It differs from our method only in whether neighborhoods are frozen, so any gap isolates the topological-consistency ingredient.

We also run oLBFGS with independent consecutive batches. This is the configuration both quasi-Newton papers report as unstable, and it serves as the lower bound for second-order methods. As an upper reference we include LINEAR retrained to convergence on the current snapshot at each evaluation point. It is infeasible online but indicates headroom.

Beating the field means three things. Our method must exceed tuned Adam on Average Anytime Performance with equal wall-clock per arriving node. It must show lower forgetting. And it must show a markedly lower rate of skipped curvature pairs than the node-only-overlap ablation under high churn.

Why not just…?

Why not just use Adam, which already adapts per-coordinate step sizes? This is the real threat. If LINEAR's loss on these streams is well-conditioned, a diagonal method will capture nearly everything, and our gains will be within noise. The overview and oBFGS work argue that diagonal scaling cannot fix rotated, off-diagonal ill-conditioning, but that is an argument, not evidence on graph streams. The measurement phase settles it directly. We will report the Hessian condition number per stream and the gap to tuned, compute-matched Adam. If the gap is negligible wherever conditioning is mild, we will say so. The contribution then narrows to the high-degree-skew streams where conditioning is poor.

Why not just keep cautious skipping with node-level overlap and accept some rejected pairs? Skipping guarantees safety, not progress. If topological noise causes most pairs to be rejected during bursts, the inverse-Hessian estimate goes stale exactly when the data shifts. The node-only-overlap ablation tests this directly. Our prediction is that its skip rate rises with edge-arrival rate while ours stays flat. If both stay flat, topological noise is not a practical problem, and the idea is falsified.

Why not just periodically retrain on a snapshot? Subset Node Representation Learning over Large Dynamic Graphs reports that incremental updates on Enwiki20 take 8.5 minutes where full-graph baselines take days. The online setting also requires the model to be usable at every moment. Snapshot retraining is therefore our upper reference, not a competitor.

Why not just freeze the whole graph for a window, as lazy-Hessian methods freeze curvature? Second-Order Optimization with Lazy Hessians reuses stale curvature under a static objective. Freezing the graph for the parameter step as well would make the model blind to new edges for the whole window and hurt anytime accuracy. We freeze neighborhoods only inside the curvature measurement, never inside the prediction path. A window-freezing variant will be included to quantify this cost.

Proposed Experiments and Decisive Checks

We use the node-arrival streams of Online Continual Graph Learning on Reddit and Roman Empire. We add Cora and Citeseer task sequences in the protocol of Continual Graph Learning, which reports a forgetting mean of 34.97% for vanilla GAT and 23.09% for its influence-based replay on Reddit. We also build a synthetic stream in which we control degree skew and feature conditioning. Metrics are Average Anytime Performance, forgetting, the fraction of skipped curvature pairs, and wall-clock per arriving node.

The decisive check is the synthetic sweep. As degree skew and edge-arrival rate increase, the node-only-overlap baseline should lose accuracy and skip more pairs, while the topology-consistent version should not. Tuned Adam should fall behind only as conditioning worsens. If the measured topological-noise term is small relative to curvature on all real streams, or if compute-matched Adam closes the gap on Reddit and Roman Empire, we will report that second-order curvature is not worth maintaining in this regime. That is itself a useful answer to the question the field keeps raising.