# A Review of Link Prediction Applications in Network Biology

Ahmad F. Al Musawi  Department of Computer Science, Virginia Commonwealth
UniversityRichmondVirginiaUSA<EMAIL_ADDRESS>Department of Information
Technology, University of Thi QarAnnasiriyahThi QarIraq<EMAIL_ADDRESS>0000-0002-5508-9968 ,  Satyaki Roy  Department of Mathematical Sciences,
University of Alabama in HuntsvilleAlabamaUSA<EMAIL_ADDRESS>and  Preetam
Ghosh  Department of Computer Science, Virginia Commonwealth
UniversityRichmondVirginiaUSA<EMAIL_ADDRESS>
(2018; 20 February 2007; 12 March 2009; 5 June 2009)

###### Abstract.

In the domain of network biology, the interactions among heterogeneous genomic
and molecular entities are represented through networks. Link prediction (LP)
methodologies are instrumental in inferring missing or prospective
associations within these biological networks. In this review, we
systematically dissect the attributes of local, centrality, and embedding-
based LP approaches, applied to static and dynamic biological networks. We
undertake an examination of the current applications of LP metrics for
predicting links between diseases, genes, proteins, RNA, microbiomes, drugs,
and neurons. We carry out comprehensive performance evaluations on established
biological network datasets to show the practical applications of standard LP
models. Moreover, we compare the similarity in prediction trends among the
models and the specific network attributes that contribute to effective link
prediction, before underscoring the role of LP in addressing the formidable
challenges prevalent in biological systems, ranging from noise, bias, and data
sparseness to interpretability. We conclude the review with an exploration of
the essential characteristics expected from future LP models, poised to
advance our comprehension of the intricate interactions governing biological
systems.

link prediction, network biology, graph representation learning

††copyright: acmcopyright††journalyear: 2018††doi: XXXXXXX.XXXXXXX††journal:
JACM††journalvolume: 37††journalnumber: 4††article: 111††publicationmonth:
8††ccs: Computer systems organization Embedded systems††ccs: Computer systems
organization Redundancy††ccs: Computer systems organization Robotics††ccs:
Networks Network reliability

##  1\. Introduction

Understanding the intricate interplay among biological entities lies at the
core of many questions in the field of systems biology. One approach to
addressing this challenge involves harnessing the power of network analysis,
notably through the mathematical construct of graphs, where biological
entities are represented as nodes, and their interconnections take the form of
links (pavlopoulos2011using, ; berger2008graph, ). The integration of network
theory in the study of molecular and biomedical interactions has led to the
emergence of network biology. This interdisciplinary domain harnesses cutting-
edge computational and visualization methodologies to unravel the intricate
structures and dynamic behaviors intrinsic to complex biological systems based
on the underlying molecular interactions, namely, protein-protein, metabolic,
signaling, and transcription-regulatory interactions (barabasi2004network, ;
BARH2014385, ).

The concept of link prediction (LP) plays a pivotal role in the burgeoning
field of network biology. It involves forecasting the likelihood of missing or
unknown connections or interactions between entities in a network (lu2011link,
). LP has been applied successfully to build recommender systems for social
networks, collaborative filtering, viral marketing, etc, based on similarity
in individual profiles (su2020link, ). In the realm of network biology, this
translates to the capability to anticipate relationships among biological
entities, such as genes, proteins, or metabolites. These predictive techniques
rely on the analysis of existing network topology, incorporating knowledge
from diverse sources like protein-protein interaction databases, gene
expression profiles, or disease association data (breit2020openbiolink, ).

The applications of link prediction in network biology are manifold. They
enable the identification of potential protein-protein interactions, the
inference of gene regulatory networks, the prediction of disease-gene
associations, and the exploration of underlying biological pathways (mirsig, ;
rev1, ; rev2, ). By unveiling these hidden connections, link prediction
contributes significantly to our understanding of complex biological systems,
facilitating the discovery of novel biomarkers, drug targets, and insights
into the intricate web of biological interactions. Furthermore, LP techniques
can help researchers model and predict these temporal dynamics by forecasting
how network connections will develop or weaken over time
(divakaran2020temporal, ). This temporal understanding is particularly crucial
for tracking disease progression, understanding gene expression changes, or
following the evolution of biological pathways.

Figure 1. Outline of the review on link prediction applications in network
biology

In this review, we delve into the application of link prediction (LP)
techniques within the domain of biological networks (refer to Fig. 1). Our
exploration spans various classes of LP methods, encompassing those reliant on
immediate neighborhoods, network centrality, and embedding techniques. We
focus on their effectiveness in predicting associations among various
biological entities, including diseases, genes, proteins, and drugs, to name a
few. Our investigation extends to the evaluation of performance metrics on
both static and dynamic biological networks. Finally, we synthesize our
findings with a discussion of the challenges encountered and future avenues of
research in the ongoing journey of LP’s application in the intricate landscape
of network biology.

This paper has been organized as follows. Sec. 2 covers the preliminaries of
graphs and their features leveraged to study biological systems. Sec. 3 covers
the three classes of LP techniques, namely, similarity-based, centrality-
based, and embedding-based, while Sec. 4 presents its existing applications in
network biology. Sec. 5 demonstrates the performance of LP in static and
dynamic biological networks. Finally, Sec. 6 and 7 discuss the challenges,
future directions, and conclusions.

##  2\. Preliminaries

A biological network is represented as a graph $G(V,E)$, where the vertex (or
node) set $V$ may represent genes, transcriptional factors, proteins,
diseases, drugs or side effects, etc. and the links represent an association
between a pair of nodes. A graph $G$ can be represented as an adjacency matrix
$A$ such that $A_{uv}=1$ if there is a relationship between nodes
$v_{x},v_{y}$ and $A_{uv}=0$ otherwise.

###  2.1. Types of Graphs

Different types of graphs are used to capture myriad biological interactions
(west2001introduction, ). The edges of $G$ may be directed or undirected. In
the undirected graph, the relationship between two nodes is symmetric, i.e.,
$A_{ij}=A_{ji}$, while in a directed graph, edges have a direction
(asymmetric) where $A_{ij}\neq A_{ji}$. The edges can also be weighted or
unweighted. In a weighted graph, the edge weights measure the strength or
intensity of the relationship between nodes while all edges have the same
weight in an unweighted graph. On the other hand, links may have signs,
namely, positive and negative. where positive and negative edges may denote
the up-regulation and down-regulation of a gene by a transcription factor,
respectively. Finally, a homogeneous graph, also called a non-attributed
graph, consists of nodes of a single type, whereas heterogeneous graphs
contain nodes and edges of different types, allowing for greater information
expression. Heterogeneous graphs can be further categorized into bipartite,
tripartite, or multimodal, depending on the number of node types.

A bipartite graph is effective when modeling the relationship between a pair
of biomedical entity types, say disease set ($a\in A$) and drug set ($b\in
B$). A bipartite network contains disjoint sets of nodes $A$ and $B$, where a
possible link $(a,b)$ may only exist between a disease and a drug. On many
occasions, a bipartite network is converted from being a two-mode network into
a one-mode projection network comprising a single entity set as nodes. In
other words, the drug-disease bipartite network is converted into a network
containing diseases as nodes and links between a pair of diseases sharing one
or more drugs. A bipartite graph can be generalized to $k$-partite graphs to
represent $k$ biomedical entity types. Lastly, graphs can evolve over a period
of time resulting in temporal networks. Let
$\mathbf{G}=\\{G_{1},...,$G${}_{T}\\}$ be a set of networks that represent the
evolving behavior of a graph over different $T$ time steps. Evolution
typically refers to the emergence or disappearance of edges among the set of
nodes, keeping the vertex set unaltered, i.e.,
$\mathbf{G}=\\{(V,E_{t})|t\in\\{1,..,T\\}\\}$.

###  2.2. Problem setting

An input network dataset represented by a graph $G=(V,E)$ is divided into two
subgraphs of training $G^{\tau}=(V,E^{\tau})$ and testing $G^{P}(V,E^{P})$,
which have non-overlapping edge sets. Training graph $G^{\tau}$ is created by
randomly sampling a fraction $f$ of all links, i.e., $|E^{\tau}|=f\times|E|$,
The testing (or probe) graph $G^{P}$ is obtained by taking the remaining edges
$E^{P}$ from $G$, making $E=E^{\tau}\cup E^{P}$. The link prediction (LP)
model is trained on $G^{\tau}$ before predicting the likelihood of an edge
between node pairs in $G^{P}$. Finally, the accuracy of the LP model is high
if it assigns a high likelihood score to the existing links in $G^{P}$ and low
scores to nonexistent links, and vice versa.

##  3\. Methodology

We provide an overview of the link prediction methods that have been widely
used for predicting links in the biomedical and biological domains. These
methods are categorized into local similarity and path-based approaches,
centrality-based approaches, and representation learning approaches.

###  3.1. Similarity-based Approaches

One intuitive and widely used approach for predicting potential relationships
is to look over the similarity of features shared between any unconnected pair
of nodes.

####  3.1.1. Local approaches

The local approaches explore the immediate neighborhood of a node $u$,
comprising a set of nodes directly connected to them within a network (denoted
by $\Gamma_{u}$). The property that two nodes have greater potential to share
a relationship (i.e., a link) if they share similar neighbors has been
leveraged by several approaches. The common neighbor (CN) metric gauges the
likelihood of a link between nodes $u,v$ as the number of neighbors they share
(lorrain1971structural, ), i.e., $S^{CN}_{u,v}=|\Gamma_{u}\cap\Gamma_{v}|$.
The variants of this approach are summarized in Table 1 and have been used as
baselines for the prediction of biological relationships (refer to Sec. 4 for
details).

Table 1. Unweighted and weighted local similarity-based metrics: $\bar{k}_{u}$ is the weighted degree of node $u$, $\lambda_{u}=max(0,n_{avg}-\bar{k}_{u})$, $n_{avg}$ represents weighted average node degree of the network, wLCL is the sum of the weights of the links connecting the common neighbors of $u$ and $v$ (local community links). $e_{u}$ refers to the external degree of $u$, computed considering the neighbours of $u$ that are not common neighbours of $u$ and $v$. Unweighted metric |  Formula
---|---
Salton (cosine similarity, CS) (salton1983introduction, ) |  $S^{SA}_{u,v}=\frac{|\Gamma_{u}\cap\Gamma_{v}|}{\sqrt{|\Gamma_{u}||\Gamma_{v}|}}$
Jaccard Index (JI) (jaccard1901etude, ) |  $S^{JA}_{u,v}~{}=\frac{|\Gamma_{u}\cap\Gamma_{v}|}{|\Gamma_{u}\cup\Gamma_{v}|}$
Sorenson index (SI) (sorensen1948method, ) |  $S^{HPI}_{u,v}=\frac{|\Gamma_{u}\cap\Gamma_{v}|}{min(|\Gamma_{u}|,|\Gamma_{v}|)}$
Hub Promoted Index (HPI) (ravasz2002hierarchical, ) |  $S^{JA}_{u,v}~{}=\frac{|\Gamma_{u}\cap\Gamma_{v}|}{|\Gamma_{u}\cup\Gamma_{v}|}$
Hub Depressed Index (HDI) (zhou2009predicting, ) |  $S^{HDI}_{u,v}=\frac{|\Gamma_{u}\cap\Gamma_{v}|}{max(|\Gamma_{u}|,|\Gamma_{v}|)}$
Resource Allocation (RA) (zhou2009predicting, ) |  $S^{RA}_{u,v}=\sum\limits_{z\in\Gamma_{u}\cap\Gamma_{v}}\frac{1}{|\Gamma_{z}|}$
Leicht-Holme-Newman(LHN-1) (leicht2006vertex, ) |  $S^{LHN}_{u,v}=\frac{|\Gamma_{u}\cap\Gamma_{v}|}{|\Gamma_{u}||\Gamma_{v}|}$
Preferential Attachment (PA) (barabasi1999emergence, ) |  $S^{PA}_{u,v}=|\Gamma_{u}||\Gamma_{v}|$
Adamic-Adar (AA) (adamic2003friends, ) |  $S^{AA}_{u,v}=\sum\limits_{z\in\Gamma_{u}\cap\Gamma_{v}}\frac{1}{\log|\Gamma_{z}|}$
Cannistraci-Alanis-Ravasi-based variation of the resource allocation (CAR) (cannistraci2013link, ; ghasemian2020stacking, ) |  $S^{CAR}_{u,v}=\sum\limits_{z\in\Gamma_{u}\cap\Gamma_{v}}\frac{\Gamma_{u}\cap\Gamma_{v}\cap\Gamma_{z}}{|\Gamma_{z}|}$
Cannistraci-Jaccard (CJC) (daminelli2015common, ) |  $S^{CJC}_{u,v}=\frac{|\Gamma_{u}\cap\Gamma_{v}|.S^{LCL}_{u,v}}{\Gamma_{u}\cup\Gamma_{v}}$
Cannistraci–Adamic–Adar (CAA) (daminelli2015common, ) |  $S^{CAA}_{u,v}=\sum\limits_{z\in(\Gamma_{u}\cap\Gamma(\Gamma_{v}))\cup(\Gamma_{v}\cap\Gamma(\Gamma_{u}))}\frac{|\gamma(z)|}{\log|\Gamma_{z}|}$
CPA (daminelli2015common, ; cannistraci2013link, ) |  $S^{CPA}_{u,v}=e_{u}e_{v}+e_{u}S^{CAR}_{u,v}+e_{v}S^{CAR}_{u,v}+(S^{CAR}_{u,v})^{2}$
CRA (daminelli2015common, ) |  $S^{CRA}_{u,v}=\sum\limits_{z\in(\Gamma_{u}\cap\Gamma(\Gamma_{v}))\cup(\Gamma_{v}\cap\Gamma(\Gamma_{u}))}\frac{|\gamma(z)|}{|\Gamma_{z}|}$
Mutual Information Index (MI) (tan2014link, ) |  $S^{MI}_{u,v}=\sum\limits_{k\in O_{uv}}I(L^{1}_{uv};k)-I(L^{1}_{uv})$
Weighted metric |  Formula
Common Neighbors (wCN) |  $wCN_{u,v}=\sum_{z\in\Gamma_{u}\cap\Gamma_{v}}\frac{w(x,z)+w(y,z)}{2}$
Preferential Attachment (wPA) |  $wPA_{u,v}=\bar{k}_{u}\times\bar{k}_{y}$
Adamic-Adar (wAA) |  $wAA_{u,v}=wCN_{u,v}\times\frac{1}{log(\sum_{\bar{z}\in\Gamma(z)}w(\bar{z},z))}$
Adjusted Czekanowski-Dice Dissimilarity (wACDD) |  $wACDD_{u,v}=\frac{2wCN_{u,v}}{\bar{k}_{u}+\bar{k}_{y}+\lambda_{u}+\lambda_{v}}$
Cannistraci-Alanis-Ravasi Index (wCAR) |  $wCAR_{u,v}=wCN_{u,v}\times wLCL$

####  3.1.2. Path-based approaches

These measures explore a slightly larger neighborhood (as opposed to the one-
hop neighborhood as is the case with local approaches) and similarity is
measured by the degree of overlap in the larger neighborhoods
(muscoloni2018local, ; zhou2021experimental, ).

  1. (1)

CH2-L2 Index is a link prediction model that assigns a reward for the internal
connectivity existing among common neighbors and penalizes outside
connectivity.

(1)
$S^{CH2-L2}_{u,v}=\sum\limits_{i\in\Gamma_{u}\cap\Gamma_{v}}\frac{1+C_{i}}{1+O_{i}}$

Here $C_{i}$ represents the number of neighbors of node $i$ that exist in
$\Gamma_{u}\cap\Gamma_{v}$, $O_{i}$ represents the number of neighbors of node
$i$ that do not exist in $\Gamma_{u}\cap\Gamma_{v}$ nor in $u$ or $v$.

  2. (2)

CH2-L3 Index: very similar to CH2-L2 metric, this metric considers all three
path lengths (two intermediate nodes $u,v$) between the targeted edge ($u,v$).

(2)
$S^{CH2-L3}_{u,v}=\sum\limits_{i\in\Gamma_{u},j\in\Gamma_{v}}\frac{A_{i,j}\sqrt{(1+\bar{C_{i}})(1+\bar{C_{j}})}}{\sqrt{(1+\bar{O_{i}})(1+\bar{O_{j}})}}$

Here $\bar{C_{i}}$ represents the number of links between node $i$ and all the
nodes that exist in the set of intermediate nodes on all 3-hop paths
connecting nodes $u$ and $v$, $\bar{O_{i}}$ represents the number of links
between node $i$ and all nodes that are not $u,v$ nor the intermediate nodes
on any 3-hop paths connecting $u$ and $v$.

Table 2. Network centrality measures, where $m$ is the sum of the weights of all edges, $A$ is an adjacency matrix, $k_{i}$ is the degree of node $i$, $c_{i}$ is the community of node $i$, $\delta$ is 1 if $c_{i}=c_{j}$ and 0 if they are not. $d(v,u)$ is the shortest-path distance between node $u$ and node $v$. $\sigma_{st}$ is the number of shortest paths from $s$ to $t$, $\sigma_{st}(v)$ is the number of shortest paths from $s$ to $t$ that pass through $v$. $V_{NB\\_INT}(u)$ is the neighbor node set of source node $u$, $E_{NB\\_INT}(u)$ is the edge set in $G_{NB}(u)=(V_{NB}(u),E_{NB}(u))$. $\alpha$ and $\beta$ are constants and $d_{k}$ is the out-degree of node $k$ if such degree is positive, or $d_{k}=1$ if the out-degree of $k$ is null. Metric |  Description |  Formula
---|---|---
Modularity (newman2006modularity, ) |  Find network communities |  $Q=\frac{1}{2m}\sum\limits_{uv\in V}[A_{uv}-\frac{k_{u}k_{v}}{2m}]\delta(c_{u}.c_{v})$
Closeness (bavelas1950communication, ) |  How close a node is to all other nodes |  $C(u)=\frac{N-1}{\sum_{v\neq u}d(v,u)}$
Betweenness (brandes2001faster, ) |  Nodes that intercept paths between other nodes |  ${BC}_{v}=\sum\limits_{s\neq v\neq t\in V}\frac{\sigma_{st}(v)}{\sigma_{st}}$
Katz (katz1953new, ) |  Nodes that reach other community nodes |  $x_{u}=\alpha\sum\limits_{v}A_{uv}x_{v}+\beta$
Eigenvector and Pagerank (bonacich1987power, ; page1999pagerank, ) |  Nodes connected to other important nodes |  $Ax=\lambda x$; $x_{u}=\alpha\sum\limits_{k}\frac{A_{k,u}}{d_{k}}\,x_{k}+\beta$
Hubs and authority (kleinberg1999authoritative, ) |  Nodes that are well-connected (hubs) and nodes that bridge hubs (authority) |  $auth(u)=A^{T}hub(u)$ $hub(u)=Aauth(u)$
Local interaction density (luo2015identification, ) |  Nodes with high interaction among its neighbors |  $LID(u)=\frac{|E_{NB\\_INT}(u)|}{|V_{NB\\_INT}(u)|}$
Linear Threshold Rank (riquelme2019neighborhood, ) |  Nodes with ability to influence non-neighbors |  $LTR(i)=\frac{|f(\\{i\\})\cup\Gamma(i)|}{n}$

###  3.2. Centrality-based Approaches

Network centrality measures (refer to Table 2 for details) quantify the
importance of nodes within a network. These measures are based on the
following concepts in network theory.

  * •

Community influence: Network modularity (newman2006modularity, ) is a standard
metric to identify network modules or communities. The relative importance of
any node within a community is measured using Katz centrality capturing the
reachability of other community nodes to the given node via its immediate
neighbors or first-degree nodes (katz1953new, ). Local interaction density
(LID) estimates the amount of interaction between the neighbors of a given
node (luo2015identification, ). Similarly, the edge clustering coefficient
(ECC) (mistry2017diffslc, ) for an edge connecting nodes $u$ and $v$ is:

(3) $ECC^{(3)}_{u,v}=\frac{z^{(3)}_{u,v}+1}{\min\\{(k_{u}-1),(k_{v}-1)\\}}$

Here, $z^{(3)}_{u,v}$ denotes the total number of triangles that encompass the
edge $(u,v)$, while $k_{u}$ and $k_{v}$ represent the number of triangles that
the nodes $u$ and $v$ each participate in, respectively.

  * •

Neighbors of significance: The importance of a node is measured in terms of
the importance of its first-degree nodes. Both PageRank and eigenvector
centralities deem a node significant if other important nodes point to it
(page1999pagerank, ; bonacich1987power, ). For example, the common neighbor
and centrality-based parameterized algorithm (CCPA) (ahmad2020missing, )
merges common neighbors with node centrality, particularly, closeness
centrality, which is defined by the average shortest path to other nodes.

(4)
$S_{u,v}^{CCPA}=\alpha.(|\Gamma_{u}\cap\Gamma_{v}|)+(1-\alpha).\frac{|V|}{d_{uv}}$

The term $\frac{|V|}{d_{uv}}$ represents the closeness centrality for edge
$(u,v)$, $d_{uv}$ is the shortest distance between the nodes $u$ and $v$.
$\alpha$ represents the user-set parameter which falls between 0 and 1. It
balances the influence of common neighbors and centrality.

  * •

Bridging components: A central node is one that acts as a bridge connecting
different network components. Betweenness centrality measures the number of
shortest paths between other node pairs that a given node intercepts
(brandes2001faster, ). Hub and authority centrality generalizes the
Eigenvector centrality by finding well-connected nodes (termed hubs) and
bridges between the hubs (termed authority) (kleinberg1999authoritative, ).

  * •

Influence diffusion: Linear Threshold Rank (LTR) is defined as the total
number of nodes activated by influence diffusion when the initial activation
set is formed by a node and its immediate neighbors (riquelme2019neighborhood,
).

###  3.3. Representation Learning-based Approaches

In this section, we cover approaches that encode the structural properties of
nodes into low-dimensional vector representations, called embeddings, before
predicting the existence of links between a pair of nodes based on the
similarity in their embeddings. We classify these methods into three groups:
matrix factorization-based, random walk-based, and neural network-based.

####  3.3.1. Matrix Factorization based methods

Non-negative matrix factorization (NMF) (wang2012nonnegative, ; cai2010graph,
) is a dimension reduction technique that decomposes a large data matrix
$X=[x_{1},...,x_{N}]\in\mathbb{R}^{M\times N}$ into a product of two (or more)
smaller matrices, i.e., $X\approx UV^{T}$, $U=[u_{ik}]\in\mathbb{R}^{M\times
K},V=[v_{jk}]\in\mathbb{R}^{N\times K}$, where the number of latent features
is a user-defined input. The decomposed matrices $U,V$, both of which are
constrained to have non-negative entries, are termed feature matrix and
coefficient matrix, respectively. While the feature matrix contains the
embedding of each data point (or node in the context of graph data) to be
leveraged for subsequent link prediction tasks, the coefficient matrix informs
the contribution of a feature in the feature vector toward the data point.

Specifically for graph data, the matrix $X$ could be a weighted or unweighted
adjacency matrix. NMF starts by initializing $U$ and $V^{T}$ with random non-
negative values. Since the goal of the optimization is to minimize the
difference between $X$ and $UV^{T}$, several cost functions are proposed such
as Frobenius norm (see Eq. 5), Kullback-Leibler (KL) divergence, and Itakura-
Saito divergence. Also, several iterative algorithms exist for updating both
$U$ and $V$ to minimize the cost function, such as multiplicative updates,
alternating least squares, and projected gradient descent.

(5)
$\min_{U,V}||X-UV^{T}||^{2}=\min(\sum_{i,j}(x_{ij}-\sum_{k=1}^{K}u_{ik}v_{jk}^{T})^{2})$

NMF lends itself to temporal link prediction approaches (see Sec. 3.4 for
details), where the goal is to analyze the evolving interaction between a
given pair of nodes over time (zhang2021temporal, ). The following three
variants have been put forth to meet different optimization requirements of
NMF:

  1. (1)

In the simplest form, it minimizes the approximation error between the
adjacency matrix $A$ and decomposed matrices $U,V$ in three consecutive time
points, i.e., $\min\sum||A-U.V^{T}||^{2}$.

  2. (2)

The intrinsic topological properties of the network have been incorporated by
refining the objective function as $\min\sum
a_{u,v}\times||f_{u}-f_{v}||^{2}$. This ensures that the latent vectors of two
nodes $u$ and $v$ are similar if they are located nearby in the input network
$G$.

  3. (3)

A consensus representation of the feature matrix, given by $U^{*}$ was
incorporated to tackle the problem of outliers in learning the latent factor.
Instead of learning the shared basis matrix of all snapshots $U$, $U^{*}$ is
estimated from all previous snapshots. The direct application of these methods
has been highlighted in the application section (see Sec. 4.1).

NMF has a wide range of applications in data mining, medical imaging, voice
processing, and link prediction (chen2017link, ). The other matrix
factorization-based techniques are based on singular value decomposition
(franceschini2016svd, ), principal component analysis (bro2014principal, ),
and independent component analysis (du2013neural, ).

####  3.3.2. Random walk-based methods

Several graph-based learning models utilize the NLP deep learning concept of
SkipGram in their models. SkipGram (mikolov2013efficient, ) is a neural
network model with one hidden layer aimed at learning the association of words
given a large document collection. The inputs of the SkipGram model are the
co-occurrence of words in the same sentence (window). This model preserves the
topological proximity of the words into embedded representation.

The DeepWalk (perozzi2014deepwalk, ) algorithm (DW) is a graph representation
learning technique that involves generating random walks from each node in a
graph and using the word2vec algorithm to learn the embeddings of the nodes.
During the random walk generation step, a fixed-length walk is performed from
each node, and the resulting sequence of nodes is treated as a sentence. The
Skip-gram variant of the word2vec algorithm is then applied to learn the node
embeddings, which capture the graph’s structural relationships and provide a
low-dimensional representation of the nodes. To determine the embeddings,
DeepWalk introduces a mapping function $\phi:v\in
V\rightarrow\mathbf{R}^{\mathbf{d}}$. Specifically, it leverages local
information obtained from truncated random walks. The similarity between any
two nodes $u,v$, given by $sim(u,v)$, is commensurate with the frequency of
co-occurrence in the same walks. Finally, the embedding of node $u$
($\phi_{u}$) preserves the topological similarity, as:

(6) $sim(u,v)=\phi_{u}^{T}\times\phi_{v}$

DeepWalk generates random walks starting on each node in the graph to be used
to gauge similarity and embedding, and its time complexity is bounded by
$O(|V|)$ (pimentel2019efficient, ). On the other hand, Node2Vec
(grover2016node2vec, )(NV) uses a flexible biased random walks algorithm that
combines breadth-first and depth-first sampling to generate node sequences
while preserving homophily and structural equivalence. For a node, $u\in V$, a
neighborhood $\Gamma_{s}(u)$ is defined as a set of nodes traversed by the
surfer starting at $u$.

Figure 2. Walk transitioned from node $t$ to $v$ and is now evaluating its
next step. The transition probability is given by $\alpha$. The illustration
has been redrawn from (grover2016node2vec, ).

Node2Vec modulates the exploration of neighborhood through parameters $p$ and
$q$ (see Fig. 2). A low $p$ $(<\min(q,1))$ enables the surfer to backtrack
often and stay restricted to a local neighborhood (breadth-first search-like),
whereas $q<1$ makes the surfer explore a larger neighborhood (depth-first
search-like). To generate embeddings, Node2Vec maximizes the log probability:

(7) $\max_{\phi}\sum_{u\in V}\log\prod_{v\in\Gamma_{s}(u)}P(v|\phi_{u})$

$P(v|\phi_{u})$ is the softmax function calculated using the embeddings of
nodes $u$ and $v$, i.e.,
$\frac{\exp(\phi_{u},\phi_{v})}{\sum_{w}\exp(\phi_{u},\phi_{w})}$.

Evidently, both DeepWalk and Node2Vec capture the topological properties of
nodes, whereby nodes that are located close to one another in the network tend
to possess similar embeddings. However, another embedding model called
struct2Vec, represents the structural similarity of the nodes. where two nodes
with similar local neighborhoods have similar embeddings even if they belong
to different components of the network (ribeiro2017struc2vec, ). To achieve
this, it employs a hierarchical approach: similarity at the bottom of the
hierarchy depends on the local neighborhoods, whereas at the top, similarity
depends on a larger neighborhood around the nodes being embedded.

####  3.3.3. Graph Neural Networks Methods

These models learn embeddings by applying the principles of deep neural
networks to graphical data. In a graph convolution network (GCN), the features
of the node are passed to their neighbor via message-passing (kipf2016semi, ).
Later, the passed information is fused with existing features of the node
using a predefined function (namely, sum, mean, or maximum, etc.). These
aggregated features are then passed to fully connected neural networks to
learn updated embeddings given specific objective functions. The inclusion of
many convolutions reflects a deeper collected knowledge of a wide area of the
graph into the final embedding of the nodes. The resulting embedding
representation is used for link prediction purposes.

GraphSAGE, SAGE short for SAmple and aggreGatE, is a technique that combines
sampling and aggregation of node-level features from the input graph
(hamilton2017inductive, ). As shown in Fig. 3, in the sampling phase,
GraphSAGE gathers a neighborhood of depth $K$ around each node. In the
aggregation phase, the embeddings of all the neighbors of node $v$, given by
$\Gamma_{v}$, are aggregated into a single vector
($\mathbf{h}_{\Gamma_{v}}^{k}$), before concatenating the embedding of $v$
($\mathbf{h}_{v}$) with the aggregated neighbor vector. Finally, the
concatenated vector is passed through a fully connected layer with nonlinear
activation function $\sigma$ controlled by weighted matrices $\mathbf{W}^{k}$,
where $k=1,2,\cdots,K$. The stated steps are as follows:

(8)
$\displaystyle\mathbf{h}_{\Gamma_{v}}^{k}=AGGREGATE_{k}(\\{\mathbf{h}_{u}^{k-1},u\in\Gamma_{v}\\})\;$
(9)
$\displaystyle\mathbf{h}_{v}^{k}=\sigma(\mathbf{W}^{k}.CONCAT(\mathbf{h}_{v}^{k-1},\mathbf{h}_{\Gamma_{v}}^{k}))$

(a) Sample neighborhood.

(b) Aggregate feature information from neighbors.

(c) Predict graph context and label using aggregated information.

Figure 3. GraphSage workflow of 1) neighborhood sampling, 2) aggregating
information from those samples, and then 3) prediction on the collected
information. The illustration has been redrawn from (hamilton2017inductive, ).

The weight parameters ($\mathbf{W}^{k}$) are updated using a loss function $J$
that encourages neighboring nodes to get similar embeddings. Specifically, the
function attempts to increase the similarity between the embeddings of $v$ and
a node $u$ that co-occurs in random walks initiated at $v$ while reducing the
similarity between $v$ and an arbitrary node $v_{n}$ sampled from a negative
sampling distribution $P_{n}$, as:

(10)
$J_{G}(v)=-\log(\sigma(\mathbf{h}_{v}^{T}.\mathbf{h}_{u}))-Q.\mathbf{E}_{v_{n}\sim
P_{n}(v)}\log(\sigma(-\mathbf{h}_{v}^{T}.\mathbf{h}_{v_{n}}))$

The other GNN is the graph autoencoder (GAE), which includes two components:
encoder and decoder (kipf2016variational, ). The encoder maps the nodes in the
input network to their respective latent representations through a series of
message-passing operations. The decoder, on the other hand, reads the latent
factor and reconstructs the original graph structure. The overall training
objective of a GAE is to minimize the error between the original graph and the
reconstructed graph. During training, the encoder and decoder work in tandem,
using backpropagation to minimize this loss.

###  3.4. Link Prediction in Temporal Networks

Temporal networks are a sequence of many static networks, each marked with a
timestamp $1,2,\cdots,T$. As discussed in Sec. 2.1, the purpose of link
prediction (LP) metrics is to predict links at time $T+1$ based on network
connectivity till time $T$. We consider three temporal metrics that adapt
existing static LP models, namely, collapsed tensor (CT) (liben2003link, ),
weighted collapsed tensor (WCT) (sharan2008temporal, ), Jaccard, and non-
negative matrix factorization (NMF). These metrics can be applied to
unweighted networks with adjacency weights $A_{uv}=\\{0,1\\}$ and weighted
networks with $A_{uv}\in[0,1]$.

  1. (1)

In collapsed tensor, the scores for the edge weights at time $T+1$
($S_{uv}^{T+1}$) are gauged to be the average of all edges across all prior
timestamps $t=1,2,\cdots,T$, as shown in Eq. 11.

(11) $S_{uv}^{T+1}=\sum_{t=1}^{T}\frac{A_{uv}^{t}}{T}$

  2. (2)

In weighted CT, the likelihood scores of edges at time $T+1$ ($S_{uv}^{T+1}$)
are calculated as in Eq. 12 where $\theta\in[0,1]$ is a weighing parameter
that assigns higher importance to recent links.

(12) $S_{uv}^{T+1}=\sum_{t=1}^{T}(1-\theta)^{T-t}A_{uv}^{t}$

  3. (3)

The temporal Jaccard coefficient leverages local similarity-based metrics (see
Sec. 3.1), namely common neighbors, to predict future links at time $T+1$
based on links at time $T$, as follows.

(13) $S_{uv}^{T+1}=\frac{|N_{u}(W^{T})\cap N_{v}(W^{T})|}{|N_{u}(W^{T})\cup
N_{v}(W^{T})|}$

Figure 4. A schematic representation showing the steps in temporal non-
negative matrix factorization-based link prediction. The matrices $U_{t}$ and
$V_{t}$ are updated based on the adjacency matrices $A$ over three consecutive
time instances $t-1,t,t+1$, before calculating the final matrices $V$ and
$U_{*}$ to predict links in a network.

  4. (4)

Temporal LP using structural consistency regularized NMF(zhang2021temporal, )
is utilized to predict the network at time $T+1$. Here, the adjacency matrix
$A_{t}$ is factorized into two non-negative matrices, the feature matrix $U$
and the coefficient matrix $V$. An optimization function is applied to
minimize the total difference between the current adjacency matrix $A_{t}$ and
the product of its factorized matrices amounting to the low-rank approximation
of $A_{t}$, i.e., $min(A_{t}-U_{t}V_{t}^{T})$. This process is done by
constantly updating the factor matrices over different time slots ($t$) to
ensure the minimization objective function. All of the $U,V$, and $U_{*}$ are
initialized with random values, and their final values are learned by adopting
an iterative strategy that fixes two of the matrices while updating the third
one (see Eqs. 14 and 15). The final network at time $T+1$ can be calculated by
Eqs. 16 \- 18 following three phases: matrix factorization, consensus learning
for basis matrices, and feature collapsing (see Fig. 4). Note that
$\alpha,\beta,\theta$ are weighing parameters with default values of $0.001$,
$0.8$, and $0.8$, respectively.

(14)
$U_{t}=U_{t}\frac{\sum_{i=t-1}^{t+1}A_{i}V_{t}+U_{*}}{3U_{t}V_{t}^{\prime}V_{t}+U_{t}}$

(15) $V_{t}=V_{t}\frac{\sum_{i=t-1}^{t+1}A^{\prime}_{i}U_{t}+\alpha
A_{i}V_{t}}{3V_{t}U_{t}^{\prime}U_{t}+\alpha\sum_{i=t-1}^{t+1}D_{i}V_{t}}$

(16) $V=\sum_{t=1}^{T}\theta^{T-t}V_{t}$

(17) $U_{*}=\frac{1}{\sum_{i=1}^{t}\beta^{t-i}}\sum_{i=1}^{t}\beta^{t-i}U_{i}$

(18) $A_{T+1}=U_{*}V$

##  4\. Applications

In this section, we discuss the application of link prediction techniques in
inferring disease-gene, protein-protein, disease-RNA, microbiome, drugs, and
brain networks.

###  4.1. Disease Gene Association Networks

Link prediction (LP) has been applied to gene networks, where the weights on
links connecting two genes denote the number of shared attributes (such as
diseases, drugs, ontology, etc.). Lobato et al. applied similarity-based LP
measures on gene interaction networks, focusing on autoimmune diseases,
namely, diabetic retinopathy, nephropathy, Kawasaki disease, systemic lupus
erythematosus, celiac disease, rheumatoid arthritis ankylosing spondylitis,
Crohn’s disease, primary sclerosing cholangitis, ulcerative colitis, type I
diabetes, vitiligo, AIDS, hypothyroidism, and psoriasis (alanis2014exploring,
). The gene networks were inferred from the bipartite gene-disease
associations 111Bipartite networks are a class of networks comprising two
groups of nodes (say, diseases and genes), where links may exist between nodes
of different groups. obtained from the genome-wide association studies (GWAS)
catalog (hindorff2009catalog, ), by creating a new network where two genes are
connected by a link (called an internal link (allali2011link, )) of weight
equal to the number of common diseases they are associated with (see Fig. 5a).
Their analysis employing weighted LP metric (see Table 1 for the formulation
of weighted similarity-based measures) showed that weighted CN, AA, ACDD, and
CAR can identify key gene associations for myriad autoimmune diseases.

(a)

(b)

Figure 5. Bipartite network of genes and diseases and its weighted one-mode
projection. This illustration has been redrawn from (alanis2014exploring, ).

Yang et al. leveraged LP to create a comprehensive network by integrating
associations from 6 gene or protein association datasets (yang2017integration,
). Their approach unfolded in the following three steps.

  * •

Raw networks. For each network dataset, the combined likelihood score of a
link between any pair of nodes was obtained as a weighted sum of scores from
several LP metrics. Following this, the highest-scoring links are preserved in
the 6 raw networks.

  * •

Final reconstruction networks. Each potential link in the raw network is
classified into 3 groups: old, new, and confirmed. The old links are the ones
in the original networks but not in the raw networks, while the new links are
the ones present in the raw networks but not in the original networks. The
confirmed links are the links that are present in both (see Fig. 5b). Finally,
in each reconstruction network, the workflow preserves the confirmed links as
well as the old or new links present in at least one of the other original
networks. Each link in a reconstruction network is given a score equal to the
weighted sum of its weight in the original network ($S_{FS}$) and raw network
link weight ($S_{TS}$):

(19) $S=\beta\times S_{FS}+(1-\beta)\times S_{TS}\hskip
14.22636pt(\beta\in[0,1])$

  * •

Integrated network. Given a score of a link in the $i^{th}$ final
reconstruction network, $S_{i}$, the algorithm assigns a final link score
given by:

(20) $\mathbf{S}=1-\sqrt{\prod_{i=1}^{n}(1-S_{i})}$

As part of temporal link prediction of gene association in cancer, Zhang et
al. (zhang2021temporal, ) presented an improvement over conventional non-
negative matrix factorization (refer to Sec. 3.3.1), termed structural
consistency non-negative matrix factorization, where the temporal adjacency
matrices for networks of gene interactions $A$ is jointly decomposed into the
corresponding basis and feature matrix representations ($B,F$) across three
timepoints $t-1,t,t+1$ while preserving the intrinsic topological properties
of the temporal networks in the feature vectors of the genes.

###  4.2. Protein-Protein interaction networks (PPINs)

Protein-protein interaction networks are networks with proteins as nodes and
links representing the interaction between pairs of proteins by means of
structural and functional subunits called domains. Kumar and Sharma proposed a
metric that combines eigenvector centrality (see Sec. 3.2) and the shortest
path length to estimate the probability of a pair of nodes sharing a link. The
proposed metric is defined as
$S_{u,v}^{S}DEV=\frac{\sqrt{{evc}_{u}+{evc}_{v}}}{sp(u,v)}$, where ${evc}_{u}$
is the eigenvector centrality of node $u$ and $sp(u,v)$ is the length of the
shortest path between nodes $u$ and $v$ (kumar2021novel, ).

The other LP approaches for PPINs involve graph embedding models (refer to
Sec. 3.3). To incorporate both structural and functional attributes into
association prediction, Nasiri et al. proposed an LP technique for unipartite
as well as bipartite PPINs that also contain node weights capturing the
functional attributes of the proteins. First, Louvain community detection
(blondel2008fast, ) is applied on a logical network of features to group
similar features, before selecting a subset of features for the subsequent
computations. Second, a PPIN is constructed by connecting proteins based on a
combination of similarities in topology and reduced features. Third, DeepWalk
(discussed in Sec. 3.3.2) is applied to the PPINs to infer associations based
on the Hadamard operator of the embedding vectors of a pair of nodes.
Similarly, Kang et al. introduced a GNN-based model applied to PPINs from the
STRING consortium (szklarczyk2015string, ), where node embeddings were created
using GCN encoder before employing a propagation rule to create link
representations for predicting protein association (kang2022lr, ). Finally,
Zhao, C., et al. designed another GNN-based framework that incorporated two
key features for the prediction of molecular interactions, namely, a mix-hop
aggregator and contrastive self-supervised GNN (zhao2021csgnn, ). While the
mix-hop aggregator allows the updates to incorporate higher-order or indirect
neighbor information into the node embeddings, contrastive self-supervised GNN
preserves local and global network information to enhance the generalizability
of the proposed model.

###  4.3. Disease Non-coding RNA networks

MicroRNAs and long non-coding RNAs affect gene expression controlling the
onset and progression of several diseases, including rare and genetic ones
(finotti2019micrornas, ). Predicting the association between RNAs, namely,
microRNA (miRNA) and long non-coding (lncRNA), and diseases is indispensable
for comprehending the molecular underpinnings of diseases. The analysis of
disease-RNA networks can help infer unknown relationships between the two
entities, resulting in the identification of therapeutic intervention. Wen et.
al constructed a bipartite network based on the known miRNA-disease
associations, where each miRNA (or disease) is expressed as an association
profile via a binary feature vector (zhang2019fast, ). Two similarity
matrices, namely the miRNA-miRNA similarity and disease-disease similarity,
are computed via the Fast Linear Neighborhood Similarity measure and
association profiles. Label propagation is applied separately to both, before
using a weighted average to predict the miRNA-disease associations.

The other LP techniques for such networks are based on graph neural networks
(GNNs), as discussed in Sec. 3.3.3. Silva and Spinosa harnessed the graph
autoencoder (GAE) framework to acquire the latent representation of nodes’
features and edges and employed a neural network classifier to predict edges
(silva2021graph, ). Similarly, Shen et al. utilized GNN to predict ncRNA-
protein interactions (NPI) across five different datasets. The model was
developed by integrating GraphSAGE on a bipartite network of NPIs as input
(shen2021npi, ). Finally, Li et al. employed GNN for miRNA-disease
associations. The model first constructs a bipartite graph of miRNAs and
diseases to represent their associations. An encoder is then used to generate
low-dimensional embeddings of miRNA and disease nodes, while consolidating
heterogeneous information from their respective neighborhoods, using an
aggregator function and a multi-layer perceptron. As a last step, the
embeddings are fed into a bilinear decoder to detect potential connections
between miRNA and disease nodes (li2021graph, ).

###  4.4. Microbiome Networks

Research on the association between the imbalance in the gut microbial
community (called dysbiosis) and systemic diseases is at a nascent stage.
Existing research aims to study the role of the oral microbiome in the
development of rheumatoid arthritis, diabetes mellitus, and pancreatic cancer.
The scientific community is relying on the advent of high-throughput
sequencing, AI, and big data technologies, to establish the effect of microbes
on health. It is important to study the confounding caused by non-modifiable
factors (like age, gender, ethnicity, and genetic makeup) and modifiable
factors (i.e., lifestyle, oral health status, and systemic factors)
(seneviratne2020oral, ).

It is worth noting that the prediction of microbiome-disease associations has
not always been formulated as a graph problem but as a supervised and deep
machine-learning one. For instance, Larsen and Dai employed support vector
machines (SVMs) to predict host status (dysbiotic or non-dysbiotic) from
microbiome feature information, such as the microbiome community structures,
predicted community enzyme function profiles, total and secondary community
metabolomes (larsen2015metabolome, ). Dahl et al. employed random forests
(RFs) to study the effect of maternal gut microbiome on premature deaths from
fecal samples of 121 mothers (dahl2017gut, ). Reiman et al. employed CNNs to
investigate how the microbial markers of the host may determine their
microbiome interactions contributing to subsequent diseases (reiman2020popphy,
). Metwally et al. utilized a long short-term memory approach to forecast food
allergies during early life based on the longitudinal profiles of the gut
microbiome in subjects, exhibiting improved predicted power than RFs, SVMs,
and deep neural networks (metwally2019utilizing, ).

Finally, Fu et al. leveraged a natural language processing technique to
generate a knowledge graph (KG) of microbes and diseases (fu2020integrated, ).
Next, they further enriched the KG by incorporating additional bacterial
feature information, such as strain, salinity, oxygen requirement, temperature
range of growth environment, and habitat, through clustering and association
analysis. Lastly, they trained deep learning, matrix factorization, and KG
embedding models on triplets of the head entity, relationship, and tail entity
of the KG to infer microbe-disease associations.

###  4.5. Drug Association

Drug association networks capture the relationship between potential drug
targets for diseases, the mechanism of action of a drug on a disease, or the
side effects of a given drug. The simplest representation of drug associations
is a bipartite network, where links may only exist between different entity
types, like drugs and side effects, drugs and diseases, etc. Luo attempted to
infer the toxicity of drugs through local similarity-based LP metrics (refer
to Sec. 3.1.1) on a bipartite network of diseases and their side effects
(luo2014predicting, ) generated from the SIDER2 dataset containing side effect
frequency for a drug (kuhn2010side, ). Gundogan et al. (gundougan2017link, )
applied the similarity-based metrics to a disease-drug bipartite network
inferred from a database of drugs, diseases, percentage of users who prefer
these drugs, class of drugs, etc. (drugs2006drugs, ), in a manner depicted in
Fig. 5a.

Others employed graph neural network (GNN) based methods for predicting drug-
disease associations. A key application of LP lies in drug repurposing, where
the goal is to find therapeutic utilities for existing drugs. Munoz et al.
designed a GNN-based workflow, called REDIRECTION (griesser2008redirection, ),
to find new drug-disease associations from a biomedical knowledgebase, called
DISNET (prieto2022disnet, ), containing information regarding diseases,
symptoms, and drugs. REDIRECTION is the drug-disease network (see Fig. 6 top)
as input and applies a two-layer convolution approach, each containing
normalization and nonlinearity activation function (ReLU). The embeddings are
encoded using GraphSAGE (see Sec. 3.3.3). Next, the decoder calculates the dot
product of embedding followed by sigmoid transformation to get the link score
between a disease-gene pair (see Fig. 6 bottom). Finally, the model parameters
are optimized using the Binary Cross Entropy as the loss function. Similarly,
Wang et al. extended a graph convolutional network model, Decagon, on the
identification of potential drug targets (wang2021drug, ). Instead of
leveraging the bipartite relationship, they used open-source drug datasets,
namely, Drugbank, SIDER, HPRD, etc., to identify target-target, drug-target,
and drug-drug relationships as links, while drug and target characteristics
were incorporated as node attributes and exhibited high prediction accuracy on
the drug-disease heterogeneous network.

Figure 6. REDIRECTION architecture showing a drug-phenotype interaction (top)
and the phases of encoder-decoder model architecture (bottom). The figure has
been redrawn from (griesser2008redirection, ).

The other LP approach for drug interaction prediction involves community
detection and supervised machine learning (ML). First, given a multilayer
bipartite network of drugs and their targets with links existing between a
pair of drug nodes, a pair of target nodes, and a drug-target pair, an
approach by Koptelov et al. predicts unknown drug-target associations
(koptelov2021lpbycd, ). To this end, pure communities (T) comprising only
drugs (D) and only targets (T) are first identified within the network, before
applying local similarity-based LP metrics in two ways: community-to-community
and node-to-community. In community-to-community network representation, LP is
applied to a network of communities as nodes and links exist between pure drug
community and target communities (see Fig. 7a); whereas in node-to-community,
links exist between a drug community and a target community, and vice versa
(Fig. 7b). In both, the links are weighted, denoting the number of links
existing between community pairs and community-node pairs in the original
drug-target bipartite network. Second, Jiang et al. proposed a two-step
approach, where embeddings of diseases and drugs were learned from a network
of drugs, diseases, proteins, miRNAs, and lncRNAs before using a supervised ML
(random forest model) to predict drug-disease associations. The proposed
approach was verified on several benchmark multi-biomolecular networks as well
as by successfully predicting a ranked list of genes connected to two common
human diseases (jiang2022effective, ).

###  4.6. Brain networks

Brain networks capture the interaction among different regions of the brain.
The latest imaging technologies made it possible to model the significant
changes in the anatomy and connections in the brain caused by disease
conditions. Efforts have been made to leverage the known topological
attributes of brain connectome, such as degree, clustering coefficients, the
shortest path length, transitivity, efficiency, etc., in combination with the
local link prediction (LP) approach (see Sec. 3.1.1) to track and predict
these changes in connectivity (he2018link, ). He et al. considered the time-
varying electroencephalography (EEG) dataset of epilepsy patients during
seizures before using a measure called, Phase Locking Value (PLV), to infer
the strength or weight of connections among different parts of the brain.
Their analysis showed that resource allocation (RA) improved greater link
prediction accuracy on the weighted networks than other local LP measures,
namely, common neighbor (CN), Adamic-Adar (AA), and Sorenson algorithms.

(a)

(b)

Figure 7. Community to community matching example. The labels assigned to the
edges indicate the count of connections between vertices belonging to matched
communities. This illustration has been redrawn from (koptelov2021lpbycd, ).

(a)

(b)

Figure 8. Prediction in brain networks: (a) Cannistraci-Alanis-Ravasi (CAR)
where two nodes (colored black) are likely to be connected if their immediate
neighbors (colored white) are mutually connected; (b) differential
connectivity in brain network, where links (colored white) present at time
$t_{0}$ disappear at time $t_{1}$ and new links (colored black) emerge at time
$t_{1}$.

Cannistraci et al. compared the performance of local metrics against a stack
of path-based approaches, called the Cannistraci-Alanis-Ravasi (CAR) index
(refer to Sec. 3.1.2), which proposes that two nodes are more likely to be
linked if their immediate neighbors are mutually connected forming a small
community (cannistraci2013link, ). Their analysis of two networks (cortical
connectome and frontal ganglia connectome) with neurons as nodes and synaptic
connections as links show that the combination of CAR and preferential
attachment, Cannistraci preferential attachment (CPA) achieves the highest
prediction accuracy. The authors intuit that the formation of new synapses
during the learning process could be a function of the existing local synaptic
communities (see Fig. 8a).

Sulaimani et al. applied local LP metrics to predict the evolution (i.e.,
addition and removal) of links in brain networks of Alzheimer’s disease
(sulaimany2017predicting, ). Specifically, given a network acquired by whole-
brain magnetic resonance imaging (MRI) of the patients at time $t$, the goal
of their time-varying LP problem is to predict the changes in connectivity at
$t^{\prime}$ ($t^{\prime}>t$). At any given $t$, a differential matrix is
created by subtracting the adjacency matrix at $t-1$ from that of $t$. Thus,
an entry of 0, 1, and -1 denote no change, link addition, and link removal,
respectively (refer to Fig. 8b for a schematic of the differential matrix).
While addition is predicted using the high likelihood of association based on
a metric, link removal is achieved by flipping the bits of the matrix before
applying LP. This study also utilizes local LP metrics, namely, RA, CN, AA,
PA, and Jaccard, to show that AA can track the changes in connectivity at
different stages of Alzheimer’s progression.

##  5\. Performance Evaluation

To assess the effectiveness of various static as well as dynamic LP models
(see Sec. 3), we select representative models from the similarity, centrality,
embedding, and temporal categories and evaluate their performance using
specific datasets. We conduct a comprehensive evaluation of the models using a
5-fold cross-validation approach and report the mean (and standard deviation
of) the area under the curve (AUC) for the receiver operating characteristic
(ROC) across the folds.

###  5.1. Evaluation Techniques and Datasets

To predict links in static biological networks (see Table. 3), we used CAR,
CH2_L2 and CH2_L3 (local and global similarity-based metrics); DeepWalk,
Node2Vec, GCN, graphSAGE and GAE (embedding and neural network methods); and
CCPA and ECC (centrality-based methods). Each input biological network
$G=(V,E)$ is split into training and testing graphs $G^{\tau}$ and $G^{P}$,
containing 80% and 20% of the edges in $E$, respectively (details discussed in
Sec. 2.2). Similarly, to predict links at time $T+1$ in temporal networks
($G_{T+1}$), the training set comprises the network snapshots of earlier time
instances, i.e., ($G_{1},G_{2},\cdots,G_{T}$). We used the following
parameters: learning rate $0.01$, 100 training epochs, node embedding size
$8$, and 32 randomly chosen embedding features. For the random walk-based
models, the number and the length of random walks are both set to $100$. For
supervised models, the nodes in $G^{\tau}$ are labeled using the Louvain
community detection algorithm (de2011generalized, ).

Table 3. Network Statistics, $|V|$: number of nodes, $|E|$: number of edges, GCC: transitivity, ACC: Avg. clustering coeff., $D$: Density, $r$: Assortativity, ASP: Avg. shortest path, $d$: diameter, MOD: modularity. (The abbreviation ts. against the dynamic networks DPPIN refers to the number of timestamps or network snapshots.) Networks | $|V|$ | $|E|$ | GCC | ACC | $D$ | $r$ | ASP | $d$ | MOD
---|---|---|---|---|---|---|---|---|---
ENZYMES_g296 (nr, ) | 125 | 282 | 0.029 | 0.006 | 0.018 | 0.287 | 12.94 | 32 | 0.758
bn-mouse_visual-cortex_2 (nr, ) | 193 | 428 | 0.005 | 0.021 | 0.012 | -0.845 | 4.271 | 8 | 0.753
bn-macaque-rhesus_brain_1 (nr, ) | 242 | 6108 | 0.337 | 0.450 | 0.105 | -0.055 | 2.218 | 4 | 0.307
bio-yeast-protein-inter (nr, ) | 1870 | 4480 | 0.055 | 0.067 | 0.001 | -0.156 | 6.812 | 19 | 0.847
bio-grid-mouse (nr, ) | 2900 | 6544 | 0 | 0 | 0.0008 | -0.153 | 9.555 | 31 | 0.925
bio-celegans-dir (nr, ) | 453 | 4065 | 0.124 | 0.647 | 0.020 | -0.22 | 2.664 | 7 | 0.405
Se-DoDecagon_sidefx (biosnapnets, ) | 594 | 1118 | 0 | 0 | 0.0032 | -0.526 | 1.978 | 2 | 0.926
PDN | 437 | 5753 | 0.119 | 0.168 | 0.030 | -0.131 | 0 | 0 | 0.329
DPPIN-Babu (fu2022dppin, ) (36 ts.) | 5003 | 111,466 |  |  |  |  |  |  |
DPPIN-Breitkreutz (fu2022dppin, ) (36 ts.) | 869 | 39,250 |  |  |  |  |  |  |
DPPIN-Yu (fu2022dppin, ) (36 ts.) | 1163 | 3602 |  |  |  |  |  |  |

###  5.2. Performance Evaluation of the static models

Fig 9a shows that there is considerable variation in the performance of
different LP models, in terms of their AUC values, across different networks.

(a) AUC (STD) performance.

(b) Time consumption in seconds.

Figure 9. Performance evaluation and time consumption of the ten different
models implemented on different networks. We reported the average AUC values
and their standard deviation using 5-fold cross-validation. The Models are
CAR, CH2_L3, CH2_L2, CCPA, ECC, DW, N2V, GCN, GraphSAGE and GAE.

Cannistraci-Alanis-Ravasi-based variation of the resource allocation (CAR)
presents consistently average performance (AUC $0.5-0.7$) across all networks,
indicating a reliable but not leading efficacy. CH2_L2 varies greatly, leading
in bn-macaque-rhesus_brain_1 and bio-celegans-dir, yet falling to lower ranks
in networks like ENZYMES_g296 and bio-grid-mouse, showing a network-dependent
performance. CH2_L3, similar to CH2_L2, excels in bn-macaque-rhesus_brain_1
and bio-celegans-dir, showing particular strength in certain biological
networks.

Both centrality-based parameterized algorithm (CCPA) and edge clustering
coefficient (ECC) consistently show average AUC performance across networks,
with their closest performance observed in bio-celegans-dir. The similarity in
the performance characteristics of ECC and CCPA can be ascribed to their
emphasis on the immediate relationships and interactions between nodes. Recall
from Sec. 3.2, ECC-based link prediction evaluates the probability of edge
formation by considering the degree of clustering around an edge, emphasizing
local connectivity. Likewise, CCPA, incorporating node closeness and common
neighbors, leverages proximity and direct ties.

DeepWalk performs notably well in PDN, suggesting it is well-suited for
networks with a structure that aligns with random walk-based methods, while
Node2Vec’s performance is more varied but tends to follow DW closely,
indicating it may share some methodological strengths and weaknesses. Graph
convolutional network (GCN) and GraphSAGE are the top performers in several
networks, with GraphSAGE taking the lead in ENZYMES_g296 and Se-
DoDecagon_sidefx, showcasing the potency of graph neural network models in
these domains. Graph autoencoder models, while sharing the GNN approach, show
more variability, suggesting that the nuances of GNN architecture and
parameters can significantly impact performance. Overall, the GNN models (GCN,
GraphSAGE, GAE) tend to rank higher, reflecting their sophisticated
representation learning capabilities.

Fig. 9b shows the average time consumed in seconds for 5-fold cross-validation
experiments. N2V, CH2_L3, and DW exhibit the longest running times. This
extended runtime is attributed to the comprehensive exploration of a wider
neighborhood during model training. In contrast, CH2_L2 and CAR have the
shortest runtimes, as they confine their exploration to a smaller
neighborhood.

###  5.3. Comparison of Link Prediction Models

####  5.3.1. Exploration versus Efficiency

Neighborhood exploration during the training phase determines the efficacy of
a model in predicting links in biological networks. The local LP metrics (see
Sec. 3.1.1), which rely on graph similarity, offer computational efficiency as
they investigate a limited neighborhood around each node. The focus on
proximity in terms of common neighborhoods between pairs of nodes may often
lead to a narrower scope that can miss critical long-range relationships
(mayo, ), potentially sacrificing prediction accuracy. On the other hand,
centrality and embedding-based LP models (see Secs. 3.2 and 3.3) encompass a
broader neighborhood. They gather information from multiple hops, aggregating
relationships over extended network distances to formulate their predictions.
This broader perspective, though more computationally intensive, often
captures richer network patterns of intricate associations among biological
entities.

The exploration of a very large neighborhood, while beneficial in capturing
long-range relationships, can present its own challenges. For instance, when
the neighborhood is expansive, the model may generate embeddings that are
excessively similar and indistinguishable, limiting its discriminative power.
This over-smoothing phenomenon (li2018deeper, ) can result in a network
representation where nodes exhibit little diversity in their predictive
features. Thus, to determine the ideal LP model, one must weigh these trade-
offs. Researchers must consider the balance between computational efficiency
and prediction accuracy in their respective domains. The key lies in tuning
the model parameters to strike a balance in neighborhood exploration, ensuring
that the LP model can provide optimal predictions while navigating the
heterogeneous biological and biomedical networks. This delicate calibration of
neighborhood size, guided by the unique characteristics of the biological
system, is pivotal to achieving the best predictive performance.

We compare the extent of correlation in the performance of the LP models. For
each biological network, we rank the AUC scores from different network models
from best to worst (see Table 4). Following this, we calculate the Kendall
rank correlation coefficient between each pair of LP models, where the
corresponding scores represent the extent of their similarity. Fig. 10a shows
the coefficients between each pair of models in green and red if the
corresponding p-value is less than or equal and greater than $0.05$,
respectively. It shows a lack of consensus among the models, suggesting that
different models work well for different networks. However, there exists some
correlation between the local and path-based models (namely, CAR, CH2_L2,
CH2_L3, CCPA, etc) as well as representation learning models (i.e., GCN, GAE,
and GraphSAGE)

Table 4. Ranking of link prediction models across various networks. $L3,L2$ and $GS$ stands for $CH2\\_L3,CH2\\_L3$ and $graphSAGE$ respectively. Networks | CAR | L3 | L2 | CCPA | ECC | DW | N2V | GCN | GS | GAE
---|---|---|---|---|---|---|---|---|---|---
ENZYMES_g296 | 7 | 4 | 8 | 6 | 10 | 5 | 9 | 2 | 1 | 3
bn-mouse_visual-cortex_2 | 5 | 3 | 7 | 10 | 4 | 6 | 9 | 1 | 2 | 8
bn-macaque-rhesus_brain_1 | 4 | 3 | 1 | 2 | 8 | 7 | 5 | 9 | 10 | 6
bio-yeast-protein-inter | 9 | 3 | 7 | 8 | 5 | 4 | 10 | 6 | 1 | 2
bio-grid-mouse | 9 | 1 | 10 | 4 | 6 | 3 | 8 | 7 | 5 | 2
bio-celegans-dir | 6 | 3 | 1 | 2 | 8 | 7 | 4 | 10 | 9 | 5
Se-DoDecagon_sidefx | 6 | 5 | 7 | 8 | 4 | 3 | 10 | 2 | 1 | 9

Next, we scrutinize the impact of topological properties, as outlined in Table
3, on network performance accuracy. To achieve this, we compute the Pearson
correlation coefficient between the Area Under the Curve (AUC) scores across
all biological network datasets and their corresponding values for a given
topological property. A high or low correlation signifies the potential of the
associated topological property to assist link prediction models in
identifying patterns.

(a)

(b)

Figure 10. Comparison of the performance accuracy of the LP models: (a)
Kendall Tau correlation heatmap with p-value significance. cells are colored
orange if their p-value is greater than 0.05, otherwise, it is colored light
green; (b) Pearson correlation coefficient between the AUC and values for a
given topological property across all the biological network datasets.

The analysis result (see Fig. 10b) consistently reveals a robust correlation,
denoted in bold blue, for network transitivity (measured as the fraction of
open triads that form triangles). This finding suggests that high transitivity
corresponds to the existence of tightly interconnected communities or cliques.
This structural coherence facilitates the identification of recurring patterns
and relationships, enhancing the ability of link prediction models to discern
and predict missing links. Conversely, network modularity, denoted in bold
magenta, exhibits an inverse correlation with high AUC scores, especially for
similarity and path-based link prediction models. This is attributed to
networks with low modularity, characterized by homogeneous communities where
nodes share similar connectivity patterns. In such cases, local and random-
walk-based link prediction models excel, leveraging the uniformity of local
structural information to predict links effectively.

####  5.3.2. Strengths and Weaknesses

As discussed in Section 5.3.1, the exploration of a broader neighborhood has
the advantage of effectively incorporating global patterns into our models.
Notably, conventional models like CAR and CH2-L2 tend to exclusively consider
one-hop neighborhoods, leading to considerably faster execution times but
lacking the knowledge of global network information. In contrast, CH2-L3
presently explores multi-hop paths, which necessitates a more substantial
computational effort. Similarly, models based on random walks can achieve
accurate predictions through meticulous training but at the cost of increased
computational overheads. Our analysis demonstrates that a random walk-based
model, specifically DeepWalk and Node2Vec, trained using 100 random walks of
length 100 starting at each node, attains a comparable performance accuracy.
Lastly, when it comes to graph neural network (GNN)–based Link Prediction (LP)
models, their success is contingent on the accuracy of the ground truth
labels. In our analysis, we employed the Louvain community detection algorithm
(de2011generalized, ) to assign cluster IDs to nodes. It is worth noting that
the Louvain-based cluster labels may not always represent the optimal labeling
for the nodes, which accounts for the below-par performance of the GNN-based
models on some biological datasets.

(a) AUC performance of DPPIN-Babu network.

(b) Time consumption in seconds.

(c) AUC performance of DPPIN-Breitkreutz network.

(d) Time consumption in seconds.

(e) AUC performance of DPPIN-Yu network.

(f) Time consumption in seconds.

Figure 11. Performance evaluation and time consumption of the four different
models (CT, WCT, Jaccard, and NMF) implemented on three dynamic networks of
PPIN (Babu, Breitkreutz, and Yu). Several models have very close performance.
We reported three different performances of WCT with
$\theta\in\\{0.1,0.2,0.5\\}$.

###  5.4. Performance Evaluation of the temporal models

Analyzing the performance of link prediction models across the DPPIN-Babu,
DPPIN-Breitkreutz, and DPPIN-Yu temporal networks reveals distinct trends (see
Figs. 11a, 11c, 11e). The Collapsed Tensor (CT) model demonstrates a steady
performance, indicating consistent predictive capability over time. Weighted
Collapsed Tensor (WCT) models exhibit increased AUC with higher weights,
particularly notable in the DPPIN-Babu network, suggesting a stronger
alignment with the network’s temporal dynamics. In contrast, the Jaccard and
Non-negative Matrix Factorization (NMF) models consistently show lower AUC
scores across all networks, implying limited effectiveness in temporal link
prediction. Overall, WCT models emerge as the most effective, balancing
robustness and adaptability to temporal changes. We note that different
weights show no impact on the metric.

The time analysis of link prediction models (see Figs. 11b, 11d, 11f) on
temporal networks indicates that the Collapsed Tensor (CT) method maintains
consistent and low computational time across all networks, highlighting its
efficiency. The Jaccard and Non-negative Matrix Factorization (NMF) methods
exhibit sporadic spikes in computational time, suggesting variability in
processing depending on the network’s state at different time points. Overall,
the CT method stands out for its temporal efficiency in link prediction tasks
across the examined networks.

Table 5. Biological and medical databases and datasets used in the literature
and the experiments conducted in this research.

Publication |  Database / Dataset |  Link |  Description
---|---|---|---
Knox et al. (knox2010drugbank, ), 2011 |  DrugBank |  https://go.drugbank.com/ |  An extensive data on drugs and drug targets, including their chemistry, action, pharmacology, and the diseases, proteins, genes, and organisms they affect. It offers in-depth information on drug pathways, pharmacogenomics, adverse reactions, and more.
Kuhn et al. (kuhn2010side, ), 2010 |  SIDER |  http://sideeffects.embl.de/ |  A comprehensive, computer-readable resource that connects 888 drugs to 1450 distinct side effect terms. The SIDER dataset encompasses 62,269 drug-side effect pairs, with about 70% of the drugs listed having between 10 and 100 different side effects. This dataset highlights the distribution of side effects across different drugs.
Prasad et al. (keshava2009human, ), 2010 |  HPRD |  http://www.hprd.org/ |  A database about human proteome, including PPI, post-translational modifications, protein subcellular localization, and more.
He, Y. et al. (he2018link, ), 2018 |  EEG of epilepsy patients |  https://epilepsy.uni-freiburg.de/ |  A dataset developed from extensive EEG recordings of 8 patients with different types of pharmocoresistant focal epilepsy, capturing intricate details of seizure activities and neural firings. These recordings were processed into weighted networks using phase locking values (PLV) derived from subband EEG oscillations, providing a comprehensive framework for analyzing the initiation, progression, and termination of seizures in the brain.
Prieto et al. (prieto2022disnet, ), 2022 |  DISNET |  https://disnet.ctb.upm.es |  An extensive collection of biomedical data aimed at facilitating drug repurposing and disease understanding through the creation and analysis of complex networks. It integrates heterogeneous biomedical information(e.i. symptoms, signs, and other medical data) to construct customizable disease networks.
Hindorff, L. et al. (hindorff2009catalog, ), 2012 |  GWAS catalog |  http://www.genome.gov/gwastudies |  A centralized database of various genome-wide association studies, aimed to identify the association between genetic variations and traits or diseases.
Havugimana et al. (havugimana2012census, ), 2012 |  hsaPPI |  |  Human PPI network created by merging biochemical fractionation data with spectrometric profiling and computational filtering.
Giurgiu et al. (giurgiu2019corum, ), 2009 |  Corum |  http://mips.helmholtz-muenchen.de/corum/ |  A collection of experimentally verified mammalian protein complexes and their interactions.
Lee et al. (lee2011prioritizing, ), 2011 |  HumanNet |  |  A comprehensive network that connects human genes on a genome-wide scale, combined from 21 extensive genomics and proteomics datasets, with the weight assigned indicating the strength of the evidence supporting each interaction’s identification.
Franceschini et al. (franceschini2012string, ), 2012 |  String |  http://string-db.org/ |  The physical and functional interactions of genes/proteins from diverse sources and organisms. Edges are weighted with a probabilistic confidence score.
Schmitt et al. (schmitt2014funcoup, ), 2014 |  FunCoup |  http://funcoup.sbc.su.se/ |  The interaction network of genes and proteins of diverse sources using Bayesian approaches.
Linghu et al. (linghu2009genome, ), 2009 |  FLN |  |  A comprehensive interaction of genes (from 6 organisms) and their links association with a common biological process.
Huntley et al. (huntley2015goa, ), 2015 |  GO |  http://www.ebi.ac.uk/GOA |  A comprehensive resource that provides standardized and structured information about the functions, processes, and cellular locations of genes and gene products. It shows the biological roles of genes and how they contribute to various cellular processes and functions. An example link between a pair of genes can be weighted based on the number of GO terms in common.
Kuhn, M. et al. (kuhn2012stitch, ), 2012 |  STITCH3 |  http://stitch.embl.de/ |  An interaction networks of proteins and chemicals extracted from a diverse set of experiments, various databases, and literature, integrating multiple sources of experimental and manually curated data. The database encompasses over 300,000 chemicals and 2.6 million proteins from 1133 different organisms, providing a broad scope of interaction information.
Gündoğan, E. and Kaya, B. (gundougan2017link, ) |  Drugs |  https://www.drugs.com/medical_conditions.html |  Drugs.com offers detailed information on a wide range of diseases and conditions. It provides comprehensive insights, including symptoms, diagnosis, and treatment options for each listed condition.
Piñero, J. et al. (pinero2016disgenet, ), 2016 |  DisGeNET |  http://www.disgenet.org/ |  An extensive collection of gene-disease associations (GDAs). As of its version 5.0, DisGeNET contains 561,119 GDAs, linking 17,074 genes to 20,370 diseases, disorders, traits, and clinical or abnormal human phenotypes. Moreover, DisGeNET also includes specific data collections such as the COVID-19 data set in version 5, which contains 1843 genes, 4018 diseases, 211 variants, and phenotypes, derived from over 49,410 publications.
Y. Li et al. (li2014hmdd, ), 2014 |  HMDD |  http://cmbi.bjmu.edu.cn/hmdd |  A comprehensive collection of experimentally supported associations between human microRNA (miRNAs) and various diseases.
T. Cui et al. (cui2018mndr, ), 2018 |  MNDR |  www.rna-society.org/mndr/ |  A network of association between long non-coding RNAs (lncRNA) and different diseases. Edges are scored based on the quality and quantity of reference studies.
Jiang, Q et al. (jiang2015lncrna2target, ), 2015 |  LncRNA2Target |  http://www.lncrna2target.org/ |  This database covers both human and mouse lncRNAs. As of version 2.0, LncRNA2Target included 152,137 lncRNA–target associations, which were compiled from 1,047 papers and 224 datasets.

Table 6. Additional biological and medical databases and datasets used in the
literature and the experiments conducted in this research.

Publication |  Database / Dataset |  Link |  Description
---|---|---|---
Chen, G et al. (chen2012lncrnadisease, ), 2012. |  LncRNADisease |  http://cmbi.bjmu.edu.cn/lncrnadisease |  An extensive compilation of associations between lncRNAs (including circular RNAs) and various diseases, enriched by a substantial addition of 25,440 new lncRNA-disease associations and curated from a wide range of literature sources. This advanced iteration enhances its utility with features like transcriptional regulatory relationships among lncRNA, mRNA, and miRNA, confidence scores for associations, and detailed curation of lncRNA interactions at multiple molecular levels, solidifying its role as a critical tool for research into the intricate roles of lncRNAs in disease.
Miao, Y. et al. (miao2018lncrnasnp2, ), 2018 |  lncRNASNP2 |  http://bioinfo.life.hust.edu.cn/lncRNASNP2 |  An extensive information on functional single nucleotide polymorphisms (SNPs) and mutations in human and mouse long non-coding RNAs (lncRNAs). This database offers a detailed repository of SNPs in lncRNAs, their effects on lncRNA structure, and the expression of quantitative trait loci (eQTLs) of lncRNAs, making it a valuable tool for understanding how these genetic variations affect lncRNA function and regulation.
Rossi, RA and Ahmed, NK,(nr, ), |  NetworkRepository |  https://networkrepository.com/ |  An interactive data repository with a web-based platform for visual interactive analytics. It provides an extensive collection of diverse networks. 1) ENZYMES_g296: This is a network of cheminformatics., 2) bn-mouse_visual-cortex_2: This is a brain network. 3) bn-macaque-rhesus_brain_1: A connectome (or neural connections) existed in the brain of rhesus macaque monkeys. 4) bio-yeast-protein-inter: The network of protein-protein interaction in yeast. 5) bio-grid-mouse. 6) bio-celegans-dir.
Kibbe, WA. et al. (kibbe2015disease, ), |  Se-DoDecagon _sidefx |  https://snap.stanford.edu, (zitnik2018modeling, ) |  This dataset organizes drug side-effects into various categories, each corresponding to different classes of diseases. The side effects are essentially additional ailments that arise alongside a patient’s main medical condition, for which the medication is intended. Classification of these side effects is based on their origin and the bodily systems they impact, aligning them with respective disease classes. The data regarding these disease classes is derived from the Disease Ontology.
|  PDN |  https://www3.nd.edu/~dial/data/diseasenetworks/ |  A Phenotypic Disease Network (PDN) is built using actual patient data, where diseases are represented as nodes and the edges reflect the co-occurrence or co-morbidity of these diseases.
Fu, D. and He, J. (fu2022dppin, ), |  PPIN |  https://github.com/DongqiFu/DPPIN/tree/main |  A collection of twelve individual dynamic network datasets, each representing dynamic protein-protein interactions within yeast cells, but at different scales.

##  6\. Challenges and Future Directions

We studied the link prediction approaches applied to complex networks of
myriad biological entities (enumerated in Tables. 5 and 6). In this section,
we enumerate the key considerations in the application of future LP models to
network biology.

###  6.1. Missing Information, Bias and Noise

A major challenge in the application of link prediction on biological networks
stems from the incompleteness of information. Several interactions within the
existing protein-protein interaction networks and gene regulatory networks are
unknown (guo2022challenges, ). Many would argue that it is the very task of
link prediction algorithms to infer these missing associations. However, link
prediction solutions employ semi-supervised learning, where known interactions
are used to train the models before reporting unknown associations
(muzio2021biological, ). Thus, the missing associations are likely to create
bias in the networks and have an adverse effect on the subsequent predictions.
The fact that the networks are not complete precludes us from deriving
inferences from their known topological properties. For instance, the
knowledge that signaling, transcriptional, and protein networks are scale-free
(barabasi2004network, ; albert2005scale, ) does not warrant that the sampled
subnetworks are scale-free as well (heath2009computational, ).

In the course of this survey, we have presented link prediction approaches
that leverage machine learning to learn low-dimensional vector representations
based on network relationships. Once the embeddings are created, the networks
lend themselves to the application of traditional supervised machine learning
methods, such as Support Vector Machines and decision trees, etc.
(su2020network, ). The similarity between the vectors is often used as a
measure of link likelihood between two biological entities. However, there are
innate assumptions in the embedding models (guo2022challenges, ). If, for
instance, the models are based on transitivity and semantic matching, it may
be difficult for them to capture symmetry and inversions. Along the same
lines, the embedding strategy needs to be relevant in the context of a
biological question. If nodes are embedded based on local network topology,
then the prediction cannot be expected to capture global features. Biological
information, such as the structure of proteins and protein complexes, the
layout of signaling pathways, or the higher-order organization of organelles,
etc. are likely to be lost (ideker2017network, ). Moreover, the noise and
sparseness in the biomedical datasets diminish the predictive capabilities of
the embedding approaches.

###  6.2. Interpretability

A significant challenge in link prediction on biomedical data is the
prediction of the interpretation of the association between a pair of
entities. In other words, let us assume that a drug and a gene are deemed to
be associated; what does this association indicate from a biological
standpoint? The drug can act as a modulator, blocker, antagonist, activator,
etc. Existing embedding techniques do not often fail to provide biological
context to the predicted associations(guo2022challenges, ). To be of utility
to biologists and clinicians, the network construction phase should emphasize
incorporating domain knowledge and the link prediction metrics should be able
to accurately predict the nature of the association between entities
(zhou2021progresses, ). Once again, accurate link prediction rests on
overcoming computational challenges in network structure learning. For
instance, standard approaches like Bayesian inference become intractable as
the number of variables increases (zhang2014network, ).

###  6.3. Network Motifs

In the future, biological and biomedical networks are going to become more
heterogeneous, aggregating data from multiple sources with biological nuances,
such as cell-type specificity, spatial and temporal resolution, or
environmental factors (guo2022challenges, ). The resultant networks are
topologically complex, characterized by weights, link directionality, multiple
layers, etc., making it difficult to assimilate information. Future prediction
models will need to adapt LP approaches applied to other domain networks in
the realm of biological and biomedical networks to cope with temporal
dynamics, such as activation and perturbation, as well as scalability
challenges in large-scale biological systems. Since local metrics relying on
triangle closing or triadic closure, path counting, and graph kernels may be
insufficient to tackle this complexity, the community may be likely to explore
deep machine learning-based dynamic embedding techniques (koutrouli2020guide,
) as well as higher-order analysis that takes into account network
substructures (or motifs) (roy2020motifs, ). There have been a few efforts to
predict links based on the motif participation of nodes (abuoda2020link, ) or
the presence or absence of motifs (roy2023inferring, ). A recent embedding
algorithm combines motifs with deep learning approaches to predict
associations (wang2020model, ). Finally, others have combined network
reconstruction to meet link prediction goals (wang2017kernel, ;
wu2019enhancing, ).

###  6.4. Heterogeneity in Knowledge Graphs

As discussed in Sec. 6.3, biological systems are an amalgamation of diverse
interactions including molecular interactions, gene functions, disease
associations, etc. Knowledge graphs are emerging as an effective tool for
researchers to access a holistic view of the biological landscape,
facilitating data-driven insights, visualization, and hypothesis generation
(mohamed2021biological, ). The application of knowledge graphs ranges from
literature mining and biological pathways analysis to personalized medicine.
Future LP techniques need to overcome the following intrinsic challenges of
biological and biomedical knowledge graphs to make accurate predictions: (a)
Imbalanced data. A biomedical knowledge graph may possess some common and some
rare associations. This class imbalance is likely to lead to biased
predictions, (b) Semantic heterogeneity. Biological entities are often
described using diverse ontologies and terminologies. Thus, link prediction
models must handle the semantic heterogeneity by mapping or aligning different
entity types and relationships, and (c) Incorporating multi-omics data.
Knowledge graphs include multi-omics data, such as genomics, proteomics, and
metabolomics. LP models must assimilate data from these diverse sources to
make biologically relevant predictions.

##  7\. Conclusion

In this review, we explored the applications of link prediction (LP)
methodologies within biological and biomedical networks comprising diseases,
genes, proteins, RNA, microbiomes, drugs, and neurons. These LP approaches
surveyed in this study fall under local, centrality, and embedding-based
categories, each with its strengths and limitations. We conducted a meticulous
performance evaluation of the most widely used LP methods, leveraging
biological network datasets to provide insights into their efficacy and
applicability. Finally, we highlighted the challenges such as noise, bias,
data sparseness, and interpretability intrinsic to biological systems and how
resolving them remains a crucial undertaking for future LP models in inferring
biologically relevant interactions.

## Acknowledgment

This work was partially supported by 5R21MH128562-02 (PI: Roberson-Nay),
5R21AA029492-02 (PI: Roberson-Nay), CHRB-2360623 (PI: Das), NSF-2316003 (PI:
Cano), VCU Quest (PI: Das) and VCU Breakthroughs (PI: Ghosh) funds awarded to
P.G.

## References

  * [1] Georgios A Pavlopoulos, Maria Secrier, Charalampos N Moschopoulos, Theodoros G Soldatos, Sophia Kossida, Jan Aerts, Reinhard Schneider, and Pantelis G Bagos.  Using graph theory to analyze biological networks.  BioData mining, 4(1):1–27, 2011.
  * [2] B. Berger, R. Singht, and J. Xu.  Graph algorithms for biological systems analysis.  In Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, pages 142–151, 2008.
  * [3] A. Barabasi and Z. Oltvai.  Network biology: understanding the cell’s functional organization.  Nature reviews genetics, 5(2):101–113, 2004.
  * [4] Debmalya Barh, Vijender Chaitankar, Eugenia Ch Yiannakopoulou, Emmanuel O. Salawu, Sudhir Chowbina, Preetam Ghosh, and Vasco Azevedo.  Chapter 21 - in silico models: From simple networks to complex diseases.  In Ashish S. Verma and Anchal Singh, editors, Animal Biotechnology, pages 385–404. Academic Press, San Diego, 2014.
  * [5] L. Lü and T. Zhou.  Link prediction in complex networks: A survey.  Physica A: statistical mechanics and its applications, 390(6):1150–1170, 2011.
  * [6] Z. Su, X. Zheng, J. Ai, Y. Shen, and X. Zhang.  Link prediction in recommender systems based on vector similarity.  Physica A: Statistical Mechanics and its Applications, 560:125154, 2020.
  * [7] A. Breit, S. Ott, A. Agibetov, and M. Samwald.  Openbiolink: a benchmarking framework for large-scale biomedical link prediction.  Bioinformatics, 36(13):4097–4098, 2020.
  * [8] J. Nalluri, D. Barh, V. Azevedo, and P. Ghosh.  mirsig: a consensus-based network inference methodology to identify pan-cancer mirna-mirna interaction signatures.  Scientific Reports, 7(39684):1–14, 2017.
  * [9] V. Chaitankar, P. Ghosh, E. Perkins, P. Gong, Y. Deng, and C. Zhang.  A novel gene network inference algorithm using predictive minimum description length approach.  BMC Systems Biology, 4(Suppl 1: S7), 2010.
  * [10] V. Chaitankar, P. Ghosh, E. Perkins, P. Gong, and C. Zhang.  Time lagged information-theoretic approaches to the reverse engineering of gene regulatory networks.  BMC Bioinformatics, 11(Suppl 6: S19), 2010.
  * [11] A. Divakaran and A. Mohan.  Temporal link prediction: A survey.  New Generation Computing, 38:213–258, 2020.
  * [12] D. West et al.  Introduction to graph theory, volume 2.  Prentice hall Upper Saddle River, 2001.
  * [13] Francois Lorrain and Harrison C White.  Structural equivalence of individuals in social networks.  The Journal of mathematical sociology, 1(1):49–80, 1971.
  * [14] Gerard Salton and Michael J McGill.  Introduction to modern information retrieval.  mcgraw-hill, 1983.
  * [15] Paul Jaccard.  Étude comparative de la distribution florale dans une portion des alpes et des jura.  Bull Soc Vaudoise Sci Nat, 37:547–579, 1901.
  * [16] Thorvald A Sorensen.  A method of establishing groups of equal amplitude in plant sociology based on similarity of species content and its application to analyses of the vegetation on danish commons.  Biol. Skar., 5:1–34, 1948.
  * [17] Erzsébet Ravasz, Anna Lisa Somera, Dale A Mongru, Zoltán N Oltvai, and A-L Barabási.  Hierarchical organization of modularity in metabolic networks.  science, 297(5586):1551–1555, 2002.
  * [18] Tao Zhou, Linyuan Lü, and Yi-Cheng Zhang.  Predicting missing links via local information.  The European Physical Journal B, 71(4):623–630, 2009.
  * [19] Elizabeth A Leicht, Petter Holme, and Mark EJ Newman.  Vertex similarity in networks.  Physical Review E, 73(2):026120, 2006.
  * [20] Albert-László Barabási and Réka Albert.  Emergence of scaling in random networks.  science, 286(5439):509–512, 1999.
  * [21] Lada A Adamic and Eytan Adar.  Friends and neighbors on the web.  Social networks, 25(3):211–230, 2003.
  * [22] Carlo Vittorio Cannistraci, Gregorio Alanis-Lobato, and Timothy Ravasi.  From link-prediction in brain connectomes and protein interactomes to the local-community-paradigm in complex networks.  Scientific reports, 3(1):1–14, 2013.
  * [23] Amir Ghasemian, Homa Hosseinmardi, Aram Galstyan, Edoardo M Airoldi, and Aaron Clauset.  Stacking models for nearly optimal link prediction in complex networks.  Proceedings of the National Academy of Sciences, 117(38):23393–23400, 2020.
  * [24] Simone Daminelli, Josephine Maria Thomas, Claudio Durán, and Carlo Vittorio Cannistraci.  Common neighbours and the local-community-paradigm for topological link prediction in bipartite networks.  New Journal of Physics, 17(11):113037, 2015.
  * [25] Fei Tan, Yongxiang Xia, and Boyao Zhu.  Link prediction in complex networks: a mutual information perspective.  PloS one, 9(9):e107056, 2014.
  * [26] Alessandro Muscoloni, Ilyes Abdelhamid, and Carlo Vittorio Cannistraci.  Local-community network automata modelling based on length-three-paths for prediction of complex network structures in protein interactomes, food webs and more.  bioRxiv, page 346916, 2018.
  * [27] Tao Zhou, Yan-Li Lee, and Guannan Wang.  Experimental analyses on 2-hop-based and 3-hop-based link prediction algorithms.  Physica A: Statistical Mechanics and Its Applications, 564:125532, 2021.
  * [28] Mark EJ Newman.  Modularity and community structure in networks.  Proceedings of the national academy of sciences, 103(23):8577–8582, 2006.
  * [29] Alex Bavelas.  Communication patterns in task-oriented groups.  The Journal of the Acoustical Society of America, 22(6):725–730, 1950.
  * [30] Ulrik Brandes.  A faster algorithm for betweenness centrality.  Journal of mathematical sociology, 25(2):163–177, 2001.
  * [31] Leo Katz.  A new status index derived from sociometric analysis.  Psychometrika, 18(1):39–43, 1953.
  * [32] Phillip Bonacich.  Power and centrality: A family of measures.  American journal of sociology, 92(5):1170–1182, 1987.
  * [33] Lawrence Page, Sergey Brin, Rajeev Motwani, and Terry Winograd.  The pagerank citation ranking: Bringing order to the web.  Technical report, Stanford InfoLab, 1999.
  * [34] Jon M Kleinberg.  Authoritative sources in a hyperlinked environment.  Journal of the ACM (JACM), 46(5):604–632, 1999.
  * [35] J. Luo and Y. Qi.  Identification of essential proteins based on a new combination of local interaction density and protein complexes.  PloS one, 10(6):e0131418, 2015.
  * [36] F. Riquelme, P. Gonzalez-Cantergiani, X. Molinero, and M. Serna.  The neighborhood role in the linear threshold rank on social networks.  Physica A: Statistical Mechanics and its Applications, 528:121430, 2019.
  * [37] D. Mistry, R. Wise, and J. Dickerson.  Diffslc: A graph centrality method to detect essential proteins of a protein-protein interaction network.  PloS one, 12(11):e0187091, 2017.
  * [38] I. Ahmad, M. Akhtar, S. Noor, and A. Shahnaz.  Missing link prediction using common neighbor and centrality based parameterized algorithm.  Scientific reports, 10(1):364, 2020.
  * [39] Yu-Xiong Wang and Yu-Jin Zhang.  Nonnegative matrix factorization: A comprehensive review.  IEEE Transactions on knowledge and data engineering, 25(6):1336–1353, 2012.
  * [40] Deng Cai, Xiaofei He, Jiawei Han, and Thomas S Huang.  Graph regularized nonnegative matrix factorization for data representation.  IEEE transactions on pattern analysis and machine intelligence, 33(8):1548–1560, 2010.
  * [41] Junyao Zhang, Xiaogang Liu, and Xiaoke Ma.  Temporal link prediction for cancer networks using structural consistency regularized non-negative matrix factorization.  In 2021 IEEE International Conference on Bioinformatics and Biomedicine (BIBM), pages 280–283. IEEE, 2021.
  * [42] Bolun Chen, Fenfen Li, Senbo Chen, Ronglin Hu, and Ling Chen.  Link prediction based on non-negative matrix factorization.  PloS one, 12(8):e0182968, 2017.
  * [43] Andrea Franceschini, Jianyi Lin, Christian von Mering, and Lars Juhl Jensen.  Svd-phy: improved prediction of protein functional associations through singular value decomposition of phylogenetic profiles.  Bioinformatics, 32(7):1085–1087, 2016.
  * [44] Rasmus Bro and Age K Smilde.  Principal component analysis.  Analytical methods, 6(9):2812–2831, 2014.
  * [45] Ke-Lin Du and Madisetti NS Swamy.  Neural networks and statistical learning.  Springer Science & Business Media, 2013.
  * [46] Tomas Mikolov, Kai Chen, Greg Corrado, and Jeffrey Dean.  Efficient estimation of word representations in vector space.  arXiv preprint arXiv:1301.3781, 2013.
  * [47] Bryan Perozzi, Rami Al-Rfou, and Steven Skiena.  Deepwalk: Online learning of social representations.  In Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 701–710, 2014.
  * [48] T. Pimentel et al.  Efficient estimation of node representations in large graphs using linear contexts.  In 2019 International joint conference on neural networks (IJCNN), pages 1–8. IEEE, 2019.
  * [49] Aditya Grover and Jure Leskovec.  node2vec: Scalable feature learning for networks.  In Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining, pages 855–864, 2016.
  * [50] Leonardo FR Ribeiro, Pedro HP Saverese, and Daniel R Figueiredo.  struc2vec: Learning node representations from structural identity.  In Proceedings of the 23rd ACM SIGKDD international conference on knowledge discovery and data mining, pages 385–394, 2017.
  * [51] Thomas N Kipf and Max Welling.  Semi-supervised classification with graph convolutional networks.  arXiv preprint arXiv:1609.02907, 2016.
  * [52] Will Hamilton, Zhitao Ying, and Jure Leskovec.  Inductive representation learning on large graphs.  Advances in neural information processing systems, 30, 2017.
  * [53] Thomas N Kipf and Max Welling.  Variational graph auto-encoders.  arXiv preprint arXiv:1611.07308, 2016.
  * [54] David Liben-Nowell and Jon Kleinberg.  The link prediction problem for social networks.  In Proceedings of the twelfth International Conference on Information and Knowledge Management, pages 556–559, 2003.
  * [55] Umang Sharan and Jennifer Neville.  Temporal-relational classifiers for prediction in evolving domains.  In 2008 Eighth IEEE International Conference on Data Mining, pages 540–549. IEEE, 2008.
  * [56] G. Alanis-Lobato, C. Cannistraci, and T. Ravasi.  Exploring the genetics underlying autoimmune diseases with network analysis and link prediction.  In 2nd Middle East Conference on Biomedical Engineering, pages 167–170. IEEE, 2014.
  * [57] L. Hindorff.  A catalog of published genome-wide association studies.  http://www. genome. gov/26525384, 2009.
  * [58] O. Allali, C. Magnien, and M. Latapy.  Link prediction in bipartite graphs using internal links and weighted projection.  In 2011 IEEE conference on computer communications workshops (INFOCOM WKSHPS), pages 936–941. IEEE, 2011.
  * [59] J. Yang, T. Yang, D. Wu, L. Lin, F. Yang, and J. Zhao.  The integration of weighted human gene association networks based on link prediction.  BMC systems biology, 11:1–17, 2017.
  * [60] Purushottam Kumar and Dolly Sharma.  A novel similarity measure for the link prediction in unipartite and bipartite networks.  Social Network Analysis and Mining, 11(1):1–14, 2021.
  * [61] Vincent D Blondel, Jean-Loup Guillaume, Renaud Lambiotte, and Etienne Lefebvre.  Fast unfolding of communities in large networks.  Journal of statistical mechanics: theory and experiment, 2008(10):P10008, 2008.
  * [62] D. Szklarczyk et al.  String v10: protein–protein interaction networks, integrated over the tree of life.  Nucleic acids research, 43(D1):D447–D452, 2015.
  * [63] Chuanze Kang, Han Zhang, Zhuo Liu, Shenwei Huang, and Yanbin Yin.  LR-GNN: a graph neural network based on link representation for predicting molecular associations.  Briefings in Bioinformatics, 23(1):bbab513, 2022.
  * [64] Chengshuai Zhao, Shuai Liu, Feng Huang, Shichao Liu, and Wen Zhang.  CSGNN: Contrastive self-supervised graph neural network for molecular interaction prediction.  In IJCAI, pages 3756–3763, 2021.
  * [65] A. Finotti, E. Fabbri, I. Lampronti, J. Gasparello, M. Borgatti, and R. Gambari.  Micrornas and long non-coding rnas in genetic diseases.  Molecular Diagnosis & Therapy, 23(2):155–171, 2019.
  * [66] Wen Zhang, Zhishuai Li, Wenzheng Guo, Weitai Yang, and Feng Huang.  A fast linear neighborhood similarity-based network link inference method to predict microrna-disease associations.  IEEE/ACM transactions on computational biology and bioinformatics, 18(2):405–415, 2019.
  * [67] Ana BOV Silva and Eduardo Jaques Spinosa.  Graph convolutional auto-encoders for predicting novel lncRNA-disease associations.  IEEE/ACM Transactions on Computational Biology and Bioinformatics, 19(4):2264–2271, 2021.
  * [68] Zi-Ang Shen, Tao Luo, Yuan-Ke Zhou, Han Yu, and Pu-Feng Du.  NPI-GNN: Predicting ncRNA-protein interactions with deep graph neural networks.  Briefings in Bioinformatics, 22(5):bbab051, 2021.
  * [69] Zhengwei Li, Jiashu Li, Ru Nie, Zhu-Hong You, and Wenzheng Bao.  A graph auto-encoder model for miRNA-disease associations prediction.  Briefings in bioinformatics, 22(4), 2021.
  * [70] Chaminda Jayampath Seneviratne, Preethi Balan, Tanujaa Suriyanarayanan, Meiyappan Lakshmanan, Dong-Yup Lee, Mina Rho, Nicholas Jakubovics, Bernd Brandt, Wim Crielaard, and Egija Zaura.  Oral microbiome-systemic link studies: perspectives on current limitations and future artificial intelligence-based approaches.  Critical reviews in microbiology, 46(3):288–299, 2020.
  * [71] Peter E Larsen and Yang Dai.  Metabolome of human gut microbiome is predictive of host dysbiosis.  Gigascience, 4(1):s13742–015, 2015.
  * [72] Cecilie Dahl, Maggie Stanislawski, Nina Iszatt, Siddhartha Mandal, Catherine Lozupone, Jose C Clemente, Rob Knight, Hein Stigum, and Merete Eggesbø.  Gut microbiome of mothers delivering prematurely shows reduced diversity and lower relative abundance of bifidobacterium and streptococcus.  PLoS One, 12(10):e0184336, 2017.
  * [73] Derek Reiman, Ahmed A Metwally, Jun Sun, and Yang Dai.  Popphy-cnn: a phylogenetic tree embedded architecture for convolutional neural networks to predict host phenotype from metagenomic data.  IEEE journal of biomedical and health informatics, 24(10):2993–3001, 2020.
  * [74] Ahmed A Metwally, Philip S Yu, Derek Reiman, Yang Dai, Patricia W Finn, and David L Perkins.  Utilizing longitudinal microbiome taxonomic profiles to predict food allergy via long short-term memory networks.  PLoS computational biology, 15(2):e1006693, 2019.
  * [75] C. Fu et al.  An integrated knowledge graph for microbe-disease associations.  In Health Information Science: 9th International Conference, HIS 2020, Amsterdam, The Netherlands, October 20–23, 2020, Proceedings 9, pages 79–90. Springer, 2020.
  * [76] Yifu Luo, Qijun Liu, Wenjian Wu, Fei Li, and Xiaochen Bo.  Predicting drug side effects based on link prediction in bipartite network.  In 2014 7th International Conference on Biomedical Engineering and Informatics, pages 729–733. IEEE, 2014.
  * [77] M. Kuhn, M. Campillos, I. Letunic, L. Jensen, and P. Bork.  A side effect resource to capture phenotypic effects of drugs.  Molecular systems biology, 6(1):343, 2010.
  * [78] E. Gündoğan and B. Kaya.  A link prediction approach for drug recommendation in disease-drug bipartite network.  In 2017 International Artificial Intelligence and Data Processing Symposium (IDAP), pages 1–4. IEEE, 2017.
  * [79] Drugs. com.  Drugs. com.  2006\.
  * [80] Markus Griesser, Thomas Hoffmann, Mari Luz Bellido, Carlo Rosati, Barbara Fink, Robert Kurtzer, Asaph Aharoni, Juan Munoz-Blanco, and Wilfried Schwab.  Redirection of flavonoid biosynthesis through the down-regulation of an anthocyanidin glucosyltransferase in ripening strawberry fruit.  Plant Physiology, 146(4):1528–1539, 2008.
  * [81] Prieto S. and A. Rodríguez-González.  Disnet: Drug repositioning and disease understanding through complex networks creation and analysis.  In RExPO22 Conference. ScienceOpen Research, 2022.
  * [82] Xiaodan Wang, Jihong Wang, and Zixin Wang.  A drug-target interaction prediction based on gcn learning.  In 2021 IEEE 9th International Conference on Bioinformatics and Computational Biology (ICBCB), pages 42–47. IEEE, 2021.
  * [83] Maksim Koptelov, Albrecht Zimmermann, Bruno Crémilleux, and Lina F Soualmia.  Lpbycd: a new scalable and interpretable approach for link prediction via community detection in bipartite networks.  Applied Network Science, 6:1–39, 2021.
  * [84] Hanjing Jiang and Yabing Huang.  An effective drug-disease associations prediction model based on graphic representation learning over multi-biomolecular network.  BMC bioinformatics, 23:1–17, 2022.
  * [85] Y. He, F. Yang, Y. Yu, and C. Grebogi.  Link prediction investigation of dynamic information flow in epilepsy.  Journal of Healthcare Engineering, 2018, 2018.
  * [86] S. Sulaimany et al.  Predicting brain network changes in alzheimer’s disease with link prediction algorithms.  Molecular BioSystems, 13(4):725–735, 2017.
  * [87] P. De Meo, E. Ferrara, G. Fiumara, and A. Provetti.  Generalized louvain method for community detection in large networks.  In 2011 11th international conference on intelligent systems design and applications, pages 88–93. IEEE, 2011.
  * [88] Ryan A. Rossi and Nesreen K. Ahmed.  The network data repository with interactive graph analytics and visualization.  In AAAI, 2015.
  * [89] M. Zitnik, R. Sosič, S. Maheshwari, and J. Leskovec.  BioSNAP Datasets: Stanford biomedical network dataset collection.  http://snap.stanford.edu/biodata, August 2018.
  * [90] Dongqi Fu and Jingrui He.  Dppin: A biological repository of dynamic protein-protein interaction network data.  In 2022 IEEE International Conference on Big Data (Big Data), pages 5269–5277. IEEE, 2022.
  * [91] M. Mayo, A. Abdelzaher, and P. Ghosh.  Long-range degree correlations in complex networks.  Computational Social Networks, 2(4):1–13, 2015.
  * [92] Qimai Li, Zhichao Han, and Xiao-Ming Wu.  Deeper insights into graph convolutional networks for semi-supervised learning.  In Proceedings of the AAAI conference on artificial intelligence, volume 32, 2018.
  * [93] Craig Knox, Vivian Law, Timothy Jewison, Philip Liu, Son Ly, Alex Frolkis, Allison Pon, Kelly Banco, Christine Mak, Vanessa Neveu, et al.  Drugbank 3.0: a comprehensive resource for ‘omics’ research on drugs.  Nucleic acids research, 39(suppl_1):D1035–D1041, 2010.
  * [94] TS Keshava Prasad, Renu Goel, Kumaran Kandasamy, Shivakumar Keerthikumar, Sameer Kumar, Suresh Mathivanan, Deepthi Telikicherla, Rajesh Raju, Beema Shafreen, Abhilash Venugopal, et al.  Human protein reference database—2009 update.  Nucleic acids research, 37(suppl_1):D767–D772, 2009.
  * [95] Pierre C Havugimana, G Traver Hart, Tamás Nepusz, Haixuan Yang, Andrei L Turinsky, Zhihua Li, Peggy I Wang, Daniel R Boutz, Vincent Fong, Sadhna Phanse, et al.  A census of human soluble protein complexes.  Cell, 150(5):1068–1081, 2012.
  * [96] Madalina Giurgiu, Julian Reinhard, Barbara Brauner, Irmtraud Dunger-Kaltenbach, Gisela Fobo, Goar Frishman, Corinna Montrone, and Andreas Ruepp.  Corum: the comprehensive resource of mammalian protein complexes—2019.  Nucleic acids research, 47(D1):D559–D563, 2019.
  * [97] Insuk Lee, U Martin Blom, Peggy I Wang, Jung Eun Shim, and Edward M Marcotte.  Prioritizing candidate disease genes by network-based boosting of genome-wide association data.  Genome research, 21(7):1109–1121, 2011.
  * [98] Andrea Franceschini, Damian Szklarczyk, Sune Frankild, Michael Kuhn, Milan Simonovic, Alexander Roth, Jianyi Lin, Pablo Minguez, Peer Bork, Christian Von Mering, et al.  String v9. 1: protein-protein interaction networks, with increased coverage and integration.  Nucleic acids research, 41(D1):D808–D815, 2012.
  * [99] Thomas Schmitt, Christoph Ogris, and Erik LL Sonnhammer.  Funcoup 3.0: database of genome-wide functional coupling networks.  Nucleic acids research, 42(D1):D380–D388, 2014.
  * [100] Bolan Linghu, Evan S Snitkin, Zhenjun Hu, Yu Xia, and Charles DeLisi.  Genome-wide prioritization of disease genes and identification of disease-disease associations from an integrated human functional linkage network.  Genome biology, 10:1–17, 2009.
  * [101] Rachael P Huntley, Tony Sawford, Prudence Mutowo-Meullenet, Aleksandra Shypitsyna, Carlos Bonilla, Maria J Martin, and Claire O’Donovan.  The goa database: gene ontology annotation updates for 2015.  Nucleic acids research, 43(D1):D1057–D1063, 2015.
  * [102] Michael Kuhn, Damian Szklarczyk, Andrea Franceschini, Christian Von Mering, Lars Juhl Jensen, and Peer Bork.  Stitch 3: zooming in on protein–chemical interactions.  Nucleic acids research, 40(D1):D876–D880, 2012.
  * [103] Janet Piñero, Àlex Bravo, Núria Queralt-Rosinach, Alba Gutiérrez-Sacristán, Jordi Deu-Pons, Emilio Centeno, Javier García-García, Ferran Sanz, and Laura I Furlong.  Disgenet: a comprehensive platform integrating information on human disease-associated genes and variants.  Nucleic acids research, page gkw943, 2016.
  * [104] Yang Li, Chengxiang Qiu, Jian Tu, Bin Geng, Jichun Yang, Tianzi Jiang, and Qinghua Cui.  Hmdd v2. 0: a database for experimentally supported human microrna and disease associations.  Nucleic acids research, 42(D1):D1070–D1074, 2014.
  * [105] Tianyu Cui, Lin Zhang, Yan Huang, Ying Yi, Puwen Tan, Yue Zhao, Yongfei Hu, Liyan Xu, Enmin Li, and Dong Wang.  Mndr v2. 0: an updated resource of ncrna–disease associations in mammals.  Nucleic acids research, 46(D1):D371–D374, 2018.
  * [106] Qinghua Jiang, Jixuan Wang, Xiaoliang Wu, Rui Ma, Tianjiao Zhang, Shuilin Jin, Zhijie Han, Renjie Tan, Jiajie Peng, Guiyou Liu, et al.  Lncrna2target: a database for differentially expressed genes after lncrna knockdown or overexpression.  Nucleic acids research, 43(D1):D193–D196, 2015.
  * [107] Geng Chen, Ziyun Wang, Dongqing Wang, Chengxiang Qiu, Mingxi Liu, Xing Chen, Qipeng Zhang, Guiying Yan, and Qinghua Cui.  Lncrnadisease: a database for long-non-coding rna-associated diseases.  Nucleic acids research, 41(D1):D983–D986, 2012.
  * [108] Ya-Ru Miao, Wei Liu, Qiong Zhang, and An-Yuan Guo.  lncrnasnp2: an updated database of functional snps and mutations in human and mouse lncrnas.  Nucleic acids research, 46(D1):D276–D280, 2018.
  * [109] Warren A Kibbe, Cesar Arze, Victor Felix, Elvira Mitraka, Evan Bolton, Gang Fu, Christopher J Mungall, Janos X Binder, James Malone, Drashtti Vasant, et al.  Disease ontology 2015 update: an expanded and updated database of human diseases for linking biomedical knowledge through disease data.  Nucleic acids research, 43(D1):D1071–D1078, 2015.
  * [110] Marinka Zitnik, Monica Agrawal, and Jure Leskovec.  Modeling polypharmacy side effects with graph convolutional networks.  Bioinformatics, 34(13):i457–i466, 2018.
  * [111] M. Guo, D. Sosa, and R. Altman.  Challenges and opportunities in network-based solutions for biological questions.  Briefings in Bioinformatics, 23(1):bbab437, 2022.
  * [112] G. Muzio, L. O’Bray, and K. Borgwardt.  Biological network analysis with deep learning.  Briefings in bioinformatics, 22(2):1515–1530, 2021.
  * [113] R. Albert.  Scale-free networks in cell biology.  Journal of cell science, 118(21):4947–4957, 2005.
  * [114] A. Heath and L. Kavraki.  Computational challenges in systems biology.  Computer Science Review, 3(1):1–17, 2009.
  * [115] C. Su, J. Tong, Y. Zhu, P. Cui, and F. Wang.  Network embedding in biomedical data science.  Briefings in bioinformatics, 21(1):182–197, 2020.
  * [116] T. Ideker and R. Nussinov.  Network approaches and applications in biology, 2017.
  * [117] T. Zhou.  Progresses and challenges in link prediction.  Iscience, 24(11):103217, 2021.
  * [118] B. Zhang, Y. Tian, and Z. Zhang.  Network biology in medicine and beyond.  Circulation: Cardiovascular Genetics, 7(4):536–547, 2014.
  * [119] M. Koutrouli, E. Karatzas, D. Paez-Espino, and G. Pavlopoulos.  A guide to conquer the biological network era using graph theory.  Frontiers in bioengineering and biotechnology, page 34, 2020.
  * [120] S. Roy, P. Ghosh, D. Barua, and S. K. Das.  Motifs enable communication efficiency and fault-tolerance in transcriptional networks.  Scientific reports, 10(1):9628, 2020.
  * [121] G. AbuOda, G. De Francisci Morales, and A. Aboulnaga.  Link prediction via higher-order motif features.  In Machine Learning and Knowledge Discovery in Databases: European Conference, ECML PKDD 2019, Würzburg, Germany, September 16–20, 2019, Proceedings, Part I, pages 412–429. Springer, 2020.
  * [122] S. Roy, A. Al Musawi, and P. Ghosh.  Inferring links in directed complex networks through feed forward loop motifs.  Humanities and Social Sciences Communications, 10(1):1–13, 2023\.
  * [123] L. Wang, J. Ren, B. Xu, J. Li, W. Luo, and F. Xia.  Model: Motif-based deep feature learning for link prediction.  IEEE Transactions on Computational Social Systems, 7(2):503–516, 2020.
  * [124] W. Wang, Y. Feng, P. Jiao, and W. Yu.  Kernel framework based on non-negative matrix factorization for networks reconstruction and link prediction.  Knowledge-Based Systems, 137:104–114, 2017.
  * [125] M. Wu, S. Wu, Q. Zhang, C. Xue, H. Kan, and F. Shao.  Enhancing link prediction via network reconstruction.  Physica A: Statistical Mechanics and its Applications, 534:122346, 2019.
  * [126] S. Mohamed, A. Nounu, and V. Nováček.  Biological applications of knowledge graph embedding models.  Briefings in bioinformatics, 22(2):1679–1693, 2021.