<figure><img src="image_1.png" /></figure>

HAL
open science

# A Degree Centrality-Enhanced Computational Approach for Local Network Alignment Leveraging Knowledge Graph Embeddings

Warith Eddine Djeddi, Sadok Ben Yahia, Engelbert Mephu Nguifo

► To cite this version:

Warith Eddine Djeddi, Sadok Ben Yahia, Engelbert Mephu Nguifo. A Degree Centrality-Enhanced Computational Approach for Local Network Alignment Leveraging Knowledge Graph Embeddings. Expert Systems with Applications, 2025, 275 (126755), 10.1016/j.eswa.2025.126755. hal-04925835

HAL Id: hal-04925835

https://hal.science/hal-04925835v1

Submitted on 3 Feb 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
Graphical Abstract

A Degree Centrality-Enhanced Computational Approach for Local Network
Alignment Leveraging Knowledge Graph Embeddings

Warith Eddine DJEDDI, Sadok BEN YAHIA, Engelbert MEPHU NGUIFO

<figure><img src="image_3.png" /></figure>
A Degree Centrality-Enhanced Computational
Approach for Local Network Alignment Leveraging
Knowledge Graph Embeddings

Warith Eddine DJEDDIª, Sadok BEN YAHIAª,ᵇ,ᶜ, Engelbert MEPHU NGUIFOᵈ

<sup>a</sup>Department of Computer Sciences, University of Tunis El Manar, Faculty of Sciences, El Manar, 2092, Tunis, Tunisia

<sup>b</sup>Tallinn University of Technology, Akadeemia tee 15a, Tallinn, 12618, Tallinn, Estonia

<sup>c</sup>Southern Denmark University, Alsion 2
Sønderborg, Sønderborg, DK-6400, Sønderborg, Denmark

<sup>d</sup>University Clermont Auvergne, Clermont Auvergne INP, ENSMSE, CNRS, LIMOS, Clermont Auvergne, 63000, Clermont-Ferrand, France

**Abstract**

Biological network alignment serves various goals, including identifying similar regions between networks of different species, transferring biological knowledge, and predicting protein complexes and functions. This paper presents KOGAL (KnOWledge Graph ALignment), a scalable multiprocessing algorithm for local protein-protein interaction (PPI) network alignment. KOGAL aims to predict conserved protein complexes across species' PPI networks. It employs two strategies for seed discovery and initial alignment: the first computes the cosine similarity between embedding vectors derived from knowledge graph models like TransE or DistMult to generate an alignment matrix. The second strategy begins the alignment process by calculating the centrality degree of nodes within each network, highlighting the importance of each protein in the network structure. Protein similarities are quantified by combining protein sequence similarities with knowledge graph embeddings, ensuring biologically meaningful structural alignments. KOGAL depicts strong results compared to other state-of-the-art approaches. When evaluated on real PPI networks, KOGAL demonstrates high accuracy across multiple metrics, including coverage, sensitivity, the number of matched reference conserved complexes (Frac), complex-wise sensitivity (Sn), positive predictive value (PPV), geometric accuracy (ACC), and maximum matching ratio (MMR).
# 1. Introduction

The PPI network alignment is essential since it drives understanding of bio-
logical systems. It is worth noting that comparing PPI networks from different
species improves our understanding of species evolution but also aids in iden-
tifying functional orthologs and predicting the associated functions [40]. PPI
network alignment has numerous applications, including detecting functional or-
thologs [40], drug design [50], PPI prediction [41, 48], and improving our under-
standing of infectious diseases [42]. So far, they have proposed several network
alignment algorithms for local and global alignment. A local network alignment
(LNA) aims to identify functionally or structurally conserved subnetworks. At the
same time, global network alignment (GNA) carries out an overall comparison to
find a unique correspondence between all nodes in the input networks [30, 36].
Generally, network alignment algorithms (local or global) can be classified into
pairwise and multiple alignments. The former aligns only two networks, while
the latter aligns at least three. Some surveys examine the impact of network em-
bedding on learning many network representations to deduce alignment among
biological networks [10], or to be used in biomedical link prediction (i.e., drug-
drug associations, drug-target interactions, protein-protein interactions) [51], node
classification, protein function prediction, recommendation systems [9, 34, 38],
medical term semantic type classification [50], and user behavior prediction [8]
by modeling dynamic interactions within networks. In this extensive survey [10],
the authors discuss different network embedding techniques to resolve the prob-
lem of network alignment between PPI networks. The various methods apply two
main strategies: First, there are other models (e.g., Word2Vec [47], Node2Vec
[49]) that perform a node embedding of the compared networks or species in the
same vector space; second, the selected model makes use of protein representa-
tions to deduce the alignment by applying different similarities (e.g., the cosine or
euclidean distance similarity) among the vector representations of proteins. The
remainder will focus on the different approaches to network alignment, which is
our main target. Various methods have been proposed for local and global align-
ment algorithms in this respect. NetworkBLAST [43] is a local network-based
alignment approach that builds an alignment based on the sequence similarities
of pairs of proteins to identify conserved protein complexes between two given
species. NetworkBLAST [43] is a variant of PathBLAST that seeks to detect triv-
ial linear pathways while discovering complex network structures. Therefore, the
approach tries to discover high-scoring seeds in the alignment graph, and after this
step, it extends the seeds using a greedy algorithm. AlignMCL [32] computes the
MCL algorithm to detect the conserved modules, altering the motif-based method of AlignNemo [31]. AlignMCL uses a list of seed nodes without providing a rule of thumb to build it. ClusterM [33] is an approach for discovering conserved protein complexes across multiple PPI networks based on the combination of the topological separability of protein complexes and protein sequence similarity. The method is based on three steps: a) finding the set of protein spines in each PPI network, b) finding separated subnetworks for each protein spine, and c) predicting conserved subnetworks within the known separated subnetworks based on PPI and sequence similarity. LePrimAlign [19] is another algorithm for predicting conserved modules based on taking as input the result of a pairwise GNA algorithm called Primalign, a many-to-many node mapping, and a graph clustering technique, after applying a threshold to filter the pertinent seed node pairs and detecting the pairs of initial clusters based on graph entropy (i.e., entropy-based graph clustering). The first step in finding clusters for each seed protein is adding all its neighbors. If graph entropy decreases, the neighbor protein with the highest weighted degree is removed from the initial cluster. The remaining steps are executed iteratively, decreasing weighted degrees until all neighboring proteins are computed. Thus, the LePrimAlign method selects the cluster or module with the least graph entropy for each PPI network. In the meantime, the first cluster pair is expanded to obtain the final aligned cluster pairs by considering both intra-network and inter-network scores.

The proposed approach aligns protein-protein interaction (PPI) networks by leveraging sequence similarity as the main driver for interspecies alignment. It begins by selecting seed proteins based on their degree of centrality in the PPI networks of any pairwise species. The top *N* proteins with the highest centrality are selected as seeds, and their local neighborhoods that comprise direct interaction partners are extracted to capture both the proteins and their interaction patterns. These subgraphs form the basis for alignment, focusing on sequence similarity across species, measured using BLAST bit scores.

Therefore, the KOGAL method identifies similar candidate proteins from this initial alignment to predict conserved complexes. Graph clustering techniques such as IPCA or MCODE are then applied iteratively to generate preliminary clusters for each protein pair. To expand these clusters, edge scores based on knowledge graph embeddings (KGE) are calculated between proteins inside and outside the initial cluster. The process continues until all candidate pairs are aligned. KOGAL leverages KGE models such as TransE, DistMult, and TransR to measure structural similarities between proteins, enabling the identification of conserved protein complexes throughout the alignment process. The alignment process is
based on a multiprocessing strategy to speed up execution and run multiple pro-
cesses simultaneously. In contrast, we compile two gold-standard references for
all the complex prediction tasks to evaluate the different graph embedding models.

The remainder of this paper is organized as follows. Section 2 outlines the materials and methods used in this study. Section 3 focuses on the construction of the Yeast-Human reference conserved protein complexes. Section 4 presents the results of the proposed alignment and analysis methods. Section 5 discusses the performance of the proposed algorithm, including its comparative evaluation against other alignment methods across diverse eukaryotic species. Finally, Section 6 concludes the study and highlights potential directions for future work.

## 2. Material and Methods

We usher in this section by presenting the general architecture, and the formu-
lation of the problem is thoroughly described.

2.1. *The general architecture of the proposed approach*

Figure 1 depicts the general architecture of the proposed approach for local
network alignment. After parsing the knowledge graph, which contains many dif-
ferent types of entities across various kinds of relationships, the approach employs
two strategies for seed discovery and initial alignment. The first strategy enhances
the alignment by calculating the centrality of nodes within each network, captur-
ing the significance of each protein in the overall network structure. The second
strategy generates an alignment matrix by computing the cosine similarity be-
tween embedding vectors derived from knowledge graph models like TransE or
DistMult, ensuring the alignment is based on functional and structural similarities.
The KOGAL approach operates in five significant steps:

1. *Degree Centrality Computation* : In this step, KOGAL integrates topo-
logical and sequence-based information to produce an initial alignment of
protein-protein interaction (PPI) networks between species. Using these
networks, the approach identifies key proteins through degree centrality,
which captures the significance of proteins based on their connectivity within
the network. The *N* top proteins in terms of centrality are selected as seeds,
forming the foundation for further analysis. Once the seeds are selected,
KOGAL extracts their local neighborhoods, which include the seed pro-
teins and their direct interaction partners. These neighborhoods are used
to generate subgraphs from the original PPI networks, allowing us to com-
pare the local structure and topology of the proteins across species. This
<figure><img src="image_4.png" /><figcaption>Figure 1: Pipeline of KOGAL for applying graph embedding methods to predict protein complexes between two species (e.g., Species A and B). The KOGAL framework initiates the seed discovery process using two distinct strategies. The first strategy, highlighted in yellow, involves computing the cosine similarity between embedding vectors generated by knowledge graph models such as TransE or DistMult to construct an alignment matrix. The second strategy, shown in green, starts by calculating the degree centrality of nodes within each network to identify key proteins in the network structure. In both strategies, protein or edge similarities are quantified by integrating sequence similarities with knowledge graph embeddings to expand the preliminary clusters detected using IPCA or MCODE. The black box represents the final local alignment achieved after detecting and expanding the initial clusters. The DistMult equation is used to compute local and global edge scores between the protein outside the scope and the proteins in the preliminary cluster by taking into consideration only the *n* related relations.</figcaption></figure>

step helps us focus not only on individual proteins but also on their interaction patterns, which provides valuable context for identifying potential functional similarities. To assess the sequence similarity between proteins, we use BLAST bit scores, which are log-transformed to reduce the influence of extreme values and normalized to a range between 0 and 1. By applying this transformation, we ensure that the sequence similarity scores are comparable across species. In particular, cross-species sequence similarity is normalized using the maximum observed score in the dataset. The initial
alignment is constructed by comparing each seed protein and its neighbor-
hood from the two species based on sequence similarity. For each pair of
proteins, the log-transformed and normalized BLAST scores are used to de-
termine similarity. Protein pairs with a sequence similarity score exceeding
a predefined threshold are aligned.

2. Cosine Similarity-Based Approach for Alignment Matrix Generation: This step aims to learn representations (i.e., embeddings) that capture the underlying semantics or meanings of the entities and relationships in the knowledge graph. Different models, such as TransE, TransR, or DisMult, can be employed. These models take the parsed knowledge graph as input and generate embeddings for each entity in the graph. The embedding process involves mapping entities and relationships to continuous vector representations in a lower-dimensional space. These embeddings aim to encode the structural and semantic information of the knowledge graph, allowing for efficient comparison and analysis. Therefore, the embedding process is computed using an element-wise product operation. This operation combines the entities' embeddings and relationships by multiplying their vector representations element-wise. The resulting vector represents the combined information from the entity and its relationship, capturing their interaction. By computing a selected model on the knowledge graph, the algorithm generates embeddings that capture the relationships and semantics of the entities within the graph. The algorithm selects only the embeddings of entities (i.e., proteins) located in the PPI networks of Human (i.e., 'Y1' as depicted by Figure 1) and Yeast (i.e., 'Y2' as shown by Figure 1). The algorithm identifies potential counterparts or similar proteins between the two networks by comparing the embeddings in 'Y1' with those in 'Y2'.

3. Clustering with IPCA or MCODE for identifying protein complexes : Discover the preliminary modules or clusters for each selected pair of seeds from the two networks using a clustering method (e.g., IPCA or MCODE). For instance, {A1, B2} represents a selected pair of seeds, as illustrated in Figure 1, generated based on the cosine similarity between the vector representations of each protein. It is worth noting that the seed pairs are generated from the initial alignment, as described in Step 2, after applying a manually defined threshold τ₁ (i.e., Threshold1 as depicted in Figure 1) to collect pairs of seeds with high similarity scores. Otherwise, computing the embedding-based similarity using the cosine metric leads to an inferred alignment matrix. From the inferred alignment matrix, KOGAL applies a manually defined threshold τ₁ (cf. Figure 1) to identify and collect pairs
of seeds with high similarity scores, forming the foundation for the alignment process. Building on this, KOGAL can rely on Step 1, which utilizes a defined threshold $\gamma$, to generate the initial alignment by establishing meaningful correspondences between proteins based on their similarity scores. For example, as illustrated in Figure 1, this strategy results in the initial alignment, where proteins are matched as follows: A1 is aligned to B2, A2 is aligned to B3 and A5 is aligned to B2. However, when KOGAL relies on Step 2, the initial alignment differs, leading to A1 being aligned to B2, A2 to B4, and A4 to B2.

After computing preliminary clusters, we obtained the two introductory aligned cluster pairs (A1,A4,A5) from the first PPI network (i.e., species 1) and (B1,B2) from the second PPI network (i.e., species 2). Then, each seed is expanded iteratively by exploring the proteins outside the scope of a given cluster (e.g., the A7 protein), which have at least one interaction with any protein inside their preliminary clusters (e.g., A7 has a direct interaction with A5);

4. Cluster expansion : We aim to find a high-edge score function for a given model by equitably considering both local and global edge scores. Thus, if the edge score similarity is greater than the manually defined threshold $\tau_2 = 0.5$ (see Threshold2 as depicted in Figure 1), the selected protein (e.g., A7) is added to the initial cluster (e.g., cluster with yellow color) to form a new cluster (e.g., cluster with blue color). This addition enhances the prediction results by iteratively adding all the proteins outside the preliminary clusters to finally obtain the (A1,A4,A5,A7) cluster aligned with the (B1,B2,B3,B4) cluster, which can be added to the local alignment results as an aligned cluster pair;

5. Alignment results : Finally, this process is repeated iteratively to select another pair of seed nodes (e.g., {A2,B4} and {A4,B2}).

The novelty of KOGAL lies in utilizing degree centrality to select seed proteins, ensuring that the alignment process begins with biologically significant nodes. By prioritizing high-degree proteins, the algorithm increases the likelihood of capturing functionally important interactions, as these proteins typically participate in multiple interactions across various biological processes. Starting from these key nodes allows the algorithm to initiate alignments in densely connected regions, where local subnetwork structures are more apparent and biologically meaningful. This strategy facilitates the identification of conserved functional modules, complexes, or pathways across species.
Furthermore, the KOGAL approach is enhanced by the integration of KGE, which contribute to the alignment process in several ways:

*   **Similarity Expansion:** KGE enable the algorithm to compute rich similarity measures between proteins, extending beyond direct features such as sequence or structure. By leveraging the relationships encoded within a broader biological knowledge graph, KOGAL can identify indirect protein-protein associations, thereby refining the alignment process.

*   **Neighborhood-Based Expansion:** After selecting the seed proteins, KOGAL employs KGE to expand the alignment by considering the neighborhood of each protein within the network. This method enables the mapping of entire subnetworks or complexes, ensuring that local alignments capture biologically significant structures and interactions.

The combined use of cosine similarity-based alignment and degree centrality-based seed selection ensures that the local alignment process is both biologically meaningful and computationally efficient, with each strategy complementing the other to enhance the accuracy and relevance of the resulting alignments. The integration of knowledge graph embeddings further enhances the algorithm's ability to capture both direct and indirect relationships between proteins, enabling more comprehensive and accurate alignments across diverse PPI networks.

## 2.2. *Problem formulation*

Consider the following two PPI networks: $G_1$ and $G_2$. Each PPI network is an unweighted, undirected graph $G_i = (V_i, E_i)$, where $V_i = \{p_{1i}, \dots, p_{|N_i|}\}$ is a set of proteins, and $|N_V|$ is the total number of vertices. $E_i$ is a set of undirected edges that represent an interaction between two proteins $v_1$ and $v_2$. Given the input protein sets (i.e., $V_i$ and $V_j$) and their respective networks (i.e., $Net_i(V_i)$ and $Net_j(V_j)$) from two different species, along with the user-specified threshold $\tau_1$ and weighting factors $\alpha$. For each protein $p_i$ in the first network (that is, $Net_i(V_i)$), the algorithm iterates through proteins $p_j$ in the second network (i.e., $Net_j(V_j)$). Crucially, this iteration excludes cases where both $p_i$ and $p_j$ are from the same species network (i.e., $p_i \in Net_i(V_i) \neq p_j \in Net_j(V_j)$).

The proposed method for aligning protein-protein interaction (PPI) networks is leveraging sequence similarity as a primary driver for alignment between species. The process begins with the generation of seed proteins, which are critical to establishing an initial set of candidate alignments. To identify these seeds, we first
compute the degree centrality for a given protein *p* (cf., lines 3 and 6 in Algorithm 1) in their inner network using the equation 1:

$$c(p) = \frac{\deg(p)}{|V| - 1}. \qquad (1)$$

The top *N* proteins with the highest centrality from both species are selected as seeds (cf., Lines 8 and 9 in Algorithm 1). After selecting the seeds, we extract their local neighborhoods by identifying the direct neighbors of each seed protein in both species' networks (cf., Lines 11 and 14 in Algorithm 1). This local neighborhood expansion captures the immediate interaction partners of each seed, allowing us to compare not only the seeds themselves but also their interaction patterns (cf. equation 2).

$$subNet(p) = \{p' \in V | (p, p') \in E\}. \qquad (2)$$

The resulting subgraphs, composed of the seed proteins and their neighbors, are used for the next step of the alignment process. Once the seed proteins and their direct neighborhoods are selected, the approach focuses on the sequence similarity between proteins from different species to produce the initial alignment. Sequence similarity is computed using BLAST bit scores, which quantify how closely related two proteins are based on their amino acid sequences. To ensure that the sequence similarity values are comparable across proteins, we apply a log transformation to the BLAST bit scores (cf., Equation 3):

$$\log\_transform(s) = \log(1 + s). \qquad (3)$$

This transformation mitigates the effects of extreme values and stabilizes the distribution of similarity scores. Additionally, we normalize the cross-species BLAST scores by dividing them by the maximum observed score (cf., Line 18 in Algorithm 1), ensuring that the sequence similarity values are constrained between 0 and 1 (cf. Equation 4):

$$sim_{norm}(p_i, p_j) = \frac{sim_{cross}(p_i, p_j)}{\max_{p'_i \in V_i, p'_j \in V_j} sim_{cross}(p'_i, p'_j)}. \qquad (4)$$

By incorporating not only the seeds themselves but also their direct neighbors, the approach captures both the sequence-based and interaction-based relationships between proteins. Then, from the initial alignment, KOGAL selects many similar candidate proteins to predict the conserved complex. Then, iteratively, the
approach applies graph clustering techniques (i.e., IPCA [14], MCODE [16], or
COACH [17] methods) to find preliminary clusters for each candidate protein pair.
After that, to feed the initial cluster with proteins outside the scope, the approach
relies on two edge scores computed from the KGE between the protein outside
the scope and all the proteins in the initial cluster. The alignment process will
terminate when the ensemble of candidate protein pairs is exhausted. Therefore,
the similarities between the proteins are computed by knowledge graph embed-
ding models (e.g., TransE [45], DistMult [44], and TransR [46]) to quantify the
structural similarities among the compared proteins [22]. The KOGAL method is
unique because it uses knowledge graph embedding, in order to find out how sim-
ilar the structures of different entities are. This makes it easier to find conserved
protein complexes during the alignment or matching process.

The KOGAL approach utilizes a network-based strategy. To accomplish this,
we define the heterogeneous graph that represents the PPI network. This defined
graph KG(V, E) is made up of *n* source species nodes S = ps₁, ps₂, ..., psₙ and
*m* target species nodes T = pt₁, pt₂, ..., ptₘ. It is worth noting that the con-
structed knowledge graph **R** has *k* different types of edges. We computed a
knowledge graph **K** as a heterogeneous, multi-relation, and undirected graph,
including data concerning a set of entities **E** and a set of relationships between
them **R**, defined as **K** ⊆ **E** × **R** × **E**. A knowledge graph is often considered
a set of triples (*h*,*r*,*t*) ∈ **K**, where *h*,*t* ∈ **E** are the head and tail entities related
by the relationship *r* ∈ **R**. Therefore, the essential triples that our knowledge
graph uses to detect protein complexes could be (*protein1*, *interact*, *protein2*) and
(*protein1*, *belongToComplex*, *protein2*), where the entities *protein1* and *protein2*
are connected by the relationships *interact* and *belongToComplex*.

Meanwhile, our research attempts to deduce an alignment between the com-
pared species based on the current data in **K** by using the KGE. In other words,
we try to discover some partial triple (*protein1*, *belongToComplex*, ?) and antici-
pate the accurate tail entity or be given (?, *belongToComplex*, *protein2*) and try to
anticipate the accurate head entity. We applied various KGE models to learn repre-
sentations of entities (e.g., proteins) and relationships (e.g., interactions associated
with complexes) in an informative, low-dimensional vector space. Consequently,
for a given model *f*: **E** × **R** × **E** → **R**, it computes a scalar score defining the cred-
ibility for each given triple (*h*,*r*,*t*) ∈ **K**. In our approach, *f* is a learned model
that is uniquely used with the embeddings of the entities and the relations in the
triples, denoted as *f*(*h*,*r*,*t*), where *h*,*t* ∈ **R**^d and *r* ∈ **R**^d. The number *d* depicts the
embedding dimensions of the entities and relations, respectively.

It is worth noting that KOGAL relies on another strategy in addition to focus-
ing on the degree and direct neighborhood of proteins. It can compute the simi-
larity between the representations of all compared proteins from the two species
by adopting the cosine metric in the embedding space to discover the initial seed
nodes (i.e., line 6 from Algorithm 1). We created a comprehensive knowledge
graph for each compared species with approximately 250.957 in edges across
four types of relationships connecting proteins, genes, metabolic pathways, and
protein-protein interactions (c.f. Table 1). The relationships are "association",
"direct-interaction," "co-membership," and "participates-in". After that, different
models were computed to learn representations of the entities and relationships
in an informative, low-dimensional vector space. Following the discovery of the
most similar entity embeddings (i.e., line 6 from Algorithm 1) for a given thresh-
old $\tau_1$, the top most relevant seeds were chosen as candidates to detect a prelimi-
nary cluster for each selected pair of seeds from the two compared networks (i.e.,
line 35 from Algorithm 1) using a given clustering method (i.e., IPCA [14] or
MCODE [16]). It is worth noting that the *IPCACL1* and *IPCACL2* functions in
Algorithm 1 invoke the IPCA [14] method to return an identified complex for a
given protein *p*.

The preliminary discovered clusters from two species are then extended or
enlarged to include other proteins not within the scope of each discovered cluster.
The outside-scope proteins illustrate the entities outside the cluster that have at
least one interaction with any entities inside the cluster. We compute the edge
score between each protein (i.e., *pcl*) in the preliminary cluster (cf. line 4 of
Algorithm 2) and its direct interactions (i.e., *a*<sub>*k*</sub>) by considering only the *direct-interaction* relation. In contrast, we compute a global edge score between the
protein (i.e., *a*<sub>*k*</sub>) and all neighboring proteins (i.e., *V*) that belong to the initial
cluster (cf. line 5 of Algorithm 2) by considering only the *co-membership* relation
(i.e., *Emb*<sub>*r*</sub>(*r*<sub>ppi</sub>)). We focus on the proteins outside the scope (i.e., *a*<sub>*k*</sub>) that have
at least one interaction with the proteins in the initially discovered clusters (i.e.,
*pcl*) (cf. line 3 of Algorithm 2).

KOGAL computes both local and global edge score functions to estimate the
likelihood of relations between the protein outside the scope and the proteins in-
side the initial clusters. The local edge score for a given triplet is calculated using
various vector operations over the representations of the interacting candidate pro-
tein, considering only the *direct-interaction* relation within its network. We use
the DistMult model [44] to calculate edge scores between the embeddings of enti-
ties and the relations for each triplet, *DistMult*(*h*,*r*,*t*), where *h*,*t* ∈ ℝ<sup>*k*</sup> and *r* ∈ ℝ<sup>*j*</sup>
(cf. line 4 of Algorithm 2). The scoring function is designed to capture symmetric
relational patterns, i.e., relations *r* such that for two proteins, *pcl* and *a*<sub>*k*</sub>, from
the source or target network, the triplets ($pcl, r, a_k$) and ($a_k, r, pcl$) hold (cf. line 4 of Algorithm 2). On the other hand, the global edge score for the given triplets computes the representations of the candidate protein (i.e., $a_k$) against all proteins within each initial cluster, considering only the *co-membership* relations (i.e., relations $r$ such that for a given protein $pcl$ and a set of proteins belonging to the preliminary discovered clusters $V$, the triplets ($pcl, r, V$) and ($V, r, pcl$) hold) (cf. line 5 of Algorithm 2). If the entity's edge score exceeds a given threshold $\tau_2$ (cf. line 7 of Algorithm 2), we iteratively add the proteins outside the scope to each cluster (cf. line 8 of Algorithm 2).

Thus, to tune the contribution of the local or global edge score in computing the overall score, we provide $\alpha$ as a relative weighting (i.e., line 8 from Algorithm 2). At the start of the alignment, the value of $\alpha$ is manually defined between two numbers in the range [0, 1]. Next, the newly aligned cluster pair from the two compared species (i.e., lines 38 and 39 from Algorithm 1) is added to the local alignment results (i.e., line 45 from Algorithm 1). Again, the approach selects another pair of seed nodes (i.e., line 34 from Algorithm 1) and repeats the preliminary cluster formation and expansion steps.

### 3. Building the Yeast-Human reference conserved protein complexes

We use the following four steps to create the two types of the gold standard reference for Yeast and Human:

* **Step 1:** The first step consists in annotating the proteins in the CYC2008 and CORUM complexes by adding the gene ontology (GO) terms to every complex;

* **Step 2:** The process of the alignment is performed between the Saccharomyces Cerevisiae S288C complexes in CYC2008 and the Homo-sapiens complexes in CORUM (version 2022.09.09) based on the GO terms;

* **Step 3:** If a Human complex has at least half the amount of proteins annotated to a GO term and the latter is occurring in the CYC2008 complex, the KOGAL approach should match the Human complex and the Yeast complex. The result of this step is the construction of the first conserved protein complexes, with a total of 2,193 complexes;

* **Step 4:** By focusing on the cellular component ontology (CCO) terms, the developed approach can be filtered by augmenting the percentage of resemblance between the two conserved complexes for Human and Yeast proteins.
<figure><img src="image_5.png" /><figcaption>Algorithm 1: The KOGAL algorithm.</figcaption></figure>
Input: Initial cluster IPCACL(p) for a given protein $p \in V$, V is a set of proteins for the initially discovered cluster, E is a set of undirected edges, thresholds $\tau_2$, and $\alpha$. Embedding vector of the relations $Emb_r$, embedding vector of the source entities $Emb_h$, embedding vector of the target entities $Emb_t$ with $h, t \in \mathbb{R}^d$ and $r \in \mathbb{R}^d$

Output: A novel extended cluster IPCACL($p$)

for each node of IPCACL, $pcl \in V$ do

▷ Net ($pcl$) = The network where protein $pcl$ is in

4: **for all** $a_k \in Net(pcl)$ **do**

if ($pcl, a_k$) form an edge, ($pcl, a_k) \in E$ **then**

$s_{embLocal} (pcl, a_k) \leftarrow DistMult (Emb_h(pcl), Emb_r(r_{ppi}), Emb_t(a_k))$

$s_{embGlobal} (a_k, V) \leftarrow DistMult (Emb_h(a_k), Emb_r(r_{ppi}), Emb_t(V))$

8: $Sim_{emb} (pcl, a_k) \leftarrow \alpha s_{embLocal} (pcl, a_k) + (1 - \alpha) s_{embGlobal} (a_k, V)$;

if $Sim_{emb} (pcl, a_k) \ge \tau_2$ **then**

IPCACL $\leftarrow$ IPCACL $\cup$ ($pcl, a_k$)

**end if**

12: **end if**

**end for**

**end for**

**return** IPCACL

<caption>**Algorithm 2:** Extension-initial-cluster(IPCACL($p$), $V$, $E$, $\tau_2$, $\alpha$, $Emb_r$, $Emb_h$)</caption>

Therefore, the execution of this step produces a contracted reference of conserved protein complexes, which can achieve 1,212 complexes if a Human complex has at least 80% of the number of proteins annotated to a GO term in the Yeast species.

## 4. Results

In this section, we evaluate the performance of the KOGAL approach compared to other relevant LNA algorithms. In our LNA process, we computed five PPI networks collected from the High-quality INTERactomes (HINT) curated database [35]: *Homo-Sapien*, *Saccharomyces Cerevisiae S288C*, *Caenorhabditis Elegans*, *Drosophila Melanogaster* and *Mus-Musculus*. The number of proteins and interactions in these PPI networks is given in Table 3. In what follows, we provide helpful information about building our knowledge graph (c.f., Table 1) using different connected entity types and interaction types. Meanwhile, we construct many networks for proteins and genes, such as a) protein-protein direct interactions (i.e., represent binary physical interactions between proteins); b) co-membership in a protein complex (i.e., represent the membership of a group of proteins); c) protein-gene associations; d) gene-gene direct interactions (i.e., represent binary physical interactions between genes); e) co-membership in a gene complex (i.e., represent the membership of a group of genes); f) participates-in a metabolic pathway for each protein.

We applied functional and topological assessment metrics to assess our approach's alignment quality and performance. For the topological assessment met-
<table><caption>Table 1: The known relationships in the knowledge graph network.</caption><thead><tr><th>Connected entity-types</th><th>Species</th><th>interaction types</th><th>Source</th><th>Total interactions</th></tr></thead><tbody><tr><td>protein-gene</td><td>Homo-sapiens</td><td>association</td><td>UniProtKB [13]</td><td>15,366</td></tr><tr><td>protein-gene</td><td>Mus-Musculus</td><td>association</td><td>UniProtKB [13]</td><td>2,146</td></tr><tr><td>protein-gene</td><td>Caenorhabditis Elegans</td><td>association</td><td>UniProtKB [13]</td><td>4,896</td></tr><tr><td>protein-gene</td><td>Saccharomyces Cerevisiae S288C</td><td>association</td><td>UniProtKB [13]</td><td>5420</td></tr><tr><td>protein-gene</td><td>Drosophila Melanogaster</td><td>association</td><td>UniProtKB [13]</td><td>8,419</td></tr><tr><td>protein-protein</td><td>Homo-sapiens</td><td>direct-interaction</td><td>HINT [35]</td><td>12,422</td></tr><tr><td>protein-protein</td><td>Mus-Musculus</td><td>direct-interaction</td><td>HINT [35]</td><td>1,664</td></tr><tr><td>protein-protein</td><td>Caenorhabditis Elegans</td><td>direct-interaction</td><td>HINT [35]</td><td>3,224</td></tr><tr><td>protein-protein</td><td>Saccharomyces Cerevisiae S288C</td><td>direct-interaction</td><td>HINT [35]</td><td>4,237</td></tr><tr><td>protein-protein</td><td>Drosophila Melanogaster</td><td>direct-interaction</td><td>HINT [35]</td><td>6,084</td></tr><tr><td>gene-gene</td><td>Homo-sapiens</td><td>direct-interaction</td><td>HINT [35]</td><td>12,412</td></tr><tr><td>gene-gene</td><td>Mus-Musculus</td><td>direct-interaction</td><td>HINT [35]</td><td>1,663</td></tr><tr><td>gene-gene</td><td>Caenorhabditis Elegans</td><td>direct-interaction</td><td>HINT [35]</td><td>3,224</td></tr><tr><td>gene-gene</td><td>Saccharomyces Cerevisiae S288C</td><td>direct-interaction</td><td>HINT [35]</td><td>4,237</td></tr><tr><td>gene-gene</td><td>Drosophila Melanogaster</td><td>direct-interaction</td><td>HINT [35]</td><td>6,081</td></tr><tr><td>protein-protein</td><td>Homo-sapiens</td><td>co-membership</td><td>HINT [35]</td><td>10,708</td></tr><tr><td>protein-protein</td><td>Mus-Musculus</td><td>co-membership</td><td>HINT [35]</td><td>2,430</td></tr><tr><td>protein-protein</td><td>Caenorhabditis Elegans</td><td>co-membership</td><td>HINT [35]</td><td>200</td></tr><tr><td>protein-protein</td><td>Saccharomyces Cerevisiae S288C</td><td>co-membership</td><td>HINT [35]</td><td>4,069</td></tr><tr><td>protein-protein</td><td>Drosophila Melanogaster</td><td>co-membership</td><td>HINT [35]</td><td>2,585</td></tr><tr><td>gene-gene</td><td>Homo-sapiens</td><td>co-membership</td><td>HINT [35]</td><td>10,705</td></tr><tr><td>gene-gene</td><td>Mus-Musculus</td><td>co-membership</td><td>HINT [35]</td><td>2,430</td></tr><tr><td>gene-gene</td><td>Caenorhabditis Elegans</td><td>co-membership</td><td>HINT [35]</td><td>200</td></tr><tr><td>gene-gene</td><td>Saccharomyces Cerevisiae S288C</td><td>co-membership</td><td>HINT [35]</td><td>4,069</td></tr><tr><td>gene-gene</td><td>Drosophila Melanogaster</td><td>co-membership</td><td>HINT [35]</td><td>2,585</td></tr><tr><td>protein-pathway</td><td>Homo-sapiens</td><td>participates-in</td><td>KEGG [12]</td><td>63917</td></tr><tr><td>protein-pathway</td><td>Mus-Musculus</td><td>participates-in</td><td>KEGG [12]</td><td>33040</td></tr><tr><td>protein-pathway</td><td>Caenorhabditis Elegans</td><td>participates-in</td><td>KEGG [12]</td><td>4202</td></tr><tr><td>protein-pathway</td><td>Saccharomyces Cerevisiae S288C</td><td>participates-in</td><td>KEGG [12]</td><td>9410</td></tr><tr><td>protein-pathway</td><td>Drosophila Melanogaster</td><td>participates-in</td><td>KEGG [12]</td><td>8912</td></tr></tbody></table>

To determine the conserved complexes from two species: *Frac*, *Sn*, *PPV*, *ACC*, and *MMR* (see Appendix A). On the other side, and to evaluate the different algorithms based on the biological significance
<table><caption>Table 2: The knowledge graph after deleting cycles from the "association", "direct-interaction", and "co-membership" relationships.</caption><thead><tr><th>Connected entity-types</th><th>Species</th><th>interaction types</th><th>Source</th><th>Total interactions</th></tr></thead><tbody><tr><td>protein-gene</td><td>Homo-sapiens</td><td>association</td><td>UniProtKB [13]</td><td>2512</td></tr><tr><td>protein-gene</td><td>Mus-Musculus</td><td>association</td><td>UniProtKB [13]</td><td>116</td></tr><tr><td>protein-gene</td><td>Caenorhabditis Elegans</td><td>association</td><td>UniProtKB [13]</td><td>979</td></tr><tr><td>protein-gene</td><td>Saccharomyces Cerevisiae S288C</td><td>association</td><td>UniProtKB [13]</td><td>954</td></tr><tr><td>protein-gene</td><td>Drosophila Melanogaster</td><td>association</td><td>UniProtKB [13]</td><td>1931</td></tr><tr><td>protein-protein</td><td>Homo-sapiens</td><td>direct-interaction</td><td>HINT [35]</td><td>7141</td></tr><tr><td>protein-protein</td><td>Mus-Musculus</td><td>direct-interaction</td><td>HINT [35]</td><td>748</td></tr><tr><td>protein-protein</td><td>Caenorhabditis Elegans</td><td>direct-interaction</td><td>HINT [35]</td><td>1900</td></tr><tr><td>protein-protein</td><td>Saccharomyces Cerevisiae S288C</td><td>direct-interaction</td><td>HINT [35]</td><td>2175</td></tr><tr><td>protein-protein</td><td>Drosophila Melanogaster</td><td>direct-interaction</td><td>HINT [35]</td><td>4067</td></tr><tr><td>gene-gene</td><td>Homo-sapiens</td><td>direct-interaction</td><td>HINT [35]</td><td>7235</td></tr><tr><td>gene-gene</td><td>Mus-Musculus</td><td>direct-interaction</td><td>HINT [35]</td><td>484</td></tr><tr><td>gene-gene</td><td>Caenorhabditis Elegans</td><td>direct-interaction</td><td>HINT [35]</td><td>1960</td></tr><tr><td>gene-gene</td><td>Saccharomyces Cerevisiae S288C</td><td>direct-interaction</td><td>HINT [35]</td><td>2218</td></tr><tr><td>gene-gene</td><td>Drosophila Melanogaster</td><td>direct-interaction</td><td>HINT [35]</td><td>3808</td></tr><tr><td>protein-protein</td><td>Homo-sapiens</td><td>co-membership</td><td>HINT [35]</td><td>6729</td></tr><tr><td>protein-protein</td><td>Mus-Musculus</td><td>co-membership</td><td>HINT [35]</td><td>1366</td></tr><tr><td>protein-protein</td><td>Caenorhabditis Elegans</td><td>co-membership</td><td>HINT [35]</td><td>67</td></tr><tr><td>protein-protein</td><td>Saccharomyces Cerevisiae S288C</td><td>co-membership</td><td>HINT [35]</td><td>2867</td></tr><tr><td>protein-protein</td><td>Drosophila Melanogaster</td><td>co-membership</td><td>HINT [35]</td><td>1527</td></tr><tr><td>gene-gene</td><td>Homo-sapiens</td><td>co-membership</td><td>HINT [35]</td><td>5973</td></tr><tr><td>gene-gene</td><td>Mus-Musculus</td><td>co-membership</td><td>HINT [35]</td><td>351</td></tr><tr><td>gene-gene</td><td>Caenorhabditis Elegans</td><td>co-membership</td><td>HINT [35]</td><td>70</td></tr><tr><td>gene-gene</td><td>Saccharomyces Cerevisiae S288C</td><td>co-membership</td><td>HINT [35]</td><td>2128</td></tr><tr><td>gene-gene</td><td>Drosophila Melanogaster</td><td>co-membership</td><td>HINT [35]</td><td>1334</td></tr><tr><td>protein-pathway</td><td>Homo-sapiens</td><td>participates-in</td><td>KEGG [12]</td><td>63917</td></tr><tr><td>protein-pathway</td><td>Mus-Musculus</td><td>participates-in</td><td>KEGG [12]</td><td>33040</td></tr><tr><td>protein-pathway</td><td>Caenorhabditis Elegans</td><td>participates-in</td><td>KEGG [12]</td><td>4202</td></tr><tr><td>protein-pathway</td><td>Saccharomyces Cerevisiae S288C</td><td>participates-in</td><td>KEGG [12]</td><td>9410</td></tr><tr><td>protein-pathway</td><td>Drosophila Melanogaster</td><td>participates-in</td><td>KEGG [12]</td><td>8912</td></tr></tbody></table>

as the same ones as those of [37] and [11], we computed:

1. Node Coverage (NCV) measures the percentage of nodes from two net-
<table><caption>Table 3: The different PPI networks used by the different approaches from HINT database</caption><thead><tr><td>Species</td><td>Nodes</td><td>Edges</td></tr></thead><tbody><tr><td>Homo-Sapien</td><td>14833</td><td>114654</td></tr><tr><td>Saccharomyces Cerevisiae S288C</td><td>5357</td><td>23617</td></tr><tr><td>Caenorhabditis Elegans</td><td>4835</td><td>12124</td></tr><tr><td>Drosophila Melanogaster</td><td>8372</td><td>31943</td></tr><tr><td>Mus-Musculus</td><td>1566</td><td>2264</td></tr></tbody></table>

works that are also present in the aligned subgraphs;

2. The Generalized $S^3$ ($GS^3$) is a metric used to measure the conservation of edges in a network alignment. It calculates the percentage of conserved edges out of the total conserved and non-conserved edges. It is designed to generalize the $S^3$ metric for one-to-one and many-to-many network alignments.

3. NCV combined with $GS^3$ ($NCV - GS^3$) is a combined metric that incorporates both NCV and $GS^3$ using the geometric mean to provide a more comprehensive assessment of alignment quality;

4. GO correctness (GC) assesses the alignment quality by annotating aligned protein pairs using Gene Ontology (GO) terms. It quantifies the extent to which protein pairs aligned under a given function that shares the same GO terms;

5. Sensitivity measures how sensitive an alignment is to the provided alignment results. It evaluates the fraction of aligned nodes annotated with a specific GO category also present in the closest cluster containing the maximum number of proteins annotated with the same GO category.

6. Cluster Interaction Quality (CIQ) is a measure of interaction conservation between all pairs of clusters in a given network alignment. It assigns a conservation score to each pair of clusters, indicating the level of interaction conservation between them. The score can take rational values, unlike binary conservation values used in pairwise network alignments.

7. Internal Cluster Quality (ICQ) measures the sequence similarities of proteins within a given cluster. It assesses the internal quality of a cluster by considering the maximum weight of any edge incident on a protein in the cluster.

8. Mean normalized entropy (MNE) is a consistency evaluation metric used in previous studies. It calculates the normalized entropy of annotated clusters, taking into account the fraction of proteins in a cluster with each GO
annotation. Lower MNE values indicate better consistency in terms of GO annotations within the clusters.

It is worth noting that some LNA approaches (e.g., KOGAL, LePrimAlign, AlignMCL) generate aligned node clusters rather than aligned protein pairs (e.g., AlignNemo, NetworkBLAST). Thus, to assess our approach using the biological metrics mentioned above, we transformed the aligned protein clusters into aligned protein pairs by supposing that for a given cluster, each protein is aligned to every other protein in that cluster. On the other hand, we sought to transform the outcomes of the LNA (i.e., AlignNemo, LocalAli, and NetworkBLAST) from aligned node pairs into aligned node clusters to evaluate the different approaches using the *Frac*, *Sn*, *PPV*, *ACC*, and *MMR* metrics, particularly focusing on the Human and Yeast species. This conversion aimed to evaluate the effectiveness of the compared methods using a gold standard reference. We compared KOGAL versus the pioneering approaches in the literature, namely LeP-rimAlign [19], AlignMCL [32], AlignNemo [31], LocalAli [15], and Network-BLAST [43]. We have applied KOGAL to different models to compute the KGE: a) KOGAL-TransE: aligns two networks using the TransE model; b) KOGAL-DistMult: aligns two networks using the DistMult model; c) KOGAL-TransR: aligns two networks using the TransR model; d) KOGAL-MPath: aligns two networks by taking into consideration four known relationships (i.e., "association", "direct-interaction", "co-membership, and participates-in) for each protein, and by computing the TransE model (cf., Table 1); e) KOGAL-RC: aligns two networks by considering the deletion of cycles and adding the metabolic pathway for each protein, and by computing the TransE model; f) KOGAL-DIPCA: The initial alignment is based on degree centrality analysis, followed by the application of the IPCA algorithm to detect or expand the identified modules or clusters; g) KOGAL-DMCODE: The initial alignment is based on degree centrality analysis, followed by the application of the MCODE algorithm to detect or expand the identified modules or clusters.

It is worth noting that the deleted cycles are from the "association", "direct interaction", and "co-membership" relationships (cf. Table 2). Adding to that, the KOGAL-TransE, KOGAL-TransR, and KOGAL-DistMult variants consider only three known relationships (i.e., "association", "direct-interaction", and "co-membership"). Detailed descriptions of the tuning parameters for the different approaches are included in Appendix B.
<table><caption>Table 4: Comparison of local network aligners based on basic gold standard reference.</caption><thead><tr><th>Approaches</th><th>Frac</th><th>Sn</th><th>PPV</th><th>ACC</th><th>MMR</th></tr></thead><tbody><tr><td colspan="6" style="text-align: center; font-weight: bold;">Human-Yeast</td></tr><tr><td>KOGAL-TransE</td><td>0.124</td><td>0.427</td><td>0.042</td><td>0.134</td><td>0.025</td></tr><tr><td>KOGAL-TransR</td><td>0.115</td><td>0.370</td><td>0.034</td><td>0.113</td><td>0.023</td></tr><tr><td>KOGAL-DistMult</td><td>0.124</td><td>0.428</td><td>0.042</td><td>0.134</td><td>0.025</td></tr><tr><td>KOGAL-MPath</td><td>0.048</td><td><strong>0.561</strong></td><td>0.045</td><td>0.160</td><td>0.010</td></tr><tr><td>KOGAL-RC</td><td>0.043</td><td>0.367</td><td>0.018</td><td>0.081</td><td>0.004</td></tr><tr><td>KOGAL-DIPCA</td><td>0.047</td><td>0.497</td><td>0.008</td><td>0.063</td><td>0.006</td></tr><tr><td>KOGAL-DMCODE</td><td>0.036</td><td>0.270</td><td>0.012</td><td>0.058</td><td>0.007</td></tr><tr><td>LePrimAlign</td><td>0.087</td><td>0.264</td><td>0.036</td><td>0.098</td><td>0.014</td></tr><tr><td>AlignMCL</td><td><strong>0.400</strong></td><td>0.280</td><td>0.033</td><td>0.096</td><td><strong>0.140</strong></td></tr><tr><td>AlignNemo</td><td>0.063</td><td>0.203</td><td><strong>0.147</strong></td><td><strong>0.173</strong></td><td>0.017</td></tr><tr><td>LocalAli</td><td>0.094</td><td>0.217</td><td>0.119</td><td>0.161</td><td>0.018</td></tr><tr><td>NetworkBLAST</td><td>0.062</td><td>0.162</td><td>0.118</td><td>0.138</td><td>0.011</td></tr><tr><td colspan="6" style="text-align: center; font-weight: bold;">Yeast</td></tr><tr><td>KOGAL-TransE</td><td><strong>0.464</strong></td><td>0.694</td><td>0.959</td><td><strong>0.816</strong></td><td><strong>0.237</strong></td></tr><tr><td>KOGAL-TransR</td><td><strong>0.464</strong></td><td>0.638</td><td>0.932</td><td>0.771</td><td>0.220</td></tr><tr><td>KOGAL-DistMult</td><td>0.464</td><td>0.694</td><td>0.960</td><td><strong>0.816</strong></td><td><strong>0.237</strong></td></tr><tr><td>KOGAL-MPath</td><td>0.083</td><td><strong>0.847</strong></td><td>0.365</td><td>0.556</td><td>0.036</td></tr><tr><td>KOGAL-RC</td><td>0.107</td><td>0.678</td><td>0.582</td><td>0.628</td><td>0.069</td></tr><tr><td>KOGAL-DIPCA</td><td>0.250</td><td>0.542</td><td>0.846</td><td>0.677</td><td>0.112</td></tr><tr><td>KOGAL-DMCODE</td><td>0.035</td><td>0.226</td><td>0.832</td><td>0.433</td><td>0.010</td></tr><tr><td>LePrimAlign</td><td>0.250</td><td>0.440</td><td><strong>0.993</strong></td><td>0.661</td><td>0.115</td></tr><tr><td>AlignMCL</td><td>0.214</td><td>0.288</td><td>0.990</td><td>0.534</td><td>0.125</td></tr><tr><td>AlignNemo</td><td>0.027</td><td>0.161</td><td>0.910</td><td>0.383</td><td>0.017</td></tr><tr><td>LocalAli</td><td>0.027</td><td>0.027</td><td>0.908</td><td>0.398</td><td>0.020</td></tr><tr><td>NetworkBLAST</td><td>0.027</td><td>0.126</td><td>0.940</td><td>0.345</td><td>0.019</td></tr><tr><td colspan="6" style="text-align: center; font-weight: bold;">Homo-sapiens</td></tr><tr><td>KOGAL-TransE</td><td>0.135</td><td>0.420</td><td>0.341</td><td>0.378</td><td>0.053</td></tr><tr><td>KOGAL-TransR</td><td>0.180</td><td>0.386</td><td>0.318</td><td>0.350</td><td>0.060</td></tr><tr><td>KOGAL-DistMult</td><td>0.135</td><td>0.420</td><td>0.341</td><td>0.378</td><td>0.053</td></tr><tr><td>KOGAL-MPath</td><td>0.044</td><td><strong>0.524</strong></td><td>0.355</td><td><strong>0.432</strong></td><td>0.018</td></tr><tr><td>KOGAL-RC</td><td>0.027</td><td>0.287</td><td>0.162</td><td>0.215</td><td>0.011</td></tr><tr><td>KOGAL-DIPCA</td><td>0.022</td><td>0.395</td><td>0.129</td><td>0.225</td><td>0.006</td></tr><tr><td>KOGAL-DMCODE</td><td>0.040</td><td>0.228</td><td>0.209</td><td>0.219</td><td>0.011</td></tr><tr><td>LePrimAlign</td><td>0.072</td><td>0.225</td><td>0.369</td><td>0.288</td><td>0.026</td></tr><tr><td>AlignMCL</td><td><strong>0.238</strong></td><td>0.236</td><td>0.401</td><td>0.308</td><td><strong>0.098</strong></td></tr><tr><td>AlignNemo</td><td>0.061</td><td>0.169</td><td>0.406</td><td>0.261</td><td>0.025</td></tr><tr><td>LocalAli</td><td>0.053</td><td>0.176</td><td>0.441</td><td>0.279</td><td>0.022</td></tr><tr><td>NetworkBLAST</td><td>0.026</td><td>0.125</td><td><strong>0.444</strong></td><td>0.235</td><td>0.010</td></tr></tbody></table>

Note: Each row lists the fraction of the amount of matched reference conserved complexes (Frac), complex-wise sensitivity (Sn), positive-predictive value (PPV), geometric accuracy (ACC), and maximum matching ratio (MMR). The best results are indicated in bold concerning each row.
<table><caption>Table 5: Comparison of different clustering techniques based on basic gold standard reference.</caption><thead><tr><th>Approaches</th><th>Frac</th><th>Sn</th><th>PPV</th><th>ACC</th><th>MMR</th><th>Predicted<br>complexes</th></tr></thead><tbody><tr><td colspan="7" style="text-align: center; font-weight: bold;">Human</td></tr><tr><td>IPCA</td><td><strong>0.495</strong></td><td><strong>0.422</strong></td><td>0.315</td><td><strong>0.365</strong></td><td><strong>0.157</strong></td><td><strong>11588</strong></td></tr><tr><td>COACH</td><td>0.491</td><td>0.418</td><td>0.247</td><td>0.322</td><td>0.142</td><td>4627</td></tr><tr><td>MCODE</td><td>0.058</td><td>0.238</td><td>0.208</td><td>0.223</td><td>0.016</td><td>325</td></tr><tr><td>ClusterONE</td><td>0.306</td><td>0.302</td><td><strong>0.376</strong></td><td>0.337</td><td>0.087</td><td>763</td></tr><tr><td colspan="7" style="text-align: center; font-weight: bold;">Yeast</td></tr><tr><td>IPCA</td><td><strong>0.785</strong></td><td><strong>0.655</strong></td><td>0.968</td><td><strong>0.796</strong></td><td><strong>0.451</strong></td><td><strong>3644</strong></td></tr><tr><td>COACH</td><td>0.714</td><td>0.621</td><td>0.944</td><td>0.766</td><td>0.446</td><td>1284</td></tr><tr><td>MCODE</td><td>0.071</td><td>0.350</td><td>0.710</td><td>0.499</td><td>0.040</td><td>144</td></tr><tr><td>ClusterONE</td><td>0.607</td><td>0.570</td><td>0.953</td><td>0.737</td><td>0.361</td><td>457</td></tr></tbody></table>

Note: Each row lists the fraction of the amount of matched reference conserved complexes (Frac), complex-wise sensitivity (Sn), positive-predictive value (PPV), geometric accuracy (ACC), and maximum matching ratio (MMR) and the number of predicted complexes from each one species. The best results are indicated in bold concerning each row.

## 4.1. Discovering conserved complexes in *Yeast* and *Human* networks

Table 4 depicts that the algorithm AlignMCL achieves the highest *FRAC* in the Human-Yeast dataset, indicating that it successfully matches a larger proportion of the known conserved complexes in that dataset. However, it has lower values for *Sn* and *PPV*, suggesting that while it matches more complexes, it has more false positives and misses some true positives. NetworkBLAST and KOGAL-MPath perform better than other KOGAL modes by achieving a good *ACC* value in the Human-Yeast dataset, but KOGAL-MPath and KOGAL-DIPCA have better *Sn* values. In the Yeast dataset, KOGAL-TransE, KOGAL-TransR, and KOGAL-DistMult show the highest fractions, suggesting their effectiveness in matching conserved complexes in Yeast. KOGAL-MPath consistently demonstrates higher sensitivity in all three datasets, indicating its ability to identify more true positive conserved complexes. LePrimAlign achieves the highest *PPV* in the Yeast dataset, suggesting that the identified conserved complexes are more likely to be true positives. Conversely, KOGAL-TransE and KOGAL-DistMult consistently exhibit higher geometric accuracy across the Yeast dataset, indicating their ability to align conserved complexes with geometric precision. KOGAL-TransE and KOGAL-DistMult achieve higher *MMR* in the Yeast datasets, indicating their ability to align larger conserved complexes with a higher matched protein ratio. LePri-
<table><caption>Table 6: Comparison of different $\tau_1$ value of KOGAL-DistMult variant based on basic gold standard reference.</caption><thead><tr><th>Threshold value</th><th>Frac</th><th>Sn</th><th>PPV</th><th>ACC</th><th>MMR</th></tr></thead><tbody><tr><td colspan="6" style="text-align: center; font-weight: bold;">Human-Yeast</td></tr><tr><td>0.0</td><td>0.118</td><td><strong>0.428</strong></td><td>0.042</td><td><strong>0.134</strong></td><td>0.024</td></tr><tr><td>0.1</td><td><strong>0.124</strong></td><td><strong>0.428</strong></td><td>0.042</td><td><strong>0.134</strong></td><td><strong>0.025</strong></td></tr><tr><td>0.2</td><td>0.108</td><td>0.389</td><td>0.041</td><td>0.126</td><td>0.020</td></tr><tr><td>0.3</td><td>0.123</td><td>0.336</td><td>0.041</td><td>0.118</td><td>0.013</td></tr><tr><td>0.4</td><td>0.012</td><td>0.141</td><td><strong>0.061</strong></td><td>0.093</td><td>0.003</td></tr><tr><td colspan="6" style="text-align: center; font-weight: bold;">Yeast</td></tr><tr><td>0.0</td><td><strong>0.464</strong></td><td><strong>0.723</strong></td><td>0.934</td><td><strong>0.822</strong></td><td>0.220</td></tr><tr><td>0.1</td><td><strong>0.464</strong></td><td>0.694</td><td>0.960</td><td>0.816</td><td>0.237</td></tr><tr><td>0.2</td><td>0.500</td><td>0.678</td><td><strong>0.968</strong></td><td>0.810</td><td><strong>0.239</strong></td></tr><tr><td>0.3</td><td>0.428</td><td>0.565</td><td>0.964</td><td>0.738</td><td>0.201</td></tr><tr><td>0.4</td><td>0.107</td><td>0.259</td><td>0.956</td><td>0.498</td><td>0.049</td></tr><tr><td colspan="6" style="text-align: center; font-weight: bold;">Homo-sapiens</td></tr><tr><td>0.0</td><td><strong>0.144</strong></td><td><strong>0.424</strong></td><td>0.343</td><td><strong>0.381</strong></td><td><strong>0.055</strong></td></tr><tr><td>0.1</td><td>0.135</td><td>0.420</td><td>0.341</td><td>0.378</td><td>0.053</td></tr><tr><td>0.2</td><td>0.085</td><td>0.325</td><td>0.356</td><td>0.340</td><td>0.033</td></tr><tr><td>0.3</td><td>0.022</td><td>0.151</td><td>0.427</td><td>0.254</td><td>0.011</td></tr><tr><td>0.4</td><td>0</td><td>0.048</td><td><strong>0.468</strong></td><td>0.150</td><td>0</td></tr></tbody></table>

Note: Each row lists the fraction of the amount of matched reference conserved complexes (Frac), complex-wise sensitivity (Sn), positive predictive value (PPV), geometric accuracy (ACC), and maximum matching ratio (MMR). The best results are indicated in bold for each row.
<table><caption>Table 7: Comparison of different local network aligners based on the second gold standard reference.</caption><thead><tr><th>Approaches</th><th>Frac</th><th>Sn</th><th>PPV</th><th>ACC</th><th>MMR</th></tr></thead><tbody><tr><td colspan="6" style="text-align: center; font-weight: bold;">Human-Yeast</td></tr><tr><td>KOGAL-TransE</td><td>0.142</td><td>0.454</td><td>0.070</td><td><strong>0.179</strong></td><td>0.036</td></tr><tr><td>KOGAL-TransR</td><td>0.132</td><td>0.396</td><td>0.058</td><td>0.151</td><td>0.034</td></tr><tr><td>KOGAL-DistMult</td><td>0.142</td><td>0.454</td><td>0.070</td><td><strong>0.179</strong></td><td>0.036</td></tr><tr><td>KOGAL-MPath</td><td>0.036</td><td><strong>0.542</strong></td><td>0.025</td><td>0.117</td><td>0.006</td></tr><tr><td>KOGAL-RC</td><td>0.044</td><td>0.380</td><td>0.034</td><td>0.114</td><td>0.007</td></tr><tr><td>KOGAL-DIPCA</td><td>0.058</td><td>0.512</td><td>0.012</td><td>0.080</td><td>0.010</td></tr><tr><td>KOGAL-DMCODE</td><td>0.034</td><td>0.283</td><td>0.019</td><td>0.073</td><td>0.010</td></tr><tr><td>LePrimAlign</td><td>0.110</td><td>0.293</td><td>0.058</td><td>0.130</td><td>0.022</td></tr><tr><td>AlignMCL</td><td><strong>0.487</strong></td><td>0.311</td><td>0.052</td><td>0.128</td><td><strong>0.190</strong></td></tr><tr><td>AlignNemo</td><td>0.056</td><td>0.187</td><td><strong>0.087</strong></td><td>0.128</td><td>0.010</td></tr><tr><td>LocalAli</td><td>0.076</td><td>0.200</td><td>0.071</td><td>0.119</td><td>0.011</td></tr><tr><td>NetworkBLAST</td><td>0.068</td><td>0.150</td><td>0.069</td><td>0.102</td><td>0.006</td></tr><tr><td colspan="6" style="text-align: center; font-weight: bold;">Yeast</td></tr><tr><td>KOGAL-TransE</td><td>0.444</td><td>0.720</td><td>0.833</td><td><strong>0.775</strong></td><td><strong>0.226</strong></td></tr><tr><td>KOGAL-TransR</td><td><strong>0.472</strong></td><td>0.655</td><td>0.889</td><td>0.763</td><td>0.231</td></tr><tr><td>KOGAL-DistMult</td><td>0.444</td><td>0.720</td><td>0.833</td><td><strong>0.775</strong></td><td><strong>0.226</strong></td></tr><tr><td>KOGAL-MPath</td><td>0.107</td><td><strong>0.836</strong></td><td>0.424</td><td>0.595</td><td>0.053</td></tr><tr><td>KOGAL-RC</td><td>0.055</td><td>0.703</td><td>0.474</td><td>0.577</td><td>0.059</td></tr><tr><td>KOGAL-DIPCA</td><td>0.194</td><td>0.576</td><td>0.751</td><td>0.658</td><td>0.102</td></tr><tr><td>KOGAL-DMCODE</td><td>0.027</td><td>0.179</td><td>0.608</td><td>0.330</td><td>0.008</td></tr><tr><td>LePrimAlign</td><td>0.194</td><td>0.379</td><td>0.930</td><td>0.594</td><td>0.090</td></tr><tr><td>AlignMCL</td><td>0.222</td><td>0.279</td><td><strong>0.984</strong></td><td>0.524</td><td>0.115</td></tr><tr><td>AlignNemo</td><td>0.035</td><td>0.146</td><td>0.950</td><td>0.373</td><td>0.012</td></tr><tr><td>LocalAli</td><td>0.035</td><td>0.163</td><td>0.945</td><td>0.393</td><td>0.016</td></tr><tr><td>NetworkBLAST</td><td>0.035</td><td>0.124</td><td>1.0</td><td>0.352</td><td>0.015</td></tr><tr><td colspan="6" style="text-align: center; font-weight: bold;">Homo-sapiens</td></tr><tr><td>KOGAL-TransE</td><td>0.203</td><td>0.431</td><td>0.448</td><td><strong>0.439</strong></td><td>0.081</td></tr><tr><td>KOGAL-TransR</td><td><strong>0.247</strong></td><td>0.395</td><td>0.397</td><td>0.396</td><td><strong>0.084</strong></td></tr><tr><td>KOGAL-DistMult</td><td>0.203</td><td>0.431</td><td>0.448</td><td><strong>0.439</strong></td><td>0.081</td></tr><tr><td>KOGAL-MPath</td><td>0.027</td><td><strong>0.541</strong></td><td>0.213</td><td>0.339</td><td>0.011</td></tr><tr><td>KOGAL-RC</td><td>0.035</td><td>0.283</td><td>0.224</td><td>0.252</td><td>0.019</td></tr><tr><td>KOGAL-DIPCA</td><td>0.026</td><td>0.411</td><td>0.249</td><td>0.320</td><td>0.007</td></tr><tr><td>KOGAL-DMCODE</td><td>0.008</td><td>0.232</td><td>0.304</td><td>0.266</td><td>0.007</td></tr><tr><td>LePrimAlign</td><td>0.097</td><td>0.234</td><td>0.444</td><td>0.322</td><td>0.041</td></tr><tr><td>AlignMCL</td><td>0.115</td><td>0.209</td><td><strong>0.475</strong></td><td>0.315</td><td>0.080</td></tr><tr><td>AlignNemo</td><td>0.045</td><td>0.169</td><td>0.327</td><td>0.235</td><td>0.014</td></tr><tr><td>LocalAli</td><td>0.036</td><td>0.176</td><td>0.351</td><td>0.249</td><td>0.015</td></tr><tr><td>NetworkBLAST</td><td>0.018</td><td>0.018</td><td>0.358</td><td>0.216</td><td>0.005</td></tr></tbody></table>

Note: Each row lists the fraction of the amount of matched reference conserved complexes (Frac), complex-wise sensitivity (Sn), positive predictive value (PPV), geometric accuracy (ACC), and maximum matching ratio (MMR). The best results are indicated in bold for each row.
mAlign and AlignNemo show relatively lower values across all three datasets for *Frac* and *Sn*. This suggests it may struggle to identify and match conserved complexes compared to other algorithms. LePrimAlign and AlignMCL demonstrate relatively lower values for the fraction (i.e., *Frac*) in the Yeast dataset compared to the KOGAL, as mentioned above modes.

In the Homo-sapiens dataset, KOGAL-MPath achieves relatively high values for the *Frac* and *Sn*, indicating their ability to identify and match many conserved complexes. They also exhibit relatively high *PPV*, suggesting a high precision in predicting conserved complexes in the Homo-sapiens dataset. AlignMCL achieves the highest *Frac* and a good *MMR* in the Homo-sapiens dataset, indicating its effectiveness in matching larger conserved complexes and achieving higher matched protein ratios. Overall, KOGAL-MPath, KOGAL-TransE, and KOGAL-DistMult consistently perform well in multiple evaluation metrics across different datasets, suggesting their effectiveness in local network alignment. The KOGAL variants align protein interactions based on their functional and structural properties. These features provide an advantage in accurately predicting and aligning protein interactions, resulting in higher accuracy and fraction metrics. The KOGAL variants yield more aligned conserved complexes, as we computed a threshold value of $\tau_1 = 0.1$ or $\tau_1 = 0.2$. As a result, it automatically generates a higher quantity of seed node pairs, which the IPCA algorithm utilizes to reveal more preliminary clusters. To put it differently, as the $\tau_1$ threshold value increases, we observe a decline in the values of the *ACC*, *MMR*, and *Frac* metrics (cf., Table 6). Consequently, this results in a decrease in the number of aligned clusters.

## 4.2. Evaluations based on the biological significance of the output alignment

As depicted in Table 8, KOGAL-TransR achieves the highest value for *NCV* among all the algorithms, indicating that it aligns a significant percentage of nodes from the two input networks. KOGAL-TransR and KOGAL-DistMult have similar performance in *NCV*, with slightly lower values than KOGAL-TransE. LePrimAlign and NetworkBLAST have the lowest *NCV* values, indicating that they align a relatively smaller percentage of nodes than other algorithms. AlignNemo, LocalAli, and NetworkBLAST achieve the highest values for *GC*, indicating that they align protein pairs with similar *GO* terms. The KOGAL variants have the highest values for *Sensitivity*, indicating that they align proteins belonging to the closest cluster regarding *GO* annotations. KOGAL-DIPCA and KOGAL-DMCODE achieve the highest *CIQ* values, indicating superior conservation of interactions between aligned pairs. This performance is attributed to
<table><caption>Table 8: Evaluations of the alignment approaches based on the alignment between Human and Yeast</caption><thead><tr><th>Approaches</th><th>NCV</th><th>GS<sup>3</sup></th><th>NCV - GS<sup>3</sup></th><th>GC</th><th>Sensitivity</th><th>CIQ</th><th>ICQ</th><th>MNE</th></tr></thead><tbody><tr><td>KOGAL-TransE</td><td>0.943</td><td>0</td><td>0.002</td><td>0.631</td><td>0.341</td><td>0.430</td><td>0.002</td><td>4.269</td></tr><tr><td>KOGAL-TransR</td><td><strong>0.944</strong></td><td>0</td><td>0.001</td><td>0.580</td><td><strong>0.342</strong></td><td><strong>0.419</strong></td><td>0.0005</td><td>4.517</td></tr><tr><td>KOGAL-DistMult</td><td>0.942</td><td>0</td><td>0.002</td><td>0.631</td><td>0.341</td><td>0.430</td><td>0.002</td><td>4.270</td></tr><tr><td>KOGAL-MPath</td><td>0.721</td><td>0</td><td>0.037</td><td>0.561</td><td>0.322</td><td>0.46</td><td>0.0007</td><td>4.517</td></tr><tr><td>KOGAL-RC</td><td>0.617</td><td>0</td><td>0.040</td><td>0.538</td><td>0.253</td><td>0.323</td><td>0.0002</td><td>4.375</td></tr><tr><td>KOGAL-DIPCA</td><td>0.425</td><td>0.01</td><td>0.046</td><td>0.785</td><td>0.145</td><td><strong>0.545</strong></td><td>0.028</td><td>5.659</td></tr><tr><td>KOGAL-DMCODE</td><td>0.169</td><td>0</td><td>0</td><td>0.873</td><td>0.066</td><td>0.514</td><td>0.106</td><td>4.283</td></tr><tr><td>LePrimAlign</td><td>0.129</td><td>0</td><td>0</td><td>0.885</td><td>0.076</td><td>0.235</td><td>0.082</td><td>4.029</td></tr><tr><td>AlignMCL</td><td>0.493</td><td>0.01</td><td>0.064</td><td>0.812</td><td>0.219</td><td><strong>0.023</strong></td><td>0.0873</td><td>3.228</td></tr><tr><td>AlignNemo</td><td>0.190</td><td>0.02</td><td>0.06</td><td><strong>0.985</strong></td><td>0.098</td><td>0.024</td><td><strong>0.402</strong></td><td><strong>1.911</strong></td></tr><tr><td>LocalAli</td><td>0.194</td><td><strong>0.03</strong></td><td><strong>0.072</strong></td><td>0.984</td><td>0.105</td><td>0.215</td><td>0.030</td><td>5.665</td></tr><tr><td>NetworkBLAST</td><td>0.100</td><td>0.02</td><td>0.046</td><td>0.978</td><td>0.061</td><td>0.176</td><td>0.032</td><td>6.167</td></tr></tbody></table>

Note: The best results are indicated in bold concerning each row.

<table><caption>Table 9: Evaluation of variations in the number of chosen initial seeds for the KOGAL-DIPCA variant based on the alignment between Human and Yeast.</caption><thead><tr><th>Number of choosed seeds</th><th>NCV</th><th>GS<sup>3</sup></th><th>NCV - GS<sup>3</sup></th><th>GC</th><th>Sensitivity</th><th>CIQ</th><th>ICQ</th><th>MNE</th><th>Runtime</th></tr></thead><tbody><tr><td>N = 100</td><td>0.304</td><td>0.01</td><td>0.045</td><td>0.781</td><td>0.108</td><td>0.544</td><td>0.025</td><td>5.708</td><td>14656</td></tr><tr><td>N = 200</td><td>0.359</td><td>0.01</td><td>0.045</td><td>0.783</td><td>0.127</td><td>0.547</td><td>0.024</td><td>5.540</td><td>25689</td></tr><tr><td>N = 300</td><td>0.386</td><td>0.01</td><td>0.046</td><td>0.779</td><td>0.132</td><td>0.552</td><td>0.026</td><td>5.644</td><td>29185</td></tr><tr><td>N = 400</td><td>0.400</td><td>0.01</td><td>0.045</td><td>0.779</td><td>0.139</td><td>0.544</td><td>0.026</td><td>5.721</td><td>32435</td></tr><tr><td>N = 800</td><td>0.425</td><td>0.01</td><td>0.046</td><td>0.785</td><td>0.145</td><td>0.545</td><td>0.028</td><td>5.659</td><td>37190</td></tr></tbody></table>

Note: The runtime values presented in the table are measured in seconds.
their alignment process, which is primarily based on sequence similarities. AlignNemo has the highest *ICQ* value, indicating that it aligns clusters with proteins with high sequence similarity. KOGAL variants are associated with substantial cluster sizes, resulting in more conserved interactions. Consequently, this is the underlying reason for the low performance of KOGAL in terms of its *ICQ* value. Larger cluster sizes diminish the *ICQ* score, which is used to evaluate the internal cluster quality of the entire alignment. AlignNemo achieves the lowest *MNE* value, indicating better consistency in annotated clusters than other algorithms. NetworkBLAST has the highest *MNE* value, suggesting lower annotated cluster consistency. Looking at the *NCV* – *GS*³, AlignMCL, and LocalAli achieve the highest values, indicating that they strike a balance between node coverage and edge conservation. Overall, AlignMCL, AlignNemo, and LocalAli demonstrate competitive performance across multiple evaluation metrics, while LePrimAlign and NetworkBLAST show relatively lower performance. In comparison, KOGAL variants exhibit comparable performance in *NCV* and *Sensitivity*, with KOGAL-DIPCA and KOGAL-DMCODE outperforming other KOGAL variants in terms of *GC*.

### 4.3. Overcoming the problem circularity in knowledge graphs

To overcome the problem of circularity, additional techniques have been implemented in conjunction with the TransE, DistMult, and TransR models. In the first technique, we removed or adjusted the circular edges in the knowledge graph based on the relation type to break the circular dependencies.

1. The initialization of an adjacency list was computed based on the provided edges and the number of nodes in the knowledge graph. Meanwhile, the approach performs a depth-first search (DFS) traversal on the graph starting from a given node. It keeps track of visited nodes and detects cycles by comparing the current node with its parent node. The recursion limit is increased to handle large graphs during DFS traversal.

2. After taking the knowledge graph and a list of cycles as input, the approach removes the edges involved in the detected cycles from the graph and returns the number of deletions made. Meanwhile, another updated knowledge graph was created by iterating over the adjacency list of the graph and taking into consideration the novel relations between entities.

The second technique focuses on incorporating semantic constraints or additional knowledge sources, such as metabolic pathways, to guide the modeling process and mitigate circularity issues. The KOGAL approach computes
the metabolic pathways from the Kyoto Encyclopedia of Genes and Genomes (KEGG) database [12] for each protein to enrich the knowledge graph and provide valuable insights into the biological context of the interactions. The metabolic pathways represent a series of biochemical reactions within a cell to facilitate various biological processes, such as energy production, the synthesis of molecules, and the breakdown of substances.

As Table SI-1 depicts, the new triplets were created after detecting and deleting cycles from the "association", "direct-interaction", and "co-membership" relationships. Adding to that, by including 119.481 metabolic pathway triplets in the knowledge graph, the approach can capture the relationships between proteins based on their involvement in specific pathways (cf. Table 2). This can help uncover potential functional associations and dependencies between proteins beyond their direct interactions. Therefore, the enriched graph can be further analyzed to identify functional modules, understand pathway crosstalk, and explore the impact of specific proteins on metabolic processes.

As Tables 4 and 7 depict, removing the cycles in the knowledge graph and integrating the metabolic pathway are computed by KOGAL-RC; indeed, this yields a loss of semantic information as the connections and relationships between proteins are distorted or lost entirely, resulting in a low number of PPI networks for each species (cf. Table 2). Therefore, we drop the removal of the cycles from the knowledge graph and focus only on adding the metabolic pathway for each protein (cf. Table 1). This strategy is computed by the KOGAL-MPath. Therefore, it is clear that the addition of metabolic pathway information to the knowledge graph in KOGAL-MPath has led to an improvement in some evaluation metrics compared to other versions of KOGAL, such as KOGAL-TransE, KOGAL-TransR, and KOGAL-DistMult. Specifically, in the case of the Human-Yeast alignment, KOGAL-MPath shows a significant improvement in *Sn*, with a value of 0.561, which is higher than any other approach listed. Therefore, the addition of metabolic pathway information in KOGAL-MPath results in an improvement of approximately 37.5% in complex-wise sensitivity compared to the average performance of the KOGAL-TransE, KOGAL-TransR and KOGAL-DistMult variants. This indicates that KOGAL-MPath can capture a more significant portion of the matched reference conserved complexes in this alignment scenario. In the Yeast dataset, KOGAL-MPath exhibits a substantial increase in *Sn*, with a value of 0.847. Therefore, in the Yeast alignment, the addition of metabolic pathway information in KOGAL-MPath results in an improvement of approximately 25.37% in complex-wise sensitivity compared to the average performance of the other KOGAL variants without taking into consideration the KOGAL-RC variant.
The ACC is also improved compared to the Homo-sapiens dataset, and KOGAL-MPath achieves the highest Sn of 0.524 and the highest ACC of 0.432. Therefore, in the Homo-sapiens alignment, the addition of metabolic pathway information in KOGAL-MPath results in an improvement of approximately 28.17% in complex-wise sensitivity compared to the average performance of the KOGAL-TransE, KOGAL-TransR and KOGAL-DistMult variants. This suggests that incorporating metabolic pathway information has a positive effect on capturing more conserved complexes and improving the accuracy of the alignment.

### 4.4. *Implementation Details*

The KOGAL approach uses the initial alignment results generated by the Deep-Graph-Learning Knowledge Embeddings (DGL-KE) [27] to efficiently learn large knowledge graphs' embeddings. The DGL-KE method stores information about proteins or genes and their relations, and it is developed by Amazon's AWS AI Laboratory [26]. The source code of KOGAL and the datasets used to generate the results is accessible through https://perso.isima.fr/~enmephun/FILES/KOGAL/.

The computation performance of the developed approach depends on the size of PPI networks (i.e number of proteins and interactions), the selection of the $τ_1$ threshold, the embedding model, and the embedding size of relations and entities (i.e, embedding dimension). For instance, by computing the TransE model as the embedding method, it took about roughly 12 hours to handle the Human and Yeast PPI network alignment using a $τ_1$ = 0.2. Meanwhile, the execution time of $τ_1$ = 0.3 and $τ_1$ = 0.4, was roughly 2 hours and 5 minutes, respectively. All the experiments were carried out on an Intel computer with a 3.70 GHz i9 processor and 128 GB of RAM.

## 5. Discussion

Our approach employed three clustering methods (i.e., IPCA, COACH, and MCODE). However, our primary focus was on the IPCA method due to its superior performance and remarkable results obtained when applied to predict protein complexes from the Human and Yeast networks PPI data (cf., Table 5). KOGAL modes showed better correspondence with reference complexes derived from the CYC2008. Generally, the protein complexes maintain the analogous cellular component, and roughly all play similar functions and/or engage in akin biological processes. The low MMR value for the Human-Yeast and Human complexes is determined by how accurately the predicted complexes represent the reference
<figure><img src="image_6.png" /><figcaption>Figure 2: KOGAL detected the conserved multimeric ribonuclease P complex. Nodes in light blue represent genes in the corresponding reference protein complexes in Saccharomyces Cerevisiae S288C PPI network. Nodes in red represent genes in the corresponding reference protein complexes in Homo-sapiens. Solid lines denote protein-protein interactions.</figcaption></figure>

<figure><img src="image_7.png" /><figcaption>Figure 3: The conserved origin recognition complex of the Yeast species aligned with an undetermined complex of the Human species detected by KOGAL. Light blue genes represent proteins in the corresponding reference protein complexes in the Saccharomyces cerevisiae S288C PPI network (i.e., left side). Red genes represent proteins in the corresponding reference protein complexes in the Homo sapiens PPI network (i.e., right side). Gray nodes are genes that do not belong to any known protein complexes. The solid lines denote protein-protein interactions, and gray dotted lines indicate semantic similarity between gray nodes with values greater than 0.5 for the cellular component and molecular function terms.</figcaption></figure>

complexes. A high MMR value indicates a strong match between the predicted and reference complexes. Conversely, a low value reflects a partial match, as the list of proteins in the predicted set is divided into different portions, with one portion allowed to match the actual reference complex. It is important to note that the threshold values of $τ_1$ and $τ_2$ are not fixed and may vary depending on the specific
<figure><img src="image_8.png" /><figcaption>Figure 4: Examining the complex connectivity detected by KOGAL. Three types of conserved complexes are aligned between the Yeast (left side) and Human (right side) species: a) Green color: CDC7-DBF7 complex; b) Yellow color: ORC complex (origin recognition complex); c) Blue dark color: MCM complex. The gray nodes are genes that do not belong to any known protein complexes. The solid lines denote protein-protein interactions.</figcaption></figure>

species, the model being used, and the desired clustering outcome. It is common to iterate and experiment with different threshold values to assess their impact on the resulting clusters and evaluate their quality. Ultimately, the choice of threshold involves a trade-off between including enough similar proteins to form meaningful clusters while avoiding the inclusion of unrelated or spurious proteins. For instance, we chose a threshold value of 0.1 for $τ_1$ in KOGAL-TransE, KOGAL-TransR, and KOGAL-DistMult. On the other hand, the values of $τ_1$ for KOGAL-MPath and KOGAL-RC are 0.2 and 0.3, respectively. We chose these different values of $τ_1$ according to the KOGAL variants since they provide the best biological alignment quality in terms of ACC, PPV, GC, Sensitivity, CIQ, and runtime ratio.

Figures 2 and 3 depict two conserved protein complexes identified by KOGAL, highlighting two discussion scenarios. The first scenario identifies the conserved multimeric ribonuclease P complex between Yeast and Human. Meanwhile, all nodes represent genes in the corresponding reference protein complexes in Yeast and Human PPI networks (cf. Figure 2). The second scenario (cf. Figure 3) involves identifying genes or proteins (i.e., gray nodes) that do not belong to the
Yeast or Human reference protein complexes. However, there is a semantic simi-
larity between genes of the compared species (i.e., gray dotted lines) with a value
greater than 0.5 for the cellular component and molecular function terms. Bearing
in mind that the reference complexes are incomplete, a newly identified complex
that does not match any of the reference complexes may be correct. However, it
is always an indeterminate complex. Meanwhile, we can assess the conformity
of the two conserved reference complexes by calculating the semantic similarity
of cellular component ontology (CCO) terms between the protein members for
each compared cluster, considering that the protein complex should be located in
the same cellular component. Figure 3 depicts that the two aligned protein com-
plexes include relevant proteins, such as TSG101, RAD18, ATXN1, and UBE2I
in the conserved protein complex in the Human PPI network and CDC6, CDC28,
and MCM2 in the Yeast protein complex. Therefore, this reflects the importance
of elaborating another conserved reference complex (i.e., the new gold standard),
which can rely on the semantic similarity between the gene ontology (GO) terms
for Human and Yeast proteins. Table 7 depicts that the KOGAL variant results
are enhanced in terms of *Frac*, *ACC*, and *MMR* values since the second gold
standard reference contains 1,212 and the first gold standard reference contains
2,193 conserved complexes. Therefore, elaborating on an accurate and complete
conserved complex could assess the actual performance of the KOGAL approach,
especially for evaluating the conserved Yeast-Human complexes. Moreover, the
high number of predicted complexes performed by KOGAL-TransE, KOGAL-
TransR, and KOGAL-DistMult can be deduced from the results since the strat-
egy of the expansion of KOGAL, which is based on the calculation of the edge
score from the KGE, can lead to predicting composed clusters with overlapping
protein complexes with dense regions related by many PPI. Complementing this,
KOGAL-MPath and KOGAL-DIPCA exhibit superior *Sn* values in the Human-
Yeast alignment.

Therefore, the influence of enlarging the scope of the initial clusters can be
depicted in Figure 4, an example of a predicted complex that incorporates the
CDC7-DBF7 complex, ORC complex, and MCM complex. The predicted com-
plexes show high connectivity between them. Overall, each protein or gene could
have myriad functions, which leads the protein to be affiliated with more than one
complex.

The integration of the metabolic pathway for each protein in order to capture
the relationships between proteins and their associated pathways improves the
KOGAL results, as is evident. For that reason, expanding the knowledge graph
by incorporating additional biological knowledge resources, such as biological
ontologies (e.g., Gene Ontology), will enrich the semantic representation of the knowledge graph and enhance the contextual information available for seed generation. On the other hand, we integrated knowledge from different species, such as the Mus-musculus species, in our knowledge graph (cf. Table 1), since mouse models are used to signal disease risks to aid in the evaluation of potential vaccines and drug development, as well as determining the influence of different immune responses [39]. Therefore, we aim to deduce an alignment between the PPI networks for Homo sapiens, Mus-musculus, and the coronavirus species to discover potential viral infections for known diseases. Specifically, we can apply the alignment to the virus-host protein-protein interaction networks between Homo sapiens and coronavirus proteins to discover more conserved edges or common viral infections [6]. The novel approach can rely on other similarity functions between two proteins or genes using protein domain vectors [52] to enhance the quality of the prediction of protein complexes. Another task ahead involves computing the value of the edge score (i.e., local and global score) through the integration of the temporal knowledge graph (TKG), which is based on a set of context for facts and the temporal consistency of the knowledge [20, 21]. The calculation of each edge score should account for the dynamic, evolving, and time-varying nature of PPI networks, inspired by HE-SNE [8]. By treating new protein interactions and annotations as streaming events, KOGAL can continuously update its alignment matrix and refine conserved protein complexes as new data becomes available. This event-driven approach ensures that KOGAL remains aligned with the latest biological discoveries, effectively addressing the challenge of evolving PPI networks and the dynamic behavior of proteins.

Our proposed KOGAL approach stands out by leveraging various types of relationships, including direct interactions and co-membership in biological complexes, to compute both local and global edge scores for network alignment. This enables KOGAL to capture diverse biological contexts, enhancing the accuracy and robustness of the alignments. A promising direction to further improve KOGAL involves incorporating disentangled embeddings [7], which represent different biological features such as protein sequences, metabolic pathways, ontologies, and interaction networks. This would allow KOGAL to capture mutually exclusive biological properties and improve the interpretability of the alignment results. For instance, the KOGAL approach could benefit from the GNN-based disentangled encoder used in the DisenSemi framework [7]. The GNN acts as a multi-channel encoder that decomposes the graph into interpretable factor graphs, extracts disentangled embeddings, and ensures that these representations remain semantically relevant for both supervised and unsupervised tasks through mutual
information-based regularization.

It is important to note that we utilized the DistMult model due to its widespread use as a bilinear method for capturing pairwise relationships in knowledge graphs. DistMult is computationally efficient and particularly effective for modeling symmetric relations, such as *direct interactions* and *co-membership* in biological complexes, which are central to our approach. Moreover, this model has been extensively validated across various biological datasets and tasks, demonstrating its robustness in representing interactions within biological networks. Our primary goal was to establish a baseline for edge scoring using a well-known and interpretable model before exploring more advanced embedding techniques, including RotatE [5], hyperbolic embeddings [4], and model based on fuzzy set representation learning [3]. However, DistMult has limitations in handling uncertain relationships commonly observed in biological data, such as partial membership in biological pathways or context-specific interactions. The recently proposed FUSE framework [3] for fuzzy set embeddings offers a promising alternative to address these challenges by incorporating uncertainty and capturing soft membership degrees between entities, thereby enhancing the flexibility and interpretability of network representations, particularly in the context of temporal knowledge graph computations.

## 5.1. Performance Analysis of KOGAL Variants Across Diverse Species Alignments

As detailed in Table 10 (see Appendix B) and Figure 5, the performance of the KOGAL variants across diverse species alignments reveals significant trends that highlight their adaptability and effectiveness in addressing the challenges of local network alignment. By integrating advanced clustering algorithms and knowledge graph embeddings, KOGAL variants demonstrate robust performance in aligning networks with varying levels of evolutionary divergence and functional complexity. Unlike the alignment of Human and Yeast species, where KOGAL variants utilize KGEs with $\tau_2 = 0.3$ to generate the initial alignment by default through the IPCA technique, the alignment of other eukaryotic species required further optimization to address the increased variability in their PPI networks. To this end, we fine-tuned the KOGAL-TransE variant to incorporate the MCODE technique for detecting densely connected regions within certain PPI networks and applied a similarity filtering threshold of $\tau_2 = 0.5$. This threshold was carefully selected to retain protein pairs with medium sequence similarity, ensuring that the initial alignment captures biologically meaningful correspondences between conserved
<figure><img src="image_9.png" /><figcaption>Figure 5: Comparison of network aligners based on normalized average scores across 10 pairwise alignments: This radar chart illustrates the performance of five network aligners (represented by colored lines) in aligning ten selected pairs of networks (i.e, Human vs Yeast, Human vs Mouse, Human vs Droso, Human vs Celeg, Mouse vs Yeast, Droso vs Yeast, Celeg vs Yeast, Mouse vs Celeg, Celeg vs Droso and Mouse vs Droso). The scores for each aligner represent the averages of the metrics obtained from the alignments, normalized to a range of [0, 1] based on the best-performing aligner for each metric. Aligners closer to the outer edges demonstrate superior performance across the evaluated metrics.</figcaption></figure>

proteins across species. We opted for $τ_2 = 0.5$ because increasing the threshold resulted in significantly fewer alignments, primarily due to the low cosine similarity between the embedding vectors of proteins from different species. This adjustment allows KOGAL-TransE to expand its scope in detecting conserved protein complexes by accommodating variations in sequence similarity, a crucial factor when aligning eukaryotic species. The MCODE-based approach further enhances the algorithm's ability to prioritize functionally conserved modules, which are more likely to be preserved across species despite the evolutionary divergence in protein sequences.

Considering Human-Mouse Alignment, KOGAL variants consistently outperform AlignNemo, LePrimAlign, and NetworkBLAST in CIQ, sensitivity, and
NCV, underscoring their ability to identify biologically meaningful clusters and ensure comprehensive coverage of protein-protein interactions (PPIs). These metrics reflect KOGAL's strength in adapting to the intricate structure of Human and Mouse networks, which are dense, highly annotated, and evolutionarily conserved. However, LePrimAlign achieves superior performance in GS3, NCV-GS3, and ICQ, indicating its strength in preserving topological consistency and functional coherence across aligned clusters. Additionally, LePrimAlign's better results in MNE suggest its precision in maintaining alignment accuracy, possibly owing to its focus on minimizing mismatches during the alignment process. The challenge in aligning Human and Mouse networks stems from their complex and highly annotated interactomes, which share significant evolutionary conservation yet exhibit nuanced differences in functional pathways. KOGAL's capability to adapt to these similarities and differences underscores its strength in leveraging knowledge graph embeddings and clustering algorithms for nuanced alignments.

In case of the Human-Droso alignment, KOGAL-DIPCA and KOGAL-DMCODE variant outperform competing approaches in CIQ, sensitivity, and NCV, highlighting their ability to detect functional clusters despite the evolutionary distance between the two compared species. Interestingly, KOGAL-TransE leads in GS3, reflecting its strength in maintaining global structural integrity. However, LePrimAlign achieves the best results for MNE and ICQ, while NetworkBLAST excels in GC, underlining its capacity to align functionally annotated proteins effectively. The divergence between Human and Drosophila melanogaster, despite their shared eukaryotic ancestry, is profound, particularly at the level of amino acid sequence divergence. These results suggest that KOGAL variants, especially those integrating DIPCA and MCODE, effectively capture functional similarities, whereas methods like NetworkBLAST benefit from more conservative alignment strategies focusing on GO term consistency.

Under the Human and Celeg PPI networks alignment, KOGAL-TransE outperforms other approaches in terms of NCV, NCV-GS3, and sensitivity, reflecting its ability to identify extensive and biologically relevant alignments. Meanwhile, KOGAL-DIPCA leads in CIQ, emphasizing its proficiency in constructing dense and coherent interaction clusters. LePrimAlign and NetworkBLAST, respectively, excel in MNE and GC, indicating their effectiveness in maintaining alignment precision and functional coherence. The Human and Celeg alignment illustrates the complexities of mapping proteins between highly divergent species with significant differences in annotation depth and evolutionary divergence. KOGAL-TransE's success in this context highlights the value of incorporating semantic embeddings derived from knowledge graphs.
The Mouse-Yeast Alignment leads KOGAL-TransE to achieve the best performance for NCV, CIQ, and MNE, showcasing its capability to bridge the gap between species with vastly different interactome sizes and annotation levels. NetworkBLAST, however, excels in GS3 and GC, emphasizing its strength in preserving functional annotations across alignments. Notably, all KOGAL variants significantly outperform competitors in CIQ, demonstrating their ability to create biologically meaningful clusters. The alignment of a mammalian species like a mouse with a unicellular organism like Yeast presents unique challenges, given their vastly different network densities and evolutionary trajectories. The alignment results for the remaining species reveal distinct performance trends among the evaluated methods. For the Droso-Yeast alignment, KOGAL-TransE, KOGAL-DIPCA, and AlignNemo demonstrate strong performance in NCV and MNE, with the KOGAL variants particularly excelling in CIQ. However, AlignNemo achieves the best performance in ICQ, showcasing its ability to preserve high-quality clusters. Similarly, in the Celeg-Yeast alignment, all KOGAL variants outperform competitors in CIQ, highlighting their consistency in cluster formation, while AlignNemo leads in ICQ, and LePrimAlign excels in MNE.

For the Mouse-Celeg alignment, KOGAL-DIPCA, KOGAL-DMCODE, and AlignNemo demonstrate strong performance in NCV and ICQ, while other metrics are more evenly distributed across methods. In the Celeg-Droso alignment, KOGAL-DIPCA and AlignNemo lead in NCV, with KOGAL-DIPCA also excelling in CIQ. AlignNemo achieves the highest scores in MNE, whereas NetworkBLAST outperforms others in GC. Lastly, in the Mouse-Droso alignment, KOGAL-DIPCA emerges as the top performer in NCV and CIQ, underlining its effectiveness in aligning species with significant evolutionary divergence. The results highlight that KOGAL variants effectively address these challenges, with each variant excelling in specific metrics depending on the alignment context. Notably, the KOGAL variant based on degree centrality and protein sequence similarity (i.e., BLAST bit scores) consistently outperforms the KOGAL-TransE variant in terms of CIQ and GC values. This indicates that incorporating degree centrality and sequence-based similarities not only preserves critical network interactions but also improves the functional correctness of alignments.

The integration of advanced techniques such as knowledge graph embeddings, IPCA, and MCODE further enhances KOGAL's flexibility and robustness, enabling it to adapt to the diverse requirements of local network alignment across species. These findings underscore the importance of combining structural, functional, and sequence-based features to achieve biologically meaningful alignments, particularly when dealing with the complexities of interspecies PPI networks. Our
findings indicate that KOGAL-DIPCA, which integrates degree centrality with the IPCA algorithm, achieves a high sensitivity score, underscoring its effectiveness in identifying biologically meaningful protein alignments, as depicted by Figure 5. Incorporating degree centrality enables the method to prioritize hub proteins, which play crucial roles in maintaining the structure and function of PPI networks. These hub proteins often act as key regulators in essential cellular processes and form the core of functional modules, thereby contributing to network stability and ensuring accurate clustering of related proteins. By emphasizing hub proteins, KOGAL-DIPCA enhances the detection of functionally cohesive clusters, particularly for proteins sharing GO annotations, thereby improving the biological relevance of the alignment.

The high sensitivity score achieved by KOGAL-DIPCA further highlights its ability to align proteins that participate in the same biological pathways or protein complexes, even across species with divergent PPI network topologies. This is especially valuable in local network alignment, where the primary objective is to uncover functionally conserved substructures. In this context, integrating degree centrality helps focus the alignment on biologically significant proteins rather than solely on structural similarities, resulting in more accurate and meaningful functional clusters. Furthermore, the approach holds significant potential for the integration of REACT (Reasoning and Action) agents and large language models (LLMs) tailored to the biomedical domain [1]. The alignment of conserved complexes produced by KOGAL across different species could be leveraged by an agent-driven LLM to add or complete entries in a KG [2] which could be indexed in a vector database, enabling semantic searches and context-aware queries.

## 6. Time Complexity and Scalability

Figures 6 depicts the runtime required for each pairwise alignment. The runtime primarily depends on the centrality-based selection of proteins and the number of top *N* hub proteins chosen for the alignment process. Specifically, we observed that increasing the number of selected hub proteins (i.e. top *N*) results in a higher runtime, as the alignment algorithm explores a larger search space of potential seed pairs (cf. Table 9). Additionally, the threshold applied to filter similarity scores between seed pairs further impacts the runtime, where lower thresholds lead to longer runtimes due to increased candidate pairs for alignment. This analysis underscores the trade-off between accuracy and computational cost, showing that the choice of centrality-based hubs and the similarity filtering criteria significantly influence the scalability of KOGAL.
<figure><img src="image_10.png" /><figcaption>Figure 6: Runtime (in seconds) for each approach across the different datasets. Red indicates that either (i) the approach was able to process the dataset but produced an empty alignment (as in the case of the LePrimAlign approach), or (ii) the approach could not complete execution within a reasonable timeframe (e.g., datasets Human-Yeast, Human-Mouse, and Human-Celeg, where the alignment process of AlignNemo exceeded three days and failed to terminate). All experiments were conducted on a high-performance computing server equipped with two AMD EPYC 9454 48-Core Processors, 770 GB of RAM, and dual NVIDIA H100 SXM5 GPUs with 80 GB of memory each.</figcaption></figure>

High-degree nodes, often referred to as hubs, are highly connected proteins that play a critical role in PPI networks. While these nodes are biologically significant and likely to belong to conserved complexes, utilizing them as seeds for alignment can significantly impact the computational complexity of the KOGAL approach. Specifically, aligning high-degree nodes requires comparing a substantially larger set of connections across species, leading to an expanded search space that introduces more nodes to explore in the neighborhood. As a result, the number of pairwise similarity calculations increases proportionally to the number of neighboring nodes, thereby contributing to increased computational overhead. This computational challenge is particularly evident in the alignment of Human and Yeast PPI networks, where the KOGAL algorithm requires more time compared to alignments between other species pairs. Human and Yeast networks tend to contain a higher number of hub proteins, resulting in more extensive local align-
ment expansions and additional iterations for filtering based on cosine similarity thresholds.

# 7. Conclusions

The novel proposed approach demonstrates competitive performance, outperforming several state-of-the-art algorithms, particularly in detecting conserved complexes between Human and Yeast species. The integration of KGE during the alignment process has proven instrumental, yielding promising results by capturing both structural and functional similarities across proteins. This highlights the potential of leveraging KGE to enrich the alignment process with biologically meaningful insights. To address the limitations posed by the incompleteness of the KG and enhance the robustness of the alignment process, we developed two specialized variants: KOGAL-DIPCA and KOGAL-DMODE. These variants incorporate degree centrality and protein sequence similarity (e.g., BLAST bit scores) as complementary strategies, ensuring accurate alignments even when the KG lacks comprehensive information. By emphasizing sequence similarity and structural importance through degree centrality, these variants effectively mitigate the challenges of incomplete data and deliver biologically significant results.

We integrated degree centrality to prioritize hub proteins in PPI networks, as these key nodes often participate in essential cellular processes and critical signaling pathways. By combining degree centrality with knowledge graph embeddings, the KOGAL framework enhances alignment by focusing on biologically significant proteins. Additionally, KOGAL is generalizable to other biological networks and can incorporate complex relationships, such as those captured by fuzzy set embeddings, to improve the interpretability of network alignments.

# Funding

This research did not receive any specific grant from funding agencies in the public, commercial, or not-for-profit sectors.

# Appendix A. Metrics for conserved protein complex prediction for pairwise PPI networks

The conserved protein complexes deduced from the PPI network alignment are evaluated between the reference complexes and the newly discovered conserved complexes. From now on, we only consider predicted conserved protein complexes containing more than three proteins for any species.
### A.1. Fraction of the matched reference conserved protein complexes

Given a conserved reference complex, represent a pairwise species

$$ Cmplx_{ref} = \{refcmplx_{spec1}, refcmplx_{spec2}\} \quad (5) $$

and a predicted conserved complexes

$$ Cmplx_{pred} = \{predcmplx_{spec1}, predcmplx_{spec2}\}. \quad (6) $$

Therefore, `refcmplx_{spec1}` and `predcmplx_{spec1}` are complexes in the first species and `refcmplx_{spec2}` and `predcmplx_{spec2}` are complexes in the second species. Meanwhile, `predcmplx` match `refcmplx`, if the neighborhood affinity scores for each compared module or complex $w(refcmplx_1, predcmplx_1) \ge 0.25$ and $w(refcmplx_2, predcmplx_2) \ge 0.25$.

The neighborhood affinity score between two complexes is computed using these formulas:

$$ \begin{aligned} w(refcmplx, predcmplx) &= \frac{|refcmplx \cap predcmplx|}{|refcmplx|} \cdot \frac{|refcmplx \cap predcmplx|}{|predcmplx|} \\ &= \frac{|refcmplx \cap predcmplx|^2}{|refcmplx| |predcmplx|}, \quad (7) \end{aligned} $$

where `refcmplx` and `predcmplx` are two protein collections. We computed the amount of matched protein complexes with an overlap score $w$ (c.f., Equation 7) greater than 0.25.

As a result, we can calculate the fraction of aligned reference conserved complexes. The reference conserved complex set is assumed to be $R$, and the predicted conserved complex set is assumed to be $P$. As a result, the fraction of aligned reference conserved complexes can be calculated as =

$$ \text{frac} = \frac{|C|}{|R|} \quad (8) $$

where

$$ C = \{S | w(refcmplx_1, predcmplx_1) \ge 0.25, \text{ and } w(refcmplx_2, predcmplx_2) \ge 0.25 \ \forall refcmplx \in R, \forall predcmplx \in P\} \quad (9) $$
## A.2 Accuracy score

Let $n$ be the number of references conserved complex:

$$ Cmplx_{ref}^{j} = \{refcmplx_{spec1}^{j}, refcmplx_{spec2}^{j}\} : j \in \{1, 2, 3, 4, \dots, n\} \quad (10) $$

Then, $m$ is the number of the predicted conserved complexes:

$$ Cmplx_{pred}^{i} = \{predcmplx_{spec1}^{i}, predcmplx_{spec2}^{i}\} : i \in \{1, 2, \dots, m\} \quad (11) $$

with $refcmplx_{spec1}^{j}$ and $predcmplx_{spec1}^{j}$ are complexes belonging to the first species and $refcmplx_{spec2}^{i}$ and $predcmplx_{spec2}^{i}$ are complexes inner the second species. Let $total_{ij}$ denote the number of proteins that pertain in the two references conserved complex $Cmplx_{ref}^{j}$ and the predicted conserved complex $Cmplx_{pred}^{i}$, and $nbr_{j}$ refer for the number of proteins in the $j$th reference conserved complex. Namely,

$$ total_{ij} = |refcmplx_{spec1}^{j} \cap predcmplx_{spec1}^{i}| + |refcmplx_{spec2}^{j} \cap predcmplx_{spec2}^{i}| \quad (12) $$

and

$$ n_{br,j} = |refcmplx_{spec1}^{j} \cup refcmplx_{spec2}^{j}| \quad (13) $$

Then, complex-wise sensitivity ($Sn$) and positive-predictive value ($PPV$) is computed by

$$ Sn = \frac{\sum_{j=1}^{n} \max_{i=1,2,\dots,m} total_{ij}}{\sum_{j=1}^{n} n_{br,j}}; PPV = \frac{\sum_{i=1}^{m} \max_{j=1,2,\dots,n} total_{ij}}{\sum_{i=1}^{m} \sum_{j=1}^{n} total_{ij}} \quad (14) $$

Therefore, the ACC score is the geometric mean of $Sn$ and $PPV$:

$$ ACC = \sqrt{Sn \times PPV} \quad (15) $$

## A.3. The maximum matching ratio (MMR)

The MMR is a way to determine how much the conserved reference complex and the predicted conserved complexes match up. The MMR reflects the maximum sum of weights of edges in a bipartite graph, where the two ensembles of proteins constitute reference conserved complexes $C$ and predict conserved complexes $S$. The bipartite graph $MatrBip_{n \times m}$ is a weighted matrix, where each weight $MatrBip_{ij}$ is the neighborhood affinity score $w(c_i, s_j)$ computed by equation 7 for the corresponding edge among conserved complexes $c_i$ and $s_j$. For
efficacy, we merely applied $B_{ij} \ge 0.25$. Therefore, the MMR metric is computed using this equation:

$$ 
\begin{aligned}
\max: & \frac{1}{|C|} \sum_{i=1}^{n} \sum_{j=1}^{m} \mathrm{MatrBip}_{ij} \sigma_{c_i, s_j} \\
& s.t. \quad \sum_{j=1}^{m} \sigma_{c_i, s_j} \le 1 \\
& \qquad \sum_{i=1}^{n} \sigma_{c_i, s_j} \le 1,
\end{aligned} 
\quad (16) $$

where $\sigma$ is an criteria function with $\sigma_{c_i,s_j} = 1$ when the edge amid conserved complexes $c_i$ and $s_j$ is chosen, and in other ways, the function is computed as $\sigma_{c_i,s_j} = 0$.

### A.4. Coverage, ME and MNE

To assess the GO consistency, we evaluated the prediction results using the coverage, the mean entropy, and the mean normalized entropy. We applied the coverage metric to compute the number of clusters containing proteins from two species. Therefore, an ideal alignment should assign most proteins to a cluster. We used the number of proteins in the whole set of proteins to figure out what percentage of the alignment was covered.

We used the mean entropy (ME) (c.f., equation 17) and the mean normalized entropy (MNE) (c.f., equation 18) of the alignments to assess the functional coherence of the alignments, which is the same method as in IsoRank-N [29] conforming to its GO annotations.

$$ H(S_v^*) = H(p_1, p_2, \dots, p_d) = - \sum_{i=1}^{d} p_i \log p_i \quad (17) $$

$$ \tilde{H}(S_v^*) = \frac{1}{\log d} H(S_v^*) \quad (18) $$

## Appendix B. Parameters tuning of the considered approaches

The parameters of the compared methods were set to the values recommended in their papers. Meanwhile, KOGAL has two adjustable parameters: we chose $\tau_1 = 0.1$ as the threshold value, and for tuning an equal contribution between the local and global edge scores, we fixed $\alpha = 0.5$ and $\tau_2 = 0.5$, as they gave us
<table><caption>Table 10: Evaluations of the alignment approaches based on the alignment between 9 species.</caption><thead><tr><th>Approaches</th><th>NCV</th><th>GS<sup>3</sup></th><th>NCV - GS<sup>3</sup></th><th>GC</th><th>Sensitivity</th><th>CIQ</th><th>ICQ</th><th>MNE</th></tr></thead><tbody><tr><td colspan="9"><strong>Human-Mouse</strong></td></tr><tr><td>KOGAL-TransE</td><td>0.249</td><td>0.02</td><td>0.065</td><td>0.867</td><td>0.110</td><td><strong>0.395</strong></td><td>0.043</td><td><strong>4.579</strong></td></tr><tr><td>KOGAL-DIPCA</td><td><strong>0.376</strong></td><td>0.01</td><td>0.049</td><td>0.872</td><td><strong>0.137</strong></td><td>0.340</td><td>0.011</td><td>6.194</td></tr><tr><td>KOGAL-DMCODE</td><td>0.189</td><td>0.01</td><td>0.044</td><td>0.953</td><td>0.078</td><td>0.368</td><td>0.064</td><td>5.298</td></tr><tr><td>AlignNemo</td><td>*</td><td>*</td><td>*</td><td>*</td><td>*</td><td>*</td><td>*</td><td>*</td></tr><tr><td>LePrimAlign</td><td>0.072</td><td><strong>0.13</strong></td><td>0.098</td><td><strong>0.957</strong></td><td>0.055</td><td>0.064</td><td><strong>0.079</strong></td><td>4.886</td></tr><tr><td>NetworkBLAST</td><td>0.064</td><td>0.01</td><td>0.027</td><td>0.903</td><td>0.037</td><td>0.131</td><td>0.011</td><td>6.826</td></tr><tr><td colspan="9"><strong>Human-Droso</strong></td></tr><tr><td>KOGAL-TransE</td><td>0.001</td><td><strong>0.29</strong></td><td>0.023</td><td>0.557</td><td>0.0008</td><td>0.033</td><td>0.046</td><td>4.598</td></tr><tr><td>KOGAL-DIPCA</td><td><strong>0.329</strong></td><td>0.01</td><td><strong>0.040</strong></td><td>0.565</td><td><strong>0.128</strong></td><td><strong>0.461</strong></td><td>0.016</td><td>5.535</td></tr><tr><td>KOGAL-DMCODE</td><td>0.177</td><td>0.01</td><td>0.034</td><td>0.703</td><td>0.079</td><td>0.388</td><td>0.072</td><td>4.816</td></tr><tr><td>AlignNemo</td><td>*</td><td>*</td><td>*</td><td>*</td><td>*</td><td>*</td><td>*</td><td>*</td></tr><tr><td>LePrimAlign</td><td>0.057</td><td>0.03</td><td><strong>0.040</strong></td><td>0.783</td><td>0.035</td><td>0.316</td><td><strong>0.080</strong></td><td><strong>4.479</strong></td></tr><tr><td>NetworkBLAST</td><td>0.133</td><td>0.01</td><td>0.035</td><td><strong>0.938</strong></td><td>0.064</td><td>0.051</td><td>0.023</td><td>6.070</td></tr><tr><td colspan="9"><strong>Human-Celeg</strong></td></tr><tr><td>KOGAL-TransE</td><td><strong>0.295</strong></td><td>0.01</td><td><strong>0.048</strong></td><td>0.326</td><td><strong>0.108</strong></td><td>0.327</td><td>0.0003</td><td>4.379</td></tr><tr><td>KOGAL-DIPCA</td><td>0.110</td><td>0.01</td><td>0.034</td><td>0.592</td><td>0.053</td><td><strong>0.472</strong></td><td>0.001</td><td>6.456</td></tr><tr><td>KOGAL-DMCODE</td><td>0.171</td><td>0.01</td><td>0.038</td><td>0.704</td><td>0.0604</td><td>0.376</td><td><strong>0.099</strong></td><td>4.411</td></tr><tr><td>AlignNemo</td><td>*</td><td>*</td><td>*</td><td>*</td><td>*</td><td>*</td><td>*</td><td>*</td></tr><tr><td>LePrimAlign</td><td>0.057</td><td><strong>0.03</strong></td><td>0.044</td><td>0.804</td><td>0.024</td><td>0.247</td><td>0.077</td><td><strong>3.915</strong></td></tr><tr><td>NetworkBLAST</td><td>0.072</td><td>0.02</td><td>0.034</td><td><strong>0.897</strong></td><td>0.030</td><td>0.037</td><td>0.064</td><td>6.182</td></tr><tr><td colspan="9"><strong>Mouse-Yeast</strong></td></tr><tr><td>KOGAL-TransE</td><td><strong>0.422</strong></td><td>0.02</td><td>0.095</td><td>0.644</td><td>0.050</td><td><strong>0.559</strong></td><td>0.005</td><td><strong>3.128</strong></td></tr><tr><td>KOGAL-DIPCA</td><td>0.232</td><td>0.02</td><td>0.064</td><td>0.802</td><td>0.040</td><td>0.365</td><td>0.013</td><td>4.813</td></tr><tr><td>KOGAL-DMCODE</td><td>0.059</td><td>0.07</td><td>0.063</td><td>0.921</td><td>0.012</td><td>0.400</td><td><strong>0.075</strong></td><td>4.897</td></tr><tr><td>AlignNemo</td><td>0.268</td><td>0.01</td><td>0.043</td><td><strong>0.937</strong></td><td><strong>0.053</strong></td><td>0.029</td><td>0.061</td><td>4.488</td></tr><tr><td>LePrimAlign</td><td>0.062</td><td>0.20</td><td><strong>0.112</strong></td><td>0.761</td><td>0.012</td><td>0.083</td><td>0.040</td><td>4.311</td></tr><tr><td>NetworkBLAST</td><td>0.004</td><td><strong>1.00</strong></td><td>0.064</td><td><strong>0.937</strong></td><td>0.0006</td><td>0</td><td>0.050</td><td>6.55</td></tr><tr><td colspan="9"><strong>Droso-Yeast</strong></td></tr><tr><td>KOGAL-TransE</td><td><strong>0.452</strong></td><td>0.01</td><td><strong>0.076</strong></td><td>0.375</td><td><strong>0.069</strong></td><td><strong>0.518</strong></td><td>0.013</td><td><strong>3.028</strong></td></tr><tr><td>KOGAL-DIPCA</td><td>0.413</td><td>0.01</td><td>0.054</td><td>0.526</td><td>0.065</td><td>0.432</td><td>0.029</td><td>3.587</td></tr><tr><td>KOGAL-DMCODE</td><td>0.060</td><td>0.01</td><td>0.026</td><td>0.672</td><td>0.015</td><td>0.450</td><td>0.118</td><td>3.247</td></tr><tr><td>AlignNemo</td><td>0.414</td><td>0</td><td>0.039</td><td>0.825</td><td>0.062</td><td>0.018</td><td><strong>0.215</strong></td><td>2.520</td></tr><tr><td>LePrimAlign</td><td>0.043</td><td><strong>0.12</strong></td><td>0.072</td><td>0.717</td><td>0.011</td><td>0.137</td><td>0.094</td><td>3.250</td></tr><tr><td>NetworkBLAST</td><td>0.031</td><td>0.03</td><td>0.031</td><td><strong>0.960</strong></td><td>0.009</td><td>0.171</td><td>0.078</td><td>5.589</td></tr><tr><td colspan="9"><strong>Celeg-Yeast</strong></td></tr><tr><td>KOGAL-TransE</td><td>0.083</td><td>0.03</td><td>0.045</td><td>0.190</td><td>0.011</td><td>0.514</td><td>0.0001</td><td>2.492</td></tr><tr><td>KOGAL-DIPCA</td><td>0.083</td><td>0.03</td><td>0.045</td><td>0.190</td><td><strong>0.041</strong></td><td>0.477</td><td>0.027</td><td>3.395</td></tr><tr><td>KOGAL-DMCODE</td><td>0.059</td><td>0.02</td><td>0.036</td><td>0.719</td><td>0.007</td><td><strong>0.524</strong></td><td>0.170</td><td>2.639</td></tr><tr><td>AlignNemo</td><td><strong>0.343</strong></td><td>0.01</td><td>0.043</td><td>0.763</td><td>0.036</td><td>0.029</td><td><strong>0.214</strong></td><td><strong>2.174</strong></td></tr><tr><td>LePrimAlign</td><td>0.041</td><td><strong>0.12</strong></td><td><strong>0.069</strong></td><td>0.709</td><td>0.006</td><td>0.213</td><td>0.107</td><td>2.595</td></tr><tr><td>NetworkBLAST</td><td>0.009</td><td><strong>0.12</strong></td><td>0.034</td><td><strong>0.915</strong></td><td>0.002</td><td>0.044</td><td>0.094</td><td>3.628</td></tr><tr><td colspan="9"><strong>Mouse-Celeg</strong></td></tr><tr><td>KOGAL-TransE</td><td>0.082</td><td><strong>0.04</strong></td><td>0.055</td><td>0.120</td><td>0.012</td><td>0.061</td><td>0</td><td><strong>2.997</strong></td></tr><tr><td>KOGAL-DIPCA</td><td>0.329</td><td>0.01</td><td>0.051</td><td>0.773</td><td>0.053</td><td><strong>0.358</strong></td><td>0.019</td><td>4.963</td></tr><tr><td>KOGAL-DMCODE</td><td>0.100</td><td>0.02</td><td>0.049</td><td>0.887</td><td>0.019</td><td>0.263</td><td>0.075</td><td>4.375</td></tr><tr><td>AlignNemo</td><td><strong>0.425</strong></td><td>0.01</td><td>0.051</td><td>0.834</td><td><strong>0.064</strong></td><td>0.034</td><td><strong>0.127</strong></td><td>3.781</td></tr><tr><td>LePrimAlign</td><td>0.075</td><td><strong>0.04</strong></td><td><strong>0.056</strong></td><td>0.892</td><td>0.022</td><td>0.212</td><td>0.048</td><td>4.236</td></tr><tr><td>NetworkBLAST</td><td>0.010</td><td>0</td><td>0</td><td><strong>0.923</strong></td><td>0.004</td><td>0</td><td>0.053</td><td>7.413</td></tr><tr><td colspan="9"><strong>Celeg-Droso</strong></td></tr><tr><td>KOGAL-TransE</td><td>0.017</td><td><strong>0.09</strong></td><td>0.039</td><td>0.308</td><td>0.003</td><td>0.181</td><td>0.034</td><td>3.178</td></tr><tr><td>KOGAL-DIPCA</td><td>0.458</td><td>0.01</td><td>0.050</td><td>0.474</td><td><strong>0.052</strong></td><td><strong>0.420</strong></td><td>0.032</td><td>3.373</td></tr><tr><td>KOGAL-DMCODE</td><td>0.089</td><td>0.01</td><td>0.035</td><td>0.701</td><td>0.016</td><td>0.349</td><td>0.114</td><td>3.127</td></tr><tr><td>AlignNemo</td><td><strong>0.480</strong></td><td>0.01</td><td><strong>0.064</strong></td><td>0.770</td><td>0.051</td><td>0.028</td><td><strong>0.163</strong></td><td><strong>2.230</strong></td></tr><tr><td>LePrimAlign</td><td>*</td><td>*</td><td>*</td><td>*</td><td>*</td><td>*</td><td>*</td><td>*</td></tr><tr><td>NetworkBLAST</td><td>0.011</td><td><strong>0.09</strong></td><td>0.031</td><td><strong>0.925</strong></td><td>0.003</td><td>0</td><td>0.048</td><td>4.068</td></tr><tr><td colspan="9"><strong>Mouse-Droso</strong></td></tr><tr><td>KOGAL-TransE</td><td>0.023</td><td><strong>0.10</strong></td><td>0.048</td><td>0.709</td><td>0.005</td><td>0.137</td><td>0.038</td><td><strong>3.001</strong></td></tr><tr><td>KOGAL-DIPCA</td><td>0.309</td><td>0.01</td><td>0.049</td><td>0.800</td><td>0.073</td><td><strong>0.216</strong></td><td>0.020</td><td>5.294</td></tr><tr><td>KOGAL-DMCODE</td><td>0.066</td><td>0.02</td><td>0.037</td><td>0.907</td><td>0.025</td><td>0.206</td><td>0.045</td><td>4.823</td></tr><tr><td>AlignNemo</td><td><strong>0.402</strong></td><td>0.01</td><td>0.049</td><td>0.862</td><td><strong>0.090</strong></td><td>0.010</td><td><strong>0.111</strong></td><td>3.763</td></tr><tr><td>LePrimAlign</td><td>0.057</td><td>0.09</td><td><strong>0.072</strong></td><td>0.810</td><td>0.032</td><td>0.203</td><td>0.052</td><td>5.333</td></tr><tr><td>NetworkBLAST</td><td>0.006</td><td>0</td><td>0</td><td><strong>0.956</strong></td><td>0.004</td><td>0</td><td>0.034</td><td>7.270</td></tr></tbody></table>

Note: The best results are indicated in bold concerning each row. Evaluation results marked with "*" indicate that AlignNemo encountered an out-of-memory error during execution. The symbol "-" denotes cases where LePrimAlign failed to detect any alignment clusters, resulting in a number of alignments equal to 0.
the best results in terms of the number of predicted conserved complexes and the ACC metric. On the other side, we selected the embedding dimension of *dim* to be 200 for both nodes and relations. The different models were trained for 300,000 epochs with a batch size of 2,000 and a learning rate of 0.25. We chose these tuning parameters as they provided the best results for the *Frac* and *ACC* metrics.

For the LePrimAlign approach, we selected the value of 0.1 as the threshold for selecting pairs of seed nodes. For both the KOGAL and LePrimAlign approaches, we set 0.02 as the threshold to prevent the joining of insignificant pairs of proteins during the prediction of clusters, as this could lead to clusters of a large size. Additionally, the PPI networks are processed by LePrimAlign, which calculates the similarity between interacting proteins by focusing on the molecular function of each protein. This is achieved using the Topological Clustering Semantic Similarity (TCSS) method [24], which is more efficient than simGIC [25].

## References

[1] M. Bran, A., Cox, S., Schilter, O., Baldassari, C., White, A. & Schwaller, P. Augmenting large language models with chemistry tools. *Nature Machine Intelligence*. pp. 1-11 (2024)

[2] Cheng, S., Zhang, N., Tian, B., Chen, X., Liu, Q. & Chen, H. Editing language model-based knowledge graph embeddings. *Proceedings Of The AAAI Conference On Artificial Intelligence*. 38, 17835-17843 (2024)

[3] Xu, F., Jiang, S., Huang, Z., Luo, X., Zhang, S., Chen, Y. & Sun, Y. FUSE: Measure-Theoretic Compact Fuzzy Set Representation for Taxonomy Expansion. *Findings Of The Association For Computational Linguistics: ACL 2024*. pp. 2707-2720 (2024,8), https://aclanthology.org/2024.findings-acl.158/

[4] Chami, I., Wolf, A., Juan, D., Sala, F., Ravi, S. & Ré, C. Low-dimensional hyperbolic knowledge graph embeddings. *ArXiv Preprint ArXiv:2005.00545*. (2020)

[5] Sun, Z., Deng, Z., Nie, J. & Tang, J. Rotate: Knowledge graph embedding by relational rotation in complex space. *ArXiv Preprint ArXiv:1902.10197*. (2019)
[6] Djeddi, W., Yahia, S. & Diallo, G. Optimizing Global Network Alignment with a Genetic Algorithm: Leveraging Pre-trained Embeddings for Protein Sequences and Gene Ontology Terms. *IEEE Transactions On Computational Biology And Bioinformatics*. pp. 1-14 (2024)

[7] Wang, Y., Luo, X., Chen, C., Hua, X., Zhang, M. & Ju, W. DisenSemi: Semi-Supervised Graph Classification via Disentangled Representation Learning. *IEEE Transactions On Neural Networks And Learning Systems*. pp. 1-13 (2024)

[8] Wang, Y., Shen, J., Song, Y., Wang, S. & Zhang, M. HE-SNE: Heterogeneous Event Sequence-based Streaming Network Embedding for Dynamic Behaviors. *2022 International Joint Conference On Neural Networks (IJCNN)*. pp. 1-8 (2022)

[9] Wang, Y., Li, Y., Li, S., Song, W., Fan, J., Gao, S., Ma, L., Cheng, B., Cai, X., Wang, S. & Others Deep graph mutual learning for cross-domain recommendation. *International Conference On Database Systems For Advanced Applications*. pp. 298-305 (2022)

[10] Milano, M., Zucco, C., Settino, M. & Cannataro, M. An Extensive Assessment of Network Embedding in PPI Network Alignment. *Entropy*. **24**, 730 (2022)

[11] Alkan, F. & Erten, C. BEAMS: backbone extraction and merge strategy for the global many-to-many alignment of multiple PPI networks. *Bioinformatics*. **30**, 531-539 (2013,12), https://doi.org/10.1093/bioinformatics/btt713

[12] Kanehisa, M., Furumichi, M., Tanabe, M., Sato, Y. & Morishima, K. KEGG: new perspectives on genomes, pathways, diseases and drugs. *Nucleic Acids Research*. **45**, D353-D361 (2017)

[13] Breuza, L., Poux, S., Estreicher, A., Famiglietti, M., Magrane, M., Tognolli, M., Bridge, A., Baratin, D., Redaschi, N., Consortium, U. & Others The UniProtKB guide to the Human proteome. *Database*. **2016** (2016)

[14] Li, M., Chen, J., Wang, J., Hu, B. & Chen, G. Modifying the DPClus algorithm for identifying protein complexes based on new topological structures. *BMC Bioinformatics*. **9**, 1-16 (2008)
[15] Hu, J. & Reinert, K. LocalAli: an evolutionary-based local alignment approach to identify functionally conserved modules in multiple networks. *Bioinformatics*. **31**, 363-372 (2015)

[16] Bader, G. & Hogue, C. An automated method for finding molecular complexes in large protein interaction networks. *BMC Bioinformatics*. **4**, 1-27 (2003)

[17] Wu, M., Li, X., Kwoh, C. & Ng, S. A core-attachment based method to detect protein complexes in PPI networks. *BMC Bioinformatics*. **10**, 1-16 (2009)

[18] Wang, Y., Jeong, H., Yoon, B. & Qian, X. ClusterM: a scalable algorithm for computational prediction of conserved protein complexes across multiple protein interaction networks. *BMC Genomics*. **21**, 1-14 (2020)

[19] Maskey, S. & Cho, Y. LePrimAlign: local entropy-based alignment of PPI networks to predict conserved modules. *BMC Genomics*. **20**, 1-12 (2019)

[20] Liu, Y., Hua, W., Xin, K. & Zhou, X. Context-aware temporal knowledge graph embedding. *International Conference On Web Information Systems Engineering*. pp. 583-598 (2020)

[21] Sadeghian, A., Armandpour, M., Colas, A. & Wang, D. ChronoR: rotation based temporal knowledge graph embedding. *Proceedings Of The AAAI Conference On Artificial Intelligence*. **35**, 6471-6479 (2021)

[22] Guzzi, P., Tradigo, G. & Veltri, P. A Novel Algorithm for Local Network Alignment Based on Network Embedding. *Applied Sciences*. **12**, 5403 (2022)

[23] Liao, C., Lu, K., Baym, M., Singh, R. & Berger, B. IsoRankN: spectral methods for global alignment of multiple protein networks. *Bioinformatics*. **25**, i253-i258 (2009)

[24] Jain, S. & Bader, G. An improved method for scoring protein-protein interactions using semantic similarity within the gene ontology. *BMC Bioinformatics*. **11**, 1-14 (2010)

[25] Pesquita, C., Faria, D., Bastos, H., Ferreira, A., Falcão, A. & Couto, F. Metrics for GO based protein semantic similarity: a systematic evaluation. *BMC Bioinformatics*. **9**, 1-16 (2008)
[26] Wang, M. Deep Graph Library: towards efficient and scalable deep learning on graphs. *ICLR Workshop On Representation Learning On Graphs And Manifolds*., https://par.nsf.gov/biblio/10311680

[27] Zheng, D., Song, X., Ma, C., Tan, Z., Ye, Z., Dong, J., Xiong, H., Zhang, Z. & Karypis, G. DGL-KE: Training Knowledge Graph Embeddings at Scale. *Proceedings Of The 43rd International ACM SIGIR Conference On Research And Development In Information Retrieval*. pp. 739-748 (2020)

[28] Das, J. & Yu, H. HINT: High-quality protein interactomes and their applications in understanding human disease. *BMC Systems Biology*. **6**, 1-12 (2012)

[29] Liao, C., Lu, K., Baym, M., Singh, R. & Berger, B. IsoRankN: spectral methods for global alignment of multiple protein networks. *Bioinformatics*. **25**, i253-i258 (2009)

[30] Menor-Flores, M. & Vega-Rodríguez, M. Boosting-based ensemble of global network aligners for PPI network alignment. *Expert Systems With Applications*. **230** pp. 120671 (2023), https://www.sciencedirect.com/science/article/pii/S0957417423011739

[31] Ciriello, G., Mina, M., Guzzi, P., Cannataro, M. & Guerra, C. AlignNemo: a local network alignment method to integrate homology and topology. *PloS One*. **7**, e38107 (2012)

[32] Mina, M. & Guzzi, P. Improving the robustness of local network alignment: design and extensive assessmentof a markov clustering-based approach. *IEEE/ACM Transactions On Computational Biology And Bioinformatics*. **11**, 561-572 (2014)

[33] Wang, Y., Jeong, H., Yoon, B. & Qian, X. ClusterM: a scalable algorithm for computational prediction of conserved protein complexes across multiple protein interaction networks. *BMC Genomics*. **21**, 1-14 (2020)

[34] Zhang, J., Zain, A., Zhou, K., Chen, X. & Zhang, R. A review of recommender systems based on knowledge graph embedding. *Expert Systems With Applications*. **250** pp. 123876 (2024), https://www.sciencedirect.com/science/article/pii/S0957417424007425

[35] Das, J. & Yu, H. HINT: High-quality protein interactomes and their applications in understanding human disease. *BMC Systems Biology*. **6**, 1-12 (2012)
[36] Djeddi, W., Ben Yahia, S. & Nguifo, E. A novel computational approach for global alignment for multiple biological networks. *IEEE/ACM Transactions On Computational Biology And Bioinformatics.* **15**, 2060-2066 (2018)

[37] Meng, L., Striegel, A. & Milenković, T. Local versus global biological network alignment. *Bioinformatics.* **32**, 3155-3164 (2016)

[38] Yuan, X., Chen, Z., Bu, X., Gao, Z., Zhao, L. & Ma, R. Knowledge graph fine-grained network with attribute transfer for recommendation. *Expert Systems With Applications.* **257** pp. 125074 (2024), https://www.sciencedirect.com/science/article/pii/S0957417424019419

[39] Yuan, L., Tang, Q., Cheng, T. & Xia, N. Animal models for emerging coronavirus: progress and new insights. *Emerging Microbes & Infections.* **9**, 949-961 (2020)

[40] Remm, M., Storm, C. & Sonnhammer, E. Automatic clustering of orthologs and in-paralogs from pairwise species comparisons. *Journal Of Molecular Biology.* **314**, 1041-1052 (2001)

[41] Marcotte, E., Pellegrini, M., Ng, H., Rice, D., Yeates, T. & Eisenberg, D. Detecting protein function and protein-protein interactions from genome sequences. *Science.* **285**, 751-753 (1999)

[42] Mulder, N., Akinola, R., Mazandu, G. & Rapanoel, H. Using biological networks to improve our understanding of infectious diseases. *Computational And Structural Biotechnology Journal.* **11**, 1-10 (2014)

[43] Kalaev, M., Smoot, M., Ideker, T. & Sharan, R. NetworkBLAST: comparative analysis of protein networks. *Bioinformatics.* **24**, 594-596 (2008)

[44] Yang, B., Yih, W., He, X., Gao, J. & Deng, L. Embedding entities and relations for learning and inference in knowledge bases. *ArXiv Preprint ArXiv:1412.6575*. (2014)

[45] Bordes, A., Usunier, N., Garcia-Duran, A., Weston, J. & Yakhnenko, O. Translating embeddings for modeling multi-relational data. *Advances In Neural Information Processing Systems.* **26** (2013)

[46] Lin, Y., Liu, Z., Sun, M., Liu, Y. & Zhu, X. Learning entity and relation embeddings for knowledge graph completion. *Twenty-ninth AAAI Conference On Artificial Intelligence.* (2015)
[47] Mikolov, T., Sutskever, I., Chen, K., Corrado, G. & Dean, J. Distributed representations of words and phrases and their compositionality. *Advances in Neural Information Processing Systems*. **26** (2013)

[48] He, Y. & Zhu, F. Reconstruction of dynamic protein-protein interaction network via graph convolutional network. *Ex-pert Systems With Applications*. **259** pp. 125140 (2025), https://www.sciencedirect.com/science/article/pii/S0957417424020074

[49] Grover, A. & Leskovec, J. node2vec: Scalable feature learning for networks. *Proceedings Of The 22nd ACM SIGKDD International Conference On Knowledge Discovery And Data Mining*. pp. 855-864 (2016)

[50] Yue, X., Wang, Z., Huang, J., Parthasarathy, S., Moosavinasab, S., Huang, Y., Lin, S., Zhang, W., Zhang, P. & Sun, H. Graph embedding on biomedical networks: methods, applications and evaluations. *Bioinformatics*. **36**, 1241-1251 (2020)

[51] Djeddi, W., Hermi, K., Ben Yahia, S. & Diallo, G. Advancing drug-target interaction prediction: a comprehensive graph-based approach integrating knowledge graph embedding and ProtBert pretraining. *BMC Bioinformatics*. **24**, 488 (2023)

[52] Veras, M., Sarker, B., Aridhi, S., Gomes, J., Macedo, J., Nguifo, E., Devignes, M. & Smail-Tabbone, M. On the design of a similarity function for sparse binary data with application on protein function annotation. *Knowledge-Based Systems*. **238** (2022)