Spectral embeddings of sparse directed networks

Orateur: Simon COSTE
Localisation: INRIA, France
Type: Séminaire de probabilités et statistiques
Site: UGE , 4B 125
Date de début: 16/02/2021 - 10:30
Date de fin: 16/02/2021 - 11:30

We study the task of clustering in directed networks. We show that 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 down to the very sparse regime where the edge density has constant order. Our analysis is based on a Master Theorem describing sharp asymptotics for isolated eigenvalues/eigenvectors of sparse, non-symmetric matrices with independent entries. We also describe the limiting distribution of the entries of these eigenvectors; in the task of digraph clustering, we provide numerical evidence for the superiority of Gaussian Mixture clustering over the widely used k-means algorithm.