  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 $\psi(A)$ for a
properly chosen $\psi$. The issue is that the spectrum of $A$ might be
contaminated by non-informational top eigenvalues, e.g., due to scale`
variations in the data, and the application of $\psi$ aims to remove these.
  Designing a good functional $\psi$ (and establishing what good means) is
often challenging and model dependent. This paper proposes a simple and generic
construction for sparse graphs, $$\psi(A) = \1((I+A)^r \ge1),$$ where $A$
denotes the adjacency matrix and $r$ is an integer (less than the graph
diameter). This produces a graph connecting vertices from the original graph
that are within distance $r$, and is referred to as 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\H{o}s-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 (the KS threshold) similarly to \cite{massoulie-STOC},
settling an open problem therein. Further, graph powering is shown to be
significantly more robust to tangles and cliques than previous spectral
algorithms based on self-avoiding or nonbacktracking walk counts
\cite{massoulie-STOC,Mossel_SBM2,bordenave,colin3}. This is illustrated on a
geometric block model that is dense in cliques.
