Skip to main content
Article
Detecting Anomalies in Bipartite Graphs with Mutual Dependency Principles
2012 IEEE 12th International Conference on Data Mining: ICDM 2012: 10-13 December 2012, Brussels, Belgium
  • Hanbo DAI, Singapore Management University
  • Feida ZHU, Singapore Management University
  • Ee Peng LIM, Singapore Management University
  • Hwee Hwa PANG, Singapore Management University
Publication Type
Conference Proceeding Article
Version
submittedVersion
Publication Date
12-2012
Abstract

Bipartite graphs can model many real life applications including users-rating-products in online marketplaces, users-clicking-webpages on the World Wide Web and users referring users in social networks. In these graphs, the anomalousness of nodes in one partite often depends on that of their connected nodes in the other partite. Previous studies have shown that this dependency can be positive (the anomalousness of a node in one partite increases or decreases along with that of its connected nodes in the other partite) or negative (the anomalousness of a node in one partite rises or falls in opposite direction to that of its connected nodes in the other partite). In this paper, we unify both positive and negative mutual dependency relationships in an unsupervised framework for detecting anomalous nodes in bipartite graphs. This is the first work that integrates both mutual dependency principles to model the complete set of anomalous behaviors of nodes that cannot be identified by either principle alone. We formulate our principles and design an iterative algorithm to simultaneously compute the anomaly scores of nodes in both partites. Moreover, we mathematically prove that the ranking of nodes by anomaly scores in each partite converges. Our framework is examined on synthetic graphs and the results show that our model outperforms existing models with only positive or negative mutual dependency principles. We also apply our framework to two real life datasets: Goodreads as a users-rating-books setting and Buzzcity as a users-clickingadvertisements setting. The results show that our method is able to detect suspected spamming users and spammed books in Goodreads and achieve higher precision in identifying fraudulent advertisement publishers than existing approaches.

Keywords
  • Anomaly Detection,
  • Bipartite Graph,
  • Mutual Dependency,
  • Mutual Reinforcement,
  • Node Anomalies
ISBN
9781467346498
Identifier
10.1109/ICDM.2012.167
Publisher
IEEE Computer Society
City or Country
Los Alamitos, CA
Copyright Owner and License
Authors
Creative Commons License
Creative Commons Attribution-NonCommercial-No Derivative Works 4.0 International
Additional URL
http://doi.ieeecomputersociety.org/10.1109/ICDM.2012.167
Citation Information
Hanbo DAI, Feida ZHU, Ee Peng LIM and Hwee Hwa PANG. "Detecting Anomalies in Bipartite Graphs with Mutual Dependency Principles" 2012 IEEE 12th International Conference on Data Mining: ICDM 2012: 10-13 December 2012, Brussels, Belgium (2012) p. 171 - 180
Available at: http://works.bepress.com/hweehwa-pang/19/