Kernels for Link Prediction
with Latent Feature Models
Canh Hao Nguyen and Hiroshi Mamitsuka
Bioinformatics Center, ICR, Kyoto University,
Gokasho, Uji, Kyoto, 611-0011, Japan{canhhao,mami}@kuicr.kyoto-u.ac.jp

Abstract. Predicting new links in a network is a problem of interestin many application domains. Most of the prediction methods utilize information on the network’s entities such as nodes to build a model oflinks. Network structures are usually not used except for the networks
with similarity or relatedness semantics. In this work, we use network
structures for link prediction with a more general network type withlatent feature models. The problem is the diﬃculty to train these models directly for large data. We propose a method to solve this problem
using kernels and cast the link prediction problem into a binary classiﬁcation problem. The key idea is not to infer latent features explicitly, but
to represent these features implicitly in the kernels, making the method
scalable to large networks. In contrast to the other methods for latent feature models, our method inherits all the advantages of kernel framework:
optimality, eﬃciency and nonlinearity. We apply our method to real dataof protein-protein interactions to show the merits of our method.

1

Introduction

Link prediction is a major problem in relational data learning [6]. In Social
Networks and Collaborative Filtering, one needs to suggest links for entities
for recommendation. In Bioinformatics and Chemoinformatics, potentially valid
links such as interactions are required to speed up experimental processes. In
order to predict links in relational data, one needs to provide a common model
for both entities and relationships (such as links) in the data. As these two
types of information are of diﬀerent natures, models are diﬃcult to design andlearn. While modeling entities are of common practice, modeling relationships
is usually of more diﬃculty. For link prediction, these relations are interpreted
diﬀerently and reﬂect diﬀerent semantics. While in social networks, links areusually of similarity or relatedness nature, it is not the case elsewhere. It is thetarget of this work to deal with a more general type of network structures, tobuild link models and to train them on large-sized real data.
In principle, there are two diﬀerent kinds of information used to learn a linkmodel for link prediction. One is the information of network entities such as
nodes of the networks. The methods falling in this category usually use the information of a pair of nodes to induce the label of having or not having a link
D. Gunopulos et al. (Eds.): ECML PKDD 2011, Part II, LNAI 6912, pp. 517–532, 2011.
c Springer-Verlag Berlin Heidelberg 2011


518

C.H. Nguyen and H. Mamitsuka[2,8,3]. Typical examples are sequences or proﬁle information of genes, which
are used to predict links (edges) in their networks. By using only the information on networks’ entities, the models of the networks assume an independentand identical distribution of links. In other words, the structures of the links
themselves are completely ignored. This is an unrealistic assumption in many
domains where networks’ structures themselves have patterns, such as social
networks [12,13] and biological networks [18,1]. It is an objective of this work toshow that network structures themselves contain information for the task.
The second kind of information used to predict links is structures (topologies)of the networks themselves. Similarity networks, due to its analogy to kernels[10,7,17,16,11], can be modeled with kernels and therefore, there exist scalable
methods. Bipartite networks can also rely on kernels for each of their parts
together with aligning the parts [19]. However, it is more diﬃcult to deal with
networks without similarity or relatedness semantics. A common network type ismodeled with latent feature models [14,1]. This network model includes similarity
networks and bipartite networks as special cases. For this type of networks, theavailable models are usually the plain latent feature models or matrix basedmodels [5,1,13]. Training these models usually requires to generate latent features
explicitly. This is a very time-consuming process, usually does not applicable tomedium-sized networks. Another problem is that approximation in the training
process leads to suboptimal solutions. Without approximation, these models
do not scale to the sizes of real data, even for medium-sized networks. It is our
motivation to be able to learn a model of this general type of networks eﬃciently
and to avoid suboptimal solutions.

Fig. 1. Given an adjacency matrix as input, the method embeds cells (links or nonlinks)
into a feature space and using classiﬁcation to infer new links

We provide a kernel method to link prediction problem using network structures for the network structures modeled with latent features. The overall description of the method is depicted in Figure 1. We design kernels to encode thestructures implicitly, without the need of generating the latent features themselves. The idea is to give high kernel values to the pairs of links that potentiallyshare latent features. We show how suitable the kernel is to sparse networks. By
not inducing the latent feature directly, our method is much faster comparedto the long execution times faced by the methods that explicitly induce latentfeatures. Our method also gives a globally optimal solution as opposed to theother methods. Nonlinearity can be incorporated into the model seamlessly. For

Kernels for Link Prediction with Latent Feature Models

519

these advantages, our method gives a very high predictive performance for link
prediction problems and applicable to real datasets of large sizes.
The paper is organized as follows. We describe the generative model of networks’ links with latent features in Section 2. We then develop our kernels forthis model in Section 3. We visualize the idea of the kernels for this model in
Section 4. We show our application in protein-protein interaction networks in
Section 5 and conclude the paper.

2

Latent Feature Models of Graphs

2.1

Biological Motivation

An example is that a protein (node) is a collection of domains (features). A
protein-protein interaction (PPI) is caused by an interaction between two domains from the two proteins [4]. However, the knowledge of domain may be
incomplete, and domain-domain interaction is far less understood. Therefore,
we wish to incorporate the domain-domain interaction knowledge in an implicit
way. Given enough links, we want to infer from many pairs of interacting proteins’ common features that play the role of domains and some pairs of features
are likely to interact for PPI task.
2.2

Latent Feature Models of Graphs

We describe a latent feature model of graphs as also appeared in [13]. In thismodel, a link (edge) in the graph is generated by the relation between the latentfeatures of the adjacent nodes. Denote A ∈ Rn×n as the adjacency matrix ofthe graph. In general, A can be any real matrix. For our special purpose ofmodeling undirected networks, we assume that A is a binary symmetric matrix.
Denote F ∈ Rn×d as a binary matrix where each row is a d-dimensional vector of
latent features. Denote W ∈ Rd×d as a real matrix encoding strength of featureinteractions. That is, Wij encodes the strength of interaction between the ith
feature and the j th feature. We deﬁne that (F ,W ) is a latent feature model for
A when(1)
A = FWFT.
It is possible that there are several causes for a link but we only record one link
(existence of a link rather than multiplicity of the link). Therefore, the equality
in the equation (1) is replaced by the element-wise operator min(x, 1) where x
is the entry of the right hand side of the equation (1). It can be rewritten as
follows(2)
A = min(F W F T , 1).
Simulation Example: The idea of latent feature model is depicted in Figure
2. In this example, the set of nodes have three latent features, with the ﬁrst two
nodes has two features. As for the feature interaction matrix, it indicates thatthe ﬁrst and the second features interact, also the third feature interact withitself.

520

C.H. Nguyen and H. Mamitsuka

2

2

4

4

6

6

8

8
1

10

1

2

2

3

3
1

12

14

2

3

10

2

4

6

8

10

12

14

16

12

14

16

16

1

2

3

2

4

6

8

10

12

14

16

Fig. 2. F W F T → A: the adjacency of the graph (rightmost) is generated by the threematrices: the latent feature matrix (F - leftmost), the feature interacting matrix (W )and the transpose of the latent feature matrix (F T ). A black cell indicates a positive
entry and a white cell indicates a 0 entry. In our latent feature model, product of theﬁrst three matrices generates the last one.

For the beneﬁts of using latent feature models instead of latent class models,
we refer to [13] for details. The following properties are observed.
– Each entry of W generates a subgraph given F . The overall generated graphis a superimposition of these subgraphs. This makes the model an additiveone.
– If W is diagonal, then the generated graph can be decomposed as a set ofcliques. This is a model of similarity graph.
– If W is symmetric, then the generated graph is symmetric. It is usually used
to encode undirected graphs.
– If F has exactly one nonzero entry in each row (such as the ones generated
by Chinese Restaurant Processes (CRP)), then generating F is equivalent
to clustering of nodes.
– If the nodes can be divided into two groups, each with a separate set offeatures, and W has only interactions of features from the two diﬀerent sets,then the generated graph is bipartite.
These properties make latent feature models general generative models for graphs.
2.3

Ideal Kernels

Given a latent feature model as a generative model of graphs, one wish to deﬁnea kernel that encodes the similarity of the nodes using this model. The semantic
similarity of two nodes under this model is the amount of latent features theyshare, weighted by the importance of each feature. Therefore, we deﬁne the ideal
kernels as follows.
Definition (Ideal kernels). Deﬁne the set of ideal kernels for a latent featuremodel of nodes F to be K = {K ∗ (D)}D , with D ∈ Rd×d is any diagonal matrix
with positive entries, andK ∗ (D) = F DF T .
(3)
A kernel value K ∗ (D)ij = Fi D(Fj )T is the weighted sum of the number ofcommon feature between the i-th and j-th nodes. However, since latent featureKernels for Link Prediction with Latent Feature Models

521

models are hardly obtained, the ideal kernels are not available. Any kernel deﬁned from data with latent feature models should be close to some ideal kernels
in some senses.

3

Link Kernels with Latent Features

We describe our kernel method to link prediction given the latent feature model
assumption of the graph structures. The idea is to use the model to derive akernel between all pairs of the nodes (called link kernel). We deﬁne the following
terms: a link is considered as a positive pair of nodes while a negative pair ofnodes encodes the non-existence of a link (nonlink).

Input: Adjacency matrix A.
1. Construct a node kernel Kn following latent feature models.
2. Construct a link kernel K based on Kn .
3. Learn a SVM on K.
Output: New adjacency matrix based on the SVM.

Fig. 3. Network Structure based Link Prediction

The link prediction problem is then formulated as a binary classiﬁcation problem. In the end, we classify the two classes, link class and nonlink class using
Support Vector Machines. The overall strategy is in Figure 3.
The kernel between pairs is based on the kernel between nodes themselves(called node kernel). We ﬁrst describe the node kernel (Kn ) that encodes thelatent feature model, its relations to ideal kernels in sparse graphs, and then thelink kernel.
3.1

Node Kernels with Latent Features

As latent feature models are the generative models of graphs, we wish to deﬁne
the similarity of two nodes as the likelihood of having common latent features.
This is inherently diﬀerent from similarity models where similarity means thelikelihood of reaching the other node through random walks [12]. However, latentfeatures are implicit, we must estimate the similarity, in form of kernels, between
nodes empirically. Knowing that nodes with common features tend to link tocommon neighbors in latent feature models, we deﬁne the basic node kernels as
the amount of common neighbors of the nodes, as follows.
Kn = norm(AAT ),

(4)

522

C.H. Nguyen and H. Mamitsuka

where norm indicates the normalization operator to make the diagonal elements
all 1. Speciﬁcally,(AAT )ij(Kn )ij = .
(5)(AAT )ii (AAT )jj
A special case of this kernel is when all the nodes have exactly one feature (suchas generated by CRP), then Kn (a, b), for any node a and b, is either 1 or 0,
indicating if they have the feature in common or not. An implication is that in
networks where latent features are expected to be sparse, Kn behaves similarly
to this extreme case, showing a good indication of common latent features.
Given the basic node kernel, additional tricks can be applied on top of thiskernel to make new families of kernels. Diﬀusion kernels and exponential kernels
on top of Kn still conserve the idea of latent features. Of course, the higher the
exponential we take on Kn the looser the idea can be kept. However, please notethat the most general version of spectral transform [11] is not guaranteed toconserve the latent feature assumption.
Note that this node kernel can be one of many terms in other kernels for
similarity graphs such as path-based [15,10,7,12]. However, we ﬁnd that our
proposed kernel in particular encodes the latent feature model that is suitablefor our problem.
3.2

Relation to Ideal Kernels on Sparse Graphs

When the graphs are sparse (in our applications), sparse models are required tomodel them. The following propositions show the relationship between the node
kernel Kn and the ideal kernels when the models are sparse. Denote Si as theset of latent features of node i.
Proposition 1 (Positivity). If Si ∩Sj = ∅ (two nodes i and j share at least one
latent feature) and that feature interacts with another feature, then (AAT )ij > 0,
therefore (Kn )ij > 0.
Proof. The proof can be easily seen because when they share a feature, they
have a common nonempty neighborhood and therefore, (Kn )ij > 0.
This shows that if the values of ideal kernels on two nodes are positive, the valueof Kn is positive as well. This means that whenever the two nodes are similar(positive kernel value) in the model, the kernel Kn can recognize that. This isuseful for sparse graphs (causing sparse kernels), Kn is not sparser than any
ideal kernel.
Proposition 2 (Monotonicity). Suppose that the edges have the same amountof neighbors in the sense that (AAT )ii (AAT )jj = (AAT )kk (AAT )ll . If (Si ∩Sj ) ⊇(Sk ∩ Sl ) then (Kn )ij ≥ (Kn )kl .
The ﬁrst assumption is about the equal amounts of neighbors for the two pairsof nodes. The amount of neighbors of a pair of nodes is deﬁned to be the productKernels for Link Prediction with Latent Feature Models

523

of numbers of its adjacent nodes. The conclusion is that, the more latent features
they share, the higher the kernel value is. This is a property of the ideal kernels
by the way they are deﬁned, showing an analogy of Kn to ideal kernels.
Proof. As (Si ∩ Sj ) ⊇ (Sk ∩ Sl ), the common neighborhood of the nodes i and j
is a superset of the the common neighborhood of the nodes k and l. Therefore,(AAT )ij ≥ (AAT )kl .
(AAT )ij(AAT )kl(Kn )ij = ≥= (Kn )kl
(AAT )ii (AAT )jj(AAT )ii (AAT )jj
from the deﬁnition of the node kernel in (4).

(6)



Lemma 1 (One feature interaction). For any latent feature model (F ,W ),there exists another latent feature model (F ,W ) that gives (i) the same adjacency matrix, (ii) the same set of ideal kernels and (iii) the feature interaction
matrix is nonzero on at most one of its entries in any row and column.
In other words, there exists another mathematically equivalent model giving thesame ideal kernel sets and adjacency matrix in which each feature interacts with
only one another feature.
Proof. The idea of the proof is to place a nonzero wij in one new row and columnof W and duplicate the columns of F when necessary to make F , keeping
the adjacency matrix unchanged. Supposed that the (unnormalized) adjacency
matrix A is computed bywij F·i (F·j )T ,(7)
A = FWFT =ij

where F·i is the i-th column of F.
Denote I = {(i, j)} that wij = 0 thenA=

wij F·i (F·j )T .

(8)(i,j)∈I

We then construct the F and W by sequentially appending feature columns
and feature interaction matrix values in the formula 8 as follows.
1. Mark all the indices in I as available.

2. Initialize F and W to empty matrices.
3. Go the the next available index in I, pick the pair wij , then
– If i = j, meaning that wii indicates a self interacting feature, then appendthe feature vector F·i at the end of the already constructed F . Append
a new row and column of W with the only nonzero element wij on thediagon of W . Mark the index of wij in I unavailable. Repeat the processfrom step 3.

524

C.H. Nguyen and H. Mamitsuka– If W is symmetric (A is symmetric) then wij = wji . Append the feature
vectors F·i and F·j to the end of F . Suppose the size of W is k, then
append two new rows and columns of W with the only nonzero elements
are wij at Wk+1,k and Wk,k+1 . Mark the indices of wij and wji in I
unavailable. Repeat the process from step 3.
– If W is not symmetric then append the features as the symmetric caseto F . For W , only one nonzero element is added to Wk,k+1 . Mark theindex of wij in I unavailable. Repeat the process from step 3.
By doing this, thenF W (F )T =



wij F·i (F·j )T = F W F T = A.

(9)(i,j)∈I

Also, each row or column of W has at most one nonzero entry by the way W
is constructed. Since the set of columns of F is the same as F ’s, the set of ideal
kernels are the same (only diﬀerent by feature weighting).
Hence, we have constructed a new model with a feature either interacts or isinteracted with at most one another feature. This is to say that there is a mathematically equivalent model that each feature only interacts with one anotherfeature. We use this fact to facilitate our sparsity reasoning as follows.
Proposition 3 (Ideal condition). Kn is an ideal kernel (Kn ∈ K) if W F T
has all row vectors uncorrelated.
Proof. When W F T has row vectors uncorrelated, then: W F T × (W F T )T is
diagonal. Denote D = W F T × F W T , then:Kn (A) = F W F T × F W T F T = F DF T .
Since D is diagonal with nonnegative entries, Kn ∈ K.

(10)



Corollary 1. If W is an unmixing matrix of an Independent Component Analysis model for F T , then Kn ∈ K.
Corollary 2. If each node has only one latent feature, such as F is generated
by a Chinese Restaurant Process or any class-based model in a model that W
has only one nonzero entry in each row or column (guaranteed by Lemma 1),
then Kn ∈ K.
This is from the fact that W F T has only one nonzero entry in each column,
therefore any pair of row vectors would have no nonzero entries in common.
This makes row vectors of W F T uncorrelated.
When the model is sparse, Kn is close to an ideal kernel as follows. Denote
E = F T F , therefore Elk = (F·l )T F·k is number of nodes having both featuresl and k. When l = k, we expect Elk to be small for sparse models. Given theLemma 1, we assume that Wil and Wjk are the only nonzero entries in rows iKernels for Link Prediction with Latent Feature Models

525

and j. Recall that Kn = F DF T = F W EW T F T . Since the entries of W are2
2
scalars, Dij = Wil Wjk Elk means that Dij/(Dii Djj ) = Elk/(Ell Ekk ). When F issparse, oﬀ-diagonal elements of E is much smaller than diagonal ones (diagonallydominant ), the same thing can be said for D. This means that D is as diagonallydominant as E. We show quantitatively how close D is to an ideal kernel.
Proposition 4 (Approximation). When the model is sparse in the sense that1( i=j |Wil Wjk Elk |p ) p ≤ δ for some small δ ∈ R, p ≥ 0, there exists an ideal
kernel F D̂F T that is close to Kn in the sense that D − D̂ p ≤ δ.
1
In the condition ( i=j |Wil Wjk Elk |p ) p , an entry Wil Wjk Elk is the weighted thenumber of nodes having the two features l and k (should also be small for sparsemodels, l = k inplies i = j). · p is the p-norm of a matrix.
Proof. We construct D̂ as a diagonal matrix with D̂ii = Dii = Wil2 Ell . Given
that Dij = Wil Wjk Elk , then11
|Dij |p ) p = (|Wil Wjk Elk |p ) p ≤ δ.
(11)
D − D̂ p = (
i=j

i=j

This shows that the more sparse the model, the closer D is to ideal kernels. When a model is sparse in the sense that each node has very few latent features,
each latent feature interacts with one another features (by the Lemma 1), Kn
should be close to the ideal kernel F D̂F T since F D̂F T is linear in D̂.
All these properties make the kernel Kn a good approximation of ideal kernels in sparse models. Sparse models are suitable for our applications in sparse
networks (nodes with small degrees). We elaborate more in the application part.
3.3

Link Kernels with Latent Features

Given the node kernel Kn , a kernel between two links is usually deﬁned to be
the combined similarity between the pairs of nodes of the links. We choose thewidely used and experimentally justiﬁed tensor product pairwise kernel [2] to be
the kernel for pairs as follows.
K((a, b), (c, d)) = Kn (a, c) · Kn (b, d) + Kn (a, d) · Kn (b, c).

(12)Here is the kernel for the two pairs of nodes (a, b) and (c, d). Denote ai , bj as
the features of a and b respectively in the feature space of Kn , then the feature
space of K consists of the following features for a pair (a, b):
ai b j + aj b i ,(13)

as in [2]. Given that the node kernel Kn is supposed to be the likelihood of
having common latent features, link kernel indicates the chance of having two
pairs of nodes with common features. For example, when the pair {a, c} sharecommon features and so do the pair {b, d}, K((a, b), (c, d)) is high.
Nonlinearity can be incorporated into this kernel, such as Gaussian kernels
on top of it.

526

4

C.H. Nguyen and H. Mamitsuka

Demonstration

We show the idea of our kernel using the simulation example in the previous
section. Suppose that we observe an incomplete graph of the example as in theadjacency matrix in Figure 4 (80% of the links are observed). We show step bystep the idea of node kernels and latent features.
0.4
0.3
0.2
2

0.1
4

0
6

−0.1

8

−0.2

10

−0.3

12

−0.4

14

−0.5
0
−0.2
−0.4

16

0.4
2

4

6

8

10

12

14

0.3

0.2

0.1

0

−0.1

−0.2

−0.3

16

Fig. 4. Adjacency matrix of an incompletegraph from the simulation example

Fig. 5. Visualing the graph with the node kernel. The cyanedges are the observed links of the graph while the red edges
are the missing ones according to the model. We observedthat the red ones follow the same patterns as the cyan ones.

Node Kernel: We visualize the nodes using the node kernel deﬁned in (4). We
use kernel PCA and plot the nodes using the ﬁrst three components in Figure
5. The nodes in the ﬁgure are the nodes of the graphs. The cyan edges are
the observed links. The red edges are the missing links according to the model.
First, we can observe that the cyan edges follow certain patterns of direction andendpoints. Another point can be observed is that the red edges follows the same
patterns (endpoints lie in clusters, edges connect the same cluster pairs). Thisis exactly what we want in learning, testing data having the same distribution
as training data. What left to be done is to keep these patterns in some spatial
representations of the edges.
Latent Features: We look into the model to show the distribution of nodes withfeatures. We label the nodes with the same feature in shaded ellipses in Figure 6.
The labels of the eclipses, F 1, F 2 and F 3 correspond to the three latent featuresin the example. We can observe that the node kernel makes these nodes close toeach other. The nodes with two features (F 1 and F 3) lie somewhere in between
the nodes with only one of the two features (F 1 or F 3).
Negative Links: As shown in Figure 5 that the observed edges and missing
edges have similar patterns. However, we use SVM to classify, we also wish thenegative class (nonlink) not to follow the patterns. Therefore, we show all theedges that belong to the nonlink class in Figure 7. We can observe that they do
not follow that patterns of the positive class (the same endpoints but connecting
diﬀerent cluster pairs from positive links’).

Kernels for Link Prediction with Latent Feature Models

Fig. 6. The positive class of links. The
nodes are grouped by their common latentfeatures. It shows that nodes sharing morecommon features tend to group together.

527

Fig. 7. The set of nonlink class. Compared to the link class, the nonlink class
has totally diﬀerent positions and orientations.

The demonstration shows that our designed node kernel successfully discovers
the patterns of the link class as opposed to the nonlink class. It tends to groupthe nodes with common features close to each other as we designed. We wish toclarify the diﬀerence of our method from the other methods such as using Chinese
Restaurant Processes or Indian Buﬀet Processes [14,9,13]. These methods groupthese nodes together explicitly while our method use a soft version of putting
them close in a space. We believe that this is the key to be robust, allowing theinference step to be globally optimal and computationally eﬃcient.

5

Application on Non-similarity Networks with Latent
FeaturesOur targeted application is to model network structures with the latent featuremodels. Even though the model includes similarity networks as special cases, ourtarget is to model more diﬃcult ones, which are not similarity ones. Social networks are usually similarity ones, therefore not the prime target of our method.
The PPI networks are the typical examples as it is non-similarity (we also show
the experiments for this in the following subsection). There are other networks
studied in Bioinformatics but they are too sparse and not large enough to study
structures statistically.
We used the PPI networks of yeast and fruit-ﬂy from DIP database for theirlargest hand-curated networks available. For statistical study, we attracted only
the largest connected component of the network in which the degree of each node
is not less than m (minimum degree of nodes). In our experiments, we show all
the values of m from 1 to 10 (8 for fruit-ﬂy). For yeast, the subnetwork with
m = 1 has 4762 nodes and 21836 links, and the subnetwork with m = 10 has 756
nodes and 8924 links. For fruit-ﬂy, the subnetwork with m = 1 has 6644 nodes
and 21501 links, and the subnetwork with m = 8 has 713 nodes and 5243 links.
This is the size of data that we expect and we will show latter on that the othermethods based on latent feature inference do not scale to this size.

528

C.H. Nguyen and H. Mamitsuka

Real PPI networks are sparse: less than 20% of the nodes in yeast and none
in fruit-ﬂy have degrees of 10 or more. This is the reason for sparsity analysis in
Section 3.2. The sparse networks require the models to be sparse as well.
For each subnetwork, we used SVM (C = 0.001, but the results are the samefor a range of C from 0.0001 to 0.1) as the classiﬁer for our link kernels. We
showed the average AUC score of diﬀerent train/test splits with the ratio 90/10.
We ﬁrst showed the appropriateness of the assumption of latent features as
opposed to the usual assumption of similarity. We then showed the time required
to build one model to reﬂect the diﬀerence in execution times or our method
compared to Indian Buﬀet Process (IBP) as described in [13] (with parameter
α = 3, which we found to be a good trade-oﬀ to be able to train on our smallest
datasets and induce a model with enough number of latent features). We thenshowed the performance of link kernels in link prediction. We also compared tosequence based link prediction to show the advantage using network structures.

Fig. 8. Latent feature versus similarity assumption: AUC of the direct method for link
prediction (vertical) at diﬀerent minimum degree of the network (horizontal axis)

5.1

Latent Feature versus Similarity

We show the ﬁtness of the latent feature model on yeast PPI networks as opposedto the similarity model in Figure 8. We used the direct method [18] to predict
links based on the two models. The idea of the direct method is simply nearest
neighbor classiﬁers. For similarity assumption, probability of having link between
two nodes is proportional to how similar they are in their connectivity patterns(called SimNN). On the other hand, with latent feature model, probability of alink between two nodes is determined by the class of its nearest neighbor in thelink kernel (called LK-NN), not the kernel between nodes.
The ﬁgure showed a signiﬁcantly diﬀerent AUC scores of the two methods
on yeast’s networks. LK-NN was usually much higher (around 0.1 and more).
It showed that latent feature model was more suitable to PPI networks thanthe conventional similarity one. The exception was at the subnetwork with theminimum degree of nodes of one. Since we were using only network structures,
the nodes with degree one may not contribute to the network structure in theseKernels for Link Prediction with Latent Feature Models

529

models. Therefore, results for the subnetworks with larger nodes’ degrees demonstrated the reasonability of the assumptions used. For this reason, the latentfeature assumption was more reasonable than similarity assumption here, andthe methods for similarity networks were not recommended to use.
5.2

Execution TimeWe show execution time required to build one model using our link kernels in
Figure 9. To compare to IBP, we also show the execution time in the process ofbuilding one model before it burns in in Figure 10. For the long times requiredby IBP, we only show the execution time for the smallest subnetwork (minimum
degree of 10 with only 756 nodes), which is supposed to require the least time
among all the subnetworks.

Fig. 9. The time required to build one
model using link kernels (in seconds) at
subnetworks with diﬀerent minimum degrees. Note that for the smallest subnetwork, the execution time is less than 90
seconds.

Fig. 10. The time to train an IBP modelof the smallest subnetwork with m = 10.
The vertical axis is the log-likelihood obtained from the model during the training
process as a function of time in the horizontal axis.

We can see that the link kernels required less than 90 seconds for the smallest
subnetwork, and increased to less than 500 seconds for the largest subnetworkof 4762 nodes. On the other hand, IBP required many hours for the smallest
subnetwork of 756 nodes and did not burn-in on larger ones within one day. We
conclude that our method using kernel saved many orders of magnitude the timeto train one model, making training on medium-sized networks possible. This isa key advantage of our kernel method.
5.3

Link Prediction Results

We compared the prediction ability of our method using link kernel to the baseline of using IBP as in [13] in Figure 11. The results are for diﬀerent subnetworks
with diﬀerent minimum degrees. For small minimum degrees, the subnetworks
have higher coverage on the whole network while the large minimum degrees

530

C.H. Nguyen and H. Mamitsuka

Fig. 11. Link prediction results on yeast PPI network: AUC of link prediction with
diﬀerent methods (vertical) at diﬀerent minimum degrees of the network (horizontalaxis). Note that IBP does not scale with larger datasets, its results are not available.

will extract denser parts of the network, making statistical inference on thispart more reliable. We show two versions of our link kernels: linear kernels andGaussian kernels (γ = 2). The incomplete results of IBP was due to the factthat experiments took too much time (more than one day) to train one model.
We can read from yeast’s results in Figure 11 that linear kernels had similar
AUC scores with IBP. However, when using the nonlinear version of Gaussian
kernels, AUC scores were signiﬁcantly higher. We conclude that our kernel based
method provided a signiﬁcantly higher AUC scores than that of IBP. One surprise was that even using only network topology, we archived high AUC scores
close to 0.9. These scores were much higher than random prediction. Given that
the PPI networks are known to be noisy and incomplete, this experiment showedthat there are patterns of the topology of the PPI networks. It also showed that
our method was eﬀective to encode these patterns.

Fig. 12. Link prediction results on fruit-ﬂy PPI network: AUC of link prediction with
diﬀerent methods (vertical) at diﬀerent minimum degrees of the network (horizontalaxis). IBP results are missing due to their time consumption.

Kernels for Link Prediction with Latent Feature Models

531

Similarly, we can see in the fruit-ﬂy’s results in Figure 12 that our method
based on kernels outperformed IBP. The results on fruit-ﬂy’s networks were much
lower than on yeast due to the fact that fruit-ﬂy’s ones are sparser, involving
more proteins and there are no proteins with degrees of 10 or more.
5.4

Comparison to Sequence-Based Prediction

As opposed to using network structures, traditional methods use nodes’ information such as protein sequences. Therefore, we also compared to spectrum kernels
on sequences to predict links in the same manner. The results were not shown in
the Figure 11 and 12 because they ranged diﬀerently. The highest AUC score on
any subset for yeast was 0.71 ± 0.008 and 0.65 ± 0.016 for fruit-ﬂy. We observethat network structures gave statistically signiﬁcantly higher AUC scores (witht -tests at 0.01 level). This might be due to the fact that kernels based on sequences contain too much redundant information, since sequence-based kernels
use all k-mers across the protein sequences. Sequence based kernels are redundant as only small parts determine its interaction ability to others.

6

Conclusion

We studied the problem of predicting new links using network structures in amore general type of networks. Speciﬁcally, we studied the networks that canbe modeled by generative processes with latent features. This is a more generalmodel of networks than the usually assumed similarity networks in most of theapplications. In order to model real networks of medium or large size, we usedkernels and casted the problem as a supervised learning one, inheriting optimality, eﬃciency and nonlinearity of the kernel framework. We showed the suitabilityof the kernels on sparse networks. We applied to the non-similarity networks ofprotein-protein interactions. The results showed that our kernel-based method
gave a much higher performance than direct latent feature inference by IBP. Our
method was also many orders of magnitude faster, and scaled to the sizes of real
networks, unlike IBP. It was also shown that network structures gave higher results than information of the nodes. We conclude that for sparse networks withlatent feature models, our method is able to utilize the relevant informationin network structures to give faster, more scalable solutions, and signiﬁcantly
higher performances.
Acknowledgments. C.H.N. is supported by JSPS. H.M. has been partially
supported by BIRD, JST (Japan Science and Technology Agency). We acknowledge anonymous reviewers for helpful comments.

References
1. Airoldi, E.M., Blei, D.M., Fienberg, S.E., Xing, E.P.: Mixed membership stochastic
blockmodels. Journal of Machine Learning Research 9, 1981–2014 (2008)
2. Ben-Hur, A., Noble, W.S.: Kernel methods for predicting protein-protein
interactions. In: ISMB (Supplement of Bioinformatics), pp. 38–46 (2005)

532

C.H. Nguyen and H. Mamitsuka

3. Bleakley, K., Biau, G., Vert, J.-P.: Supervised reconstruction of biological networks
with local models. In: ISMB/ECCB (Supplement of Bioinformatics), pp. 57–65(2007)
4. Deng, M., Mehta, S., Sun, F., Chen, T.: Inferring domain-domain interactions
from protein-protein interactions. In: Proceedings of the Sixth Annual International
Conference on Computational Biology, pp. 117–126. ACM Press, New York (2002)
5. Ding, C.: Orthogonal nonnegative matrix tri-factorizations for clustering. In:
SIGKDD, pp. 126–135 (2006)
6. Getoor, L., Taskar, B.: Introduction to Statistical Relational Learning (Adaptive
Computation and Machine Learning). The MIT Press, Cambridge (2007)
7. Kandola, J.S., Shawe-Taylor, J., Cristianini, N.: Learning semantic similarity. In:
NIPS, pp. 657–664 (2002)
8. Kato, T., Tsuda, K., Asai, K.: Selective integration of multiple biological data forsupervised network inference. Bioinformatics 21(10), 2488–2495 (2005)
9. Kemp, C., Tenenbaum, J.B., Griﬃths, T.L., Yamada, T., Ueda, N.: Learning systems of concepts with an inﬁnite relational model. In: Proceedings of the 21st
National Conference on Artiﬁcial Intelligence, vol. 1, pp. 381–388. AAAI Press,
Menlo Park (2006)
10. Kondor, R.I., Laﬀerty, J.D.: Diﬀusion kernels on graphs and other discrete input
spaces. In: ICML, pp. 315–322 (2002)
11. Kunegis, J., Lommatzsch, A.: Learning spectral graph transformations for link prediction. In: ICML 2009: Proceedings of the 26th Annual International Conference
on Machine Learning, pp. 561–568. ACM, New York (2009)
12. Liben-Nowell, D., Kleinberg, J.M.: The link prediction problem for social networks.
In: CIKM, pp. 556–559 (2003)
13. Miller, K., Griﬃths, T., Jordan, M.: Nonparametric latent feature models for link
prediction. In: Bengio, Y., Schuurmans, D., Laﬀerty, J., Williams, C.K.I., Culotta,
A. (eds.) Advances in Neural Information Processing Systems, vol. 22, pp. 1276–
1284 (2009)
14. Navarro, D.J., Griﬃths, T.L.: A nonparametric bayesian method for inferring features from similarity judgments. In: NIPS, pp. 1033–1040 (2006)
15. Newman, M.E.J.: Clustering and preferential attachment in growing networks.
Physical Review E 64(2), 025102+ (2001)
16. Shimbo, M., Ito, T., Mochihashi, D., Matsumoto, Y.: On the properties of vonneumann kernels for link analysis. Machine Learning Journal 75(1), 37–67 (2009)17. Smola, A.J., Kondor, R.: Kernels and regularization on graphs. In: Schölkopf, B.,
Warmuth, M.K. (eds.) COLT/Kernel 2003. LNCS (LNAI), vol. 2777, pp. 144–158.
Springer, Heidelberg (2003)
18. Vert, J.-P., Yamanishi, Y.: Supervised graph inference. In: NIPS (2004)
19. Yamanishi, Y.: Supervised bipartite graph inference. In: NIPS, pp. 1841–1848(2008)