[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

EigenRec: generalizing PureSVD for effective and efficient top-N recommendations

  • Regular Paper
  • Published:
Knowledge and Information Systems Aims and scope Submit manuscript

Abstract

We introduce EigenRec, a versatile and efficient latent factor framework for top-N recommendations that includes the well-known PureSVD algorithm as a special case. EigenRec builds a low-dimensional model of an inter-item proximity matrix that combines a similarity component, with a scaling operator, designed to control the influence of the prior item popularity on the final model. Seeing PureSVD within our framework provides intuition about its inner workings, exposes its inherent limitations, and also, paves the path toward painlessly improving its recommendation performance. A comprehensive set of experiments on the MovieLens and the Yahoo datasets based on widely applied performance metrics, indicate that EigenRec outperforms several state-of-the-art algorithms, in terms of Standard and Long-Tail recommendation accuracy, exhibiting low susceptibility to sparsity, even in its most extreme manifestations—the Cold-Start problems. At the same time, EigenRec has an attractive computational profile and it can apply readily in large-scale recommendation settings.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6

Similar content being viewed by others

Notes

  1. Note that even though the actual values of the reconstructed matrix do not have a meaning in terms of ratings, they induce an ordering of the items which is sufficient for recommending top-N lists.

  2. A preliminary version of this work has been presented in [28].

  3. High-level and MPI implementations of EigenRec can be found here: https://github.com/nikolakopoulos/EigenRec.

  4. Remember that these “scores” are by definition the elements that replace the previously zero-valued entries of the original ratings matrix \({\mathbf {R}}\), after its reconstruction using only the f largest singular dimensions.

  5. For which, if we assume scaling parameter d, matrix W equals \({\mathbf {R}}\,{\mathrm{diag}}\{\Vert {\mathbf {r}}_{{\mathbf {1}}}\Vert ,\Vert {\mathbf {r}}_{{\mathbf {2}}}\Vert ,\dots ,\Vert {\mathbf {r}}_{{\mathbf {m}}}\Vert \}^{d-1}.\)

  6. Note that to alleviate this, one can use sophisticated parallel schemes that try to overlap communication with computations; however, their analysis goes deep into high-performance computing and lies outside the scope of this paper.

  7. Different approaches to compute partial singular value decompositions of sparse matrices can be found in [38, 39].

References

  1. Anderson C (2008) The long tail: Why the future of business is selling less of more. Hyperion, New York

    Google Scholar 

  2. Aurentz JL, Kalantzis V, Saad Y (2017) Cucheb: a GPU implementation of the filtered Lanczos procedure. Comput Phys Commun 220:332–340

    Article  Google Scholar 

  3. Bai Z, Demmel J, Dongarra J, Ruhe A, van der Vorst H (2000) Templates for the solution of algebraic eigenvalue problems: a practical guide, vol 11. SIAM, Philadelphia

    Book  MATH  Google Scholar 

  4. Balakrishnan S, Chopra S (2012) Collaborative ranking. In: Proceedings of the fifth ACM international conference on Web search and data mining, WSDM ’12. ACM, New York, pp 143–152. https://doi.org/10.1145/2124295.2124314

  5. Blackford LS, Petitet A, Pozo R, Remington K, Whaley RC, Demmel J, Dongarra J, Duff I, Hammarling S, Henry G et al (2002) An updated set of basic linear algebra subprograms (blas). ACM Trans Math Softw 28(2):135–151

    Article  MathSciNet  Google Scholar 

  6. Blom K, Ruhe A (2004) A krylov subspace method for information retrieval. SIAM J Matrix Anal Appl 26(2):566–582

    Article  MathSciNet  MATH  Google Scholar 

  7. Bobadilla J, Ortega F, Hernando A, GutiéRrez A (2013) Recommender systems survey. Knowl. Based Syst 46:109–132. https://doi.org/10.1016/j.knosys.2013.03.012

    Article  Google Scholar 

  8. Chebotarev P, Shamis E (1997) The matrix-forest theorem and measuring relations in small social groups. Autom Remote Control 58(9):1505–1514

    MATH  Google Scholar 

  9. Chen J, Saad Y (2009) Lanczos vectors versus singular vectors for effective dimension reduction. IEEE Trans Knowl Data Eng 21(8):1091–1103

    Article  Google Scholar 

  10. Cremonesi P, Koren Y, Turrin R (2010) Performance of recommender algorithms on top-n recommendation tasks. In: Proceedings of the fourth ACM conference on Recommender systems, RecSys ’10. ACM, pp 39–46. https://doi.org/10.1145/1864708.1864721

  11. Desrosiers C, Karypis G (2011) A comprehensive survey of neighborhood-based recommendation methods. In: Ricci F, Rokach L, Shapira B, Kantor PB (eds) Recommender systems handbook. Springer, US, pp 107–144. https://doi.org/10.1007/978-0-387-85820-3_4

    Chapter  Google Scholar 

  12. Elbadrawy A, Karypis G (2015) User-specific feature-based similarity models for top-n recommendation of new items. ACM Trans Intell Syst Technol 6(3):33:1–33:20. https://doi.org/10.1145/2700495

    Article  Google Scholar 

  13. Fouss F, Francoisse K, Yen L, Pirotte A, Saerens M (2012) An experimental investigation of kernels on graphs for collaborative recommendation and semisupervised classification. Neural Netw 31:53–72

    Article  MATH  Google Scholar 

  14. Fouss F, Pirotte A, Renders J, Saerens M (2007) Random-walk computation of similarities between nodes of a graph with application to collaborative recommendation. IEEE Trans Knowl Data Eng 19(3):355–369

    Article  Google Scholar 

  15. Gallopoulos E, Philippe B, Sameh AH (2015) Parallelism in matrix computations, 1st edn. Springer, Berlin

    MATH  Google Scholar 

  16. Gantner Z, Drumond L, Freudenthaler C, Rendle S, Schmidt-Thieme L (2010) Learning attribute-to-feature mappings for cold-start recommendations. In: 2010 IEEE 10th international conference on data mining (ICDM), pp 176–185. https://doi.org/10.1109/ICDM.2010.129

  17. Goldberg K, Roeder T, Gupta D, Perkins C (2001) Eigentaste: a constant time collaborative filtering algorithm. Inf Retr 4(2):133–151. https://doi.org/10.1023/A:1011419012209

    Article  MATH  Google Scholar 

  18. Harper FM, Konstan JA (2015) The movielens datasets: history and context. ACM Trans Interact Intell Syst 5(4):19:1–19:19. https://doi.org/10.1145/2827872

    Article  Google Scholar 

  19. Huang Z, Chen H, Zeng D (2004) Applying associative retrieval techniques to alleviate the sparsity problem in collaborative filtering. ACM Trans Inf Syst 22(1):116–142. https://doi.org/10.1145/963770.963775

    Article  Google Scholar 

  20. Joachims T, Swaminathan A, Schnabel T (2017) Unbiased learning-to-rank with biased feedback. In: Proceedings of the tenth ACM international conference on web search and data mining, WSDM ’17. ACM, New York, pp 781–789. https://doi.org/10.1145/3018661.3018699

  21. Kabbur S, Ning X, Karypis G (2013) Fism: factored item similarity models for top-n recommender systems. In: Proceedings of the 19th ACM SIGKDD international conference on knowledge discovery and data mining, KDD’13. ACM, New York, pp 659–667. https://doi.org/10.1145/2487575.2487589

  22. Kalantzis V, Li R, Saad Y (2016) Spectral schur complement techniques for symmetric eigenvalue problems. Electron Trans Numer Anal 45:305–329

    MathSciNet  MATH  Google Scholar 

  23. Koren Y (2008) Factorization meets the neighborhood: a multifaceted collaborative filtering model. In: Proceedings of the 14th ACM SIGKDD international conference on knowledge discovery and data mining, KDD’08. ACM, New York, pp 426–434. https://doi.org/10.1145/1401890.1401944

  24. Koren Y, Bell R, Volinsky C (2009) Matrix factorization techniques for recommender systems. Computer 42(8):30–37

    Article  Google Scholar 

  25. Lanczos C (1950) An iteration method for the solution of the eigenvalue problem of linear differential and integral operators. United States Government Press Office, Washington, D.C

    Book  MATH  Google Scholar 

  26. Nikolakopoulos A, Garofalakis J (2014) NCDREC: a decomposability inspired framework for top-n recommendation. In: 2014 IEEE/WIC/ACM international joint conferences on web intelligence (WI) and intelligent agent technologies (IAT), vol 1, pp 183–190. https://doi.org/10.1109/WI-IAT.2014.32

  27. Nikolakopoulos AN, Kalantzi M, Garofalakis JD (2014) On the use of lanczos vectors for efficient latent factor-based top-n recommendation. In: Proceedings of the 4th international conference on web intelligence, mining and semantics (WIMS14), WIMS ’14. ACM, New York, pp 28:1–28:6. https://doi.org/10.1145/2611040.2611078

  28. Nikolakopoulos AN, Kalantzis V, Gallopoulos E, Garofalakis JD (2017) Factored proximity models for top-n recommendations. In: 2017 IEEE international conference on big knowledge (ICBK), pp 80–87. https://doi.org/10.1109/ICBK.2017.14

  29. Nikolakopoulos AN, Korba A, Garofalakis JD (2016) Random surfing on multipartite graphs. In: 2016 IEEE international conference on big data (big data), pp 736–745. https://doi.org/10.1109/BigData.2016.7840666

  30. Nikolakopoulos AN, Kouneli MA, Garofalakis JD (2015) Hierarchical itemspace rank: exploiting hierarchy to alleviate sparsity in ranking-based recommendation. Neurocomputing 163:126–136. https://doi.org/10.1016/j.neucom.2014.09.082

    Article  Google Scholar 

  31. Sarwar B, Karypis G, Konstan J, Riedl J (2000) Application of dimensionality reduction in recommender system-a case study. Tech. rep., DTIC Document

  32. Schnabel T, Swaminathan A, Singh A, Chandak N, Joachims T (2016) Recommendations as treatments: debiasing learning and evaluation. In: Proceedings of the 33rd international conference on international conference on machine learning, ICML’16, vol 48, pp 1670–1679. JMLR.org. http://dl.acm.org/citation.cfm?id=3045390.3045567

  33. Shani G, Gunawardana A (2011) Evaluating recommendation systems. In: Ricci F, Rokach L, Shapira B, Kantor PB (eds) Recommender systems handbook. Springer, Boston, pp 257–297. https://doi.org/10.1007/978-0-387-85820-3_8

    Chapter  Google Scholar 

  34. Sharma M, Zhou J, Hu J, Karypis G (2015) Feature-based factorized bilinear similarity model for cold-start top-n item recommendation. In: Proceedings of the 2015 SIAM international conference on data mining, SDM’15, pp 190–198. https://doi.org/10.1137/1.9781611974010.22

  35. Snir M, Otto S, Huss-Lederman S, Walker D, Dongarra J (1998) MPI-the complete reference, vol 1: the MPI core, 2nd. (revised) edn. MIT Press, Cambridge

  36. Takács G, Pilászy I, Németh B, Tikk D (2009) Scalable collaborative filtering approaches for large recommender systems. J Mach Learn Res 10:623–656 http://dl.acm.org/citation.cfm?id=1577069.1577091

  37. Wu K, Simon H (2000) Thick-restart lanczos method for large symmetric eigenvalue problems. SIAM J Matrix Anal Appl 22(2):602–616

    Article  MathSciNet  MATH  Google Scholar 

  38. Wu L, Romero E, Stathopoulos A (2016) Primme_svds: A high-performance preconditioned svd solver for accurate large-scale computations. arXiv preprint arXiv:1607.01404

  39. Wu L, Stathopoulos A (2015) A preconditioned hybrid svd method for accurately computing singular triplets of large matrices. SIAM J Sci Comput 37(5):S365–S388

    Article  MathSciNet  MATH  Google Scholar 

  40. Yahoo Webscope Program: Yahoo!R2Music Dataset. https://webscope.sandbox.yahoo.com/

  41. Yin H, Cui B, Li J, Yao J, Chen C (2012) Challenging the long tail recommendation. Proc VLDB Endow 5(9):896–907

    Article  Google Scholar 

  42. Zhou D, Bousquet O, Lal TN, Weston J, Schölkopf B (2003) Learning with local and global consistency. In: Thrun S, Saul LK, Schölkopf B (eds) Advances in neural information processing systems 16 [Neural information processing systems, NIPS 2003, 8–13 Dec 2003, Vancouver and Whistler, British Columbia, Canada]. MIT Press, pp 321–328. http://papers.nips.cc/paper/2506-learning-with-local-and-global-consistency

Download references

Acknowledgements

Vassilis Kalantzis was partially supported by a Gerondelis Foundation Fellowship. The authors acknowledge the Minnesota Supercomputing Institute (http://www.msi.umn.edu) at the University of Minnesota for providing resources that contributed to the research results reported within this paper.

Author information

Authors and Affiliations

  1. Digital Technology Center, University of Minnesota, Minneapolis, MN, USA

    Athanasios N. Nikolakopoulos

  2. Department of Computer Science and Engineering, University of Minnesota, Minneapolis, MN, USA

    Vassilis Kalantzis

  3. Department of Computer Engineering and Informatics, University of Patras, Patras, Greece

    Efstratios Gallopoulos & John D. Garofalakis

Authors
  1. Athanasios N. Nikolakopoulos
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Vassilis Kalantzis
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Efstratios Gallopoulos
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. John D. Garofalakis
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Athanasios N. Nikolakopoulos.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Nikolakopoulos, A.N., Kalantzis, V., Gallopoulos, E. et al. EigenRec: generalizing PureSVD for effective and efficient top-N recommendations. Knowl Inf Syst 58, 59–81 (2019). https://doi.org/10.1007/s10115-018-1197-7

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10115-018-1197-7

Keywords

Search

Navigation