Graph neural networks break down as they get deeper because every layer averages each node's features with its neighbors'. After many rounds of averaging, all nodes look alike. This is called over-smoothing, and it has been studied almost entirely as a function of depth on a fixed graph. We argue that the same failure appears in a place nobody measures: the memory of temporal graph networks. These models keep a state vector per node and update it at every interaction event, and each update mixes the states of the two endpoints. A stream of millions of events is therefore a very long product of averaging steps, even when the model has only one layer. Our claim is that node memories in these models lose dimensionality over the course of a stream in the same way deep static GNN features do. If that is true, it offers a concrete, testable account of why memory-based temporal models sometimes lose to trivial heuristics.
The opportunity matters because the Temporal Graph Benchmark showed that a moving-average heuristic reaches an NDCG@10 of 0.559 on tgbn-reddit while the memory model TGN reaches 0.315. That benchmark also found that memory models degrade on high-surprise intervals, where test edges were never seen in training. The field has no mechanistic explanation for these failures. We propose one, a way to measure it, and a minimal fix. We also say in advance what result would show the fix is unnecessary.
Core Claim
In a memory-based temporal GNN, over-smoothing accumulates over stream time rather than over layer depth. The linearized memory dynamics are a product of time-varying mixing matrices, one per event batch. The ergodicity argument that Demystifying Oversmoothing in Attention-Based Graph Neural Networks used for attention across layers therefore applies across events. Write $S_t \in \mathbb{R}^{n \times d}$ for the matrix of $n$ node memories of width $d$ after event batch $t$. Let $P_t$ be the row-stochastic matrix that mixes each interacting node's memory with its counterpart's, with the identity on nodes that did not interact. Let $W_t$ be the learned recurrent map. In the linearized picture,
$$S_T \approx P_T \cdots P_2 P_1 \, S_0 \, W_1 \cdots W_T .$$
That paper's result is that products of such matrices converge exponentially to rank one when the union of graphs over sliding windows stays connected. Here that condition becomes "the interaction stream keeps connecting the node population." This yields three predictions. First, the effective rank of memory decays with stream length. Second, the decay is faster on dense, well-mixed streams. Third, it stalls at roughly the number of jointly connected components when the stream has persistent communities.
Following Are we measuring oversmoothing in graph neural networks correctly?, we measure collapse with effective rank rather than Dirichlet energy. That paper showed Dirichlet energy misses collapse at practical depths, while effective rank tracks accuracy with an average Pearson correlation of 0.91. The effective rank is
$$\mathrm{Erank}(S) = \exp\Big(-\textstyle\sum_i p_i \log p_i\Big), \quad p_i = \sigma_i / \textstyle\sum_j \sigma_j ,$$
where $\sigma_i$ are the singular values of the centered memory matrix. The GRU gates in real models are nonlinear and can partly counteract mixing, so the linear argument is a hypothesis, not a proof. The first job of the project is to find out whether the collapse is real.
Relation to Prior Work
Three papers motivate the question. Demystifying Oversmoothing in Attention-Based Graph Neural Networks proves rank-one collapse for inhomogeneous products across layers of a static graph. We reuse its analysis but index the product by physical time over an evolving edge set, a setting it explicitly leaves aside. Are we measuring oversmoothing in graph neural networks correctly? supplies our measurement. It warns that high rank is necessary but not sufficient for accuracy, so we always pair rank with a linear probe. The Temporal Graph Benchmark supplies the failure we want to explain.
Two dynamic-graph papers come closest and constrain what counts as new. Todyformer splits the stream into temporal patches and claims that its global Transformer "refreshes" node representations and prevents uniformity. It never measures representation rank over time, and it removes recurrent memory rather than diagnosing it. SPEDGNN keeps embedding singular spectra well-conditioned by replacing attention with a power-method SVD. That is the closest mechanism to ours, but it conditions a per-step transform. It does not analyze the event-by-event recursion that we claim causes the collapse, and it does not track spectra across stream length.
TRicci removes up to 80% of temporal edges using a curvature score. Removing edges reduces mixing, so under our account it may partly succeed by slowing memory collapse, a possibility it never tests. Two static-graph papers point toward the fix. Anti-Symmetric DGN shows that anti-symmetric updates preserve feature energy over 30 or more layers, and its authors name dynamic graphs as the open extension. Complete the Missing Half keeps a high-pass channel that encodes differences between a node and its neighbors.
Research Program
The first part is diagnostic. We instrument TGN-style memory models and record memory effective rank, numerical rank, and a linear-probe accuracy for node attributes or future activity at regular points along the stream. We then relate these to per-window MRR on the TGB link-prediction datasets and to per-window surprise index.
A controlled synthetic study tests the theory directly. We generate streams with fixed latent node classes and vary three things independently: interaction density, cross-class mixing rate, and community persistence. The theory predicts that rank decays faster with more cross-class mixing and plateaus near the number of persistent communities.
We also measure gradient norms into early memory updates, to see whether the backward form of over-smoothing identified in Backward Oversmoothing appears through time. This is a secondary check, not a main claim.
The second part is a minimal intervention, called rank-preserving memory. It makes two changes to the memory update. First, the counterpart's memory enters the update only as its deviation from a running population mean. This is a temporal high-pass channel in the spirit of filterbank GNNs, and it removes the shared component that ergodic mixing concentrates on. Second, the recurrent state transition uses an anti-symmetric matrix, borrowed from A-DGN, so the update does not dissipate memory energy. Both changes are drop-in replacements for the memory update in existing temporal graph models and add negligible compute.
Baselines
The "do nothing" reference is unmodified TGN with its standard memory and training recipe, run through the official TGB loaders and evaluation. Any gain we report must come from changing the memory update alone. The non-learning heuristics EdgeBank and Moving Average are a second naive reference that a learned model must justify itself against. On tgbn-reddit the file reports Moving Average at 0.559 NDCG@10 against TGN at 0.315 (Temporal Graph Benchmark). Closing a meaningful part of that gap would itself be a result.
The strongest existing methods differ by dataset. On tgbl-wiki, NAT has the best reported MRR of 0.749 (Temporal Graph Benchmark). On tgbl-review, GraphMixer and TGAT lead, but no reported number was found on Lacuna for them. On tgbl-comment, Todyformer is reported 39% above the next-best model in MRR (Todyformer), but no absolute value was found on Lacuna, so we will rerun it. SPEDGNN is included because it is the closest spectral-conditioning competitor. TRicci-sparsified TGN is included because it is the obvious "reduce mixing by pruning" competitor.
All methods get the same memory width, the same hyperparameter search budget over learning rate and memory decay, and five seeds. They are tuned on the TGB validation split only. We count the proposal as beating a baseline only if two conditions hold. Its MRR or NDCG@10 must exceed the baseline beyond seed variance on at least the high-mixing datasets. And its gain must be concentrated in the windows where the baseline's memory rank is lowest.
Ablations isolate the key ingredient. We test the centered message alone, the anti-symmetric transition alone, and both together. We also include a random-rank control that injects noise to raise effective rank without adding information. That control guards against the "rank is not sufficient" caveat: if noise helps as much, the mechanism is wrong.
Why not just…?
Why not just decay or periodically reset node memories? This is the real threat. Pulling memory back toward a fixed point limits how many mixing steps accumulate, which breaks the product's convergence. Our worry is that the default fixed point, zero or a shared initial state, is itself identical across nodes, so decay may trade collapse for forgetting. Residual anchoring on static graphs shows this kind of trade-off: models tethered to local features fail on long-range tasks, as the Star dataset result of roughly 65% chance accuracy in Analyzing the effect of residual connections to oversmoothing illustrates. We include tuned exponential decay and fixed-interval reset as baselines. If they match rank-preserving memory on both rank and MRR, we will report the diagnostic and theory as the contribution and recommend decay as the fix.
Why not just use memory-less models like GraphMixer or EdgeBank? If memory collapse is the problem, dropping memory is a legitimate answer, and TGB shows memory-less models win on high-surprise data. But memory-less models cannot carry long-horizon node history. Our prediction is specific: memory models should lose exactly where memory rank has collapsed, and should win elsewhere once rank is preserved. The per-window analysis settles this. If memory-less models win uniformly, even where memory rank is high, our account of the failure is wrong.
Why not just sparsify the stream with TRicci? Pruning reduces mixing and could slow collapse as a side effect. It is also tuned for retention of ROC-AUC, reported at 97.7% of full-graph performance under 80% removal (TRicci), not for preventing smoothing. It also risks the long-range sensitivity loss that DropSens documents for degree-blind edge dropping. We measure memory rank under TRicci. If pruning alone restores rank and accuracy, that supports our mechanism and weakens the case for a new update rule, and we will say so.
Why not just add LayerNorm to memory? Per-node normalization fixes scale but not direction. Rank-one collapse means all memories point the same way, which normalization preserves. We include LayerNorm memory as a baseline to confirm this empirically.
Proposed Experiments and Decisive Checks
We run on tgbl-wiki, tgbl-review, tgbl-coin, and tgbl-comment (MRR with historical negatives), on tgbn-reddit (NDCG@10), and on the Wikipedia, Reddit, and MOOC streams used by SPEDGNN. All runs use the official TGB suite.
The first decisive check is existence. On the synthetic streams, memory effective rank in unmodified TGN must fall with stream length and cross-class mixing, and plateau near the number of persistent communities. On at least two real datasets, per-window effective rank must correlate with per-window MRR. If memory rank stays flat on real streams, the central claim fails and the project stops at a negative result, which is still worth publishing given the surprise-index puzzle.
The second check is attribution. Rank-preserving memory must raise both effective rank and linear-probe accuracy, and the noise control must not.
The third check is practical. The accuracy gain must hold against tuned decay and TRicci, and must appear in the collapsed windows specifically.
A final analysis relates per-window surprise index to memory rank, to test whether the TGB failure on high-surprise data is, at least in part, a collapse of node memory.
References
- Temporal Graph Benchmark for Machine Learning on Temporal Graphs
- Demystifying Oversmoothing in Attention-Based Graph Neural Networks
- Are we measuring oversmoothing in graph neural networks correctly?
- Todyformer: Towards Holistic Dynamic Graph Transformers with Structure-Aware Tokenization
- Well-Conditioned Spectral Transforms for Dynamic Graph Representation
- Edge Sparsification via Temporal Forman-Ricci Curvature for Dynamic Graph Learning
- Anti-Symmetric DGN: a stable architecture for Deep Graph Networks
- Complete the Missing Half: Augmenting Aggregation Filtering with Diversification for Graph Convolutional Networks
- Backward Oversmoothing: why is it hard to train deep Graph Neural Networks?
- Analyzing the effect of residual connections to oversmoothing in graph neural networks
- Effects of Dropout on Performance in Long-range Graph Learning Tasks