CSP Seminar

An information theoretic approach to correlated graph matching

Farhad Shirani

Research Assistant Professor
New York University
Thursday, February 08, 2018
4:00pm - 5:00pm
1005 EECS

Add to Google Calendar

About the Event

In this talk, a new framework for analyzing the matchability of pairs of correlated graphs is introduced. Given a pair of stochastically correlated graphs, the objective is to deduce the one-to-one correspondence between their vertices which is consistent with the underlying statistical correlation. Graph matching problems arise in various settings of practical interest including social network de-anonymization, study of biological data, web graphs, image processing, etc. Previous approaches to the problem often leverage the graph structure for reliable matching. In contrast, the approach presented in this talk considers the adjacency matrices of the two graphs and uses concentration of measure theorems to determine whether the two graphs can be matched reliably. This involves deriving bounds on the probability of joint typicality of permutations of sequences of pairs of random variables. We apply the framework both to seeded and seedless matching scenarios under various graph models. Our main result shows that reliable matching is contingent upon the value of the mutual information between the variables corresponding to the edge probabilities of the two graphs being greater than a critical value.


Farhad Shirani obtained his B.Sc. degree from Sharif University of Technology in 2011 and Ph.D. from the University of Michigan at Ann Arbor in 2017. He also received his M.Sc. in Applied Mathematics from the University of Michigan in 2016. Currently, he is a Research Assistant Professor at the New York University at New York. His research interests include multiterminal communication systems, coding theory, privacy and security.

Additional Information

Contact: Judi Jones

Phone: 763-8557


Sponsor(s): ECE

Faculty Sponsor: Dave Neuhoff

Open to: Public