{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,11]],"date-time":"2026-01-11T04:43:50Z","timestamp":1768106630736,"version":"3.49.0"},"reference-count":66,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2023,1,10]],"date-time":"2023-01-10T00:00:00Z","timestamp":1673308800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100012166","name":"National Key R&D Program of China","doi-asserted-by":"crossref","award":["2020AAA0103800"],"award-info":[{"award-number":["2020AAA0103800"]}],"id":[{"id":"10.13039\/501100012166","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"crossref","award":["61976198 and 62022077"],"award-info":[{"award-number":["61976198 and 62022077"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100012226","name":"Fundamental Research Funds for the Central Universities","doi-asserted-by":"crossref","award":["WK2150110017"],"award-info":[{"award-number":["WK2150110017"]}],"id":[{"id":"10.13039\/501100012226","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Inf. Syst."],"published-print":{"date-parts":[[2023,1,31]]},"abstract":"<jats:p>We focus on Maximum Inner Product Search (MIPS), which is an essential problem in many machine learning communities. Given a query, MIPS finds the most similar items with the maximum inner products. Methods for Nearest Neighbor Search (NNS) which is usually defined on metric space do not exhibit the satisfactory performance for MIPS problem since inner product is a non-metric function. However, inner products exhibit many good properties compared with metric functions, such as avoiding vanishing and exploding gradients. As a result, inner product is widely used in many recommendation systems, which makes efficient Maximum Inner Product Search a key for speeding up many recommendation systems.<\/jats:p>\n          <jats:p>Graph-based methods for NNS problem show the superiorities compared with other class methods. Each data point of the database is mapped to a node of the proximity graph. Nearest neighbor search in the database can be converted to route on the proximity graph to find the nearest neighbor for the query. This technique can be used to solve MIPS problem. Instead of searching the nearest neighbor for the query, we search the item with a maximum inner product with query on the proximity graph. In this article, we propose a reinforcement model to train an agent to search on the proximity graph automatically for MIPS problem if we lack the ground truths of training queries. If we know the ground truths of some training queries, our model can also utilize these ground truths by imitation learning to improve the agent\u2019s searchability. By experiments, we can see that our proposed mode which combines reinforcement learning with imitation learning shows the superiorities over the state-of-the-art methods.<\/jats:p>","DOI":"10.1145\/3512767","type":"journal-article","created":{"date-parts":[[2022,2,14]],"date-time":"2022-02-14T20:19:19Z","timestamp":1644869959000},"page":"1-27","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":13,"title":["Reinforcement Routing on Proximity Graph for Efficient Recommendation"],"prefix":"10.1145","volume":"41","author":[{"given":"Chao","family":"Feng","sequence":"first","affiliation":[{"name":"University of Science and Technology of China, Hefei, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Defu","family":"Lian","sequence":"additional","affiliation":[{"name":"University of Science and Technology of China, Hefei, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xiting","family":"Wang","sequence":"additional","affiliation":[{"name":"Microsoft Research Asia, Beijing, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Zheng","family":"Liu","sequence":"additional","affiliation":[{"name":"Microsoft Research Asia, Beijing, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xing","family":"Xie","sequence":"additional","affiliation":[{"name":"Microsoft Research Asia, Beijing, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Enhong","family":"Chen","sequence":"additional","affiliation":[{"name":"University of Science and Technology of China, Hefei, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2023,1,10]]},"reference":[{"key":"e_1_3_2_2_2","article-title":"Layer normalization","author":"Ba Jimmy Lei","year":"2016","unstructured":"Jimmy Lei Ba, Jamie Ryan Kiros, and Geoffrey E. Hinton. 2016. Layer normalization. arXiv:1607.06450. Retrieved from https:\/\/arxiv.org\/abs\/1607.06450.","journal-title":"arXiv:1607.06450."},{"key":"e_1_3_2_3_2","first-page":"931","volume-title":"Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition","author":"Babenko Artem","year":"2014","unstructured":"Artem Babenko and Victor Lempitsky. 2014. Additive quantization for extreme vector compression. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition. 931\u2013938."},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.1145\/2645710.2645741"},{"key":"e_1_3_2_5_2","first-page":"475","volume-title":"Proceedings of the International Conference on Machine Learning","author":"Baranchuk Dmitry","year":"2019","unstructured":"Dmitry Baranchuk, Dmitry Persiyanov, Anton Sinitsin, and Artem Babenko. 2019. Learning to route in similarity graphs. In Proceedings of the International Conference on Machine Learning. 475\u2013484."},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.5555\/944919.944966"},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.1145\/361002.361007"},{"issue":"4","key":"e_1_3_2_8_2","doi-asserted-by":"crossref","first-page":"333","DOI":"10.1109\/TSE.1979.234200","article-title":"Multidimensional binary search trees in database applications","author":"Bentley Jon Louis","year":"1979","unstructured":"Jon Louis Bentley. 1979. Multidimensional binary search trees in database applications. IEEE Transactions on Software Engineering SE-5, 4 (1979), 333\u2013340.","journal-title":"IEEE Transactions on Software Engineering"},{"key":"e_1_3_2_9_2","article-title":"Hierarchical memory networks","author":"Chandar Sarath","year":"2016","unstructured":"Sarath Chandar, Sungjin Ahn, Hugo Larochelle, Pascal Vincent, Gerald Tesauro, and Yoshua Bengio. 2016. Hierarchical memory networks. arXiv:1605.07427. Retrieved from https:\/\/arxiv.org\/abs\/1605.07427.","journal-title":"arXiv:1605.07427."},{"key":"e_1_3_2_10_2","first-page":"2058","volume-title":"Proceedings of the International Conference on Machine Learning","author":"Chang Kai-Wei","year":"2015","unstructured":"Kai-Wei Chang, Akshay Krishnamurthy, Alekh Agarwal, Hal Daume, and John Langford. 2015. Learning to search better than your teacher. In Proceedings of the International Conference on Machine Learning. PMLR, 2058\u20132066."},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","DOI":"10.1145\/3331184.3331196"},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.1145\/3411754"},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.1109\/TIP.2017.2668218"},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-014-9885-5"},{"key":"e_1_3_2_15_2","doi-asserted-by":"publisher","DOI":"10.1109\/CVPR.2013.237"},{"key":"e_1_3_2_16_2","unstructured":"Mohamad Dolatshah Ali Hadian and Behrouz Minaei-Bidgoli. 2015. Ball*-tree: Efficient spatial indexing for constrained nearest-neighbor search in metric spaces. arXiv:1511.00628. Retrieved from https:\/\/arxiv.org\/abs\/1511.00628."},{"key":"e_1_3_2_17_2","unstructured":"Chao Du and Jingdong Wang. 2014. Inner product similarity search using compositional codes.  arXiv:1406.4966. Retrieved from https:\/\/arxiv.org\/abs\/1406.4966."},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.1145\/355744.355745"},{"key":"e_1_3_2_19_2","doi-asserted-by":"publisher","DOI":"10.1109\/CVPR.2013.379"},{"key":"e_1_3_2_20_2","volume-title":"Vector Quantization and Signal Compression","author":"Gersho Allen","year":"2012","unstructured":"Allen Gersho and Robert M. Gray. 2012. Vector Quantization and Signal Compression, Vol. 159. Springer Science & Business Media."},{"key":"e_1_3_2_21_2","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2012.193"},{"key":"e_1_3_2_22_2","doi-asserted-by":"publisher","DOI":"10.1109\/MASSP.1984.1162229"},{"key":"e_1_3_2_23_2","first-page":"482","volume-title":"Proceedings of the Artificial Intelligence and Statistics","author":"Guo Ruiqi","year":"2016","unstructured":"Ruiqi Guo, Sanjiv Kumar, Krzysztof Choromanski, and David Simcha. 2016. Quantization based fast inner product search. In Proceedings of the Artificial Intelligence and Statistics. PMLR, 482\u2013490."},{"key":"e_1_3_2_24_2","first-page":"3887","volume-title":"Proceedings of the International Conference on Machine Learning","author":"Guo Ruiqi","year":"2020","unstructured":"Ruiqi Guo, Philip Sun, Erik Lindgren, Quan Geng, David Simcha, Felix Chern, and Sanjiv Kumar. 2020. Accelerating large-scale inference with anisotropic vector quantization. In Proceedings of the International Conference on Machine Learning. PMLR, 3887\u20133896."},{"key":"e_1_3_2_25_2","doi-asserted-by":"publisher","DOI":"10.1109\/CVPR.2016.90"},{"key":"e_1_3_2_26_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2008.22"},{"key":"e_1_3_2_27_2","doi-asserted-by":"publisher","DOI":"10.1145\/3219819.3219971"},{"key":"e_1_3_2_28_2","doi-asserted-by":"publisher","DOI":"10.1109\/CVPR.2009.5206651"},{"key":"e_1_3_2_29_2","first-page":"2321","volume-title":"Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition","author":"Kalantidis Yannis","year":"2014","unstructured":"Yannis Kalantidis and Yannis Avrithis. 2014. Locally optimized product quantization for approximate nearest neighbor search. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition. 2321\u20132328."},{"issue":"6","key":"e_1_3_2_30_2","doi-asserted-by":"crossref","first-page":"1069","DOI":"10.1007\/s10994-018-5711-7","article-title":"Improved maximum inner product search with better theoretical guarantee using randomized partition trees","volume":"107","author":"Keivani Omid","year":"2018","unstructured":"Omid Keivani, Kaushik Sinha, and Parikshit Ram. 2018. Improved maximum inner product search with better theoretical guarantee using randomized partition trees. Machine Learning 107, 6 (2018), 1069\u20131094.","journal-title":"Machine Learning"},{"key":"e_1_3_2_31_2","volume-title":"Proceedings of the 3rd International Conference on Learning Representations","author":"Kingma Diederik P.","year":"2015","unstructured":"Diederik P. Kingma and Jimmy Ba. 2015. Adam: A method for stochastic optimization. In Proceedings of the 3rd International Conference on Learning Representations. Yoshua Bengio and Yann LeCun (Eds.). http:\/\/arxiv.org\/abs\/1412.6980."},{"key":"e_1_3_2_32_2","unstructured":"Thomas N. Kipf and Max Welling. 2016. Semi-supervised classification with graph convolutional networks. In 5th International Conference on Learning Representations ICLR 2017 Toulon France April 24-26 2017 Conference Track . OpenReview.net."},{"key":"e_1_3_2_33_2","doi-asserted-by":"publisher","DOI":"10.1145\/2396761.2396831"},{"key":"e_1_3_2_34_2","doi-asserted-by":"publisher","DOI":"10.1145\/2396761.2396831"},{"key":"e_1_3_2_35_2","doi-asserted-by":"publisher","DOI":"10.1109\/MC.2009.263"},{"key":"e_1_3_2_36_2","doi-asserted-by":"publisher","DOI":"10.1145\/3035918.3064009"},{"key":"e_1_3_2_37_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10994-021-05962-3"},{"key":"e_1_3_2_38_2","doi-asserted-by":"publisher","DOI":"10.1145\/3366423.3380187"},{"key":"e_1_3_2_39_2","doi-asserted-by":"publisher","DOI":"10.1145\/3366423.3380151"},{"key":"e_1_3_2_40_2","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2019.2951386"},{"key":"e_1_3_2_41_2","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2020.2964232"},{"key":"e_1_3_2_42_2","doi-asserted-by":"publisher","DOI":"10.1145\/3447548.3467315"},{"key":"e_1_3_2_43_2","doi-asserted-by":"publisher","DOI":"10.1145\/3447548.3467441"},{"key":"e_1_3_2_44_2","doi-asserted-by":"publisher","DOI":"10.1109\/WACV.2007.18"},{"key":"e_1_3_2_45_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.is.2013.10.006"},{"key":"e_1_3_2_46_2","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2018.2889473"},{"key":"e_1_3_2_47_2","first-page":"4721","volume-title":"Proceedings of the Advances in Neural Information Processing Systems","author":"Morozov Stanislav","year":"2018","unstructured":"Stanislav Morozov and Artem Babenko. 2018. Non-metric similarity graphs for maximum inner product search. In Proceedings of the Advances in Neural Information Processing Systems. 4721\u20134730."},{"key":"e_1_3_2_48_2","doi-asserted-by":"publisher","DOI":"10.1109\/SPIRE.1999.796589"},{"key":"e_1_3_2_49_2","first-page":"10652","volume-title":"Proceedings of the Advances in Neural Information Processing Systems","author":"Negrinho Renato","year":"2018","unstructured":"Renato Negrinho, Matthew Gormley, and Geoffrey J. Gordon. 2018. Learning beam search policies via imitation learning. In Proceedings of the Advances in Neural Information Processing Systems. 10652\u201310661."},{"key":"e_1_3_2_50_2","first-page":"1926","volume-title":"Proceedings of the International Conference on Machine Learning","author":"Neyshabur Behnam","year":"2015","unstructured":"Behnam Neyshabur and Nathan Srebro. 2015. On symmetric and asymmetric lshs for inner product search. In Proceedings of the International Conference on Machine Learning. PMLR, 1926\u20131934."},{"key":"e_1_3_2_51_2","doi-asserted-by":"publisher","DOI":"10.5555\/3045118.3045323"},{"key":"e_1_3_2_52_2","first-page":"278","volume-title":"Proceedings of the ICML","volume":"99","author":"Ng Andrew Y.","year":"1999","unstructured":"Andrew Y. Ng, Daishi Harada, and Stuart Russell. 1999. Policy invariance under reward transformations: Theory and application to reward shaping. In Proceedings of the ICML, Vol. 99. 278\u2013287."},{"key":"e_1_3_2_53_2","volume-title":"Five Balltree Construction Algorithms","author":"Omohundro Stephen M.","year":"1989","unstructured":"Stephen M. Omohundro. 1989. Five Balltree Construction Algorithms. International Computer Science Institute Berkeley."},{"key":"e_1_3_2_54_2","doi-asserted-by":"publisher","DOI":"10.1145\/2339530.2339677"},{"key":"e_1_3_2_55_2","volume-title":"Proceedings of the Advances in Neural Information Processing Systems","volume":"27","author":"Shrivastava Anshumali","year":"2014","unstructured":"Anshumali Shrivastava and Ping Li. 2014. Asymmetric LSH (ALSH) for sublinear time maximum inner product search (MIPS). In Proceedings of the Advances in Neural Information Processing Systems, Z. Ghahramani, M. Welling, C. Cortes, N. Lawrence, and K. Q. Weinberger (Eds.), Vol. 27. Curran Associates, Inc. Retrieved from https:\/\/proceedings.neurips.cc\/paper\/2014\/file\/310ce61c90f3a46e340ee8257bc70e93-Paper.pdf."},{"key":"e_1_3_2_56_2","first-page":"812","volume-title":"Proceedings of the 31st Conference on Uncertainty in Artificial Intelligence","author":"Shrivastava Anshumali","year":"2015","unstructured":"Anshumali Shrivastava and Ping Li. 2015. Improved asymmetric locality sensitive hashing (ALSH) for maximum inner product search (MIPS). In Proceedings of the 31st Conference on Uncertainty in Artificial Intelligence (Amsterdam, Netherlands). AUAI Press, Arlington, Virginia, 812\u2013821."},{"key":"e_1_3_2_57_2","doi-asserted-by":"publisher","DOI":"10.5555\/2976040.2976207"},{"key":"e_1_3_2_58_2","doi-asserted-by":"publisher","DOI":"10.1145\/2043932.2043987"},{"key":"e_1_3_2_59_2","first-page":"5239","volume-title":"Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and 9th International Joint Conference on Natural Language Processing","author":"Tan Shulong","year":"2019","unstructured":"Shulong Tan, Zhixin Zhou, Zhaozhuo Xu, and Ping Li. 2019. On efficient retrieval of top similarity vectors. In Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and 9th International Joint Conference on Natural Language Processing. 5239\u20135249."},{"key":"e_1_3_2_60_2","article-title":"Preparata, F. P., M. I. shamos: Computaional geometry. An introduction. springer-verlag, new york - berlin - heidelberg - tokyo 1985, xii, 390 pp., 231 Figs., DM 148.-","year":"1987","unstructured":"Th. and Fischer. 1987. Preparata, F. P., M. I. shamos: Computaional geometry. An introduction. springer-verlag, new york - berlin - heidelberg - tokyo 1985, xii, 390 pp., 231 Figs., DM 148.-. Biometrical Journal (1987).","journal-title":"Biometrical Journal"},{"key":"e_1_3_2_61_2","first-page":"5998","volume-title":"Proceedings of the Advances in Neural Information Processing Systems","author":"Vaswani Ashish","year":"2017","unstructured":"Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, \u0141ukasz Kaiser, and Illia Polosukhin. 2017. Attention is all you need. In Proceedings of the Advances in Neural Information Processing Systems. 5998\u20136008."},{"key":"e_1_3_2_62_2","volume-title":"Proceedings of the Web Conference","author":"Wang Xiting","year":"2022","unstructured":"Xiting Wang, Kunpeng Liu, Dongjie Wang, Le Wu, Yanjie Fu, and Xing Xie. 2022. Multi-level recommendation reasoning over knowledge graphs with reinforcement learning. In Proceedings of the Web Conference."},{"key":"e_1_3_2_63_2","doi-asserted-by":"publisher","DOI":"10.1145\/3408317"},{"key":"e_1_3_2_64_2","doi-asserted-by":"publisher","DOI":"10.5555\/3295222.3295325"},{"key":"e_1_3_2_65_2","first-page":"3203","volume-title":"Proceedings of the IJCAI","volume":"17","author":"Xue Hong-Jian","year":"2017","unstructured":"Hong-Jian Xue, Xinyu Dai, Jianbing Zhang, Shujian Huang, and Jiajun Chen. 2017. Deep matrix factorization models for recommender systems. In Proceedings of the IJCAI, Vol. 17. Melbourne, Australia, 3203\u20133209."},{"key":"e_1_3_2_66_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.aiopen.2021.01.001"},{"key":"e_1_3_2_67_2","first-page":"8218","volume-title":"Proceedings of the Advances in Neural Information Processing Systems","author":"Zhou Zhixin","year":"2019","unstructured":"Zhixin Zhou, Shulong Tan, Zhaozhuo Xu, and Ping Li. 2019. M\u00f6bius transformation for fast inner product search on graph. In Proceedings of the Advances in Neural Information Processing Systems. 8218\u20138229."}],"container-title":["ACM Transactions on Information Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3512767","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3512767","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T18:09:29Z","timestamp":1750183769000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3512767"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,1,10]]},"references-count":66,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2023,1,31]]}},"alternative-id":["10.1145\/3512767"],"URL":"https:\/\/doi.org\/10.1145\/3512767","relation":{},"ISSN":["1046-8188","1558-2868"],"issn-type":[{"value":"1046-8188","type":"print"},{"value":"1558-2868","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,1,10]]},"assertion":[{"value":"2021-06-16","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-01-19","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-01-10","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}