Optimizing Generalized PageRank Methods for Seed-Expansion Community
  Detection
  Landing probabilities (LP) of random walks (RW) over graphs encode rich
information regarding graph topology. Generalized PageRanks (GPR), which
represent weighted sums of LPs of RWs, utilize the discriminative power of LP
features to enable many graph-based learning studies. Previous work in the area
has mostly focused on evaluating suitable weights for GPRs, and only a few
studies so far have attempted to derive the optimal weights of GRPs for a given
application. We take a fundamental step forward in this direction by using
random graph models to better our understanding of the behavior of GPRs. In
this context, we provide a rigorous non-asymptotic analysis for the convergence
of LPs and GPRs to their mean-field values on edge-independent random graphs.
Although our theoretical results apply to many problem settings, we focus on
the task of seed-expansion community detection over stochastic block models.
There, we find that the predictive power of LPs decreases significantly slower
than previously reported based on asymptotic findings. Given this result, we
propose a new GPR, termed Inverse PR (IPR), with LP weights that increase for
the initial few steps of the walks. Extensive experiments on both synthetic and
real, large-scale networks illustrate the superiority of IPR compared to other
GPRs for seeded community detection.
