# PageRank Bandits for Link Prediction

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

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- Builds on 54 of its 80 references that are in the map.
- First posted on arXiv 3 Nov 2024.

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

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [Neural Message Passing for Quantum Chemistry](https://mlsanity.com/paper/1704.01212/) (2017)
- [Neural Tangent Kernel: Convergence and Generalization in Neural Networks](https://mlsanity.com/paper/1806.07572/) (2018)
- [Open Graph Benchmark: Datasets for Machine Learning on Graphs](https://mlsanity.com/paper/2005.00687/) (2020)
- [node2vec: Scalable Feature Learning for Networks](https://mlsanity.com/paper/1607.00653/) (2016)
- [DeepWalk: Online Learning of Social Representations](https://mlsanity.com/paper/1403.6652/) (2014)
- [Revisiting Semi-Supervised Learning with Graph Embeddings](https://mlsanity.com/paper/1603.08861/) (2016)
- [Link Prediction Based on Graph Neural Networks](https://mlsanity.com/paper/1802.09691/) (2018)
- [A Convergence Theory for Deep Learning via Over-Parameterization](https://mlsanity.com/paper/1811.03962/) (2018)
- [LINE: Large-scale Information Network Embedding](https://mlsanity.com/paper/1503.03578/) (2015)
- [Gradient Descent Finds Global Minima of Deep Neural Networks](https://mlsanity.com/paper/1811.03804/) (2018)
- [On Exact Computation with an Infinitely Wide Neural Net](https://mlsanity.com/paper/1904.11955/) (2019)
- [Temporal Graph Networks for Deep Learning on Dynamic Graphs](https://mlsanity.com/paper/2006.10637/) (2020)
- [Inductive Representation Learning on Temporal Graphs](https://mlsanity.com/paper/2002.07962/) (2020)
- [Neural Bellman-Ford Networks: A General Graph Neural Network Framework for Link Prediction](https://mlsanity.com/paper/2106.06935/) (2021)
- [A Review of Relational Machine Learning for Knowledge Graphs](https://mlsanity.com/paper/1503.00759/) (2015)
- [Generalization Bounds of Stochastic Gradient Descent for Wide and Deep Neural Networks](https://mlsanity.com/paper/1905.13210/) (2019)
- [Inductive Representation Learning in Temporal Networks via Causal Anonymous Walks](https://mlsanity.com/paper/2101.05974/) (2021)
- [Finite-Time Analysis of Kernelised Contextual Bandits](https://mlsanity.com/paper/1309.6869/) (2013)
- [Deep Bayesian Bandits Showdown: An Empirical Comparison of Bayesian Deep Networks for Thompson Sampling](https://mlsanity.com/paper/1802.09127/) (2018)
- [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)
- [Data Augmentation for Deep Graph Learning: A Survey](https://mlsanity.com/paper/2202.08235/) (2022)
- [Neural Thompson Sampling](https://mlsanity.com/paper/2010.00827/) (2020)
- [Inductive Matrix Completion Based on Graph Neural Networks](https://mlsanity.com/paper/1904.12058/) (2019)
- [Graph Neural Networks for Link Prediction with Subgraph Sketching](https://mlsanity.com/paper/2209.15486/) (2022)
- [Neo-GNNs: Neighborhood Overlap-aware Graph Neural Networks for Link Prediction](https://mlsanity.com/paper/2206.04216/) (2022)
- [Neural Contextual Bandits with Deep Representation and Shallow Exploration](https://mlsanity.com/paper/2012.01780/) (2020)

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

- [Language in the Flow of Time: Time-Series-Paired Texts Weaved into a Unified Temporal Narrative](https://mlsanity.com/paper/2502.08942/) (2025)
- [Transformer Copilot: Learning from The Mistake Log in LLM Fine-tuning](https://mlsanity.com/paper/2505.16270/) (2025)
- [Pave Your Own Path: Graph Gradual Domain Adaptation on Fused Gromov-Wasserstein Geodesics](https://mlsanity.com/paper/2505.12709/) (2025)
- [Graph4MM: Weaving Multimodal Learning with Structural Information](https://mlsanity.com/paper/2510.16990/) (2025)
- [PyG-SSL: A Graph Self-Supervised Learning Toolkit](https://mlsanity.com/paper/2412.21151/) (2024)
- [Can Graph Neural Networks Learn Language with Extremely Weak Text Supervision?](https://mlsanity.com/paper/2412.08174/) (2024)
- [Breaking Silos: Adaptive Model Fusion Unlocks Better Time Series Forecasting](https://mlsanity.com/paper/2505.18442/) (2025)
- [Scam Detection for Ethereum Smart Contracts: Leveraging Graph Representation Learning for Secure Blockchain](https://mlsanity.com/paper/2412.12370/) (2024)
- [Invariant Link Selector for Spatial-Temporal Out-of-Distribution Problem](https://mlsanity.com/paper/2505.24178/) (2025)
- [Learnable Spatial-Temporal Positional Encoding for Link Prediction](https://mlsanity.com/paper/2506.08309/) (2025)
- [FLeW: Facet-Level and Adaptive Weighted Representation Learning of Scientific Documents](https://mlsanity.com/paper/2509.07531/) (2025)
- [OWLEYE: Zero-Shot Learner for Cross-Domain Graph Data Anomaly Detection](https://mlsanity.com/paper/2601.19102/) (2026)
- [COPF: An Online Framework for Deployment-Stable Counterfactual Fairness in Evolving Graphs](https://mlsanity.com/paper/2606.00700/) (2026)
- [Link prediction on multi-relational graphs from an influence propagation perspective](https://mlsanity.com/paper/2608.05016/) (2026)

## Abstract (arXiv)

Link prediction is a critical problem in graph learning with broad applications such as recommender systems and knowledge graph completion. Numerous research efforts have been directed at solving this problem, including approaches based on similarity metrics and Graph Neural Networks (GNN). However, most existing solutions are still rooted in conventional supervised learning, which makes it challenging to adapt over time to changing customer interests and to address the inherent dilemma of exploitation versus exploration in link prediction. To tackle these challenges, this paper reformulates link prediction as a sequential decision-making process, where each link prediction interaction occurs sequentially. We propose a novel fusion algorithm, PRB (PageRank Bandits), which is the first to combine contextual bandits with PageRank for collaborative exploitation and exploration. We also introduce a new reward formulation and provide a theoretical performance guarantee for PRB. Finally, we extensively evaluate PRB in both online and offline settings, comparing it with bandit-based and graph-based methods. The empirical success of PRB demonstrates the value of the proposed fusion approach. Our code is released at https://github.com/jiaruzouu/PRB.