  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.
