TANGENT: a novel, 'Surprise me', recommendation algorithm

ABSTRACT

Most of recommender systems try to find items that are most relevant to the older choices of a given user. Here we focus on the "surprise me" query: A user may be bored with his/her usual genre of items (e.g., books, movies, hobbies), and may want a recommendation that is related, but off the beaten path, possibly leading to a new genre of books/movies/hobbies.

How would we define, as well as automate, this seemingly selfcontradicting request? We introduce TANGENT, a novel recommendation algorithm to solve this problem. The main idea behind TANGENT is to envision the problem as node selection on a graph, giving high scores to nodes that are well connected to the older choices, and at the same time well connected to unrelated choices. The method is carefully designed to be (a) parameter-free (b) effective and (c) fast. We illustrate the benefits of TANGENT with experiments on both synthetic and real data sets. We show that TANGENT makes reasonable, yet surprising, horizon-broadening recommendations. Moreover, it is fast and scalable, since it can easily use existing fast algorithms on graph node proximity.

REFERENCES

• 1: ]]R. Albert, H. Jeong, and A.-L. Barabasi. Diameter of the world wide web. Nature, (401):130--131, 1999.
• 2: Lars Backstrom , Dan Huttenlocher , Jon Kleinberg , Xiangyang Lan, Group formation in large social networks: membership, growth, and evolution, Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, August 20-23, 2006, Philadelphia, PA, USA [doi>10.1145/1150402.1150412]
• 3: Robert Bell , Yehuda Koren , Chris Volinsky, Modeling relationships at multiple scales to improve accuracy of large recommender systems, Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining, August 12-15, 2007, San Jose, California, USA [doi>10.1145/1281192.1281206]
• 4: Mustafa Bilgic , Lise Getoor, Effective label acquisition for collective classification, Proceeding of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2008, Las Vegas, Nevada, USA [doi>10.1145/1401890.1401901]
• 5: ]]U. Brandes. A Faster Algorithm for Betweenness Centrality. Mathematical Sociology, 25(2):163--177, 2001.
• 6: Andrei Broder , Ravi Kumar , Farzin Maghoul , Prabhakar Raghavan , Sridhar Rajagopalan , Raymie Stata , Andrew Tomkins , Janet Wiener, Graph structure in the Web, Proceedings of the 9th international World Wide Web conference on Computer networks : the international journal of computer and telecommunications netowrking, p.309-320, June 2000, Amsterdam, The Netherlands
• 7: Jeffrey Dean , Sanjay Ghemawat, MapReduce: simplified data processing on large clusters, Communications of the ACM, v.51 n.1, January 2008 [doi>10.1145/1327452.1327492]
• 8: ]]P. G. Doyle and J. L. Snell. Random Walks and Electric Networks. Mathematical Association of America, 1984.
• 9: Francois Fouss , Alain Pirotte , Jean-Michel Renders , Marco Saerens, Random-Walk Computation of Similarities between Nodes of a Graph with Application to Collaborative Recommendation, IEEE Transactions on Knowledge and Data Engineering, v.19 n.3, p.355-369, March 2007 [doi>10.1109/TKDE.2007.46]
• 10: ]]L. C. Freeman. A Set of Measures of Centrality Based on Betweenness. Sociometry, 40(1):35--41, March 1977.
• 11: David Gibson , Jon Kleinberg , Prabhakar Raghavan, Inferring Web communities from link topology, Proceedings of the ninth ACM conference on Hypertext and hypermedia : links, objects, time and space---structure in hypermedia systems: links, objects, time and space---structure in hypermedia systems, p.225-234, June 20-24, 1998, Pittsburgh, Pennsylvania, United States [doi>10.1145/276627.276652]
• 12: ]]M. Girvan and M. E. J. Newman. Community structure is social and biological networks.
• 13: Taher H. Haveliwala, Topic-sensitive PageRank, Proceedings of the 11th international conference on World Wide Web, May 07-11, 2002, Honolulu, Hawaii, USA [doi>10.1145/511446.511513]
• 14: R. Jin , C. Wang , D. Polshakov , S. Parthasarathy , G. Agrawal, Discovering frequent topological structures from graph datasets, Proceedings of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining, August 21-24, 2005, Chicago, Illinois, USA [doi>10.1145/1081870.1081944]
• 15: Junzo Kamahara , Tomofumi Asakawa , Shinji Shimojo , Hideo Miyahara, A Community-Based Recommendation System to Reveal Unexpected Interests, Proceedings of the 11th International Multimedia Modelling Conference, p.433-438, January 12-14, 2005 [doi>10.1109/MMMC.2005.5]
• 16: George Karypis , Vipin Kumar, Multilevel k-way hypergraph partitioning, Proceedings of the 36th annual ACM/IEEE Design Automation Conference, p.343-348, June 21-25, 1999, New Orleans, Louisiana, United States [doi>10.1145/309847.309954]
• 17: Yehuda Koren , Stephen C. North , Chris Volinsky, Measuring and extracting proximity in networks, Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, August 20-23, 2006, Philadelphia, PA, USA [doi>10.1145/1150402.1150432]
• 18: Jure Leskovec , Jon Kleinberg , Christos Faloutsos, Graphs over time: densification laws, shrinking diameters and possible explanations, Proceedings of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining, August 21-24, 2005, Chicago, Illinois, USA [doi>10.1145/1081870.1081893]
• 19: Jure Leskovec , Kevin J. Lang , Anirban Dasgupta , Michael W. Mahoney, Statistical properties of community structure in large social and information networks, Proceeding of the 17th international conference on World Wide Web, April 21-25, 2008, Beijing, China [doi>10.1145/1367497.1367591]
• 20: Sean M. McNee , John Riedl , Joseph A. Konstan, Being accurate is not enough: how accuracy metrics have hurt recommender systems, CHI '06 extended abstracts on Human factors in computing systems, April 22-27, 2006, Montréal, Québec, Canada [doi>10.1145/1125451.1125659]
• 21: Jennifer Neville , Özgür Şimşek , David Jensen , John Komoroske , Kelly Palmer , Henry Goldberg, Using relational knowledge discovery to prevent securities fraud, Proceedings of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining, August 21-24, 2005, Chicago, Illinois, USA [doi>10.1145/1081870.1081922]
• 22: ]]M. E. J. Newman. The structure and function of complex networks. SIAM Review, 45:167--256, 2003.
• 23: ]]M. E. J. Newman. A measure of betweenness centrality based on random walks. Social Networks, 27(1):39--54, January 2005.
• 24: Caleb C. Noble , Diane J. Cook, Graph-based anomaly detection, Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2003, Washington, D.C. [doi>10.1145/956750.956831]
• 25: ]]L. Page, S. Brin, R. Motwani, and T. Winograd. The PageRank Citation Ranking: Bringing Order to the Web. Stanford Digital Library Technologies Project, SIDL-WP-1999-0120, 1999.
• 26: ]]C. R. Palmer and C. Faloutsos. Electricity Based External Similarity of Categorical Attributes. In PAKDD, pages 486--500, 2003.
• 27: ]]J. Pei, A. W.-C. Fu, X. Lin, and H. Wang. Computing Compressed Multidimensional Skyline Cubes Efficiently. In ICDE, pages 96--105, 2007.
• 28: Paul Resnick , Neophytos Iacovou , Mitesh Suchak , Peter Bergstrom , John Riedl, GroupLens: an open architecture for collaborative filtering of netnews, Proceedings of the 1994 ACM conference on Computer supported cooperative work, p.175-186, October 22-26, 1994, Chapel Hill, North Carolina, United States [doi>10.1145/192844.192905]
• 29: ]]B. M. Sarwar, G. Karypis, J. Konstan, and J. Riedl. Recommender Systems for Large-Scale E-Commerce: Scalable Neighborhood Formation Using Clustering. In Proceedings of the Fifth International Conference on Computer and Information Technology, 2002.
• 30: Jimeng Sun , Huiming Qu , Deepayan Chakrabarti , Christos Faloutsos, Relevance search and anomaly detection in bipartite graphs, ACM SIGKDD Explorations Newsletter, v.7 n.2, p.48-55, December 2005 [doi>10.1145/1117454.1117461]
• 31: Hanghang Tong , Christos Faloutsos, Center-piece subgraphs: problem definition and fast solutions, Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, August 20-23, 2006, Philadelphia, PA, USA [doi>10.1145/1150402.1150448]
• 32: Hanghang Tong , Christos Faloutsos , Jia-Yu Pan, Random walk with restart: fast solutions and applications, Knowledge and Information Systems, v.14 n.3, p.327-346, March 2008 [doi>10.1007/s10115-007-0094-2]
• 33: Fei Wang , Sheng Ma , Liuzhong Yang , Tao Li, Recommendation on Item Graphs, Proceedings of the Sixth International Conference on Data Mining, p.1119-1123, December 18-22, 2006 [doi>10.1109/ICDM.2006.133]
• 34: Dong Xin , Jiawei Han , Xifeng Yan , Hong Cheng, Mining compressed frequent-pattern sets, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Data mining

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Search process; Clustering

General Terms:
Algorithms, Experimentation

Keywords:
graph mining, node proximity, recommender system