Graph powering and spectral robustness

DOI10.1137/19M1257135MaRDI QIDQ5027021zbMATH OpenOpenAlexFDO

Authors Emmanuel Abbe, Enric Boix-Adserà, Peter Ralli, Colin Sandon

Publication date 3 February 2022

Published in SIAM Journal on Mathematics of Data Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1809.04818

zbMATH Keywords

community detectionnetwork data analysisrandom graphsspectral algorithmsspectral embeddingsstochastic block models

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Bayesian inference (62F15) Robustness and adaptive procedures (parametric inference) (62F35) Inference from stochastic processes and spectral analysis (62M15)

Abstract: 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, ${\displaystyle }$psi(A) = 1((I+A)^r ge1),${\displaystyle }$ 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 ErdH{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.

Recommendations

• Graph partitioning via adaptive spectral techniques
• Spectra of random graphs with given expected degrees
• Spectral concentration and greedy k-clustering
• Spectral redemption in clustering sparse networks
• Analysis of spectral clustering algorithms for community detection: the general bipartite setting

Cites work

• A proof of alon's second eigenvalue conjecture
• A proof of the block model threshold conjecture
• A Simple SVD Algorithm for Finding Hidden Partitions
• Approximating the exponential, the lanczos method and an Õ(m)-time spectral algorithm for balanced separator
• Community detection and stochastic block models
• Community detection in sparse networks via Grothendieck's inequality
• Community detection on Euclidean random graphs
• Community detection thresholds and the weak Ramanujan property
• Expander graphs and their applications
• Faster algorithms via approximation theory
• From frequency to meaning: vector space models of semantics
• Fundamental limits of weak recovery with applications to phase retrieval
• Graph partitioning via adaptive spectral techniques
• Graph sparsification by effective resistances
• Group synchronization on grids
• How robust are reconstruction thresholds for community detection?
• Impact of regularization on spectral clustering
• Large deviations for the graph distance in supercritical continuum percolation
• Mixture models, robustness, and sum of squares proofs
• On the second eigenvalue of a graph
• Phase transitions in semidefinite relaxations
• Proof of the achievability conjectures for the general stochastic block model
• Ramanujan graphs
• Random Geometric Graphs
• Robust estimators in high-dimensions without the computational intractability
• Robust moment estimation and improved clustering via sum of squares
• Semidefinite programs on sparse random graphs and their application to community detection
• Small subgraphs of random regular graphs
• Spectral redemption in clustering sparse networks
• The Rotation of Eigenvectors by a Perturbation. III
• What are zeta functions of graphs and what are they good for?

Cited in

(8)

• Rate optimal Chernoff bound and application to community detection in the stochastic block models
• Eigenvalues of the non-backtracking operator detached from the bulk
• scientific article; zbMATH DE number 7626708 (Why is no real title available?)
• scientific article; zbMATH DE number 7626779 (Why is no real title available?)
• Community detection in the sparse hypergraph stochastic block model
• Learning sparse graphons and the generalized Kesten-Stigum threshold
• Sparse random hypergraphs: non-backtracking spectra and community detection
• Semi-supervised clustering of sparse graphs: crossing the information-theoretic threshold

This page was built for publication: Graph powering and spectral robustness

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5027021)