KRAFTY: Khatri-Rao Framework for Joint Cluster Recovery
Siyi Gao, Zachary Lubberts, Marianna Pensky · 2026
Read KRAFTY: Khatri-Rao Framework for Joint Cluster Recovery by Siyi Gao, Zachary Lubberts, Marianna Pensky (2026) 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-2603-04608.txt.
Introduction
Gao and colleagues recover joint clusters across views with KRAFTY. Many datasets describe the same entities from complementary angles, like brain scans over time. Clustering each view alone misses shared structure, and each view mixes joint clusters, showing only part of the picture. KRAFTY models this setting in a space of enough dimension that each joint cluster fills its own orthogonal subspace. A sharp scree plot drop then marks the true joint cluster count, easing model choice. Simulations show KRAFTY wins when joint clusters outnumber per-view cluster sums.
Catalog record
| CREATOR | Siyi Gao, Zachary Lubberts, Marianna Pensky |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 106821 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2603.04608
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
KRAFTY: Khatri-Rao Framework for Joint Cluster Recovery Siyi Gao, Zachary Lubberts, Marianna Pensky Abstract When multiple datasets describe complementary information about the same set of entities, for example, brain scans of an individual over time, global trade network across years, or user information across social media platforms, integrating these snapshots allows us to see a more holistic picture. A common way of identifying structure in data is through clustering, but while clustering may be applied to each dataset separately, we learn more in the multi-view setting by identifying joint clusters. We consider a clustering problem where each view conflates some of these joint clusters, only revealing partial information, and seek to recover the true joint cluster structure. We introduce this multi-view clustering model and a method for recovering it: the transposed Khatri–RAo Framework for joinT cluster recoverY (KRAFTY). The model is flexible and can accommodate a variety of data-generating processes, including latent positions in random dot product graphs and Gaussian mixtures. A key advantage of KRAFTY is that it represents joint clusters in a space with sufficient dimension so that each joint cluster occupies an orthogonal subspace in the transposed Khatri-Rao matrix, which results in a sharp drop in the scree plot at the true number of joint clusters, enabling easy model selection. Our simulations show that when the number of joint clusters exceeds the sum of the numbers of clusters in each individual view, our method outperforms existing methods in both joint clustering accuracy and estimation of the number of joint clusters. keywords Community detection; Khatri-Rao product; Multi-view clustering 1 Introduction 1.1 Background and Motivation Community detection and clustering are core tasks in statistics and machine learning Jaeger & Banks 2023 ; Milligan & Cooper 1987 ; Abbe 2023 ; Fortunato & Newman 2022 . Clustering analysis is defined as partitioning objects into groups (clusters) so that within-group similarity is high and between-group similarity is low; similarity may be defined by network connectivity, feature-space distances, or other affinities Jaeger & Banks 2023 ; Milligan & Cooper 1987 ; von Luxburg 2007 . Cluster analysis has been applied to data in several modern applications, such as genetic profiles Toh & Horimoto 2002 and social-network snapshots Handcock et al. 2007 , to uncover meaningful latent patterns, and numerous techniques have been developed for single-dataset clustering Jaeger & Banks 2023 ; Milligan & Cooper 1987 ; von Luxburg 2007 ; Jin et al. 2023 . Early work in the multi-view setting focused on recovery of a single, consistent clustering across sources Abbe 2023 ; Fortunato & Newman 2022 ; Jin et al. 2023 . More recently, multi-view clustering has gained attention Yang & Wang 2018 ; Vallès-Català et al. 2016 as many applications provide datasets from different sources or views, and joint clustering can yield a more informative partition. There has also been a growing interest in studying differences between subspaces across networks or clusterings MacDonald et al. 2021 ; Gallagher et al. 2021 ; Arroyo et al. 2020 ; Agterberg et al. 2025 , leading to numerous multi-view spectral clustering approaches Jing et al. 2021 ; Lei & Lin 2023 . A common multi-view spectral approach concatenates the per-view spectral embeddings and then performs a second spectral decomposition followed by clustering, called Multiple Adjacency Spectral Embedding ( MASE ) in Arroyo et al. 2020 . Such approaches have two drawbacks. First, rank deficiency: each view’s embedding dimension is typically set to its own number of clusters, so concatenation yields a space of dimension at most the sum of per-view cluster counts, whereas the true number of joint clusters can be as large as the product across views. Second, determining the number of joint clusters: these methods usually lack an explicit estimator for the joint number of clusters, relying instead on an “elbow” in the scree plot, which may be ambiguous. To address these challenges, our study introduces the transposed Khatri-Rao product framework, which provides sufficient rank for estimating the number of joint clusters and achieves strong performance in both estimating the number of joint clusters and joint clustering. 1.2 Notations For a positive integer n , we denote [n]=\{1,\dots,n\} . We denote by \mathcal{O}_{r,k} the set of r\times k matrices with orthonormal columns, where \mathcal{O}_{r}=\mathcal{O}_{r,r} . We denote the set of clustering matrices that partition n objects into K clusters by \mathcal{C}_{n,K} . Here, \mathcal{C}_{n,K} consists of n\times K binary matrices where each row has one value 1 and the rest are zeros. We denote the i -th row and the j -th column of a matrix A by, respectively, A(i,:) and A(:,j) . We denote the identity matrix of order m by I_{m} . We denote the matrix of K left singular vectors of matrix X by \mbox{SVD}_{K}(X) . We denote the Frobenius, spectral, and 2\rightarrow\infty matrix norms by, respectively, \|\cdot\|_{F},\|\cdot\| and \|\cdot\|_{2,\infty} , where \|A\|_{2,\infty}=\displaystyle\max_{i}\|A(i,:)\| . We denote the Hadamard and the Kronecker products of matrices A and B by, respectively, A\circ B and A\otimes B . For matrices A\in\mathbb{R}^{n\times m} and B\in\mathbb{R}^{n\times q} with the same number of rows, we define the transposed-Khatri-Rao product as A\tkr B\in\mathbb{R}^{n\times mq} , where for i\in[n], (A\tkr B)(i,:)=A(i,:)\otimes B(i,:)=[A(i,1)B(i,:)\,|\cdots|\,A(i,m)B(i,:)]. Some properties of this product are provided in Appendix A.6 . We use C_{\tau} for a generic constant that depends on \tau only and can take different values throughout the paper. 1.3 The Model In this paper, we consider the common scenario where data are obtained from V sources (views). Each of these V views is associated with a clustering assignment z_{v}:\ [n]\to K_{v} with associated clustering matrix Z_{v}\in\{0,1\}^{n\times K_{v}} , where K_{v} is the number of clusters in view v\in[V] . These clustering assignments may have any joint configuration. Our goal is to recover the joint clustering assignment function z:[n]\to[K] or associated clustering matrix Z\in\{0,1\}^{n\times K} that describes the joint configuration of clusters. To make this precise, let the total number of clusters K in the joint assignment be a value \max_{v\in[V]}\,K_{v}\leq K\leq\prod_{v}K_{v}, (1) and let Z\in\{0,1\}^{n\times K} be the true joint clustering matrix, which has exactly one nonzero entry in each row. The individual clustering matrices Z_{v}=ZP_{v} , where P_{v}\in\{0,1\}^{K\times K_{v}} has at least one nonzero entry in each column, and exactly one nonzero entry in each row. This ensures that all of the individual clusterings are consistent with the joint clustering, but may combine some of the joint clusters together. Typically, all views will have fewer clusters individually than the true number of joint clusters. In what follows, we assume that V is small and data consist of either view-specific estimated clustering matrices \widehat{Z}_{v}\in\mathcal{C}_{n,K_{v}} , v\in[V] , or estimated matrices of singular vectors \widehat{U}_{v}\in\mathcal{O}_{n,K_{v}} , v\in[V] , that can be used for clustering. We make no additional assumptions on the sources of the data, however, a common scenario would be the results of k -means applied to the V different views. While the problem initially seems easy, in reality, it is not. Consider a simple situation where V=2 . Let K_{1}=K_{2}=3 , let n be large, and let clusters in both views be generated uniformly at random with probability 1/3 . Then, the clustering assignments z_{1} and z_{2} are independent and the combined clustering consists of K_{1}\times K_{2}=9 groups of