Graph neural networks that learn from streams of timestamped interactions usually keep a running summary vector, a "memory", for every node and update it each time the node takes part in an event. Every update mixes in a message from the node's partner. Over a long stream this works like the repeated neighbor-averaging that causes over-smoothing in deep static GNNs: node memories drift toward one another and come to occupy a narrow, low-dimensional subspace. We propose to measure this slow, time-indexed collapse directly. We then test whether it explains a known embarrassment for the field: the Temporal Graph Benchmark reports that a non-learning Moving Average reaches 0.559 NDCG@10 on tgbn-reddit, while TGN, a learned memory-based model, reaches only 0.315. Finally, we test whether a cheap streaming correction that restores the spread of the memories can close that gap when only a small fraction of node labels is available.
The correction uses no data augmentation, so it does not edit the graph. It also does not push connected nodes apart. It only penalizes the memory matrix for concentrating its variance in a few directions. In two sentences: deep temporal graph models may lose to simple averages because their node memories quietly collapse as the stream grows, and this collapse matters most when labels are scarce. We will diagnose that collapse with an effective-rank measurement over stream time and repair it with a spectral regularizer that keeps the neighbor structure scarce labels depend on.
Core Claim
We claim three things.
- Diagnosis. Memory-based temporal GNNs show a measurable decline in the effective rank of their node-memory matrix as stream time grows.
- Mechanism. The size of that decline predicts how far the model falls behind the Moving Average heuristic, and the gap widens as the label budget shrinks.
- Remedy. A covariance-level regularizer applied to the event batch restores rank and recovers most of the lost accuracy. It does this better than two alternatives:
- a pairwise repulsion force of the kind used by ContraNorm;
- the contrastive views used in temporal self-supervision, whether built by editing the graph or by perturbing model weights.
Claim 1 is falsifiable on its own. If memories do not lose rank, the paper becomes a negative result that rules out over-smoothing as the explanation for the heuristic gap. That outcome would still be useful.
Where This Sits in Prior Work
Work that supplies the vocabulary. Two papers separate complete collapse (all representations shrink to one point) from dimensional collapse (representations span only a thin cone) and argue that effective rank is the right measurement:
- ContraNorm derives a normalization layer from one gradient step on a uniformity loss. On Cora it keeps a 32-layer GCN at about 46% accuracy, against about 19% for the vanilla GCN.
- Are we measuring oversmoothing in graph neural networks correctly? makes the same case for rank-based measurement.
Both treat depth as the variable that drives collapse. We treat stream length as that variable, and nobody has measured it there. The file lists static-to-dynamic transfer of anti-smoothing methods as an open problem. It records no work testing ContraNorm, Deeper-GXX or A-DGN on temporal streams. Deeper-GXX pulls 1-hop neighbors together and pushes non-neighbors apart. A-DGN keeps information stable across depth with anti-symmetric weight matrices.
Work that constrains the design. Two results limit what the remedy can do:
- The literature already notes a tension. Repulsion forces that undo over-smoothing work against the neighbor smoothing that lets a few labels spread to unlabeled nodes, which is the mechanism behind FeatProp-style propagation. This rules out a pairwise uniformity loss as the default when labels are scarce, and it is why we target the spectrum of the memory matrix instead.
- Mind the Label Shift of Augmentation-based Graph OOD Generalization shows that editing the graph structure can silently change a sample's true class. Together with Trivedi et al., who find that much of graph contrastive learning's apparent gain comes from the message-passing backbone, this argues against making edge-dropping augmentation the source of self-supervision.
The closest temporal work. TGAC adds contrastive learning to a TGN-style encoder. It builds the two views by pruning edges with hand-set centrality and timestamp thresholds. It does not study collapse or scarce labels. TADGNN unrolls discrete snapshots into one time-augmented graph and uses deep GCNII-style residual layers to avoid over-smoothing. It is fully supervised and works only on snapshots. SimGRACE avoids augmentation by contrasting an encoder with a weight-perturbed copy, and does well with 1% labels on static graphs.
Our work differs from all three in the same way. Their contrastive or residual machinery is a design choice motivated by intuition. We identify a specific failure, memory rank collapse, measure it, and test interventions against that measurement. Augmentation-based and weight-perturbation contrastive learning become competing remedies to evaluate, not assumed ingredients.
Research Program
Stage 1: Diagnosis
We instrument TGN-style memory models and TGAT-style attention models on the TGB node-affinity datasets tgbn-reddit, tgbn-trade and tgbn-genre. At regular points in stream time we record the effective rank of the matrix of active node memories. Write $M_t \in \mathbb{R}^{n_t \times d}$ for the memories of the $n_t$ nodes seen up to time $t$, with memory dimension $d$, and let $\sigma_1,\dots,\sigma_d$ be its singular values. The effective rank is
$$\mathrm{erank}(M_t) = \exp\Big(-\sum_{i=1}^{d} p_i \log p_i\Big), \qquad p_i = \frac{\sigma_i}{\sum_j \sigma_j},$$
following the definition used by ContraNorm. It equals $d$ when variance is spread evenly across all directions and approaches 1 under full collapse.
We will also record two things:
- how quickly the representations of nodes in different label groups converge toward each other, measured by the ratio of within-class to between-class distance;
- a version of the measurement that controls for degree. The file notes that over-smoothed embeddings converge toward an equilibrium set by node degree, so we compute erank separately within degree strata to rule out a pure degree artifact.
The diagnostic prediction is that erank decreases monotonically over stream time. It should decrease faster for nodes with many events, and faster when more temporal message-passing layers are stacked.
Stage 2: Remedy
The intervention is a regularizer on each event batch. Let $B$ be the memories updated in the current batch, combined with a small reservoir sample of memories that were not updated. Let $\hat C_B$ be their covariance after normalizing it to unit trace. We add
$$\mathcal{R}(B) = \Big\| \hat C_B - \tfrac{1}{d} I \Big\|_F^2$$
to the training loss. Here $I$ is the $d \times d$ identity and the norm is the Frobenius norm.
This penalty is minimized when variance is spread across all directions. It says nothing about whether two particular connected nodes are close, which is the property that separates it from ContraNorm's pairwise repulsion. It costs $O(|B| d^2)$ per batch, with no pass over the full graph and no bi-level optimization, so it fits the streaming setting and the inference-latency concern TGB raises.
Self-supervision on the unlabeled stream
The unlabeled part of the stream supplies self-supervision through future-interaction prediction, which needs no augmentation. On top of that we test, as separate arms:
- TGAC-style augmented views;
- SimGRACE-style weight-perturbed views.
This tests a direct question: once collapse is controlled, does any form of contrastive view add value? Trivedi et al.'s finding predicts the answer may be no.
Label scarcity
TGB's node-affinity labels are relatively dense. We subsample the labeled nodes at each label timestamp to 1%, 5%, 20% and 100%, using fixed seeds, and rerun every method at every budget. Our prediction is specific: the benefit of rank repair grows as the label budget shrinks. With few labels, the classifier's gradients are too weak to keep the memory directions apart on their own.
Snapshot setting
To check that the phenomenon is not specific to memory modules, we repeat the diagnosis on TADGNN-style time-augmented snapshot graphs on WIKI, increasing the depth of the unrolled graph.
Baselines
Moving Average (naive reference point). This is the strongest naive reference. It predicts a node's future affinity as the average of its recent label vectors and has no learned parameters. It is the strongest competitor on this question because the TGB paper reports it beating TGN on three of four node-affinity datasets, with 0.559 against 0.315 NDCG@10 on tgbn-reddit (Temporal Graph Benchmark). We run it with the same evaluation splits and the same label subsampling. It can only average the labels it is shown, so at low budgets it averages fewer observations. The proposal succeeds only if the regularized model beats Moving Average at the 1% and 5% budgets on at least two of the three datasets. Narrowing the gap is not enough.
Strongest learned baseline: TGN. This is TGN as configured in TGB. The file reports no node-affinity numbers for TGAT, GraphMixer or NAT. NAT's 0.749 MRR on tgbl-wiki is a link-prediction figure and does not transfer to this task. For tgbn-trade and tgbn-genre the file gives no exact numbers for any method: no reported result found on Lacuna for these datasets. We will therefore rerun TGN ourselves on every dataset and budget, using the same tuning budget as our method. That budget is a fixed number of hyperparameter trials, selected on validation NDCG only.
Strongest augmentation-based competitor: TGAC. This is TGAC with its published pruning thresholds plus the same tuning budget. Its reported link-prediction AUC of 98.85 on Wikipedia shows the encoder is strong, but the file reports no node-classification figure for it: no reported result found on Lacuna for TGAC on TGB node affinity.
Snapshot baseline: TADGNN. On WIKI snapshots the reference is TADGNN's reported 69.2% Macro-AUC, against 54.3% for DySAT (TADGNN). That figure was obtained with full labels, so we reproduce it before subsampling.
Ablations isolating the key ingredient. The first ablation swaps the covariance penalty for ContraNorm's pairwise uniformity step at matched strength. If the regularizer only helps because it spreads representations, the two should tie. Our claim predicts the pairwise version does worse at low budgets, because it separates neighbors. Further ablations remove the regularizer from the label-free stream periods only, and replace it with simple normalization of the memory vectors.
Why not just…?
Why not just use Moving Average and stop? This is a real threat on node-affinity tasks. If Moving Average still wins at every label budget, the honest conclusion is that learned memory adds nothing there, and we will report it. The case for learning rests on two points. First, scarce labels starve an averaging method in a way they may not starve a model that learns from unlabeled events. Second, on unseen nodes the heuristic has no history to average. We will separately score test nodes that have little or no label history.
Why not just reset, decay or layer-normalize the memories? Periodic resets and decay limit the drift but also discard history. Normalizing each memory vector fixes its length but not its direction, so vectors can still cluster in a narrow cone. This is exactly the dimensional collapse ContraNorm distinguishes from complete collapse. Neither fix is ruled out by evidence in the file, so both are run as baselines with tuned decay rates. If either matches the spectral regularizer on erank and accuracy, the simpler fix is the contribution and we will say so.
Why not just apply SimGRACE to TGN? This is the obvious move at this intersection, and the file records no one doing it. But SimGRACE's weight perturbation creates contrastive pressure without targeting rank. It is also sensitive to the perturbation scale. We include it as an arm and measure its effect on erank. If it restores rank as well as the covariance penalty does, the mechanism claim still holds but the remedy is redundant.
Why not just use fewer temporal layers? Shallow models limit over-smoothing across depth. But memory collapse accumulates across events, not layers, so the diagnosis predicts erank decline even in one-layer models. Measuring erank in a one-layer TGN directly tests this.
Decisive Checks
The study rests on three checks.
- Correlation. Across datasets, budgets and checkpoints, the decline in erank should predict the NDCG@10 gap between TGN and Moving Average. If it does not, the mechanism claim fails regardless of what the remedy does.
- Intervention. The covariance regularizer should raise erank and reduce the gap, with a larger effect at 1% labels than at 100%.
- Contrast with repulsion. Pairwise repulsion should restore erank comparably but reduce accuracy at low budgets. We will also measure how far apart connected same-label nodes end up under each method.
We report means over five seeds with standard deviations. Per-batch overhead is measured against TGN's inference latency, since TGB flags speed as a reason heuristics are preferred.
References
- Temporal Graph Benchmark for Machine Learning on Temporal Graphs
- ContraNorm: A Contrastive Learning Perspective on Oversmoothing and Beyond
- Are we measuring oversmoothing in graph neural networks correctly?
- Tackling Oversmoothing of GNNs with Contrastive Learning
- Anti-Symmetric DGN: a stable architecture for Deep Graph Networks
- Active Learning for Graph Neural Networks via Node Feature Propagation.
- Mind the Label Shift of Augmentation-based Graph OOD Generalization
- Augmentations in Graph Contrastive Learning: Current Methodological Flaws & Towards Better Practices
- Temporal Graph Representation Learning with Adaptive Augmentation Contrastive
- Dynamic Graph Node Classification via Time Augmentation
- SimGRACE: A Simple Framework for Graph Contrastive Learning without Data Augmentation