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.
%0 Journal Article
%1 Kloumann2017Block
%A Kloumann, Isabel M.
%A Ugander, Johan
%A Kleinberg, Jon
%D 2017
%J Proceedings of the National Academy of Sciences
%K classification-models, missing-information, pagerank influence communities
%N 1
%P 33--38
%R 10.1073/pnas.1611275114
%T Block models and personalized PageRank
%U http://dx.doi.org/10.1073/pnas.1611275114
%V 114
%X 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.
@article{Kloumann2017Block,
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.}},
added-at = {2019-06-10T14:53:09.000+0200},
archiveprefix = {arXiv},
author = {Kloumann, Isabel M. and Ugander, Johan and Kleinberg, Jon},
biburl = {https://www.bibsonomy.org/bibtex/2bc997c7e3a237713868f671b23a0b8ec/nonancourt},
citeulike-article-id = {14095858},
citeulike-linkout-0 = {http://dx.doi.org/10.1073/pnas.1611275114},
citeulike-linkout-1 = {http://arxiv.org/abs/1607.03483},
citeulike-linkout-2 = {http://arxiv.org/pdf/1607.03483},
day = 3,
doi = {10.1073/pnas.1611275114},
eprint = {1607.03483},
interhash = {6413f6a2e1f977ea3da08fa0e63aff81},
intrahash = {bc997c7e3a237713868f671b23a0b8ec},
issn = {1091-6490},
journal = {Proceedings of the National Academy of Sciences},
keywords = {classification-models, missing-information, pagerank influence communities},
month = jan,
number = 1,
pages = {33--38},
posted-at = {2016-07-15 12:00:24},
priority = {2},
timestamp = {2019-08-01T16:14:15.000+0200},
title = {{Block models and personalized PageRank}},
url = {http://dx.doi.org/10.1073/pnas.1611275114},
volume = 114,
year = 2017
}