297 citations · 781 across the 21 of their papers we have counts for
6 papers · 1 filter
Spectral Inference Methods on Sparse Graphs: Theory and Applications
Alaa Saade
In an era of unprecedented deluge of (mostly unstructured) data, graphs are proving more and more useful, across the sciences, as a flexible abstraction to capture complex relation…
Spectral Bounds for the Ising Ferromagnet on an Arbitrary Given Graph
Alaa Saade, Florent Krzakala, Lenka Zdeborová
We revisit classical bounds of M. E. Fisher on the ferromagnetic Ising model, and show how to efficiently use them on an arbitrary given graph to rigorously upper-bound the partiti…
Matrix Completion from Fewer Entries: Spectral Detectability and Rank Estimation
Alaa Saade, Florent Krzakala, Lenka Zdeborová
The completion of low rank matrices from few entries is a task with many practical applications. We consider here two aspects of this problem: detectability, i.e. the ability to es…
Computational Complexity, Phase Transitions, and Message-Passing for Community Detection
Aurélien Decelle, Janina Hüttel, Alaa Saade +1
We take a whirlwind tour of problems and techniques at the boundary of computer science and statistical physics. We start with a brief description of P, NP, and NP-completeness. We…
Spectral Clustering of Graphs with the Bethe Hessian
Alaa Saade, Florent Krzakala, Lenka Zdeborová
Spectral clustering is a standard approach to label nodes on a graph by studying the (largest or lowest) eigenvalues of a symmetric real matrix such as e.g. the adjacency or the La…
Spectral density of the non-backtracking operator
Alaa Saade, Florent Krzakala, Lenka Zdeborová
The non-backtracking operator was recently shown to provide a significant improvement when used for spectral clustering of sparse networks. In this paper we analyze its spectral de…