Many real graphs grow over time and mix several kinds of entities and links: a code-hosting graph where users open issues, push commits and fork repositories, or a forum where users reply, vote and subscribe. A model trained on such a stream must keep learning from new interactions without losing what it learned from old ones, a failure called catastrophic forgetting, and it usually must do so with a small, fixed memory for past data. Prior work on graph continual learning has found that replaying small connected pieces of past graphs works better than replaying isolated nodes. The reason is that a graph neural network (a model that computes each node's representation by passing messages along edges) needs the edges around a node to reproduce its past behavior. That evidence comes almost entirely from graphs with one node type and one edge type.
This note proposes that, on temporal heterogeneous graphs, the unit of stored memory should be a whole typed temporal motif: a small, time-ordered pattern of two or three interactions whose node types and relation types are recorded, such as "user opens issue on repo, then another user comments on that issue within a day." The opportunity is sharpest under a fixed storage budget. If a memory keeps individual edges sampled at rate $p$, a closed three-edge pattern survives intact only at rate about $p^3$, so random edge buffers mostly destroy the multi-relational structure the model relies on. We propose a cheap streaming method that selects and stores whole typed motifs. We also propose a benchmark protocol, built from the TGB 2.0 temporal heterogeneous datasets, that compares every memory strategy, including simple lookup heuristics, at the same byte budget.
Core Claim
At an equal storage budget, replaying whole typed temporal motifs reduces forgetting of link-prediction ability on temporal heterogeneous graphs more than three alternatives: replaying sampled edges, type-balanced edges, or untyped triads. It also beats a non-learned edge-lookup heuristic given the same budget. The advantage should be largest at small budgets and on datasets where many interactions sit inside closed typed patterns. Both predictions follow from the $p^3$ survival argument, and both can be falsified.
The proposal differs from its closest neighbors in specific ways. HERO replays subgraphs grown from diverse nodes along hand-specified meta-paths (fixed sequences of relation types, such as author–paper–author). It distills meta-path attention scores and is evaluated on domain-incremental node classification over discrete tasks. We need no meta-paths, work in continuous time, and target link ranking. OTGNet shows that triad replay beats isolated-node replay on temporal graphs. Its graphs have a single relation type, and its influence-function selection scales quadratically. We add types and use linear streaming selection. TGB 2.0 supplies the datasets and the ranking protocol, but it studies no continual setting. No paper in the file combines all three.
Research Program
The method. The streaming selector processes each arriving edge $(u, r, v, t)$, where $u$ and $v$ are nodes, $r$ is the relation type, and $t$ is the timestamp. It enumerates the two- and three-edge temporal motifs that this edge closes within a time window $\delta$, using a bounded sample of recent neighbors. This keeps the per-edge cost constant and the total cost linear in stream length, which avoids the quadratic selection costs that the file notes for OTGNet and for SAOT. Each motif is labeled by its motif class: the ordered tuple of its node types and relation types.
Allocating the budget. The memory budget is split across motif classes. Each class's share mixes its observed frequency with the current model's ranking loss on that class's recent instances. Every class gets a minimum share, so rare schemas do not disappear. This guards against the "vanishing minority class" effect that TACO found coarsening suffers. Within a class, instances are kept by reservoir sampling.
Handling old entities that keep changing. Stored motifs are refreshed rather than frozen. When a node in a stored motif gains new interactions, the motif becomes eligible for replacement by a newer instance of the same class. This handles the "evolving old" problem identified by LTF, and it avoids the frozen-history assumption behind PI-GNN.
Backbone. We use a temporal message-passing encoder with learnable edge-type embeddings in the style of Simple-HGN from Zhou et al.. Their result is a constraint on our design: well-tuned edge-typed attention matches meta-path models, so we deliberately avoid meta-path machinery. During replay, each stored motif is presented as a small temporal neighborhood mixed into the batches from the current task.
The benchmark protocol. This is the benchmarking contribution. Each TGB 2.0 dataset is cut chronologically into tasks. After training on each task, the model is evaluated on every past task's test window using TGB 2.0's type-aware negative sampling and time-aware filtered Mean Reciprocal Rank (MRR, the average inverse rank of the true link among sampled candidates). Edges that cross task boundaries are quarantined from training and validation, which addresses the leakage problem raised in the benchmarking literature.
All memory strategies get an identical byte budget. All learned methods get an identical hyperparameter-search budget, with model selection done only on validation windows, following the separation of selection and assessment argued by Errica et al.. We report Average Performance and Average Forgetting computed over MRR, following the metrics of CGLB. A second, schema-incremental variant introduces relation types progressively, which stresses new-type adaptation.
Baselines
The naive reference points are plain fine-tuning on each new task with no memory, and joint retraining on all data seen so far. The first sets the forgetting floor and the second the upper bound. Both use the same backbone and tuning budget. A useful result must close most of the gap between them.
Budgeted EdgeBank and recency/frequency lookup (RecB). These are the strongest non-learned competitors. In TGB 2.0, EdgeBank was the only method that scaled on tkgl-wikidata, with filtered MRR 0.535. On tkgl-icews, RecB reached 0.211 validation MRR against TLogic's 0.186 test MRR. For the temporal heterogeneous datasets we target (thgl-software, thgl-github, thgl-forum, thgl-myket), no reported result was found on Lacuna for EdgeBank or RecB. We will run both in two forms: unbudgeted, as in the original benchmark, and restricted to the same byte budget as our memory. Beating them means a higher Average Performance in MRR than budgeted EdgeBank at every budget. Coming within noise of unbudgeted EdgeBank would also be meaningful.
HERO. This is the strongest heterogeneous continual-learning method in the file. It reports 4.3% Average Forgetting on DBLP versus 26% for fine-tuning. On its own domain-incremental DBLP, IMDB, Freebase and Yelp setting, we will run HERO's released configuration and our method at matched memory. Beating it means equal or lower forgetting without meta-paths. On the TGB 2.0 protocol, HERO's meta-path subgraph sampler will replace our selector inside the same backbone.
OTGNet. OTGNet is the strongest temporal motif-replay method. It reports 73.88% Average Performance on Reddit versus 54.61% for TGAT with bias correction. We will run it with types discarded, at the same budget.
Ablations. Three ablations isolate the key ingredient. Reservoir edge replay tests whether motifs matter at all. Type-stratified edge replay tests whether type balance alone explains the gains. Untyped motif replay tests whether type labels matter. A fourth ablation removes the refresh rule to test whether keeping evolving old entities current matters.
Why not just…?
Why not just use EdgeBank, which never forgets? This is the most serious threat. Unbudgeted EdgeBank stores the entire history, so forgetting is not defined for it. That is exactly why the comparison must be made at equal storage. If a budgeted EdgeBank matches motif replay, the honest conclusion is that a learned model adds nothing under memory limits on these datasets, and we will report it as such. The $p^3$ argument predicts that budgeted EdgeBank degrades less gracefully than motif replay only when test links depend on closed multi-relational context. The closure-density analysis below tests that directly.
Why not just replay edges with a Simple-HGN-style encoder and skip motifs? Zhou et al. showed that edge-type embeddings on a plain attention network rival complex heterogeneous models, so a type-aware encoder with flat replay is a credible competitor. We adopt their encoder ourselves, so the only difference between the two arms is the memory unit. The type-stratified edge-replay ablation settles whether storing whole motifs beats storing the same number of bytes as balanced edges.
Why not just use a structure-agnostic memory of node features and degrees? Errica et al. and Carta et al. found that structure often adds little. However, Carta et al. also found that replay, not topology, is what prevents forgetting. Their evidence is from graph classification, whereas link prediction depends on structure by definition. We include a replay arm that stores node features plus degree statistics to measure this directly.
Proposed Experiments
The main experiment runs every method on the four TGB 2.0 temporal heterogeneous datasets, plus tkgl-smallpedia and tkgl-icews. We use five chronological tasks, three memory budgets (0.1%, 1% and 5% of stream bytes), and five seeds. We report Average Performance and Average Forgetting over filtered MRR, along with wall-clock time and peak memory.
Three decisive checks follow. First, at the smallest budget, motif replay must beat reservoir edge replay, type-stratified edge replay and budgeted EdgeBank by more than the variation across seeds. Second, across datasets and motif classes, the gain over edge replay should increase with the fraction of test links that close a typed motif. If it does not, the mechanism is wrong. Third, untyped motif replay should fall between edge replay and typed motif replay. A secondary run on HERO's benchmark tests whether meta-path-free motif memory matches meta-path distillation, which directly addresses the tension between HERO and Simple-HGN. A final scaling run on thgl-myket (53 million interactions) checks that selection time stays linear in stream length while the quadratic selectors used by OTGNet-style methods run out of time.
References
- Towards Heterogeneous Continual Graph Learning via Meta-knowledge Distillation
- Towards Open Temporal Graph Neural Networks
- TGB 2.0: A Benchmark for Learning on Temporal Knowledge Graphs and Heterogeneous Graphs
- SAOT: Self-Supervised Continual Graph Learning with Structure-Aware Optimal Transport
- A Topology-aware Graph Coarsening Framework for Continual Graph Learning
- A Selective Learning Method for Temporal Graph Continual Learning
- Continual Learning on Dynamic Graphs via Parameter Isolation
- Are we really making much progress?: Revisiting, benchmarking and refining heterogeneous graph neural networks
- A Fair Comparison of Graph Neural Networks for Graph Classification
- CGLB: Benchmark Tasks for Continual Graph Learning
- Catastrophic Forgetting in Deep Graph Networks: A Graph Classification Benchmark