# Estimating Higher-Order Mixed Memberships via the ℓ2,∞ Tensor Perturbation Bound

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Builds on 22 of its 37 references that are in the map.
- First posted on arXiv 16 Dec 2022.

## Builds on (most cited first, 22 of 22)

- [Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview](https://mlsanity.com/paper/1809.09573/) (2018)
- [Spectral Methods for Data Science: A Statistical Perspective](https://mlsanity.com/paper/2012.08496/) (2020)
- [Implicit Regularization in Nonconvex Statistical Estimation: Gradient Descent Converges Linearly for Phase Retrieval, Matrix Completion, and Blind Deconvolution](https://mlsanity.com/paper/1711.10467/) (2017)
- [Tensor SVD: Statistical and Computational Limits](https://mlsanity.com/paper/1703.02724/) (2017)
- [Optimality of Spectral Clustering in the Gaussian Mixture Model](https://mlsanity.com/paper/1911.00538/) (2019)
- [Nonconvex Low-Rank Tensor Completion from Noisy Data](https://mlsanity.com/paper/1911.04436/) (2019)
- [Layer aggregation and reducibility of multilayer interconnected networks](https://mlsanity.com/paper/1405.0425/) (2014)
- [Heteroskedastic PCA: Algorithm, Optimality, and Applications](https://mlsanity.com/paper/1810.08316/) (2018)
- [Near-optimal bounds for phase synchronization](https://mlsanity.com/paper/1703.06605/) (2017)
- [Community Detection on Mixture Multi-layer Networks via Regularized Tensor Decomposition](https://mlsanity.com/paper/2002.04457/) (2020)
- [Tensor Clustering with Planted Structures: Statistical Optimality and Computational Limits](https://mlsanity.com/paper/2005.10743/) (2020)
- [Community Detection for Hypergraph Networks via Regularized Tensor Power Iteration](https://mlsanity.com/paper/1909.06503/) (2019)
- [Exact Clustering in Tensor Block Model: Statistical Optimality and Computational Limit](https://mlsanity.com/paper/2012.09996/) (2020)
- [Estimating Mixed Memberships with Sharp Eigenvector Deviations](https://mlsanity.com/paper/1709.00407/) (2017)
- [Mixed Membership Estimation for Social Networks](https://mlsanity.com/paper/1708.07852/) (2017)
- [Inference for Heteroskedastic PCA with Missing Data](https://mlsanity.com/paper/2107.12365/) (2021)
- [Multiway clustering via tensor block models](https://mlsanity.com/paper/1906.03807/) (2019)
- [Leave-one-out Singular Subspace Perturbation Analysis for Spectral Clustering](https://mlsanity.com/paper/2205.14855/) (2022)
- [Entrywise Estimation of Singular Vectors of Low-Rank Matrices with Heteroskedasticity and Dependence](https://mlsanity.com/paper/2105.13346/) (2021)
- [Incoherent Tensor Norms and Their Applications in Higher Order Tensor Completion](https://mlsanity.com/paper/1606.03504/) (2016)
- [A Sharp Blockwise Tensor Perturbation Bound for Orthogonal Iteration](https://mlsanity.com/paper/2008.02437/) (2020)
- [An ℓp theory of PCA and spectral clustering](https://mlsanity.com/paper/2006.14062/) (2020)

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

- [Valid Conformal Prediction for Dynamic GNNs](https://mlsanity.com/paper/2405.19230/) (2024)
- [Heteroskedastic Tensor Clustering](https://mlsanity.com/paper/2311.02306/) (2023)
- [On the Robustness of the Successive Projection Algorithm](https://mlsanity.com/paper/2411.16195/) (2024)
- [Optimal and exact recovery on the general nonuniform Hypergraph Stochastic Block Model](https://mlsanity.com/paper/2304.13139/) (2023)
- [Identifiability of Nonnegative Tucker Decompositions -- Part I: Theory](https://mlsanity.com/paper/2505.12713/) (2025)
- [Signed Diverse Multiplex Networks: Clustering and Inference](https://mlsanity.com/paper/2402.10242/) (2024)
- [Perfect Clustering in Nonuniform Hypergraphs](https://mlsanity.com/paper/2504.08980/) (2025)
- [Perfect Clustering in Very Sparse Diverse Multiplex Networks](https://mlsanity.com/paper/2507.19423/) (2025)

## Abstract (arXiv)

Higher-order multiway data is ubiquitous in machine learning and statistics and often exhibits community-like structures, where each component (node) along each different mode has a community membership associated with it. In this paper we propose the tensor mixed-membership blockmodel, a generalization of the tensor blockmodel positing that memberships need not be discrete, but instead are convex combinations of latent communities. We establish the identifiability of our model and propose a computationally efficient estimation procedure based on the higher-order orthogonal iteration algorithm (HOOI) for tensor SVD composed with a simplex corner-finding algorithm. We then demonstrate the consistency of our estimation procedure by providing a per-node error bound, which showcases the effect of higher-order structures on estimation accuracy. To prove our consistency result, we develop the ℓ2,∞ tensor perturbation bound for HOOI under independent, heteroskedastic, subgaussian noise that may be of independent interest. Our analysis uses a novel leave-one-out construction for the iterates, and our bounds depend only on spectral properties of the underlying low-rank tensor under nearly optimal signal-to-noise ratio conditions such that tensor SVD is computationally feasible. Finally, we apply our methodology to real and simulated data, demonstrating some effects not identifiable from the model with discrete community memberships.