Detecting Anomalies in Bipartite Graphs with Mutual Dependency Principles

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 connect...

Full description

Saved in:
Bibliographic Details
Main Authors: DAI, Hanbo, ZHU, Feida, LIM, Ee Peng, PANG, Hwee Hwa
Format: text
Language:English
Published: Institutional Knowledge at Singapore Management University 2012
Subjects:
Online Access:https://ink.library.smu.edu.sg/sis_research/1736
https://ink.library.smu.edu.sg/context/sis_research/article/2735/viewcontent/ICDM_12.pdf
Tags: Add Tag
No Tags, Be the first to tag this record!
Institution: Singapore Management University
Language: English
id sg-smu-ink.sis_research-2735
record_format dspace
spelling sg-smu-ink.sis_research-27352017-07-11T14:56:40Z Detecting Anomalies in Bipartite Graphs with Mutual Dependency Principles DAI, Hanbo ZHU, Feida LIM, Ee Peng PANG, Hwee Hwa 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. 2012-12-01T08:00:00Z text application/pdf https://ink.library.smu.edu.sg/sis_research/1736 info:doi/10.1109/ICDM.2012.167 https://ink.library.smu.edu.sg/context/sis_research/article/2735/viewcontent/ICDM_12.pdf http://creativecommons.org/licenses/by-nc-nd/4.0/ Research Collection School Of Computing and Information Systems eng Institutional Knowledge at Singapore Management University Anomaly Detection Bipartite Graph Mutual Dependency Mutual Reinforcement Node Anomalies Databases and Information Systems Numerical Analysis and Scientific Computing
institution Singapore Management University
building SMU Libraries
continent Asia
country Singapore
Singapore
content_provider SMU Libraries
collection InK@SMU
language English
topic Anomaly Detection
Bipartite Graph
Mutual Dependency
Mutual Reinforcement
Node Anomalies
Databases and Information Systems
Numerical Analysis and Scientific Computing
spellingShingle Anomaly Detection
Bipartite Graph
Mutual Dependency
Mutual Reinforcement
Node Anomalies
Databases and Information Systems
Numerical Analysis and Scientific Computing
DAI, Hanbo
ZHU, Feida
LIM, Ee Peng
PANG, Hwee Hwa
Detecting Anomalies in Bipartite Graphs with Mutual Dependency Principles
description 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.
format text
author DAI, Hanbo
ZHU, Feida
LIM, Ee Peng
PANG, Hwee Hwa
author_facet DAI, Hanbo
ZHU, Feida
LIM, Ee Peng
PANG, Hwee Hwa
author_sort DAI, Hanbo
title Detecting Anomalies in Bipartite Graphs with Mutual Dependency Principles
title_short Detecting Anomalies in Bipartite Graphs with Mutual Dependency Principles
title_full Detecting Anomalies in Bipartite Graphs with Mutual Dependency Principles
title_fullStr Detecting Anomalies in Bipartite Graphs with Mutual Dependency Principles
title_full_unstemmed Detecting Anomalies in Bipartite Graphs with Mutual Dependency Principles
title_sort detecting anomalies in bipartite graphs with mutual dependency principles
publisher Institutional Knowledge at Singapore Management University
publishDate 2012
url https://ink.library.smu.edu.sg/sis_research/1736
https://ink.library.smu.edu.sg/context/sis_research/article/2735/viewcontent/ICDM_12.pdf
_version_ 1770571485548642304