Estimating Higher-Order Mixed Memberships via the l2,∞ Tensor Perturbation Bound

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 article we propose the sub-Gaussian) 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 under sub-Gaussian noise, which showcases the effect of higher-order structures on estimation accuracy. To prove our consistency result, we develop the l2,∞ tensor perturbation bound for HOOI under independent, heteroscedastic, sub-Gaussian 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. Supplementary materials for this article are available online, including a standardized description of the materials available for reproducing the work.