Optimizing Generalized PageRank Methods for Seed-Expansion Community Detection
This work addresses the optimization of GPR weights for community detection, offering incremental improvements in performance for graph-based learning applications.
The authors tackled the problem of optimizing Generalized PageRank (GPR) methods for seed-expansion community detection by analyzing the convergence of landing probabilities on random graphs, finding that predictive power decreases slower than previously thought. They proposed a new GPR called Inverse PR (IPR) with increasing weights for initial walk steps, which outperformed other GPRs in experiments on synthetic and large-scale real networks.
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.