PageRank Bandits for Link Prediction

• URL: http://arxiv.org/abs/2411.01410v1
• Date: Sun, 03 Nov 2024 02:39:28 GMT
• Title: PageRank Bandits for Link Prediction
• Authors: Yikun Ban, Jiaru Zou, Zihao Li, Yunzhe Qi, Dongqi Fu, Jian Kang, Hanghang Tong, Jingrui He,
• Abstract summary: Link prediction is a critical problem in graph learning with broad applications such as recommender systems and knowledge graph completion. 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.
• Score: 72.61386754332776
• License:
• Abstract: 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.

Related papers

• Improving rule mining via embedding-based link prediction [2.422410293747519]
  Rule mining on knowledge graphs allows for explainable link prediction. Several approaches combining the two families have been proposed in recent years. We propose a new way to combine the two families of approaches.
  arXiv  Detail & Related papers  (2024-06-14T15:53:30Z)
• Probabilistic Demand Forecasting with Graph Neural Networks [0.0]
  This paper builds on previous research on Graph Neural Networks (GNNs) and makes two contributions. First, we integrate a GNN encoder into a state-of-the-art DeepAR model. The combined model produces probabilistic forecasts, which are crucial for decision-making under uncertainty. Second, we propose to build graphs using article similarity, which avoids reliance on a pre-defined graph structure. Experiments on three real-world datasets show that the proposed approach consistently outperforms non-graph benchmarks.
  arXiv  Detail & Related papers  (2024-01-23T21:20:48Z)
• Variational Disentangled Graph Auto-Encoders for Link Prediction [10.390861526194662]
  This paper proposes a novel framework with two variants, the disentangled graph auto-encoder (DGAE) and the variational disentangled graph auto-encoder (VDGAE) The proposed framework infers the latent factors that cause edges in the graph and disentangles the representation into multiple channels corresponding to unique latent factors.
  arXiv  Detail & Related papers  (2023-06-20T06:25:05Z)
• Drop Edges and Adapt: a Fairness Enforcing Fine-tuning for Graph Neural Networks [9.362130313618797]
  Link prediction algorithms tend to disfavor the links between individuals in specific demographic groups. This paper proposes a novel way to enforce fairness on graph neural networks with a fine-tuning strategy. One novelty of DEA is that we can use a discrete yet learnable adjacency matrix in our fine-tuning.
  arXiv  Detail & Related papers  (2023-02-22T16:28:08Z)
• Large-Scale Sequential Learning for Recommender and Engineering Systems [91.3755431537592]
  In this thesis, we focus on the design of an automatic algorithms that provide personalized ranking by adapting to the current conditions. For the former, we propose novel algorithm called SAROS that take into account both kinds of feedback for learning over the sequence of interactions. The proposed idea of taking into account the neighbour lines shows statistically significant results in comparison with the initial approach for faults detection in power grid.
  arXiv  Detail & Related papers  (2022-05-13T21:09:41Z)
• GNNRank: Learning Global Rankings from Pairwise Comparisons via Directed Graph Neural Networks [68.61934077627085]
  We introduce GNNRank, a modeling framework compatible with any GNN capable of learning digraph embeddings. We show that our methods attain competitive and often superior performance compared with existing approaches.
  arXiv  Detail & Related papers  (2022-02-01T04:19:50Z)
• Deep Probabilistic Graph Matching [72.6690550634166]
  We propose a deep learning-based graph matching framework that works for the original QAP without compromising on the matching constraints. The proposed method is evaluated on three popularly tested benchmarks (Pascal VOC, Willow Object and SPair-71k) and it outperforms all previous state-of-the-arts on all benchmarks.
  arXiv  Detail & Related papers  (2022-01-05T13:37:27Z)
• Robustification of Online Graph Exploration Methods [59.50307752165016]
  We study a learning-augmented variant of the classical, notoriously hard online graph exploration problem. We propose an algorithm that naturally integrates predictions into the well-known Nearest Neighbor (NN) algorithm.
  arXiv  Detail & Related papers  (2021-12-10T10:02:31Z)
• Latent Bandits Revisited [55.88616813182679]
  A latent bandit problem is one in which the learning agent knows the arm reward distributions conditioned on an unknown discrete latent state. We propose general algorithms for this setting, based on both upper confidence bounds (UCBs) and Thompson sampling. We provide a unified theoretical analysis of our algorithms, which have lower regret than classic bandit policies when the number of latent states is smaller than actions.
  arXiv  Detail & Related papers  (2020-06-15T19:24:02Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.