  Clustering is indispensable for data analysis in many scientific disciplines.
Detecting clusters from heavy noise remains challenging, particularly for
high-dimensional sparse data. Based on graph-theoretic framework, the present
paper proposes a novel algorithm to address this issue. The locally asymmetric
geometries of neighborhoods between data points result in a directed similarity
graph to model the structural connectivity of data points. Performing
similarity propagation on this directed graph simply by its adjacency matrix
powers leads to an interesting discovery, in the sense that if the in-degrees
are ordered by the corresponding sorted out-degrees, they will be
self-organized to be homophilic layers according to the different distributions
of cluster densities, which is dubbed the Homophilic In-degree figure (the HI
figure). With the HI figure, we can easily single out all cores of clusters,
identify the boundary between cluster and noise, and visualize the intrinsic
structures of clusters. Based on the in-degree homophily, we also develop a
simple efficient algorithm of linear space complexity to cluster noisy data.
Extensive experiments on toy and real-world scientific data validate the
effectiveness of our algorithms.
