has been successfully evaluated with very large ontologies.

Preliminaries
A mapping (also called match) between entitiesIn this work we accept any input ontology in the OWL 2 language [1]}. We refer to (OWL 2) concepts, properties and individuals as entities. of two ontologies \(\mathcal {O} _1\) 
and \(\mathcal {O} _2\) 
is typically represented as a
4-tuple \(\langle e_1,e_2,r,c\rangle \)  where \(e_1\)  and \(e_2\)  are entities of \(\mathcal {O} _1\)  and \(\mathcal {O} _2\) ,
respectively; \(r\)  is a semantic relation, typically one of \( \lbrace \sqsubseteq , \sqsupseteq , \equiv \rbrace  \) ; and \(c\)  is a confidence value,
usually, a real number within the interval \(\left(0,1\right]\) . For simplicity, we refer to a mapping
as a pair \(\langle e_1,e_2 \rangle \) .
An ontology alignment is a
set of mappings \(\mathcal {M}\)  between two ontologies \(\mathcal {O} _1\)  and \(\mathcal {O} _2\) .
An ontology matching task \(\mathcal {M}\)  is composed of a pair of ontologies
\(\mathcal {O} _1\)  (typically called source) and \(\mathcal {O} _2\)  (typically called target) and possibly an associated reference alignment \(\mathcal {M}^{RA} \) .
The objective of a matching task is to discover an overlapping of \(\mathcal {O} _1\)  and
\(\mathcal {O} _2\)  in the form of an alignment \(\mathcal {M}\) . The size or search space
of a matching task is typically bound to the size of the
Cartesian product between the entities of the input ontologies:
\(\vert Sig(\mathcal {O} _1) \vert \times \vert Sig(\mathcal {O} _2)\vert \) ,
where \(Sig(\mathcal {O})\)  denotes the signature (i.e., entities) of \(\mathcal {O} \)  and \(\vert \cdot \vert \)  denotes the size of a set.
An ontology matching system is a program
that, given as input a matching task \(\mathcal {M}=\langle \mathcal {O} _1, \mathcal {O} _2\rangle \) ,
generates an ontology alignment \(\mathcal {M}^{S} \) .Typically automatic, although there are systems that also allow human interaction [2]}.
The standard evaluation measures for an alignment \(\mathcal {M}^{S} \)  are
precision (P), recall (R) and f-measure (F) computed against a reference alignment \(\mathcal {M}^{RA} \)  as follows:

\(P = \frac{\vert \mathcal {M}^{S} \cap \mathcal {M}^{RA} \vert }{\vert \mathcal {M}^{S} \vert },~R = \frac{\vert \mathcal {M}^{S} \cap \mathcal {M}^{RA} \vert }{\vert \mathcal {M}^{RA} \vert },~F = 2 \cdot \frac{P \cdot R}{P + R}\) 

<FIGURE>Problem definition and quality measures
We denote division of an ontology matching task \(\mathcal {M}\) , composed by
the ontologies \(\mathcal {O} _1\)  and \(\mathcal {O} _2\) , as the process of finding
\(n\)  matching subtasks \(\mathcal {M}_{i}=\langle \mathcal {O} _1^{i}, \mathcal {O} _2^{i} \rangle \)  (with
\(i\) =1,...,\(n\) ), where \(\mathcal {O} _1^{i} \subset \mathcal {O} _1\)  and \(\mathcal {O} _2^{i} \subset \mathcal {O} _2\) .
Size of the division.
The size of each matching subtask
is
smaller than the
original task and thus reduces the search space.
Let \({\mathcal {M}} ^{n}=\lbrace \mathcal {M}_1,\ldots ,\mathcal {M}_n\rbrace \) 
be
the division of a matching task \(\mathcal {M}\)  into \(n\)  subtasks.
The
size ratio of the
subtasks \(\mathcal {M}_i\)  and \({\mathcal {M}} ^{n}\) 
with respect to the original matching task size
is
computed as follows:
\(\mathsf {SizeRatio}(\mathcal {M}_i, \mathcal {M}) = \frac{\vert Sig(\mathcal {O} _1^{i}) \vert \times \vert Sig(\mathcal {O} _2^{i}) \vert }{\vert Sig(\mathcal {O} _1) \vert \times \vert Sig(\mathcal {O} _2)\vert }\) 


\(\mathsf {SizeRatio}({\mathcal {M}} ^{n}, \mathcal {M}) =\sum _{i=1}^{n}\mathsf {SizeRatio}(\mathcal {M}_i, \mathcal {M})\) 

The ratio \(\mathsf {SizeRatio}(\mathcal {M}_i, \mathcal {M})\)  is
less than
\(1.0\)  while the aggregation \(\sum _{i=1}^{n}\mathsf {SizeRatio}(\mathcal {M}_i, \mathcal {M})\) , being \(n\)  the number of matching subtasks,
can be greater than
\(1.0\)  as matching subtasks depend on the division technique and may overlap.
Alignment coverage.
The division of the matching task aims at
preserving the target outcomes of the original matching task.
The coverage is
calculated with respect to a relevant alignment \(\mathcal {M}\) , possibly the
reference alignment \(\mathcal {M}^{RA} \) 
of the matching task
if it exists, and
indicates whether that alignment can still be (potentially) discovered with the matching subtasks.
The formal notion
of coverage is given in Definitions REF  and REF .
Definition 1 (Coverage of a matching task) 

Let \(\mathcal {M}=\langle \mathcal {O} _1, \mathcal {O} _2\rangle \)  be a matching task and \(\mathcal {M}\)  an
alignment. We say that a mapping \(m=\langle e_1,e_2 \rangle  \in \mathcal {M}\)  is covered by
the matching task if \(e_1 \in Sig(\mathcal {O} _1)\)  and \(e_2 \in Sig(\mathcal {O} _2)\) . The
coverage of \(\mathcal {M}\)  w.r.t. \(\mathcal {M}\)  (denoted as \(\mathsf {Coverage}(\mathcal {M}, \mathcal {M})\) )
represents the set of mappings
\(\mathcal {M}^{\prime } \subseteq \mathcal {M}\) 
covered by \(\mathcal {M}\) .

Definition 2 (Coverage of the matching task division) 

Let \({\mathcal {M}} ^{n}=\lbrace \mathcal {M}_1,\ldots ,\mathcal {M}_n\rbrace \)  be the result of dividing a matching
task \(\mathcal {M}\)  and \(\mathcal {M}\)  an alignment. We say that a mapping \(m\in \mathcal {M}\)  is covered by \({\mathcal {M}} ^{n}\)  if \(m\)  is at least covered by one of the matching
subtask \(\mathcal {M}_i\)  (with \(i\) =1,...,\(n\) ) as in Definition REF .
The coverage of \({\mathcal {M}} ^{n}\)  w.r.t. \(\mathcal {M}\)  (denoted as \(\mathsf {Coverage}({\mathcal {M}} ^{n}, \mathcal {M})\) )
represents the set of mappings \(\mathcal {M}^{\prime } \subseteq \mathcal {M}\)  covered by \({\mathcal {M}} ^{n}\) .
The coverage is
given as a ratio with respect to the (covered)
alignment:

\(\mathsf {CoverageRatio}({\mathcal {M}} ^{n}, \mathcal {M}) =\frac{\vert \mathsf {Coverage}({\mathcal {M}} ^{n}, \mathcal {M})\vert }{\vert \mathcal {M}\vert }\) 



Methods
In this section we present our approach to compute a division
\({\mathcal {M}} ^{n}=\lbrace \mathcal {M}_1,\ldots ,\mathcal {M}_n\rbrace \)  given a matching task \(\mathcal {M}=\langle \mathcal {O} _1, \mathcal {O} _2\rangle \)  and the number of target subtasks \(n\) .
We rely on locality ontology modules to extract
self-contained modules of the input ontologies. The module extraction and task division
is tailored to the ontology alignment task at hand
by embedding the contextual semantics of a (combined) inverted index of the ontologies in the matching task.
Figure REF  shows an overview of our approach.
(i) The ontologies \(\mathcal {O} _1\)  and \(\mathcal {O} _2\)  are indexed using the lexical index LexI (see Section REF ); (ii) LexI is divided into clusters based on the semantic embeddings of its entries (see Section REF ); (iii) entries in those clusters derive potential mapping sets (see Section REF ); and (iv) the context of these mapping sets lead to matching subtasks (see Sections REF  and REF ). Next, we elaborate on the methods behind these steps.
Locality modules and context
Logic-based module extraction techniques compute ontology fragments that capture
the meaning of an input signature
(e.g., set of entities)
with respect to a given
ontology. That is, a module contains the context
(i.e., sets of semantically related entities) of the input signature.
In this paper we rely on bottom-locality modules
[3]}, [4]}, which will be referred to as locality-modules or simply as modules. These modules include the ontology axioms required to describe the entities in the signature.
Locality-modules compute self-contained ontologies and are tailored to tasks that require reusing a fragment of an ontology. Please refer to [3]}, [4]} for further details.
Locality-modules play an key role in our approach
as they provide the context
for the entities in a given mapping or set of mappings as formally
presented in Definition REF .
Definition 3 (Context of a mapping and an alignment) 

Let \(m=\langle e_1,e_2 \rangle \)  be a mapping
between two ontologies \(\mathcal {O} _1\)  and \(\mathcal {O} _2\) . We define the context of \(m\)  (denoted
as \(\mathsf {Context}(m, \mathcal {O} _1, \mathcal {O} _2)\) ) as a pair of locality modules \(\mathcal {O} _1^{\prime }\subseteq \mathcal {O} _1\)  and \(\mathcal {O} _2^{\prime } \subseteq \mathcal {O} _2\) , where \(\mathcal {O} _1^{\prime }\)  and \(\mathcal {O} _2^{\prime }\)  include the semantically related entities to \(e_1\)  and \(e_2\) , respectively.
Similarly, the context for an alignment \(\mathcal {M}\)  between two ontologies
\(\mathcal {O} _1\)  and \(\mathcal {O} _2\)  is denoted as \(\mathsf {Context}(\mathcal {M}, \mathcal {O} _1, \mathcal {O} _2)=\langle \mathcal {O} _1^{\prime }, \mathcal {O} _2^{\prime } \rangle \) , where \(\mathcal {O} _1^{\prime }\)  and \(\mathcal {O} _2^{\prime }\)  are modules
including the semantically related entities for the entities \(e_1 \in Sig(\mathcal {O} _1)\)  and \(e_2 \in Sig(\mathcal {O} _2)\)  in each mapping \(m=\langle e_1,e_2 \rangle  \in \mathcal {M}\) .

Intuitively, as the context of an alignment (i.e., \(\mathsf {Context}(\mathcal {M}, \mathcal {O} _1, \mathcal {O} _2)=\langle \mathcal {O} _1^{\prime }, \mathcal {O} _2^{\prime } \rangle \) ) semantically characterises the entities involved
in that alignment, a matching task \(\mathcal {M}=\langle \mathcal {O} _1, \mathcal {O} _2\rangle \)  can be reduced to the task \(\mathcal {M}^{\mathcal {M}}_{\mathcal {O} _1\text{-}\mathcal {O} _2} =\langle \mathcal {O} _1^{\prime }, \mathcal {O} _2^{\prime } \rangle \)  without information loss in terms of finding \(\mathcal {M}\)  (i.e., \(\mathsf {Coverage}(\mathcal {M}^{\mathcal {M}}_{\mathcal {O} _1\text{-}\mathcal {O} _2}, \mathcal {M})=\mathcal {M}\) ).
For example, in the small OAEI largebio tasks [7]}, [8]} systems are given the context of the reference alignment as a (reduced) matching task (e.g., \(\mathcal {M}^{RA}_{\text{fma-nci}} = \mathsf {Context}(\mathcal {M}^{RA} _{\text{fma-nci}},\ \mathcal {O} _\text{FMA}, \mathcal {O} _\text{NCI})=\langle \mathcal {O} _\text{FMA}^{\prime }, \mathcal {O} _\text{NCI}^{\prime } \rangle \) ), instead of the whole FMA and NCI ontologies.
<TABLE>
Indexing the ontology vocabulary
We rely on a semantic inverted index (we will refer to this index as LexI). This index maps sets of words to the
entities where these words appear.
LexI encodes the labels of all entities of the input ontologies \(\mathcal {O} _1\)  and \(\mathcal {O} _2\) , including their lexical variations (e.g., preferred labels, synonyms), in the form of key-value pairs
where the key is a set of words and the value is a set of entities
such that the set of words of the key
appears in (one of) the entity labels.
Similar indexes are commonly used in information retrieval applications [9]}, Entity Resolution systems [10]}, and also exploited in ontology alignment systems (e.g., LogMap [11]}, ServOMap [12]}
and AML [13]}) to reduce the search space and enhance the matching process.
Table REF  shows a few example entries of LexI for two input ontologies.
LexI is created as follows.
[(i)]
Each label associated to an ontology entity is split into a set of
words; for example, the label “Lunate facet of hamate” is split into the set {“lunate”, “facet”, “of”, “hamate”}.

Stop-words are removed from the set of words.

Stemming techniques are applied to each word (i.e., {“lunat”, “facet”, “hamat”}).

Combinations of subsets of words also serve as keys in LexI; for example,
{“lunat”, “facet”}, {“hamat”, “lunat”} and so on.In
order to avoid a combinatorial blow-up, the number of computed subsets of words
is limited.

Entities leading to the same (sub)set of words are associated to the
same key in LexI, for example {“disorder”} is associated with three entities.
Finally,

entries in LexI pointing to entities of only one ontology or associated to a number of entities larger than \(\alpha \)  are not considered.In the experiments we used \(\alpha =60\) .

Note that a single entity label may lead to several entries in LexI, and
each entry in LexI points to one or more entities.

Covering matching subtasks
Each entry (i.e., a key-value pair) in LexI is a source of candidate mappings. For
instance, the example in Table REF  suggests that there is a
candidate
mapping \(m=\langle \mathsf {\mathcal {O} _1\hspace{0.0pt}:\hspace{0.0pt}Disorder\_of\_stomach},\mathsf {\mathcal {O} _2\hspace{0.0pt}:\hspace{0.0pt}Pregnancy\_disorder} \rangle \) 
since
these entities
are associated to
the {“disorder”} entry in LexI.
These mappings are not necessarily correct but will link lexically-related entities, that is, those entities sharing at least one word among their labels (e.g., “disorder”).
Given a subset of entries or rows of LexI (i.e., \(l \subseteq \textsf {LexI} \) ), the function
\(\mathsf {Mappings}(l)=\mathcal {M}^{l}\)  provides the set of mappings derived from \(l\) . We refer to the
set of all (potential) mappings suggested by LexI (i.e., \(\mathsf {Mappings}(\textsf {LexI})\) ) as \(\mathcal {M}^{\textsf {LexI}} \) . \(\mathcal {M}^{\textsf {LexI}} \)  represents a manageable subset of the Cartesian product between the entities of the input ontologies. For example, LexI suggest around \(2\times 10^4\)  potential mappings for the matching task \(\mathcal {M}_{\text{fma-nci}} = \langle \mathcal {O} _\text{FMA}, \mathcal {O} _\text{NCI}\rangle \) , while the Cartesian product between \(\mathcal {O} _\text{FMA}\)  and \(\mathcal {O} _\text{NCI}\)  involves more than \(5\times 10^9\)  mappings.
Since standard ontology alignment systems rarely discover mappings outside
\(\mathcal {M}^{\textsf {LexI}} \) , the context of \(\mathcal {M}^{\textsf {LexI}} \)  (recall Definition REF )
can be seen as a
reduced matching task \(\mathcal {M}^{\textsf {LexI}} =\mathsf {Context}(\mathcal {M}^{\textsf {LexI}}, \mathcal {O} _1, \mathcal {O} _2)=\langle \mathcal {O} _1^{\textsf {LexI}}, \mathcal {O} _2^{\textsf {LexI}} \rangle \)  of the original task \(\mathcal {M}=\langle \mathcal {O} _1, \mathcal {O} _2\rangle \) . However, the modules \(\mathcal {O} _1^{\textsf {LexI}}\)  and \(\mathcal {O} _2^{\textsf {LexI}}\) , although smaller than
\(\mathcal {O} _1\)  and \(\mathcal {O} _2\) , can still be challenging for many ontology matching systems. A solution is to divide or cluster the entries in LexI to lead to several tasks involving smaller ontology modules.
Definition 4 (Matching subtasks from LexI) 

Let \(\mathcal {M}=\langle \mathcal {O} _1, \mathcal {O} _2\rangle \)  be a matching task, LexI the inverted index of the ontologies \(\mathcal {O} _1\)  and \(\mathcal {O} _2\) , and \(\lbrace l_1,\ldots ,l_n\rbrace \)  a set of \(n\)  clusters of entries in LexI.
We denote the set of matching subtasks from LexI as
\({\mathcal {M}} ^{n} = \lbrace \mathcal {M}^{\textsf {LexI}} _1,\ldots ,\mathcal {M}^{\textsf {LexI}} _n\rbrace \)  where each cluster \(l_i\)  leads to the matching subtask \(\mathcal {M}^{\textsf {LexI}} _i=\langle \mathcal {O} _1^{i},\mathcal {O} _2^{i} \rangle \) , such that \(\mathsf {Mappings}(l_i) = \mathcal {M}^{\textsf {LexI}} _i\)  is the set of mappings suggested by the LexI entries in \(l_i\)  (i.e., key-value pairs)
and \(\mathcal {O} _1^{i}\)  and \(\mathcal {O} _2^{i}\)  represent the context of \(\mathcal {M}^{\textsf {LexI}} _i\)  w.r.t. \(\mathcal {O} _1\)  and \(\mathcal {O} _2\) .

Quality of the matching subtasks.
The matching subtasks in Definition REF  rely on LexI and the notion of context, thus it is expected that the tasks in \({\mathcal {M}} ^{n}\)  will cover most of the mappings \(\mathcal {M}^{S} \)  that a matching system can compute, that is \(\mathsf {CoverageRatio}({\mathcal {M}} ^n, \mathcal {M}^{S})\)  will be close to \(1.0\) .
Furthermore, the use of locality modules to compute the context guarantees the extraction of matching subtasks that are suitable to ontology alignment systems in terms of preservation of the logical properties of the given signature.
Intuitively each cluster of LexI will lead
to a smaller matching task \(\mathcal {M}^{\textsf {LexI}} _i\)  (with respect to both \(\mathcal {M}^{\textsf {LexI}} \)  and \(\mathcal {M}\) ) in terms of
search space. Hence \(\mathsf {SizeRatio}(\mathcal {M}^{\textsf {LexI}} _i, \mathcal {M})\)  will be smaller than \(1.0\) .
The overall aggregation of ratios (cf. Equation REF )
depends on the clustering strategy of the entries in LexI and it is also
expected to be smaller than \(1.0\) .
Reducing the search space
in each matching subtask \(\mathcal {M}^{\textsf {LexI}} _i\)  has the potential of enabling
the evaluation of systems that
cannot cope with the original matching task \(\mathcal {M}\)  in a given time-frame or
with (limited) computational resources.
<TABLE>
Semantic embeddings
We use a semantic embedding approach to identify, given \(n\) , a set of clusters of
entries \(\lbrace l_1,\ldots ,l_n\rbrace \)  from LexI. As in Definition REF , these clusters
lead to the set of matching subtasks \({\mathcal {M}} ^{n} = \lbrace \mathcal {M}^{\textsf {LexI}} _1,\ldots ,\mathcal {M}^{\textsf {LexI}} _n\rbrace \) .
The semantic embeddings aim at representing into the same (vector) space the features
about the relationships among words and ontology entities that occur in LexI.
Hence, words and entities that belong to similar semantic contexts will typically have
similar vector representations.
Embedding model.
Our approach currently relies on the StarSpace toolkitStarSpace:
https://github.com/facebookresearch/StarSpace and its neural embedding
model [14]} to learn embeddings for the words and
ontology entities in LexI.
We adopt the
TagSpace [15]} training setting of
StarSpace. Applied to our setting, StarSpace learns associations between a set of
words (i.e., keys in LexI)
and a set of relevant ontology entities (i.e., values in LexI).
The StarSpace model is trained by assigning a \(d\) -dimensional vector to
each of the relevant features (e.g., the individual words and the ontology entities in LexI).
Ultimately,
the look-up matrix (the matrix of embeddings - latent vectors) is learned by
minimising the loss function in Equation REF .

\(\!\sum _{\begin{array}{c}(w, e) \in E^+,\\e^- \in E^-\end{array}}L^{batch} (sim(\mathbf {v}_w, \mathbf {v}_e), sim(\mathbf {v}_w, \mathbf {v}_{e_1^-}), \ldots ,\\sim(\mathbf {v}_w, \mathbf {v}_{e_j^-}))\) 

In this loss function we compare positive samples with negative samples. Hence we need to indicate the generator of positive pairs \((w, e) \in E^+\)  (in our setting those are word-entity pairs from LexI) and the
generator of negative entries \(e^- \in E^-\) 
(in our case we sample from the list of entities in the values of LexI).
StarSpace follows the strategy by Mikolov et al.
[16]} and selects a random subset of \(j\)  negative examples
for each batch update.
Note that we tailor the generators to the alignment task by sampling from LexI.
The similarity function
\(sim\) 
operates on \(d\) -dimensional vectors (e.g., \(\mathbf {v}_w\) , \(\mathbf {v}_e\)  and
\(\mathbf {v}_e^-\) ),
in our case we use the standard dot
product in Euclidean space.
Clustering strategy.
The semantic embedding of each entry \(\varepsilon =(K, V) \in \)  LexI is
calculated by concatenating [(i)]
the mean vector representation of the vectors associated to each word in the key \(K\) , with

the mean vector of the vectors of the ontology entities in the value \(V\) ,

as in Equation REF , where \(\oplus \)  represents the concatenation of
two vectors, \(\mathbf {v}_w\)  and \(\mathbf {v}_e\)  represents \(d\) -dimensional vector embeddings learnt by
StarSpace, and \(\mathbf {v}_\varepsilon \)  is a (\(2*d\) )-dimension vector.

\(\mathbf {v}_\varepsilon = \frac{1}{|K|}\sum _{w \in K}\mathbf {v}_w \oplus \frac{1}{|V|}\sum _{e \in V}\mathbf {v}_e\) 

Based on the embeddings \(\mathbf {v}_\varepsilon \)  we then perform standard clustering
with the K-means algorithm to obtain the clusters of LexI entries \(\lbrace l_1,\ldots ,l_n\rbrace \) .
For example, following our approach, in the example of Table REF 
entries in rows 1 and 2 (respectively 3 and 4) would belong to the same
cluster.
Suitability of the embedding model.
Although we could have followed other embedding strategies, we advocated to learn new entity embeddings with StarSpace for the following reasons:
[(i)]

ontologies, particularly in the biomedical domain, may bring specialised vocabulary that is not fully covered by precomputed word embeddings;

to embed not only words but also concepts of both ontologies; and

to obtain embeddings tailored to the ontology alignment task (i.e., to learn
similarities among words and concepts dependant on the task).

StarSpace provides the required functionalities to embed the semantics of LexI and identify accurate clusters. Precise clusters will lead to smaller matching
tasks, and thus, to a reduced global size of the computed division of the
matching task \({\mathcal {M}} ^{n}\)  (cf. Equation REF ).
Evaluation
In this section we provide empirical evidence to support the suitability of the proposed method to divide the ontology alignment task.
We rely on the datasets of the Ontology Alignment Evaluation Initiative (OAEI)
[7]}, [8]}, more specifically, on the matching
tasks provided in the anatomy,
largebio
and phenotype
tracks.
Table REF  provides an overview of these OAEI tasks and the related ontologies and mapping sets.
The methods have been implemented in JavaJava codes: https://github.com/ernestojimenezruiz/logmap-matcher
and PythonPython codes: https://github.com/plumdeq/neuro-onto-part (neural embedding strategy), tested on a Ubuntu Laptop with an
Intel Core i9-8950HK CPU@2.90GHz
and allocating up to \(25Gb\)  of RAM.
Datasets, matching subtasks, computed mappings
and other supporting resources are available in the Zenodo repository [19]}.
For all of our experiments we used the following StarSpace hyperparameters:
-trainMode 0 -similarity dot –epoch 100 –dim 64.
<FIGURE>Adequacy of the division approach
We have evaluated the adequacy of our division strategy in terms of coverage (as
in Equation REF ) and size (as in Equation REF ) of the resulting division \({\mathcal {M}} ^n\) 
for each of the matching task in Table REF .
Coverage ratio.
Figures REF  and REF  shows the coverage of the different
divisions \({\mathcal {M}} ^n\)  with respect to the reference alignment and system computed
mappings, respectively.
As system mappings we have used the
consensus alignment with vote=3, that is, mappings that have been voted by at
least 3 systems in the last OAEI campaigns.
The overall coverage results are encouraging:
[(i)]
the divisions \({\mathcal {M}} ^n\)  cover over \(94\%\)  of the reference alignments for all tasks, with the exception of the SNOMED-NCI case where coverage ranges from \(0.94\)  to \(0.90\) ;

when considering system mappings, the coverage for all divisions is over \(0.98\)  with the exception of AMA-NCIA, where it ranges from \(0.956\)  to \(0.974\) ;

increasing the number of divisions \(n\)  tends to slightly decrease the coverage in some of the test cases,
this is an expected behaviour as the computed divisions include different semantic contexts (i.e., locality modules) and some relevant entities may fall out the division; finally

as shown in [20]}, the results in terms of coverage of state-of-the-art partitioning methods (e.g., [21]}, [22]}) are very low for the OAEI largebio track (\(0.76\) , \(0.59\)  and \(0.67\)  as the best results for FMA-NCI, FMA-SNOMED and SNOMED-NCI, respectively), thus, making the obtained results even more valuable.

Size ratio.
The results in terms of the size (i.e., search space) of
the selected divisions \({\mathcal {M}} ^n\)  are
presented in Figure REF .
The search space is improved with respect to the original \(\mathcal {M}\)  for all the cases, getting as low as \(5\%\)  of the original matching task size for the FMA-NCI and FMA-SNOMED cases.
The gain in the reduction of the search space gets relatively stable after a
given division size; this result is expected since the context provided by
locality modules ensures modules with the necessary semantically related entities.
The scatter plot in Figure REF  visualise the size of the source
modules against the size of the target modules for the FMA-NCI matching subtasks with divisions of size \(n \in \lbrace 5, 20, 50, 100\rbrace \) . For
instance, the (blue) circles represent points \(\big (\vert Sig(\mathcal {O} _1^{i})\vert , \vert Sig(\mathcal {O} _2^{i}) \vert \big )\)  being
\(\mathcal {O} _1^{i}\)  and \(\mathcal {O} _2^{i}\)  the source and target modules (with \(i\) =1,...,5)
in the matching subtasks of \({\mathcal {M}} ^5\) . It can be noted that, on average, the size of source and target modules decreases as the size of the division increases. For example, the largest task in  \({\mathcal {M}} ^{20}\)  is represented in point \((6754, 9168)\) , while the largest task in  \({\mathcal {M}} ^{100}\)  is represented in point \((2657, 11842)\) .
<TABLE>Computation times. The time to compute the divisions of the matching task is
tied to the number of locality modules to extract, which can be
computed in polynomial time relative to the size of
the input ontology [3]}.
The creation of LexI does not add an important overhead, while the training of
the neural embedding model ranges from \(21s\)  in AMA-NCI to \(224s\)  in SNOMED-NCI.
Overall, for example, the required time to compute the division with 100 matching subtasks
ranges from \(23s\)  (AMA-NCIA) to approx. \(600s\)  (SNOMED-NCI).
Evaluation of OAEI systems
In this section we show that the division of the alignment task enables systems that, given
some computational constraints, were unable to complete an OAEI task.
We have selected the following five systems
from the latest OAEI campaigns, which include novel alignment techniques but failed to scale to very large matching tasks:
MAMBA (v.2015) [24]}, FCA-Map (v.2016) [25]}, SANOM (v.2017) [26]}, ALOD2vec (v.2018) [27]} and
POMap++ (v.2018) [28]}.
MAMBA failed to complete the anatomy track, while FCA-Map, SANOM, ALOD2vec and
POMap++ could not complete the largest tasks in the largebio track.
MAMBA and SANOM threw an out-of-memory exception with \(25Gb\) , whereas FCA-Map,
ALOD2vec and POMap++ did not complete the tasks within a 6 hours time-frame.
We have used the SEALS infrastructure to conduct the evaluation
[7]}, [8]}.
Table REF  shows the obtained results
in terms of precision, recall, f-measure, and
computation times (time for the easiest and the hardest task, and total time for all tasks)
over different divisions \({\mathcal {M}} ^n\)  computed using our strategy.
For example, FCA-Map was run over divisions
with 20 and 50 matching subtasks (i.e., \(n \in \lbrace 20, 50\rbrace \) ) in the FMA-NCI case.
Note that for each matching subtask a system generates a partial alignment \(\mathcal {M}^{S} _i\) , the final alignment for the (original)
matching task is computed as the union of all partial alignments
(\(\mathcal {M}^{S} =\bigcup _{i=1}^{n} \mathcal {M}^{S} _i\) ).
The results are encouraging and can be summarised as follows:

We enabled several systems to produce results even for the largest OAEI
test case (e.g., FCA-Map with SNOMED-NCI).

The computation times are also very good falling under the 6 hours time frame, specially given that the (independent) matching subtasks have been run sequentially without
parallelization.

The size of the divisions, with the exception of FCA-Map, is beneficial in terms of total computation time.

The increase of number of matching subtasks is positive or neutral for MAMBA, POMap++ and ALOD2vec in terms of f-measure, while it is slightly reduced for FCA-Map and SANOM.

Global f-measure results are lower than top OAEI systems;
nevertheless, since the above systems could not be evaluated without the
divisions, these results are obtained without any
fine-tuning of their parameters.

The computation times of the hardest tasks, as \(n\)  increases, is also reduced. This has a positive impact in the monitoring of alignment systems as the hardest task is completed in a reasonable time.


Related work
Partitioning and blocking.
Partitioning and modularization
techniques have been extensively used within the Semantic Web to improve the efficiency when solving the task at hand
(e.g., visualization [31]}, [32]},
reuse [4]}, debugging
[34]}, classification
[35]}).
Partitioning or blocking has also been widely used to reduce the complexity of the
ontology alignment task [13]}.
In the literature there are two major categories of partitioning
techniques, namely: independent and dependent. Independent
techniques typically use only the structure of the ontologies and are not concerned about
the ontology alignment task when performing the partitioning. Whereas
dependent partitioning methods rely on both the structure of the ontology and
the ontology alignment task at hand.
Although our approach does not compute (non-overlapping) partitions of the
ontologies, it can be considered a dependent technique.
Prominent examples of ontology alignment systems including partitioning
techniques are Falcon-AO [21]}, GOMMA [38]}, COMA++ [39]} and TaxoMap
[22]}.
Falcon-AO, GOMMA and COMA++ perform independent partitioning where the clusters of the source and target ontologies are independently
extracted. Then pairs of similar clusters (i.e., matching subtasks) are aligned using standard techniques. TaxoMap [22]}
implements a dependent technique where the partitioning is combined with the matching process.
TaxoMap proposes two methods, namely: PAP (partition, anchor, partition) and APP (anchor, partition, partition).
The main difference of these methods is the order of extraction of (preliminary) anchors to discover pairs of
partitions to be matched (i.e., matching subtasks).
SeeCOnt
[42]} presents a seeding-based clustering technique to
discover
independent clusters in the input ontologies.
Their approach has been evaluated
with the Falcon-AO system by replacing its native PBM (Partition-based Block Matching) module [43]}.
Laadhar et al. [28]}
have recently integrated within the
system POMap++ a hierarchical agglomerative clustering
algorithm to divide an ontology into a set of partitions.
The above approaches, although presented interesting ideas,
did not provide guarantees about the size and coverage
of the discovered partitions or divisions.
Furthermore, they have not been successfully evaluated on very large ontologies.
On the one hand, as reported by Pereira et al. [20]}
the results in terms of coverage of the PBM method of Falcon-OA, and the PAP and APP methods of TaxoMap are very low for the OAEI largebio track.
On the other hand, as discussed in Section , POMap++ fails to scale with the largest largebio tasks.
Note that the recent work in [46]} has borrowed from our workshop paper [47]} the quality measures presented in Section REF . They obtain competitive coverage results for medium size ontologies; however, their approach, as in POMap++, does not scale for large ontologies.
Blocking techniques are also extensively used in Entity Resolution (see [10]} for a survey).
Although related, the problem of blocking in ontologies is different as the logically related axioms for a seed signature play an important role when computing the blocks.
Our dependent approach, unlike traditional partitioning and blocking methods, computes overlapping self-contained modules (i.e., locality modules [3]}).
Locality modules guarantee the extraction of all semantically related entities
for a given signature.
This capability enhances the coverage results and enables the inclusion of the
(semantically) relevant information required by an alignment system.
It is worth mentioning that
the need of self-contained and covering modules, although not thoroughly
studied, was also highlighted in a preliminary work by
Paulheim [50]}.
Embedding and clustering.
Recently, machine learning techniques such as semantic embedding [51]} have been investigated for ontology alignment.
They often first learn vector representations of the entities and then predict the alignment [52]}, [53]}, [54]}.
However, most of them focus on alignment of ontology individuals (i.e., ABox) without considering the ontology concepts and axioms at the terminological level (i.e., TBox).
Nkisi-Orji et al. [55]} predicts the alignment between ontology concepts with Random Forest, but incorporates the embeddings of words alone, without any other semantic components like in our work.
Furthermore, these approaches focus on predicting the alignment,
while our work aims at boosting an existing alignment system. Our framework could potentially be adopted in systems like in [55]} if facing scalability problems for large ontologies.
Another piece of related work is the clustering of semantic components,
using the canopy clustering algorithm [57]}
where objects are grouped into canopies and each object can be a member of multiple canopies.
For example, Wu et al. [58]} first extracted canopies (i.e., mentions) from a knowledge base,
and then grouped the entities accordingly so as to finding out the entities with the same semantics (i.e., canonicalization).
As we focus on a totally different task – ontology alignment,
the context that can be used, such as the embeddings for the words and
ontology entities in LexI, is different from these works, which leads to a different clustering method.

Conclusions and future work
We have developed a novel framework to split the ontology alignment
task into several matching subtasks based on a semantic inverted index,
locality modules, and a neural embedding model.
We have performed a comprehensive evaluation which suggests that
the obtained divisions are suitable in practice in terms of both coverage and size.
The division of the matching task allowed us to obtain results for
five systems which failed to complete these tasks in the past.
We have focused on systems failing to complete a task, but a suitable adoption and integration of the presented framework within the pipeline of any ontology alignment system has the potential to improve the results in terms of
computation times.
Opportunities.
Reducing the ontology matching task into smaller and more manageable tasks may
also bring opportunities to enhance
[(i)]
user interaction [2]},

reasoning and repair [60]},

benchmarking and monitoring [7]}, [8]}, and

parallelization.

The computed independent matching subtasks can potentially be run
in parallel in evaluation platforms like the HOBBIT [63]}. The current evaluation was conducted sequentially as [(i)]

the SEALS instance only allows running one task at a time, and

the evaluated systems were not designed to run several tasks in parallel; for instance, we managed to run MAMBA outside SEALS, but it relies on a MySQL database and raised a concurrent access exception.

Impact on the f-measure.
As shown in Section REF , the impact of the number of divisions on the f-measure depends on the evaluated systems. In the near future we aim at conducting an extensive evaluation of our framework over OAEI systems able to deal with the largest tasks in order to obtain more insights about the impact on the f-measure. In [64]} we reported a preliminary evaluation where YAM-Bio [65]} and AML [66]} kept similar f-measure values, while LogMap [11]} had a reduction in f-measure, as the number of divisions increased.
Number of subdivisions.
Currently our strategy requires the size of the
number of matching subtasks or divisions as input. The (required) matching subtasks may be known before
hand if, for example, the matching tasks are to be run in parallel in a number
of available CPUs. For the cases where the resources are limited or where a
matching system is known to cope with small ontologies, we plan to design an
algorithm to estimate the number of divisions so that
the size of the matching subtasks in the computed divisions is appropriate to the system and resource constraints.
Dealing with a limited or large lexicon.
The construction of LexI shares a limitation with state-of-the-art systems when the input ontologies are lexically disparate or in different languages.
In such cases, LexI can be enriched with general-purpose lexicons (e.g., WordNet), more specialised background knowledge (e.g., UMLS Metathesaurus) or with translated labels using online services (e.g., Google).
On the other hand, a large lexicon may also have an important impact in the computation times. Our conducted evaluation shows, however, that we can cope with very large ontologies with a rich lexicon (e.g., NCI Thesaurus).
Notion of context.
Locality-based modules are typically much smaller than the whole ontology and they have led to very good results in terms of size and coverage. We plan, however,
to study different notions of context
of an alignment (e.g., the tailored modules proposed in
[68]}) to further improve the results in terms of size while keeping the same level of coverage.
This work was supported by the SIRIUS Centre for Scalable Data Access (Norges forskningsråd), the AIDA project (Alan Turing Institute), Samsung Research UK, Siemens AG, and the EPSRC projects AnaLOG, OASIS and UK FIRES. We would also like to thank the anonymous reviewers that helped us improve this work.
