Technical Summary: Never Skip a Batch: Dense Learning of Temporal GNNs via Adaptive Pseudo-Supervision

1. Problem Statement

Temporal Graph Networks (TGNs) are state-of-the-art models for dynamic graph tasks, yet their training efficiency is severely hampered by supervision sparsity in real-world datasets. In many applied problems (e.g., recommendation, fraud detection), labeled interactions constitute less than 2% of total events. Consequently, standard TGN implementations process batches in two distinct modes:

1. Supervised Batches: Full training steps involving gradient updates and memory updates.
2. Unsupervised Batches: Only memory and neighbor sampler updates occur; no gradient-based training is performed because ground-truth labels are absent.

This "skip-a-batch" behavior creates a significant bottleneck. The model skips parameter updates for the vast majority of data, leading to high-variance gradient updates when labels are finally available and slow wall-clock convergence. The paper posits that node preferences evolve slowly over time, suggesting that historical supervision signals can be leveraged to generate informative pseudo-targets for these otherwise idle batches.

2. Methodology: Moving-Averaged Labels (MAL)

The authors propose Moving-Averaged Labels (MAL), a pseudo-labeling scheme that generates soft targets for unsupervised batches based on historical supervision signals. This approach is orthogonal to the underlying model architecture (e.g., TGNv2, DyRep) and introduces no additional learnable parameters.

Core Mechanism

For a node $v$ in a batch $B_t$ lacking ground-truth labels, MAL constructs a pseudo-target $\tilde{y}^{(v)}_t$ using past observed targets. The pseudo-target is defined as:
$$\tilde{y}^{(v)}_t = \bar{y}^{(v)}_t + \gamma \cdot \epsilon$$
Where:

• $\bar{y}^{(v)}_t$ is an aggregate of historical targets.
• $\epsilon$ is zero-mean noise sampled from a uniform distribution, normalized to ensure $\tilde{y}^{(v)}_t$ remains a valid probability distribution (sums to 1).
• $\gamma$ is a noise scaling factor acting as a regularizer.

Aggregation Strategies

The paper evaluates three strategies for computing the historical aggregate $\bar{y}^{(v)}_t$:

1. Persistent Forecast (PF): Reuses the most recently observed label for the node.
2. Moving Average (MA): Incrementally updates the pseudo-label using a window size $w$. When a new target $y^{(v)}_t$ arrives, the aggregate is updated as:
   $$\bar{y}^{(v)}_t = \frac{w-1}{w}\bar{y}^{(v)}_{t-1} + \frac{1}{w}y^{(v)}_t$$
3. Historical Average (HA): Aggregates all past targets with equal weight (theoretical baseline).

Training Pipeline

The method modifies the standard TGN training loop. When a batch arrives without ground-truth labels, the model computes the pseudo-targets $\tilde{y}$ using the chosen aggregation strategy. The model then performs a full forward pass, computes the cross-entropy loss against these pseudo-labels, and backpropagates to update both the GNN parameters and the memory modules. This transforms "idle" computation into productive training steps.

3. Theoretical Analysis

The paper provides a theoretical justification for why MAL improves convergence speed by reducing the variance of stochastic gradients.

• Variance Reduction: Under the assumption of constant (or slowly drifting) user preferences, the authors model label generation as a process where true labels are one-hot vectors. They prove that aggregating $h$ historical labels (History Average) reduces the variance of the label estimator compared to a single observation.
• Convergence Bound: For Stochastic Gradient Descent (SGD) with a $\mu$-strongly convex loss, the regret bound $R_T$ is proportional to the gradient variance $\sigma^2$. The authors derive that for History Average Labels (HA), the variance scales with $\frac{1}{\min(h, k)}$, where $h$ is the history length and $k$ is the number of possible interaction classes.
• Result: This implies a theoretical speedup in convergence of a factor of $\min(h, k)$ compared to vanilla training, provided the assumption of temporal consistency holds.

4. Experimental Results

The authors evaluated MAL on the Temporal Graph Benchmark (TGB) using four large-scale datasets: tgbn-trade, tgbn-genre, tgbn-reddit, and tgbn-token. They implemented MAL on TGNv2 and a modified DyRepv2 (incorporating TGNv2's source-target identification).

Key Findings

• Predictive Performance: MAL consistently outperformed vanilla training and alternative baselines. On the TGNv2 model, Moving Average (MA) achieved NDCG@10 improvements ranging from 3% to 17% across datasets compared to vanilla training.
• Convergence Speed: The most significant gain was in training efficiency. MAL reduced the time-to-accuracy (time to reach the top score) by an average of 6× across all datasets. In some cases (e.g., tgbn-token), the method achieved the performance of a fully converged vanilla model in a fraction of the time.
• Comparison with Baselines:
  • Vanilla Models: Many existing architectures (JODIE, TGAT, CAW-N, etc.) collapsed to trivial solutions (performing similarly to a mean-target baseline) on TGB datasets without the specific architectural improvements of TGNv2.
  • Alternative Pseudo-Labeling: MAL outperformed Persistent Forecast (PF), Label Smoothing, and Self-Supervised (SSL) next-edge prediction strategies.
  • Window Size: An ablation study showed that optimal window sizes vary by dataset (e.g., $w=3$ for trade, $w=9$ for Reddit), but a default of $w=7$ generally provided robust performance.
• Robustness:
  • Noise: The method remained stable across varying noise factors ($\gamma$).
  • Temporal Shuffling: When training labels were shuffled (destroying temporal consistency), performance dropped significantly for all methods, confirming that the gains stem from temporal consistency rather than mere regularization.
  • Sparsity: Under controlled label removal, MAL's relative advantage over vanilla training increased as supervision became scarcer.

5. Significance and Claims

The paper claims to address a fundamental inefficiency in dynamic graph learning: the waste of computational resources on unsupervised batches.

• Paradigm Shift: The work shifts the paradigm from "train only when supervised" to "always train, intelligently extrapolate."
• Efficiency without Complexity: The method achieves state-of-the-art (SOTA) results and significant speedups without modifying the model architecture, adding learnable parameters, or requiring a separate pre-training stage.
• Theoretical Grounding: It provides a theoretical proof that aggregating historical supervision reduces gradient variance, leading to faster convergence under mild assumptions of temporal stability.
• Practical Impact: By enabling dense learning on sparse data, MAL makes training large-scale temporal graph models significantly faster and more effective, particularly in domains where labeled events are rare.

The authors conclude that temporal consistency is an untapped supervisory signal that, when leveraged via simple moving averages, offers a principled and lightweight solution to gradient sparsity in temporal graph learning.