Backbone-Based Neighbor Transferring Proximity Graph for Fast Inner Product Retrieval

Modern recommender systems usually rely on inner product search to find relevant items. The inner product inherently considers both the norm and direction of vectors, which naturally aligns well with purchasing behavior. Unlike the metric space, the inner product space does not follow the triangle inequality and the identity of indiscernibles. This makes search in the inner product space more challenging as the neighbor transferring is not as stable as metric space, which directly affects the connectivity and efficiency of graph-based methods. Existing representative methods, including ip-nsw and its successors, are insert-based graph construction algorithms. These insert-based algorithms build the edges between non-candidate points which makes them unsuitable for maximum inner product search (MIPS). In this paper, we analyze neighbor transferring in the inner product space and find that normalized points can improve the efficiency of neighbor transferring. Based on this idea, we propose a new inner product search method that has the following advantages: (i) It constructs a highly accurate proximity graph that can help the inner product search and reduce the index size to a minimum of 1%. (ii) Good efficiency: Our algorithm is about 20% faster than other competitors with the same recall. (iii) Stable accuracy: Our algorithm can achieve good accuracy on different datasets and settings. Experiment results on different datasets demonstrate that our algorithm constantly and significantly outperforms other state-of-the-art algorithms. These advantages can significantly improve current recommender systems.