Generalized Low-Rank Matrix Contextual Bandits with Graph Information

• URL: http://arxiv.org/abs/2507.17528v1
• Date: Wed, 23 Jul 2025 14:07:47 GMT
• Title: Generalized Low-Rank Matrix Contextual Bandits with Graph Information
• Authors: Yao Wang, Jiannan Li, Yue Kang, Shanxing Gao, Zhenxin Xiao,
• Abstract summary: The matrix contextual bandit (CB) is a powerful framework that has been widely applied in sequential decision-making scenarios.<n>In many real-world scenarios, such as online advertising and recommender systems, additional graph information often exists beyond the low-rank structure.<n>We propose a novel matrix CB algorithmic framework that builds upon the classical upper confidence bound (UCB) framework.
• Score: 10.955203089942582
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The matrix contextual bandit (CB), as an extension of the well-known multi-armed bandit, is a powerful framework that has been widely applied in sequential decision-making scenarios involving low-rank structure. In many real-world scenarios, such as online advertising and recommender systems, additional graph information often exists beyond the low-rank structure, that is, the similar relationships among users/items can be naturally captured through the connectivity among nodes in the corresponding graphs. However, existing matrix CB methods fail to explore such graph information, and thereby making them difficult to generate effective decision-making policies. To fill in this void, we propose in this paper a novel matrix CB algorithmic framework that builds upon the classical upper confidence bound (UCB) framework. This new framework can effectively integrate both the low-rank structure and graph information in a unified manner. Specifically, it involves first solving a joint nuclear norm and matrix Laplacian regularization problem, followed by the implementation of a graph-based generalized linear version of the UCB algorithm. Rigorous theoretical analysis demonstrates that our procedure outperforms several popular alternatives in terms of cumulative regret bound, owing to the effective utilization of graph information. A series of synthetic and real-world data experiments are conducted to further illustrate the merits of our procedure.

Related papers

• Contrastive Matrix Completion with Denoising and Augmented Graph Views for Robust Recommendation [1.0128808054306186]
  Matrix completion is a widely adopted framework in recommender systems.<n>We propose a novel method called Matrix Completion using Contrastive Learning (MCCL)<n>Our approach not only improves the numerical accuracy of the predicted scores--but also produces superior rankings with improvements of up to 36% in ranking metrics.
  arXiv  Detail & Related papers  (2025-06-12T12:47:35Z)
• Online Clustering of Dueling Bandits [59.09590979404303]
  We introduce the first "clustering of dueling bandit algorithms" to enable collaborative decision-making based on preference feedback.<n>We propose two novel algorithms: (1) Clustering of Linear Dueling Bandits (COLDB) which models the user reward functions as linear functions of the context vectors, and (2) Clustering of Neural Dueling Bandits (CONDB) which uses a neural network to model complex, non-linear user reward functions.
  arXiv  Detail & Related papers  (2025-02-04T07:55:41Z)
• A Unified Regularization Approach to High-Dimensional Generalized Tensor Bandits [16.06016915165857]
  Decision-making scenarios often involve data that is both high-dimensional and rich in contextual information.<n>We propose a generalized linear tensor bandits algorithm designed to tackle these challenges.<n>Our framework not only provides better bounds but also has a broader applicability.
  arXiv  Detail & Related papers  (2025-01-18T10:46:12Z)
• Demystifying Online Clustering of Bandits: Enhanced Exploration Under Stochastic and Smoothed Adversarial Contexts [27.62165569135504]
  A line of research, known as online clustering of bandits, extends contextual MAB by grouping similar users into clusters.<n>Existing algorithms, which rely on the upper confidence bound (UCB) strategy, struggle to gather adequate statistical information to accurately identify unknown user clusters.<n>We propose two novel algorithms, UniCLUB and PhaseUniCLUB, which incorporate enhanced exploration mechanisms to accelerate cluster identification.
  arXiv  Detail & Related papers  (2025-01-01T16:38:29Z)
• Learning to Model Graph Structural Information on MLPs via Graph Structure Self-Contrasting [50.181824673039436]
  We propose a Graph Structure Self-Contrasting (GSSC) framework that learns graph structural information without message passing. The proposed framework is based purely on Multi-Layer Perceptrons (MLPs), where the structural information is only implicitly incorporated as prior knowledge. It first applies structural sparsification to remove potentially uninformative or noisy edges in the neighborhood, and then performs structural self-contrasting in the sparsified neighborhood to learn robust node representations.
  arXiv  Detail & Related papers  (2024-09-09T12:56:02Z)
• A Clustering Method with Graph Maximum Decoding Information [6.11503045313947]
  We present a novel clustering method for maximizing decoding information within graph-based models, named CMDI.<n> CMDI incorporates two-dimensional structural information theory into the clustering process, consisting of two phases: graph structure extraction and graph partitioning.<n> Empirical evaluations on three real-world datasets demonstrate that CMDI outperforms classical baseline methods, exhibiting a superior decoding information ratio (DI-R)<n>These findings underscore the effectiveness of CMDI in enhancing decoding information quality and computational efficiency, positioning it as a valuable tool in graph-based clustering analyses.
  arXiv  Detail & Related papers  (2024-03-18T05:18:19Z)
• T-GAE: Transferable Graph Autoencoder for Network Alignment [79.89704126746204]
  T-GAE is a graph autoencoder framework that leverages transferability and stability of GNNs to achieve efficient network alignment without retraining. Our experiments demonstrate that T-GAE outperforms the state-of-the-art optimization method and the best GNN approach by up to 38.7% and 50.8%, respectively.
  arXiv  Detail & Related papers  (2023-10-05T02:58:29Z)
• EGRC-Net: Embedding-induced Graph Refinement Clustering Network [66.44293190793294]
  We propose a novel graph clustering network called Embedding-Induced Graph Refinement Clustering Network (EGRC-Net) EGRC-Net effectively utilizes the learned embedding to adaptively refine the initial graph and enhance the clustering performance. Our proposed methods consistently outperform several state-of-the-art approaches.
  arXiv  Detail & Related papers  (2022-11-19T09:08:43Z)
• Optimal Propagation for Graph Neural Networks [51.08426265813481]
  We propose a bi-level optimization approach for learning the optimal graph structure. We also explore a low-rank approximation model for further reducing the time complexity.
  arXiv  Detail & Related papers  (2022-05-06T03:37:00Z)
• Matrix Completion with Hierarchical Graph Side Information [39.00971122472004]
  We consider a matrix completion problem that exploits social or item similarity graphs as side information. We develop a universal, parameter-free, and computationally efficient algorithm that starts with hierarchical graph clustering. We conduct extensive experiments on synthetic and real-world datasets to corroborate our theoretical results.
  arXiv  Detail & Related papers  (2022-01-02T03:47:41Z)
• A Robust and Generalized Framework for Adversarial Graph Embedding [73.37228022428663]
  We propose a robust framework for adversarial graph embedding, named AGE. AGE generates the fake neighbor nodes as the enhanced negative samples from the implicit distribution. Based on this framework, we propose three models to handle three types of graph data.
  arXiv  Detail & Related papers  (2021-05-22T07:05:48Z)
• Probabilistic Case-based Reasoning for Open-World Knowledge Graph Completion [59.549664231655726]
  A case-based reasoning (CBR) system solves a new problem by retrieving cases' that are similar to the given problem. In this paper, we demonstrate that such a system is achievable for reasoning in knowledge-bases (KBs) Our approach predicts attributes for an entity by gathering reasoning paths from similar entities in the KB.
  arXiv  Detail & Related papers  (2020-10-07T17:48:12Z)
• Semi-Supervised Learning with Meta-Gradient [123.26748223837802]
  We propose a simple yet effective meta-learning algorithm in semi-supervised learning. We find that the proposed algorithm performs favorably against state-of-the-art methods.
  arXiv  Detail & Related papers  (2020-07-08T08:48:56Z)

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.