Block Models and Personalized PageRank

Abstract

Methods for ranking the importance of nodes in a network have a rich history in machine learning and across domains that analyze structured data. Recent work has evaluated these methods though the seed set expansion problem: given a subset $S$ of nodes from a community of interest in an underlying graph, can we reliably identify the rest of the community? We start from the observation that the most widely used techniques for this problem, personalized PageRank and heat kernel methods, operate in the space of landing probabilities of a random walk rooted at the seed set, ranking nodes according to weighted sums of landing probabilities of different length walks. Both schemes, however, lack an a priori relationship to the seed set objective. In this work we develop a principled framework for evaluating ranking methods by studying seed set expansion applied to the stochastic block model. We derive the optimal gradient for separating the landing probabilities of two classes in a stochastic block model, and find, surprisingly, that under reasonable assumptions the gradient is asymptotically equivalent to personalized PageRank for a specific choice of the PageRank parameter $\alpha$ that depends on the block model parameters. This connection provides a novel formal motivation for the success of personalized PageRank in seed set expansion and node ranking generally. We use this connection to propose more advanced techniques incorporating higher moments of landing probabilities; our advanced methods exhibit greatly improved performance despite being simple linear classification rules, and are even competitive with belief propagation.

30 pages, 3 figures

References in corpus (6)

• Resolution limit in community detection
• Identifiability of parameters in latent structure models with many observed variables
• Evaluating Local Community Methods in Networks
• Scalable detection of statistically significant communities and hierarchies, using message-passing for modularity
• Belief Optimization for Binary Networks: A Stable Alternative to Loopy Belief Propagation
• Spectral Clustering of Graphs with the Bethe Hessian

Cited by in corpus (17)

• Random walks and diffusion on networks
• Random Walks on Simplicial Complexes and the normalized Hodge 1-Laplacian
• Element-centric clustering comparison unifies overlaps and hierarchy
• Multiscale mixing patterns in networks
• Adaptive Universal Generalized PageRank Graph Neural Network
• The impossibility of low rank representations for triangle-rich complex networks
• A Framework for the Construction of Generative Models for Mesoscale Structure in Multilayer Networks
• Testing for Global Network Structure Using Small Subgraph Statistics
• Adaptive Diffusions for Scalable Learning over Graphs
• Optimizing Generalized PageRank Methods for Seed-Expansion Community Detection
• Mean Field Analysis of Personalized PageRank with Implications for Local Graph Clustering
• Higher-order Network Analysis Takes Off, Fueled by Classical Ideas and New Data
• Targeted sampling from massive block model graphs with personalized PageRank
• Stochastic Block Models are a Discrete Surface Tension
• PageRank centrality and algorithms for weighted, directed networks with applications to World Input-Output Tables
• Centrality with Diversity
• Efficient and High-Quality Seeded Graph Matching: Employing High Order Structural Information