Link Prediction in Metabolic Networks
using Topology-based Mixture Models
Akira Ninagawa

Koji Eguchi

akiraninagawa@cs25.scitec.kobeakiraninagawa@cs25.scitec.kobe-u.ac.jp

eguchi@port.kobeeguchi@port.kobe-u.ac.jp

Department of Computer Scienceand Systems Engineering,
Kobe University, Kobe, Japan

Background¾A large variety of information can be represented as networks, andavailable data for such networks have increased recently.
¾For instance: social networks, ecological webs, communicationnetworks, metabolic networks, and protein interaction networks.
¾Our focus is on biological metabolic networks.
¾A metabolic network represents the process of converting the food thatwas taken from outside the body into energies and chemical compounds
necessary for living.

Background¾Complex Network analysis or link mining has become crucial tools in awide variety of fields.
¾In the area of the complex network analysis, macroscopic properties
have been pursued, such as scale-free property.
¾In the area of the link mining, some particular tasks have beenaddressed from microscopic points of view, such as group detection (aka,network clustering) and link prediction in a network.

Background¾Group detection or network clustering is the task of classifying vertices ina network into underlying groups in an unsupervised manner.
¾Link prediction is the task of predicting the existence of an unobserved
link between two vertices.
¾We focus on these two tasks, especially link prediction.

Groupdetection

Link prediction

Background
Information used for link prediction¾Link prediction using only vertex attributes•It requires sufficient expertise on the target domain.
•High precision may be achieved at the expense of less flexibility.

¾Link prediction using only network topology information•It requires less or no expertise on the target domain.
•It can be widely used, although precision might be lower.
•There are not many researches in this category, but it is promising.

Variations of topologytopology-based link prediction methods
By measuring similarity / proximity between vertices
By computing likelihood of edges using observed subgraphResearch objectives¾We propose a link prediction method only based on network topology.
¾We compute likelihood of unobserved edges using a hierarchicalBayesian mixture model (our proposed method), which is estimated fromobserved subgraph in the network.
To our knowledge, there are no researches on such a topologytopologybased mixture model for link prediction, either in biological or
nonnon-biological domains.

¾We demonstrate the improvement brought by our method in the link
prediction task, compared with some existing methods.

Proposed method¾The¾The adjacentadjacent vertices
vertices distribution
distribution ofof each
each vertex
vertex isis assumed
assumed toto be
be aa
mixturemixture ofof underlying
underlying groups
groups inin thethe network;
network; andand each
each group
group isis assumed
assumed to
tobe
be aa multinomial
multinomial distribution
distribution ofof vertices.
vertices.

Cgroup2

E FF
D CF DEgroup1

B A FAB AACB

B

ADCE

DF
Network

Proposed method¾The¾The adjacentadjacent vertices
vertices distribution
distribution ofof each
each vertex
vertex is
is assumed
assumed to
to be
be aa
mixturemixture ofof underlying
underlying groups
groups inin thethe network;
network; andand each
each group
group isis assumed
assumed totobe
be aa multinomial
multinomial distribution
distribution ofof vertices.
vertices.

BAF

0.9

C
group20.70.5

B

AABCEDDFCEE FF
D CF D0.6E

group1B A FA
B A

1.0

0.8

0.5

CAE

DF
Network

Proposed method¾We¾We further
further introduced
introduced conjugate
conjugate (Dirichlet)(Dirichlet) distributions
distributions forfor thethe per-vertex
per-vertex
groupgroup distribution
distribution andand thethe per-groupper-group vertex
vertex distribution.
distribution.
¾Underlying¾Underlying groups
groups areare estimatedestimated such
such asas byby Gibbs
Gibbs Sampling
Sampling method.
method.

?
BA?

FBA

BEC

DDFCE

CA

DEF
Network

Proposed method¾We¾We further
further introduced
introduced conjugate
conjugate (Dirichlet)(Dirichlet) distributions
distributions forfor thethe per-vertex
per-vertex
groupgroup distribution
distribution andand thethe per-groupper-group vertex
vertex distribution.
distribution.
¾Underlying¾Underlying groups
groups areare estimatedestimated such
such asas byby Gibbs
Gibbs Sampling
Sampling method.
method.
modeled groups (outputoutput)

?
BA
BC?

F

observed network (inputinput)

AA

B
E

DDFCECAEDFNetworkProposed method¾We¾We further
further introduced
introduced conjugate
conjugate (Dirichlet)(Dirichlet) distributions
distributions forfor thethe per-vertex
per-vertex
groupgroup distribution
distribution andand thethe per-groupper-group vertex
vertex distribution.
distribution.
¾Underlying¾Underlying groups
groups areare estimatedestimated such
such asas byby Gibbs
Gibbs Sampling
Sampling method.
method.
(outputoutput)?
BAF?
0.9

0.7

0.5ECD

1.00.80.5C

BAAB

0.6A

F

D(inputinput)
DCEEFNetwork

Proposed method¾We¾We further
further introduced
introduced conjugate
conjugate (Dirichlet)(Dirichlet) distributions
distributions forfor thethe per-vertex
per-vertex
groupgroup distribution
distribution andand thethe per-groupper-group vertex
vertex distribution.
distribution.
¾Underlying¾Underlying groups
groups areare estimatedestimated such
such asas byby Gibbs
Gibbs Sampling
Sampling method.
method.
(outputoutput)

B

AF0.9C
group20.70.5

B

AABCE

DE FF
D CF D0.6E

group1B A FAB A

1.00.80.5CA

FD(inputinput)
DCEEFNetworkProposed method

α : a hyperparameter of Dirichlet distributionsα

It is known as LDA[D.M.Blei et al,03]
in text modeling.

for the per-vertex group distributions

β:Nθ
βMig

θ : per-vertex group (multinomial) distributions
φ : per-group vertex (multinomial) distributions
g : groupv : vertices in observed network

N : the number of vertices in a target network
Mi : the number of vertices adjacent from aKφa hyperparameter of Dirichlet distributions
for the per-group vertex distributions

vertex vi , that is, the degree of vertex viv

K : the number of groups

A hierarchical Bayesian model of a network

Unknown parameters can be
estimated using Gibbs Sampling[T.L.Griffitds et al, 04].

Proposed method¾Then,¾Then, wewe predict
predict unobserved
unobserved links
links fromfrom thethe estimatedestimated models
models ofof groups
groups.
①②We compute the likelihood of generating a link between a pair of vertices,using the models.
We rank all unobserved links in descending order of the likelihood, andthen evaluate the ranking.

BA FA B A
group1BBCFEA
A

CEDEA

C F C EFF D
group2 D

0.9 0.7

0.5

B
D

F

C

E

0.6

0.8

0.5

1.0C

AE

D
FNetwork

Experiments
We predict links in a metabolic network
experimental settings¾The data we used in our experiments is the metabolic network of “S.Cerevisiae”
extracted from KEGG/PATHWAY database [Y.Yamanishi et al, 05].
¾The number of vertices is 668, the number of links is 782, and the proportion of
the links to all vertex pairs is 0.0125.
¾We used 80% of all the vertex pairs as training data, 10% as development data
and the remainder as test data.
¾We conducted experiments on the task of link prediction using 50 sets oftraining data, development data and test data that are randomly sampled.
¾We compared the proposed method with the three existing methods.
¾We determined the following four parameters: hyperparameter α and β ofDirichlet prior distributions, the number of latent groups K, and the number ofiterations for Gibbs Sampling, so that development-set log-likelihood is maximized.

Experiments
Three existing methods for comparison•Jaccard’s Coefficient:| a | I | aY |It is based on the idea that a pair of vertices,
Jaccard ( X , Y ) = X
each of which has smaller degree is more
| a X | U | aY |important than others.
(where aX indicates X’s adjacent vertices.)•Adamic/Adar:

This measure assigns different weight toeach common adjacent vertex.
A larger weight is assigned to a vertex ofsmaller degree.

1log| ak |k∈|a X |I|aY |∑Adamic / Adar ( X , Y ) =•Katz:¾The Katz value is determined according toboth the number of paths and the length ofeach path.
¾ γ is a weight parameter fixed somewherefrom 0 to 1.
¾ paths indicates the number of paths fromvertex X to vertex Y of which length is l .
l

X ,Y∞

Katz ( X , Y ) = ∑ γ ⋅ paths
l =1llX ,YExperiments
We used Mean Average Precision to evaluate theresult
Mean Average Precision (MAP) 1
1prec(r)∑∑| data | d ∈ data  | true d | r∈ rank d data indicates test data set (in this case, |data| = 50).
 trued indicates the whole set of links that appear in the test data d.
 rankd indicates the list of predicted links with ranks, corresponding to test data d.
 prec(r) indicates the precision of the r -th rank in the predicted link list.
 The precision is defined as the proportion of true links out of r top-ranked
predicted links.

Experiments
Experimental results•MAP is what was defined in the previous slide.
•MP@10 is the precision of 10 top-ranked predicted links, averaged over 50 sets oftest data.
•The link prediction performance of our method is more than 18 points higher thanthat of the other three methods, in terms of MAP.
•According to mean of precision at the 10th rank (MP@10), our methods remarkably
outperformed the baselines, as well.

Future work To apply to largerlarger-scale networks
 To consider multiple type of links or multiple types ofvertices
We are planning to investigate dependence between different typesof vertices, which can be classified such as using EC number.

 To improve the inference algorithm
We are planning to modify Gibbs Sampling algorithm to better suit
our model.

Thank you for your attention

The process of generating a network
is formalized as follows:
1.
2.
3.

For all vi vertices sample θi ~ Dirichlet(α)
For all gk groups sample φk ~ Dirichlet(β)
For each of the Mi vertices vj adjacent from vertex vi:a. Sample a group zij ~ Multinomial(θi)
b. Sample a vertex vj ~ Multinomial(φzij)

Given hyperparameters α and β, the full joint
distribution over all variables and parameter is asfollows:N

P(E, Z,θ , φ | α , β ) =P(φ | β )∏ P(θ i | α )P(z i | θ i )P(ei | z i , φ )i =1Hyperparameter:
The hyperparameter is the parameter
influencing the entire probability modeland defining the prior probability.

Dirichlet distribution:•The Dirichlet distribution is a distribution overmultinomial parameters.
•Multinomial β distribution•Multinomial conjugate prior distribution

Gibbs Sampling:
Assuming the conditional probability distribution
fixing variables except one variable, we sample
many times with it.

About our network data:•Each vertex represents an enzyme, and eachlink represents that two enzymes are observedto act consecutively as catalysts.
•The reason using the biological network is that
our methods may be useful to identify theunknown parts of the metabolic network.

Proposed method
Gibbs Sampling¾Gibbs Sampling is used as the algorithm to solve approximately since exact
estimations using a hierarchical bayesian model are generally difficult.
¾Gibbs Sampling is one of statistical tools called Markov chain Monte Carlomethods(MCMC).
¾MCMC is the method to simulate Markov chains which is invariant distribution.
¾In Gibbs Sampling, using the random numbers and conditional distribution,a sample sequence is generated by repeatedly updating variables obtained
from the observed distribution. And the requested invariant distribution
is obtained.
¾Generated sample sequences are used to calculate expectation andmarginal probability.

A hierarchical Bayesian modelIn the case using bayesian model not having hierarchies, a posteriori distribution ofparameter when data are given can be obtained using Bayes’ theorem by following:Pr(λ | D) =Pr( D | λ ) Pr(λ )Pr( D)

So the parameter λ is generated according to Pr(λ),
and given the parameter, data D are generated according to Pr(D|λ).
A hierarchical Bayesian model is stratified this model.
The hyperparameter μ is generated according to Pr(μ), and given the parameter,
the parameter λ is generated according to Pr(λ|μ).
Additionally, given the parameter, data D are generated according to Pr(D|λ).
So the posteriori distribution is obtained according to this model by following:Pr(λ , µ | D) ∝ Pr( D | λ ) Pr(λ | µ ) Pr( µ )When data are divided into some hierarchies a good result may beobtained if the factor common to each hierarchy is modeled by the priordistribution of hyperparameter.