# Estimating Mixed Memberships with Sharp Eigenvector Deviations

arXiv: https://arxiv.org/abs/1709.00407 · HTML: https://mlsanity.com/paper/1709.00407/

## Key facts

- Cited by 22 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 1 Sep 2017.

## Built on by (most cited first, 22 of 22)

- [Source Localization of Graph Diffusion via Variational Autoencoders for Graph Inverse Problems](https://mlsanity.com/paper/2206.12327/) (2022)
- [Community detection for weighted bipartite networks](https://mlsanity.com/paper/2109.10319/) (2021)
- [Estimating Higher-Order Mixed Memberships via the ℓ2,∞ Tensor Perturbation Bound](https://mlsanity.com/paper/2212.08642/) (2022)
- [Bipartite mixed membership distribution-free model. A novel model for community detection in overlapping bipartite weighted networks](https://mlsanity.com/paper/2211.00912/) (2022)
- [A useful criterion on studying consistent estimation in community detection](https://mlsanity.com/paper/2109.14950/) (2021)
- [Community detection by spectral methods in multi-layer networks](https://mlsanity.com/paper/2403.12540/) (2024)
- [Identifiable Shared Component Analysis of Unpaired Multimodal Mixtures](https://mlsanity.com/paper/2409.19422/) (2024)
- [On the Robustness of the Successive Projection Algorithm](https://mlsanity.com/paper/2411.16195/) (2024)
- [Beyond Sin-Squared Error: Linear-Time Entrywise Uncertainty Quantification for Streaming PCA](https://mlsanity.com/paper/2506.12655/) (2025)
- [Directed mixed membership stochastic blockmodel](https://mlsanity.com/paper/2101.02307/) (2021)
- [Directed degree corrected mixed membership model and estimating community memberships in directed networks](https://mlsanity.com/paper/2109.07826/) (2021)
- [Mixed membership distribution-free model](https://mlsanity.com/paper/2112.04389/) (2021)
- [Mixed membership estimation for categorical data with weighted responses](https://mlsanity.com/paper/2310.10989/) (2023)
- [Overlapping and nonoverlapping models](https://mlsanity.com/paper/2111.01392/) (2021)
- [Entrywise Recovery Guarantees for Sparse PCA via Sparsistent Algorithms](https://mlsanity.com/paper/2202.04061/) (2022)
- [Controllability of Coarsely Measured Networked Linear Dynamical Systems (Extended Version)](https://mlsanity.com/paper/2206.10569/) (2022)
- [Estimating mixed memberships in multi-layer networks](https://mlsanity.com/paper/2404.03916/) (2024)
- [Entrywise error bounds for low-rank approximations of kernel matrices](https://mlsanity.com/paper/2405.14494/) (2024)
- [Generalized Grade-of-Membership Estimation for High-dimensional Locally Dependent Data](https://mlsanity.com/paper/2412.19796/) (2024)
- [Fast exact recovery of noisy matrix from few entries: the infinity norm approach](https://mlsanity.com/paper/2501.19224/) (2025)
- [Global Optimization on Graph-Structured Data via Gaussian Processes with Spectral Representations](https://mlsanity.com/paper/2511.07734/) (2025)
- [Mixed Membership sub-Gaussian Models](https://mlsanity.com/paper/2604.22633/) (2026)

## Abstract (arXiv)

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.