Pith. sign in

REVIEW 3 major objections 6 minor 1 cited by

On the Power of Heuristics in Temporal Graphs

T0 review · 3 major / 6 minor · reviewed 2026-08-08 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read This paper claims that four simple recency- and popularity-counting heuristics match or exceed state-of-the-art neural network models on standard temporal graph link prediction benchmarks, making reported deep-learning gains look partly…

desk verdict A useful cautionary result undermined by a post-hoc per-dataset tweak; the SOTA claim is not supported as stated, but the heuristics and diagnostic deserve a serious look. read the letter →

arxiv 2502.04910 v1 pith:DCM375YT submitted 2025-02-07 cs.LG

Filip Cornell , Oleg Smirnov , Gabriela Zarzar Gandler , Lele Cao This is my paper · ORCID
classification cs.LG
keywords temporalgraphslinkpredictionrecencyheuristicpopularitybenchmarkevaluationMeanReciprocalRanknegativesampling
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper tries to establish that much of what looks like progress in temporal graph link prediction is actually memorization of simple temporal regularities. It shows that four scores — how recently a node was a destination, how recently two nodes interacted, and the global and local counts of such events — can be combined into a heuristic that matches or beats state-of-the-art neural models on the Temporal Graph Benchmark and ranks at or near the top on BenchTemp. If the result holds, it resets the minimum bar for temporal graph models and makes fair evaluation the central problem.

What carries the argument

The load-bearing machinery is a family of four integer-valued scores: Global Recency (last timestamp any source linked to the destination), Local Recency (last timestamp the query source linked to the destination), Global Popularity (total times the destination appeared), and Local Popularity (total times the source chose that destination). Candidates are ranked by one heuristic, with ties resolved by the next in a fixed order. Because scores are integers, exact optimistic and pessimistic ranks for all candidates can be computed in $O(\log S)$ time using Fenwick trees, making full-ranking evaluation feasible where neural baselines rely on biased sampling. A complementary diagnostic, Complementary Normalized Rank (CNR), plots the fraction of true edges ranked at least as high as a given rank percentile, showing how much signal recency and popularity carry in each dataset.

What would settle it

Run the same TGB and BenchTemp evaluations under a pre-registered rule that selects the heuristic from training data alone (or with a fixed heuristic for all datasets); if the resulting Mean Reciprocal Rank drops below the neural baselines, the state-of-the-art claim would be refuted. Checking whether the inverse-LR result for tgbl-review was decided after inspecting test edges would settle the point directly.

Watch

Extended reading notes

Core claim

On the paper's terms, the central discovery is that under the standard sampled-negative evaluation protocols, heuristic ranking by recency and popularity alone achieves state-of-the-art Mean Reciprocal Rank on all TGB datasets tested and top ranks on several BenchTemp datasets, while neural networks often fall behind. Recency is the stronger signal, but popularity works as a tie-breaker, and the optimal heuristic combination differs per dataset. The authors interpret this as evidence that current deep models struggle to capture the dominant temporal patterns, and that sampled evaluation with easy negatives can overstate model quality.

Load-bearing premise

The claim depends on the heuristics having been chosen per dataset without using test-set labels, including the decision to invert Local Recency for the review dataset after observing that almost all new edges point to unseen destinations.

Editorial extensions

If this is right

  • New temporal graph models should be required to beat these heuristic baselines in the same evaluation protocol before claiming advances.
  • Sampled negative evaluation, which is standard in these benchmarks, can systematically favor learned models; full-ranking evaluation or harder negative sampling is needed for trustworthy comparisons.
  • Dataset-specific heuristic choice matters: no single recency or popularity score dominates, so benchmarks should report per-dataset patterns that determine which baseline is appropriate.
  • Because the heuristics run on a CPU in seconds to minutes while neural models run on GPUs for hours, cheap strong baselines are now available for large-scale temporal graph pipelines.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The inverse-LR trick for the review dataset suggests a general protocol: measure a dataset's novelty (fraction of new edges to previously unseen destinations) before training, and let that decide whether recency should be maximized or inverted; neural models that cannot switch inductive bias this cheaply will be at a structural disadvantage.
  • If the same heuristic audit were applied to other temporal graph benchmarks, leaderboard gaps between neural methods may shrink substantially, implying some published gains are specific to easy negative sampling rather than to temporal reasoning.
  • A directly testable extension would be to feed these heuristic scores as input features to neural models; the paper's results imply such hybrids should outperform both pure heuristics and pure neural methods.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 6 minor

Summary. The paper proposes four deterministic heuristics for temporal link prediction—global/local recency and global/local popularity—and a lexicographic combination thereof, plus a CNR metric for visualizing recency/popularity effects. It evaluates these on TGB and BenchTemp, reporting MRR/AUC-ROC and runtime comparisons, and claims that the heuristics achieve state-of-the-art performance on all TGB datasets.

Significance. The heuristics are simple, parameter-free, and efficiently implementable with Fenwick trees; the CNR plots are a useful diagnostic tool. If the claims were fully substantiated, the paper would be an important cautionary result showing that current temporal link prediction benchmarks can be solved by memorization of recency/popularity. However, the headline claim is currently not supported because the reported 'Combined' results include per-dataset heuristic selection and a test-informed inverse-LR modification for tgbl-review, and the best heuristic varies across datasets. The paper is a useful contribution to the evaluation critique, but the central claim requires substantial revision.

major comments (3)
  1. [§3.3, §C, Table 2] The tgbl-review Combined MRR of 0.522 (Table 2) is not produced by the fixed order LR → GR → LP → GP stated in §3.3; Appendix C explains that after observing that approximately 98% of new tgbl-review edges connect to previously unseen destinations, the authors 'apply an inverse LR heuristic' and combine it with GR. No a priori rule is given for when to invert LR. If this modification was chosen after inspecting test-set statistics, the reported number is a selected result rather than a prediction, and the abstract's 'state-of-the-art performance across all datasets' claim is unsupported.
  2. [Tables 1 and 2] No single heuristic, including Combined, is the best on all TGB datasets: on tgbl-comment, GP (0.723) substantially outperforms Combined (0.455), and on tgbl-subreddit, LP (0.738) outperforms Combined (0.717). The claim of state-of-the-art across all datasets therefore requires per-dataset selection of the best heuristic, which is not described as a fixed rule. The paper should either report a single fixed heuristic that achieves the claimed result on all datasets or revise the claim to 'the best of our heuristics per dataset achieves...'.
  3. [§3.3, Tables 1-2] The reported MRR values for the discrete heuristics depend on tie-breaking, but the paper does not state how ties are broken when computing MRR. The paper defines optimistic and pessimistic ranks only for CNR (§5), yet many heuristics produce numerous ties, especially on coarser timestamps. Without specifying whether MRR uses R+, R−, or random tie-breaking, the numbers are ambiguous and could be optimistically biased. Please report the tie-breaking rule used and, ideally, give both optimistic and pessimistic MRR.
minor comments (6)
  1. [§5] The definition of CNR is self-referential: 'CNR(p) = 1 − Rp/|E|' followed by 'Rp = |E|(1 − CNR(p))'; please define Rp as the rank such that a fraction p of edges are ranked no lower than Rp, and clarify the direction.
  2. [§3.3] The statement 'Selecting optimal heuristics for speed and performance depends on the dataset and is left for future study' sits uneasily with the abstract's 'state-of-the-art across all datasets' claim; please reconcile the two.
  3. [Table 1 vs Table 2] Table 1 omits tgbl-subreddit while Table 2 includes it; the main text should be consistent about which TGB datasets are covered.
  4. [Abstract/Reproducibility] The paper states that code is publicly available but does not provide a URL or repository identifier in the preprint.
  5. [Figure 1] Figure 1 duplicates Figure 2a for tgbl-review; consider merging to reduce redundancy.
  6. [General] There are minor typographical inconsistencies, e.g., 'T aoBao' in Figure 2 caption and 'UNtrade' vs 'UNTrade' in Tables 3-4.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the heuristics are deterministic, parameter-free functions of past edges, evaluated against external benchmarks; the per-dataset heuristic choice is a model-selection concern, not a circular derivation.

full rationale

The paper's central claims are empirical comparisons between fixed heuristic scoring functions and neural baselines on public benchmarks. The heuristic definitions (GR, LR, GP, LP) are given directly as functions of past temporal edges and contain no fitted parameters; there is no equation in which an output is defined in terms of the target quantity it is supposed to predict. The Combined heuristic is a lexicographic composition defined in Section 3.3 independently of any benchmark result. The only potentially problematic passage is Appendix C's inverse-LR modification for tgbl-review, which is a per-dataset heuristic choice rather than a fitted parameter; even if that choice was informed by test-set behavior, it does not make the reported MRR equal to the heuristic's input by construction, so it is a soundness/overfitting issue rather than circularity. The paper contains no load-bearing self-citations: prior heuristic work (EdgeBank, PopTrack) is cited as related work but the present heuristics are defined from scratch. No uniqueness theorem is imported, and no known result is merely renamed. Consequently, the derivation chain is self-contained with respect to circularity, and the score is 0.

Assumptions & free parameters 2 free parameters · 2 assumptions · 0 invented entities

The method has no numeric free parameters, but the heuristic combination order is a design choice, and for tgbl-review the authors adopt an inverse-LR variant after observing data characteristics. The evaluation also assumes the official sampled metrics are the right standard, even though the paper itself cites results that sampled metrics are biased.

free parameters (2)
  • Per-dataset heuristic choice = LR->GR->LP->GP for most datasets; inverse LR+GR for tgbl-review
    Selected after inspecting the data, not part of a fixed algorithm. The tgbl-review exception is described in Appendix C.
  • Tie-breaking convention for MRR = Unspecified (optimistic vs pessimistic)
    Discrete scores create many ties; the reported numbers may depend on this choice, which is not documented in the main text.
assumptions (2)
  • domain assumption The official TGB and BenchTemp sampled negative metrics are the appropriate 'standard evaluation protocols' for judging link predictors.
    The paper's SOTA claim is relative to these leaderboards, while Appendix B acknowledges that sampled metrics are biased (citing Krichene and Rendle).
  • standard math Heuristics only use edges prior to the query timestamp and do not update on test edges.
    The definitions in Section 3 restrict scores to tau < t, which is required for a fair transductive evaluation.

how reviews work

0 comments
Cite this review

Pith. "Pith review of On the Power of Heuristics in Temporal Graphs." pith.science (2026). https://pith.science/paper/DCM375YT

@misc{pith2026250204910,
  author       = {Pith},
  title        = {Pith review of: On the Power of Heuristics in Temporal Graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/DCM375YT}},
  note         = {Machine review of arXiv:2502.04910}
}
read the original abstract

Dynamic graph datasets often exhibit strong temporal patterns, such as recency, which prioritizes recent interactions, and popularity, which favors frequently occurring nodes. We demonstrate that simple heuristics leveraging only these patterns can perform on par or outperform state-of-the-art neural network models under standard evaluation protocols. To further explore these dynamics, we introduce metrics that quantify the impact of recency and popularity across datasets. Our experiments on BenchTemp and the Temporal Graph Benchmark show that our approaches achieve state-of-the-art performance across all datasets in the latter and secure top ranks on multiple datasets in the former. These results emphasize the importance of refined evaluation schemes to enable fair comparisons and promote the development of more robust temporal graph models. Additionally, they reveal that current deep learning methods often struggle to capture the key patterns underlying predictions in real-world temporal graphs. For reproducibility, we have made our code publicly available.

Figures

Figures reproduced from arXiv: 2502.04910 by the authors.

Figure 1
Figure 1. Complementary Normalized Rank (CNR) plots comparing optimistic ( [PITH_FULL_IMAGE:figures/full_fig_p004_1.png] view at source ↗
Figure 2
Figure 2. Complementary Normalized Ranking Plots showing optimistic ( [PITH_FULL_IMAGE:figures/full_fig_p009_2.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Are Large Language Models Good Temporal Graph Learners?

    cs.CL 2025-06 conditional novelty 6.0 of 10

    TGTalker prompts LLMs with the most recent edges and neighbor history of a temporal graph, achieving link prediction accuracy competitive with specialized temporal graph neural networks on five real-world datasets.

Reference graph

Works this paper leans on

31 extracted references · 23 canonical work pages · cited by 1 Pith paper

  1. [1]

    write newline

    " write newline "" before.all 'output.state := FUNCTION n.dashify 't := "" t empty not t #1 #1 substring "-" = t #1 #2 substring "--" = not "--" * t #2 global.max substring 't := t #1 #1 substring "-" = "-" * t #2 global.max substring 't := while if t #1 #1 substring * t #2 global.max substring 't := if while FUNCTION format.date year duplicate empty "emp...

  2. [2]

    Bringing light into the dark: A large-scale evaluation of knowledge graph embedding models under a unified framework

    Mehdi Ali, Max Berrendorf, Charles Tapley Hoyt, Laurent Vermue, Mikhail Galkin, Sahand Sharifzadeh, Asja Fischer, Volker Tresp, and Jens Lehmann. Bringing light into the dark: A large-scale evaluation of knowledge graph embedding models under a unified framework. IEEE Transactions on Pattern Analysis and Machine Intelligence, 44 0 (12): 0 8825--8845, 2021

    work page 2021

  3. [3]

    Bias and debias in recommender system: A survey and future directions

    Jiawei Chen, Hande Dong, Xiang Wang, Fuli Feng, Meng Wang, and Xiangnan He. Bias and debias in recommender system: A survey and future directions. ACM Transactions on Information Systems, 41 0 (3): 0 1--39, 2023

    2023

  4. [4]

    Do we really need complicated model architectures for temporal networks? In The Eleventh International Conference on Learning Representations, 2023

    Weilin Cong, Si Zhang, Jian Kang, Baichuan Yuan, Hao Wu, Xin Zhou, Hanghang Tong, and Mehrdad Mahdavi. Do we really need complicated model architectures for temporal networks? In The Eleventh International Conference on Learning Representations, 2023

    work page 2023

  5. [6]

    A new data structure for cumulative frequency tables

    Peter M Fenwick. A new data structure for cumulative frequency tables. Software: Practice and experience, 24 0 (3): 0 327--336, 1994

    work page 1994

  6. [7]

    Long range propagation on continuous-time dynamic graphs

    Alessio Gravina, Giulio Lovisotto, Claudio Gallicchio, Davide Bacciu, and Claas Grohnfeldt. Long range propagation on continuous-time dynamic graphs. In Proceedings of the 41st International Conference on Machine Learning, ICML'24, 2024

    work page 2024

  7. [8]

    Benchtemp: A general benchmark for evaluating temporal graph neural networks

    Qiang Huang, Xin Wang, Susie Xi Rao, Zhichao Han, Zitao Zhang, Yongjun He, Quanqing Xu, Yang Zhao, Zhigao Zheng, and Jiawei Jiang. Benchtemp: A general benchmark for evaluating temporal graph neural networks. In 2024 IEEE 40th International Conference on Data Engineering (ICDE), pp.\ 4044--4057. IEEE, 2024 a

    work page 2024

  8. [9]

    Temporal graph benchmark for machine learning on temporal graphs

    Shenyang Huang, Farimah Poursafaei, Jacob Danovitch, Matthias Fey, Weihua Hu, Emanuele Rossi, Jure Leskovec, Michael Bronstein, Guillaume Rabusseau, and Reihaneh Rabbany. Temporal graph benchmark for machine learning on temporal graphs. Advances in Neural Information Processing Systems, 36, 2024 b

    work page 2024

Show all 31 references
  1. [10]

    Neural temporal walks: Motif-aware representation learning on continuous-time dynamic graphs

    Ming Jin, Yuan-Fang Li, and Shirui Pan. Neural temporal walks: Motif-aware representation learning on continuous-time dynamic graphs. Advances in Neural Information Processing Systems, 35: 0 19874--19886, 2022

    2022

  2. [11]

    A survey on popularity bias in recommender systems

    Anastasiia Klimashevskaia, Dietmar Jannach, Mehdi Elahi, and Christoph Trattner. A survey on popularity bias in recommender systems. User Modeling and User-Adapted Interaction, 34 0 (5): 0 1777--1834, 2024

    2024

  3. [12]

    On sampled metrics for item recommendation

    Walid Krichene and Steffen Rendle. On sampled metrics for item recommendation. In Proceedings of the 26th ACM SIGKDD international conference on knowledge discovery & data mining, pp.\ 1748--1757, 2020

    2020

  4. [13]

    Predicting dynamic embedding trajectory in temporal interaction networks

    Srijan Kumar, Xikun Zhang, and Jure Leskovec. Predicting dynamic embedding trajectory in temporal interaction networks. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD ’19. ACM, July 2019 a . doi:10.1145/3292500.3330895

    2019

  5. [14]

    Predicting dynamic embedding trajectory in temporal interaction networks

    Srijan Kumar, Xikun Zhang, and Jure Leskovec. Predicting dynamic embedding trajectory in temporal interaction networks. In Proceedings of the 25th ACM SIGKDD international conference on knowledge discovery & data mining, pp.\ 1269--1278, 2019 b

    2019

  6. [15]

    Neighborhood-aware scalable temporal network representation learning

    Yuhong Luo and Pan Li. Neighborhood-aware scalable temporal network representation learning. In Learning on Graphs Conference, pp.\ 1--1. PMLR, 2022

    2022

  7. [16]

    Mixture of link predictors on graphs

    Li Ma, Haoyu Han, Juanhui Li, Harry Shomer, Hui Liu, Xiaofeng Gao, and Jiliang Tang. Mixture of link predictors on graphs. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024

    2024

  8. [17]

    Towards better evaluation for dynamic link prediction

    Farimah Poursafaei, Shenyang Huang, Kellin Pelrine, and Reihaneh Rabbany. Towards better evaluation for dynamic link prediction. Advances in Neural Information Processing Systems, 35: 0 32928--32941, 2022 a

    2022

  9. [18]

    A strong node classification baseline for temporal graphs

    Farimah Poursafaei, Zeljko Zilic, and Reihaneh Rabbany. A strong node classification baseline for temporal graphs. In Proceedings of the 2022 SIAM International Conference on Data Mining (SDM), pp.\ 648--656. SIAM, 2022 b

    2022

  10. [19]

    Temporal graph networks for deep learning on dynamic graphs

    Emanuele Rossi, Ben Chamberlain, Fabrizio Frasca, Davide Eynard, Federico Monti, and Michael Bronstein. Temporal graph networks for deep learning on dynamic graphs. arXiv preprint arXiv:2006.10637, 2020 a

    2006 arXiv

  11. [20]

    Temporal graph networks for deep learning on dynamic graphs

    Emanuele Rossi, Ben Chamberlain, Fabrizio Frasca, Davide Eynard, Federico Monti, and Michael Bronstein. Temporal graph networks for deep learning on dynamic graphs. In ICML 2020 Workshop on Graph Representation Learning, 2020 b

    2020

  12. [21]

    Temporal graph analysis with tgx

    Razieh Shirzadkhani, Shenyang Huang, Elahe Kooshafar, Reihaneh Rabbany, and Farimah Poursafaei. Temporal graph analysis with tgx. In Proceedings of the 17th ACM International Conference on Web Search and Data Mining, pp.\ 1086--1089, 2024

    2024

  13. [22]

    Dyrep: Learning representations over dynamic graphs

    Rakshit Trivedi, Mehrdad Farajtabar, Prasenjeet Biswal, and Hongyuan Zha. Dyrep: Learning representations over dynamic graphs. In International conference on learning representations, 2019

    2019

  14. [23]

    Tcl: Transformer-based dynamic graph modelling via contrastive learning

    Lu Wang, Xiaofu Chang, Shuang Li, Yunfei Chu, Hui Li, Wei Zhang, Xiaofeng He, Le Song, Jingren Zhou, and Hongxia Yang. Tcl: Transformer-based dynamic graph modelling via contrastive learning. arXiv preprint arXiv:2105.07944, 2021 a

    2021 arXiv

  15. [24]

    Inductive representation learning in temporal networks via causal anonymous walks

    Yanbang Wang, Yen-Yu Chang, Yunyu Liu, Jure Leskovec, and Pan Li. Inductive representation learning in temporal networks via causal anonymous walks. In International Conference on Learning Representations (ICLR), 2021 b

    2021

  16. [25]

    A survey on the fairness of recommender systems

    Yifan Wang, Weizhi Ma, Min Zhang, Yiqun Liu, and Shaoping Ma. A survey on the fairness of recommender systems. ACM Transactions on Information Systems, 41 0 (3): 0 1--43, 2023

    2023

  17. [26]

    On the feasibility of simple transformer for dynamic graph modeling

    Yuxia Wu, Yuan Fang, and Lizi Liao. On the feasibility of simple transformer for dynamic graph modeling. In Proceedings of the ACM on Web Conference 2024, pp.\ 870--880, 2024

    2024

  18. [27]

    Inductive representation learning on temporal graphs

    Da Xu, Chuanwei Ruan, Evren Korpeoglu, Sushant Kumar, and Kannan Achan. Inductive representation learning on temporal graphs. In International Conference on Learning Representations, 2020

    2020

  19. [28]

    Towards better dynamic graph learning: New architecture and unified library

    Le Yu, Leilei Sun, Bowen Du, and Weifeng Lv. Towards better dynamic graph learning: New architecture and unified library. Advances in Neural Information Processing Systems, 36: 0 67686--67700, 2023

    2023

  20. [29]

    Efficient neural common neighbor for temporal graph link prediction

    Xiaohui Zhang, Yanbo Wang, Xiyuan Wang, and Muhan Zhang. Efficient neural common neighbor for temporal graph link prediction. arXiv preprint arXiv:2406.07926, 2024

    2024

  21. [30]

    @esa (Ref

    \@ifxundefined[1] #1\@undefined \@firstoftwo \@secondoftwo \@ifnum[1] #1 \@firstoftwo \@secondoftwo \@ifx[1] #1 \@firstoftwo \@secondoftwo [2] @ #1 \@temptokena #2 #1 @ \@temptokena \@ifclassloaded agu2001 natbib The agu2001 class already includes natbib coding, so you should ...

  22. [31]

    \@lbibitem[] @bibitem@first@sw\@secondoftwo \@lbibitem[#1]#2 \@extra@b@citeb \@ifundefined br@#2\@extra@b@citeb \@namedef br@#2 \@nameuse br@#2\@extra@b@citeb \@ifundefined b@#2\@extra@b@citeb @num @parse #2 @tmp #1 NAT@b@open@#2 NAT@b@shut@#2 \@ifnum @merge>\@ne @bibitem@firs...

  23. [32]

    Since the heuristics rely exclusively on recency, batching inherently leads to a measurable loss of information, as temporally dependent edges are grouped together

    @open @close @open @close and [1] URL: #1 \@ifundefined chapter * \@mkboth \@ifxundefined @sectionbib * \@mkboth * \@mkboth\@gobbletwo \@ifclassloaded amsart * \@ifclassloaded amsbook * \@ifxundefined @heading @heading NAT@ctr thebibliography [1] @ \@biblabel @NAT@ctr \@bibset...

    2022 arXiv

Pith tools

Reviewed August 8, 2026 · model on record in the stance chip above.