# On the Power of Heuristics in Temporal Graphs

arXiv: https://arxiv.org/abs/2502.04910 · HTML: https://mlsanity.com/paper/2502.04910/

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 7 Feb 2025.

## Built on by (most cited first, 11 of 11)

- [What Do Temporal Graph Learning Models Learn?](https://mlsanity.com/paper/2510.09416/) (2025)
- [Are Large Language Models Good Temporal Graph Learners?](https://mlsanity.com/paper/2506.05393/) (2025)
- [Base3: a simple interpolation-based ensemble method for robust dynamic link prediction](https://mlsanity.com/paper/2506.12764/) (2025)
- [TGM: a Modular and Efficient Library for Machine Learning on Temporal Graphs](https://mlsanity.com/paper/2510.07586/) (2025)
- [Are We Really Measuring Progress? Transferring Insights from Evaluating Recommender Systems to Temporal Link Prediction](https://mlsanity.com/paper/2506.12588/) (2025)
- [Revisiting Node Affinity Prediction in Temporal Graphs](https://mlsanity.com/paper/2510.06940/) (2025)
- [Relatron: Automating Relational Machine Learning over Relational Databases](https://mlsanity.com/paper/2602.22552/) (2026)
- [Where Does Neural Advantage Arise in Continuous-Time Dynamic Graph Prediction?](https://mlsanity.com/paper/2608.06765/) (2026)
- [What Softmax Throws Away: Mass-Aware Attention for Evidence Accumulation](https://mlsanity.com/paper/2607.22781/) (2026)
- [Beat the Counter First: A Baseline for Temporal-Graph Anomaly Detectors](https://mlsanity.com/paper/2608.15965/) (2026)
- [Do Temporal Link Predictors Need Learned Memory? A Smoothed-Count Baseline with a Handful of Parameters](https://mlsanity.com/paper/2609.35364/) (2026)

## Abstract (arXiv)

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.