Link Propagation: A Fast Semi-supervised Learning Algorithm for Link Prediction
Hisashi Kashima∗

Tsuyoshi Kato†

Yoshihiro Yamanishi‡

Masashi Sugiyama§

Koji Tsuda¶
Abstract
We propose Link Propagation as a new semi-supervised learning
method for link prediction problems, where the task is to predict
unknown parts of the network structure by using auxiliary information such as node similarities. Since the proposed method canfill in missing parts of tensors, it is applicable to multi-relational
domains, allowing us to handle multiple types of links simultaneously. We also give a novel efficient algorithm for Link Propagation
based on an accelerated conjugate gradient method.

Keywords
Link Prediction, Supervised network inference, Semisupervised learning, Biological networks, Social networks.
1 Introduction
Many phenomena in the world can be represented by setsof entities, and sets of static and dynamic relationships
among the entities. Such relationships include friendships
among people, actions such as someone clicking an on-line
advertisement, and physical interactions among proteins.
Collections of such relationships form networks.
The problem of predicting the structure of networks iscalled the link prediction problem, which is one of the important tasks of link mining [9] in the data mining community. A typical setting of the link prediction problem is topredict unknown parts of the structure of a network (or, thefuture structure of the network) from the known parts of the
network. Link prediction has various applications in many
fields such as social network analysis, marketing, and bioinformatics. For example, it can be used to predict relationships among participants such as friendships in social networks, or to predict users’ future behaviors such as clicking
advertisements for marketing. In the field of bioinformatics,
predicting protein-protein interactions and regulatory relationships can provide guidance for the design of experiments
for discovering new biological facts.
The link prediction problem can be seen as the problem of completing an adjacency matrix which represents the∗ IBM Research, Tokyo Research Laboratory† Ochanomizu University, Center for Informational Biology‡ Mines ParisTech, Institut Curie, Inserm U900

§ Tokyo Institute of Technology, Department of Computer Science¶ Max Planck Institute for Biological Cybernetics

structure of a network. One of the standard approaches to thelink prediction problem is to regard it as a binary classification problem of the elements of the adjacency matrix. In thispaper, we add another dimension to the adjacency matrix,
which indicates the extension of single-type link prediction
to multiple-type link prediction. The extension results in introducing a third-order tensor which represents an adjacancy
matrix with link types. Consequently, we consider a completion problem of the tensor as a generalization of the standard
link prediction problem (Section 2). This is regarded as abinary classification problem of the elements of the tensor.
The tensor representation of the network structure allows us
to handle not only the existence of links but also the types oflinks, including temporal links. Furthermore, the tensor representation makes it possible to simultaneously predict multiple networks that have correlations with each other.
The link prediction problem can fall into two categories
in accordance with the information used for prediction:(i) topological-information-based link prediction and (ii)node-information-based link prediction. The former typeof link prediction uses only adjacency matrices. Based on
observed parts of the adjacency matrices, the missing parts
are predicted by using, for example, matrix factorization
techniques [23, 28]. On the other hand, the latter type of link
prediction exploits node information such as feature vectorsof nodes or similarity values among nodes. One of thestate-of-the-art approaches for this purpose is the pair-wise
support vector machine (pair-wise SVM), which combinesnode-wise kernel matrices to construct a pair-wise kernel
matrix [2, 3, 26]. In this paper, we discuss the latter type,i.e. link prediction based on node information.
In this paper, we propose using one of the well-known
approaches of semi-supervised learning called label propagation [40, 41] for link prediction (Section 3.1). Label propagation was originally intended for use in node classification,
but we apply the idea to pairs of nodes with multiple link
types (i.e. (node, node, type)-triplets) and predict the relationships among the nodes. Since we need a triplet-wise similarity matrix to apply the label propagation idea to triplets,
we propose to use the Kronecker product and the Kronecker
sum of the element-wise similarity matrices (Section 3.2).
To solve the resultant system of linear equations, we apply
the conjugate gradient method (Section 4.1). Since naive

application of the conjugate gradient method causes serious
scalability problems, we use an acceleration technique called“vec-trick” [22, 36] and its generalized versions for tensors,which significantly reduces the computation time and spacerequirements (Section 4.2). Moreover, we show interesting
special cases that can be implemented very easily by usingR
the functions of MATLAB⃝(Section 5).
Finally, we discuss the relationships between our approach and related approaches (Section 6), and demonstrate
the performance of the proposed method by using several
real-world network data sets (Section 7).
In summary, this work makes three main contributions:(i) We develop a new semi-supervised link prediction method
by applying the label propagation method [40, 41] to link
prediction. The new method is the first method for tensor
completion using auxiliary information. It allows us to handle not only strength of links among pairs of nodes, but also
various types of links.
(ii) We propose using the Kronecker sum similarity as anovel similarity measure among node pairs, which is shownto outperform the existing Kronecker product similarity inmany cases.
(iii) We propose an efficient learning algorithm based on the
conjugate gradient method. It mitigates the scalability problem caused by naive application of the label propagation.

2 Link prediction problem
The link prediction problem is usually described as a task to
predict how likely a link exists between an arbitrary pair ofnodes. In this paper, we consider a more general problem ofpredicting multiple types of links among the pairs of nodes1 .
Let us denote two sets of nodes by X :={x1 , x2 , . . . , xM } and Y := {y1 , y2 , . . . , yN }, and the typesof link by Z := {z1 , z2 , . . . , zT }. Some or all of X and Y
may be identical in accordance with applications. Note that
M := |X|, N := |Y | and T := |Z|. Taking an on-line store
as an example, X, Y , and Z are sets of users, items, and possible actions by a user to an item, respectively. The actions
include “click”, “buy”, and “evaluation”. So, a type-zk link
between two nodes xi and yj indicates that an user xi takes
an action zk to an item yj (Figure 1(left)). Let us consider another example. If we want to predict the relationships among
the members of a community, Both X and Y are the members, and Z is a set of relationship types among the members,
for example, Z := {friendship, working relationship}. Notethat we assume X = Y in this case.
Since a type-zk link for a node pair (xi , yj ) can be
1 The models and techniques used in this paper are easily extended
to handling links among more than triplets, but we will limit ourselveson triplets since we want to keep the description simple and triplets canaccommodate many important cases.

link strength
A userAn action
A userAn item

An item
An action

Figure 1: An example of a link. The fact that a user xi ∈ X
gives an action (e.g. “evaluation”) to an item yj ∈ Y isrepresented as a (single-type) link for a triplet (xi , yj , zk ).
The link strength fijk indicates confidence of the existenceof the link.

considered as a (single-type) link for a triplet (xi , yj , zk ),multiple-type link prediction for node pairs is equivalent tosingle-type link prediction for node triplets. Therefore, wedenote a set of single-type relationships among triplets by an
M × N × T third-order tensor,[F]i,j,k := fijk .
The variable fijk indicates how likely a link exists for the
triplet (xi , yj , zk ) ∈ X × Y × Z, which we refer to as linkstrength (Figure 1(right)). A large value of link strength
indicates high confidence of the existence of a link, and asmall value indicates high confidence of the absence of alink.
Now, we define another M × N × T third-order tensor
F ∗ which represents the observed parts of the network. F ∗plays the role of the target values given in a training data set
in supervised learning. Let E be the set of indices for triplets
whose link existence/absence is known (i.e. the set of indicesof the labeled instances). Each element of F ∗ is defined as{∗
fijk
if (i, j, k) ∈ E,∗
[F ]i,j,k :=0otherwise,∗
where fijk
is set to some positive value if a link exists for(xi , yj , zk ), and to some negative value if no link exists for(xi , yj , zk ). For (i, j, k) ∈/ E, [F ∗ ]i,j,k is filled with zerofor convenience, since we do not use them. Particularly, we∗
recommend to set fijk
as{|E|/|E + | if a link exists for (xi , yj , zk ),∗fijk :=−|E|/|E − | if no link exists for (xi , yj , zk ),where |E + | and |E − | are the numbers of triplets withlinks and those without links, respectively. Note that

(|E + | + |E − | = |E| ≤ M N T ). This way of setting the target values corresponds to the Fisher discriminant if we use
the squared loss function [4].
Since we consider node-information-based link prediction, we are also given similarity matrices WX , WY , and WZ
among the elements of X, Y , and Z, respectively2 . Thosematrices are non-negative and symmetric. In the previous
example of (user, item, action)-link prediction, WX represents similarities among the users, where its (i, ℓ)-th element[WX ]i,ℓ indicates the similarity between the i-th user xi andthe ℓ-th user xℓ . Similarly, WY and WZ are for the items andthe actions, respectively.
In summary, the link prediction problem discussed inthis paper is defined as follows.
INPUT:· Three symmetric and nonnegative matrices WX , WY ,and WZ for three entity sets X, Y , and Z.
· A third-order tensor F ∗ representing the known partsof the network.
OUTPUT: A third-order tensor F representing linkstrength for all triplets.

A node pairA node pair
Similar
triplets?

Propagationzk

zk

Similar
triplets

A type-zk link
existsA type-zk link
existsUnknown

A node pairA node pairzk

A type-zk link
exists(a) The link propagation principle for existence of a link

A node pairA node pair?
Unknown

Similar
triplets

A node pairA node pair
Propagationzk

zk

No type-zk link
exists

No type-zk link
existsSimilar
tripletszk

No type-zk link
exists(b) The link propagation principle for absence of a link

Figure 2: The idea of the link propagation principle for (a)existence of a link and (b) absence of a link. The figures
depict that if two triplets are similar to each other, their
existence/absence of links is likely to be identical.

3 Link Propagation: A new semi-supervised link
prediction method
In this section, we introduce our new approach to the link strength”. In accordance with this “link propagation principrediction problem. We refer to our semi-supervised link ple”, we define the objective function to minimize as
prediction method as “Link Propagation”, which has the objective function (3.2) and either of the triplet-wise similarity (3.1)
σ ∑matrices (3.4) and (3.6).
J({fijk }) :=wijk,ℓmn (fijk − fℓmn )2
2
i,j,k,ℓ,m,n3.1 Formulation. Since the link prediction problem de1 ∑
µ ∑
∗ 2
2
scribed in the previous section is a semi-supervised learn+(fijk − fijk
) +
fijk
,
2
2
ing problem (more precisely, a transductive learning prob(i,j,k)∈E(i,j,k)∈E/
lem since we have the test data set in the training phase), we
use label propagation [40, 41], which is one of the state-of- where wijk,ℓmn is the symmetric triplet-wise similarity bethe-art semi-supervised learning methods. The label propa- tween two triplets (xi , yj , zk ) and (xℓ , ym , zn ) (which will
gation method was originally used for predicting the labels be defined later). The first term of Eq. (3.1) indicates thatof unlabeled nodes by using the label propagation principle, the two link strength values fijk and fℓmn for the two tripletsthat is, “Two nodes that are similar to each other are likely should be close to each other if the similarity wijk,ℓmn beto have the same label”. The idea of label propagation can tween the two triplets is large. The second term is the loss
be generalized to link prediction, since the link prediction function that fits the predictions to their target values for the
problem can be regarded as a task of predicting labels for triplets in E. The last term is a regularization term to pre(node, node, type)-triplets. Applying the label propagation vent the predictions from being too far from zero, and also
method to triplets, we can predict link strength as the labels for numerical stability. σ > 0 and µ > 0 are regularization
parameters which balance the three terms in Eq. (3.1).
for the triplets.
Now, we rewrite Eq. (3.1) using tensors. For that, we
Modifying the label propagation principle, we can state
definean M × N × T tensor G as
the triplet version of the inference principle as “Two similar{(node, node, type)-triplets are likely to have the same link1
if (i, j, k) ∈ E,[G]i,j,k = √2 Even if they are not given, there is a possibility of constructing themµ otherwise,from the observed links, for example, by similarities among the fibers ofF ∗ . However, we do not discuss this further in this paper.

and let L be an M N T × M N T matrix called Laplacianmatrix defined as

Thus, the Kronecker product similarity between two triplets
is designed as the product of the similarities in each set.
This is an extension of the pair-wise similarity used inwhere D is a diagonal matrix whose diagonal elements are
kernel methods [2, 3, 26] to triplets. The Kronecker product∑similarity corresponds to the inner product in the product[D]i,i :=[W]i,j ,space of the three feature spaces, if WX , WY , and WZj
are kernel matrices defined as the inner products in theand W is a triplet-wise similarity matrix whose elements arefeature spaces of WX , WY , and WZ , respectively. Using thedefined as
Kronecker product similarity, we can express the Laplacian[W]M N (k−1)+M (j−1)+i,M N (n−1)+M (m−1)+ℓ := wijk,ℓmn . matrix in Eq. (3.3) asL := D − W,

Using G and L, Eq. (3.1) is rewritten asσ⊤(3.2) J(F) =vec (F) Lvec (F)21+ ∥ vec (F ∗ G) − vec (F ∗ ) ∥22 ,2
where ∗ is the Hadamard product (i.e. the element-wiseproduct of two tensors), and vec (A) is the vector constructedby stacking the mode-1 fibers (i.e. column) of the tensor
A, defined as vec (A)(k−1)N T +(j−1)N +i := [A]i,j,k . Note
that, when X = Y and there is no link direction, the frontal
slices of F ∗ are symmetric, then the solution F ∗ becomes
symmetric.
To obtain F that minimizes Eq. (3.2), we differentiate
Eq. (3.2) with respect to vec (F), which results in∂J(F)= σLvec (F) + vec (F ∗ G) − vec (F ∗ ) .
∂vec (F)(3.5)

L = DZ ⊗ DY ⊗ DX − WZ ⊗ WY ⊗ WX ,where DX is a diagonal∑
matrix whose diagonal elements aredefined as [DX ]i,i := j [WX ]i,j ; DY and DZ are definedsimilarly.
Since the product space of the Kronecker product similarity sometimes becomes too complex and is of overly highdimensions, we also consider another similarity with a more
restricted feature space (if it is a kernel function), which wecall the Kronecker sum similarity. The Kronecker sum similarity is based on the idea that two triplets are similar to eachother if two of the three cross-triplet pairs of nodes are identical, and the other cross-triplet pair is similar to each other(Fig. 3(b)). We define the Kronecker sum similarity as(3.6) W:= WZ ⊕ WY ⊕ WX=

(WZ ⊗ IN ⊗ IM ) + (IT ⊗ WY ⊗ IM )+ (IT ⊗ IN ⊗ WX ) ,Setting this to 0 for obtaining the stationary point, we obtainthe following linear equation,
where ⊕ indicates the Kronecker sum defined by WZ ⊕∗W
Y := WZ ⊗ IN + IT ⊗ WY , and IM is an identity matrix of(3.3)(σL + diag (vec (G))) vec (F) = vec (F ) ,size M × M . This is equivalently expressed in an elementwhere the operator diag produces a diagonal matrix whose wise manner as
diagonal elements are given by its argument vector.
wijk,ℓmn := [WX ]i,ℓ δ(j = m) δ(k = n)
3.2 Designing the triplet-wise similarity matrix. Since+ δ(i = ℓ) [WY ]j,m δ(k = n)
it is not realistic to give all of the M 2 N 2 T 2 elements of+ δ(i = ℓ) δ(j = m) [WZ ]k,n ,the triplet-wise similarity matrix W, we consider systematicconstruction of W using the element-wise similarity matrices where δ is a function which returns 1 if the argument is true,
WX , WY , and WZ . For addressing the scalability issues and 0 otherwise. Using the Kronecker sum similarity, we candiscussed in the next section, we restrict the class of W, and express the Laplacian matrix in Eq. (3.3) as
consider two ways for constructing W.
L = LZ ⊕ LY ⊕ LX ,The first one is the Kronecker product similarity, which (3.7)
is based on the idea that two triplets are similar to each otherif each of the three cross-triplet pairs of nodes are similar where LX is the Laplacian matrix defined as LX := DX −to each other (Fig. 3(a)). The Kronecker product similarity WX . LY and LZ are defined similarly.
As is clear from the definitions, the Kronecker productmatrix is defined as
can give an arbitrary pair of triplets a similarity score greater(3.4)
W := WZ ⊗ WY ⊗ WX ,than zero, while the Kronecker sum can give a positive score
where ⊗ indicates the Kronecker product. This is equiva- only to the pairs which share at least two elements of thetriplets.
lently expressed in an element-wise manner as
At first sight, since the Kronecker sum similarity has awijk,ℓmn := [WX ]i,ℓ [WY ]j,m [WZ ]k,n .
fewer number of pairs with positive similarity values thanEach of 3 cross-triplet pairs is similar
Similar Similar Similar

Two triplets are similar(a) Kronecker product similarity

Each of 2 cross-triplet pairs is identical& 1 cross-triplet pair is similar
Identical Identical Similar

Two triplets are similar(b) Kronecker sum similarity

Figure 3: Intuitive examples of (a) the Kronecker productsimilarity and (b) the Kronecker sum similarity.

the Kronecker product similarity, it seemingly can not fully
exploit node similarity information. But as we will see inthe experiments (Section 7), the Kronecker sum similarity iscompatible with the Link Propagation method, since pairs
with zero similarity values can utilize link information ofeach other through the other pairs with positive similarity
values using the label propagation mechanism.
Another intuition behind the Kronecker sum similarity
is that similar nodes tend to form triangle link structure,
which is one of the generative processes of small world
networks [10]. It is known that a variety of real-world
networks including biological networks and social networks
are small world networks.
The two definitions of the triplet-wise similarity can beseen as constructing a product graph over the triplets if we
consider the element-wise similarity matrices as weighted
graphs. The Kronecker product and the Kronecker sum
correspond to the tensor product graph and the Cartesian
product graph of the weighted graphs [14], respectively.
Finally, we mention the scalability problem occurredin using the Kronecker product/sum similarity matrix. As
mentioned earlier, even if the element-wise similarity matrices are small, their Kronecker product becomes huge
(M N T × M N T ), so it is not reasonable to store them explicitly in the memory. The matrix is rather sparse for the
Kronecker sum similarity, but still needs much space. Since
the kernel methods use the same similarity matrix we use as
kernel matrices [2, 3, 26]. they also suffer from the severe

scalability problem. In the next section, we overcome thisproblem by the conjugate gradient method using the “vectricks”.
4

A fast algorithm for Link Propagation method

In this section, we propose a conjugate gradient method
accelerated by using the technique called “vec-tricks”. The
resultant algorithm needs O(M 2 N 2 T 2 (M + N + T )) timeand O(M 2 + N 2 + T 2 + M N T ) space.
4.1 Conjugate gradient method for Link Propagation.
The conjugate gradient method is a standard approach tosolving a system of linear equations [11]. The algorithmof the conjugate gradient method for Af = f∗ is shown in
Algorithm 1. We modify it to solve our system of linear
equations (3.3) for Link Propagation.
First, we replace A, f, and f∗ by using the correspondences, A = σL + diag (vec (G)), f = vec (F), and f∗ =vec (F ∗ ). We also replace the other vectors f(t), p(t), q(t),and r(t) by tensors F(t), P(t), Q(t), and R(t), respectively.
Then, we obtain the conjugate gradient algorithm for our system of linear equations (3.3) as detailed in Algorithm 2. Notethat the algorithm is described using tensor notation in contrast to the standard conjugate gradient algorithm (Algorithm
1) being described in terms of vectors.
Most of the steps in Algorithm 2 are easily obtainedby simple substitutions, but Line 2 and Line 4 need somederivation. Here, we derive only Line 2. Line 4 can bederived in a similar manner. First, we define the following
two operators LPROD and LSUM for the Kronecker product andfor the Kronecker sum, respectively, as(4.8)

LPROD (B) :=(DZ ⊗ DY ⊗ DX

(4.9)

L

−WZ ⊗ WY ⊗ WX ) vec (B) ,(LZ ⊗ LY ⊗ LX ) vec (B) ,SUM(B) :=

where B is an M × N × T tensor. Bearing the above
correspondences in mind , r(0) := f∗ − Af(0) is rewrittenasvec (R(0)) := vec (F ∗ ) − (σL + diag (vec (G))) vec (F(0))= −σL{PROD|SUM} vec (F(0)) ,where we used F ∗ = F(0) = diag (vec (G)) vec (F(0)),
and Eqs. (3.5) and (3.7). In Algorithm 2, the operator
L{PROD|SUM} is replaced with LPROD when we use the Kronecker
product similarity, or with LSUM when we use the Kronecker
product similarity.
However, evaluation of Eqs. (4.8) and (4.9) is still acomputational bottleneck of Algorithm 2, since the tripletwise similarity matrix is huge.
4.2 The “vec-tricks”. We here show that computation of
Eqs. (4.8) and (4.9) can be made significantly efficientAlgorithm 1 Conjugate Gradient (A, f∗ , ϵ).
∗1: f(0) := f∗2: r(0) := f − Af(0), and p(0) := r(0)3: for t = 0, 1, 2, . . . do
4:q(t) := Ap(t)
⟨
⟩
5:
6:
7:
8:

α(t) := ⟨r(t),p(t)where mode-n multiplication is an operation that multiplies
the mode-n fibers of a tensor by a matrix. For third-ordertensors, these are defined as[B ×1 AX ]i,j,k :=⟩p(t),q(t)[B ×2 AY ]i,j,k :=N∑[B]i,ℓ,k [AY ]j,ℓ ,ℓ=1[B ×3 AZ ]i,j,k :=2

if< ϵ2 , return f(t + 1)
10:p(t + 1) := r(t + 1) + β(t)p(t)11: end for
9:[B]ℓ,j,k [AX ]i,ℓ ,ℓ=1

f(t + 1) := f(t) + α(t)p(t)r(t + 1) := r(t) − α(t)q(t)∥r(t+1)∥2β(t) := ∥r(t)∥2 2∥r(t+1)∥22∥r(0)∥22M∑

T∑[B]i,j,ℓ [AZ ]k,ℓ ,ℓ=1

and each of them returns an M × N × T tensor. For moreon general tensor calculation, see [20], for example. The
form of Eq. (4.11) is naturally extendable to third-order (or∗Algorithm 2 Link Propagation (F , G, WX , WY , WZ , σ, ϵ);higher-order) tensors, and we obtain the following equation.
{PROD|SUM}
PROD
L
is replaced with L(Eq. (4.16)) for the Kro(4.12)
SUM
necker product similarity, or with L ( Eq. (4.17)) for the(AZ ⊗ AY ⊗ AX )vec (B) = vec (B ×1 AX ×2 AY ×3 AZ ) .
Kronecker sum similarity.
1: F(0) := F ∗While the naive computation in the left-hand side needs
2: R(0) := −σL{PROD|SUM} (F(0)), and P(0) := R(0)O(M 2 N 2 T 2 ) computation time and space, we can reduce it
3: for t = 0, 1, 2, . . . doto O(M N T (M +N +T )) computation time and O(M N T )}4:Q(t) := ⟨σL{PROD|SUM
space in the right-hand side.
⟩ (P(t)) + G ∗ P(t)R(t),P(t)Next, we consider the case with the Kronecker sum.
⟩5:α(t) := ⟨P(t),Q(t)Similar to the case of the Kronecker product, we have6:
F(t + 1) := F(t) + α(t)P(t)(4.13) (AY ⊕ AX )vec (B) = vec (BAY + AX B)
7:
R(t + 1) := R(t) − α(t)Q(t)∥R(t+1)∥22(4.14)= vec (B ×1 AX + B ×2 AY ) .
8:β(t) :=
2
9:∥R(t)∥2∥R(t+1)∥2
if ∥R(0)∥2 < ϵ, return F(t + 1)

P(t + 1) := R(t + 1) + β(t)P(t)11: end for10:

by using the “vec-tricks” [22, 36], which accelerates themultiplication of matrix Kronecker products and a vectorized
matrix/tensor.
Let AX , AY , and AZ be M × M , N × N , and T × T
symmetric matrices, respectively. Let B be an M ×N matrix,
and B be an M × N × T tensor. The basic idea of the “vectricks” lies in the following equation [22]:(4.10)(AY ⊗ AX )vec (B) = vec (AX BAY ) .

The left-hand side of Eq. (4.10) needs O(M 2 N 2 ) computation time and space, while the right-hand side needs only
O(M N (M + N )) time and O(M N ) space. Vishwanathan
et al. [36] used this formula for accelerating the computationof the graph kernels.
Now, we generalize Eq. (4.10) to obtain its tensor
version. Bearing in mind that matrices are second-ordertensors, we rewrite Eq. (4.10) using mode-n multiplicationof tensors [20] as(4.11)(AY ⊗ AX )vec (B) = vec (B ×1 AX ×2 AY ) ,Again, Eq. (4.14) is generalized to tensors as(4.15)(AZ ⊕ AY ⊕ AX )vec (B)= vec (B ×1 AX + B ×2 AY + B ×3 AZ ) .
When AX = AY , the number of multiplications can be
reduced, since B ×1 AX and B ×2 AY are essentially thesame.
By using Eqs. (4.11) and (4.15), the computation of Eqs.
(4.8) and (4.9) can be significantly simplified as(4.16)(4.17)LPROD (B) = B ×1 DX ×2 DY ×3 DZ− B ×1 WX ×2 WY ×3 WZ ,LSUM (B) = B ×1 LX + B ×2 LY + B ×3 LZ .

4.3 Discussion on efficiency. A great advantage of our
Link Propagation algorithm is in its memory efficiency.
It requires only O(M N T + M 2 + N 2 + T 2 ) memory
thanks to the “vec-tricks”. In terms of the computational
complexity, it requires O(M 2 N 2 T 2 (M + N + T )) time
theoretically, because each iteration of the conjugate gradientalgorithm can be executed in O(M N T (M + N + T )) time,and O(M N T ) iterations are required to solve the linearequations completely. In practice, the number of iterations
required for convergence is much smaller than O(M N T ),and we observed that the predictive performance did notchange after only several iterations in our experiments.
The improvement by using the “vec-tricks” is significant, because it is not clear so far how to apply the “vectricks” to kernel methods. If we imagine the triplet-wise
extension of the pair-wise SVM using the same similarity matrix without the “vec-tricks”, the space complexity isO(M 2 N 2 T 2 ) and the time complexity is O(M 3 N 3 T 3 ). The
time complexity comes from the fact that the quadratic programming problem needs cubic time complexity with respect
to the number of parameters (in the case of kernel mathods,
it is the same as the number of training examples). As many
fast optimization methods have been developed for SVM, its
practical speed is not too slow in general. Nevertheless, as
it is difficult to keep the whole kernel matrix in the memory,
we cannot always use the fastest software packages in our
problems.
5 Easily implementable special cases
In this section, we show special cases of pair-wise link
prediction (i.e. when T = 1) with µ := 1, where we caneasily implement the proposed method by using the builtin functions of existing numerical computing environments
Rsuch as MATLAB⃝.
Since setting µ := 1 implies [G]i,j = 1 for all (i, j),it holds that diag (vec (G)) = IM N . Therefore, Eq. (3.3)
becomes(5.18)(σL + IM N ) vec (F) = vec (F∗ ) .

Note that F = F, F ∗ = F∗ , and G = G when T = 1.
When W is the Kronecker product similarity, Eq. (5.18)
becomes(σDY ⊗ DX − σWY ⊗ WX + IM N ) vec (F) = vec (F∗ ) .
By using Eq. (4.10), we obtain
σDX FDY − σWX FWY + F = F∗ .
This equation is called the generalized Sylvester equation [22]. Vishwanathan et al. [36] proposed using S andT that satisfy DY ⊗ DX + WY ⊗ WX ≈ S ⊗ T for approximating the equation as TFS + F = F∗ , and solving it byR
using the dlyap function in MATLAB⃝.
When W is the Kronecker sum similarity, Eq. (5.18)
becomes(5.19)(σLY ⊕ LX + IM N ) vec (F) = vec (F∗ ) .

We can derive the relation
) (
)
(
1
1
σLY ⊕ LX + IM N = σLY + IN ⊕ σLX + IM ,22which is substituted into Eq. (5.19) to obtain
((
) (
))
1
1
σLY + IN ⊕ σLX + IM
vec (F) = vec (F∗ ) .
2
2
By using Eq. (4.13), this can be rewritten as
) (
)
(
1
1
F σLY + IN + σLX + IM F = F∗ .
22This equation is called the Sylvester equation [22], and canR
be solved by using the lyap function in MATLAB⃝. Unlike the case with the Kronecker product, no approximation
is involved, and therefore we can obtain the exact solution.
6 Related work
The link prediction problem has been studied in the context
of predicting biological networks such as protein-protein
interaction networks and gene regulatory networks in thebioinformatics area, and also in the context of link mining [9]in the data mining community.
In bioinformatics, several node-information-based approaches were proposed, such as an EM-based approach [19]and metric-learning-based approaches [35, 38]. The pairwise kernel which we will compare our method with in our
experiments (Section 7) was proposed for predicting proteinprotein interactions [3]. Interestingly, the same kernel was
also proposed for entity resolution [26], and collaborative filtering [2], independently.
In the data mining community, the link prediction problem is studied as one of the fundamental tasks of link mining. There are several methods that utilize only structural information such as link metrics (e.g. [24]). Matrix factorization approaches [23, 28] are also grouped into topologicalinformation-based methods.
There are also supervised learning methods using node
information as well as topological information, for example,[13, 25]. There have also been several works (e.g. [27, 31]) that apply the framework of statistical relational learning
to link prediction. A similar model is called the exponential random graph model in social network analysis [1]. Recently, sophisticated generative models of networks from
Bayesian perspective have been proposed [5, 39].
Recently, there have been proposed several approaches
to extending the existing network analysis methods to modeling the temporal dynamics of network structure. For example, Fu et al. [7] extended the exponential random graphmodel [1, 31] to temporal modeling. Some attempts (e.g.
[29, 30]) use tensor analysis techniques [20] for temporal relation data as generalization of matrix analysis for pair-wise
relations. Note that they do not exploit node informationsuch as the node similarity matrices used in this paper.
The basic idea of label propagation was proposed by
Zhou et al. [40] and Zhu et al. [41]. The scalability problems

are often discussed [8, 42], but the technique we used inthis paper is totally different from theirs. To the best of ourknowledge, we are the first to use auxiliary information insemi-supervised link prediction.
The matrix “vec-trick” (Eq. (4.10)) was used by Vishwanathan et al. [36] for accelerating the computation of thegraph kernels.
7 Experiments
In this section, we show some experimental results for
single-type link prediction (matrix completion) and multipletype link prediction (third-order tensor completion) basedon node information. Section 7.1 describes the results ofsingle-type link prediction problems. We demonstrate that
our semi-supervised link prediction performs better than thepair-wise kernel method, where both approaches are basedon combined node information. Section 7.2 describes the results of multiple-type link prediction problems, where ourtask is simultaneous prediction of multiple networks related to each other. We demonstrate that predicting multiple
networks simultaneously achieves better predictive performance than predicting each network separately.
Throughout all of the experiments, we set σ = 0.001
and µ = 1 for Link Propagation. Note that for pair-wise link
prediction, we take T = |Z| = 1, and F and F ∗ are thesecond-order tensors (i.e. matrices) F and F∗ , respectively.
7.1 Pair-wise link prediction (T = 1). We compared our
method with the pair-wise kernel method [2, 3, 26], which isone of the state-of-the-art link prediction methods using node
information. In the pair-wise kernel method, link strength
between a node pair (xi , yj ) is modeled by∑
f (i, j) :=αℓ,m κPAIR ((i, j), (ℓ, m)).
(ℓ,m)
PAIR

The kernel κ ((i, j), (ℓ, m)) represents similarity between
two node pairs (xi , yj ) and (xℓ , ym ), and the αs are themodel parameters. In its original definition [2, 3, 26], thepair-wise kernel is defined by using the node-wise kernel κas(7.20)
κPAIR ((i, j), (ℓ, m)) := κ(i, ℓ)κ(j, m) + κ(i, m)κ(j, ℓ),which corresponds to the Kronecker product similarity. Notethat the above kernel is symmetrized.
Alternatively, we can use another pair-wise kernel corresponding to the Kronecker sum similarity as follows.
(7.21)
κPAIR ((i, j), (ℓ, m)) := δ(i = ℓ)κ(j, m) + κ(i, ℓ)δ(j = m)
+δ(i = m)κ(j, ℓ) + κ(i, m)δ(j = ℓ).
Since the size of the pair-wise kernel matrices were
too huge to construct explicitly in the memory, it was notreasonable to apply standard SVM implementations such
as SVMlight [16]. Therefore, we used an on-line learningalgorithm which processes one training example at eachtraining step, so it is computationally and spatially efficient.
In our experiments, we employed the passive-aggressivealgorithm [6], which is an efficient on-line large-marginlearning algorithm. We used the 1-norm version (PA-I) of thealgorithm with C = √1. All of the kernels were normalized as
κPAIR ((i, j), (ℓ, m))/ κPAIR ((i, j), (i, j))κPAIR ((ℓ, m), (ℓ, m)).
All of the training data was processed three times in the
training phase for better convergence and prediction.
We used three data sets for pair-wise link prediction.
The first data set [38] contains the metabolic pathways of theyeast S. Cerevisiae in the KEGG/PATHWAY database [17].
Proteins are represented as nodes, and a link indicates thatthe two proteins are enzymes that catalyze successive reactions. The number of nodes in the network is 618, and thenumber of links is 2,782. In this data set, three kernel matrices based on gene expressions, localization sites, and phylogenetic profiles are given. We used them as the kernel matrices or the similarity matrices3 .
The second data set is a protein-protein interaction
network data set constructed by von Mering et al. [37].
We followed Tsuda and Noble [32], and used the medium
confidence network, containing 2, 617 nodes and 11, 855
links. In this data set, each protein is given a 76-dimensional
binary vector, each of whose dimensions indicates whether
or not the protein is related to a particular function. We used
the inner product values between the vectors as the kernel
matrix or the similarity matrix4 .
The third data set is a social network representing theco-authorships in the NIPS conferences, containing 2, 865
nodes and 4, 733 links. Authors correspond to nodes, and alink between two nodes means that there is at least one coauthored paper by the corresponding authors. In this dataset, each author is given a feature vector, each of whose
dimensions corresponds to occurrences of a particular wordin the author’s papers. We used the inner product of thevectors as the kernel matrix or the similarity matrix5 .
We randomly selected 10% of all the pairs(|E|/(M N T ) ≈ 0.10) as training data, and evaluated
AUC on the remaining pairs; this procedure was repeated 10
times.
Figure 4 shows the averaged AUCs and their standard
deviations for the metabolic network data. “Pair-wise Kernel(prod)” and “Pair-wise Kernel (sum)” denote the pair-wisekernel method using the passive-aggressive algorithm with
the Kronecker product kernel (7.20) and the Kronecker sum
3 Available at http://web.kuicr.kyoto-u.ac.jp/supp/yoshi/ismb05/.
Although a kernel matrix based on chemical information is also given in thisdata set, we did not use it since it includes negative entries.
4 Available at http://noble.gs.washington.edu/proj/maxent/.
5 Available at http://ai.stanford.edu/˜gal/data.html.

Pair-wise

0.80

metabolicKernel(prod)

network

0.75

Link
Propagation

protein-protein

0.70(prod)

interaction

C
U0.65
A

Pair-wise

network

Kernel(sum)

0.60

socialLink

network

Propagation
(sum)

0.55
1

0.50

10

100

1000

10000

100000 (sec)computation time

expression
Pair-wise Kernel(prod)

phylogenetic

Link Propagation(prod)

Pair-wise Kernel(sum)

localization
Link Propagation(sum)

Figure 6: Comparison of computation time by each method.

Figure 4: Summary of results for the KEGG metabolicR
the algorithms were implemented in R for Microsoft⃝
Winnetwork.
R
R
R
⃝
⃝
⃝
dows XP on an IBM IntelliStation ZPro 6221 with anRRIntel⃝
Xeon⃝
3.06-GHz CPU and 1.5-GB RAM.
The
results
show the efficiency of Link Propagation. We
0.85
0.80
can see that Link Propagation is much faster than the pair0.80
wise kernel method, and the improvement is significant when
0.75
0.75
we use the Kronecker product similarity. Also, the KroC
U 0.700.70
necker sum is consistently faster than the Kronecker product.
A
0.65This is because the number of pairs with positive Kronecker
0.65
0.60
sum similarity is smaller than that for the Kronecker productsimilarity in the case of the pair-wise kernel method, and be0.60
0.55
Pair-wise
Link
Pair-wise
Link
Pair-wise
Link
Pair-wiseLinkcause the number of iterations needed for convergence by the
Kernel
Propagation Kernel
Propagation
Kernel
Propagation Kernel
Propagation(prod)(prod)(sum)(sum)(prod)(prod)(sum)(sum)
Kronecker sum similarity is smaller than that the Kronecker
product similarity in the case of Link Propagation.
Figure 5: Summary of results for the protein-protein interac7.2 Triplet-wise link prediction (T > 1). Using thetion network (left) and the social network (right).
proposed method for triplet-wise link prediction, we canpredict two networks simultaneously. Alternatively, we canpredict the two networks separately by using the proposed
kernel (7.21), respectively. “Link Propagation (prod)” and method for pair-wise link prediction. We compared the“Link Propagation (sum)” denote the proposed method with two approaches in order to investigate whether or not thethe Kronecker product similarity and the Kronecker sum simultaneous network prediction improves the predictive
similarity, respectively. Three results are shown for each of performance.
the information sources, gene expression (expression), phyWe used two biological network data sets for tripletlogenetic profile (phylogenetic), and localization sites (local- wise link prediction. Each data set contains two related
ization). Figure 5 shows the results for the protein-protein networks. Therefore, tensors with T = 2 arise, when weinteraction network data (left) and the social network data consider two networks simultaneously. The first data set(right), respectively. In most of the cases, Link Propagation is two protein-protein interaction networks from different
outperforms the pair-wise kernel method. Interestingly, de- labs [15, 34]. In this data set, we collected two sets ofspite its restricted feature space, the Kronecker sum performs protein-protein interactions detected from the yeast-twobetter than the Kronecker product in many cases.
hybrid system in two different labs, one of which forms a
Next, we compare the computation time by each network (Ito) with 1, 422 nodes and 744 links, and the othermethod. Figure 6 shows the average computation time in log (Uetz) forms a network with the same nodes as those of thescale spent on each data set in the training and test phases. Ito network and 888 links. They share 123 links in common.
Note that the passive-aggressive learner with the pair-wise
The second data set is a pair of a physical protein-protein
kernels was trained with only one scan of the training data interaction network and a genetic protein-protein network(which degrades the predictive performance though). All of stored in the MIPS database [12]. In the physical network,two proteins have a link if the interaction between the two
proteins is experimentally confirmed. In the genetic network,
two proteins have a link if the simultaneous mutations in thetwo corresponding genes cause a cell death. The physicalnetwork consists of 1, 225 nodes and 3, 474 links, while thegenetic network consists of the same nodes as those of thephysical network and 1, 333 links. The two networks share
198 links in common.
In both of the two data sets, the kernel matrices and thesimilarity matrices are constructed using gene expressions,
phylogenetic profiles, and localization sites by following thesame procedure as Yamanishi et al. [38]. Also, we set thesimilarity between the two networks to one.
We randomly selected 50% of all the triplets(|E|/(M N T ) ≈ 0.50) as training data, and evaluated AUC
for the remaining pairs; this procedure was repeated 10
times. We used a higher proportion of the data as training
data than those we used for pair-wise link prediction, since
we need the two networks to overlap to some degree.
Figure 7 shows the averaged AUCs and their standard
deviations for the two protein-protein interaction networks
with the Kronecker product similarity and the Kronecker
sum similarity. “Ito (each)” and “Ito (simultaneous)” indicate the results for the Ito network by network-by-network
prediction and simultaneous prediction, respectively. Similarly, “Uetz (each)” and “Uetz (simultaneous)” are for the
Uetz network. Three results are shown for each of the information sources. We find that predicting the two networks simultaneously improved the predictive performances in manycases.
Figure 8 shows the results for the genetic network andthe physical network with the Kronecker product similarity and the Kronecker sum similarity. “genetic (each)” and“genetic (simultaneous)” indicate the results for the genetic
network by network-by-network prediction and simultaneous prediction, respectively. Similarly, “physical (each)” and“physical (sum)” are for the physical network. Three results
are shown for each of the information sources. Although
the improvement is not so significant as the experiment withthe two protein networks, simultaneous prediction improves
the performance especially when using the Kronecker sum
similarity. Again, in both of the data sets, the Kronecker
sum similarity consistently outperforms the Kronecker product similarity.
Finally, we show experimental results for three networks. We constructed three networks consisting of 223
common proteins in the previous three networks, the genetic
network, the Ito network, and the Uetz network. Each ofthem has 70–140 links, and they share 5–30 links in common. Figure 9 shows the results with the Kronecker productsimilarity and the Kronecker sum similarity. Since the number of links is small, the variance of the AUC values tends
to be high. Even so, we can still see the trend that the re-sults improve as the number of networks used in simultaneous prediction increases.
8 Concluding remarks
We proposed a new semi-supervised link prediction method
by applying the label propagation technique to link prediction. This allows us to handle not only strength of the links
among pairs of nodes, but also the type of links. We used
the Kronecker sum similarity as the similarity matrices aswell as the Kronecker product similarity. Moreover, we proposed an efficient learning algorithm based on the conjugate
gradient method. Use of the tensor “vec-tricks” mitigated
the scalability problem caused by naive application of label
propagation. The experimental results showed that the proposed approach is quite promising.
Finally, we conclude this paper by mentioning some future work. First, we will consider compressed representationof the solution. Even if the similarity matrices and F ∗ aresparse, the solution F is usually dense, so it is hard even to
store F in the main memory for large-scale problems. One
possible approach might be to use compact tensor representations [20] for storing F. Use of topological information is
also promising. It is possible to construct similarity matrices
from visible parts of F ∗ . It would be interesting to compare
our method using those similarity matrices with the othermethods using only topological information such as matrix
factorization [23, 28] and tensor decomposition [20]. Information integration is crucial, since we often have multiple
similarity matrices obtained from various data sources. We
will consider incorporating methods that adjust the weightof each similarity matrix automatically [18, 21, 33]. Our future work might also include out of sample prediction using
approximated inference without solving entire systems, andprediction with only positive links.
References[1] C. J. Anderson, S. Wasserman, and B. Crouch. A p∗ primer:
logit models for social networks. Social Networks, 21:37–66,
1999.
[2] J. Basilico and T. Hofmann. Unifying collaborative andcontent-based filtering. In Proceedings of the 21st International Conference on Machine Learning (ICML), 2004.
[3] A. Ben-Hur and W. S. Noble. Kernel methods for predicting protein-protein interactions. Bioinformatics, 21(Suppl.
1):i38–i46, 2005.
[4] C. Bishop. Pattern Recognition and Machine Learning.
Springer, 2006.
[5] W. Chu, V. Sindhwani, Z. Ghahramani, and S. Keerthi.
Relational learning with Gaussian processes. In Advances in
Neural Information Processing Systems 19, 2007.
[6] K. Crammer, O. Dekel, J. Keshet, S. Shalev-Shwartz, and
Y. Singer. Online passive-aggressive algorithms. Journal of
Machine Learning Research, 7:551–585, 2006.

0.70

0.80

0.75
0.65

Ito
(each)

0.70

Ito(simultaneous)C
U 0.60
A

0.65

Uetz
(each)
Uetz

0.60(simultaneous)

0.55
0.55

0.50

0.50
expression

phylogenetic

expression

localization

phylogenetic

localization

Figure 7: Summary of results for the two protein-protein interaction networks with the Kronecker product similarity (left)
and the Kronecker sum similarity (right), respectively.

0.80

0.90

0.75

0.85

genetic(each)

C
U
A

0.70

0.80

genetic(simultaneous)

0.65

0.75

physical(each)
physical(simultaneous)

0.60

0.70

0.55

0.65
expression

phylogenetic

localization

expression

phylogenetic

localization

Figure 8: Summary of results for the genetic network and the physical network with the Kronecker product similarity (left)
and the Kronecker sum similarity (right).

[7] W. Fu, F. Guo, S. Hanneke, and E. Xing. Recovering
temporally rewiring networks: A model-based approach. In
Proceedings of the 24th International Conference on Machine
Learning (ICML), 2007.
[8] J. Garcke and M. Griebel. Semi-supervised learning withsparse grids. In Proceedings of the 22nd ICML Workshop on
Learning with Partially Classified Training Data, 2005.
[9] L. Getoor and C. P. Diehl. Link mining: a survey. SIGKDD
Explorations, 7(2):3–12, 2005.
[10] D. Goldberg and F. Roth. Assessing experimentally derived interaction in a small world. Proceedings of the National Academy of Sciences of the United States of America,
100:4372–4376, 2003.
[11] G. H. Golub and C. F. V. Loan. Matrix computations (3rded.). Johns Hopkins University Press, 1996.
[12] U. Güldener, M. Münsterkötter, M. Oesterheld, P. Pagel,
A. Ruepp, H.-W. Mewes, and V. Stümpflen. Mpact: themips protein interaction resource on yeast. Nucleic Acids
Research, 34:D436–D441, 2006.
[13] M. A. Hasan, V. Chaoji, S. Salem, and M. Zaki. Link
prediction using supervised learning. In Workshop on Link
Discovery: Issues, Approaches and Applications (LinkKDD),
2005.

[14] W. Imrich and S. Klavzar. Product Graphs: Structure and
Recognition. Wiley, 2000.
[15] T. Ito, T. Chiba, R. Ozawa, M. Yoshida, M. Hattori, and
Y. Sakaki. A comprehensive two-hybrid analysis to explore
the yeast protein interacome. Proceedings of the National
Academy of Sciences, 98(8):4569–4574, 2001.
[16] T. Joachims. Learning to Classify Text Using Support Vector
Machines: Methods, Theory and Algorithms. Kluwer Academic Publishers, 2003.
[17] M. Kanehisa, S. Goto, S. Kawashima, Y. Okuno, and M. Hattori. The KEGG resources for deciphering the genome. Nucleic Acids Research, 32:D277–D280, 2004.
[18] T. Kato, H. Kashima, and M. Sugiyama. Integration of multiple networks for robust label propagation. In Proceedingsof the 8th SIAM International Conference on Data Mining(SDM), 2008.
[19] T. Kato, K. Tsuda, and K. Asai. Selective integration ofmultiple biological data for supervised network inference.
Bioinformatics, 21(10):2488–2495, 2005.
[20] T. G. Kolda and B. W. Bader. Tensor decompositions andapplications. Technical Report SAND2007-6702, Sandia
National Laboratories, 2007.
[21] G. R. G. Lanckriet, M. Deng, N. Cristianini, M. I. Jordan, and

0.90

0.80

0.85

0.75

0.80
0.70

0.75

C 0.65
U
A

0.70
0.65

0.60

0.60

0.55

0.55
0.50

0.50

0.45

genetic(each)

genetic(2-simultaneous)

genetic(3-simultaneous)Ito(each)

Ito(2-simultaneous)Ito(3-simultaneous)

Uetz(each)

Uetz(2-simultaneous)Uetz(3-simultaneous)

0.45
0.40

0.40
expression

phylogenetic

localization

expression

phylogenetic

localization

Figure 9: Summary of results for the genetic network, the Ito network, and the Uetz network with the Kronecker productsimilarity (left) and the Kronecker sum similarity (right).

W. S. Noble. Kernel-based data fusion and its application toprotein function prediction in yeast. In Proceedings of the
Pacific Symposium on Biocomputing (PSB), 2004.
[22] A. J. Laub. Matrix Analysis for Scientists and Engineers.
Society for Industrial and Applied Mathematics, 2005.
[23] D. Lee and H. Seung. Algorithms for non-negative matrix
factorization. In Advances in Neural Information Processing
Systems 13, 2001.
[24] D. Liben-Nowell and J. Kleinberg. The link prediction problem for social networks. In Proceedings of the 12th International Conference on Information and Knowledge Management (CIKM), pages 556–559, 2004.
[25] J. O’Madadhain, J. Hutchins, and P. Smyth. Prediction andranking algorithms for event-based network data. SIGKDD
Explorations, 7(2):23–30, 2005.
[26] S. Oyama and C. D. Manning. Using feature conjunctions
across examples for learning pairwise classifiers. In Proceedings of the 15th European Conference on Machine Learning(ECML), pages 322–333, 2004.
[27] A. Popescul and L. H. Ungar. Statistical relational learningfor link prediction. In IJCAI Workshop on Learning Statistical Models from Relational Data, 2003.
[28] N. Srebro, J. Rennie, and T. Jaakkola. Maximum-margin
matrix factorization. In Advances in Neural Information
Processing Systems 17, 2005.
[29] J. Sun, S. Papadimitriou, and P. Yu. Window-based tensor
analysis on high-dimensional and multi-aspect streams. In
Proceedings of the 6th IEEE International Conference on
Data Mining (ICDM), pages 1076–1080, 2006.
[30] J. Sun, D. Tao, and C. Faloutsos. Beyond streams andgraphs: Dynamic tensor analysis. In Proceedings of the 12th
International Conference on Knowledge Discovery and Data
Mining (KDD), pages 374–383, 2006.
[31] B. Taskar, M. Wong, P. Abbeel, and D. Koller. Link prediction in relational data. In Advances in Neural Information
Processing Systems 16, 2004.
[32] K. Tsuda and W. S. Noble. Learning kernels from biologicalnetworks by maximizing entropy. Bioinformatics, 20(Suppl.
1):i326–i333, 2004.
[33] K. Tsuda, H. Shin, and B. Schölkopf. Fast protein classifi-

cation with multiple networks. Bioinformatics, 21 Suppl. 2,
2005.
[34] P. Uetz, L. Giot, G. Cagney, T. Mansfield, R. Judson,
J. Knight, D. Lockshon, V. Narayan, and et al. A comprehensive analysis of protein-protein interactions in saccharomyces
cerevisiae. Nature, 403(6770):623–627, 2000.
[35] J.-P. Vert and Y. Yamanishi. Supervised graph inference.
In Advances in Neural Information Processing Systems 15,
2005.
[36] S. V. N. Vishwanathan, K. Borgwardt, and N. Schraudolph.
Fast computation of graph kernels. In Advances in Neural
Information Processing Systems 19, 2007.
[37] C. von Mering, R. Krause, B. Snel, M. Cornell, S. Olivier,S. Fields, and P. Bork. Comparative assessment of large-scaledata sets of protein-protein interactions. Nature, 417:399–
403, 2002.
[38] Y. Yamanishi, J.-P. Vert, and M. Kanehisa. Supervised
enzyme network inference from the integration of genomic
data and chemical information. Bioinformatics, 21:i468–
i477, 2005.
[39] K. Yu, W. Chu, S. Yu, V. Tresp, and Z. Xu. Stochastic relational models for discriminative link prediction. In Advancesin Neural Information Processing Systems 19, 2007.
[40] D. Zhou, O. Bousquet, J. Weston, and B. Schölkopf. Learningwith local and global consistency. In Advances in Neural
Information Processing Systems 16, 2004.
[41] X. Zhu, Z. Ghahramani, and J. Lafferty. Semi-supervised
learning using Gaussian fields and harmonic functions. In
Proceedings of the 20th International Conference on Machine
Learning (ICML), 2003.
[42] X. Zhu and J. Lafferty. Harmonic mixtures: combining
mixture models and graph-based methods for inductive andscalable semi-supervised learning. In Proceedings of the
22nd International Conference on Machine Learning (ICML),
2005.