2011 Poster Sessions : Matching Noisy Graphs Using Heat Kernel Signatures

Student Name : Nan Hu
Advisor : Leo Guibas
Research Areas: Graphics/HCI
We consider the problem of matching two anonymous networks that share all their nodes but whose edge sets differ, albeit only slightly. We aim to identify the nodes in these two graphs such that the graph topologies are mostly aligned. The problem is a variant of the well-studied graph isomorphism problem and there are a range of potential applications and uses in social network analysis, from assessing the possibility for unification of social activity information of users across different online social platforms to detecting who is who in two networks that capture communication patterns of terrorists. The solution we propose is an informative graph signature on each node, defined as the \emph{heat kernel signature (HKS)}, that describes the role of a node relative to other nodes in the graph topology. The HKS is naturally multi-scale and captures global network structural information beyond immediate neighborhoods. By matching nodes in two graphs with similar HKS, we develop a practical algorithm to identify nodes in two graphs with similar topology. Analytically we demonstrate the continuity of HKS under small graph perturbations. Our experimental results on both randomly generated graphs and a real world paper citation network favor the solution over several other candidate methods.

Nan is a PhD student from Electrical Engineering department working with Professor Leo Guibas. He is interested in the design and analysis of algorithms on graphs representing real-life data. He got his Bachelor's degree from Peking University, China and M.S. degree from University of Kentucky.