Diffusions and related random walk procedures are of central importance in
many areas of machine learning, data analysis, and applied mathematics. Because
they spread mass agnostically at each step in an iterative manner, they can
sometimes spread mass "too aggressively," thereby failing to find the "right"
clusters. We introduce a novel Capacity Releasing Diffusion (CRD) Process,
which is both faster and stays more local than the classical spectral diffusion
process. As an application, we use our CRD Process to develop an improved local
algorithm for graph clustering. Our local graph clustering method can find
local clusters in a model of clustering where one begins the CRD Process in a
cluster whose vertices are connected better internally than externally by an
$O(\log^2 n)$ factor, where $n$ is the number of nodes in the cluster. Thus,
our CRD Process is the first local graph clustering algorithm that is not
subject to the well-known quadratic Cheeger barrier. Our result requires a
certain smoothness condition, which we expect to be an artifact of our
analysis. Our empirical evaluation demonstrates improved results, in particular
for realistic social graphs where there are moderately good---but not very
good---clusters.

提出了一种更快且更本地的 Capacity Releasing Diffusion (CRD) Process 并将其用于改进本地图聚类算法，该算法能够在开始 CRD 过程的聚类模型中找到内部连接更好而不是外部连接更好的聚类，是第一个不受二次 Cheeger 障碍影响的本地图聚类算法。