- 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
- 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 . As a side note, the limit has no stated asymptotic parameter (I assume ). As a last remark on this, the definitions and theorems are stated in terms of the estimates , 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.
- 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.
- 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 -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 such that . These results seems to differ.
- Table 3 reports that TST recovers the correct number of clusters on HORSE in out of runs are , and subsampling, but Table 6 report 100% recovery on HORSE at .
Minor weaknesses and notational issues:
- Notations are inconsistent between the main text and the appendices: vs or vs . The quantity 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
- How does SDP perform when 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?
- In the context of MNIST, the selection rule returns . How should a user proceed in a truly unsupervised setting? What are the NMI/ARI against the digit labels for , and , and how do the baselines compare?
- How does the halo mechanism work in practice? Could you provide experiments for this?
- 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 instead of .
- 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.