SDM’12 tutorial: Discovering Roles and Anomalies in Graphs: Theory and Applications

Description

Given a graph, how can we find suspicious nodes? How can we automatically discover roles for nodes? Roles are compact summaries of a node’s behavior that generalize across networks. For example, one role could be ‘star’ – with a star node being both influential and having a low neighborhood overlap. Are there good features that we extract for nodes that indicate role-membership? What are the different applications in which these discovered roles can be effectively used? The objective of this tutorial is to provide a concise and intuitive overview of the most important concepts and tools, which can detect roles (or functions) for nodes in both static and dynamic graphs. We review the state of the art in three related fields: (a) community discovery, (b) equivalences (from sociology), and (c) propositionalisation (from multi-relational data mining). The emphasis of this tutorial is to give the intuition behind these powerful mathematical concepts and tools, which are usually lost in the various technical literatures, as well as to give case studies that illustrate their practical use.

Foils

• Part 1
• Part 2
  

Outline of the Tutorial

•

Part 1: Theory [Eliassi-Rad, 60 minutes]

• what are roles
• roles and communities
• roles and equivalences (from sociology)
• roles and propositionalisation (from multi-relational data mining)

•

Part 2: Patterns and Anomaly detection [Faloutsos, 60 minutes]•

• Patterns in large graphs: Beyond six-degrees
• ‘OddBall’ for structural anomalies
• Temporal patterns and anomalies
• Application: Fraud detection
  

Who Should Attend

Researchers that want to get up to speed with theories and applications for discovering roles and anomalies in graphs. Also, practitioners who want a concise, intuitive overview of the state of the art.

Prerequisites

None. The emphasis is on the intuition behind all the formal concepts and tools.

Presenters’ Bios

• Tina Eliassi-Rad is an Assistant Professor of Computer Science at Rutgers University. She earned her Ph.D. in Computer Sciences at the University of Wisconsin-Madison. Prior to joining Rutgers, Tina was a Member of Technical Staff at Lawrence Livermore National Laboratory. Broadly speaking, her research interests include data mining, machine learning, and artificial intelligence. Tina’s work has been applied to the World-Wide Web, large- scale scientific simulation data, complex networks, and cyber situational awareness. Tina is an action editor for the Data Mining and Knowledge Discovery Journal. In 2010, she received an Outstanding Mentor Award from the US DOE Office of Science.
• Christos Faloutsos is a Professor at Carnegie Mellon University. He has received the Research Contributions Award in ICDM 2006, the Innovations award in KDD’10, 18 “best paper” awards, and several teaching awards. He has given over 30 tutorials and over 10 invited distinguished lectures. His research interests include data mining for graphs and streams, fractals, and database performance.