Link Prediction via Community Detection in
Bipartite Multi-Layer Graphs
Maksim Koptelov[0000−0001−9065−2827] , Albrecht
Zimmermann, and Bruno Crémilleux[0000−0001−8294−9049][0000−0002−8319−7456]

Normandie Univ, UNICAEN, ENSICAEN, CNRS, GREYC, 14000 Caen, France{maksim.koptelov,albrecht.zimmermann,bruno.cremilleux}@unicaen.fr

Abstract. The growing number of multi-relational networks pose newchallenges concerning the development of methods for solving classicalgraph problems in a multi-layer framework, such as link prediction. In
this work, we combine an existing bipartite local models method withapproaches for link prediction from communities to address the link
prediction problem in multi-layer graphs. To this end, we extend existing community detection-based link prediction measures to the bipartite multi-layer network setting. We obtain a new generic framework
for link prediction in bipartite multi-layer graphs, which can integrate
any community detection approach, is capable of handling an arbitrary
number of networks, rather inexpensive (depending on the community
detection technique), and able to automatically tune its parameters. We
test our framework using two of the most common community detection
methods, the Louvain algorithm and spectral partitioning, which can beeasily applied to bipartite multi-layer graphs. We evaluate our approach
on benchmark data sets for solving a common drug-target interaction
prediction task in computational drug design and demonstrate experimentally that our approach is competitive with the state-of-the-art.
Keywords: Link prediction · Community detection · Multi-layer graphs.

1

Introduction

Many real world applications can be modeled as bipartite graphs, vertices ofwhich are divided into two distinct groups [31]. The problem setting that motivates our work is the prediction of links between drug candidates and biologicaltargets, an essential step of computational drug design. But there are other link
prediction settings that fall into the same category, for instance user-productrecommendation.
The available data on drug-target interaction prediction are of heterogeneous
structure, i.e. represented by networks the edges of which have different origins,
thus making the use of most existing link prediction methods in a straightforward
way impossible. Current solutions are limited by the number or type of networks,
often referred to as layers, e.g. three layers with two assumed to be similarity
networks [6, 26, 4].

2

M. Koptelov et al.

To address these restrictions, we take inspiration from existing methods thatuse community detection to perform link prediction [17, 36, 29, 33]. While thisdecouples the problem into how to find communities in multilayer graphs, andhow to exploit them for prediction, existing link prediction measures [5, 34, 12]
are not directly applicable to the bipartite setting. To address this restriction,
we extend several of those measures to our problem setting. In addition, we goa step further by proposing alternatives to those measures based on an existing
bipartite local model. While we evaluate two concrete approaches for community detection, spectral partitioning and the Louvain algorithm, both of which
can be easily applied to multi-layer graphs, we do not require any particularcommunity detection approach. Our long-term contribution is the adaptation ofexisting link-prediction-by-community-detection measures to the bipartite multilayer setting, which we evaluate experimentally, and the selection of best measure
and community detection approach combination. In addition, we demonstratethat the parameter settings of the spectral partitioning method can be effectively
set via internal cross-validation.
The rest of the paper is organized as follows. Section 2 provides basic notations and definitions. Section 3 discusses related work on link prediction andcommunity detection in multi-layer networks. Section 4 explains how we adapt
existing measures for our framework. Section 5 describes the data used for evaluation, the experimental setup and presents the results. Finally, Section 6 concludes
and outlines the future work.

2

Definitions

A graph is a tuple G =< V, E >, where V = {v1 , v2 , ..., vn } denotes a set ofvertices or nodes, and E ⊆ V × V a set of edges defined by distinct vertex pairs(u, v) ∈ V × V with u 6= v (without self-loops). We also use the notion of abipartite graph, which we define as a graph the vertices of which can be divided
into two classes V1 and V2 such that there is no edge between vertices of thesame class: G =< V1 ∪ V2 , E >, E ⊂ V1 × V2 .
We address weighted and unweighted graphs in the same manner. We define aweighted graph as one with a labeling function for edges E 7→ Ae with Ae ∈ [0, 1],
where 0 means no interaction between vertices, 1 confirmed interaction, and anintermediate value represents interaction probability. An unweighted graph is one
where every edge is labeled by 1.
To exploit different sources of information in one single structure, we employ multi-layer networks. The problem we address in this paper is one of link
prediction in such networks which we define as follows. For a given bipartite(n)(m)
multi-layer graph G = GV1 V2 ∪ GV1 ∪ GV2 with 1 + n + m layers, where:– GV1 V2 = hV1 ∪ V2 , Ei , λv , λei i is a bipartite layer with u ∈ V1 labeled withidentifiers of type V1 , v ∈ V2 labeled with identifiers of type V2 , ∀(u, v) ∈E, u ∈ V1 , v ∈ V2 and Ae = {0, 1},– GiV1 = hV1 , EVi 1 , λv , λeiV i are layers of type V1 ,1

Link Prediction via Community Detection in Bipartite Multi-Layer Graphs

3– GiV2 = hV2 , EVi 2 , λv , λeiV i are layers of type V2 ,2

Predict, whether for a given (u, v) 6∈ E, u ∈ V1 , v ∈ V2 λe ((u, v)) = 1. We limit
ourselves to the relatively easier task of predicting whether there is an activity
or not, leaving the prediction of its strength as future work.
Note, according to the classification of Kivelä et al. [20], the multi-layer
networks used in this work are not node-aligned 1 , not layer-disjoint 2 , havediagonal couplings 3 which are categorical 4 , and the number of layers can be any.
We represent graphs as matrices. The adjacency matrix A has size n × n,n = |V |, and Aij represents the weight of the edge (vi , vj ). In the case of multilayer networks, we aggregate the weights of multiple edges between vi and vj bysumming them up. Note, A has zeros on the main diagonal, because graphs asused in this work have no self-loops. The degree matrix D is the diagonal matrix
deg(v1 ) 0
...
n
X


..
,
deg(v
)
=
Aij
D= 0
i
.
0 
j=1
0
deg(vn )of same size as A, where deg(vi ) represents the degree of vertex vi . The degreeof a vertex is the sum of the weights of the edges adjacent to vi [14].
The last, and arguably most important, matrix used in this paper is the
Laplacian matrix. The Laplacian matrix, denoted by L, is a matrix of the same
dimensionality as A and D, defined as the difference between the degree matrix
and the adjacency matrix: L = D − A. L has the same values as D on the
diagonal, and off the diagonal Lij is equal to −Aij .

3

Related work

Existing methods for link prediction in bipartite multi-layer networks for addressing the drug-target interaction problem can be grouped into three classes:
similarity based, random-walker based, and latent models based. The first groupassumes 2 out of 3 possible layers to be similarity networks for drugs and targets
respectively, and exploits similarity information to perform link prediction on thethird bipartite layer [11, 4]. The second models the behavior of a random-walker
to perform link prediction in multi-layer graph using PageRank adaptations [6,7, 21]. Such methods are dependent on fixing the similarity networks and while
we extended the approach to any number of networks in [21], it pays for thisflexibility with high computational cost. The last group of methods maps drugs,
targets and their interactions into a combined feature space, and performs drugtarget interaction prediction using distance functions or regression analysis [35,37]. The most recent family of methods in this mold is often referred to as graph1

All nodes are shared between all layers
Each node is present only in a single layer
3Inter-layer edges, that cross layers, are only between nodes and their counterparts
4
Diagonal couplings for which all possible inter-layer edges are present
24

M. Koptelov et al.

embeddings [15]. The main disadvantage of this group of methods is a certain
lack of interpretability.
The idea to use community information to predict links in graphs is not novel.
Clauset et al. [8] proposed to exploit a learned hierarchical generative community
model to estimate the probabilities of missing links in partially known networks.
The authors of [17, 36, 33] combine community detection with existing edge prediction methods to improve the prediction accuracy. These methods are basedon the hypothesis that vertices in the same community have similar properties,
and missing edges are more likely to be found within communities than elsewhere. Missing edges are predicted by node similarity using nearest-neighbormeasures [36], Stochastic Block Models [17], or in-group and out-group neighborsimilarity measures [33]. Edges can be predicted for vertices belonging to thesame community even if there is no path between them within the community[19]. The density of links in a particular community or between two communities
can be exploited in a naı̈ve Bayes model to predict links [27]. The authors of[1] reimagine communities as groups of edges rather than vertices, and [29] use
community detection to modify similarity measures. Finally, there is a set of
methods which extend the concept of shared neighborhoods [25] to community
neighborhoods [5, 34, 12]. In addition, in [18] neighborhood measures have been
extended to multiple layers.
Community detection in multi-graphs can also be performed in different ways:
directly, by ensemble-based methods, or by graph flattening. The direct methods perform discovery of communities on the multi-layer network directly, e.g.
by adapting objective functions for community detection to the multi-layer setting [22, 32, 10]. Ensemble-based methods perform community detection on eachlayer separately, and aggregate discovered communities afterwards [32]. Flattening approaches, finally, summarize multiple edges into single ones and use
the resulting single-layer network to discover communities by using one of thecommon community detection approaches such as spectral partitioning [24] orLouvain algorithm [3]. In this work we use the last type of approaches due totheir ease of use and potentially low computational complexity.

4

Our approach

In our problem setting, we want to predict links between two distinct types ofnodes, e.g. drugs and targets in our experiments. To achieve this, we perform
communities discovery using an existing community detection approach, thenexploit the discovered communities to solve the link prediction task.
4.1

Link prediction by community detection in bipartite setting

To be able to use existing link-prediction-by-community-detection measures wehave to adapt them to the bipartite setting. Due to the construction of the
networks we use and the community detection methods we evaluate, resulting

Link Prediction via Community Detection in Bipartite Multi-Layer Graphs

5communities can be mixed, i.e. containing both types of nodes, drugs and targets, as well as pure, of either type, drugs or targets only. Also, the community
detection methods we use produce non-overlapping communities only. Mixed
communities can be exploited directly with existing measures for link prediction
via community detection (see Section 3), but pure communities cannot, ignoringa large number of drug-target pairs. To overcome this, we treat all communities
as non-mixed and split mixed communities into pure ones. Notably, this split
does not have to be done explicitly, but a mixed community can be treated as
two pure ones with links between them. We exploit discovered communities in
one of the two proposed ways: by matching “community to community” or “nodeto community”.
Community to community In this case, each drug community is paired witheach target community, then an adapted measure used to perform link prediction between paired communities. Each non-interacting drug-target pair between
paired communities is assigned the same link probability score. At the end of
the matching, each non-interacting drug-target pair from the network will havebeen assigned a single score, which can be used to rank predictions. We refer tothis approach as community to community (or CC ) formulation.
Node to community Another way of exploiting communities is to pair eachnode of one type with communities of the other type. The advantage of thatmethod is that for a selected drug di and target tj , the prediction can be madetwice: once analyzing connections of a drug with target communities and second
analyzing target connections with drug communities, providing a more reliable
estimate. The approach based on this idea is called Bipartite Local Models [2].
The link probability score between di and tj is computed by aggregating thetwo results [4]. We report results using mean as an aggregation function. Our
experiments showed that the difference between max and mean is negligible, andwe use mean to get a more reliable result. We do not consider min as aggregator,
because in case of no evidence for existence of the link in one of the independent
predictions the combined probability is also 0. We refer to this approach as node
to community (or NC ) formulation.
4.2

Existing link prediction measures adaptation

We divide all existing link prediction measures into two categories: neighborhood measures and others, which we refer as community-based. The first groupof measures are based on the notion of neighborhood, i.e. the set of vertices
directly connected to the examined vertices. The semantic similarity between
neighborhood and community, i.e. sets of vertices in both cases, allows us to
use neighborhood measures in our setting. The other measures are not basedon a notion of neighborhood, but on other metrics, and thus are grouped into
separate group in our work.

6

M. Koptelov et al.

Neighborhood measures Many existing link prediction measures exploit theneighborhoods of vertices e.g. in the form of common neighbors (CN), the Jaccard coefficient (JC), a preferential attachment measure (PA), or SimRank (SR)[25]:
CN (di , tj ) = |{v | (di , v) ∈ E} ∩ {u | (tj , u) ∈ E}|,(1)

CN (di , tj ),|{v | (di , v) ∈ E} ∪ {u | (tj , u) ∈ E}|(2)

JC(di , tj ) =P A(di , tj ) = Γ (di ) · Γ (tj ), with Γ (di ) =|V |X

Aik , Γ (tj ) =k=1

SR(di , tj ) =

|V |
X

Ajk ,

(3)

k=1

CN (di , tj ).
P A(di , tj )(4)

Due to the nature of communities we obtain, there is little overlap between vertices’ neighborhoods, preventing the direct use of neighborhood-based measures.
To overcome this, we adapt neighborhood measures for use with our communities, treating them like neighborhoods: the CN measure turns the number ofcommon neighbors of communities di and tj into the number of connections, JC
represents the fraction of all possible connections of di and tj that are connected
to both, PA is defined by a product of degrees of communities di and tj , finally
SR is equal to the number of connections of communities di and tj normalized by
the product of their degrees. Using the CC and NC formulations our bipartite
adaptations take the form:
1. Instead of the measures from Eq. 1-4 we define CNCC , JCCC , PACC and
SRCC versions corresponding to CC matching:
CNCC (di , tj ) = |{(d, t) ∈ E | d ∈ C(di ), t ∈ C(tj )}|,

(5)

CNCC (di , tj ),|C(di )| · |C(tj )|(6)

P ACC (di , tj ) = |ΓC (di )| · |ΓC (tj )|,(7)

JCCC (di , tj ) =SRCC (di , tj ) =CNCC (di , tj ),P ACC (di , tj )(8)where C(di ), C(tj ) represent communities of a drug dPi and a target tj respectively. We overload Γ for communities as Γ (C(v)) = v∈C(v),u∈C(v)w(v, u).
/2. The NC version of CN is defined as the average of the two independent
predictions, CNN C (di ) = |{t | (di , t) ∈ E, t ∈ C(tj )}|, CNN C (tj ) = |{d |(tj , d) ∈ E, d ∈ C(di )}|, for di , and tj respectively:
CNN C (di , tj ) =1(CNN C (di ) + CNN C (tj )) .
2

(9)

Link Prediction via Community Detection in Bipartite Multi-Layer Graphs

7

In the same manner, we can define NC versions for other measures from[25], the JC (Eq. 10), PA (Eq. 11) and SR (Eq. 12), taking into account thatP AN C (di ) = Γ (di ) · Γ (C(tj )) and P AN C (tj ) = Γ (tj ) · Γ (C(di )):
1 CNN C (di ) CNN C (tj )JCN C (di , tj ) =
+
,
(10)
2
|C(tj )|
|C(di )|
1
(P AN C (di ) + P AN C (tj )),2
1 CNN C (di ) CNN C (tj )SRN C (di , tj ) =+.
2 P AN C (di )P AN C (tj )P AN C (di , tj ) =

(11)
(12)

Community-based measures Other measures proposed in the literature arebased on one or several of the following assumptions: all vertices have the same
semantic, all edges have the same semantic, edges are unweighted, or vertices
whose link is to be predicted find themselves in the same community. We therefore cannot use most of the measures proposed in the literature but we can adapt
some to our bipartite setting.
1. Cannistraci et al. [5] in their CAR-based measures propose to exploit thedensity of communities to reward (or penalize) densely (sparsely) connectedneighbors of the vertices whose link is to be predicted. Our adapted CARbased common neighbors (CCN) will be defined as CN regularized by community local degree, which is in turn defined as the sum of weights of alledges inside community. The NC formulation of CCN takes a form:
CCNN C (di , tj ) =1(CCNN C (di ) + CCNN C (tj )) ,2

with CCNN C (di ) and CCNN C (tj ) in turn defined as:
X
CCNN C (di ) = |{t | (di , t) ∈ E, t ∈ C(tj )}| ·(13)

A(tl , tk ) andtl ,tk ∈C(tj )X

CCNN C (tj ) = |{t | (tj , d) ∈ E, d ∈ C(di )}| ·A(dl , dk ).

dl ,dk ∈C(di )In the same manner, the CAR-based Jaccard coefficient (CJC) is redefinedas CCN normalized by the size of the community:
CJCN C (di , tj ) =1(CJCN C (di ) + CJCN C (tj )) ,2

with CJCN C (di ) =CJCN C (tj ) =CCNN C (di )and|C(tj )|CCNN C (tj ).
|C(di )|

(14)

8

M. Koptelov et al.

2. Xie et al. [34] propose to exploit the connection of vertices to communities,
summing over all communities. Our adaptation of their measure, which werefer to as Neighboring community-based (NCB) is defined as the normalized
sum of all CN regularized by the size of the respective community. The NC
formulation of this measure will take the form:
N CBN C (di , tj ) =1(N CBN C (di ) + N CBN C (tj )) ,2

(15)with N CBN C (di ) and N CBN C (tj ) in turn:
N CBN C (di ) =ctX|{t | (di , t) ∈ E, t ∈ Ck }| |{t | t ∈ Ck }|
·
and
|Ck |
|T |

k=1

N CBN C (tj ) =cdX|{d | (tj , d) ∈ E, d ∈ Ck }| |{d | d ∈ Ck }|
·
.
|Ck |
|D|

k=1

Moreover, assuming communities are pure, i.e. consisting only of either drugs
or targets, these equations can be simplified to the sum of all CN normalized
by the number of vertices of one type:c

N CBN C (di ) =t
1 X|{t | (di , t) ∈ E, t ∈ Ck }|,
|T |

k=1
c

N CBN C (tj ) =d
1 X|{d | (tj , d) ∈ E, d ∈ Ck }|.
|D|

k=1

3. Ding et al. [12], finally, propose to exploit the neighborhoods of communities.
Our adaptation of their measure, which the authors refer to as Community
relevance Jaccard coefficient (CRJC), is defined as a number of common
nodes of examined communities and nodes of the opposite type connected tothose communities normalized by the total number of nodes in this selection.
The adapted measure is better suited to a CC formulation:
CRJCCC (di , tj ) =|CRJCCC (di ) ∩ CRJCCC (tj )|,|CRJCCC (di ) ∪ CRJCCC (tj )|(16)

with CRJCCC (di ) and CRJCCC (tj ):CRJCCC (di ) = {t | (d, t) ∈ E, d ∈ C(di )} ∪ {d | d ∈ C(di )},CRJCCC (tj ) = {d | (t, d) ∈ E, t ∈ C(tj )} ∪ {t | t ∈ C(tj )}.

5

Experimental evaluation

To evaluate the two community detection algorithms, the effect of their parameter settings, and the prediction measures defined in the preceding section, we
performed experiments on a number of benchmark data sets for drug-target
activity prediction.

Link Prediction via Community Detection in Bipartite Multi-Layer Graphs

5.1

9Experimental protocol

We begin by evaluating the different measures described in Section 4 with two
common community detection approaches, keeping most of the parameters fixed,
and select the best performing measure. Following this, we show how an internalcross-validation can be used to fixed the methods’ parameters, and report on
their results. Finally, we show what happens if we optimized those parameterson the test data, giving us the arguably best results, and show that the internalcross-validation creates models of similar quality, i.e. using cross-validation is anappropriate method to fix parameters.
Community detection methods We test our approach with spectral partitioning [24] and the Louvain algorithm [3] as community detection approaches.
The first finds the best cut to partition nodes based on eigenvalues of the Laplacian matrix and a threshold method [30, 13], while the second greedily optimizes
modularity, generic measure to determine the quality of each partition produced
by a community detection approach [28, 13]. We apply spectral partitioning tomulti-layer graphs by flattening the graph, i.e. summing edge weights to derive
the adjacency and degree matrices before performing partitioning. We apply the
Louvain algorithm to multi-layer graphs by flattening the graph as well. Since
the algorithm is not limited to adjacency and degree matrices, we create an instance of a single graph, multiple edges of which are aggregated with the sum
function.
Parameters to optimize Spectral partitioning has two parameters: m value
and the thresholding method. The m parameter represents the number of eigenvectors corresponding to the m smallest non-zero eigenvalues used to partition
the graph into at most 2m groups. As thresholds methods we can use sign cut
or default, which partitions entries based on whether they are greater or lessthan zero, bisection cut or median, using the median value of entries in an eigenvector as a threshold, producing two components of approximately equal size[16]. We also evaluate mean, which uses the average, and sum that exploits thefact that there are approximately equally as many positive and negative valuesin eigenvectors of Laplacian matrix, such that in practice they sum to a value
close to zero. Moreover, the same threshold can be applied to all eigenvectors,
or each individual eigenvector can have its own threshold. We call the former
approach global, and the latter individualized. Additionally, the global threshold
can be computed by applying the aggregating function (mean, median or sum)to all eigenvectors or only to the m actually used. We refer to this latter type as
localized. To sum up, we evaluate 9 different thresholding methods: global, localized, individualized and their combinations with mean, median and sum. The
combination global sum is a special case since taking the first eigenvector, whose
entries all have the same, positive, value, into account violates the “close to zero”
property sum thresholding exploits. We therefore do not evaluate that thresholding method, but add default thresholding to the mix for the experimental
evaluation.

10

M. Koptelov et al.

The Louvain algorithm has only one parameter – resolution limit – which defines a modularity scale. Practically speaking, at different moments of time t, thedifference between optimal partitioning and partitioning produced by the Louvain is various and the resolution parameter represents this change in time [23].
Data sets We perform our experiments on the data sets introduced in [35]:Enzyme, G-protein coupled receptors (GPCR), Ion Channels (IC) and Nuclear
Receptors (NR). In addition, we use the Kinase set [9]. These data sets havebeen used in prior work on drug-target interaction prediction [6, 37, 26, 4], andcan be considered benchmarks. The data consist of 3 networks: drug similarities, target similarities and drug-target interaction (the bipartite graph). Theinteraction network is presented as binary relation lists, while the similarity data
are presented by matrices. The data were transformed to adjacency lists, andfor the sake of (computational) convenience we mapped ligand and drug names
to consecutive integers, i.e. l0, l1, l2, . . ., t0, t1, t2, . . ., the required input for our
implementation. The data sets’ basic properties are presented in Table 1.
Table 1. Basic properties of Benchmark and IUPHAR data sets and running times (*– for 1 fold in average with Spectral partitioning and JCCC measure)
Data set Drugs Targets Interactions Layers |V |EnzymeGPCR
IC
NR
Kinase|E|

Sparsity CC Runningtime*, s

445
223
210
54
68

664
95
204
26
442

2926
635
1476
90
1527

3
3
3
3
3

1109
318
414
80
510

321832
29853
44127
1846
101266

0.524
0.592
0.516
0.584
0.780

1
1
1
1
1

58.67
3.99
7.06
0.15
9.94

IUPHAR 8137

2502

12456

6

10639 26706838

0.472

1

3477.8

Evaluation protocol To perform evaluation of our experiments we performed
a 5×5-fold cross-validation, with each fold containing 20% of all drug-target interactions, acting as test set for link prediction once, while community detection
is performed on the other 80%. The process is repeated 5 times, the results areaveraged among all runs.
Quality measures We evaluate all the predictions by AUC (Area Under ROC
Curve) and AUPR (Area Under Precision-Recall Curve), averaging the results.
We also report standard deviation values when it is applicable.
Implementation We implemented spectral partitioning and all link prediction
measures in Python5 , using the networkx library to model the multi-layer network, the python-louvain package as Louvain algorithm implementation, NumPy
for all matrix computations and sklearn to calculate the curves.
5

https://zimmermanna.users.greyc.fr/supplementary-material.html

Link Prediction via Community Detection in Bipartite Multi-Layer Graphs

5.2

11

Experimental results

Link prediction measures evaluation We first test the different link prediction measures from Section 4 on communities produced by either spectral partitioning or the Louvain algorithm. To reduce computational complexity, we use
default parameters of the community detection approaches: default as thresholdfor spectral partitioning and 1.0 as resolution limit for the Louvain algorithm.
Note, that we optimize m for spectral partitioning on the test data in this experiment, because there is no a priori number of eigenvalues that will fit all data. The
results are presented in Fig. 1, with community to community formulations on
the left, node to community ones on the right of each plot. The best-performing
measure for each group is indicated by a + sign over the corresponding bar.
We also report on the figure the optimal m value for every measure in spectral
partitioning.
The results show that a number of measures, e.g. SRCC , CNN C , SRN C ,CCNN C , CJCN C , N CBN C , have acceptable performance in terms of AUC on
most of data sets while the Jaccard coefficient usually performs best for both
the CC and NC versions. These two, JCCC and JCN C , are therefore the measures we will use going forward. Another result is that for these parameter settings spectral partitioning and the Louvain algorithm give approximately thesame AUC, but the latter improves on AUPR. Finally, using node to community predictions requires a lower m, i.e. less fine-grained partitions, for spectral
partitioning.
Parameter selection for spectral partitioning via internal cross-validation
In link prediction, as in any other predictive task, the main issue is choosing parameter values, in the case of spectral partition m and the thresholding method,in the case of Louvain the resolution limit. In the absence of other knowledge,
one would use cross-validation as a systematic method to optimize parameters.
Several-fold cross-validation is also the method of choice to evaluate the performance of a classifier, however, so that we use a double cross-validation in thissection: splitting off an external test fold (containing 20% of present edges) toevaluate the model, and using an internal five-fold cross-validation to fix themodel’s parameters.
During the internal cross-validation, we performed grid search over the different parameter settings, varying m in the interval [1, 25], and testing this value
with all nine options for thresholding.
Table 2 presents the results. It shows both the results of internal evaluation,i.e. on the validation set used to fix parameter values, and of the external evaluation, i.e. on the unseen training data. The main conclusion to draw is that thosevalues align very closely w.r.t. AUC, i.e. that there is no risk of overfitting whenbuilding the model. Concerning AUPR, interestingly enough, the results on thetesting folds are in fact higher than for the validation data used in the internalcross-validation. Notably, using N C matching always gives better results thanCC matching, often by a large margin.

12

M. Koptelov et al.

Fig. 1. Link prediction measures evaluation on the benchmark data sets. The symbol +denotes the best performing measure for each group of formulations in each data set.

Link Prediction via Community Detection in Bipartite Multi-Layer Graphs

13

Table 2. Spectral partitioning parameter optimization via internal cross-validation
Data set Measure

Internal validationµ AUC σ µ AUPR σ

External validationµ AUC σ µ AUPR σ

Enzyme JCCCJCN C
GPCR JCCC
JCN C
IC
JCCC
JCN C
NR
JCCC
JCN C
Kinase JCCC
JCN C

0.85
0.91
0.79
0.84
0.82
0.87
0.73
0.75
0.76
0.85

0.85
0.92
0.80
0.85
0.83
0.88
0.72
0.77
0.77
0.86

0.00
0.00
0.01
0.01
0.01
0.00
0.02
0.03
0.01
0.00

0.14
0.19
0.11
0.19
0.31
0.32
0.21
0.19
0.17
0.26

0.04
0.02
0.02
0.01
0.03
0.06
0.03
0.02
0.01
0.02

0.01
0.01
0.02
0.01
0.02
0.01
0.06
0.06
0.03
0.01

0.19
0.26
0.15
0.25
0.40
0.41
0.24
0.23
0.23
0.35

0.07
0.06
0.02
0.02
0.04
0.05
0.08
0.13
0.02
0.02

Parameter selection for Louvain via internal cross-validation The only
parameter to optimize for Louvain is the resolution parameter, which we vary in
the interval [0.1, 1] using steps of 0.1.
Table 3. Louvain algorithm resolution optimization via internal cross-validation
Data set Measure

Internal validationµ AUC σ µ AUPR σ

External validationµ AUC σ µ AUPR σ

Enzyme JCCCJCN C
GPCR JCCC
JCN C
IC
JCCC
JCN C
NR
JCCC
JCN C
Kinase JCCC
JCN C

0.94
0.95
0.73
0.85
0.94
0.96
0.79
0.81
0.72
0.90

0.96
0.96
0.80
0.89
0.95
0.97
0.82
0.80
0.73
0.91

0.00
0.00
0.01
0.01
0.00
0.00
0.03
0.03
0.00
0.00

0.52
0.56
0.18
0.28
0.50
0.61
0.27
0.30
0.15
0.38

0.00
0.02
0.02
0.03
0.01
0.02
0.06
0.05
0.01
0.01

0.00
0.01
0.03
0.01
0.01
0.01
0.06
0.09
0.01
0.01

0.69
0.71
0.31
0.49
0.65
0.78
0.45
0.42
0.19
0.50

0.04
0.02
0.05
0.04
0.04
0.03
0.13
0.14
0.01
0.03

As in the case of spectral partitioning, the performance is rather close interms of AUC but the differences in AUPR are even more pronounced. GPCR
is a bit of an outlier for this experiment in that the differences between internal
quality estimation and test fold results are larger than for the other data set.
The superior performance of N C matching holds, however.
Comparison to the state-of-the-art From the two tables above, we can seethat Louvain with JCN C performs better than spectral partitioning. Here, we
compare its results to those of the state-of-the-art methods reported in [4] interms of AUC:
– Enzyme: 0.97 compared to 0.96 for our method with Louvain,

14

M. Koptelov et al.

– GPCR: 0.95 compared to 0.89,– IC: 0.98 compared to 0.97,– NR: 0.88 comared to 0.82,– and Kinase: 0.9 compared to 0.91,
and can see that our proposed approach performs very similar.
Baseline comparison We have addressed this problem setting in prior work,
using a random walk approach [21] which is basically an extension of PageRankfor any number of layers, and thus can be considered as a baseline in this work.
JCCC and JCN C in combination with both spectral partitioning and the Louvain
clearly outperform that baseline in terms of AUC (0.84, 0.8, 0.76, 0.63 and 0.61
for the Enzyme, GPCR, IC, NR, and Kinase data sets respectively) and AUPR
(0.15, 0.22, 0.27, 0.26 and 0.13 for the Enzyme, GPCR, IC, NR, and Kinase data
sets respectively).
Interpretability Our approach offers a straightforward option for interpretation/explainability of a link prediction: for each of the two vertices, we can show
the communities they belong to, the weights of intra-community edges, the number and layout of inter-community edges, and their numerical translation by themeasure and matching technique. This is a possibility that is not available forrecent, well-performing techniques based on graph embeddings.
Scalability In order to verify scalability of our approach we tested it on a bigger
data set, IUPHAR, having 6 layers, and described in detail in [21]. The data set
basic properties are presented in Table 1. We used spectral partitioning withdefault threshold and an optimal value of m = 400 optimized on the test data.
We used JC, the best performing measure and CC as a matching techniquefor performance reasons. As for the smaller networks, the prediction quality(AUC=0.7365 ± 0.02 std, AUPR 0.01 ± 0.0 std) is much better than in ourprevious work [21] (AUC 0.5735) (which was derived from leave-out-out crossvalidation). Running times for a single test fold, the majority of which is taken up
by community matching, are shown in Table 1. We can see that the quotient of
the number of IUPHAR edges to the number in smaller networks is lower thanthat of running times, indicating that the method scales when using spectral
partitioning.

6

Conclusion and perspectives

We have presented a framework for link prediction in bipartite multi-layer graphs
using graph community structure and link prediction measures adapted fromthose proposed in the literature. We have found empirically that combining thewell-known and relatively straightforward Jaccard coefficient, particularly in a
BLM formulation, with the Louvain algorithm for community detection allows
us to achieve results that are competitive with the state-of-the-art.

Link Prediction via Community Detection in Bipartite Multi-Layer Graphs

15

We have limited ourselves to two easy-to-use community detection methods
in this work, and will evaluate the use of other methods in the future. We also
intend to perform experiments on larger data sets that have shown themselves to
be too computationally expensive for methods such as the one proposed in [4].
Finally, we intend to add layers derived from other information sources to the
networks and use our approach to identify possible redundancies among them.

References
1. Ahn, Y.Y., Bagrow, J.P., Lehmann, S.: Link communities reveal multiscale complexity in networks. nature 466(7307), 761 (2010)
2. Bleakley, K., Yamanishi, Y.: Supervised prediction of drug–target interactions using bipartite local models. Bioinformatics 25(18), 2397–2403 (2009)
3. Blondel, V.D., Guillaume, J.L., Lambiotte, R., Lefebvre, E.: Fast unfolding of communities in large networks. Journal of statistical mechanics: theory and experiment2008(10), P10008 (2008)
4. Buza, K., Peska, L.: Aladin: A new approach for drug–target interaction prediction.
In: ECML/PKDD. pp. 322–337. Springer (2017)
5. Cannistraci, C.V., Alanis-Lobato, G., Ravasi, T.: From link-prediction in brain connectomes and protein interactomes to the local-community-paradigm in complex
networks. Scientific reports 3, 1613 (2013)
6. Chen, X., Liu, M.X., Yan, G.Y.: Drug–target interaction prediction by random
walk on the heterogeneous network. Molecular BioSystems 8(7), 1970–1978 (2012)
7. Cheng, F., Zhou, Y., Li, W., Liu, G., Tang, Y.: Prediction of chemical-protein
interactions network with weighted network-based inference method. PloS one 7(7),e41064 (2012)
8. Clauset, A., Moore, C., Newman, M.E.: Hierarchical structure and the predictionof missing links in networks. Nature 453(7191), 98 (2008)
9. Davis, M.I., Hunt, J.P., Herrgard, S., Ciceri, P., Wodicka, L.M., Pallares, G.,
Hocker, M., Treiber, D.K., Zarrinkar, P.P.: Comprehensive analysis of kinase inhibitor selectivity. Nature biotechnology 29(11), 1046 (2011)
10. De Bacco, C., Power, E.A., Larremore, D.B., Moore, C.: Community detection,link prediction, and layer interdependence in multilayer networks. Phys. Review E
95(4), 042317 (2017)11. Ding, H., Takigawa, I., Mamitsuka, H., Zhu, S.: Similarity-based machine learning methods for predicting drug–target interactions: a brief review. Briefings inbioinformatics 15(5), 734–747 (2013)
12. Ding, J., Jiao, L., Wu, J., Liu, F.: Prediction of missing links based on community
relevance and ruler inference. Knowledge-Based Systems 98, 200–215 (2016)
13. Fortunato, S.: Community detection in graphs. Phys. Reports 486(3-5), 75–174(2010)
14. Gallier, J.H.: Notes on elementary spectral graph theory. applications to graphclustering using normalized cuts. CoRR abs/1311.2492 (2013)
15. Goyal, P., Ferrara, E.: Graph embedding techniques, applications, and performance: A survey. Knowledge-Based Systems 151, 78–94 (2018)
16. Guattery, S., Miller, G.L.: On the performance of spectral graph partitioning methods. In: SODA. vol. 95, pp. 233–242 (1995)
17. Guimerà, R., Sales-Pardo, M.: Missing and spurious interactions and the reconstruction of complex networks. Proc. of the Nat. Academy of Sciences 106(52),22073–22078 (2009)

16

M. Koptelov et al.

18. Hristova, D., Noulas, A., Brown, C., Musolesi, M., Mascolo, C.: A multilayer approach to multiplexity and link prediction in online geo-social networks. EPJ Data
Science 5(1), 24 (2016)19. Jalili, M., Orouskhani, Y., Asgari, M., Alipourfard, N., Perc, M.: Link prediction
in multiplex online social networks. Royal Society open science 4(2), 160863 (2017)
20. Kivelä, M., Arenas, A., Barthelemy, M., Gleeson, J.P., Moreno, Y., Porter, M.A.:
Multilayer networks. J. Complex Networks 2(3), 203–271 (2014)
21. Koptelov, M., Zimmermann, A., Crémilleux, B.: Link prediction in multi-layer
networks and its application to drug design. In: IDA. pp. 175–187. Springer (2018)
22. Kuncheva, Z., Montana, G.: Community detection in multiplex networks using
locally adaptive random walks. In: ASONAM. pp. 1308–1315. ACM (2015)
23. Lambiotte, R., Delvenne, J.C., Barahona, M.: Laplacian dynamics and multiscale
modular structure in networks (2008)
24. Leskovec, J., Rajaraman, A., Ullman, J.D.: Mining of massive datasets. Cambridge
university press (2014)
25. Liben-Nowell, D., Kleinberg, J.: The link-prediction problem for social networks. J.
of the Am. society for information science and technology 58(7), 1019–1031 (2007)
26. Lim, H., Gray, P., Xie, L., Poleksic, A.: Improved genome-scale multi-target virtual screening via a novel collaborative filtering approach to cold-start problem.
Scientific reports 6, 38860 (2016)
27. Liu, Z., He, J.L., Kapoor, K., Srivastava, J.: Correlations between community
structure and link formation in complex networks. PloS one 8(9), e72908 (2013)
28. Newman, M.E., Girvan, M.: Finding and evaluating community structure in networks. Phys. Review E 69(2), 026113 (2004)
29. Soundarajan, S., Hopcroft, J.: Using community information to improve the precision of link prediction methods. In: WWW. pp. 607–608. ACM (2012)
30. Spielman, D.A., Teng, S.H.: Spectral partitioning works: Planar graphs and finite
element meshes. Linear Algebra and its Applications 421(2-3), 284–305 (2007)
31. Sun, J., Qu, H., Chakrabarti, D., Faloutsos, C.: Neighborhood formation andanomaly detection in bipartite graphs. In: ICDM. pp. 8–pp. IEEE (2005)
32. Tagarelli, A., Amelio, A., Gullo, F.: Ensemble-based community detection in multilayer networks. Data Mining and Knowledge Discovery 31(5), 1506–1543 (2017)
33. Valverde-Rebaza, J.C., de Andrade Lopes, A.: Link prediction in online social
networks using group information. In: ICCSA. pp. 31–45. Springer (2014)
34. Xie, Z., Dong, E., Li, J., Kong, D., Wu, N.: Potential links by neighbor communities.
Physica A: Statistical Mechanics and its Applications 406, 244–252 (2014)
35. Yamanishi, Y., Araki, M., Gutteridge, A., Honda, W., Kanehisa, M.: Predictionof drug–target interaction networks from the integration of chemical and genomic
spaces. Bioinformatics 24(13), i232–i240 (2008)
36. Yan, B., Gregory, S.: Finding missing edges in networks based on their community
structure. Phys. Review E 85(5), 056112 (2012)
37. Zheng, X., Ding, H., Mamitsuka, H., Zhu, S.: Collaborative matrix factorization
with multiple similarities for predicting drug-target interactions. In: KDD. pp.
1025–1033. ACM (2013)