Recommendation Subgraphs for Web Discovery

ABSTRACT

Recommendations are central to the utility of many popular e-commerce websites. Such sites typically contain a set of recommendations on every product page that enables visitors and crawlers to easily navigate the website. These recommendations are essentially universally present on all e-commerce websites. Choosing an appropriate set of recommendations at each page is a critical task performed by dedicated backend software systems. We formalize the concept of recommendations used for discovery as a natural graph optimization problem on a bipartite graph and propose three methods for solving the problem in increasing order of sophistication: a local random sampling algorithm, a greedy algorithm and a more involved partitioning based algorithm. We first theoretically analyze the performance of these three methods on random graph models and characterize when each method will yield a solution of sufficient quality and the parameter ranges when more sophistication is needed. We complement this by roviding an empirical analysis of these algorithms on simulated and real-world production data from a retail website. Our results confirm that it is not always necessary to implement complicated algorithms in the real-world, and demonstrate that very good practical results can be obtained by using simple heuristics that are backed by the confidence of concrete theoretical guarantees.

References

1. G. Adomavicius and A. Tuzhilin. Toward the next generation of recommender systems: A survey of the state-of-the-art and possible extensions. IEEE Trans. on Knowl. and Data Eng., 17(6):734--749, June 2005.
2. D. Almazro, G. Shahatah, L. Albdulkarim, M. Kherees, R. Martinez, and W. Nzoukou. A survey paper on recommender systems. arXiv preprint arXiv:1006.5278, 2010.
3. C. Anderson. The Long Tail: Why the Future of Business Is Selling Less of More. Hyperion, 2006.
4. A. Auger and B. Doerr. Theory of Randomized Search Heuristics: Foundations and Recent Developments. Series on Theoretical Computer Science. World Scientific Publishing Company, 2011.
5. Robert M Bell, Yehuda Koren, and Chris Volinsky. The bellkor solution to the netflix prize.
6. A. S. Das, M. Datar, A. Garg, and S. Rajaram. Google news personalization: scalable online collaborative filtering. In Proceedings of the 16th international conference on World Wide Web, pages 271--280. ACM, 2007.
7. J. Dean and S. Ghemawat. Mapreduce: simplified data processing on large clusters. In OSDI '04: Proceedings of the sixth conference on symposium on operating systems design and implementation. USENIX Association, 2004.
8. B. Du, M. Demmer, and E. Brewer. Analysis of www traffic in cambodia and ghana. In Proceedings of the 15th international conference on World Wide Web, WWW '06, pages 771--780. ACM, 2006.
9. Ran Duan and Seth Pettie. Approximating maximum weight matching in near-linear time. In Foundations of Computer Science (FOCS), 2010 51st Annual IEEE Symposium on, pages 673--682. IEEE, 2010.
10. P. Erdos and A. Renyi. On random graphs, I. Publicationes Mathematicae, 6:290--297, 1959.
11. H. Gabow. An efficient reduction technique for degree-constrained subgraph and bidirected network flow problems. In Proceedings of the fifteenth annual ACM symposium on Theory of computing, STOC '83, pages 448--456. ACM, 1983.
12. J. Hannon, M. Bennett, and B. Smyth. Recommending twitter users to follow using content and collaborative filtering approaches. In Proceedings of the fourth ACM conference on Recommender systems, pages 199--206. ACM, 2010.
13. J. E. Hopcroft and R. M. Karp. An n 5/2 algorithm for maximum matchings in bipartite graphs. SIAM Journal on computing, 2(4):225--231, 1973.
14. B. A. Huberman and L. A. Adamic. Internet: growth dynamics of the world-wide web. Nature, 401(6749):131--131, 1999.
15. BloomReach Inc. Inside the technology: Web relevance engine.
16. S. Janson, T. Luczak, and A. Rucinski. Random Graphs. Wiley Series in Discrete Mathematics and Optimization. Wiley, 2011.
17. R. M. Karp, U. Vazirani, and V. Vazirani. An optimal algorithm for on-line bipartite matching. In Proceedings of the twenty-second annual ACM symposium on Theory of computing. ACM, 1990.
18. Christos Koufogiannakis and Neal E Young. Distributed fractional packing and maximum weighted b-matching via tail-recursive duality. In Distributed Computing, pages 221--238. Springer, 2009.
19. C. Kumar, J. B. Norris, and Y. Sun. Location and time do matter: A long tail study of website requests. Decision Support Systems, 47(4):500--507, 2009.
20. G. Linden, B. Smith, and J. York. Amazon. com recommendations: Item-to-item collaborative filtering. Internet Computing, IEEE, 7(1):76--80, 2003.
21. L Lovasz and M. D. Plummer. Matching theory. North-Holland mathematics studies. Akademiai Kiado, 1986.
22. George L Nemhauser, Laurence A Wolsey, and Marshall L Fisher. An analysis of approximations for maximizing submodular set functions. Mathematical Programming, 14(1):265--294, 1978.
23. P. Resnick and H. R. Varian. Recommender systems. Communications of the ACM, 40(3):56--58, 1997.
24. Purnamrita Sarkar, Deepayan Chakrabarti, and Andrew W Moore. Theoretical justification of popular link prediction heuristics. In IJCAI Proceedings-International Joint Conference on Artificial Intelligence, volume 22, page 2722, 2011.
25. J. B. Schafer, J. Konstan, and J. Riedi. Recommender systems in e-commerce. In Proceedings of the 1st ACM conference on Electronic commerce, EC '99, pages 158--166. ACM, 1999.

Index Terms

• Theory of computation

  • Design and analysis of algorithms