Optimizing Generalized PageRank Methods for Seed-Expansion Community Detection

Abstract

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.

NeurIPS 2019

References in corpus (9)

• Community detection in graphs
• Semi-Supervised Classification with Graph Convolutional Networks
• Spectral Networks and Locally Connected Networks on Graphs
• Stochastic blockmodels and community structure in networks
• Scalable detection of statistically significant communities and hierarchies, using message-passing for modularity
• Block Models and Personalized PageRank
• Adaptive Diffusions for Scalable Learning over Graphs
• Mean Field Analysis of Personalized PageRank with Implications for Local Graph Clustering
• Quadratic Decomposable Submodular Function Minimization: Theory and Practice (Computation and Analysis of PageRank over Hypergraphs)

Cited by in corpus (8)

• Distance Encoding: Design Provably More Powerful Neural Networks for Graph Representation Learning
• Graph Information Bottleneck
• Adaptive Universal Generalized PageRank Graph Neural Network
• Scalable Graph Neural Networks via Bidirectional Propagation
• SUREL+: Moving from Walks to Sets for Scalable Subgraph-based Graph Representation Learning
• Semi-supervised Graph Neural Networks for Pileup Noise Removal
• Node Feature Extraction by Self-Supervised Multi-scale Neighborhood Prediction
• Scalable Deep Graph Clustering with Random-walk based Self-supervised Learning