Preprints, papers, documents

The spectral point of view on large networks

I study spectral properties of random objects like graphs and matrices, and their application to statistical inference problems. The use of low-dimensional spectral embeddings has proven to be a fruitful method in such problems as matrix completion, community detection, graph alignment, etc. I recently got into spectral convolutions in graph neural networks.

The spectral gap of sparse random digraphs

Arxiv link – published in Annales de l'IHP.

I prove an asymptotic upper bound for the second eigenvalue of the transition matrix of the simple random walk, over a random directed graph with given degree sequence. An immediate consequence of this result is a proof of the Alon conjecture for directed regular graphs. The proof is based on a variation of the trace method introduced by Bordenave (2015).

Emergence of extended states in random graphs

Joint work with Justin Salez.

Arxiv link – published in Annals of Probability.

We confirm the long-standing prediction that c=e2.718c=e \approx 2.718 is the threshold for the emergence of a non-vanishing absolutely continuous part (extended states) at zero in the limiting spectrum of the Erdös-Renyi random graph with average degree cc.

Detection thresholds in very sparse matrix completion

Joint work with Charles Bordenave and Raj Rao Nadakuditi.

Arxiv link – submitted.

We completely describe the extremal elements in the eigendecomposition of some very sparse matrices, with a new and efficient point of view regarding the problem of matrix completion in the very hard regime. We show how non-symmetric matrices can sometimes be quite beneficial in such regimes.

A simpler spectral approach for clustering directed networks

Joint work with Ludovic Stephan.

Arxiv link – submitted.

We prove spectral asymptotics for very sparse inhomogeneous random matrices, as well as limits for eigenvector distributions. We apply these results to clustering in sparse, directed networks and we show that the simplest method based on the eigenvectors of the adjacency matrix provably works well. We provide numerical evidence for the superiority of Gaussian mixture against Kmeans when doing the last step of the spectral clustering pipeline..

Eigenvalues of the non-backtracking operator detached from the bulk

Joint work with Yizhe Zhu.

Arxiv link – Published in Random Matrix Theory and Applications.

This is a note on "bulk insider" eigenvalues for the non-backtracking spectrum of SBM. We prove their existence in the ω(logn)\omega(\log n) regime, which partially answers a question of Dall'Amico et al 2019. The existence is still not proved in the sparse regime (feb. 2021).

The characteristic polynomial of sparse matrices seen from infinity

Following the recent paper of Bordenave, Chafaï and Garcia-Zelada, I show that when AnA_n is a random n×nn\times n matrix with all n2n^2 entries independent random variables with distribution Bernoulli(d/n)\mathrm{Bernoulli}(d/n) and d>1d>1 is fixed while nn \to \infty, then the random polynomial qn(InzAn)q_n(I_n - zA_n) converges weakly in distribution towards a random analytic function on D(0,1/d)D(0, 1/\sqrt{d}).

This entails a short proof for the asymptotics of the high eigenvalues of sparse directed Erdos-Réniy matrices.

Work in preparation (April 11, 2021).

I'm working on the same thing for random directed regular graphs.

Other works

Order and fluctuations in point processes

In parallel, I'm interested in the rigidites of random point processes, such as number-rigidities, fluctuations reductions, hyperuniformity, and the possible links between these notions. There are different ways in which point processes in Rd\mathbb{R}^d can exhibit a stronger order than the totally chaotic Poisson process; hyperuniformity is when the (random) number of points NrN_r falling in a large domain BrB_r of radius rr has a reduced variance, that is, when

limrVar(Nr)Vol(Br)=0. \lim_{r \to \infty} \frac{\mathrm{Var}(N_r)}{\mathrm{Vol}(B_r)} = 0.

In this survey, I try to give a mathematical overview of this rich domain. Topics: the Fourier caracterization of hyperuniformity, the fluctuation scale, the links with number-rigidity and maximal rigidity for stealthy processes, the example of pertubed lattices.

Here is a version of this survey. It's still work in progress.

Hyperuniformity survey (april 2021)

A note on a generalization of the Erdos-Gallai Theorem

Joint work with Charles Bordenave.

Arxiv link – Published in Journal of Combinatorial Theory (series B).

This is a short note on a generalization of the Erdös-Gallai theorem on graphical sequences.