# Graph powering and spectral robustness

arXiv: https://arxiv.org/abs/1809.04818 · HTML: https://mlsanity.com/paper/1809.04818/

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 13 Sep 2018.

## Built on by (most cited first, 10 of 10)

- [Topological Relational Learning on Graphs](https://mlsanity.com/paper/2110.15529/) (2021)
- [Spectral clustering in the Gaussian mixture block model](https://mlsanity.com/paper/2305.00979/) (2023)
- [Reaching Kesten-Stigum Threshold in the Stochastic Block Model under Node Corruptions](https://mlsanity.com/paper/2305.10227/) (2023)
- [Sparse random hypergraphs: Non-backtracking spectra and community detection](https://mlsanity.com/paper/2203.07346/) (2022)
- [Community detection with the Bethe-Hessian](https://mlsanity.com/paper/2411.02835/) (2024)
- [A simpler spectral approach for clustering in directed networks](https://mlsanity.com/paper/2102.03188/) (2021)
- [Spectral Robustness for Correlation Clustering Reconstruction in Semi-Adversarial Models](https://mlsanity.com/paper/2108.04729/) (2021)
- [On the Robustness of Spectral Algorithms for Semirandom Stochastic Block Models](https://mlsanity.com/paper/2412.14315/) (2024)
- [Semi-Supervised Clustering of Sparse Graphs: Crossing the Information-Theoretic Threshold](https://mlsanity.com/paper/2205.11677/) (2022)
- [SubSearch: Robust Estimation and Outlier Detection for Stochastic Block Models via Subgraph Search](https://mlsanity.com/paper/2506.03657/) (2025)

## Abstract (arXiv)

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 ≥1), 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 ErdHos-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 citemassoulie-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 citemassoulie-STOC,MosselSBM2,bordenave,colin3. This is illustrated on a geometric block model that is dense in cliques.