# Efficient Neural Common Neighbor for Temporal Graph Link Prediction

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

## Key facts

- Cited by 18 papers in the map (data through 14 Oct 2026).
- Builds on 32 of its 57 references that are in the map.
- First posted on arXiv 12 Jun 2024.

## Builds on (most cited first, 30 of 32)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering](https://mlsanity.com/paper/1606.09375/) (2016)
- [Link Prediction Based on Graph Neural Networks](https://mlsanity.com/paper/1802.09691/) (2018)
- [Temporal Graph Networks for Deep Learning on Dynamic Graphs](https://mlsanity.com/paper/2006.10637/) (2020)
- [Masked Label Prediction: Unified Message Passing Model for Semi-Supervised Classification](https://mlsanity.com/paper/2009.03509/) (2020)
- [Graph Neural Networks in Recommender Systems: A Survey](https://mlsanity.com/paper/2011.02260/) (2020)
- [Inductive Representation Learning on Temporal Graphs](https://mlsanity.com/paper/2002.07962/) (2020)
- [Predicting Dynamic Embedding Trajectory in Temporal Interaction Networks](https://mlsanity.com/paper/1908.01207/) (2019)
- [Neural Bellman-Ford Networks: A General Graph Neural Network Framework for Link Prediction](https://mlsanity.com/paper/2106.06935/) (2021)
- [Time2Vec: Learning a Vector Representation of Time](https://mlsanity.com/paper/1907.05321/) (2019)
- [Inductive Representation Learning in Temporal Networks via Causal Anonymous Walks](https://mlsanity.com/paper/2101.05974/) (2021)
- [Towards Better Dynamic Graph Learning: New Architecture and Unified Library](https://mlsanity.com/paper/2303.13047/) (2023)
- [Labeling Trick: A Theory of Using Graph Neural Networks for Multi-Node Representation Learning](https://mlsanity.com/paper/2010.16103/) (2020)
- [Do We Really Need Complicated Model Architectures For Temporal Networks?](https://mlsanity.com/paper/2302.11636/) (2023)
- [Temporal Graph Benchmark for Machine Learning on Temporal Graphs](https://mlsanity.com/paper/2307.01026/) (2023)
- [Towards Better Evaluation for Dynamic Link Prediction](https://mlsanity.com/paper/2207.10128/) (2022)
- [Graph Neural Networks for Link Prediction with Subgraph Sketching](https://mlsanity.com/paper/2209.15486/) (2022)
- [APAN: Asynchronous Propagation Attention Network for Real-time Temporal Graph Embedding](https://mlsanity.com/paper/2011.11545/) (2020)
- [Neo-GNNs: Neighborhood Overlap-aware Graph Neural Networks for Link Prediction](https://mlsanity.com/paper/2206.04216/) (2022)
- [Evaluating Graph Neural Networks for Link Prediction: Current Pitfalls and New Benchmarking](https://mlsanity.com/paper/2306.10453/) (2023)
- [TCL: Transformer-based Dynamic Graph Modelling via Contrastive Learning](https://mlsanity.com/paper/2105.07944/) (2021)
- [Neural Common Neighbor with Completion for Link Prediction](https://mlsanity.com/paper/2302.00890/) (2023)
- [Neighborhood-aware Scalable Temporal Network Representation Learning](https://mlsanity.com/paper/2209.01084/) (2022)
- [Revisiting Link Prediction: A Data Perspective](https://mlsanity.com/paper/2310.00793/) (2023)
- [LPFormer: An Adaptive Graph Transformer for Link Prediction](https://mlsanity.com/paper/2310.11009/) (2023)
- [DistTGL: Distributed Memory-Based Temporal Graph Neural Network Training](https://mlsanity.com/paper/2307.07649/) (2023)
- [Repeat-Aware Neighbor Sampling for Dynamic Graph Learning](https://mlsanity.com/paper/2405.17473/) (2024)
- [Efficient Dynamic Graph Representation Learning at Scale](https://mlsanity.com/paper/2112.07768/) (2021)

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

- [TIDFormer: Exploiting Temporal and Interactive Dynamics Makes A Great Dynamic Graph Transformer](https://mlsanity.com/paper/2506.00431/) (2025)
- [Understanding and Improving Laplacian Positional Encodings For Temporal GNNs](https://mlsanity.com/paper/2506.01596/) (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)
- [TAMI: Taming Heterogeneity in Temporal Interactions for Temporal Graph Link Prediction](https://mlsanity.com/paper/2510.23577/) (2025)
- [Higher-order Structure Boosts Link Prediction on Temporal Graphs](https://mlsanity.com/paper/2505.15746/) (2025)
- [HyperEvent: A Strong Baseline for Dynamic Link Prediction via Relative Structural Encoding](https://mlsanity.com/paper/2507.11836/) (2025)
- [Self-Exploring Language Models for Explainable Link Forecasting on Temporal Graphs via Reinforcement Learning](https://mlsanity.com/paper/2509.00975/) (2025)
- [Integrating Sequential and Relational Modeling for User Events: Datasets and Prediction Tasks](https://mlsanity.com/paper/2510.11903/) (2025)
- [Where Does Neural Advantage Arise in Continuous-Time Dynamic Graph Prediction?](https://mlsanity.com/paper/2608.06765/) (2026)
- [Bridging the Divide: End-to-End Sequence-Graph Learning](https://mlsanity.com/paper/2510.25126/) (2025)
- [Kernelized Edge Attention: Addressing Semantic Attention Blurring in Temporal Graph Neural Networks](https://mlsanity.com/paper/2602.00596/) (2026)
- [Institutional Equity Holdings Prediction Using Node Affinities of Dynamic Graphs](https://mlsanity.com/paper/2607.12067/) (2026)
- [A Survey on GNN-based Link Prediction: Techniques, Applications, and Challenges](https://mlsanity.com/paper/2607.16198/) (2026)
- [Back to All-Entity Ranking: Sampler-Dependent Evaluation in Continuous-Time Dynamic Graphs](https://mlsanity.com/paper/2607.27861/) (2026)
- [HAWKEYE: Seeing One Layer Deeper -- A Cohesion-Aware Structural Channel for Temporal Link Prediction](https://mlsanity.com/paper/2608.22727/) (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)

Temporal graphs are widespread in real-world applications such as social networks, as well as trade and transportation networks. Predicting dynamic links within these evolving graphs is a key problem. Many memory-based methods use temporal interaction histories to generate node embeddings, which are then combined to predict links. However, these approaches primarily focus on individual node representations, often overlooking the inherently pairwise nature of link prediction. While some recent methods attempt to capture pairwise features, they tend to be limited by high computational complexity arising from repeated embedding calculations, making them unsuitable for large-scale datasets like the Temporal Graph Benchmark (TGB). To address the critical need for models that combine strong expressive power with high computational efficiency for link prediction on large temporal graphs, we propose Temporal Neural Common Neighbor (TNCN). Our model achieves this balance by adapting the powerful pairwise modeling principles of Neural Common Neighbor (NCN) to an efficient temporal architecture. TNCN improves upon NCN by efficiently preserving and updating temporal neighbor dictionaries for each node and by using multi-hop common neighbors to learn more expressive pairwise representations. TNCN achieves new state-of-the-art performance on Review from five large-scale real-world TGB datasets, 6 out of 7 datasets in the transductive setting and 3 out of 7 in the inductive setting on small- to medium-scale datasets. Additionally, TNCN demonstrates excellent scalability, outperforming prominent GNN baselines by up to 30.3 times in speed on large datasets. Our code is available at https://github.com/GraphPKU/TNCN.