Optimizing Reachability in Graph-Based Recommender Systems

While accuracy has long been prioritized as the primary metric for Recommender Systems (RSs), it is increasingly accepted that the system’s overall quality is not solely determined by this factor. Reachability, the ease with which users can navigate the whole content catalog through recommendations, emerges as a pivotal yet under-explored concept: not only it ensures a smooth experience for users, but it also provides more equitable exposure for the items, avoiding that only a small fraction of popular items get the bulk of the attention. Despite its importance, the few existing studies analyze reachability without attempting a proper optimization. In this article, we study the problem of optimizing the overall reachability of a RS while maintaining high-quality recommendations. We model a user browsing session as a random walk on a recommendation graph, where the links and the transition probabilities are defined based on the relevance score of the recommendation list that the user gets at every step. In this setting, reachability is modeled as the expected length of a path to reach a given item. We introduce two optimization problems, one discrete and one continuous, and characterize their theoretical properties. We then devise two algorithms that outperform non-trivial baseline methods in enhancing reachability while maintaining a high Normalized Discounted Cumulative Gain (nDCG) score. Our experimental results show that, in some settings, our methods are able to improve the reachability metric by 80% while only compromising nDCG by 5%. Moreover, our empirical analysis shows that optimizing for reachability provides positive effects also on other prevalent “beyond-accuracy” metrics.