CS Paper Radar

Efficient Group-Penalty k-means for Text Clustering with Noisy LLM-Generated Constraints

Feiteng Nie, Yuan Sun, Shengkun Zhu, Sheng Wang, Zhiyong Peng

cs.DB ·submitted 2026-10-28 10:27 UTC · v1
theory

Abstract

k-means provides a simple and efficient foundation for text clustering, but embedding alone can miss task-specific semantic boundaries. Must-link (ML) and cannot-link (CL) constraints can correct such errors, yet conventional constrained clustering assumes that these relations are already supplied. LLMs can generate them without task-specific labels, but exhaustive querying is costly and their judgments can be incorrect. We present GPKmeans, an efficient Group-Penalty k-means method for text clustering with noisy LLM-generated constraints. GPKmeans uses LLM as an offline local pairwise annotator, querying selected anchor-candidate pairs for sparse ML links and constructing set-valued CL evidence without all-pairs queries. It converts connected components of the ML-link graph and the generated CL sets into groups with normalized, bounded soft penalties, limiting each group's influence independently of its size. Cached coordinate descent is proposed to efficiently solve the constraints clustering problem. We prove finite-step convergence and derive deterministic and probabilistic oracle-referenced bounds that relate objective distortion to the penalty coefficients and to the group-level error probabilities of the generated constraints. Across nine datasets, GPKmeans uses fewer LLM calls and yields more accurate constraints. It achieves the best average ACC, NMI, and ARI while running approximately 30 times faster than state-of-the-art constrained clustering methods.

Closest papers

Nearest neighbours by meaning across the whole index.

LEDGER: LLM-Evidence-Driven Graph-Encoded Clustering-Friendly Representations for Short Texts

cs.SI ·2026-11-13 ·Jie Wang, Kuang Zhou
similarity 0.69
Abstract

Short-text clustering is important for analyzing user-generated content in social networks and online services, supporting applications such as topic discovery and user intent analysis. However, the desired grouping depends on an application-specific clustering criterion that general-purpose text embeddings may not capture. Large language models (LLMs) can apply such a criterion to a pair of texts without human annotation, and existing methods use their responses as generated descriptions, binary decisions or selected neighbours. These discrete outputs discard how strongly the LLM supports a pair and how many judgments stand behind it. Each judgment is also used alone or within the neighbourhood of a single text, so the relations that link judgments across the corpus remain unused. In this paper, we propose LEDGER, an LLM-guided graph representation learning framework for short-text clustering. LEDGER aggregates the repeated numerical scores of each text pair into an accumulated score and an observation count, which define an evidence target for every queried pair. The pairs whose scores reach a threshold form a relation graph, over which a graph encoder propagates text features with a propagation range learned jointly with the encoder. A pairwise predictor trained to match the evidence targets shapes the learned representation, and a distilled student encoder extends it to unqueried texts without further LLM requests. Extensive experiments on seven datasets with four frozen text embeddings show that LEDGER achieves the highest mean clustering accuracy and NMI against five comparison methods, and ablations show that the graph, the learned propagation range and the evidence target each improve performance.

0.10

Optimal Approximation for Constrained Correlation Clustering via Repulsion

cs.DS ·2026-11-03 ·Yixin Cao, Ying Xu
similarity 0.62
Abstract · Superseding arXiv:2608.04883

The best-known approximation factor for constrained correlation clustering stood at three for nearly two decades, until a recent improvement to below $16/7$. We give a randomized polynomial-time $(2+\varepsilon)$-approximation using \emph{Repulsion}, a recursive operation that separates a metric ball from its complement. Repulsion naturally respects hard constraints and admits a short potential-based analysis; as a warm-up, radius-$2/3$ Repulsion rounds the standard metric LP into a feasible partition of cost at most three times its objective. The $(2+\varepsilon)$-approximation takes a two-stage approach, first removing must-links with arbitrarily small loss in the approximation ratio. The second stage combines lossless, constraint-aware preclustering with the bounded sub-cluster LP framework of Cao, Cohen-Addad, Lee, Li, Newman, and Vogl (STOC 2024). Repeated positive conditioning and sampling produce candidate sets, which radius-one Repulsion partitions into feasible clusters at controlled cost. We also give an approximation-preserving reduction from vertex cover to cluster deletion, a special case with only cannot-links. Apart from establishing a matching factor-two hardness threshold under the Unique Games Conjecture, it motivates our two-stage approach and Repulsion.

0.15

Uncertainty-Aware Probabilistic Constrained Clustering from Entangled Pairwise Supervision

cs.LG cs.AI ·2026-08-12 ·Shaojie Zhang, Ke Chen
top venue similarity 0.62
Abstract · Accepted at NeurIPS 2026 (Spotlight). Camera-ready revision; 44 pages, including appendices

Pairwise constrained clustering typically relies on hard must-link/cannot-link labels, whereas realistic pairwise supervision may be real-valued and entangle intrinsic ambiguity, expert judgment, and stochastic corruption. Existing deep constrained clustering (DCC) methods mainly target hard, expert-agnostic constraints, treating soft labels mostly numerically rather than semantically. We formalize this setting as uncertainty-aware probabilistic constrained clustering (UPCC), defining a canonical aleatoric relation through a heterogeneous observation process and analyzing its conditional identifiability. We introduce ProbPair, an angular pairwise objective for probabilistic relations, and build ECI-PP, an estimator--corrector--integrator framework that refines imperfect supervision via belief estimation, correction, and reliability-aware integration. Across challenging probabilistic supervision settings, experiments on diverse benchmarks show that ECI-PP outperforms state-of-the-art DCC methods and remains robust with a shared default configuration.

0.37

SIMQ: A Single Graph-based Index for Multi-Vector Query

cs.IR cs.DB ·2026-11-17 ·Yifan Lu, Jiabao Jin, Xiaoyao Zhong, Peng Cheng, Xiangyu Wang +5 more
publishedcode/data similarity 0.61
Abstract · under ICDE 2027 review, 13 pages

Multi-vector retrieval models such as ColBERT achieve state-of-the-art effectiveness by representing documents as sets of token-level vectors and scoring via MaxSim, but their high computational cost limits scalability to large corpora. Existing approximate methods face fundamental bottlenecks: centroid interaction matrix approaches require computing a full matrix at every query and rely on GPU-accelerated clustering, while data-oblivious compression methods yield unstable recall that requires repeated compensation. We propose SIMQ (Single graph Index for Multi-vector Query), a framework that bridges single-vector graph indices and multi-vector retrieval through data-aware sampling-based clustering and per-token graph navigation, simultaneously bypassing all aforementioned bottlenecks. SIMQ organizes all token vectors into fine-grained clusters via data-aware sampling, builds a single graph index over cluster centroids independently of PLAID's residual representation, and approximates the MaxSim score through per-token graph search without materializing any interaction matrix or relying on GPU acceleration. We provide theoretical analysis showing that, under a manifold assumption and successful cell retrieval, data-aware partitioning has a smaller expected approximation error than a data-oblivious partition. Building on this foundation, SIMQ+ further introduces count-based scoring and a dynamic candidate set to improve robustness across varying query conditions. Experiments on five benchmarks compare recall, throughput, and construction time against several baselines, primarily on CPU; large-scale PLAID k-means centroids are built on a separate GPU machine. SIMQ has been integrated into VSAG, an Ant Group's open-source vector search library.

0.32

GRAND-HC: Graph-Refined Author Name Disambiguation

cs.IR ·2026-08-24 ·Yuanhao Sun, Zhouyang Jin, Yi Xu, Luoyi Fu, Jiaxin Ding +3 more
publishedcode/datahot direction similarity 0.60
Abstract

From-Scratch Name Disambiguation (SND) groups papers sharing an ambiguous name into clusters of distinct real-world authors. Existing methods suffer from two critical limitations: (1) inherent long-tailed author distribution biases representation learning, causing over-merging of tail authors; (2) existing cluster number estimation methods are unreliable for long paper sequences, hindering large-scale deployment. We propose \textbf{GRAND-HC}, a complete end-to-end SND framework. We construct a heterogeneous paper graph via co-author, co-organization, and co-venue relations, using a graph attention network as the embedding backbone. \textbf{Harmony Contrastive Learning (HCL)} dynamically reweights training loss to suppress overfitting to prolific authors, learning discriminative embeddings. A \textbf{Graph-Refined Distance Matrix (GRDM)} leverages graph topology to optimize pairwise distances, further preventing tail author over-merging. Meanwhile, a lightweight \textbf{Paper Compression Module (PCM)} achieves accurate cluster number estimation across varying scales. Finally, Hierarchical Agglomerative Clustering outputs the final clusters. Extensive experiments demonstrate state-of-the-art macro F1 performance. GRAND-HC has been deployed in a billion-scale academic database. Source code: https://github.com/baokou-fw2/GRAND-HC.

0.62

LLM-Assisted Discovery of Typed Semantic Links for Ontology Network Construction

cs.CL cs.AI ·2026-10-01 ·Nouha Hayouni, Sheeba Samuel, Alsayed Algergawy
similarity 0.59
Abstract

Constructing typed, justified semantic links between ontologies is essential for enabling interoperability across heterogeneous and interdisciplinary knowledge domains. However, manually curating such links is difficult to scale. To address this challenge, we propose an end-to-end framework for ontology network construction that automates the discovery and generation of both intra-domain and inter-domain relationships. Our approach combines domain-adapted DistilBERT embeddings for dense contextual representation, clustering-based pre-filtering to reduce the candidate search space, and GPT-4o-driven relationship generation via iterative prompt engineering to produce semantically rich, interpretable links. Applied to ReproduceMeON - a network of 33 ontologies spanning machine learning, microscopy, computational science, and experimental workflow - the pipeline reduces approximately 800k raw concept pairs to 95k high-quality candidates. Human expert validation of 429 generated relationships by two independent annotators yields an overall precision of 80.19% (91.49% on high-certainty annotations) and an F1 of 0.890, with substantial inter-annotator agreement. Comparative experiments against five similarity-based baselines, including Sentence-BERT, show a substantial performance gap (best baseline F1 = 0.581), while an ablation study demonstrates that similarity-based methods alone fail to discriminate valid from invalid relationships (AUC approx 0.5) on the filtered candidate set. These findings highlight the necessity of LLM-based reasoning over concept roles and domain semantics for accurate relationship construction.

0.18

Hidden relationships in a document-derived property graph: top-k chunk embeddings and inverse-distance weighting over a dynamically evolving ontology

cs.CE cs.LG ·2026-08-31 ·Bilge Kaan Karamete, Hunter Casten
similarity 0.58
Abstract

Large language models extracting knowledge graphs from text capture only explicitly stated facts, often leaving semantically related entities disconnected across documents. We present an additive, engine-neutral second pass that discovers these latent ties without altering extracted facts. Each document is chunked and embedded once; top-k nearest- neighbor queries across existing chunks yield candidate node pairs via entity membership maps. Candidate pairs are scored using Shepard inverse-distance weighting with a rescaled chord distance metric, avoiding the threshold-collapsing flaw of affine cosine scoring behind a k-NN gate. Un-gated per-pair accumulators form a commutative monoid, ensuring the pipeline is strictly order-independent and scales incrementally without recomputing prior documents. Implemented across FalkorDB, Kinetica, ArangoDB, and Neo4j, our method shows that 768- and 240-dimensional embeddings retain 92% and 72% edge fidelity against a 3072-D baseline while achieving a 25x faster top-k formulation.

0.21

TopicMerge: A Divide and Conquer Approach to Topic Modeling

cs.CL cs.LG ·2026-10-14 ·Matthew Raffel, Lizhong Chen, Sai Munikoti, Sameera Horawalavithana
top venue similarity 0.58
Abstract · Findings of EMNLP 2026

Recent advancements in topic modeling have split into two main paths: efficient embedding-based methods that offer scalability but are often outperformed on standard clustering metrics, and Large Language Model (LLM) approaches that achieve state-of-the-art clustering performance but at the cost of prohibitive computational expense and poor scalability. This paper introduces TopicMerge, a novel multi-stage pipeline that bridges these approaches to achieve both state-of-the-art clustering performance and computational efficiency. TopicMerge first employs an efficient clustering pipeline to deliberately over-segment a document corpus into a large set of fine-grained, semantically pure micro-clusters, which are then given initial semantic labels. It then introduces a novel, iterative merging algorithm where an LLM, guided by local neighborhood context, arbitrates on consolidating candidate pairs. These approved merges are then selectively executed and semantically relabeled by the LLM, hierarchically building broader, more coherent topics. Extensive experiments on the Bills and Wiki datasets show that TopicMerge achieves state-of-the-art clustering performance while reducing required LLM calls by over 92% compared to document-level methods, offering a practical and scalable solution.

0.38