Spectral bandits for smooth graph functions with applications in recommender systems

• URL: http://arxiv.org/abs/2605.20552v1
• Date: Tue, 19 May 2026 23:07:21 GMT
• Title: Spectral bandits for smooth graph functions with applications in recommender systems
• 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.53425581221678
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Smooth functions on graphs have wide applications in manifold and semi-supervised learning. In this paper, 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 recommended item is a node and its expected rating is similar to its neighbors. The goal is to recommend items that have high expected ratings. We aim for the algorithms where the cumulative regret 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 two algorithms for solving our problem that scale linearly in this dimension. Our experiments on real-world content recommendation problem show that a good estimator of user preferences for thousands of items can be learned from just tens nodes evaluations.

Related papers

• 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 [39.534255812216784]
  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-28T06:29:27Z)
• 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)
• Learning Heuristics for the Maximum Clique Enumeration Problem Using Low Dimensional Representations [0.0]
  We use a learning framework for a pruning process of the input graph towards reducing the clique of the maximum enumeration problem. We study the role of using different vertex representations on the performance of this runtime method. We observe that using local graph features in the classification process produce more accurate results when combined with a feature elimination process.
  arXiv  Detail & Related papers  (2022-10-30T22:04:32Z)
• 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)
• 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)
• 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.