# Optimizing Generalized PageRank Methods for Seed-Expansion Community Detection

arXiv: https://arxiv.org/abs/1905.10881 · HTML: https://mlsanity.com/paper/1905.10881/

## Key facts

- Cited by 35 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 26 May 2019.

## Built on by (most cited first, 30 of 35)

- [Sign and Basis Invariant Networks for Spectral Graph Representation Learning](https://mlsanity.com/paper/2202.13013/) (2022)
- [Node Feature Extraction by Self-Supervised Multi-scale Neighborhood Prediction](https://mlsanity.com/paper/2111.00064/) (2021)
- [Breaking the Limit of Graph Neural Networks by Improving the Assortativity of Graphs with Local Mixing Patterns](https://mlsanity.com/paper/2106.06586/) (2021)
- [Graph Convolution for Semi-Supervised Classification: Improved Linear Separability and Out-of-Distribution Generalization](https://mlsanity.com/paper/2102.06966/) (2021)
- [Certified Graph Unlearning](https://mlsanity.com/paper/2206.09140/) (2022)
- [GRAND+: Scalable Graph Random Neural Networks](https://mlsanity.com/paper/2203.06389/) (2022)
- [Effects of Graph Convolutions in Multi-layer Networks](https://mlsanity.com/paper/2204.09297/) (2022)
- [How Universal Polynomial Bases Enhance Spectral Graph Neural Networks: Heterophily, Over-smoothing, and Over-squashing](https://mlsanity.com/paper/2405.12474/) (2024)
- [HL-Net: Heterophily Learning Network for Scene Graph Generation](https://mlsanity.com/paper/2205.01316/) (2022)
- [Understanding Non-linearity in Graph Neural Networks from the Bayesian-Inference Perspective](https://mlsanity.com/paper/2207.11311/) (2022)
- [Confidence-Based Feature Imputation for Graphs with Partially Known Features](https://mlsanity.com/paper/2305.16618/) (2023)
- [Scalable and Certifiable Graph Unlearning: Overcoming the Approximation Error Barrier](https://mlsanity.com/paper/2408.09212/) (2024)
- [What Can We Learn from State Space Models for Machine Learning on Graphs?](https://mlsanity.com/paper/2406.05815/) (2024)
- [Federated Learning over Coupled Graphs](https://mlsanity.com/paper/2301.11099/) (2023)
- [Joint Graph Rewiring and Feature Denoising via Spectral Resonance](https://mlsanity.com/paper/2408.07191/) (2024)
- [SUREL+: Moving from Walks to Sets for Scalable Subgraph-based Graph Representation Learning](https://mlsanity.com/paper/2303.03379/) (2023)
- [MGC: A Complex-Valued Graph Convolutional Network for Directed Graphs](https://mlsanity.com/paper/2110.07570/) (2021)
- [PINA: Leveraging Side Information in eXtreme Multi-label Classification via Predicted Instance Neighborhood Aggregation](https://mlsanity.com/paper/2305.12349/) (2023)
- [A Comprehensive Benchmark on Spectral GNNs: The Impact on Efficiency, Memory, and Effectiveness](https://mlsanity.com/paper/2406.09675/) (2024)
- [Spectro-Riemannian Graph Neural Networks](https://mlsanity.com/paper/2502.00401/) (2025)
- [Differentially Private Graph Diffusion with Applications in Personalized PageRanks](https://mlsanity.com/paper/2407.00077/) (2024)
- [Graph Convolutional Network with Connectivity Uncertainty for EEG-based Emotion Recognition](https://mlsanity.com/paper/2310.14165/) (2023)
- [Foundations and Frontiers of Graph Learning Theory](https://mlsanity.com/paper/2407.03125/) (2024)
- [Layer-wise Adaptive Graph Convolution Networks Using Generalized Pagerank](https://mlsanity.com/paper/2108.10636/) (2021)
- [Scalable Deep Graph Clustering with Random-walk based Self-supervised Learning](https://mlsanity.com/paper/2112.15530/) (2021)
- [Towards Understanding Graph Neural Networks: An Algorithm Unrolling Perspective](https://mlsanity.com/paper/2206.04471/) (2022)
- [Semi-supervised Community Detection via Structural Similarity Metrics](https://mlsanity.com/paper/2306.01089/) (2023)
- [Faster Local Solvers for Graph Diffusion Equations](https://mlsanity.com/paper/2410.21634/) (2024)
- [Positional Encoding meets Persistent Homology on Graphs](https://mlsanity.com/paper/2506.05814/) (2025)
- [An Effective Universal Polynomial Basis for Spectral Graph Neural Networks](https://mlsanity.com/paper/2311.18177/) (2023)

## Abstract (arXiv)

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.