Consistent spectral clustering in sparse tensor block models

Ian Välimaa, Lasse Leskelä · 2025

Read Consistent spectral clustering in sparse tensor block models by Ian Välimaa, Lasse Leskelä (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2501-13820.txt.

Introduction

Ian Valimaa and Lasse Leskela set out a block model for sparse multiway data and a grouping method that provably works when data are thin. Multiway data show up in gene work, product advice, and social network study, but they are sparse and large. Their work came out in twenty twenty-five.

The model fits whole number tensors with few entries. The grouping method adds a trimming step to cut noise swings, and the authors find a density line above which it stays correct. Noise is framed in a way that allows heavier tails than the usual case. The model class stays closed when modes are merged, which lets them weigh signal loss against noise cuts.

Catalog record

CREATORIan Välimaa, Lasse Leskelä
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE147 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2501-13820

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Consistent spectral clustering in sparse tensor block models Ian Välimaa, Lasse Leskelä Abstract High-order clustering aims to classify objects in multiway datasets that are prevalent in various fields such as bioinformatics, recommendation systems, and social network analysis. Such data are often sparse and high-dimensional, posing significant statistical and computational challenges. This paper introduces a tensor block model specifically designed for sparse integer-valued data tensors. We propose a simple spectral clustering algorithm augmented with a trimming step to mitigate noise fluctuations, and identify a density threshold that ensures the algorithm’s consistency. Our approach models sparsity using a sub-Poisson noise concentration framework, accommodating heavier than sub-Gaussian tails. Remarkably, this natural class of tensor block models is closed under aggregation across arbitrary modes. Consequently, we obtain a comprehensive framework for evaluating the tradeoff between signal loss and noise reduction incurred by aggregating data. The analysis is based on a novel concentration bound for sparse random Gram matrices. The theoretical findings are illustrated through numerical experiments. \mydate 1 Introduction 1.1 Background Multiway clustering refers to the statistical problem of analyzing an array of size n_{1}\times\cdots\times n_{d} by grouping similar elements along one or more of its d modes. Such arrays arise in many applications, including multi-tissue gene expression data where arrays have modes corresponding to individuals, genes, and tissues [ 30 , 43 , 52 ] ; recommendation systems, where user–item interactions include additional modes for context [ 9 , 35 ] ; and computer vision, where multiway relationships among pixels, features, and object parts help capture complex visual patterns [ 1 , 3 ] . In many of these settings, the observed data consist of nonnegative integers, with entries representing count data such as gene transcript abundances and interaction frequencies. To study such settings, we focus on tensor block models for count-valued arrays. A canonical example is a d -way array \mathcal{Y}\in\mathbb{Z}_{\geq 0}^{n\times\cdots\times n} in which the entries \mathcal{Y}(i_{1},\dots,i_{d}) are Poisson distributed with mean \rho\mathcal{S}_{z(i_{1})\dots z(i_{d})} . Here z\colon\{1,\dots,n\}\to\{1,\dots,r\} denotes the cluster membership vector, \rho>0 is a scaling parameter controlling sparsity, and \mathcal{S}\in[0,1]^{r\times\cdots\times r} is a d -way core tensor characterizing how cluster memberships affect interactions. This framework generalizes the d -uniform hypergraph stochastic block model (HSBM) [ 24 ] from binary data to integer-valued count data. The aim is to recover the cluster membership vector z from the observed data tensor, identifying clusters up to permutation of labels. Sparsity is modeled by letting \rho\to 0 as n\to\infty , while keeping the core tensor \mathcal{S} fixed. The key theoretical objective is to identify critical thresholds of \rho that separate the regimes in which consistent recovery is statistically possible from those in which it is also computationally tractable. In regular d -uniform HSBM models, the information-theoretic consistency threshold is \rho\asymp n^{-(d-1)}, (1.1) meaning that no algorithm can recover the clusters better than random guessing when \rho\ll n^{-(d-1)} [ 27 , 44 , 45 ] , whereas consistent clustering is possible when \rho\gg n^{-(d-1)} [ 19 ] . More importantly, polynomial-time clustering algorithms have been shown to achieve consistency in sparse regimes with \rho\gg n^{-(d-1)} [ 12 , 19 , 25 ] . Moreover, exact recovery of clusters is known to be achievable when \rho exceeds the threshold ( 1.1 ) by a logarithmic factor [ 2 , 23 , 33 , 54 ] . These advances suggest that there is no statistical–computational gap in clustering sparse uniform hypergraphs. However, all of the aforementioned polynomial-time algorithms rely on aggregating the observed data tensor into a matrix with entries A_{ij}\ =\ \sum_{i_{3},\dots,i_{d}}\mathcal{Y}_{iji_{3}\dots i_{d}}. The analytical accuracy guarantees for such algorithms essentially require that the population-level aggregate matrix \mathbb{E}A is sufficiently informative for cluster identification. For d -uniform HSBMs with a core tensor of form \mathcal{S}_{z(i_{1})\dots z(i_{d})}\ =\ \begin{cases}a,&\quad z(i_{1})=\cdots=z(i_{d}),\\ b,&\quad\text{else},\end{cases} aggregation does not cause information loss at the population level, and, in regimes relevant for exact recovery, not even at the sample level [ 8 ] . However, for more general core tensors \mathcal{S} , aggregation may result in information loss, rendering clustering based on the aggregate data matrix impossible. When the cluster membership vector z is not identifiable from \mathbb{E}A , aggregation-based methods break down. An alternative reduction from tensors to matrices is flattening, a key component of low-rank tensor approximation methods such as higher-order singular value decomposition (HOSVD) [ 16 ] and higher-order orthogonal iteration (HOOI) [ 17 ] . Unlike aggregation, flattening preserves all the information. Ke, Shi, and Xia [ 32 ] investigated flattening-based methods for a degree-corrected block model for hypergraphs. They established consistency above a density threshold \rho\asymp n^{-d/2}\log^{1/2}n. (1.2) While this threshold is significantly above the information-theoretic limit ( 1.1 ), it is widely believed to be close to the optimal computational threshold for polynomial-time algorithms. Indeed, Kunisky [ 34 ] recently showed that no low coordinate degree algorithm can detect the community structure below \rho\asymp n^{-d/2}D(n)^{-(d-2)/2} , where D(n) is conjectured to correspond to \omega(\log n) for polynomial-time algorithms. Despite these advances, theoretical understanding of clustering Poisson and other count-valued data in tensors remains limited. Poisson distributions have heavier tails than sub-Gaussian ones, and thus require different tools for concentration analysis. Yet Poisson models are natural in many applications, including ecology (species count per site [ 13 ] ) and political science (vote count per polling station [ 14 ] ). Because sub-Poisson tail behavior is stable under aggregation, it provides a natural and robust assumption for modeling counts. Moreover, the sub-Poisson class is broad, encompassing both Bernoulli and Poisson distributions. 1.2 Main contributions The main contributions of this paper are the following. First, we propose a polynomial-time clustering method that avoids aggregation altogether. It flattens the data tensor into a matrix and then computes a hollow Gram matrix followed by spectral decomposition. This sidesteps the problem of an uninformative adjacency matrix. Unlike most previous methods, we include a trimming step to remove high-degree nodes. Second, by developing a new concentration inequality for integer-valued Gram matrices, we prove that consistent clustering is possible in polynomial time when \rho\gg n^{-d/2}. (1.3) Notably, this matches the computational lower bound in [ 34 ] up to logarithmic factors and sharpens the threshold ( 1.2 ) by removing the logarithmic factor. This suggests a nearly optimal algorithm for this class of problems. Third, we extend the stochastic block modeling framework from binary to integer-valued data tensors. This is enabled by applying concentration bounds that exploit the sub-Poisson tail via Bennett’s inequality [ 40 ] . This becomes particularly useful when aggregating the data to a lower-order tensor, because it preserves sub-Poisson tails. Moreover, our algorithm supports mode-specific clustering with varying dimensions and cluster structures across modes, and our analysis establishes recovery guarantees in this general multiway setting. For n_{1}\times\dots\times n_{d} -dimensional arrays, the critical threshold ( 1.3 ) then generalizes to \rho\gg(n_{1}\cdots n_{d})^{-1/2}. (1.4) 1.3 Related work Flattening-based multiway clustering methods have been studied in several recent works under closely related models. Particular instances are temporal and multilayer networks, modeled as binary arrays of dimensions n\times n\times t , where t corresponds to the number of layers or time slots [ 2 , 5 , 6 , 39 , 42 ] . In this setting, Lei and Lin [ 37 ] established

Read the complete text