acceptodds
Under review as a conference paper at ICLR 2027

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

Abstract

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.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
Short Text Clustering, Ambiguous Sample Discovery, Graph Structural Fragility, Minimum Spanning Tree, Clustering Stability

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_Xz77OpenReview ↗
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 C(T)C(T) is constructed by removing the k−1k-1 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

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 kk centers. We agree that, in such rounds, the kk-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\varepsilon_n. Theorem 4.8 accounts for this error through g(2εn)g(2\varepsilon_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 kk 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.

StepFRGP (as submitted)FRGP without spectral clustering
1–2Embeddings →\to symmetric kNN graph GKG_K; T=MST(GK)T=\mathrm{MST}(G_K); reference partition C(T)C(T) obtained by removing the k−1k-1 longest edgesidentical
3LL rounds; each round removes k−1k-1 distinct edges sampled without replacement with probability proportional to dijMSTd^{\mathrm{MST}}_{ij}identical, reusing the same LL rounds
4Uniformly sample one component S(ℓ)S^{(\ell)}; nodes outside S(ℓ)S^{(\ell)} receive the null label ⊥\botidentical draws; a variant uses all kk components
5Spectral embedding with eigengap-selected dimension r(ℓ)r^{(\ell)} →\to k-means with kk centers →\to Hungarian alignment to C(T)C(T)Component identity: each component takes the label of the reference cluster sharing the most nodes, arg⁡max⁡r∣Cj(ℓ)∩Cr∣\arg\max_r \lvert C^{(\ell)}_j \cap C_r \rvert; no eigengap, no k-means, no alignment
6Normalized per-node assignment entropy across roundsidentical formula

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.

Component selectionMinimum size 20Minimum size 50
Uniformly sample one component0.68760.6997
Use all components0.72710.7324

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 kk-way splitting is absent. This supports the graph-perturbation mechanism underlying FRGP.

2. Correction to the synthetic experiments (W2, Q2)

Thank you for noting the unexpectedly high AUCs at λ=0\lambda=0 and λ=1\lambda=1 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 x=λxa+(1−λ)xb+εx=\lambda x_a+(1-\lambda)x_b+\varepsilon, 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 (σ=0\sigma=0), 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\sigma=0).

λ\lambda00.050.10.30.50.70.90.951
AUC0.50050.76040.76780.82561.00000.80970.78990.75190.5059

At λ=0.5\lambda=0.5, 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 σ=0\sigma=0, 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 4pij(1−pij)4p_{ij}(1-p_{ij}) over fixed neighbors, with pijp_{ij} the co-assignment frequency across repeated k-means runs (the factor 44 scales scores to [0,1][0,1] 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.

MethodAG News AUCAG News SSAG News ICSStackOverflow AUCStackOverflow SSStackOverflow ICSNLU++ AUCNLU++ SSNLU++ ICS
FRGP0.78130.09710.50350.72710.15060.58980.81250.14410.6485
Neighbor clustering stability0.64370.07450.43900.66930.12730.51650.63330.20160.7207
Soft-assignment entropy0.75920.08380.44500.55560.11130.52840.38140.32860.8026
Relative cluster margin0.73960.07380.44040.82390.13470.52210.43940.38290.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 εn\varepsilon_n, with εn→0\varepsilon_n\to0 in the asymptotic analysis. Reference-induced alignment errors are included in this condition. Theorem 4.8 explicitly accounts for the error through g(2εn)g(2\varepsilon_n), and εn\varepsilon_n also enters the effective boundary-switching probability qiFRGPq_i^{\mathrm{FRGP}}. 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.

Reviewer_4A73OpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes an unsupervised graph perturbation method named FRGP, which quantifies the clustering assignment instability (entropy) of samples by extracting a minimum spanning tree (MST) and performing distance-aware edge cutting, thereby effectively identifying and separating ambiguous samples in short text clustering and significantly improving the compactness and stability of downstream clustering.

Critical strengths
  1. FRGP formulates ambiguous sample discovery as a problem of maximizing graph structural fragility, and rigorously proves that the mechanism based on the Minimum Spanning Tree (MST) and distance-aware cutting provides a larger lower bound on entropy separation, thereby effectively distinguishing intra-cluster samples from structurally ambiguous ones.

  2. Through kNN and MST graph sparsification along with subgraph sampling, this method significantly reduces time and space complexity while achieving optimal ambiguous sample identification rates and more compact clustering quality across both real-world scenarios and public benchmark datasets.

Critical weaknesses
  1. On the largest real-world dataset, due to the lack of reliable ground-truth labels for ambiguous samples, the paper can only evaluate the method using label-free downstream clustering metrics.

  2. Although the paper reduces the complexity of the spectral clustering phase through MST sparsification, the initial construction of the exact kNN graph still incurs an O(n2d)O(n^2d) time complexity, and requires executing LL rounds of spectral clustering and Hungarian algorithm alignment, which still presents a significant computational bottleneck in truly large-scale short-text scenarios.

Questions for authors
  1. FRGP employs the Hungarian algorithm to align the clustering results of local subgraphs with the global reference partition. If a perturbation causes drastic structural changes in the subgraph (e.g., a local cluster being completely scattered), would this forced alignment introduce artificial noise and pollute the final entropy calculation?

  2. The paper's theoretical proof relies on the assumption of "strongly separated semantic clusters." However, in high-dimensional embedding spaces for short texts, semantic overlap is prevalent, making strict geometric separation difficult to guarantee. If the inter-cluster boundaries in real-world data are highly overlapping, would this theoretical guarantee degrade significantly?

2 comments

We greatly appreciate Reviewer 4A73's recognition of our structural-fragility formulation, entropy-separation theory, and the computational benefits of graph sparsification and subgraph sampling, along with the constructive comments on evaluation, scalability, label alignment, and theoretical assumptions. We address each concern and question in detail below.

1. Ambiguity rankings without spectral clustering and alignment (Q1)

Thank you for asking whether forced Hungarian alignment introduces artificial noise when perturbations scatter a local cluster. Each round's random MST cuts only sample vertices; spectral clustering uses their induced subgraph in the original kNN graph, preserving all edges between retained vertices. Hungarian alignment maximizes overlap with the fixed reference partition by relabeling clusters without changing groupings. It is a standard tool for optimal label matching, used for reference-based relabeling in mixture models (Cron & West, 2011) and maximum-overlap matching between network partitions (Peixoto, 2021). Our theory allows clustering and alignment errors across rounds: under Assumption 4.5, Theorem 4.8 accounts for them via g(2εn)g(2\varepsilon_n), separately from finite-sampling error. The entropy-separation guarantee requires controlled errors; it does not mean relabeling always resolves arbitrary cluster splitting or merging.

To test ranking dependence on alignment, we reproduce the control from our response to Reviewer bk2V (item 1). Graph construction and perturbation alone separate ambiguous from stable samples; spectral clustering further improves AUC but is unnecessary for this separation. Without spectral clustering, mean AUCs of 0.69–0.73 on the food-delivery evaluation set indicate retained discrimination between samples annotated as ambiguous or stable.

The eigengap heuristic, spectral embedding, k-means, and Hungarian alignment are all in FRGP's step 5. We replace only this step, keeping steps 1–4 and 6, perturbation rounds, and sampled vertex sets identical across versions. Table R1 summarizes both.

Table R1. The two versions share steps 1–4 and 6 and differ only in step 5.

StepFRGP (as submitted)FRGP without spectral clustering
1–2Embeddings →\to symmetric kNN graph GKG_K; T=MST(GK)T=\mathrm{MST}(G_K); reference partition C(T)C(T) obtained by removing the k−1k-1 longest edgesidentical
3LL rounds; each round removes k−1k-1 distinct edges sampled without replacement with probability proportional to dijMSTd^{\mathrm{MST}}_{ij}identical, reusing the same LL rounds
4Uniformly sample one component S(ℓ)S^{(\ell)}; nodes outside S(ℓ)S^{(\ell)} receive the null label ⊥\botidentical draws; a variant uses all kk components
5Spectral embedding with eigengap-selected dimension r(ℓ)r^{(\ell)} →\to k-means with kk centers →\to Hungarian alignment to C(T)C(T)Component identity: each component takes the label of the reference cluster sharing the most nodes, arg⁡max⁡r∣Cj(ℓ)∩Cr∣\arg\max_r \lvert C^{(\ell)}_j \cap C_r \rvert; no eigengap, no k-means, no alignment
6Normalized per-node assignment entropy across roundsidentical formula

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.

Component selectionMinimum size 20Minimum size 50
Uniformly sample one component0.68760.6997
Use all components0.72710.7324

In this control, cross-round label changes arise solely from graph partitioning and deterministic mapping to reference clusters, with no variability from spectral-coordinate selection, k-means optimization, or Hungarian matching. With all other steps shared, the AUC difference measures the combined contribution of spectral clustering and alignment: comparable rankings remain without them, while adding them yields further gains.

We further evaluated alignment-free ambiguity detection with fixed sampled vertex sets and spectral-clustering results. For adjacent nodes, we computed co-assignment frequency pijp_{ij} over jointly sampled rounds and averaged 4pij(1−pij)4p_{ij}(1-p_{ij}) over observed neighbors (the factor of 4 scales scores to [0,1][0,1] without changing rankings or AUC). This score is independent of the reference partition and cluster numbering. Across five seeds, AUCs are 0.7363 ± 0.0304 on AG News and 0.7541 ± 0.0186 on StackOverflow. These results demonstrate useful ambiguity information in the sampled clusterings recoverable without Hungarian alignment, directly supporting effective ambiguity detection beyond this particular alignment procedure.

2. Strong separation under semantic overlap (Q2)

Thank you for asking whether the theoretical guarantee degrades when cluster boundaries overlap. Assumption 4.1 requires strong separation only among the cores of stable clusters, not among all samples. Assumption 4.3 explicitly allows ambiguous samples to lie between several cluster cores and to connect to multiple semantic clusters, so semantic overlap near cluster boundaries is one of the situations the method is designed for, not a violation of its assumptions.

Increased overlap may weaken the separation of stable cores and increase clustering and alignment errors, potentially reducing the entropy-separation bound in Theorem 4.8 under its stated assumptions. The guarantee remains conditional on the error terms being controlled. Empirically, the public benchmarks and the food-delivery dataset all contain substantial boundary overlap, and FRGP still achieves the AUCs reported in Tables 2 and 3.

Identifying the overlapping samples is useful in two ways. It improves the stability of clustering on the remaining stable samples and yields clearer cluster boundaries. It also lets the application handle ambiguous samples separately: in the food-delivery data, ambiguous items are often bundled meals such as a cola-and-hamburger combo, which share characteristics of both the beverage and fast-food categories; once identified, the platform can place them in a dedicated category or send them for manual labeling.

3. Ambiguity labels and evaluation on the real-world dataset (W1)

Thank you for highlighting the need to clarify the source of the ambiguity annotations and the evaluation protocol for the largest real-world dataset. The ambiguity labels for the food-delivery dataset were manually annotated by industry professionals following the platform's category-operating rules. In addition to the downstream clustering metrics in Table 1, Table 3 reports AUC and Precision against these manual labels, so ambiguity detection on this dataset is also evaluated directly against annotations; FRGP reaches an AUC of 0.8569 there. We will state the annotation source in the revised Section 5 and clarify the evaluation purposes of the two tables.

4. Computational cost at larger scale (W2)

Thank you for raising the computational cost of exact kNN construction and of the repeated clustering and alignment rounds. We agree that building the exact kNN graph costs O(n2d)O(n^2 d) and is a major computational cost; this cost is shared by all methods that start from an exact kNN graph and is not specific to FRGP. FRGP reduces the remaining costs through one-time kNN construction, sparse graph storage, and spectral clustering on sampled subgraphs. As detailed in Appendix G, the working memory is O(nd+nK+nk)O(nd+nK+nk), and Hungarian alignment costs O(k3)O(k^3) per round, where kk is the number of clusters, not the number of samples.

FRGP is deployed on our industrial partner's platform and meets its runtime requirements. On the food-delivery dataset with about 28,000 menu items and 1,792-dimensional ACGE embeddings, Table 1 reports a runtime of 20 minutes 57 seconds on a server with an Intel Xeon Gold 6271 CPU, an NVIDIA Tesla P100 GPU with 16 GB of memory, and 62 GB of system RAM.

To assess large-scale feasibility, we measured FRGP's wall-clock runtime on datasets containing 100,000 samples with 1792-dimensional embeddings. The runtime was 1 hour 56 minutes. The result demonstrates that FRGP can process large-scale datasets within an acceptable time, supporting its practical feasibility for large-scale ambiguity discovery.

 

References

[1] Cron, A. J., & West, M. (2011). Efficient Classification-Based Relabeling in Mixture Models. The American Statistician, 65(1), 16–20.

[2] Peixoto, T. P. (2021). Revealing Consensus and Dissensus between Network Partitions. Physical Review X, 11(2), 021003.

Reviewer_bk2VOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper proposes Fragility Revealing Graph perturbation (FRGP) approach to identify "ambiguous" samples in short text clustering applications, although it can be used on any modality once we have the embeddings and can compute a similarity between the samples.

Some short texts do not provide enough information to have a clear semantic class assigned to them. If a short sentence can have multiple plausible interpretations, and thus, semantic groups, then the decision fuziness is a reflection of the input, not a limitation of the clustering method. A simpler example: we ask a botanist to group pictures of flowers based on their type, but some pictures are too blurry to make up the flower type. Their inability to do so does not mean a lack of expertise. The goal of the suggested manuscript is to identify those "blurry" samples instead of using them against the botanist.

The proposed method works as follows:

  • Constructs kk-NN graph from text embeddings, compute a minimum spanning tree, and obtains a reference partition by removing the tree's longest k−1k-1 edges.
  • Each round removes k−1k-1 edges with probabilities proportional to their distances, samples one resulting connected component, runs spectral clustering on the original kNN graph induced by those nodes, and aligns the labels to the reference partition.
  • Normalized assignment entropy across sampled rounds gives each point's ambiguity score.

The authors evaluate their ambiguity detection and the compactness of clusters after filtering high-scoring points.

Critical strengths

The ability to identify points with uncertain cluster membership is a useful one, as it allows separation the clustering algorithm limitation from data-dependent limitation. The continuous ranking also allows dynamic selection of samples to be reviewed instead of a fixed threshold.

The method is generally easy to follow, and the paper provides pseudocode, prompts, ablations, and conditional entropy bounds and compares between ambiguity and the compactness of the retained clusters.

The reported AUC gains merit consideration: FRGP obtains 0.7813, 0.7271, 0.8125 on AG News, StackOverflow, and NLU++, respectively, exceeding the three mixed-membership baselines, although still require a reproducible definition of the evaluation targets before any significance assessment.

Critical weaknesses

The most noticeable item is the order at which quantities are used before they defined mathematically: "bridge", δij,T,Gk\delta_{ij}, \mathcal{T}, G_k in Definition 3.1,F\mathcal{F} just before Assumption 4.1 at L252, L253 "Tr(i)T_{r(i)} denote a nearby semantic cluster" (one to many mapping?, what is "nearby"). These tiny discrepancies when they accumulate create a feeling of going through a rugged mathematical presentation. If they're defined in the appendix, the definitions should be referenced.

The main methodical weakness comes from relying on the spectral clustering and its related heuristics. FRGP measures the variability of the particular spectral clustering pipeline under graph modifications chosen by the method: the spectral dimension is selected by an eigengap heuristic, followed by k-means and label alignment. So the high assignment entropy may reflect sensitivity of the spectral embedding and rank selection even when the underlying texts have clear semantic memberships. The experiments do not isolate these contributions from semantic ambiguity.

Spectral-clustering (SC) sensitivity has an established literature such as Huang et al. (2008), Spectral Clustering with Perturbed Data which relates clustering error under data perturbations to changes in Laplacian eigenvectors. Andreotti et al. (2021), Measuring the stability of spectral clustering study the distance to a vanishing spectral gap, and Peng and Yoshida (2020), Average Sensitivity of Spectral Clustering, analyze sensitivity to random edge deletions and provide stability guarantees under graph-spectrum conditions (which is likely the most relevant). Thus, SC is not uniformly stable and depends on the relevant spectral separation and perturbation regime.

A well defined method should separate graph-perturbation effects from k-means variability, and compare alternative clustering routines under the same sampled vertex sets. Assumption 4.5 requires vanishing error on core sample does not establish that the implemented pipeline avoids these sources of instability.

Questions for authors
  • What evidence distinguishes semantic ambiguity from sensitivity of the spectral-clustering pipeline?
  • Could you separate graph-perturbation variability from k-means and alignment variability?
  • Does FRGP produce similar ambiguity rankings with alternative clustering routines applied to the same sampled vertex sets?
  • Can Assumption 4.5’s vanishing clustering and alignment error be justified for the actual sampling and clustering procedure?
3 comments

We are grateful to Reviewer bk2V for recognizing the value of identifying samples with uncertain cluster membership, the clarity of our method, and the reported gains in ambiguity detection. We appreciate the reviewer's thoughtful comments on mathematical presentation and the sources of assignment instability. Below, we address each concern and question in detail.

1. Ambiguity rankings without spectral clustering (W2, Q1)

Thank you for asking what evidence distinguishes semantic ambiguity from the sensitivity of spectral clustering and its heuristics. The graph construction and perturbation alone already separate ambiguous samples from stable ones; spectral clustering improves the AUC further but is not necessary for this separation. It achieves mean AUCs of 0.69–0.73 on the food-delivery evaluation set, demonstrating its ability to distinguish samples annotated as ambiguous from those annotated as stable without these components. We describe this control experiment below. Item 3 further examines within-graph initialization variability and between-graph variability.

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.

StepFRGP (as submitted)FRGP without spectral clustering
1–2Embeddings →\to symmetric kNN graph GKG_K; T=MST(GK)T=\mathrm{MST}(G_K); reference partition C(T)C(T) obtained by removing the k−1k-1 longest edgesidentical
3LL rounds; each round removes k−1k-1 distinct edges sampled without replacement with probability proportional to dijMSTd^{\mathrm{MST}}_{ij}identical, reusing the same LL rounds
4Uniformly sample one component S(ℓ)S^{(\ell)}; nodes outside S(ℓ)S^{(\ell)} receive the null label ⊥\botidentical draws; a variant uses all kk components
5Spectral embedding with eigengap-selected dimension r(ℓ)r^{(\ell)} →\to k-means with kk centers →\to Hungarian alignment to C(T)C(T)Component identity: each component takes the label of the reference cluster sharing the most nodes, arg⁡max⁡r∣Cj(ℓ)∩Cr∣\arg\max_r \lvert C^{(\ell)}_j \cap C_r \rvert; no eigengap, no k-means, no alignment
6Normalized per-node assignment entropy across roundsidentical formula

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.

Component selectionMinimum size 20Minimum size 50
Uniformly sample one component0.68760.6997
Use all components0.72710.7324

In this control, the label changes across rounds come only from the graph partition and the deterministic mapping to the reference clusters; there is no variation from spectral-coordinate selection, k-means optimization, or Hungarian matching. Since the two versions share all other steps, the difference in AUC measures the total contribution of spectral clustering and alignment: comparable rankings are obtained without them, and they add a further gain. We do not claim that spectral clustering is unimportant; item 3 below separates initialization variability from graph-related variability to show where its contribution lies. We will report the comparison on the same datasets, with dataset names and seeds, in the revised appendix.

2. Relation to the spectral-clustering sensitivity literature (W2)

Thank you for pointing us to this literature. We agree that spectral clustering is not uniformly stable and that its behavior depends on the spectral separation and on the perturbation regime. Huang et al. (2008) relate the clustering error under data perturbation to changes in the Laplacian eigenvectors. Andreotti et al. (2021) characterize stability through the distance to a vanishing kk-th spectral gap, and distinguish structured from unstructured perturbations. Peng and Yoshida (2020) derive conditional bounds on the average sensitivity of spectral clustering under random edge removal, involving λ2/λ32\lambda_2/\lambda_3^2 in the two-cluster case, and report that spectral clustering is stable when the input graph has cluster structure.

Our setting differs in two respects. First, rather than deleting input-graph edges uniformly at random, we cut MST edges with probabilities proportional to their cosine distances, favoring long, weak links. Second, we evaluate each node's cross-round assignment entropy against ambiguity annotations, rather than single-run clustering error. To test whether high entropy reflects spectral-clustering sensitivity even for semantically clear texts, item 1 removes spectral clustering entirely, while item 3 separates initialization from graph-related variability. Both yield ambiguity rankings with AUCs well above chance, consistent with Peng and Yoshida's (2020) finding that spectral clustering is stable on graphs with cluster structure and becomes less stable as the relevant spectral gap shrinks. We will cite and discuss these three works in the revised Section 4.

3. Separating graph-perturbation variability from k-means and alignment variability (Q2)

We conducted two complementary experiments. The first separates within-graph initialization variability from between-graph variability using an alignment-free co-assignment measure. The second decomposes FRGP's assignment entropy into a within-graph term and a graph-related term, assessing whether the latter remains informative about the ambiguity annotations.

On AG News and StackOverflow, we used 100 sampled subgraphs and 10 k-means initialization seeds per subgraph, keeping the spectral coordinates fixed within each subgraph. Let pij(g)p_{ij}^{(g)} denote the frequency with which two neighboring nodes are placed in the same cluster across initializations. We decomposed the total variability as:

4pˉij(1−pˉij)=4Eg[pij(g)(1−pij(g))]+4Var⁡g(pij(g)).4\bar{p}_{ij}(1-\bar{p}_{ij}) = 4\mathbb{E}_g[p_{ij}^{(g)}(1-p_{ij}^{(g)})] + 4\operatorname{Var}_g(p_{ij}^{(g)}).

The first term on the right captures within-graph initialization variability, and the second captures between-graph variability. The factor of 4 scales the score to [0,1][0,1] without changing its ranking or AUC.

Averaging each term over the neighbors of a node gives a node-level score. This calculation needs no reference matching or Hungarian alignment, because whether two nodes share a cluster does not depend on how the clusters are numbered. The AUC of each term is reported below.

Table R3. AUCs of the total, within-graph, and between-graph co-assignment scores.

ScoreAG NewsStackOverflow
Total0.81370.7450
Within-graph initialization0.64240.6753
Between-graph0.81340.7400

We additionally examined FRGP's assignment entropy on the food-delivery dataset using the same design, retaining the original alignment:

H(Zi)=EG[H(Zi∣G)]+I(Zi;G).H(Z_i)=\mathbb{E}_G[H(Z_i\mid G)]+I(Z_i;G).

The first term on the right is the within-graph term, and the second is the graph-related term. All terms are normalized by log⁡k\log k. The following table reports their node-wise means and the AUC of the graph-related term.

Table R4. Assignment-entropy decomposition under the original alignment.

AlignmentMean total entropyMean within-graph termMean graph-related termGraph-related AUC
Original0.65100.44510.20590.6382

These results directly show that variation across perturbed graphs carries substantial information for ambiguity detection. On AG News and StackOverflow, the alignment-free between-graph term achieves AUCs of 0.8134 and 0.7400—nearly matching the total scores (0.8137 and 0.7450) and exceeding the within-graph initialization scores (0.6424 and 0.6753). On the food-delivery dataset, the graph-related term of FRGP's assignment entropy achieves an AUC of 0.6382 under the original alignment, capturing the combined response of spectral embedding, clustering, and alignment to sampled-graph changes. Together, these findings support graph perturbation as an effective mechanism for revealing ambiguity, retaining predictive information after within-graph initialization variability is separated out.

4. Alternative clustering routines on the same sampled vertex sets (Q3)

The table below compares three alternative clustering routines. FRGP performs well with all three alternatives, indicating that its scores retain useful information for identifying ambiguous samples.

Table R5. AUCs of FRGP with alternative clustering methods.

Clustering methodAUC
K-means0.6726
Ward0.7518
Diagonal GMM0.7152

5. Justification of Assumption 4.5 (Q4)

Theoretically, established spectral-clustering consistency results support Assumption 4.5. Rohe et al. (2011) and Lei and Rinaldo (2015) establish vanishing misclustering rates under suitable graph regularity and spectral separation conditions, while Su et al. (2020) and Deng et al. (2021) establish exact recovery. These results support vanishing clustering errors in well-separated graphs. For alignment, Cron and West (2011) establish Hungarian matching as a method for optimal label matching to a fixed reference partition. The consistency results are asymptotic and concern well-separated graph models, supporting the plausibility of Assumption 4.5 without verifying it for our finite-sample procedure. Theorem 4.8 explicitly accounts for clustering and alignment error through g(2εn)g(2\varepsilon_n), separately from finite-sampling error; its entropy-separation guarantee remains conditional on controlling this error.

Empirically, two experiments (item 1 and Reviewer 4A73, Q1) show mean AUCs of approximately 0.70 for MST-based perturbation and subgraph sampling without spectral clustering or alignment, and around 0.75 when pairwise co-assignment replaces Hungarian alignment. Full FRGP achieves 0.7813 on AG News and generally outperforms the main-experiment baselines. These results suggest that MST-based perturbation and subgraph sampling provide the primary contribution, with spectral clustering and alignment further improving ambiguity detection. Consistent with this design, when ambiguous samples are prevalent, the k−1k-1 cuts mainly perturb the global graph rather than recover exactly kk semantic clusters. Subgraph spectral clustering helps recover stable-sample labels, while ambiguous samples' weak connections to multiple clusters increase perturbation sensitivity, producing cross-round assignment changes.

6. Notation and order of definitions (W1)

Thank you for noting that several quantities precede mathematical definitions. We agree that these ordering issues collectively hinder readability and have revised the definitions and their presentation in the manuscript to clarify potential ambiguities and improve readability.

The revision clarifies graph/tree and sample-set notation: Section 3.1 defines a bridge before equation (1), and Definition 3.1 introduces T(GK)\mathcal{T}(G_K) as all spanning trees of GKG_K. Before its assumptions, Section 4 introduces the intra-cluster sample set T\mathcal{T}, its ambiguous-sample complement F\mathcal{F}, and the clusters Tr\mathcal{T}_r comprising T\mathcal{T}. “Nearby semantic cluster” explicitly refers to Assumption 4.3: each i∈Fi\in\mathcal{F} has distinct nearby clusters Ta(i)\mathcal{T}_{a(i)} and Tb(i)\mathcal{T}_{b(i)} satisfying min⁡j∈Ta(i)δij≤Δnear\min_{j\in\mathcal{T}_{a(i)}}\delta_{ij}\le\Delta_{\mathrm{near}} and min⁡j∈Tb(i)δij≤Δnear\min_{j\in\mathcal{T}_{b(i)}}\delta_{ij}\le\Delta_{\mathrm{near}}, where δij\delta_{ij} denotes cosine distance between text embeddings and Δin<Δambiguous≤Δnear<Δout\Delta_{\mathrm{in}}<\Delta_{\mathrm{ambiguous}}\le\Delta_{\mathrm{near}}<\Delta_{\mathrm{out}}. Thus, a(i)a(i) and b(i)b(i) index distinct nearby clusters for the same sample, without requiring unique cluster assignment.

 

References

[1] Huang, L., Yan, D., Taft, N., & Jordan, M. I. (2008). Spectral Clustering with Perturbed Data. Advances in Neural Information Processing Systems, 21, 705–712.

[2] Andreotti, E., Edelmann, D., Guglielmi, N., & Lubich, C. (2021). Measuring the stability of spectral clustering. Linear Algebra and its Applications, 610, 673–697.

[3] Peng, P., & Yoshida, Y. (2020). Average Sensitivity of Spectral Clustering. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 1132–1140.

[4] Rohe, K., Chatterjee, S., & Yu, B. (2011). Spectral clustering and the high-dimensional stochastic blockmodel. The Annals of Statistics, 39(4), 1878–1915.

[5] Lei, J., & Rinaldo, A. (2015). Consistency of spectral clustering in stochastic block models. The Annals of Statistics, 43(1), 215–237.

[6] Su, L., Wang, W., & Zhang, Y. (2020). Strong Consistency of Spectral Clustering for Stochastic Block Models. IEEE Transactions on Information Theory, 66(1), 324–338.

[7] Deng, S., Ling, S., & Strohmer, T. (2021). Strong Consistency, Graph Laplacians, and the Stochastic Block Model. Journal of Machine Learning Research, 22(117), 1–44.

[8] Cron, A. J., & West, M. (2011). Efficient Classification-Based Relabeling in Mixture Models. The American Statistician, 65(1), 16–20.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.