IFDS Wisc RA Rungang Han, in joint work with IFDS RA Yuetian Luo and Affiliates Anru Zhang and Miaoyan Wang, has been awarded a Best Student Paper Award from the Statistical Learning and Data Science Section of the American Statistical Association for the paper “Exact Clustering in Tensor Block Model: Statistical Optimality and Computational Limit.” Rungang will present the paper in August at the Joint Statistical Meetings (JSM) 2021: https://community.amstat.org/slds/awards/student-paper-award
This paper develops an efficient and statistically optimal two-stage algorithm for multi-way high-order clustering motivated by multi-tissue gene expression analysis and dynamic network analysis. High-order clustering aims to identify heterogeneous substructure in the multiway datasets that arise commonly in neuroimaging, genomics, and social network studies. The non-convex and discontinuous nature of the problem poses significant challenges in both statistics and computation. This work proposes a tensor block model and the computationally efficient methods, high-order Lloyd algorithm and high-order spectral clustering, for high-order clustering in the tensor block model. The convergence of the proposed procedure is established, and their method is proved to achieve exact clustering under some mild assumptions. This work also gives the complete characterization for the statistical-computational trade-off in high-order clustering based on three different signal-to-noise ratio regimes. The proposed procedures are evaluated via extensive experiments on both synthetic datasets and real data examples in the flight route network and online click-through prediction.