# Informed Machine Learning for Improved Similarity Assessment in Process-
Oriented Case-Based Reasoning

Maximilian Hoffmann1,2 Ralph Bergmann1,2 1Business Information Systems II,
University of Trier, 54296 Trier, Germany
http://www.wi2.uni-trier.de
{hoffmannm<EMAIL_ADDRESS>
2German Research Center for Artificial Intelligence (DFKI)
Branch University of Trier, Behringstraße 21, 54296 Trier, Germany
{maximilian.hoffmann<EMAIL_ADDRESS>
###### Abstract

Currently, Deep Learning (DL) components within a Case-Based Reasoning (CBR)
application often lack the comprehensive integration of available domain
knowledge. The trend within machine learning towards so-called Informed
machine learning can help to overcome this limitation. In this paper, we
therefore investigate the potential of integrating domain knowledge into Graph
Neural Networks (GNNs) that are used for similarity assessment between
semantic graphs within process-oriented CBR applications. We integrate
knowledge in two ways: First, a special data representation and processing
method is used that encodes structural knowledge about the semantic
annotations of each graph node and edge. Second, the message-passing component
of the GNNs is constrained by knowledge on legal node mappings. The evaluation
examines the quality and training time of the extended GNNs, compared to the
stock models. The results show that both extensions are capable of providing
better quality, shorter training times, or in some configurations both
advantages at once.

##  1 Introduction

Case-Based Reasoning (CBR) Aamodt and Plaza (1994); Richter and Weber (2013)
is used widespread across different domains, e. g., modeling of cooking
recipes Hoffmann et al. (2020), prediction of seawater temperatures Corchado
and Lees (2001), natural language processing of support tickets Amin et al.
(2020a), and assisted reuse of data mining workflows Zeyen et al. (2019). One
of its strengths is the use of structured domain knowledge that is modeled,
among others, for the case representation, for the definition of similarity
measures, and for case adaptation methods Richter and Weber (2013). An
integral part of recent CBR research is the use of Deep Learning (DL) methods,
which is indicated by workshops dedicated to this topic, e. g., the workshops
on the International Conference on Case-Based Reasoning (ICCBR) in 2017
Sánchez-Ruiz and Kofod-Petersen (2017) and 2019 Kapetanakis and Borck (2019),
and a variety of published papers, e. g., Mathisen et al. (2021); Hoffmann et
al. (2020); Amin et al. (2020a); Klein et al. (2019). Many of these works are
hybrid approaches where DL components are integrated in the underlying CBR
methodology Watson (1999) to solve certain core tasks such as similarity
assessment or case adaptation. This is a reasonable choice due to the ability
of DL to automatically learn patterns from available data, diminishing the
need for time-consuming manual data analysis and extraction Stahl and Gabel
(2006); Leake and Crandall (2020). However, most of these hybrid approaches
lack a comprehensive integration of the CBR-provided knowledge into the DL
methods, leading to possibly unused potential of improved quality and
performance. A recent trend in artificial intelligence research explicitly
deals with such an integration of symbolic knowledge into machine learning
methods, i. e., Informed Machine Learning von Rueden et al. (2020). The core
ideas of informed machine learning can be directly used in our scenario of
hybrid approaches by combining the strengths of CBR and DL: On the one hand,
CBR offers a large amount of domain knowledge that is often of high quality.
On the other hand, the DL components provide the flexibility and
expressiveness to integrate and process this domain knowledge.

In this paper, we want to investigate the possibilities of informed machine
learning in the research field of Process-Oriented Case-Based Reasoning
(POCBR) Minor et al. (2014). POCBR is a subfield of CBR that deals with
procedural knowledge such as semantic graphs Bergmann and Gil (2014). We
examine how POCBR domain knowledge can be used to improve DL-based similarity
assessment between semantic graphs. The presented methods extend the DL models
from our previous work Hoffmann et al. (2020) and explain the representation
and integration of domain knowledge for two specific scenarios. We also put
these two methods into the context of an informed machine learning taxonomy by
von Rueden et al. [2020] to encourage a broader discussion about this topic in
CBR research. The paper is structured as follows: Section 2 shows foundations
regarding the used semantic graph representation and the similarity assessment
between these graphs and, additionally, related work is presented. Further,
Sect. 3 elaborates on our approach for integrating domain knowledge into
semantic graph embedding models. To evaluate our approach and to briefly
discuss the possibilities of domain knowledge integration for DL methods in
CBR, we present an experimental evaluation in Sect. 4. Finally, Sect. 5
concludes the paper and shows areas of future work.

##  2 Foundations and Related Work

The foundations include the semantic workflow representation that we use in
our concept and experiments as well as the similarity assessment between pairs
of these workflows (see Sect. 2.1). We also present the core ideas of informed
machine learning, as described by von Rueden et al. [2020] (see Sect. 2.2).
Further, related work is presented (see Sect. 2.3).

###  2.1 Semantic Workflow Representation and Similarity Assessment

Our main focus in this paper is similarity assessment between semantic graphs
in POCBR. We represent all case bases and queries as semantically annotated
directed graphs referred to as _NEST_ graphs introduced by Bergmann and Gil
[2014]. More specifically, a _NEST_ graph is a quadruple $W=(N,E,S,T)$ that is
composed of a set of nodes $N$ and a set of edges $E\subseteq N\times N$. Each
node and each edge has a specific type from $\Omega$ that is indicated by the
function $T:N\cup E\rightarrow\Omega$. Additionally, the function $S:N\cup
E\rightarrow\Sigma$ assigns a semantic description from $\Sigma$ (semantic
metadata language, e. g., an ontology) to nodes and edges. Whereas nodes and
edges are used to build the structure of each workflow, types and semantic
descriptions are additionally used to model semantic information. Hence, each
node and each edge can have a semantic description. Figure 1 shows a simple
example of a _NEST_ graph that represents a cooking recipe for making a
sandwich. The mayo-gouda sandwich is prepared by executing the cooking steps
coat and layer (task nodes) with the ingredients mayo, baguette, sandwich
dish, and gouda (data nodes). All components are linked by edges that indicate
relations, e. g., mayo is consumed by coat. Semantic descriptions of task
nodes and data nodes are used to further specify semantic information
belonging to the workflow components. Figure 1 shows an example of the
semantic description of the task node coat. The provided information is used
to describe the task more precisely. In this case, a spoon and a baguette
knife is needed to execute the task (Auxiliaries) and the estimated time that
the task takes is two minutes (Duration).

We use the CBR framework ProCAKE Bergmann et al. (2019) to process NEST
graphs, thus their semantic descriptions can be represented in various ways.
As seen in the example, atomic data types such as strings and numerics can be
combined within composite data types such as attribute-value pairs and lists.
This complexity and flexibility in representation is not easy to handle for
DL-based approaches (see Leake and Crandall (2020) and Hoffmann et al. (2020)
for more details) and requires specific data encoding methods which will be a
topic in our approach (see Sect. 3).

Figure 1: Exemplary Cooking Recipe represented as NEST Graph

Determining the similarity between two _NEST_ graphs, i. e., a query workflow
$\operatorname{\textit{QW}}$ and a case workflow $\operatorname{\textit{CW}}$,
requires a similarity measure that assesses the link structure of nodes and
edges as well as the semantic descriptions and types of these components.
Bergmann and Gil [2014] propose a semantic similarity measure that determines
a similarity based on the local-global principle. A global similarity, i. e.,
the similarity between two graphs, is composed of local similarities, i. e.,
the pairwise similarities of nodes and edges. The similarity between two nodes
with identical types is defined as the similarity of the semantic descriptions
of these nodes. The similarity between two edges with identical types does not
only consider the similarity of the semantic descriptions of the edges, but in
addition the similarity of the connected nodes as well. In order to put
together a global similarity by aggregating local similarities, the domain’s
similarity model has to define similarity measures for all components of the
semantic description, i. e.,
$\operatorname{\textit{sim}}_{\Sigma}:\Sigma\times\Sigma\rightarrow[0,1]$. The
global similarity of the two workflows
$\operatorname{\textit{sim}}(\operatorname{\textit{QW}},\operatorname{\textit{CW}})$
is finally calculated by finding an injective partial mapping $m$ that
maximizes
$\operatorname{\textit{sim}}_{m}(\operatorname{\textit{QW}},\operatorname{\textit{CW}})$.

$\operatorname{\textit{sim}}(\operatorname{\textit{QW}},\operatorname{\textit{CW}})=max\\{\operatorname{\textit{sim}}_{m}(\operatorname{\textit{QW}},\operatorname{\textit{CW}})\leavevmode\nobreak\
|\\\ \text{admissible mapping}\leavevmode\nobreak\ m\\}$ (1)

The complex process of finding a mapping that maximizes the global similarity
between a query $\operatorname{\textit{QW}}$ and a single case
$\operatorname{\textit{CW}}$ is tackled by utilizing an A* search algorithm
(see Bergmann and Gil (2014) for more details). However, A* search is usually
time-consuming and can lead to long retrieval times Zeyen and Bergmann (2020);
Klein et al. (2019); Hoffmann et al. (2020) which also motivates this work.

###  2.2 Informed Machine Learning

von Rueden et al. [2020] characterize the integration of prior knowledge, i.
e., already existing knowledge from the present domain, into a machine
learning pipeline according to three key factors. All three of these key
factors further contain several sub-factors. The source of the prior knowledge
is the first key factor. It is further distinguished between sources with
different levels of validation, e. g., knowledge from natural sciences is
explicitly validated while common world knowledge is usually not. Besides the
source of knowledge, knowing and analyzing its representation is also crucial
for classifying informed machine learning methods. A knowledge representation
can vary from logic rules over knowledge graphs to human feedback, all
requiring individual processing strategies. The third factor is the point of
knowledge integration within the machine learning pipeline. This refers to
four possible integration hooks: the training data, the DL architecture
(referred to as ”hypothesis set” in the original paper von Rueden et al.
(2020)), the learning algorithm, and the final hypothesis. In our approach, we
will particularly focus on the representation and the point of integration of
the domain knowledge (see Sect. 3).

###  2.3 Related Work

In CBR research, several approaches have been proposed that use DL methods as
a key component. However, the presentation of these approaches is mostly
outcome-focused, concentrating on the integration of the DL methods within a
CBR application rather than on the usage of CBR-provided knowledge. One of the
few examples of the latter approaches is the work of Stahl and Gabel [2006]
where they provide a general learning approach for similarity measures. They
identify three different knowledge sources, i. e., similarity meta knowledge,
knowledge from the case base, and expert knowledge, that are beneficial for
being integrated into their machine learning pipeline. Outcome-focused
approaches are much more common. For instance, Corchado and Lees [2001]
integrate a neural network into CBR retrieval and reuse phases where the
network is dynamically retrained during runtime w. r. t. the current query.
The application is used to predict water temperatures along a sea route.
Dieterle and Bergmann [2014] use neural networks for several tasks within
their CBR application that predicts prices of domain names, e. g., for
feature-weighting of case attributes. In our previous work Hoffmann et al.
(2020); Klein et al. (2019) and in other approaches Mathisen et al. (2021);
Amin et al. (2020b), siamese neural networks are used for learning similarity
functions between cases. The resulting similarity functions are mainly used
for retrieval situations. The application of DL methods on case adaptation is
discussed by several other approaches, e. g., Leake et al. (2021); Liao et al.
(2018). These two exemplary approaches pursue the idea of using neural
networks in combination with the case-difference heuristic for solving an
upcoming problem with known solutions from the case base. DL is also used in
the context of textual CBR Amin et al. (2020a, b). These approaches use
siamese neural networks and word embeddings for tasks of natural language
processing. Furthermore, Gabel and Godehardt [2015] and Keane and Kenny [2019]
tackle a major drawback of DL applications when compared to CBR applications:
the reduced explainability. The former approach addresses the problem by
projecting DL predictions onto real cases before using them. The latter
approach tries to explain the predictions of DL methods with CBR components in
a twin-systems approach. To guide research of CBR and DL, Leake and Crandall
[2020] elaborate ways where the CBR methodology Watson (1999) can advance DL.
They present benefits and drawbacks of both methods and, additionally,
identify questions that arise when developing hybrid approaches. These
questions further motivate our work since we see knowledge integration along
with suitable case representation and similarity assessment, i. e., the main
contributions of this paper, as a key factor for answering these questions.

##  3 Similarity Assessment with Informed Machine Learning Methods

This section presents our approach for integrating domain knowledge into the
Graph Neural Networks (GNNs) for POCBR, which were originally proposed in our
previous work Hoffmann et al. (2020). We present two novel extensions to the
GNNs, aimed at improving the similarity assessment capabilities. The
extensions are motivated by utilizing existing knowledge present in the
underlying CBR application regarding case representation (see Sect. 3.2) and
similarity matching constraints (see Sect. 3.3). Before explaining these
methods, we will first give a brief overview of the GNNs that build the
foundation for the approach in this paper (see Sect. 3.1).

###  3.1 Graph Neural Networks for Similarity Assessment

Two siamese GNNs are used for learning pairwise graph similarities, i. e., the
Graph Embedding Model (GEM) and the Graph Matching Network (GMN) (see Fig. 2).
Both models follow the same basic structure but show different levels of
expressiveness which leads to different areas of application. The four main
components are the encoder, the propagation layer, the aggregator, and the
graph similarity. The encoder initially performs an encoding and embedding of
all nodes and edges from both graphs to form single embedding vectors which
further represent individual nodes and edges, respectively. During
propagation, the vector-based information is iteratively merged according to
the edge structure of the graphs. Thereby, node embedding vectors are updated
via element-wise summations according to the information of all incoming edges
and the nodes that are connected via these edges. After propagating
information for a number of rounds, the aggregator combines the embeddings of
all nodes from each graph to form a single whole-graph embedding. The final
component forms a single scalar similarity value with the embedding vectors of
both graphs.

Figure 2: GEM (left) and GMN (right) (based on Li et al. (2019))

The difference between both models comes from a different propagation strategy
and a different computation of the final similarity. The GEM uses an isolated
propagation strategy that only propagates information within a single graph.
The aggregated vectors of both graphs are eventually put together to a
similarity value via a simple cosine similarity. In contrast, the GMN uses a
cross-graph matching component that propagates information across both graphs
in an early state of similarity assessment. Thereby, the embedding vector of
each node from one graph is compared with the embedding vector of each node
from the other graph by means of a vector similarity measure. The higher the
similarity and therefore the attention, the stronger is the information flow
between two nodes. The whole-graph embedding vectors are eventually fed into a
Multi-Layer Perceptron (MLP) that generates the final similarity. These
differences of both models lead to different reasonable application areas.
That is, GEM is faster but less expressive and therefore more suitable to be
used as a similarity measure for candidate filtering such as in MAC/FAC
applications Forbus et al. (1995); Kendall-Morwick and Leake (2014). GMN is
slower than GEM but shows great potential in approximating graph similarities
with low margins of error (see the evaluation in Hoffmann et al. (2020) for
more details).

###  3.2 Extension 1 - Tree Encoding

The first extension concerns the encoding and processing of semantic
descriptions (see Sect. 2.1) in GEM and GMN. Currently, each atomic entry of a
semantic description (e. g., integer, float, string) is encoded as a single
vector consisting of a one-hot type encoding part with a proprietary data
encoding part specific to each data type. Composite data types (e. g.,
attribute-value lists, sets) are handled as a collection of atomic encodings
which is transformed to a single matrix structure per encoded semantic
description. For instance, the exemplary semantic description from Fig. 1
shows two composite types, i. e., the attribute-value list coat and the list
Auxiliaries, as well as three atomic types, i. e., the duration and both list
entries. The encoding of this semantic description is a single matrix
consisting of three entries which equals the number of all atomic types. The
sequence results from the two composite types that are concatenated.

Figure 3: Exemplary Tree Structure of an Encoded Semantic Description

In order to process this data in the encoder step of GEM and GMN, the matrix
is processed by Recurrent Neural Networks (RNNs) which aggregate the sequence
of vectors to a single vector. This is not ideal since the underlying sequence
structure does not accurately represent the relations of the components of the
semantic descriptions. Therefore, with the first extension, we represent the
encoded semantic descriptions as tree structures and extend the encoders of
GEM and GMN to process these tree structures with GNNs. Fig. 3 shows the new
format where atomic types are represented as ellipses and composite types as
rectangles. The connections between nodes represent their relations, i. e.,
child-of and parent-of. Regarding the computations in the neural network, we
handle this representation as a graph that is processed with a GNN Battaglia
et al. (2018). Analogously to the general embedding process of GEM and GMN
(see Fig. 3.1), information is propagated between the nodes of the graph along
the edge connections. The edges are either of type child-of or parent-of,
which is given as a piece of information that is propagated. The result after
several iterations of propagation is a single embedding vector for each node
and each edge of the workflow graph. The used GNN can also be parameterized to
either reuse the same neural network layers for each iteration or to use
different layers. The latter configuration is more expressive and
computationally expensive since parameter learning can be performed
individually for each iteration (see both configurations as part of our
evaluation in Sect. 4). Regarding the taxonomy of informed machine learning
(see Sect. 2.2), this method focuses on knowledge representation and
integration. We use a new representation for the semantic descriptions which
is very similar to their domain-defined tree structure. We also integrate this
representation into the training data and the hypothesis set, in order to
enable the model to use the data properly. The source of the data is given by
the structural relations of the semantic descriptions. In Sect. 4 of their
paper, Leake and Crandall [2020] raise a few key questions for CBR research of
DL integrations, with one of those questions concerning case representation.
We want to point out that the aforementioned extension contributes to this
question. Our approach can also be used as a standalone method for
representing and processing structured, object-oriented cases such as the
semantic descriptions.

###  3.3 Extension 2 - Matching Constraints

The second extension concerns the propagation component of GMN. It is inspired
by the graph matching algorithm that we use to assess the similarity of graphs
(see Sect. 2.1). In the propagation component of GMN (see Fig. 2), each node
of one graph is compared with each node of the other graph by means of their
respective cosine vector similarity (ranged between 0 and 1). The resulting
similarity values are activated with a softmax activation in order to generate
attention values. This way, information is propagated between the nodes of two
graphs w. r. t. to their pairwise attention.

Figure 4: Exemplary Matching Process

According to the definition of the used graph matching algorithm (see Sect.
2.1), only nodes and edges with the same type are allowed to be matched. That
is, the matching process is constrained according to the types of nodes and
edges. These constraints can be integrated into the propagation component of
GMN by only allowing to determine cosine similarity for nodes of the same
type. Fig. 4 shows an exemplary matching process of a query and a case graph
(grey background) with dotted lines depicting all possible mappings of the
query nodes to the case nodes. All illegal mappings are marked with a bold
cross. For instance, coat is a task node and can only be matched with other
task nodes, leading to an illegal match between coat and ciabatta. The data
node baguette has only one possible mapping partner since the case graph only
contains one data node, i. e., ciabatta. All pairs of nodes with different
types are assigned to a similarity of 0, representing maximum dissimilarity.
Thus, their attention is close to 0 which leads to almost no information
propagation between nodes of different types. Please note that this method
only applies to GMN since GEM’s propagation component does not include a
cross-graph attention matching. Regarding the taxonomy of informed machine
learning (see Sect. 2.2), the source of the knowledge is given by the
similarity definitions for semantic graphs. It is represented in form of
mapping constraints and directly integrated into the hypothesis set. In
contrast to the first extension, there is no change of the input data
required.

##  4 Experimental Evaluation

Table 1: Evaluation Results

We evaluate our extended GNNs by comparing them to the stock models of GEM and
GMN (see Sect. 3.1). In addition, we compare the effects of different
combinations of the two extensions which are indicated by subscripts and
superscripts in our terminology: GEM1, for instance, is GEM extended with the
first extension. Furthermore, for the first extension, a superscript denotes
whether the propagation layers are reused or not, e. g., GEM1R for reused
layers (see Sect. 3.2 for the explanation of layer reuse). The second
extension is also marked with a subscript, e. g., GMN2. Combinations of both
extensions are marked with both numbers as a subscript, e. g., GMN1,2. This
gives a total of nine evaluated variants (see the columns in Tab. 1 for the
entire enumeration).

We measure the Mean Average Error (MAE) of the predicted similarities as an
indication of how well the model learns to assess pairwise case similarities,
which correlates with suitable retrieval quality. In addition, we look at the
influence of the extensions on the performance of each model. We take the
training time as a representative measure since performance changes according
to training time can be commonly transferred to other indicators, e. g., test
time, validation time or inference latency Coleman et al. (2019).
Additionally, we report only the relative changes rather than the absolute
time values in order to allow a direct comparison for this evaluation. We
investigate the following hypotheses:

  1. H1

Integrating domain knowledge into GEM and GMN can improve the quality of
similarity assessment w. r. t. MAE.

  2. H2

The integration of domain knowledge into GEM and GMN can decrease training
time.

The hypotheses also aim at investigating a possible trade-off between quality
improvements (H1) and increased training times (H2). Unless the extensions
decrease both the MAE and the training time, it has to be discussed which
applications benefit from which approach.

###  4.1 Experimental Setup

We perform our experiments with two case bases from different domains. The
cooking workflows (CB-I) are derived from 40 manually-modeled cooking recipes
that are extended to 800 workflows by generalizing and specializing
ingredients and cooking steps Müller (2018), resulting in 660 training cases,
60 validation cases, and 80 test cases. The workflows of the data mining
domain (CB-II) are built from sample processes that are delivered with
RapidMiner (see Zeyen et al. (2019) for more details), resulting in 509
training cases, 40 validation cases, and 60 test cases. The training cases are
used as training input for the neural networks while the validation cases are
used to monitor the training process and to optimize hyperparameter values.
Hyperparameter tuning is performed individually per domain with the two stock
models of GEM and GMN. The extended models then use the same hyperparameter
settings as the associated stock model, e. g., GEM1R uses the same
hyperparameter configuration as GEM in the same domain. The measurements of
MAE compare the predictions of the GNNs with the ground-truth similarity
values according to our semantic graph similarity measure (see Sect. 2.1 and
Hoffmann et al. (2020) for more details). Those values are determined by
computing pairwise similarities for all testing cases and averaging the values
to a single number. Additionally, the average time for a single training
iteration with 64 workflow pairs is measured to provide an insight of the
variants’ effects on training time. The machine that is used for training and
testing computations is a PC with an Intel i7 6700 CPU (4 cores, 8 threads),
an NVIDIA GTX 3070 GPU, and 48 GB of RAM, running Windows 10 64-bit.

###  4.2 Experimental Results

The evaluation results are depicted in Tab. 1. The table shows the MAE and the
average training iteration time (in milliseconds) of all evaluated models and
for both case bases. The lowest MAE and training time values are highlighted
in bold font, grouped by base model (first line) and domain (rotated text on
the left).

The quality of the models w. r. t. MAE shows no significant influence of the
extensions on the GEM model. Both for CB-I and CB-II, the best MAE is provided
by the stock GEM model. While the extended models of CB-I are on par with the
stock model, the extended models of CB-II show a decreased quality with a
maximum reduction of approx. 17% for GEM1R. The effectiveness of the extended
GMN variants is different. The GMN stock model is not the best performing
model for either of the case bases. In fact, the extensions lead to a maximum
MAE decrease of approx. 12% for CB-I and of approx. 10% for CB-II. But not all
extensions decreased the MAE and the success of one extension is not
consistent for both case bases. For instance, whereas GEM1 shows the best
overall MAE for CB-I it does not lead to a decrease when applied to CB-II. The
same results can be observed for GEM2 when applied to CB-II.

The time values show different effects of the extensions for either of the
case bases and the base models. Integrating the first extension into GEM
results in time increases for CB-I with a maximum of approx. 44%. For GEM and
CB-II, however, the first extension brings performance benefits of 17 - 23%.
The extended variants of GMN show a similar picture. The first extension has
similar run times compared to the stock GMN model. Only GMN1 for CB-I sticks
out with an increase of approx. 17%. The second extension only has a large
impact on performance for CB-I, i. e., a maximum of 24% slower than the stock
model. For CB-II, the combination of both extensions seems to increase the
training times. It is also apparent that GMN1R decreased the training time for
both case bases compared to the stock model and achieves the lowest values of
the GMN variants.

###  4.3 Discussion

The most noticeable observation of this experiment is the inconsistency of the
effects that different extensions have on different domains. Compared to the
stock models, those effects range from a decrease in training time and MAE, e.
g., GMN1R, to an increase in training time and MAE, e. g., GMN2. This leads to
the preliminary result of this experiment: Whether an extension method is
beneficial for the underlying GNN is highly dependent on the method itself and
the target domain. Individual testing of different methods and subsequent
tuning is inevitable. The effect of the first extension on GEM is a good
example in which way more general knowledge about the case representation can
lead to different results in different domains. This extension significantly
increases the training time for CB-I and decreases it for CB-II, compared to
the stock models. This is reasonable as CB-II tends to have larger semantic
descriptions and graphs that are more affected by the slow, sequential
computations of RNNs which process the semantic descriptions in the stock
models (see Sect. 3.2). The graphs and semantic descriptions of CB-I are
smaller than those of CB-II and, thus, show an opposing effect where the
information propagation in the GNNs is more expensive than the RNN
computations. The example also shows the trade-off between quality and time:
In most cases, a reduction of the MAE results in an increase of time. This
means that the underlying domain should be analyzed for its requirements
regarding these two aspects and appropriate benchmarks should be conducted.
Considering the discussed results, H1 can be accepted for GMN due to multiple
retriever variants that improve quality, compared to the stock models. H2 can
also be accepted for GMN due to GMN1R which leads to a decreased training
time. The experiments show less indications of positive effects for GEM. The
first extension fails at improving the quality for both CB-I and CB-II. Thus,
H1 is rejected for GEM. H2 can be partly accepted due to the positive effects
of the first extension on the training time for CB-II.

##  5 Conclusion and Future Work

This paper examines the potential of including domain knowledge of Case-Based
Reasoning (CBR) applications into Deep Learning (DL) models for learning
similarities between semantic graphs. We present two different methods for
integration into two Graph Neural Networks. The first method aims at
representing the semantic annotations of nodes and edges in a tree structure
that enables the usage of message-passing neural networks for processing. The
tree structure reflects the implicit relations of the data which is composed
of composite and atomic data types. The second method introduces constraints
to the attention-based matching procedure of the GNN, based on domain
knowledge about legal node and edge mappings in the similarity assessment
procedure. This method guides the DL model to use very low attention for non-
legal mappings and higher attention for legal mappings. Both extensions are
part of an experimental evaluation, focusing on changes in retrieval quality
and training time. The results show that the extensions are able to improve
quality and to reduce training time when being compared to the stock models.
However, the effects are not consistent across different domains and different
models.

A focus of future work should be on conducting a more comprehensive evaluation
of the approaches from this paper in order to measure the influence of
knowledge integration for more domains. It has the goal of verifying the
results and finding more integration opportunities in the research field of
CBR. Additionally, the ideas of informed machine learning von Rueden et al.
(2020) can be used to provide a more detailed overview of the challenges and
opportunities when being applied to CBR. Furthermore, the approaches from this
paper can especially be a chance for applications that deal with case
adaptation and DL, e. g., Liao et al. (2018); Leake et al. (2021). Since
adaptation is usually a knowledge-intensive process, our approaches can help
by providing expressive learning capabilities combined with possibilities of
domain knowledge integration.

## References

  * Aamodt and Plaza [1994] Agnar Aamodt and Enric Plaza.  Case-based reasoning: Foundational issues, methodological variations, and system approaches.  AI Communications, 7(1):39–59, 1994.
  * Amin et al. [2020a] Kareem Amin, Stelios Kapetanakis, Nikolaos Polatidis, Klaus-Dieter Althoff, and Andreas Dengel.  Deepkaf: A heterogeneous cbr & deep learning approach for nlp prototyping.  In Mirjana Ivanovic, editor, International Conference on INnovations in Intelligent SysTems and Applications, pages 1–7, Piscataway, New Jersey, 2020. IEEE.
  * Amin et al. [2020b] Kareem Amin, George Lancaster, Stelios Kapetanakis, Klaus-Dieter Althoff, Andreas Dengel, and Miltos Petridis.  Advanced similarity measures using word embeddings and siamese networks in cbr.  In Yaxin Bi, Rahul Bhatia, and Supriya Kapoor, editors, Intelligent Systems and Applications, volume 1038 of Advances in Intelligent Systems and Computing, pages 449–462. Springer, Cham, 2020.
  * Battaglia et al. [2018] Peter W. Battaglia, Jessica B. Hamrick, Victor Bapst, Alvaro Sanchez-Gonzalez, Vinicius Zambaldi, Mateusz Malinowski, Andrea Tacchetti, David Raposo, Adam Santoro, Ryan Faulkner, Caglar Gulcehre, Francis Song, Andrew Ballard, Justin Gilmer, George Dahl, Ashish Vaswani, Kelsey Allen, Charles Nash, Victoria Langston, Chris Dyer, Nicolas Heess, Daan Wierstra, Pushmeet Kohli, Matt Botvinick, Oriol Vinyals, Yujia Li, and Razvan Pascanu.  Relational inductive biases, deep learning, and graph networks, 2018.  arXiv:1806.01261.
  * Bergmann and Gil [2014] Ralph Bergmann and Yolanda Gil.  Similarity assessment and efficient retrieval of semantic workflows.  Inf. Syst., 40:115–127, 2014.
  * Bergmann et al. [2019] Ralph Bergmann, Lisa Grumbach, Lukas Malburg, and Christian Zeyen.  ProCAKE: A Process-Oriented Case-Based Reasoning Framework.  In Workshop Proc. of ICCBR, volume 2567, pages 156–161. CEUR-WS.org, 2019.
  * Coleman et al. [2019] Cody Coleman, Daniel Kang, Deepak Narayanan, Luigi Nardi, Tian Zhao, Jian Zhang, Peter Bailis, Kunle Olukotun, Chris Ré, and Matei Zaharia.  Analysis of DAWNBench, a Time-to-Accuracy Machine Learning Performance Benchmark.  ACM SIGOPS Operating Systems Review, 53(1):14–25, 2019.
  * Corchado and Lees [2001] Juan M. Corchado and B. Lees.  Adaptation of cases for case based forecasting with neural network support.  In Sankar K. Pal, editor, Soft computing in case based reasoning, pages 293–319. Springer, London, 2001.
  * Dieterle and Bergmann [2014] Sebastian Dieterle and Ralph Bergmann.  A hybrid cbr-ann approach to the appraisal of internet domain names.  In Luc Lamontagne and Enric Plaza, editors, Case-based Reasoning Research and Development, volume 8765 of Lecture Notes in Computer Science, pages 95–109. Springer, Cham, 2014.
  * Forbus et al. [1995] Kenneth D. Forbus, Dedre Gentner, and Keith Law.  MAC/FAC: A Model of Similarity-Based Retrieval.  Cogn. Sci., 19(2):141–205, 1995.
  * Gabel and Godehardt [2015] Thomas Gabel and Eicke Godehardt.  Top-down induction of similarity measures using similarity clouds.  In Eyke Hüllermeier, editor, Case-based Reasoning Research and Development, volume 9343 of Lecture Notes in Computer Science, pages 149–164. Springer, Cham, 2015.
  * Hoffmann et al. [2020] Maximilian Hoffmann, Lukas Malburg, Patrick Klein, and Ralph Bergmann.  Using siamese graph neural networks for similarity-based retrieval in process-oriented case-based reasoning.  In Ian Watson and Rosina Weber, editors, Case-Based Reasoning Research and Development, volume 12311 of Lecture Notes in Computer Science, pages 229–244. Springer, Cham, 2020.
  * Kapetanakis and Borck [2019] Stelios Kapetanakis and Hayley Borck, editors.  Workshops Proceedings for the Twenty-seventh International Conference on Case-Based Reasoning co-located with the Twenty-seventh International Conference on Case-Based Reasoning (ICCBR 2019), Otzenhausen, Germany, September 8-12, 2019, CEUR Workshop Proceedings. CEUR-WS.org, 2019.
  * Keane and Kenny [2019] Mark T. Keane and Eoin M. Kenny.  How case-based reasoning explains neural networks: A theoretical analysis of xai using post-hoc explanation-by-example from a survey of ann-cbr twin-systems.  In Kerstin Bach and Cindy Marling, editors, Case-Based Reasoning Research and Development, volume 11680 of Lecture Notes in Computer Science, pages 155–171. Springer, Cham, 2019.
  * Kendall-Morwick and Leake [2014] Joseph Kendall-Morwick and David Leake.  A study of two-phase retrieval for process-oriented case-based reasoning.  In Stefania Montani and Lakhmi C. Jain, editors, Successful Case-based Reasoning Applications-2, volume 494 of Studies in Computational Intelligence, pages 7–27. Springer, 2014.
  * Klein et al. [2019] Patrick Klein, Lukas Malburg, and Ralph Bergmann.  Learning workflow embeddings to improve the performance of similarity-based retrieval for process-oriented case-based reasoning.  In Kerstin Bach and Cindy Marling, editors, Case-Based Reasoning Research and Development, volume 11680 of Lecture Notes in Computer Science, pages 188–203. Springer, Cham, 2019.
  * Leake and Crandall [2020] David Leake and David Crandall.  On bringing case-based reasoning methodology to deep learning.  In Ian Watson and Rosina Weber, editors, Case-Based Reasoning Research and Development, volume 12311 of Lecture Notes in Computer Science, pages 343–348. Springer, Cham, 2020.
  * Leake et al. [2021] David Leake, Xiaomeng Ye, and David Crandall.  Supporting case-based reasoning with neural networks: An illustration for case adaptation.  In Andreas Martin, Knuth Hinkelmann, Hans-Georg Fill, Aurona Gerber, Doug Lenat, Reinhard Stolle, and Frank van Harmelen, editors, Proceedings of the AAAI 2021 Spring Symposium on Combining Machine Learning and Knowledge Engineering. CEUR-WS.org, California, 2021.
  * Li et al. [2019] Yujia Li, Chenjie Gu, Thomas Dullien, Oriol Vinyals, and Pushmeet Kohli.  Graph Matching Networks for Learning the Similarity of Graph Structured Objects.  In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, Proc. of the 36th Int. Conf. on Machine Learning, ICML 2019, USA, volume 97 of Proc. of Machine Learning Research, pages 3835–3845. PMLR, 2019\.
  * Liao et al. [2018] Chieh-Kang Liao, Alan Liu, and Yu-Sheng Chao.  A machine learning approach to case adaptation.  In 2018 IEEE First International Conference on Artificial Intelligence and Knowledge Engineering (AIKE), pages 106–109. IEEE, 2018.
  * Mathisen et al. [2021] Bjørn Magnus Mathisen, Kerstin Bach, and Agnar Aamodt.  Using extended siamese networks to provide decision support in aquaculture operations.  Applied Intelligence, pages 1–12, 2021.
  * Minor et al. [2014] Mirjam Minor, Stefania Montani, and Juan A. Recio-García.  Process-oriented case-based reasoning.  Inf. Syst., 40:103–105, 2014.
  * Müller [2018] Gilbert Müller.  Workflow Modeling Assistance by Case-based Reasoning.  Springer, 2018.
  * Richter and Weber [2013] Michael M. Richter and Rosina O. Weber.  Case-Based Reasoning: A Textbook.  Springer, Berlin/Heidelberg, 2013.
  * Sánchez-Ruiz and Kofod-Petersen [2017] Antonio A. Sánchez-Ruiz and Anders Kofod-Petersen, editors.  Proceedings of ICCBR 2017 Workshops (CAW, CBRDL, PO-CBR), Doctoral Consortium, and Competitions co-located with the 25th International Conference on Case-Based Reasoning (ICCBR 2017), Trondheim, Norway, June 26-28, 2017, CEUR Workshop Proceedings. CEUR-WS.org, 2017.
  * Stahl and Gabel [2006] Armin Stahl and Thomas Gabel.  Optimizing similarity assessment in case-based reasoning.  In Proceedings, The Twenty-First National Conference on Artificial Intelligence and the Eighteenth Innovative Applications of Artificial Intelligence Conference, July 16-20, 2006, Boston, Massachusetts, USA, pages 1667–1670. AAAI Press, 2006.
  * von Rueden et al. [2020] Laura von Rueden, Sebastian Mayer, Katharina Beckh, Bogdan Georgiev, Sven Giesselbach, Raoul Heese, Birgit Kirsch, Julius Pfrommer, Annika Pick, Rajkumar Ramamurthy, Michał Walczak, Jochen Garcke, Christian Bauckhage, and Jannis Schuecker.  Informed Machine Learning - A Taxonomy and Survey of Integrating Knowledge into Learning Systems, 2020.  arXiv:1903.12394.
  * Watson [1999] Ian Watson.  Case-based reasoning is a methodology not a technology.  Knowledge-Based Systems, 12(5-6):303–308, 1999.
  * Zeyen and Bergmann [2020] Christian Zeyen and Ralph Bergmann.  A*-based similarity assessment of semantic graphs.  In Ian Watson and Rosina Weber, editors, Case-Based Reasoning Research and Development, volume 12311 of Lecture Notes in Computer Science, pages 17–32. Springer, Cham, 2020.
  * Zeyen et al. [2019] Christian Zeyen, Lukas Malburg, and Ralph Bergmann.  Adaptation of scientific workflows by means of process-oriented case-based reasoning.  In Kerstin Bach and Cindy Marling, editors, Case-Based Reasoning Research and Development, volume 11680 of Lecture Notes in Computer Science, pages 388–403. Springer, Cham, 2019.