Density-based Clustering with Kernel Diffusion
Authors: Chao Zheng
Yingjie Chen
Chong Chen
Jianqiang Huang
Xian-Sheng Hua
Venue: ICLR 2022 Submitted (2022)
Keywords: density-based clustering
diffusion process
density function
face clustering

Abstract: Finding a suitable density function is essential for density-based clustering algorithms such as DBSCAN and DPC. A naive density corresponding to the indicator function of a unit $d$-dimensional Euclidean ball is commonly used in these algorithms. Such density suffers from capturing local features in complex datasets. To tackle this issue, we propose a new kernel diffusion density function, which is adaptive to data of varying local distributional characteristics and smoothness. Furthermore, we develop a surrogate that can be efficiently computed in linear time and space and prove that it is asymptotically equivalent to the kernel diffusion density function. Extensive empirical experiments on benchmark and large-scale face image datasets show that the proposed approach not only achieves a significant improvement over classic density-based clustering algorithms but also outperforms the state-of-the-art face clustering methods by a large margin.

Under review as a conference paper at ICLR 2022
DENSITY-BASED CLUSTERING WITH KERNEL DIFFU- SION
Anonymous authors Paper under double-blind review
ABSTRACT
Finding a suitable density function is essential for density- clustering algo- rithms such as DBSCAN and DPC. A naive density corresponding to the indicator function of a unit d-dimeensionl Euclidean ball is commonly used in these al- gorithms. Such a density suffers from an inability to capture local features in complex datasets. To tackle this issue, we propose new kernel diffusion density function, which adaptive to data of varying local distributional characteristics and smoothness. Furthermore, we develop a surrogate that can be efficiently computed in linear time and space and prove that it asymptotically equivalent to the kernel diffusion density function. Extensive empirical experiments on benchmark and large-scale face image datasets show that the proposed approach not only achieves significant improvement over classic density-based clustering algorithms but also outperforms the state-of-the-at face clustering methods by a large margin.
INTRODUCTION
Density-based clustering algorithms are widely used in variety of applications, ranging from high energy physics (Tramacere & Vecchio 2012 Rovere et al. 2020)). material sciences (Marquis)
al. 2019 Reza al.] (2007), social network analysis (Shi et al. 2014 Khatoon & Banu 2019)
to molecular biology (Cao et al. 2017 Ziegler et al.) 2020). In these algorithms, data points are partitioned into clusters that are considered to be sufficiently or locally high-density areas with respect to underlying probability density or a similar reference function. We call them density functions throughout this paper. These techniques are attractive to practitioners, due to their non- parametric feature, which leads to flexibility in discovering clusters that have arbitrary shapes, whilst classic methods such as k-means and k-medoids (Friedman et al. 2000I) can only detect convex (c.g.. spherical) clusters. Seminal work in the context of density-based clustering includes DBSCAN (Ester
et al. 1996) and DPC (Rodriguez & Laio 2014), among many others (Ankerst et al. 1999 Cuevas al.
2001 Comaniciu & Meer 2002 Hinneburg & Gabriel, 2007]
Stuetzle (003).
Most density- based clustering algorithms implicitly identify cluster centers and assign remaining points to the clusters by connecting with the higher density point nearby. To proceed with these methods it requires a density function, which is usually an estimate of the underlying true probability density or some variants of it. For example, a popular choice is the naive density function that is carried out by simply calculating the number of data points covered in the s-neighborhood of each x. Note that such densities are not adaptive to different distribution regions. One of the challenging scenarios is when clusters in the data have varying local features, for example, size, height, spread, and smoothness. Therefore, the resulting density function has tendency to flatten the peaks and valleys in the data distribution, which leads to underestimation of the number of clusters (see Figure 1). Many heuristies variations of DBSCAN and DPC have been proposed to magnify the local features, thus making the clustering task easier (Campello et al. 2013 Chen al.) [2018] Ertöz et al., 2003 Zhu et al.) 2016). Most of these methods can be viewed as performing clustering on certain transformations of the naive density function. However, if the naive density function itself is quite problematic in the first place, these methods will become less effective.
Zhu
Moreover, even if apply adaptive alternatives to modify the classic density functions, there other contentious issues of the generally used linear kernel density estimator (KDE). It often suffers from severe boundary bias (Marron & Ruppert 1994) and is acknowledged computationally

---

Under review as a conference paper at ICLR 2022
Figure 1: (a) Data generated from Gaussian mixture model with 3 components, each has differing variance and weight. (b) Naive density function in 2D (top) and 3D (bottom): only one peak can be identified. (c) Proposed kernel diffusion density function: 3 clusters can be easily discovered.
Cluster-2
Cluster-3
(a) Data clusters
(b) Naive density
(c) Kernel diffusion density
expensive. These phenomenon prevent the classic density functions being practically useful and reliable, especially for large-scale and complex clustering tasks.
To overcome these problems in density-based clustering algorithms, in this paper we propose a general approach to build the so-called kernel diffusion density function to replace classic density functions. The key idea is to construct the density from a user-specified bivariate kernel that has desired local adaptive properties. Instead of using the naive density function and its variants, utilize the bivariate kernel to derive a transition probability. A diffusion process is induced by this transition probability, which admits limiting and stationary distribution. This limiting distribution serves plausible density function for clustering with reduced error.
Under this framework. we provide examples of symmetric and asymmetric bivariate kernels to construct the kernel diffusion density function, which can tackle clustering complex and locally varying data. We apply the resulting adapted DBSCAN and DPC algorithms to widely different empirical datasets and show significant improvement in each of these analyses. The main contributions of this paper are summarized below:
We introduce new bivariate kernel functions and construct the associated kernel diffusion processes. Based the diffusion process, propose kernel diffusion density function to adapt density-based clustering algorithms such as DBSACN and DPC, which attains accuracy in the presence of varying local features.
We derive a computationally much more efficient surrogate, and show analytically it is asymptotic equivalent the proposed kernel diffusion density function.
By extensive experiments, we demonstrate the superiority of kernel diffusion density func- tion over naive density function and its variants when applying DBSCAN and DPC, and show it outperforms state-of- of-the-art GCN-based based methods on face clustering tasks.
RELATED WORK
Density-Based Clustering There is vast literature on adapting density-based clustering algorithms to tackle large variations in different clusters the data. DPC itself is such a refinement of DBSCAN, it determines cluster centers not only by highest density values but also by taking into account their distances from each other, thus has generally better performance in complex clustering tasks. Other attempts include rescaling the data to have relative reference measures instead of KDE (Zhu
2

---

Under review as a conference paper at ICLR 2022
al. 2016 Chen al. 2018), and using the number of shared-nearest-neiggee between two points to replace the geometric distance (Ertöz et al. 2003).
Diffusion Maps The technique of diffusion maps (Coifiman et al. 2005 Coifimn & Lafon 2006
gives a multi-scale organization of the data according to their underl underlying geometric structure. uses local similarity measure to create diffusion process the data which integrates local geometry different scales along time I. Generally speaking, the diffusion will segment the data into several smaller clusters in small and group data into one cluster for large L. Applying eigenfunctions at carefully selected time leads to good macroscopic representations of the data, which is useful in dimension reduction and spectral clustering (Nadler et al.) 2005).
Face Clustering Face clustering has been extensively studied as an important application in machine learning. Traditional algorithms include k-means, hierarchical clustering (Sibson 1973) and ARO (Otto et al.] 2017). Many recent works take advantage of supervised information and GCN models, achieving impressive improvement comparing to traditional algorithms. name few, CDP (Zhan et al., 2018) proposes to aggregate the features extracted by different models;
L-GCN (Wang et al. 2019)) predicts the linkage in an instance pivot subgraph; LTC (Yang et al. (019)) generates a series of subgraphs as proposals and detects face clusters thereon; and GCN(V+E) (Yang ct al. 2020) learns both the confidence and connectivity by GCN. In this paper we demonstrate that the proposed density- clustering algorithm with kernel diffusion, general clustering approach, even outperforms theses state-of sate-offthee tf-tthrr methods that are especially designed for face clustering.
PRELIMINARIES
3.1 NOTATIONS
Let the dataset D { [,, C IR be ni i.i.d samples drawn from distribution measure F with density / on IR Let F, denote the corresponding empirical distribution measured with respect to D, i.., (A) = 3.2 E Lx,), where 1-(+) denotes the indicator function of set A. We write ||u|] as the Euclidean norm of vector u. Let B ((x.=) and Va denote the d-dimensional e e-ball centered at and the volume of the unit ball (O, 1), respectively. Let (x) denote the set of k-nearest neighbors of point within the dataset D.
3.2 DENSITY FUNCTION
Density-based algorithms perform clustering by specifying and segmenting high-value areas in a density function denoted by p. Usually, we calculate each of p(z;), and then identify cluster centers with (locally) highest values. Many popular algorithms such as DBSCAN and DPC employ the following naive density function:
(() V2
Puaive (x)
Σ
ngd
BED
The naive density function Puaive is actually empirical estimation of f for carefully chosen e. It easy to observe, for clustering purpose we only care about Paaive (z) up to a normalising constant, which makes it simply equivalent counting the total number of data points in the e-ball around x.
In practice, the data distribution may be very complex and contains varying local features that are difficult be detected. The naive density in (I) with the same radius for all x usually suffers from unsatisfactory empirical performance, for example, failing to identify small clusters with fewer data points. One possible way alleviate this problem is through a transformation into the following local contrast (LC) function (Chen et al. 2018):
(Lc(x)
Σ (EN
In this way. PLC compares the density of each data point with its k-nearest neighbors. To the benefit of LC, let us consider z to be a cluster center. After local contrasting, Pt.((r) is likely to reach the value of l regardless of the size of this cluster.
3

---

Under review as a conference paper at ICLR 2022
However density functions like PLC still highly depend on the underpinning performance of Paaive- This restricts their applications in clustering data with challenging local features.
4 METHODOLOGY
In this section, we present new type of density-based clustering algorithm, based the notion of kernel diffusion density function. Towards this end, we will introduce a kernel diffusion density function, which takes account of local adaptability and is well-suited for clustering purpose. We provide details on how to derive this density function from a diffusion process induced by bivariate kernels, We also provide a surrogate density function that computationally more efficient.
4.1 DIFFUSION PROCESS AND KERNEL DIFFUSION DENSITY
Considering a bivariate kernel function D D + Rt, such that:
k(x, y) is positive semi-definite, i.e., k(x;, y) 2
k(z, y) is F, -nttergre with respect to both æ and y.
We define d(x) = n So (ax, y) (v) as a local measure the volume at æ and define
k(x,y) d(x)
p(z, v)
(3)
is easy to see that p(z, y) satisfies the conservation property n II p(z, ())F, 1. As a result, p(x, y) can be viewed as a probability for a random walk on the dataset from point to point y. which induces Markov chain on D with in various applications, known as the normalized graph Laplacian construction. For example, we can view D as graph, I 7 P the normalized graph Laplacian, and d(x:) normalization factor.
transition matrix P = [p(z, y)]. This technique is standard
For t 2 O, the probability of transiting from x to in t time steps is given by Pt, the t-th power P. Running the Markov chain forward in time, we observe the dataset different scales, which the diffusion process X2 on D. Let p(x, l): D x IR+ - IR+ be the associated probability density, which governed by the following second-order differential equation with initial conditions:
{
at dL,( = -ppxz, p(z, 0) (0(2),
(4)
where (n(x) ) a probability density at time = 0. In practice we can use any valid choice of do(xx) e.g. the uniform density.
To give an explicit example of the diffusion process, consider sub-class of k. i.e. isotropic kernels, dual interpret h as
where k(x,, v) K[]] wl/²/h) for some function I.: lR R+ Here a scale parameter to infer local information and as time step h = At at which the random walk jumps. Then we can define the forward Chapman-Kolmogorre Kolmogorov operator Tp as
Tr(x)= =n S. p(z, v) (y)
Note that Tr is the data distribution time /. h, thus be viewed continuous analogues of the left multiplication by the transition matrix P. Letting h - 0, the random walk converges to a continuous diffusion process with probability density evolves continuously in f. In this case, explicitly write the second-order differential equation in (4) as:
i おr p(x, p(x, t) lim h-+0
p(z. t h) p(x,t) lim
TF p(x,t),
(5)
h
where La = lim (Tr - 1)/h is the conventional infinitesimal generator of the process.
Now ready to introduce our kernel diffusion density function.
4

---

Under review as a conference paper at ICLR 2022
Definition 1. (Kernel diffusion density function) Suppose the Markov chain induced by P is ergodic, we define the kernel diffusion density function as the limiting probability density of the diffusson process Xx, i.e.
(KD(a) = lim p(a, 1). 1-000
(6)
Intuitively, on the one hand, with increased values of t we expect the diffusion process X, gradually reveals the geometric structure (such as high-density regions) the data distribution F. To see this, note that the transition probability P reflects connectivity between data. We can interpret a cluster as an underlying geometric structure in which the probability staying in this region is high during transition. In the diffusion process, the probability of following a path along a structure usually increases with t, as the involved data points are dense and highly connected. Therefore, the path consists of short and high probability jumps. Whilst paths that do not follow any structure consists of long and low probability jumps, which lowers their overall probability. As a result, geometry structures of F is magnified during the diffusion.
On the other hand, by talking certain sophisticated forms of k<x, that take into account of local adaptivity, we also slow down the diffusion to avoid trivial geometry structures such as one big cluster for all the data points. In this way, we can eventually identify the correct geometry structure at the right scale.
4.2 LOCALLY ADAPTIVE KERNELS
To address the local adaptability in kernel diffusion density function, propose the following two bivariate kernels. Both of them are very simple variations of the most commonly used classic kernels.
Symmetrii-GGussian kernel:
k(z, v) = exp (- || y/1
IV)
(7)
h
Here and are both hyper-parameters. We call this kernel symmetric since k(r, v) = k(y, x)
Asymmetric-Gaussin kernel:
k(x, v) exp (- || y/
(a(a))()-
(8)
h
Here and are hyper-parametert Note that in this case k(x, y) is asymmetric as E N&(w) does imply (y).
Bivariate kernels defined in 7 and ( are just combinations of classic Gaussian kernel and s- neighbourhood k-nearest neighbours kernels, respectively. With these simple combinations, truncate Gaussian kernel at local areas, and the contribution of each point y to the construction of the density function (xD( depends only on the distance |yy - x|| but also on the local geometry structure around ær Hence, the new kernels are adaptive at different I, which is expected to lead to better clustering performance against local features. We remark that the Asymmetric Soymmetric-Gaussian kernel takes into account varying neighborhood around each thus is more adaptive comparing to the Caametric-Gaussian kernel.
Although here we only provide two examples of locally adaptive kernels, other options can be easily created similar spirit under this framework, e.g., changing the Gaussian kernels other kernels or changing the e-neighbourhood (k-nearest neighbours) kernels to other locally truncated functions. Once (ax 3/ is determined, we can derive the corresponding density function PKD- Next, we just need simply apply any density clustering procedure like DPC or DBSCAN based on PKD instead of the naive density function Pnaive-
In Section 5
assess the empirical performance of the proposed kernel diffusion density function with the above two locally adaptive kernels. They outperform existing density- based algorithms and other state-of-the-art methods.
5

---

Definition 2. (Fast kernel diffusion density function) Let ply, x) be the transition probability from point y to point v, as defined equation 1 We define the fast kernel diffusion density function as Under review as a conference paper at ICLR 2022
4.3 FAST KERNEL DIFFUSION DENSITY
The kernel diffusion density function can be calculated as the stationary distribution of a Markov chain induced by the transition matrix P. Numerically, we can solve it by iteratively right multiplying P witt p(z, !) until convergence, or applying QR decomposition on P. These methods are expensive in terms of computational cost, especially when the sample size n is large.
To tackle this problem, we propose the following surrogate of PKD( which is computationally more efficient.
PPKD (x) = S. ply. x x))F
is straightforward that PEKD can be obtained in linear time and memory space, as we only need to compute the column averages of matrix P.
Here we show that PFkD is only computationally efficient but also suitable for detecting local features. This is illustrated through the following Theorem Consider special case that k(x, y) B((.,)(y)) Then it is easy verify that
(FKD(x)
Σ
Ca
WE B(x,s) Anaive(1)
where Co = ns is a normalising constant. In this way, we build connection between PFKd and the naive density function Pnaive in this special example.
Theorem 1. Consider the above special case that k(z,y) (B))))) In addition, assume the dataset
( Inn can be split into disjoint clusters: i.e., X Di U... Dm and for each x E D, B(x,8) 8) only contain data points that belong to the same cluster as x. Denote P5 Dj ExED, (FKD(z) (z) as the average density cluster j. We have
pm
Theorem I demonstrates that the averaged PeKD in each cluster the same regardless of cluster sizes and other local features. This shows that PEKD elevates the density of small clusters, which is essential for finding the density peaks of small clusters.
Previously we claim that PTKD is a surrogate of the kernel diffusion density PKD- Next, we want to reveal the relationship between these two density functions from asymptotic viewpoint. To proceed, we will need the following assumption.
Assumption There exists some positive constant e that is independent of n. such that (FKD(I)= S c holds for every
D.
This is very mild assumption, since it always holds that (FKD (z) ) <
and the average of PFKd (z) over the dataset is Jp PFKD JLF, (z) = L/n. which vanishes as n - oo. Now we are ready to present the following theorem that characterise the closeness between fTKD and PKD-
Theorem 2. Suppose that Assumption holds and the Markov chain induced by the kernel k(x, y) is ergodic. We have
(KD(x) PFKD
a.s 1
As shown in the Appendix, the almost sure convergence in Theorem 2 is of a fast rate at n Thus it safe for to use it to replace PKD in finite sample experiments. This result also verified by our numerical experiments in Section 5
5 EXPERIMENTS
In this section, we empirically evaluate the proposed kernel diffusion density functions against Pnaive and PLC in bbased clustering algorithms, and also compare them with other state-of-the-art

---

Under review as a conference paper at ICLR 2022
Table 1: Clustering performance on benchmark datasets with different density functions applied to DPC. Pairwise F-score (Fp) and BCube F-score (F')) under optimal parameter tuning are given. The best and second-bset results in each dataset are bolded and underlined, respectively.
Fp
FB
Dataset
05ym PFKD
Pnaive
PLC
PKD
PKD
FKD
Pnaive
PLC
PKD
PKD
FKD
PFKD
Banknote
54.3
31.6
67.2
83.9
67.2
93.6
57.7
31.8
67.2
85.1
67.2
93.6
Breast-d
55.9
51.8
78.0
69.1
67.4
72.6
59.0
58.7
76.0
69.7
69.4
72.2
Breast-o
57.6
70.7
82.8
92.9
82.7
92.9
52.2
74.1
75.9
92.2
75.8
92.2
Control
48.6
49.3
49.0
63.9
52.5
64.5
51.6
52.4
52.0
70.8
55.1
71.8
Glass
36.9
39.0
46.3
48.1
44.8
47.8
42.7
45.7
55.1
56.9
53.5
57.1
Haberman
66.9
64.1
74.5
75.7
75.8
75.7
66.9
63.3
74.5
75.8
75.9
75.8
Ionosphere
27.4
28.3
46.9
54.9
46.0
53.9
25.0
25.8
42.6
52.5
41.7
49.2
Iris
54.3
53.8
65.8
74.6
69.2
74.6
61.6
62.3
72.7
80.0
74.0
80.0
Libras
20.0
22.9
29.3
31.5
26.0
31.0
26.8
29.1
37.8
41.8
33.3
39.8
Pageblocks
92.9
93.0
90.5
90.2
89.7
90.2
89.9
90.0
89.8
89.7
89.6
89.7
Seeds
54.3
54.9
68.0
78.0
69.5
78.0
54.3
55.4
72.4
78.7
72.9
78.7
Segment
48.4
48.0
57.1
58.0
41.4
56.1
64.2
63.8
67.1
69.2
60.6
68.2
Wine
45.2
61.1
56.6
68.0
60.0
65.3
46.0
61.9
61.5
74.7
66.3
71.4
methods. We denote PKD and PFKD as the kemel diffusion density functions and its fast surrogate, with Coaametrie-Gausiinn kernel, respectively. Similarly, we denote sny and (FKD the proposed two density functions with asymmetric- Gausssaan kernel, respectively. We examine their performance on wide range of datasets. The clustering results are measured Pairwise F-score (Banerjee et 2005). BCubed F-score (Amigó et al. 2009) or NMI (Cover 1999).
sym
sym
5.1 PERFORMANCE ON BENCHMARK DATASETS
We now discuss the performance 13 benchmark datasets (~~100 to ~5, 000 data points) from UCI repository. The metadata summarised in the Appendix.
sym As summarised in Table both PKD and PKD uniformly outperform Pnaive and PLC in terms of clustering accuracy in terms F-scores. results based on NMI are deferred to the Appendix. The proposed kernel diffusion density functions with asymmetric Gaussian kernel, PKD which enjoys better local adaptivity analytically, achieves the best results on most datasets and outperforms Praive sym and PLC by large margin. It is worth noticing that the two fast surrogates, PFKD and PrKD achieve sym comparable results with their original counterparts, PKD and PKD In the Appendix similar results observed for the same set of density functions applied DBSCAN.
aym
Figure 2: Precision-Recall curves of different approaches applied to DPC on MSIM dateset, using (a) Pairwise metric, and (b) BCubed metric
10200
prackion
jewcldmn

---

Under review as a conference paper at ICLR 2022
5.2 PERFORMANCE ON FACE IMAGE DATASETS
Clustering face images according their latent identity becomes an important application in recent years. It is challenging in the sense that face image datasets usually contain thousands of identities, corresponding to thousands of clusters. Meanwhile, the number of images for each identity (cluster) is quite different, corresponding to the variety of cluster sizes. We assess the performance of the proposed approach on two popular face image datasets: emore 200k (Zhan et al. 2018) and MSIM (Guo et 2016).
emore 200k. The dataset contains 2.577 identities with 200,000 images following the protocol in Zhan et al. (2018). We set to 0.8, 200, and to 0.5 for density- Results summarized in Table 2 The proposed diffusion density func- tions are applied DPC, and com- pared with k-means, HAC (Sibson 1973). ARO (Otto al. 201 7). and CDP (Zhan et al. 2018). Agan, we observe significant improvement in the proposed density functions over Pnaive and PLC- It is also worth point- ing out that, density-based cluster- ing with proposed kernel diffusion density functions also outperform the state-of-the-arts approaches such as CDP by a large margin.
Table 2: Clustering performance on emore_ 200k. BCubed precision, recall and F-score are reported.
Algorithm # clusters
Precision
Recall
FB
methods.
k-means
2,577
94.24
74.89
83.45
HAC
2,577
97.74
88.02
92.62
Baseline
ARO
85,150
52.96
16.93
25.66
CDP
89.35
88.98
89.16
Puaive
7928
92.36
78.14
84.65
PtC
3485
96.15
86.58
91.11
Density -based
PkD
2781
95.82
93.24
94.51
PKD
usy
2546
95.48
93.82
94.64
PEKD
3622
95.27
92.54
93.89
PEKD
2569
96.37
93.93
95.13
-oot available
MSIM. The dataset contains 8,573 iden- tities with around 584,000 images follow- ing the protocols in Yang al. (2020). We set E to 0.8, k to 200, and h to 0.5 for density-based methods. We reported the results of clustering performance in Table Precision versus Recall curves for different density functions (applied Ta-
Table 3: Clustering performance MS1M. Pairwise F.
score and BCubed F-score are reported.
Algorithm
# clusters
Fp
FB
k-means
8,573
79.21
81.23
HAC
8,573
70.63
70.46
Unsupervised
ARO
13.60
17.00
to DPC) are plotted Figure 3 the proposed kernel diffusion den- sity functions outperform Praive and PLC- Note that (CCN-based methods such
CDP
75.02
78.70
L-GCN
78.68
84.37
Supervised
LTC
85.66
85.52
GCN(V+E)
87.55
85.94
L-GCN WWang et al.) 2019), LTC (Yang al. 2019) and GCN (V+E) (Yang al. 2020) achieve generally better clustering performance than unsupervised methods due to their supervised nature. However, it quite encouraging see that the proposed kernel diffusion approaches, al- though are also unsupervised clustering methods, considerably outperform the GCN-based methods.
Puaive
59551
78.37
79.35
PLC
24019
83.61
85.06
J0m
Density- based
PKD
Jay
22869
88.15
87.14
PEKD
Jom
34246
84.40
85.37
asym
22927
87.26
87.41
Not available
5.3 SENSITIVITY ANALYSIS
Next, we examine the sensitivity of the proposed kernel diffusion density functions to hyper- parameters and compare it with Puaive and PLC. The results are obtained via extensive experiments on emore 200k and MSIM, which are shown in Figure We can that the clustering performance of sym is much more stable than Pnaive and Prc when we vary the value of e. Whilst PKD the parameter k. and both PKD and PkD quite robust the parameter h.
daym is robust to
sym
8

---

Under review as a conference paper at ICLR 2022
Figure 3: Sensitivity analysis emore_ amnor__00kk and MS1M. We investigate the clustering performance by varying the following parameters: (a) Radius of E-ball; (b) Number &s of nearest neighbors; (c) Bandwidth h of Gaussian kernel.
200k
1.0
1.00
0.95
Beabed Parore
0.95
0.90
0.85
0.90
0.7
0.80
0.6
0.5
0.70
0.2
0.4
0.6
0.8
1.0
20
40
60
80
100
0.2
0.4
0.5
0.8
1.0
MS1M
1.00
0.95
Brubed Pagere
0.95
0.90
0.85
0.7
0.6
0.75
0.70
0.80
0.6
100
(0) h
-
P
5.4 COMPUTATIONAL COST
We carried out series of experiments on MSIM to demonstrate the computational efficiency of the fast surrogate PeKd in terms of time and space. With collec- tion of subsampled data from MSIM different percentile levels, we run both the kernel diffusion density PKD and the fast surrogate PFKD- As we can observe from Figure 4 the running time and memory usage of PKD increase dramatically with the sample size. Whilst ØFKD retains a very low level of computational cost. This suggests that PFKD. which achieves an ex- cellent computational efficiency, should be favored in practice.
Figure 4: Running time and memory usage of the pro- posed methods at different sample sizes on MS1 M..
140
running time:
100
mory usage Pro
TO00000 USS0 (G9)
memorry Usage An1
00
20
100
200
300
400
500
600
#samples (x10*)
CONCLUSION
Density-based clustering has a profound impact on machine learning and data mining. However, the underpinning naive density function suffers from detecting varying local features, causing extra errors in the clustering. We propose a new set of density functions based on the kernel diffusion process resolve this problem, which is adaptive to density regions of varying local distributional features. We demonstrate that DBSCAN and DPC adapted by the proposed approach have improved clustering performance comparing their classic versions and other state-of-the-an methods.

---

Under review as a conference paper at ICLR 2022
REFERENCES
Enrique Amigó, Julio Gonzalo, Javier Artiles, and Felisa Verdejo. A comparison of extrinsic clustering evaluation metries based on formal constraints. Information Retrieval, 12(4):461 2009.
Mihael Ankerst, Markus Breunig, Hans-Peter Kriegel, and Jörg Sander. Opties: Ordering points to identify the clustering structure. ACM Sigmod Record, 28(2):49-66) 60, 1999.
Arindam Banerjee, Chase Krumpelman, Joydeep Ghosh, Sugato Basu, and Raymond J Mooney. Model-based overlapping clustering. In Proceedings of the eleventh ACM SIGKDD International Conference on Knowledge Discovery Data Mining, pp. 532-537, 2005.
Ricardo JGB Campello, Davoud Moulavi, and Jörg Sander. Density-based clustering based on hierarchical density estimates. In Pacific-Asia Conference Knowledge Discovery and Data Mining, pp. 160-172. Springer, 2013.
Junyue Cao, Jonathan S Packer, Vijay Ramani, Darren A Cusanovich, Chau Huynh, Riza Daza, Xiaojie Qiu, Choli Lee, Scott N Furlan, Frank J Steemers, et al. Comprehensive single-cell transcriptional profiling of multicellular organism. Science, 357(6352) 2017.
Bo Chen, Kai Ming Ting, Takashi Washio, and Ye Zhu. Local contrast as an effective means to robust clustering against varying densities. Machine Learning, 107(8):1621-1644) 2018.
Ronald R Coifman and Stéphane Lafon. Diffusion maps. Applied and Computational Harmonic Analysis, 21(1):5-30, 2006.
Ronald Coifman, Stephane Lafon, Ann B Lee, Mauro Maggioni, Boaz Nadler, Frederick Warner, and Steven W Zucker. Geometric diffusions as a tool for harmonic analysis and structure definition of data: Diffusion maps. Proceedings of the National Academy of Sciences, 102(21):7426-4431 2005.
Dorin Comaniciu and Peter Meer. Mean shift: A robust approach toward feature space analysis. IEEE Transactions on Pattern Analysis and Machine Intelligence, 24(5):603-61) 2002.
Thomas M Cover. Elements of information theory. John Wiley Sons, 1999.
Antonio Cuevas, Manuel Febrero, and Ricardo Fraiman. Cluster analysis: a further approach based density estimation. Computational Statistics & Data Analysis, 36(4):441-455 2001.
Levent Ertöz, Michael Steinbach, and Vipin Kumar. Finding clusters of different sizes, shapes, and densities in noisy, high dimensional data. In Proceedings of the 2003 SIAM International Conference on Data Mining, pp. 47-58. SIAM, 2003.
Martin Ester, Hans-Pete Peter Kriegel, Jörg Sander, Xiaowei Xu, et al. A density- based algorithm for discovering clusters in large spatial databases with noise. In KDD, volume 96, pp. 226-231, 1996.
Jerome Friedman, Trevor Hastie, Robert Tibshirani, et al. The elements of statistical learning, volume Springer Series in Statistics New York, 2001.
Yandong Guo, Lei Zhang, Yuxiao Hu, Xiaodong He, and Jianfeng Gao. Ms-celeb- Im: A dataset and benchmark for large-scale face recognition. In European Conference on Computer Vision, pp. 87-102. Springer, 2016.
Alexander Hinneburg and Hans Meas-n Gabriel. Denclue 2.0: Fast clustering based on kernel density estimation. In International Symposium on Intelligent Data Analysis, pp. 70-80. Springer, 2007.
Jeffrey Hunter. Generalized inverses and their application to applied probability problems. Linear Algebra and Its Applications, 45:157-198. 1982.
Mehjabin Khatoon and W Aisha Banu. An efficient method to detect communities in social networks using dbscan algorithm. Social Network Analysis and Mining, 11): 2019.
10

---

Under review as a conference paper at ICLR 2022
Emmanuelle A Marquis, Vicente Traullo-Peters, Yan Dong, Auriane Etienne, Svetlana Fedotova, Katsuhiko Fujii, Koji Fukuya, Evgenia Kuleshova, Anabelle Lopez, Andrew London, et al. On the use of density-based algorithms for the analysis of solute clustering in atom probe tomography data. In Proceedings of the 18th International Conference on Environmental Degradation of Materials in Nuclear Power Systems- Water Reactors, pp. 2097-2113. Springer, 2019.
James S Marron and David Ruppert. Transformations to reduce boundary bias in kemel density estimation. Journal of the Royal Statistical Sociery: Series B (Methodological), 56(4):653-67 671, 1994.
Boaz Nadler, Stephane Lafon, Ronald R Coifman, and Ioannis Kevrekidis. Diffusion maps, spectral clustering and cigenfunctions of fokker-plane planck operators. arXiv preprint math/0506090, 2005.
Charles Otto, Dayong Wang, and Anil K Jain. Clustering millions of faces by identity, IEEE
Transactions on Putlern Analysis and Machine Intelligence, 40(2):289-303, 2017.
Hasanzadch PR Reza, AH Rezaie, SHH Sadeghi, MH Moradi, and M Ahmadi. A density-based fuzzy clustering technique for non-destructive detection of defects in materials. Ndr & E International, 40(4))337-346, 2007.
Alex Rodriguez and Alessandro Laio. Clustering by fast search and find of density peaks. Science, 344(6191)11422-4999 2014.
Marco Rovere, Ziheng Chen, Antonio Di Pilato, Felice Pantaleo, and Chris Seez. Clue: A fast parallel clustering algorithm for high granularity calorimeters in high-energy physics. Frontiers in Big Data, 3, 2020.
Jieming Shi, Nikos Mamoulis, Dingming Wu, and David W Cheung. Density- -baed place clustering in goo-so networks. In Proceedings of the 2014 ACM SIGMOD International Conference on Management of Data, pp. 99-110, 2014.
Robin Sibson. Slink: an optimally efficient algorithm for the single-link cluster method. The Computer Journal, (611)330-34 1973.
Werner Steezzle. Estimating the cluster tree of a density by analyzing the minimal spanning tree of sample. Journal of Classification, 20(1):25-44 2003.
Tramacere and C Vecchio. 7-ray dbscan: clustering algorithm applied to fermi-lat 7-ray data. In AIP Conference Proceedings, volume 1505, pp. 705-708 American Institute of Physics, 2012.
UCL. UCI machine learning repository.
uci www..u.......aaaaaee
php
Zhongdao Wang, Liang Zheng, Yali Li, and Shengjin Wang. Linkage based face clustering via graph convolution network. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 1117-1125 2019.
Lei Yang, Xiaohang Zhan, Dapeng Chen, Junjie Yan, Chen Change Loy, and Dahua Lin. Learning to cluster faces on affinity graph. In Proceedings of the IEEF/CVF Conference on Computer Vision and Puttern Recognition, pp. 2298-2306, 2019.
Lei Yang. Dapeng Chen, Xiaohang Zhan, Rui Zhao, Chen Change Loy, and Dahua Lin. Learning to cluster faces via confidence and connectivity estimation. In Proceedings of the IEEE/CVF Conference Computer Vision and Pattern Recognition. pp. 13369-13378 2020.
Xiaohang Zhan, Ziwei Liu, Junjie Yan, Dahua Lin, and Chen Change Loy. Consensus-driven propagation in massive unlabeled data for face recognition. In Proceedings of the European Conference on Computer Vision (ECCV), pp. 568-583, 2018.
Ye Zhu, Kai Ming Ting. and Mark J Carman. Density-ratio based clustering for discovering clusters with varying densities. Puttern Recognition, 60:983-997, 2016.
Carly GK Ziegler, Samuel Allon, Sarah K Nyquist, Ian M Mbano, Vincent N Miao, Constantine N Tzouanas, Yuming Cao, Ashraf S Yousif, Julia Bals, Blake M Hauser, al. Sars-cov-2 receptor ace2 an interferon-stimulated gene in human airway epithelial cells and is detected in specific cell subsets across tissues. Cell, 18165):0066-1035 2020.

---

Under review as a conference paper at ICLR 2022
A APPENDIX
In this supplementary file, we provide technical proofs the theoretical results Section 4.3 and present extra empirical experiments regarding our kernel diffusion approach with symmetric and asymmetric Gaussian kernels applied to DBSCAN. All the numerical experiments are carried out on standard work station with Intel 64-cores CPU and two Nvidia P100 GPUs.
A.1 PSEUDO CODE FOR DBSCAN AND DPC.
Algorithm DBSCAN
1: Input: SetOfPoints X, Eps MinPts k
2: H:=f== E [B) n 2 k]:
3: G:=undirected graph with vertices H and edge between 2, x' E if l x1 S
4: Output: connected components of G
The connected compoenents of the graph are determined a clusters,a dn the remaining points are unclustered and considered as noise-points.
Algorithm 2 DPC
Input: SetOfPoints, TruneDis de
2: Compute di,j for Vi, E SerOfPoints;
3: For from I to SetOfPoints.size:
4: Pi p=:= D [dd.)-d.)
5: 6; := minjjo; 2p. (dzy)
6: Plot decision map M with as the horizontal axis and as the vertical axis;
7: Mark Point i with relatively higher P; and 6e cluster center;
8: Mark Point i with relatively lower oi but relatively higher ó; as noise point;
9: Assign the rest point with the label the same as the nearest cluster center;
10: Output: SetOfPoints
A.2 PROOFS THEORETICAL RESULT.
Proof of Theorem Since (Di,... Dm are disjoint, we have p(z, y) 0 if x and belong to different clusters. By the definition of matrix P. for each E Dj. we have
[ pla, y(x.y)dF.,()) 1,
which implies that
JESD JVED,
I
|Dyl-
Therefore,
=
D3 = -SEED, yED,
p(z, (F = 1Dyl.
which implies that P3 = 1 for any j -1,,.... I,...., m.
Before proceeding to the proof of Theorem 2 we need following auxiliary lemma that relates the stationary distribution of Markov chain to an arbitrary vector g-
Lemma A.1. Let P be transition probability matrix of a finite inreducible discrete time Markov chain with states, which admits stationary distribution, denoted by vector n. We write (L...., 1)" E I as the a column vector of ones. The following holds for any vector such that gd e x 0:
(1) (1 -P+eg") non-singular.
(2) Let H P ) then प. g" H.
12

---

Under review as a conference paper at ICLR 2022
Proof. Since iT is the stationary distribution, we have x"e 1. Applying Theorem 3.3 in (Hunter 1982) yields that matrix (1 - P + eg") is non-singular.
Next recall that x² P n², therefore we have
T" [1 P + +egg))
= n²" - = eg
= e"èe
=g¹
which implies x² =9² H.
Proof of Theorem 2. Note that for for each x D, the linear reference function (FKD Jp ply, F. (y) is the corresponding column average of the transition matrix P. We write the i-th column vector of as
p: x...._.........xx...)) x()),
...
Therefore (FK e pt/n
Since the Markov chain induced by the kernel k(x, y) is ergodic, the density p(æ, t) of the diffusion process X, converges the limiting stationary distribution of the Markov chain, denoted by क.
We can write the n-vectors of y and æ in the following form:
(g1s..., = ((PFKD(Z))))) (FKK())))..) and = (PKD(=I)),.... (KD()))
where 9: = eF ps is the i-th column sums of matrix P. As a result, we have
1 LeT 1, and n S/ PKDdFn(x) = = / (R)
n
By the definition of g, know
(eg") )== = neg"
and e pp==9
It follows from Lemma A.I that (1 P + eg²t) is non-singular and n" g" H. where H
(I- - P eg")
We define B I eg". By simple algebra calculation, find B is non-singular with
eg
B = 1
11 n+1
g"
As result, it is easy to see that that gd B-1
and
H p PB PB-
Use the Neumann series, we have
8
H H=B B
(pB-
Thus
TT - T. / T (( )
20
11 1
B
PB (PB-1) 1)
Since assume for any I E D, ((x)
for some 0 < c < 1. This leads
g Pj < nce T Dj negj
Therefore, let K2 be the j-th compoenent of g' PB- it is straightforward
Kg < n + gj < cgj.
13

---

Under review as a conference paper at ICLR 2022
This implies for every D,
1
[ạKD(х) pFKD(=)) S (F)
++
1=0
1
S PFKD(I)
(n+ 1)(1 c)
Hence we have
PKD(2;)
P lim n-+ PFKD(x)
-1 =1
which completes the proof.
A.3 ADDITIONAL. NUMERICAL. EXPERIMENTS
Naive density with different bandwidths. To illustrate the fail of naive density function in scenario as in Figure 1, we also plot with range of different values of hyperparameters below. We can observe that it is difficult to detect the three true underlying clusters in all the cases.
Figure 5: Naive density function in 3D with different values e.
0.05
<= 0.2
<= 0.3
== 0.4
The parameter s (radius of the ball, used in Pasive, PLC, PKD and PFKD) is tuned by searching within the range between 0.1 and I with am increment of 0. parameter (number of asym nearest neighbors, used in PLC. PKD and asym, is tuned by searching within the range between 10% and 50% number of samples, with an increment of 10%.
Hyperparameters
xym
sym
Metadata of benchmark datasets. The number of samples n, the number of clusters and feature dimension for each benchmark dataset are listed in Table below.
Benekmark datasets with DBSCAN. We provide the performance of the conventional density functions, Pnoive and Pr.c, and the proposed kernel diffusion density functions with symmetric and asymmetric Gaussian kernels, PkD and PEXD (* E {sym, asym)). applied to DBSCAN on 13 bench- mark datasets. The results are summarised in T Similar to DPC, we see that both sym and asym PKD uniformly outperform Praive and PLC in terms of clustering quality. PKD which has better local adaptivity analytically, achieves the best results on most datasets and outperforms others by a significant margin in Breast-o, Control, Haberma and Seeds.
asym
NMI for benchmark datasets. Below we present Table the clustering results for benchmark datasets based on NMI metric.
14

---

Under review as a conference paper at ICLR 2022
Table 4: Metadata of benchmark datasets, includes sample size (7)) the number of clusters (c), and feature dimension d.
Dataset
Y2
d
Banknote
1372
2
4
Breast-d
569
2
30
Breast-o
699
2
9
Control
600)
6
60
Glass
214
7
9
Haberman
306
2
3
Ionosphere
351
2
34
Iris
150
3
4
Libras
360
15
90
Pageblocks
5473
5
10
Seeds
210
Segment
210
7
19
Wine
178
3
13
Table 5: Clustering performance on benchmark datasets with different density functions applied to
DBSCAN. Pairwise F-score (Fp) and BCube F-score (Fn) under optimal parameter tuning given.
The best and second-best results in each dataset are bolded and underlined, respectively.
Fp
FB
Dataset
sym PKD
asym PKD
sym PFKD
asym PFKD
sym PKD
asym PKD
sym PFKD
asym PFKD
Puaive
PLC
Pnaive
PLC
Banknote
26.8
60.7
62.0
66.4
65.4
66.4
26.5
65.1
60.7
67.4
65.7
67.4
Breast-d
56.7
63.0
65.0
66.6
67.2
66.6
60.9
64.7
66.0
67.4
67.2
67.4
Breast-o
18.2
55.3
59.2
70.6
70.5
70.6
15.9
50.7
52.3
71.3
70.6
71.2
Control
32.5
37.1
51.0
60.3
48.9
59.1
34.2
50.1
53.7
66.9
51.6
65.7
Glass
22.0
29.8
29.8
42.5
42.0
42.5
25.8
36.9
36.9
45.2
43.5
45.2
Haberman
68.6
72.2
68.6
75.6
68.9
75.3
69.2
73.1
69.2
75.8
68.3
75.7
Ionosphere
25.9
68.4
68.0
74.2
74.2
74.2
23.8
64.1
63.7
72.1
72.1
72.1
Iris
66.2
69.8
66.2
57.2
73.7
73.3
67.2
76.6
67.2
67.0
79.4
79.0
Libras
18.1
12.0
15.6
13.8
20.2
13.5
31.1
16.5
42.1
45.5
32.9
37.7
Pageblocks
48.4
89.2
90.0
90.1
89.9
90.1
45.2
85.5
89.7
89.5
89.7
89.5
Seeds
57.8
47.6
57.8
63.2
22.4
62.4
59.2
53.0
59.2
70.0
24.4
69.2
Segment
18.5
47.9
54.8
30.8
41.4
30.8
22.5
55.2
66.6
53.6
59.9
53.6
Wine
40.5
40.5
40.5
49.5
50.0
49.5
45.7
45.7
45.7
52.3
51.3
52.3
Number of clusters. In Table 7 present the number of clusters returned by the density-based methods for the benchmark datasets. It can be observed that clustering with the proposed diffusion density functions returned significantly better estimate of the number of clusters, comparing that with classic density functions such as Proine and PL.-
15

---

Under review as a conference paper at ICLR 2022
Table 6: Clustering performance benchmark datasets with different density functions applied to DPC. NMI under optimal parameter tuning are given. The best results each dataset are bolded.
NMI
Dataset
Pruiie
PLC
sym PKD
asym PKD
3ym PFDD
PHKD
k-means
Spectral
Banknote
27.5
33.0
21.7
64.8
53.2
80.2
34.2
17.3
Breast-d
43.7
49.1
46.8
57.4
55.7
46.1
62.3
52.6
Breast-o
30.2
32.7
37.2
79.1
36.4
78.4
74.8
14.0
Control
60.6
60.6
63.2
69.5
61.0
69.6
75.4
68.3
Glass
43.1
43.4
45.0
48.4
43.8
46.6
34.8
36.4
Haberman
9.5
5.7
9.5
3.2
16.9
3.2
7.8
6.6
Ionosphere
27.9
28.0
30.9
31.1
30.1
30.5
13.5
5.2
Iris
51.1
53.1
60.1
73.4
62.6
73.4
74.2
70.6
Libras
63.3
66.4
63.0
68.8
68.2
69.1
60.0
56.1
Pageblocks
8.6
13.0
11.8
28.7
14.4
29.1
13.2
12.1
Seeds
47.1
49.8
53.6
64.8
58.6
64.8
67.4
60.3
Segment
63.5
64.4
65.1
72.2
63.0
70.7
61.2
65.2
Wine
58.1
58.2
72.0
73.3
71.1
58.6
84.2
72.7
Table 7: Number of clusters returned by different density functions applied to DPC. The ground truth listed the last column.
Dataset
Pnaive
PUC
sym PKD
asym PKD
sym PFKD
asym PTKD
Ground Truth
Banknote
16
44
26
2
7
2
Breast-d
3
2
3
3
Breast-o
15
17
7
2
1
2
2
Control
32
32
23
23
27
Glass
4
21
4
8
3
7
Haberman
34
40
34
1
Tonosphere
12
11
7
6
7
2
Iris
8
12
4
2
3
3
Libras
12
60
2
61
100
55
15
Pageblocks
7
25
3
10
11
8
5
Seeds
10
10
2
6
Segment
21
27
14
8
6
9
7
Wine
3
16


Reviews:
[{"review_id": "zxf31K8zoYP", "reviewer": "Reviewer_SSTf", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The proposed idea is interesting and novel. However, there are several concerns to be addressed:\n-There is no theoretical justification that the proposed method is able to capture the local characteristics of the dataset.  \n-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?\n-What is the complexity of computing \\rho_{KD}?\n- 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.\n- Clustering is an unsupervised problem. It is not acceptable to tune the hyperparameters based on supervised measures.\n- 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.\n-  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?\n- What is the dimensionality of the face datasets?\n- As a general remark, density-based methods are not considered effective in the case of small datasets of relatively high dimensionality. \n", "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.  ", "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.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "PiaGw1aj-MM", "reviewer": "Reviewer_Nbci", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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...\n\nMy 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.\n\nExperiments: -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. \n -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.\n -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.\n- 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?\n\nClarity: - 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.\n- 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.\n- 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?\n- 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.\n- 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?)\n\nIf these concerns can be suitably addressed, I would be willing to adjust my score upwards.\n\n* 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.\n\nSome minor comments/questions/corrections follow:\n- Why is a standard kernel density estimate referred to as ``naive''? Perhaps ``standard'' is more appropriate?\n- 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?\n- You mention the issue of boundary bias in kernel density estimation. Does this have any relevance in density clustering?\n- 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.\n- The operator T_F seems to take x as an argument, so why is this suppressed in the definition?\n\nFinally, 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_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.", "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.\n\nExperimental 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.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "CRIVEpKD3cQ", "reviewer": "Reviewer_apj8", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The suggested kernels are easy to understand, and many experimental results are provided, including sensitivity analysis to hyperparameters and computational analysis. \n\nHowever, the authors need to more clearly explain and motivate their approach.\n\nFirst of all, Section 4.1 needs to be re-written much more carefully and accurately. For example:\n-  \"$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.\n-  \"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?\n- 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?\n- Aren't equations (4) and (5) *first*-order differential equations?\n- 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? \n\nClarifications for other parts:\n- 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.\n- 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$?\n\nFor the experiments:\n- 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.\n- 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?\n\nSmaller problems that can be fixed with editing:\n- The sentence \"Letting $h \\to 0$, the random walk...\" doesn't make sense. It may have too many verbs?\n- In page 5, \"some intuitions that why...\"\n- In page 5, \"process grouping of all the data...\"\n- $\\hat{g}$ and $\\hat{\\rho}$ in the appendix are not defined.\n", "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. \nPerformance of proposed method on many clustering experiments are provided.", "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.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "-hZF1thsrif", "reviewer": "Reviewer_BUbF", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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. \n\nI 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.\n\nFor 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? \n\nThe 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.\n\n[1] Von Luxburg, Ulrike. \"A tutorial on spectral clustering.\" Statistics and computing 17.4 (2007): 395-416.\n\n[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.\n\n[3] Schubert, Erich, Sibylle Hess, and Katharina Morik. \"The relationship of DBSCAN to matrix factorization and spectral clustering.\" LWDA. 2018.\n\n[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_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.\n\nThe 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. ", "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.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

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