acceptodds
Under review as a conference paper at ICLR 2027

Let’s make some noise: The Critical State of External Evaluation of Clusterings with Noise

Abstract

Detecting noise is an important and beneficial feature of frequently used clustering algorithms like DBSCAN or HDBSCAN. However, the external evaluation of clusterings containing noise labels is handled inconsistently in the literature: as common external cluster validity indices (CVIs) like NMI or ARI are not defined for noise labels, a variety of ways to handle noise has emerged, most without proper foundations or explicit description. In this survey, we examine i) how papers presenting noise-detecting clustering methods evaluate their methods, and ii) the datasets that have been used. We define four desirable properties for noise-aware external CVIs and perform experiments across a wide range of existing noise-handling strategies. By highlighting where these properties are violated, we show that evaluation in this field is currently neither uniform nor scientifically adequate. Based on these findings, we propose two new noise-aware CVIs, and (Noise-Aware ARI), combining ARI on cluster points with Cohen's and the Matthews–Pearson coefficient on the binary noise classification, respectively. We show that both satisfy all four properties and confirm on real data, with held-out minority classes and foundation-model-annotated images as noise, that flawed strategies certify degenerate clusterings with perfect scores while the proposed measures do not.

Primary area:
datasets and benchmarks
Keywords:
clustering evaluation, noise labels, cluster validity indices, noise handling, external evaluation, density-based clustering

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_R1uJOpenReview ↗
Rating
3(+1)
Confidence
4
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The paper reviews how clustering solutions with noise labels are evaluated using supervised scores and shows that common noise handling conventions can produce misleading scores. It formalizes four desirable properties for noise-aware external evaluation and proposes two scores combining ARI on mutually non-noise points with a separate measure of noise-detection agreement. Through theoretical analysis and experiments, the paper compares these measures with existing alternatives and illustrates how the employed scores can affect clustering assessment and parameter selection.

Critical strengths

S1. The paper provides a valuable review of current evaluation practices for clustering with noise, highlighting inconsistencies and limitations of available benchmarks. It formalizes desirable properties for noise-aware evaluation and analyzes existing and proposed measures against them.

S2. The proposed scores explicitly distinguish clustering agreement from noise-detection quality. This discrimination seems sensible and helpful since clustering and noise detection are different tasks.

Critical weaknesses

W1. I do not consider that this problem is currently of particular importance, since several popular clustering algorithms do not provide noise labels. Moreover, it seems that real datasets of this type are not yet available.

W2. Since we are speaking of external measures, the practical usefulness is questionable, since clustering is unsupervised and does not assume the existence of cluster (and noise) labels.

W3. Although it is discussed in the paper, the superiority against singleton ARI and AMI is not clear in practice. Better scores do not imply better decisions based on those scores.

Questions for authors

Q1. I do not see any reason to present two scores differing only in the evaluation function (\kappa and \phi) for noise detection.

Q2. In which practically meaningful cases does NARI improve evaluation over singleton-based ARI/AMI?

Q3. Why not reporting two separate measures (cluster validity and noise detection) instead of combining them into one composite score? This would provide a clearer view on the quality of the clustering solution. The combination of the two as a weighted average is rather straightforward.

5 comments

Dear Reviewer R1uJ, thank you for your review and insightful questions. Before addressing your questions individually, we would first like to briefly clarify that we strongly disagree with both W1 and W2. The fact that some clustering algorithms do not produce noise labels does not diminish the relevance of evaluating methods that explicitly distinguish noise points from cluster members. Moreover, the unsupervised nature of clustering does not diminish the importance of external evaluation, which is essential for benchmarking algorithms and comparing methods with each other.

Q1

The two variants instantiate a common noise-aware evaluation framework using two established notions of binary agreement. Cohen’s κ measures agreement beyond the level expected from the observed marginal frequencies, whereas φ, equivalently the Matthews correlation coefficient, measures correlation between the binary noise indicators.

Their different normalizations matter when predicted and reference noise proportions differ. When these proportions coincide, the coefficients agree. Otherwise, they can respond differently to over- or under-detection of noise. Both variants retain the same theoretical guarantees of our construction.

Including both also demonstrates that the principal findings are reproduced with two established choices for the noise component. We will clarify the shared NARI construction and explain the distinct interpretations of its κ- and φ-based variants.

Q2

A concrete example is parameter selection in our existing DBSCAN sweep on CLUTO-t4.8k (Section 3.6). NARIκ and NARIφ both select the same DBSCAN configuration. The resulting selections compare as follows:

Selection criterionNoise-classification errorsClusters containing only ground-truth noiseCorrectly matched cluster objects
Singleton ARI261127,207
Singleton AMI13827,210
NARIκ13317,219
NARIφ13317,219

Noise-classification errors count both ground-truth noise assigned to clusters and genuine cluster objects rejected as noise. Correctly matched cluster objects are counted after optimal one-to-one cluster-label matching, out of 7,236 ground-truth cluster objects. Both NARI variants therefore select a configuration with fewer noise-classification errors, fewer spurious noise-only clusters, and more correctly recovered cluster objects than either singleton baseline.

We have additionally completed an astronomical case study using Gaia DR3 observations around NGC 869 and NGC 884. We construct the reference labeling from published catalogue memberships (Hunt and Reffert, 2024), assigning unmatched sources the reference noise label. The field contains 8,834 stars: 662 catalogue members and 8,172 background-labelled objects. In the DBSCAN/HDBSCAN parameter search on this field, singleton ARI selects a configuration that correctly matches 534 catalogue members and rejects 128 members as noise. Both NARI variants select a configuration that correctly matches 601 members and rejects only 60. This recovers 67 additional members, with total noise-classification errors of 259 versus 245. Singleton AMI selects the same configuration as both NARI variants. This example demonstrates a practically relevant difference in member recovery, complementing the improvement over both singleton baselines on CLUTO.

These comparisons assess the selected clusterings directly against reference labels. More generally, NARI explicitly evaluates noise rejection: singleton encoding makes a rejected noise point indistinguishable from a one-point cluster, whereas NARI preserves this distinction. We will incorporate these comparisons into the manuscript to make their practical implications for parameter selection explicit.

Q3

Reporting clustering agreement and noise-detection quality separately is useful for interpreting a result, and our implementation already returns both components, their associated sample counts, and the combined score. This decomposability is an explicit advantage of NARI.

Simply averaging scores does not resolve how noise labels enter the clustering component. Standard ARI and AMI compare partitions without assigning a special meaning to noise labels. Applying them to clusterings containing noise therefore requires an additional convention, such as treating noise as a cluster, encoding noise points as singletons, filtering them, or applying a filtering penalty. Our analysis demonstrates that these choices have substantive consequences for the resulting evaluation.

NARI explicitly defines the two evaluation tasks: ARI measures agreement on the objects that both labelings identify as cluster objects, while κ or φ evaluates the binary noise assignments over all observations. Every disagreement about whether an object is noise is therefore assessed explicitly. The combined score provides a reproducible criterion for benchmarking and parameter selection when the components favor different configurations, while retaining access to both components for interpretation. The weighting is also consequential. It depends on both labelings, assigning the clustering component the fraction of common cluster objects and the noise component the complementary fraction. Appendix C demonstrates that using ground-truth-only or prediction-only weights can produce perfect scores despite severe noise-detection errors. Our contribution therefore includes the precise definition and theoretical analysis of a noise-aware evaluation criterion, together with evidence of its consequences for practical selection decisions. We will make these complementary roles of the component scores and the aggregate more explicit in the manuscript.

W1

Noise rejection is a central capability of DBSCAN, HDBSCAN, and OPTICS, and our survey documents its use in newer methods (see Table 2). Reliable evaluation matters both when comparing noise-detecting methods and when comparing them with methods that assign every observation to a cluster. The availability of algorithms without noise rejection therefore makes consistent evaluation across these outputs particularly relevant.

The evaluation problem also arises on standard benchmarks whose reference labels contain no noise: predicted noise labels still require an explicit evaluation rule. Filtering these observations can hide the rejection of substantial parts of the reference clustering and yield a perfect score on the retained subset. Thus, the relevance of noise-aware evaluation extends beyond benchmarks with ground-truth noise.

We have further strengthened the empirical evidence with an astronomical case study using Gaia DR3 observations around NGC 869 and NGC 884. Identifying stellar clusters within a field-star background is an established scientific application of clustering with noise. We use published memberships from Hunt and Reffert (2023, updated 2024), whose catalogue was constructed using HDBSCAN with additional statistical and photometric validation. Our dataset consists of 8,834 stars: 662 catalogue members and 8,172 background-labelled stars treated as noise.

On the same five scaled astrometric features, standard K-Means with k=2 assigns all 8,172 background stars to clusters and merges the members of both dominant stellar clusters into one predicted cluster. This result is identical across ten seeds with 20 initializations each. Nevertheless, NMI-LNP-I assigns it a near-perfect score of 0.9964. Both NARI variants score this solution at 0.00125, compared with 0.8198 and 0.8239 for their selected HDBSCAN solution, which makes 259 noise-classification errors and correctly matches 601 catalogue members. Furthermore, Purity-LNP-I assigns its maximum score of 1 to an HDBSCAN partition containing 2,194 clusters and 5,752 noise-classification errors.

These findings demonstrate both the relevance of noise rejection in a real scientific application and the practical consequences of how it is evaluated. As reviewer njDT also highlights, these evaluation choices affect parameter selection and method comparisons.

W2

Clustering can be unsupervised while its output is evaluated against reference labels in a benchmark. External evaluation is standard practice for assessing whether a method recovers known structures and for comparing competing algorithms. Our contribution addresses the reliability of this established practice when clustering outputs contain noise labels.

Table 2 already surveys 21 publications, 20 of which report external evaluation measures. Beyond this focused survey of noise-handling practices, the following 16 examples from KDD, ICLR, ICML, and NeurIPS illustrate the widespread use of reference-based evaluation in recent research. They cover deep, graph, multi-view, ensemble, and combinatorial clustering, as well as cell-clustering applications.

AuthorsPaperVenueExternal measures
Leiber et al.The DipEncoder: Enforcing Multimodality in AutoencodersKDD 2022NMI, ARI
Yang et al.Effective Clustering on Large Attributed Bipartite GraphsKDD 2024ACC, NMI, ARI
Liu et al.Revisiting Modularity Maximization for Graph Clustering: A Contrastive Learning PerspectiveKDD 2024ACC, NMI, ARI, F1
Lin et al.Spectral Subspace Clustering for Attributed GraphsKDD 2025ACC, NMI, ARI
Liu et al.Deep Temporal Graph ClusteringICLR 2024ACC, NMI, ARI, F1
Jia et al.Towards Calibrated Deep Clustering NetworkICLR 2025ACC, NMI, ARI
Miklautz et al.Breaking the Reclustering Barrier in Centroid-based Deep ClusteringICLR 2025ACC, NMI, ARI
Li & JiaConMix: Contrastive Mixup at Representation Level for Long-tailed Deep ClusteringICLR 2025ACC, NMI, ARI
Svirsky & LindenbaumInterpretable Deep Clustering for Tabular DataICML 2024ACC, NMI, ARI
Dai et al.Multi-View Clustering by Inter-cluster Connectivity Guided RewardICML 2024NMI, Purity, ARI
Wang et al.MC-GTA: Metric-Constrained Model-Based Clustering using Goodness-of-fit Tests with AutocorrelationsICML 2024ARI, NMI
Zhang et al.Generalization Performance of Ensemble Clustering: From Theory to AlgorithmICML 2025NMI, ARI, Purity
Arutyunova et al.Approximately Pareto-optimal Solutions for Bi-Objective k-ClusteringNeurIPS 2024NMI, RI, Fβ
Chen et al.Bridging Gaps: Federated Multi-View Clustering in Heterogeneous Hybrid ViewsNeurIPS 2024ACC, NMI, ARI
Guo et al.Robust Contrastive Multi-view Clustering against Dual Noisy CorrespondenceNeurIPS 2024ACC, NMI, ARI
Um et al.Gene-Gene Relationship Modeling Based on Genetic Evidence for Single-Cell RNA-Seq Data ImputationNeurIPS 2024ARI, NMI, CA

ACC and CA denote clustering accuracy. ACC and CA denote clustering accuracy.

Our work strengthens the methodological foundation of these comparisons. When an algorithm rejects observations as noise, its evaluation requires an explicit treatment of those labels. Our theoretical analysis and experiments demonstrate that this choice can change parameter selection and method rankings, and can even assign perfect scores to degenerate solutions. Ensuring that external evaluation reflects both clustering agreement and noise-detection quality therefore has direct practical value.

W3

The practical evidence concerns the clustering configurations selected by each evaluation criterion. As detailed in our response to Q2, both NARI variants select the same CLUTO-t4.8k configuration with 133 noise-classification errors, compared with 261 for singleton ARI and 138 for singleton AMI. This configuration also recovers more genuine cluster objects and contains fewer spurious noise-only clusters. These improvements are assessed directly against the reference labels and demonstrate better parameter-selection decisions. The additional Gaia case study in Q2 illustrates how the choice of evaluation criterion affects the recovery of stellar cluster members in a real scientific application.

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

This paper investigates the external validation problem of clustering with noisy labels. The author points out that existing literature has highly inconsistent treatment of noise labels when calculating external CVI. Common strategies systematically reward degraded clustering, ignore noise detection, or make comparative conclusions dependent on undeclared implementation choices. The author proposes four properties: unbiasedness, supremely reachable, no false optima, monotonicity, and systematically evaluates the combination of eight basic CVIs and multiple noise processing strategies. Subsequently, two noise perception metrics were proposed: a weighted combination of clustering quality (ARI on a common cluster object subset) and noise recognition quality (Cohen's or Matthews'). The author provides theoretical proof, synthetic degradation experiments, real data parameter search, CIFAR-10/CLIP labeled noise experiments, and SHADE/DBSCAN case studies.

Critical strengths
  1. The issue is important and has been overlooked for a long time. Noise labels are common in density clustering, deep clustering, and anomaly/noise detection, but there is indeed a lack of unified standards for how to handle noise in external evaluations. The paper provides ample evidence that this is not about implementation details, but rather about changing parameter selection and cross method ranking. Very systematic.

  2. The paper does not only propose a new indicator, but first establishes a property framework, investigates existing strategies, proposes new indicators, and verifies them through synthetic, real, and parameter search experiments.

  3. The theoretical part is clear. Propositions 1-4 deal with unbiasedness, supremely reachable, non false optima, and component monotonicity, respectively. Although P4 has limitations, the proof is straightforward and has practical guidance for characterizing the properties of two NARIs.

Figure 3 shows the failure modes of Mf Mp Ms and Mc, while Sections 3.6-3.7 and Section L demonstrate how these failures actually alter the ranking of DBSCAN/HDBSCAN/SHADE. These all have good experimental persuasiveness.

  1. The author promises to release a benchmark suite for pip installation and provide anonymous repositories, experimental scripts, and proof of properties. This has practical value in the field.
Critical weaknesses
  1. The claimed monotonicity of P4 is stronger than the actual results. Proposition 4 only proves the monotonicity of components under the fixed common cluster object subset, while the author explicitly acknowledges in Section B.1 that two NARI indicators may also be monotonic under any single point re labeling. Marking P4 as ✓ in Table 1 may lead readers to mistakenly believe that it is globally monotonic.

  2. The real GT noise protocol is still a proxy. Held out minor classes form compact micro-clusters, not diffuse background noise; CLIP labels semantic blurred images, not noise in the sense of density. The author acknowledges this in the Limitations section, but the wording of "real-world impact" in Section 3.7 and the Abstract still tends to be strong. To support real-world conclusions, it is best to include a real noise benchmark that is truly diffuse, or to explicitly limit the scope of the conclusions.

  3. NARI cannot distinguish between "noise point pollution existing clusters" and "noise point formation false clusters". Both of them enter the noise component, so NARI only punishes inconsistent noise flags and does not penalize false cluster structures. The author acknowledges in Limitations, but this is an important dimension for external clustering evaluation, especially when the false clusters themselves have structure.

  4. Insufficient experimental stability report. Most degradation experiments are single deterministic runs, and real data parameter searches mainly report arg-max configurations, lacking multiple random seeds or bootstrap confidence intervals. SHADE used three seeds, but other methods did not. For the strong conclusion of 'changing method ranking', it is recommended to supplement stability analysis.

  5. There are minor issues with writing and symbols. For example, appearing near Proposition 2; Some tables are formatted incorrectly in the PDF. Symbols and table formats should be standardized.

Questions for authors
  1. Proposition 4 appears to prove monotonicity only for the components under a fixed common cluster-object subset, while Section B.1 acknowledges that the two NARI indicators may also be monotonic under any single-point relabeling. Please clarify exactly which conditions the monotonicity in Proposition 4 covers and whether it is only local/conditional monotonicity. Please also explain why P4 is marked as ✓ in Table 1, and revise the relevant statements or table marking so that readers are not led to believe that P4 is globally monotonic.

  2. The proposed real GT-noise protocol may still be a proxy setting: the held-out minor classes form compact micro-clusters rather than diffuse background noise, and CLIP labels semantic blurred images rather than noise in the density sense. Although this is acknowledged in the Limitations section, the wording of “real-world impact” in Section 3.7 and the Abstract still seems too strong. Please explain to what extent this protocol can represent real noise scenarios. Can the authors include a real noise benchmark with genuinely diffuse noise? If not, please explicitly limit the scope of the conclusions and revise the overly strong statements in the Abstract and Section 3.7.

  3. NARI assigns both cases to the noise component, and therefore only penalizes inconsistent noise flags rather than false cluster structures; this is particularly important for external clustering evaluation when the false clusters themselves have structure. Please explain more directly how NARI behaves in these two cases and what its specific limitations are, and discuss whether additional analysis or metrics capable of penalizing false cluster structures are needed. Please also clarify how this limitation affects the interpretation of the experimental results.

  4. Most degradation experiments appear to be single deterministic runs, and the real-data parameter searches mainly report arg-max configurations, lacking multiple random seeds or bootstrap confidence intervals; SHADE uses three seeds, but other methods do not. Given the strong conclusion of “changing method ranking,” please supplement stability analyses such as multiple seeds, repeated runs, or bootstrap confidence intervals, and explain why only SHADE uses three seeds and whether this affects the fairness of the comparison, so as to more strongly support the ranking-change conclusion.

  5. There are several writing and symbol issues, for example, an anomalous symbol appears near Proposition 2, and some tables are formatted incorrectly in the PDF. Please fix the symbol/statement issue near Proposition 2, check and re-typeset the relevant tables, unify the symbols and table formats throughout the paper, and carefully proofread the manuscript to improve readability and presentation quality.

8 comments

Thank you for your detailed and thoughtful review, and for recognizing the importance of the problem and the systematic nature of our study. Your suggestions have helped us strengthen the empirical evidence and clarify the scope of the theoretical guarantees. We address your questions below, including the results of the additional experiments.

Q1

Proposition 4 establishes conditional, componentwise monotonicity. For a fixed reference labeling, the two predictions must share the same common cluster-object subset S. If neither the restricted ARI on S nor the binary noise-agreement coefficient decreases, NARI cannot decrease. It increases strictly when a component with positive weight improves. These conditions keep the aggregation weights fixed. Noise assignments of ground-truth noise objects may still differ between the predictions.

This guarantee applies to any pair of predictions satisfying these conditions, rather than only to local changes. It ensures that improvements in the evaluated components cannot produce a worse aggregate score. Appendix B.1 demonstrates that singleton ARI and AMI can violate this property under the same conditions, highlighting a concrete advantage of the proposed construction. The checkmark in Table 1 denotes this precise guarantee. We will explicitly label P4 and the corresponding table column as componentwise monotonicity under a fixed common subset, and distinguish this guarantee from the empirical degradation results. We will also make explicit that Proposition 4 does not assert monotonicity under arbitrary single-point relabelings.

Q2

Our real-data experiments establish a concrete practical finding: under both annotation protocols, filtering-based evaluation can assign perfect scores to DBSCAN/HDBSCAN configurations that label almost all observations as noise, while the proposed measures penalize these solutions. These experiments complement the controlled analysis by demonstrating consequences for parameter selection on real feature distributions.

We have now complemented our existing real-data experiments with an astronomical case study using Gaia DR3 observations around NGC 869 and NGC 884. In this application, star clusters appear as overdensities in astrometric space, embedded in a naturally occurring field-star background that constitutes noise for cluster identification. We use the published memberships from the catalogue of Hunt and Reffert (2023, updated 2024), constructed using HDBSCAN with additional statistical and photometric cluster validation. The distinction between cluster members and field stars is also established in astronomical membership methods that represent these populations using Gaussian mixtures in proper-motion and parallax space (Agarwal et al., 2021). We retain all catalogue groups represented in the observed field and assign unmatched sources the reference noise label. The resulting dataset contains 8,834 stars: 662 catalogue members and 8,172 background-labelled objects.

Using five scaled astrometric features, we evaluated 7,500 DBSCAN and 249,500 HDBSCAN configurations. The experiment demonstrates the practical consequences of noise handling: filtered ARI assigns its maximum score of 1 to 391 distinct partitions with 245–683 noise classification errors. Both NARI variants select the same two-cluster solution, with 601 correctly matched catalogue members and 259 noise classification errors. Omitting the five catalogue members with membership scores below 0.5 from evaluation leaves the selections of all ten evaluated criteria unchanged.

This additional experiment provides evidence from observed star clusters and their surrounding stellar background, complementing the class-exclusion and CLIP annotation protocols. We will incorporate the results into Section 3.7 and explicitly describe the reference-label construction for each experimental setting.

Q3

NARIκ and NARIφ penalize both contamination of existing clusters and the formation of spurious clusters through their explicit noise-detection component. If two predictions have identical noise flags and induce the same partition on the common cluster objects, they receive the same score, regardless of how the missed noise objects are allocated. Spurious clusters are therefore penalized for containing misclassified noise, without an additional penalty for their number or arrangement.

This invariance has a practical benefit: splitting missed noise into increasingly small clusters cannot improve the score while leaving the noise-detection errors unchanged. Our existing noisyGaussian example illustrates its relevance. Assigning 30% of the ground-truth noise points to five-point microclusters while preserving the genuine clusters yields singleton ARI of 0.98 and singleton AMI of 0.72, whereas NARIκ and NARIφ yield 0.39 and 0.49. The explicit noise component makes this substantial noise-detection failure visible.

Accordingly, our experimental NARI rankings assess agreement with the reference cluster partition and noise assignments. They do not additionally distinguish the consequences of allocating the same missed noise objects to existing clusters versus separate spurious clusters. Where this distinction matters, complementary diagnostics can report the ground-truth noise fraction within each predicted cluster and the number and sizes of clusters containing only ground-truth noise.

Developing measures that additionally distinguish these arrangements is an interesting direction for future work, particularly for applications that assign different costs to contamination and spurious cluster formation. Such an extension would require specifying the desired sensitivity to false cluster structure and examining its relationship with the four properties studied here. We will expand the discussion to clarify this distinction, its implications for interpreting the experimental rankings, and the role of complementary diagnostics.

Q4

Thank you for this suggestion. We have completed additional stability analyses covering training randomness, data sampling and ordering, and evaluation uncertainty.

  1. Real-data parameter searches: ten sampling/order seeds. We repeated the full 241-configuration search on each of the four minority-class datasets, varying the sampled noise objects and input ordering. Across all 40 dataset–seed combinations, ARI_f and Purity-LNP-I select degenerate solutions with at least 98% predicted noise and a perfect score of 1. Both NARI variants, as well as ARI_s and AMI_s, avoid these solutions in all 40 cases.
  2. CIFAR/CLIP: 500 paired bootstrap replicates. We resampled objects jointly across the fixed candidate pool, recomputed all scores, and reselected each metric’s argmax in every replicate. At both annotation thresholds, ARI_f and Purity-LNP-I select degenerate solutions in 500/500 replicates, while both NARI variants consistently select the same nine-cluster configuration. The conditional 95% bootstrap percentile intervals for NARIκ are [0.354, 0.376] at 5% annotated noise and [0.365, 0.390] at 10%.
  3. Degradation experiments: 560 trajectories. We repeated all 56 dataset–scheme settings across ten point-order seeds, also varying cluster order. The principal failure modes recur across repetitions. Both NARI variants decrease at every evaluated checkpoint in all 320 trajectories of the four targeted noise-corruption schemes. Pointwise merging and shuffling can exhibit local rebounds; these are distinguished from the componentwise monotonicity guarantee discussed in our response to Q1.
  4. SHADE: ten training seeds. SHADE was originally repeated across three seeds because its training is stochastic; DBSCAN and HDBSCAN are deterministic for fixed data, input ordering, and parameters. We have now extended SHADE to ten training seeds, with parameter selection performed separately within each seed. Seeds are not optimized over. Comparing the same selected configurations under ARI_c and NARIκ, the ranking reversal between SHADE and DBSCAN occurs in 10/10 seeds on both Synth_low and Synth_high. On HTRU2, the reversal occurs in 7/10 seeds for each comparison of SHADE with DBSCAN or HDBSCAN. We will report these frequencies alongside the per-seed results to make the stability of the method-ranking conclusions explicit.

We will incorporate the per-seed summaries, bootstrap intervals, and mean ± SD degradation curves into the revised manuscript.

Q5

Thank you for pointing out these presentation issues. We will standardize the metric notation and property names throughout the manuscript and harmonize the table formatting. We will also proofread the compiled PDF to check mathematical symbols, cross-references, table alignment, and readability throughout the main text and appendix. As we do not find the described issue near Proposition 2, we want to politely ask whether you mean the “end of proof”- symbol at the end of the proof for Proposition 2 that presents (as intended) as a simple square?

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

The paper tackles a problem in clustering evaluation and proposes two noise-aware measures, NARIκ and NARIφ.

Critical strengths

It tackles a problem in clustering evaluation and proposes two noise-aware measures, NARIκ and NARIφ. The theoretical analysis is interesting.

Critical weaknesses
  1. The survey part does not have full coverage. It’s better if a classification tree or table can be provided which help the readers
  2. Mathematical justification of the proposed new index will improve the quality of the paper.
  3. The evaluation on real-world samples is performed, but the tests on the held-out minority classes and samples annotated by the foundation model are somewhat limited as not all the types of natural noise can be considered.
  4. It would be beneficial to test the proposed measures on a range of high-dimensional datasets from real-world scenarios.
  5. Further studies on the effect of varying noise ratios and cluster-size distributions on NARIκ and NARIφ could be performed.
  6. The measures considered in the paper cannot differentiate between noise points that corrupt existing clusters and noise points that form spurious separate clusters. This limitation deserves more discussion.
  7. It would be interesting to compare the proposed measures with some other recently proposed clustering evaluation measures that can handle the noisy criteria/attributes and possibly further highlight practical advantages of the proposed approach.
  8. The authors should consider discussing the computational scalability of the proposed measures for very large data sets.
Questions for authors
  1. The survey part does not have full coverage. It’s better if a classification tree or table can be provided which help the readers
  2. Mathematical justification of the proposed new index will improve the quality of the paper.
  3. The evaluation on real-world samples is performed, but the tests on the held-out minority classes and samples annotated by the foundation model are somewhat limited as not all the types of natural noise can be considered.
  4. It would be beneficial to test the proposed measures on a range of high-dimensional datasets from real-world scenarios.
  5. Further studies on the effect of varying noise ratios and cluster-size distributions on NARIκ and NARIφ could be performed.
  6. The measures considered in the paper cannot differentiate between noise points that corrupt existing clusters and noise points that form spurious separate clusters. This limitation deserves more discussion.
  7. It would be interesting to compare the proposed measures with some other recently proposed clustering evaluation measures that can handle the noisy criteria/attributes and possibly further highlight practical advantages of the proposed approach.
  8. The authors should consider discussing the computational scalability of the proposed measures for very large data sets.
3 comments

Thank you for your careful review and constructive suggestions. We appreciate your positive assessment of the theoretical analysis and your recommendations for making the survey, empirical coverage, and practical implications clearer. We address each point below.

W1/Q1

Our survey organizes the literature on external evaluation of clusterings with explicit noise labels. Table 2 already maps the surveyed publications to their evaluation measures and noise-handling strategies. To make this contribution more accessible, we will add a compact classification table organized by the main strategies: noise-as-a-cluster, singleton encoding, filtering, and filtering with a penalty. The table will also show how LNP-I and our proposed measures relate to these approaches, providing the requested conceptual overview.

We would also welcome pointers to specific approaches or references that the reviewer considers missing, so that we can address them directly.

W2/Q2

The proposed measures are supported by both a principled construction and formal analysis. They combine clustering agreement on common cluster objects with chance-corrected agreement on noise assignments. Appendix B establishes asymptotic chance correction under the stated null model, attainment of the maximum at perfect agreement, absence of spurious perfect scores, and componentwise monotonicity for a fixed common cluster-object subset.

Appendix C further demonstrates the benefit of determining the weights from both labelings: one-sided alternatives can assign perfect scores to substantially incorrect predictions. We will make the connection between these design choices, theoretical guarantees, and empirical results more prominent in Section 3.5.

Could the reviewer clarify which aspect of the construction or theoretical analysis they would like to see justified further? A specific pointer would help us address the concern directly.

W3/Q3

NARIκ and NARIφ operate solely on the reference and predicted labelings. For a fixed pair of labelings, their scores are invariant to the feature-space distribution of the noise objects. They therefore require no assumption that noise follows a particular distribution, such as uniform or Gaussian noise. Different noise distributions can affect the outputs of clustering algorithms, which motivates testing the evaluation criteria on diverse real-data settings.

Our existing real-data experiments investigate two complementary annotation protocols: held-out minority classes and CLIP-based uncertainty annotations. Under both protocols, filtering-based parameter selection can assign perfect scores to clusterings that discard almost all observations as noise. These experiments demonstrate practical consequences of the evaluation problem across different reference-labeling scenarios.

We have also completed an astronomical case study using Gaia DR3 observations around NGC 869 and NGC 884, where stellar clusters are embedded in a naturally occurring field-star background. We construct the reference labeling from published catalogue memberships (Hunt and Reffert, 2024), assigning unmatched sources the reference noise label. The dataset contains 8,834 stars: 662 catalogue members and 8,172 background-labelled objects.

In this additional parameter search, filtered ARI assigns its maximum score of 1 to 391 distinct partitions with 245–683 noise-classification errors. Both NARI variants select the same solution, with 601 correctly matched catalogue members and 259 noise-classification errors. This case study complements the existing annotation protocols with evidence from an established scientific application of clustering with noise. We will incorporate it into Section 3.7 and make the reference-label construction and interpretation of each protocol explicit.

W4/Q4

Note that the dimensionality of the data does not influence external evaluation measures, which operate solely on the two labelings, independently of any data coordinates.

Furthermore, our experiments already include high-dimensional real datasets: HAR with 561 features in the minority-class noise experiment and TCGA with 20,531 input features in the SHADE/DBSCAN/HDBSCAN case study. DBSCAN and HDBSCAN operate on the standardized features without dimensionality reduction.

These experiments demonstrate the applicability of the evaluation framework to real datasets with hundreds to tens of thousands of features. We will consolidate the dataset dimensions, preprocessing, annotation protocols, and results into a concise overview to make this existing evidence more visible.

W5/Q5

Our controlled experiments already investigate both factors. The eight configurations include ground-truth noise proportions of 1%, 10%, 15%, and 85%. For cluster-size imbalance, we compare equal, linearly increasing (1:…:7), and exponentially increasing (e¹:…:e⁷) cluster sizes while keeping the number of clusters at seven and the noise proportion at 15%.

Appendix E evaluates both proposed measures alongside singleton ARI and AMI under seven degradation schemes for each configuration, yielding 56 dataset–degradation combinations. The results show the expected overall decrease in scores as degradation progresses across settings with rare or dominant noise and markedly different cluster-size distributions. We will highlight this coverage and the corresponding results more prominently in the main text.

W6/Q6

This behavior follows from the explicit separation of clustering agreement and noise-detection agreement in NARIκ and NARIφ. If two predictions have identical noise flags and induce the same partition on the common cluster objects, they receive the same score, regardless of how the missed noise objects are allocated. This ensures that missed noise remains penalized independently of its grouping: splitting it into smaller spurious clusters cannot improve the score.

Our controlled experiments explicitly cover both scenarios through the “noise to data” and “noise to one cluster” degradation schemes. These illustrate how both measures respond to increasing noise-detection errors.

For applications where contamination of existing clusters and spurious cluster formation have different consequences, developing measures that additionally distinguish these arrangements is an interesting direction for future work. Such an extension would require specifying the desired sensitivity to false cluster structure and examining its relationship with the four properties studied here.

Complementary diagnostics can already distinguish these outcomes: we recommend reporting the ground-truth noise fraction within each predicted cluster, together with the number and sizes of clusters containing only ground-truth noise. These provide additional information alongside the aggregate score. We will expand the discussion to explain this design choice, its practical implications, and this direction for future work.

W7/Q7

We will expand the related-work discussion to include evaluation under noisy or irrelevant attributes. For example, Feature Importance Rescaling improves internal clustering evaluation by adjusting feature contributions and attenuating noisy features (de Amorim and Makarenkov, 2026). Noise-aware internal evaluation, including DISCO (Beer et al., ICLR 2026), is already discussed in our survey. These approaches assess clustering quality from the feature geometry. Our work addresses the complementary task of evaluating agreement with a reference labeling that explicitly distinguishes cluster objects and noise. We will make this distinction clearer in the related-work discussion.

We would welcome pointers to specific recent external measures with explicit noise-label support that the reviewer would like to see included in the comparison.

W8/Q8

The proposed measures are computationally lightweight. Each requires one ARI computation on the points that both labelings identify as cluster objects, together with a binary noise-agreement calculation. The noise indicators, component weights, and binary contingency counts can be obtained in linear time; κ and φ are then computed directly from these counts. ARI likewise uses contingency counts without explicitly enumerating point pairs. The evaluation operates entirely on label vectors and requires neither feature-space distances nor a pairwise distance matrix.

Appendix K already benchmarks the constituent measures from 103 to 106 observations. At one million observations, the measured median runtimes are approximately 0.17 seconds for ARI, 0.03 seconds for κ, and 0.14 seconds for φ, compared with 1.44 seconds for AMI on the reported hardware. Each measurement uses seven timed runs after a warm-up call. These results support the computational practicality of the proposed construction for large datasets and repeated evaluation during parameter selection.

We will make this computational decomposition and the existing runtime evidence more prominent in the main text.

Area_Chair_WanMOpenReview ↗

Please leave some comments for the authors!

Thank you for your thoughtful reviews. When you have a chance, please read the authors’ responses to your comments and update the discussion with your assessment. Please note whether your concerns have been addressed and briefly mention any remaining questions.

Comments on the paper

1 comment

We thank all reviewers and the area chair for their valuable time and especially thank Reviewers njDT and R1uJ for following up on our responses and allowing us to further improve our paper.

We are glad that the reviewers share our view of the problem, that "the issue is important and has been overlooked for a long time" (Reviewer njDT). Our work is "a valuable review of current evaluation practices for clustering with noise" (Reviewer R1uJ) and our analysis is "very systematic" (Reviewer njDT).

We introduced external CVIs that can evaluate noise labels by separating clustering agreement and noise detection, which was found to be "sensible and helpful" (Reviewer R1uJ).

We have uploaded a revised version of the paper that incorporates the feedback and the additions promised in our responses: The new material includes:

  • A case study on astronomic data describing stars' locations and velocities (the Gaia case study, Sec. 3.7, App. M.3).
  • Overview tables of strategies and datasets (App. O)
  • A selection comparison against the singleton baselines (App. P)
  • Stability analyses (App. Q).

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.