Efficient Graph Matching: Algorithms and Theory

Departments: Electrical Engineering
Time: Thursday, March 5, 2020 - 4:00pm - 5:00pm
Type: Seminar Series
Presenter: Jiaming Xu; Assistant Professor, The Fuqua School of Business at Duke University
Room/Office: Room 107
Location:
J. Robert Mann, Jr. Engineering Student Center
10 Hillhouse Avenue
New Haven, CT 06511
United States
See map: Google Maps

Department of Electrical Engineering Seminar

Jiaming Xu
Assistant Professor
The Fuqua School of Business at Duke University

“Efficient Graph Matching: Algorithms and Theory”

Abstract: Given a pair of graphs, the problem of graph matching or network alignment refers to finding a bijection between the vertex sets so that the edge sets are maximally aligned. This is a ubiquitous problem arising in a variety of applications across diverse fields such as network privacy, computational biology, computer vision, and natural language processing. Graph matching is an instance of the notoriously difficult quadratic assignment problem (QAP), which is NP-hard to solve or to approximate.

Despite the worst-case computational hardness of QAP, I will present two computationally efficient graph matching algorithms with strong statistical performance. One is based on appropriately chosen distance statistics of the degree profiles (empirical distribution of the degrees of neighbors). The other is based on pairwise alignments between all eigenvectors of the first graph with all eigenvectors of the second, which can be equivalently viewed as solving a regularized quadratic programming relaxation of QAP. We show that for a correlated Erdos-Renyi model, both methods can return the exact matching with high probability if the two graphs differ by at most a 1/polylog(n) fraction of edges, both for dense graphs and for sparse graphs with at least polylog(n) average degree. These results significantly improve the state of the art of efficient graph matching algorithms in terms of time complexity, noise tolerance, and graph sparsity. The superiority of our methods is also demonstrated on a variety of synthetic and real datasets. Preprints available at https://arxiv.org/abs/1811.07821, https://arxiv.org/abs/1907.08880, and https://arxiv.org/abs/1907.08883.

Bio: Jiaming Xu is an assistant professor in the Fuqua School of Business at Duke University which he joined in July 2018. Before that, he was an assistant professor in the Krannert School of Management at Purdue University from August 2016 to June 2018, a research fellow with the Simons Institute for the Theory of Computing, UC Berkeley from January 2016 to June 2016, and a postdoctoral fellow with the Statistics Department, The Wharton School, University of Pennsylvania from January 2015 to December 2015. He received the Ph.D. degree from UIUC in 2014 under the supervision of Prof. Bruce Hajek, the M.S. degree from UT-Austin in 2011, and the B.E. degree from Tsinghua University in 2009, all in Electrical and Computer Engineering. His research interests include high-dimensional statistics, networks, optimization, information theory, and queueing theory.

Hosted by: Professor Leandros Tassiulas

Thursday, March 5, 2020
10 Hillhouse Ave Mann Student Center- 4:00 PM