Source-linked AI summary
Block Models and Personalized PageRank
Isabel Kloumann, Johan Ugander, Jon Kleinberg
TL;DR
Seed set expansion requires ranking nodes to recover a hidden community from a small seed subset, but standard random-walk scores lack an objective-based justification. The paper studies this task in a two-block stochastic block model and derives optimal landing-probability classifiers. Personalized PageRank emerges asymptotically as the optimal geometric discriminant for a model-specific parameter, while covariance-aware extensions substantially improve performance and compete with belief propagation.
Problem
Seed set expansion seeks to recover a hidden community from a small known seed set, while personalized PageRank and heat kernel lack a direct objective-based justification for combining walk probabilities.
Method
The paper evaluates landing-probability ranking in a two-block stochastic block model, deriving block centroids, optimal discriminants, and covariance-adjusted linear and quadratic classifiers.
Results
Personalized PageRank is asymptotically equivalent to the optimal geometric discriminant for a model-specific α, while covariance-aware methods greatly improve performance and compete with belief propagation.
Takeaways & Limitations
The stochastic block model provides a principled motivation for personalized PageRank and a basis for strengthening it with higher-moment information.
Takeaways & Limitations
The theoretical proof assumes a dense stochastic block model, and it is unclear whether the equivalence extends to sparse block models; practical use also requires learning model parameters.
Abstract
from arXiv · showhide
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 $α$ 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.
1 Introduction
Seed set expansion asks whether a small labeled subset can guide reliable recovery of its hidden community. This paper frames random-walk ranking methods through a two-block stochastic block model, deriving a principled connection between personalized PageRank and optimal landing-probability classification while proposing covariance-aware improvements.
- Seed set expansion: Seed set expansion ranks nodes outside a known subset to recover the remainder of a hidden, internally well-connected community.The problem applies to web-page discovery, social-group identification, and online group construction.
- Existing ranking methods: Personalized PageRank and heat kernel methods combine random-walk landing probabilities across walk lengths into node scores.Their rankings correspond geometrically to sweeps through landing-probability space using method-specific hyperplanes.
- Open motivation: Existing methods lacked a direct argument that their weighting schemes optimally combine landing probabilities for the seed-expansion objective.The paper identifies their coefficients as specific, apparently arbitrary combinations of features relevant to community membership.
- Model-based framework: The two-block stochastic block model supplies a graph-generation setting with a known correct hidden-community answer for evaluating landing-probability rankings.One block represents the labeled seed community and the other its complement.
- Main theoretical connection: The optimal hyperplane between block centroids is asymptotically equivalent to personalized PageRank for a PageRank parameter determined by block-model parameters.This establishes a formal bridge between personalized PageRank and stochastic-block-model classification.
- Advanced methods: Covariance-adjusted linear and quadratic scores incorporate landing-probability variances and covariances and significantly outperform personalized PageRank on the stochastic block model benchmark.The methods account for correlations between landing probabilities from different walk lengths.
2 Discriminant Functions for Stochastic Block Models
The paper models seed set expansion with stochastic block models and derives discriminant functions over random-walk landing probabilities. Under stated conditions, the optimal geometric classifier connects asymptotically to personalized PageRank, while covariance-aware rules provide a richer alternative.
- Stochastic block models: A stochastic block model partitions nodes into blocks with block-specific connection probabilities, including a two-block setting where the seed community is distinguished from its complement.The framework also extends to multiple blocks and binary classification between unions of blocks.
- Geometric and standard walk scores: Geometric discrimination ranks nodes by the inner product with the vector connecting in-class and out-class landing-probability centroids.Personalized PageRank and the heat kernel are finite linear discriminants with respective weight vectors wPPR(α) = (α, α^2, ..., α^K) and wHK(t).
- Landing-probability features: Each node is represented by its first K random-walk landing probabilities, which serve as features for ranking or classifying community membership.The k-step landing probability is the probability that a walk from a seed reaches the node after exactly k steps.
- PageRank connection: For two identical communities, the empirical geometric weight vector is asymptotically equivalent to personalized PageRank weights for a parameter determined by the block model.The equivalence is expressed through concentration of the scaled empirical weights around a theoretical vector Ψ.
- C-block extension: For arbitrary block models, the asymptotically optimal geometric weights can be derived from a C-dimensional matrix recurrence, with personalized PageRank emerging in special cases.The result does not require balanced block sizes or equal expected degrees, and applies to nontrivial substructure across blocks.
- Fisherian discriminants: Fisherian discriminants incorporate heterogeneous variances and covariances of landing probabilities, yielding covariance-adjusted linear rules that can differ substantially from geometric scoring.The practical parameter-learning discussion focuses on two-block affiliation models with known block sizes and consistent estimates of edge probabilities.
3 Computational Results
The experiments evaluate landing-probability classifiers on stochastic block models, comparing the proposed covariance-adjusted methods with personalized PageRank, heat kernel, and Belief Propagation. Covariance-adjusted approaches match or slightly exceed Belief Propagation near the resolution limit and substantially improve seed-set recall over ordinary personalized PageRank.
- Partition recovery: Covariance-adjusted methods recover correlated partitions up to Belief Propagation’s resolution limit and slightly outperform it just beyond that limit.The comparison uses Pearson correlation on a 128-node SBM with equal blocks and average degree 16.
- Partition recovery: Personalized PageRank and heat kernel perform poorly compared with covariance-adjusted methods for correlated partition recovery.
- Seed-set expansion: The quadratic discriminant substantially improves cumulative recall over ordinary personalized PageRank, identifying the first 64 nodes with high recall.The evaluation uses equal 64-node blocks and two choices of pin and pout.
- Seed-set expansion: Personalized PageRank and heat kernel achieve comparable recalls, while the single-covariance linear method has recall nearly identical to the fully quadratic method.Personalized PageRank is tested with both estimated and true PageRank parameters, and heat kernel uses t = 2.
- Benchmark: Belief Propagation is used as a benchmark for optimal performance, but it has greater computational complexity and does not operate in the landing-probability framework.The proposed classifiers and Belief Propagation are therefore compared despite using different computational frameworks.
4 Discussion
The paper motivates personalized PageRank through stochastic block models and extends the landing-probability framework with covariance-adjusted classifiers. These extensions outperform personalized PageRank and heat kernel on SBM seed-set recovery while opening several questions about broader models and distributions.
- Discussion: Personalized PageRank is the optimal geometric discriminant for classifying nodes in a hidden seed community under a stochastic block model.
- Discussion: Covariance-adjusted linear and quadratic classifiers extend the landing-probability approach beyond personalized PageRank and heat kernel.
- Discussion: The covariance-adjusted classifiers dramatically outperform personalized PageRank and heat kernel for recovering seed sets in stochastic block model graphs.
- Open questions: The connection motivates questions about alternative graph models, alternative random walks, and more explicit models of landing-probability distributions.The paper specifically raises whether heat kernel methods can emerge as optimal and whether joint distributions can be modeled beyond first two moments.
A.1 Proof of Lemma 1
The proof establishes concentration of random walk counts and landing probabilities for a two-block stochastic block model under equal community sizes and fixed positive connection probabilities. It uses degree concentration, recurrence relations, induction, and deterministic containment arguments.
- Assumptions: The lemma assumes equally sized communities, fixed block-model parameters, positive connection probabilities, and a designated seed block.
- Concentration: With probability at least 1 −δ for sufficiently large n, random walk landing probabilities concentrate around recurrence-based quantities for all relevant walk lengths.The argument first obtains degree bounds using multiplicative Chernoff bounds and a union bound.
- Walk quantities: The proof models seed-to-block walk counts and aggregate landing probabilities for walks ending in the seed block or its complement.
- Proof strategy: The proof handles dependencies among walk counts by analyzing recurrence solutions that correspond to expected counts in a graph with independently resampled edges.
- Inductive bounds: Degree concentration implies recurrence bounds on walk counts, which are propagated across lengths by induction and then transferred to aggregate sums and landing-probability ratios.The resulting bounds use multiplicative factors involving γ and γ2, with the proof becoming deterministic after the degree containment event.
- Conclusion: The final containment results hold with probability at least 1 −δ after choosing γ and γ2 so their powers remain within the target ϵ bounds.The displayed results include bounds for ˆAk, ˆBk, and their sum.
B Proofs for C–dimensional Case
The C-block proof reduces the landing-probability analysis to aggregate in-class and out-class quantities under degree-homogeneity conditions. This reduction yields a closed-form characterization showing asymptotic equivalence between the geometric discriminant weights and personalized PageRank.
- Generalization: The C-dimensional analysis connects stochastic block models, geometric classification in landing-probability space, and personalized PageRank.
- Aggregate reduction: Aggregate walk quantities over the in-class and out-class replace the individual walk counts for every block.
- Aggregate reduction: Under degree-homogeneity conditions, the proof formulates a 2 × 2 recurrence for aggregate quantities instead of diagonalizing the full C × C recurrence.
- Main result: The resulting closed-form solution shows that the geometric discriminant weight vector for the C-block problem is asymptotically equivalent to personalized PageRank.
B.1 Proof of Lemma 2
The proof establishes that block-level random-walk landing probabilities concentrate around recurrence-defined quantities with high probability. It handles dependencies from revisiting edges through degree containments and an induction over walk length.
- Concentration setup: Lemma 2 bounds block-level landing probabilities using solutions to a C-dimensional linear recurrence.The recurrence tracks expected block-level walk quantities, while the random graph quantities are shown to remain within multiplicative bounds.
- Concentration setup: Walk counts for lengths greater than one are dependent because walks may revisit edges.This prevents directly replacing random walk counts with ratios of their expectations.
- Degree containment: With probability at least 1 −δ, degree counts remain within multiplicative factors of 1 ±γ for sufficiently large n.Chernoff bounds control individual degree events, and a union bound controls all such events simultaneously.
- Inductive step: An induction propagates the degree containment to walk-count bounds through length K.The proof assumes bounds at length k and derives corresponding bounds at length k+1.
- Conclusion: The resulting landing-probability containment holds with probability at least 1 −δ.The final multiplicative bounds follow by choosing γ and γ2 so their accumulated error satisfies the target ϵ.
B.2 Proof of Lemma 3
The proof of Lemma 3 shows by induction that a block-aggregated recurrence reproduces sums of node-level recurrence solutions. This connects the C-dimensional walk analysis to aggregate quantities for two partitions.
- Recurrence formulation: Lemma 3 considers a matrix recurrence with two node partitions and specified initial conditions.The quantities wk and zk aggregate recurrence solutions over the two partitions.
- Inductive proof: The base case follows by expanding the matrix multiplication and applying the initial conditions and definitions of the aggregate quantities.The same calculation verifies the corresponding base case for the second aggregate.
- Inductive proof: The induction assumes the aggregate identities at length k and proves them at length k+1.The update uses the recurrence structure and the definitions of the partition-level coefficients.
- Conclusion: The induction concludes that the aggregate recurrence solutions equal the corresponding sums over node-level solutions.This completes the proof for both partition aggregates.
B.3 Proof of Proposition 2
The proof of Proposition 2 characterizes the geometric discriminant weights through recurrence solutions and establishes their asymptotic relation to personalized PageRank. Under homogeneous block conditions, the recurrence reduces from C dimensions to two.
- Proposition setup: For fixed walk lengths, the geometric discriminant vector concentrates around a deterministic vector Ψ in ℓ1 norm with probability at least 1 −δ.The bound applies as n becomes sufficiently large.
- Recurrence characterization: The deterministic weights Ψ are defined from solutions to a C-dimensional linear homogeneous recurrence.These solutions describe block-level landing-probability behavior.
- Recurrence reduction: If expected degrees are homogeneous within and between the two partitions, Ψ is determined by a 2-dimensional recurrence.This condition is weaker than requiring a two-dimensional stochastic block model because each partition may contain multiple blocks.
- Closed form: The proof obtains the two-dimensional closed form by diagonalizing the reduced recurrence matrix.Its eigenvalues and eigenvectors yield the recurrence solution used to compute Ψ.
- PageRank equivalence: When blocks are identically distributed, the derived weights are precisely personalized PageRank weights for a particular α.The parameter is α = (pin −pout)/(Cpout + (pin −pout)).
C Details of Belief Propagation
This section describes belief propagation for stochastic block models, including its message-passing formulation, sparse approximation, initialization, and computational cost. BP provides a stronger global benchmark than the paper’s independent landing-probability classifiers.
- Motivation: Maximum-likelihood block assignment is NP-hard in general, motivating practical inference methods such as BP.BP is reported to outperform EM in practice and reach the known detectability threshold.
- Comparison: BP performs global joint inference, whereas Lin-SBMRank and Quad-SBMRank classify nodes independently from random-walk landing probabilities.This makes BP a more computationally demanding benchmark than the paper’s discriminative rules.
- BP formulation: Belief propagation infers latent block labels by iterating conditional marginal messages on the stochastic block model.At convergence, node beliefs can be used for classification by selecting the highest-belief class.
- Sparse BP: For sparse graphs with bounded maximum degree d, sparse BP reduces each iteration to O(d^2N) computation instead of O(N^3).The approximation retains only neighbor-dependent message equations after applying three heuristic simplifications.
- Initialization: The paper initializes beliefs using known class proportions and initializes balanced-class messages uniformly at random.Iterations stop at a numerical tolerance or after a maximum iteration count.
D Additional Computational Results and Discussion
Additional results evaluate SBM partition recovery across parameter settings and show that normalized linear classification performs strongly, while fixed mismatched parameters can substantially reduce classification quality.
- Numerical considerations: For large step counts, landing probabilities approach the stationary distribution, making late covariance-matrix columns strongly collinear.The practical analysis therefore uses landing probabilities from the first K = 6 steps.
- Performance results: Figure S1 evaluates Pearson correlation r between inferred and true partitions across pin and pout settings for PageRank and SBMRank methods.The heatmaps compare fixed-parameter PageRank, true-parameter PageRank, and normalized linear SBMRank; quadratic SBMRank is similar to the linear method.
- Performance results: Normalized linear classification performs significantly better across the space of stochastic block model parameters than the compared PageRank configurations.The corresponding quadratic classification heatmap is visually similar and slightly higher-performing than the normalized linear classification.
- Parameter sensitivity: Fixed discriminant parameters that are far from the true SBM values can make classification quite poor.The fixed PageRank configuration in Figure S1A illustrates this sensitivity to parameter choice.
- Parameter estimation: The methods require knowledge or estimation of the underlying SBM parameters, for which the paper employs consistent estimators in the affiliation model.The estimators target pin and pout from an observed adjacency matrix.