Fragility-Revealing Graph Perturbations for Ambiguous Sample Discovery in Short Text Clustering

Short text clustering is unstable when ambiguous samples are forced into hard clusters. Repeated clustering measures instability caused by algorithmic randomness. In contrast, we cast ambiguous sample discovery as a graph sparsification problem designed to reveal ambiguity. We propose the fragility-revealing graph perturbation (FRGP) method, an unsupervised method that aims to maximize the structural fragility of the semantic graph. We derive a semantic spanning subgraph that maximizes sensitivity to edge removal. Among such connected spanning subgraph, the minimum spanning tree has the least semantic distortion. Theoretically, under common assumptions on cluster separation and kNN connectivity, the entropy induced by these perturbations separates intra-cluster samples from structurally ambiguous samples. We further prove that the designed edge-weighted cutting mechanism gives a larger lower bound on the entropy gap than uniform cutting. Simulations verify the theoretical separation results. Experiments and ablation studies show that FRGP effectively identifies ambiguous samples, thereby making the retained clusters more compact for downstream use.