Clustering

Follow this topic Ask about this topic

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

345 papers31 papers in the last four weeks, up 11% on the four weeks before. 0.2% of all new papers.

Feb 26, 2026

Low-degree Lower bounds for clustering in moderate dimension

We study the fundamental problem of clustering

n

points into

K

groups drawn from a mixture of isotropic Gaussians in

\mathbb{R}^d

. Specifically, we investigate the requisite minimal distance

Δ

between mean vectors to partially recover the underlying partition. While the minimax-optimal threshold for

Δ

is well-established, a significant gap exists between this information-theoretic limit and the performance of known polynomial-time procedures. Although this gap was recently characterized in the high-dimensional regime (

n \leq dK

), it remains largely unexplored in the moderate-dimensional regime (

n \geq dK

). In this manuscript, we address this regime by establishing a new low-degree polynomial lower bound for the moderate-dimensional case when

d \geq K

. We show that while the difficulty of clustering for

n \leq dK

is primarily driven by dimension reduction and spectral methods, the moderate-dimensional regime involves more delicate phenomena leading to a "non-parametric rate". We provide a novel non-spectral algorithm matching this rate, shedding new light on the computational limits of the clustering problem in moderate dimension.

Alexandra Carpentier, Nicolas Verzelen

Institut für Mathematik, Universität Potsdam, Germany. · INRAE, MISTEA, Univ. Montpellier, Montpellier, France

Low-Degree Polynomial Method Clustering Gaussian Mixture Models Statistical Learning Theory Information-Theoretic Lower Bounds

Feb 26, 2026

Hypernetwork-based approach for grid-independent functional data clustering

Functional data clustering is concerned with grouping functions that share similar structure, yet most existing methods implicitly operate on sampled grids, causing cluster assignments to depend on resolution, sampling density, or preprocessing choices rather than on the underlying functions themselves. To address this limitation, we introduce a framework that maps discretized function observations -- at arbitrary resolution and on arbitrary grids -- into a fixed-dimensional vector space via an auto-encoding architecture. The encoder is a hypernetwork that maps coordinate-value pairs to the weight space of an implicit neural representation (INR), which serves as the decoder. Because INRs represent functions with very few parameters, this design yields compact representations that are decoupled from the sampling grid, while the hypernetwork amortizes weight prediction across the dataset. Clustering is then performed in this weight space using standard algorithms, making the approach agnostic to both the discretization and the choice of clustering method. By means of synthetic and real-world experiments in high-dimensional settings, we demonstrate competitive clustering performance that is robust to changes in sampling resolution -- including generalization to resolutions not seen during training.

Anirudh Thatipelli, Ali Siahkoohi

Department of Computer Science, University of Central Florida

Clustering Deep Clustering

Feb 25, 2026

Fair Model-based Clustering

The goal of fair clustering is to find clusters such that the proportion of sensitive attributes (e.g., gender, race, etc.) in each cluster is similar to that of the entire dataset. Various fair clustering algorithms have been proposed that modify standard K-means clustering to satisfy a given fairness constraint. A critical limitation of several existing fair clustering algorithms is that the number of parameters to be learned is proportional to the sample size because the cluster assignment of each datum should be optimized simultaneously with the cluster center, and thus scaling up the algorithms is difficult. In this paper, we propose a new fair clustering algorithm based on a finite mixture model, called Fair Model-based Clustering (FMC). A main advantage of FMC is that the number of learnable parameters is independent of the sample size and thus can be scaled up easily. In particular, mini-batch learning is possible to obtain clusters that are approximately fair. Moreover, FMC can be applied to non-metric data (e.g., categorical data) as long as the likelihood is well-defined. Theoretical and empirical justifications for the superiority of the proposed algorithm are provided.

Jinwon Park, Kunwoong Kim, Jihu Lee +1

Graduate School of Data Science, Seoul National University · Department of Statistics, Seoul National University

Clustering Group Fairness Latent Variable Models

Feb 24, 2026

Multi-Vector Index Compression in Any Modality

We study efficient multi-vector retrieval for late interaction in any modality. Late interaction has emerged as a dominant paradigm for information retrieval in text, images, visual documents, and videos, but its computation and storage costs grow linearly with document length, making it costly for image-, video-, and audio-rich corpora. To address this limitation, we explore query-agnostic methods for compressing multi-vector document representations under a constant vector budget. We introduce four approaches for index compression: sequence resizing, memory tokens, hierarchical pooling, and a novel attention-guided clustering (AGC). AGC uses an attention-guided mechanism to identify the most semantically salient regions of a document as cluster centroids and to weight token aggregation. Evaluating these methods on retrieval tasks spanning text (BEIR), visual-document (ViDoRe), and video (MSR-VTT, MultiVENT 2.0), we show that attention-guided clustering consistently outperforms other parameterized compression methods (sequence resizing and memory tokens), provides greater flexibility in index size than non-parametric hierarchical clustering, and achieves competitive or improved performance compared to a full, uncompressed index. The source code is available at: github.com/hanxiangqin/omni-col-press.

Hanxiang Qin, Alexander Martin, Rohan Jha +3

Johns Hopkins University, Baltimore, MD, USA

Multi-Vector Retrieval Embedding Compression Multimodal IR Clustering

Feb 24, 2026

SODA-CitrON: Static Object Data Association by Clustering Multi-Modal Sensor Detections Online

The online fusion and tracking of static objects from heterogeneous sensor detections is a fundamental problem in robotics, autonomous systems, and environmental mapping. Although classical data association approaches such as JPDA are well suited for dynamic targets, they are less effective for static objects observed intermittently and with heterogeneous uncertainties, where motion models provide minimal discriminative power with respect to clutter. In this paper, we propose a novel method for static object data association by clustering multi-modal sensor detections online (SODA-CitrON), while simultaneously estimating positions and maintaining persistent tracks for an unknown number of objects. The proposed unsupervised machine learning approach operates in a fully online manner and handles temporally uncorrelated and multi-sensor measurements. Additionally, it has a worst-case loglinear complexity in the number of sensor detections while providing full output explainability. We evaluate the proposed approach in different Monte Carlo simulation scenarios and compare it against state-of-the-art methods, including POM-based filtering, DBSTREAM clustering, and JPDA. The results demonstrate that SODA-CitrON consistently outperforms the compared methods in terms of F1 score, position RMSE, MOTP, and MOTA in the static object mapping scenarios studied.

Jan Nausner, Kilian Wohlleben, Michael Hubner

Center for Digital Safety & Security, Austrian Institute of Technology GmbH, Vienna, Austria

Data Association Multimodal Sensor Fusion Clustering

Feb 23, 2026

Exploring Anti-Aging Literature via ConvexTopics and Large Language Models

The rapid expansion of biomedical publications creates challenges for organizing knowledge and detecting emerging trends, underscoring the need for scalable and interpretable methods. Common clustering and topic modeling approaches such as K-means or LDA remain sensitive to initialization and prone to local optima, limiting reproducibility and evaluation. We propose a reformulation of a convex optimization based clustering algorithm that produces stable, fine-grained topics by selecting exemplars from the data and guaranteeing a global optimum. Applied to about 12,000 PubMed articles on aging and longevity, our method uncovers topics validated by medical experts. It yields interpretable topics spanning from molecular mechanisms to dietary supplements, physical activity, and gut microbiota. The method performs favorably, and most importantly, its reproducibility and interpretability distinguish it from common clustering approaches, including K-means, LDA, and BERTopic. This work provides a basis for developing scalable, web-accessible tools for knowledge discovery.

Lana E. Yeganova, Won G. Kim, Shubo Tian +4

Division of Intramural Research (DIR), NLM, NIH, Bethesda, MD USA 20894

Topic Modeling Clustering

Feb 23, 2026

AuditoryHuM: Auditory Scene Label Generation and Clustering using Human-MLLM Collaboration

Manual annotation and clustering of audio datasets is labour intensive. We introduce AuditoryHuM, a training-free framework for the unsupervised discovery and clustering of auditory scene labels using human-Multimodal Large Language Model (MLLM) collaboration. Leveraging MLLMs, our framework generates contextually relevant labels for audio data. To ensure label quality and mitigate hallucinations, zero-shot learning (Human-CLAP) quantifies the alignment between generated text labels and raw audio. A targeted human-in-the-loop intervention, refines only the lowest aligned pairs. The discovered labels form an interpretable alignment vector to group audio into cohesive clusters. The framework was evaluated across three auditory scene datasets (ADVANCE, AHEAD-DS, and TAU 2019), achieving a 96.1% reduction in human labour for ADVANCE during testing. Downstream models trained on our clusters exhibit enhanced classification accuracy vs the baseline (0.79 to 0.84) in clean acoustic environments, though performance scales down in dense, complex soundscapes. The project page: https://github.com/Australian-Future-Hearing-Initiative

Henry Zhong, Jörg M. Buchholz, Julian Maclaren +2

Australian Hearing Hub, Macquarie University, Sydney, Australia · Google Research Australia, Sydney, Australia

Clustering LLM-Assisted Annotation Human-in-the-Loop Annotation Unsupervised Clustering Audio Understanding

Feb 20, 2026

CAKE: Confidence in Assignments via K-partition Ensembles

Clustering is widely used for unsupervised structure discovery, yet it offers limited insight into how reliable each individual assignment is. Diagnostics, such as convergence behavior or objective values, may reflect global quality, but they do not indicate whether particular instances are assigned confidently, especially for initialization-sensitive algorithms like k-means. This assignment-level instability can undermine both accuracy and robustness. Ensemble approaches improve global consistency by aggregating multiple runs, but they typically lack tools for quantifying pointwise confidence in a way that combines cross-run agreement with geometric support from the learned cluster structure. This work introduces CAKE (Confidence in Assignments via K-partition Ensembles), a framework that evaluates each point using two complementary statistics computed over a clustering ensemble: assignment stability and consistency of local geometric fit. These are combined into a single, interpretable score in [0,1]. The theoretical analysis shows that CAKE remains effective under noise and separates stable from unstable points. Experiments on synthetic and real-world datasets indicate that CAKE effectively highlights ambiguous points and stable core members, providing a confidence ranking over instances that can be used for selection or prioritization in downstream clustering workflows.

Aggelos Semoglou, John Pavlopoulos

Department of Informatics, Athens University of Economics and Business, Athens, Greece · Archimedes Research Unit, Athena Research Center, Athens, Greece

Clustering Unsupervised Clustering

Feb 20, 2026

Explaining AutoClustering: Uncovering Meta-Feature Contribution in AutoML for Clustering

AutoClustering methods aim to automate unsupervised learning tasks, including algorithm selection (AS), hyperparameter optimization (HPO), and pipeline synthesis (PS), by often leveraging meta-learning over dataset meta-features. While these systems often achieve strong performance, their recommendations are often difficult to justify: the influence of dataset meta-features on algorithm and hyperparameter choices is typically not exposed, limiting reliability, bias diagnostics, and efficient meta-feature engineering. This limits reliability and diagnostic insight for further improvements. In this work, we investigate the explainability of the meta-models in AutoClustering. We first review 22 existing methods and organize their meta-features into a structured taxonomy. We then apply a global explainability technique (i.e., Decision Predicate Graphs) to assess feature importance within meta-models from selected frameworks. Finally, we use local explainability tools such as SHAP (SHapley Additive exPlanations) to analyse specific clustering decisions. Our findings highlight consistent patterns in meta-feature relevance, identify structural weaknesses in current meta-learning strategies that can distort recommendations, and provide actionable guidance for more interpretable Automated Machine Learning (AutoML) design. This study therefore offers a practical foundation for increasing decision transparency in unsupervised learning automation.

Matheus Camilo da Silva, Leonardo Arrighi, Ana Carolina Lorena +1

Department of Mathematics, Computer Science and Geosciences, University of Trieste, Piazzale Europa, 1, 34127 Trieste TS, Italy. · Division of Computer Science, Aeronautics Institute of Technology, Praça Marechal Eduardo Gomes, 50, 12228-900 São José dos Campos SP, Brazil.

Automated Machine Learning Meta-Learning Explainable Artificial Intelligence Clustering

Feb 19, 2026

SubQuad: Near-Quadratic-Free Structure Inference with Distribution-Balanced Objectives in Adaptive Receptor framework

Comparative analysis of adaptive immune repertoires at population scale is hampered by two practical bottlenecks: the near-quadratic cost of pairwise affinity evaluations and dataset imbalances that obscure clinically important minority clonotypes. We introduce SubQuad, an end-to-end pipeline that addresses these challenges by combining antigen-aware, near-subquadratic retrieval with GPU-accelerated affinity kernels, learned multimodal fusion, and fairness-constrained clustering. The system employs compact MinHash prefiltering to sharply reduce candidate comparisons, a differentiable gating module that adaptively weights complementary alignment and embedding channels on a per-pair basis, and an automated calibration routine that enforces proportional representation of rare antigen-specific subgroups. On large viral and tumor repertoires SubQuad achieves measured gains in throughput and peak memory usage while preserving or improving recall@k, cluster purity, and subgroup equity. By co-designing indexing, similarity fusion, and equity-aware objectives, SubQuad offers a scalable, bias-aware platform for repertoire mining and downstream translational tasks such as vaccine target prioritization and biomarker discovery.

Rong Fu, Zijian Zhang, Kun Liu +3

Independent Researcher

Clustering Approximate Nearest Neighbor Search

Feb 18, 2026

On the Hardness of Approximation of the Fair k-Center Problem

In this work, we study the hardness of approximation of the fair

k

-center problem. In this problem, we are given a set of data points in a metric space that is partitioned into groups and the task is to choose a subset of

k

-data points, called centers, such that a prescribed number of data points from each group are chosen while minimizing the maximum distance from any point to its closest center. Although a polynomial-time

3

-approximation is known for fair

k

-center in general metrics, it has remained open whether this approximation guarantee is tight or could be further improved, especially since the classical unconstrained

k

-center problem admits a polynomial-time factor-

2

approximation. We resolve this open question by proving that, assuming

\mathsf{P} \neq \mathsf{NP}

, for any

ε>0

, no polynomial-time algorithm can approximate fair

k

-center to

(3-ε)

-factor. Our inapproximability results hold even when only two disjoint groups are present and at least one center must be chosen from each group. Further, it extends to the canonical one-per-group setting with

k

-groups (for arbitrary

k

), where exactly one center must be selected from each group. Consequently, the factor-

3

barrier for fair

k

-center in general metric spaces is inherent, and existing

3

-approximation algorithms are optimal up to lower-order terms even in these restricted regimes. This result stands in sharp contrast to the

k

-supplier formulation, where both the unconstrained and fair variants admit factor-

3

approximation in polynomial time.

Suhas Thejaswi

Department of Computer Science, Aalto University, Finland

Approximation Algorithms Clustering Group Fairness

Feb 18, 2026

Neighborhood Stability as a Measure of Nearest Neighbor Searchability

Clustering-based Approximate Nearest Neighbor Search (ANNS) organizes a set of points into partitions, and searches only a few of them to find the nearest neighbors of a query. Despite its popularity, there are virtually no analytical tools to determine the suitability of clustering-based ANNS for a given dataset -- what we call "searchability." To address that gap, we present two measures for flat clusterings of high-dimensional points in Euclidean space. First is Clustering-Neighborhood Stability Measure (clustering-NSM), an internal measure of clustering quality -- a function of a clustering of a dataset -- that we show to be predictive of ANNS accuracy. The second, Point-Neighborhood Stability Measure (point-NSM), is a measure of clusterability -- a function of the dataset itself -- that is predictive of clustering-NSM. The two together allow us to determine whether a dataset is searchable by clustering-based ANNS given only the data points. Importantly, both are functions of nearest neighbor relationships between points, not distances, making them applicable to various distance functions including inner product.

Thomas Vecchiato, Sebastian Bruch

University of Copenhagen, Copenhagen, Denmark · Northeastern University, Boston, MA, USA

Approximate Nearest Neighbor Search Clustering

Feb 18, 2026

Empirical Cumulative Distribution Function Clustering for LLM-based Agent System Analysis

Large language models (LLMs) are increasingly used as agents to solve complex tasks such as question answering (QA), scientific debate, and software development. A standard evaluation procedure aggregates multiple responses from LLM agents into a single final answer, often via majority voting, and compares it against reference answers. However, this process can obscure the quality and distributional characteristics of the original responses. In this paper, we propose a novel evaluation framework based on the empirical cumulative distribution function (ECDF) of cosine similarities between generated responses and reference answers. This enables a more nuanced assessment of response quality beyond exact match metrics. To analyze the response distributions across different agent configurations, we further introduce a clustering method for ECDFs using their distances and the

k

-medoids algorithm. Our experiments on a QA dataset demonstrate that ECDFs can distinguish between agent settings with similar final accuracies but different quality distributions. The clustering analysis also reveals interpretable group structures in the responses, offering insights into the impact of temperature, persona, and question topics.

Chihiro Watanabe, Jingyu Sun

NTT Computer and Data Science Laboratories , 3-9-11, Midori-cho, Musashino-shi, Tokyo, Japan

LLM Agent Evaluation Language Model Generation Evaluation Clustering

Feb 17, 2026

Khatri-Rao Clustering for Data Summarization

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.

Martino Ciaperoni, Collin Leiber, Aristides Gionis +1

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

Clustering Deep Clustering

Feb 17, 2026

Perspectives - Interactive Document Clustering in the Discourse Analysis Tool Suite

This paper introduces Perspectives, an interactive extension of the Discourse Analysis Tool Suite designed to empower Digital Humanities (DH) scholars to explore and organize large, unstructured document collections. Perspectives implements a flexible, aspect-focused document clustering pipeline with human-in-the-loop refinement capabilities. We showcase how this process can be initially steered by defining analytical lenses through document rewriting prompts and instruction-based embeddings, and further aligned with user intent through tools for refining clusters and mechanisms for fine-tuning the embedding model. The demonstration highlights a typical workflow, illustrating how DH researchers can leverage Perspectives's interactive document map to uncover topics, sentiments, or other relevant categories, thereby gaining insights and preparing their data for subsequent in-depth analysis.

Tim Fischer, Chris Biemann

Language Technology Group, Department of Informatics, University of Hamburg, Germany

Feb 17, 2026

Doubly Stochastic Mean-Shift Clustering

Standard Mean-Shift algorithms are notoriously sensitive to the bandwidth hyperparameter, particularly in data-scarce regimes where fixed-scale density estimation leads to fragmentation and spurious modes. In this paper, we propose Doubly Stochastic Mean-Shift (DSMS), a novel extension that introduces randomness not only in the trajectory updates but also in the kernel bandwidth itself. By drawing both the data samples and the radius from a continuous uniform distribution at each iteration, DSMS effectively performs a better exploration of the density landscape. We show that this randomized bandwidth policy acts as an implicit regularization mechanism, and provide convergence theoretical results. Comparative experiments on synthetic Gaussian mixtures reveal that DSMS significantly outperforms standard and stochastic Mean-Shift baselines, exhibiting remarkable stability and preventing over-segmentation in sparse clustering scenarios without other performance degradation.

Tom Trigano, Yann Sepulcre, Itshak Lapidot

Shamoon College of Engineering, Department of Electrical Engineering, Ashdod, Israel · Sapir Academic College, Department of Engineering, Sderot, Israel · Afeka Tel-Aviv Academic College of Engineering, School of Electrical Engineering, Israel +1

Clustering Unsupervised Clustering Density-Based Clustering

Feb 16, 2026

A Pragmatic Method for Comparing Clusterings with Overlaps and Outliers

Clustering algorithms are an essential part of the unsupervised data science ecosystem, and extrinsic evaluation of clustering algorithms requires a method for comparing the detected clustering to a ground truth clustering. In a general setting, the detected and ground truth clusterings may have outliers (objects belonging to no cluster), overlapping clusters (objects may belong to more than one cluster), or both, but methods for comparing these clusterings are currently undeveloped. In this note, we define a pragmatic similarity measure for comparing clusterings with overlaps and outliers, show that it has several desirable properties, and experimentally confirm that it is not subject to several common biases afflicting other clustering comparison measures.

Ryan DeWolfe, Paweł Prałat, François Théberge

Department of Mathematics, Toronto Metropolitan University, Toronto, Canada · Tutte Institute for Mathematics and Computing, Ottawa, Canada

Clustering Unsupervised Clustering

Feb 16, 2026

MacNet: An End-to-End Manifold-Constrained Adaptive Clustering Network for Interpretable Whole Slide Image Classification

Whole slide images (WSIs) are the gold standard for pathological diagnosis and sub-typing. Current main-stream two-step frameworks employ offline feature encoders trained without domain-specific knowledge. Among them, attention-based multiple instance learning (MIL) methods are outcome-oriented and offer limited interpretability. Clustering-based approaches can provide explainable decision-making process but suffer from high dimension features and semantically ambiguous centroids. To this end, we propose an end-to-end MIL framework that integrates Grassmann re-embedding and manifold adaptive clustering, where the manifold geometric structure facilitates robust clustering results. Furthermore, we design a prior knowledge guiding proxy instance labeling and aggregation strategy to approximate patch labels and focus on pathologically relevant tumor regions. Experiments on multicentre WSI datasets demonstrate that: 1) our cluster-incorporated model achieves superior performance in both grading accuracy and interpretability; 2) end-to-end learning refines better feature representations and it requires acceptable computation resources.

Mingrui Ma, Chentao Li, Pan Huang +1

School of Computer Science and Technology, Xinjiang University, Urumqi 830046, China · Affiliated Tumor Hospital of Xinjiang Medical University, Xinjiang 830011, China · Fu Foundation School of Engineering and Applied Science, Columbia University, New York, NY 10027, USA +1

Histopathology Image Classification Explainable Medical Image Analysis Multiple Instance Learning Clustering

Feb 16, 2026

Prototype Instance-semantic Disentanglement with Low-rank Regularized Subspace Clustering for WSIs Explainable Recognition

The tumor region plays a key role in pathological diagnosis. Tumor tissues are highly similar to precancerous lesions and non tumor instances often greatly exceed tumor instances in whole slide images (WSIs). These issues cause instance-semantic entanglement in multi-instance learning frameworks, degrading both model representation capability and interpretability. To address this, we propose an end-to-end prototype instance semantic disentanglement framework with low-rank regularized subspace clustering, PID-LRSC, in two aspects. First, we use secondary instance subspace learning to construct low-rank regularized subspace clustering (LRSC), addressing instance entanglement caused by an excessive proportion of non tumor instances. Second, we employ enhanced contrastive learning to design prototype instance semantic disentanglement (PID), resolving semantic entanglement caused by the high similarity between tumor and precancerous tissues. We conduct extensive experiments on multicentre pathology datasets, implying that PID-LRSC outperforms other SOTA methods. Overall, PID-LRSC provides clearer instance semantics during decision-making and significantly enhances the reliability of auxiliary diagnostic outcomes.

Chentao Li, Pan Huang

Whole-Slide Image Analysis Histopathology Image Classification Explainable Medical Image Analysis Multiple Instance Learning Clustering

Feb 9, 2026

Incremental (k, z)-Clustering on Graphs

Given a weighted undirected graph, a number of clusters

k

, and an exponent

z

, the goal in the

(k, z)

-clustering problem on graphs is to select

k

vertices as centers that minimize the sum of the distances raised to the power

z

of each vertex to its closest center. In the dynamic setting, the graph is subject to adversarial edge updates, and the goal is to maintain explicitly an exact

(k, z)

-clustering solution in the induced shortest-path metric. While efficient dynamic

k

-center approximation algorithms on graphs exist [Cruciani et al. SODA 2024], to the best of our knowledge, no prior work provides similar results for the dynamic

(k,z)

-clustering problem. As the main result of this paper, we develop a randomized incremental

(k, z)

-clustering algorithm that maintains with high probability a constant-factor approximation in a graph undergoing edge insertions with a total update time of

\tilde O(k m^{1+o(1)}+ k^{1+\frac{1}λ} m)

, where

λ\geq 1

is an arbitrary fixed constant. Our incremental algorithm consists of two stages. In the first stage, we maintain a constant-factor bicriteria approximate solution of size

\tilde{O}(k)

with a total update time of

m^{1+o(1)}

over all adversarial edge insertions. This first stage is an intricate adaptation of the bicriteria approximation algorithm by Mettu and Plaxton [Machine Learning 2004] to incremental graphs. One of our key technical results is that the radii in their algorithm can be assumed to be non-decreasing while the approximation ratio remains constant, a property that may be of independent interest. In the second stage, we maintain a constant-factor approximate

(k,z)

-clustering solution on a dynamic weighted instance induced by the bicriteria approximate solution. For this subproblem, we employ a dynamic spanner algorithm together with a static

(k,z)

-clustering algorithm.

Emilio Cruciani, Sebastian Forster, Antonis Skarlatos

European University of Rome, Italy. · Department of Computer Science, University of Salzburg, Salzburg, Austria. · Department of Computer Science, University of Warwick, Coventry, England.

Clustering Graph Clustering Approximation Algorithms

Jan 29, 2026

TabClustPFN: A Prior-data Fitted Network for Tabular Data Clustering

Prior-data Fitted Networks (PFNs) have reframed supervised tabular learning as single-pass in-context inference without per-dataset optimization. Extending this paradigm to clustering is appealing yet fundamentally more challenging, due to absent supervision, unknown cluster cardinality, and label switching inherent to partition outputs. Existing PFN-based clustering methods address these challenges only partially, either requiring known cardinality as input or relying on unstable label-ordering conventions and overly restrictive synthetic priors. We introduce TabClustPFN, a clustering PFN that resolves all challenges jointly through co-designed prior, objective, and architecture. Our hybrid pretraining prior captures heterogeneous real-tabular geometry; our decoupled partition inference network--cardinality inference network architecture jointly infers cluster assignments and cardinality in a single pass; and our SoftARI training objective is permutation-invariant by construction, eliminating the need for any label-ordering convention. On a 44 curated real-world tabular benchmark, TabClustPFN achieves state-of-the-art clustering performance against classical, deep, and amortized baselines, with runtime comparable to efficient baselines. Code is available at https://github.com/Tianqi-Zhao/TabClustPFN.

Tianqi Zhao, Guanyang Wang, Yan Shuo Tan +1

Renmin University of China · Rutgers University · National University of Singapore +1

Cluster Number Estimation Clustering Unsupervised Clustering Prior-Data Fitted Networks

Jan 15, 2026

CROCS: A Two-Stage Clustering Framework for Behaviour-Centric Consumer Segmentation with Smart Meter Data

With grid operators confronting rising uncertainty from renewable integration and a broader push toward electrification, Demand-Side Management (DSM) -- particularly Demand Response (DR) -- has attracted significant attention as a cost-effective mechanism for balancing modern electricity systems. Unprecedented volumes of consumption data from a continuing global deployment of smart meters enable consumer segmentation based on real usage behaviours, promising to inform the design of more effective DSM and DR programs. However, existing clustering-based segmentation methods insufficiently reflect the behavioural diversity of consumers, often relying on rigid temporal alignment, and faltering in the presence of anomalies, missing data, or large-scale deployments. To address these challenges, we propose a novel two-stage clustering framework -- Clustered Representations Optimising Consumer Segmentation (CROCS). In the first stage, each consumer's daily load profiles are clustered independently to form a Representative Load Set (RLS), providing a compact summary of their typical diurnal consumption behaviours. In the second stage, consumers are clustered using the Weighted Sum of Minimum Distances (WSMD), a novel set-to-set measure that compares RLSs by accounting for both the prevalence and similarity of those behaviours. Finally, community detection on the WSMD-induced graph reveals higher-order prototypes that embody the shared diurnal behaviours defining consumer groups, enhancing the interpretability of the resulting clusters. Extensive experiments on both synthetic and real Australian smart meter datasets demonstrate that CROCS captures intra-consumer variability, uncovers both synchronous and asynchronous behavioural similarities, and remains robust to anomalies and missing data, while scaling efficiently through natural parallelisation. These results...

Luke W. Yerbury, Ricardo J. G. B. Campello, G. C. Livingston +2

Clustering Demand Response Time Series Clustering Power Systems

Jan 12, 2026

Nonparametric Kernel Clustering with Bandit Feedback

Clustering with bandit feedback refers to the problem of partitioning the arms of an

N

-armed stochastic bandit according to their underlying distributions, based on noisy observations collected sequentially and adaptively. This setting has attracted growing interest for its applicability in recommendation systems, crowdsourcing, and adaptive trials. Existing works rely on the strong assumption that arm distributions are sub-Gaussian, which can only distinguish arms whose distributions differ in mean - missing realistic settings where distributional differences lie in shape or higher moments. % We introduce a framework of nonparametric clustering with bandit feedback, free of any parametric assumptions regarding the arm distributions. We adopt a kernel-based approach and reformulate the problem as clustering arms according to their kernel mean embeddings in a reproducing kernel Hilbert space (RKHS). Building on this formulation, we introduce the \kabc\ algorithm, prove that it is

δ

-PAC, and derive a non-asymptotic high-probability upper bound on its sampling complexity. The bound is governed by a variance-aware signal-to-noise ratio defined as the minimum over pairs of arms in distinct clusters of the ratio between their squared MMD and their RKHS variance. \kabc\ achieves instance-dependent guarantees while being adaptive to this unknown ratio. We validate our approach empirically on synthetic and real-world datasets, demonstrating that \kabc\ succeeds in distributional clustering settings where mean-based methods fail.

Victor Thuot, Sebastian Vogt, Debarghya Ghoshdastidar +1

MISTEA, UMPA-ENSL · LRR-TUM · MISTEA

Clustering Multi-Armed Bandits

Jan 9, 2026

A Fast and Effective Method for Euclidean Anticlustering: The Assignment-Based-Anticlustering Algorithm

Anticlustering is an NP-hard combinatorial optimization problem that consists of partitioning a set of objects into equal-sized groups called anticlusters such that the objects in the same anticluster are as dissimilar as possible and thereby representative of the entire set of objects. Here we study the case where the dissimilarity metric is the squared Euclidean distance between the respective feature vectors. Applications of Euclidean anticlustering include social studies, cross-validation, creating mini-batches for stochastic gradient descent, and finding balanced K-cut partitions. In particular, machine-learning applications such as mini-batch generation involve million-scale datasets and very large values of K, making scalable anticlustering algorithms essential. We propose a new algorithm, the Assignment-Based Anticlustering (ABA) algorithm, that scales to instances with millions of objects and hundreds of thousands of anticlusters within seconds to minutes, which is far beyond what existing anticlustering methods can manage. We demonstrate here, via an extensive computational study, that our algorithm outperforms existing anticlustering methods in both solution quality and running time. This is so also for anticlustering with categories. For the related problem of balanced K-cut partitioning, our algorithm is superior to the well-known METIS method. The code of our algorithm is available on GitHub.

Philipp Baumann, Olivier Goldschmidt, Dorit S. Hochbaum +1

Department of Business Administration, University of Bern, Engehaldenstr. 4, 3012 Bern, Switzerland · Riverside County Office of Education, Riverside, CA 92501, USA · Industrial Engineering and Operations Research Department, University of California, Berkeley, CA 94720, USA

Clustering Combinatorial Optimization

Dec 29, 2025

Finite Topological Space Filtrations: A Topological Framework for Data Analysis

We introduce a data-analysis framework based on filtrations of finite topological spaces. Starting from a finite metric data set, we construct a sequence of coarsening topologies on the same set of points. These topologies give persistence modules and barcodes in the usual way, but they also retain information that is lost when the filtration is reduced to homology. At each level one can examine, for example, which points are topologically indistinguishable, how their minimal neighbourhoods overlap, how connected components merge, and how these features change from one level to the next. We develop the basic theory of these filtrations, establish stability results under suitable hypotheses, and give practical constructions starting directly from a distance matrix. We then study what can be learned from the resulting finite topologies. On synthetic data with known clusters of different shapes, sizes, and densities, we examine how these regions appear among the finite-topological structures and how they merge as the topology coarsens. We also study what happens when points that become uncovered early in the construction are removed and the analysis is repeated. For one-dimensional homology, we use paths in the finite-topological structure to locate cycles and to examine how their appearance is related to the geometry of the data. We finally apply these ideas to two real data sets with quite different structures. On the Paul15 single-cell data, we use the evolving finite topology to examine fine cellular states, their overlaps and relations, their assembly into larger groups, and the effect of removing points that connect these structures. On COIL20, where images of an object are sampled through a full rotation, we study how the cyclic organization of the images is reflected in the finite-topological evolution and in the associated one-dimensional homology.

Selçuk Kayacan

Bahçeşehir University, Faculty of Engineering and Natural Sciences, Istanbul, Turkey

Clustering Persistent Homology Topological Data Analysis

Dec 18, 2025

Persistent Multiscale Density-based Clustering

Clustering is a cornerstone of modern data analysis. Detecting clusters in exploratory data analyses (EDA) requires algorithms that make few assumptions about the data. Density-based clustering algorithms are particularly well-suited for EDA because they describe high-density regions, assuming only that a density exists. Applying density-based clustering algorithms in practice, however, requires selecting appropriate hyperparameters, which is difficult without prior knowledge of the data distribution. For example, DBSCAN requires selecting a density threshold, and HDBSCAN* relies on a minimum cluster size parameter. In this work, we propose Persistent Leaves Spatial Clustering for Applications with Noise (PLSCAN), a multiscale density-based clustering algorithm that replaces HDBSCAN*'s fixed minimum cluster size pruning of a mutual-reachability linkage hierarchy with a persistence-based cluster selection procedure. Effectively, PLSCAN identifies all minimum cluster sizes for which HDBSCAN* produces stable (leaf) clusters. In concept, PLSCAN applies scale-space clustering principles and is equivalent to persistent homology on a novel metric space. We compare its performance to HDBSCAN* on several real-world datasets, demonstrating that it achieves a higher median ARI, is less sensitive to changes in the number of mutual reachability neighbours, and has higher stability under resampling. Additionally, we compare PLSCAN's computational costs to

k

-Means++, demonstrating competitive run-times on low-dimensional datasets. At higher dimensions, run times scale more similarly to HDBSCAN*.

Daniël Bot, Leland McInnes, Jan Aerts

1UHasselt, Data Science Institute (DSI) · 2Tutte Institute for Mathematics and Computing · 3KU Leuven, Augmented Intelligence for Data Analytics Lab, Department of Biosystems

Clustering Unsupervised Clustering Density-Based Clustering

Dec 5, 2025

BalLOT: Balanced $k$ -means clustering with optimal transport

We consider the fundamental problem of balanced

k

-means clustering. In particular, we introduce an optimal transport approach to alternating minimization called BalLOT, and we show that it delivers a fast and effective solution to this problem. We establish this with several theoretical guarantees and a variety of numerical experiments. On the theory front, we first prove that for generic data, BalLOT produces integral couplings at each step. Next, we perform a landscape analysis to provide theoretical guarantees for both exact and partial recoveries of planted clusters under the stochastic ball model. We also propose initialization schemes that achieve one-step recovery of planted clusters. To conclude, we present numerical experiments that corroborate our theoretical results.

Wenyan Luo, Dustin G. Mixon

Department of Mathematics, The Ohio State University, Columbus, Ohio, USA · Translational Data Analytics Institute, The Ohio State University, Columbus, Ohio, USA

Clustering Nonconvex Optimization

Dec 4, 2025

ClusterFusion: Hybrid Clustering with Embedding Guidance and LLM Adaptation

Text clustering is a fundamental task in natural language processing, yet traditional clustering algorithms with pre-trained embeddings often struggle in domain-specific contexts without costly fine-tuning. Large language models (LLMs) provide strong contextual reasoning, yet prior work mainly uses them as auxiliary modules to refine embeddings or adjust cluster boundaries. We propose ClusterFusion, a hybrid framework that instead treats the LLM as the clustering core, guided by lightweight embedding methods. The framework proceeds in three stages: embedding-guided subset partition, LLM-driven topic summarization, and LLM-based topic assignment. This design enables direct incorporation of domain knowledge and user preferences, fully leveraging the contextual adaptability of LLMs. Experiments on three public benchmarks and two new domain-specific datasets demonstrate that ClusterFusion not only achieves state-of-the-art performance on standard tasks but also delivers substantial gains in specialized domains. To support future work, we release our newly constructed dataset and results on all benchmarks.

Yiming Xu, Yuan Yuan, Vijay Viswanathan +1

Adobe · Carnegie Mellon University

Clustering Text Clustering Semantic Clustering

Dec 2, 2025

Agentic AI for Clustering, Relationship Discovery, and Semantic Trading in Prediction Markets

Prediction markets allow users to trade on outcomes of real-world events, but are prone to fragmentation with overlapping questions, implicit equivalences, and hidden contradictions across markets. We present an agentic AI (AAI) pipeline that autonomously recovers cross-market structure from contract text before prices enter the analysis. The workflow first clusters markets into coherent topical groups using natural-language understanding over contract text and metadata, and then identifies contracts within each cluster, but from different event markets, that exhibit strong dependence or leader--follower relationships. We evaluate this system, along with a natural language inference (NLI) benchmark, on a large prediction market dataset from early 2026. Using resolved outcomes to evaluate identified relations, we find that AAI-identified relations are 62.8% consistent with exchange-recorded settlements, whereas the NLI benchmark only achieves 40.6% accuracy. Within clusters, the AAI output is sparse and also remarkably compatible as a signed graph with a frustration rate of 0.324%. As an application, we show how discovered relations inform semantics-based trading strategies on prediction markets. One such strategy yields 14.12% net ROI after fees in a two-month period in 2026. Overall, we demonstrate the potential for agentic AI as a structural discovery layer for prediction markets.

Agostino Capponi, Alfio Gliozzo, Brian Zhu

Columbia University, Columbia Business School · IBM · Columbia University

Relation Extraction Clustering Agentic AI Prediction Markets

Nov 27, 2025

Mixed Data Clustering Survey and Challenges

The advent of the big data paradigm has transformed how industries manage and analyze information, ushering in an era of unprecedented data volume, velocity, and variety. Within this landscape, mixed-data clustering has become a critical challenge, requiring innovative methods that can effectively exploit heterogeneous data types, including numerical and categorical variables. Traditional clustering techniques, typically designed for homogeneous datasets, often struggle to capture the additional complexity introduced by mixed data, underscoring the need for approaches specifically tailored to this setting. Hierarchical and explainable algorithms are particularly valuable in this context, as they provide structured, interpretable clustering results that support informed decision-making. This paper introduces a clustering method grounded in pretopological spaces. In addition, benchmarking against classical numerical clustering algorithms and existing pretopological approaches yields insights into the performance and effectiveness of the proposed method within the big data paradigm.

Guillaume Guerard, Sonia Djebali

L´eonard de Vinci Pˆole Universitaire, Research Center, 12 Avenue L´eonard de Vinci, Paris La D´efense, 92916, France.