  Tensor clustering, which seeks to extract underlying cluster structures from
noisy tensor observations, has gained increasing attention. One extensively
studied model for tensor clustering is the tensor block model, which postulates
the existence of clustering structures along each mode and has found broad
applications in areas like multi-tissue gene expression analysis and multilayer
network analysis. However, currently available computationally feasible methods
for tensor clustering either are limited to handling i.i.d. sub-Gaussian noise
or suffer from suboptimal statistical performance, which restrains their
utility in applications that have to deal with heteroskedastic data and/or low
signal-to-noise-ratio (SNR).
  To overcome these challenges, we propose a two-stage method, named
$\mathsf{High\text{-}order~HeteroClustering}$ ($\mathsf{HHC}$), which starts by
performing tensor subspace estimation via a novel spectral algorithm called
$\mathsf{Thresholded~Deflated\text{-}HeteroPCA}$, followed by approximate
$k$-means to obtain cluster nodes. Encouragingly, our algorithm provably
achieves exact clustering as long as the SNR exceeds the computational limit
(ignoring logarithmic factors); here, the SNR refers to the ratio of the
pairwise disparity between nodes to the noise level, and the computational
limit indicates the lowest SNR that enables exact clustering with polynomial
runtime. Comprehensive simulation and real-data experiments suggest that our
algorithm outperforms existing algorithms across various settings, delivering
more reliable clustering performance.
