Statistical guarantees for local graph clustering
  Local graph clustering methods aim to find small clusters in very large
graphs. These methods take as input a graph and a seed node, and they return as
output a good cluster in a running time that depends on the size of the output
cluster but that is independent of the size of the input graph. In this paper,
we adopt a statistical perspective on local graph clustering, and we analyze
the performance of the l1-regularized PageRank method~(Fountoulakis et. al.)
for the recovery of a single target cluster, given a seed node inside the
cluster. Assuming the target cluster has been generated by a random model, we
present two results. In the first, we show that the optimal support of
l1-regularized PageRank recovers the full target cluster, with bounded false
positives. In the second, we show that if the seed node is connected solely to
the target cluster then the optimal support of l1-regularized PageRank recovers
exactly the target cluster. We also show empirically that l1-regularized
PageRank has a state-of-the-art performance on many real graphs, demonstrating
the superiority of the method. From a computational perspective, we show that
the solution path of l1-regularized PageRank is monotonic. This allows for the
application of the forward stagewise algorithm, which approximates the solution
path in running time that does not depend on the size of the whole graph.
Finally, we show that l1-regularized PageRank and approximate personalized
PageRank (APPR), another very popular method for local graph clustering, are
equivalent in the sense that we can lower and upper bound the output of one
with the output of the other. Based on this relation, we establish for APPR
similar results to those we establish for l1-regularized PageRank.
