Estimating Mixed Memberships With Sharp Eigenvector Deviations

DOI10.1080/01621459.2020.1751645zbMATH Open1506.62331arXiv1709.00407OpenAlexW3017845708MaRDI QIDQ5881973FDOQ5881973

Authors: Xueyu Mao, Purnamrita Sarkar, Deepayan Chakrabarti 

Publication date: 14 March 2023

Published in: Journal of the American Statistical Association (Search for Journal in Brave)

Abstract: We consider the problem of estimating community memberships of nodes in a network, where every node is associated with a vector determining its degree of membership in each community. Existing provably consistent algorithms often require strong assumptions about the population, are computationally expensive, and only provide an overall error bound for the whole community membership matrix. This paper provides uniform rates of convergence for the inferred community membership vector of each node in a network generated from the Mixed Membership Stochastic Blockmodel (MMSB); to our knowledge, this is the first work to establish per-node rates for overlapping community detection in networks. We achieve this by establishing sharp row-wise eigenvector deviation bounds for MMSB. Based on the simplex structure inherent in the eigen-decomposition of the population matrix, we build on established corner-finding algorithms from the optimization community to infer the community membership vectors. Our results hold over a broad parameter regime where the average degree only grows poly-logarithmically with the number of nodes. Using experiments with simulated and real datasets, we show that our method achieves better error with lower variability over competing methods, and processes real world networks of up to 100,000 nodes within tens of seconds.

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

Recommendations

• A tensor approach to learning mixed membership community models
• Estimating mixed-memberships using the symmetric Laplacian inverse matrix
• Overlapping community detection in networks via sparse spectral decomposition
• Mixed membership stochastic blockmodels
• Detecting overlapping communities in networks using spectral methods

zbMATH Keywords

clusteringnetworksasymptotic analysisoverlapping community detection

Mathematics Subject Classification ID

Classification and discrimination; cluster analysis (statistical aspects) (62H30) Learning and adaptive systems in artificial intelligence (68T05)

Cites Work

• Spectral clustering and the high-dimensional stochastic blockmodel
• Consistency of spectral clustering in stochastic block models
• Mixed membership stochastic blockmodels
• A useful variant of the Davis-Kahan theorem for statisticians
• Computing a nonnegative matrix factorization -- provably
• Entrywise eigenvector analysis of random matrices with low expected rank
• Exact Recovery in the Stochastic Block Model
• Improved Graph Clustering
• Numerical recipes. The art of scientific computing.
• A tensor approach to learning mixed membership community models
• A limit theorem for scaled eigenvectors of random dot product graphs
• Community discovery using nonnegative matrix factorization
• Efficient discovery of overlapping communities in massive networks
• Multidimensional binary search trees used for associative searching
• Spectral statistics of Erdős-Rényi graphs. I: Local semicircle law
• Signal-plus-noise matrix models: eigenvector deviations and fluctuations
• The two-to-infinity norm and singular subspace geometry with applications to high-dimensional statistics
• The (un)supervised NMF methods for discovering overlapping communities as well as hubs and outliers in networks
• Unperturbed: spectral analysis beyond Davis-Kahan

Cited In (11)

• Finding mixed memberships in categorical data
• Survival Mixed Membership Blockmodel
• Estimating mixed-memberships using the symmetric Laplacian inverse matrix
• A tensor approach to learning mixed membership community models
• Latent Space Modeling of Hypergraph Data
• Asymptotically efficient estimators for stochastic blockmodels: the naive MLE, the rank-constrained MLE, and the spectral estimator
• The two-to-infinity norm and singular subspace geometry with applications to high-dimensional statistics
• Entrywise limit theorems for eigenvectors of signal-plus-noise matrix models with weak signals
• Spectral Clustering via Adaptive Layer Aggregation for Multi-Layer Networks
• Assigning topics to documents by successive projections
• An \({\ell_p}\) theory of PCA and spectral clustering

This page was built for publication: Estimating Mixed Memberships With Sharp Eigenvector Deviations

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