[DB Seminar] Fall 2015: Alex Beutel

Which seems more suspicious: 5,000 tweets from 200 users on 5 IP addresses, or 10,000 tweets from 500 users on 500 IP addresses but all with the same trending topic and all in 10 minutes?  The literature has many methods that try to find dense blocks in matrices, and, recently, tensors, but no method gives a principled way to score the suspiciousness of dense blocks with different numbers of modes and rank them to draw human attention accordingly.  Dense blocks are worth inspecting, typically indicating fraud, emerging trends, or some other noteworthy deviation from the usual.  Our main contribution is that we show how to unify these methods and how to give a principled answer to questions like the above.  Specifically, (a) we give a list of axioms that any metric of suspiciousness should satisfy; (b) we propose an intuitive, principled metric that satisfies the axioms, and is fast to compute; (c) we propose CrossSpot, an algorithm to spot dense regions, and sort them in importance (“suspiciousness”) order.  Finally, we apply CrossSpot to real data, where it improves the F1 score over previous techniques by 68% and finds retweet-boosting in a real social dataset spanning 0.3 billion posts.