Multiway clustering via tensor block models

Miaoyan Wang, Yuchen Zeng

Introduction

In fields like genomics and social network analysis, data often arrives as tensors (higher-order arrays). For example, a gene expression tensor might track thousands of genes across hundreds of individuals and dozens of tissues. Researchers expect this data to have a hidden "block" structure—groups of genes that behave similarly in specific subsets of tissues and people.

Existing approaches usually treat this as a general low-rank estimation problem (using CP or Tucker decomposition) and then apply clustering as a second step. However, these methods don't fully exploit the underlying block-constant nature of the data. This leads to sub-optimal accuracy and a lack of "identifiability"—meaning you might find the right mathematical subspace, but you cannot easily map it back to specific clusters of individuals or genes.

This paper introduces the Tensor Block Model (TBM), a unified framework for identifying "checkerbox" structures in large, noisy multi-dimensional datasets. By directly exploiting block structures rather than just low-rankness, the authors achieve significantly faster convergence rates and more accurate multiway clustering than traditional methods.

Methods

The authors propose the Tensor Block Model (TBM), which assumes the observed tensor is a noisy version of a core tensor where entries are constant within defined blocks.

Illustration of the Tensor Block Model and its sparse variant.

Key components of the approach include:

  • Unified Least-Squares Estimation: A single framework that handles continuous, binary, and hybrid data types.
  • Alternating Optimization: A higher-order extension of the $k$-means algorithm. It iteratively updates the "core" (the average value of each block) and the "membership matrices" (which index belongs to which cluster) until convergence.
  • Sparse TBM: To handle "needle in a haystack" scenarios where only a few blocks have significant signals (elevated means), the authors introduce $\ell_0$ and $\ell_1$ (Lasso) regularizations.
  • BIC for Model Selection: They provide a Bayesian Information Criterion (BIC) specifically tuned for tensors to automatically determine the optimal number of clusters for each dimension.

Datasets

The model was evaluated using both synthetic simulations and two distinct real-world datasets:

  1. Brain Expression Data: A real-valued tensor containing ~1 million expression values across 13 brain tissues, 193 individuals, and 362 genes.
  2. Nations Data: A $14 \times 14 \times 56$ binary tensor representing 56 types of political relationships between 14 countries from 1950–1965.
  3. Synthetic Tensors: Gaussian and Bernoulli tensors used to rigorously test convergence rates and noise tolerance.

Key Insights and Results

  • Block Structure Over Low-Rankness: While a block structure implies the tensor is low-rank, the reverse isn't true. By explicitly modeling the blocks, TBM achieves a much better mean squared error (MSE) rate—specifically $O(d^{-(K-1)})$ compared to $O(d^{-1})$ for previous convex relaxation methods.
  • Simultaneous Estimation: Unlike two-step methods (decompose then cluster), TBM performs estimation and clustering in a "single shot," which improves both accuracy and interpretability.
  • Identifiability: Traditional Tucker models suffer from rotational invariance, making it hard to identify individual factors. TBM factors are identifiable up to simple label permutations, making the results much easier for scientists to interpret.
  • Consistency Guarantees: The authors mathematically prove that as the dimensions of the tensor grow, the probability of misclassifying an entry into the wrong block drops to zero.
Root mean squared error (RMSE) performance of the TBM method across different sample sizes and cluster configurations.
  • Superior Accuracy: In simulations, TBM consistently outperformed CP+k-means and Tucker+k-means in terms of both RMSE and Clustering Error Rate (CER), especially as noise levels increased.
  • Biological Relevance: On the Brain Expression data, TBM explained 85.6% of the variance (compared to 57.6% for CP+k-means). It successfully identified specific gene-tissue blocks, such as genes related to the central nervous system being over-expressed in the spinal cord.
  • Geopolitical Clustering: On the Nations data, the model naturally partitioned countries into "Eastern bloc," "Western bloc," and "Neutral" clusters based solely on their relational data.
  • Sparsity Benefits: The sparse TBM variant proved highly effective at filtering out background noise, correctly identifying "true zero" blocks with high precision.

Limitations and Future Work

  • Non-Convexity: The optimization problem is non-convex, meaning the algorithm can get stuck in local optima. The authors mitigate this by using multiple random initializations, but a more robust global optimization strategy remains an open challenge.
  • Computational Scaling: While the per-iteration cost scales linearly with the number of entries, extremely high-dimensional tensors (e.g., billions of entries) would still require significant memory and compute power.
  • Structural Constraints: The current model assumes non-overlapping blocks. Future work could explore overlapping or hierarchical block structures.
  • Incorporating Prior Knowledge: Future versions could incorporate symmetry (for social networks) or non-negativity constraints to further refine the model for specific domains.

Summary updated

Abstract

We consider the problem of identifying multiway block structure from a large noisy tensor. Such problems arise frequently in applications such as genomics, recommendation system, topic modeling, and sensor network localization. We propose a tensor block model, develop a unified least-square estimation, and obtain the theoretical accuracy guarantees for multiway clustering. The statistical convergence of the estimator is established, and we show that the associated clustering procedure achieves partition consistency. A sparse regularization is further developed for identifying important blocks with elevated means. The proposal handles a broad range of data types, including binary, continuous, and hybrid observations. Through simulation and application to two real datasets, we demonstrate the outperformance of our approach over previous methods.
BibTeX
@inproceedings{wang2019multiway,
  author = {Miaoyan Wang and Yuchen Zeng},
  title = {{Multiway clustering via tensor block models}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2019},
  url = {https://openreview.net/forum?id=ioOhZG2AUq},
}
Figure