Online Collaborative Filtering on Graphs

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.