Prof. Elza Erkip - A Communications Perspective on Graph Matching

Professor:
Elza Erkip
Institute Professor, Electrical and Computer Engineering Department
New York University
Abstract:
Consider two correlated graphs the first of which has labeled vertices, whereas the second one is unlabeled. Graph matching attempts to recover the labels of the second graph by using the correlation of the two graphs. Applications of graph matching range from web privacy, where the graphs correspond to publicly and privately available information of internet users and their interactions on the web, to image segmentation to protein networks. This talk explores how graph matching can be posed as a communications problem, and tools from information theory, communication theory and probability can be used to derive theoretical guarantees and algorithms for graph matching.