IEEE TRANSACTIONS ON NEURAL NETWORKS AND LEARNING SYSTEMS, VOL. 23, NO. 11, NOVEMBER 2012

1793

Latent Feature Kernels for Link
Prediction on Sparse Graphs
Canh Hao Nguyen and Hiroshi Mamitsuka
Abstract— Predicting new links in a network is a problem ofinterest in many application domains. Most of the prediction
methods utilize information on the network’s entities, such as
nodes, to build a model of links. Network structures are usually
not used except for networks with similarity or relatedness
semantics. In this paper, we use network structures for link
prediction with a more general network type with latent featuremodels. The problem with these models is the computational costto train the models directly for large data. We propose a method
to solve this problem using kernels and cast the link prediction
problem into a binary classification 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 featuremodels, our method inherits all the advantages of the kernelframework: optimality, efficiency, and nonlinearity. On sparsegraphs, we show that our proposed kernels are close enough tothe ideal kernels defined directly on latent features. We apply
our method to real data of protein–protein interaction and gene
regulatory networks to show the merits of our method.
Index Terms— Latent feature kernels, latent feature models,link prediction, sparse graphs.

I. I NTRODUCTIONL

INK prediction is a major problem in relational data
learning [1]. In social networks and collaborative filtering, one needs to suggest links for entities for recommendation. In bioinformatics and chemoinformatics, potentiallyvalid links such as interactions are required to speed up
experimental processes. In order to predict links in relationaldata, one needs to provide a common model for both entities
and relationships (such as links) in the data. As these two typesof information are of different natures, models are difficult
to design and learn. While modeling entities is common
practice, modeling relationships is usually more difficult. For
link prediction, these relationships are interpreted differently
and reflect different semantics. While in social networks links
are usually of similarity or relatedness nature, it is not thecase elsewhere. It is the aim of this paper to deal with a moregeneral type of network structures to build link models and to
train them on large-sized real data.

Manuscript received June 8, 2012; revised August 16, 2012; accepted
August 19, 2012. Date of publication October 2, 2012; date of current
version October 15, 2012. The work of C. H. Nguyen and H. Mamitsuka
was supported in part by the Institute for Bioinformatics Research andDevelopment (BIRD) of the Japan Science and Technology (JST) agency
and KAKENHI Grants-in-Aid for Scientific Research under Grant 24300054
of MEXT, Japan. The work of C. H. Nguyen was supported in part by theJapan Society for the Promotion of Science.
The authors are with the Bioinformatics Center, Institute ofChemical Rerearch, Kyoto University, Kyoto 611-0011, Japan (e-mail:canhhao@kuicr.kyoto-u.ac.jp; mami@kuicr.kyoto-u.ac.jp).
Color versions of one or more of the figures in this paper are available
online at http://ieeexplore.ieee.org.
Digital Object Identifier 10.1109/TNNLS.2012.2215337

In principle, there are two different kinds of information
used to learn a link model for link prediction. One is the information on entities of networks such as nodes. The methods
falling in this category usually use the information of a pair ofnodes to induce the label with or without a link [2]–[4]. Typicalexamples are sequences or profile information of genes, which
are used to predict links (edges) in their networks. By using
only the information on the entities of networks, the models of
the networks assume an independent and identical distributionof links. In other words, the structures of the links themselves
are completely ignored. This is an unrealistic assumption
in many domains where structures of networks themselves
have patterns, such as social networks [5], [6] and biologicalnetworks [7], [8]. There are different models for networks suchas class-based [9], [10], feature-based [11], [12], or spacebased [13], [14] models that have been proven to be usefulfor networks from a variety of domains of application. It isan objective of this paper to show that network structures
themselves contain information for the task.
The second kind of information used to predict links is
the structures (topologies) of the networks themselves, withor without node information. Similarity networks, becauseof their analogy to kernels [15]–[20], can be modeled withkernels and, therefore, there exist scalable methods. Bipartite
networks can also rely on kernels for each of their parts
together with aligning the parts [21]. Relational graphicalmodels [10], [22], [23] are more general, allowing the incorporation of node information with topological templates. Thesemodels are difficult to adapt to specific network models as wellas computationally expensive. One special type of network
structure, which is of interest recently, is models with latentfeatures [8], [12], [24]. For this type of networks, the available
models are usually the plain latent feature models [6], [8] ormatrix-based models [13], [14]. Training these models usuallyrequires the generation of latent features explicitly. This isa very time-consuming process, and usually does not obtain
globally optimal solutions. It is difficult to scale them to
networks with thousands of nodes. More details of the network
structure models can be seen in [25]. In this paper, we deal
with latent feature models of network structures.
The problem we are faced with is that networks are known
to be generated from latent features. It is the case in biologicalnetworks where a link is a physical attachment of proteins.
These networks are nonsimilarity networks in the sense thata link between two nodes does not mean that the nodes havesome features in common [26]. Methods for social networks
usually use similarity semantics and, therefore, are not suitablefor our problem. The features that generate the links in the
networks are usually not known for all the nodes in the2162–237X/$31.00 © 2012 IEEE

1794

IEEE TRANSACTIONS ON NEURAL NETWORKS AND LEARNING SYSTEMS, VOL. 23, NO. 11, NOVEMBER 2012

networks, and therefore the methods using information on
network entities are not applicable. We need to use patternsof network structures to model the networks themselves.
On our targeted applications, one key point is that these networks are reasonably sparse. We also show some statistics inthe application sections on real data. The good news is that, insparse networks, if their structures can be learned statistically,
the connectivity pattern for each node must be governed by asmall number of factors. By having a small number of different
factors for a node, there is a high chance that the links fromthe node share the same factor, i.e., have the same generative
pattern. In essence, the connectivity patterns can give some
information about the global structure of the networks, making
it possible to predict new links in the networks using thesepatterns (see Section IV for a formal analysis).
We provide a kernel method to the link prediction problem
using network structures that are modeled with latent features.
The overall description of the method is depicted in Fig. 1.
We design kernels to encode the structures implicitly, without
the need for generating the latent features themselves. The
idea is to give high kernel values to the pairs of links that
potentially share latent features. We show analytically how
suitable the kernel is to sparse networks. That is, given thatthe networks are sparse, our defined kernels will be closeenough to the ideal kernels, which are the kernels that capture
the semantics of the model but not computable from data. By
using latent feature implicitly together with support vector
machine (SVM) classifiers [27] on top, our proposed method
has the following advantages.
1) Our method is significantly faster than other methods
that infer latent features explicitly.
2) It gives globally optimal solutions unlike other methods
that may converge to local minima.
3) It can inherit seamlessly other advantages of SVMs suchas nonlinearity.
Because of these advantages, our method gives a very highpredictive performance for link prediction problems and isapplicable to real datasets of large sizes. We also show thatthe use of network structures gives higher performance thanwhen using basic node information because the nodes tend tocontain redundant information for the link prediction task.
The rest of this paper is organized as follows. We describe
the generative model of network structures with latent featuresin Section II. We then develop our kernels for this modeland make a simulation to demonstrate the idea in Section III.
We show how suitable the kernels are for sparse networks in
Section IV. We show our application in networks with latentfeatures of protein–protein interaction (PPI) in Section V. We
also show an application to a nonsimilarity network type ofgene regulatory network in Section VI. We then sum up andconclude this paper in Section VII.
II. L ATENT F EATURE M ODELS OF G RAPHS
A. Biological Motivation
A protein (node) can be regarded as a collection of domains(features). A PPI is caused by a physical interaction between(a) Input(b) Learning(c) Output

Fig. 1. Overall description of the method. Given an adjacency matrix as
input, the method embeds cells (links or nonlinks) into a feature space anduses classification to infer new links.

two domains from the two proteins [28]. However, the knowledge of domains may be incomplete, and domain–domaininteractions are not well understood. Therefore, we wish toincorporate the domain–domain interaction knowledge in an
implicit way. Given enough links, we want to infer the featuresthat are shared by interacting protein pairs and play the roleof domains, where some pairs of features are likely to interact
to generate PPIs.
A key difference between these networks and social networks is in the pair of features (each feature from each node)that cause a link. In PPI networks, the pair of features are thetwo domains with 3-D shapes that complement each other.
They are usually different features. On the other hand, insocial networks, the pair of features are usually the same, suchas the same hobby of friends. This makes our PPI networks
nonsimilarity networks, as opposed to similarity networks insocial networks.
B. Latent Feature Models of Graphs
We describe a latent feature model of graphs, as also
appearing in [6]. In this model, a link (edge) in the graphis generated by the relation between the latent features of theadjacent nodes. Let A ∈ Rn×n denote the adjacency matrix ofthe graph. In general, A can be any real matrix. For our special
purpose of modeling undirected networks, we assume that A
is a binary symmetric matrix. Let F ∈ Rn×d denote a binary
matrix where each row is a d-dimensional vector of latentfeatures. Let W ∈ Rd×d , named feature interaction matrix,
denote a real matrix encoding strengths of feature interactions.
That is, Wi j encodes the strength of interaction between thei th feature and the j th feature. We say that the i th featureinteracts with the j th feature if and only if Wi j = 0. We saythat (F, W ) is a latent feature model for A if
A = F W F T.

(1)

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 (1) is replacedby the element-wise operator round(min(x, 1)), where x is theentry on the right-hand side of (1). It can be rewritten as
A = round(min(F W F T, 1)).

(2)1) Simulation Example: The idea of the latent feature model
is depicted in Fig. 2. In this example, the set of nodes havethree latent features, with the first two nodes having two
features and the rest having one feature each. The feature

NGUYEN AND MAMITSUKA: LATENT FEATURE KERNELS FOR LINK PREDICTION ON SPARSE GRAPHS

2

2

4

4

6

6

8

1
2
3

10
12

123

14

8

1
2
3

10
2

4

6

8 10 12 14 16

12
14

16

16
123

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 three matrices: the latent feature matrix (F, leftmost), the featureinteracting 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, the product of the first three matrices generates
the last one.

interaction matrix indicates that the first and the second
features interact, and also the third feature interacts with itself.
For the benefit of using latent feature models, we refer to[6] for details. The following properties are observed.
1) Each entry of W generates a subgraph given F. The
overall generated graph is a superimposition of thesesubgraphs. This makes the model an additive one.
2) If W is diagonal, then the generated graph can be
decomposed as a set of cliques. This is a model ofsimilarity graphs.
3) If W is symmetric, then the generated graph is symmetric. It is usually used to encode undirected graphs.
4) If F has exactly one nonzero entry in each row (suchas the ones generated by Chinese restaurant processes),then generating F is equivalent to clustering of nodes.
5) If the nodes can be divided into two groups, each with aseparate set of features, and W has only interactions offeatures from the two different sets, then the generated
graph is bipartite.
These properties make latent feature models general generative models for graphs.
III. L ATENT F EATURE K ERNELS FOR L INK P REDICTION
We describe our kernel method to link prediction given thelatent feature model of the graph structures. The idea is to
use the model to derive a kernel between all pairs of thenodes (named link kernel). We define the following terms:
a link is considered as a positive pair of nodes, whereas thenonexistence of a link (nonlink) is encoded by a negative pairof nodes.
The link prediction problem is then formulated as a binaryclassification problem. In the end, we classify the two classes,
the link class and the nonlink class, using SVMs. The overall
strategy is shown in Algorithm 1.
The kernel between pairs is based on that between nodes
themselves (named node kernel). We first describe the node
kernel (K n ) that encodes the latent feature model, and thenthe link kernel.
A. Node Kernels With Latent Features
We wish to define the similarity of two nodes as thelikelihood of having common latent features. This is inherently

1795

Algorithm 1 Network-Structure-Based Link Prediction
Input: Adjacency matrix A.
1) Construct a node kernel K n following latent featuremodels.
2) Construct a link kernel K based on K n .
3) Learn an SVM on K .
Output: New adjacency matrix based on the SVM.

different from similarity models where similarity means thelikelihood of reaching the other node through random walks[5]. However, latent features are not observable, and, therefore,
we must estimate the similarity, in the form of kernels,
between nodes empirically. Knowing that nodes with common
features tend to link to common neighbors in latent featuremodels, we define the basic node kernels as the ratio ofcommon neighbors of the nodes, as follows:
1

1

K n = D− 2 A A T D− 2(3)where D is a diagonal degree matrix: D ∈ R n×n , and
Dii =

n


Ai j .

(4)

j =1

A special case of this kernel is when all the nodes haveexactly one feature (such as generated by Chinese restaurant
processes). The resulting K n (a, b) takes either 1 or 0 for any
node a and b, depending on whether they have a feature incommon or not. An implication is that, in networks in which
latent features are expected to be sparse, K n behaves similarly
to this extreme case, showing a good indication of common
latent features.
Given the basic node kernel, additional transformations canbe applied on top of this kernel to make new families ofkernels. Diffusion kernels and exponential kernels on top of
K n still conserve the idea of latent features. Of course, thehigher the power we take on K n , the looser the idea can be
kept. However, note that the most general version of spectral
transform [20] is not guaranteed to conserve the latent featureassumption.
Note that this node kernel occurs as a term in the series
expansion of many path/walk-based kernels [5], [15], [16],[29], [30] designed for similarity graphs. However, we findthat our proposed kernel in particular encodes the latent featuremodel that is suitable for our problem.
B. Latent Features Kernels for Links
We call the link kernels built on the node kernels K n (withlatent feature assumption) latent feature kernels. Given thenode kernel K n , a kernel between two links is usually defined
to be the combined similarity between the pairs of nodes of thelinks. In other words, the similarity between a pair of nodes{a, b} and another one {c, d} is based on the similarity of: 1) a
to c and b to d and 2) the similarity of a to d and b to c. This
leads to two issues.
The first issue is how to define a combined similarity of two
pairs of nodes. We break this down to a fixed order of nodes,

1796

IEEE TRANSACTIONS ON NEURAL NETWORKS AND LEARNING SYSTEMS, VOL. 23, NO. 11, NOVEMBER 2012

such as using the similarity in 1) only. This is basically the
problem of finding a map between input a and b to c and d,respectively. Therefore, this is a structured output learning
problem [31], [32] with the special property that the input
and output are from the same space. In the context of kernel
methods, we can use the existing joint kernels [33] to define
an ordered kernel between the two pair of nodes as follows:
K × ((a, b), (c, d)) = K n (a, c) · K n (b, d)

(5)

or

2
4
6
8
10
12

K × ((a, b), (c, d)) = K n (a, c) + K n (b, d)

(6)

14

or any other variations of joint kernels.
The second issue is how to account for the unordered natureof the links in general. That is, the similarity is supposed to
be defined over both orders of the two pairs of nodes 1 and2 at the same time. We follow the solution in [23] and [2]1
to break the asymmetry of the ordering by summing them up
together16

K ((a, b), (c, d)) = K × ((a, b), (c, d)) + K × ((a, b), (d, c)).
(7)
It is noteworthy that the pairwise kernel as defined in [2] isa special case with the joint kernel defined in (5). We use thispairwise kernel in our later experiments. The interpretation of
the kernel is as follows.
Let ai and b j , respectively, be the i th and j th features ofa and b in the kernel-induced feature space of K n . Then thefeature space of K consists of the following features for a pair(a, b):
ai b j + a j bi .

(8)

If the node kernel K n indeed captures the likelihood of two
nodes having common features, the link kernel indicates the
chance of having two pairs of nodes with common features.
For example, when the pair {a, c} shares common features,the likelihood of the pair {b, d}, K ((a, b), (c, d)) sharing thesame features is high.
Nonlinearity can be incorporated into this kernel, such as
by applying polynomial or Gaussian kernels on top of it.
C. Bipartite Graphs
We describe a special case of latent feature kernels for bipartite graphs. We show that in this case, our kernel framework
is equivalent to structured output learning. Suppose that thegraph is a bipartite graph; so for any link {a, b}, a is in thefirst part and b is in the second part of the graph. The similarityof two links {a, b} and {c, d}, in a similar manner as before,
would be the similarity between the corresponding nodes.
However, the key difference in bipartite graphs is that thepair of nodes in any link is ordered. It only makes sense todefine the similarity between links by a combined similarity
1 The same solution is also used in [34]. However, we do not use thisformulation because of some of its drawbacks, a discussion of which is beyond
the scope of this paper.

2

4

6

8

10

12

14

16

Fig. 3.
Adjacency matrix of an incomplete graph from the simulation
example.

between nodes of the same parts. Therefore, in the samemanner, we define a kernel between the two links as
K ((a, b), (c, d)) = K × ((a, b), (c, d)).

(9)This is exactly the case of joint kernel map representationof structured output learning with kernels [32]. One difference
is in the objective function for learning. While structured
output learning estimates the density of the training data,
our method samples negative examples and classifies the twoclasses instead.
D. 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 the adjacency matrix
in Fig. 3 (only 80% of the links are known). We show stepby step the idea of node kernels and latent features.
1) Node Kernel: We visualize the nodes using the node
kernel defined in (3). We use kernel principal component
analysis and plot the nodes using the first three principal
components in Fig. 4. The nodes in the figure are the nodesof the graphs. The cyan edges are the observed links. The reddashed edges are the missing links according to the modelin the simulation example. First, we can observe that thecyan edges follow certain patterns of direction and endpoints.
Another point that can be observed is that the dashed rededges follow the same patterns (endpoints lie in clusters andedges connect the same cluster pairs). This is exactly what wewant in learning—testing data having the same distribution as
training data. What is left to be done is to keep these patterns
in some spatial representations of the edges.
2) Latent Features: We look into the model to show the
distribution of nodes with features. We label the nodes withthe same feature in shaded ellipses in Fig. 5. The ellipses
correspond to the three latent features in the example. We canobserve that the node kernel makes these nodes close to eachother. The nodes with two features lie somewhere in between
the nodes with only one of the two features.

NGUYEN AND MAMITSUKA: LATENT FEATURE KERNELS FOR LINK PREDICTION ON SPARSE GRAPHS

0.4

1797

0.4

0.2
0.2

0
0

−0.2
−0.2

−0.4
0

−0.4
0

−0.2
−0.4

−0.2

−0.6
−0.8

−0.4

−0.2

0

0.2

0.4

−0.6

Fig. 4. Visualizing the graph with the node kernel. The cyan edges are theobserved links of the graph, while the dashed red edges are the missing links
according to the model in the simulation. We can observe that the red links
follow the same patterns as the cyan ones.

0.4
0.2
0
−0.2
−0.4
0
−0.2
−0.4
−0.6
−0.8

−0.4

−0.2

−0.4

0

0.2

0.4

Fig. 5. Positive class of links. The nodes are grouped by their common latentfeatures. This shows that nodes sharing more common features tend to group
together.

3) Negative Links: As shown in Fig. 4, the observed edges
and missing edges have similar patterns. However, since we
use SVM for classification, we also wish the negative class(nonlink) not to follow the same patterns. Therefore, we show
all the edges that belong to the nonlink class in Fig. 6. We
can observe that they do not follow the patterns of the positiveclass, having the same endpoints but connecting cluster pairs
different from the link classes.
The demonstration shows that our designed node kernel
successfully discovers the patterns of the link class as opposedto the nonlink class. It tends to group the nodes with common
features close to each other as we designed. We wish toclarify the difference of our method from other methods suchas those using Chinese restaurant processes or Indian buffet
processes (IBP) [6], [9], [12]. These methods group thesenodes together explicitly, whereas our method uses a softversion of putting them close in a space. We believe that thisis the key to robustness, allowing the inference step to reachglobally optimal solutions and be scalable to large networks.
IV. N ODE K ERNELS ON S PARSE G RAPHS
Our objective is to model networks with latent featuremodels. The problem is that, in reality, intrinsic features are

−0.8

−0.4

−0.2

0

0.2

0.4

Fig. 6. Set of nonlink class. Compared to the link class, the nonlink classhas different positions and orientations.

not possible to obtain, and inferring them explicitly is often
intractable. Therefore, we use network structures (topology) tomodel the networks themselves. The key observation is thatthese networks are sparse, as they are generated by a small
number of features, producing certain patterns on network
structures. Hence, in this section, we show that, for sparse
networks, the information we extract from network structures
is close to the information of the features that are not available.
In other words, the models we construct for the networks areclose to the true generative models of the networks themselves.
Toward this end, we define kernels that encode the similarity
between nodes if the features are fully observed, named ideal
kernels. The ideal kernels, which are what ideally the node
kernels should be but this is not possible to obtain, are thebenchmarks. As our method uses kernels with SVMs, weformally show how close the node kernels built on network
structures could be to the ideal kernels. Given that the ideal
kernels contain information of latent features, if the node kernels that we obtain are the ideal kernels, then the success of ourlink kernels rests solely on the ability of the link kernels to represent the links given the node kernels. Given the way the link
kernels are defined on the basis of the node kernels, we expectthat the link kernels that we obtain are also close to those built
on ideal kernels in some sense. The main result is containedin the four propositions. We also show here an idea of how
our defined kernels reflect the latent features of the graphs.
A. Ideal Kernels
Consider a graph generated by a latent feature model of 1.
If the model (F, W ) were observable, we would be able todesign an ideal node kernel encoding the similarity of nodes
in this graph. The semantic similarity of two nodes under
this model is the number of latent features they share, being
weighted by the importance of the features. Therefore, we
define the ideal kernels as follows.
1) Definition (Ideal Kernels): Define the set of ideal kernels
for a latent feature model (F, W ) to be K = {K ∗ (D)} D , where
D ∈ Rd×d is any diagonal matrix with positive entries, andK ∗ (D) = F D F T.

(10)

1798

IEEE TRANSACTIONS ON NEURAL NETWORKS AND LEARNING SYSTEMS, VOL. 23, NO. 11, NOVEMBER 2012

A kernel value K ∗ (D)i j = Fi D(F j )T is the weighted
sum of the number of common features between the i th andj th nodes. However, since latent feature models are obtainedwith difficulty, the ideal kernels are not available. Any kernel
defined from data with latent feature models should be close
to some ideal kernels.
Below, we will show that the node kernel we define is close
to ideal kernels for sparse networks, which are the target ofour method.

In other words, there exists another mathematically equivalent model giving the same ideal kernel sets and the adjacency
matrix in which each feature interacts with only one feature.
Proof: The idea of the proof is to place a nonzero Wi j in
one new row and column of W × and duplicate the columns of
F when necessary to make F × , keeping the adjacency matrix
unchanged. Suppose that the (unnormalized) adjacency matrix
A is computed by
Wi j F·i (F· j )T(12)
A = FW FT =ij

B. Relationship Between Node Kernels and Ideal Kernels on
Sparse Graphs
When the graphs are sparse (as in our applications), sparsemodels are required to model them. The following propositions
show the relationship between the node kernel K n and theideal kernels when the models are sparse in the sense defined
therein. Let Si denote the set of latent features of node i .
Proposition 1 (Positivity): If Si ∩ S j = ∅ (two nodes i andj share at least one latent feature) and that the feature causes
both of the nodes i and j to have links to another node, then
(A A T )i j > 0, and therefore (K n )i j > 0.
Proof: The proof can be easily seen because, when theyshare a feature, they have a common nonempty neighborhood,and therefore (K n )i j > 0.
This shows that, if the values of ideal kernels on two nodes
are positive, the value of K n is positive as well. This means
that, whenever the two nodes are similar (positive kernel value)in the model, the kernel K n can recognize that. This is usefulfor sparse graphs (causing sparse kernels) in which K n is notsparser than any ideal kernel.
Proposition 2 (Monotonicity): Suppose that the pairs of
nodes have the same number of neighbors in the sense that
Dii D j j = Dkk Dll [D is defined as in (4)]. If (Si ∩ S j ) ⊇(Sk ∩ Sl ), then (K n )i j ≥ (K n )kl .
The first assumption is about the equal numbers of neighbors for the two pairs of nodes. The number of neighbors ofa pair of nodes is defined to be the product of the numbers ofneighbors of the two nodes. The conclusion is that, the morelatent features they share, the higher the kernel value is. Thisis a property of the ideal kernels by the way in which they
are defined, showing an analogy of K n to ideal kernels.
Proof: As (Si ∩S j ) ⊇ (Sk ∩Sl ), the common neighborhoodof the nodes i and j is a superset of the common neighborhoodof the nodes k and l. Therefore, (A A T )i j ≥ (A A T )kl .

(13)(i, j )∈I

We then construct the F × and W × by sequentially appending the feature columns and feature interaction matrix valuesin (13) as follows.
1) Mark all the indices in I as available.
2) Initialize F × and W × to empty matrices.
3) Go to the next available index in I , pick the pair (i, j ),and then continue as follows.
a) If i = j , meaning that wii indicates a selfinteracting feature, then append the 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 Wi j on the diagonal of W × .
Mark the index of Wi j in I unavailable. Repeat theprocess from step 3.
b) If W is symmetric (A is symmetric), then Wi j =w j i . Append the feature vectors F·i and F· j tothe end of F × . Suppose that the size of W × isk, then append two new rows and columns of W × ,××
and Wk,k+1
to be Wi j .
setting the values of Wk+1,kMark the indices of Wi j and W j i in I unavailable.
Repeat the process from step 3.
c) If W is not symmetric, then append the features
as the symmetric case to F × . For W × , only one
×. Mark thenonzero element is added to Wk,k+1
index of Wi j in I unavailable. Repeat the processfrom step 3.
After all indices in I are marked unavailable, we have
Wi j F·i (F· j )T = F W F T = A. (14)F × W × (F × )T =(i, j )∈I

(A A T )i j
(K n )i j = 
Dii D j j
(A A T )kl≥ = (K n )kl
Dii D j jwhere F·i is the i th column of F.
Let I = {(i, j )} that Wi j = 0. ThenA=
Wi j F·i (F· j )T.

(11)from the definition of the node kernel in (3).
Lemma 1 (One Feature Interaction): For any latent featuremodel (F, W ), there exists another latent feature model(F × , W × ) that gives: 1) the same adjacency matrix; 2) thesame set of ideal kernels; and 3) the feature interaction matrix
with at most one nonzero entry in any row and column.

Also, each row or column of W × has at most one nonzero
entry by the way in which W × is constructed. Since the setof columns of F × is the same as F’s, the set of ideal kernels
is the same (only different by feature weighting).
Hence, we have constructed a new model with a feature
which either interacts or is interacted with at most one feature.
This is to say that there is a mathematically equivalent modelin which each feature only interacts with one another feature.
We use this fact to facilitate our sparsity reasoning as follows.
Proposition 3 (Ideal Condition): K n is an ideal kernel(K n ∈ K) if the row vectors of W F T are pairwise orthogonal.

NGUYEN AND MAMITSUKA: LATENT FEATURE KERNELS FOR LINK PREDICTION ON SPARSE GRAPHS

1799

Proof: When the row vectors of W F T are pairwise
orthogonal, then W F T × (W F T )T is diagonal. Denote D =W F T × F W T . Then
K n (A) = F W F T × F W T F T = F D F T .

(15)Since D is diagonal with nonnegative entries, K n ∈ K.
Corollary 1: If W is the inverse of a mixing matrix of an
independent component analysis model [35] for F T and W F T ·1 = 0, then K n ∈ K.
1 denotes the vector of all 1 and 0 denotes the vector of
all 0. The corollary comes from the fact that independent
components are uncorrelated and, in this case, orthogonal.
Corollary 2: If each node has only one latent feature, suchthat F is generated by a Chinese restaurant process or any
class-based model in which W has only one nonzero entry ineach row or column (guaranteed by Lemma 1), then K n ∈ K.
The corollary comes from the fact that W F T has only one
nonzero entry in each column, and 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, K n is close to an ideal kernel asfollows. Let E = F T F. Then Elk = (F·l )T F·k is the numberof nodes having both features l and k. When l = k, we expect
Elk to be small in comparison with Ell and E kk for sparsemodels. In other words, E is diagonally dominant. We show
the relationship between the diagonal dominance of D and thesparsity of F as well as how close K n is to ideal kernels.
Given Lemma 1, we assume that Wil and W j k are theonly nonzero entries in rows i and j . Recall that K n =F D F T = F W E W T F T . Since the entries of W are scalars,
2 /(E E ).
Di j = Wil W j k Elk means that Di2j /(Dii D j j ) = Elkll kk
When F is sparse, the off-diagonal elements of E are muchsmaller than diagonal ones (diagonally dominant). The samething 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 sparse1
in the sense that ( i= j |Wil W j k Elk | p ) p ≤ δ for some smallδ ∈ R, p ≥ 0, there exists an ideal kernel F D̂ F T that is close
to K n in the sense that D − D̂ p ≤ δ.
1
In the condition ( i= j |Wil W j k Elk | p ) p , an entry
Wil W j k Elk is the weighted number of nodes having the two
features l and k (should also be small for sparse models,l = k implying 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 Di j = Wil W j k Elk , then
⎛
⎛
⎞1
⎞1
p
p


p⎠
p⎠
⎝
⎝
|Di j |=
|Wil W j k Elk |D − D̂ p =i = j≤ δ.

i = j(16)

This shows that the sparser 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 anotherfeature (by Lemma 1) and K n should be close to the ideal
kernel F D̂ F T since F D̂ F T is linear in D̂.

(a)

(b)

(c)

Fig. 7. Simulation example networks with latent features. A circle representsa group of five nodes with the same latent feature sets. An edge between
circles is a set of links from all nodes in one circle to all in the other one.
(a)–(c) Networks become denser.
TABLE IL INK P REDICTION R ESULTS ON S IMULATION N ETWORKSW ITH D IFFERENT S PARSITY L EVELS
Network

Mean AUC score(a)0.979 ± 0.020(b)0.903 ± 0.026(c)0.843 ± 0.044

All these properties make the kernel K n a good approximation of ideal kernels in sparse models. Sparse models are
suitable for our applications in sparse networks (nodes withsmall degrees). We elaborate more in the applications section.
C. Simulation
We conduct a simulation to show that, when the network issparse in the sense that a node has a small number of latentfeatures and each feature only interacts with one another, thenour kernels can capture well the similarity in the shared latentfeatures. By this we mean that our defined kernels are closeenough to ideal kernels, which are supposed to give perfectperformance. The simulation networks are generated according
to the topology in Fig. 7.
The experiment was set up as follows. We sampled 50% of
the links for training and used the rest for testing. We used
our method, and we report the average area under the curve(AUC) scores of 50 runs in Table I.
We can observe that, when the network was generated
by the simple model in (a), our method gave perfect AUC
scores. As the models became denser, our method gave poorer
performance. This might be due to the fact that our proposed
kernels become further from the ideal kernels. Our simulationsuggests that our kernels are good for very sparse models of
networks (that generate sparse networks).
V. A PPLICATION : N ETWORKS W ITH L ATENT F EATURES
Our targeted application is to model network structures withthe latent feature models. Even though the model includes
similarity networks as special cases, our main target is nonsimilarity networks such as PPI networks. An experiment in
the following subsection verifies that PPI networks are indeed
nonsimilarity networks. There are other networks studied inbioinformatics but they are too sparse and not large enough tostudy structures statistically.

1800

IEEE TRANSACTIONS ON NEURAL NETWORKS AND LEARNING SYSTEMS, VOL. 23, NO. 11, NOVEMBER 2012

TABLE IIN UMBER OF N ODES AND L INKS FOR D IFFERENT

0.9

S UBNETWORKS W ITH VARYING M INIMUM D EGREE m

0.85

1
2
3
4
5
6
7
8
9
10

Yeast
Nodes
4762
3775
2891
2260
1811
1507
1245
1046
890
756

Links
21 83620 84919 13917 315
15 58214 11212 607
11 255
10 0648924

Fruit-fly
Nodes
Links
6644
21501
4783
19640
3397
16944
2539
14452
1923
12072
1403
9568
1098
7796
713
5243

SimNN
LK−NN

0.8
AUC

m

0.75

0.7

0.65
0

We used the PPI networks of yeast and the fruit fly fromthe DIP database [36] because of their largest hand-curated
networks available. For statistical study, we focused on only
the largest connected component of the m-core of the network(the largest connected subnetwork with all the nodes having
the degrees of m or more). In our experiments, we show theresults for all the values of m from 1 to 10 (8 for the fruit fly).
We show in Table II the sizes of the data. We will show lateron that the other methods based on latent feature inference donot scale to these sizes.
Real PPI networks are sparse: less than 20% of the nodes
in yeast and none in the fruit fly have degrees of 10 or more.
This is the reason for sparsity analysis in Section IV.
For each subnetwork, we sampled the nonlink class datafrom arbitrary pairs of nodes that are not known to have any
link between them. The number of nonlinks is the same as thenumber of links to make the data balanced. This process was
repeated five times. We showed the average AUC score of 20
random train/test splits with the ratio 90 : 10. We used SVM(soft margin parameter C = 0.001, but the results were thesame for a range of C from 0.0001 to 0.1) as the classifier
for our link kernels. We first show the appropriateness of
the assumption of latent features as opposed to the usualassumption of similarity. We then show the time required tobuild one model to clarify the difference in real computation
time between our method and IBP [6] (with parameter α = 3,
which we found to be a good tradeoff to be able to train on oursmallest datasets and induce a model with a sufficient numberof latent features). We then show the performance of link
kernels in link prediction. We also compare the performanceof link kernels to that of sequence-based link prediction toshow the advantage using network structures.
A. Latent Feature Versus Similarity
Fig. 8 shows the fitness of the latent feature model on yeast
PPI networks as opposed to the similarity model. To compare
the models, i.e., the assumptions of similarity and latent features, we use the simple nearest neighbor classifiers, resulting
in the two following methods.
1) SimNN for similarity assumption: Using the direct
method [7]. The more walks of length two between the

2

4
6
8
10
Minimum degree of nodes

12

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

nodes, the more likely they have a link between them.
Using the normalized adjacency matrix, this method
happens to be equivalent to using the node kernels andpredicting links based on the similarity (kernel value) of
the two nodes.
2) LK-NN for latent feature assumption: The latent feature
kernel is used as the similarity measure of pairs of nodes.
A pair of nodes takes the label of its closest pair of nodes
with a known label (link or nonlink).
Fig. 8 shows significantly different AUC scores of the two
methods on the yeast PPI networks. LK-NN was usually muchhigher (around 0.1 and more). It shows that the latent featuremodel was more suitable to the PPI networks than the conventional similarity one. The exception was at the subnetworkwith the minimum degree of nodes of 1. Since we were using
only network structures, the nodes with degree 1 may notcontribute to the network structure in these models. Therefore,
results for the subnetworks with nodes with larger degrees
demonstrated the reasonability of the assumptions used. For
this reason, the latent feature assumption was more reasonable
than the similarity assumption here, and the methods for
similarity networks were not recommended to be used.
B. Execution TimeWe show execution time required to build one model using
our link kernels in Fig. 9. To compare with IBP, we also
show the execution time in the process of building one model
before it burns in in Fig. 10. Since IBP requires a longcomputation time, we only show the execution time for thesmallest subnetwork (minimum degree of 10 with only 756
nodes), which is supposed to require the least time among all
the subnetworks.
We can see that the link kernels took less than 90 s for thesmallest subnetwork, which increased to 480 s for the largest
subnetwork of 4762 nodes. On the other hand, IBP took many
hours for the smallest subnetwork of 756 nodes and did not

NGUYEN AND MAMITSUKA: LATENT FEATURE KERNELS FOR LINK PREDICTION ON SPARSE GRAPHS

500

1801

0.91

450

0.9

Time to train one model

0.89

400

0.88

350

AUC

Second

0.87

300

0.86

250
0.85

200
150

0.83

100

0.82

50
0

2

4
6
Minimum degree of nodes

8

10

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

4.5

LinearGaussian
IBP

0.84

x 10

0.81

0

2

4
6
8
Minimum degree of nodes

10

Fig. 11. Link prediction results on the yeast PPI network. AUC of link
prediction with different methods (vertical) at different minimum node degreesof the network (horizontal axis). Note that IBP does not scale with larger
datasets, and hence the results of IBP are unavailable.

burn in on larger ones within one day. The reason is that
IBP uses sampling methods that are usually very expensive
computationally. We conclude that our method can save bymany orders of magnitude the time to train one model, making
training on networks with thousands of nodes possible. Thisis a key advantage of our kernel method.

The results are for different subnetworks with different minimum degrees. For small minimum degrees, the subnetworks
have higher coverage on the whole network, while the large
minimum degrees will extract denser parts of the network,
making statistical inference on this part more reliable. We
show two versions of our link kernels: linear kernels andGaussian kernels (K (x, z) = exp(−γ |x − z|2 ) with γ = 2).
The incomplete results of IBP were due to the fact that theexperiments took too much time (more than one day) to train
one model.
We can read from yeast’s results in Fig. 11 that linear kernels had similar AUC scores with IBP. However,when using the nonlinear version of Gaussian kernels, AUC
scores were significantly higher. We conclude that our kernelbased method provide a significantly higher AUC scoresthan IBP. One surprising result was that even using network topology only, we achieved 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 shows that there are patterns for the topology of the PPI networks. This result
also shows that our method is effective in encoding thesepatterns.
Similarly, we can see from the results on the fruit fly
PPI network in Fig. 12 that our method based on kernels
outperforms IBP. The AUC scores on fruit fly PPI networks
are much lower than on yeast because of the fact that fruit fly
networks are sparser, involving more proteins and there are noproteins with degrees of 10 or more.

C. Link Prediction Results

D. Comparison to Sequence-Based Prediction

We compare the prediction ability of our method using
link kernel to the baseline of using IBP as in [6, Fig. 11].

As opposed to using network structures, traditional methods
use node information such as protein sequences. Therefore, we

4Log−likelihood convergence in time

3.5

Second

3
2.5
2
1.5
1
0.5
0
−7.5

−7

−6.5

−6
−5.5
−5
−4.5
Model log−likelihood

−4

−3.5
4
x 10

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

1802

IEEE TRANSACTIONS ON NEURAL NETWORKS AND LEARNING SYSTEMS, VOL. 23, NO. 11, NOVEMBER 2012

0.8

TABLE IIIN UMBER OF N ODES AND L INKS FOR D IFFERENT S UBNETWORKS

0.79

OF E. C OLI G ENE R EGULATORY N ETWORK W ITH VARYINGM INIMUM N ODE D EGREES m

0.78
m

Nodes

Links

1

1437

3901

2

1064

3528

3

678

2763

4

446

2091

5

239

1302

0.77

AUC

0.76
0.75
0.74
LinearGaussian
IBP

0.73
0.72

1

0.9

SimNN
LK−NN

0.71
0.7
0

2

4

6

0.8

8

Fig. 12. Link prediction results on the fruit fly PPI network, showing the
AUC of link prediction with different methods (vertical) at different minimum
degrees of the network (horizontal axis). IBP results are available only forthe 8-core.

also compared our method to spectrum kernels on sequences
to predict links. The results are not shown in Figs. 11 and
12 because their ranges are different. The highest AUC score
was 0.71 ± 0.008 for yeast and 0.65 ± 0.016 for fruit
fly. We observe that network-based methods gave higher AUC
scores, being statistically significant (with t-tests at 0.01 level).
This might be due to the fact that kernels based on sequences
contain too much redundant information, since sequencebased kernels use all k-mers across the protein sequences.
Sequence-based kernels are redundant because only small
parts may determine the interaction ability of proteins toothers.

AUC

Minimum degree of nodes
0.7

0.6

0.5

0.4
0

1

2
3
4
Minimum degree of nodes

5

6

Fig. 13. Latent feature versus similarity assumption on gene regulatory
networks. AUC of the direct method for link prediction (vertical) is shown at
different minimum degrees of the network (horizontal axis).

We extend our application domain to another type of nonsimilarity network: the gene regulatory network of E. coli [37].
This network has the largest number of links among all gene
regulatory networks and is well studied. Regulatory networks
are not well known to have latent features that generate the
network structures. They do not fit into any other categories
of similarity or bipartite networks. The regulatory network of
E. Coli is not too sparse, and it is a scale-free network.
We carried out experiments in the same manner as in theprevious section for the PPI network. We extracted the largest
connected components with the minimum degrees m. We show
the sizes of our data in Table III. We then used SVM withdefault parameters as in the previous section to train theclassifiers for out method.

we wish to see how appropriate and general our model iscompared to the most common similarity network type. We
use the simple direct method as before to highlight the meritof similarity measures. We show the average AUC scores inFig. 13. We can observe that the similarity network assumption
gives very low AUC scores, almost close to random. Our
method, on the other hand, gives very high AUC scores. We
conclude that, while the latent feature model trained with
our method is flexible for this network, it is not the samefor similarity networks. In fact, gene regulatory networks arecloser to bipartite networks in which there is a set of common
regulators that regulates most other genes, including themselves. Therefore, they have some bipartite structures in them,among other links, that make them not bipartite networks. This
explains why our network model is flexible enough to capture
this type of structure whereas similarity networks totally fail todo so.

A. Latent Feature Versus Similarity

B. Execution Time

Given that gene regulatory networks are not known to be
any kind of networks that are usually used for link prediction,

We also compared the execution times of our method tothe method that explicitly infers the latent features of IBP.

VI. A PPLICATION : OTHER N ONSIMILARITY N ETWORKSNGUYEN AND MAMITSUKA: LATENT FEATURE KERNELS FOR LINK PREDICTION ON SPARSE GRAPHS

problem as a supervised learning one, inheriting the optimality,
efficiency, and nonlinearity of the kernel framework. We
showed the suitability of the kernels on sparse networks. We
applied our methods to two types of networks: the networks of
PPIs where latent features are expected and the networks forgene regulations, which are known not to belong to similarity
or bipartite networks. The results showed that our kernelbased method gave a higher performance than the direct latentfeature inference method of IBP. Our method was also manyorders of magnitude faster, and scaled to the sizes of real
networks, unlike IBP. It was also shown that network structures
give higher predictive performance than node information. We
conclude that for sparse networks with latent feature models,
our method is able to utilize the relevant information in
network structures to give significantly faster execution time,
more scalable solutions, and higher performances.

0.98

0.96

0.94

0.92
AUC

LinearGaussian

0.9

1803

IBP
0.88

0.86

ACKNOWLEDGMENT

0.84
0

1

2
3
4
Minimum degree of nodes

5

6

Fig. 14. Link prediction results on E. Coli gene regulatory network. AUC oflink prediction with different methods (vertical) is shown at different minimum
degrees of the network (horizontal axis). IBP results are missing due to theirlarge time consumption.

Our method took less than 2 s on average, whereas IBP
cost 5097 ± 1021 s on the smallest subnetwork with theminimum degree of nodes of 5. Our method is, therefore,
significantly faster. The same argument can be applied, and
IBP uses sampling methods that are computationally very
expensive. Our method, however, only uses convex quadratic
programming, and therefore is very efficient.
C. Link Prediction Results
We also compare the link prediction ability of our methodwith the link kernel to the baseline of using IBP in Fig. 14.
We follow the same settings as in the previous section. We
also compare the linear and Gaussian kernels to IBP. We
reach similar conclusions as in the networks with known
latent features in the previous section. The performance ofour method becomes higher in subnetworks with a higher
minimum degree (m). It is noteworthy that our method takes
only a very small fraction of time compared to IBP.
It is surprising that methods using the latent features
implicitly or explicitly gave very high AUC scores on thesesubnetworks (0.9 or more). This means that latent featuremodels are general enough to capture the structure of thisnetwork. That is, the gene regulatory network is likely to havelatent features as well.
VII. C ONCLUSION
We have studied the problem of predicting new links
using network structures in a more general type of networks.
Specifically, we studied the networks that can be modeledby generative processes with latent features. This is a moregeneral model of networks than the usually assumed similarity
networks in most of the applications. In order to model real
networks of medium or large size, we used kernels and cast the

The authors would like to thank the editors, the anonymous
reviewers, and the laboratory members for their helpful comments.
R EFERENCES[1] L. Getoor and B. Taskar, Introduction to Statistical Relational Learning (Adaptive Computation and Machine Learning). Cambridge, MA:
MIT Press, Nov. 2007.
[2] A. Ben-Hur and W. S. Noble, “Kernel methods for predicting proteinprotein interactions,” Bioinformatics, vol. 21, no. 1, pp. 38–46, 2005.
[3] T. Kato, K. Tsuda, and K. Asai, “Selective integration of multiple biological data for supervised network inference,” Bioinformatics, vol. 21,
no. 10, pp. 2488–2495, 2005.
[4] K. Bleakley, G. Biau, and J.-P. Vert, “Supervised reconstruction of
biological networks with local models,” Bioinformatics, vol. 23, no. 13,
pp. 57–65, 2007.
[5] D. Liben-Nowell and J. Kleinberg, “The link-prediction problem forsocial networks,” J. Amer. Soc. Inf. Sci. Technol., vol. 58, pp. 1019–
1031, May 2007.
[6] K. Miller, T. Griffiths, and M. Jordan, “Nonparametric latent featuremodels for link prediction,” in Advances in Neural Information Processing Systems 22, Y. Bengio, D. Schuurmans, J. Lafferty, C. K. I. Williams,
and A. Culotta, Eds. Cambridge, MA: MIT Press, 2009, pp. 1276–1284.
[7] J.-P. Vert and Y. Yamanishi, “Supervised graph inference,” in Advancesin Neural Information Processing Systems. Cambridge, MA: MIT Press,
2005, pp. 1433–1440.
[8] E. M. Airoldi, D. M. Blei, S. E. Fienberg, and E. P. Xing, “Mixedmembership stochastic blockmodels,” J. Mach. Learn. Res., vol. 9, pp.
1981–2014, Jun. 2008.
[9] C. Kemp, J. B. Tenenbaum, T. L. Griffiths, T. Yamada, and N. Ueda,“Learning systems of concepts with an infinite relational model,” inProc. 21st Nat. Conf. Artif. Intell., vol. 1. 2006, pp. 381–388.
[10] Z. Xu, V. Tresp, K. Yu, and H.-P. Kriegel, “Infinite hidden relationalmodels,” in Proc. 22nd Conf. Uncertain. Artif. Intell., 2006, pp. 1–8.
[11] T. Griffiths and Z. Ghahramani, “Infinite latent feature models and theIndian buffet process,” in Advances in Neural Information Processing
Systems. Cambridge, MA: MIT Press, 2005.
[12] D. J. Navarro and T. L. Griffiths, “A nonparametric Bayesian method
for inferring features from similarity judgments,” in Advances in Neural
Information Processing Systems. Cambridge, MA: MIT Press, 2006, pp.
1033–1040.
[13] N. Srebro, J. D. M. Rennie, and T. S. Jaakola, “Maximum-margin matrix
factorization,” in Advances in Neural Information Processing Systems,
vol. 17. Cambridge, MA: MIT Press, Jul. 2005, pp. 1329–1336.
[14] C. Ding, “Orthogonal nonnegative matrix tri-factorizations for clustering,” in Proc. 12th ACM SIGKDD Int. Conf. Knowl. Discov. Data
Mining, 2006, pp. 126–135.
[15] R. I. Kondor and J. D. Lafferty, “Diffusion kernels on graphs and otherdiscrete input spaces,” in Proc. Int. Conf. Mach. Learn., 2002, pp. 315–
322.

1804

IEEE TRANSACTIONS ON NEURAL NETWORKS AND LEARNING SYSTEMS, VOL. 23, NO. 11, NOVEMBER 2012[16] J. S. Kandola, J. Shawe-Taylor, and N. Cristianini, “Learning semantic
similarity,” in Advances in Neural Information Processing Systems.
Cambridge, MA: MIT Press, 2002, pp. 657–664.
[17] A. J. Smola and R. I. Kondor, “Kernels and regularization on graphs,”
in Proc. COLT, 2003, pp. 144–158.
[18] T. Kato, H. Kashima, M. Sugiyama, and K. Asai, “Conic programmingfor multitask learning,” IEEE Trans. Knowl. Data Eng., vol. 22, no. 1,
pp. 957–968, Jul. 2010.
[19] M. Shimbo, T. Ito, D. Mochihashi, and Y. Matsumoto, “On the propertiesof von Neumann kernels for link analysis,” J. Mach. Learn., vol. 75,
no. 1, pp. 37–67, 2009.
[20] J. Kunegis and A. Lommatzsch, “Learning spectral graph transformations for link prediction,” in Proc. 26th Annu. Int. Conf. Mach. Learn.,
2009, pp. 561–568.
[21] Y. Yamanishi, “Supervised bipartite graph inference,” in Advances in
Neural Information Processing Systems. Cambridge, MA: MIT Press,
2008, pp. 1841–1848.
[22] B. Taskar, M. F. Wong, P. Abbeel, and D. Koller, “Link prediction in
relational data,” in Advances in Neural Information Processing Systems.
Cambridge, MA: MIT Press, 2003.
[23] J. Basilico and T. Hofmann, “Unifying collaborative and content-based
filtering,” in Proc. 21st Int. Conf. Mach. Learn., 2004, p. 9.
[24] Z. Xu, V. Tresp, K. Yu, S. Yu, and H.-P. Kriegel, “Dirichlet enhanced
relational learning,” in Proc. 22nd Int. Conf. Mach. Learn., 2005, pp.
1004–1011.
[25] M. A. Hasan and M. J. Zaki, “A survey of link prediction in social
networks,” in Social Network Data Analytics, C. Aggarwal, Ed. New
York: Springer-Verlag, 2011, ch. 9, pp. 243–275.
[26] C. H. Nguyen and H. Mamitsuka, “Kernels for link prediction withlatent feature models,” in Proc. Eur. Conf. Mach. Learn. Knowl. Disc.
Databases, vol. 2. 2011, pp. 517–532.
[27] B. E. Boser, I. M. Guyon, and V. N. Vapnik, “A training algorithm
for optimal margin classifiers,” in Proc. 5th Annu. Workshop Comput.
Learn. Theory, 1992, pp. 144–152.
[28] M. Deng, S. Mehta, F. Sun, and T. Chen, “Inferring domain-domaininteractions from protein-protein interactions,” in Proc. 6th Annu. Int.
Conf. Comput. Biol., 2002, pp. 117–126.
[29] M. E. J. Newman, “Clustering and preferential attachment in growing
networks,” Phys. Rev. E, vol. 64, no. 2, pp. 102–115, Jul. 2001.
[30] F. Fouss, A. Pirotte, J. M. Renders, and M. Saerens, “Random-walkcomputation of similarities between nodes of a graph with application tocollaborative recommendation,” IEEE Trans. Knowl. Data Eng., vol. 19,
no. 3, pp. 355–369, May 2007.
[31] G. H. Bakir, T. Hofmann, B. Schölkopf, A. J. Smola, B. Taskar, andS. V. N. Vishwanathan, Predicting Structured Data (Neural Information
Processing). Cambridge, MA: MIT Press, 2007.
[32] I. Tsochantaridis, T. Hofmann, T. Joachims, and Y. Altun, “Support vector machine learning for interdependent and structured output spaces,”in Proc. 21st Int. Conf. Mach. Learn., 2004, p. 104.
[33] T. Hofmann, I. Tsochantaridis, and Y. Altun, “Learning over discrete
output spaces via joint kernel functions,” in Proc. Adv. Neural Inf.
Process. Syst., Workshop Kernel Methods, 2002.

[34] H. Kashima, S. Oyama, Y. Yamanishi, and K. Tsuda, “On pairwise
kernels: An efficient alternative and generalization analysis,” in Proc.
13th Pacific-Asia Conf. Adv. Knowl. Disc. Data Mining, 2009, pp. 1030–
1037.
[35] A. Hyvärinen, J. Karhunen, and E. Oja, Independent Component Analysis. New York: Wiley, 2001.
[36] L. Salwínski, C. S. Miller, A. J. Smith, F. K. Pettit, J. U. Bowie, andD. Eisenberg, “The database of interacting proteins: 2004 update,” Nucl.
Acids Res., vol. 32, no. 1, pp. 449–451, 2004.
[37] S. Gama-Castro, H. Salgado, M. Peralta-Gil, A. Santos-Zavaleta,
L. Muntildeiz-Rascado, H. Solano-Lira, V. Jimenez-Jacinto, V. Weiss,
J. S. Garciacutea-Sotelo, A. Loacutepez-Fuentes, L. Porroacuten-Sotelo,
S. Alquicira-Hernaacutendez, A. Medina-Rivera, I. MartiacutenezFlores, K. Alquicira-Hernaacutendez, R. Martiacutenez-Adame,
C. Bonavides-Martiacutenez, J. Miranda-Riacuteos, A. M. Huerta,
A. Mendoza-Vargas, L. Collado-Torres, B. Taboada, L. Vega-Alvarado,
M. Olvera, L. Olvera, R. Grande, E. Morett, and J. Collado-Vides,“RegulonDB version 7.0: Transcriptional regulation of escherichia coli
k-12 integrated within genetic sensory response units (gensor units),”
Nucl. Acids Res., vol. 39, no. 1, pp. 98–105, 2011.

Canh Hao Nguyen received the B.S. degree fromthe University of New South Wales, Sydney, Australia, in 2002, and the M.S. and Ph.D. degrees
from the Japan Advanced Institute of Science andTechnology, Ishikawa, Japan, in 2006 and 2009,
respectively.
He is currently a Post-Doctoral Fellow. His current
research interests include machine learning methods
with applications in network and biological data.

Hiroshi Mamitsuka received the B.S. degree inbiophysics and biochemistry, the M.E. degree in
information engineering, and the Ph.D. degree
in information sciences from the University ofTokyo, Tokyo, Japan, in 1988, 1991, and 1999,
respectively.
He has done extensive work in machine learning,data mining and bioinformatics. His current researchinterests include mining from graphs and networks
in biology and chemistry.