Fast direction-aware proximity for graph mining

ABSTRACT

In this paper we study asymmetric proximity measures on directed graphs, which quantify the relationships between two nodes or two groups of nodes. The measures are useful in several graph mining tasks, including clustering, link prediction and connection subgraph discovery. Our proximity measure is based on the conceptof escape probability. This way, we strive to summarize the multiple facets of nodes-proximity, while avoiding some of the pitfalls to which alternative proximity measures are susceptible. A unique feature of the measures is accounting for the underlying directional information. We put a special emphasis on computational efficiency, and develop fast solutions that are applicable in several settings. Our experimental study shows the usefulness of our proposed direction-aware proximity method for several applications, and that our algorithms achieve a significant speedup (up to 50,000x) over straight forward implementations.

REFERENCES

• 1: B. Aditya , Gaurav Bhalotia , Soumen Chakrabarti , Arvind Hulgeri , Charuta Nakhe , Parag Parag , S. Sudarshan, BANKS: browsing and keyword searching in relational databases, Proceedings of the 28th international conference on Very Large Data Bases, p.1083-1086, August 20-23, 2002, Hong Kong, China
• 2: Andrey Balmin , Vagelis Hristidis , Yannis Papakonstantinou, Objectrank: authority-based keyword search in databases, Proceedings of the Thirtieth international conference on Very large data bases, p.564-575, August 31-September 03, 2004, Toronto, Canada
• 3: Michael Collins , Robert E. Schapire , Yoram Singer, Logistic Regression, AdaBoost and Bregman Distances, Proceedings of the Thirteenth Annual Conference on Computational Learning Theory, p.158-169, June 28-July 01, 2000
• 4: Pedro Domingos , Matt Richardson, Mining the network value of customers, Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining, p.57-66, August 26-29, 2001, San Francisco, California [doi>10.1145/502512.502525]
• 5: P. Doyle and J. Snell. Random walks and electric networks, volume 22. Mathematical Association America, New York, 1984.
• 6: Christos Faloutsos , Kevin S. McCurley , Andrew Tomkins, Fast discovery of connection subgraphs, Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, August 22-25, 2004, Seattle, WA, USA [doi>10.1145/1014052.1014068]
• 7: Michalis Faloutsos , Petros Faloutsos , Christos Faloutsos, On power-law relationships of the Internet topology, ACM SIGCOMM Computer Communication Review, v.29 n.4, p.251-262, Oct. 1999
• 8: J. Friedman. Greedy function approximation: A gradient boosting machine. In Annual of Statistics, 2001.
• 9: Floris Geerts , Heikki Mannila , Evimaria Terzi, Relational link-based ranking, Proceedings of the Thirtieth international conference on Very large data bases, p.552-563, August 31-September 03, 2004, Toronto, Canada
• 10: G. Golub and C. Loan. Matrix Computation. Johns Hopkins, 1996.
• 11: M. Grötschel, C. L. Monma, and M. Stoer. Design of survivable networks. In Handbooks in Operations Research and Management Science 7: Network Models. North Holland, 1993.
• 12: T. Hastie, R. Tibshirani, and J. Friedman. The Elements of Statistical Learning. Springer.
• 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: Jingrui He , Mingjing Li , Hong-Jiang Zhang , Hanghang Tong , Changshui Zhang, Manifold-ranking based image retrieval, Proceedings of the 12th annual ACM international conference on Multimedia, October 10-16, 2004, New York, NY, USA [doi>10.1145/1027527.1027531]
• 15: 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]
• 16: David Liben-Nowell , Jon Kleinberg, The link prediction problem for social networks, Proceedings of the twelfth international conference on Information and knowledge management, November 03-08, 2003, New Orleans, LA, USA [doi>10.1145/956863.956972]
• 17: Jia-Yu Pan , Hyung-Jeong Yang , Christos Faloutsos , Pinar Duygulu, Automatic multimedia cross-modal correlation discovery, Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, August 22-25, 2004, Seattle, WA, USA [doi>10.1145/1014052.1014135]
• 18: Jimeng Sun , Huiming Qu , Deepayan Chakrabarti , Christos Faloutsos, Neighborhood Formation and Anomaly Detection in Bipartite Graphs, Proceedings of the Fifth IEEE International Conference on Data Mining, p.418-425, November 27-30, 2005 [doi>10.1109/ICDM.2005.103]
• 19: 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]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.m Miscellaneous

General Terms:
Algorithms, Experimentation

Keywords:
graph mining, proximity, random walk