Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Local Graph Clustering Beyond Cheeger's Inequality   Motivated by applications of large-scale graph clustering, we study
random-walk-based LOCAL algorithms whose running times depend only on the size
of the output cluster, rather than the entire graph. All previously known such
algorithms guarantee an output conductance of $\tilde{O}(\sqrt{\phi(A)})$ when
the target set $A$ has conductance $\phi(A)\in[0,1]$. In this paper, we improve
it to $$\tilde{O}\bigg( \min\Big\{\sqrt{\phi(A)},
\frac{\phi(A)}{\sqrt{\mathsf{Conn}(A)}} \Big\} \bigg)\enspace, $$ where the
internal connectivity parameter $\mathsf{Conn}(A) \in [0,1]$ is defined as the
reciprocal of the mixing time of the random walk over the induced subgraph on
$A$.
  For instance, using $\mathsf{Conn}(A) = \Omega(\lambda(A) / \log n)$ where
$\lambda$ is the second eigenvalue of the Laplacian of the induced subgraph on
$A$, our conductance guarantee can be as good as
$\tilde{O}(\phi(A)/\sqrt{\lambda(A)})$. This builds an interesting connection
to the recent advance of the so-called improved Cheeger's Inequality [KKL+13],
which says that global spectral algorithms can provide a conductance guarantee
of $O(\phi_{\mathsf{opt}}/\sqrt{\lambda_3})$ instead of
$O(\sqrt{\phi_{\mathsf{opt}}})$.
  In addition, we provide theoretical guarantee on the clustering accuracy (in
terms of precision and recall) of the output set. We also prove that our
analysis is tight, and perform empirical evaluation to support our theory on
both synthetic and real data.
  It is worth noting that, our analysis outperforms prior work when the cluster
is well-connected. In fact, the better it is well-connected inside, the more
significant improvement (both in terms of conductance and accuracy) we can
obtain. Our results shed light on why in practice some random-walk-based
algorithms perform better than its previous theory, and help guide future
research about local clustering.

26
The categories of this paper are: bayes-an
19
The categories of this paper are: eess
7
The categories of this paper are: hep-th
8
The categories of this paper are: hep-ex
28
The categories of this paper are: alg-geom
29
The categories of this paper are: funct-an
5
The categories of this paper are: gr-qc
32
The categories of this paper are: atom-ph
34
The categories of this paper are: chem-ph
23
The categories of this paper are: solv-int
9
The categories of this paper are: nlin
27
The categories of this paper are: comp-gas
4
The categories of this paper are: cond-mat
25
The categories of this paper are: patt-sol
31
The categories of this paper are: ao-sci
33
The categories of this paper are: plasm-ph