Overview

Clustering seeks useful groupings when labels are absent or incomplete, helping reveal structure in data such as text, images, graphs, time series, and scientific measurements. Methods include centroid-based k-means, density and hierarchical clustering, graph and spectral methods, mixture models, and newer approaches that learn embeddings or use optimal transport; fairness, privacy, streaming, and federated settings add further constraints. Work also studies how to choose the number of clusters and assess stability, uncertainty, interpretability, and statistical significance. No single method works best across data types: deep methods do not consistently beat strong conventional algorithms, and reliable validation remains a central challenge.

Latest papers

370 papers29 papers in the last four weeks, down 12% on the four weeks before. 0.2% of all new papers.

Nov 13, 2026

Small Is Not Dead: Distance-Aware Cluster Revival for e-means

e-means (Bessa et al., 2026) is a recent mini-batch k-means algorithm, now part of the FAISS library, that reaches the error of Lloyd's algorithm about an order of magnitude faster on large embedding datasets. Every five mini-batches, it removes every cluster whose running point count falls below a tenth of the average and reuses its centre to split a large cluster. In the authors' ablation, removing this mechanism, called dead-cluster revival, raises the error more than removing any other component added to the moving-average update. The rule, however, considers only cluster size: it cannot distinguish a cluster that is small because it is redundant from one that covers a rare, isolated group of points, and on data with such groups it repeatedly removes centres whose removal is costly. We add a second condition, based on the distance between centres: a small cluster is removed only if its centre is close to another centre, relative to a running estimate of the mean squared error. When a centre equals the mean of its points, this squared distance is an upper bound on the average increase in squared error, per point of the cluster, caused by removing the centre. The condition costs one nearest-centre search for the small clusters every five mini-batches and adds no measurable running time. On the e-means paper's embedding benchmarks, it never prevents a removal, so the results are identical to those of FAISS. On datasets with small isolated groups not used during development, it reduces the test error after two epochs by roughly 10% to 80% relative to count-based revival, and it preserves the advantage of k-means++ initialization; on the other evaluation datasets, it stays within about 1% of the better of revival enabled and disabled. We also report two failure modes that the analysis predicts. This is a CPU proof of concept; GPU implementations are left to future work.
Nov 13, 2026

Two-Clustering Regime of Token Dynamics in Causal Attention

We partially resolve Conjecture 1 of [Karagodin et al., Clustering in Causal Attention Masking (NeurIPS 2024)] and extend it to time-dependent parameter regimes. The conjecture predicts that causal attention dynamics converge to two clusters aligned with the eigenvectors associated with the largest eigenvalue λmax⁡λ_{\max} of the value transformation. We prove that this behavior holds when λmax⁡>0λ_{\max}>0 and is generally false when λmax⁡≤0λ_{\max}\le0. The resulting two-cluster regime is common in practice and substantially more challenging than the classical single-cluster setting studied previously. A central contribution of our work is the identification of a rigorous dimension reduction phenomenon: despite evolving in a high-dimensional embedding space, token trajectories collapse onto a two-dimensional structure governed by a small number of dominant directions. Building on this insight, we introduce a new analytical framework--instability within the flow--inspired by instability phenomena in physical systems. This framework enables the analysis of steady-regime behavior in non-monotone, non-autonomous attention dynamics. Our theoretical findings are illustrated through simulations and experimental studies using Group Query Attention (GQA) layers.
Nov 13, 2026

LLM-Guided Cluster Lifecycle Management: Deciding When and How to Evolve Behavioral Clusters

Behavioral clusters learned over user or item interactions drift as behavior evolves: some fragment into sub-behaviors, some converge, some disappear, and new patterns emerge. Two paradigms dominate the maintenance of evolving clusterings. Threshold triggers fire a pre-specified action when a hardcoded statistic crosses a cutoff; refit-and-track (MONIC-style) re-clusters every window and infers transitions from how the new clusters align with the previous window's. Both hardwire the decision into a threshold or a re-clustering rule. We study an alternative in which a large language model (LLM) makes the lifecycle decision in place. Given a threshold-free, whole-population view of the current cluster set (statistical health, labels, member texts, residual mass), the LLM decides per cluster whether and how to act (split, merge, retire, create, or no-action) without re-clustering. Because the useful signal channel depends on how informative the labels are, we fix a richness-conditioned policy in advance: statistics when label distinctiveness is low, fused statistics+semantics when it is high. On three public datasets spanning label richness (YooChoose 0.17, MOOC 0.50, News-Category 0.70), the policy-selected LLM mode obtains the highest F1 on all three, with far fewer interventions and stronger restraint than tuned threshold heuristics and a MONIC steelman (paired Wilcoxon p <= 0.003, bootstrap 95% CIs excluding zero). The gain is concentrated more in precision than recall. The useful modality shifts from statistics to semantics/fusion as richness rises. Semantics hurt on YooChoose, fusion is roughly neutral on MOOC, and the semantic channel is required on News. One base prompt template and one fixed policy serve all three datasets, whereas the tuned baseline collapses when moved between them. We treat this shift as a practitioner diagnostic observed on three datasets, not a validated law.
Nov 12, 2026

Collaborative Task Allocation for Heterogeneous Multi-Robot Systems Through Iterative Clustering

Multi-robot systems face the challenge of efficiently allocating teams of heterogeneous robots to tasks. The task allocation problem is complicated by collaborative interactions between robots where teams of robots develop emergent capabilities that enable them to complete tasks that would be inefficient or impossible for individual robots. To address these challenges, we present an iterative clustering algorithm for collaborative task allocation in heterogeneous multi-robot systems. This approach partitions the computationally intractable global optimization problem into smaller, tractable subproblems by iteratively forming clusters of robots and tasks, then optimizing assignments within each cluster. By ensuring robots remain clustered with their currently assigned tasks, we guarantee monotonic improvement in overall utility with each iteration. We analyze the convergence of the algorithm and characterize how cluster size constraints determine which suboptimal assignments could trap the algorithm. In simulation, iterative clustering consistently outperforms simulated annealing, and a group-based auction in both computation time and solution quality, and outperforms a hedonic game approach in solution quality.
Nov 9, 2026

Beyond the First Hit: Towards Tight Guarantees for kk-means++

Let RkR_k be the worst-case ratio between the expected cost of the kk seeds chosen by kk-means++ and the optimal kk-means cost. In their seminal paper introducing kk-means++, Arthur and Vassilvitskii (SODA 2007) showed that 2ln⁡k≤Rk≤8(ln⁡k+2)2\ln k\le R_k\le8(\ln k+2), and Makarychev, Reddy and Shan (NeurIPS 2020) improved the upper bound to 5(ln⁡k+2)5(\ln k+2). We prove Rk≤1163233+2.108 Hk−2R_k\le\frac{1163}{233}+2.108\,H_{k-2} for every k≥3k\ge3 by a computer-assisted argument, and Rk≤5+2.3139 Hk−2R_k\le5+2.3139\,H_{k-2} for every k≥2k\ge2 by a short analytic argument; here HjH_j is the jjth harmonic number. Since Hk−2≤1+ln⁡kH_{k-2}\le1+\ln k, this lowers the leading coefficient of ln⁡k\ln k from 55 to 2.1082.108. We also determine R2=5R_2=5 and R3=185/32R_3=185/32 exactly; both are suprema that are approached but not attained. On the lower side we prove Rk≥2(1+Hk−1)R_k\ge2(1+H_{k-1}) for every kk, and give a second family of lower bounds that is larger than this for 2≤k≤182\le k\le18. Previous analyses bound the expected cost of a cluster just after it is first sampled by a constant times its optimal cost, and then charge that cost for the rest of the run. We instead track how a cluster's cost evolves after its first hit: a cluster left with a large residual cost is likely to be sampled again before it accumulates much of the logarithmic charge, and each repeat repairs it.
Nov 9, 2026

Reproducible quantum clustering for single-cell transcriptome atlases

Current single-cell clustering pipelines discard most genes and can yield inconsistent clusters across random seeds. We introduce KQE-2, a training-free hybrid quantum-classical framework for reproducible whole-transcriptome clustering. KQE-2 maps cells into entanglement-free quantum states, enabling exact feature evaluation on classical hardware and direct checks on a quantum processor. Theoretically, we prove that removing entanglement is necessary and sufficient to bound single-qubit feature variance locally. Practically, while retraining scVI shifted 14% of cells and altered rare-type markers and drug targets, KQE-2 delivered identical biology across runs. On standard highly variable genes, the quantum encoding alone raised accuracy on a developing cortex from 0.61 to 0.79. KQE-2 scales to 11.4 million nuclei on one server, outperforming the compared methods on eight of ten complete atlases (and within the best method's run-to-run range on two), and leads on six even under standard downstream clustering.
Nov 6, 2026

Coresets for Capacitated Clustering via Dual Concentration

We study coresets for clustering problems, focusing on the classical kk-median and kk-means objectives. A coreset is a small weighted summary of the input data that approximately preserves the clustering cost for every choice of centers. Such summaries are a central tool for scaling clustering algorithms to large datasets. In this work, we consider the capacitated setting, where the clustering is subject not only to choosing centers but also to respecting prescribed cluster-size constraints. This model is a natural generalization of standard clustering and has been widely studied, but its coreset complexity is less well understood. For finite metric spaces, we obtain optimal-size coresets; surprisingly, these match the best-known bounds for unconstrained clustering. We also give improved coreset bounds in Euclidean space, notably the first coresets with near-linear dependence in kk while being independent of the dimension and input size. The main new technical ingredients are concentration bounds for the dual solutions of min-cost flow problems, which allow for both significantly simpler and tighter analyses of the underlying sampling distribution used in the coreset construction.
Nov 6, 2026

e-means: outperforming k-means (in one-tenth the epochs)

Lloyd's k-means algorithm is a long-running standard for clustering, with applications in data analysis, retrieval, quantization and data curation. In this paper, we introduce an exponential moving average optimization procedure for k-means with mini-batch updates, powered by modern deep learning machinery and new insights. We also establish scaling laws on how decay rate and batch size impact final performance. This gives us a formulaic rule to fix them for multiple problem sizes and embedding datasets, without the need for any hyperparameter sweep. The resulting clustering algorithm, coined e-means, is much faster than Lloyd k-means and converges to lower losses, frequently even beating k-means++. On a wide array of embeddings datasets, it beats the loss of Lloyd k-means at 25 epochs in 1.4 to 2.6 epochs, which translates to 10-45x GPU wall-clock speedups compared to state-of-the-art k-means implementations. As an example, e-means partitions DINO10B, a dataset of 10 billion DINO embeddings, into 16 million clusters in only 2.5 epochs, reaching a loss below Lloyd's at 25 epochs.
Nov 4, 2026

Credibility Clustering for Experience Rating: An Automated Approach to Risk Group Allocation in Group Life Insurance

In insurance, experience rating plays a crucial role in mitigating adverse selection by adjusting premiums according to historical claims experience. A key step in this process is the classification of insured collectives into homogeneous risk groups. Within group life insurance, this classification traditionally relies on manual decisions and arbitrary thresholds, which may lead to inefficiencies and inconsistent outcomes. This paper proposes a data-driven methodology for automating risk group allocation based on a combination of the multidimensional Bühlmann-Straub model and k-means clustering -- referred to as credibility clustering. By incorporating credibility weights, the method accounts for the varying statistical significance of experience data and ensuresthat risk classifications are both actuarially sound and practically implementable. Empirical results based on real-world group life insurance data from a major European insurer demonstrate that the proposed framework outperforms the two k-means benchmark variants considered in the empirical application in terms of viability, temporal stability and accounting for statistical reliability.
Nov 4, 2026

Alleviating Limited Effectiveness and Multi-Class Collapse in Deep Graph-level Clustering

Given a collection of NN graphs, graph-level clustering (GLC) seeks to partition the NN graphs into semantically meaningful groups, which serves as a fundamental task in analyzing graph-structured data. While Graph Isomorphism Networks (GINs) have become the de facto encoders for GLC, they still fail to distinguish graphs due to their neglect of global topology. On top of that, existing deep clustering frameworks suffer from severe "clustering collapse" issues, particularly in imbalanced multi-class scenarios. To address these challenges, we propose S3^3GLC, a novel framework that integrates global topological characteristics with local neighborhood features for balanced GLC. Theoretically, we leverage the Hoffman-Wielandt inequality to construct Spectral Signature as a rigorous lower bound for graph edit distance (GED), providing a computationally efficient proxy for global topological features. We additionally propose a joint manifold-preserving sparse regression module to fuse Spectral Signature with Spatial Representation, eliminating noise while preserving the complementary information. Furthermore, to mitigate clustering collapse, we introduce a balanced clustering objective based on optimal transport, harnessing the Sinkhorn-Knopp normalization to enforce equipartition constraints on cluster assignments. Extensive experiments on 10 real-world datasets demonstrate that S3^3GLC significantly outperforms 15 state-of-the-art baselines, achieving remarkable improvements on benchmark datasets such as REDDIT-12K and OGBG-PPA.
Nov 4, 2026

Improved approximation algorithms for capacitated cluster editing

We study the minimum-disagreement cluster editing problem that, from a complete edge-signed graph, where a positive edge represents two vertices agreeing to each other while a negative represents a disagreement, constructs disjoint cliques of upper bounded size such that the total number of negative edges inside cliques and positive edges outside cliques is minimized. When the sizes of the candidate cliques are unbounded, the problem is NP-hard and APX-hard, and many approximation algorithms with improving ratios have been proposed in the literature and the state-of-the-art approximation ratio of α=1.3865+εα= 1.3865 + ε. The capacitated variant, in which the candidate cliques have sizes no greater than a given kk, is less studied and the best approximation ratio is 5.375.37. In this paper, we study the latter problem. We first present a downsizing procedure that achieves an approximation ratio of αk=2α+1α_k = 2 α+ 1, based on any αα-approximation algorithm for the uncapacitated problem. Secondly, we propose a hybrid of cluster-LP sampling and pivoting and show that for every fractional capacitated cluster-LP solution of cost LL, the hybrid using ordinary pivoting has an expected cost at most 95L+110\OPTk\frac 95 L + \frac 1{10} \OPT_k, and the hybrid using conditional pivoting has an expected cost at most 306203L+50203\OPTk\frac {306}{203} L + \frac {50}{203} \OPT_k. A cardinality-constrained adaptation of the approximate dual-separation framework of García-Soriano and Schohn supplies the required fractional solution and yields a randomized (1.9+ε)(1.9 + ε)-approximation algorithm and a randomized (1.7537+ε)(1.7537 + ε)-approximation algorithm, respectively.
Nov 3, 2026

VISTA: Vision-Language Integrated Semantic Triage Architecture for Online Face Clustering in Long Videos

Clustering faces by identity in long, continuous video streams is a challenging task that serves as a building block for human-centric video analysis. The majority of existing face clustering models are offline, i.e., they assume the entire data to be available altogether. In many practical scenarios, however, the entire data is either unavailable or poses computational challenges to be processed in its entirety. A handful of online methods that exist rely on geometric visual features and simple thresholding techniques, which fail when the faces exhibit significant appearance variations in long, unconstrained videos. To this end, we present VISTA, the first vision language framework for online face clustering in long videos. VISTA leverages semantic reasoning in a controlled, uncertainty aware fashion to maintain both high cluster purity and long range identity continuity. This makes it robust to the variations in illumination, pose, and costume changes that the faces and characters exhibit in long real world videos. Extensive experiments on the VPCD benchmark dataset (with 15 full episodes from The Big Bang Theory [2007-2019], Buffy the Vampire Slayer [1997-2003], and Sherlock [2010-2017]) demonstrate that VISTA achieves a robust precision and recall balance, consistently improving over the strongest matched online unsupervised baseline (COFC) under identical detector, embeddings, and evaluation protocol. Code and supplementary material: https://github.com/SkyJiashu/VISTA.
Nov 2, 2026

Embedding Semantic Entropy: NLI-Free Semantic Uncertainty Estimation with Geometry-Aware Clustering

Large Language Models (LLMs) often generate fluent yet incorrect responses, making un- certainty estimation important for reliable deployment. Semantic Entropy (SE) estimates uncertainty by clustering responses based on semantic equivalence, but it relies on hard entailment-based clustering. We propose Embedding Semantic Entropy, which replaces entailment-based clustering with K-Medoids in semantic embedding space and uses dynamic cluster selection to account for intra-cluster compactness and inter-cluster separation. We evaluate the method on TriviaQA, SQuAD, NQ-Open, SVAMP, and BioASQ using Falcon- 7B-Instruct, LLaMA-2-7B, LLaMA-2-7B-Chat, and Gemma-7B. Results show competitive AUROC and AUARC performance, suggesting that NLI-based entailment clustering can be replaced with embedding-space clustering with limited degradation while improving the inspectability of semantic grouping. This matters because semantic uncertainty scores depend on underlying semantic groups; by making these groups explicit, compact, and separable in embedding space, Emb-SE turns uncertainty estimation from a black-box en- tailment decision into an inspectable clustering problem.
Nov 2, 2026

Malware Clustering in the Wild: Taxonomy, Challenges, and Evaluation Metrics

As malware continues to grow in volume, diversity, and sophistication, clustering has emerged as a critical technique for analyzing large malware corpora. Clustering enables the discovery of structural relationships, behavioral patterns, and evolutionary trends, and is widely used to group unknown samples, infer malware family boundaries, and identify novel variants. However, existing research remains fragmented, employing a wide range of clustering techniques with no unified perspective that systematically organizes prior work or clearly identifies gaps in the literature. This survey addresses this gap by organizing previous malware clustering research into seven categories: centroid-based, hierarchical-based, density-based, distribution-based, mixed- type, fuzzy, and AI-driven approaches. In addition, this survey summarizes publicly available malware datasets commonly used in clustering research and examines the feature representations derived from these datasets. Our goal is to clarify the current landscape and outline promising avenues for future research on malware clustering, including how AI-driven methods may shape large-scale and reproducible analysis.
Nov 1, 2026

Autoencoder Based Deep Clustering of Point Clouds

Motivated by a problem in Generative Specification-Producing AIs (SPAIs), we focus on a problem of deep clustering of three-dimensional shapes specified by point clouds. After reviewing clustering and deep clustering, we study the fully unsupervised pipeline in which a FoldingNet autoencoder is first trained for reconstruction and then K-means++ is then applied to the resulting codewords. We report clustering accuracy (ACC), normalized mutual information (NMI) and adjusted Rand index (ARI) on ModelNet10 and ModelNet40 datasets, as a function of the number of clusters K. We also provide t-SNE visualizations of the codewords, and discuss the choice of K.
Oct 31, 2026

A Batched Hartigan's kk-Means Clustering

Hartigan's kk-means algorithm has theoretical advantages over the standard Lloyd's variant, which has become synonymous with "kk-means". Yet, Hartigan's algorithm is far slower in practice due to its inherently sequential calculations. We devise a Batched Hartigan's method that enables vectorized calculation by exploiting the triangle inequality to expose a set of parallel-safe updates and a smaller set of sequential updates. This makes Hartigan's method competitive with Lloyd's in execution speed for the first time.
Oct 31, 2026

Regularized Wasserstein Distance for Discrete Generative Modeling and Clustering Analysis

In this paper, we formulate clustering analysis as discrete generative modeling. Specifically, when the generator is restricted to a finite candidate space, the generated samples naturally emerge as the most representative prototypes of the underlying data distribution. To model such a discrete candidate space, we employ a Discrete Distribution Network (DDN). However, DDN suffers from unstable training due to its hard nearest-neighbor selection. To stabilize training and encourage geometric consistency, we replace DDN's l2 loss between images with regularized Wasserstein distance between the empirical distributions of real and generated images. The resulting framework, termed Discrete Generative Clustering (DGC), offers four notable advantages: 1) the learned cluster centers are directly interpretable, as they are realistic synthetic samples; 2) the inference cost scales logarithmically with the number of clusters, i.e., O(log K), making the method scalable to extremely large K; 3) the regularized Wasserstein distance provides a smooth and well-behaved optimization objective that facilitates stable convergence, whereas DDN's l2 loss tends to converge to poor local optima; and 4) DGC replaces DDN's nearest-neighbor selection with random-neighbor selection, which avoids the density shift problem during multi-step forward. Extensive experiments on several benchmarks demonstrate the effectiveness and desirable properties of DGC. The code is publicly available at GitHub.
Oct 30, 2026

A Generalized Sparse Fuzzy Clustering Framework with Automated Cluster Cardinality Estimation Ability

Fuzzy clustering provides a robust framework for handling ambiguous and overlapping data boundaries, yet its traditional formulation generates entirely dense membership assignments that limit noise resilience and prevent estimating the true number of clusters, when it is unknown. To address these limitations, we introduce in this paper the Generalized Sparse Fuzzy Clustering (GSFC) framework, which incorporates a continuous sparsity penalty into the fuzzy objective function. Because closed-form solutions are precluded by the simultaneous presence of fuzzifier and sparsity exponents, we propose an efficient primal-dual bisection search coupled with specialized analytic pathways to rigorously enforce the partition constraint while organically driving trace memberships to exact zero. This mathematically enforced sparsity empowers the algorithm to autonomously estimate the true number of clusters by dynamically pruning redundant clusters, provided that it is initialized by a larger than the true number of clusters. Furthermore, we integrate a virtual noise sink to insulate outliers from the rest of the data points. The usage of the proposed framework is also extended to line segment detection. Extensive empirical evaluations across synthetic toy datasets, high-noise geometric stress tests, and real-world benchmarks (UCI wine dataset and hyperspectral images) demonstrate that GSFC effectively exceeds conventional fuzzy benchmarks while autonomously resolving cluster cardinality. Additionally, it significantly outperforms existing sparse possibilistic and probabilistic soft-clustering alternatives in line detection tasks.
Oct 28, 2026

ExplainCC: Explaining Correlated Clusters by Node Labels

An increasingly important requirement for clustering algorithms is that decisions and outcomes need to be clearly understandable for human users. We address this requirement for the Correlation Clustering (CC) problem, in case the objects to be clustered are accompanied by labels. In CC one seeks to partition a set of objects into clusters based on pairwise similarity and dissimilarity information. Our proposed model only considers clusters that can be explained by a label tree, which is essentially a decision tree that partitions the objects according to labels. The goal is to find an explainable partition of the data that minimizes the CC objective function. We formalize this problem from a theoretical viewpoint, and prove several hardness of approximation results, also when constraining the size of the tree. Our proposed greedy method finds locally optimal splits, and works recursively in a top-down approach. To efficiently compute the best split, we carefully maintain certain counters. An experimental evaluation demonstrates its effectiveness. The proposed algorithm processes graphs with over million edges in a few minutes, can find the ground truth in synthetic data, and is able to produce interpretable clusters in real world networks.
Oct 27, 2026

Low-degree polynomials lower bounds for clustering in small dimension

We study the computational limits of clustering nn observations drawn from a mixture of KK isotropic distributions in Rd\mathbb R^d, in the regime where the number KK of groups is much larger than the dimension dd. In this regime, tensor-based procedures recover the partition with a polylogarithmic separation between the centers, but they require a sample size that is a large and non-explicit polynomial of dKdK, whereas the existing low-degree lower bounds only show that nn must be larger than dK2dK^2. We introduce a mixture of 2K2K product Bernoulli distributions on {0,1}d\{0,1\}^d, with K=(d+1)mK=(d+1)^m, whose centers are built from a dual BCH code. This construction ensures that the moment tensors of the observations coincide with those of the uniform distribution on {−1,1}d\{-1,1\}^d up to the order 2m+12m+1. For any fixed mm, we establish a low-degree polynomial lower bound showing that clustering is hard as long as the separation ΔΔ satisfies Δ2≪(K2d3/2/n)1/(2m+2)∧dΔ^2\ll(K^2d^{3/2}/n)^{1/(2m+2)}\wedge\sqrt d, up to polylogarithmic factors. In particular, with a polylogarithmic separation, low-degree polynomials require n≳K2d3/2n\gtrsim K^2d^{3/2} observations, up to polylogarithmic factors. Through a Gaussianization argument, this hardness carries over, in the sense of reductions, to isotropic Gaussian mixtures. Our proof relies on a family of polynomials of the observations, indexed by bipartite graphs, which is almost orthonormal. The moments of these polynomials are governed by the number of solutions of polynomial systems over the finite field F_d+1\mathbb F\_{d+1} that are induced by the BCH code, and the crux of our analysis is to connect the combinatorial structure of the bipartite graphs with the structure of the solution sets of these systems.
Oct 27, 2026

Normalized Cuts and Data Clustering via Matrix Fractional Programming

The normalized cut (NCut) problem is a fundamental one in the area of data clustering. Despite its fractional structure, the NCut problem is seldom considered from a fractional programming (FP) perspective in the existing literature. The main reason is that the conventional FP method is inadequate for this problem case: the classical Dinkelbach's transform can only handle a single ratio and hence is limited to the two-class clustering, whereas the multi-class clustering involves multiple ratio terms. This work proposes a novel so-called multidimensional quadratic transform that is capable of dealing with the multi-ratio case; it recasts the NCut problem into a bipartite matching problem---which can be immediately solved by linear search. Furthermore, we explore the connection between the proposed FP method and the minorization-maximization (MM) theory, and in turn characterize the convergence behavior of our algorithm. Finally, we conduct experiments to numerically demonstrate the advantages of the proposed FP-based algorithm in a variety of data clustering and image segmentation tasks.
Oct 27, 2026

ClusterSplat: Semantic Cluster Selection for 3D Visual Grounding in Gaussian Splatting

We study 3D visual grounding in 3D Gaussian Splatting (3DGS), where a referring expression should identify a target object as both a rendered 2D mask and a set of explicit 3D Gaussians. Prior methods typically extract 3D targets by applying heuristic thresholding or top-ratio filtering to dense primitive-level relevance scores. However, these scores often vary substantially across scenes and prompts, making such heuristics sensitive and leading to unstable targeting. ClusterSplat addresses this by reframing 3D target selection as cluster-level selection over scene-adaptive candidates. The method first learns instance-aware Gaussian features, forms feature-aware seed voxels, and merges neighboring seed voxels when a description-length criterion decreases, producing a scene-specific set of cluster candidates. Given a referring expression, a query-conditioned cluster scorer ranks the cluster candidates with a lightweight MLP, and the selected cluster directly defines the explicit 3D target while its cluster score is rendered for the 2D mask. On ScanRefer, ClusterSplat achieves the best rendered 2D segmentation and explicit 3D target metrics among the compared 3DGS baselines. It also obtains the best average Ref-LERF scores, supporting the same trend under fine-grained referring descriptions. On ScanNet v2 class name queries, ClusterSplat achieves the strongest rendered 2D results and the highest 3D matching accuracy, while maintaining competitive 3D IoU. Our project page is available at https://jaesung8.github.io/clustersplat/ .
Oct 24, 2026

Clustering of High-Dimensional Human Gene Score Data for Target Cell Classification

The goal is to investigate whether the total human gene-score dataset and the selected human kinase-gene dataset exhibit the same number of clusters when analysed using the same set of 769 features. Two datasets were considered: the complete gene score dataset and a subset containing selected kinase genes. Two missing-data strategies were investigated. In Case I, rows containing missing gene-score values were removed. In Case II, rows with more than 20% missing values were excluded and the other missing values were replaced by the corresponding column mean. For each case, the data were scaled and principal component analysis (PCA) was performed before clustering. Four clustering approaches were considered: K-Means, Hierarchical Clustering, Fuzzy C-Means, and Graph-based Clustering. Across both datasets and both missing-data treatments, the optimal number of clusters was found to be two. In the absence of an optimal number of clusters, the quality of clustering was assessed using the Silhouette score. Relatively high Silhouette scores were obtained in all cases.
Oct 23, 2026

Kernelised covariance matrices, dimension reduction and imbalanced spectral clustering

The Gaussian Mixture Model (abbrv. GMM) is a classic generative model for clustered data, for which spectral clustering based on dimension reduction via PCA has been an effective framework. In this work, we investigate kernelised covariance matrices as an alternative mechanism for dimension reduction and spectral clustering, focusing on truncation kernels that select pairs of data points with suitable separation constraints. The structure of these matrices is motivated by considerations from statistical mechanics of repulsive particle systems. Our approach is particularly relevant for the setting of imbalanced clusters, where the sizes of the largest and smallest clusters have a diverging ratio with the problem size, and existing PCA-based methods turn out to be of limited effectiveness. We demonstrate efficient dimension reduction and clustering performance of these modified covariance matrices, substantiated by quantitative bounds. In particular, they achieve superior dimension reduction guarantees compared to PCA for a wide range of parameters in the regime of imbalanced clusters. For spectral clustering, our approach exhibits improvements over PCA in the imbalanced setting, in particular guaranteeing accurate clustering in a much larger regime of intra-cluster separations. Our theoretical guarantees reflected in a range of simulation experiments that exhibit these improvements for unbalanced clustering problems. Our analytical approach, based on kernel Laplacians, provide a toolbox as well as a relevant conceptual ingredient for clustering problems at large. We believe that our work will motivate the application of such kernelised covariance matrices for related classes of statistical problems, as well as spur new investigations in the theory of random matrices.
Oct 22, 2026

Evolving Federated Density Peak Clustering with Shuffler-Based Anonymization

In this paper, we present a novel one-shot federated clustering approach based on evolving fuzzy clustering and shuffler-based anonymization. In federated clustering, each round reveals additional model information to the server and can increase the opportunity to infer properties of local datasets, even when raw samples are never shared. Consequently, fewer client-server exchanges and unlinkability are important, so transmitted information cannot be attributed to any single client. Data-stream clustering algorithms, which learn in a single pass over the data, align well with the one-shot federated learning paradigm, where a single communication round can be sufficient. The proposed Evolving Federated Density Peak Clustering (eFDPC) method combines evolving fuzzy data-stream clustering and density peak clustering in a federated setting. Each client independently evolves micro-clusters from private data mini-batches through cluster addition and merging. To limit communication, density peak clustering is applied to the learned micro-clusters and only the selected peaks are transmitted, rather than the full local models. A shuffler-based layer is introduced between the clients and the server to anonymize contributions prior to reconstruction and global peak selection. We consider a peak-only variant, eFDPC-P, as well as eFDPC-G with server-side label propagation. Experiments on synthetic and real-world benchmark datasets show that eFDPC outperforms recent federated clustering baselines in one-shot settings and scales to higher-dimensional, non-IID data.
Oct 21, 2026

NEST: Nested Embedding Representation for Multiscale Clustering

Real-world data often exhibits cluster structure at multiple resolutions, yet existing methods typically learn a single partition or construct an explicit hierarchy. Inspired by Matryoshka Representation Learning, we introduce NEST, an unsupervised framework that encodes coarse-to-fine structure within a single embedding. NEST jointly optimizes clustering and separation across nested prefix subspaces, enabling progressively finer distinctions as embedding dimensionality increases, with rank and within-cluster regularization that keep the embedding from collapsing. Empirically, distances in the learned embedding follow the hierarchy distance more closely than those of the input, although the hierarchy is never observed during training. On synthetic hierarchies, NEST recovers multiscale structure given only the number of clusters per level. Experiments on vision, text, and single-cell data further demonstrate multiscale organization across real-world representations. By making clustering granularity an intrinsic property of the representation, NEST provides a unified approach to multiscale structure discovery.
Oct 21, 2026

Asymmetric Likelihood-Free Hypothesis Testing

In likelihood-free hypothesis testing (LFHT), given samples from two unknown distributions P,QP,Q on [n][n] with dTV(P,Q)≥ε\mathrm{d_{TV}}(P,Q)\geq\varepsilon, and from a third distribution D∈{P,Q}D\in\{P,Q\}, the goal is to identify whether D=PD=P or D=QD=Q. We study asymmetric likelihood-free hypothesis testing, where the sample budgets sPs_P and sQs_Q for PP and QQ may differ, and characterize the feasible triples (sP,sQ,sD)(s_P,s_Q,s_D) up to logarithmic factors. We establish that unequal reference budgets can give a polynomial saving. For instance, for constant separation, nn samples from PP and n3/4n^{3/4} from QQ allow testing with O~(n1/4)\widetilde O(n^{1/4}) samples from DD, whereas both existing baselines---symmetric LFHT and unequal-sample closeness testing---require Ω(n)Ω(\sqrt n) samples from DD. We further apply our results to non-adaptive distribution 2-clustering, where the sample allocation among kk distributions must be fixed before observing any data. We obtain matching upper and lower bounds for this problem up to logarithmic factors in terms of the domain size, number of distributions, smaller cluster size, and separation, both with one cluster distribution known and with both unknown. Comparing with known bounds for adaptive sample allocation gives a worst-case adaptivity gap of Θ~(k1/4)\widetildeΘ(k^{1/4}).
Oct 20, 2026

Agent AI Zarządzający Siecią Open RAN Zorientowana na Użytkownika

Jednym z najważniejszych wyzwań związanych z implementacją sieci Open RAN o architekturze zorientowanej na użytkownika jest odpowiednie formowanie tzw. klastrów obsługujących. Problem ten może być efektywnie rozwiązany za pomocą zaproponowanego Agenta AI bazującego na modelu językowym. Wyniki symulacji pokazały, że zaproponowane rozwiązanie pozwala na ponad 2-krotne zwiększenie mediany rozkładu przepływności użytkowników względem standardowej architektury zorientowanej na sieć.
Oct 20, 2026

Coincidence-Maximizing Customer Clustering Using Smart Meter Data

Electricity distribution planning depends on peak-demand coincidence within customer groups, yet similarity-based clustering of smart-meter data does not optimize it directly. We formulate customer grouping to maximize the average of group coincidence factors, weighted by each group's daily share of summed individual peak demand. We prove that jointly optimizing memberships and group peak times is strongly NP-hard even for two groups. We therefore develop a fixed-peak refinement procedure applicable to any feasible partition. It alternates between identifying group peak times and exactly reassigning customers under minimum group-size constraints. Each polynomial-time reassignment maximizes a lower bound tight at the current partition, so accepted updates strictly improve weighted coincidence. We initialize refinement by clustering individual peak-time distributions and evaluate the method on four public smart-meter panels (27,654 customers) using chronological holdouts and 200 paired replicates with complete refitting. Refinement consistently improves weighted coincidence during fitting and reduces sensitivity to initialization. On held-out days, the method outperforms random grouping and five standalone benchmarks, with mean paired gains of 1.08-3.48 percentage points over the strongest benchmark. Requiring nearly equal group sizes lowers test weighted coincidence only modestly. The groups retain recognizable peak-time patterns over time, suggesting applications in peak-aware customer aggregation.
Oct 15, 2026

Unsupervised Clustering of Public Transport Vehicles Using Deep Morphological Features and Color Histograms

Surveillance cameras along urban roads produce large volumes of unlabeled video that could support the monitoring of public transport, but grouping the observed vehicles into meaningful categories without manual annotation remains challenging, since buses from different routes often share the same body structure and differ mainly in their color schemes. This study presents an unsupervised clustering methodology for public transport vehicles that combines morphological features extracted with a frozen DINOv2 Vision Transformer and handcrafted HSV color histograms through weighted early fusion, followed by UMAP projection and K-Means clustering. The method was evaluated on 7,972 bus images extracted from about 1,460 hours of video of an arterial road in Mexico City, with the goal of isolating the buses of the city's public bus network (RTP) without supervision. With a fusion of 65% morphological and 35% color features, the pipeline produced 14 clusters that separate distinct routes and vehicle types, and it increased the precision of the target cluster with respect to morphological features alone. These results show that color complements self-supervised features for route-level clustering, provided that it does not dominate the representation.