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 per-formance of the l(1)-regularized PageRank method (Fountoulakis et al., 2019) 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 sup-port of l(1)-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 sup-port of l(1)-regularized PageRank recovers exactly the target cluster. We also show empirically that l(1)-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 l(1)-regularized PageRank is monotonic. This allows for the application of the forward stagewise algorithm, which approximates the entire solution path in running time that does not depend on the size of the whole graph. Finally, we show that l(1)-regularized PageRank and approximate per-sonalized PageRank (APPR) (Andersen et al., 2006), 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 l(1)-regularized PageRank.

Automated summary

This paper analyzes the performance of the l(1)-regularized PageRank method for recovering a single target cluster and demonstrates its state-of-the-art performance on real graphs. The monotonic solution path allows for the application of the forward stagewise algorithm to approximate the entire solution path in a running time independent of the size of the whole graph. Moreover, the equivalence between l(1)-regularized PageRank and approximate personalized PageRank is established, leading to similar results for the latter method.