Graph powering and spectral robustness

Combinatorics Seminar
Friday, October 12, 2018 - 3:00pm
1 hour (actually 50 minutes)
Skiles 005
Princeton University

Spectral algorithms, such as principal component analysis and spectral
clustering, typically require careful data transformations to be
effective: upon observing a matrix A, one may look at the spectrum of
ψ(A) for a properly chosen ψ. We propose a simple and generic
construction for sparse graphs based on graph powering. It is shown
that graph powering regularizes the graph and decontaminates its
spectrum in the following sense: (i) If the graph is drawn from the
sparse Erd˝os-R´enyi ensemble, which has no spectral gap, it is shown
that graph powering produces a “maximal” spectral gap, with the latter
justified by establishing an Alon-Boppana result for powered graphs;
(ii) If the graph is drawn from the sparse SBM, graph powering is
shown to achieve the fundamental limit for weak recovery.

(Joint work with E. Abbe, E. Boix, C. Sandon.)