Efficient algorithms speed up recommending similar items in huge networks
Efficient Swing Computation for Retrieval in Large-Scale Recommender Systems
Information Retrieval
Summary
Finding items similar to a given item in networks with billions of interactions is usually very slow or inaccurate. The authors propose two new algorithms, ASC and K-ASC, that quickly estimate item similarities with some error guarantees. These methods combine smart random sampling techniques and special filtering to handle both common and rare items efficiently. Tests show these algorithms are much faster than previous ones while keeping similar quality, even on enormous datasets with billions of edges.
What this means in practice
- •For recommendation system engineers: Reduce computation time for item similarity searches in massive recommender system graphs without sacrificing accuracy.
- •For online retail platform developers: Enable faster real-time personalized item recommendations on platforms with billions of user interactions by using scalable approximate algorithms.$Commercial implications: Improves product recommendation speed and quality for e-commerce platforms, enhancing customer experience and engagement.
Authors
Runhao Jiang, Renchi Yang
Abstract
Given a user-item graph $G$, a query item $v_q$ and a target item $v_t$, the Swing score $sw(v_q, v_t)$ of the item pair $(v_q, v_t)$ leverages the user-item-user interaction structure to evaluate their similarity. This measure is found to be highly effective in item-to-item (i2i) retrieval task and finds extensive applications in industrial-scale recommender systems. However, existing solutions towards computing Swing scores are either prohibitively expensive due to their quadratic time complexity w.r.t. the item degree, or rely on truncation heuristics that yield unsatisfactory quality, rendering them impractical particularly on graphs with billions of interactions. In this paper, we present ASC and $K$-ASC, two novel and efficient algorithms for approximate and top-$K$ Swing queries, to address the aforementioned limitations. Specifically, these algorithms provide rigorous theoretical guarantees in probabilistic relative and additive errors of Swing values. The basic idea of ASC is to combine two randomized algorithms, GNS and USS, in a simple yet non-trivial way to adaptively process high- and low-degree query items with minimal runtime cost. In particular, $K$-ASC offers practical efficiency and effectiveness for top-$K$ queries through a filter-refinement paradigm with carefully-designed heuristics. Extensive experiments over eight real datasets demonstrate that ASC and $K$-ASC can achieve orders of magnitude speed-up over competitors in terms of computational time while offering the same approximate and top-$K$ query result quality, and in particular, $K$-ASC is highly efficient on massive graphs including the billion-edge Yambda and MAG datasets.