# Targeted sampling from massive block model graphs with personalized
PageRank††thanks: This research is supported in part by NSF Grants DMS-1612456
and DMS-1916378 and ARO Grant W911NF-15-1-0423.

Fan Chen  Department of Statistics  Yini Zhang  School of Journalism and Mass
Communication  Karl Rohe  Department of Statistics

###### Abstract

This paper provides statistical theory and intuition for Personalized PageRank
(PPR), a popular technique that samples a small community from a massive
network. We study a setting where the entire network is expensive to
thoroughly obtain or maintain, but we can start from a seed node of interest
and “crawl” the network to find other nodes through their connections. By
crawling the graph in a designed way, the PPR vector can be approximated
without querying the entire massive graph, making it an alternative to
snowball sampling. Using the degree-corrected stochastic block model, we study
whether the PPR vector can select nodes that belong to the same block as the
seed node. We provide a simple and interpretable form for the PPR vector,
highlighting its biases towards high degree nodes outside of the target block.
We examine a simple adjustment based on node degrees and establish consistency
results for PPR clustering that allows for directed graphs. These results are
enabled by recent technical advances showing the element-wise convergence of
eigenvectors. We illustrate the method with the massive Twitter friendship
graph, which we crawl using the Twitter API. We find that (i) the adjusted and
unadjusted PPR techniques are complementary approaches, where the adjustment
makes the results particularly localized around the seed node and (ii) the
bias adjustment greatly benefits from degree regularization.

###### Abstract

This document provides several supplementary materials to “Targeted sampling
from massive block model graphs with personalized PageRank”. Section S1
contains a proof for the entrywise error control (Theorem 2). Section S2 gives
additional information about some model parameters, including B,
$\mathcal{P}$, $\alpha$, and $N$. Section S3 extends the results in Kloumann
et al. (2017) to the DC-SBM from a linear discriminant analysis perspective.
Section S4 supplies three targeted Twitter samples about the seed @NBCPolitics
described in the paper. The PPR clustering is implemented in R and all source
codes are available at author’s GitHub (https://github.com/RoheLab/aPPR).

Keywords Community detection; Degree-corrected stochastic block model; Local
clustering; Network sampling; Personalized PageRank

##  1 Introduction

Much of the literature on graph sampling has treated the entire graph, or all
of the people in it, as the target population. However, in many settings, the
target population is a small community in the massive graph. For example, a
key difficulty in studying social media is to gather data that is sufficiently
relevant for the scientific objective. A motivating example for this paper is
to sample the Twitter friendship graph for accounts that report and discuss
current political events.111See our website http://murmuration.wisc.edu which
does this. This corresponds to sampling and identifying multiple different
communities, each a potentially small part of the massive network. In such an
application, the graph is useful for two primary reasons. First, via link
tracing, we can find potential members of the target population. Second, the
graph connections are informative for identifying community membership.
Throughout, we presume that the sampling is initiated around a “seed node”
that belongs to the target community of interest.

Personalized PageRank (PPR) can be thought of as an alternative to snowball
sampling, a popular technique for gathering individuals close to the seed
node. For some $d\geq 0$, snowball sampling gathers all individuals who are
$d$ friends away from the seed. This process has two competing flaws for our
application which are addressed by PPR. First, snowball sampling fails to
account for the density of common friendships. For example, perhaps $i$ and
$j$ are both one friend removed from the seed, but $i$ has 10 friends in
common with the seed, while $j$ only has 1 friend in common. It seems natural
to suppose that $i$ is closer than $j$ to the seed. Hence, the metric for
snowball sampling can be misleading. Second, the snowball sample size grows
very quickly with $d$. For example, under the “six degrees of separation”
phenomenon (Watts and Strogatz, 1998; Newman et al., 2006), snowballing
gathers the entire graph if $d\geq 6$.

PPR gives a sample that is more localized around the seed node. The PPR vector
is defined as the stationary distribution of what we call a personalized
random walk (Page et al., 1998). At each step of the personalized random walk,
the random walker returns to the seed node with probability $\alpha$, called
the teleportation constant, and with probability $1-\alpha$, the random walker
goes to an adjacent node that is chosen uniformly at random. Consider the
stationary distribution of this process as giving the inclusion probability
for a sample of size 1. This is the PPR vector. PPR naturally leads to a
clustering algorithm, where the cluster is made up of the nodes with a large
inclusion probability. To quickly approximate the PPR vector, Berkhin (2006)
proposed an algorithm that only examines nodes with large inclusion
probabilities (i.e. nodes near the seed). As such, PPR is particularly useful
for its computational efficiency – the running time and the amount of data it
requires is nearly linear in the size of the output cluster, which is
typically much smaller than that of the entire graph. Due to the local nature
of the algorithm, it can be used to study large graphs such as Twitter where
the entire graph is not available, but where one can query to find the
connections to any small set of nodes.

One way to conduct local clustering is by exploring and ranking the nearby
nodes of a seed node. (Andersen and Lang, 2006; Andersen and Peres, 2009;
Alamgir and von Luxburg, 2010; Gharan and Trevisan, 2012). Spielman and Teng
(2004) pioneered local clustering by defining nearness as the landing
probability of a random walk starting from the seed node. Their algorithm’s
guarantee was improved in follow-up work by Andersen et al. (2006) which
proposed using an approximate PPR vector. Local algorithms can be applied
recursively to solving more complicated problems such as graph partitions
(k-way partitions) (Spielman and Teng, 1996; Karypis and Kumar, 1998), and has
many fruitful applications (Jeh and Widom, 2003; Macropol et al., 2009; Liao
et al., 2009; Gupta et al., 2013; Gleich, 2015), particularly when it comes to
sampling and studying massive graphs.

Along with the widespread use of PPR, there has been recent work to study its
statistical estimation properties under a statistical model with latent
community structure. Beyond the scope of local clustering, Kloumann et al.
(2017) showed that the PPR vector is asymptotically equivalent to optimal
linear discriminant analysis under the stochastic block model (SBM) (Holland
et al., 1983), assuming a symmetry condition on the block structure. We add to
this statistical understanding of PPR by providing a simple and more general
representation for PPR vectors that allows for different block sizes, more
than two blocks, degree heterogeneity, and directed edges. In order to
understand the effects of heterogeneous node degrees, this paper uses the
degree-corrected stochastic block model (DC-SBM) (Karrer and Newman, 2011) and
examines when the PPR clustering recovers nodes within the same block as the
seed node (local cluster). Breaking the symmetry that is imposed by Kloumann
et al. (2017) reveals additional insight. In particular, given a seed node in
the first block, we show that PPR is likely to contain high degree nodes
outside of that block. We study an adjustment that was previously proposed in
Andersen et al. (2006). We show how this adjustment can correct for the bias.
We illustrate these ideas with examples from the Twitter friendship graph.

###  1.1 An illustrative example in social media

Local clustering using PPR is particularly well suited to studying current
political events on Twitter because (i) the accounts that discuss politics or
current events are a small part of the entire Twitter graph, (ii) it is
reasonable to believe that the accounts in our target population are well
connected to one another in the Twitter friendship graph, and (iii) while the
entire Twitter graph is not publicly available, the way that PPR (Algorithm 1
and 3) queries the graph matches the Twitter API protocol which is the primary
mode of access for researchers.

While we do not suppose that the Twitter friendship graph is sampled from a
DC-SBM, Twitter does have all of the heterogeneities that our results identify
as important. The Twitter friendship graph is composed of users who can freely
follow others but will not necessarily be followed back, or friended. Such
asymmetry between following and friending forms a directed graph where
follower count indicates status – some popular/high-status nodes command
millions of followers while the majority of nodes are followed by far fewer.

Table 1:  Top 15 handles by PPR clustering. Column names represent seed nodes,
and the sampled nodes are ranked by PPR values, with teleportation constant
$\alpha=0.15$ uniformly.

@CNN @BreitbartNews @dailykos 1 CNN Breaking News Alex Marlow Hillary Clinton
2 CNN International AndrewBreitbart Stephen Colbert 3 Wolf Blitzer Big
Hollywood Rachel Maddow MSNBC 4 Anderson Cooper Big Government Jake Tapper 5
Christiane Amanpour James O’Keefe Joy Reid 6 Pope Francis Sean Hannity Chris
Hayes 7 Dr. Sanjay Gupta Raheem Emma Gonzlez 8 CNNMoney Joel B. Pollak Markos
Moulitsas 9 Jake Tapper Ann Coulter Maggie Haberman 10 Brian Stelter Allum
Bokhari Sarah Silverman 11 CNN Newsroom Ben Kew Lin-Manuel Miranda 12 Dana
Bash Brandon Darby Elizabeth Warren 13 CNN Politics Noah Dulis Jon Favreau 14
BBC Breaking News Michelle Malkin Michelle Obama 15 Brooke Baldwin Nate Church
Bill Clinton • Through the PPR vector, the top 15 handles returned to each of
the three seed nodes fit well with the characteristics of the seed nodes. They
are popular/high-status handles either directly related to the seed nodes or
align with their political leanings. This shows the effectiveness of
clustering via the PPR vector. It also shows the PPR vector’s preference for
highly connected nodes.

Table 2:  Top 15 handles by adjusted PPR (with regularization) sampling.
Column names represent seed nodes, and the sampled nodes are ranked by
adjusted PPR values, with teleportation constant $\alpha=0.15$ uniformly.

@CNN @BreitbartNews @dailykos 1 PowerZ Robert Two Thanks 2 Elissa Weldon Lee
Peace Catherine Daligga 3 Tess Eastment Wynn Marlow exmearden 4 Chris_Dawson
Logan Churchwell Faith Gardner 5 carol kinstle Peter Schweizer Andrew Thornton
6 erinmclaughlin Breitbart Sports UnreasonableFridays 7 Taylor Ward Jon
Fleischman DKos Top Comments 8 Jennifer Z. Deaton Nate Church 2016 relitigator
9 Pam Benson Daniel Nussbaum Daily Kos 10 amy entelis Noah Dulis Walter
Einenkel 11 Grace Bohnhoff Jon David Kahn Candelaria Vargas 12 kate lazarus
Breitbart California Mara Schechter 13 Newstron Ken Klukowski Emi Feldman 14
Becky Brittain pam key The Soulful Negress 15 CNN Ballot Bowl Auntie Hollywood
Kim Soffen • After adjustment, PPR returns a more localized cluster. Instead
of the highly visible public faces of the three seed organizations, the
individuals in this table serve a central role to the internal organization
(e.g. editors and writers). Depending on the application, one might prefer the
results in Table 1 or Table 2.

The theoretical results in this paper suggest that such degree heterogeneities
will make the PPR vector biased for detecting block memberships (Theorem 1).
We propose a way to adjust for this bias (Algorithm 2) and show that it is a
consistent estimator (Corollary 1). Not surprisingly, this section
demonstrates that PPR with and without the bias adjustment give fundamentally
different results on the Twitter graph. However, depending on the application,
the biases in the PPR vector might be advantageous. In this way, PPR with and
without the bias adjustment are complementary, not competing, approaches.

To illustrate, Table 1 displays the top 15 handles ranked by the PPR vector
(without adjustment) for three different seed nodes: @CNN, @BreitbartNews, and
@dailykos, the Twitter accounts of three different types of media outlets that
exhibit distinct political leanings (legacy broadcast news, online right-wing
and online left-wing). For @CNN, all top 15 handles ranked by the PPR vector
are its subsidiary accounts and its celebrity reporters and anchors (like Wolf
Blitzer and Anderson Cooper), except for one account, Pope Francis, who enjoys
an extremely larger following. The top 15 handles for @BreitbartNews are a
mixed bag of influential conservatives (like Sean Hannity and Ann Coulter) and
Breitbart’s editors/writers. However, the top 15 handles returned to @dailykos
by the PPR vector are all famous liberal personalities not directly affiliated
with Daily Kos, but one, its founder Markos Moulitsas. Those people range from
democratic politicians to liberal media personalities and journalists, such as
Hillary Clinton, Stephen Colbert, and Rachel Maddow. All the handles align
with the characteristics of their respective media outlets, attesting to the
clustering effectiveness. However, it is worth noting that the top handles
ranked by the PPR vector tend to be popular handles with millions of
followers. This shows that the PPR vector’s preference for high in-degree
nodes.

In contrast, for each of the three seeds, adjusted PPR finds accounts that are
more central to the internal functioning of these organizations. Table 2 lists
those accounts. The bias adjustment also greatly benefits from a degree
regularization (Qin and Rohe, 2013). For @CNN, those handles include primarily
its own staff/producers/journalists (like Elissa Weldon, Chris_Dawson, and
Grace Bohnhoff), a freelance journalist (Tess Eastment). The pattern is
similar for @BreitbartNews and @dailykos, their top 15 handles including their
own journalists, editors as well as related writers/campaigners/activists. The
general pattern is that the adjustment returns editors, journalists and staff
working within each media outlet. As such, the adjustment is useful for
identifying a more localized cluster.

###  1.2 Main contributions

The main contributions of the paper are (a) a simple and interpretable form
for the PPR vector and (b) a statistical guarantee for clustering with the
adjusted PPR vector.

  1. (a)

This paper reveals a simple two-stage form of the PPR vector under the
population (expectation) DC-SBM. Consider the $v$-th element of the PPR vector
as the probability of sampling node $v$ in a sample of size 1 from the
stationary distribution of the personalized random walk. This inclusion
probability is akin to stratified sampling:

> The inclusion probability for node $v$ is the product of two separate
> probabilities. First, the probability that the personalized random walk
> samples any node in $v$’s block. Second, the probability that the
> personalized random walk selects node $v$, conditional on sampling that
> block.

Both of these probabilities have simple expressions. If there are $K$ blocks
in the graph, then the block-wise probability comes from the PPR vector of a
graph with $K$ vertices, with edge weights specified by the “block connection
matrix” in the DC-SBM. The second probability is proportional to the degree of
node $v$. In addition to the population results, Theorem 2 demonstrates that
when the graph is random, the PPR vector concentrates around its population
(expectation) under certain conditions.

  2. (b)

This paper identifies two sources of bias of using a PPR vector for local
clustering under the DC-SBM – the ancillary effects of heterogeneous node
degrees and block degrees. With this finding, the paper examines a simple bias
adjustment that remedies the two biases simultaneously and suggests conditions
when the adjusted PPR can be used to return the correct local cluster. In
other words,

> PPR clustering with the adjustment achieves the precise identification of
> the local cluster, provided the graph is sufficiently dense.

These results establish statistical performance (consistency) of PPR
clustering under the DC-SBM, in the sparse regime where the minimum expected
degree grows logarithmically with the number of nodes in the network. Our
results provide an element-wise perturbation bound for PPR vectors, that
allows the number of clusters to grow with the size of graphs, and generalize
to a directed graph setting as PageRank does.

The rest of the paper proceeds as follows. Section 2 formally introduces the
PPR method and some of the known results. Section 2 also introduces the
degree-corrected stochastic block model. Section 3 gives a population analysis
of the PPR clustering under directed block model graphs. Section 4 provides
concentration results for the PPR vector when the graph is random and provides
a statistical guarantee on the PPR local clustering method. Section 5 presents
several numerical results showing the effectiveness of the PPR clustering.
Section 6 illustrates the PPR clustering through the massive Twitter
friendship graph and demonstrates the benefits of a smoothing step in the PPR
adjustment.

##  2 Preliminaries

Throughout this paper, let $G=(V,E)$ denotes an unweighted and connected
graph, where $E$ is the edge set and $V$ is the set of vertices indexed by
$1,...,N$. When $G$ is an undirected and unweighted graph, encode $E$ into a
binary adjacency matrix $A\in\\{0,1\\}^{N\times N}$ with $A_{uv}=A_{vu}=1$ if
and only if edge $(u,v)$ appears in $E$. Define a diagonal matrix
$D=\mathop{\mathrm{diag}}\left(d_{1},...,d_{N}\right)$ and the graph
transition matrix $P$ as follows:

$\displaystyle d_{u}=\sum_{v\in V}A_{uv}$ and $\displaystyle P=D^{-1}A.$

When $G$ is a directed graph, the adjacency matrix $A\in\\{0,1\\}^{N\times N}$
accordingly becomes asymmetric with $A_{uv}=1$ if and only if edge $(u,v)\in
E$, and the graph transition matrix is defined as

$P=[D^{\text{out}}]^{-1}A,$

where
$D^{\text{out}}=\mathop{\mathrm{diag}}\left(d^{\text{out}}_{1},...,d^{\text{out}}_{N}\right)$
and $d^{\text{out}}_{u}=\sum_{v\in V}A_{uv}$ is the number of edges leaving
from node $u$. In addition, define
$D^{\text{in}}=\mathop{\mathrm{diag}}\left(d^{\text{in}}_{1},...,d^{\text{in}}_{N}\right)$
where $d^{\text{in}}_{v}=\sum_{u\in V}A_{uv}$ is the number of edges pointing
to node $v$.

###  2.1 Personalized PageRank and the local clustering algorithm

The personalized PageRank (PPR) is an extension of Google’s PageRank (Brin and
Page, 1998; Haveliwala, 2003). To illustrate, consider a personalized random
walk (or originally called “surfing”) on the graph $G=(V,E)$ with a seed node
$v_{0}\in V$. At each step, the random walker either restarts from the seed
node $v_{0}$ with probability $\alpha$ (called the teleportation constant) or
continues the random walk from the current node to a neighbor uniformly at
random. The personalized PageRank vector $p\in[0,1]^{N}$ is the stationary
distribution of this process, thus the solution to the equation

$p^{\top}=\alpha\pi^{\top}+(1-\alpha)p^{\top}P,$ (1)

where $P$ is the graph transition matrix, and $\pi$ is the elementary unit
vector in the direction of seed node $v_{0}$. Here $p$ is a column vector
normalized by a positive scalar such that its elements sum to 1, and without
loss of generality, we set $v_{0}=1$ and thus $\pi=(1,0,...,0)^{\top}$.

In general, the preference vector $\pi$ does not have to be an elementary unit
vector, but any probability distribution on $V$. For example, when
$\pi=(1/N,...,1/N)^{\top}$, PPR is equivalent to ordinary PageRank. Moreover,
the PPR vector is a linear function of the preference vector. That is, let
$p(\pi_{1})$ and $p(\pi_{2})$ be two PPR vectors corresponding to two
preference vectors $\pi_{1}$ and $\pi_{2}$ respectively. Then, for a new
preference vector that is a convex combination of $\pi_{i}$, the resulting PPR
vector is constructive of $p(\pi_{i})$,

$p(w_{1}\pi_{1}+w_{2}\pi_{2})=w_{1}p(\pi_{1})+w_{2}p(\pi_{2}),$

where $w_{i}\geq 0$ and $w_{1}+w_{2}=1$. Define $\Pi$ to be an $N\times N$
matrix with repeating rows $\pi^{\top}$, and let $Q=\alpha\Pi+(1-\alpha)P$,
then $Q$ is the Markov transition matrix for the stochastic process and
Equation (1) becomes $p^{\top}=p^{\top}Q$. Below are some useful properties of
the PageRank vector (also see Haveliwala (2003); Jeh and Widom (2003) and
Appendix A).

######  Proposition 1.

For any fixed $\alpha\in(0,1]$, the PPR vector $p$ is

  1. cmrmn(a)

the left leading eigenvector of $Q$, associated with the simple eigenvalue 1;
and

  2. cmrmn(b)

the infinite sum of landing probability
$\\{\left(P^{s}\right)^{\top}\pi\\}_{s=0}^{\infty}$ with weights
$\phi=\\{\alpha(1-\alpha)^{s}\\}_{s=0}^{\infty}$,

$p^{\top}=\alpha\sum_{s=0}^{\infty}(1-\alpha)^{s}\pi^{\top}P^{s}.$ (2)

Berkhin (2006) gives an iterative algorithm based on Proposition 1 to
approximate the PPR vector (that scales to large graphs); each update requires
only neighborhood information of one visited vertex. A few lines of linear
algebra show that the PPR vector is equivalent to the solution to the linear
system

$p^{\top}=\alpha^{\prime}\pi^{\top}+(1-\alpha^{\prime})p^{\top}W,$

where $W=(I+P)/2$ is the lazy graph transition matrix and
$\alpha^{\prime}=\alpha/(2-\alpha)$. Using this fact, Algorithm 1 approximates
the PPR vector in running time of order
$\mathcal{O}\left(\frac{1}{\epsilon\alpha}\right)$, by reaching at most
$\frac{2}{\epsilon(1-\alpha)}$ vertices. The following proposition gives a
guarantee on the approximation error for this algorithm in terms of the
tolerance parameter and the degrees of visited nodes.

######  Proposition 2 (Entrywise approximation error (Andersen et al., 2006)).

Let $p$ be a PPR vector, and let $p^{\epsilon}\in{[0,1]}^{N}$ be an
approximate PPR vector computed by Algorithm 1 with a tolerance $\epsilon>0$.
For any vertex $u$ that is sampled in Algorithm 1,

$\left|p_{u}-p^{\epsilon}_{u}\right|\leq\epsilon d_{u}.$

Proposition 2 ensures that for any fixed graph, the approximate PPR vector is
arbitrarily close to the exact PPR vector, as long as the tolerance
$\epsilon>0$ is sufficiently small. Appendix A contains a proof of this
proposition for completeness. Given a seed node in the graph, Algorithm 2 uses
the approximate PPR vector from Algorithm 1 and returns a set of nodes with
the largest corresponding values in the adjusted personalized PageRank (aPPR)
vector, which is defined as

$p^{*}_{v}=\frac{p_{v}}{d_{v}},\text{ for }v=1,2,...,N.$

The aPPR vector was previously proposed in Andersen et al. (2006). Algorithm 1
and 2 operate on undirected graphs. We will generalize them to directed graphs
in Section 3 thanks to a simplified and interpretable form for the PPR vector.

Algorithm 1 Approximate PPR Vector (undirected) (Andersen et al., 2006)

0: Undirected graph $G$, preference vector $\pi$, teleportation constant
$\alpha$, and tolerance $\epsilon$.

Initialize $p\leftarrow 0$, $r\leftarrow\pi$,
$\alpha^{\prime}\leftarrow\alpha/(2-\alpha)$.

while $\exists u\in V$ such that $r_{u}\geq\epsilon d_{u}$ do

Uniformly sample a vertex $u$ satisfying $r_{u}\geq\epsilon d_{u}$.

$p_{u}\leftarrow p_{u}+\alpha^{\prime}r_{u}$.

for $v:(u,v)\in E$ do

$r_{v}\leftarrow r_{v}+(1-\alpha^{\prime})r_{u}/(2d_{u})$.

end for

$r_{u}\leftarrow(1-\alpha^{\prime})r_{u}/2$.

end while

Return: $\epsilon$-approximate PPR vector $p$.

Algorithm 2 PPR Clustering (undirected)

0: Undirected graph $G$, seed node $v_{0}$, and the desired size of local
cluster $n$.

1: Calculate the approximate PPR vector $p$ (Algorithm 1).

2: Adjust the PPR vector $p$ by node degrees, $p^{*}_{v}\leftarrow
p_{v}/d_{v}$.

3: Rank all vertices according to the adjusted PPR vector $p^{*}$.

Return: local cluster – $n$ top-ranking nodes.

###  2.2 Stochastic block model

In the stochastic block model (SBM), each node belongs to one of $K$ blocks.
The presence of each edge corresponds to an independent Bernoulli random
variable, where the probability of an edge between any two nodes depends only
on the block memberships of two nodes (Holland et al., 1983). The formal
definition is as follows.

######  Definition 1.

For a vertex set $V=\\{1,2,...,N\\}$, let
$z:\\{1,2,...,N\\}\rightarrow\\{1,2,...,K\\}$ partition the $N$ nodes into $K$
blocks, so $z(v)$ is the block membership of vertex $v$. Let B be a $K\times
K$ matrix with all entries range in $[0,1]$. Under the SBM, the probability of
an edge between $u$ and $v$ is $\textbf{B}_{z(u)z(v)}$. That is, $A_{uv}\mid
z(u),z(v)\overset{\text{ind.}}{\sim}\text{Bernoulli}\left(\textbf{B}_{z(u)z(v)}\right)$,
for any $u,v\in\\{1,2,...,N\\}$.

Under the ordinary SBM, nodes in the same block have the same expected degree.
One extension is the degree-corrected stochastic block model (DC-SBM), which
adds a series of parameters ($\theta_{v}>0$ for every vertex $v$) to create
more heterogeneous node degrees (Karrer and Newman, 2011). Let B be a $K\times
K$ matrix with $\textbf{B}_{ij}>0$ for any $i$ and $j$. Then the probability
of an edge between $u$ and $v$ is $\theta_{u}\theta_{v}\textbf{B}_{z(u)z(v)}$.
That is,

$A_{uv}\mid
z(u),z(v)\overset{\text{ind.}}{\sim}\text{Bernoulli}\left(\theta_{u}\theta_{v}\textbf{B}_{z(u)z(v)}\right),$

for $u,v\in\\{1,2,...,N\\}$. Since $\theta_{v}$’s are arbitrary to a
multiplicative constant which can be absorbed into B, Karrer and Newman (2011)
suggest imposing the constraint that the $\theta_{v}$’s sum to 1 within each
block. That is, $\sum_{v:z(v)=i}\theta_{v}=1$ for all $i=1,2,..,K$. With this
constraint, $\textbf{B}_{ij}$ represents the expected number of edges between
block $i$ and $j$ if $i\neq j$, and twice of that if $i=j$. Throughout this
paper, we presume B is positive definite 222This prevents scenarios where
edges are unlikely within blocks and more likely between blocks. In such
scenarios, local clustering needs to be reimagined cautiously. See
Supplementary Materials S2 for additional details about generalizations. and
all blocks are connected (we ignore any blocks that are isolated from the
seed). The DC-SBM can be generalized to directed graphs by giving each node
two parameters, $\theta^{\text{in}}_{v}$ and $\theta^{\text{out}}_{v}$,
controlling its in-degree and out-degree respectively (Zhu et al., 2013).
Then, the presence of an directed edge from $u$ to $v$, given the block
memberships, corresponds to an independent Bernoulli random variable,

$A_{uv}\mid
z(u),z(v)\overset{\text{ind.}}{\sim}\text{Bernoulli}\left(\theta^{\text{out}}_{u}\theta^{\text{in}}_{v}\textbf{B}_{z(u)z(v)}\right).$

In order to make the model identifiable, we need to impose a structural
constraint on $\theta^{\text{in}}$’s and $\theta^{\text{out}}$’s, that both of
them sum up to 1 within each block,

$\sum_{v:z(v)=i}\theta^{\text{in}}_{v}=\sum_{v:z(v)=i}\theta^{\text{out}}_{v}=1,\text{
for any }i=1,2,...,K.$

Because the off-diagonal elements of B can be interpreted as the expected
number of edges between blocks, we define the block in-degree and block out-
degree to be the total number of incoming edges and outgoing edges
respectively, that is,
$\textbf{d}^{\text{in}}_{j}=\sum_{i=1}^{K}\textbf{B}_{ij}$, and
$\textbf{d}^{\text{out}}_{i}=\sum_{j=1}^{K}\textbf{B}_{ij}$.

##  3 Population Analysis of PageRank

In this section, we analyze the PPR vector of the expected adjacency matrix
under the DC-SBM. This provides a simple representation of the PPR vector that
motivates (1) the bias adjustment and (2) the generalization of Algorithm 1
and 2 to directed graphs.

We use three distinct typefaces to denote three classes of objects.
Calligraphic typeface is given to the population version of any observable
quantities in random graphs, such as graph adjacency matrix and node degrees
(e.g. Equation (3)). Normal typeface is given to unobserved model parameters,
such as block membership and degree parameters $\theta_{i}$. Bold face is
given to all block-level quantities and parameters like B and
$\textbf{d}^{\text{out}}_{i}$.

Define the population graph adjacency matrix,

$\mathcal{A}=\mathbb{E}\left(A\mid z(1),z(2),...,z(N)\right),$ (3)

to be the expectation of random adjacency matrix $A$. Let
$Z\in\\{0,1\\}^{N\times K}$ be the block membership matrix with $Z_{vi}=1$ if
and only if vertex $v$ belongs to block $i$, and define diagonal matrices
$\Theta^{\text{in}}$ and $\Theta^{\text{out}}$ with entries
$\theta^{\text{in}}$’s and $\theta^{\text{out}}$’s respectively. Then, under
the directed DC-SBM with $K$ blocks and parameters
$\\{\textbf{B},Z,\Theta^{\text{in}},\Theta^{\text{out}}\\}$,
$\mathcal{A}\in\mathbb{R}^{K\times K}$ can be compactly expressed as

$\mathcal{A}=\Theta^{\text{out}}Z\textbf{B}Z^{\top}\Theta^{\text{in}}.$

Accordingly, we define the population node degrees and the population
transition matrix, $\mathcal{d}^{\text{in}}_{u}=\sum_{v\in
V}\mathcal{A}_{uv}$, $\mathcal{d}^{\text{out}}_{v}=\sum_{u\in
V}\mathcal{A}_{uv}$, and
$\mathcal{P}=\left[\mathcal{D}^{\text{out}}\right]^{-1}\mathcal{A}$, where
$\mathcal{D}^{\text{in}}$ and $\mathcal{D}^{\text{out}}$ are the diagonal
matrices of the population node in-degrees $\mathcal{d}^{\text{in}}_{u}$’s and
out-degrees $\mathcal{d}^{\text{out}}_{v}$’s respectively. Let $\mathcal{p}$
be the population PPR vector (i.e., the solution to equation
$\mathcal{p}^{\top}=\alpha\pi^{\top}+(1-\alpha)\mathcal{p}^{\top}\mathcal{P}$)
and let $\mathcal{p}^{*}=\left[\mathcal{D}^{\text{in}}\right]^{-1}\mathcal{p}$
be the population aPPR vector.

In addition, define the block transition matrix
$\textbf{P}\in\mathbb{R}^{K\times K}$ as

$\textbf{P}=\left[\textbf{D}^{\text{out}}\right]^{-1}\textbf{B},$ (4)

where $\textbf{D}^{\text{in}}\in\mathbb{R}^{K\times K}$ and
$\textbf{D}^{\text{out}}\in\mathbb{R}^{K\times K}$ are diagonal matrices of
the block in-degrees $\textbf{d}^{\text{in}}_{i}$’s and out-degrees
$\textbf{d}^{\text{out}}_{i}$’s.

###  3.1 A representation of PPR vectors

This section provides a simple and interpretable form for PPR vectors under
the population DC-SBM. To this end, we define the “block-wise” PPR vector
$\textbf{p}\in\mathbb{R}^{K}$ to be the unique solution to linear system

$\textbf{p}^{\top}=\alpha\bm{\pi}^{\top}+(1-\alpha)\textbf{p}^{\top}\textbf{P},$
(5)

where $\bm{\pi}=Z^{\top}\pi\in\mathbb{R}^{K}$ is the block-wise preference
vector and P is the block transition matrix in Equation (4). This treats the
block connectivity matrix B as a weighted adjacency matrix of blocks and the
block of seed node as a seed block. To build up the relationship between PPR
and the block-wise PPR, the next theorem gives an explicit form for PPR
vectors which also reveals the sources of bias for local clustering.

######  Theorem 1 (Explicit form of PPR vectors).

Under the population directed DC-SBM with $K$ blocks and parameters
$\left\\{\textbf{B},Z,\Theta^{\text{in}},\Theta^{\text{out}}\right\\}$,

  1. cmrmn(a)

the population PPR vector $\mathcal{p}\in\mathbb{R}^{N}$ has elements

$\mathcal{p}_{u}=\theta^{\text{in}}_{u}\textbf{p}_{z(u)}$

where p is the block-wise PPR vector in Equation (5),

  2. cmrmn(b)

and the population aPPR vector $\mathcal{p}^{*}\in\mathbb{R}^{N}$ has elements

$\mathcal{p}^{*}_{u}=\textbf{p}^{*}_{z(u)}$ (6)

where $\textbf{p}^{*}=\left[\textbf{D}^{\text{in}}\right]^{-1}\textbf{p}$.

Theorem 1 demonstrates that the PPR vector $\mathcal{p}$ decomposes into
block-related information (p) and node specific information ($\Theta$). Within
each block, the PPR values are proportional to the node degree parameters
$\theta_{v}$’s and sum up to the block-wise PPR value of the block. The proof
of Theorem 1 (Appendix A) relies on a key observation (Appendix A.3) that the
powers of population transition matrix, $\mathcal{P}^{s}$ for $s=1,2,\dots$,
have a similarly simple form and the node specific information components
(i.e., $z(v)$ and $\theta_{v}$) are invariant in $s$.

In order to justify the adjustment (Step 2) in Algorithm 2, we observe that
the seed always has the highest population aPPR score. This turns out to be a
key feature that facilitates the aPPR vector to recover a local cluster
correctly, so we state it in the following lemma.

######  Lemma 1 (The largest entry of aPPR vector).

Under the population DC-SBM, assume that the minimum expected degree is
positive, that is, $\min_{v\in V}\mathcal{d}_{v}>0$. Then, for any fixed
$\alpha>0$, the population aPPR vector $\mathcal{p}^{*}$ has the strictly
largest entry corresponding to the seed node,

$\mathcal{p}^{*}_{v_{0}}>\mathcal{p}^{*}_{v},\text{ for any }v\neq v_{0}.$

On the other hand, this is not generally true for a PPR vector.

When $\alpha=0$ (i.e., no teleportation), the PPR vector becomes the limiting
distribution of a standard random walk and all entries of the aPPR vector are
equal (Appendix A). Lemma 1 (applied to block-wise PPR vectors) and Theorem 1
together identify two sources of bias for PPR vectors and suggest a
justification for the degree adjustment, which we discuss in order:

  1. (i)

Both node degree heterogeneity ($\Theta$) and block size imbalance (D)
confound the identification of local cluster by the PPR vector. In particular,
suppose vertex $v$ belongs to a block $z(v)=i$ other than 1. PPR vector
assigns it a score $\theta_{v}\textbf{p}_{i}$, where $\textbf{p}_{i}$ is the
block-wise PPR of block $i$, and $\theta_{v}$ is the parameter specifically
controlling the degree of $v$. Then, node $v$ may rank at the top, if
$\theta_{v}$ is large enough. Furthermore, Lemma 1 implies that
$\textbf{p}_{1}$ is not necessarily the largest due to block degree
heterogeneity. Specifically, if block $i$ has an exceedingly high block
degree, it is likely that $\mathcal{p}$ fails to down-rank node $v$ vis-a-vis
those nodes of block 1.

  2. (ii)

Adjusted personalized PageRank removes the node and the block degree
heterogeneity simultaneously, and perfectly recovers the local cluster. To see
this, note that $\textbf{p}^{*}$ is the adjusted version of block-wise PPR
vector. From Lemma 1, $\textbf{p}^{*}_{1}$ is the largest entry of
$\textbf{p}^{*}$. From Equation 6, the aPPR vector assigns any vertex $v$ a
score $\textbf{p}^{*}_{z(v)}$. Hence, nodes with the highest value of
$\mathcal{p}^{*}$ belong to block 1, which is precisely the desired local
cluster.

Note that the PPR vector can still be biased for local clustering even under
the classic SBM. To see this, set the matrix $\Theta$ to the identity matrix
in Theorem 1. In this case, the heterogeneous block degrees still confound the
PPR vector (Section 5.2); there is generally no guarantee for $\textbf{p}_{1}$
to appear on the top (due to Lemma 1), unless there are further symmetry
conditions. Kloumann et al. (2017) uses such one scenario. As a byproduct of
our analysis, we extend their results under the DC-SBM with the symmetric
conditions (see Supplementary Materials S3 to the paper).

###  3.2 Local clustering on directed graphs

In light of the clean form of PPR vectors under the DC-SBM, one can modify
Algorithm 1 and 2 to operate on a directed graph accordingly. To this end,
note that the transition matrix of a directed graph requires node out-degrees,
hence Algorithm 1 examines only the edges leaving visited nodes. Consequently
it suffices to replace $d_{u}$’s in Algorithm 1 by $d^{\text{out}}_{u}$’s
(Algorithm 3). Proposition 2 applies to Algorithm 3 as well, and one can
approximate the PPR vector provided the out-degrees of visited nodes can be
observed and the tolerance parameter $\epsilon>0$ is sufficiently small.

To perform local clustering on a directed graph, Algorithm 4 adjusts the
approximate PPR vectors from Algorithm 3 by node in-degrees, that is,

$p^{*}_{v}=\frac{p_{v}}{d^{\text{in}}_{v}},\text{ for }v=1,2,...,N.$

Another option is regularized adjustment, which produces the regularized PPR
(rPPR) vector,

$p^{\tau}_{v}=\frac{p_{v}}{d^{\text{in}}_{v}+\tau},\text{ for }v=1,2,...,N,$

where $\tau>0$ is the regularization parameter. The regularized adjustment
greatly stabilize the PPR clustering in practice, by removing nodes with
extremely low in-degrees (see Section 6 for more details). Adjusted PPR for
directed graphs is a local algorithm so long as $d^{\text{in}}$ is available
with a local query, for example, the Twitter friendship graph.

Algorithm 3 Approximate PPR Vector (directed)

0: Directed graph $G$, preference vector $\pi$, teleportation constant
$\alpha$, and tolerance $\epsilon$.

Initialize $p\leftarrow 0$, $r\leftarrow\pi$,
$\alpha^{\prime}\leftarrow\alpha/(2-\alpha)$.

while $\exists u\in V$ such that $r_{u}\geq\epsilon d^{\text{out}}_{u}$ do

Sample a vertex $u$ uniformly at random, satisfying $r_{u}\geq\epsilon
d^{\text{out}}_{u}$.

$p_{u}\leftarrow p_{u}+\alpha^{\prime}r_{u}$.

for $v:(u,v)\in E$ do

$r_{v}\leftarrow r_{v}+(1-\alpha^{\prime})r_{u}/(2d^{\text{out}}_{u})$.

end for

$r_{u}\leftarrow(1-\alpha^{\prime})r_{u}/2$.

end while

Return: $\epsilon$-approximate PPR vector $p$.

Algorithm 4 PPR Clustering (directed)

0: Directed graph $G$, seed node $v_{0}$, the desired size of local cluster
$n$, and an optional regularization parameter $\tau$.

1: Calculate the approximate PPR vector $p$ (Algorithm 3).

2: Adjust the PPR vector $p$ with: Option (a): node in-degrees,
$p^{*}_{v}\leftarrow p_{v}/d^{\text{in}}_{v}$,Option (b): regularized node in-
degrees, $p^{\tau}_{v}\leftarrow p_{v}/(d^{\text{in}}_{v}+\tau)$.

3: Rank all vertices according to the aPPR vector $p^{*}$ or $p^{\tau}$.

Return: local cluster – $n$ top-ranking nodes.

##  4 Personalized PageRank in Random Graphs

This section establishes several concentration results for the local
clustering algorithm using the adjusted PPR vector (Algorithm 2 and 4) under
the DC-SBM. The results show that if the graph is generated from the DC-SBM,
then PPR clustering returns the desired local cluster with high probability.
Since in Algorithm 4, the calculation for PPR vectors only relies on node out-
degrees and the adjustment step solely utilizes node in-degrees, it is not
difficult to distinguish $d^{\text{in}}$ and $d^{\text{out}}$. Thus, we state
the results in undirected graphs for simplicity. One can draw the analogous
conclusions for directed graphs by tracing the proof step by step.

We first present a useful tool that controls the entrywise errors of a PPR
vector in random graphs. Recall that $\mathcal{p}$ is the stationary
distribution of probability transition matrix
$\mathcal{Q}=\alpha\Pi+(1-\alpha)\mathcal{P}$. For any vector
$x\in\mathbb{R}^{n}$, define the vector infinity norm as
$\|x\|_{\infty}=\max_{i}|x_{i}|$. The following theorem bounds the entrywise
error of the stationary distribution of $\mathcal{Q}$.

######  Theorem 2 (Concentration of the PPR vectors).

Let $G=(V,E)$ be a graph of $N$ vertices generated from the DC-SBM with $K$
blocks and parameters $\left\\{\textbf{B},Z,\Theta\right\\}$. Let $p$ and
$\mathcal{p}$ be the PPR vector corresponding to random transition matrix $P$
and its population version $\mathcal{P}$ respectively, with the same
teleportation constant $\alpha$. Let $p^{*},\mathcal{p}^{*}\in[0,1]^{N}$ be
the adjusted PPR vector of $p$ and $\mathcal{p}$. Let $\delta$ be the average
expected node degrees, that is, $\delta=\frac{1}{N}\sum_{v\in
V}\mathcal{d}_{v}$. Assume that $\rho=\frac{\max_{v\in
V}\mathcal{d}_{v}}{\min_{v\in V}\mathcal{d}_{v}}$ is bounded by some finite
constant and that

$\delta>c_{0}(1-\alpha)^{2}\log{N},$ (7)

for some sufficiently large constant $c_{0}>0$. Then, with probability at
least $1-\mathcal{O}(N^{-5})$,

$\displaystyle\frac{\|p-\mathcal{p}\|_{\infty}}{\|\mathcal{p}\|_{\infty}}\leq
c_{1}(1-\alpha)\sqrt{\frac{\log{N}}{\delta}},$ and
$\displaystyle\frac{\|p^{*}-\mathcal{p}^{*}\|_{\infty}}{\|\mathcal{p}^{*}\|_{\infty}}\leq
c_{2}(1-\alpha)\sqrt{\frac{\log{N}}{\delta}},$

for some sufficiently large constant $c_{1},c_{2}>0$.

The proof of Theorem 2 invokes the elementary eigenvector perturbation bound
for asymmetric matrices, an analog to the celebrated Davis-Kahan $\sin\Theta$
theorem (Davis and Kahan, 1970), and the novel leave-one-out technique due to
Chen et al. (2019). The detailed proof is given in the Supplementary Materials
S1 to the paper.

Theorem 2 demonstrates that if the expected average degree $\delta$ exceeds
$(1-\alpha)^{2}\log{N}$ to some sufficiently large extent, then with high
probability, the random aPPR vector concentrates around the population aPPR
vector in terms of all entries. In fact, the concentration statement holds for
any valid preference vector $\pi$. Hence, the classic PageRank vector and some
other variants also enjoy the entrywise error bounds, so long as they can be
written as the solution to the linear system (1).

Next, we introduce a separation measure of the DC-SBM. Recall that one can
conduct a local clustering task by selecting nodes ranked by the adjusted PPR
vector $p^{*}$. In the population version, it is equivalent to distinguishing
between $\textbf{p}^{*}_{1}$ and $\textbf{p}^{*}_{k}$, for all $k=2,3,...,K$,
which also characterizes the distance from the desired local cluster (block 1)
to its complement set (the other blocks). Only if they are sufficiently
separated, can the local cluster be identifiable in the sample. Due to Lemma
1, we assume without loss of generality that the second block has the second
highest value in the “block-wise” aPPR vector, that is,
$\textbf{p}^{*}_{1}>\textbf{p}^{*}_{2}\geq\textbf{p}^{*}_{k}$ for
$k=3,4,...,K$. Then, we define the separation measure
$\Delta_{\alpha}\in(0,1]$,

$\Delta_{\alpha}=\frac{\textbf{p}^{*}_{1}-\textbf{p}^{*}_{2}}{\textbf{p}^{*}_{1}},$

which turns out to be crucial in determining the sample complexity required to
guarantee the exact recovery. We remark that $\Delta_{\alpha}$ is an
increasing function of the teleportation constant, hence the subscript
$\alpha$.

With Theorem 2 and the separation measure, we then give following corollary
that bounds the accuracy of Algorithm 2, in terms of graph edge density.

######  Corollary 1 (Exact recovery by adjusted PPR vector).

For any seed nodes, let $C\subset V$ be the local cluster of $n$ nodes
returned by Algorithm 2 with teleportation constant $\alpha$ and tolerance
$\epsilon$, and $\mathcal{C}\subset V$ be the nodes in the seed node’s block.
Assume that $\rho<c_{0}$, $\epsilon\leq
c_{1}(1-\alpha)\textbf{p}^{*}_{1}\sqrt{\log{N}/\delta}$, and that

$\delta>16c_{2}\left(\frac{1-\alpha}{\Delta_{\alpha}}\right)^{2}\log{N},$ (8)

for some sufficiently large constants $c_{0},c_{1},c_{2}>0$. If the desired
size of the local cluster $n=\left|\mathcal{C}\right|$, then with probability
at least $1-\mathcal{O}(N^{-5})$, we have $C=\mathcal{C}$.

The proof of Corollary 1 is presented in Appendix A. We make a few remarks:

  1. (i)

Corollary 1 demonstrates that Algorithm 2 works under a sparse scenario, where
the number of edges is exceedingly small in proportion to the number of
possible edges in the network. To reach the entrywise control of the aPPR
vector and the sufficient separation of local cluster from others, the theorem
calls for the expected node degree $\delta$ to grow with only a fraction (for
any fixed teleportation constant $\alpha$) of the logarithm of the size of the
network, $\log{N}$. In other words, Algorithm 2 requires a sample complexity
(the number of edges) of order

$\left(\frac{1-\alpha}{\Delta_{\alpha}}\right)^{2}N\log{N}.$

  2. (ii)

The results show that $\alpha$ leverages between the sampling complexity and
statistical performance of PPR clustering. To see this, rearrange condition
(8),

$\left(\frac{1-\alpha}{\Delta_{\alpha}}\right)^{2}<{\frac{c^{\prime}\delta}{\log{N}}},$

for some small enough constant $c^{\prime}>0$. As $\alpha$ increases, the left
hand side is decreasing to zero thus making the condition more likely to hold.
On the other hand, as $\alpha$ increases, the tolerance $\epsilon$ must
decrease at rate $\mathcal{O}(1-\alpha)$ in order to guarantee an entrywise
control of $p^{\epsilon}$ analogous to the form in Theorem 2 (Appendix A).
More intuitively, if $\epsilon$ does not decrease, then as $\alpha$ goes to
one, Algorithm 1 may terminate early without reaching all vertices in the
desired local cluster. In sum, Algorithm 1 and 3 need at least
$\mathcal{O}\left(\frac{1}{\alpha(1-\alpha)}\right)$ queries (see
Supplementary Materials S2 for an example). This implies that one can approach
the conditions in Corollary 1 by setting the teleportation constant
sufficiently large, while the computational burden can increase as
$\alpha\rightarrow 1$.

##  5 Simulation Studies

This section compares the PPR vector and the aPPR vector. The results show the
effectiveness and robustness of aPPR vector in detecting a local cluster.
Experiment 1 utilizes the DC-SBM with a power-law degree distribution and
investigates the effects of heterogeneous node degrees. Experiment 2 uses the
SBM with unequal block sizes to study the influences of heterogeneous block
degrees. Experiment 3 generates networks from the SBM with equal block sizes
and varying edge density to examine the efficacy of PPR methods in sparse
graphs.

In all simulations, we employee the block connectivity matrix B with
homogeneous diagonal elements, $\textbf{B}_{ii}=b_{1}$, and homogeneous off-
diagonal elements, $\textbf{B}_{ij}=b_{2}$ for any $i\neq j$. Define the
signal-to-noise ratio (SNR) to be the expected number of in-block edges
divided by the expected number of out-block edges, that is,
$b_{1}/(b_{2}(K-1))$, where $K$ is the number of blocks. In particular, we set
the SNR to $1.5$ and choose the teleportation constant of $\alpha=0.15$
throughout the section. Additional simulation results (illustrating the
Theorem 2) are available from Supplementary Materials S2.

###  5.1 Experiment 1

Figure 1: Comparison of PPR (left two panels) and aPPR (right two panels)
under the DC-SBM with one seed node (upper two panels) and ten seed nodes
(bottom two panels). Local cluster is in blue and other clusters are colored
in yellow. Solid horizontal lines on right panels indicate the median of aPPR
values within each cluster.

This experiment illustrates how node degree heterogeneity affects the
discriminant power in identifying local cluster using a PPR vector or an aPPR
vector. The results also illustrate the advantages of having multiple seed
nodes. The $\Theta$ parameters from the DC-SBM are drawn from the power law
distribution with lower bound $x_{\min}=1$ and shape parameter $\beta=2.5$. A
random networks were sampled from the DC-SBM with $K=3$, $N=1500$ and equal
block sampling proportions,

$z(v)\overset{\text{i.i.d.}}{\sim}\text{Multinomial}\left(\frac{1}{3},\frac{1}{3},\frac{1}{3}\right),$

for vertex $v=1,2,...,N$, whose expected average degree ($\delta$) is set to
$105$. The PPR vector is calculated with one or ten seeds randomly chosen from
block one.

Figure 1 plots PPR values (left two panels) and aPPR values (right two panels)
of a random graph generated from the DC-SBM, excluding seed node(s). The upper
two panels in Figure 1 contrast PPR and aPPR when there is only one seed node
and the bottom two panels compare two vectors when ten seed nodes are used.
The vertices from the local block in the SBM are colored in blue and the
others are in yellow. The nodes are ordered first by block, then by node
degree parameters $\theta$ (left is larger). A horizontal line is drawn for
each block indicating the median of the aPPR values within that block.

With one seed node (upper two panels), the scatter plots has two clouds within
each block. The upper cloud contains the immediate neighbors of the seed node.
This separation disappears when multiple seed nodes are used (bottom two
panels). To see the effect of node heterogeneity, the skewed distribution of
PPR values in each block demonstrates its bias towards high degree node inside
and outside of the seed nodes block in the SBM. In contrast, aPPR values are
evenly distributed within blocks, verifying that aPPR vector removes the
effects of node degree heterogeneity.

###  5.2 Experiment 2

This experiment compares PPR and aPPR under the SBM with block degree
heterogeneity. A number of random networks were sampled from the SBM with
$K=3$, $N=900$, and geometric block sampling proportions,

$z(v)\overset{\text{i.i.d.}}{\sim}\text{Multinomial}\left(1,b,b^{2}\right),$
(9)

where $b\in\left\\{1.0,1.2,1.4,1.6,1.8,2.0\right\\}$. When $b$ is larger, the
population of nodes in each block becomes more unbalanced and thus inducing
greater block degree heterogeneity. The block connectivity matrix B is
configured as described in the beginning of this section. The expected average
degree ($\delta$) is set to 70. For each sampled network, the size of the
first block is assumed known to Algorithm 2. The PPR vector is calculated
exactly in place of the approximation PPR vector (Step 1), with one seed
randomly chosen from the first block.

The top panels of Figure 2 displays the PPR vector on an example network with
$b=1.4$, demonstrating its preference toward the high degree block (the third
block) over local cluster. Given the size of the first block, we measure the
accuracy by the proportion of vertices belonging to the first block in the
returned cluster. The bottom left panel of Figure 2 shows the accuracy of PPR
and aPPR for six different values of $b$ (i.e., the geometric ratio in
distribution (9)) where each point is the average of 100 sampled network. The
comparison demonstrates that the adjusted PPR vector corrects the bias of PPR
caused by block heterogeneity. Moreover, block degree heterogeneity degrades
the performance of both PPR and aPPR. Note that aPPR outperforms PPR even when
$b=1$; this is likely due to the fact that even when nodes have equal expected
degrees in the SBM, the actual node degrees will be heterogeneous due to the
randomness in the sampled graph. In a finite graph, this variability is enough
to give aPPR an advantage over PPR. Asymptotically, this advantage should fade
away (Kloumann et al., 2017).

Figure 2: (Top) Simulated network generated from the classic SBM of 3 blocks
with block degree heterogeneity. Three horizontal lines indicate the median of
PPR and aPPR values within each cluster. (Bottom Left) Comparison of
performance for PPR (triangles with solid line) and aPPR (circles with dashed
line) under the SBM with different levels of block degree heterogeneity.
(Bottom Right) Comparison of performance for PPR and aPPR under the four-
parameters SBM with different sparsity. Error bars are drawn using standard
deviation.

###  5.3 Experiment 3

This experiment investigates the performance of PPR and aPPR under the SBM
where there is no heterogeneity in the expected node degrees or block degrees.
A number of random networks were sampled from the four-parameter stochastic
block model, $\text{SBM}(K=3,N=900,b_{1}=0.6,b_{2}=0.2)$ (Rohe et al., 2011).
Under the four-parameter SBM, each of $K$ blocks has equal size in
expectation, $N/K$, and the probability of a connection between two nodes is
$b_{2}$ if they are in two separate blocks, or $b_{1}$ if in the same one. In
addition, the expected average degree varies,
$\delta\in\left\\{15,30,45,60,75,90\right\\}$. For every setting, the results
are averaged over 100 samples of the network. The PPR vector is calculated
with one seeds randomly chosen from block one. The bottom right panel of
Figure 2 contrasts the accuracy of PPR and aPPR against six different values
of expected average degree, showing that when the sampled graph has minimal
degree heterogeneity, the adjusted PPR vector has only slightly higher
accuracy than the PPR vector.

##  6 A Sample of Twitter

In this section, we provide a more detailed case study to illustrate the
properties of different PPR vectors. We obtain a local cluster of nodes around
the seed node @NBCPolitics (NBC Politics) in the Twitter friendship graph. In
the Twitter graph, the nodes are called handles or accounts (e.g.
@NBCPolitics) and if Twitter handle $i$ follows Twitter handle $j$, then we
define this as a directed edge $(i,j)$ pointing from $i$ to $j$. Affiliated
with NBC news, NBC Politics specializes in political news coverage and has
over 470k followers on Twitter (in-degree) and follows 145 handles (out-
degree) as of December 2018. A brief look through @NBCPolitics’ following list
reveals that it follows a wide range of accounts, from TV programs, reporters
and editors affiliated with NBC, to media accounts and journalists of other
news outlets as well as politicians.

Data on following and handle profile information were collected through the
Standard Twitter Search API. We queried the Twitter friendship graph starting
from the seed node @NBCPolitics, using Algorithm 3 with teleportation constant
$\alpha=0.15$ and termination parameter $\epsilon=10^{-7}$, ending up with
5840 surrounding handles. Through this exercise, we intend to illustrate the
properties and applications of local clustering using PPR, aPPR and rPPR
vectors, where we set the regularization parameter $\tau$ to 100.

Table 3:  Top 30 handles of PPR with seed node @NBCPolitics and the
teleportation constant $\alpha=0.15$ in December 2018.

Name Followers Description 1 Melania Trump 11242283 This account is run by the
Office of First Lady Melania Trump… 2 The White House 17625630 Welcome to
@WhiteHouse! Follow for the latest from President… 3 Chuck Todd 2032038
Moderator of @meetthepress and @nbcnews political director; … 4 NBC News
6280551 The leading source of global news and info for more than 75 … 5 NBC
Nightly News 962290 Breaking news, in-depth reporting, context on news from …
6 Andrea Mitchell 1737764 NBC News Chief Foreign Affairs Correspondent/anchor,
Andrea … 7 Savannah Guthrie 881669 Mom to Vale & Charley, TODAY Co-Anchor,
Georgetown Law. … 8 Joe Scarborough 2521215 With Malice Toward None 9 MSNBC
2261911 The place for in-depth analysis, political commentary and … 10 Rachel
Maddow MSNBC 9498076 I see political people… 11 Breaking News 9223158 12 NBC
News First Read 53847 The first place for news and analysis from the @NBCNews
Poli… 13 TODAY 4276453 America’s favorite morning show $|$ Snapchat: todayshow
14 Meet the Press 566713 Meet the Press is the longest-running television show
in history … 15 The Wall Street Journal 16188842 Breaking news and features
from the WSJ. 16 Pete Williams 70062 NBC News Justice Correspondent. Covers US
Supreme Court, … 17 Mark Murray 97571 Mark Murray is the senior political
editor for NBC News, … 18 POLITICO 3695835 Nobody knows politics like
POLITICO. Got a news tip for us? … 19 Katy Tur 587474 MSNBC anchor @2pm, NBC
News correspondent, author of NYT … 20 Bill Clinton 10697521 Founder, Clinton
Foundation and 42nd President of the United… 21 Kasie Hunt 381704 @NBCNews
Capitol Hill Correspondent. Host, @KasieDC, Sundays… 22 TIME 15584815 Breaking
news and current events from around the globe. Host… 23 Kelly O’Donnell 195765
White House Correspondent @NBCNews Veteran of Cap Hill & … 24 John McCain
3181773 Memorial account for U.S. Senator John McCain, 1936-2018. To… 25 Peter
Alexander 283522 @NBCNews White House Correspondent / Weekend @TODAYshow … 26
Hallie Jackson 359099 Chief White House Correspondent / @NBCNews / @MSNBC
Anchor … 27 Kristen Welker 182244 @NBCNews White House Correspondent. Links
and retweets … 28 Carrie Dann 37119 .@NBCNews / @NBCPolitics. RTs not
endorsements. 29 Willie Geist 807536 Host @NBC #SundayTODAY, Co-Host
@Morning_Joe, “Sunday … 30 Morning Joe 563650 Live tweet during the show!
Links to must-read op-eds … • Through the PPR vector, the top 30 handles
returned to @NBCPolitics include NBC’s news related programs and celebrity
reporters, comparable mainstream media outlets, as well as prominent political
and public figures and institutions. Such results line up with its status as a
mainstream political news source, demonstrating clustering effectiveness.
Those Twitter handles tend to have millions of followers, showing the PPR
vector’s bias toward high in-degree.

We first present the results of PPR. As Table 3 shows, the top 30 handles
(except @NBCPolitics) with the highest PPR values are a combination of (i)
NBC’s news related programs such as NBC News, TODAY and Meet the Press; (ii)
NBC’s political reporters, anchors and editors, from well-known figures like
Chuck Todd and Andrea Mitchell to less-known ones like Pete Williams (justice
correspondent) and Mark Murray (senior political editor); (iii) other
mainstream news outlets such as The Wall Street Journal, POLITICO, and TIME;
and (iv) prominent public figures and politicians like Melania Trump, Bill
Clinton and John McCain. In light of NBC’s status as a mainstream news outlet
and the political focus of @NBCPolitics, such results make sound sense. It
must also be noted that all the top 30 handles are direct friends of
@NBCPolitics’s and have at least tens of thousands of followers. The median
follower count is 1.4 million, suggesting high in-degrees. In fact, the
pattern observed in the top 30 extends to the top 200 handles with the highest
PPR values, which include NBC’s own programs, journalists, editors and staff;
fellow mainstream media outlets and their staff; and prominent public figures,
politicians and government institutions (see Supplementary Materials S4). The
median in-degree of top 200 handles is around 184k, though there are four
handles with less than one thousand followers. One important thing to notice
is that among the top 200 handles, the first 139 are all directly followed by
@NBCPolitics, with handles having high in-degrees generally ranked higher than
those having low in-degrees (although @NBCPolitics follows 145 handles, 6 of
them might have privacy protection that has prevented us from accessing their
information). The remaining handles on the list, although not directly
followed by @NBCPolitics, include five handles associated with NBC, from its
news anchor Lester Holt to its News International President. However, the
majority of those indirectly followed by @NBCPolitics are mainly high profile
political and public figures (like President Trump, Vice President Pence,
Hillary Clinton, and Stephen Colbert), government organizations (like
WhiteHouse Office of Cabinet Affairs and National Security Council), and
mainstream news outlets (like New York Times, CNN and AP) and well-known
journalists (like John Dickerson and Anderson Cooper). We can thus conclude
that the PPR vector is biased toward popular accounts followed directly by the
seed node or indirectly by its friends, reflecting the popular Twitter handles
followed by them. This property of the PPR vector can be harnessed by
researchers interested in identifying the upstream of a handle, i.e., those
Twitter elites who are followed by and might influence the seed node and by
extension its followers.

Table 4: Top 30 handles of aPPR with seed node @NBCPolitics and the
teleportation constant $\alpha=0.15$ in December 2018.

Name Followers Description 1 Stephanie Palla 198 Enroll America National
Regional Director… 2 Jennifer Sizemore 386 3 Alissa Swango 441 Director of
Digital Programming at @natgeo. All things … 4 Making a Difference 670
@NBCNightlyNews’ popular feature profiles ordinary … 5 Ron Whittemore 1 6
Svante Stockselius 3 7 Greg Martin 1161 Political Booking Producer at @nbcnews
@todayshow 8 Area Man 1 I am Area Man. I pwn your news feed. 9 CELESTIA
ROBINSON 2 10 NBC Field Notes 1390 NBC News correspondents and
http://t.co/1eSopOQt8s … 11 rob adams 2 12 JL 2 13 David Kelsey 1 14 Hank
Morris 1 15 Jesse Marks 1 16 Brayden Rainey 1 17 child of the tiger 3 yet
another activist twitter, fighting all those fun… 18 Julie Swango 4 19 Author
Dianne Kube 7 Dianne Kube is an Author with a passion, for family,… 20
Consider the Source 7 21 Adam Edelman 2341 Political reporter @nbcnews.
Wisconsin native, … 22 Phil McCausland 2519 @NBCNews Digital reporter focused
on the rural-urban… 23 Corky Siemaszko 2538 Senior Writer at NBC News Digital
(former NY Daily … 24 Sam Petulla 2588 Editor @cnnpolitics • Usually looking
for datasets. … 25 Ken Strickland 2693 NBC News Washington Bureau Chief 26
Mike Mullen 7 27 Elyse PG 2697 White House producer @nbcnews $|$@USCAnnenberg
alum … 28 A. Johnson 2 Change your thoughts & you change your world. -Normal…
29 Steve Fenton 4 30 Dobe Pitty Mami 13 • Through the aPPR vector, the top 30
handles returned to @NBCPolitics include some relevant handles (NBC’s news
team and their counterparts in other mainstream news organizations) and many
obscure ones (handles with few followers and no profile descriptions). This
results from the aPPR vector’s bias toward extreme low degree and introduces
noise to the clustering results.

In contrast, the aPPR vector up-weights handles that are much less popular
(i.e., those with low in-degrees). As shown in Table 2, the 30 handles with
the highest aPPR values include NBC’s reporters, writers, editors, producers,
and programs, all of whom have a few hundred to a few thousand followers. The
30 handles also include those unaffiliated with NBC, such as director of a
non-profit (Enroll America), director of digital programming at National
Geographic, and @CNNPolitics’ editor. All of them are professionally related
to the seed node. This testifies to the applicability of aPPR for locating an
idiosyncratic local cluster around a seed node. However, more than half (17)
of the 30 handles are obscure and not directly followed by @NBCPolitics. The
reason they appear on the list is probably that they have just one and at most
a dozen followers (recall that aPPR divides by in-degree). In fact, 160 of the
top 200 handles are not direct friends of @NBCPolitics; the median in-degree
of the top 200 handles is merely 8 (Supplementary Materials S4). Those handles
might have ended up on the list due to a combination of luck and, more
importantly, their extremely low in-degrees. In this regard, “noise” can be
introduced by the aPPR vector because it prioritizes handles with extremely
low in-degrees that are possibly several degrees separated from the seed node.

Table 5: Top 30 handles of rPPR with seed node @NBCPolitics and the
teleportation constant $\alpha=0.15$ in December 2018.

Name Followers Description 1 Stephanie Palla 198 Enroll America National
Regional Director http://t.co/X6jJIE… 2 Jennifer Sizemore 386 3 Alissa Swango
441 Director of Digital Programming at @natgeo. All things food…. 4 Making a
Difference 670 @NBCNightlyNews’ popular feature profiles ordinary people do… 5
Greg Martin 1161 Political Booking Producer at @nbcnews @todayshow 6 NBC Field
Notes 1390 NBC News correspondents and http://t.co/1eSopOQt8s reporters… 7
Adam Edelman 2341 Political reporter @nbcnews. Wisconsin native, Bestchester …
8 Phil McCausland 2519 @NBCNews Digital reporter focused on the rural-urban
divide…. 9 Corky Siemaszko 2538 Senior Writer at NBC News Digital (former NY
Daily News … 10 Sam Petulla 2588 Editor @cnnpolitics • Usually looking for
datasets. You can … 11 Ken Strickland 2693 NBC News Washington Bureau Chief 12
Elyse PG 2697 White House producer @nbcnews $|$@USCAnnenberg alum $|$ LA kid …
13 Hasani Gittens 3002 Level 29 Mage. Senior News Ed. @NBCNews. Sheriff of
Nattahna… 14 Scott Foster 3464 Senior Producer, Washington @NBCNEWS @TODAYshow
15 Zach Haberman 3693 Lead Breaking News Editor, @NBCNews. Previously had
other jobs… 16 Emmanuelle Saliba 4004 Head of Social Media Strategy @Euronews
$|$ Launched #THECUBE … 17 Alex Johnson 4371 News, data and analysis for
@NBCNews; data geek; … 18 Savannah Sellers 4637 News junkie. Host of NBC’s
”Stay Tuned” on Snapchat. Storyte… 19 NYC Clothing Bank 154 We distribute new,
never-worn clothing and merchandise… 20 Shaquille Brewster 5362 @NBCNews
Producer/Politics $|$ @HowardU Alum$|$ Journalist $|$ Pol… 21 Joey Scarborough
6277 NBC News Social Media Editor. New York Daily News Alum. RTs … 22 Jane C.
Timm 6478 @nbcnews political reporter and fact checker. More fun than … 23
Anthony Terrell 6827 Emmy Award winning journalist. Political observer.
Covered … 24 NBC News Videos 7838 The latest video from http://t.co/xPyvMOTEF6
25 Libby Leist 7946 Executive Producer @todayshow 26 Voices United 310 Voices
United is a non profit educational organization … 27 Social Headlines 344
Daily roundup of top social media and networking stories. 28 James
Miklaszewski 337 Writer, Photographer, Editor, Director, Producer, Newshound …
29 Courtney Kube 9494 NBC News National Security & Military Reporter… 30 Bob
Corker 10042 Serving Tennesseans in the U.S. Senate • Through the rPPR vector,
the top 30 handles returned to @NBCPolitics include much fewer low in-degree
and obscure ones and many more moderately connected nodes that are relevant to
@NBCPolitics, including its reporters and editors and media professionals from
other organizations.

To reduce noise, we applied a regularization step to the aPPR vector to remove
those “distant” and small nodes while preserving the close and relevant ones.
In Table 3, the majority of the top 30 handles with the highest regularized
aPPR (i.e., rPPR) values have three- or four-digit numbers of followers.
Similar to the aPPR results, they include NBC’s news crew. But the difference
is that the overwhelming majority (18) of the top 30 handles work at NBC. Some
handles who work for other news organizations (e.g., Sam Petulla at
@cnnpolitics and Emmanuelle Saliba at @Euronews) might have previously worked
at NBC or have close connection with its news team. Even the four handles that
are not directly followed by @NBCPolitics are interesting – they are non-
profit organizations (NYC Clothing Bank and Voices United) and news-related
individual or organization (James Miklaszewski and Social Headlines). This
pattern can also be observed in the top 200 handles, 72 of whom are directly
followed by @NBCPolitics. The overwhelming majority of those directly followed
by it are affiliated with NBC, comprising its day-to-day news team, who enjoy
much less publicity than the celebrity reporters. The remaining 128 of them,
who are not directly followed by @NBCPolitics, actually also include 20 NBC’s
journalists and staff, such as Ray Farmer (NBC News photographer) and Jim
Miklaszewski (chief Pentagon correspondent for NBC News). Others are non-
profits like Vets Helping Heroes and professionals from other news
organizations or companies such as WSJ, NFL Network, and Microsoft, who might
have worked for NBC or have close connection with it. Although there still
appear to be obscure handles with few followers, they decrease significantly
in number – the median in-degree of the top 200 handles is 340 (Supplementary
Materials S4), a precipitous drop from that of the top PPR handles yet not too
small as compared to that of the top aPPR handles. We thus conclude that the
regularized aPPR vector returns a local cluster with little noise, reflecting
a seed node’s close circles, either directly or indirectly related.

In order to evaluate the influence of the desired cluster size $n$ on the
results based on different PPR vectors, we compare the local clusters of PPR,
aPPR, and rPPR by varying sample size. Define the in-and-out ratio of local
cluster $C\subset V$ as the proportion of edges inside $C$ among all edges
connected to $C$,

$\frac{2\times\sum_{u,v\in C}A_{uv}}{\sum_{u\in
C}d^{\text{in}}_{u}+d^{\text{out}}_{u}}.$

A higher in-and-out ratio indicates a more internally connected sample. Figure
3 (Right) shows the effectiveness of aPPR and rPPR in producing a compact
local cluster. When the sample size is bigger than 100, the connectedness of
the local cluster produced by rPPR stabilizes; the greater the sample size,
the more densely connected a cluster aPPR would produce. However, PPR is
easily susceptible to the inclusion of popular nodes. In this case, a sharp
drop of in-and-out ratio for PPR when the sample size reaches around 140 is
caused by inclusions of highly popular accounts @POTUS (President Trump) and
@realDonaldTrump (Donald J. Trump).

The PPR clustering is fairly robust to the choice of teleportation constant,
despite the size of local cluster. To illustrate this, we also performed the
same pipeline of analysis with the seed @NBCPolitics while varying the value
of $\alpha$ (e.g., $0.05$, $0.25$, and $1/3$) in parallel. We observed that
those local clusters returned by Algorithm 4 all share a great portion of
members in common. For example, there are 280 (93.3%) overlapping members
between two targeted samples of size $n=300$, using $\alpha=0.15$ and $0.25$
respectively. These suggest a low sensitivity to the teleportation constant
(see Supplementary Materials S2).

The left panel of Figure 3 depicts the behaviors of PPR, aPPR and rPPR. Each
handle queried in this sampling is displayed as a dot, with y-axis
representing the PPR value and x-axis the number of followers (i.e., in-
degree). Top handles with the highest PPR values are above blue dashed line,
which tend to concentrate on the right end of the x-axis and thus are biased
toward high in-degrees. Top handles with highest aPPR values are dots to the
left of the yellow dotdash line, which gather on the left end of the x-axis
and thus in favor of low in-degrees. Regularized aPPR, by purple dots,
excludes the very low degree nodes and very high degree nodes. As the
empirical results show, these three vectors can be thought of as lenses
through which we view the local structure of a given Twitter handle with
varying foci, rendering high, moderate, and low in-degree blocks and serving
different needs and purposes.

Figure 3: Left: an illustration of 5840 Twitter handles examined by Algorithm
3 and three samples of size 200 by PPR, aPPR, and rPPR. Each dot represents a
user in Twitter. The blue dashed line delimits the top 200 handles by PPR
vector; vertices above the line are PPR’s sample. Similarly, the yellow
dotdash line determines the sample returned by Algorithm 4 given $n=200$;
vertices above this boundary correspond to aPPR’s sample. In particular, dots
in purple stand for the sample of rPPR; the purple solid line shows the
boundary of this sample. Right: The in-and-out ratio of local clusters
identified by PPR, aPPR, and rPPR, as the sample sizes vary. A higher in-and-
out ratio indicates a more internally connected cluster.

##  7 Discussion

This paper studies the PPR vector under the degree-corrected stochastic block
model and PPR clustering in massive block model graphs. We establish some
consistency results for this method, and examine its performance through
analysis of Twitter friendship graph. As shown in the results, the PPR vectors
with and without adjustment have distinct properties and can be used to
effectively sample a massive graph for various purposes. However, there are
limitations worthy of future investigations.

In Section 3, we provide a representation of the PPR vector under the DC-SBM
and its extension into directed graphs. The result does not impose extra
structural restrictions on the model parameters, except that B corresponds to
a strongly connected “block-wise” graph. We consider a positive definite
connectivity matrix particularly so that it is intuitive to conceive the
notion of local cluster. In practice (and many of our experiments, see
Supplementary Materials S2), however, a PPR-type algorithm appears to continue
working for a broader range of B (e.g., singular or indefinite), provided that
the teleportation constant is sufficiently large (e.g. $\alpha>0.1$). It is
unclear yet what is the minimum constraint needed on B in order for the PPR
clustering to function. In addition, DC-SBM does have its limits. For example,
the model fails to capture either mixed block membership or popularity
features which are potentially informative in real world networks. The
behavior of a PPR vector under other extensions of stochastic block model,
such as mixed membership stochastic block model and popularity-adjusted block
model, remains unknown (Airoldi et al., 2008; Sengupta and Chen, 2018). Future
studies on the PPR vector under these models could shed further light on the
PPR clustering and offer more practical guidelines on their application.

In Section 4, we proved the consistency of the PPR clustering, requiring the
average expected node degree to grow in order of $\log{N}$, which hits the
boundary between the theoretical guarantees and the realistic observation. In
contrast, scale-free networks such as the preferential attachment model
(Barabási and Albert, 1999) have finite expected node degrees. Future
investigations into variants of PPR that could possibly overcome this
limitation yet ensure a fine local cluster discovery would be particularly
interesting and useful.

In Section 6, we introduce the regularized version of adjusted PPR (rPPR)
vector, with a series of empirical evidence showing its efficacy in targeted
sampling. While the results appear promising, theoretical guarantees for this
technique remain unexplored. In order for some mathematical analyses, one may
resort to the techniques used in Le et al. (2016). It is previously shown that
the regularized graph Laplacian (or transition matrix) enjoys “nice” finite
sample properties, which facilitate the consistency of many regularized
spectral methods. It thus is reasonable conjecture that rPPR vectors are also
suitable for local clustering.

An R implementation of the PPR clustering is available at author’s GitHub
(https://github.com/RoheLab/aPPR).

## Acknowledgments

This research is supported by NSF Grants DMS-1612456 and DMS-1916378 and ARO
Grant W911NF-15-1-0423. Thank you to Yuling Yan and E. Auden Krauska for the
helpful comments. Thank you to Alex Hayes for kindly advising on the software
development.

##  Appendix A Technical Proofs

###  A.1 Proof of Proposition 1

###### Proof.

We apply Perron-Frobenius theorem for the first part (Perron, 1907; Frobenius
et al., 1912), and complete the proof by construction.

  1. (a)

First, notice that $Q$ is a Markov transition matrix by modifying $G=(V,E)$ a
little. To this end, (i) shrink the weights of every existing edge by factor
$1-\alpha$, and (ii) add an edge weighted $\alpha$ between seed node $v_{0}$
and all nodes in the graph. Then $Q$ represents the new graph
$G^{\prime}(V,E^{\prime})$, which is strongly connected by construction. Hence
$Q$ is irreducible.

The PPR vector $p$ is all-positive. To see this, note that the equation
$p^{\top}=p^{\top}Q$ implies that $p$ is a stationary distribution for the
standard random walk on $G^{\prime}$. Since $G^{\prime}$ is strongly
connected, it follows that the stationary distribution must be all-positive.

From the Perron-Frobenius theorem, the only all-positive eigenvector of a non-
negative irreducible matrix is associated with the leading eigenvalue, which
is 1 in our case. Since the leading eigenvalue of non-negative irreducible
matrix is simple, we conclude that $p$ is unique.

  2. (b)

We finish the proof by constructing an explicit form of the PPR vector. Let
$R_{\alpha}=\alpha\sum_{s=0}^{\infty}(1-\alpha)^{s}P^{s}.$ The infinite sum
converges for $\alpha\in(0,1]$. Then, $p=R_{\alpha}^{\top}\pi$ satisfies the
definition of personalized PageRank vector,

$\displaystyle\alpha\pi^{\top}+(1-\alpha)\pi^{\top}R_{\alpha}P$
$\displaystyle=$
$\displaystyle\alpha\pi^{\top}+(1-\alpha)\pi^{\top}\left(\alpha\sum_{s=0}^{\infty}(1-\alpha)^{s}P^{s}\right)P$
$\displaystyle=$
$\displaystyle\alpha\pi^{\top}+\alpha\sum_{s=1}^{\infty}(1-\alpha)^{s}\pi^{\top}P^{s}$
$\displaystyle=$ $\displaystyle\pi^{\top}R_{\alpha}.$

Since the solution is unique, we have $p=R_{\alpha}^{\top}\pi$. ∎

###  A.2 Proof of Proposition 2

###### Proof.

Algorithm 1 maintains two vectors, $p^{\epsilon}$ and $r$, by transporting
probability mass from $r$ to $p^{\epsilon}$ at each updating step. Note that
the termination criterion implies that $r_{u}<\epsilon d_{u}$ for any $u$
sampled, thus it suffices to prove that

$\left|p_{u}-p^{\epsilon}_{u}\right|\leq r_{u}.$

For a fixed $\alpha$, let $p(x)$ be the PPR vector with preference vector
$x\in\mathbb{R}^{N}$ satisfying $x_{i}\geq 0$ and $\|x\|_{1}\leq 1$. Then
$p(\pi)$ is the exact PPR vector as in Equation (2). Since
$p(x)^{\top}P=p(x^{\top}P)$, we have (Jeh and Widom, 2003)

$p(x)=\alpha x+(1-\alpha)p(P^{\top}x).$ (10)

We argue that $p^{\epsilon}+p(r)$ is invariant in updating steps. To see this,
suppose $(p^{\epsilon})^{\prime}$ and $r^{\prime}$ are the results of
performing one update on $p^{\epsilon}$ and $r$ after sampling node $u$. We
have

$\displaystyle(p^{\epsilon})^{\prime}$ $\displaystyle=$ $\displaystyle
p^{\epsilon}+\alpha r_{u}e_{u},$ $\displaystyle r^{\prime}$ $\displaystyle=$
$\displaystyle r-r_{u}e_{u}+(1-\alpha)r_{u}P^{\top}e_{u}.$

where $e_{u}$ is the unit vector on the direction of $u$. Then,

$\displaystyle p(r)$ $\displaystyle=$ $\displaystyle
p(r-r_{u}e_{u})+p(r_{u}e_{u})$ $\displaystyle\overset{\text{(i)}}{=}$
$\displaystyle p(r-r_{u}e_{u})+\alpha
r_{u}e_{u}+(1-\alpha)p\left(r_{u}P^{\top}e_{u}\right)$
$\displaystyle\overset{\text{(ii)}}{=}$ $\displaystyle
p\left(r-r_{u}e_{u}+(1-\alpha)r_{u}P^{\top}e_{u}\right)+\alpha r_{u}e_{u}$
$\displaystyle=$ $\displaystyle
p(r^{\prime})+\left(p^{\epsilon}\right)^{\prime}-p^{\epsilon},$

where (i) is applying Equation (10) at $x=r_{u}e_{u}$ and (ii) comes from the
linearity of PPR vector in the preference vector.

The desired result follows from recognizing that $p^{\epsilon}+p(r)$ is
initially $\vec{0}+p(\pi)$ and that when the algorithm terminates,
$\left[p(r)\right]_{u}\leq r_{u}$ for any sampled $u$. ∎

Remark. If $\epsilon d_{1}>1$, Algorithm 1 terminates after the first round
and simply output $p=\vec{0}$. Under this circumstance, Proposition 2 still
holds, because
$\left|p_{u}-p^{\epsilon}_{u}\right|\leq\left|p_{u}\right|+\left|p^{\epsilon}_{u}\right|\leq
1$.

###  A.3 Lemmas for the DC-SBM

######  Lemma 2 (Properties of the DC-SBM).

Under the population directed DC-SBM with $K$ blocks and parameters
$\left\\{\textbf{B},Z,\Theta^{\text{in}},\Theta^{\text{out}}\right\\}$,

  1. cmrmn(a)

$\textbf{D}^{\text{in}}=Z^{\top}\mathcal{D}^{\text{in}}Z$, and
$\textbf{D}^{\text{out}}=Z^{\top}\mathcal{D}^{\text{out}}Z$ , and

  2. cmrmn(b)

$\mathcal{d}^{\text{in}}_{v}=\theta^{\text{in}}_{v}\textbf{d}^{\text{in}}_{z(v)}$,
and
$\mathcal{d}^{\text{out}}_{v}=\theta^{\text{out}}_{v}\textbf{d}^{\text{out}}_{z(v)}$.

###### Proof.

a is an alternative way of writing the definition. For b, we prove the first
equation. Recall that for any $i$, $\sum_{u:z(u)=i}\theta^{\text{out}}_{u}=1$,
then by definition,

$\mathcal{d}^{\text{in}}_{v}=\sum_{u}\theta^{\text{out}}_{u}\theta^{\text{in}}_{v}B_{z(u)z(v)}=\theta^{\text{in}}_{v}\sum_{j=1}^{K}\left(\textbf{B}_{jz(v)}\sum_{u:z(u)=j}\theta^{\text{out}}_{u}\right)=\theta^{\text{in}}_{v}\textbf{d}^{\text{in}}_{z(v)}.$

∎

Remark. Since $Z^{\top}\Theta^{\text{in}}Z=I_{K}$, a implies
$\left[\mathcal{D}^{\text{in}}\right]^{-1}\Theta^{\text{in}}Z=Z\left[\textbf{D}^{\text{in}}\right]^{-1}$.

######  Lemma 3 (Explicit form of $\mathcal{P}$ and its powers).

Under the population directed DC-SBM with $K$ blocks and parameters
$\left\\{\textbf{B},Z,\Theta^{\text{in}},\Theta^{\text{out}}\right\\}$, the
population graph transition is the product

$\mathcal{P}=Z\textbf{P}Z^{\top}\Theta^{\text{in}}.$

and its matrix powers are

$\mathcal{P}^{k}=Z\textbf{P}^{k}Z^{\top}\Theta^{\text{in}}.$

###### Proof.

By definition and Lemma 2b, for any $u,v\in V$,

$\mathcal{P}_{uv}=\left(\theta^{\text{out}}_{u}\textbf{d}^{\text{out}}_{z(u)}\right)^{-1}\theta^{\text{out}}_{u}\theta^{\text{in}}_{v}\textbf{B}_{z(u)z(v)}=\theta^{\text{in}}_{v}\textbf{B}_{z(u)z(v)}/\textbf{d}^{\text{out}}_{z(u)}=\theta^{\text{in}}_{v}\textbf{P}_{z(u)z(v)}.$

For the powers of $\mathcal{P}$, noticing that
$Z^{\top}\Theta^{\text{in}}Z=I_{K}$,

$\mathcal{P}^{2}=Z\textbf{P}Z^{\top}\Theta^{\text{in}}Z\textbf{P}Z^{\top}\Theta^{\text{in}}=Z\textbf{P}^{2}Z^{\top}\Theta^{\text{in}}.$

The desired result follows from the principle of induction on $k$-th power. ∎

###  A.4 Proof of Theorem 1

###### Proof.

By Proposition 1 and Lemma 3, we have

$\displaystyle\mathcal{p}$ $\displaystyle=$
$\displaystyle\alpha\sum_{s=0}^{\infty}(1-\alpha)^{s}\left(\mathcal{P}^{s}\right)^{\top}\pi$
$\displaystyle=$
$\displaystyle\alpha\sum_{s=0}^{\infty}(1-\alpha)^{s}\Theta^{\text{in}}Z\left(\textbf{P}^{s}\right)^{\top}Z^{\top}\pi$
$\displaystyle=$
$\displaystyle\Theta^{\text{in}}Z\left(\alpha\sum_{s=0}^{\infty}(1-\alpha)^{s}\left(\textbf{P}^{s}\right)^{\top}\bm{\pi}\right)$
$\displaystyle=$ $\displaystyle\Theta^{\text{in}}Z\textbf{p},$

In addition, it follows from Lemma 2a that

$\mathcal{p}^{*}=\left[\mathcal{D}^{\text{in}}\right]^{-1}\mathcal{p}=\left[\mathcal{D}^{\text{in}}\right]^{-1}\Theta^{\text{in}}Z\textbf{p}=Z\left[\textbf{D}^{\text{in}}\right]^{-1}\textbf{p}=Z\textbf{p}^{*}.$

This completes the proof. ∎

###  A.5 Proof of Lemma 1

###### Proof.

For any $\alpha>0$, the PPR vector with seed node $v_{0}=1$ is the solution to
the equation $\mathcal{p}^{\top}=\mathcal{p}^{\top}\mathcal{Q}$, where
$\mathcal{Q}=\alpha\Pi+(1-\alpha)\mathcal{P}$. Define a sequence of
probability distribution $\mathcal{p}^{s}\in\mathbb{R}^{N}$ such that
$\mathcal{p}^{s}=\left(\mathcal{Q}^{s}\right)^{\top}\mathcal{p}^{0}$, where
$\mathcal{p}^{0}$ is an arbitrary initial probability distribution. Then,
$\lim_{s\rightarrow\infty}\mathcal{p}^{s}=\mathcal{p}$. For simplicity, we
assume $\mathcal{p}^{0}$ is close to $\mathcal{p}$, that is, for any
$\varepsilon>0$ and $s\geq 0$,

$\|\mathcal{p}^{s}-\mathcal{p}\|_{\infty}<\varepsilon/2.$ (11)

This can be achieved by finding an integer $S(\varepsilon)$ large enough and
setting $\mathcal{p}^{0}=\mathcal{p}^{S}$.

We first claim that

$\max_{u\neq
1}\frac{\mathcal{p}^{s+1}_{u}}{\mathcal{d}_{u}}\leq(1-\alpha)\max_{u\in
V}\frac{\mathcal{p}^{s}_{u}}{\mathcal{d}_{u}}.$ (12)

In fact, for any $u\neq 1$,

$\displaystyle\mathcal{p}^{s+1}_{u}$ $\displaystyle=$
$\displaystyle\alpha\mathds{1}_{\\{u=1\\}}+(1-\alpha)\sum_{v\in
V}\frac{\mathcal{A}_{vu}}{\mathcal{d}_{v}}\mathcal{p}^{s}_{v}$
$\displaystyle\leq$ $\displaystyle(1-\alpha)\left(\sum_{v\in
V}\mathcal{A}_{vu}\right)\max_{v\in
V}\frac{\mathcal{p}^{s}_{v}}{\mathcal{d}_{v}}$ $\displaystyle=$
$\displaystyle(1-\alpha)\mathcal{d}_{u}\max_{v\in
V}\frac{\mathcal{p}^{s}_{v}}{\mathcal{d}_{v}}.$

We then show
$\frac{\mathcal{p}^{s}_{1}}{\mathcal{d}_{1}}>\frac{\mathcal{p}^{s}_{v}}{\mathcal{d}_{v}}$
for any $v\neq 1$ by contradiction. Suppose otherwise that
$\frac{\mathcal{p}^{s}_{1}}{\mathcal{d}_{1}}\leq\max_{u\neq
1}\frac{\mathcal{p}^{s}_{u}}{\mathcal{d}_{u}}$, then Equation (11) implies for
any $s^{\prime}$,

$\displaystyle\frac{\mathcal{p}^{s^{\prime}}_{1}}{\mathcal{d}_{1}}\leq\frac{\mathcal{p}^{s}_{1}+\varepsilon}{\mathcal{d}_{1}}\leq\max_{u\neq
1}\frac{\mathcal{p}^{s}_{u}}{\mathcal{d}_{u}}+\frac{\varepsilon}{\mathcal{d}_{1}}\leq\max_{u\neq
1}\frac{\mathcal{p}^{s^{\prime}}_{u}+\varepsilon}{\mathcal{d}_{u}}+\frac{\varepsilon}{\mathcal{d}_{1}}\leq\max_{u\neq
1}\frac{\mathcal{p}^{s^{\prime}}_{u}}{\mathcal{d}_{u}}+\frac{2\varepsilon}{\mathcal{d}_{\min}},$

where $\mathcal{d}_{\min}=\min_{v\in V}\mathcal{d}_{v}$. Hence, $\max_{u\in
V}\frac{\mathcal{p}^{s^{\prime}}_{u}}{\mathcal{d}_{u}}\leq\max_{u\neq
1}\frac{\mathcal{p}^{s^{\prime}}_{u}}{\mathcal{d}_{u}}+\frac{2\varepsilon}{\mathcal{d}_{\min}}$.
In addition, applying Equation (12) recursively we have

$\displaystyle\max_{u\in V}\frac{\mathcal{p}^{s}_{u}}{\mathcal{d}_{u}}$
$\displaystyle=$ $\displaystyle\max_{u\neq
1}\frac{\mathcal{p}^{s}_{u}}{\mathcal{d}_{u}}$ $\displaystyle\leq$
$\displaystyle(1-\alpha)\max_{u\in
V}\frac{\mathcal{p}^{s-1}_{u}}{\mathcal{d}_{u}}$ $\displaystyle\leq$
$\displaystyle(1-\alpha)\left(\max_{u\neq
1}\frac{\mathcal{p}^{s-1}_{u}}{\mathcal{d}_{u}}+\frac{2\varepsilon}{\mathcal{d}_{\min}}\right)$
$\displaystyle\leq$ $\displaystyle(1-\alpha)^{s}\max_{u\in
V}\frac{\mathcal{p}^{0}_{u}}{\mathcal{d}_{u}}+\frac{2\varepsilon}{\mathcal{d}_{\min}}\sum_{t=1}^{s-1}(1-\alpha)^{t}.$

The inequality means that if $\mathcal{d}_{\min}>0$ is fixed,
$\mathcal{p}^{s}_{u}$ can be arbitrarily small when $s\rightarrow\infty$,
which contradicts the fact that $\mathcal{p}$ is a probability distribution.
This completes the proof.

Remark. When the teleportation constant is zero, the PPR vector becomes the
stationary probability distribution of a standard random walk,

$\left(\frac{\mathcal{d}_{1}}{\sum_{i}\mathcal{d}_{i}},\frac{\mathcal{d}_{2}}{\sum_{i}\mathcal{d}_{i}},...,\frac{\mathcal{d}_{N}}{\sum_{i}\mathcal{d}_{i}}\right).$

After adjusting by node degrees, every entry becomes identical
(${1/\sum_{i}\mathcal{d}_{i}}$). The lemma is intuitive, recognizing that the
teleportation introduces a particular favor of the seed node.

Remark. When the edges are weighted (non-negative), the stationary
distribution of a random walk is still proportional to node degrees, if one
defines the degree as sum of edge weights incident to the node (Lovász, 1996).
Note also that the stationary distribution of a random walk in a directed
graph is characterized by the in-degree of nodes (Ghoshal and Barabási, 2011;
Lu et al., 2013). The conclusion and a modified proof apply to directed or
weighted graphs. ∎

###  A.6 Proof of Corollary 1

###### Proof.

The algorithm ranks all vertices according to ${p^{\epsilon}}^{*}$, and the
population local cluster can be explicitly written as

$\mathcal{C}=\\{v\in V:\mathcal{p}_{v}^{*}=\textbf{p}^{*}_{1}\\}.$

It suffices to show that

${p^{\epsilon}_{v}}^{*}>{p^{\epsilon}_{u}}^{*},\text{ for }\forall
v\in\mathcal{C},u\in V\backslash\mathcal{C},$

where ${p^{\epsilon}}^{*}_{v}=p^{\epsilon}_{v}/d_{v}$. To this end, we apply
triangle inequality and get

$\displaystyle\frac{{p^{\epsilon}_{v}}^{*}-{p^{\epsilon}_{u}}^{*}}{\|\mathcal{p}^{*}\|_{\infty}}$
$\displaystyle\geq$
$\displaystyle\frac{\mathcal{p}^{*}_{v}-\mathcal{p}^{*}_{u}}{\|\mathcal{p}^{*}\|_{\infty}}-\frac{|p^{*}_{v}-\mathcal{p}^{*}_{v}|}{\|\mathcal{p}^{*}\|_{\infty}}-\frac{|p^{*}_{u}-\mathcal{p}^{*}_{u}|}{\|\mathcal{p}^{*}\|_{\infty}}-\frac{\left|{p^{\epsilon}_{u}}^{*}-p^{*}_{u}\right|}{\|\mathcal{p}^{*}\|_{\infty}}-\frac{\left|{p^{\epsilon}_{v}}^{*}-p^{*}_{v}\right|}{\|\mathcal{p}^{*}\|_{\infty}}$
$\displaystyle\geq$
$\displaystyle\Delta-\frac{2\|p^{*}-\mathcal{p}^{*}\|_{\infty}}{\|\mathcal{p}^{*}\|_{\infty}}-\frac{2\|{p^{\epsilon}}^{*}-p^{*}\|_{\infty}}{\|\mathcal{p}^{*}\|_{\infty}}.$

Since $\Delta_{\alpha}\leq 1$, assumption (8) contains condition (7) in
Theorem 2, which together with Proposition 2 implies that

$\displaystyle\frac{\|p^{*}-\mathcal{p}^{*}\|_{\infty}}{\|\mathcal{p}^{*}\|_{\infty}}<\frac{1}{4}\Delta,$
$\displaystyle\frac{\|{p^{\epsilon}}^{*}-p^{*}\|_{\infty}}{\|\mathcal{p}^{*}\|_{\infty}}<\frac{1}{4}\Delta,$

if $\Delta^{2}\delta/\log{N}$ is large enough. These collectively imply
$p^{*}_{v}>p^{*}_{u}$ as desired. ∎

Supplementary Materials

##  Appendix S1 A proof for the entrywise error control

We start with a few lemmas to prepare for the proof of Theorem 2. For
completeness, Section S1.3 lists a few inequalities that are used throughout
the proofs.

###  S1.1 Some definitions and lemmas

In this section, we introduce a few notations used in Lemma S3 and list a few
properties of vector norm and matrix norm (Brémaud, 2013).

For any strictly positive probability distribution vector
$p\in\mathbb{R}^{N}$, the inner product space indexed by $p$ is a real vector
space $\mathbb{R}^{N}$ endowed with the inner product

$\langle x,y\rangle_{p}=\sum_{v=1}^{N}p_{v}x_{v}y_{v}.$

The corresponding vector norm and the induced matrix norm are defined
respectively as

$\|x\|_{p}=\sqrt{\langle x,x\rangle_{p}}\text{ \ and \
}\|A\|_{p}=\sup_{\|x\|_{p}=1}\|A^{\top}x\|_{p}.$

######  Lemma S1.

If $0\leq p_{\min}\leq p_{v}\leq p_{\max}$ for all $v=1,2,...,N$, then the
following inequalities hold

$\sqrt{p_{\min}}\|x\|_{2}\leq\|x\|_{p}\leq\sqrt{p_{\max}}\|x\|_{2}\text{ \ and
\
}\sqrt{\frac{p_{\min}}{p_{\max}}}\|A\|_{2}\leq\|A\|_{p}\leq\sqrt{\frac{p_{\max}}{p_{\min}}}\|A\|_{2}.$

The following lemma provides concentration of the node degrees in a graph
generated from the DC-SBM.

######  Lemma S2 (Degree concentration).

Let $G=(V,E)$ be a graph of $N$ vertices generated from the DC-SBM with $K$
blocks and parameters $\left\\{\textbf{B},Z,\Theta\right\\}$. Let $d_{\min}$
and $d_{\max}$ be the smallest and the largest node degree observed. Let
$\delta$ be the average expected node degree, and define
$\rho=\mathcal{d}_{\max}/\mathcal{d}_{\min}$. If $\delta\geq
c_{0}(1-\alpha)\log{N}$ for some sufficiently large constant $c_{0}>0$, then
with probability at least $1-\mathcal{O}(N^{-10})$, it holds that

$\frac{\delta}{2\rho}\leq d_{\min}\leq d_{\max}\leq\frac{3\rho\delta}{2}.$
(13)

###### Proof.

Note that the definition of $\rho$ immediately implies that

$\frac{\delta}{\rho}\leq\mathcal{d}_{\min}\leq\mathcal{d}_{\max}\leq\delta\rho.$

The lemma follows from the standard Chernoff’s bound, hence is omitted. ∎

The following useful lemma concerns the eigenvector perturbation for
probability transition matrices, promoted from the celebrated Davis-Kahan
$\sin\Theta$ Theorem (Davis and Kahan, 1970).

######  Lemma S3 (Eigenvector perturbation).

Suppose that $Q$, $\hat{Q}$, and $\mathcal{Q}$ are probability transition
matrices with stationary distributions $p$, $\hat{p}$, and $\mathcal{p}$
respectively. Assume that $\mathcal{Q}$ represents a reversible Markov chain.
Then,

$\|p-\hat{p}\|_{\mathcal{p}}\leq\frac{\|(Q-\hat{Q})^{\top}p\|_{\mathcal{p}}}{1-\max\\{\lambda_{2}(\mathcal{Q}),-\lambda_{N}(\mathcal{Q})\\}-\|\hat{Q}-\mathcal{Q}\|_{\mathcal{p}}}.$

The proof the Lemma S3 can be found in Chen et al. (2019) Section 3, thus
omitted.

###  S1.2 Proof of Theorem 2

###### Proof.

The proof processes as follows. We first bound the entrywise error rate of
$p$,

$\frac{\|p-\mathcal{p}\|_{\infty}}{\|\mathcal{p}\|_{\infty}}\leq
c_{0}\sqrt{\frac{\log{N}}{\delta}},$

by invoking the novel leave-one-out techniques (Chen et al., 2019), The
entrywise error bounds of $p^{*}$ follows immediately.

Recall that both $p$ and $\mathcal{p}$ are stationary distribution, which
means

$p=Q^{\top}p\text{ \ and \ }\mathcal{p}=\mathcal{Q}^{\top}\mathcal{p}.$

Due to this, for any $w=1,2,...,N$, we can decompose

$\displaystyle p_{w}-\mathcal{p}_{w}$ $\displaystyle=$ $\displaystyle
Q^{\top}_{\cdot w}p-\mathcal{Q}^{\top}_{\cdot w}\mathcal{p}$ $\displaystyle=$
$\displaystyle\underbrace{(Q_{\cdot w}-\mathcal{Q}_{\cdot
w})^{\top}\mathcal{p}}_{:=I_{1}^{w}}+\underbrace{Q^{\top}_{\cdot
w}(p-\mathcal{p})}_{:=I_{2}^{w}},$

where $Q_{\cdot w}$ denotes the $w$-th column of $Q$.

  1. (a)

We start with the first term $I^{w}_{1}$. Note that

$\displaystyle I_{1}^{w}$ $\displaystyle=$
$\displaystyle(1-\alpha)\sum_{v=1}^{N}\left[\frac{A_{vw}}{d_{v}}-\frac{\mathcal{A}_{vw}}{\mathcal{d}_{v}}\right]\mathcal{p}_{v}$
$\displaystyle=$
$\displaystyle\underbrace{(1-\alpha)\sum_{v=1}^{N}\left[(A_{vw}-\mathcal{A}_{vw})\frac{1}{\mathcal{d}_{v}}\right]\mathcal{p}_{v}}_{:=I_{11}^{w}}+\underbrace{(1-\alpha)\sum_{v=1}^{N}A_{vw}\left(\frac{1}{d_{v}}-\frac{1}{\mathcal{d}_{v}}\right)\mathcal{p}_{v}}_{:=I_{12}^{w}}.$

Recall that $A_{vw}$’s correspond to independent Bernoulli random variables,
we can easily bound the first term using Bernstein’s inequality (Lemma S6),
with probability at least $1-\mathcal{O}(N^{-8})$,

$\displaystyle|I_{11}^{w}|$ $\displaystyle\leq$
$\displaystyle(1-\alpha)\left|\sum_{v=1}^{N}(A_{vw}-\mathcal{A}_{vw})\right|\frac{\|p\|_{\infty}}{\delta}$
$\displaystyle\leq$
$\displaystyle(1-\alpha)\left(\sqrt{16\log{N}\sum_{v=1}^{N}\mathcal{A}_{vw}}+\frac{16\log{N}}{3}\right)\frac{\|p\|_{\infty}}{\delta}$
$\displaystyle\overset{\text{(i)}}{\leq}$
$\displaystyle(1-\alpha)\left(4\sqrt{\frac{\rho\log{N}}{\delta}}+\frac{16\log{N}}{3\delta}\right)\|p\|_{\infty},$

where (i) follows from the fact that $\rho\delta\leq\mathcal{d}_{\max}$.

Note that the second term is

$I_{12}^{w}=(1-\alpha)\sum_{v=1}^{N}\mathds{1}_{(v,w)\in
E}\left(\frac{1}{d_{v}}-\frac{1}{\mathcal{d}_{v}}\right)\mathcal{p}_{v},$

to which we can apply the Hoeffding’s inequality (Lemma S4) and obtain

$\mathbb{P}\left(|I_{12}^{w}|\leq\rho(1-\alpha)\sqrt{\frac{\rho\log{N}}{\delta}}\|\mathcal{p}\|_{\infty}\right)\geq
1-2N^{-8}.$

In sums, we have high probability event

$|I^{w}_{1}|\leq(1-\alpha)\left((4+\rho)\sqrt{\rho}+3\sqrt{\frac{\log{N}}{\delta}}\right)\sqrt{\frac{\log{N}}{\delta}}\|p\|_{\infty}.$
(14)

  2. (b)

The statistical dependency between $p$ and $Q$ introduces difficulty in
sharply bounding $I_{2}^{w}$. Nevertheless, we can invoke the leave-one-out
techniques to decouple the dependency. To this end, we define, for each
$w=1,2,...,N$, a new transition matrix $Q^{(w)}=\alpha\Pi+(1-\alpha)P^{(w)}$
that bridges between $Q$ and $\mathcal{Q}$. $P^{(w)}$ has almost the same
entries as $P$ except for replacing those in $w$-th row or column by their
expectations; that is, for any $u\neq v$,

$P^{(w)}_{uv}=\left\\{\begin{array}[]{ll}P_{uv},&u\neq w\text{ and }v\neq
w,\\\ \mathcal{P}_{uv},&u=w\text{ or }v=w,\end{array}\right.$

and for any $u=1,2,...,N$,

$P^{(w)}_{uu}=1-\sum_{v:v\neq u}P^{(w)}_{uv},$

in order to ensure that $P^{(w)}$ and $Q^{(w)}$ are transition matrices. In
addition, define $p^{(w)}$ to be the stationary distribution corresponding to
$Q^{(w)}$. As demonstrated in Chen et al. (2019), $p^{(w)}$ helps us well
approximate $p$, yet it is statistically independent of $Q_{\cdot w}$.

Now we decompose $I_{2}^{w}$ as follows:

$\displaystyle I_{2}^{w}$ $\displaystyle=$
$\displaystyle\sum_{v=1}^{N}Q_{vw}(p_{v}-\mathcal{p}_{v})$ $\displaystyle=$
$\displaystyle\underbrace{\sum_{v=1}^{N}Q_{vw}\left(p_{v}-p^{(w)}_{v}\right)}_{:=I_{21}^{w}}+\underbrace{\sum_{v=1}^{N}Q_{vw}\left(p^{(w)}_{v}-\mathcal{p}_{v}\right)}_{:=I_{22}^{w}}.$

  3. (c)

In this part, we focus on the first term $I_{21}^{w}$, where we would need
another intermediate quantity to facilitate our estimation. To be specific,
consider the leave-one-out version of $Q$ conditioning on the graph $G=(V,E)$,
$Q^{(w,G)}=\alpha\Pi+(1-\alpha)P^{(w,G)}$, which is almost the same as $Q$
except for replacing the non-zero entries in $w$-th row or column by their
expectations. Concretely, for and $u\neq v$,

$P^{(w,G)}_{uv}=\left\\{\begin{array}[]{ll}P_{uv},&u\neq w\text{ and }v\neq
w,\\\ \mathds{1}_{(u,v)\in E}\mathcal{P}_{uv},&u=w\text{ or
}v=w,\end{array}\right.$

and for any $u=1,2,...,N$, define

$P^{(w,G)}_{uu}=1-\sum_{v:v\neq u}P^{(w,G)}_{uv},$

so that $P^{(w,G)}$ is a probability transition matrix.

With $Q^{(w,G)}$ in mind, we now apply Cauchy-Schwarz inequality on
$I_{21}^{w}$ to reach

$\displaystyle|I_{21}^{w}|$ $\displaystyle=$
$\displaystyle\left|\sum_{v=1}^{N}Q_{vw}\left(p_{v}-p^{(w)}_{v}\right)\right|$
$\displaystyle\leq$
$\displaystyle\left(\sum_{v=1}^{N}Q_{vw}^{2}\right)^{\frac{1}{2}}\left\|p-p^{(w)}\right\|_{2}$
$\displaystyle\overset{\text{(i)}}{\leq}$
$\displaystyle\sqrt{\alpha+\frac{1}{d_{\min}}}\sqrt{\frac{\mathcal{p}_{\max}}{\mathcal{p}_{\min}}}\left\|p-p^{(w)}\right\|_{\mathcal{p}}$
$\displaystyle\overset{\text{(ii)}}{\leq}$
$\displaystyle\sqrt{\alpha+\frac{1}{d_{\min}}}\sqrt{\frac{\mathcal{p}_{\max}}{\mathcal{p}_{\min}}}\frac{1}{\gamma}\left\|\left(Q-Q^{(w)}\right)^{\top}p^{(w)}\right\|_{2}$
$\displaystyle\overset{\text{(iii)}}{\overset{\text{w.h.p.}}{\leq}}$
$\displaystyle\sqrt{\alpha+\frac{2\rho}{\delta}}\frac{\sqrt{\kappa}}{\gamma}\left(\underbrace{\left\|(Q-Q^{(w,G)})^{\top}p^{(w)}\right\|_{2}}_{:=I^{w}_{211}}+\underbrace{\left\|(Q^{(w,G)}-Q^{(w)})^{\top}p^{(w)}\right\|_{2}}_{:=I^{w}_{212}}\right).$

where (i) follows from Lemma S1 and the fact that
$P_{vw}\leq\frac{1}{d_{\min}}$, (ii) comes from Lemma S3, and (iii) results
from Lemma S2 and the triangle inequality, and recognizing
$\kappa=\mathcal{p}_{\max}/\mathcal{p}_{\min}$ (from the proof of Proposition
1, it is bounded), and “w.h.p.” is short for “with high probability”. Note
that $\Pi$ adds at most 1 to the rank of $\mathcal{Q}$, and because we presume
$B$ is positive definite $\mathcal{P}$ has exactly $K$ positive eigenvalues
among other zeros (Section S2.2). Here,
$\gamma=1-\max\\{\lambda_{2}(\mathcal{Q}),-\lambda_{N}(\mathcal{Q})\\}-\|Q^{(w,G)}-\mathcal{Q}\|_{\mathcal{p}}$
is the spectral gap and is lower bounded by some positive constant (due to
Khanna et al. (2017)). Then, it boils down to controlling $I^{w}_{211}$ and
$I^{w}_{212}$.

For $I^{w}_{211}$, the $w$-th entry inside the vector norm is

$\displaystyle\left[\left(Q-Q^{(w,G)}\right)^{\top}p^{(w)}\right]_{w}$
$\displaystyle=$
$\displaystyle\left[\left(Q-\mathcal{Q}\right)^{\top}p^{(w)}\right]_{w}$
$\displaystyle=$
$\displaystyle(1-\alpha)\sum_{v=1}^{N}(P_{vw}-\mathcal{P}_{vw})p^{(w)}_{v}.$

Note that $p^{(w)}_{v}$ is statistically independent of $P_{\cdot w}$. Then,
by Hoeffding’s inequality (Lemma S4) and Lemma S2, we have with probability at
least $1-2N^{-8}$,

$\left[\left(Q-Q^{(w,G)}\right)^{\top}p^{(w)}\right]_{w}\leq
4\rho(1-\alpha)\sqrt{\frac{\rho\log{N}}{\delta}}\left\|p^{(w)}\right\|_{\infty}.$
(15)

As for any $u\neq w$, applying Hoeffding’s inequality again yields

$\displaystyle\left[\left(Q-Q^{(w,G)}\right)p^{(w)}\right]_{u}$
$\displaystyle=$
$\displaystyle(1-\alpha)\sum_{v=1}^{N}\left(P_{vu}-\mathcal{P}_{vu}\right)p^{(w)}_{v}$
$\displaystyle=$
$\displaystyle(1-\alpha)\left(P_{uu}-P^{(w,G)}_{uu}\right)p^{(w)}_{u}$
$\displaystyle+(1-\alpha)\left(P_{uw}-P^{(w,G)}_{uw}\right)p^{(w)}_{w}$
$\displaystyle=$
$\displaystyle-(1-\alpha)\left(P_{uw}-P^{(w,G)}_{uw}\right)p^{(w)}_{u}$
$\displaystyle+(1-\alpha)\left(P_{uw}-P^{(w,G)}_{uw}\right)p^{(w)}_{w}.$

Recognizing that

$\displaystyle\left|P_{uw}-P^{(w,G)}_{uw}\right|$ $\displaystyle=$
$\displaystyle\left\\{\begin{array}[]{ll}A_{uw}d^{-1}_{uu}-\mathcal{A}_{uw}\mathcal{d}^{-1}_{uu},&(u,w)\in
E,\\\ 0,&(u,w)\notin E,\end{array}\right.$

we apply again the Hoeffding’s inequality (Lemma S4) together with (13), and
obtain with probability at least $1-\mathcal{O}\left(N^{-8}\right)$,

$\left|\left[\left(Q-Q^{(w,G)}\right)^{\top}p^{(w)}\right]_{u}\right|\leq\left\\{\begin{array}[]{ll}4\rho(1-\alpha)\frac{\sqrt{\log{N}}}{\delta}\left\|p^{(w)}\right\|_{\infty},&(u,w)\in
E,\\\ 0,&(u,w)\notin E.\end{array}\right.\\\ $ (17)

Combining (15) and (17) yields

$\displaystyle I^{w}_{211}$ $\displaystyle\leq$ $\displaystyle
4\rho(1-\alpha)\left(1+\sqrt{\sum_{u:u\neq w}\mathds{1}_{(u,w)\in
E}}\right)\sqrt{\frac{\rho\log{N}}{\delta}}\left\|p^{(w)}\right\|_{\infty}$
$\displaystyle\overset{\text{(i)}}{\overset{\text{w.h.p.}}{\leq}}$
$\displaystyle
8\rho^{2}\sqrt{\rho}(1-\alpha)\sqrt{\frac{\log{N}}{\delta}}\left\|p^{(w)}\right\|_{\infty},$

where (i) follows from the high probability event that $d_{\max}\leq
3\rho\delta/2$.

Regarding $I^{w}_{212}$, since $(Q^{(w,G)}-Q^{(w)})\mathcal{p}=\vec{0}$, we
can rewrite this as

$I^{w}_{212}=\left\|\left(Q^{(w,G)}-Q^{(w)}\right)^{\top}\left(p^{(w)}-\mathcal{p}\right)\right\|_{2}.$

Similarly, note that
$P^{(w)}_{vw}-P^{(w,G)}_{vw}=\frac{\mathcal{A}_{vw}}{\mathcal{d}_{v}}\mathds{1}_{(w,v)\notin
E}$, we apply Bernstein’s inequality on $w$-th term inside the vector norm to
obtain that with probability at least $1-2N^{-8}$,

$\displaystyle\left[\left(Q^{(w,G)}-Q^{(w)}\right)\left(p^{(w)}-\mathcal{p}\right)\right]_{w}$
$\displaystyle=$
$\displaystyle(1-\alpha)\sum_{v=1}^{N}\left(P^{(w,G)}_{vw}-P^{(w)}_{vw}\right)\left(p^{(w)}_{v}-\mathcal{p}_{v}\right)$
$\displaystyle=$
$\displaystyle(1-\alpha)\sum_{v=1}^{N}\frac{1}{\mathcal{d}_{v}}\left(p^{(w)}_{v}-\mathcal{p}_{v}\right)\mathds{1}_{(w,v)\notin
E}$ $\displaystyle\overset{\text{w.h.p.}}{\leq}$
$\displaystyle(1-\alpha)\left(4\rho\sqrt{\frac{\rho\log{N}}{\delta}}+\frac{16}{3}\frac{\log{N}}{\delta}\right)\left\|p^{(w)}-\mathcal{p}\right\|_{\infty}.$

For any $u\neq w$, the $u$-th term inside vector norm is

$\displaystyle\left[\left(Q^{(w,G)}-Q^{(w)}\right)\left(p^{(w)}-\mathcal{p}\right)\right]_{u}$
$\displaystyle=$
$\displaystyle(1-\alpha)\sum_{v=1}^{N}\left(P^{(w,G)}_{vu}-P^{(w)}_{vu}\right)\left(p^{(w)}_{v}-\mathcal{p}_{v}\right)$
$\displaystyle=$
$\displaystyle(1-\alpha)\left(P^{(w,G)}_{vv}-P^{(w)}_{uu}\right)\left(p^{(w)}_{u}-\mathcal{p}_{u}\right)$
$\displaystyle+(1-\alpha)\left(P^{(w,G)}_{vw}-P^{(w)}_{uw}\right)\left(p^{(w)}_{w}-\mathcal{p}_{w}\right)$
$\displaystyle=$
$\displaystyle-(1-\alpha)\left(P^{(w,G)}_{vw}-P^{(w)}_{uw}\right)\left(p^{(w)}_{u}-\mathcal{p}_{u}\right)$
$\displaystyle+(1-\alpha)\left(P^{(w,G)}_{vw}-P^{(w)}_{uw}\right)\left(p^{(w)}_{w}-\mathcal{p}_{w}\right).$

Recognizing that

$P^{(w)}_{uw}-P^{(w,G)}_{uw}=\mathcal{A}_{uw}\mathcal{d}^{-1}_{u}\mathds{1}_{(u,w)\notin
E},$

we have from (13) that

$\left|\left[\left(Q^{(w,G)}-Q^{(w)}\right)^{\top}\left(p^{(w)}-\mathcal{p}\right)\right]_{u}\right|\leq
2\mathcal{A}_{uw}\mathcal{d}^{-1}_{u}\mathds{1}_{(u,w)\notin
E}(1-\alpha)\left\|p^{(w)}-\mathcal{p}\right\|_{\infty}.$

Hence, we have with probability at least $1-\mathcal{O}\left(N^{-8}\right)$,

$\displaystyle I^{w}_{212}$ $\displaystyle\leq$
$\displaystyle(1-\alpha)\left(4\rho\sqrt{\rho}\sqrt{\frac{\log{N}}{\delta}}+\frac{16}{3}\frac{\log{N}}{\delta}+2\sqrt{\sum_{u:u\neq
w}\frac{\mathds{1}_{(u,w)\notin
E}}{\mathcal{D}_{uu}^{2}}}\right)\left\|p^{(w)}-\mathcal{p}\right\|_{\infty}$
$\displaystyle\overset{\text{(i)}}{\leq}$
$\displaystyle(1-\alpha)\left(4\rho\sqrt{\rho}\sqrt{\frac{\log{N}}{\delta}}+\frac{16}{3}\frac{\log{N}}{\delta}+2\rho\sqrt{\frac{\rho}{\delta}}\right)\left\|p^{(w)}-\mathcal{p}\right\|_{\infty},$

where (i) follows from the high probability event that $d_{\max}\leq
3\rho\delta/2$. Combining the above two bounds, we have with probability at
least $1-\mathcal{O}\left(N^{-8}\right)$ that

$\displaystyle I^{w}_{21}$ $\displaystyle\leq$
$\displaystyle\sqrt{\alpha+\frac{2\rho}{\delta}}\frac{\sqrt{\kappa}}{\gamma}\left(I^{w}_{211}+I^{w}_{212}\right)$
$\displaystyle\leq$ $\displaystyle
c(1-\alpha)\left(8\rho^{2}\sqrt{\frac{\rho\log{N}}{\delta}}\|p^{(w)}\|_{\infty}+\left(2\rho\sqrt{\frac{\rho}{\delta}}+4\rho\sqrt{\frac{\rho\log{N}}{\delta}}+\frac{16}{3}\frac{\log{N}}{\delta}\right)\|p^{(w)}-\mathcal{p}\|_{\infty}\right)$
$\displaystyle\overset{\text{(i)}}{\leq}$ $\displaystyle
8c\rho^{2}(1-\alpha)\sqrt{\frac{\rho\log{N}}{\delta}}\|\mathcal{p}\|_{\infty}$
$\displaystyle+c(1-\alpha)\left(8\rho^{2}\sqrt{\frac{\rho\log{N}}{\delta}}+2\rho\sqrt{\frac{\rho}{\delta}}+4\sqrt{\frac{\rho\log{N}}{\delta}}+\frac{16}{3}\frac{\log{N}}{\delta}\right)\|p^{(w)}-\mathcal{p}\|_{\infty}$
$\displaystyle\overset{\text{(ii)}}{\leq}$ $\displaystyle
8c\rho^{2}(1-\alpha)\sqrt{\frac{\rho\log{N}}{\delta}}\|\mathcal{p}\|_{\infty}+\frac{c}{2}\|p^{(w)}-\mathcal{p}\|_{\infty}$
$\displaystyle\overset{\text{(iii)}}{\leq}$ $\displaystyle
16c\rho^{2}(1-\alpha)\sqrt{\frac{\rho\log{N}}{\delta}}\|\mathcal{p}\|_{\infty}+c\|p-\mathcal{p}\|_{\infty}.$

where $c=\sqrt{\alpha+\frac{2\rho}{\delta}}\frac{\sqrt{\kappa}}{\gamma}$, and
(i) follows from the triangle inequality
$\left\|p^{(w)}\right\|_{\infty}\leq\left\|p^{(w)}-\mathcal{p}\right\|_{\infty}+\|\mathcal{p}\|_{\infty}$,
and (ii) holds as long as $\delta>c_{0}(1-\alpha)^{2}\log{N}$ for some
$c_{0}>0$ sufficiently large, and (iii) comes from the triangle inequality
$\left\|p^{(w)}-\mathcal{p}\right\|_{\infty}\leq\left\|p^{(w)}-p\right\|_{2}+\|p-\mathcal{p}\|_{\infty}$.

  4. (d)

Now it is left to estimate the last item $I^{w}_{22}$. Note that

$\displaystyle I^{w}_{22}$ $\displaystyle=$
$\displaystyle\sum_{v=1}^{N}\mathds{1}_{(v,w)\in
E}Q_{vw}\left(p^{(w)}_{v}-\mathcal{p}_{v}\right)$ $\displaystyle=$
$\displaystyle\sum_{v=1}^{N}\left[\alpha\mathds{1}_{\\{w=1\\}}+(1-\alpha)\frac{1}{d_{v}}\mathds{1}_{(v,w)\in
E}\right]\left(p^{(w)}_{v}-\mathcal{p}_{v}\right)$ $\displaystyle=$
$\displaystyle\underbrace{\alpha\sum_{v=1}^{N}\mathds{1}_{\\{w=1\\}}\left(p^{(w)}_{v}-\mathcal{p}_{v}\right)}_{:=I^{w}_{221}}+\underbrace{(1-\alpha)\sum_{v=1}^{N}\frac{\mathds{1}_{(v,w)\in
E}}{\mathcal{d}_{v}}\left(p^{(w)}_{v}-\mathcal{p}_{v}\right)}_{:=I^{w}_{222}}$
$\displaystyle+\underbrace{(1-\alpha)\sum_{v=1}^{N}\left(\frac{1}{d_{v}}-\frac{1}{\mathcal{d}_{v}}\right)\mathds{1}_{(v,w)\in
E}\left(p^{(w)}_{v}-\mathcal{p}_{v}\right)}_{:=I^{w}_{223}}.$

Since both $p^{(w)}$ and $\mathcal{p}$ are distribution vector,
$I^{w}_{221}=0$. Then, due to Hoeffding’s inequality (Lemma S4),

$\displaystyle|I^{w}_{222}|$ $\displaystyle\leq$ $\displaystyle
4\rho(1-\alpha)\sqrt{\frac{\rho\log{N}}{\delta}}\left\|p^{(w)}-\mathcal{p}\right\|_{\infty},$
$\displaystyle|I^{w}_{223}|$ $\displaystyle\leq$ $\displaystyle
2\rho(1-\alpha)\sqrt{\frac{\rho\log{N}}{\delta}}\left\|p^{(w)}-\mathcal{p}\right\|_{\infty},$

with probability at least $1-\mathcal{O}\left(N^{-8}\right)$. Thus, we reach
the high probability event

$\displaystyle|I^{w}_{22}|$ $\displaystyle\leq$ $\displaystyle
6\rho(1-\alpha)\sqrt{\frac{\rho\log{N}}{\delta}}\left\|p^{(w)}-\mathcal{p}\right\|_{\infty}.$

In sums, we reach with probability at least
$1-\mathcal{O}\left(N^{-8}\right)$,

$\displaystyle|I^{w}_{2}|$ $\displaystyle\leq$ $\displaystyle
16\rho^{2}(1-\alpha)\frac{\sqrt{\kappa\rho}}{\gamma}\sqrt{\alpha+\frac{2\rho}{\delta}}\sqrt{\frac{\log{N}}{\delta}}\|\mathcal{p}\|_{\infty}$
(18)
$\displaystyle+\left(\frac{\sqrt{\kappa}}{\gamma}\sqrt{\alpha+\frac{2\rho}{\delta}}+6\rho(1-\alpha)\sqrt{\frac{\rho\log{N}}{\delta}}\right)\|p-\mathcal{p}\|_{\infty}.$

  5. (e)

Collecting the preceding bounds (14) and (18) together, we conclude that with
high probability

$\displaystyle\|p-\mathcal{p}\|_{\infty}$ $\displaystyle=$
$\displaystyle\max_{w}|p_{w}-\mathcal{p}_{w}|$ $\displaystyle\leq$
$\displaystyle
c_{2}(1-\alpha)\sqrt{\frac{\log{N}}{\delta}}\|\mathcal{p}\|_{\infty}+c_{3}\|p-\mathcal{p}\|_{\infty},$

as long as $\delta/[(1-\alpha)\log{N}]$ is sufficiently large, which controls
the entrywise error of $p$,

$\frac{\|p-\mathcal{p}\|_{\infty}}{\|\mathcal{p}\|_{\infty}}\leq
c_{1}(1-\alpha)\sqrt{\frac{\log{N}}{\delta}},$ (19)

for some sufficiently large constant $c_{1},c_{2},c_{3}>0$.

Remark. $c_{2}$ and $c_{3}$ are controlled by constants $\rho,\kappa,\gamma$,
which are thereby driven from the model parameters B, $\Theta$, $K$, and $Z$.

  6. (f)

Finally, we accomplish the proof by observing that

$\displaystyle\frac{\|p^{*}-\mathcal{p}^{*}\|_{\infty}}{\|\mathcal{p}^{*}\|_{\infty}}$
$\displaystyle\leq$
$\displaystyle\frac{2\max\left(d_{\min}^{-1},\mathcal{d}_{\min}^{-1}\right)}{\mathcal{d}_{\min}^{-1}}\frac{\|p-\mathcal{p}\|_{\infty}}{\|\mathcal{p}\|_{\infty}}$
$\displaystyle\leq$
$\displaystyle\frac{4\|p-\mathcal{p}\|_{\infty}}{\|\mathcal{p}\|_{\infty}}.$

Above observation together with the inequality (19) allow us to control the
entrywise error of $p^{*}$ as claimed, with probability at least
$1-\mathcal{O}\left(N^{-5}\right)$,

$\frac{\|p^{*}-\mathcal{p}^{*}\|_{\infty}}{\|\mathcal{p}^{*}\|_{\infty}}\leq
c_{2}(1-\alpha)\sqrt{\frac{\log{N}}{\delta}},$

for some sufficiently large constant $c_{2}>0$. ∎

###  S1.3 Concentration inequalities

The following is a standard concentration inequality used throughout the
paper.

######  Lemma S4 (Hoeffding’s inequality).

Let $\\{X_{i}\\}_{1\leq i\leq n}$ be a sequence of independent random
variables where $X_{i}\in[a_{i},b_{i}]$ for each $1\leq i\leq n$, and
$S_{n}=\sum_{i=1}^{n}X_{i}$. Then,

$\mathbb{P}(|S_{n}-\mathbb{E}S_{n}|\geq t)\leq
2\exp\left\\{-\frac{t^{2}}{\sum_{i=1}^{n}(b_{i}-a_{i})^{2}}\right\\}.$

The next lemma is a special case of Chernoff’s bound.

######  Lemma S5 (Chernoff’s bounds).

Let $\\{X_{i}\\}_{1\leq i\leq n}$ be a sequence of independent random
variables, whose sum is $S_{n}$, each having probability $p_{i}$ of being
equal to $a_{i}$, otherwise 0. Define $\mu=\sum_{i}p_{i}a_{i}$. Then, for any
$\epsilon>0$,

$\mathbb{P}\left(X_{i}\geq(1+\epsilon)\mu\right)\leq(1+\epsilon)^{-\epsilon\mu},$
$\mathbb{P}\left(X_{i}\leq(1-\epsilon)\mu\right)\leq(1-\epsilon)^{\epsilon\mu}.$

For the use of this paper, we only invoke a simpler version of Bernstein
inequality.

######  Lemma S6 (Bernstein’s inequality).

Let $\\{X_{i}\\}_{1\leq i\leq n}$ be a sequence of independent random
variables with $|X_{i}|\leq B$ for each $1\leq i\leq n$, and
$S_{n}=\sum_{i=1}^{n}X_{i}$ and $T_{n}=\sum_{i=1}^{n}X_{i}^{2}$. Then, with
probability at least $1-2n^{-a}$,

$|S_{n}-\mathbb{E}[S_{n}]|\leq\sqrt{2a\log
n\mathbb{E}[T_{n}]}+\frac{2a}{3}B\log n$

for any $a\geq 2$.

The proofs of Lemma S4, S5, and S6 can be found in Boucheron et al. (2013),
hence are omitted.

##  Appendix S2 Additional information on model parameters

###  S2.1 Block connectivity matrix B

In the paper, we assume that the block connectivity matrix B corresponds to a
strongly connected graph at block level and is positive definite. These
assumptions asserts the efficacy of PPR clustering and is primarily a
technical assumption sufficient for our theoretical results. In fact, we
require B to represent to a strongly connected graph because this enables the
block-wise PPR vector to have the largest value corresponding to the block of
seed(s) (Lemma 1 in the paper). On the other hand, we impose the positive
definiteness on B because this allows us to intuitively define the notion of
local cluster, yet our statistical theory (i.e., the entrywise control of
sample PPR vector) does not explicitly rely on such positive-definiteness per
se. It is not clear yet whether these constraints are necessary in order for
PPR clustering to function; possible generalizations of them are of research
interest.

We list a few concrete examples showing that (i) if we break the strongly-
connectivity assumption, the PPR clustering can fail, despite a reasonable
teleportation constant, $\alpha=0.15$, but (ii) PPR clustering often works as
hoped even when B is not positive-definite. Throughout, we assume that the
first block is targeted and consider directed graphs with three underlying
blocks ($K=3$). The first two instances of B demonstrates the necessity of the
strongly-connectivity constraint, which ensures the block-wise aPPR vector to
possess the largest first element. The third and forth instances, on the other
hand, indicate that B need not to be positive definite.

####  S2.1.1 Violating the strongly-connective assumption

##### Hierarchy case.

Let the block connectivity matrix

$\textbf{B}=\begin{bmatrix}p&p&p\\\ 0&p&p\\\ 0&0&p\end{bmatrix}$

for some constant $p>0$. $\textbf{B}_{ij}$ is the number (or the probability)
of edges from the $i$-th block to the $j$-th block in population. Then, the
directed graph represented by B is not strongly connected, as block 3 has no
path to the first block. In fact, this graph (specified by upper triangular B)
has a hierarchical structure, where the third block is in the center (or the
highest hierarchy) of the graph, and the member of first block are essentially
satellite from outside. Particularly, edges only come from outsiders to
insiders.

We now perform the PPR clustering on the first cluster. The block-wise
transition matrix is

$\textbf{P}=\begin{bmatrix}1/3&1/3&1/3\\\ 0&1/2&1/2\\\ 0&0&1\end{bmatrix}.$

Then, both B and P are positive definite, with eigenvalues of $(p,p,p)$ and
$(1,1/2,1/3)$ respectively. To ease the calculation, we set $p=3$. Then the
block-wise PPR vector is approximately

$\textbf{p}=(0.209,0.103,0.688),$

and the block-wise aPPR vector is approximately (after adjusting by column
sums of B)

$\textbf{p}^{*}=(0.0698,0.0172,0.0764).$

As shown, neither block-wise PPR vector nor aPPR vector properly recognize the
local cluster 1.

##### Adding a small amount of circulation.

If we add a small quantity to the left bottom element of above B matrix, then
the block connectivity matrix corresponds to a connected graph. To illustrate,
we assign a small value to it, $\textbf{B}_{31}=0.1$, then the new block
connectivity matrix becomes

$\textbf{B}^{\prime}=\begin{bmatrix}p&p&p\\\ 0&p&p\\\ 0.1&0&p\end{bmatrix}.$

To explore the PPR vector, we set $p=3$ once again. In this case,
$\textbf{B}^{\prime}$ has one real eigenvalue ($\approx 4.069$) and two
imaginary eigenvalues. The block-wise PPR vector is approximately

$\textbf{p}=(0.235,0.115,0.650),$

and the block-wise aPPR vector is approximately (after adjusting by column
sums of $\textbf{B}^{\prime}$)

$\textbf{p}^{*}=(0.0755,0.0192,0.0723).$

In this case, the PPR clustering works like a charm.

####  S2.1.2 Violating the positive-definite assumption

Consider again the $K=3$ design with equally distributed block size. We
present two examples breaking the positive-definite assumption on B, where the
PPR cluster still operates properly.

##### Indefinite case.

Given some constants $r>p>0$, define

$\textbf{B}=\begin{bmatrix}p&r&r\\\ r&p&r\\\ r&r&p\end{bmatrix}.$

In this case, the random graphs generated from such configuration of B have a
unique characteristic: two vertices with different block memberships are more
likely to connect than those pairs belonging to the same block. Note that the
three eigenvalues of B are $p+2r$, $p-r$, and $p-r$. Hence, $B$ is an
indefinite matrix (so does the block-wise transition matrix P).

Interestingly, the PPR clustering continues working under this circumstance.
For simplicity, setting $p=3$ and $r=9$, and we articulate the block-wise PPR
vector and aPPR vector. In fact, the block-wise PPR vector is approximately

$\textbf{p}=(0.386,0.306,0.306).$

Since B has homogeneous column sums, it follows that the first element in the
block-wise aPPR vector is also the largest, suggesting the effectiveness of
PPR clustering. The same conclusion hold when we set $p=3$ and $r=99$ (or
$999$).

##### Singular case.

Suppose $p>0$ and let

$\textbf{B}=\begin{bmatrix}0&p&0\\\ p&0&p\\\ 0&p&0\end{bmatrix}.$

In this case, nodes in block 1 only connect with those nodes in block 2, and
the nodes in block 3 only have edges with block 2’s members. Note that B is
singular because three of its eigenvalues are 1, -1, and 0. So does the block-
wise transition matrix. However, the PPR clustering remain effective. In fact,
the block-wise PPR vector and aPPR vector are

$\displaystyle\textbf{p}=(0.345,0.459,0.195)$ and
$\displaystyle\textbf{p}^{*}=\frac{1}{p}(0.345,0.230,0.195).$

In both cases (when B is not positive-definite), the block-wise aPPR vector
correctly assigns the largest value to the first element and thus is still
effective for targeted sampling. These examples suggest a potentially greater
applicability of the PPR clustering under the block model graph.

####  S2.1.3 Comments

Putting together above demonstrations, we briefly comment on B and the PPR
clustering. (i) The strongly-connectivity assumption is essential for the PPR
clustering to be consistent. (ii) The efficacy of PPR clustering is
conditioning on the fact that teleportation constant is sufficiently large. If
we assign an extremely small to it, e.g. $\alpha=0.001$, the PPR clustering
collapses. (iii) Beyond community-like graphs (where B is positive-definite),
the PPR clustering has potential for working on a more general block model
graphs.

###  S2.2 Spectral analysis on graph transition $\mathcal{P}$

In this section, we present a spectral analysis of graph transition matrix,
which demonstrates that (1) under the population DC-SBM, a graph transition
matrix $\mathcal{P}$ has exactly $K$ positive eigenvalues, and $N-K$ zero
eigenvalues, and (2) in a random graph generated from the DC-SBM, the graph
transition matrix $P$ is close to its population, with respect to spectral
norm.

######  Lemma S7 (Eigen-decomposition for $\mathcal{P}$ and P).

Under the population DC-SBM with $K$ blocks and parameters
$\left\\{\textbf{B},Z,\Theta\right\\}$, let $\mathcal{P}\in\mathbb{R}^{N\times
N}$ be the population graph transition matrix and
$\textbf{P}\in\mathbb{R}^{K\times K}$ be the block-wise transition matrix.
Then, $\mathcal{P}$ and P have the same $K$ positive eigenvalues. The
remaining $N-K$ eigenvalues of $\mathcal{P}$ are all zeros. Denote the $K$
positive eigenvalues of both matrices as
$\lambda_{1}\geq\lambda_{2}\geq\cdots...\lambda_{K}\geq 0$, and let
$\mathcal{X}\in\mathbb{R}^{N\times K}$ and $\mathcal{Y}\in\mathbb{R}^{K\times
K}$ contain the left eigenvector of $\mathcal{P}$ and P respectively,
corresponding to $\lambda_{i}$ in their $i$-th column. Then, there exists a
orthogonal matrix $U\in\mathbb{R}^{K\times K}$, such that

  1. cmrmn(a)

$\mathcal{X}^{\top}=\mathcal{D}^{-1/2}\Theta^{1/2}ZU;$ and

  2. cmrmn(b)

$\mathcal{Y}^{\top}=\textbf{D}^{-1/2}U.$

###### Proof.

We follow the proof of Lemma 3.3 in Qin and Rohe (2013). Define
$\textbf{L}=\textbf{D}^{-1/2}\textbf{B}\textbf{D}^{-1/2}$, then
$\textbf{P}=\textbf{D}^{-1/2}\textbf{L}\textbf{D}^{1/2}$. By model assumption,
$\textbf{P}\succ 0$.

Define the graph Laplacian $\mathcal{L=D^{-1/2}AD^{-1/2}}$, then by Lemma 2b,

$\mathcal{L}_{uv}=\frac{\mathcal{A}_{uv}}{\sqrt{\mathcal{d}_{u}\mathcal{d}_{v}}}=\frac{\theta_{u}\theta_{v}\textbf{B}_{z(u)z(v)}}{\sqrt{\mathcal{d}_{u}\mathcal{d}_{v}}}=\frac{\textbf{B}_{z(u)z(v)}\sqrt{\theta_{u}\theta_{v}}}{\sqrt{\textbf{d}_{z(u)}\textbf{d}_{z(v)}}}=[\textbf{L}]_{z(u)z(v)}\sqrt{\theta_{u}\theta_{v}},$

or equivalently,

$\mathcal{L}=\Theta^{1/2}Z\textbf{L}Z^{\top}\Theta^{1/2}.$

Then

$\mathcal{X}^{\top}\Lambda\mathcal{X}^{\prime}=\mathcal{D}^{-1/2}\Theta^{1/2}ZU\Lambda
U^{\top}Z^{\top}\Theta^{1/2}\mathcal{D}^{1/2}=\mathcal{D}^{-1/2}\mathcal{L}\mathcal{D}^{1/2}=\mathcal{D}^{-1}\mathcal{A}=\mathcal{P},$

and

$\mathcal{Y}^{\top}\Lambda\mathcal{Y}^{\prime}=\textbf{D}^{-1/2}U\Lambda
U^{\top}\textbf{D}^{1/2}=\textbf{D}^{-1/2}\textbf{L}\textbf{D}^{1/2}=\textbf{P},$

where $\mathcal{X}^{\prime}=U^{\top}Z^{\top}\Theta^{1/2}\mathcal{D}^{1/2}$ and
$\mathcal{Y}^{\prime}=U^{\top}\textbf{D}^{1/2}$ are right eigenvectors if
$\mathcal{P}$ and P respectively. Recognizing that
$\mathcal{X}^{\top}\mathcal{X}^{\prime}=\mathcal{Y}^{\top}\mathcal{Y}^{\prime}=I_{K}$
completes the proof. ∎

######  Lemma S8.

Let $L$ be a symmetric matrix, let $D$ be a diagonal matrix, and let
$P=D^{-1/2}LD^{1/2}$. If $x$ is an eigenvector of $L$ corresponding to
eigenvalue $\lambda$, then

  1. cmrmn(a)

$D^{-1/2}x$ is a right eigenvector of $P$ with eigenvalue $\lambda$,

  2. cmrmn(b)

$\|P^{\top}P\|=\|L\|^{2}$.

###### Proof.

Let $y=D^{-1/2}x$, then

$Py=D^{-1/2}LD^{1/2}y=D^{-1/2}Lx=\lambda D^{-1/2}x=\lambda y.$

Part a of the lemma follows. To see b, observe that $y$ is also an eigenvector
of $P^{\top}P$ with eigenvalue $\lambda^{2}$. ∎

Lemma S8 implies that $P$ has the same spectral norm of graph Laplacian $L$.
Since $L$ concentrates to $\mathcal{L}$ (see for example Qin and Rohe (2013)
for a proof), we have under a random graph generated from the DC-SBM, the
graph transition matrix $P$ concentrates to its population $\mathcal{P}$ with
respect to spectral norm.

###  S2.3 Teleportation constant $\alpha$

In the paper, we state that a sufficiently large teleportation constant
$\alpha$ enables the entrywise control of sample PPR vector, thus facilitating
the PPR clustering in a random graph. Here, from a practical perspective, we
further illustrate the sensitivity of PPR clustering to $\alpha$, with the
Twitter friendship network. To this end, we investigate the targeted sampling
returned by four configurations of the teleportation constant,
$\alpha\in\\{0.1,0.15,0.25,1/3\\}$, where NBC Politics (@NBCPolitics) is the
seed. The tolerance parameter is fixed, $\epsilon=10^{-7}$, in four targeted
sampling.

Table S1 lists the number of Twitter users we examined and the total number of
users we “reached” (as of August 2019) in four attempts. Here, we examine a
user by retrieving its friend list (after which it gets a positive $p_{u}$
value in Algorithm 3), and reach a user once it appears in a user’s friend
list (at which point, it possesses a positive $r_{v}$ value in Algorithm 3).
Given the same tolerance parameter, varying the teleportation constant largely
affects the number of nodes examined/reached. This demonstrates the role of
teleportation constant in leveraging between the seed preference and the
standard random walk.

Supplementary Table S1: Number of nodes examined/reached by Algorithm 3 with seed node @NBCPolitics and different teleportation constants, and a fixed tolerance parameter $\epsilon=10^{-7}$, as in August 2019. $\alpha$ | Examined | Reached
---|---|---
0.1 | 7,445 | 342,454
0.15 | 5,919 | 272,985
0.25 | 4,860 | 228,561
1/3 | 3,984 | 193,848

Despite the fact that different $\alpha$’s result in substantial difference in
network coverage, when the algorithm stops, the estimated local clusters
appear to share a vast majority in common. To demonstrate this immediately, we
inspect the local clusters of size $n=300$ returned by Algorithm 4 with four
$\alpha$’s and quantify to what degree do they overlap each other. Table S2
shows the percentage of common members between each pair of four returned
local clusters. As shown, most pairs have about 90% overlapping members,
indicating that PPR clustering is fairly robust against the teleportation
constant.

The stability of PPR clustering continues to show when we vary the cluster
size, $n=100,150,...,700$. Figure S1 shows the proportion of common members
across all four local clusters, returned by PPR, aPPR, and rPPR (with the
regularizer $\tau=10$). Overall, the PPR clustering produces a fairly
consistent local cluster, with around 80% of members overlapping across four
different strengths of teleportation (see Supplementary Materials).

Supplementary Table S2: Percentage of pairwise overlapping among three local clusters around @NBCPolitics with different teleportation constants, $\alpha\in\\{0.1,0.15,0.25,1/3\\}$, as in August 2019. $\alpha$ | 0.1 | 0.15 | 0.25 | 1/3
---|---|---|---|---
0.1 | 100% | 92.7% | 89.3% | 87.7%
0.15 |  | 100% | 93.3% | 90%
0.25 |  |  | 100% | 92%
1/3 |  |  |  | 100%
Supplementary Figure S1: Sensitivity to the teleportation constant,
$\alpha=\\{0.1,0.15,0.25,1/3\\}$. Shown are the percentage (left) and number
(right) of common members across all four local clusters returned by three PPR
clustering methods. The targeted sample size increases from 100 to 700 with
the increment of 50.

We conclude that in practice, PPR clustering (i) is mainly influential to the
number of nodes examined in the targeted sampling and (ii) has fairly robust
performance with respect to the choice of teleportation constant.

###  S2.4 The graph size $N$

Supplementary Figure S2:  Entrywise error rate versus the graph sizes. Shown
are relative entrywise error (REE) corresponding to different underlying graph
sizes, averaged over 30 replicates. For each dot, an error bar indicates the
standard error. The RER for aPPR vector is scaled down by a factor of 240 to
improve visualization. The ticks in x-axis are transformed through logarithm
with the natural base.

In the paper, we provide an entrywise error control for the PPR vector and the
aPPR vector (Theorem 2), assuming the edge density is sufficiently large
(i.e., inequality (7) in the main paper). Simulation 3 in Section 5
demonstrates the relationship between the expected degree ($\delta$) and the
error rate of PPR clustering, as promised by the theorem. Here, we provide
another simulation to illustrate Theorem 2. Specifically, we further
investigate the affect of graph size ($N$) on the relative entrywise error
(REE) of the PPR vector
($\frac{\|p-\mathcal{p}\|_{\infty}}{\|\mathcal{p}\|_{\infty}}$), given some
edge density ($\delta$).

We generate 30 replicates of networks of size $N=e^{x}$, where
$x\in\\{6.5,7,7.5,8,8.5,9\\}$, from the four-parameter stochastic block model,
$\text{SBM}(K=3,N,b_{1}=9,b_{2}=3)$. The average expect degree is set to
$\delta=125$. Both PPR vectors and aPPR vectors are calculated for every
network, with teleportation constant $\alpha=0.15$ and $10$ seeds randomly
selected from the first block. Figure S2 depict the REE with respect to
different graph sizes (scaled by a logarithm transformation with the natural
base). As shown, with $\delta$ fixed (not growing at the rate of $\log{N}$),
the REE increases as the graph expands, so does the variance of REE for both
PPR and aPPR vectors, matching the results in Theorem 2.

##  Appendix S3 Connection to linear discriminant analysis

In this section, we give another representation of PPR vectors in the landing
probability space, which builds upon Kloumann et al. (2017). This assorts PPR
to a greater functional regime. Then, we extend the previous result that links
the PPR vectors with linear discriminant functions under the DC-SBM. In
particular, when every block has the same degree (volume), where D becomes a
scalar matrix, the PPR vector is asymptotically equivalent to the optimal
linear discriminant function.

First, we briefly introduce linear discriminant analysis in landing
probability space, which the PPR vector also lives in. Consider a random walk
on the graph starting from a seed node. Define the landing probability
$r_{s}^{v}$ to be the probability that the random walk ends up at $v\in V$
after exactly $s$ steps. The landing probability space is the space of landing
probability of any nodes.

A linear discriminant (LD) analysis keeps the first $S$ landing probability on
each node, $r^{v}=(r^{v}_{0},r^{v}_{1},...,r^{v}_{S})\in\mathbb{R}^{S}$, and
divides vertices into two sets by thresholding on the linear discriminant
score vector $l\in\mathbb{R}^{N}$, whose $v$-th entry is defined to be inner
product

$l_{v}=\langle\omega,r^{v}\rangle$

with some weights $\omega\in\mathbb{R}^{S}$. For example, let
$\omega=r^{v_{1}}-r^{v_{2}}$, where $v_{1}$, $v_{2}$ are empirical centroids
of two node sets. Then $l_{v}$ increases as $v$ slides from $v_{1}$ to
$v_{2}$, and thresholding $(\|v_{1}\|^{2}-\|v_{2}\|^{2})/2$ allocates vertices
to nearest centroid.

Remark. The landing probability of the $s$-th step,
$r_{s}=\left(r^{1}_{s},r^{2}_{s},...,r^{N}_{s}\right)\in\mathbb{R}^{N}$, is
defined as $\left(P^{s}\right)^{\top}\pi$. It follows from proposition 1 that
PPR vector $p=\sum_{s=0}^{\infty}\phi_{s}r_{s}$ with
$\phi_{s}=\alpha(1-\alpha)^{s}$. Keeping the first $S$ terms yields an LD
score vector with the weights
$\omega_{PPR}=(\phi_{0},\phi_{1},...,\phi_{S-1})$.

We then perform population (expectation) analysis for PPR in the landing
probability space. Define the population block landing probability
$\textbf{W}^{k}_{s}$ to be the probability that a random walk from $v_{0}$
ends up in block $k$ after exactly $s$ steps, where $k=1,2,...,K$ and
$s=0,1,...,S-1$. Given that $v_{0}$ is in block 1,
$\textbf{W}^{\cdot}_{0}=(1,0,...,0)^{\top}$. Using the first $S$ steps block
landing probabilities, the next lemma gives an explicit form of LD vectors.

######  Lemma S9 (Explicit form of LD vectors).

Under the population DC-SBM with $K$ blocks and parameters
$\left\\{\textbf{B},Z,\Theta\right\\}$, assume all blocks have the same
degrees. Let $\mathcal{l}(k)$ be the linear discriminant score vector between
block 1 and block $k$. Then,

  1. cmrmn(a)

$\textbf{W}^{\cdot}_{s}=\textbf{P}^{\top}\textbf{W}^{\cdot}_{s-1}$,
$s=1,2,...,S-1$; and

  2. cmrmn(b)

$\mathcal{l}(k)=\Theta Z\textbf{l}(k)$, $k=2,...,K$, where
$\textbf{l}(k)=\textbf{W}\textbf{W}^{\top}(e_{1}-e_{k})$.

Here, $e_{k}$ is the elementary unit vector on the direction of $k$-th block.

###### Proof.