Link prediction for partially observed networks

Introduction

A variety of data in many different fields can be described by networks. Examples include friendship and social networks, food webs, protein-protein interaction and gene regulatory networks, the World Wide Web, and many others.

One of the fundamental problems in network science is link prediction, where the goal is to predict the existence of a link between two nodes based on observed links between other nodes as well as additional information about the nodes (node covariates) when available (see , and for recent reviews). Link prediction has wide applications. For example, recommendation of new friends or connections for members is an important service in online social networks such as Facebook. In biological networks, such as protein-protein interaction and gene regulatory networks, it is usually time-consuming and expensive to test existence of links by comprehensive experiments; link prediction in these biological networks can provide specific targets for future experiments.

There are two different settings under which the link prediction problem is commonly studied. In the first setting, a snapshot of the network at time $t$, or a sequence of snapshots at times $1,...,t$, is used to predict new links that are likely to appear in the near future (at time $t+1$). In the second setting, the network is treated as static but not fully observed, and the task is to fill in the missing links in such a partially observed network. These two tasks are related in practice, since a network evolving over time can also be partially observed and a missing link is more likely to emerge in the future. From the analysis point of view, however, these settings are quite different; in this paper, we focus on the partially observed setting and do not consider networks evolving over time.

There are several types of methods for the link prediction problem in the literature. The first class of methods consists of unsupervised approaches based on various types of node similarities. These methods assign a similarity score $s(i,j)$ to each pair of nodes $i$ and $j$, and higher similarity scores are assumed to imply higher probabilities of a link. Similarities can be based either on node attributes or solely on the network structure, such as the number of common neighbors; the latter are known as structural similarities. Typical choices of structural similarity measures include local indices based on common neighbors, such as the Jaccard index or the Adamic-Adar index , and global indices based on the ensemble of all paths, such as the Katz index and the Leicht-Holme-Newman Index . Comprehensive reviews of such similarity measures can be found in and .

Another class of approaches to link prediction includes supervised learning methods that use both network structures and node attributes. These methods treat link prediction as a binary classification problem, where the responses are $\{1,0\}$ indicating whether there exists a link for a pair, and the predictors are covariates for each pair, which are constructed from node attributes. A number of popular supervised learning methods have been applied to the link prediction problem. For example, and use the support vector machine with pairwise kernels, and compares the performance of several supervised learning methods. Other supervised methods use probabilistic models for incomplete networks to do link prediction, for example, the hierarchical structure models , latent space models , latent variable models , and stochastic relational models .

Our approach falls in the supervised learning category, in the sense that we make use of both the node similarities and observed links. However, one difficulty in treating link prediction as a straightforward classification problem is the lack of certainty about the negative and positive examples. This is particularly true for negative examples (absent edges). In biological networks in particular, there may be no certain negative examples at all . For instance, in a protein-protein interaction network, an absent edge may not mean that there is no interaction between the two proteins – instead, it may indicate that the experiment to test that interaction has not been done, or that it did not have enough sensitivity to detect the interaction. Positive examples could sometimes also be spurious – for example, high-throughput experiments can yield a large number of false positive protein-protein interactions . Here we propose a new link prediction method that allows for the presence of both false positive and false negative examples. More formally, we assume that the network we observe is the true network with independent observation errors, i.e., with some true edges missing and other edges recorded erroneously. The error rates for both kinds of errors are assumed unknown, and in fact cannot be estimated under this framework. However, we can provide rankings of potential links in order of their estimated probabilities, for node pairs with observed links as well as for node pairs with no observed links. These relative rankings rather than absolute probabilities of edges are sufficient in many applications. For example, pairs of proteins without observed interactions that rank highly could be given priority in subsequent experiments. To obtain these rankings, we utilize node covariates when available, and/or network topology based on observed links.

The rest of the paper is organized as follows. In Section 2, we specify our (rather minimal) model assumptions for the network and the edge errors. We propose link ranking criteria for both directed and undirected networks in Section 3. The algorithms used to optimize these criteria are discussed in Section 4. In Section 5 we compare performance of proposed criteria to other link prediction methods on simulated networks. In Section 6, we apply our methods to link prediction in a protein-protein interaction network and a school friendship network. Section 7 concludes with a summary and discussion of future directions.

The network model

A network with $n$ nodes (vertices) can be represented by an $n\times n$ adjacency matrix $A=[A_{ij}]$, where

We will consider the link prediction problem for both undirected and directed networks. Therefore $A$ can be either symmetric (for undirected networks) or asymmetric (for directed networks).

where $\alpha$ and $\beta$ are the probabilities of correctly recording a true edge and an absent edge, respectively. Note that we assume that this probability is constant and does not depend on $i$, $j$, or $P_{ij}$. Then we have

If the values of $\alpha$, $\beta$ and $P_{ij}$ were known, then the probabilities of true edges conditional on the observed adjacency matrix could have been estimated as

Link prediction criteria

The key assumption we make is that if two pairs of nodes are similar to each other, the probability of links within these two pairs are also similar. Specifically, in Figure 1, $P_{ij}$ and $P_{i^{\prime}j^{\prime}}$ are assumed close in value if node $i$ is similar to node $i^{\prime}$ and node $j$ is similar to node $j^{\prime}$. For directed networks, we measure similarity of node pairs $(i,i^{\prime})$ and $(j,j^{\prime})$ by the product $W_{ii^{\prime}}W_{jj^{\prime}}$ (see Figure 1), which implies two pairs are similar only if both pairs of endpoints are similar. This assumption should not to be confused with a different assumption made by many unsupervised link prediction methods, which assume that a link is more likely to exist between similar nodes, applicable to networks with assortative mixing. Assortative networks are common – a typical example is a social network, where people commonly tend to be friends with those of similar age, income level, race, etc. However, there are also networks with disassortative mixing, in which the assumption that similar pairs are more likely to be connected is no longer valid – for example, predators do not typically feed on each other in a food web. Our assumption, in contrast, is equally plausible for both assortative and disassortative networks, as well as more general settings, as it does not assume anything about the relationship between $P_{ij}$ and $W_{ij}$.

In some applications, we may have additional information about true positive and negative examples, i.e., some $A_{ij}$’s may be known to be true 1’s and true 0’s, while others may be uncertain. This could happen, for example, when validation experiments have been conducted on a subset of a gene or protein network inferred from expression data. If such information is available, it makes sense to use it, and we can then modify criterion (5) as follows:

where $E_{ij}=1$ if it is known that $A_{ij}=A^{True}_{ij}$, and 0 otherwise. This is similar to a semi-supervised criterion proposed in . However, did not consider the uncertainty in positive and negative examples, nor did they consider the undirected case which we discuss next. Since (6) only involves a partial sum of the loss function terms, we will refer to (6) as the partial-sum criterion and (5) as the full-sum criterion for the rest of the paper.

2 Link prediction for undirected networks

For undirected networks, our key assumption that $P_{ij}$ and $P_{i^{\prime}j^{\prime}}$ are close if two pairs $(i,i^{\prime})$ and $(j,j^{\prime})$ are similar needs to take into account that the direction no longer matters; thus the pairs are similar if either $i$ is similar to $i^{\prime}$ and $j$ is similar to $j^{\prime}$, or if $i$ is similar to $j^{\prime}$ and $j$ is similar to $i^{\prime}$ (see Figure 2. Thus we need a new pair similarity measure that combines $W_{ii^{\prime}}W_{jj^{\prime}}$ and $W_{ij^{\prime}}W_{ji^{\prime}}$. There are multiple options; for example, two natural combinations are

Empirically, we found that $S_{2}$ performs better than $S_{1}$ for a range of real and simulated networks. The reason for this can be easily illustrated on the stochastic block model. The stochastic block model is a commonly used model for networks with communities, where the probability of a link only depends on the community labels of its two endpoints. Specifically, given community labels $c=\{c_{1},\dots,c_{n}\}$, $A^{True}_{ij}$’s are independent Bernoulli random variables with

where $S=[S_{ab}]$ is a $K\times K$ symmetric matrix, and $K$ is the number of communities in the network. Suppose we have the best similarity measure we can possibly hope to have based on the truth, $W_{ij}=I(c_{i}=c_{j})$, where $I$ is the indicator function. In that case, (7) implies $P_{ij}=P_{i^{\prime}j^{\prime}}$ if $\max(W_{ii^{\prime}}W_{jj^{\prime}},W_{ij^{\prime}}W_{ji^{\prime}})=1$, whereas the sum of the weights would be misleading.

Similarly to the directed case, if we have information about true positive and negative examples, we can use a partial-sum criterion

where $E_{ij}=1$ if it is known that $A_{ij}=A^{True}_{ij}$, otherwise $E_{ij}=0$.

3 Node similarity measures

The last component we need to specify is the node similarity matrix $W$. One typical situation is when we have reasons to believe that the external node covariates are related to the structure of the network, in which case it is natural to use covariate information to construct $W_{ii^{\prime}}$. Though more complicated formats do exist, node covariates are typically represented by an $n\times p$ matrix $X$ where $X_{ik}$ is the value of variable $k$ on node $i$. Then $W_{ii^{\prime}}$ can be taken to be some similarity measure between the $i$-th and $i^{\prime}$-th rows of $X$. For example, if $X$ contains only numerical variables and has been standardized, we can use the exponential decay kernel,

where $\|\cdot\|$ is the Euclidean vector norm.

When node covariates are not available, node similarity $W_{ii^{\prime}}$ is usually obtained from the topology of the observed network $A$, i.e., $W_{ii^{\prime}}$ is large if $i$ and $i^{\prime}$ have a similar pattern of connections with other nodes. For undirected networks, a simple choice of $W_{ii^{\prime}}$ could be

where $|\cdots|$ denotes cardinality of a set. This particular measure turns out to be not very useful: since most real networks are sparse, most entries of any $k$-th column will be 0, and thus most of $W_{ii^{\prime}}$’s would be large. A more informative measure is the Jaccard index ,

where $N(i)=\{k:A_{ik}=1\}$ is the set of neighbors of node $i$.

The directed networks case is similar, except we need to count the in and the out links separately. The formulas corresponding to (10) and (11) become

where $N_{1}(i)=\{k:A_{ik}=1\}$ and $N_{2}(i)=\{k:A_{ki}=1\}$.

Optimization algorithms

The proposed link prediction criteria are convex and quadratic in parameters, and thus optimization is fairly straightforward. The obvious approach is to treat the matrix $f$ as a long vector with $n^{2}$ elements (or $n(n-1)/2$ in the undirected case), and solve the linear system obtained by taking the first derivative of any criterion above with respect to this vector. However, solving a system of linear equations could be challenging for large-scale problems ; the number of parameters here is $O(n^{2})$, and so the linear system requires $O(n^{4})$ memory. However, if $W$ is sparse, or sparsified by applying thresholding or some other similar method, then solving the linear system is the efficient choice.

If the $W$ matrix is not sparse, an iterative algorithm with sequential updates that only requires $O(n^{2})$ memory would be a better choice than solving the linear system. We propose an iterative algorithm following the idea of block coordinate descent . A block coordinate descent algorithm partitions the coordinates into blocks and iteratively optimizes the criterion with respect to each block while holding the other blocks fixed.

First, we derive the update equations for directed networks. Note (5) and (6) can be written in the general form

Let $D$ be an $n\times n$ diagonal matrix with $D_{ii}=\sum_{j}W_{ij}$. Then

Plugging (13) and (14) into (12), and taking the first derivative of $Q$ with respect to $f_{i\cdot}$, we obtain

Solving $\frac{\partial Q}{\partial f_{i\cdot}}=0$ with respect to $f_{i\cdot}$, we obtain the updating formula

where $f_{i\cdot}^{(t)}$ is the value of $f_{i\cdot}$ at iteration $t$.

This update is fast to compute but its derivation relies on the product form of $W_{ii^{\prime}}$ and $W_{jj^{\prime}}$, and thus is not directly applicable in the undirected case, where $S_{2}$ is used as the similarity measure. However, we can still approximate $S_{2}$ with a product, using the fact that for $x\geq 0,y\geq 0$, $\lim_{q\rightarrow\infty}\sqrt[q]{x^{q}+y^{q}}=\max(x,y)$. Thus, for sufficiently large $q$, we have

Further, $W^{q}$ is a monotone transformation of $W$ and can also serve as a similarity measure. Based on (17), we propose to substitute the following approximate criterion for undirected networks,

where $V_{ij}\equiv 1$ for the full sum criterion and $V_{ij}=E_{ij}$ for the partial sum criterion. By symmetry,

This is now in the same form as (12), with each term in the sum containing a product of $W_{ii^{\prime}}$ and $W_{jj^{\prime}}$, and therefore (18) can be solved by block coordinate descent with an analogous updating equation as that in the directed network case.

In practice, we found that when $W$ is sparse or truncated to be sparse, solving the linear system can be much faster than the block coordinate descent method; however, when $W$ is dense and the number of nodes is reasonably large, the block coordinate descent method dominates directly solving linear equations.

Simulation studies

In this section, we test performance of our link prediction methods on simulated networks. In all cases, each network consists of $n=1000$ nodes, and node $i$’s covariates $X_{i}$ are independently generated from a multivariate normal distribution $N_{p}(0,I_{p})$ with $p=5$. Each $A_{ij}^{True}$ is generated independently, with $\mbox{logit}P_{ij}=f(X_{i},X_{j})$. We consider the following functions $f(X_{i},X_{j})$:

The right hand column gives sparser versions of functions in the left hand column (subtracting a constant within the logit link functions lowers the overall degree), which we use to compare dense and sparse networks (the average degrees of all these networks are reported in Figures 3 and 4). Functions (a) and (b) are asymmetric in $X_{i}$ and $X_{j}$, giving directed networks, while (c) and (d) are symmetric functions corresponding to undirected networks. Further, $(a)$ and $(c)$ are linear functions; $(b)$ is the projection model proposed in , under which the link probability is determined by the projection of $X_{i}$ onto the direction of $X_{j}$, and $(d)$ is an undirected version of the projection model.

We also generate indicators $E_{ij}$’s as independent Bernoulli variables taking values 1 and 0 with equal probability, and set $A_{ij}=E_{ij}A^{True}_{ij}$. This setup corresponds to the “partially observed” network of the title, where all the observed edges are true but the missing edges may or may not be true 0s.

Since we have node covariates affecting the probabilities of links in this case, we define the similarity matrix $W$ by

where we choose $\sigma=\frac{1}{4}\mbox{median}\{\|X_{i}-X_{i^{\prime}}\|,i=1,...,n,i^{\prime}=1,...,n\}$. After truncating $W$ at 0.1, we optimize all criteria by solving linear equations, with $\lambda$ chosen by 5-fold cross validation.

The performance of link prediction is evaluated on the “test” set $\{(i,j):E_{ij}=0\}$. We report ROC curves, which only depend on the rankings of the estimates $\hat{f}_{ij}$ rather than their numerical values. Specifically, let $R_{ij}$ be the ranking of $\hat{f}_{ij}$ on the test set in descending order. For any integer $k$, we define false positives as pairs $(i,j)$ ranked within top $k$ but without links in the true network ($A_{ij}^{True}=0$), and true positives as pairs ranked within top $k$ with $A_{ij}^{True}=1$. Then the true positive rate (TPR) and the false positive rate (FPR) are defined by

The ROC curves showing the false positive rate vs. the true positive rate over a range of $k$ values are shown in Figures 3 (directed networks) and 4 (undirected networks). Each curve is the average of 20 replicates. We also show the ROC curve constructed from true $P_{ij}$’s as a benchmark..

Overall, both the full sum and the partial sum criteria perform well. There is little difference between directed network models and their undirected versions. As expected, the partial sum criterion always gives better results since it has more information and only uses the true positive and negative examples for training. But its performance is quite comparable to the completely unsupervised full sum criterion, except perhaps for model $(c)$. The gaps between the unsupervised full sum criterion and semi-supervised partial sum criterion become smaller for sparse networks, as the false negatives in the full sum are only a small proportion of the large number of true negatives in a sparse network. The ROC curve obtained from the true model in sparse networks is better than in the corresponding dense networks; this seemingly counter-intuitive finding is also explained by the large number of 0s in sparse networks. However, gaps between both our link prediction methods and the true model are larger in all the sparse networks than in their dense counterparts. This confirms the observation that a small number of positive examples in sparse networks makes the link prediction problem challenging.

Applications

Our first application is to an undirected network containing yeast protein-protein interactions from . This network was edited to contain only highly reliable interactions supported by multiple experiments , resulting in 984 protein nodes and 2438 edges, with the average node degree about 5. We take this verified network to be the true underlying network $A^{True}$. also constructed a matrix measuring similarities between proteins based on gene expression, protein localization, phylogenetic profiles and yeast two-hybrid data, which we use as the node similarity matrix $W$ for link prediction.

Here, we compare the full sum criterion (8), the partial sum criterion (9), and the latent variable model proposed by . To test prediction, we generate indicators $E_{ij}$’s as independent Bernoulli variables taking value 1 with probability $\alpha$, and set $A_{ij}=E_{ij}A^{True}_{ij}$. We consider three different values of $\alpha$, $\alpha=0.2,0.5,0.8$, corresponding to different amounts of available information.

We use the block coordinate descent algorithm proposed in Section 4 to approximately optimize (8) and (9), with $q=10$ and $\lambda$ chosen by cross-validation. The latent variable model depends on a tuning parameter $K$, the dimension of the latent space. We fix $K=5$ since larger values of $K$ do not significantly change the performance in this example. We again use ROC curves to evaluate the link prediction performance on the set $\{(i,j):E_{ij}=0\}$. Each ROC curve in Figure 5 is the average of 10 random realizations of $E_{ij}$’s.

The semi-supervised criterion always performs better than the unsupervised criterion, as it should. Further, the semi-supervised criterion almost always outperforms the latent variable model, except for very small values of the false positive rate, and the fully unsupervised criterion also starts to outperform the latent variable model as the false positive rate increases. The latent variable model is also more sensitive to the sampling rate $\alpha$, with performance deteriorating for $\alpha=0.2$. This is because the model relies heavily on the structure of the network, and a low sampling rate may substantially distort the overall network topology. On the other hand, we use the node similarity matrix $W$ which depends only on the features of the proteins, and is thus unaffected by the sampling rate.

2 The school friendship network

This dataset is a school friendship network from the National Longitudinal Study of Adolescent Health (see for detailed information). This network contains 1011 high school students and 5459 directed links connecting students to their friends, as reported by the students themselves. The average degree of this network is also around $5$. Here we test our two link prediction criteria, with the same settings for $E_{ij}$ as in the protein example. Since the latent variable model of is not applicable to directed networks, we omit it here. Due to lack of node covariates, we construct a network-based similarity $W$ by using the Jaccard index defined in (11). We again apply block coordinate descent to minimize the criteria with $\lambda$ chosen by cross-validation, and report the average ROC curves over 10 realizations of $E_{ij}$’s. As shown in Figure 6, both criteria perform fairly well for $\alpha=0.8$ and $\alpha=0.5$, but fail for $\alpha=0.2$, as the sampling rate is too small for $W$ to capture the overall network topology. This does not happen in the protein-protein interactions network, since $W$ is constructed from covariates on proteins and is unaffected by sub-sampling.

Summary and future work

In this article, we have proposed a new framework for link prediction that allows uncertainty in observed links and non-links of a given network. Our method can provide relative rankings of potential links for pairs with and without observed links. The proposed link prediction criteria are fully non-parametric and essentially model-free, relying only on the assumption that similar node pairs have similar link probabilities, which is valid for a wide range of network models. One direction we would like to explore in the future is to combine more specific parametric network models with our non-parametric approach, with the goal of achieving both robustness and efficiency. We are also investigating consistency properties of our method, which is challenging because it requires developing a novel theoretical framework for evaluating consistency of rankings. We are also developing extensions that would allow the probabilities of errors, $\alpha$ and $\beta$, to depend on the underlying probabilities of links. This would allow, for example, making highly probable links more likely to be observed correctly. Ultimately, we would also like to incorporate the general framework of link uncertainty into other network problems, for example, community detection.

References