Spectral bandits

• URL: http://arxiv.org/abs/2604.25272v1
• Date: Tue, 28 Apr 2026 06:29:27 GMT
• Title: Spectral bandits
• Abstract summary: We study a bandit problem where the payoffs of arms are smooth on a graph.<n>This framework is suitable for solving online learning problems that involve graphs, such as content-based recommendation.
• Score: 39.534255812216784
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Smooth functions on graphs have wide applications in manifold and semi-supervised learning. In this work, we study a bandit problem where the payoffs of arms are smooth on a graph. This framework is suitable for solving online learning problems that involve graphs, such as content-based recommendation. In this problem, each item we can recommend is a node of an undirected graph and its expected rating is similar to the one of its neighbors. The goal is to recommend items that have high expected ratings. We aim for the algorithms where the cumulative regret with respect to the optimal policy would not scale poorly with the number of nodes. In particular, we introduce the notion of an effective dimension, which is small in real-world graphs, and propose three algorithms for solving our problem that scale linearly and sublinearly in this dimension. Our experiments on content recommendation problem show that a good estimator of user preferences for thousands of items can be learned from just tens of node evaluations.

Related papers

• Spectral bandits for smooth graph functions with applications in recommender systems [39.53425581221678]
  We study a bandit problem where the payoffs of arms are smooth on a graph.<n>This framework is suitable for solving online learning problems that involve graphs, such as content-based recommendation.
  arXiv  Detail & Related papers  (2026-05-19T23:07:21Z)
• Revealing graph bandits for maximizing local influence [64.91400609178565]
  We study a graph bandit setting where the objective of the learner is to detect the most influential node of a graph by requesting as little information from the graph as possible.<n>One of the relevant applications for this setting is marketing in social networks, where the marketer aims at finding and taking advantage of the most influential customers.
  arXiv  Detail & Related papers  (2026-05-01T07:54:58Z)
• Spectral bandits for smooth graph functions [41.230043580577174]
  We study a bandit problem where the payoffs of arms are smooth on a graph.<n>This framework is suitable for solving online learning problems that involve graphs, such as content-based recommendation.
  arXiv  Detail & Related papers  (2026-04-20T15:39:22Z)
• Are All Edges Necessary? A Unified Framework for Graph Purification [6.795209119198288]
  Not all edges in a graph are necessary for the training of machine learning models. In this paper, we try to provide a method to drop edges in order to purify the graph data from a new perspective.
  arXiv  Detail & Related papers  (2022-11-09T20:28:25Z)
• Graph Sanitation with Application to Node Classification [41.311131936203715]
  We introduce the graph sanitation problem, to answer an question. By learning a better graph as part of the input of the mining model, it is expected to benefit graph mining in a variety of settings. In particular, it brings up to 25% performance improvement over the existing robust graph neural network methods.
  arXiv  Detail & Related papers  (2021-05-19T20:22:15Z)
• Learnable Graph Matching: Incorporating Graph Partitioning with Deep Feature Learning for Multiple Object Tracking [58.30147362745852]
  Data association across frames is at the core of Multiple Object Tracking (MOT) task. Existing methods mostly ignore the context information among tracklets and intra-frame detections. We propose a novel learnable graph matching method to address these issues.
  arXiv  Detail & Related papers  (2021-03-30T08:58:45Z)
• Evaluating Node Embeddings of Complex Networks [0.0]
  Agood embedding should capture the graph topology, node-to-node relationship, and other relevant information about the graph. The main challenge is that one needs to make sure that embeddings describe the properties of the graphs well. We do a series of experiments with selected graph embedding algorithms, both on real-world networks as well as artificially generated ones.
  arXiv  Detail & Related papers  (2021-02-16T16:55:29Z)
• Line Graph Neural Networks for Link Prediction [71.00689542259052]
  We consider the graph link prediction task, which is a classic graph analytical problem with many real-world applications. In this formalism, a link prediction problem is converted to a graph classification task. We propose to seek a radically different and novel path by making use of the line graphs in graph theory. In particular, each node in a line graph corresponds to a unique edge in the original graph. Therefore, link prediction problems in the original graph can be equivalently solved as a node classification problem in its corresponding line graph, instead of a graph classification task.
  arXiv  Detail & Related papers  (2020-10-20T05:54:31Z)
• Grale: Designing Networks for Graph Learning [68.23038997141381]
  We present Grale, a scalable method we have developed to address the problem of graph design for graphs with billions of nodes. Grale operates by fusing together different measures of(potentially weak) similarity to create a graph which exhibits high task-specific homophily between its nodes. We have deployed Grale in more than 20 different industrial settings at Google, including datasets which have tens of billions of nodes, and hundreds of trillions of potential edges to score.
  arXiv  Detail & Related papers  (2020-07-23T13:25:36Z)
• Online Dense Subgraph Discovery via Blurred-Graph Feedback [87.9850024070244]
  We introduce a novel learning problem for dense subgraph discovery. We first propose a edge-time algorithm that obtains a nearly-optimal solution with high probability. We then design a more scalable algorithm with a theoretical guarantee.
  arXiv  Detail & Related papers  (2020-06-24T11:37:33Z)

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.