Advertisement
Published in:
2011 | OriginalPaper | Chapter
Unifying Guilt-by-Association Approaches: Theorems and Fast Algorithms
Authors : Danai Koutra, Tai-You Ke, U. Kang, Duen Horng (Polo) Chau, Hsing-Kuo Kenneth Pao, Christos Faloutsos
Published in: Machine Learning and Knowledge Discovery in Databases
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
If several friends of
Smith
have committed petty thefts, what would you say about
Smith
? Most people would not be surprised if
Smith
is a hardened criminal.
Guilt-by-association
methods combine weak signals to derive stronger ones, and have been extensively used for anomaly detection and classification in numerous settings (e.g., accounting fraud, cyber-security, calling-card fraud).
The focus of this paper is to compare and contrast several very successful,
guilt-by-association
methods:
Random Walk with Restarts
, Semi-Supervised Learning, and
Belief Propagation
(BP).
Our main contributions are two-fold: (a) theoretically, we prove that all the methods result in a similar matrix inversion problem; (b) for practical applications, we developed
FaBP
, a fast algorithm that yields 2× speedup, equal or higher accuracy than BP, and is guaranteed to converge. We demonstrate these benefits using synthetic and real datasets, including YahooWeb, one of the largest graphs ever studied with BP.