REVIEW 4 major objections 4 minor 40 references
Never Skip a Batch: Dense Learning of Temporal GNNs via Adaptive Pseudo-Supervision
T0 review · 4 major / 4 minor · reviewed 2026-08-15 · deepseek-v4-flash
Pith's one-line read History-averaged pseudo-labels reduce gradient variance in temporal GNN training, cutting time-to-accuracy by up to 15 times on standard benchmarks.
desk verdict A plausible pseudo-labeling trick for temporal GNNs, but the variance proof is flawed and the headline speedups rely on a nonstandard 5% training split. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The central object is the history-averaged pseudo-label $\tilde{y}_t^{(v)}$, an aggregate of all supervision signals observed for node $v$ before time $t$; the abstract calls this Moving-Averaged Labels (MAL), the body calls it History-Averaged Labels (HAL). Three variants are used: Historical Average (plain mean of all past targets), Moving Average (exponentially weighted recent labels), and Persistent Forecast (last observed label). The pseudo-label enters the objective by replacing $y$ in the cross-entropy loss while the model, loss, and architecture stay unchanged. The theoretical load is carried by Lemma 2, which models one component of the pseudo-label as the product of an observation-indicator Bernoulli $\xi$ and a scaled multinomial frequency $\eta_k$, derives the variance $\mathrm{Var}(t_h)=u(k-1)/(k^2 h)+u(1-u)/k^2$, and feeds it into the SGD regret bound of Theorem 1 to produce the $\min(h,k)$ speedup factor.
What would settle it
Train the method on a synthetic temporal graph where each node's true label is redrawn uniformly at random at every timestamp, so historical averages carry no information about the current label; if convergence is still faster than vanilla SGD, the reported speedup is not explained by unbiased variance reduction.
Extended reading notes
Core claim
The paper's discovery, stated in good faith, is that the slow drift of node preferences is itself a usable supervisory signal. When ground-truth targets are missing, replacing them with the node's historical label distribution (computed as a historical average, an exponential moving average, or the last observed value) gives an unbiased estimator of the current target, and the extra averaging shrinks the per-label variance from order $1/k$ to order $1/\min(h,k)$. Substituting this variance estimate into the standard SGD regret bound yields an upper bound on regret that is smaller by the same factor, which the paper reads as a proof that pseudo-labels accelerate convergence. On the TGB suite, TGNv2 with these pseudo-targets reaches its best validation NDCG@10 in fewer steps and less wall-clock time, up to 15 times faster on the harder datasets, with test quality on par with or slightly better than the vanilla model.
Load-bearing premise
The result depends on historical pseudo-labels being an unbiased proxy for a node's current label and on label variance being proportional to gradient variance; if past preferences stop tracking current ones, or if label noise does not translate linearly into gradient noise, the claimed convergence speedup does not follow.
Editorial extensions
If this is right
- On label-sparse temporal graphs, training becomes continuous: batches without ground truth still produce gradient updates instead of being skipped.
- Time-to-accuracy shrinks by up to an order of magnitude on the tested benchmarks, which matters when models must be retrained frequently on streaming data.
- Because the method adds no parameters and changes neither the loss nor the architecture, it can be dropped into any temporal GNN, not just TGNv2.
- The three aggregation variants provide a stability-versus-reactivity dial: persistent forecast suits stable preferences, moving average suits drifting ones, and historical average suits long-run baselines.
- The theoretical factor $\min(h,k)$ predicts diminishing returns from extending history once history length exceeds the number of target categories.
Reading between the lines
- Outside the paper's experiments, the same pseudo-supervision logic could apply to link prediction and temporal knowledge graph completion, where supervision is also sparse and sequential.
- A testable extension is to make the aggregation window adaptive: choose per-node weighting from validation performance, which could handle both stable and volatile users without adding parameters.
- The paper's own target-shuffling ablation points to a boundary: when preferences drift fast, persistent forecast degrades while moving average retains more quality, so a drift-aware mixture of the three variants is a natural next step.
- If the variance argument transfers to other architectures, label-level variance reduction would complement optimizer-level methods such as Adam or variance-reduced SGD, attacking a different component of optimization noise.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper proposes to train temporal graph networks on every batch by using pseudo-labels computed from past observed targets, with three aggregation strategies: Historical Average (HA), Moving Average (MA), and Persistent Forecast (PF). It claims a theoretical result that historical averaging reduces gradient variance and accelerates convergence by a factor of min(h,k), where h is the history length and k the number of classes, and it reports experiments on four Temporal Graph Benchmark datasets showing up to 15x faster training for TGNv2 with competitive accuracy. The method introduces no trainable parameters and is intended to be architecture-agnostic. A notable feature of the experimental protocol is that for three of the four datasets only the last 5% of the chronologically ordered training edges are retained, which the authors justify by saying that on the full training sets models converge within a single epoch.
Significance. If the claims were correct, the paper would offer a simple, zero-parameter, architecture-agnostic technique for mitigating sparse supervision in temporal GNNs, and the ablation studies on edge-order and target-order shuffling are useful. The appendix contains complete proofs of the stated lemmas and theorems, and the method description is mostly clear. However, the theoretical derivation rests on a label model that does not match the implemented averaging process and on an unproved proportionality between label variance and gradient variance; moreover, the headline speedups are measured on a modified benchmark with a nonstandard 5% training split and no comparison to standard TGB results. These issues undermine the central claims of the paper as stated, so the contribution is not established in its current form.
major comments (4)
- [Section 3.2, Lemma 2 (Appendix A, Lemma 4)] The random variable t_h = eta_k * xi, with eta_k independent of xi, does not model the historical average of one-hot labels under missingness. For h independent observations in which a fixed label is observed with probability u/k per observation, the component average is Binomial(h, u/k)/h, whose variance is u(k-u)/(k^2 h) and vanishes as h grows. The paper's formula u(k-1)/(k^2 h) + u(1-u)/k^2 retains an h-independent term u(1-u)/k^2, so the claimed min(h,k) speedup in Theorem 3 follows from a label model that the method does not implement. The theorem therefore does not establish the stated convergence acceleration; the variance-reduction result must be re-derived for the actual averaging process, and with the correct model the speedup factor would be h rather than min(h,k).
- [Section 3.2, paragraph after Lemma 2] The assertion that the gradient variance can be written as \tilde{c} Var(t_h) for a non-stochastic constant \tilde{c} across all layers is not justified. For the last layer, Var(p_i - y_i) is not equal to Var(y_i) in general; it also depends on the variance of the model output p_i through the joint distribution of inputs and labels. For earlier layers, the chain rule introduces products of activations and Jacobians that are random and correlated with the label, so a label-independent constant \tilde{c} is not available without additional assumptions. Since Theorem 3 uses this proportionality to convert the label variance into a gradient-variance bound, the convergence-rate claim is not supported by the provided derivation.
- [Section 5.1, Table 1; Section 5.2, Table 2] The reported speedups for tgbn-genre, tgbn-reddit, and tgbn-token are obtained on a modified protocol that keeps only the last 5% of the chronologically ordered training edges, not on the standard TGB 70/15/15 split. The paper explicitly states that on the full training sets models converge within one epoch, which would obscure the effect of pseudo-labeling. Consequently, the abstract's unqualified claims of up to 15x acceleration and 'new SOTA' are not established for the standard benchmark; the experiments compare methods only in an artificial low-data regime. No results on the full training splits, no comparison with published TGB numbers, and no error bars or multiple-seed statistics are reported, so even within the modified regime the quantitative claims are not verified.
- [Section 4.1, Eqs. (5)-(6); Section 4.2] The manuscript is internally inconsistent about the training target. The supervised-batch description says predictions are compared to ground-truth labels y_t^{(v)}, but Eq. (6) states that the loss replaces y_t^{(v)} with pseudo-labels \tilde{y}_t^{(v)} 'for almost all nodes and batches.' It is therefore unclear whether supervised batches use true labels, pseudo-labels, or a mixture; this determines whether the pseudo-label gradient is unbiased and is essential for reproducing the experiments. The method definition must be clarified before the empirical results can be interpreted.
minor comments (4)
- [Abstract and title] The metadata abstract refers to 'Moving-Averaged Labels (MAL)' and to experiments on TGNv2 and DyRepv2, while the full-text abstract refers to 'History-Averaged Labels (HAL)' and the experiments cover only TGNv2; these inconsistencies should be corrected.
- [Section 4.2] The paper says the method has zero additional parameters, but the noise scale gamma, the noise amplitude alpha, the moving-average window w, and the 5% truncation threshold are tunable hyperparameters; their selection procedure and sensitivity are not reported.
- [Section 5.2] The 'N steps' metric in Table 2 is not defined precisely; it should state whether it counts gradient updates, batches, or forward passes.
- [Figure 3] The logarithmic time axis makes the claimed speedup difficult to read; the figure would benefit from marking the convergence point for each method and from showing the Default curve beyond the early training range.
Circularity Check
No significant circularity; the theoretical result is derived from an explicit label model and the empirical claims are measured against baselines, not fitted.
full rationale
The paper's central theoretical claim is that aggregating historical one-hot labels into a running average reduces stochastic-gradient variance and thus improves the SGD regret bound. The derivation chain is self-contained: Lemma 2 defines a probabilistic label model (t_h = eta_k * xi, with eta_k a scaled Binomial component and xi a Bernoulli missingness indicator), computes its mean and variance in closed form, and Theorem 3 plugs that variance into the standard regret bound from Shamir and Zhang. No step reduces to its own input by construction: the variance reduction is not assumed, but computed; the speedup factor min(h,k) follows from comparing the upper bounds for h=1 and h>1; and the pseudo-label update rules in Section 4 (Historical Average, Moving Average, Persistent Forecast) are defined independently of the convergence claim. The empirical evaluation reports measured NDCG@10 and wall-clock time for HA/MA/PF against a Default baseline; no fitted parameter is renamed as a prediction, and no uniqueness theorem is imported from the authors' prior work. The nonstandard 5% training split is an external-validity concern rather than a circularity, and the mismatch between the Lemma 2 label model and the true historical average is a correctness concern, not a circular reduction. The paper also contains no load-bearing self-citation. Accordingly, no circular step is identified.
Assumptions & free parameters
free parameters (3)
- 5% training truncation =
5% of chronologically ordered edges
- Moving average window w =
Not reported for main results
- Noise scaling gamma =
Not reported
assumptions (4)
- domain assumption SGD regret bound for strongly convex loss applies to TGN training with pseudo-labels
- ad hoc to paper Gradient variance is proportional to label variance: Var(dL/dc_ij) = e_j^2 Var(t_h), and similarly for all layers with a constant c
- ad hoc to paper Historical average label is modeled as product of independent Bernoulli(u) and Binomial(h, 1/k)/h
- domain assumption User preferences are constant or change slowly during the label history
Cite this review
Pith. "Pith review of Never Skip a Batch: Dense Learning of Temporal GNNs via Adaptive Pseudo-Supervision." pith.science (2026). https://pith.science/paper/VKJ2W63R
@misc{pith2026250512526,
author = {Pith},
title = {Pith review of: Never Skip a Batch: Dense Learning of Temporal GNNs via Adaptive Pseudo-Supervision},
year = {2026},
howpublished = {\url{https://pith.science/paper/VKJ2W63R}},
note = {Machine review of arXiv:2505.12526}
}
read the original abstract
Temporal graph networks suffer from irregular supervision in realworld dynamic graphs, as most minibatches contain few labeled events. The lack of labels leads to high-variance gradient updates and, consequently, slow wall-clock convergence. To constructively reduce sparsity, our Moving-Averaged Labels (MAL) assigns soft pseudo-targets based on past supervised signals using a running label distribution while leaving the loss and the model architecture unchanged. Thus, supervision gaps are replaced with informative signals independent of a temporal graph model and the message passing or memory components used. Theoretical analysis supports our insight that aggregating historical supervision into moving average targets reduces stochastic gradient variance, yielding faster convergence under mild assumptions. Experimentally, for TGNv2 and DyRepv2 (our modification of DyRep) models, MAL boosts predictive performance, establishing a new SOTA, and improves time-to-accuracy (on average 6x faster to reach the top score) for a common suite of Temporal Graph Benchmark datasets.
Reference graph
Works this paper leans on
- [1]
-
[2]
T. Bertin-Mahieux, D. P. Ellis, B. Whitman, and P. Lamere. The million song dataset. In Ismir, volume 2, page 10, 2011
work page 2011
- [3]
-
[4]
S. Bubeck. Convex optimization: Algorithms and complexity. Foun- dations and Trends® in Machine Learning, 8(3–4):231–357, 2015. doi: 10.1561/2200000050
-
[5]
R. Cai, X. Bai, Z. Wang, Y . Shi, P. Sondhi, and H. Wang. Modeling sequential online interactive behaviors with temporal point process. In Proceedings of the 27th ACM international conference on information and knowledge management, pages 873–882, 2018
work page 2018
-
[6]
W. Cong, S. Zhang, J. Kang, B. Yuan, H. Wu, X. Zhou, H. Tong, and M. Mahdavi. Do we really need complicated model architectures for temporal networks?, 2023
work page 2023
-
[7]
S. Deng, H. Rangwala, and Y . Ning. Learning dynamic context graphs for predicting social events. In Proceedings of the 25th ACM SIGKDD international conference on knowledge discovery & data mining, pages 1007–1016, 2019
work page 2019
-
[8]
J. Gastinger, S. Huang, M. Galkin, E. Loghmani, A. Parviz, F. Pour- safaei, J. Danovitch, E. Rossi, I. Koutis, H. Stuckenschmidt, et al. TGB 2.0: A benchmark for learning on temporal knowledge graphs and het- erogeneous graphs. Advances in neural information processing systems, 37:140199–140229, 2024
work page 2024
Show all 40 references
-
[9]
S. Guo, Y . Lin, N. Feng, C. Song, and H. Wan. Attention based spatial-temporal graph convolutional networks for traffic flow forecast- ing. In Proceedings of the AAAI conference on artificial intelligence , volume 33, pages 922–929, 2019
2019
-
[10]
G. Han, W. Chen, X. Zhang, J. Xu, A. Liu, and L. Zhao. Tkgf-ntp: Temporal knowledge graph forecasting via neural temporal point pro- cess. In 2023 IEEE International Conference on Web Services (ICWS), pages 318–328. IEEE, 2023
2023
-
[11]
Huang, F
S. Huang, F. Poursafaei, J. Danovitch, M. Fey, W. Hu, E. Rossi, J. Leskovec, M. Bronstein, G. Rabusseau, and R. Rabbany. Temporal graph benchmark for machine learning on temporal graphs. Advances in Neural Information Processing Systems, 36:2056–2073, 2023
2023
-
[12]
R. J. Hyndman and G. Athanasopoulos. Forecasting: principles and practice. OTexts, 2018
2018
-
[13]
Järvelin and J
K. Järvelin and J. Kekäläinen. Cumulated gain-based evaluation of ir techniques. ACM Transactions on Information Systems (TOIS), 20(4): 422–446, 2002
2002
-
[14]
Johnson and T
R. Johnson and T. Zhang. Accelerating stochastic gradient descent us- ing predictive variance reduction. In Advances in Neural Information Processing Systems, pages 315–323, 2013
2013
-
[15]
D. P. Kingma and J. Ba. Adam: A method for stochastic optimization. International Conference on Learning Representations (ICLR), 2015
2015
-
[16]
Klenitskiy, A
A. Klenitskiy, A. V olodkevich, A. Pembek, and A. Vasilev. Does it look sequential? an analysis of datasets for evaluation of sequential recom- mendations. In Proceedings of the 18th ACM Conference on Recom- mender Systems, pages 1067–1072, 2024
2024
-
[17]
Kumar, X
S. Kumar, X. Zhang, and J. Leskovec. Predicting dynamic embed- ding trajectory in temporal interaction networks. In Proceedings of the 25th ACM SIGKDD international conference on knowledge discovery & data mining, pages 1269–1278, 2019
2019
-
[18]
Lee et al
D.-H. Lee et al. Pseudo-label: The simple and efficient semi-supervised learning method for deep neural networks. In Workshop on challenges in representation learning, ICML, volume 3, page 896. Atlanta, 2013
2013
-
[19]
Y . Li, J. Yin, and L. Chen. Informative pseudo-labeling for graph neural networks with few labels. Data Mining and Knowledge Discovery , 37 (1):228–254, 2023
2023
-
[20]
Z. Ma, K. Ethayarajh, T. Thrush, S. Jain, L. Wu, R. Jia, C. Potts, A. Williams, and D. Kiela. Dynaboard: An evaluation-as-a-service plat- form for holistic next-generation benchmarking. Advances in Neural Information Processing Systems, 34:10351–10367, 2021
2021
-
[21]
Pfaff, M
T. Pfaff, M. Fortunato, A. Sanchez-Gonzalez, and P. Battaglia. Learning mesh-based simulation with graph networks. In International confer- ence on learning representations, 2020
2020
-
[22]
Rakhlin, O
A. Rakhlin, O. Shamir, and K. Sridharan. Making gradient descent op- timal for strongly convex stochastic optimization. InProceedings of the 29th International Coference on International Conference on Machine Learning, pages 1571–1578, 2012
2012
-
[23]
Robbins and S
H. Robbins and S. Monro. A stochastic approximation method. The Annals of Mathematical Statistics, 22(3):400–407, 1951. doi: 10.1214/ aoms/1177729586
1951
-
[24]
Rossi, B
E. Rossi, B. Chamberlain, F. Frasca, D. Eynard, F. Monti, and M. Bron- stein. Temporal graph networks for deep learning on dynamic graphs. arXiv preprint arXiv:2006.10637, 2020
2006 arXiv
-
[25]
Sanchez-Gonzalez, J
A. Sanchez-Gonzalez, J. Godwin, T. Pfaff, R. Ying, J. Leskovec, and P. Battaglia. Learning to simulate complex physics with graph net- works. In International conference on machine learning, pages 8459–
-
[26]
Shalev-Shwartz and S
S. Shalev-Shwartz and S. Ben-David. Understanding machine learning: From theory to algorithms. Cambridge university press, 2014
2014
-
[27]
Shamir and T
O. Shamir and T. Zhang. Stochastic gradient descent for non-smooth optimization: Convergence results and optimal averaging schemes. In Proceedings of the 30th International Conference on Machine Learn- ing, ICML 2013, Atlanta, GA, USA, 16-21 June 2013 , volume 28 of JMLR Works...
2013
-
[28]
Shamsi, F
K. Shamsi, F. Victor, M. Kantarcioglu, Y . Gel, and C. G. Akcora. Char- talist: Labeled graph datasets for utxo and account-based blockchains. Advances in Neural Information Processing Systems, 35:34926–34939, 2022
2022
-
[29]
W. Song, Z. Xiao, Y . Wang, L. Charlin, M. Zhang, and J. Tang. Session- based social recommendation via dynamic graph attention networks. In Proceedings of the Twelfth ACM international conference on web search and data mining, pages 555–563, 2019
2019
-
[30]
B. A. Tjandra, F. Barbero, and M. Bronstein. Enhancing the expressivity of temporal graph networks through source-target identification. arXiv preprint arXiv:2411.03596, 2024
2024 arXiv
-
[31]
Trivedi, M
R. Trivedi, M. Farajtabar, P. Biswal, and H. Zha. Dyrep: Learning repre- sentations over dynamic graphs. In International Conference on Learn- ing Representations, 2019
2019
-
[32]
Wang and J
H. Wang and J. Leskovec. Unifying graph convolutional neural net- works and label propagation. arXiv preprint arXiv:2002.06755, 2020
2002 arXiv
-
[33]
Wang, Y .-Y
Y . Wang, Y .-Y . Chang, Y . Liu, J. Leskovec, and P. Li. Inductive repre- sentation learning in temporal networks via causal anonymous walks. arXiv preprint arXiv:2101.05974, 2021
2021 arXiv
-
[34]
Xie, M.-T
Q. Xie, M.-T. Luong, E. Hovy, and Q. V . Le. Self-training with noisy student improves imagenet classification. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pages 10687–10698, 2020
2020
-
[35]
D. Xu, C. Ruan, E. Korpeoglu, S. Kumar, and K. Achan. In- ductive representation learning on temporal graphs. arXiv preprint arXiv:2002.07962, 2020
2002 arXiv
-
[36]
Y . You, Z. Zhang, C.-J. Hsieh, J. Demmel, and K. Keutzer. ImageNet training in minutes. In Proceedings of the 47th international conference on parallel processing, pages 1–10, 2018
2018
-
[37]
L. Yu, L. Sun, B. Du, and W. Lv. Towards better dynamic graph learn- ing: New architecture and unified library. In Thirty-seventh Conference on Neural Information Processing Systems, 2023
2023
-
[38]
Zhan and C
K. Zhan and C. Niu. Mutual teaching for graph convolutional networks. Future Generation Computer Systems, 115:837–843, 2021
2021
-
[39]
L. Zhao, Y . Song, C. Zhang, Y . Liu, P. Wang, T. Lin, M. Deng, and H. Li. T-GCN: A temporal graph convolutional network for traffic prediction. IEEE transactions on intelligent transportation systems , 21(9):3848– 3858, 2019
2019
-
[40]
X. Zhu. Semi-supervised learning with graphs. Carnegie Mellon Uni- versity, 2005. A Proofs of the theoretical results For convenience, we repeat below the statements we aim to prove. Lemma 4. The expectation of th is u k and the variance of th isuk−1 k2h +u(1−u) 1 k2 . Proof. ...
2005
Reviewed August 15, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.