Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: This paper proposes a different density function for popular density-based clustering algorithms, i.e. truncated symmetric and asymmetric Gaussian kernels for DBSCAN and DPC. It offers some diffusion-based argument for why that is a better density function for clustering than naive function, and provides a computationally more efficient surrogate function as well. 
Performance of proposed method on many clustering experiments are provided.
main_review: The suggested kernels are easy to understand, and many experimental results are provided, including sensitivity analysis to hyperparameters and computational analysis. 

However, the authors need to more clearly explain and motivate their approach.

First of all, Section 4.1 needs to be re-written much more carefully and accurately. For example:
-  "$p(x,y)$ can be viewed as a probability for a random walk on the dataset from point x to point y": I don't think random walk is the correct term here, as random walks can be paths of any lengths.
-  "view D as a graph": a graph is a set of nodes and edges. Right now, D is only a set of points/samples. What are the edges?
- If L is the normalized graph Laplacian, is it a $n \times n$ matrix? If so, what is $L \rho(x, t)$ in equation (4) with the output of $\rho$ being a scalar?
- Aren't equations (4) and (5) *first*-order differential equations?
- The approach should be better motivated, i.e. include the answer to what is the point of all this discussion about diffusion, in the context of clustering? The paragraph on the top of page 5 is probably the most important part of Section 4, but it's not easy to understand. Can the authors explain the second half of that paragraph in more detail, perhaps with a figure or a toy example? 

Clarifications for other parts:
- There needs to be a more concrete description/explanation of the density-based clustering algorithms, i.e. DBSCAN and DPC, using the notations from this paper. The introduction, related work or preliminaries would be a good place.
- Section 4.3 is a little hard to follow. For example in page 6, "This shows that $\rho_{FKD}$ elevates the density of small clusters": what does this sentence mean, and how does it follow from Theorem 1? Are there any divide-by-zero problems that could happen with $\rho$?

For the experiments:
- Sections 5.1 and 5.2 are missing sufficient reproducibility information. How many times were the experiments conducted? Should there be error bars? What are the "suitable range in the parameter space"? These are information that should have been included in the appendix if page limit was the issue.
- In Sections 5.4, how doest the computational cost of $\rho_{FKD}$ compare to the other density functions such as $\rho_{naive}, \rho_{LC}$? Is there a computation-accuracy tradeoff?

Smaller problems that can be fixed with editing:
- The sentence "Letting $h \to 0$, the random walk..." doesn't make sense. It may have too many verbs?
- In page 5, "some intuitions that why..."
- In page 5, "process grouping of all the data..."
- $\hat{g}$ and $\hat{\rho}$ in the appendix are not defined.

summary_of_the_review: This paper has promising experimental results, but is not ready for publication at this stage. It could become a stronger paper after major revision by motivating and explaning their approach more carefully.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The paper introduces a new approach to performing clustering, based on constructing a Markov process on the input space, in which transitions are determined according to normalised kernel similarity scores, as in Spectral Clustering (SC). Unlike SC, however, the proposal utilises the stationary distribution of the process, or an approximation thereof, evaluated on the data set, as a density function to be used within existing density based clustering algorithms, such as DBSCAN and Density Peaks Clustering (DPC). Experimental results are given to illustrate the methods potential improvement of standard kernel density estimates, and also its potential improvement over purpose-built models for face clustering.
main_review: The proposed method is interesting, and the presentation in the paper is reasonably clear, with some exceptions which I will note below. The empirical results certainly exhibit that potential for strong performance may be there, but I have reservations...

My primary concerns relate to the experimental set up and some uncertainties relating to the presentation, and also the clarity in relation to some of the technical points.

Experiments: -It isn't clear to me if the locally adaptive kernels were only used within the proposed approach, or also within DBSCAN and DPC. If only in the proposed approach, then it is not clear if the improvements in performance are actually a result of the new method, or simply down to the choice of kernel. I appreciate that the asymmetric kernel may not be usable in these frameworks, but simple adjustments can be used to symmetrise if necessary. 
 -Without a data-driven means for selecting the tuning parameters for the model, it is not clear whether the results presented are realisable in practice. While "best case" plus "sensitivity study" do provide some evidence of practical relevance, it still isn't entirely clear how well we can expect the method to perform without access to an oracle tuner.
 -In relation to the face clustering problem, were the purpose-driven methods also given access to oracle tuning, or were they tuned using the data? If the latter, then these performance comparisons are not indicative of the actual comparative performance.
- The method is arguably more similar to normalised spectral clustering than to density clustering. Including results from spectral clustering seems an important change to make. In particular, if you use the same locally adaptive kernels within spectral clustering, does your method outperform?

Clarity: - The object D is unclear. At first this is the data set, and then later becomes the entire input space, as far as I can tell. This is especially important when included in technical statements like Assumption 1 and Theorem 2, where the interpretation might differ considerably.
- In the theoretical discussion, the objects \rho_{KD} and \rho_{FKD} are treated as constant, yet these are random variables. Is the convergence described in Theorem 2 sure convergence? As far as I can tell from the proof, it is, but the proof is not very clearly presented.
- The way Theorem 2 is stated, it seems to describe pointwise convergence rather than uniform convergence, yet uniform convergence is used in the text. Can you clarify?
- In Assumption 1 the value of c needs to be independent of n, presumably, otherwise a sequence tending to one as n tends to infinity might present a problem.
- You state that \rho_{FKD} can be determined in linear time. However, doesn't construction of P require at least log-linear time (or even worse?)

If these concerns can be suitably addressed, I would be willing to adjust my score upwards.

* Note that my score on "correctness" below is motivated by the fact that, without further evidence, the claims about practical performance are, in my opinion, not adequately supported. Otherwise the paper appears to be correct.

Some minor comments/questions/corrections follow:
- Why is a standard kernel density estimate referred to as ``naive''? Perhaps ``standard'' is more appropriate?
- The sentence "Such density suffers from capturing local features in complex datasets." in the abstract seems to be incorrect. Should this not read "Such a density suffers from an inability to capture local features in complex datasets.", or similar?
- You mention the issue of boundary bias in kernel density estimation. Does this have any relevance in density clustering?
- In Figure 1 I would argue that it isn't clear the diffusion density shows three clusters "clearly". Arguably the most sparse of the clusters actually manifests as multiple modes and that overclustering might result.
- The operator T_F seems to take x as an argument, so why is this suppressed in the definition?

Finally, although the grammar does not lead to difficulty in comprehension, I would recommend that the authors have their submission proof-read by a native English speaker as there are numerous minor grammatical imprecisions.
summary_of_the_review: An interesting idea with a fairly thorough discussion. However, some issues about clarity in relation to the technical parts of the paper.

Experimental results illustrate some promise, but it is very unclear if the reported performance is practicable as they are based on oracle tuning of hyper-parameters.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The authors propose a new density function for density clustering models such as DBSCAN and Density Peaks Clustering (DPC). Given a kernel $K$ and the corresponding normalized random walk transition matrix $P = diag(K\mathbf{1})^{-1}K$, the authors propose to use the density function which corresponds to the stationary distribution attained in the limit. Since this function is expensive to compute, the authors propose a surrogate density function which is easier to compute.

The main experiments compare various density functions for DPC on UCI classification datasets and the DPC on density functions to face detection methods on two face identification datasets. 
main_review: In some regards, the motivation of the proposed density function is clear. The performance of density-based clustering methods depends to a large degree on the employed density measure and the traditional measures have obvious flaws. The proposed idea is sound and the experiments indicate that the proposed measures are able to improve the performance of clustering methods. 

I am missing in this paper though the connection between the employed clustering methods (DBSCAN and DPC) and the density measure. Likewise, the connection of the proposed method to spectral clustering using the random walk Laplacian is not discussed at all. Shouldn't spectral clustering with the random walk Laplacian return a clustering which maximizes the stationary distribution function within each cluster as well[1]? The relation between spectral clustering and DBSCAN has been established [2,3]. Likewise, spectral clustering itself has an interpretation as a density-based clustering method[4]. As a result, since there is already some literature about kernel diffusion maps and spectral clustering (as cited by the authors), the relationship between these clustering methods and what is particularly novel in this work should be made clear.

For example, Theorem 1 states that clusters which are disconnected in the graph indicated by the epsilon neighborhood kernel have the same density in each cluster. From best practice in spectral clustering we know that disconnected clusters are very sensitive to noise and other perturbations. So, the case which is assumed in Thm 1 to motivate the proposed density measure, should actually be avoided. In this regard, I would ask for a more complete picture of density-based clusterings (including spectral clustering), their theoretical background, and how the proposed density measure can improve the clustering performance (also in dependence of the employed clustering method). At the same time, there exist methods to learn the kernel function such that the data is well clusterable. How is the proposed density measure positioned with respect to these methods? 

The experimental evaluation should be made stronger. The authors state that the required kernel parameters are tuned, which indicates for me that the experimental evaluation makes use of the class information which is not available in real-life clustering applications. I think that this approach could be interesting for experiments such as the ones in Tbl1, where the potential of the density function is evaluated. However, there should be more experiments which simulate the actual clustering process. I would propose to use synthetic data to illustrate differences in the clustering behavior, where the clusters are generated according to given density measures. Such an analysis could also provide insight into the cases where the proposed measures do not work well. Another interesting analysis would be an experiment on synthetic data where the noise is increased. Then, also other clustering procedures should be compared, e.g. spectral clustering and newer nonconvex clustering methods.  How the parameters are defined in the face clustering application is not explicitly described, so I assume that again the parameters have been tuned, which should be avoided.

[1] Von Luxburg, Ulrike. "A tutorial on spectral clustering." Statistics and computing 17.4 (2007): 395-416.

[2] Y. Chen, "DBSCAN Is Semi-Spectral Clustering," 2020 6th International Conference on Big Data and Information Analytics (BigDIA), 2020, pp. 257-264, doi: 10.1109/BigDIA51454.2020.00048.

[3] Schubert, Erich, Sibylle Hess, and Katharina Morik. "The relationship of DBSCAN to matrix factorization and spectral clustering." LWDA. 2018.

[4] Hess, Sibylle, et al. "The SpectACl of nonconvex clustering: a spectral approach to density-based clustering." Proceedings of the AAAI Conference on Artificial Intelligence. Vol. 33. No. 01. 2019.
summary_of_the_review: The authors propose a potentially interesting density measure for density-based clustering methods. Yet, the proposed measure is not sufficiently discussed in the scope of similar works for spectral clustering and the experimental evaluation is using class-label information for hyperparameter tuning, which is not eligible for clustering analyses. Hence, I reject the paper as is and suggest that the authors extend the experimental evaluation and provide a comparison to the related spectral clustering approaches for the next submission.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The paper presents a methodology for defining the density reference function required in density-based clustering methods such as DBSCAN and DPC. The density function is obtained as the limiting probability density of a diffusion process and it takes into account the local characteristics of the dataset. A surrogate density is also proposed that is fast to compute. The method is compared to typical density functions used in DBSCAN and DPC.  
main_review: The proposed idea is interesting and novel. However, there are several concerns to be addressed:
-There is no theoretical justification that the proposed method is able to capture the local characteristics of the dataset.  
-The fast surrogate (FKD) density is very simple to compute. It seems strange that it provides comparable performance to KD. Are there cases where FKD does not perform well?
-What is the complexity of computing \rho_{KD}?
- A major drawback of the method is that it includes additional hyperparameters compared to the naïve approach. In the presented experimental results (Table 1) the value of hyperparameter h=0.5. Therefore the empirical conclusions are conditioned on this value.
- Clustering is an unsupervised problem. It is not acceptable to tune the hyperparameters based on supervised measures.
- I suggest that the authors should provide NMI values for the datasets of Table 1. This is the typical measure. For the face datasets that are more complex, the use of F-measures is acceptable. Moreover, for the datasets of Table 1, it is suggested to present results using typical clustering methods (eg. k-means) as happens with the face datasets.
-  It is important to provide information on the number of clusters returned by the density-based methods for all datasets. Do they recover the ground truth number of clusters?
- What is the dimensionality of the face datasets?
- As a general remark, density-based methods are not considered effective in the case of small datasets of relatively high dimensionality. 

summary_of_the_review: The proposed idea is interesting and suggests an alternative way for specifying density functions for density-based clustering. However, there exist several unresolved issues regarding theoretical justification and, mainly, experimental validation.
review_title: null

Meta-review: This paper proposes a kernel diffusion method to improve upon density-based clustering methods. The reviewers found the empirical results quite promising and there is consensus that there are some good ideas in this work. However, their criticisms are strikingly consistent that the technical details are lacking and some of the claims are not fully supported, and these criticisms were not found to be fully addressed in the author responses. I agree with the assessment that this is promising in a major revision toward a future submission but it is currently not complete, especially in the theoretical and technical details.
Decision: Reject