Online Collaborative Filtering on Graphs
成果类型：
Article
署名作者：
Banerjee, Siddhartha; Sanghavi, Sujay; Shakkottai, Sanjay
署名单位：
Cornell University; University of Texas System; University of Texas Austin
刊物名称：
OPERATIONS RESEARCH
ISSN/ISSBN：
0030-364X
DOI：
10.1287/opre.2016.1508
发表日期：
2016
页码：
756-769
关键词：
摘要：
Existing approaches to designing recommendation systems with user feedback focus on settings where the number of items is small and/or admit some underlying structure. It is unclear, however, if these approaches extend to applications like social network news feeds and content-curation platforms, which have large and unstructured content pools and constraints on user-item recommendations. To this end, we consider the design of recommendation systems in content-rich setting-where the number of items and the number of item-views by users are of a similar order and an access graph constrains which user is allowed to see which item. In this setting, we propose recommendation algorithms that effectively exploit the access graph, and characterize how their performance depends on the graph topology. Our results demonstrate the importance of serendipity in exploration and how recommendation improves when the access graph has higher expansion; they also suggest reasons behind the success of simple algorithms like Twitter's latest-first policy. From a technical perspective, our model presents a framework for studying explore-exploit trade-offs in large-scale settings, with potentially infinite number of items. We present algorithms with competitive-ratio guarantees under both finite-horizon and infinite-horizon settings; conversely, we demonstrate that naive policies can be highly suboptimal and also that in many settings, our results are orderwise optimal.