Computer Science Thesis Oral

Tuesday, October 17, 2017 - 1:00pm


8102 Gates Hillman Centers


NEIL SHAH, Ph.D. Student

Anomaly Detection in Large Social Graphs

Given the ever-growing prevalence of online social services, leveraging massive datasets has become an increasingly important challenge for businesses and end-users alike.  Online services capture a wealth of information about user behavior and platform interactions, such as who-follows-whom relationships in social networks and who-rates-what-and-when relationships in e-commerce networks.  Since many of these services rely on data-driven algorithms to recommend content to their users, authenticity of user behavior is paramount to success.  But given anonymity on the internet, how do we know which users and actions are real or not?  This thesis focuses on this problem and introduces new techniques to effectively and efficiently discern anomalous and fraudulent behavior in online social graphs. Specifically, we work on three thrusts: plain graphs, dynamic graphs and rich graphs.

Firstly, we focus on plain graphs, in which only static connectivity information is known.
We detail several proposed algorithms spanning the topics of spectral fraud detection in a single graph, blame attribution between graph snapshots, and structurally diverse graph summarization.

Next, we broaden our scope to dynamic graphs, in which we leverage connectivity information over a span of time.  We describe multiple relevant works which describe how to identify and summarize anomalous temporal graph structures, model interarrival time patterns in user queries to find anomalous search behavior, and identify "group" anomalies comprising of users acting in lockstep.

Lastly, we expand our reach to rich graphs, in which connectivity information is supplemented by other attributes, such as time, rating, number of messages sent, etc.  To this end, we discuss several works which focus on ranking abnormality of nodes in edge-attributed graphs, and characterizing multimodality of link fraud.

The techniques described in this thesis span various disciplines including data mining, machine learning, network and social sciences and information theory and are practically applicable to a number of real-world fraud and general anomaly detection scenarios.  They are carefully designed to attain high precision and recall in practice and scale to massive datasets, including social networks, telecommunication networks, e-commerce and collaboration networks with up to millions of nodes and billions of edges.

Thesis Committee:
Christos Faloutsos (Chair)
Roni Rosenfeld
Jaime Carbonell
Jiawei Han (University of Illinois at Urbana-Champaign)

For More Information, Contact:


Thesis Oral