Remembering Who Connects to Whom: Mixing-Aware Memory for Continual Graph Learning

Graph neural networks learn by letting each node average information from its neighbors. When a network changes over time and new categories of nodes keep appearing, these models forget old categories. The standard fix is to keep a small memory of past data and replay it while training on new data. We argue that current memories for graphs store the wrong thing. They keep what old nodes look like, but they throw away how classes connect to each other. In many real networks connected nodes are different on purpose: fraudsters link to victims, buyers to sellers, papers to venues. Networks of this kind are called heterophilous. The pattern of which class links to which class is often the most predictive signal, and it shifts over time. A memory built to look smooth erases this pattern, and replaying it teaches the model a wrong picture of the past.

We propose a replay memory that explicitly keeps the class-to-class connection pattern for each relation type. We call this pattern the mixing pattern. The memory also keeps the high-frequency part of node features, meaning how a node differs from its neighbors. We test whether this memory reduces forgetting on streams whose mixing pattern drifts. The claim is narrow and can be falsified. In class-incremental and time-incremental graph streams, a large share of forgetting comes from drift in the relation-specific class-compatibility structure. Low-pass memory condensation cannot preserve that structure. Matching it directly in the memory reduces forgetting by more than a heterophily-aware backbone combined with a standard memory does.

Why existing memories fail here

Three replay designs set the starting point, and all three motivate the gap. CaT condenses each past task into a tiny synthetic graph. It does this by matching the embeddings of a random graph encoder under maximum mean discrepancy (MMD, a distance between two sets of samples). It then trains only on these balanced synthetic sets, and reaches 64.5% accuracy on class-incremental CoraFull at a 1% memory budget. A random message-passing encoder mostly averages over neighbors, which makes it a low-pass filter. Complete the Missing Half shows that low-pass filtering discards the "diversification" half of the signal. That half carries roughly 10 points of accuracy on heterophilous graphs such as Texas and Cornell. Matching only low-pass embeddings therefore gives no guarantee that the condensed graph keeps that half.

DSLR goes further in the same direction. It rewires the replay buffer with structure learning, and the authors measure that this rewiring raises the homophily ratio of replayed nodes. That works on the citation and co-purchase graphs DSLR evaluates. On fraud or traffic graphs it would delete exactly the edges that matter.

LTF handles the hardest dynamic setting: old classes keep evolving while new ones arrive. It selects replay subsets by aligning feature distributions with MMD. It does not model how the connection structure between classes moves.

Two papers constrain the design. THeGCN shows that temporal graphs exhibit heterophily across both edges and time. Allowing negative neighbor weights raises PEMSLA accuracy from 48.27% (APAN) to 55.82%. Heterophily is therefore signal, not noise, in exactly the dynamic regime where continual learning is needed. Revisiting Homophily Ratio shows that a single homophily number is too coarse. A class-transition matrix, and the edge entropy computed from it, predicts GNN accuracy far better. That paper also finds label-edge mismatch artifacts in 5 of 6 standard heterophilous benchmarks. This tells us to verify our findings on controlled streams and not only on those benchmarks.

The closest bridge to heterogeneous graphs is HERO. It handles continual learning on graphs with multiple node and edge types. It uses meta-learning, replay subgraphs sampled along hand-specified meta-paths (chains of typed relations), and distillation of meta-path attention. HERO assumes smoothing along meta-paths and needs those paths defined in advance. Our memory works at the level of single typed edges, so it needs no meta-paths. It targets the drift in heterophily that HERO does not model.

Core Claim and Mechanism

For each relation type $r$ and time window $t$, let $C_r^{(t)}$ be the row-normalized matrix whose entry $(a,b)$ is the fraction of class-$a$ nodes' $r$-edges that land on class-$b$ nodes. This compatibility matrix is the object we argue is forgotten.

The synthetic memory for a past task consists of three parts: a small set of synthetic nodes with learnable features, labels, and a learnable typed adjacency. We fit it with the following objective:

$$ \mathcal{L}_{\text{mem}} = \sum_{r} \Big[ \mathrm{MMD}\big(Z^{\text{LP}}_r, \tilde Z^{\text{LP}}_r\big) + \mathrm{MMD}\big(Z^{\text{HP}}_r, \tilde Z^{\text{HP}}_r\big) \Big] + \lambda \sum_r \big\| C_r - \tilde C_r \big\|_F^2 . $$

Here $Z^{\text{LP}}_r$ are random-encoder embeddings that average over $r$-neighbors in the real task graph. $Z^{\text{HP}}_r$ are the matching "difference" embeddings, a node's features minus its $r$-neighbor average, following the high-pass channel of FB-GNN. Tildes denote the same quantities computed on the synthetic memory. $\lambda$ weights the compatibility term. The first term is CaT's objective restricted per relation type. The second and third terms are the new ingredients.

Because the compatibility term is computed per relation type rather than per meta-path, the memory can absorb a new relation type when it appears. It simply adds one more term, with no schema engineering.

The dynamic part is a refresh rule. For each old class we track the drift $\|C_r^{(t)} - C_r^{(t-1)}\|$ restricted to that class's row. The memory entries of old classes whose mixing has moved past a threshold are re-condensed from recent data. This is a cheap, targeted answer to LTF's "evolving old" problem, aimed at structure rather than features.

The backbone that trains on the memory can be any temporal or heterogeneous model. Our main runs use the backbones the comparison papers used: TGAT for temporal streams and a standard heterogeneous GNN for HERO's datasets.

Research Program

The work has three parts.

The first is diagnostic. On every stream we compute per-task changes in the compatibility matrices, in the scalar homophily ratio, and in WTGNN-style edge entropy. We then regress each baseline's per-class forgetting on these quantities. If compatibility drift does not explain forgetting beyond feature drift, the premise fails and we stop.

The second is the memory itself. We build it on top of CaT's training-in-memory protocol, so that any gain is attributable to what the memory stores.

The third is a controlled drift generator. We take the label sequence of an existing stream and rewire edges between windows to hit a target compatibility matrix, while holding node features and degree sequences fixed. This lets us dial homophily drift from zero to a full reversal. It also sidesteps the label-edge mismatch artifacts that weaken conclusions drawn only from Texas or Cornell.

Baselines

The naive reference points are fine-tuning and the "Bare" model trained from scratch on each task. Their reported numbers are LTF's TGAT fine-tuning results: an Average Precision of 0.0141 on Yelp and an Average Forgetting of 0.1550 on Reddit. HERO reports 26% forgetting on DBLP. We rerun both naive models in our pipeline. BeGin finds that Bare often has the best Intransigence, meaning it learns the current task most easily. We therefore report Intransigence alongside forgetting, so we cannot win on forgetting by freezing plasticity.

The strongest existing methods differ by regime, and we run each on its home benchmark with its released settings and the same memory budget as ours.

On temporal class-incremental streams the strongest method is LTF. It reports an Average Precision of 0.0682 on Yelp against 0.0648 for OTGNet, and an Average Forgetting of 0.0474 on Reddit. Beating it means higher Average Precision and lower Average Forgetting on Yelp and Reddit, averaged over at least five seeds and outside seed variance, at matched memory size and wall-clock budget. LTF reports 72 seconds per epoch on Amazon; we will report our time per epoch the same way.

On static class-incremental streams the strongest is CaT. It reports 64.5% on CoraFull at a 1% budget, so beating it means exceeding that at the same 1% ratio. CaT is also our direct parent. Our variant with $\lambda = 0$ and no high-pass term is CaT made relation-aware, which isolates the compatibility term.

On heterogeneous streams the strongest is HERO. It reports 4.3% Average Forgetting on DBLP and a +2.7% Average Precision gain over its strongest baseline. We run it with its predefined meta-paths, which gives it extra prior knowledge that our method does not use.

DSLR is run with and without its homophily-raising rewiring, as the explicit "make memory homophilous" competitor.

The key ablations remove the high-pass term, the compatibility term, and the drift-triggered refresh, one at a time. Hyperparameters for all methods get the same search budget on a held-out early segment of each stream.

Why not just…?

Why not just swap in a heterophily-aware backbone and keep the existing memory? This is the most serious threat. A THeGCN-style or FB-GNN-style backbone trained on CaT or LTF memory might recover most of the gain. We settle it with a two-by-two factorial: low-pass versus dual-channel backbone, crossed with standard versus mixing-aware memory, on both real and synthetic-drift streams. Our hypothesis predicts an interaction. The backbone helps only if the memory still contains the high-frequency and compatibility information it needs, and a low-pass-condensed memory has already discarded it. If the heterophily-aware backbone with standard memory matches our memory, the claim is wrong, and we will report it that way.

Why not just freeze a random encoder and avoid drift altogether? The Unreasonable Effectiveness of Randomized Representations shows this is strong in online continual graph learning, because nothing drifts. But a frozen low-pass encoder fixes in advance the assumption about how classes connect. The WTGNN results (87.29% versus GCN's 58.38% on Texas) show how much relation-aware modeling is worth when edges are predictive. We include the frozen-random baseline in both low-pass and dual-channel forms. We expect it to be competitive under zero drift and to degrade as the drift generator reverses the mixing pattern. If it does not degrade, adaptation is not needed in this regime.

Why not just store a larger buffer of raw subgraphs? Raw subgraphs keep their true edges and so keep the mixing pattern automatically. The question is cost. We give raw-subgraph replay, with coverage-based node selection as in DSLR, a sweep of memory budgets measured in stored bytes. We report the budget at which it matches our memory. If it matches at the same byte budget, condensation adds nothing here.

Why not just prune heterophilous edges as DSLR does? DSLR's rewiring buys buffer efficiency on homophilous graphs: its 1–2% buffer matches 3% without rewiring. We expect it to hurt where heterophilous edges carry the label signal. THeGCN's gain from negative neighbor weights and FB-GNN's high-pass channel both point that way. Running DSLR with and without rewiring on the fraud-style and traffic streams tests this directly.

Proposed Experiments

The temporal streams are LTF's Yelp, Reddit, and Amazon class-incremental settings with a TGAT backbone. The heterogeneous streams are HERO's DBLP, IMDB, and Freebase, plus BeGin's time-incremental ogbn-mag scenario. We also include the PEMS traffic graphs from THeGCN, converted to class-incremental streams. No reported continual-learning result was found on Lacuna for PEMS, so the baselines will be run by us. CoraFull and Reddit follow CaT's class-incremental protocol. Metrics are BeGin's Average Performance, Average Forgetting, and Intransigence, plus memory bytes and time per epoch.

The first decisive check is the diagnostic regression: compatibility drift must predict baseline forgetting beyond feature drift and scalar homophily change. The second is the factorial backbone-by-memory interaction. The third is the controlled drift sweep. The gap between our memory and CaT/LTF should grow monotonically with the injected compatibility drift and vanish near zero drift. A flat gap would mean the gains come from something other than remembering who connects to whom.