Online collaborative filtering on graphs

DOI10.1287/OPRE.2016.1508zbMATH Open1348.68288arXiv1411.2057OpenAlexW2113676952MaRDI QIDQ2830757FDOQ2830757

Authors: Siddhartha Banerjee, Sujay Sanghavi, Sanjay Shakkottai 

Publication date: 31 October 2016

Published in: Operations Research (Search for Journal in Brave)

Abstract: A common phenomena in modern recommendation systems is the use of feedback from one user to infer the `value' of an item to other users. This results in an exploration vs. exploitation trade-off, in which items of possibly low value have to be presented to users in order to ascertain their value. Existing approaches to solving this problem focus on the case where the number of items are small, or admit some underlying structure -- it is unclear, however, if good recommendation is possible when dealing with content-rich settings with unstructured content. We consider this problem under a simple natural model, wherein the number of items and the number of item-views are of the same order, and an `access-graph' constrains which user is allowed to see which item. Our main insight is that the presence of the access-graph in fact makes good recommendation possible -- however this requires the exploration policy to be designed to take advantage of the access-graph. Our results demonstrate the importance of `serendipity' in exploration, and how higher graph-expansion translates to a higher quality of recommendations; it also suggests a reason why in some settings, simple policies like Twitter's `Latest-First' policy achieve a good performance. From a technical perspective, our model presents a way to study exploration-exploitation tradeoffs in settings where the number of `trials' and `strategies' are large (potentially infinite), and more importantly, of the same order. Our algorithms admit competitive-ratio guarantees which hold for the worst-case user, under both finite-population and infinite-horizon settings, and are parametrized in terms of properties of the underlying graph. Conversely, we also demonstrate that improperly-designed policies can be highly sub-optimal, and that in many settings, our results are order-wise optimal.

Full work available at URL: https://arxiv.org/abs/1411.2057

Recommendations

• Improved collaborative filtering
• Improved recommendation systems
• Tailored recommendations
• Collaborative filtering for massive multinomial data
• Recommender systems as mechanisms for social learning

zbMATH Keywords

social networkscompetitive analysisonline recommendation

Mathematics Subject Classification ID

Social networks; opinion dynamics (91D30) Small world graphs, complex networks (graph-theoretic aspects) (05C82) Computing methodologies for information systems (hypertext navigation, interfaces, decision support, etc.) (68U35)

Cites Work

• Matrix completion from noisy entries
• Asymptotically efficient adaptive allocation rules
• Title not available (Why is that?)
• Finite-time analysis of the multiarmed bandit problem
• AdWords and generalized online matching
• Bounds for Certain Multiprocessing Anomalies
• A Knapsack Secretary Problem with Applications
• Regret analysis of stochastic and nonstochastic multi-armed bandit problems
• Competitive weighted matching in transversal matroids
• Inferring Rankings Using Constrained Sensing
• Semi-matchings for bipartite graphs and load balancing
• Faster algorithms for semi-matching problems (extended abstract)
• Regret bounds for sleeping experts and bandits
• Linearly parameterized bandits

Cited In (6)

• Collaborative filtering for massive multinomial data
• Preface to the special issue on information and decisions in social and economic networks
• Recommender systems as mechanisms for social learning
• Big data in humanitarian supply chain management: a review and further research directions
• Reliable graph-based collaborative ranking
• Exploiting Positive and Negative Graded Relevance Assessments for Content Recommendation

This page was built for publication: Online collaborative filtering on graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2830757)