Research map / Graph learning / Knowledge and temporal graphs
PageRank Bandits for Link Prediction
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Reformulates link prediction as sequential contextual bandit decisions and proposes PRB, which propagates neural exploitation-exploration scores over the evolving graph via PageRank, with a regret bound and experiments on online and offline link prediction.
Problem
Link prediction is usually treated as conventional supervised learning on a static or chronologically split graph, which adapts poorly to evolving interests and ignores the exploration-exploitation trade-off and theoretical guarantees.
Approach
Combine neural contextual bandits (exploitation network plus gradient-feature exploration network) with PageRank propagation: candidate-node exploitation/exploration scores form the restart vector, and the stationary PageRank vector over the evolving graph is used to select the link target, with each observed link added to the graph.
Key results
- Online link prediction over 10,000 rounds: PRB achieves cumulative regret 1555 on MovieLens and 1455 on AmazonFashion, lower than the best baseline EE-Net (1638 and 1698).
- Offline link prediction: PRB reaches HR@100 of 92.33 on Cora and 84.54 on Pubmed, versus NCNC at 89.65 and 81.29, reported as an average 2.42% gain over NCNC.
- Regret bound is sublinear in T, of order tilde-O(sqrt(d~ k T)) times a complexity term depending on the NTK matrix.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| add PageRank graph propagation and contextual-bandit exploration to bandit-based prediction | PRB · online link prediction | cumulative regret: 1555 $\pm$ 21.7 vs 1638 $\pm$ 15.3; 1455 $\pm$ 18.4 vs 1698 $\pm$ 19.3; 1929 $\pm$ 17.0 vs 2190 $\pm$ 16.3; 3236 $\pm$ 1 | Helped |
| add PageRank graph propagation and contextual-bandit exploration to link prediction | PRB · offline link prediction: Cora, Citeseer, Pubmed, Collab, PPA, DDI | Hits@k: 92.33 $\pm$ 0.57 vs 89.65 $\pm$ 1.36; 95.13 $\pm$ 1.28 vs 93.47 $\pm$ 0.95; 84.54 $\pm$ 0.86 vs 81.29 $\pm$ 0.95; 67.29 | Helped |
| add the exploration network (ablation) | PRB · online link prediction and node classification | cumulative regret: 1555 $\pm$ 21.7 vs 1892 $\pm$ 15.1; 1455 $\pm$ 18.4 vs 1567 $\pm$ 24.6; 1929 $\pm$ 17.0 vs 1994 $\pm$ 23.6; 3236 $\pm$ 1 | Helped |
| add 10% prior edges to the initial graph (ablation) | PRB · online link prediction and node classification | cumulative regret: 1521 $\pm$ 17.6; 1408 $\pm$ 23.5; 1858 $\pm$ 15.7; 3085 $\pm$ 14.3; 1804 $\pm$ 23.5; 2158 $\pm$ 33.1; 1630 $\pm$ 11.5 | Mixed |
Surprising findings
- The paper reports that PRB is more costly at inference than some graph baselines on certain datasets (e.g., PRB 0.58 s on Pubmed vs NCNC 0.07 s), which is not highlighted in the main text.
Limitations
- Only one integration of bandits with PageRank is studied; other random-walk methods or GNNs are not explored.
- Evaluated only on link prediction and node classification; subgraph matching and node clustering are left for future work.
- Regret bound depends on the NTK effective dimension and the value of alpha is treated as prior knowledge.
Experimental setup
Datasets: MovieLens Amazon Fashion Facebook GrQc Cora Citeseer Pubmed ogbl-collab ogbl-ppa ogbl-ddi
Benchmarks: MovieLens Amazon Fashion Facebook GrQc Cora Citeseer Pubmed ogbl-collab ogbl-ppa ogbl-ddi
Metrics: cumulative regret Hits@k
Baselines: Neural Greedy NeuralUCB NeuralTS EE-Net CN AA RA GCN SAGE SEAL NBFNet Neo-GNN
Builds on: NeuralUCB NeuralTS EE-Net PageRank Neural Tangent Kernel
Closest papers by meaning
- Neural Combinatorial Clustered Bandits for Recommendation Systems (AAAI 2025 · similarity 0.84)
- Bandits Meet Mechanism Design to Combat Clickbait in Online Recommendation (ICLR 2024 · similarity 0.84)
- Online Clustering of Dueling Bandits (ICML 2025 · similarity 0.84)
- Revisiting Link Prediction: a data perspective (ICLR 2024 · similarity 0.83)
- Efficient Contextual Bandits with Uninformed Feedback Graphs (ICML 2024 · similarity 0.83)
- Gaussian Process Bandits for Top-k Recommendations (NeurIPS 2024 · similarity 0.83)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.