Optimizing Generalized PageRank Methods for Seed-Expansion Community Detection

Introduction

PageRank (PR), an algorithm originally proposed by Page et al. for ranking web-pages has found many successful applications, including community detection , link prediction and recommender system design . The PR algorithm involves computing the stationary distribution of a Markov process by starting from a seed vertex and then performing either a one-step of random walk (RW) to the neighbors of the current seed or jumping to another vertex according to a predetermined probability distribution. The RW aids in capturing topological information about the graph, while the jump probabilities incorporate modeling preferences . A proper selection of the RW probabilities ensures that the stationary distribution induces an ordering of the vertices that may be used to determine the “relevance” of vertices or the structure of their neighborhoods.

Despite the wide utility of PR , recent work in the field has shifted towards investigating various generalizations of PR. Generalized PR (GPR) values enable more accurate characterizations of vertex distances and similarities, and hence lead to improved performance of various graph learning techniques . GPR methods make use of arbitrarily weighted linear combinations of landing probabilities (LP) of RWs of different length, defined as follows. Given a seed vertex and another arbitrary vertex $v$ in the graph, the $k$-step LP of $v$, $x_{v}^{(k)}$, equals the probability that a RW starting from the seed lands at $v$ after $k$ steps; the GPR value for vertex $v$ is defined as $\sum_{k=0}^{\infty}\gamma_{k}x_{v}^{(k)},$ for some weight sequence $\{\gamma_{k}\}_{k\geq 0}$. Certain GPR representations, such as personalized PR (PPR) or heat-kernel PR (HPR), are associated with weight sequences chosen in a heuristic manner: PPR uses traditional PR weights, $\gamma_{k}=(1-\alpha)\alpha^{k},$ for some $\alpha\in(0,1),$ and a seed set that captures locality constraints. On the other hand, HPR uses weights of the form $\gamma_{k}=\frac{h^{k}}{k!}e^{-h},$ for some $h>0$. A question that naturally arises is what are the provably near-optimal or optimal weights for a particular graph-based learning task.

Clearly, there is no universal approach for addressing this issue, and prior work has mostly reported comparative analytic or empirical studies for selected GPRs. As an example, for community detection based on seed-expansion (SE) where the goal is to identify a densely linked component of the graph that contains a set of a priori defined seed vertices, Chung proved that the HPR method produces communities with better conductance values than PPR . Kloster and Gleich confirmed this finding via extensive experiments over real world networks. Avron and Horesh leveraged time-dependent PRs, a convolutional form of HPR and PPR , and showed that this new PR can outperform HPR on a number of real network datasets. Another line of work considered adaptively learning the GPR weights given access to sufficiently many both within-community and out-of-community vertex labels . Related studies were also conducted in other application domains such as web-ranking and recommender system design .

Recently, Kloumann et al. took a fresh look at the GPR-based seed-expansion community detection problem. They viewed LPs of different steps as features relevant to membership in the community of interest, and the GPRs as scores produced by a linear classifier that digests these features. A key observation in this setting is that the GPR weights have to be chosen with respect to the informativeness of these features. Based on the characterization of the mean-field values of the LPs over a modified stochastic block model (SBM) , Kloumann et al. determined that PPR with a proper choice of the parameter $\alpha$ corresponds to the optimal classifier if only the first-order moments are available. Unfortunately, as the variance of the LPs was ignored, the performance of the PPR was shown to be sub-optimal even for synthetic graphs obeying the generative modeling assumptions used in .

We report substantial improvements of the described line of work by characterizing the non-asymptotic behavior of the LPs over random graphs. More precisely, we derive non-asymptotic conditions for the LPs to converge to their mean-field values. Our findings indicate that in the non-asymptotic setting, the discriminative power of $k$-step LPs does not necessarily deteriorate as $k$ increases; this follows since our bounds on the variance decay even faster than the distance between the means of LPs within the same and across two different communities. We leverage this finding and propose new weights that suitably increase with the length of RWs for small values of $k$. This choice differs significantly from the geometrically decaying weights used in PPR, as suggested by .

The reported results may also provide useful means for improving graph neural networks (GNN) and their variants for vertex classification tasks. Currently, the typical numbers of layers in graph neural networks is $2-3$, as such a choice offers the best empirical performance . More layers may over-smooth vertex features and thus provide worse results. However, in this setting, long paths in the graphs may not be properly utilized, as our work demonstrates that these paths may have strong discriminative power for community detection. Hence a natural research direction of research regarding GNNs is to investigate how to leverage long paths over graphs without over-smoothing the vertex features. Concurrent to this work, several empirical studies were performed to address the same problem. The work in used a decoupling non-linear transformation of features and PR propagation over graphs, while used GNNs over graphs that are transformed based on GPRs.

Our contributions are multifold. We derive the first non-asymptotic bound of the distance between LP vectors to their mean-field values over random graphs. This bound allows us to better our understanding of a class of GPR-based community detection approaches. For example, it explains why PPR with a parameter $\alpha\simeq 1$ often achieves good community detection performance and why HPR statistically outperforms PPR for community detection, which matches the combinatorial demonstration proposed previously . Second, we describe the first non-asymptotic characterization of GPRs with respect to their mean-field values over edge-independent random graphs. The obtained results improve the previous analysis of standard PR methods as one needs fewer modeling assumptions and arrives at more general conclusions. Third, we introduce a new PR-type classifier for SE community detection, termed inverse PR (IPR). IPR carefully selects the weights for the first several steps of the RW by taking into account the variance of the LPs, and offers significantly improved SE community detection performance compared to canonical PR diffusions (such as HPR and PPR) over SBMs. Fourth, we present extensive experiments for detecting seeded communities in real large-scale networks using IPR. Although real world networks do not share the properties of SBMs used in our analysis, IPR still significantly outperforms both HPR and PPR for networks with non-overlapping communities and offers performance improvement over two examined networks with overlapping community structures.

Preliminaries

We start by formally introducing LPs, GPR methods, random graphs and other relevant notions.

Some of our subsequent discussion focuses on two-block SBMs. In this setting, we let $C_{1}$, $C_{0}\subset V$ denote the two blocks, such that $|C_{1}|=n_{1}$ and $|C_{0}|=n_{0}$. For any pair of vertices from the same block $u,v\in C_{i}$, we set $p_{uv}=p_{i},$ for some $p_{i}\in(0,1)$, $i\in\{0,1\}$. Note that we allow self loops, i.e. we allow $u=v$, which makes for simpler notation without changing our conclusions. For pairs $uv$ such that $u\in C_{1}$ and $v\in C_{0}$, we set $p_{uv}=q,$ for some $q\in(0,1)$. A two-block SBM in this setting is parameterized by $(n_{1},p_{1},n_{0},p_{0},q)$.

Mean-field Convergence Analysis of LPs and GPRs

Let $\bar{\lambda}=\max\{|\bar{\lambda}_{2}|,|\bar{\lambda}_{n}|\}$. Suppose that $\bar{d}_{\min}=\omega(\log n)$. Then, with high probability, and for some constants $C_{1},\,C_{2},\,C_{3}$ that do not depend on $n$ or $k$, one has

Moreover, let $g(\gamma,\bar{\lambda},\bar{d}_{\min})=\sum_{k\geq 1}\gamma_{k}k\left(\bar{\lambda}+C_{3}\sqrt{\frac{\log n}{\bar{d}_{\min}}}\right)^{k-1}$. Then,

1) If $\|x^{(0)}\|_{2}=O(\frac{1}{\sqrt{n}})$ and $\frac{\bar{d}_{\max}\log n}{\bar{d}_{\min}^{2}}=o(1)$, then for any sequence $\{k^{(n)}\}_{n\geq 0}$, $\|x^{(k^{(n)})}-\bar{x}^{(k^{(n)})}\|_{1}=o(1),\;w.h.p.$; 2) If $\bar{d}_{\min}=\omega(\log n)$ and $\bar{\lambda}<1-c,$ for some $c>0$ and $n\geq n_{0}$ such that $\frac{c}{3}>C_{4}\sqrt{\frac{\log n}{\bar{d}_{\min}}}$ where $n_{0},C_{4}$ are constants, then for any $x^{(0)}$ and sequence $\{k^{(n)}\}_{n\geq n_{0}}$ that satisfies $k^{(n)}\geq(\log n+\log\frac{\bar{d}_{\max}}{\bar{d}_{\min}})/c$, we have $\|x^{(k^{(n)})}-\bar{x}^{(k^{(n)})}\|_{1}=o(1),\;w.h.p.$

1) If $\|x^{(0)}\|_{2}=O(\frac{1}{\sqrt{n}}),$ $\frac{\bar{d}_{\max}\log n}{\bar{d}_{\min}^{2}}=o(1),$ and $\bar{\lambda}<1-c$ for some $c>0,$ then for any weight sequence $\{\gamma^{(n)}\}_{n\geq 0}$ such that $\sum_{k}\gamma_{k}^{(n)}<\infty$, one has $\|pr(\gamma^{(n)},x^{(0)})-\bar{pr}(\gamma^{(n)},x^{(0)})\|_{1}=o(1),\;w.h.p.$ 2) If $\gamma_{0}^{(n)}/\sum_{k}\gamma_{k}^{(n)}\geq C_{5}>0$ for some constant $C_{5},$ $\bar{\lambda}<1-c$ for some $c>0,$ and $\frac{\bar{d}_{\max}\log n}{\bar{d}_{\min}^{2}}=o(1)$, then for any $x^{(0)}$ one has $\frac{\|pr(\gamma^{(n)},x^{(0)})-\bar{pr}(\gamma^{(n)},x^{(0)})\|_{2}}{\|\bar{pr}(\gamma^{(n)},x^{(0)})\|_{2}}=o(1)\;w.h.p.$ 3) If $\bar{d}_{\min}=\omega(\log n)$ and $g(\gamma^{(n)},\bar{\lambda}^{(n)})=\sum_{k\geq 1}\gamma_{k}^{(n)}k(\bar{\lambda}^{(n)}+C_{6})^{k-1}=O(\sqrt{\frac{\bar{d}_{\min}}{n\bar{d}_{\max}}})$ for some constant $C_{6}>0$, then for any $x^{(0)}$ one has $\|pr(\gamma^{(n)},x^{(0)})-\bar{pr}(\gamma^{(n)},x^{(0)})\|_{1}=o(1)\;w.h.p.$

The following lemma uses the same proof techniques as Lemma 3.2 to provide an upper bound on the distance between the DNLPs $z^{(k)}$ and $\bar{z}^{(k)}$, which we find useful in what follows. The result essentially removes the dependence on the degrees in the first term of the right hand side of (1).

Suppose that the conditions of Lemma 3.2 are satisfied. Then, one has

GPR-Based SE Community Detection

One important application of PRs is in SE community detection: For each vertex $v$, the LPs $\{x_{v}^{(k)}\}_{k\geq 0}$ may be viewed as features and the GPR as a score used to predict the community membership of $v$ by comparing it with some threshold . Kloumann et al. investigated mean-field LPs, i.e., $\{\bar{x}_{v}^{(k)}\}_{k\geq 0}$, and showed that under certain symmetry conditions, PPR with $\alpha=\bar{\lambda}_{2}$ corresponds to an optimal classifier for one block in an SBM, given only the first-order moment information. However, accompanying simulations revealed that PPR underperforms with respect to classification accuracy. As a result, Fisher’s linear discriminant was used instead by empirically leveraging information about the second-order moments of the LPs, and was showed to have a performance almost matching that of belief propagation, a statistically optimal method for SBMs .

In what follows, we rigorously derive an explicit formula for a variant of Fisher’s linear discriminant by taking into account the individual variances of the features while neglecting their correlations. This explicit formula provides new insight into the behavior of GPR methods for SE community detection in SBMs and will be later generalized to handle real world networks (see Section 5).

Suppose that the mean vectors and covariance matrices of the features from two classes $C_{0},\,C_{1}$ are equal to $(\mu_{0},\Sigma_{0})$ and $(\mu_{1},\Sigma_{1})$, respectively. For simplicity, assume that the covariance matrices are identical, i.e., $\Sigma_{0}=\Sigma_{1}=\Sigma$. The Fisher’s linear discriminant depends on the first two moments (mean and variance) of the features , and may be written as $F(x)=[\Sigma^{-1}(\mu_{1}-\mu_{0})]^{T}\,x$. The label of a data point $x$ is determined by comparing $F(x)$ with a threshold.

Neglecting the differences in the second order moments by assuming that $\Sigma=\sigma^{2}I$, Fisher’s linear discriminant reduces to $G(x)=(\mu_{1}-\mu_{0})^{T}\,x$, which induces a decision boundary that is orthogonal to the difference between the means of the two classes; $G(x)$ is optimal under the assumptions that only the first-order moments $\mu_{1}$ and $\mu_{0}$ are available.

The two linear discriminants have different practical advantages and disadvantages in practice. On the one hand, $\Sigma$ can differ significantly from $\sigma^{2}I,$ in which case $G(x)$ performs much worse than $F(x)$. On the other hand, estimating the covariance matrix $\Sigma$ is nontrivial, and hence $F(x)$ may not be available in a closed form. One possible choice to mitigate the above drawbacks is to use what we call the pseudo Fisher’s linear discriminant,

where $\text{diag}(\Sigma)$ is the diagonal matrix of $\Sigma$; $\text{diag}(\Sigma)$ preserves the information about variances, but neglects the correlations between the terms in $x$. This discriminant essentially allows each feature to contribute equally to the final score. More precisely, given a feature of a vertex $v,$ say $x_{v}^{(k)},$ its corresponding weight according to $SF(\cdot)$ equals $\frac{\mu_{1}^{(k)}-\mu_{0}^{(k)}}{(\sigma^{(k)})^{2}},$ where $(\sigma^{(k)})^{2}$ denotes the variance of the feature (i.e., the $k$-th component in the diagonal of $\Sigma$). Note that this weight may be rewritten as $\frac{\mu_{1}^{(k)}-\mu_{0}^{(k)}}{\sigma^{(k)}}\times\frac{1}{\sigma^{(k)}}$; the first term is a frequently-used metric for characterizing the predictiveness of a feature, called the effect size , while the second term is a normalization term that positions all features on the same scale.

Next, we derive an expression for $SF(x)$ pertinent to SE community detection, following the setting proposed for Fisher’s linear discriminant in . To model the community to be detected with seeds and the out-of-community portion of a graph respectively, we focus on two-block SBMs with parameters $(n_{1},p_{1},n_{0},p_{0},q)$, and characterize both the means $\mu_{1}$, $\mu_{0}$ and the variances $\text{diag}(\Sigma)$. Note that for notational simplicity, we first work with DNLPs $\{z_{v}^{(k)}\}_{k\geq 0}$ as the features of choice, as they can remove degree-induced noise; the results for LPs $\{x_{v}^{(k)}\}_{k\geq 0}$ are only stated briefly.

2 S​F​(⋅)𝑆𝐹⋅SF(\cdot) Weights and the Inverse PageRank

Choosing the initial seed set to lie within one single community, e.g. $\sum_{v\in C_{1}}x_{v}^{(0)}=1$, and using some algebraic manipulations (see Section C of the Supplement), we obtain

Recall that $\bar{\lambda}_{2}$ stands for the second largest eigenvalue of the mean-field random walk matrix $\bar{W}$. The result in (4) shows that the distance between the means of the DNLPs of the two classes decays with $k$ at a rate $\bar{\lambda}_{2}$. This result is similar to its counterpart in for LPs $\{x_{v}^{(k)}\}_{k\geq 0},$ but the results in additionally requires $\bar{d}_{v}=\bar{d}_{u}$ for vertices $u$ and $v$ belonging to different blocks. By only using the difference $\mu_{1}^{(k)}-\mu_{0}^{(k)}$ without the variance, the authors of proposed to use the discriminant $G(x)=(\mu_{1}-\mu_{0})^{T}\,x$, which corresponds to PPR with $\alpha=\bar{\lambda}_{2}$.

Combining the characterizations of the means and variances, we arrive at the following conclusions.

Inverse PR. As already observed, for finite $n$ and with high probability, $\lambda_{2}$ only slightly exceeds $\bar{\lambda}_{2}$. Moreover, for SBMs with unknown parameters or for real world networks, $\bar{\lambda}_{2}$ may not be well-defined, or it may be hard to compute numerically. Hence, in practice, one may need to use the heuristic value $\bar{\lambda}_{2}=\lambda_{2}=\theta,$ where $\theta$ is a parameter to be tuned. In this case, $SF(\cdot)$ with degree normalization is associated with the weights $\gamma_{k}=\theta^{-k}$, while $SF(\cdot)$ without degree normalization is associated with the weights $\gamma_{k}=\theta^{k}/(\phi+\theta^{k})^{2}$. When $k$ is small, $\gamma_{k}$ roughly increases as $\theta^{-k}$; we term a PR with this choice of weights as the Inverse PR (IPR). Note that IPR with degree normalization may not converge in practice, and LP information may be estimated only for a limited number of $k$ steps. Our experiments on real world networks reveal that a good choice for the maximum value of $k$ is $4-5$ times the maximal length of the shortest paths from all unlabeled vertices to the set of seeds.

Other insights. Note that IPR resembles HPR when $k$ is small and $\gamma_{k}$ increases, as it dampens the contributions of the first several steps of the RW. This result also agrees with the combinatorial analysis in that advocates the use of HPR for community detection. Note that IPR with degree normalization has monotonically increasing weights, which reflects the fact that community information is preserved even for large-step LPs. To some extent, this result can be viewed as a theoretical justification for the empirical fact that PPR is often used with $\alpha\simeq 1$ to achieve good community detection performance .

Experiments

We evaluate the performance of the IPR method over synthetic and large-scale real world networks.

Datasets. The network data used for evaluation may be classified into three categories. The first category contains networks sampled from two-block SBMs that satisfy the assumptions used to derive our theoretical results. The second category includes three real world networks, Citeseer , Cora and PubMed , all frequently used to evaluate community detection algorithms . These networks comprise several non-overlapping communities, and may be roughly modeled as SBMs. The third category includes the Amazon (product) network and the DBLP (collaboration) network from the Stanford Network Analysis Project . These networks contain thousands of overlapping communities, and their topologies differ significantly from SBMs (see Table 1 in the Supplement for more details). For synthetic graphs, we use single-vertex seed-sets; for real world graphs, we select $20$ seeds uniformly at random from the community of interest.

Comparison of the methods. We compare the proposed IPRs with PPR and HPR methods, both widely used for SE community detection . Methods that rely on training the weights were not considered as they require outside-community vertex labels. For all three approaches, the default choice is degree-normalization, indicated by the suffix “-d”. For synthetic networks, the parameter $\theta$ in IPR is set to $\bar{\lambda}_{2}=\frac{0.05-q}{0.05+q},$ following the recommendations of Section 4.2. For real world networks, we avoid computing $\lambda_{2}$ exactly and set $\theta\in\{0.99,0.95,0.90\}$. The parameters of the PPR and HPR are chosen to satisfy $\alpha\in\{0.9,0.95\}$ and $h\in\{5,10\}$ and to offer the best performance, as suggested in . The results for all PRs are obtained by accumulating the values over the first $k$ steps; the choice for $k$ is specified for each network individually.

Evaluation metric. We adopt a metric similar to the one used in . There, one is given a graph, a hidden community $\mathcal{C}$ to detect, and a vertex budget $Q$. For a potential ordering of the vertices, obtained via some GPR method, the top-$Q$ set of vertices represents the predicted community $\mathcal{P}$. The evaluation metric used is $|\mathcal{P}\cap\mathcal{C}|/|\mathcal{C}|$. By default, $Q=|\mathcal{C}|,$ if not specified otherwise. Other metrics, such as the Normalized Mutual Information and the F-score may be used instead, but since they require additional parameters to determine the GPR classification threshold, the results may not allow for simple and fair comparisons. For SBMs, we independently generated $1000$ networks for every set of parameters. For each network, the results are summarized based on $1000$ independently chosen seed sets for each community-network pair and then averaged over over all communities.

Synthetic graphs. In synthetic networks, all three PRs with degree normalization perform significantly better than their unnormalized degree counterparts. Thus, we only present results for the first class of methods in Figure 2 (Left). As predicted in Section 4.2, IPR-d offers substantially better detection performance than either PPR-d and HPR-d, and is close in quality to belief propagation (BP). Note that the recall of IPR-d keeps increasing with the number of steps. This means that even for large values of $k$, the landing probabilities remain predictive of the community structures, and decreasing the weights with $k$ as in HPR and PPR is not appropriate for these synthetic graphs. The classifier $G(x)$, i.e., a PPR with parameters $\frac{p-q}{p+q}$ suggested by , has worse performance than the PPR method with parameter $0.95$ and is hence not depicted.

Citeseer, Cora and PubMed. Here as well, PRs with degree normalization perform better than PRs without degree normalization. Hence, we only display the results obtained with degree normalization. The first line of Figure 2 (Right) shows that IPR-d $0.99$ significantly outperforms both PPR-d and HPR-d for all three networks. Moreover, the performance of IPR-d $0.99$ improves with increasing $k,$ once again establishing that LPs for large $k$ are still predictive. The results for IPR-d $0.90,\,0.95$ and a related discussion are postponed to Section A.1 in the Supplement.

The second line of Figure 2 (Right) illustrates the rankings of vertices within the predicted community given the first $50$ steps of the RW. Note that only for the Citeseer network does PPR provide a better ranking of vertices in the community for small $Q$; for the other two networks, IPR outperforms PPR and HPR on the whole ranking of vertices.

Amazon, DBLP. We first preprocess these networks by following a standard approach described in Section A.2 of the Supplement. As opposed to the networks in the previous two categories, the information in the vertex degrees is extremely predictive of the community membership for this category. Figure 5.1 shows the predictiveness based on one-step LPs and DNLPs for these two networks. As may be seen, degree normalization may actually hurt the predictive performance of LPs for these two networks. This observation coincides with the finding in . Hence, for this case, we do not perform degree normalization. As recommended in Section 4.2, the weights are chosen as $\gamma_{k}=\frac{\theta^{k}}{(\theta^{k}+\phi)^{2}},$ where $\theta,\phi$ are parameters to be tuned. The value of $\phi$ typically depends on how informative the degree of a vertex is. Here, we simply set $\phi=\theta^{10}$ which makes $\gamma_{k}$ achieve its maximal value for $k=10$. We also find that for both networks, $\alpha=0.95$ is a good choice for PPR while for HPR, $h=10$ and $h=5$ are adequate for the Amazon and the DBLP network, respectively.

Further results are listed in Table 5.1, indicating that HPR outperforms other PR methods when $k=5$; HPR is used with parameter $\geq 5$, and the weights for the first $5$ steps in HPR increase. This yet again confirms our findings regarding the predictiveness of large-step LPs. For larger $k$, IPR matches the performance of HPR and even outperforms HPR on the DBLP network. Vertex rankings within the communities are available in Section A.2 of the Supplement.

Discussion and Future Directions

There are many directions that may be pursued in future studies, including: (1) Our non-asymptotic analysis works for relatively dense graphs for which the minimum degree equals $\bar{d}_{\min}=\omega(\log n)$. A relevant problem is to investigate the behavior of GPR over sparse graphs. (2) The derived weights ignore the correlations between LPs corresponding to different step-lengths. Characterizing the correlations is a particularly challenging and interesting problem. (3) Recently, research for network analysis has focused on networks with higher-order structures. PPR and HPR-based methods have been generalized to the higher-order setting . Analysis has shown that these higher-order GPR methods may be used to detect communities of networks that approximates higher-order network (motif/hypergraph) conductance . Related works also showed that PR-based approaches are powerful for practical community detection with higher-order structures . Hence, generalizing our analysis to higher-order structure clustering is another topic for future consideration. A follow-up work on the mean-field analysis of higher-order GPR methods may be found in . (4) Our work provides new insights regarding SE community detection. Re-deriving the non-asymptotic results for other GPR-based applications, including recommender system design and link prediction, is another class of problems of interest. For example, GRP/RW-based approaches are frequently used on commodities-user bipartite graphs of recommender systems. There, one may model the network as a random graph with independent edges that correspond to one-time purchases governed by preference scores of the users. Similarities of vertices can also be characterized by GPRs and used to predict emerging links in networks . In this setting, it is reasonable to assume that the graph is edge-independent but with different edge probabilities. Analyzing how the GPR weights influence the similarity scores to infer edge probabilities may improve the performance of current link prediction methods.

Acknowledgement

This work was supported by the NSF STC Center for Science of Information at Purdue University. The authors also gratefully acknowledge useful discussions with Prof. David Gleich from Purdue University.

References

Appendix A Supplementary Information for Experiments

Table 1 describes the properties of the datasets used in our evaluations in more detail.

For all real world networks, we first extract the largest connected component of each network in the preprocessing step. For Citeseer and Cora, we arrive at a networks with $2,120$ and $2,485$ vertices, respectively. Other networks considered are connected and thus used in their original form.

Figure 3 (Left) demonstrates that for these three networks, PRs with degree normalization perform better than their unnormalized counterparts. Figure 3 (Right) compares IPR-d with different parameters and demonstrates that the performance in the first few steps offered by IPR with $\theta$ equal to $0.95$ and $0.90$ is significantly better than that of IPR with parameter $0.99$, but that it afterwards remains the same or even degrades with increasing $k$. To better understand this phenomenon, we computed the $\lambda_{2}$ value of these three networks, which equal to $0.9985$, $0.995$ and $0.9859$, respectively. As predicted in Section 4.2, setting $\theta=\lambda_{2}$ is helpful for obtaining a stable IPR, while more steps are required to “saturate” the performance. In practice, computing $\lambda_{2}$ for massive networks is time consuming, so we suggest to conservatively select a large $\theta$ and only focus on the first several steps of the random walk. Note that according to our experiments, the averaged maximal lengths of all shortest paths between unlabeled vertices and the seed sets are as follows: Citeseer, $16.0$; Cora, $11.4$; PubMed: $10.6$. Therefore, the recommended choices for $k$ are $80,57$ and $53$, respectively.

A.2 Additional Observations for the Amazon and DBLP Network Evaluations

Note that the evaluation metric we adopt is adequate for communities of similar sizes, which is not the case for the Amazon and DBLP communities. We hence further restrict our choice of community structures to analyze for these two networks. We perform a preprocessing method used in : We select communities closest in size to $m^{3/4}$, where $m$ is the size of the largest community. This leads to $113$ communities with sizes in $$for the Amazon network, and$101$communities with sizes in$$for the DBLP network. For each test, starting from the seed set, we first perform a 4-step (3-step) breadth-first-search to extract a sub-network of the Amazon (DBLP) network. This allows our methods to work locally, and is similar in strategy to the approach adopted in . The obtained sub-networks have$10k$-$40k$vertices and cover, on average, more than 70$4$; for DBLP,$3$. Therefore, accumulating over the first$15-20$ steps of the RW is appropriate. Using the obtained sub-networks, we evaluated different GPR approaches.

Figure 4 further illustrates the rankings of vertices within the predicted communities after accumulating the results of the first $20$ LPs. Note that for the Amazon network, all three PRs give similar ranking results while for the DBLP network, IPR with parameter $0.9$ outperforms the other two PRs. Again, according to the results for the DBLP network, PPR performs well when ranking vertices with small budgets $Q$.

Appendix B Proofs of the Results in Section 3

Moreover, as $|d_{v}-\bar{d}_{v}|=|\sum_{u\in V}(A_{uv}-p_{uv})|$, using Bernstein’s inequality once again, we conclude that

Therefore, with probability at least $1-3e^{-\frac{\epsilon^{2}}{10}\bar{d}_{v}}$, it holds that

where $a)$ follows from plugging in (5) and (6) into the underlying expression, $b)$ is a consequence of the fact that $\sum_{u\in V}p_{uv}^{2}\leq\frac{(\sum_{u\in V}p_{uv})^{2}}{n}=\frac{\bar{d}_{v}^{2}}{n}$ and $c)$ follows from $\bar{d}_{v}\leq n(1-\epsilon)$. As $\bar{d}_{v}=\omega(1)$, the above probability converges to $1$ as $n\rightarrow\infty$.

B.2 Proof of Lemma 3.2 and Lemma 3.5

Before proving Lemma 3.2 and Lemma 3.5 we introduce some useful notation. For a graph with adjacency matrix $A$ and degree matrix $D$, the Randić matrix is defined as $R=D^{-\frac{1}{2}}AD^{-\frac{1}{2}}$. Denote its mean-field value by $\bar{R}=\bar{D}^{-\frac{1}{2}}\bar{A}\bar{D}^{-\frac{1}{2}}$. It is straightforward to see that the eigenvalues of the RW matrix $W$ of an undirected graph are the same as those of $R$. Furthermore, let $d_{N}$ be the normalized degree vector of $G$, i.e., $d_{N,v}=d_{v}/\sum_{u\in V}d_{u}$, and let $D_{N}$ be the normalized diagonal degree matrix, i.e., $D_{N}=(\sum_{u\in V}d_{u})^{-1}D$. The spectral norm of a matrix $M$ is denoted by $\|M\|_{2}$. Throughout the Supplement, we also use $\lesssim$ to indicate that the upper bound ignores multiplicative constants.

For any edge-independent random graph, if $\bar{d}_{\min}=\omega(\log n),$ there exist a constant $C$ and $b\in\{0.5,1\}$ such that

Based on the Bernstein’s inequality, we have

Note that $\sum_{u\in V}(A_{vu}-p_{vu})=\sum_{u\in V}A_{vu}-\sum_{u\in V}p_{vu})=d_{v}-\bar{d}_{v}$. By dividing both sides by $\bar{d}_{v}$ and using the union bound, we have

Moreover, choosing $c>3$ and observing that for all $v\in V$, $\bar{d}_{v}-c\sqrt{\bar{d}_{v}\log n}\leq d_{v}\leq\bar{d}_{v}+c\sqrt{\bar{d}_{v}\log n}\,\,w.h.p.$, we have $-\frac{c}{2}\sqrt{\log n}\lesssim d_{v}^{\frac{1}{2}}-\bar{d}_{v}^{\frac{1}{2}}\lesssim\frac{c}{2}\sqrt{\log n}\,\,w.h.p.$ This proves the claimed result. ∎

For any edge-independent random graph model, if $\bar{d}_{\min}=\omega(\log n)$, then

Let $d_{N}^{\prime}=(\frac{d_{v}}{\sum_{u\in V}\bar{d}_{u}})_{v\in V}$. Then,

We separately establish bounds on the two terms of the sum. First,

where $a)$ follows from Bernstein’s inequality and $b)$ from Cauchy’s inequality. Second,

$w.h.p.$, where $a)$ is a consequence of Lemma B.1. Combining the two above results establishes the claim. ∎

Let $d_{N}^{\frac{1}{2}}$ be the vector obtained by taking the square root of the elements in the vector $d_{N}$. If $\bar{d}_{\min}=\omega(\log n)$, then

where $a)$ follows from $1+(d_{N}^{\frac{1}{2}})^{T}\bar{d}_{N}^{\frac{1}{2}}\leq 2$. To bound $\|d_{N}^{\frac{1}{2}}-\bar{d}_{N}^{\frac{1}{2}}\|_{2}$, let $d_{N}^{{}^{\prime}\frac{1}{2}}=(\frac{d_{v}^{\frac{1}{2}}}{\sqrt{\sum_{u\in V}\bar{d}_{u}}})_{v\in V}$. Then,

We establish bounds for the two terms as:

where $a)$ is a consequence of Bernstein’s inequality while $b)$ only includes the dominant term, and

where $a)$ is again a consequence of Bernstein’s inequality while $b)$ only includes the dominant term. Hence, we have $\|d_{N}^{\frac{1}{2}}-\bar{d}_{N}^{\frac{1}{2}}\|_{2}\lesssim\sqrt{\frac{\log n}{\bar{d}_{\min}}}\,w.h.p.$, as claimed. ∎

The next result can be obtained by invoking Theorem 2 of .

If $\bar{d}_{\min}=\omega(\log n)$, then there exists some constant $C_{4}$ such that

Moreover, recall that $\bar{\lambda}=\max\{|\bar{\lambda}_{2}|,|\bar{\lambda}_{n}|\}$ and let $\lambda=\max\{|\lambda_{2}|,|\lambda_{n}|,$ $|\bar{\lambda}_{2}|,|\bar{\lambda}_{n}|\}$. Using Weyl’s Theorem , one has $\lambda\leq\bar{\lambda}+C_{4}\sqrt{\frac{\log n}{\bar{d}_{\min}}}\,w.h.p.$

Now, let us turn our attention to proving Lemma 3.2. First, let $W_{N}=W-d_{N}\mathbf{1}^{T}$ and $\bar{W}_{N}=\bar{W}-\bar{d}_{N}\mathbf{1}^{T}$. It is easy to check that $W_{N}(x-d_{N})=W_{N}x=Wx-d_{N}$. Moreover, as $W_{N}d_{N}=d_{N}$, we have

Let $d_{N}^{\frac{1}{2}}$ be the vector obtained by taking the square root of the elements in the vector $d_{N}$ and define $R_{N}=R-d_{N}^{\frac{1}{2}}(d_{N}^{\frac{1}{2}})^{T}$. Then, $W_{N}=D^{\frac{1}{2}}R_{N}D^{-\frac{1}{2}}$. Note that $R_{N}$ essentially equals the Randić matrix with its first principle component removed. Then,

where $a)$ is a consequence of the triangle inequality, $b)$ is based on inequality (8) and Lemma B.1 that guarantees $d_{\max}\lesssim\bar{d}_{\max}$ and $\bar{d}_{\min}\lesssim d_{\min}$, and $c)$ follows from Lemma B.1, Lemma B.3 and Lemma B.4. To prove the first inequality, we observe that

where $a)$ is a consequence of (7) and $b)$ follows based on Lemma B.2 and the inequality (9). This proves the first inequality in Lemma 3.2. Since we have $\|pr(\gamma,x^{(0)})-\bar{pr}(\gamma,x^{(0)})\|_{2}\leq\sum_{k=0}^{\infty}\gamma_{k}\|x^{(k)}-\bar{x}^{(k)}\|_{2},$ the bound for $\|pr(\gamma,x^{(0)})-\bar{pr}(\gamma,x^{(0)})\|_{2}$ may be derived by using an analysis similar to the one applied to $\|x^{(k)}-\bar{x}^{(k)}\|_{2}$.

Lemma 3.5 may be established in a similar manner. However, due to degree normalization, one can remove the dependence on $\|d_{N}-\bar{d}_{N}\|_{2}$. Recall once again the definition of the DNLPs $z^{(k)}$ and the normalized degree matrix $D_{N}$, which allow us to write $z^{(k)}=D_{N}^{-1}x^{(k)}$. The LHS of the result in Lemma 3.5 may be rewritten as

where $a)$ follows from (7), $b)$ is a consequence of Lemma B.1 and c) is based on the same arguments used to establish (9).

B.3 Proof of Theorem 3.3

First, we note that $\|x^{(k)}-\bar{x}^{(k)}\|_{1}\leq\sqrt{n}\|x^{(k)}-\bar{x}^{(k)}\|_{2}$. Based on Lemma 3.2, it is easy to see that if $\|x^{(0)}\|_{2}=O(\frac{1}{\sqrt{n}})$, $\frac{\bar{d}_{\max}\log n}{\bar{d}_{\min}^{2}}=o(1)$, one has $\|x^{(k^{(n)})}-\bar{x}^{(k^{(n)})}\|_{1}=o(1)\;w.h.p.$

If $\bar{\lambda}<1-c$, $\frac{c}{3}>C_{4}\sqrt{\frac{\log n}{\bar{d}_{\min}}}$ and $k^{(n)}\geq\frac{\log n+\log\frac{\bar{d}_{\max}}{\bar{d}_{\min}}}{c}$, then for large enough $n$,

In this case, we also have $\|x^{(k^{(n)})}-\bar{x}^{(k^{(n)})}\|_{1}=o(1)\;w.h.p.$

B.4 Proof of Theorem 3.4

The result in 1) is a consequence of Lemma 3.2,

Suppose that $\sum_{k\geq 1}\gamma_{k}^{(n)}\leq B$ for large enough $n$. Then,

As $\gamma_{0}^{(n)}\geq C_{5}\sum_{k}\gamma_{k}^{(n)}$, we have $\|\bar{pr}(\gamma^{(n)},x^{(0)})\|_{2}\geq C_{5}\|x^{(0)}\|_{2}$. Hence,

Lemma 3.2 ensures that the result in 2) is met. The result in 3) is again a consequence of Lemma 3.2 because

and for large enough $n$, $\bar{\lambda}+C_{4}\sqrt{\log n/\bar{d}_{\min}}\leq\bar{\lambda}+C_{6}.$

Appendix C Derivation of the Means

For notational simplicity, we let $\beta_{1}=\frac{n_{1}p_{1}}{n_{1}p_{1}+n_{0}q}$ and $\beta_{0}=\frac{n_{0}p_{0}}{n_{1}q+n_{0}p_{0}}$. Furthermore, we use $P_{i}^{(k)}=\sum_{v\in C_{i}}\bar{x}_{v}^{(k)}$, $i\in\{0,1\}$ to denote the sum of $k$-step LPs within the block $C_{i}$. Due to the symmetry, $\{P_{i}^{(k)}\}_{i\in\{0,1\}}$ may be obtained from the following recursion, with initial conditions $[P_{1}^{(0)},\,P_{0}^{(0)}]=[1,\,0]$:

Consequently, $\mu_{1}^{(k)}=\bar{z}_{v}^{(k)}=\frac{\bar{x}_{v}^{(k)}}{\bar{d}_{v}}=\frac{P_{1}^{(k)}/n_{1}}{n_{1}p_{1}+n_{0}q}$ and $\mu_{0}^{(k)}=\frac{P_{0}^{(k)}/n_{0}}{n_{0}p_{0}+n_{1}q}$. It is straightforward to show that the matrix $W^{\prime}$ has eigenvalues $1$ and $\beta_{1}+\beta_{0}-1,$ and that $\beta_{1}+\beta_{0}-1$ equals $\bar{\lambda}_{2}$ of the mean-field random walk matrix $\bar{W}$. Combining $\mu_{1}^{(k)}$, $\mu_{0}^{(k)}$ and $\bar{\lambda}_{2}=\beta_{1}+\beta_{0}-1$, we arrive at the result of equation (4).