Publications and preprints

You can also find a list of my publications on my Google Scholar page.

Extremal eigenvalues of random graphs

I studied the spectral properties of several random graph models. In the very sparse case, where the average degrees are constant, it is known that the spectrum of the adjacency matrix does not reflect the underlying properties of the model. However, the extremal eigenvalues, and their associated eigenvectors of other matrices (such as the non-backtracking matrix BB) associated to the graph still allow to recover information about the model.

Robustness of spectral methods for community detection

Joint work with Laurent Massoulié

Published in COLT 2019 - Article link - Slides - Poster

A common drawback of spectral methods in community detection is their sensivity to noise: they rely on the tree-like and tangle-free properties of the stochastic block model, which are easily destroyed by adding very few edges. To remedy this problem, we introduce a spectral method based on the distance matrix D()D^{(\ell)}. We show that for carefully chosen \ell, our algorithm achieves non-trivial reconstruction in the SBM, and is robust to a perturbation of at most O(nϵ)O(n^\epsilon) edges for a deterministic ϵ>0\epsilon > 0. We also extend the range of spectral algorithms to cover the case of repeated eigenvalues of the signal matrix.

Non-backtracking spectra of weighted inhomogeneous random graphs

Joint work with Laurent Massoulié

Submitted - arXiv link

We study a model of random weighted graphs, where the only requirement is the pairwise independence of the edges. Under mild conditions on the expected adjacency matrix QQ, we show that the top eigenvalues of QQ (above a certain deterministic threshold) are reflected in the spectrum of the non-backtracking matrix BB. We also provide an asymptotic expansion for the scalar products between the eigenvectors of BB and a lifted version of those of QQ. This result has several applications in inference problems, including several variants of community detection as well as (noisy) matrix completion.

A simpler spectral approach for clustering in directed networks

Joint work with Simon Coste.

Submitted - arXiv link

We show that, when clustering directed networks, using the eigenvalue/eigenvector decomposition of the adjacency matrix is simpler than all common methods which are based on a combination of data regularization and SVD truncation, and works well down to the very sparse regime where the edge density has constant order. We also describe the limiting distribution of the entries of these eigenvectors; in the task of digraph clustering with spectral embeddings, we provide numerical evidence for the superiority of Gaussian Mixture clustering over the widely used k-means algorithm.

Other inference problems

I am also interested in various inference problems, especially on graphs. The main goal is often to identify easy, hard and IT-impossible phases, where the problem is either polynomially feasible, feasible but with no known polynomial algorithm, or provably impossible.

Planting trees in graphs, and finding them back

Joint work with Laurent Massoulié and Don Towsley.

Published in COLT 2019 - Article link - Slides - Poster

This paper deals with the problem of finding a copy of a tree Γ\Gamma with known shape, planted inside an Erdős-Rényi random graph with parameters (n,λ/n)(n, \lambda / n). In the case where Γ\Gamma is a path, we provide a complete phase transition diagram that depends on the value of λ\lambda; the highlight is the notable absence of hard phase, which deviates from common inference problems. We also exhibit a partial phase diagram when Γ\Gamma is a DD-ary tree with D>1D > 1, with an interesting phase transition in λ\lambda.