Khatri-Rao Clustering for Data Summarization

Martino Ciaperoni; Collin Leiber; Aristides Gionis; Heikki Mannila

cs.LGFeb 17, 2026

Khatri-Rao Clustering for Data Summarization

Authors: Martino Ciaperoni, Collin Leiber, Aristides Gionis, Heikki Mannila

Organizations: Scuola Normale Superiore Pisa, Italy · Aalto University Espoo, Finland · KTH Royal Institute of Technology Digital Futures Stockholm, Sweden

Abstract

As datasets continue to grow in size and complexity, finding succinct yet accurate data summaries poses a key challenge. Centroid-based clustering, a widely adopted approach to address this challenge, finds informative summaries of datasets in terms of few prototypes, each representing a cluster in the data. Despite their wide adoption, the resulting data summaries often contain redundancies, limiting their effectiveness particularly in datasets characterized by a large number of underlying clusters. To overcome this limitation, we introduce the Khatri-Rao clustering paradigm that extends traditional centroid-based clustering to produce more succinct but equally accurate data summaries by postulating that centroids arise from the interaction of two or more succinct sets of protocentroids. We study two central approaches to centroid-based clustering, namely the well-established k-Means algorithm and the increasingly popular topic of deep clustering, under the lens of the Khatri-Rao paradigm. To this end, we introduce the Khatri-Rao k-Means algorithm and the Khatri-Rao deep clustering framework. Extensive experiments show that Khatri-Rao k-Means can strike a more favorable trade-off between succinctness and accuracy in data summarization than standard k-Means. Leveraging representation learning, the Khatri-Rao deep clustering framework offers even greater benefits, reducing even more the size of data summaries given by deep clustering while preserving their accuracy.

Figures & tables

Figure 1. stickfigures dataset. Example of two sets of $3$ protocentroids interacting additively to generate $9$ centroids.

Figure 2. For a synthetic ( Blobs ) and a real ( optdigits ) dataset, we show relative percentage changes in unsupervised clustering accuracy and parameter count for clustering solutions from algorithms based on the Khatri-Rao paradigm relative to the baseline algorithms $k$ - Means , Deep-k-Means ( DKM ) and Improved Deep Embedded Clustering ( IDEC ).

Figure 3. Diagram showing the interactions of two sets of protocentroids to generate cluster centroids.

Figure 4. Khatri-Rao-based (top) and arbitrarily-structured (bottom) synthetic data. Combining additively (

\oplus=+

) or multiplicatively (

\oplus=\times

) the first (red triangles) and second (blue triangles) sets of protocentroids yields the cluster centroids (purple diamonds). Gray lines indicate which protocentroid affects each cluster centroid.

Figure 5. Diagram summarizing the Khatri-Rao clustering paradigm in the $k$ - Means (a) and deep clustering (b) settings; in this example, $p=3$ , $n_{l}=2$ and $q=2$ . The centroid in red is obtained by aggregating the protocentroids in red.

Figure 6. Experiments using the Blobs and Classification datasets with $100$ ground truth clusters. Inertia (left) and purity (right) as a function of the cardinality $h_{1}=h_{2}$ of two sets of protocentroids. $k$ - Means $(h_{1}h_{2})$ uses $h_{1}h_{2}$ vectors to represent centroids, while all other algorithms use $h_{1}+h_{2}$ vectors.

Dataset	# Data points	# Features	# Labels	IR
MNIST	25000	784	10	1.00
Double MNIST	10000	1568	100	1.00
HAR	10299	561	6	0.72
Olivetti Faces	400	4096	40	1.00
CMU Faces	624	960	20	0.88
Symbols	1020	398	6	0.90

Table 1. Characteristics of the datasets used in the experiments. For each dataset, we report the number of data points, the number of features, the number of ground-truth clusters (# Labels) and the imbalance ratio (IR), defined as the ratio of the smallest to the largest cluster size.

Figure 7. Experiments using the Blobs and Classification datasets with $100$ ground truth clusters. Inertia as a function of the number of sets of protocentroids. Here, Khatri-Rao - $k$ - Means always uses $12$ total vectors to represent centroids. All baselines assume $h_{1}=h_{2}=6$ .

Dataset	Khatri-Rao - $k$ - Means - $+$ ( $h_{1}+h_{2}$ )				Khatri-Rao - $k$ - Means - $\times$ ( $h_{1}+h_{2}$ )				$k$ - Means ( $h_{1}+h_{2}$ )				$k$ - Means ( $h_{1}h_{2}$ )				Params
	ARI	ACC	NMI	Inertia	ARI	ACC	NMI	Inertia	ARI	ACC	NMI	Inertia	ARI	ACC	NMI	Inertia
MNIST	$0.298$	$0.436$	$0.428$	$1.05$	$0.309$	$0.435$	$0.441$	$1.07$	$0.357$	$0.515$	$0.467$	$1.05$	$0.366$	$0.515$	$0.498$	$1.00$	$0.70$
Double MNIST	$0.109$	$0.211$	$0.467$	$1.16$	$0.068$	$0.119$	$0.396$	$1.07$	$0.049$	$0.081$	$0.329$	$1.20$	$0.075$	$0.143$	$0.428$	$1.00$	$0.20$
HAR	$0.320$	$0.515$	$0.486$	$1.06$	$0.285$	$0.456$	$0.451$	$1.04$	$0.291$	$0.442$	$0.461$	$1.03$	$0.420$	$0.539$	$0.559$	$1.00$	$0.83$
Olivetti Faces	$0.248$	$0.398$	$0.664$	$1.34$	$0.239$	$0.393$	$0.643$	$1.41$	$0.181$	$0.287$	$0.565$	$1.46$	$0.456$	$0.600$	$0.790$	$1.00$	$0.33$
CMU Faces	$0.414$	$0.503$	$0.760$	$1.52$	$0.463$	$0.561$	$0.788$	$1.52$	$0.408$	$0.452$	$0.767$	$1.46$	$0.754$	$0.772$	$0.902$	$1.00$	$0.45$

Table 2. Experiments on synthetic and real-world datasets comparing Khatri-Rao -

k

- Means using the product ( Khatri-Rao -

k

- Means -

\times

) and sum ( Khatri-Rao -

k

- Means -

+

) aggregator functions with two sets of

h_{1}

and

h_{2}

protocentroids against

k

- Means (

h_{1}+h_{2}

) and

k

- Means (

h_{1}h_{2}

). For each dataset and algorithm, we report unsupervised clustering accuracy (ACC), adjusted Rand index (ARI), normalized mutual information (NMI) and inertia (normalized by dividing by the inertia of

k

- Means (

h_{1}h_{2}

)). The last column reports the ratio of the number of parameters used compared to

k

- Means (

h_{1}h_{2}

Dataset	IDEC			Khatri-Rao IDEC			DKM			Khatri-Rao DKM			Params Ratio
	ARI	ACC	NMI	ARI	ACC	NMI	ARI	ACC	NMI	ARI	ACC	NMI
MNIST	$0.616$	$0.771$	$0.682$	$0.630$	$0.746$	$0.712$	$0.574$	$0.718$	$0.693$	$0.645$	$0.788$	$0.719$	$0.74$
Double MNIST	$0.174$	$0.285$	$0.532$	$0.180$	$0.292$	$0.536$	$0.178$	$0.295$	$0.537$	$0.201$	$0.330$	$0.553$	$0.79$
HAR	$0.581$	$0.692$	$0.660$	$0.621$	$0.703$	$0.701$	$0.539$	$0.649$	$0.634$	$0.619$	$0.676$	$0.714$	$0.62$
Olivetti Faces	$0.399$	$0.517$	$0.746$	$0.371$	$0.510$	$0.734$	$0.437$	$0.570$	$0.769$	$0.387$	$0.542$	$0.736$	$0.88$
CMU Faces	$0.564$	$0.646$	$0.782$	$0.648$	$0.707$	$0.823$	$0.690$	$0.761$	$0.852$	$0.525$	$0.631$	$0.743$	$0.66$

Table 3. Experiments on synthetic and real-world datasets comparing the deep-clustering algorithms DKM and IDEC to their Khatri-Rao counterparts using the sum aggregator function. For each dataset and algorithm, we report unsupervised clustering accuracy (ACC), adjusted Rand index (ARI) and normalized mutual information (NMI). The last column reports the ratio of the number of parameters used by Khatri-Rao DKM and Khatri-Rao IDEC compared to DKM and IDEC .

Figure 8. Experiments using the Blobs dataset. Runtime in seconds (top) and peak memory usage in Mebibytes (bottom) by number of data points $n$ , number of features $m$ and number of centroids $k$ . Here, $k$ - Means $(h_{1}h_{2})$ uses $h_{1}h_{2}$ vectors to represent centroids, while all other algorithms use $h_{1}+h_{2}$ vectors. The $y$ -axis is on a logarithmic scale.

Figure 9. Comparison of Khatri-Rao - $k$ - Means with product aggregator using two sets of $h_{1}=h_{2}=6$ protocentroids with different approaches to color quantization using the same number of parameters.

Figure 10. FEMNIST dataset. Inertia against communication costs from the server to the clients (in Bytes) in a simulated federated learning environment for F $k$ M and Khatri-Rao - F $k$ M using the product aggregator.

Clustering

Clustering groups data points by shared structure, developing methods to discover, validate, and interpret groups across diverse data and constraints.

See all 345 papers

Data-Native Global Optimization for Big Data K-means Clustering
Jul 17, 2026Ravil Mussabayev, Rustam Mussabayev, Zukhra Yerdaliyeva +1Clustering Unsupervised Clustering
AI Research Lab, Satbayev University, Almaty, 050000, Kazakhstan · Laboratory for Analysis and Modeling of Information Processes, Institute of Information and Computational Technologies, Almaty, 050010, Kazakhstan
CLUBench: A Clustering Benchmark
May 28, 2026Feng Xiao, Dazhi Fu, Chris Ding +1Benchmark Design Clustering
The Chinese University of Hong Kong (Shenzhen)
Beyond Worst-Case Coreset Bounds for $k$ -Clustering via Determinantal Sampling
Sep 6, 2026Diptarka Chakraborty, Satyaki Mukherjee, Gaurav Vallabhdas Revankar +1Coreset Selection Clustering
School of Computing, National University of Singapore · Department of Mathematics, National University of Singapore · Department of Mathematics, Indian Institute of Technology Bombay

Jul 17, 2026J/K move · Enter open · S save

Data-Native Global Optimization for Big Data K-means Clustering

Ravil Mussabayev, Rustam Mussabayev, Zukhra Yerdaliyeva, Kuldeyev Nursultan

AI Research Lab, Satbayev University, Almaty, 050000, Kazakhstan · Laboratory for Analysis and Modeling of Information Processes, Institute of Information and Computational Technologies, Almaty, 050010, Kazakhstan

Clustering Unsupervised Clustering Global Optimization

Open paper AskPDF arXiv

Big data clustering remains challenging: the Minimum Sum-of-Squares Clustering (MSSC) problem underlying K-means is NP-hard, and existing methods either reach poor local minima or require prohibitive metaheuristic hybrids. We target arbitrarily tall data: a fixed feature space may contain arbitrarily many, possibly infinitely many, observations, while the algorithm accesses only finite random samples. We propose Big-means++, an algorithm achieving scalability and global-search quality by curating inputs to MSSC optimization on big data. It orchestrates local K-means refinements into a data-native global search for big data clustering. Rather than optimizing the full-data MSSC objective, Big-means++ traverses sample-induced surrogate landscapes. Each sample defines a distinct empirical MSSC approximation with a perturbed local-optimum structure, turning sample-to-sample variation into a global-search mechanism. Unlike Big-means, a flowing-incumbent strategy propagates centroid state across empirical landscapes through K-means refinements on fresh samples without rollback to a best-so-far solution. This increases mobility and favors stable, high-quality configurations across approximations of the full-data structure. A new shaking mechanism varies sample size geometrically, broadening the surrogate landscapes explored across resolution scales, accounting for cluster imbalance, and improving solution quality. A competitive multi-agent system asynchronously explores independent sampled landscapes, transforming diverse stochastic trajectories into collective search intelligence. Automatic convergence detection stops each agent after attaining a high-quality solution but before further search risks degrading it, while providing a universal speed-quality control. Experiments on 22 datasets against 11 competing algorithms demonstrate the effectiveness, efficiency, and robustness of Big-means++.

Abstract

Clustering

Explore similar work

Data-Native Global Optimization for Big Data K-means Clustering

CLUBench: A Clustering Benchmark

Beyond Worst-Case Coreset Bounds for kkk-Clustering via Determinantal Sampling

Beyond Worst-Case Coreset Bounds for $k$ -Clustering via Determinantal Sampling