Unifying Guilt-by-Association Approaches: Theorems and Fast Algorithms

Danai Koutra

Date: 12/01/2012
University: Computer Science Department, Carnegie Mellon University
Room : A56
Time: 4:00pm (coffee: 3:30)

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 2x speedup, equal or higher accuracy than BP, and is guaranteed to converge.
We demonstrate these bene ts using synthetic and real datasets, including YahooWeb, one of the largest graphs ever studied with BP.

MaDgIK 2009-2018