Relevance search and anomaly detection in bipartite graphs

ABSTRACT

Many real applications can be modeled using bipartite graphs, such as users vs. files in a P2P system, traders vs. stocks in a financial trading system, conferences vs. authors in a scientific publication network, and so on. We introduce two operations on bipartite graphs: 1) identifying similar nodes (relevance search), and 2) finding nodes connecting irrelevant nodes (anomaly detection). And we propose algorithms to compute the relevance score for each node using random walk with restarts and graph partitioning; we also propose algorithms to identify anomalies, using relevance scores. We evaluate the quality of relevance search based on semantics of the datasets, and we also measure the performance of the anomaly detection algorithm with manually injected anomalies. Both effectiveness and efficiency of the methods are confirmed by experiments on several real datasets.

REFERENCES

• 1: Charu C. Aggarwal , Philip S. Yu, Outlier detection for high dimensional data, ACM SIGMOD Record, v.30 n.2, p.37-46, June 2001
• 2: J. Breese, D. Heckerman, and C. Kadie. Empirical analysis of predictive algorithms for collaborative filtering. In UAI, 1998.
• 3: Sergey Brin , Lawrence Page, The anatomy of a large-scale hypertextual Web search engine, Computer Networks and ISDN Systems, v.30 n.1-7, p.107-117, April 1, 1998
• 4: Deepayan Chakrabarti, AutoPart: parameter-free graph partitioning and outlier detection, Proceedings of the 8th European Conference on Principles and Practice of Knowledge Discovery in Databases, p.112-124, September 20-24, 2004, Pisa, Italy
• 5: Deepayan Chakrabarti , Spiros Papadimitriou , Dharmendra S. Modha , Christos Faloutsos, Fully automatic cross-associations, 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.1014064]
• 6: Inderjit S. Dhillon , Subramanyam Mallela , Dharmendra S. Modha, Information-theoretic co-clustering, 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.956764]
• 7: Gary William Flake, Steve Lawrence, and C. Lee Giles. Efficient identification of Web communities. In KDD, 2000.
• 8: M. Girvan and M. E. J. Newman. Community structure in social and biological networks. In Proc. Natl. Acad. Sci. USA, volume 99, 2002.
• 9: 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]
• 10: Taher H. Haveliwala and Sepandar D. Kamvar. The second eigenvalue of the google matrix. Stanford University Technical Report, 2003.
• 11: Glen Jeh , Jennifer Widom, SimRank: a measure of structural-context similarity, Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, July 23-26, 2002, Edmonton, Alberta, Canada [doi>10.1145/775047.775126]
• 12: R. Kannan , S. Vempala , A. Veta, On clusterings-good, bad and spectral, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.367, November 12-14, 2000
• 13: George Karypis , Vipin Kumar, Multilevel k-way partitioning scheme for irregular graphs, Journal of Parallel and Distributed Computing, v.48 n.1, p.96-129, Jan. 1998 [doi>10.1006/jpdc.1997.1404]
• 14: Stefan Klink, Michael Ley, Emma Rabbidge, Patrick Reuther, Bernd Walter, and Alexander Weber. Browsing and visualizing digital bibliographic data. In VisSym, pages 237--242, 2004.
• 15: 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]
• 16: 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]
• 17: Ricardo A. Baeza-Yates , Berthier Ribeiro-Neto, Modern Information Retrieval, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1999
• 18: Upendra Shardanand , Pattie Maes, Social information filtering: algorithms for automating “word of mouth”, Proceedings of the SIGCHI conference on Human factors in computing systems, p.210-217, May 07-11, 1995, Denver, Colorado, United States [doi>10.1145/223904.223931]
• 19: Gilbert Strang. Introduction to Linear Algebra. Wellesley-Cambridge Press, 3 edition, 1998.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Search process; Relevance feedback
      H.3.4 Systems and Software
          Subjects: Performance evaluation (efficiency and effectiveness)

General Terms:
Algorithms, Design, Performance