acceptodds
Withdrawn from ICLR 2027

Spectral Density Peaks Clustering

Withdrawn from ICLR 2027, so left out of the paper lists and the map.

Abstract

Cluster analysis is still an open problem despite the wide range of techniques available in the literature. Each family of clustering algorithms has distinct strengths and limitations: graph-theoretical approaches benefit from a solid linear algebra foundation, but struggle with structures of varying size and density; density-based methods can detect arbitrarily-shaped clusters, yet they often rely on sensitive and method-dependent heuristics. We introduce a spectral formulation of Density Peaks clustering, based on a transition matrix that encodes the probability of a point being the nearest higher-density neighbor of another. This matrix naturally integrates with Perron Cluster Analysis to coarse-grain Markov chains with complex spectra, addressing the limitations of both the aforementioned paradigms. The proposed method, Spectral Density Peaks, is evaluated on synthetic and real-world datasets against state-of-the-art competitors.

Primary area:
unsupervised, self-supervised, semi-supervised, and supervised representation learning
Keywords:
Density-Based Clustering, Density Peaks Clustering, Perron Cluster Cluster Analysis, Transition Matrices

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_wEdTOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper introduces Spectral Density Peaks (SDP), a clustering method that aims to combine the strengths of density-based and spectral clustering. To do so, the method constructs a transition matrix that encodes the probability that one point is the nearest "higher-density neighbor" of another, based on pairwise "density-dominance" probabilities. Clusters are then identified as metastable sets of the resulting non-reversible Markov chain using complex-valued PCCA+ (cPCCA+). The authors propose a new criterion for selecting the number of clusters, the Timescale Separation Threshold (TST). The method is evaluated on five 2-D synthetic benchmarks, on MNIST, and on a molecular dynamics trajectory of the peptide CLN025.

Critical strengths

Clustering is a central problem in machine learning, and bridging density-based and spectral clustering is a worthwhile and non-trivial goal. Turning the hard "nearest higher-density neighbor" relation of DP and Quick Shift into a probabilistic one, using the uncertainty of the density estimates, is natural and elegant. Analyzing the resulting chain with tools for non-reversible Markov chains (cPCCA+) is a sensible combination of mature literatures. The authors discuss their independence assumptions and provide an empirical check of assumption (ii) in Appendix G.

Critical weaknesses
  1. While reading the paper, I found the theoretical results rather weak.
  • Theorem A.1 seems close to a tautology, definition A.4 ("well-sampled cluster") assumes essencially the goal of the theorem, which then follows by a one-line bound of Si\mathcal{S}^i. As a side note, the limit →∞\to \infty has no stated asymptotic parameter (I assume NN). As a last remark on this, the definitions and theorems are stated in terms of the estimates ρ^\hat \rho, so that these are property of the estimator's ouput, and not of the underlying true distribution.
  • Property A.1 gives a bound on the Leakage probability, but this bound does not seem informative on points where the screening-set is small, such as density saddles, which are typically where one could expect the leakage. A clarification or example in those context would greatly help making sense of this bound.
  • Lastly, while Section 3 defines the ground-truth clusters as "bassins of attraction of the gradient flow", this definition is not used again, and the appendices work with the given sample label.
  1. The experimental claims seems overstated in some extent.
  • The paper states that "SDP attains the highest NMI on all five datasets", but on every dataset, the difference with the second-best method is within one standard deviation. In my opinion, not outperforming the baselines is not a problem in itself, but the claims made should match the evidence.
  • All quantitative benchmarks are 2-D, so that it isn't clear how the proposed approach works quantitatively in high dimensions. MNIST has known labels, yet no quantitative metric and no baseline is reported.
  • The halo and entropy in Section 3.3 is not used in the experiments.
  1. The selection of the numnber of clusters via the TST criterion is central to the paper's claims, but I found several aspect of it that bothered me.
  • As written, this formulation lacks a proper justification. The empirical results are not convincing enough, they are limit to 22-D datasets, and TST fails on the only high-dimensional dataset presented (MNIST), where the TST criterion is manually overridden.
  • The TST score is only named in Section 3.2, and is deferred to Appendix C. Their description is ambiguous, as the main text refers to "TST score maximization", while in the appendix it selects the largest mm such that S(m)>θS(m) > \theta. These results seems to differ.
  • Table 3 reports that TST recovers the correct number of clusters on HORSE in 00 out of 1010 runs are 25%25\%, 50%50\% and 75%75\% subsampling, but Table 6 report 100% recovery on HORSE at N=15000N= 15000.

Minor weaknesses and notational issues:

  • Notations are inconsistent between the main text and the appendices: si,js_{i,j} vs s^(i,l)\hat{s}^{(i,l)} or ρi^\hat{\rho_i} vs ρ^(i)\hat{\rho}^{(i)}. The quantity zi,jz_{i,j} is introduced in Eq. 1 but its expression is rewritten in Defintiion A.3 and A.4.
  • Boldface is used inconsistently, please check throughout
  • Highlighting the best results in the tables would improve readability.
  • The phrasing is often hard to follow. For example, the sentence introducing assumption (iii) ("conditional independence of pairwise density-dominance events for a reference point i, the joint probabilities can be factorized into products of the corresponding marginals") is not clear.
Questions for authors
  1. How does SDP perform when kk is given ? This would separate the quality of transition matrix from that of the selection criterion. How does it compare to other methods when everyone is using the same number of clusters?
  2. In the context of MNIST, the selection rule returns k=4k=4. How should a user proceed in a truly unsupervised setting? What are the NMI/ARI against the digit labels for k=4k = 4, 1010 and 1818, and how do the baselines compare?
  3. How does the halo mechanism work in practice? Could you provide experiments for this?
  4. How does SDP and the TST criterion evolves in high-dimensional settings?

Suggestions I would suggest the following edits to the paper.

  • Rewrite appendix A using ρ\rho instead of ρ^\hat \rho.
  • Move the definition of the TST criterion in the main text, as it is part of the contributions of the paper
  • Use a paired test (e.g. Wilcoxon signed-rank) to make explicit the differences or not in the experimental results.
  • Fix the notations issues.
Reviewer_z3mKOpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper introduces SDP, a method that constructs a "density-dominance probability" based on adaptive kk-NN density estimation and its associated uncertainty. This probability is used to derive a row-stochastic, non-invertible Markov chain transition matrix. Subsequently, cPCCA+ is applied to perform coarse-graining, yielding a soft clustering, with the number of clusters determined by the TST spectral gap criterion. The contributions include a formulation of density-peak clustering through the lens of graph theory and Markov chains, an uncertainty-aware transition matrix, an efficient sparse implementation, and the provision of soft membership assignments alongside "halo" (outlier) identification. The method is validated on five 2D synthetic datasets, the MNIST dataset, and molecular dynamics trajectories (CLN025); it achieves the highest NMI scores on the synthetic data, reveals an over-segmented structure for MNIST, and identifies interpretable conformational states for the CLN025 system.

Critical strengths
  1. Density-peak clustering is formalized as an irreversible Markov chain and coarse-grained using cPCCA+; this provides a clear perspective and establishes actionable distinctions from methods such as DPA, SC, and MS.

  2. Transition probabilities are constructed by explicitly leveraging uncertainty in density estimation, with a defined path toward sparsification, offering practical engineering feasibility.

  3. The method achieves the highest average NMI across five synthetic benchmarks and demonstrates a runtime advantage over SC and MS.

Critical weaknesses
  1. The core statistical assumptions are overly strong. Equations (2)–(3) rely on approximations such as the Gaussian nature of density errors and conditional independence; however, the correlation correction is only validated on small-scale synthetic data in the appendix. There is no proof that these assumptions hold for datasets like MNIST, CLN025, or high-dimensional real-world data, a point that directly impacts the reliability of the derived transition matrices and clustering results.

  2. The selection of the number of clusters is not truly parameter-free. TST relies on default values ​​(θ=1,λ=0.01\theta=1, \lambda=0.01), and for the MNIST dataset, the authors manually selected a second peak (k=18) rather than the primary peak (k=4). This undermines the paper’s central claims of "minimal user intervention" and unsupervised automation.

  3. The experimental evidence is insufficient to support broad applicability. The performance gains over DPA on synthetic data are limited, and the real-world experiments are restricted to MNIST and a single CLN025 trajectory, the latter of which lacks ground truth. The absence of systematic evaluation, such as testing against noise/outliers, high-dimensional large-scale datasets, or varying density scales, makes it difficult to demonstrate that this method offers a substantial advantage over existing density-based or spectral clustering approaches.

Questions for authors
  1. When assumptions (ii)(iii) are clearly violated, are there still stateable guarantees for the leakage bound of the transition matrix P\mathbf{P} and the cluster recovery of cPCCA+? Can you provide quantitative verification on non-synthetic data?

  2. How to select$\theta=1$ and λ=0.01\lambda=0.01 of TST in principle? What is the sensitivity of these two parameters on five synthetic data, MNIST and CLN025?

  3. Why is the TST maximum peak k=4 not used in MNIST, but the second peak k=18 is manually selected? If fully automatic selection is required, what will be the output of the method, and how can such a posteriori manual intervention be avoided?

  4. Are NMI differences with DPA on synthetic data subject to pairwise significance testing? Does the comparison still hold under the same sparsification/runtime budget?

  5. Is the exponential leakage decay of Appendix A still demonstrable after sparse PAk truncation? How much impact does truncated neighborhood size have on cluster number selection and NMI?

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

The authors present SDP (Spectral Density Peaks), a method that combines density peaks with PCCA+. For that, they estimate densities around points, derive a density dominance matrix C that stores the probability that a point has a higher density than another point (which is most relevant for the density peaks concept), combine it with a pairwise distance matrix to yield a matrix that 1) gives the probabilities that a point is the "strictly nearest higher-density neighbor of another" point and 2) can be regarded as a Markov state transition matrix. By finding the Markov states with cPCCA+, one receives clusters around those density-peaks. The authors also introduce a k selection method via spectral-gaps (which is unfortunately only described in the appendix), s.t. the method is basically hyperparameter free.

Critical strengths

S1) SDP is a cool method that is based on the density-peaks concept. The combination with Markov states is well motivated.

S2) Being based on fuzzy labels, the method can detect noise automatically - it seems to work on noisy data, which is not easy to achieve.

Critical weaknesses

W1) Experiments are not convincing.

  • The main five datasets are synthetic datasets in only two dimensions. While the datasets are tested with varying sample sizes, it would be relevant to know how the method performs in higher-dimensional data.

  • The results of SDP can contain noise points, which is cool, and the authors also describe how they evaluate in presence of noise labels, which I appreciate a lot as it is often neglected. However, in Tab. 2, please state the percentage/number of detected noise points. This is very important as it can bias the resulting NMI (especially if you handle points labeled as noise as one cluster and the datasets contain many noise points). It would be interesting how many of the ground truth noise points were also detected as noise by SDP (this does not become clear from Tab. 7 in the appendix neither)

  • The competitors are rather basic baselines and newer methods should be included, e.g. the ones discussed in the background section, or e.g., [1,2,3]. Also a comparison to EM (expectation maximization clustering) would be interesting.

[1] Chen, Y., Hu, X., Fan, W., Shen, L., Zhang, Z., Liu, X., ... & Li, H. (2020). Fast density peak clustering for large scale data based on kNN. Knowledge-Based Systems, 187, 104824.

[2] Zhao, J., Wang, G., Pan, J. S., Fan, T., & Lee, I. (2023). Density peaks clustering algorithm based on fuzzy and weighted shared neighbor for uneven density datasets. Pattern Recognition, 139, 109406.

[3] Bian, Z., Chung, F. L., & Wang, S. (2020). Fuzzy density peaks clustering. IEEE Transactions on Fuzzy Systems, 29(7), 1725-1738.

W2) Some relevant parts of the method are only described in the appendix

  • The selection of k is only discussed very briefly in 3.2 and the detailed description from Appendix C should be in the main paper. It would also be beneficial to perform experiments on how good the k-estimation is.
  • In Sec. 3.2, it does not become entirely clear from the text whether QS is actually used or only described here in order to explain the intuition behind other steps.
  • While it is ok to refer to the appendix for the detailed computation, at least a rough estimate of the complexity should be given in Sec. 3.4 when you already have "Algorithmic Scalability" as a header.
  • Give NMI for the MNIST clustering you discuss in Fig. 3.

Minor

  • Highlight best/second best results in bold/underlined helps reading a table like Tab. 1 faster.
  • line 158: use \varepsilon consistently and do not switch between \epsilon and \varepsilon.
  • line 158: Jaccard overlap should be cited or referred to and be explained briefly.
  • Line 159: two full stops instead of one.
  • Line 196: PAk should be cited or referred to.
  • Description of MNIST dataset in 4.2 can be shortened to make space for more relevant stuff as described above.
  • Some of the references contain full first names, and some contain abbreviated first names. Please keep it uniform.
Questions for authors

See weak points:

Q1) How does the method perform on high-dimensional data?

Q2) How good is the noise detection? (How many of the GT noise objects are detected? How many false positives do you find? How many noise points did the GT have?)

Q3) How good is the k-estimation? For MNIST, your method is far from 10 - how is it for other datasets?

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

Related papers

Discussion (0)

Sign in to comment.