# Exact Clustering in Tensor Block Model: Statistical Optimality and Computational Limit

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

## Key facts

- Cited by 23 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 18 Dec 2020.

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

- [Leave-one-out Singular Subspace Perturbation Analysis for Spectral Clustering](https://mlsanity.com/paper/2205.14855/) (2022)
- [Tensor-on-Tensor Regression: Riemannian Optimization, Over-parameterization, Statistical-computational Gap, and Their Interplay](https://mlsanity.com/paper/2206.08756/) (2022)
- [Low-rank Tensor Estimation via Riemannian Gauss-Newton: Statistical Optimality and Second-Order Convergence](https://mlsanity.com/paper/2104.12031/) (2021)
- [An iterative clustering algorithm for the Contextual Stochastic Block Model with optimality guarantees](https://mlsanity.com/paper/2112.10467/) (2021)
- [ALMA: Alternating Minimization Algorithm for Clustering Mixture Multilayer Network](https://mlsanity.com/paper/2102.10226/) (2021)
- [Estimating Higher-Order Mixed Memberships via the ℓ2,∞ Tensor Perturbation Bound](https://mlsanity.com/paper/2212.08642/) (2022)
- [Deflated HeteroPCA: Overcoming the curse of ill-conditioning in heteroskedastic PCA](https://mlsanity.com/paper/2303.06198/) (2023)
- [Optimal Clustering by Lloyd Algorithm for Low-Rank Mixture Model](https://mlsanity.com/paper/2207.04600/) (2022)
- [Multiway Spherical Clustering via Degree-Corrected Tensor Block Models](https://mlsanity.com/paper/2201.07401/) (2022)
- [Sparse Subspace Clustering in Diverse Multiplex Network Model](https://mlsanity.com/paper/2206.07602/) (2022)
- [Statistical and Computational Efficiency for Smooth Tensor Estimation with Unknown Permutations](https://mlsanity.com/paper/2111.04681/) (2021)
- [Optimal and exact recovery on the general nonuniform Hypergraph Stochastic Block Model](https://mlsanity.com/paper/2304.13139/) (2023)
- [Causal Customer Churn Analysis with Low-rank Tensor Block Hazard Model](https://mlsanity.com/paper/2405.11377/) (2024)
- [Mode-wise Principal Subspace Pursuit and Matrix Spiked Covariance Model](https://mlsanity.com/paper/2307.00575/) (2023)
- [Signed Diverse Multiplex Networks: Clustering and Inference](https://mlsanity.com/paper/2402.10242/) (2024)
- [Tensor Methods in High Dimensional Data Analysis: Opportunities and Challenges](https://mlsanity.com/paper/2405.18412/) (2024)
- [MultiwayPAM: Multiway Partitioning Around Medoids for LLM-as-a-Judge Score Analysis](https://mlsanity.com/paper/2603.10287/) (2026)
- [Statistical and computational rates in high rank tensor estimation](https://mlsanity.com/paper/2304.04043/) (2023)
- [Mixture of multilayer stochastic block models for multiview clustering](https://mlsanity.com/paper/2401.04682/) (2024)
- [Computationally efficient reductions between some statistical models](https://mlsanity.com/paper/2402.07717/) (2024)
- [VEC-SBM: Optimal Community Detection with Vectorial Edges Covariates](https://mlsanity.com/paper/2402.18805/) (2024)
- [Perfect Clustering in Nonuniform Hypergraphs](https://mlsanity.com/paper/2504.08980/) (2025)
- [Simultaneous estimation of connectivity and dimensionality in samples of networks](https://mlsanity.com/paper/2508.12483/) (2025)

## Abstract (arXiv)

High-order clustering aims to identify heterogeneous substructures in multiway datasets that arise commonly in neuroimaging, genomics, social network studies, etc. The non-convex and discontinuous nature of this problem pose significant challenges in both statistics and computation. In this paper, we propose a tensor block model and the computationally efficient methods, high-order Lloyd algorithm (HLloyd), and high-order spectral clustering (HSC), for high-order clustering. The convergence guarantees and statistical optimality are established for the proposed procedure under a mild sub-Gaussian noise assumption. Under the Gaussian tensor block model, we completely characterize the statistical-computational trade-off for achieving high-order exact clustering based on three different signal-to-noise ratio regimes. The analysis relies on new techniques of high-order spectral perturbation analysis and a ``singular-value-gap-free'' error bound in tensor estimation, which are substantially different from the matrix spectral analyses in the literature. Finally, we show the merits of the proposed procedures via extensive experiments on both synthetic and real datasets.