Node similarity, Graph Similarity and Matching: Theory and Applications
Presenters:
Danai Koutra, Carnegie Mellon University, [email protected]
Tina Eliassi-Rad, Rutgers University, [email protected]
Christos Faloutsos, Carnegie Mellon University, [email protected]
Tutorial Website:
http://www.cs.cmu.edu/~dkoutra/tut/sdm14.html
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 e ciently 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.
