Online Collaborative Filtering on Graphs

Siddhartha Banerjee (), Sujay Sanghavi () and Sanjay Shakkottai ()
Additional contact information
Siddhartha Banerjee: School of ORIE, Cornell University, Ithaca, New York 14853
Sujay Sanghavi: Department of ECE, The University of Texas at Austin, Austin, Texas 78705
Sanjay Shakkottai: Department of ECE, The University of Texas at Austin, Austin, Texas 78705

Operations Research, 2016, vol. 64, issue 3, 756-769

Abstract: 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.

Keywords: online recommendation; social networks; competitive analysis (search for similar items in EconPapers)
Date: 2016
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (4)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.2016.1508 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:64:y:2016:i:3:p:756-769

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().