Many temporal graph models keep a memory vector for each node. Examples are transaction networks, Reddit posting logs, and Wikipedia edit streams. Every time an edge event arrives, the model blends the memories of the two endpoints. That blending is a form of neighbour averaging. In static graphs, repeated averaging is known to drive all node representations toward the same vector, a failure called over-smoothing. This note proposes that the same failure happens along the time axis of an event stream, which we call temporal rank collapse. Temporal rank collapse would help explain an awkward fact: on dynamic node-affinity tasks, a moving-average heuristic beats a learned memory model by a wide margin. On tgbn-reddit the reported scores are 0.559 versus TGN's 0.315 in normalized discounted cumulative gain at 10 (NDCG@10), according to the Temporal Graph Benchmark.
The proposed remedy comes from the graph-transformer literature on missing structural bias. Graph transformers attend over all node pairs and cannot see the graph's shape unless it is injected through structural encodings, which are extra per-node features describing position in the graph. Our version is a structural encoding that stays cheap to maintain on a stream. Each node draws a random vector when it first appears. A short trajectory of time-decayed propagations of these vectors is then updated in constant time per event. This gives every node a fixed, never-averaged identity component plus walk-count features that describe its evolving neighbourhood. It needs no eigendecomposition and no warm-up history. The claim is two-sided. First, temporal rank collapse is real and predicts accuracy loss on streams. Second, a streaming encoding that cannot collapse fixes it more cheaply and more inductively than the obvious alternatives.
Core Claim
Consider memory-based temporal graph networks. Their memory update has the form $h_u \leftarrow (1-z)\,h_u + z\,\tilde h_u(h_v)$: a gated convex combination of the node's old memory $h_u$ and a candidate $\tilde h_u$ computed from the partner node's memory $h_v$, with gate value $z \in (0,1)$. Such models behave like a product of time-varying, row-stochastic-like averaging matrices.
Demystifying Oversmoothing in Attention-Based Graph Neural Networks analyses exactly this kind of product of time-varying matrices for static-graph attention. It proves that strictly positive weights cannot cut information paths, and that the product collapses to rank one at an exponential rate. That paper assumes fixed connectivity. We conjecture, and will try to prove under a joint-connectivity condition, that the same collapse holds when connectivity changes event by event. The condition is that the union of edges over every window of length $T$ is connected. Under it, memory rank should decay exponentially in the number of such windows, not in the number of layers.
The practical consequence is testable. Long-lived, heavily active nodes should have the most homogenized memories. Effective rank of the memory matrix should track accuracy on streams. On static graphs, Are we measuring oversmoothing in graph neural networks correctly? reports this correlation at a Pearson coefficient of 0.91 for effective rank. That same paper shows Dirichlet energy, the common smoothness measure, to be misleading, which is why we measure rank instead.
The remedy reuses the method of Graph Positional Encoding via Random Feature Propagation, which propagates random node vectors and keeps the whole trajectory. That paper shows early steps act as randomized counters of triangles and cycles and late steps approach dominant eigenvectors. It computes the trajectory on a static graph, and we make it incremental. Each node $u$ holds a random vector $r_u \in \{\pm 1\}^k$, drawn once on arrival, and trajectory vectors $p_u^{(1)},\dots,p_u^{(S)}$, where $k$ is the random dimension and $S$ is a small number of steps. On an event $(u,v,t)$ we update
$$p_u^{(s)} \leftarrow e^{-\Delta t_u/\tau}\,p_u^{(s)} + p_v^{(s-1)}, \qquad p_v^{(s)} \leftarrow e^{-\Delta t_v/\tau}\,p_v^{(s)} + p_u^{(s-1)},$$
Here $p^{(0)}=r$, $\Delta t_u$ is the time since $u$'s last event, $\tau$ is a decay constant, and per-step normalization is applied as in the original method. The cost is $O(Sk)$ per event.
Two properties matter. First, $r_u$ is never averaged, so the encoding contains a full-rank component by construction. Second, inner products such as $\langle p_u^{(a)}, p_v^{(b)} \rangle$ are unbiased estimates of time-decayed counts of walks of length $a+b$ between $u$ and $v$. That is pairwise structure of the kind CorDGT builds from snapshot shortest-path distances, obtained here without any path computation.
Research Program
The work has three parts, and each can succeed or fail independently.
The first part is diagnostic. We instrument TGN-style memory, CTAN's anti-symmetric continuous-time propagation, and Todyformer's alternating local–global blocks. For each, we log numerical rank and effective rank of the memory matrix as the stream advances, broken down by node age and activity. We then correlate these with per-window accuracy. The question is whether temporal rank collapse exists, and whether it explains where learned models lose to the moving-average heuristic.
The second part is theory. We try to extend the joint-spectral-radius and ergodicity argument of the attention over-smoothing paper to event-driven gated updates, and to state the joint-connectivity condition explicitly. Backward Oversmoothing shows that collapsed forward features also flatten gradients and trap training. That result motivates checking whether truncated backpropagation through time on streams shows the same trap.
The third part is method. We build the streaming encoding above and attach it to TGN-style memory, to CTAN, and to a Todyformer-style transformer. In the transformer, the encoding also supplies the cross-node structural bias that Todyformer's within-timeline positional encodings lack.
Baselines
The naive reference points are the non-learning heuristics from the Temporal Graph Benchmark: moving average and persistence forecasts. They are run with the benchmark's own protocol and negative sampling. On tgbn-reddit the moving average reaches 0.559 NDCG@10 against TGN's 0.315, and beating 0.559 there is the clearest single success criterion. On tgbl-wiki the strongest reported number in the file is NAT at 0.749 Mean Reciprocal Rank (MRR), from the same benchmark paper. For tgbl-comment, Todyformer reports beating the next best model by 39% MRR, but no absolute value was found on Lacuna. For tgbl-review and tgbl-coin, L-STEP reports only placements, not values: L-STEP placed second and third respectively.
The strongest learned competitors are three. CTAN is strongest on long-range propagation; it reports near-perfect accuracy on T-PathGraph out to path length 20 while TGN collapses. Todyformer is strongest on large-scale link prediction. CorDGT is the closest structural-encoding competitor. All are rerun in our harness with identical splits, identical memory and embedding dimensions, and an equal hyperparameter search budget in GPU-hours. Our encoding adds parameters only through its input projection, so we also give each baseline a matched-width input layer.
Three ablations isolate the key ingredient. The first keeps only $r_u$ with no trajectory: does a fixed random identity alone fix collapse? The second keeps the trajectory but re-draws $r_u$ every window, which tests whether a persistent anchor matters. The third replaces the encoding with periodically recomputed Laplacian eigenvectors on snapshots, at matched wall-clock cost. Beating a baseline means a gain larger than the seed-to-seed standard deviation over five seeds, on at least three of the four node-affinity datasets.
Why not just…?
Why not just use CTAN, whose anti-symmetric dynamics already conserve energy? This is the most serious threat. Non-dissipative dynamics preserve feature norm and gradient norm. Whether they preserve rank in the presence of nonlinearities and gating is unmeasured; CTAN reports no rank analysis. In addition, uAGNN shows strict non-dissipation hurts on homophilic graphs, where some smoothing is useful. If CTAN's memory rank stays flat and adding our encoding to CTAN brings no gain, we will report that collapse is solved by non-dissipation. The surviving contribution would then be the structural walk-count features, which we would test separately on link prediction.
Why not just give every node a learnable ID embedding? Learnable IDs are full rank, but they cannot represent nodes unseen during training. The Temporal Graph Benchmark stresses that its datasets have a high "surprise index", meaning many test edges are new. Our random anchors are drawn at arrival and need no training. The inductive split of each benchmark tests this directly.
Why not just add normalization or residual connections to the memory? Rescaling cannot restore lost directions. The measurement paper shows collapse is a rank phenomenon that scale-invariant metrics capture, so a normalization layer should leave effective rank unchanged. We will include a PairNorm-style memory normalization baseline to confirm this empirically rather than assume it.
Why not just ensemble the model with the moving average? This may well win on node affinity, and we will report the ensemble. It does not explain the failure, and it adds no structural information for link prediction. The diagnostic in the first part of the program says whether the gap is caused by collapse at all.
Proposed Experiments
The benchmarks are the node-affinity tasks tgbn-reddit, tgbn-trade, tgbn-genre and tgbn-token, the link tasks tgbl-wiki, tgbl-review and tgbl-comment, and the synthetic T-PathGraph task. On T-PathGraph we additionally vary path length and the event density inside each joint-connectivity window, so that we can check the predicted exponential decay rate.
We plan three decisive checks. First, if memory effective rank does not decline over the stream in TGN, or does not correlate with per-window accuracy, the core claim is wrong. We would then stop treating the work as an over-smoothing paper and retain it only as an encoding paper. Second, raising rank is trivially easy with random features, and the measurement paper warns that high rank does not imply accuracy. We therefore report rank of the learned memory component separately from the injected encoding, and judge success only by task metrics. Third, the full trajectory must beat the anchor-only ablation on link prediction. If it does not, the walk-count structure contributes nothing beyond identity, and the encoding reduces to random node features.
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?
- Graph Positional Encoding via Random Feature Propagation
- Dynamic Graph Transformer with Correlated Spatial-Temporal Positional Encoding
- Long Range Propagation on Continuous-Time Dynamic Graphs
- Todyformer: Towards Holistic Dynamic Graph Transformers with Structure-Aware Tokenization
- Backward Oversmoothing: why is it hard to train deep Graph Neural Networks?
- Learnable Spatial-Temporal Positional Encoding for Link Prediction
- Non-Dissipative Graph Propagation for Non-Local Community Detection