  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.
