<div dir="ltr"><blockquote type="cite"><div><div style="text-align:center;font-size:10pt"><img size="92065" alt="The University of Chicago, Department of Statistics" id="gmail-m_4768070729990697872CAD6AC1-7E2A-4B5C-97A4-2269CC1C8594" src="cid:f25ca310-e3a2-43a1-ad0a-cacf091e47d2" class="gmail-CToWUd gmail-a6T" tabindex="0" style="cursor: pointer; outline: 0px; font-size: 10pt;"><br></div><div style="font-family:Helvetica;font-size:14px"><div style="font-family:Arial,Helvetica,sans-serif;font-size:10pt;margin:0px;text-align:center"><br></div><div style="margin:0px;text-align:center"><div style="margin:0in;font-size:12pt;font-family:Calibri,sans-serif"><b><span style="margin:0px;padding:0in;border:1pt none windowtext;font-family:Arial,sans-serif"></span></b></div><div style="margin:0in;font-size:12pt"><b><font face="Arial, sans-serif"><b><b style="font-family:Arial,Helvetica,sans-serif">Statistics Colloquium</b></b></font></b></div><b><span style="margin:0px;padding:0in;border:1pt none windowtext;font-size:14pt;font-family:Arial,sans-serif"><span style="margin:0px;font-size:12pt"></span></span></b><p style="margin-top:0px;margin-bottom:0px"></p><p align="center" style="margin:0in 0in 3pt;font-size:12pt;font-family:Calibri,sans-serif"><b><span style="margin:0px;font-family:Arial,sans-serif"><br></span><span style="margin:0px;font-family:Arial,sans-serif">YIHONG WU</span></b><span style="margin:0px;font-size:14pt;font-family:Arial,sans-serif"><span style="margin:0px;font-size:12pt"><b> </b></span></span></p><p align="center" style="margin:0in 0in 12pt;font-size:12pt;font-family:Calibri,sans-serif"><span style="margin:0px;font-size:10pt;font-family:Arial,sans-serif">Department of Statistics<br>Yale University </span></p><div style="margin:0in;font-size:12pt;font-family:Calibri,sans-serif"><span style="margin:0px;font-family:Arial,sans-serif">“</span><span style="margin:0px;font-size:14pt;font-family:Arial,sans-serif"><span style="margin:0px;font-size:12pt;color:rgb(32,31,30)">Spectral Graph Matching: Theory and Algorithms”</span><span style="margin:0px;font-size:12pt"> </span></span></div><p align="center" style="margin:0in;font-size:12pt;font-family:Calibri,sans-serif"><span style="margin:0px;font-size:16pt;font-family:Arial,sans-serif"><span style="margin:0px;font-size:12pt"> </span></span></p><div style="margin:0in;font-size:12pt;font-family:Calibri,sans-serif"><span style="margin:0px;font-family:Arial,sans-serif">MONDAY, February 14, 2022, at 4:30 PM</span><span style="margin:0px;font-size:14pt;font-family:Arial,sans-serif"><span style="margin:0px;font-size:12pt"> </span></span></div><div style="margin:0in;font-size:12pt;font-family:Calibri,sans-serif"><span style="margin:0px;font-size:11pt;font-family:Arial,sans-serif"><b>In-Person</b>, John Crerar Library, Room 390</span></div><div style="margin:0in"><font face="Arial, sans-serif"><span style="font-size:14.6667px"><b>and</b></span></font><span style="font-size:11pt;font-family:Arial,sans-serif"> via Zoom</span><span style="font-size:12pt;font-family:Arial,sans-serif"><span style="font-size:11pt"> </span></span></div><p align="center" style="margin:0in;font-size:12pt;font-family:Calibri,sans-serif"><span style="margin:0px;font-family:Arial,sans-serif"><span style="margin:0px;font-size:11pt"></span></span></p><blockquote type="cite" style="font-size:15px;color:rgb(32,31,30)"><div style="margin:0px"><div dir="ltr" style="margin:0px"><div style="margin:0px"><div><b>Zoom Info</b></div><div><span style="font-family:Arial,Helvetica,sans-serif"><a href="https://urldefense.com/v3/__https://uchicago.zoom.us/j/93503971966?pwd=WTZuc3c4Ui9YUHA1UVlhT0R1cWlmdz09__;!!BpyFHLRN4TMTrA!rf3hw6IFZJAecdv4kyuWPmPtXy3Lrg3wbOHk0uXxfcV2tlRlA2uN_FSBPodvyNr8CBw$" title="https://uchicago.zoom.us/j/93503971966?pwd=WTZuc3c4Ui9YUHA1UVlhT0R1cWlmdz09" target="_blank">https://uchicago.zoom.us/j/93503971966?pwd=WTZuc3c4Ui9YUHA1UVlhT0R1cWlmdz09</a></span></div><span style="font-family:Arial,Helvetica,sans-serif"><div>Meeting ID: 935 0397 1966,   Passcode: stats2022</div></span></div></div></div></blockquote><p style="margin-top:0px;margin-bottom:0px"></p><p align="center" style="margin:12pt 0in;font-size:12pt;font-family:Calibri,sans-serif"><span style="margin:0px;font-family:Arial,sans-serif">ABSTRACT</span><span style="margin:0px;font-size:14pt;font-family:Arial,sans-serif"><span style="margin:0px;font-size:12pt"> </span></span></p><p style="margin:0in"></p><div style="font-size:12pt;margin:0px;font-family:Calibri,sans-serif"><span style="margin:0px;font-size:10pt;font-family:Arial,Helvetica,sans-serif;color:rgb(32,31,30)">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.</span></div><div style="margin:0px"><font color="#201f1e" face="Arial, sans-serif"><span style="margin:0px;font-size:14.6667px"><br></span></font></div><span style="font-size:11pt;margin:0px;font-family:Arial,sans-serif;color:rgb(32,31,30)"><div style="margin:0px"><span style="margin:0px;font-size:10pt;font-family:Arial,Helvetica,sans-serif">Based on joint work with Zhou Fan (Yale), Cheng Mao (Georgia Tech), Jiaming Xu (Duke), and Sophie Yu (Duke) available at </span><span style="margin:0px;font-size:12pt"><a href="https://urldefense.com/v3/__https://arxiv.org/abs/1907.08880__;!!BpyFHLRN4TMTrA!rf3hw6IFZJAecdv4kyuWPmPtXy3Lrg3wbOHk0uXxfcV2tlRlA2uN_FSBPodvfZSeLqk$" target="_blank" style="margin:0px"><span style="margin:0px;padding:0in;border:1pt none windowtext;font-size:10pt;font-family:Arial,Helvetica,sans-serif">https://arxiv.org/abs/1907.08880</span></a></span><span style="margin:0px;font-size:10pt;font-family:Arial,Helvetica,sans-serif">, </span><span style="margin:0px;font-size:12pt"><a href="https://urldefense.com/v3/__https:/arxiv.org/abs/1907.08883__;!!BpyFHLRN4TMTrA!qBgE2WtquD_vYQIrukahL12KpSj-qd8lkq4ESr5MBluwPfZQDBPSTp9CcE0vPI9_bz4$" target="_blank" style="margin:0px"><span style="margin:0px;padding:0in;border:1pt none windowtext;font-size:10pt;font-family:Arial,Helvetica,sans-serif">https://arxiv.org/abs/1907.08883</span></a></span><span style="margin:0px;font-size:10pt;font-family:Arial,Helvetica,sans-serif">, </span><span style="margin:0px;font-size:12pt"><a href="https://urldefense.com/v3/__https:/arxiv.org/abs/2008.10097__;!!BpyFHLRN4TMTrA!qBgE2WtquD_vYQIrukahL12KpSj-qd8lkq4ESr5MBluwPfZQDBPSTp9CcE0v1NjBW5s$" target="_blank" style="margin:0px"><span style="margin:0px;padding:0in;border:1pt none windowtext;font-size:10pt;font-family:Arial,Helvetica,sans-serif">https://arxiv.org/abs/2008.10097</span></a></span><span style="margin:0px;font-size:10pt;font-family:Arial,Helvetica,sans-serif">, </span><span style="margin:0px;font-size:12pt"><a href="https://urldefense.com/v3/__https:/arxiv.org/abs/2110.11816__;!!BpyFHLRN4TMTrA!qBgE2WtquD_vYQIrukahL12KpSj-qd8lkq4ESr5MBluwPfZQDBPSTp9CcE0vBt0bOag$" target="_blank" style="margin:0px"><span style="margin:0px;padding:0in;border:1pt none windowtext;font-size:10pt;font-family:Arial,Helvetica,sans-serif">https://arxiv.org/abs/2110.11816</span></a></span><span style="margin:0px;font-size:10pt;font-family:Arial,Helvetica,sans-serif">.</span></div></span><div style="margin:0px"><font color="#201f1e" face="Arial, sans-serif"><span style="margin:0px;font-size:14.6667px"><br></span></font></div><span style="font-size:11pt;margin:0px;font-family:Arial,sans-serif;color:rgb(32,31,30)"><div style="margin:0px"><b><span style="margin:0px;font-size:10pt;font-family:Arial,Helvetica,sans-serif">Bio:</span></b><span style="margin:0px;font-size:10pt;font-family:Arial,Helvetica,sans-serif"> 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.</span><span style="margin:0px"><span style="margin:0px;font-size:10pt;font-family:Arial,Helvetica,sans-serif"> </span></span></div></span></div></div></div></blockquote><br clear="all"><div><br></div>-- <br><div dir="ltr" class="gmail_signature" data-smartmail="gmail_signature"><div dir="ltr"><div><div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr"><i style="font-size:12.8px">Rob Mitchum</i></div><div dir="ltr"><i>Associate Director of Communications for Data Science and Computing<br></i><div style="font-size:12.8px"><i style="font-size:12.8px">University of Chicago</i><br></div><div style="font-size:12.8px"><i style="font-size:12.8px"><a href="mailto:rmitchum@ci.uchicago.edu" target="_blank">rmitchum@uchicago.edu</a></i><br></div><div style="font-size:12.8px"><i style="font-size:12.8px">773-484-9890</i><br></div></div></div></div></div></div></div></div></div>