# Neural Class Expression Synthesis

N’Dah Jean Kouagou<EMAIL_ADDRESS>0000-0002-4217-897X
Paderborn UniversityWarburger Str. 100PaderbornNRWGermany33098 ,  Stefan
Heindorf<EMAIL_ADDRESS>0000-0002-4525-6865 Paderborn
UniversityWarburger Str. 100PaderbornNRWGermany33098 ,  Caglar Demir
<EMAIL_ADDRESS>0000-0001-8970-3850 Paderborn UniversityWarburger Str.
100PaderbornNRWGermany33098 and  Axel-Cyrille Ngonga Ngomo<EMAIL_ADDRESS>0000-0001-7112-3516 Paderborn UniversityWarburger Str.
100PaderbornNRWGermany33098

(2023)

###### Abstract.

Most existing approaches for class expression learning in description logics
are search algorithms. As the search space of these approaches is infinite,
they often fail to scale to large learning problems. Our main intuition is
that class expression learning can be regarded as a translation problem. Based
thereupon, we propose a new family of class expression learning approaches
which we dub neural class expression synthesis. Instances of this new family
circumvent the high search costs entailed by current algorithms by translating
training examples into class expressions in a fashion akin to machine
translation solutions. Consequently, they are not subject to the runtime
limitations of search-based approaches post training. We study three instances
of this novel family of approaches to synthesize class expressions from sets
of positive and negative examples. An evaluation of our approach on four
benchmark datasets suggests that it can effectively synthesize high-quality
class expressions with respect to the input examples in approximately one
second on average. Moreover, a comparison to other state-of-the-art approaches
suggests that we achieve better F-measures on large datasets. For
reproducibility purposes, we provide our implementation as well as pretrained
models in our public GitHub repository at
https://github.com/fosterreproducibleresearch/NCES.

neural network, concept learning, class expression learning, learning from
examples

††journalyear: 2023††conference: Proceedings of the ACM Web Conference 2023;
April 30–May 4, 2023; Austin, Texas, USA††booktitle: Proceedings of the ACM
Web Conference 2023 (WWW ’23), April 30–May 4, 2023, Austin, Texas,
USA††price: 15.00††doi: XXXXXXX.XXXXXXX††isbn: 978-1-4503-XXXX-X/18/06††ccs:
Computing methodologies††ccs: Computing methodologies Machine learning††ccs:
Computing methodologies Ensemble methods††ccs: Computing methodologies
Learning from demonstrations††ccs: Computing methodologies Neural
networks††ccs: Computing methodologies Learning latent representations††ccs:
Theory of computation Description logics††ccs: Theory of computation Automated
reasoning

##  1\. Introduction

One of the most popular families of web-scale knowledge bases (Heist et al.,
2020) is that of RDF knowledge bases equipped with an ontology in W3C’s web
ontology language OWL (McGuinness et al., 2004). Examples include DBpedia
(Bizer et al., 2009), Wikidata (Vrandečić and Krötzsch, 2014), and CaliGraph
(Heist and Paulheim, 2019). One means to implement ante-hoc explainable
machine learning on these knowledge bases is class expression learning (also
called concept learning) (Fanizzi et al., 2008; Lehmann and Hitzler, 2010;
Lehmann, 2010; Rizzo et al., 2020; Tran et al., 2014; Heindorf et al., 2022).
Informally, class expression learning approaches learn a class expression
which describes individuals provided as positive examples. Class expression
learning has applications in several domains, including ontology engineering
(Lehmann et al., 2011), bio-medicine (Lehmann and Völker, 2014) and Industry
4.0 (Bin et al., 2017). There exist three main learning settings in class
expression learning:  (1) positive and negative learning,  (2) positive-only
learning, and  (3) class-inclusion learning (Lehmann, 2009).  This paper
tackles setting (1).

Several methods have been proposed to solve class expression learning
problems, the best are based on refinement operators (Fanizzi et al., 2008;
Lehmann, 2009, 2010; Lehmann and Hitzler, 2010; Rizzo et al., 2020; Kouagou et
al., 2022) and evolutionary algorithms (Heindorf et al., 2022). A common
drawback of these approaches is their lack of scalability. While the reasoning
complexity of all learning approaches grows with the expressivity of the
underlying description logic (DL) (Ozaki, 2020; Konev et al., 2016), those
based on refinement operators and evolutionary algorithms further suffer from
the exploration of an infinite conceptual space for each learning problem
(Rizzo et al., 2020). Another inherent limitation of existing methods for
class expression learning from examples is their inability to leverage
previously solved problems—their algorithm always starts from scratch for each
new learning problem.

In view of the large sizes of modern knowledge bases, e.g., DBpedia (Bizer et
al., 2009) and Wikidata (Vrandečić and Krötzsch, 2014), we propose a new
family of approaches, dubbed neural class expression synthesizers (NCES), for
web-scale applications of class expression learning. The fundamental
hypothesis behind this family of algorithms is that one should be able to
capture enough semantics from latent representations (e.g., embeddings) of
examples to directly synthesize class expressions in a fashion akin to machine
translation, i.e., without the need for costly exploration. This hypothesis is
supported by the significant improvement in the performance of machine
translation approaches brought about by neural machine translation (NMT) (Cho
et al., 2014a; Wu et al., 2016). NMT approaches translate from a source
language to a target language by exploiting an intermediary representation of
a text’s semantics. NCES behave similarly but translate from the “language” of
sets of positive/negative examples to the “language” of class expressions. We
instantiate this new paradigm by implementing three NCES instances that target
the description logic $\mathcal{ALC}$. We show that our NCES instances
generate high-quality class expressions with respect to the given sets of
examples while remaining scalable. Note that NCES instances synthesize
solutions for multiple learning problems at the same time as they accept
batches of inputs. This makes NCES particularly fit for deployment in large-
scale applications of class expression learning, e.g., on the web.

The rest of the paper is organized as follows: First, we present existing
approaches for class expression learning and introduce the notations and
prerequisites needed throughout the paper. Next, we describe the intuition
behind NCES in detail and introduce three instantiations of this new family of
algorithms. We then compare these instantiations with state-of-the-art
approaches on four benchmark datasets. Finally, we discuss our results and
draw conclusions from our experiments.

##  2\. Related Work

Class expression learning has been of interest to many researchers in recent
years. Of the proposed approaches, the most prominent include those based on
evolutionary algorithms (Heindorf et al., 2022) and refinement operators
(Fanizzi et al., 2008; Lehmann, 2010; Lehmann et al., 2011; Bühmann et al.,
2016; Sarker and Hitzler, 2019; Kouagou et al., 2022). The state-of-the-art
EvoLearner (Heindorf et al., 2022) initializes its population by random walks
on the knowledge graph which are subsequently converted to description logic
concepts, represented as abstract syntax trees. These concepts are further
refined by means of mutation and crossover operations. EvoLearner outperformed
approaches based on refinement operators such as CELOE and OCEL from the DL-
Learner framework (Heindorf et al., 2022). Previously, Lehmann and Hitzler
(2010) studied different properties that a refinement operator can have, then
designed a refinement operator to learn class expressions in description
logics. Their learning algorithm, CELOE (Lehmann et al., 2011), is implemented
in DL-Learner (Lehmann, 2009) alongside OCEL and ELTL (Bühmann et al., 2016).
CELOE extends upon OCEL by using a different heuristic function, and it is
currently regarded as the best class expression learning algorithm in DL-
Learner. Although ELTL was designed for the lightweight description logic
$\mathcal{EL}$, we include it in this study to check whether our generated
learning problems can be solved in a simpler description logic. ECII (Sarker
and Hitzler, 2019) is a recent approach for class expression learning that
does not use a refinement operator and only invokes a reasoner once for each
run. This approach was designed to overcome the runtime limitations of
refinement operator-based approaches. Other attempts to prune the search space
of refinement operator-based approaches include DL-Focl (Rizzo et al., 2020).
It is a modified version of DL-Foil (Fanizzi et al., 2008) that is
quintessentially based on omission rates. DL-Focl uses techniques such as
lookahead strategy and local memory to avoid reconsidering sub-optimal
choices.

Even though existing approaches for class expression learning have shown
promising results, most of them are search-based. As a result, these
approaches often use entailment checks—which are hard to compute, see Ozaki
(2020)—or compute classification accuracies at each step of the search
process. In contrast, NCES instances synthesize class expressions without a
search process. As the training process of our synthesizers only involves
instance data embeddings and a vocabulary of atoms, they can be extended to
more expressive description logics such as $\mathcal{ALCQ(D)}$.

##  3\. Background

###  3.1. Notation

DL is short for description logic, and DNN stands for deep neural network.
Unless otherwise specified, $\mathcal{K}=(\mathit{TBox},\mathit{ABox})$ is a
knowledge base in $\mathcal{ALC}$, and $\mathcal{N}_{I}$ is the set of all
individuals in $\mathcal{K}$. The $\mathit{ABox}$ consists of statements of
the form $C(a)$ and $R(a,b)$, whereas the $\mathit{TBox}$ contains statements
of the form $C\sqsubseteq D$, where $C,D$ are concepts, $R$ is a role, and
$a,b$ are individuals in $\mathcal{K}$. We use the representation of OWL
knowledge bases as sets of triples to compute embeddings of individuals,
classes and roles. The conversion into triples is carried out using standard
libraries such as RDFLib (Krech, 2006). We then use the knowledge graph
representation of the knowledge bases to compute embeddings, which are
essential to our proposed approach (see Figure 1). The function $|.|$ returns
the cardinality of a set. $\mathbbm{1}$ denotes the indicator function, i.e.,
a function that takes two inputs and returns $1$ if they are equal, and $0$
otherwise. Let a matrix $M$ and integers $i$, $j$ be given. $M_{:,j}$,
$M_{i,:}$, and $M_{ij}$ represent the $j$-th column, the $i$-th row, and the
entry at the $i$-th row and $j$-th column, respectively. Similar notations are
used for higher-dimensional tensors.

We define the vocabulary $\mathit{Vocab}$ of a given knowledge base
$\mathcal{K}$ to be the list of all atomic concepts and roles in
$\mathcal{K}$, together with the following constructs in any fixed ordering: “
” (white space), “.” (dot), “$\sqcup$”, “$\sqcap$”, “$\exists$”, “$\forall$”,
“$\neg$”, “(”, and “)”, which are all referred to as atoms.
$\mathit{Vocab}[i]$ is the atom at position $i$ in $\mathit{Vocab}$. These
constructs are used by NCES to synthesize class expressions in $\mathcal{ALC}$
(see Section 4 for details). Let $C$ be a class expression, then $\hat{C}$ and
$\bar{C}$ are the list (in the order they appear in $C$) and set of atoms in
$C$, respectively.

###  3.2. Description Logics

Description logics (Nardi et al., 2003) are a family of knowledge
representation paradigms based on first-order logics. They have applications
in several domains, including artificial intelligence, the semantic web, and
biomedical informatics. In fact, the web ontology language, OWL, uses
description logics to represent the terminological box of RDF ontologies. In
this work, we focus on the description logic $\mathcal{ALC}$
($\mathcal{A}$ttributive $\mathcal{L}$anguage with $\mathcal{C}$omplement)
(Schmidt-Schauß and Smolka, 1991) because of its simplicity and
expressiveness. The syntax and semantics of $\mathcal{ALC}$ are presented in
Table 1.

Table 1. $\mathcal{ALC}$ syntax and semantics. $\mathcal{I}$ is an interpretation and $\Delta^{\mathcal{I}}$ its domain. Construct | Syntax | Semantics
---|---|---
Atomic concept | $A$ | $A^{\mathcal{I}}\subseteq{\Delta^{\mathcal{I}}}$
Atomic role | $R$ | $R^{\mathcal{I}}\subseteq{\Delta^{\mathcal{I}}\times\Delta^{\mathcal{I}}}$
Top concept | $\top$ | $\Delta^{\mathcal{I}}$
Bottom concept | $\bot$ | $\emptyset$
Conjunction | $C\sqcap D$ | $C^{\mathcal{I}}\cap D^{\mathcal{I}}$
Disjunction | $C\sqcup D$ | $C^{\mathcal{I}}\cup D^{\mathcal{I}}$
Negation | $\neg C$ | $\Delta^{\mathcal{I}}\setminus C^{\mathcal{I}}$
Existential role restriction | $\exists~{}R.C$ | $\\{a^{\mathcal{I}}\in\Delta^{\mathcal{I}}/\exists~{}b^{\mathcal{I}}\in C^{\mathcal{I}},(a^{\mathcal{I}},b^{\mathcal{I}})\in R^{\mathcal{I}}\\}$
Universal role restriction | $\forall~{}R.C$ | $\\{a^{\mathcal{I}}\in\Delta^{\mathcal{I}}/\forall~{}b^{\mathcal{I}},(a^{\mathcal{I}},b^{\mathcal{I}})\in R^{\mathcal{I}}\Rightarrow b^{\mathcal{I}}\in C^{\mathcal{I}}\\}$

###  3.3. Refinement Operators

###### Definition 3.1 ((Lehmann and Hitzler, 2010)).

Given a quasi-ordered space $(\mathcal{S},\preceq)$, a downward (respectively
upward) refinement operator on $\mathcal{S}$ is a mapping
$\rho:\mathcal{S}\rightarrow 2^{\mathcal{S}}$ such that for all
$C\in\mathcal{S}$, $C^{\prime}\in\rho(C)$ implies $C^{\prime}\preceq C$
(respectively $C\preceq C^{\prime}$).

A refinement operator can be finite, proper, redundant, minimal, complete,
weakly complete or ideal. Note that some of these properties can be combined
whilst others cannot (Lehmann and Hitzler, 2010). For class expression
learning in description logics, weakly complete, finite, and proper refinement
operators are the most used.

###  3.4. Class Expression Learning

###### Definition 3.2.

Given a knowledge base $\mathcal{K}$, a target concept $T$, a set of positive
examples $E^{+}=\\{e^{+}_{1},e^{+}_{2},\ldots,e^{+}_{n_{1}}\\}$, and a set of
negative examples $E^{-}=\\{e^{-}_{1},e^{-}_{2},\ldots,e^{-}_{n_{2}}\\}$, the
learning problem is to find a class expression $C$ such that for
$\mathcal{K}^{\prime}=\mathcal{K}\cup\\{T\equiv C\\}$, we have $\forall$
$e^{+}\in E^{+}\ \forall e^{-}\in E^{-},\ \mathcal{K}^{\prime}\models
C(e^{+})$ and $\mathcal{K}^{\prime}\not\models C(e^{-})$ .

Most existing approaches use hard-coded heuristics or refinement operators to
search for the solution $C$. When an exact solution does not exist, an
approximate solution in terms of accuracy or F-measure is to be returned by
the approaches. In this work, we exploit the semantics embedded in latent
representations of individuals to directly synthesize $C$.

###  3.5. Knowledge Graph Embedding

A knowledge graph can be regarded as a collection of assertions in the form of
subject-predicate-object triples $(s,p,o)$. Embedding functions project
knowledge graphs onto continuous vector spaces to facilitate downstream tasks
such as link prediction (Bordes et al., 2013), recommender systems (Zhang et
al., 2016), and structured machine learning (Kouagou et al., 2022). Many
embedding approaches for knowledge graphs exist (Wang et al., 2017; Dai et
al., 2020). Some of them use only facts observed in the knowledge graph
(Nickel et al., 2012; Bordes et al., 2014). Others leverage additional
available information about entities and relations, such as textual
descriptions (Xie et al., 2016; Wang et al., 2016). Most embedding approaches
initialize each entity and relation with a random vector, matrix or tensor and
learn the embeddings as an optimization problem. For example, TransE (Bordes
et al., 2013) represents entities and relations as vectors in the same space
and aims to minimize the Euclidean distance between $s+p$ and $o$ for each
triple $(s,p,o)$. In this work, we use two embedding approaches to evaluate
our approach and conduct additional experiments (see Section 4.2 and Section
A.2).

###  3.6. Permutation-Invariant Neural Network Architectures for Set Inputs

We deal with set-structured input data as in 3D shape recognition (Qi et al.,
2017), multiple instance learning (Dietterich et al., 1997), and few-shot
learning (Finn et al., 2017; Snell et al., 2017). These tasks benefit from
machine learning models that produce the same results for any arbitrary
reordering of the elements in the input set. Another desirable property of
these models is the ability to handle sets of arbitrary size.

In recent years, several approaches have been developed to meet the
aforementioned requirements. The most prominent of these approaches include
Deep Set (Zaheer et al., 2017) and Set Transformer (Lee et al., 2019). The
Deep Set architecture encodes each element in the input set independently and
uses a pooling layer, e.g., averaging, to produce the final representation of
the set. In contrast, the Set Transformer architecture uses a self-attention
mechanism to represent the set, which allows pair-wise and even higher-order
interactions between the elements of the input set. As a result, the Set
Transformer architecture shows superior performance on most tasks compared to
Deep Set with a comparable model size (Lee et al., 2019). In this work, we
hence choose the Set Transformer architecture (more details in Section 4)
whose building blocks are elucidated in the following paragraphs.

##### Attention

Given query, key, value vectors $Q\in\mathbb{R}^{n_{q}\times d_{q}},\
K\in\mathbb{R}^{n_{v}\times d_{q}},\ V\in\mathbb{R}^{n_{v}\times d_{v}}$, and
an activation function $\sigma$, an attention function computes the output as
a weighted sum of $V$:

(1) $\displaystyle\mathrm{Att}(Q,K,V;\sigma)=\sigma(QK^{T})V.$

Here, $n_{q}$, $n_{v}$, $d_{q}$, $d_{v}$ are the numbers of queries, values,
dimensions of each query vector, and dimensions of each value vector,
respectively. The activation function is chosen in a way that higher weights
correspond to higher dot product values between queries and keys. We use
softmax as activation function, as in (Lee et al., 2019).

##### Multi-head Attention

A multi-head attention function with $h$ heads first projects $Q,\ K,\ V$ onto
$h$ different projections $Q_{j}$, $K_{j}$, $V_{j}$ for $j=1,\ldots,h$. Each
projection is performed using a trainable projection map, usually a linear
layer. Next, the attention function $\mathrm{Att}(.;\sigma)$ is applied to
each projection, and the outputs are concatenated. Finally, the result of the
concatenation is fed to a linear layer for the final output:

(2) $\displaystyle O_{j}$
$\displaystyle=\mathrm{Att}(Q_{j},K_{j},V_{j};\sigma),$ (3)
$\displaystyle\mathrm{Multihead}(Q,K,V)$
$\displaystyle=\text{Concat}(O_{1},\ldots,O_{h})W^{O}.$

For computational efficiency, a natural choice for the projection dimensions
is $Q_{j}\in\mathbb{R}^{n_{q}\times(d_{q}/h)}$,
$K_{j}\in\mathbb{R}^{n_{v}\times(d_{q}/h)}$,
$V_{j}\in\mathbb{R}^{n_{v}\times(d_{v}/h)}$, and
$W^{O}\in\mathbb{R}^{d_{v}\times d_{v}}$.

##### Multi-head Attention Block (MAB)

Lee et al. (2019) introduced a modified version of multi-head attention blocks
tailored toward set-structured inputs. We employ the same attention blocks but
without layer normalisation, as the latter did not improve the results in our
learning tasks. For any $X,\ Y\in\mathbb{R}^{n\times d}$, we define
$\mathrm{MAB}$ as:

(4) $\displaystyle H$ $\displaystyle=X+\mathrm{Multihead(X,Y,Y)},$ (5)
$\displaystyle\mathrm{MAB}(X,Y)$ $\displaystyle:=H+\mathrm{rFF}(H),$

where $\mathrm{rFF}$ is a feedforward neural network layer and $n$ is the
number of elements in the input sets of embeddings.

##### Set Attention Block (SAB)

This module operates on a single set of embedding vectors. Following (Lee et
al., 2019), we define $\mathrm{SAB}$ as:

(6) $\displaystyle\mathrm{SAB}(X):=\mathrm{MAB}(X,X).$

##### Induced Set Attention Block (ISAB)

To reduce the computational complexity in attention mechanisms for especially
large sets, (Lee et al., 2019) proposed using so-called inducing points. The
main idea is to introduce a (small) fixed-size trainable matrix
$I\in\mathbb{R}^{m\times d}$ as a bridge in SAB. More specifically, ISAB is
defined for any $X\in\mathbb{R}^{n\times d}$ as:

(7) $\displaystyle H$ $\displaystyle=\mathrm{MAB}(I,X)\in\mathbb{R}^{m\times
d},$ (8) $\displaystyle\mathrm{ISAB}(X)$
$\displaystyle:=\mathrm{MAB}(X,H)\in\mathbb{R}^{n\times d}.$

Note that the computation cost in ISAB is $4\times(m\times d\times n)$. This
is less than that of SAB $2\times(n\times d\times n)$ for $n>>m$. In this
paper, we learn 32 inducing points ($m=32$).

##### Pooling by Multi-head Attention (PMA)

As opposed to the pooling mechanism in (Zaheer et al., 2017), where the
learned features from the encoder are summed (decoding), the decoder in Set
Transformer applies a multi-head attention function between a trainable
feature matrix and the features from the encoder. Formally, a Pooling by
Multi-head Attention layer (PMA) with $k$ seed vectors
$S\in\mathbb{R}^{k\times d}$ is defined for any $X\in\mathbb{R}^{n\times d}$
by:

(9) $\displaystyle\mathrm{PMA}(X):=\mathrm{MAB(S,X)}.$

In this work, we learn a single seed vector ($k=1$).

##  4\. Neural Class Expression Synthesis

In this section, we present our proposed family of approaches for class
expression learning from examples. We start with a formal definition of the
learning problem that we aim to solve, then present our proposed approach in
detail.

###  4.1. Learning Problem

###### Definition 4.1.

Given a knowledge base $\mathcal{K}$, a set of positive examples
$E^{+}=\\{e^{+}_{1},e^{+}_{2},\ldots,e^{+}_{n_{1}}\\}$, and a set of negative
examples $E^{-}=\\{e^{-}_{1},e^{-}_{2},\ldots,e^{-}_{n_{2}}\\}$, the learning
problem is to synthesize a class expression $C$ in $\mathcal{ALC}$ using atoms
(classes and roles) in $\mathcal{K}$ that accurately classifies the provided
examples.

The above definition implies the need for a system that can map instance data
to class expressions in the description logic $\mathcal{ALC}$. We devise such
a system by building and training well-selected neural network architectures.
The system and its components are referred to as neural class expression
synthesizers (NCES).

###  4.2. Learning Approach

We propose the following simple recipe to implement the idea behind NCES.
First, given a knowledge base over $\mathcal{ALC}$, convert it into a
knowledge graph (see Subsection 3.1). Then, embed said knowledge graph into a
continuous vector space using any state-of-the-art embedding model in the
literature. We used ConEx (Demir and Ngomo, 2021) for this purpose because it
outperforms many other embedding models while remaining scalable. Note that we
also used TransE in additional experiments to further validate the
effectiveness of our proposed approach (see Appendix A.2). The computed
embeddings are then used as features for a model able to take a set of
embeddings as input and encode a sequence of atoms as output (see Figure 1).

Figure 1. NCES architecture. DNN stands for deep neural network. The input
consists of positive examples (dotted green box) and negative examples (dotted
red box).

####  4.2.1. Neural Network Architectures

We conduct our experiments using the following network architectures: the Long
Short-Term Memory (LSTM) (Hochreiter and Schmidhuber, 1997), the Gated
Recurrent Unit (GRU) (Cho et al., 2014b), and the Set Transformer (Lee et al.,
2019). The latter is known to be permutation equivariant while the two others
are not (see more in Section 5). Nonetheless, LSTM and GRU can handle set
inputs as long as an ordering is defined since they deal well with sequential
data (Zhao et al., 2018; Zulqarnain et al., 2019). In this work, we use the
default ordering (the order in which we received the data) of the elements in
each set during the data generation process (see Section 5.1.2).

##### Recurrent Networks (LSTM and GRU)

We use two recurrent layers followed by three linear layers with the relu
activation function and a batch normalization layer. A recurrent neural
network produces a sequence of $n$ hidden states $h_{i}$ ($i$=$1,\dots,n$) for
each input sequence of length $n$. In this work, we are concerned with a
sequence of $n_{1}$ positive examples and a sequence of $n_{2}$ negative
examples which are processed separately with the same network:

(10) $\displaystyle h^{pos}_{1},\dots,h^{pos}_{n_{1}}=RNN(x_{pos});\
h^{neg}_{1},\dots,h^{neg}_{n_{2}}=RNN(x_{neg});$

where $x_{pos}$ and $x_{neg}$ are the sequences of embeddings of positive and
negative examples, respectively. $RNN$ is a two-layer LSTM or GRU network. The
hidden state vectors of the two sets of examples are summed separately, then
concatenated and fed to a sequence of 3 linear layers:

(11) $\displaystyle h_{pos}$ $\displaystyle:=\sum_{t=1}^{T_{1}}h^{pos}_{t};\
h_{neg}:=\sum_{t=1}^{T_{2}}h^{neg}_{t};\ h:=\mathrm{Concat}(h_{pos},h_{neg});$
(12) $\displaystyle O$
$\displaystyle=W_{3}(\mathrm{bn}(W_{2}f(W_{1}h+b_{1})+b_{2}))+b_{3}.$

Here, $f$ is the relu activation function, $\mathrm{bn}$ is a batch
normalization layer, and $W_{1},b_{1},W_{2},b_{2},W_{3},b_{3}$ are trainable
weights.

##### Set Transformer

This architecture comprises an encoder $\mathit{Enc}$ and a decoder
$\mathit{Dec}$. The encoder is a stack of two $\mathrm{ISAB}$ layers, and the
decoder is composed of a single $\mathrm{PMA}$ layer with one seed vector
($k=1$), and a linear layer. As in the previous paragraph, the sets of
positive and negative examples for a given class expression are first encoded
separately using the encoder. The outputs are then concatenated row-wise and
fed to the decoder:

(13) $\displaystyle O_{pos}$ $\displaystyle=\mathit{Enc}(x_{pos});\
O_{neg}=\mathit{Enc}(x_{neg});$ (14) $\displaystyle O$
$\displaystyle=\mathit{Dec}(\mathrm{Concat}(O_{pos},O_{neg})).$

Although the encoder captures interactions intra-positive and intra-negative
examples separately, the decoder further captures interactions across the two
sets of examples from the concatenated features through self-attention. This
demonstrates the representational power of the Set Transformer model for our
set-structured inputs for class expression synthesis.

The output $O$ from 11 and 13 is reshaped into a $(1+|\mathit{Vocab}|)\times
L$ matrix, where $L$ is the length of the longest class expression that NCES
instances can generate. These scores allow us to compute the loss (see
Equation 15) and update model weights through gradient descent during
training.

####  4.2.2. Loss

We train our NCES instances using the the loss function $\mathcal{L}$ defined
by:

(15)
$\displaystyle\mathcal{L}(x,y)=-\frac{1}{NL}\sum_{i=1}^{N}\sum_{j=1}^{L}\log\left(\frac{\exp(x_{i,y_{ij},j})}{\sum_{c=1}^{C}\exp(x_{i,c,j})}\right),$

where $N$ is the size of the minibatch, $C$ is the number of classes,
$x\in\mathbb{R}^{N\times C\times L}$ is the minibatch of predicted class
scores for each position in the target sequence of atoms, and
$y\in\mathbb{N}^{N\times L}$ is the minibatch of actual class indices.
Minimizing $\mathcal{L}$ constrains the model to assign a high score to the
entry corresponding to the correct token ($\exp(x_{i,y_{ij},j})\approx 1$)
while keeping the remaining scores relatively low ($\sum_{c=1,c\neq
y_{ij}}^{C}\exp(x_{i,c,j})\approx 0$). In this work, $C=1+|\mathit{Vocab}|$,
where the additional $+1$ accounts for the special token “PAD” that we used to
pad all class expressions to the same length. Contrarily to some works that
omit this special token when computing the loss, we use it as an ordinary
token during training. This way, we can generate class expressions more
efficiently at test time with a single forward pass in the model, then strip
off the generated tokens after the special token. To avoid exploding gradients
and accelerate convergence during training, we adopt the gradient clipping
technique (Zhang et al., 2019).

####  4.2.3. Learning Metrics

Apart from the loss function, we introduce two accuracy measures to quantify
how well neural networks learn during training: soft accuracy and hard
accuracy. The former only accounts for the correct selection of the atoms in
the target expression, while the latter additionally measures the correct
ordering of the selected atoms. Formally, let $T$ and $P$ be the target and
predicted class expressions, respectively. Recall the notation $\bar{C}$ and
$\hat{C}$ introduced in Section 3.1 for any class expression $C$. The soft
($Acc_{s}$) accuracy and hard accuracy ($Acc_{h}$) are defined as follows:

(16) $\displaystyle
Acc_{s}(T,P)=\frac{|\bar{T}\cap\bar{P}|}{|\bar{T}\cup\bar{P}|};\
Acc_{h}(T,P)=\frac{\sum_{i=1}^{\min(l_{1},l_{2})}\mathbbm{1}(\hat{T}[i],\hat{P}[i])}{\max(l_{1},l_{2})}.$

where $l_{1}$ and $l_{2}$ are the lengths of $\hat{T}$ and $\hat{P}$,
respectively.

####  4.2.4. Class Expression Synthesis

We synthesize class expressions by mapping the output scores $O$ (see
Equations 11 and 13) to the vocabulary. More specifically, we select the
highest-scoring atoms in the vocabulary for each position along the sequence
dimension:

(17) $\displaystyle\mathrm{id}_{j}$
$\displaystyle=\operatorname*{arg\,max}_{c\in[1,C]}O_{:,j}\text{ for
}j=1,\ldots,L,$ (18) $\displaystyle synthesized\\_atom_{j}$
$\displaystyle=\mathit{Vocab}[\mathrm{id}_{j}].$

####  4.2.5. Model Ensembling

Ensemble learning has proven to be one of the most robust approaches for tasks
involving complex noisy data (Sagi and Rokach, 2018; Dong et al., 2020). In
this work, we combine class expression synthesizers’ predictions post training
by averaging the predicted scores. Specifically, given the output scores
$O_{i}\in\mathbb{R}^{C\times L}$ ($i=1,2,3$) as defined in 11 and 13 for the
three models LSTM, GRU, and Set Transformer, we consider four different
ensemble models: three pairwise ensemble models, and one global ensemble model
(LSTM, GRU, and Set Transformer are combined). Formally, the ensemble scores
are computed as:

(19) $\displaystyle O=\frac{\sum_{i\in\mathcal{I}}O_{i}}{|\mathcal{I}|}\text{
with }\mathcal{I}\subseteq{\\{1,2,3\\}}\text{ and }|\mathcal{I}|\geq 2.$

Then, the synthesized expression is constructed as explained in Section 4.2.4
using the average scores $O$.

##  5\. Evaluation

###  5.1. Experimental Setup

####  5.1.1. Datasets

We evaluated our proposed approach on the Carcinogenesis (Westphal et al.,
2019), Mutagenesis (Westphal et al., 2019), Semantic
Bible111https://www.semanticbible.com/ntn/ntn-overview.html, and the Vicodi
(Nagypál, 2005) knowledge bases. Carcinogenesis and Mutagenesis are knowledge
bases about chemical compounds and how they relate to each other. The Semantic
Bible knowledge base describes each named object or thing in the New
Testament, categorized according to its class, including God, groups of
people, and locations. The Vicodi knowledge base was developed as part of a
funded project and describes European history. The statistics of each of the
knowledge bases are given in Table 2.

Table 2. Detailed information about the datasets used for evaluation. $|\mathit{Vocab}|$ is computed as $|\mathrm{Classes}|+|\mathrm{Prop.}|+11$, where $+11$ accounts for the special characters or atoms (see caption of Figure 1). $\mathrm{|LPs|}$ is the number of learning problems in the test set.  Dataset |  $|$Ind.$|$ |  $|$Classes$|$ |  $|$Prop.$|$ | $|\mathit{TBox}|$ | $|\mathit{ABox}|$ | $|\mathrm{Train}|$ | $|\mathrm{LPs}|$ | $|\mathit{Vocab}|$
---|---|---|---|---|---|---|---|---
Carcinogenesis | 22,372 | 142 |  04 | 144 |  074,223 |  09,662 | 98 | 157
Mutagenesis | 14,145 |  086 |  05 |  082 |  047,722 |  02,138 | 22 | 102
Semantic Bible |  000724 |  048 | 29 |  056 |  003,106 |  02,479 | 26 |  088
Vicodi | 33,238 | 194 | 10 | 204 | 116,181 | 15,533 | 157 | 215

####  5.1.2. Training and Test Data Construction

We generated class expressions of different forms from the input knowledge
base using the recent refinement operator by (Kouagou et al., 2022) that was
developed to efficiently generate numerous class expressions to serve as
training data for concept length prediction in $\mathcal{ALC}$. The data that
we generate is passed to the filtering process, which discards any class
expression $C$ such that an equivalent but shorter class expression $D$ was
not discarded. Note that each class expression comes with its set of
instances, which are computed using the fast closed-world reasoner based on
set operations described in (Heindorf et al., 2022). These instances are
considered positive examples for the corresponding class expression; negative
examples are the rest of the individuals in the knowledge base. Next, the
resulting data is randomly split into training and test sets. To ensure that
our approach is scalable to large knowledge bases, we introduce a hyper-
parameter $n=n_{1}+n_{2}$ that represents the total number of positive and
negative examples we sample for each class expression to be learned by NCES.
Note that $n$ is fixed for each knowledge base, and it depends on the total
number of individuals.

####  5.1.3. Evaluation Metrics

We measure the quality of a predicted class expression in terms of accuracy
and F-measure with respect to the positive/negative examples. Note that we
cannot expect to exactly predict the target class expression in the test data
since there can be multiple equivalent class expressions.

####  5.1.4. Hyper-parameter Optimization for NCES

We employed random search on the hyper-parameter space since it often yields
good results while being computationally more efficient than grid search
(Bergstra and Bengio, 2012); the selected values—those with the best
results—are reported in Table 3. In the table, it can be seen that most
knowledge bases share the same optimal values of hyper-parameters: the
minibatch size $N$, the number of training epochs $epochs$, the optimizer
$opt.$, the learning rate $lr$, the maximum output sequence length $L$, the
number of embedding dimensions $d$, the number of inducing points $m$, and the
gradient clipping value $gc$. Although we may increase $n$ for very large
knowledge bases, $n=\min(\frac{|\mathcal{N}_{I}|}{2},1000)$ appears to work
well with our evaluation datasets. This suggests that one can effortlessly
find fitting hyper-parameters for new datasets.

Table 3. Hyper-parameter settings per dataset. Dataset | $epochs$ | $opt.$ | $lr$ | $d$ | $N$ | $L$ | $n$ | $m$ | $gc$
---|---|---|---|---|---|---|---|---|---
Carcinogenesis | 500 | Adam | 0.0003 | 40 | 256 | 32 | 1,000 | 32 | 5
Mutagenesis | 500 | Adam | 0.0003 | 40 | 256 | 32 | 1,000 | 32 | 5
Semantic Bible | 500 | Adam | 0.0003 | 40 | 256 | 32 |  00362 | 32 | 5
Vicodi | 500 | Adam | 0.0003 | 40 | 256 | 32 | 1,000 | 32 | 5

####  5.1.5. Hardware and Training Time

We trained our chosen NCES instances on a server with 1TB of RAM and an NVIDIA
RTX A5000 GPU with 24 GB of RAM. Note that during training, approximately 8GB
of the 1TB RAM is currently used by NCES. As search-based approaches do not
require a GPU for class expression learning, we used a 16-core Intel Xeon
E5-2695 with 2.30GHz and 16GB RAM to run all approaches (including NCES post
training) for class expression learning on the test set. The number of
parameters and training time of each NCES instance are reported in Table 4.
From the table, we can observe that NCES instances are lightweight and can be
trained within an hour on medium size knowledge bases. Note that training is
only required once per knowledge base.

Table 4. Model size and training time. The runtime is in hours (h). | Carcinogenesis | Mutagenesis | Semantic Bible | Vicodi
---|---|---|---|---
| $|\mathrm{Params.}|$ | $\mathrm{Time}$ | $|\mathrm{Params.}|$ | $\mathrm{Time}$ | $|\mathrm{Params.}|$ | $\mathrm{Time}$ | $|\mathrm{Params.}|$ | $\mathrm{Time}$
NCES${}_{\text{LSTM}}$ | 921,024 | 0.60h | 693,984 | 0.21h | 636,192 | 0.13h | 1,160,448 | 0.91h
NCES${}_{\text{GRU}}$ | 866,240 | 0.42h | 639,200 | 0.17h | 581,408 | 0.12h | 1,105,664 | 0.63h
NCES${}_{\text{ST}}$ | 956,992 | 0.77h | 729,952 | 0.25h | 672,160 | 0.15h | 1,196,416 | 1.21h

###  5.2. Results

####  5.2.1. Syntactic Accuracy

Our neural class expression synthesizers were trained for 500 epochs on each
knowledge base. In Figure 2, we only show the hard accuracy curves during
training due to space constraints. The rest of the training curves can be
found on our Github repository. The curves in Figure 2 suggest that NCES
instances train fast with exponential growth in accuracy for the first 10
epochs. All models reach a syntactic accuracy of 100% between 400 and 500
training epochs on large knowledge bases (Carcinogenesis and Vicodi) while
achieving a lower performance on smaller ones (Mutagenesis and Semantic
Bible). This suggests that NCES instances are well suited for large datasets.
We validate this hypothesis through the quality of the synthesized solutions
on the test set (see Table 5).

Figure 2. Training accuracy curves.

####  5.2.2. Comparison to State-of-the-art Approaches

Table 5. Evaluation results per approach and dataset. The star (*) indicates
statistically significant differences between the best search-based and the
best synthesis-based approaches. We report the mean and standard deviation.
$\uparrow$ indicates that the higher is better (F-measure and Accuracy), and
$\downarrow$ indicates that the lower is better (Runtime). Underlined values
are the second best.

| F1(%) $\uparrow$
---|---
| Carcinogenesis | Mutagenesis | Semantic Bible | Vicodi
CELOE | 59.06$\pm$38.61 | 96.43$\pm$15.81 |  95.04$\pm$9.50* | 63.69$\pm$30.18
ELTL | 40.36$\pm$31.94 | 33.06$\pm$31.22 | 40.91$\pm$30.56 | 40.98$\pm$32.07
ECII | 33.10$\pm$37.12 | 26.37$\pm$35.45 | 48.25$\pm$36.37 | 89.08$\pm$15.86
EvoLearner | 85.19$\pm$21.51 | 95.18$\pm$06.19 | 87.82$\pm$12.56 | 87.62$\pm$12.58
NCES${}_{\text{LSTM}}$ | 82.46$\pm$25.41 | 67.11$\pm$45.87 | 79.15$\pm$29.08 | 84.00$\pm$28.05
NCES${}_{\text{GRU}}$ | 86.53$\pm$26.27 | 64.21$\pm$44.75 | 78.62$\pm$26.56 | 85.82$\pm$28.31
NCES${}_{\text{ST}}$ | 85.44$\pm$27.92 | 88.97$\pm$25.35 | 79.05$\pm$21.34 | 88.76$\pm$24.00
NCES${}_{\text{ST+GRU}}$ |  97.11$\pm$9.60* | 90.58$\pm$26.00 | 81.31$\pm$29.31 | 94.24$\pm$18.95
NCES${}_{\text{ST+LSTM}}$ | 93.94$\pm$16.34 | 97.97$\pm$03.58 | 79.96$\pm$26.50 |  95.42$\pm$13.74*
NCES${}_{\text{GRU+LSTM}}$ | 87.74$\pm$24.07 | 82.20$\pm$30.62 | 81.07$\pm$26.03 | 92.04$\pm$20.62
NCES${}_{\text{ST+GRU+LSTM}}$ | 96.13$\pm$10.65 | 90.78$\pm$26.57 | 82.33$\pm$26.51 | 94.96$\pm$16.44
| Accuracy(%) $\uparrow$
| Carcinogenesis | Mutagenesis | Semantic Bible | Vicodi
CELOE | 66.54$\pm$29.10 | 99.80$\pm$00.66 | 98.01$\pm$04.78 | 84.59$\pm$12.84
ELTL | 41.07$\pm$33.85 | 37.56$\pm$31.32 | 40.63$\pm$28.38 | 59.93$\pm$29.12
ECII | – | – | – | –
EvoLearner | 98.98$\pm$02.97 | 99.92$\pm$00.14 | 99.20$\pm$00.71 | 99.82$\pm$00.72
NCES${}_{\text{LSTM}}$ | 99.69$\pm$00.78 | 99.28$\pm$01.64 | 96.05$\pm$09.17 | 99.89$\pm$00.31
NCES${}_{\text{GRU}}$ | 99.79$\pm$00.65 | 99.20$\pm$02.55 | 97.21$\pm$06.01 | 99.83$\pm$00.57
NCES${}_{\text{ST}}$ | 99.79$\pm$00.52 | 99.91$\pm$00.18 | 98.63$\pm$01.34 | 99.88$\pm$00.48
NCES${}_{\text{ST+GRU}}$ | 99.91$\pm$00.36 | 99.94$\pm$00.12 | 96.50$\pm$07.22 | 99.94$\pm$00.24
NCES${}_{\text{ST+LSTM}}$ | 99.86$\pm$00.46 | 99.96$\pm$00.09 | 96.65$\pm$08.26 | 99.97$\pm$00.09
NCES${}_{\text{GRU+LSTM}}$ | 99.74$\pm$00.86 | 99.87$\pm$00.34 | 96.84$\pm$06.68 | 99.93$\pm$00.31
NCES${}_{\text{ST+GRU+LSTM}}$ | 99.93$\pm$00.31 | 99.97$\pm$00.07 | 97.50$\pm$06.03 | 99.95$\pm$00.22
| Runtime(sec.) $\downarrow$
| Carcinogenesis | Mutagenesis | Semantic Bible | Vicodi
CELOE | 205.05$\pm$134.41 | 46.07$\pm$84.51 | 94.11$\pm$127.07 | 280.57$\pm$67.14
ELTL | 24.28$\pm$0.67 | 13.51$\pm$0.69 | 16.5$\pm$58.54 | 384.23$\pm$202.57
ECII | 2217.35$\pm$602.79 | 2014.28$\pm$598.25 | 635.33$\pm$135.1 | 3736.37$\pm$2681.51
EvoLearner | 39.76$\pm$22.91 | 27.25$\pm$14.65 | 16.6$\pm$5.37 | 123.86$\pm$47.26
NCES${}_{\text{LSTM}}$ | 0.12$\pm$0.00 | 0.26$\pm$0.00 | 0.05$\pm$0.00 | 0.09$\pm$0.00
NCES${}_{\text{GRU}}$ | 0.07$\pm$0.00 | 0.23$\pm$0.00 | 0.06$\pm$0.00 | 0.06$\pm$0.00
NCES${}_{\text{ST}}$ | 0.04$\pm$0.00* | 0.18$\pm$0.00* | 0.02$\pm$0.00* | 0.04$\pm$0.00*
NCES${}_{\text{ST+GRU}}$ | 0.10$\pm$0.00 | 0.22$\pm$0.00 | 0.05$\pm$0.00 | 0.07$\pm$0.00
NCES${}_{\text{ST+LSTM}}$ | 0.15$\pm$0.00 | 0.22$\pm$0.00 | 0.06$\pm$0.00 | 0.08$\pm$0.00
NCES${}_{\text{GRU+LSTM}}$ | 0.24$\pm$0.00 | 0.30$\pm$0.00 | 0.07$\pm$0.00 | 0.14$\pm$0.00
NCES${}_{\text{ST+GRU+LSTM}}$ | 0.23$\pm$0.00 | 0.30$\pm$0.00 | 0.07$\pm$0.00 | 0.11$\pm$0.00

We compare our approach against EvoLearner, CELOE, ECII, ELTL, and DL-Foil.
Note that DL-Foil is not included in Table 5 because it could not terminate on
most learning problems that we considered. The algorithm actually gets stuck
on the refinement of a partial description during the search process on some
learning problems. On the other side, we could not run DL-Focl with the
documentation provided. The maximum execution time for CELOE and EvoLearner
was set to 300 seconds per learning problem while ECII and ELTL were executed
with their default settings, as they do not have the maximum execution time
parameter in their original implementation.

From Table 5, we can observe that our approach (with ensemble prediction)
significantly outperforms all other approaches in runtime on all datasets, and
in accuracy and F-measure on the Carcinogenesis, Mutagenesis, and Vicodi
knowledge bases. We used the Wilcoxon Rank Sum test with a significance level
of 5$\%$ and the null hypothesis that the compared quantities per dataset are
from the same distribution. The best search-based approach only outperforms
NCES instances (including ensemble models) on the smallest dataset, the
Semantic Bible knowledge base. The reason for this is that deep learning
models are data-hungry and often fail to generalize well on small datasets.
Our approach is hence well suited for large knowledge bases where search-based
approaches are prohibitively slow.

####  5.2.3. Predictive Performance Analysis of NCES Instances

Figure 3. Prediction performance on learning problems where at least one model
synthesized a solution with F${}_{1}<$ 10%.

To better understand the main differences between our selected NCES instances,
we compared their synthesized solutions on the most challenging learning
problems. These learning problems are those for which at least an NCES
instance synthesized a solution with an F-measure less than 10%. The results
are reported in Figure 3. The size of each point in the figure is proportional
to the number of times the corresponding NCES instance was ranked first in
terms of F-measure. From the figure, we can observe that the Set Transformer
model outperforms recurrent neural networks on three datasets: Mutagenesis,
Semantic Bible, and Vicodi (see the size of the blue points), while ranking
second on the Carcinogenesis knowledge base behind the GRU model. It can also
be observed that for each of these learning problems, there always exist at
least one NCES instance that synthesizes a solution with quality of at least
50%. This motivated us to ensemble different NCES instances, which indeed led
to increased predictive performance (see Table 5).

###  5.3. Discussion

The hypothesis behind this work was that high-quality class expressions can be
synthesized directly out of training data, i.e., without the need for an
extensive search. Our results clearly undergird our hypothesis. While our
approaches are outperformed by CELOE on the Semantic Bible knowledge base,
they achieve the best performance on the three other datasets with over 11.92%
absolute improvement on the Carcinogenesis dataset. This large difference is
due to the fact that most search-based approaches fail to find any suitable
solution for some learning problems. For example, the second learning problem
on the Carcinogenesis knowledge base is Iodine $\sqcup$ ($\exists$
inBond.(Carbon-17 $\sqcup$ Fluorine)). The solutions computed by each of the
approaches are as follows: CELOE: $\neg\texttt{Hydrogen}$ (F1: 3.87%), ELTL:
$\top$ (F1: 3.15%), ECII: $\neg$Structure $\sqcup$ $\neg$Bond $\sqcup$
$\neg$Atom (F1: 0.0%), EvoLearner: Iodine-95 $\sqcup$ ($\exists$
inBond.(Carbon-17 $\sqcup$ Fluorine)) (F1: 100%), NCES${}_{\text{ST}}$: Iodine
$\sqcup$ ($\exists$ inBond.(Carbon-17 $\sqcup$ Fluorine-92)) (F1: 100%),
NCES${}_{\text{ST+LSTM}}$: Iodine $\sqcup$ ($\exists$ inBond. (Carbon-17
$\sqcup$ Fluorine)) (F1: 100%). Here, our ensemble model
NCES${}_{\text{ST+LSTM}}$ synthesized the exact solution while
NCES${}_{\text{ST}}$ and EvoLearner computed high-quality approximate
solutions with an F-measure of 100%. On the other hand, CELOE, ECII, and ELTL
failed to find any suitable solutions within the set timeout.

The scalability of the synthesis step of our approaches makes them
particularly suitable for situations where many class expressions are to be
computed for the same knowledge base. For example, using the Set Transformer
architecture on the Carcinogenesis knowledge base, one can conjecture that the
minimum number of learning problems from which the cost of deep learning
becomes worthwhile is: 13 for NCES vs. CELOE, 69 for NCES vs. EvoLearner, 114
for NCES vs. ELTL, and 1 for NCES vs. ECII. These values are calculated by
solving for $n$ in $n\times
T_{\texttt{algo\\_learn}}>T_{\texttt{train}}+T_{\texttt{inference}}$, where
$T_{\texttt{algo\\_learn}}$, $T_{\texttt{train}}$, and
$T_{\texttt{inference}}$ are the average learning time of a search-based
approach, the training time, and the inference time of NCES, respectively.
Although ELTL appears to be one of the fastest search-based approaches, it
computes lower quality solutions compared to the other approaches as it runs
in the lightweight description logic $\mathcal{EL}$.

##  6\. Conclusion and Future Work

We proposed a novel family of approaches for class expression learning, which
we dub neural class expression synthesizers (NCES). NCES use neural networks
to directly synthesize class expressions from input examples without requiring
an expensive search over all possible class expressions. Given a set timeout
per prediction, we showed that our approach outperforms all state-of-the-art
search-based approaches on large knowledge bases. Taking training time into
account, our approach is suitable for application scenarios where many
concepts are to be learned for the same knowledge base. In future work, we
will investigate means to transfer the knowledge acquired on one knowledge
base to other knowledge bases. Furthermore, we plan to extend our approach to
more expressive description logics such as $\mathcal{ALCQ(D)}$.

## References

  * (1)
  * Bergstra and Bengio (2012) James Bergstra and Yoshua Bengio. 2012.  Random Search for Hyper-Parameter Optimization.  _J. Mach. Learn. Res._ 13 (2012), 281–305.
  * Bin et al. (2017) Simon Bin, Patrick Westphal, Jens Lehmann, and Axel Ngonga. 2017.  Implementing scalable structured machine learning for big data in the SAKE project. In _2017 IEEE International Conference on Big Data (Big Data)_. IEEE, 1400–1407.
  * Bizer et al. (2009) Christian Bizer, Jens Lehmann, Georgi Kobilarov, Sören Auer, Christian Becker, Richard Cyganiak, and Sebastian Hellmann. 2009\.  Dbpedia-a crystallization point for the web of data.  _Journal of web semantics_ 7, 3 (2009), 154–165.
  * Bordes et al. (2014) Antoine Bordes, Xavier Glorot, Jason Weston, and Yoshua Bengio. 2014.  A semantic matching energy function for learning with multi-relational data - Application to word-sense disambiguation.  _Mach. Learn._ 94, 2 (2014), 233–259.
  * Bordes et al. (2013) Antoine Bordes, Nicolas Usunier, Alberto García-Durán, Jason Weston, and Oksana Yakhnenko. 2013\.  Translating Embeddings for Modeling Multi-relational Data. In _NIPS_. 2787–2795.
  * Bühmann et al. (2016) Lorenz Bühmann, Jens Lehmann, and Patrick Westphal. 2016\.  DL-Learner—A framework for inductive learning on the Semantic Web.  _Journal of Web Semantics_ 39 (2016), 15–24.
  * Cho et al. (2014a) Kyunghyun Cho, Bart van Merrienboer, Dzmitry Bahdanau, and Yoshua Bengio. 2014a.  On the Properties of Neural Machine Translation: Encoder-Decoder Approaches. In _SSST@EMNLP_. Association for Computational Linguistics, 103–111.
  * Cho et al. (2014b) Kyunghyun Cho, Bart van Merrienboer, Çaglar Gülçehre, Dzmitry Bahdanau, Fethi Bougares, Holger Schwenk, and Yoshua Bengio. 2014b.  Learning Phrase Representations using RNN Encoder-Decoder for Statistical Machine Translation. In _EMNLP_. ACL, 1724–1734.
  * Dai et al. (2020) Yuanfei Dai, Shiping Wang, Neal N Xiong, and Wenzhong Guo. 2020\.  A survey on knowledge graph embedding: Approaches, applications and benchmarks.  _Electronics_ 9, 5 (2020), 750.
  * Demir and Ngomo (2021) Caglar Demir and Axel-Cyrille Ngonga Ngomo. 2021\.  Convolutional Complex Knowledge Graph Embeddings. In _ESWC_ _(Lecture Notes in Computer Science, Vol. 12731)_. Springer, 409–424.
  * Dietterich et al. (1997) Thomas G Dietterich, Richard H Lathrop, and Tomás Lozano-Pérez. 1997.  Solving the multiple instance problem with axis-parallel rectangles.  _Artificial intelligence_ 89, 1-2 (1997), 31–71.
  * Dong et al. (2020) Xibin Dong, Zhiwen Yu, Wenming Cao, Yifan Shi, and Qianli Ma. 2020.  A survey on ensemble learning.  _Frontiers of Computer Science_ 14, 2 (2020), 241–258.
  * Fanizzi et al. (2008) Nicola Fanizzi, Claudia d’Amato, and Floriana Esposito. 2008\.  DL-FOIL Concept Learning in Description Logics. In _ILP_ _(Lecture Notes in Computer Science, Vol. 5194)_. Springer, 107–121.
  * Finn et al. (2017) Chelsea Finn, Pieter Abbeel, and Sergey Levine. 2017\.  Model-Agnostic Meta-Learning for Fast Adaptation of Deep Networks. In _ICML_ _(Proceedings of Machine Learning Research, Vol. 70)_. PMLR, 1126–1135.
  * Heindorf et al. (2022) Stefan Heindorf, Lukas Blübaum, Nick Düsterhus, Till Werner, Varun Nandkumar Golani, Caglar Demir, and Axel-Cyrille Ngonga Ngomo. 2022\.  EvoLearner: Learning Description Logics with Evolutionary Algorithms. In _WWW_. ACM, 818–828.
  * Heist et al. (2020) Nicolas Heist, Sven Hertling, Daniel Ringler, and Heiko Paulheim. 2020.  Knowledge Graphs on the Web-An Overview.
  * Heist and Paulheim (2019) Nicolas Heist and Heiko Paulheim. 2019.  Uncovering the Semantics of Wikipedia Categories. In _ISWC (1)_ _(Lecture Notes in Computer Science, Vol. 11778)_. Springer, 219–236.
  * Hochreiter and Schmidhuber (1997) Sepp Hochreiter and Jürgen Schmidhuber. 1997.  Long Short-Term Memory.  _Neural Comput._ 9, 8 (1997), 1735–1780.
  * Konev et al. (2016) Boris Konev, Ana Ozaki, and Frank Wolter. 2016.  A Model for Learning Description Logic Ontologies Based on Exact Learning. In _AAAI_. AAAI Press, 1008–1015.
  * Kouagou et al. (2022) N’Dah Jean Kouagou, Stefan Heindorf, Caglar Demir, and Axel-Cyrille Ngonga Ngomo. 2022\.  Learning Concept Lengths Accelerates Concept Learning in ALC. In _ESWC_ _(Lecture Notes in Computer Science, Vol. 13261)_. Springer, 236–252.
  * Krech (2006) D Krech. 2006.  Rdflib: A python library for working with rdf.  _Online https://github. com/RDFLib/rdflib_ (2006).
  * Lee et al. (2019) Juho Lee, Yoonho Lee, Jungtaek Kim, Adam Kosiorek, Seungjin Choi, and Yee Whye Teh. 2019\.  Set transformer: A framework for attention-based permutation-invariant neural networks. In _International conference on machine learning_. PMLR, 3744–3753.
  * Lehmann (2009) J. Lehmann. 2009\.  DL-Learner: learning concepts in description logics.  _The Journal of Machine Learning Research_ (2009).
  * Lehmann (2010) J. Lehmann. 2010\.  _Learning OWL class expressions_. Vol. 22.  IOS Press.
  * Lehmann et al. (2011) J. Lehmann, S. Auer, L. Bühmann, and S. Tramp. 2011\.  Class expression learning for ontology engineering.  _Journal of Web Semantics_ (2011).
  * Lehmann and Hitzler (2010) J. Lehmann and P. Hitzler. 2010.  Concept learning in description logics using refinement operators.  _Machine Learning_ 78 (2010).
  * Lehmann and Völker (2014) Jens Lehmann and Johanna Völker. 2014.  _Perspectives on ontology learning_. Vol. 18.  IOS Press.
  * McGuinness et al. (2004) Deborah L McGuinness, Frank Van Harmelen, et al. 2004\.  OWL web ontology language overview.  _W3C recommendation_ 10, 10 (2004), 2004.
  * Nagypál (2005) Gábor Nagypál. 2005\.  History ontology building: The technical view.  _Humanities, Computers and Cultural Heritage_ (2005), 207.
  * Nardi et al. (2003) D. Nardi, Ronald J. Brachman, et al. 2003\.  An introduction to description logics.  _Description logic handbook_ 1 (2003).
  * Nickel et al. (2012) M. Nickel, V. Tresp, and H. Kriegel. 2012.  Factorizing yago: scalable machine learning for linked data. In _Proc. of WWW_.
  * Ozaki (2020) A. Ozaki. 2020.  Learning Description Logic Ontologies: Five Approaches. Where Do They Stand?  _KI-Künstliche Intelligenz_ (2020).
  * Qi et al. (2017) Charles R Qi, Hao Su, Kaichun Mo, and Leonidas J Guibas. 2017\.  Pointnet: Deep learning on point sets for 3d classification and segmentation. In _Proceedings of the IEEE conference on computer vision and pattern recognition_. 652–660.
  * Rizzo et al. (2020) G. Rizzo, N. Fanizzi, and C. d’Amato. 2020.  Class expression induction as concept space exploration: From DL-Foil to DL-Focl.  _Future Generation Computer Systems_ (2020).
  * Sagi and Rokach (2018) Omer Sagi and Lior Rokach. 2018.  Ensemble learning: A survey.  _Wiley Interdisciplinary Reviews: Data Mining and Knowledge Discovery_ 8, 4 (2018), e1249.
  * Sarker and Hitzler (2019) M. K. Sarker and P. Hitzler. 2019.  Efficient concept induction for description logics. In _Proc. of AAAI_.
  * Schmidt-Schauß and Smolka (1991) M. Schmidt-Schauß and G. Smolka. 1991.  Attributive concept descriptions with complements.  _Artificial intelligence_ (1991), 1–26.
  * Snell et al. (2017) Jake Snell, Kevin Swersky, and Richard Zemel. 2017\.  Prototypical networks for few-shot learning.  _Advances in neural information processing systems_ 30 (2017).
  * Tran et al. (2014) Thanh-Luong Tran, Quang-Thuy Ha, Thi-Lan-Giao Hoang, Linh Anh Nguyen, and Hung Son Nguyen. 2014\.  Bisimulation-based concept learning in description logics.  _Fundamenta Informaticae_ 133, 2-3 (2014), 287–303.
  * Vrandečić and Krötzsch (2014) Denny Vrandečić and Markus Krötzsch. 2014.  Wikidata: a free collaborative knowledgebase.  _Commun. ACM_ 57, 10 (2014), 78–85.
  * Wang et al. (2017) Q. Wang, Z. Mao, B. Wang, and L. Guo. 2017\.  Knowledge graph embedding: A survey of approaches and applications.  _IEEE Transactions on Knowledge and Data Engineering_ (2017).
  * Wang et al. (2016) Z. Wang, J. Li, Z. LIU, and J. TANG. 2016\.  Text-enhanced representation learning for knowledge graph. In _Proc. of IJCAI_.
  * Westphal et al. (2019) Patrick Westphal, Lorenz Bühmann, Simon Bin, Hajira Jabeen, and Jens Lehmann. 2019.  SML-Bench–A benchmarking framework for structured machine learning.  _Semantic Web_ 10, 2 (2019), 231–245.
  * Wu et al. (2016) Y. Wu, M. Schuster, Z. Chen, et al. 2016\.  Google’s neural machine translation system: Bridging the gap between human and machine translation.  _arXiv preprint arXiv:1609.08144_ (2016).
  * Xie et al. (2016) R. Xie, Z. Liu, J. Jia, H. Luan, and M. Sun. 2016.  Representation learning of knowledge graphs with entity descriptions. In _Proc. of AAAI_.
  * Zaheer et al. (2017) Manzil Zaheer, Satwik Kottur, Siamak Ravanbakhsh, Barnabas Poczos, Russ R Salakhutdinov, and Alexander J Smola. 2017.  Deep sets.  _Advances in neural information processing systems_ 30 (2017).
  * Zhang et al. (2016) Fuzheng Zhang, Nicholas Jing Yuan, Defu Lian, Xing Xie, and Wei-Ying Ma. 2016\.  Collaborative knowledge base embedding for recommender systems. In _Proceedings of the 22nd ACM SIGKDD international conference on knowledge discovery and data mining_. 353–362.
  * Zhang et al. (2019) J. Zhang, T. He, S. Sra, and A. Jadbabaie. 2019\.  Why gradient clipping accelerates training: A theoretical justification for adaptivity.  _arXiv preprint arXiv:1905.11881_ (2019).
  * Zhao et al. (2018) H. Zhao, S. Sun, and B. Jin. 2018.  Sequential fault diagnosis based on LSTM neural network.  _Ieee Access_ (2018).
  * Zulqarnain et al. (2019) M. Zulqarnain, R. Ghazali, M. G. Ghouse, et al. 2019\.  Efficient processing of GRU based on word embedding for text classification.  _JOIV_ 3 (2019).

##  Appendix A Appendix

Additional experiments were conducted to further demonstrate the effectiveness
of neural class expression synthesizers. These include performance measures
with respect to random permutations of the elements in the input sets, and
class expression synthesis using the simple embedding model TransE.

Table 6. Average performance change after shuffling input examples. $\Delta$
stands for difference.

| F1(%) $\Delta$
---|---
| Carcinogenesis | Mutagenesis | Semantic Bible | Vicodi
NCES${}_{\text{LSTM}}$ | -2.14 | +01.96 | -10.74 | -0.49
NCES${}_{\text{GRU}}$ | +2.07 | +19.06 | -09.78 | +2.71
NCES${}_{\text{ST}}$ |  00.00 |  000.00 |  000.00 |  00.00
| Accuracy(%) $\Delta$
| Carcinogenesis | Mutagenesis | Semantic Bible | Vicodi
NCES${}_{\text{LSTM}}$ | -0.09 | -0.32 | -5.11 | -0.33
NCES${}_{\text{GRU}}$ |  00.00 | +0.59 | -1.52 | +0.06
NCES${}_{\text{ST}}$ |  00.00 |  00.00 |  00.00 |  00.00

(a)

(b)

Figure 4. Training curves using TransE embeddings. Table 7. Evaluation of NCES instances per dataset using TransE embeddings.  |  F1(%) $\uparrow$
---|---
| Carcinogenesis | Mutagenesis | Semantic Bible | Vicodi
NCES${}_{\text{LSTM}}$ |  81.55$\pm$28.28 |  73.16$\pm$41.04 |  86.01$\pm$25.14 |  82.25$\pm$28.41
NCES${}_{\text{GRU}}$ |  88.07$\pm$25.05 |  55.51$\pm$45.60 |  74.04$\pm$32.75 |  86.30$\pm$24.11
NCES${}_{\text{ST}}$ |  87.82$\pm$23.74 |  79.40$\pm$34.61 |  88.01$\pm$19.81 |  89.89$\pm$24.70
NCES${}_{\text{ST+GRU}}$ |  90.94$\pm$22.31 |  84.45$\pm$31.57 |  85.86$\pm$30.12 |  95.51$\pm$13.56
NCES${}_{\text{ST+LSTM}}$ |  93.23$\pm$15.50 |  86.57$\pm$30.94 |  90.45$\pm$23.02 |  93.44$\pm$17.70
NCES${}_{\text{GRU+LSTM}}$ |  93.22$\pm$14.60 |  78.83$\pm$35.41 |  87.83$\pm$22.94 |  90.85$\pm$19.87
NCES${}_{\text{ST+GRU+LSTM}}$ |  93.33$\pm$16.89 |  95.23$\pm$15.66 |  88.97$\pm$25.69 |  95.99$\pm$11.86
|  Accuracy(%) $\uparrow$
| Carcinogenesis | Mutagenesis | Semantic Bible | Vicodi
NCES${}_{\text{LSTM}}$ |  99.69$\pm$0.79 |  99.64$\pm$0.99 |  98.34$\pm$03.70 |  99.81$\pm$0.51
NCES${}_{\text{GRU}}$ |  99.73$\pm$1.29 |  99.03$\pm$2.65 |  93.89$\pm$13.05 |  99.85$\pm$0.48
NCES${}_{\text{ST}}$ |  99.68$\pm$0.89 |  99.78$\pm$0.37 |  98.49$\pm$02.65 |  99.89$\pm$0.39
NCES${}_{\text{ST+GRU}}$ |  99.79$\pm$0.71 |  99.84$\pm$0.35 |  96.37$\pm$09.29 |  99.95$\pm$0.27
NCES${}_{\text{ST+LSTM}}$ |  99.88$\pm$0.48 |  99.86$\pm$0.35 |  98.65$\pm$03.62 |  99.90$\pm$0.40
NCES${}_{\text{GRU+LSTM}}$ |  99.89$\pm$0.33 |  99.66$\pm$0.98 |  98.26$\pm$04.48 |  99.91$\pm$0.34
NCES${}_{\text{ST+GRU+LSTM}}$ |  99.88$\pm$0.49 |  99.95$\pm$0.09 |  97.05$\pm$08.84 |  99.94$\pm$0.27
|  Runtime(sec.) $\downarrow$
| Carcinogenesis | Mutagenesis | Semantic Bible | Vicodi
NCES${}_{\text{LSTM}}$ |  0.80$\pm$0.0 |  0.34$\pm$0.0 |  0.32$\pm$0.0 |  0.26$\pm$0.0
NCES${}_{\text{GRU}}$ |  0.08$\pm$0.0 |  0.14$\pm$0.0 |  0.18$\pm$0.0 |  0.35$\pm$0.0
NCES${}_{\text{ST}}$ |  0.04$\pm$0.0 |  0.10$\pm$0.0 |  0.17$\pm$0.0 |  0.07$\pm$0.0
NCES${}_{\text{ST+GRU}}$ |  0.29$\pm$0.0 |  0.66$\pm$0.0 |  0.13$\pm$0.0 |  0.11$\pm$0.0
NCES${}_{\text{ST+LSTM}}$ |  0.31$\pm$0.0 |  0.74$\pm$0.0 |  0.48$\pm$0.0 |  0.20$\pm$0.0
NCES${}_{\text{GRU+LSTM}}$ |  0.65$\pm$0.0 |  1.37$\pm$0.0 |  0.68$\pm$0.0 |  0.42$\pm$0.0
NCES${}_{\text{ST+GRU+LSTM}}$ |  0.35$\pm$0.0 |  1.13$\pm$0.0 |  0.60$\pm$0.0 |  0.28$\pm$0.0

###  A.1. Stability with Respect to Shuffled Inputs

We compared all three neural network architectures with respect to random
permutations applied to the sets of positive and negative examples. First, all
models are trained with the default ordering in the input sets. Then, they are
evaluated on the unseen learning problems where random permutations are
applied to the elements in the input sets. The results are reported in Table
6. From the table, we can observe that shuffling the input sets of examples
does not have any impact on the output of the Set Transformer model.
Oppositely, we can observe significant changes in the quality of the
synthesized expressions for recurrent neural network models (LSTM and GRU).
The GRU model showed improvements in F-measure on three datasets (with up to
19.06% on Mutagenesis) and dropped by 9.78% F-measure on the Semantic Bible
knowledge base. The LSTM model synthesized poorer solutions on three out of
four datasets with a narrow improvement by 1.96% F-measure on the Mutagenesis
knowledge base. The differences in accuracy are smaller because this metric
does not always properly reflect the quality of the synthesized solutions.

From these results, it is clear that the Set Transformer architecture is best
suited for class expression learning since it yields the same predictions
regardless of the order of the elements in the input sets. Nonetheless,
recurrent neural network architectures can be useful in application scenarios
where one needs multiple, closely related predictions for the same input sets.

###  A.2. Class Expression Synthesis Using TransE Embeddings

To check whether our approach works only with specific types of embedding
models, we ran additional experiments using the TransE (Bordes et al., 2013)
embedding model. TransE is a translational embedding model that represents
entities and relations as vectors in the same space and aims to minimize the
Euclidean distance between $s+p$ and $o$ for each triple $(s,p,o)$ in the
input knowledge graph. Although it is a simple embedding model, TransE remains
one of the most popular embedding models to achieve state-of-the-art results
in many downstream tasks while remaining scalable to large datasets.

Figure 4 shows the training curves of NCES instances using TransE embeddings.
As in the case of ConEx embeddings, the training accuracy curves grow
exponentially within the first 10 epochs and reach their culminant point
(100%) during training on the Carcinogenesis and Vicodi knowledge bases.
Similarly, the loss decreases at the same rate and approaches 0 in the last
training epochs. Additionally, Table 7 shows that high-quality solutions are
synthesized on the test set. This suggests that our NCES instances are able to
learn how to map instance data to class expressions in $\mathcal{ALC}$ with
translational embeddings provided by TransE. Consequently, one can expect NCES
instances to work well with other embedding models provided that they compute
embeddings that are to some extent faithful to the input knowledge graph.