11institutetext: Department of Information Engineering and Computer Science
(DISI),
University of Trento, Italy
11email: {daqian.shi, xiaoyue.li<EMAIL_ADDRESS>
# KAE: A Property-based Method for Knowledge Graph Alignment and Extension

Daqian Shi  Xiaoyue Li and Fausto Giunchiglia

###### Abstract

A common solution to the semantic heterogeneity problem is to perform
knowledge graph (KG) extension exploiting the information encoded in one or
more candidate KGs, where the alignment between the reference KG and candidate
KGs is considered the critical procedure. However, existing KG alignment
methods mainly rely on entity type (etype) label matching as a prerequisite,
which is poorly performing in practice or not applicable in some cases. In
this paper, we design a machine learning-based framework for KG extension,
including an alternative novel property-based alignment approach that allows
aligning etypes on the basis of the properties used to define them. The main
intuition is that it is properties that intentionally define the etype, and
this definition is independent of the specific label used to name an etype,
and of the specific hierarchical schema of KGs. Compared with the state-of-
the-art, the experimental results show the validity of the KG alignment
approach and the superiority of the proposed KG extension framework, both
quantitatively and qualitatively.

###### Keywords:

knowledge graph extension entity type alignment entity type recognition
property-based machine learning

##  1 Introduction

The semantic heterogeneity problem arises whenever there is a need to exploit
knowledge graphs (KGs) from heterogeneous resources [36]. Here we focus on KGs
where nodes are entities decorated by data properties and relations are object
properties. Furthermore, we talk of entity type (etype) meaning the class to
which an entity belongs, e.g., Person and Event. A solution of semantic
heterogeneity is to perform KG extension that extends the reference KG by
knowledge encoded in one or more candidate KGs. Meanwhile, KG alignment is an
attractive topic that involves various tasks, e.g., well-known ontology
matching (OM), where two practical tasks are considered critical steps to
achieving KG extension. Firstly, the alignments between etypes from reference
and candidate KGs [21, 32, 2], exploiting only schema level information, as it
is the most often case in OM. Secondly, the alignments between reference
etypes and candidate entities, exploiting additional information of entities,
also known as etype recognition [43, 47]. These two kinds of alignments are
prerequisites for extending the reference KG at both the schema level and
instance level, respectively.

Etype alignment is a prepositive task during KG extension since etypes define
the schema of collected entities in a KG. The reference KG can directly
integrate candidate entities if their corresponding etypes align with
reference etypes. Existing etype alignment methods mainly exploit natural
language processing (NLP) based [14, 52] and structure-based [35, 24]
techniques. Both techniques enforce etype label matching as a prerequisite.
NLP-based methods utilize diverse lexical-based similarity metrics and synonym
analysis to align etype labels, which raises limitations when applied in
practice. Labels may suggest a wrong etype [49], where the same concept can be
labeled differently by KGs. For instance, an eagle can be labeled as Bird in a
general-purpose KG and Eagle in a domain-specific KG. In turn, the same label
may present different concepts in heterogeneous KGs, which will also lead to
wrong recognition results. Structure-based methods consider the KG hierarchy
as an additional input, where the structure of a hierarchy is used to drive
the label matching, e.g., it is suggested to perform label matching to sub-
classes or super-classes. However, these methods may also mislead the
conclusions as properties assigned to an etype in the hierarchy are cumulative
and depend only on nodes in the path from the root and, therefore, do not
depend on the order by which they are assigned [30]. In addition, the
difference in taxonomy between KGs will increase the impact of such mistakes,
e.g., the super-class of etype Eagle can be Animal in one KG and Bird in
another KG. On the other hand, the alignments between etypes and entities
(here we call etype recognition task) are also critical since the reference KG
can also be extended by candidate entities that are not included in aligned
etypes. However, it is not easy to identify such alignments due to the lexical
labels are not applicable to alignment entities and etypes. For instance,
entity apple can be a company, a fruit, or the name of a pet, but there is
only trivial lexical similarity between entity apple and etypes company, fruit
and pet. Thus, current NLP-based and structure-based methods poorly perform
the etype recognition task either.

As a solution to the above problems, the main intuition of this paper is to
align etypes/entities with reference etypes for KG extension on the basis of
the properties used to define them. It is, in fact, the properties that are
used to intentionally define an etype, and this definition is independent of
the specific label and also independently of its hierarchy [27]. This allows
us to think of etypes as being organized in hierarchies, where lower etypes
inherit properties from upper etypes and where the entities populating an
etype also populate all the upper etypes. In turn, it allows us to think of KG
alignment as a problem of matching inheritance hierarchies, where etypes may
or may not be populated with entities. Figure 1 (a) provides one such
hierarchy, used as a running example in the rest of the paper. In practice,
most relevant KGs are associated with large numbers of properties, see, e.g.,
DBpedia [4] and OpenCyc [23]. And the reason for this is quite obvious, being
that one of the purposes of KG extension is exactly that of extending the
number of properties.

In this paper, we propose a machine learning (ML)-based framework to realize
KG extension task, including an algorithm for generic KG alignment based on
the above intuition of exploiting properties. We introduce a formalization
strategy, where we organize a KG and its inner mappings between
etypes/entities and properties based on the use of formal concept analysis
(FCA) [27]. Then, we present three property-based metrics to measure the
similarity between etypes and entities, where the metrics characterize the
role that properties have in the definition of given etypes from different
aspects. They capture the main idea that the number of aligned properties
affects the contextual similarity between etypes and entities. The proposed
similarity metrics and algorithm are applied in two key modules of the KG
extension framework, i.e., etype alignment and KG extension modules. Finally,
we will obtain an extended reference KG by integrating etypes and entities
from the candidate KGs.

Overall, the main contributions of this paper are as follows:

  * •

We design an ML-based framework for KG alignment and extension tasks, where
etype alignment and etype recognition are introduced as two key procedures.

  * •

We proposed a novel set of property-based metrics for measuring contextual
similarity between KGs while introducing an FCA-based KG formalization
strategy.

  * •

We implement a classification-based method for KG alignment, which exploits
the property-based information by our proposed metrics.

  * •

We compare our method with state-of-the-art etype recognition methods from
several different perspectives. The experimental results show the validity of
the similarity metrics and the superiority of the proposed KG extension
framework, both quantitatively and qualitatively.

The rest of the paper is organized as follows. Section 2 discusses the
motivation for exploiting properties for etype recognition and section 3
demonstrates how we formalize a KG and its inner mappings into FCA contexts.
Section 4 introduces three specificity measurements and their corresponding
property-based etype similarity metrics. In section 5, we describe the
proposed ML-based KG extension framework and the details of individual
modules. Then we discuss the experiment setups and experimental results in
Section 6. Finally, we present the related work in Section 7 and conclude the
paper in Section 8.

##  2 Intuitive Discussion

###  2.1 Task Description

In the knowledge integration area, KG alignment and extension can be organized
as sequential tasks, where KG alignment aims to align the knowledge from
candidate KG and reference KG, and KG extension aims to integrate target
information into the reference KG following the aligned knowledge. To clearly
define the above-mentioned tasks, we define a KG as a hierarchy of concepts,
where properties are used to describe them. Specifically, we define the schema
of a KG and its inner relations as $KGS=\langle C,P,R\rangle$, where
$C=\\{C_{1},...,C_{n}\\}$ being the classes of entities (i.e. etypes),
$P=\\{p_{1},...,p_{m}\\}$ being the set of properties, $R=\\{\langle
C_{i},T(C_{i})\rangle|C_{i}\in C\\}$ being the set of correspondences between
etypes and properties, and function $T(C_{i})$ returns properties associated
with $C_{i}$. As for the entities $I$, we define $I=\\{I_{1},...,I_{l}\\}$
being the set of entities in $KG$, where each entity $I_{i}$ can be identified
by one or several etypes. $t(I_{i})$ refers to the set of associations between
entities and properties. We consider that the property $p_{i}$ is used to
describe an etype $C_{i}$ or an entity $I_{i}$ when the property belongs to
set $T(C_{i})$ or $t(I_{i})$, respectively. Thus, given a reference $KG_{ref}$
and a candidate $KG_{cand}$, considering the two cases in KG alignment, etype
alignment task aims to align the candidate etypes $C_{cand}$ with the
reference etypes $C_{ref}$, and etype recognition task aims to align the
candidate entities $I_{cand}$ with $C_{ref}$, where $C_{cand},I_{cand}\in
KG_{cand}$, $C_{ref}\in KG_{ref}$111Notice both etype alignment and etype
recognition are specific tasks of KG alignment..

###  2.2 Observations and Motivations

Figure 1: An example of the hierarchical schema in KG.

Property is one of the most basic and critical elements for intentionally
defining KG concepts, which is independent of the specific label used to name
concepts and of the specific hierarchical schema of KGs [31]. For each KG
schema, etypes play the role of categorization, and properties aim to draw
sharp lines so that each entity in the domain falls determinately either in or
out of each etype [29]. Meanwhile, we also have the following observations
when comparing properties across different KGs:

  * •

In a specific KG, each etype is described by a set of properties, whereas most
of the properties are distinguishable according to the belonging etypes and a
small number of properties are shared across different etypes.

  * •

Same or similar properties are shared across different KGs for describing same
concepts.

To clearly present these observations, we introduce a special type of Venn
graphs, namely knowledge lotuses, to represent the shareability of properties
that occurs within and across KGs. Knowledge lotuses provide a synthetic view
of how different KGs overlap in properties [30]. Figure 1 (b)-(d) show several
examples222The values in the lotuses in Figure 1 (b)-(d) are computed via a
lexical analysis method., where we assume that we have four contexts built
from (parts of) the four biggest KGs, namely OpenCyc333www.cyc.com,
DBpedia444https://www.dbpedia.org/, Schema.org555https://schema.org/, and
FreeBase [9]. Each value in a lotus refers to the number of shared properties.
For instance, in Figure 1 (b), we notice that the two etypes Person and
Organization share four properties in DBpedia. In Figure 1 (c), we can see
that the definitions of Person, as in OpenCyc and DBpedia, share twenty-three
properties. Meanwhile, we also present concrete shared properties of etype
Person across different KGs in Table 1, e.g., birth and education are applied
in both OpenCyc and DBpedia. All these examples present features of
properties, namely, the unity for describing the same concept and the
diversity for distinguishing different concepts. For instance, a Person can be
distinguished from a Place by the property birth, which is a crucial step to
align etypes and identify the type of entities. Thus, inspired by these
observations, we find that it is important to exploit and measure properties
for better performance of KG alignment and extension tasks.

Table 1: Shared Properties of etype Person across different KGs. Contexts |  | Tot. |  | Shared Properties
---|---|---|---|---
OpenCyc & DBpedia |  | 39 |  | birth, education, title, activity, ethnicity, employer, status…
OpenCyc & Schema.org |  | 21 |  | contact, suffix, tax, job, children, works, worth, gender, net…
DBpedia & FreeBase |  | 33 |  | title, number, related, birth, parent, work, name…
DBpedia & Schema.org |  | 22 |  | death, sibling, point, member, nationality, award, parents…

##  3 Knowledge Graph Formalization

We formalize the relation between properties and KG concepts as associations
to introduce the property information into the target KG tasks. At the schema
level, the KG schema will be flattened into a set of triples, where each
triple encodes information about etype-property associations, e.g., triple
“organization-domain-LocatedIn” encodes the “organization-LocatedIn”
association. Instance-level cases generally define triples as “entity-
property-entity”, where two associations are encoded. For instance, instance-
level triple “EiffelTower-LocatedIn-Paris” encodes two entity-property
associations “EiffelTower-LocatedIn” and “LocatedIn-Paris”. We introduce FCA
[27] to encode such associations as a formalization of the KGs we process.
Notice that both the schema-level and instance-level associations are included
in the formalization. Specifically, we have two working assumptions:

  * •

We consider both etypes $C$ and entities $I$. Similar to general formalization
methods [51, 18], we associate an entity with its set of properties
$t(I_{i})$. Different from general methods, we also associate an etype with
its set of properties $T(C_{i})$.

  * •

Etype characterization exploits not only the properties associated with it but
also the properties which are associated with other concepts. Thus, we
introduce the notion of unassociated properties and exploit this distinction
in the formalization process.

As an example, the hierarchy of the KG schema in Figure 1 is extracted from
DBpedia [4]. In each box, etypes are presented in yellow and their properties
in green. The arrow refers to the sub-class of relation between two etypes. We
then formalize these etypes into an FCA context as shown in Figure 2. We adopt
the following conventions. The value box with a “+1” represents the fact the
property is associated with the etype, e.g., citizenship is associated with
Person. The value box with a “-1” means the property is unassociated with the
etype, e.g., date is not used to describe etype Person. The value “0” (for
undefined) represents the fact that the property is unassociated with the
etype but associated with one of its sub-classes. The intuition is that the
property might or might not be used to describe the current etype, e.g.,
academy award is used to describe Artist and it might be used to describe
Person since Artist is a subclass of Person. Similar to etypes, we can also
find formalized entities and their properties in Figure 2. Need to notice that
these entities are selected from the KG with a hierarchical schema, thus, they
can inherit the unassociated properties from their etypes, e.g., as an
Athlete, Usain Bolt does not have property duration.

Figure 2: An example of formalizing KG into FCA contexts

We encode the above-mentioned three correlations as the parameter $w_{E}(p)$.
Since the correlation of “associated with” is positive for a property-based
description, the correlation of “unassociated with” is negative and the
correlation of “undefined” is neutral, we define the parameter as:

$w_{E}(p)=\left\\{\begin{tabular}[]{ll}1,&if $p\in prop(E)$\\\ 0,&if $p\notin
prop(E)\land p\in prop(E.subclass)$\\\ -1,&if $p\notin prop(E)\land p\notin
prop(E.subclass)$\end{tabular}\right.$ (1)

where we suppose $K$ as the union of etypes $C$ and entities $I$ in a KG for a
general demonstration and the etype/entity $E\in K$, $p$ is the target
property, $E.subclass$ refers to the sub-classes of the etype $E$ and
$prop(E)$ refers to the properties associated with $E$. Need to notice a
special case that undefined properties also exist where a specific entity
misses the inherited property, such as race track is used to describe Sports
events but missed for its entity Snooker Championship, which will also make
$w_{E}(p)=0$. In this case, we encode properties for each etype and then
record the properties associated with each entity. If an entity does not
contain a property it should inherit from its etype, it is considered
undefined. With our designed KG formalization method, we distinguish several
concrete situations for learning the association between properties and
etypes/entities and encoding more property information. The proposed
formalized approach serves as a pre-process for subsequent property-based
similarity methods used in computations in the following sections.

##  4 Property-based Similarity Metrics

One of the intuitions of our work is to identify etypes and entities by
properties that are essential elements for defining KG concepts [30]. The
reference etype tends to match with the candidate etype/entity when they have
properties overlapped. Therefore, it is critical to measure the overlapped
properties between etypes since etypes with completely overlapped properties
rarely happen in real-world KGs [26]. Meanwhile, we also exploit the
intuitions underlying the normalization of the “get-specific” heuristic
provided in [33] to distinguish the weights of different overlapped
properties. The key inspiration is that properties at different levels of
specificity have different relevance in the etype recognition. In particular,
a more specific property provides more information that allows for defining
concepts. As a result, in this section, we introduce three notions of
horizontal specificity, vertical specificity, and informational specificity
and their corresponding similarity metrics for measuring the degree of
overlapped properties.

###  4.1 Horizontal Specificity

For measuring the specificity of a property, a possible idea is to
horizontally compare the number of etypes that are described by a specific
property, namely the shareability of the property [30]. If a property is used
to describe diverse etypes, it means that the property is not highly
characterizing its associated etypes. Thus, for instance, in figure 1, the
property name is used to describe Person, Place, Athlete and Artist, where
name is a common property that appears in different contexts. Dually,
settlement is a horizontally highly specific property since it is associated
only with the etype Place. Based on this intuition, we consider the
specificity of a property as related to its shareability. Therefore, we
propose $HS$ (Horizontal Specificity) for measuring property specificity. More
precisely, $HS$ aims to measure the number of etypes that are associated with
the target property in a specific KG. We model $HS$ as:

$HS_{KG}(E,p)=w_{E}(p)*{e^{\lambda(1-|K_{p}|)}}$ (2)

where: $p$ is the input property and $K_{p}$ is the set of etypes described by
the input property in a specific $KG$ and $|K_{p}|$ is the number of etypes in
$K_{p}$, thus $|K_{p}|\geq 1$; $e$ denotes the natural mathematical constant
[25]; $\lambda$ represents a constraint factor, the range of $\lambda$ is
$(0,1]$. The reason for using an exponential function to model the $HS$ is
that we aim to normalize the horizontal specificity. The motivation is that
different properties may have a larger difference on $|K_{p}|$ in large KGs.
Need to note that the range of the $HS$ is $[-1,1]$, and the extremum points
both indicate that the property is shared by one or a few etypes, signifying
that the property is highly specific. The impact of such specificity is
determined by the target etypes used for description, which is captured by the
$\lambda$, resulting in different outcomes.

###  4.2 Vertical Specificity

Etypes are organized into classification hierarchies such that the upper-layer
etypes represent more abstract or more general concepts, whereas the lower-
layer etypes represent more concrete or more specific concepts [33, 45].
Correspondingly, properties of upper-layer etypes are more general since they
are used to describe general concepts, vice versa, properties of lower-layer
etypes are more specific since they are used to describe specific concepts. We
assume that lower-layer properties will contribute more to the identification
of an etype since they are more specific. For instance, in Figure 1, as a
lower-layer etype, Artist can be identified by the property academy award but
not by the property name. Based on this intuition, we propose $VS$ for
capturing the vertical specificity, as follows:

$VS_{KG}(E,p)=w_{E}(p)*\min_{E\in K_{p}}layer(E)$ (3)

where $layer(E)$ refers to the calculation based on the layer of the
inheritance hierarchy where an etype $E$ is defined, under a min-max
normalization. Note that $layer(E)\in[0,1]$ and all $E$ in set $K_{p}$ are
described by $p$. The range of $VS$ is $[-1,1]$, and extremum of the $VS=1$
and $VS=-1$ demonstrates the property is hierarchically specific while holding
opposing impacts on the target etype, and $VS=0$ demonstrates the property is
not specific enough from the hierarchical point of view.

###  4.3 Informational Specificity

Horizontal specificity allows measuring the shareability of properties, which
is independent and does not change (increase/decrease) with the number of
entities populating it. We take into account this fact by introducing the
notion of informational specificity $IS$. The intuition is that $IS$ will
decrease when the entity counting increases. Thus, for instance, the $IS$ of
gold medalist decreases when there are increasing entities of athletes, as
from the schema in Figure 2. Clearly, $IS$, differently from $HS$, can be used
in the presence of entities. The definition of informational specificity is
inspired by Kullback–Leibler divergence theory [54], which is introduced to
measure the difference between two sample distributions $Y$ and $\hat{Y}$.
More specifically, given a known sample distribution $Y$, assume that a new
coming attribute $x$ changes $Y$ to $\hat{Y}$. Then, the Kullback–Leibler
divergence theory demonstrates that the importance of $x$ for defining $Y$ is
positively related to the difference between $Y$ and $\hat{Y}$. In the
definition of informational specificity, we need to exploit some notions from
information theory, where we apply informational entropy $H(K)$ as:

$H(K_{v})=\frac{-\sum_{i=1}^{|K_{v}|}F(E_{i})\log\frac{F(E_{i})}{F(K_{v})}}{F(K_{v})}$
(4)

where $K_{v}$ refers to any subset of $K$ in a KG and $|K_{v}|$ is the number
of etypes included; $H(\cdot)$ represents the informational entropy of an
etype set; $E_{i}$ is a specific etype in set $K_{v}$, thus $|K_{v}|\geq 1$;
$F(E_{i})$ refers to the number of samples of etype $E_{i}$, and $F(K_{v})$
refers to the number of all samples in $K_{v}$. Need to notice when we
calculate the informational entropy for KGs without entities, $F(E_{i})=1$
since each KG includes one etype sample. For KGs with entities, $F(E_{i})$ and
$F(K_{v})$ depend on the number of samples of the given etype and the subset
of KG. After obtaining informational entropy, the informational specificity
$IS$ of property is defined as:

$IS_{KG}(E,p)=w_{E}(p)*(H(K)-H(\hat{K}))$ (5)

where $K$ is the set of all etypes in $KG$, and $\hat{K}$ is the set of etypes
without associated with the input property $p$, thus $\hat{K}=K-K_{p}$. Being
subtracted by the overall informational entropy $H(K)$, $IS$ presents the
importance of the property $p$ for describing the given etype set $K$. For
computational convenience, we employ the min-max normalization method to
constrain the calculation results within the range of $[-1,1]$.

###  4.4 Similarity Metrics

We have modeled the specificity of properties, which represent their weights
for describing KGs from different measuring aspects. Then, we define three
similarity metrics based on the corresponding specificity to measure the
property overlapping between two concepts. Given two KGs, the reference KG $A$
and candidate KG $B$, we define a function for calculating different
similarities between etypes/entities from $A$ and $B$ based on their
corresponding specificity:

$Sim(E_{a},E_{b})=\frac{1}{2}\sum_{i=1}^{k}\left(\frac{SPC_{A}(E_{a},p_{i})}{|prop(E_{a})|}+\frac{SPC_{B}(E_{b},p_{i})}{|prop(E_{b})|}\right)$
(6)

where we take $E_{a}$, $E_{b}$ as the candidate etypes from $A$ and $B$
respectively, thus $E_{a}\in A$ and $E_{b}\in B$; $prop(E)$ refers to the
properties associated with the specific etype and $|prop(E)|$ is the number of
properties in $prop(E)$; $SPC_{ETG}(\cdot)$ represents the specificity
measurements we defined above,
$SPC(\cdot)=\\{HS(\cdot),VS(\cdot),IS(\cdot)\\}$, thus $SPC_{A}(E_{a},p_{i})$
and $SPC_{B}(E_{b},p_{i})$ refer to the specificity of the aligned property
$p_{i}$ in $A$ and $B$ respectively; $k$ is the number of aligned properties
which are associated with both etype $E_{a}$ and $E_{b}$. As a result, we
obtain three similarity metrics which are horizontal similarity $Sim_{H}$,
vertical similarity $Sim_{V}$ and informational similarity $Sim_{I}$.

Notice that each similarity metric is symmetric, more specifically,
$Sim(E_{a},E_{b})=Sim(E_{b},E_{a})$. Note also that we apply z-score
normalization [42] to all similarity metrics at during calculations to
constrain the range of $Sim_{H},Sim_{V},Sim_{I}$ in $[0,1]$ for computational
convenience purposes. The normalization following the function
$z=\frac{x-\mu}{\sigma}$, where $z$ is the normalized value, $x$ is the
original value, $\mu$ is the mean of all values, and $\sigma$ is the standard
deviation of all values.

##  5 The Proposed Method

Figure 3: The framework of KG alignment and extension.

In order to extend the reference KG by given candidate KGs, we propose a
framework that exploits the FCA formalization and property-based similarity
metrics defined above, shown in Figure 3. The framework mainly consists of six
modules, namely: KG parser, KG formalization module, property matcher,
similarity calculation module, etype matcher, and KG extension module. Notice
that modules are marked in different colors for distinguishing their usage.

Different from KG completion task [60, 57] which manipulates entities in a
single KG, there will be two (or more) KGs involves in the KG extension task,
where we have $KG_{ref}$ and $KG_{cand}$ as inputs. The KG parser aims to
parse the input KG as a structured set of etypes, entities, and properties.
The KG will be flattened into a set of triples, where associations will be
extracted from triples. Then the triples and associations will be used to
generate an FCA for each input KG by the KG formalization module666The KG
parser and the formalization module are marked in blue since they are data
processing modules in the framework.. After all properties of input KGs have
been collected, they are sent to the NLP-based property matcher. Different
labels of properties may express similar meanings since many of them are
variations of the same label. Thus, an NLP pipeline is designed to normalize
all input properties, where phrase segmentation, lemmatization, and stop-word
removal are introduced for better normalization performance. String-based and
language-based similarity metrics are exploited for matching the properties by
normalized labels [6, 7]. Then, we align properties from input KGs following
the results of property matcher. In the next phase, we generate the proposed
property-based similarity metrics $Sim_{H}$, $Sim_{V}$, and $Sim_{I}$ by
inputting the FCA contexts and aligned properties. According to the Function
(6), three similarity values will be generated for each etype pair, which will
then be passed to the etype matcher together with general string-based and
language-based similarity metrics. We will align etypes by the output of the
etype matcher777Two matchers and the following alignment operations are marked
in yellow.. In the final step, the knowledge extension module888Notice the
modules with algorithms, i.e., similarity calculation and KG extension module,
are marked in red. integrates entities from the candidate KG according to the
new reference KG schema that is updated with aligned etypes. In Figure 3 we
use a circle arrow to demonstrate this process since our method will first
implement etype-etype alignment to integrate the aligned etypes directly into
the reference KG, and then implement entity-etype alignment to integrate the
rest of entities. The final output of the framework is an extended reference
KG with integrated etypes and entities.

###  5.1 Similarity Calculation Algorithm

Algorithm 1 Calculating horizontal similarity $Sim_{H}$ between reference and
candidate KGs. $L_{H}=SimilarityCalculation(f_{a},f_{b})$

0: Reference and candidate FCA contexts $f_{a}$, $f_{b}$;

0: List of all horizontal similarities $L_{H}$;

1: $PM=(p_{a}\times p_{b})=PropertyMatcher(f_{a},f_{b})$; {$PM$ is formed as a
set of aligned property pairs, where $p_{a}\in f_{a}$, $p_{b}\in f_{b}$.}

2: $EM=(E_{a}\times E_{b})=EtypeSelector(f_{a},f_{b})$; {etypes $E_{a},E_{b}$
from $f_{a},f_{b}$ are assembled as candidate calculation pairs $EM$.}

3: for all $(E_{j},E_{k})\in EM$ do

4: $sim_{H}(E_{j},E_{k})=0$; {initialize the value of horizontal similarity
$sim_{H}(E_{j},E_{k})$.}

5: for all $(p_{n},p_{m})\in PM$ do

6: if $p_{n}\in prop(E_{j})\wedge p_{m}\in prop(E_{k})$ then

7:
$sim_{H}(E_{j},E_{k}).add(\frac{HS_{A}(E_{j},p_{n})}{|prop(E_{j})|}{+}\frac{HS_{B}(E_{k},p_{m})}{|prop(E_{k})|})$;
{calculate the corresponding specificity $HS$ for the similarity
$sim_{H}(E_{j},E_{k})$.}

8: end if

9: end for

10: $L_{H}.stack(\frac{1}{2}*sim_{H}(E_{j},E_{k}))$; {stack the value of
horizontal similarity to the list $L_{H}$.}

11: end for

12: return $L_{H}$

The property-based similarity calculation is one of the critical parts of this
work. We detail the calculation as $SimilarityCalculation(\cdot)$, as shown in
Algorithm 1. After formalizing reference $KG_{ref}$ and candidate $KG_{cand}$,
we assume that the two FCA contexts $f_{a}$ and $f_{b}$ are generated
correspondingly. Then we obtain property matching pairs $PM$ from the property
matcher. To calculate the similarity of etypes, we need to generate candidate
etypes pairs $EM$ for further processing. For each candidate pair in $EM$, we
check their correlated properties and update the specificity values to
$Sim_{H}$, $Sim_{V}$ and $Sim_{I}$ when their properties are aligned. After
traversing all the candidate pairs, we obtain a complete etype similarity list
$L$ which will be used for training the ML model and aligning candidate
etypes. Notice that we present the algorithm for calculating the horizontal
similarity $Sim_{H}$ in algorithm 1, the metrics vertical similarity $Sim_{V}$
and informational similarity $Sim_{I}$ will be calculated by the same
algorithm where the only modification is to change $HS_{KG}(\cdot)$ to
$VS_{KG}(\cdot)$ and $IS_{KG}(\cdot)$, respectively.

###  5.2 Knowledge Graph Extension Algorithm

Algorithm 2 Extending reference KG by integrating a candidate KG.
$KG_{ext}=KGExtension(KG_{ref},KG_{cand},EM_{ali})$

0: Reference and candidate knowledge graphs $KG_{ref}$, $KG_{cand}$;Aligned
etype pairs $EM_{ali}$;

0: The extended reference knowledge graph $KG_{ext}$;

1: for all $(E_{a},E_{b})\in EM_{ali}$ do

2: $E_{a}.addProperty(E_{b}.property)$; {Merging the properties of etype
$E_{b}$ into $E_{a}$, where $E_{a}\in KG_{ref},E_{b}\in KG_{cand}$. }

3: $E_{a}.addEntities(E_{b}.Entities)$; {Merging the entities of $E_{b}$ into
$E_{a}$. }

4: for all $E_{sub}\in E_{b}.subClass$ do

5: $E_{a}.addSubClass(E_{sub})$; {Merging the etypes $E_{sub}$ and their
entities into $E_{a}$.}

6: end for

7: $KG_{ext}.update(E_{a})$;

8: end for

9: $E_{ref}=listEtypes(KG_{ref})$;

10: $Ent_{cand}=listEntities(KG_{cand})$;

11: for all $Ent_{i}\in Ent_{cand}$ do

12: if $Ent_{i}\notin EM_{ali}$ then

13: $E_{n}=EtypeRecognizer(Ent_{i},E_{ref})$; {Recognizing the etype $E_{n}$
of candidate entities $Ent_{i}$, where $E_{n},E_{ref}\in KG_{ref}$.}

14: $E_{n}.addEntities(Ent_{i})$;

15: end if

16: $KG_{ext}.update(E_{n})$

17: end for

18: return $KG_{ext}$

With the help of etype alignment results, we extend the reference KG by
integrating the entities from the candidate KG $KG_{cand}$, details are shown
in Algorithm 2. For each etype $E_{b}$ that is aligned with etype $E_{a}$ from
$KG_{cand}$, we directly add its properties and entities into $E_{a}$ by
$addProperty(\cdot)$ and $addEntities(\cdot)$, respectively. We also consider
all subclasses of the aligned etype $E_{b}$ since the subclass inherit the
properties of the etype and will bring new entities. If the subclass $E_{sub}$
of $E_{b}$ is not aligned with any other etypes in $KG_{ref}$, $E_{sub}$ and
its associated properties and entities will be merged into $E_{a}$. Thus, we
integrate candidate entities with $KG_{ref}$ when their etypes are able to
align with $KG_{ref}$. Then, the proposed property-based similarity metrics
are applied to align the rest of the candidate entities with etype $E_{ref}$
from reference KG, namely function $EtypeRecognizer(\cdot)$. If we
successfully match an etype $E_{n}$ with the entity $Ent_{i}$, $Ent_{i}$ will
be merged into $E_{n}$, if not, $Ent_{i}$ will be discarded. Need to notice
that depending on the real-world application scenario and topic, the KG
engineer will decide if it is needed to integrate the not aligned etypes with
their correpsonding entities into $KG_{ref}$. Finally, all changes will be
updated to $KG_{ref}$ and we will obtain an extended KG $KG_{ext}$ as the
final result of our method.

###  5.3 Machine Learning-based Matchers

According to the Algorithm 2 and Figure 3, we can find there are three ML-
based matchers in our proposed framework. Here we present more details of
training and setting these matchers.

####  5.3.1 Etype Matcher

We develop an ML-based method that deals with etype matching as a binary
classification task. The main idea is to predict if two incoming etypes are
aligned with each other. For applying this method, a list of candidate pairs
are generated by pairing etypes from $KG_{cand}$ and $KG_{ref}$. We will
record candidate etype pairs $EM_{ali}$ when the result of classification is
“aligned”. The proposed property-based similarity metrics $Sim_{H}$, $Sim_{V}$
and $Sim_{I}$ are introduced to train the ML models for matching etypes. For
better performance, we also exploit label-based and language-based similarity
metrics, along with property-based similarity metrics for training the etype
matcher.

####  5.3.2 Etype Recognizer

The strategy for developing an etype recognizer is very similar to the etype
matcher, where we predict if candidate entities are aligned with target
etypes. Thus, we will also generate candidate pairs that consist of entities
from $KG_{cand}$ and etypes from $KG_{ref}$. Etypes from $KG_{ref}$ will be
outputted as the final recognition results. Compared to the etype matcher, the
main difference is that the etype recognizer mainly uses property-based
similarity metrics as features for model training since the lexical labels are
not applicable to match entities and etypes. Thus, property-based similarity
metrics $Sim_{H}$, $Sim_{V}$, and $Sim_{I}$ are applied for the etype
recognizer.

####  5.3.3 Property Matcher

The property matcher aims to align properties between KGs, where label-based
and language-based similarity metrics are used for modeling training. The
matching strategy is same as etype matcher. It is critical to obtain a
powerful property matcher since both etype matcher and etype recognizer are
based on the result of property matcher. In this section, we discuss the
following solutions to reduce the effect of misaligned properties.

  * •

Use of the formalization parameter $w_{E}(p)$. As we introduced in section 2,
besides “associated” (positive) and “unassociated” (negative) properties, we
also defined “undefined” properties (neutral). Since misaligned properties
will not be used for similarity calculation, they are treated as “undefined”
properties which will not affect the model training and reduce the additional
interference. However, additional interference from misaligned properties
appears if “unassociated” and “undefined” properties are not distinguished.

  * •

Use of similarity metrics. Similar to lexical-based similarity metrics, our
property-based similarity metrics also allow to match etypes by soft aligning,
even if there are few properties not aligned. This will increase the
robustness of our etype recognition approach.

  * •

Use of ML-based models. By learning from the practical data from different
resources, ML models will propose a learnable strategy rather than a fixed
threshold for determining alignments, which will maximize the use of existing
aligned properties and minimize the effect of misaligned properties.

##  6 Evaluation

In this section, we aim to evaluate our proposed method by two crucial steps
during KG integration, including (1) etype alignment, and (2) etype
recognition of entities. Thus, we organize this section as follows. Section
6.1 introduces the experimental setups, including the datasets we used,
feature selection, and evaluation strategy. Sections 6.2 and 6.3 present the
analysis and quantitative evaluation results, respectively. In section 6.4, we
also demonstrate the ablation study to explain the setting of parameters.

###  6.1 Experimental Setup

####  6.1.1 Dataset Selection.

For evaluating the result of etype alignment, we exploit the Ontology
Alignment Evaluation Initiative999http://oaei.ontologymatching.org/2021/
(OAEI) as the main reference for the selection of the etype recognition
problems. As of today, this in fact the major source of KG alignment problems.
Our proposed method for KG extension involves extending a reference KG through
one or more candidate KGs. This implies that the reference KG typically
possesses a more comprehensive and high-quality schema, serving as a
foundation for KG extension. Our approach focuses on KGs that incorporate
etypes associated with a substantial number of properties and complete
schemas. As a result, we have selected the following cases: the bibliographic
ontology dataset (BiblioTrack) [20] and conference track (ConfTrack) [59]
($ra1$101010https://owl.vse.cz/ontofarm/ version). From the bibliographic
ontology dataset, we select #101-103 and series #301-304, which present real-
life ontologies for bibliographic references from the web. We select the
alignment between #101 and #304 as the training set for training our ML-based
etype matcher, and the rest of the ontology alignments as the testing set. The
conference track contains 16 ontologies, dealing with conference
organizations, and 21 reference alignments. We set all 21 reference alignments
from the conference track as the testing set to validate our etype matcher.
Notice that we select the training and testing set from different datasets
since we aim to prove the adaptation of our approach, which also prevents our
approach from overfitting.

For validating the algorithm of etype recognition, we build a dataset called
EnType, since there is no publicly released dataset for such etype recognition
task between two KGs. We exploit DBpedia infobox
dataset111111http://wikidata.dbpedia.org/services-resources/ontology as the
reference KG for providing reference etypes. Because DBpedia is a general-
purpose KG that contains common etypes in the real world, where sufficient
properties are applied for describing these etypes. Then we select candidate
entities from DBpedia, SUMO and several domain-specific datasets [53]. The
entities we selected mainly according to common etypes, more specifically,
Person, Place, Event, Organization and their sub-classes. Finally, we obtain
20,000 etype-entity candidate pairs, where 6,000 from DBpedia (EnTypeSelf) and
14,000 from the remaining resources (EnTypeGen). Need to notice, this dataset
will be randomly separated into the training and testing set to implement the
ML model.

####  6.1.2 Feature Selection.

Our approach applies a general binary classification strategy, which is
independent of the specific ML model. Thus, the data label of positive and
negative samples refers to if the pair etype-etype or etype-entity is aligned.
Besides our property-based similarity metrics, some of the most common string-
based and language-based similarity metrics are selected as additional metrics
for achieving better etype recognition performance. The data consists of three
kinds of features, which are property-based similarity metrics ($Sim_{H}$,
$Sim_{V}$ and $Sim_{I}$), string-based similarity metrics (N-gram [21],
Longest common sub-sequence [21], Levenshtein distance [58]) and language-
based similarity metrics (Wu and Palmer similarity [41] and Word2Vec [17]).
These similarity metrics aim to measure different aspects of the relevance
between the reference etype and candidates. Since all the above-mentioned
similarity metrics are symmetric, the order of etype/entity in the candidate
pair will not affect the final results. Moreover, we apply only property-based
similarity metrics ($Sim_{H}$, $Sim_{V}$ and $Sim_{I}$) for etype recognition
since the label of the candidate entity are commonly not relevant to its
etype.

####  6.1.3 Training Strategy.

We have discussed that candidate pairs for applying binary classification in
different etype recognition tasks. However, positive and negative samples in
candidate pairs are usually not balanced in practice, more specifically,
negative samples will be produced much more than positive samples. For
instance, there will be one million candidate pairs generated when aligning
two KGs that contain 1,000 etypes each, where only hundreds of them are
positive samples. As a result, the ML model trained by such unbalanced
datasets easily to be overfitted. To address this issue, we propose a model
training strategy that increases the weight of positive samples to achieve a
balanced training set and alleviate overfitting. By duplicating a part of
positive samples, we achieve the best etype recognition performance by keeping
the ratio of positive and negative samples as 1:10. Notice that such a data
augmentation strategy is not applied to the testing set, the candidate pairs
in the testing set are selected randomly to avoid interference.

####  6.1.4 Dealing with Trivial Samples.

In order to decrease the negative samples and avoid generating unnecessary
candidate pairs, we prune the trivial samples which are obviously to be
negative. Regarding different tasks, we have:

  * •

For etype alignment task, we apply label-based measurements to filter the
obviously negative samples. Given two etypes $E_{a}$ and $E_{b}$ from a
candidate pair, we define the pre-selection factor $PS_{s}$ as:

$PS_{s}=Ngram(E_{a},E_{b})+Word2Vec(E_{a},E_{b})$ (7)

where $Ngram(\cdot)$ and $Word2Vec(\cdot)$ are two similarity measurements;
$Ngram(\cdot)$ assesses lexical similarity between strings by analyzing
contiguous sequences of n items from a given string [21]; $Word2Vec(\cdot)$
captures semantic similarity between strings through deep feature
representations using the Word2Vec model [17]. Thus, we consider
$(E_{a},E_{b})$ to be an obviously negative candidate etype pair if $PS_{s}$
is greater than the threshold $th$. Experimentally, we find that $th=0.3$ will
lead to better results, where around 70% of trivial sample pairs are reduced
while maintaining minimal interference with the majority of positive samples.

  * •

For the etype recognition task, the obviously negative candidate pair is
identified when two entities $I_{a}$ and $I_{b}$ have no shared property.
Thus, such candidate pairs will be pruned before inputting into the etype
recognizer.

The pre-selection of trivial samples will effectively reduce the run-time for
model training. Moreover, such a training strategy will help to decrease the
risk of overfitting by alleviating redundant samples and to improve the
performance of KG alignment.

####  6.1.5 Evaluation metrics.

In our experiment, we exploit standard evaluation metrics including precision
(Prec.), recall (Rec.) and $F_{1}$-measure ($F_{1}$-m.), and additional
$F_{0.5}$-measure ($F_{0.5}$-m.) and $F_{2}$-measure ($F_{2}$-m.) [44] to
comprehensively validate our method and compare it with state-of-the-art
methods. We form the etype recognition candidates as pairs, where each pair
consists of a reference etype and a candidate etype/entity alignment.
$F_{\beta}$-measures ($F_{\beta}$-m.) are defined as the harmonic mean of
recall and precision:

$F_{\beta}\textbf{-m.}=(1+\beta^{2})*\frac{Prec.*Rec.}{\beta^{2}*Prec.+Rec.}$
(8)

where $\beta$ is the configuration factor that allows for weighting precision
or recall more highly if it is more important for the use case. And metrics
$F_{1}$-m., $F_{2}$-m. and $F_{0.5}$-m. are defined when
$\beta=\\{1,2,0.5\\}$, respectively. We consider the $F_{\beta}$-m. to be the
most relevant metrics for evaluation since it reflects both recall and
precision.

###  6.2 Etype Alignment

####  6.2.1 Qualitative analysis.

Table 2 provides representative examples to show the etype similarity metrics
of candidate etype-etype pairs from cmt-confof (former four rows) and cmt-
conference (latter four rows) in ConfTrack. Value box “Match” demonstrates if
two etypes are referring to the same concept, where $\times$ refers to a
positive answer. We find that the value of our property-based similarity
metrics indeed capture the contextual similarity between relevant etypes,
where aligned etypes output higher values (e.g., paper-contribution), in turn,
non-aligned etypes return lower values (e.g., person-document). With a broad
observation of the metric values, we consider the property-based similarity
metrics $Sim_{H}$, $Sim_{V}$ and $Sim_{I}$ are valid for etype-etype pairs.

Table 2: Representative samples of property-based similarity $Sim_{V}$, $Sim_{H}$ and $Sim_{I}$ on etype-etype pairs. Etyperef | Etypecand | $Sim_{V}$ | $Sim_{H}$ | $Sim_{I}$ | Match
---|---|---|---|---|---
Paper | Contribution | 1 | 0.853 | 0.730 | $\times$
SubjectArea | Topic | 0.756 | 0.740 | 0.857 | $\times$
Author | Topic | 0.198 | 0.353 | 0.018 |
Meta-Review | Poster | 0 | 0.312 | 0.262 |
Chairman | Chair | 1 | 0.559 | 0.554 | $\times$
Person | Person | 1 | 0.970 | 0.678 | $\times$
Person | Document | 0.02 | 0.06 | 0 |
Chairman | Publisher | 0 | 0.07 | 0.195 |

####  6.2.2 Quantitative Evaluation.

Table 3: Quantitative comparisons on etype alignment. Methods | ConfTrack | BiblioTrack
---|---|---
Prec. | Rec. |  $F_{0.5}$-m. |  $F_{1}$-m. |  $F_{2}$-m. | Prec. | Rec. |  $F_{0.5}$-m. |  $F_{1}$-m. |  $F_{2}$-m.
FCAMap [15] | 0.680 | 0.625 | 0.668 | 0.651 | 0.635 | 0.820 | 0.783 | 0.812 | 0.801 | 0.790
AML [24] | 0.832 | 0.630 | 0.782 | 0.717 | 0.662 | 0.869 | 0.822 | 0.859 | 0.845 | 0.830
LogMap [35] | 0.798 | 0.592 | 0.746 | 0.680 | 0.624 | 0.832 | 0.694 | 0.800 | 0.757 | 0.718
Alexandre et. al. [8] | 0.795 | 0.638 | 0.758 | 0.708 | 0.664 | 0.827 | 0.786 | 0.818 | 0.806 | 0.794
Nkisi-Orji et. al. [39] | 0.860 | 0.514 | 0.758 | 0.643 | 0.559 | 0.858 | 0.682 | 0.816 | 0.760 | 0.711
LogMapLt [35] | 0.716 | 0.554 | 0.676 | 0.625 | 0.580 | 0.796 | 0.781 | 0.793 | 0.788 | 0.784
ETAXGBoost | 0.827 | 0.676 | 0.792 | 0.744 | 0.702 | 0.870 | 0.832 | 0.862 | 0.851 | 0.840
ETAANN | 0.813 | 0.604 | 0.760 | 0.693 | 0.636 | 0.797 | 0.811 | 0.799 | 0.803 | 0.808

We apply two ML models to evaluate the validity of our proposed similar
metrics on the etype alignment task, including XGBoost [16] and artificial
neural network (ANN) classifier [37], namely ETAXGBoost and ETAANN. We
compared our work with state-of-the-art etype alignment methods121212as most
of them came out of previous OAEI evaluation campaigns, including FCAMap [15],
AML [24], CNN-based ontology matching [8], word-embedding-based ontology
alignment [39], LogMap and LogMapLt [35]. We calculate mentioned evaluation
metrics for a comprehensive comparison. Notice that we focus on the result of
etype-etype alignment in this experiment.

Table 3 shows the results of our approach with the different models mentioned
above, compared with the results of state-of-the-art methods. Firstly, we can
find our approach with different models produces different results. ETAXGBoost
performs better than ETAANN and also outperforms other methods on BiblioTrack
and most of the cases in ConfTrack. The method by Nkisi-Orji et. al. [39]
leads the precision on ConfTrack, while it poorly performs on recall for both
datasets. AML also shows competitive overall results compared to other state-
of-the-art methods. Considering the average results of our approach with
different models are performing better or close to the state-of-the-art, we
can say that our approach surpasses the state-of-the-art competitors on the
etype alignment task131313All methods do not have significant differences in
running times.. Meanwhile, the promising overall performance produced by two
different models indicates that our proposed similarity metrics and etype
alignment approach are valid and adaptive.

###  6.3 Etype Recognition of Entities

Table 4: Representative samples of $Sim_{V}$, $Sim_{H}$ and $Sim_{I}$ on etype-entity pairs. $C_{ref}$ | $I_{cand}$ | $Sim_{V}$ | $Sim_{H}$ | $Sim_{I}$ | Match
---|---|---|---|---|---
Person | MiltHinton | 1 | 0.787 | 0.873 | $\times$
Person | Jadakiss | 1 | 0.645 | 0.305 | $\times$
Person | Boston | 0.264 | 0.173 | 0.041 |
Place | Boston | 0.720 | 1 | 0.433 | $\times$
Place | Jadakiss | 0.128 | 0.093 | 0.148 |
Organization | MiltHinton | 0.070 | 0.022 | 0.092 |
Table 5: Quantitative evaluation of etype recognition on dataset EnType. Methods | Self recognition | General recognition
---|---|---
Person | Org. | Place | Event | Person | Org. | Place | Event
Sleeman et. al. [49] | 0.633 | 0.509 | 0.618 | 0.712 | 0.365 | 0.274 | 0.420 | 0.323
Giunchiglia et. al. [30] | 0.594 | 0.582 | 0.672 | 0.651 | 0.480 | 0.494 | 0.563 | 0.501
ETRXGBoost | 0.850 | 0.795 | 0.820 | 0.814 | 0.634 | 0.509 | 0.610 | 0.514
ETRANN | 0.863 | 0.760 | 0.837 | 0.808 | 0.589 | 0.435 | 0.497 | 0.486
Table 6: Quantitative evaluation of etype recognition on different entity
resolutions.

Methods | Person | Organization
---|---|---
Athlete | MilitaryPerson | Artist | Comedian | MilitaryOrg. | Company | SportsClub | ReligiousOrg.
Sleeman et. al. [49] | 0.639 | 0.472 | 0.690 | 0.597 | 0.479 | 0.463 | 0.637 | 0.510
Giunchiglia et. al. [30] | 0.658 | 0.429 | 0.736 | 0.522 | 0.512 | 0.487 | 0.624 | 0.482
ETRXGBoost | 0.756 | 0.508 | 0.760 | 0.581 | 0.656 | 0.487 | 0.719 | 0.550
ETRANN | 0.712 | 0.507 | 0.732 | 0.659 | 0.613 | 0.528 | 0.702 | 0.491

####  6.3.1 Qualitative Analysis

Table 4 presents some examples of similarity metrics between reference etypes
and candidate entities from the dataset EnType. Similar to Table 2, the value
box “Match” with $\times$ refers to that the candidate entity is classified as
the reference etype. Similar to what happened in candidate etype pairs, we
find the similarity metrics of aligned candidate pairs return much higher
values than unaligned pairs. Thus, we conclude the proposed similarity metrics
are also valid for measuring etype-entity pairs.

####  6.3.2 Quantitative Evaluation

As for the evaluation of the etype recognizer, we involve two subsets
EnTypeSelf and EnTypeGen in this experiment. The subset EnTypeSelf contains
candidate entities and reference etypes from the same KG, i.e., self
recognition, which should be a relatively easier task. In turn, general
recognition denotes the recognition on subset EnTypeGen, where candidate
entities are selected from other resources. Table 5 shows the results of etype
recognition ($F_{1}$-measure), where we exploit the same models as in the
etype alignment task, i.e., ETRXGBoost and ETRANN. Two state-of-the-art
methods[49, 30] are also included in the experiment. Firstly, we can find that
our methods ETR using the proposed property-based similarity metrics surpass
two state-of-the-art methods significantly. For the self recognition group,
ETRXGBoost performs better in two cases while ETRANN also achieves competitive
results. For general recognition cases, the XGBoost-based ETR method keeps its
stable performance and surpasses all comparing methods. We achieve promising
results in both cases, which prove the validity of our similarity metrics and
the etype recognition approach. Meanwhile, we find that the precision of the
general recognition case is lower than that of self recognition, which follows
the difficulty of the two cases.

Considering that etype recognition performance is affected by entity
resolutions, we apply an additional experiment for aligning entities with more
specific etypes. We select four sub-classes of etype person and organization
and their corresponding entities as candidate pairs, respectively. We keep
comparing ETRXGBoost, ETRANN and the same state-of-the-art methods in this
experiment. Table 6 presents the $F_{1}$-measure of the recognition results.
We can find our methods still achieve better recognition performance than
other methods in each case. Both two models obtain promising overall
performance on specific etype recognition, where ETRANN performs better on
Comedian and Company, and ETRXGBoost leads the rest of the cases. The
experimental results show that our metrics and approach can also be applied
for specific instance-level etype recognition, which further supports the
performance of KG extension algorithm.

###  6.4 Ablation Study

We demonstrate ablation studies in this section for validating the
effectiveness of some specific components introduced in our KG extension
framework.

####  6.4.1 Effect of similarity metrics

The first ablation study is to evaluate if each of the proposed property-based
similarity metrics is effective. In this experiment, we test the
backbones141414trained by all three metrics ($Sim_{V},Sim_{H},Sim_{I}$) (B)
which were used in the etype alignment and recognition tasks, respectively.
Based on the backbones, we also design a controlled group that includes models
trained without one of the property-based similarity metrics (i.e. B-SimV,
B-SimH and B-SimI) and models trained without all metrics (i.e. B-L). If the
backbones perform better than the corresponding models in the controlled
group, we can quantitatively conclude that each of the property-based
similarity metrics ($Sim_{V},Sim_{H},Sim_{I}$) contributes to the etype
alignment and recognition tasks. Table 7 demonstrates the $F_{1}$-measure of
each group. We apply ConfTrack for etype alignment and EnTypeGen for etype
recognition. Note that we select two models for both cases as Table 7 shows.
We find that backbones perform better than models in the controlled group,
especially for models trained without all metrics. Thus, we consider all
property-based similarity metrics contribute to better recognition
performance. Particularly, SimV and SimH significantly affect the performance
of etype alignment cases, and SimI affects etype recognition cases more.

Table 7: Ablation study on property-based similarity metrics. Dataset | Model | Backbone | B-SimV | B-SimH | B-SimI | B-L
---|---|---|---|---|---|---
ConfTrack | ETAANN | 0.713 | 0.635 | 0.639 | 0.660 | 0.618
ETAXGBoost | 0.740 | 0.648 | 0.655 | 0.694 | 0.632
EnTypeGen | ETRANN | 0.537 | 0.327 | 0.391 | 0.309 | -
ETRXGBoost | 0.559 | 0.413 | 0.402 | 0.385 | -

####  6.4.2 Effect of constraint factor

In section 4.1, we defined a constraint factor $\lambda$ for calculating the
metric $Sim_{H}$. This study aims to statistically identify the value of
$\lambda$. We apply the dataset ConfTrack and its two best-performed models.
The value of $\lambda$ is set evenly from 0.1 to 1 by discrete points. We
evaluate if this pre-set factor affects the final recognition performance and
obtain the best value of $\lambda$ for generic etype recognition. Table 8
demonstrates the results, where we highlight both the best and second-best
results. We can find that different values of $\lambda$ do affect the final
etype recognition performance. And two models show a similar trend that the
best value of $\lambda$ is close to 0.5. As a result, we assign $\lambda=0.5$
to calculate metric $Sim_{H}$ in our experiments.

Table 8: Ablation study on the constraint factor $\lambda$.The best and second-best results are highlighted in  red and  blue, respectively. Factor | Model | 0.1 | 0.2 | 0.3 | 0.4 | 0.5 | 0.6 | 0.7 | 0.8 | 0.9
---|---|---|---|---|---|---|---|---|---|---
$\lambda$ | ETAANN | 0.613 | 0.638 | 0.670 | 0.678 | 0.712 | 0.685 | 0.679 | 0.653 | 0.630
ETAXGBoost | 0.662 | 0.677 | 0.714 | 0.727 | 0.729 | 0.716 | 0.654 | 0.711 | 0.705

##  7 Case Study

This section aims to qualitatively analyze the KG extension performance of our
proposed method by use cases. In the case of KG extension, we assume that
there will be a reference KG extended based on one or more candidate KGs. We
aim to simulate a real-world scenario, where people extend the general purpose
KG by specific-domain KGs to enlarge its usability. We select the widely
applied schema.org as the reference KG. For the candidate KGs, we introduce
two specific-domain KGs
Transportation151515https://carlocorradini.github.io/Trentino_Transportation
and educationtrentino161616https://alihamzaunitn.github.io/kdi-
educationtrentino. These two KGs are created for presenting local
transportation and education, respectively. We selected these KGs because they
provide very different examples in terms of the number of properties and
etypes. Moreover, almost all their etypes labels are human understandable,
which helps qualitative analysis.

We introduce four ranking metrics in the case study, namely Class Match
Measure (CMM) [1], Density Measure (DEM) [1], Focus [26] and TF-IDF [46]. CMM
aims to evaluate the coverage of a KG for the given search etypes, by looking
for etypes in each KG that have labels matching a search term either exactly
or partially. DEM is intended to approximate the representational density or
information content of etypes and consequently the level of knowledge detail,
considering etypes including the number of subclasses, the number of
properties associated with that etype, the number of siblings, etc. Focus aims
to evaluate KG by identifying informative etypes with higher categorization
relevance, by using the properties associated with the target etypes. TF-IDF
is also widely used for KG ranking by calculating relevance between potential
KG with a specific term that describes the domain of interest. These metrics
are used to evaluate the quality of the extended reference KG, where we
compare the metrics on the original reference KG with the extended reference
KG to see if the new-coming items from candidate KGs affect the quality of the
reference KG. More specifically, we record the metrics for valid etypes in KG,
and use the performance of these scores as a baseline, by selecting their
scores for the top 15 etypes. The relevance of our approach is then measured
in terms of accuracy (from 0 to 1) by checking how many etypes of ranking
results are in the eypes ranking lists provided by the knowledge engineers.
The output of this experiment is represented in Fig. 4.

Figure 4: Experimental results of KG extension function.

The main observation is that our extended KG shows promising performance with
all metrics. More specifically, with the given terms chosen by knowledge
engineers, we can find the extended KG shows great categorization relevance by
metric Focus. The scores of CMM and DEM also show promising scores,
respectively, which demonstrates the quality of the knowledge coverage and the
representational density. Our KG gains a fair score on metric TF-IDF since the
reference schema.org is a general-purpose KG that contains pretty diverse
concepts, which will affect the relevance with specific domain corpus to some
extent. The second observation presents that the extended KG performs better
than the original KG on most of the metrics. The increasing score of metric
CMM presents that the new-coming items enlarge the coverage of the etypes in
the KG. The improving DEM score shows the details of etypes from reference KG
have been enhanced by the extended properties and subclasses. The increasing
Focus score also presents a trend where categories can be better identified
from a taxonomy perspective. Notice that the extended schema.org has even more
diverse concepts after KG extension, which becomes a possible reason for the
slight decrease in TF-IDF score. Overall, the experimental results in the case
study demonstrate the ability of our method for KG alignment and extension.

##  8 Related Work

###  8.1 Ontology Matching and Schema Alignment

Ontology matching and schema alignment are attractive research topics in
recent decades. In the early phases of the research, researchers mainly
focused on string-based methods. String analysis techniques were defined
including 1) string-based metrics (N-gram, Levenshtein, etc.), 2) syntactic
operations (lemmatization, stop word removal, etc.) and 3) semantic analysis
(synonyms, antonyms, etc.) [14]. Sun et al, [52] review a wide range of string
similarity metrics and propose the ontology alignment method by selecting
similarity metrics in different scales. Although string-based methods can lead
to effective performance in many cases, selecting the right metric for
matching specific datasets is the most challenging part. To solve this issue,
an ensemble matching strategy is introduced in some studies [12, 38], which
apply multiple matchers based on different string-based metrics. The principle
of these works is that the combined matchers are more powerful than individual
ones. The structure of a KG has also been considered as important information
for identifying etypes [28, 5]. Such studies suppose that two etypes are more
likely to be aligned if they have the same super-class or sub-class. The
LogMap system [35] uses a two-step matching strategy, that is, matches two
etypes $E_{a}$ and $E_{b}$ by a lexical matcher, and then considers the etypes
that are semantically close to $E_{a}$ are more likely to be semantically
close to $E_{b}$. AML [24] introduces an ontology matching system that
consists of a string-based matcher and a structure-based matcher, building
internal correspondences by exploiting is-a and part-of relationships.

Machine learning techniques have been widely applied to this topic. Some
studies model the etype matching task as a binary classification task, trying
to encode the information like string and structure similarities as features
for model training. Amrouch et al, [3] develop a decision tree model by
exploiting lexical and semantic similarities of the etype labels to match
schemas. By encoding the lexical similarity of the superclass and subclass as
structure similarity, Bulygin and Stupnikov [13] improve the former method and
achieve promising results. At the same time, formal concept analysis (FCA)
lattices are applied in schema matching methods [15, 51]. To refine the health
records searching outputs, Cure et al, [18] exploit FCA and Semantic Query
Expansion to assist the end-user in defining their queries and in refining the
expanded search space. Stumme et al, [51] propose a bottom-up ontology merging
approach by using FCA lattices to keep the ontology hierarchy.

###  8.2 Entity Type Recognition

According to the different usage and motivation, studies on entity type
recognition (also called entity typing) focus on three main directions: (1)
recognizing the type of entity from text [56, 40]; (2) recognizing the type of
entities from the single KG for KG completion [57, 60]; (3) recognizing the
type of entities from different KGs for KG extension [49], which is the focus
of this paper. Different from the former two tasks, we focus on recognizing
the type of etypes/entities from other KGs for extending the reference KG
automatically. In this field, some dedicated methods are proposed for specific
datasets [19, 47]. Rather than using label-based methods, some previous
studies also consider properties as a possible solution, [49, 48] propose an
etype recognition method by modeling etype recognition as a multi-class
classification task. However, a pre-filtering step is needed since only
properties shared across all candidates are counted for training and testing,
which means there will be a few properties remaining after such filtering and
a large amount of critical information will be discarded. Thus, the adaptation
of such methods will be limited when applied in practice. Giunchiglia and
Fumagalli [30] propose a set of metrics for selecting the reference KG to
improve the above method, which achieves improved performance with the support
of a large amount of KGs. However, there are still limitations since these
studies consider all properties with the same weight and neglect to
distinguish properties that will contribute differently during etype
recognition.

###  8.3 Knowledge Graph Extension

KG extension aims to integrate additional knowledge from other KGs. It is
different from KG self-completion which adds missing knowledge (concepts and
properties) into the reference KG without exploiting other resources. In the
context of the semantic web, most of the current cases locate the
corresponding entity pairs in KGs and then directly integrate KGs by taking
their union [34]. Several approaches for integrating schemas, given in terms
of theories of classical first-order logic and rule bases, have been proposed.
They either cast rules into classical logic or limit the interaction between
rules and schemas [22, 50]. Bruijn et al. [11] presented three embeddings for
ordinary and disjunctive nonground logic programs under the stable model
semantics to select KGs for integration. Wiharja et al. [55] improved the
correctness of KG combinations based on Schema Aware Triple Classification
(SATC), which enables sequential combinations of KG embedding approaches.
However, these approaches are still limited when applied in practice. Novel
methods for automatic schema integration are needed to extend general-domain
KGs in a efficient and accurate way.

##  9 Conclusions

In this paper, we have proposed an ML-based framework for KG alignment and
extension via a set of novel property-based similarity metrics. Firstly, we
introduce a KG formalization method, which encodes etypes/entities and their
corresponding properties into FCA contexts. We discuss that the corresponding
properties are used to intentionally describe etypes, which provides us with a
novel insight for identifying etypes. Then we propose three metrics for
measuring the contextual similarity between reference etypes and candidate
etypes/entities, namely the horizontal similarity $Sim_{H}$, the vertical
similarity $Sim_{V}$, and the informational similarity $Sim_{I}$. Based on our
proposed metrics, we introduce the framework with detailed algorithms and
modules for KG alignment and extension. Thus, we validate our framework for
the corresponding tasks. Compared with the state-of-the-art methods, the
experimental results show the validity of the similarity metrics and the
superiority of the proposed KG alignment methods, both quantitatively and
qualitatively. Our future work will focus on exploring the further utilization
of the proposed similarity metrics in tasks such as KG refinement and
completion, including complex KG matching cases and resolving conflicts during
the KG extension process. This exploration is expected to enhance the depth
and accuracy of knowledge extraction and increase the practical applicability
and adaptability of our proposed methods.

## Acknowledgements

The research conducted by Fausto Giunchiglia has received funding from the
_InteropEHRate_ project, co-funded by the European Union (EU) Horizon 2020
program under grant number 826106, and the research conducted by Daqian Shi
has received funding from the program of China Scholarships Council (No.
202007820024).

## References

  * [1] Alani, H., Brewster, C.: Metrics for ranking ontologies (2006)
  * [2] Algergawy, A., Cheatham, M., Faria, D., Ferrara, A., Fundulaki, I., Harrow, I., Hertling, S., Jiménez-Ruiz, E., Karam, N., Khiat, A., et al.: Results of the ontology alignment evaluation initiative 2018. In: 13th International Workshop on Ontology Matching co-located with the 17th ISWC (OM 2018). vol. 2288, pp. 76–116 (2018)
  * [3] Amrouch, S., Mostefai, S., Fahad, M.: Decision trees in automatic ontology matching. International Journal of Metadata, Semantics and Ontologies 11(3), 180–190 (2016)
  * [4] Auer, S., Bizer, C., Kobilarov, G., Lehmann, J., Cyganiak, R., Ives, Z.: Dbpedia: A nucleus for a web of open data. In: The semantic web, pp. 722–735. Springer (2007)
  * [5] Autayeu, A., Giunchiglia, F., Andrews, P.: Lightweight parsing of classications into lightweight ontologies. In: European Conference on Research and Advanced Technology for Digital Libraries (ECDL 2010). Glasgow, United Kingdom (September 2010)
  * [6] Bella, G., Giunchiglia, F., McNeill, F.: Language and domain aware lightweight ontology matching. Journal of Web Semantics 43, 1–17 (2017)
  * [7] Bella, G., Zamboni, A., Giunchiglia, F.: Domain-based sense disambiguation in multilingual structured data. In: The Diversity Workshop at the European Conference on Artificial Intelligence (ECAI) (2016)
  * [8] Bento, A., Zouaq, A., Gagnon, M.: Ontology matching using convolutional neural networks. In: Proceedings of the 12th language resources and evaluation conference. pp. 5648–5653 (2020)
  * [9] Berant, J., Chou, A., Frostig, R., Liang, P.: Semantic parsing on freebase from question-answer pairs. In: Proceedings of the 2013 conference on empirical methods in natural language processing. pp. 1533–1544 (2013)
  * [10] Berners-Lee, T., Hendler, J., Lassila, O.: The semantic web. Scientific american 284(5), 34–43 (2001)
  * [11] Bruijn, J.D., Eiter, T., Polleres, A., Tompits, H.: Embedding nonground logic programs into autoepistemic logic for knowledge-base combination. ACM Transactions on Computational Logic (TOCL) 12(3), 1–39 (2011)
  * [12] Bulygin, L.: Combining lexical and semantic similarity measures with machine learning approach for ontology and schema matching problem. In: Proceedings of the XX International Conference “Data Analytics and Management in Data Intensive Domains”(DAMDID/RCDL’2018). pp. 245–249 (2018)
  * [13] Bulygin, L., Stupnikov, S.A.: Applying of machine learning techniques to combine string-based, language-based and structure-based similarity measures for ontology matching. In: DAMDID/RCDL. pp. 129–147 (2019)
  * [14] Cheatham, M., Hitzler, P.: String similarity metrics for ontology alignment. In: International semantic web conference. pp. 294–309. Springer (2013)
  * [15] Chen, G., Zhang, S.: Identifying mappings among knowledge graphs by formal concept analysis. In: OM@ ISWC. pp. 25–35 (2019)
  * [16] Chen, T., Guestrin, C.: Xgboost: A scalable tree boosting system. In: Proceedings of the 22nd acm sigkdd international conference on knowledge discovery and data mining. pp. 785–794 (2016)
  * [17] Church, K.W.: Word2vec. Natural Language Engineering 23(1), 155–162 (2017)
  * [18] Curé, O.C., Maurer, H., Shah, N.H., Le Pendu, P.: A formal concept analysis and semantic query expansion cooperation to refine health outcomes of interest. BMC medical informatics and decision making 15(1), 1–6 (2015)
  * [19] Dsouza, A., Tempelmeier, N., Demidova, E.: Towards neural schema alignment for openstreetmap and knowledge graphs. In: International Semantic Web Conference. pp. 56–73. Springer (2021)
  * [20] Euzenat, J., Ferrara, A., Hollink, L., Isaac, A., Joslyn, C., Malaisé, V., Meilicke, C., Nikolov, A., Pane, J., Sabou, M., et al.: Results of the ontology alignment evaluation initiative 2009 (2010)
  * [21] Euzenat, J., Shvaiko, P., et al.: Ontology matching, vol. 18. Springer (2007)
  * [22] Fahad, M.: Initial results for ontology matching workshop 2015 dkp-aom: results for oaei 2015. In: CEUR Workshop Proceedings (2015)
  * [23] Färber, M., Ell, B., Menne, C., Rettinger, A.: A comparative survey of dbpedia, freebase, opencyc, wikidata, and yago. Semantic Web Journal 1(1), 1–5 (2015)
  * [24] Faria, D., Pesquita, C., Santos, E., Palmonari, M., Cruz, I.F., Couto, F.M.: The agreementmakerlight ontology matching system. In: OTM Confederated International Conferences” On the Move to Meaningful Internet Systems”. pp. 527–541. Springer (2013)
  * [25] Finch, S.R.: Mathematical constants. Cambridge university press (2003)
  * [26] Fumagalli, M., Shi, D., Giunchiglia, F.: Ranking schemas by focus: A cognitively-inspired approach. In: International Conference on Conceptual Structures. pp. 73–88. Springer (2021)
  * [27] Ganter, B., Wille, R.: Formal concept analysis: mathematical foundations. Springer Science & Business Media (2012)
  * [28] Giunchiglia, F., Autayeu, A., Pane, J.: S-match: an open source framework for matching lightweight ontologies. Semantic Web 3(3), 307–317 (2012)
  * [29] Giunchiglia, F., Fumagalli, M.: On knowledge diversity. In: JOWO (2019)
  * [30] Giunchiglia, F., Fumagalli, M.: Entity type recognition–dealing with the diversity of knowledge. In: Proceedings of the International Conference on Principles of Knowledge Representation and Reasoning. vol. 17, pp. 414–423 (2020)
  * [31] Giunchiglia, F., Shi, D.: Property-based entity type graph matching. arXiv preprint arXiv:2109.09140 (2021)
  * [32] Giunchiglia, F., Shvaiko, P., Yatskevich, M.: S-match: an algorithm and an implementation of semantic matching. In: European semantic web symposium. pp. 61–75. Springer (2004)
  * [33] Giunchiglia, F., Zaihrayeu, I., Kharkevich, U.: Formalizing the get-specific document classification algorithm. In: International Conference on Theory and Practice of Digital Libraries. pp. 26–37. Springer (2007)
  * [34] Hogan, A., Blomqvist, E., Cochez, M., d’Amato, C., de Melo, G., Gutierrez, C., Gayo, J.E.L., Kirrane, S., Neumaier, S., Polleres, A., et al.: Knowledge graphs. arXiv preprint arXiv:2003.02320 (2020)
  * [35] Jiménez-Ruiz, E., Grau, B.C.: Logmap: Logic-based and scalable ontology matching. In: International Semantic Web Conference. pp. 273–288. Springer (2011)
  * [36] Lonsdale, D., Embley, D.W., Ding, Y., Xu, L., Hepp, M.: Reusing ontologies and language components for ontology generation. Data & Knowledge Engineering 69(4), 318–330 (2010)
  * [37] Nath, S., Naskar, R.: Automated image splicing detection using deep cnn-learned features and ann-based classifier. Signal, Image and Video Processing 15(7), 1601–1608 (2021)
  * [38] Nezhadi, A.H., Shadgar, B., Osareh, A.: Ontology alignment using machine learning techniques. International Journal of Computer Science & Information Technology 3(2), 139 (2011)
  * [39] Nkisi-Orji, I., Wiratunga, N., Massie, S., Hui, K.Y., Heaven, R.: Ontology alignment based on word embedding and random forest classification. In: Joint European Conference on Machine Learning and Knowledge Discovery in Databases. pp. 557–572. Springer (2018)
  * [40] Onoe, Y., Durrett, G.: Fine-grained entity typing for domain independent entity linking. In: Proceedings of the AAAI Conference on Artificial Intelligence. vol. 34, pp. 8576–8583 (2020)
  * [41] Palmer, M., Wu, Z.: Verb semantics and lexical zhibiao w u. In: Proceedings of the 32nd Annual Meeting of the Association for Computational Linguistics, Las Cruces, New Mexico. pp. 133–138 (1994)
  * [42] Patro, S., Sahu, K.K.: Normalization: A preprocessing stage. arXiv preprint arXiv:1503.06462 (2015)
  * [43] Portisch, J., Hladik, M., Paulheim, H.: Background knowledge in schema matching: Strategy vs. data. In: International Semantic Web Conference. pp. 287–303. Springer (2021)
  * [44] Pour, N., Algergawy, A., Amini, R., Faria, D., Fundulaki, I., Harrow, I., Hertling, S., Jiménez-Ruiz, E., Jonquet, C., Karam, N., et al.: Results of the ontology alignment evaluation initiative 2020. In: Proceedings of the 15th International Workshop on Ontology Matching (OM 2020). vol. 2788, pp. 92–138. CEUR-WS (2020)
  * [45] Rios-Alvarado, A.B., Lopez-Arevalo, I., Sosa-Sosa, V.J.: Learning concept hierarchies from textual resources for ontologies construction. Expert Systems with Applications 40(15), 5907–5915 (2013)
  * [46] Salton, G., Buckley, C.: Term-weighting approaches in automatic text retrieval. Information processing & management 24(5), 513–523 (1988)
  * [47] Shalaby, W., Al Jadda, K., Korayem, M., Grainger, T.: Entity type recognition using an ensemble of distributional semantic models to enhance query understanding. In: 2016 IEEE 40th Annual Computer Software and Applications Conference (COMPSAC). vol. 1, pp. 631–636. IEEE (2016)
  * [48] Sleeman, J., Finin, T.: Type prediction for efficient coreference resolution in heterogeneous semantic graphs. In: 2013 IEEE Seventh International Conference on Semantic Computing. pp. 78–85. IEEE (2013)
  * [49] Sleeman, J., Finin, T., Joshi, A.: Entity type recognition for heterogeneous semantic graphs. AI Magazine 36(1), 75–86 (2015)
  * [50] Steve, G., Gangemi, A., Pisanelli, D.M.: Integrating medical terminologies with onions methodology (1997)
  * [51] Stumme, G., Maedche, A.: Fca-merge: Bottom-up merging of ontologies. In: IJCAI. vol. 1, pp. 225–230 (2001)
  * [52] Sun, Y., Ma, L., Wang, S.: A comparative evaluation of string similarity metrics for ontology alignment. Journal of Information &Computational Science 12(3), 957–964 (2015)
  * [53] Tang, J., Zhang, J., Yao, L., Li, J., Zhang, L., Su, Z.: Arnetminer: extraction and mining of academic social networks. In: Proceedings of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining. pp. 990–998 (2008)
  * [54] Van Erven, T., Harremos, P.: Rényi divergence and kullback-leibler divergence. IEEE Transactions on Information Theory 60(7), 3797–3820 (2014)
  * [55] Wiharja, K., Pan, J.Z., Kollingbaum, M., Deng, Y.: More is better: Sequential combinations of knowledge graph embedding approaches. In: Joint International Semantic Technology Conference. pp. 19–35. Springer (2018)
  * [56] Xin, J., Lin, Y., Liu, Z., Sun, M.: Improving neural fine-grained entity typing with knowledge attention. In: Proceedings of the AAAI Conference on Artificial Intelligence. vol. 32 (2018)
  * [57] Yaghoobzadeh, Y., Schütze, H.: Multi-level representations for fine-grained typing of knowledge base entities. arXiv preprint arXiv:1701.02025 (2017)
  * [58] Yujian, L., Bo, L.: A normalized levenshtein distance metric. IEEE transactions on pattern analysis and machine intelligence 29(6), 1091–1095 (2007)
  * [59] Zamazal, O., Svátek, V.: The ten-year ontofarm and its fertilization within the onto-sphere. Journal of Web Semantics 43, 46–53 (2017)
  * [60] Zhao, Y., Zhang, A., Xie, R., Liu, K., Wang, X.: Connecting embeddings for knowledge graph entity typing. arXiv preprint arXiv:2007.10873 (2020)