skip to main content
10.1145/3626772.3657916acmconferencesArticle/Chapter ViewAbstractPublication PagesirConference Proceedingsconference-collections
short-paper
Open access

Turbo-CF: Matrix Decomposition-Free Graph Filtering for Fast Recommendation

Published: 11 July 2024 Publication History

Abstract

A series of graph filtering (GF) -based collaborative filtering (CF) showcases state-of-the-art performance on the recommendation accuracy by using a low-pass filter (LPF) without a training process. However, conventional GF-based CF approaches mostly perform matrix decomposition on the item-item similarity graph to realize the ideal LPF, which results in a non-trivial computational cost and thus makes them less practical in scenarios where rapid recommendations are essential. In this paper, we propose Turbo-CF, a GF-based CF method that is both training-free and matrix decomposition-free. Turbo-CF employs a polynomial graph filter to circumvent the issue of expensive matrix decompositions, enabling us to make full use of modern computer hardware components (i.e., GPU). Specifically, Turbo-CF first constructs an item-item similarity graph whose edge weights are effectively regulated. Then, our own polynomial LPFs are designed to retain only low-frequency signals without explicit matrix decompositions. We demonstrate that Turbo-CF is extremely fast yet accurate, achieving a runtime of <u>less than 1 second</u> on real-world benchmark datasets while achieving recommendation accuracies comparable to best competitors.

References

[1]
Jianxin Chang, Chen Gao, Yu Zheng, Yiqun Hui, Yanan Niu, Yang Song, Depeng Jin, and Yong Li. 2021. Sequential recommendation with graph neural networks. In SIGIR. 378--387.
[2]
Lei Chen, Le Wu, Richang Hong, Kun Zhang, and Meng Wang. 2020. Revisiting graph based collaborative filtering: A linear residual graph convolutional network approach. In AAAI. 27--34.
[3]
Huixuan Chi, Hao Xu, Hao Fu, Mengya Liu, Mengdi Zhang, Yuji Yang, Qinfen Hao, and Wei Wu. 2022. Long short-term preference modeling for continuous-time sequential recommendation. arXiv preprint arXiv:2208.00593 (2022).
[4]
Jeongwhan Choi, Seoyoung Hong, Noseong Park, and Sung-Bae Cho. 2023. Blurring-sharpening process models for collaborative filtering. In SIGIR. 1096--1106.
[5]
Yea Rem Choi, Vsevolod Nikolskiy, and Vladimir Stegailov. 2020. Matrix-matrix multiplication using multiple GPUs connected by NVlink. In GloSIC. IEEE, 354--361.
[6]
Paul Covington, Jay Adams, and Emre Sargin. 2016. Deep neural networks for youtube recommendations. In RecSys. 191--198.
[7]
Ken Goldberg, Theresa Roeder, Dhruv Gupta, and Chris Perkins. 2001. Eigentaste: A constant time collaborative filtering algorithm. Information Retrieval, Vol. 4 (2001), 133--151.
[8]
Carlos A Gomez-Uribe and Neil Hunt. 2015. The Netflix recommender system: Algorithms, business value, and innovation. ACM Transactions on Management Information Systems, Vol. 6, 4 (2015), 1--19.
[9]
Kazushige Goto and Robert A van de Geijn. 2008. Anatomy of high-performance matrix multiplication. ACM Transactions on Mathematical Software, Vol. 34, 3 (2008), 1--25.
[10]
Xiangnan He, Kuan Deng, Xiang Wang, Yan Li, Yongdong Zhang, and Meng Wang. 2020. LightGCN: Simplifying and powering graph convolution network for recommendation. In SIGIR. 639--648.
[11]
Xiangnan He, Lizi Liao, Hanwang Zhang, Liqiang Nie, Xia Hu, and Tat-Seng Chua. 2017. Neural collaborative filtering. In WWW. 173--182.
[12]
Xiangnan He, Hanwang Zhang, Min-Yen Kan, and Tat-Seng Chua. 2016. Fast matrix factorization for online recommendation with implicit feedback. In SIGIR. 549--558.
[13]
Chandima Hewa Nadungodage, Yuni Xia, and John Jaehwan Lee. 2017. A GPU-oriented online recommendation algorithm for efficient processing of time-varying continuous data streams. Knowledge and Information Systems, Vol. 53 (2017), 637--670.
[14]
Steven Huss-Lederman, Elaine M Jacobson, Anna Tsao, Thomas Turnbull, and Jeremy R Johnson. 1996. Implementation of Strassen's algorithm for matrix multiplication. In SC. 32--es.
[15]
Olivier Jeunen. 2019. Revisiting offline evaluation for implicit-feedback recommender systems. In RecSys. 596--600.
[16]
Bowen Jin, Chen Gao, Xiangnan He, Depeng Jin, and Yong Li. 2020. Multi-behavior recommendation with graph convolutional networks. In SIGIR. 659--668.
[17]
Bin Ju, Yuntao Qian, Minchao Ye, Rong Ni, and Chenxi Zhu. 2015. Using dynamic multi-task non-negative matrix factorization to detect the evolution of user preferences in collaborative filtering. PLoS One, Vol. 10, 8 (2015), e0135090.
[18]
Dawen Liang, Rahul G Krishnan, Matthew D Hoffman, and Tony Jebara. 2018. Variational autoencoders for collaborative filtering. In WWW. 689--698.
[19]
Greg Linden, Brent Smith, and Jeremy York. 2003. Amazon. com recommendations: Item-to-item collaborative filtering. IEEE Internet computing, Vol. 7, 1 (2003), 76--80.
[20]
Jiahao Liu, Dongsheng Li, Hansu Gu, Tun Lu, Peng Zhang, Li Shang, and Ning Gu. 2023. Personalized graph signal processing for collaborative filtering. In WWW. 1264--1272.
[21]
Kelong Mao, Jieming Zhu, Xi Xiao, Biao Lu, Zhaowei Wang, and Xiuqiang He. 2021. UltraGCN: Ultra simplification of graph convolutional networks for recommendation. In CIKM. 1253--1262.
[22]
Antonio Ortega, Pascal Frossard, Jelena Kovavcević, José MF Moura, and Pierre Vandergheynst. 2018. Graph signal processing: Overview, challenges, and applications. Proceedings of the IEEE, Vol. 106, 5 (2018), 808--828.
[23]
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. 2019. PyTorch: An imperative style, high-performance deep learning library. (2019).
[24]
Fabíola SF Pereira, Jo ao Gama, Sandra de Amo, and Gina MB Oliveira. 2018. On analyzing user preference dynamics with temporal social networks. Machine Learning, Vol. 107 (2018), 1745--1773.
[25]
Steffen Rendle, Christoph Freudenthaler, Zeno Gantner, and Lars Schmidt-Thieme. 2009. BPR: Bayesian personalized ranking from implicit feedback. In UAI. 452--461.
[26]
Jason Sanders and Edward Kandrot. 2010. CUDA by example: An introduction to general-purpose GPU programming. Addison-Wesley Professional.
[27]
Yifei Shen, Yongji Wu, Yao Zhang, Caihua Shan, Jun Zhang, B Khaled Letaief, and Dongsheng Li. 2021. How powerful is graph convolution for recommendation?. In CIKM. 1619--1629.
[28]
David I Shuman, Sunil K Narang, Pascal Frossard, Antonio Ortega, and Pierre Vandergheynst. 2013. The emerging field of signal processing on graphs: Extending high-dimensional data analysis to networks and other irregular domains. IEEE Signal Processing Magazine, Vol. 30, 3 (2013), 83--98.
[29]
Mithuna Thottethodi, Siddhartha Chatterjee, and Alvin R Lebeck. 1998. Tuning Strassen's matrix multiplication for memory efficiency. In SC. IEEE, 36--36.
[30]
Nguyen Thanh Toan, Phan Thanh Cong, Nguyen Thanh Tam, Nguyen Quoc Viet Hung, and Bela Stantic. 2018. Diversifying group recommendation. IEEE Access, Vol. 6 (2018), 17776--17786.
[31]
Rianne van den Berg, Thomas N. Kipf, and Max Welling. 2017. Graph convolutional matrix completion. CoRR, Vol. abs/1706.02263 (2017).
[32]
Wenjie Wang, Yiyan Xu, Fuli Feng, Xinyu Lin, Xiangnan He, and Tat-Seng Chua. 2023. Diffusion recommender model. In SIGIR. 832--841.
[33]
Xiang Wang, Xiangnan He, Meng Wang, Fuli Feng, and Tat-Seng Chua. 2019. Neural graph collaborative filtering. In SIGIR. 165--174.
[34]
Xiang Wang, Hongye Jin, An Zhang, Xiangnan He, Tong Xu, and Tat-Seng Chua. 2020. Disentangled graph collaborative filtering. In SIGIR. 1001--1010.
[35]
Le Wu, Yong Ge, Qi Liu, Enhong Chen, Richang Hong, Junping Du, and Meng Wang. 2017. Modeling the evolution of users' preferences and social links in social networking services. IEEE Transactions on Knowledge and Data Engineering, Vol. 29, 6 (2017), 1240--1253.
[36]
Shu Wu, Yuyuan Tang, Yanqiao Zhu, Liang Wang, Xing Xie, and Tieniu Tan. 2019. Session-based recommendation with graph neural networks. In AAAI. 346--353.
[37]
Jiafeng Xia, Dongsheng Li, Hansu Gu, Jiahao Liu, Tun Lu, and Ning Gu. 2022. FIRE: Fast incremental recommendation with graph signal processing. In WWW. 1808--1819.
[38]
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. 2019. How powerful are graph neural networks?. In ICLR. 1--17.
[39]
Xiujuan Xu, Jianyu Zhou, Yu Liu, Zhenzhen Xu, and Xiaowei Zhao. 2014. Taxi-RS: Taxi-hunting recommendation system based on taxi GPS data. IEEE Transactions on Intelligent Transportation Systems, Vol. 16, 4 (2014), 1716--1727.
[40]
Rex Ying, Ruining He, Kaifeng Chen, Pong Eksombatchai, William L Hamilton, and Jure Leskovec. 2018. Graph convolutional neural networks for web-scale recommender systems. In KDD. 974--983.
[41]
Lei Zheng, Chun-Ta Lu, Fei Jiang, Jiawei Zhang, and Philip S Yu. 2018. Spectral collaborative filtering. In RecSys. 311--319.

Index Terms

  1. Turbo-CF: Matrix Decomposition-Free Graph Filtering for Fast Recommendation

    Recommendations

    Comments

    Information & Contributors

    Information

    Published In

    cover image ACM Conferences
    SIGIR '24: Proceedings of the 47th International ACM SIGIR Conference on Research and Development in Information Retrieval
    July 2024
    3164 pages
    ISBN:9798400704314
    DOI:10.1145/3626772
    This work is licensed under a Creative Commons Attribution International 4.0 License.

    Sponsors

    Publisher

    Association for Computing Machinery

    New York, NY, United States

    Publication History

    Published: 11 July 2024

    Check for updates

    Author Tags

    1. collaborative filtering
    2. low-pass filter
    3. matrix decomposition
    4. polynomial graph filter
    5. recommender system.

    Qualifiers

    • Short-paper

    Funding Sources

    Conference

    SIGIR 2024
    Sponsor:

    Acceptance Rates

    Overall Acceptance Rate 792 of 3,983 submissions, 20%

    Contributors

    Other Metrics

    Bibliometrics & Citations

    Bibliometrics

    Article Metrics

    • 0
      Total Citations
    • 201
      Total Downloads
    • Downloads (Last 12 months)201
    • Downloads (Last 6 weeks)52
    Reflects downloads up to 13 Jan 2025

    Other Metrics

    Citations

    View Options

    View options

    PDF

    View or Download as a PDF file.

    PDF

    eReader

    View online with eReader.

    eReader

    Login options

    Media

    Figures

    Other

    Tables

    Share

    Share

    Share this Publication link

    Share on social media