mlsanityData to 7 Oct 2026

PageRank Bandits for Link Prediction

arXiv 2411.01410 ↗First posted 3 Nov 2024cs.LG cs.AI cs.SIcited by 14

Not on the map. Why?

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.

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

Builds on

54 of 80 references.

References · 54

  1. 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,282
  2. 2017Inductive Representation Learning on Large Graphscited by 6,284
  3. 2017Neural Message Passing for Quantum Chemistrycited by 3,460
  4. 2018Neural Tangent Kernel: Convergence and Generalization in Neural Networkscited by 2,597
  5. 2020Open Graph Benchmark: Datasets for Machine Learning on Graphscited by 2,148
  6. 2016node2vec: Scalable Feature Learning for Networkscited by 1,913
  7. 2014DeepWalk: Online Learning of Social Representationscited by 1,543
  8. 2016Revisiting Semi-Supervised Learning with Graph Embeddingscited by 970
  9. 2018Link Prediction Based on Graph Neural Networkscited by 829
  10. 2018A Convergence Theory for Deep Learning via Over-Parameterizationcited by 784
  11. 2015LINE: Large-scale Information Network Embeddingcited by 582
  12. 2018Gradient Descent Finds Global Minima of Deep Neural Networkscited by 572
38 more
  1. 2019On Exact Computation with an Infinitely Wide Neural Netcited by 572
  2. 2020Temporal Graph Networks for Deep Learning on Dynamic Graphscited by 521
  3. 2020Inductive Representation Learning on Temporal Graphscited by 454
  4. 2021Neural Bellman-Ford Networks: A General Graph Neural Network Framework for Link Predictioncited by 273
  5. 2015A Review of Relational Machine Learning for Knowledge Graphscited by 264
  6. 2019Generalization Bounds of Stochastic Gradient Descent for Wide and Deep Neural Networkscited by 221
  7. 2021Inductive Representation Learning in Temporal Networks via Causal Anonymous Walkscited by 188
  8. 2013Finite-Time Analysis of Kernelised Contextual Banditscited by 177
  9. 2018Deep Bayesian Bandits Showdown: An Empirical Comparison of Bayesian Deep Networks for Thompson Samplingcited by 166
  10. 2023Towards Better Dynamic Graph Learning: New Architecture and Unified Librarycited by 154
  11. 2020Labeling Trick: A Theory of Using Graph Neural Networks for Multi-Node Representation Learningcited by 148
  12. 2023Do We Really Need Complicated Model Architectures For Temporal Networks?cited by 141
  13. 2022Data Augmentation for Deep Graph Learning: A Surveycited by 132
  14. 2020Neural Thompson Samplingcited by 127
  15. 2019Inductive Matrix Completion Based on Graph Neural Networkscited by 85
  16. 2022Graph Neural Networks for Link Prediction with Subgraph Sketchingcited by 81
  17. 2022Neo-GNNs: Neighborhood Overlap-aware Graph Neural Networks for Link Predictioncited by 78
  18. 2020Neural Contextual Bandits with Deep Representation and Shallow Explorationcited by 71
  19. 2023Neural Common Neighbor with Completion for Link Predictioncited by 64
  20. 2017Ensemble Samplingcited by 62
  21. 2021EE-Net: Exploitation-Exploration Neural Networks in Contextual Banditscited by 43
  22. 2023Alleviating Matthew Effect of Offline Reinforcement Learning in Interactive Recommendationcited by 38
  23. 2023TAP4LLM: Table Provider on Sampling, Augmenting, and Packing Semi-structured Data for Large Language Model Reasoningcited by 32
  24. 2021Local Clustering in Contextual Multi-Armed Banditscited by 29
  25. 2024Heterogeneous Contrastive Learning for Foundation Models and Beyondcited by 27
  26. 2021Neural Active Learning with Performance Guaranteescited by 22
  27. 2021Graph Sanitation with Application to Node Classificationcited by 20
  28. 2021Multi-facet Contextual Bandits: A Neural Network Perspectivecited by 20
  29. 2023Graph Neural Banditscited by 20
  30. 2024BACKTIME: Backdoor Attacks on Multivariate Time Series Forecastingcited by 18
  31. 2022Learning Neural Contextual Bandits Through Perturbed Rewardscited by 17
  32. 2020Generic Outlier Detection in Multi-Armed Banditcited by 14
  33. 2024PromptIntern: Saving Inference Costs by Internalizing Recurrent Prompt during Large Language Model Fine-tuningcited by 13
  34. 2022Improved Algorithms for Neural Active Learningcited by 11
  35. 2023BeMap: Balanced Message Passing for Fair Graph Neural Networkcited by 11
  36. 2024Neural Active Learning Beyond Banditscited by 10
  37. 2022DISCO: Comprehensive and Explainable Disinformation Detectioncited by 9
  38. 2022Neural Bandit with Arm Group Graphcited by 8

50 most cited of 54 All 54 (JSON)

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2024: 3; 2025: 8; 2026: 3.

14 papers.

Sort:

  1. 2025Language in the Flow of Time: Time-Series-Paired Texts Weaved into a Unified Temporal Narrativecited by 35
  2. 2025Transformer Copilot: Learning from The Mistake Log in LLM Fine-tuningcited by 21
  3. 2025Pave Your Own Path: Graph Gradual Domain Adaptation on Fused Gromov-Wasserstein Geodesicscited by 17
  4. 2025Graph4MM: Weaving Multimodal Learning with Structural Informationcited by 17
  5. 2024PyG-SSL: A Graph Self-Supervised Learning Toolkitcited by 14
  6. 2024Can Graph Neural Networks Learn Language with Extremely Weak Text Supervision?cited by 13
  7. 2025Breaking Silos: Adaptive Model Fusion Unlocks Better Time Series Forecastingcited by 12
  8. 2024Scam Detection for Ethereum Smart Contracts: Leveraging Graph Representation Learning for Secure Blockchaincited by 5
  9. 2025Invariant Link Selector for Spatial-Temporal Out-of-Distribution Problemcited by 5
  10. 2025Learnable Spatial-Temporal Positional Encoding for Link Predictioncited by 3
  11. 2025FLeW: Facet-Level and Adaptive Weighted Representation Learning of Scientific Documentscited by 2
  12. 2026OWLEYE: Zero-Shot Learner for Cross-Domain Graph Data Anomaly Detectioncited by 1
2 more
  1. 2026COPF: An Online Framework for Deployment-Stable Counterfactual Fairness in Evolving Graphscited by 0
  2. 2026Link prediction on multi-relational graphs from an influence propagation perspectivecited by 0