BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Memento EPFL//
BEGIN:VEVENT
SUMMARY:Spectral graph matching and regularized quadratic relaxations
DTSTART:20200303T163000
DTEND:20200303T173000
DTSTAMP:20260408T005655Z
UID:bb6bc941149739dbfaaaef60abe1ff5e49f84bfa8d1e5768b41b8c07
CATEGORIES:Conferences - Seminars
DESCRIPTION:Prof. Yihong Wu Associate Professor of Statistics and Data Sci
 ence\nYale University more info\nAbstract:\nGraph matching aims at finding
  the vertex correspondence that maximally aligns the edge sets of two give
 n graphs. This task amounts to solving a computationally intractable quadr
 atic assignment problem (QAP). We propose a new spectral method\, which co
 mputes 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 inverse
 ly weighted by the gap between the corresponding eigenvalues. This spectra
 l method can be equivalently viewed as solving a regularized quadratic pro
 gramming relaxation of the QAP. We show that for a correlated Erdos-Renyi 
 model\, this method finds the exact matching with high probability if the 
 two graphs differ by at most a 1/polylog(n) fraction of edges\, both for d
 ense graphs and for sparse graphs with at least polylog(n) average degree.
  The proposed algorithm matches the state of the art of polynomial-time al
 gorithms based on combinatorial ideas\, and exponentially improves the per
 formance of existing spectral methods that only compare top eigenvectors o
 r eigenvectors of the same order. The analysis exploits local laws for the
  resolvents of sparse Wigner matrices. The superiority of this new spectra
 l method is also demonstrated on a variety of datasets\, in terms of both
  matching accuracy and computational efficiency.\n\nBased on joint work wi
 th Zhou Fan (Yale)\, Cheng Mao (Georgia Tech)\, and Jiaming Xu (Duke). Pre
 prints available at https://arxiv.org/abs/1907.08880 and https://arxiv.org
 /abs/1907.08883.\n\n 
LOCATION:INR 113 https://plan.epfl.ch/?room==INR%20113
STATUS:CONFIRMED
END:VEVENT
END:VCALENDAR