[Colloquium] TODAY 4:30: Stats Colloquium -- Yihong Wu (Yale), “Spectral Graph Matching: Theory and Algorithms”

[Rob Mitchum]

[image: The University of Chicago, Department of Statistics]

*Statistics Colloquium*


*YIHONG WU*

Department of Statistics
Yale University
“Spectral Graph Matching: Theory and Algorithms”


MONDAY, February 14, 2022, at 4:30 PM
*In-Person*, John Crerar Library, Room 390
*and* via Zoom

*Zoom Info*
https://uchicago.zoom.us/j/93503971966?pwd=WTZuc3c4Ui9YUHA1UVlhT0R1cWlmdz09
<https://urldefense.com/v3/__https://uchicago.zoom.us/j/93503971966?pwd=WTZuc3c4Ui9YUHA1UVlhT0R1cWlmdz09__;!!BpyFHLRN4TMTrA!rf3hw6IFZJAecdv4kyuWPmPtXy3Lrg3wbOHk0uXxfcV2tlRlA2uN_FSBPodvyNr8CBw$>
Meeting ID: 935 0397 1966,   Passcode: stats2022

ABSTRACT

Graph matching aims at finding the vertex correspondence that maximally
aligns the edge sets of two given graphs. This task amounts to solving a
computationally intractable quadratic assignment problem (QAP). We propose
a new spectral method, which computes the eigendecomposition of the two
adjacency matrices and returns a matching based on the pairwise alignments
between all eigenvectors of the first graph with all eigenvectors of the
second. Each alignment is inversely weighted by the gap between the
corresponding eigenvalues. This spectral method can be equivalently viewed
as solving a regularized quadratic programming relaxation of the QAP. We
show that, for a correlated Erdos-Renyi model with average degree at least
polylog(n), this method finds the exact matching with high probability if
the two graphs differ by at most a 1/polylog(n) fraction of edges. The
proposed algorithm matches the state of the art of polynomial-time
algorithms based on combinatorial ideas, and exponentially improves the
performance of existing spectral methods that only compare top eigenvectors
or eigenvectors of the same order. The analysis exploits local laws for the
resolvents of sparse Wigner matrices. The superiority of this new spectral
method is also demonstrated on a variety of datasets, in terms of both
matching accuracy and computational efficiency. Finally, we discuss various
open questions in the context of statistical and computational limits of
this problem.

Based on joint work with Zhou Fan (Yale), Cheng Mao (Georgia Tech), Jiaming
Xu (Duke), and Sophie Yu (Duke) available at
https://arxiv.org/abs/1907.08880
<https://urldefense.com/v3/__https://arxiv.org/abs/1907.08880__;!!BpyFHLRN4TMTrA!rf3hw6IFZJAecdv4kyuWPmPtXy3Lrg3wbOHk0uXxfcV2tlRlA2uN_FSBPodvfZSeLqk$>
, https://arxiv.org/abs/1907.08883
<https://urldefense.com/v3/__https:/arxiv.org/abs/1907.08883__;!!BpyFHLRN4TMTrA!qBgE2WtquD_vYQIrukahL12KpSj-qd8lkq4ESr5MBluwPfZQDBPSTp9CcE0vPI9_bz4$>
, https://arxiv.org/abs/2008.10097
<https://urldefense.com/v3/__https:/arxiv.org/abs/2008.10097__;!!BpyFHLRN4TMTrA!qBgE2WtquD_vYQIrukahL12KpSj-qd8lkq4ESr5MBluwPfZQDBPSTp9CcE0v1NjBW5s$>
, https://arxiv.org/abs/2110.11816
<https://urldefense.com/v3/__https:/arxiv.org/abs/2110.11816__;!!BpyFHLRN4TMTrA!qBgE2WtquD_vYQIrukahL12KpSj-qd8lkq4ESr5MBluwPfZQDBPSTp9CcE0vBt0bOag$>
.

*Bio:* Yihong Wu is an associate professor in the Department of Statistics
and Data Science at Yale University. He received his B.E. degree from
Tsinghua University in 2006 and Ph.D. from Princeton University in 2011. He
is a recipient of the NSF CAREER award in 2017 and Sloan fellowship in
Mathematics in 2018. He is broadly interested in the theoretical and
algorithmic aspects of high-dimensional statistics, information theory, and
optimization.



-- 
*Rob Mitchum*

*Associate Director of Communications for Data Science and Computing*
*University of Chicago*
*rmitchum at uchicago.edu <rmitchum at ci.uchicago.edu>*
*773-484-9890*
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20220214/b1f24032/attachment-0001.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: image.png
Type: image/png
Size: 69780 bytes
Desc: not available
URL: <http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20220214/b1f24032/attachment-0001.png>