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.

该研究旨在通过发现 PageRank 参数与种子集扩展问题之间的联系，提出了一种评估排名方法的原则框架，并提出了一种简单的线性分类规则用于更高阶的落点概率的种子扩展问题。