Multiway Spherical Clustering via Degree-Corrected Tensor Block Models

Abstract

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.

References in corpus (12)

• Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview
• Square Deal: Lower Bounds and Improved Relaxations for Tensor Recovery
• Consistency of Spectral Hypergraph Partitioning under Planted Partition Model
• Hypergraph Spectral Clustering in the Weighted Stochastic Block Model
• Community Detection for Hypergraph Networks via Regularized Tensor Power Iteration
• Provable Convex Co-clustering of Tensors
• Uniform Hypergraph Partitioning: Provable Tensor Methods and Sampling Techniques
• Stochastic Block Model for Hypergraphs: Statistical limits and a semidefinite programming approach
• Bayesian Network--Response Regression
• Spectral Thresholds in the Bipartite Stochastic Block Model
• Supervised tensor decomposition with features on multiple modes
• Time-dependent community structure in legislation cosponsorship networks in the Congress of the Republic of Peru

Cited by in corpus (1)

• Optimal and exact recovery on the general nonuniform Hypergraph Stochastic Block Model