- Rating
- 2
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 3
Read review
Paper summary
This paper proposes Fragility-Revealing Graph Perturbations (FRGP) for ambiguous sample discovery in short text clustering. The method constructs a minimum spanning tree (MST), applies distance-aware edge perturbations, and measures assignment instability through entropy. Theoretical analysis and experiments on real-world and public datasets demonstrate its effectiveness in identifying ambiguous samples.
Critical strengths
(1)The paper offers an interesting perspective on ambiguous sample discovery by modeling structural fragility in semantic graphs. (2)The proposed framework is well motivated and supported by theoretical analysis of entropy separability.
Critical weaknesses
(1)In Section 3.1, the method samples only one connected component after MST edge cutting but still performs spectral clustering with the global number of clusters (k). If the sampled component contains only one semantic cluster, this may cause artificial cluster splitting. It is unclear how the subsequent label alignment avoids this issue or satisfies Assumption 4.5. (2)In Appendix C, ambiguous samples are generated as (x=\lambda x_a+(1-\lambda)x_b). When (\lambda=0) or (1), these samples follow the same Gaussian component distributions as intra-cluster samples. Under matched cluster sampling, they should be statistically indistinguishable. However, Table 5 reports AUC values of 0.9586 and 0.9788, respectively. These unexpectedly high results require further explanation. (3)The construction of reference ambiguity labels for public benchmarks is not clearly specified. Moreover, comparisons with simple ambiguity measures, such as clustering stability, assignment entropy, and cluster-margin scores, are missing. Table 3 also shows that A1 achieves higher Precision at the 5% and 10% thresholds than FRGP, suggesting that its advantage is not consistent across all evaluation settings. (4) The reference partition is constructed by removing the longest MST edges, but these edges are not guaranteed to correspond to true cluster boundaries, particularly under cluster imbalance, bridge points, or near-tied edge lengths. Errors in this partition may propagate through Hungarian alignment and distort the entropy scores. The paper does not evaluate the quality or sensitivity of this reference partition. (5) In the real-world experiment, dish names are first passed to an LLM with a prompt that explicitly asks for category-level descriptions before embedding. This may inject category information into the representations and weaken the claim that the method is fully label-free. The paper lacks an ablation using raw-text embeddings or descriptions generated without explicit category cues.
Questions for authors
(1)Could the authors clarify why spectral clustering uses (k) clusters on a single sampled component and explain how this design is consistent with Assumption 4.5? (2)Could the authors explain the unexpectedly high AUC values at (\lambda=0) and (\lambda=1) in Table 5? (3)Could the authors clarify the ambiguity-label construction protocol and include comparisons with simpler ambiguity detection baselines?
3 comments
2. Correction to the synthetic experiments (W2, Q2)
Thank you for noting the unexpectedly high AUCs at and in Table 5. You are correct: endpoint interpolated samples share the within-cluster distribution and should be indistinguishable. We found that the generation code used , adding noise with excessively large variance beyond the stated formula. This introduced an unintended distinguishing signal at the endpoints, contrary to the stated interpolation model. We apologize for the inconsistency between the code and Appendix C.
After removing the extra noise (), the endpoint AUCs are 0.5005 and 0.5059, both close to chance, as expected. The corrected mean AUCs are shown below.
Table R3. Corrected mean AUCs across interpolation weights with no extra noise ().
| 0 | 0.05 | 0.1 | 0.3 | 0.5 | 0.7 | 0.9 | 0.95 | 1 | |
|---|---|---|---|---|---|---|---|---|---|
| AUC | 0.5005 | 0.7604 | 0.7678 | 0.8256 | 1.0000 | 0.8097 | 0.7899 | 0.7519 | 0.5059 |
At , interpolated samples retain within-cluster variability but are centered in expectation midway between the two cluster means, placing them between the source clusters on average and providing a geometric basis for distinguishing them from within-cluster samples. In the corrected experiment, FRGP achieves a reported AUC of 1.0000 at this midpoint, while endpoint AUCs return to approximately 0.5. With , results from varying all other simulation parameters also match our expectations for FRGP. Together, these results show that FRGP successfully identifies intermediate interpolated samples without relying on extra noise absent from the stated interpolation formula.
3. Ambiguity-label construction and simple baselines (W3, Q3)
Thank you for requesting clearer label construction and simpler baselines. AG News and StackOverflow have semantic category labels for each text. Excluding out-of-domain samples, we used an LLM to label texts exhibiting characteristics of two or more categories as ambiguous. NLU++ has utterance-level intent annotations; since multiple annotated elements can express one coherent request, we labeled single-intent utterances stable and those with four to six intents ambiguous. Table 2 and the comparison below use these same rules, to be added to revised Section 5 and Appendix D.
We added three simple measures: neighbor clustering stability, averaging over fixed neighbors, with the co-assignment frequency across repeated k-means runs (the factor scales scores to without changing rankings or AUC); soft-assignment entropy, the normalized entropy of distance-based soft assignments to k-means centers; and relative cluster margin, scoring smaller relative distance gaps between the nearest and second-nearest centers as more ambiguous.
Table R4. Comparison of FRGP and simple baselines on AUC, SS, and ICS.
| Method | AG News AUC | AG News SS | AG News ICS | StackOverflow AUC | StackOverflow SS | StackOverflow ICS | NLU++ AUC | NLU++ SS | NLU++ ICS |
|---|---|---|---|---|---|---|---|---|---|
| FRGP | 0.7813 | 0.0971 | 0.5035 | 0.7271 | 0.1506 | 0.5898 | 0.8125 | 0.1441 | 0.6485 |
| Neighbor clustering stability | 0.6437 | 0.0745 | 0.4390 | 0.6693 | 0.1273 | 0.5165 | 0.6333 | 0.2016 | 0.7207 |
| Soft-assignment entropy | 0.7592 | 0.0838 | 0.4450 | 0.5556 | 0.1113 | 0.5284 | 0.3814 | 0.3286 | 0.8026 |
| Relative cluster margin | 0.7396 | 0.0738 | 0.4404 | 0.8239 | 0.1347 | 0.5221 | 0.4394 | 0.3829 | 0.7888 |
FRGP leads in AUC on AG News and NLU++ and in SS and ICS on AG News and StackOverflow, with two exceptions. Relative cluster margin has higher StackOverflow AUC (0.8239 vs. 0.7271), so FRGP's ranking advantage is dataset-dependent. On NLU++, soft-assignment entropy leads in ICS (0.8026) despite an AUC of 0.3814, while relative cluster margin leads in SS (0.3829). Both outperform FRGP in SS and ICS but have substantially lower AUCs: better downstream metrics do not necessarily mean better ambiguity detection and require interpretation alongside annotation-based AUC. The NLU++ evaluation subset has 62 categories averaging fewer than 20 samples per cluster; all three simple measures fall below FRGP's AUC of 0.8125 in this sparse setting.
For the reviewer's ablation concern, Table 3 shows Precision at 5%, 10%, and 15% selection rising from 0.5625 to 0.6875 and 0.7625 for FRGP, but dropping markedly from 0.8500 to 0.7562 and 0.5541 for A1. Thus, A1's high Precision is concentrated in a small top-ranked subset and declines with broader selection. FRGP's substantially higher Precision at 15% (0.7625 vs. 0.5541) and overall AUC (0.8569 vs. 0.7144) support stronger ambiguity detection beyond this small subset and better ambiguous-versus-stable discrimination across the full ranking.
4. Quality and sensitivity of the reference partition (W4)
Assumption 4.5 requires that conditional on a sample being included, the probability of clustering and alignment failure is bounded by , with in the asymptotic analysis. Reference-induced alignment errors are included in this condition. Theorem 4.8 explicitly accounts for the error through , and also enters the effective boundary-switching probability . Thus, the analysis accommodates imperfect clustering and alignment while retaining an explicit condition on their errors; it does not require exact recovery by the reference partition itself.
Empirically, the complete FRGP pipeline, including the chosen reference partition and Hungarian alignment, achieves AUCs of 0.7813, 0.7271, and 0.8125 on AG News, StackOverflow, and NLU++, respectively (Table 2). These results demonstrate effective ambiguity detection with the reference partition used in our experiments. Because the evaluation uses the final assignment-entropy scores after alignment, it assesses the combined effect of reference-based alignment and the other pipeline components. The results therefore provide direct empirical support for the practical effectiveness of the current design on the evaluated datasets.
5. Category cues in the LLM-generated descriptions (W5)
Thank you for raising the concern about category cues in the LLM-generated descriptions. In the food-delivery application, dish names can contain distracting characters, emojis, and auxiliary descriptions. Our motivation for introducing the LLM prompt was to obtain clearer semantic representations of these noisy inputs, rather than to introduce category descriptions for their own sake. Although the prompt produces category-level descriptions, as disclosed in Appendix F, these are generated from the dish names without supplying ground-truth category or ambiguity labels.
On AG News, StackOverflow, and NLU++, we directly encode the original texts into 1,024-dimensional embeddings using BGE-M3, without relying on LLM-generated category-level descriptions. FRGP achieves AUCs of 0.7813, 0.7271, and 0.8125, respectively (Table 2). Reference ambiguity labels are used only for evaluation and are not provided to FRGP. These results support FRGP's ability to effectively identify ambiguous samples without relying on additional label information. The LLM preprocessing used in the food-delivery application is therefore not a prerequisite for the effectiveness of FRGP.
We would like to express our gratitude to Reviewer Xz77 for recognizing the interesting perspective of discovering ambiguous samples through structural fragility in semantic graphs, as well as the motivation of our framework and its theoretical support through entropy-separability analysis. We appreciate the reviewer's detailed comments, which help us clarify the method and strengthen its evaluation. Below, we address each concern and question in detail.
1. Spectral clustering with k clusters on a single sampled component (W1, Q1)
Thank you for pointing out that a sampled component may contain only one semantic cluster while spectral clustering still uses k centers. We agree that, in such rounds, the k-way split can subdivide a single semantic cluster. Hungarian alignment matches the resulting cluster labels to the reference partition; it does not itself undo this subdivision. We clarify below how this issue relates to our theoretical assumptions and what the existing control experiment establishes.
On the theory side, errors caused by such subdivisions fall within the clustering and alignment failures considered in Assumption 4.5, whose probability conditional on a sample being included is bounded by εn. Theorem 4.8 accounts for this error through g(2εn), separately from the finite-sampling error. The entropy-separation guarantee therefore requires these errors to be controlled; it does not require every round to recover the correct partition.
The control experiment reported in our response to Reviewer bk2V (item 1) provides complementary evidence. The graph-based control retains ambiguity-detection information without splitting each sampled component into k clusters. Without spectral clustering, k-means, or Hungarian matching, it achieves reported mean AUCs of 0.69–0.73 on the food-delivery evaluation set. These results support the ability of graph perturbations and component-based label assignment to distinguish annotated ambiguous samples from stable ones without within-component clustering.
The eigengap heuristic, the spectral embedding, k-means, and Hungarian alignment are all in step 5 of FRGP. We therefore keep steps 1–4 and 6 unchanged and replace only step 5, using the same perturbation rounds and the same sampled vertex sets in both versions. Table R1 summarizes the two versions.
Table R1. The two versions share steps 1–4 and 6 and differ only in step 5.
The control computes the same normalized assignment entropy as FRGP. To limit the influence of very small components, we require each component to contain at least 20 or 50 nodes, in both the reference partition and the perturbation cuts. We report the mean AUC under two settings: sampling one component uniformly, and using all components.
Table R2. AUCs without spectral clustering under different component-selection settings.
In this control, label changes across rounds arise from graph partitioning and deterministic mapping to the reference clusters, with no variation from spectral-coordinate selection, k-means optimization, or Hungarian matching. The reported results therefore provide evidence that ambiguity-detection information is present in the graph-based construction even when within-component k-way splitting is absent. This supports the graph-perturbation mechanism underlying FRGP.