Abstract

Given a graph how can we find similarities among its nodes? Given a sequence of graphs, can we spot similarities or differences between them and detect temporal anomalies? How can we match the nodes in different graphs in order to reveal similarities between them? In a microscopic level, the nodes can be similar in terms of their proximity or their structural features and roles. In a macroscopic level, two graphs are similar if the structures within them are similar, or equivalently their nodes are connected in similar ways. How can we find the similarity between two graphs when the node correspondence is known or unknown? When the correspondence is unknown, how can we efficiently match the two graphs, i.e., infer the node mapping? The objective of this tutorial is to provide a concise and intuitive overview of the most important concepts and tools, which can detect similarities between nodes of a static graph and different snapshots of dynamic graphs or distinct networks.

We review the state of the art in three related fields: (a) node similarity and role discovery, (b) graph similarity, and (c) graph matching. The emphasis of this tutorial is to give the intuition behind these powerful mathematical concepts and tools, as well as case studies that illustrate their practical use in data mining.

Slides

Part 1a     Part 1b     Part 2a     Part 2b

Outline

• [Part 1a] Node similarity: Roles [45 minutes]
  • What are roles
  • Roles and communities
  • Roles and equivalences (from sociology)
  • Roles (from data mining)
• [Part 1b] Node similarity: Proximity [25 minutes]
  • Graph-theoretic Approaches
  • Effective Conductance
  • Guilt-by-association techniques (RWR, BP,SSL)
  • Applications
• [Part 2a] Graph Similarity with known node correspondence [25 minutes]
  • Simple features
  • Complex features
  • Visualization
• [Part 2b] Graph Similarity with UNknown node correspondence [25 minutes]
  • Unipartite graphs (methods avoiding or solving the node correspondence problem)
  • Bipartite graphs
  • Challenges, and heuristics

Presenters' bios

Danai Koutra is a Ph.D. student at the Computer Science Department at Carnegie Mellon University. She earned her diploma in ECE at the National Technical University of Athens. Her research interests include large-scale graph mining, graph similarity and matching, graph summarization, and anomaly detection. Danai's research has been applied mainly to social, collaboration and web networks, as well as brain connectivity graphs. She holds 7 patents on bipartite graph alignment.

Tina Eliassi-Rad is an Associate Professor of Computer Science at Rutgers University. She earned her Ph.D. from the University of Wisconsin-Madison. Within data mining and machine learning, Tina's research has been applied to the World-Wide Web, text corpora, large-scale scientific simulation data, complex networks, and cyber situational awareness. She has given over 80 invited presentations. 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.