# Multiway Spherical Clustering via Degree-Corrected Tensor Block Models

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 23 of its 47 references that are in the map.
- First posted on arXiv 19 Jan 2022.

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

- [Community Detection and Stochastic Block Models](https://mlsanity.com/paper/1703.10146/) (2017)
- [Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview](https://mlsanity.com/paper/1809.09573/) (2018)
- [Statistical and Computational Guarantees of Lloyd's Algorithm and its Variants](https://mlsanity.com/paper/1612.02099/) (2016)
- [Tensor SVD: Statistical and Computational Limits](https://mlsanity.com/paper/1703.02724/) (2017)
- [Reducibility and Statistical-Computational Gaps from Secret Leakage](https://mlsanity.com/paper/2005.08099/) (2020)
- [An Optimal Statistical and Computational Framework for Generalized Tensor Estimation](https://mlsanity.com/paper/2002.11255/) (2020)
- [Square Deal: Lower Bounds and Improved Relaxations for Tensor Recovery](https://mlsanity.com/paper/1307.5870/) (2013)
- [Community Detection in Degree-Corrected Block Models](https://mlsanity.com/paper/1607.06993/) (2016)
- [Community Detection for Hypergraph Networks via Regularized Tensor Power Iteration](https://mlsanity.com/paper/1909.06503/) (2019)
- [Consistency of Spectral Hypergraph Partitioning under Planted Partition Model](https://mlsanity.com/paper/1505.01582/) (2015)
- [Exact Clustering in Tensor Block Model: Statistical Optimality and Computational Limit](https://mlsanity.com/paper/2012.09996/) (2020)
- [Stochastic Block Model for Hypergraphs: Statistical limits and a semidefinite programming approach](https://mlsanity.com/paper/1807.02884/) (2018)
- [Iterative Algorithm for Discrete Structure Recovery](https://mlsanity.com/paper/1911.01018/) (2019)
- [Hypergraph Spectral Clustering in the Weighted Stochastic Block Model](https://mlsanity.com/paper/1805.08956/) (2018)
- [Optimal Cluster Recovery in the Labeled Stochastic Block Model](https://mlsanity.com/paper/1510.05956/) (2015)
- [Multiway clustering via tensor block models](https://mlsanity.com/paper/1906.03807/) (2019)
- [Uniform Hypergraph Partitioning: Provable Tensor Methods and Sampling Techniques](https://mlsanity.com/paper/1602.06516/) (2016)
- [Provable Convex Co-clustering of Tensors](https://mlsanity.com/paper/1803.06518/) (2018)
- [Community Recovery in Hypergraphs](https://mlsanity.com/paper/1709.03670/) (2017)
- [On the Minimax Misclassification Ratio of Hypergraph Community Detection](https://mlsanity.com/paper/1802.00926/) (2018)
- [Spectral Thresholds in the Bipartite Stochastic Block Model](https://mlsanity.com/paper/1506.06737/) (2015)
- [Bayesian Network--Response Regression](https://mlsanity.com/paper/1606.00921/) (2016)
- [Supervised tensor decomposition with features on multiple modes](https://mlsanity.com/paper/1910.09499/) (2019)

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

- [Nonbacktracking spectral clustering of nonuniform hypergraphs](https://mlsanity.com/paper/2204.13586/) (2022)
- [Optimal and exact recovery on the general nonuniform Hypergraph Stochastic Block Model](https://mlsanity.com/paper/2304.13139/) (2023)
- [Degree Heterogeneity in Higher-Order Networks: Inference in the Hypergraph boldsymbolβ-Model](https://mlsanity.com/paper/2307.02818/) (2023)
- [MultiwayPAM: Multiway Partitioning Around Medoids for LLM-as-a-Judge Score Analysis](https://mlsanity.com/paper/2603.10287/) (2026)

## Abstract (arXiv)

We consider the problem of multiway clustering in the presence of unknown degree heterogeneity. Such data problems arise commonly in applications such as recommendation system, neuroimaging, community detection, and hypergraph partitions in social networks. The allowance of degree heterogeneity provides great flexibility in clustering models, but the extra complexity poses significant challenges in both statistics and computation. Here, we develop a degree-corrected tensor block model with estimation accuracy guarantees. We present the phase transition of clustering performance based on the notion of angle separability, and we characterize three signal-to-noise regimes corresponding to different statistical-computational behaviors. In particular, we demonstrate that an intrinsic statistical-to-computational gap emerges only for tensors of order three or greater. Further, we develop an efficient polynomial-time algorithm that provably achieves exact clustering under mild signal conditions. The efficacy of our procedure is demonstrated through two data applications, one on human brain connectome project, and another on Peru Legislation network dataset.