# Towards a Flexible and High-Fidelity Approach to
Distributed DNN Training Emulation

Banruo Liu  0009-0002-9932-6096 Tsinghua University ,  Mubarak Adetunji
Ojewale  0000-0003-3861-1782 KAUST ,  Yuhan Ding  0009-0000-2829-0319 Tsinghua
University and  Marco Canini  0000-0002-5051-4283 KAUST

###### Abstract.

We propose NeuronaBox, a flexible, user-friendly, and high-fidelity approach
to emulate DNN training workloads. We argue that to accurately observe
performance, it is possible to execute the training workload on a subset of
real nodes and emulate the networked execution environment along with the
collective communication operations. Initial results from a proof-of-concept
implementation show that NeuronaBox replicates the behavior of actual systems
with high accuracy, with an error margin of less than 1% between the emulated
measurements and the real system.

††copyright: none††doi: ††conference: ; 2024††journalyear: ;

##  1\. Introduction

Modern DNN training clusters are remarkable engineering feats that more
closely resemble high-performance specialized computing environments – and the
large costs that these entail – than their mainstream counterparts in
commodity cloud computing datacenters. Optimizing resource utilization and
overall efficiency is paramount to maximizing the performance of training
workloads and minimizing associated costs. Therefore, it is highly desirable
to explore the large space of potential design considerations, performance
optimizations and configuration tunings, and ideally to do so without
incurring time, energy, and monetary costs of profiling training workloads at
scale on actual hardware.

Conducting in-depth “what if” analyses is essential to making informed
decisions and beneficial for a variety of scenarios. For instance, a ML
engineer may want to explore for a given model the impact of a particular
parallelization strategy111Possible strategies include data parallelism (Xing
et al., 2015), tensor parallelism (Shoeybi et al., 2020), pipeline parallelism
(Huang et al., 2019), fully sharded data parallelism (Zhao et al., 2023) among
others. on the training time and resource utilization. But it is not practical
to profile the training workload on thousands of HW accelerators (GPUs, TPUs,
etc.) for each possible strategy and different configurations. Similarly, a
researcher may want to quantify the benefits _at scale_ of a new optimization
technique to improve LLM training efficiency. Also in this case, it is hardly
feasible to run systematic experiments on a large cluster for each possible
configuration.

Recent work has shown the potential of simulation and analytical methods to
gain insights about DNN training behavior (Rashidi et al., 2020, 2022;
Robinson M. et al., 2022; Ardalani et al., 2024; Won et al., 2023; Bang et
al., 2023). However, these approaches suffer from at least one of three
limitations:  1) they require significant effort to transform the actual
workloads into an input model for the simulator,  2) they require explicit
models of parallelization strategies and incorporating new ones entails non-
trivial development of new simulation models, and,  3) the fidelity of their
results is limited by how faithful the underlying analytical models of compute
and communication are, which are notoriously difficult to get right at scale
(Mittal et al., 2018).

Figure 1. A training job running in a 4-node cluster (left) is emulated by
executing a single real node ($N_{0}$) wrapped by NeuronaBox, which emulates
the environment (right).

This work pioneers and advocates the use of emulation to aid in the analysis
and experimentation of distributed DNN training workloads. What we mean by
emulation is illustrated in Fig. 1. In a nutshell, we propose to isolate a
node subset (denoted as ${\mathcal{N}}$) of a distributed training job and
emulate the networked execution environment (denoted as ${\mathcal{E}}$) from
the perspective of the nodes in ${\mathcal{N}}$. We elect to view the network
as a natural boundary between the real and emulated environments since
communication between nodes in distributed training jobs typically occurs
through a collective communication library (e.g., NCCL (NVIDIA, 2024b)) that
both isolates the training scripts from dealing with all the unnecessary
details of the underlying network and demarcates clear points for inter-
process synchronization. We refer to our approach as NeuronaBox.

Notably, in this approach, the nodes in ${\mathcal{N}}$ run unmodified
training scripts, DNN frameworks and libraries. In particular, the
communication is handled by the actual collective communication library over
the network fabric. Meanwhile, the emulation environment ${\mathcal{E}}$
executes on dedicated hardware resources. The requirements for the emulation
environment are modest: it doesn’t require HW accelerators, it can run on a
single CPU-based node, and it requires network bandwidth to match the
available aggregate bandwidth of nodes in ${\mathcal{N}}$.

The key benefit of this approach is that it allows us to faithfully execute on
real hardware a portion of the training workload, which executes without
overheads from instrumentation (since there is none) nor profiling
${\mathcal{N}}$ in controlled conditions. Therefore, we can observe the actual
behavior of the training job, including the HW utilization metrics and
collective communication patterns that are critical in analyzing the
performance of distributed training workloads.

We wish to stress that our objective is to enable performance analysis and
optimization of distributed training workloads. Implications on model quality
are out of scope.

Thus, in this work, we initiate the study of these core research questions:
1) _What aspects of the workload must ${\mathcal{E}}$ emulate?_ 2) _How can
this approach maintain high fidelity while retaining wide applicability?_

With this short paper, we aim to provide an initial exploration of the
feasibility and potential of this approach, and to solicit feedback from the
community on the soundness of our approach and the prospects for future
research.

##  2\. Proposed Approach

Our goal is to enable any subset ${\mathcal{N}}$ of nodes in a distributed DNN
training job to execute the workload as if it were running on the entire set
of nodes and resources. We propose to achieve this goal by emulating the
interactions between ${\mathcal{N}}$ and its networked environment
${\mathcal{E}}$, which in a sense can be viewed as a virtualization of the
remaining job’s nodes. We argue that, under certain assumptions (detailed
below), by observing the performance of ${\mathcal{N}}$, we can analyze and
extrapolate the behavior for an entire job with high fidelity.

In our design, we adhere to two driving principles:

1) Ease of use. The user should be able to use NeuronaBox without any
modification to their existing code.

2) Flexibility and independence of parallelization strategies. NeuronaBox
should target a level of abstraction that is independent of the specific
parallelization strategy. NeuronaBox should be flexible to seamlessly adapt to
changes in parallelization strategies, including new ones that may emerge in
the future.

Workflow and architecture. Fig. 2 depicts an overview of our approach. The
high-level workflow of NeuronaBox is as follows. First, the user provides the
training script, the job configuration (e.g., world size, nodes in
${\mathcal{N}}$, HW resources, etc.), and optionally a set of what-if
conditions for experimentation (an example is given later). Second, NeuronaBox
initializes the emulation environment by synthesizing the network topology and
instantiating a communication model that calculates delay times for collective
operations within the emulated environment. Third, the training script is
launched (e.g., via torchrun). Meanwhile, desired performance metrics like
iteration time and resource utilization are gathered in ${\mathcal{N}}$.
Traces of collective communication (e.g., NCCL traces) can also be collected.

Assumptions. We assume that nodes have uniform hardware and network
configuration. In practice, it is common to execute distributed training jobs
on homogeneous clusters (Wang et al., 2024; Zheng et al., 2022; Touvron et
al., 2023; Liu et al., 2019; Lai et al., 2023). We assume that the model fits
entirely within ${\mathcal{N}}$. This assumption is not restrictive, as it is
common to use model or tensor parallelism within a node or a shard (Hwang et
al., 2023; Shoeybi et al., 2020) . We expect that these assumption yield a
sort of symmetry in the workload distribution across the nodes, which allows
us to treat the nodes in ${\mathcal{N}}$ as a representative sample of the
entire nodes. We discuss how to extend our arguments to a non-uniform scenario
in § 2.3.

Further, we assume that the collective communication layer is the only point
of interaction between ${\mathcal{N}}$ and ${\mathcal{E}}$. This assumption is
reasonable, as the collective communication layer is the primary interface
between the computation and the network stack in distributed training jobs.
Finally, note that we are free to modify the DNN framework and collective
communication libraries within the emulator. That is how we are able to
implement NeuronaBox!

Scalability. While collective communication is a natural layer to target in
our work, the astute reader may now wonder how scalable this approach is.
Scalability is traditionally a challenge in network emulators (Lantz et al.,
2010; Vahdat et al., 2002), as emulating a large number of nodes could
overload the emulator. Our key insight is that we are only interested in the
interaction between ${\mathcal{N}}$ and the outside world. And so, the actual
communication between the emulated nodes can be skipped. Instead, only the
delay resulting from these communication operations needs to be incorporated
into the emulation. As a result, the number of connections as well as the
amount of data transfer for NeuronaBox are the same as that of
${\mathcal{N}}$. This observation allow NeuronaBox to potentially scale to a
large number of nodes. A complete exploration of the scalability of NeuronaBox
is left for future work.

In the remainder of this section, we detail the design and implementation of
our proposed approach, NeuronaBox. Since we aim to demonstrate feasibility
through a proof-of-concept, we focus on a single real node, denoted by
$N_{0}$. That is, ${\mathcal{N}}=\\{N_{0}\\}$.

Figure 2. Overall workflow and architecture of NeuronaBox.

###  2.1. Initialization

Before we describe how NeuronaBox behaves during training, we first need to
initialize the emulator. This requires setting up the environment, including
the network topology and the communication model.

Topology detection. This step involves establishing the connection between any
pair of nodes, and finding the optimal data paths between all node pairs. It
is normally bootstrapped by the collective communication library itself.
During this process, each node builds up its own local topology graph (how HW
accelerators are connected via NVLink, PCIe and NICs), then exchanges its
local graph and, together with other nodes, builds the global graph. In
NeuronaBox, the emulator fakes the local graph of emulated nodes based on the
job configuration input. Then, it emulates multiple end points (the
virtualized job nodes) so that nodes in ${\mathcal{N}}$ can communicate with
them (directly via RDMA).

Delay calculation. Based on the global topology, NeuronaBox calculates the
communication and computation delays within the emulated environment. In our
design, we provide an interface so that the calculation itself is done within
a user-defined add-on plugin. For example, the delay in a ring all-reduce call
can be estimated simply by using the classical all-reduce delay model (Thakur
et al., 2005), or by using a packet-level simulator. In the future we seek to
leverage the network simulation components of DNN simulators (Ardalani et al.,
2024; Won et al., 2023; Bang et al., 2023).

###  2.2. Emulation in a Uniform Scenario

Figure 3. An example DAG for four-node ring all-reduce. The upper left squares
shows the net result of all-reduce, where color-coded data from different
nodes are reduced and then gathered at each node. The upper right figure shows
the dependency DAG for ${\mathcal{N}}$ ($N_{0}$). The lower figure shows how
we merge the dependency DAG of $N_{1},N_{2},N_{3}$ into ${\mathcal{E}}$. The
cross-node dependencies from $send(x)$ to $recv(x)$ are not shown for clarity
sake. We only show the initial 4 steps of all-reduce for simplicity.

In general, a collective operation (e.g., ring all-reduce) can be split into a
number of messages with dependencies. The emulator must send/receive messages
in a way that takes into account both the dependency and the internal protocol
of the collective operations library (in our case, NCCL). We first describe
how we treat a single collective operation and then generalize to multiple
asynchronous collective operations.

Single collective operation. Recall that we only need to consider the
interaction between ${\mathcal{N}}$ and ${\mathcal{E}}$. This means that we
can omit the dependencies for communication within ${\mathcal{E}}$. The
workflow of a collective operation can be represented as a directed acyclic
graph (DAG) where vertices are send or recv tasks and edges are the data
dependencies. Thus, we note that in NeuronaBox, this DAG can be greatly
simplified. Fig. 3 shows an example for ring all-reduce.222The all-reduce
operation performs reduction on data (i.e., sums) across nodes and stores the
result in a buffer at every node. We use different color for data in different
worker. It is worth noting that the DAGs for ${\mathcal{N}}$ and NeuronaBox
are isomorphic. As a result, with every message received from ${\mathcal{N}}$
to ${\mathcal{E}}$, we can always determine the correct state in order to
generate the next message of the collective operation workflow.

To achieve this, ${\mathcal{E}}$ maintains a bitmap of the messages that have
been sent to or received from ${\mathcal{N}}$, and it applies the following
two actions (${\mathcal{E}}$ polls these using background threads) that
advance the state of the DAG ensuring synchronization correctness:

1) Try Send To ${\mathcal{N}}$. A message can be sent if and only if all its
predecessors have been sent or received in the DAG. If the next unsent message
in the bitmap fulfils this condition, we update the bitmap and send the
message.

2) Try Receive From ${\mathcal{N}}$. Upon receiving a message from
${\mathcal{N}}$, ${\mathcal{E}}$ checks whether it is the expected message for
the current operation. If this is the case, the bitmap of the record is
updated; otherwise, an error is reported.

Multiple async collective operations. The design of a single collective
operation can easily be extended to support multiple operations by assigning a
unique ID to each operation and maintaining its information in a logically
centralized controller. We record the mapping of operations to their message
bitmaps. We ensure fairness between the individual streams through round-robin
polling. Note that the method for single operation is asynchronous by nature,
as the functions are polled by background threads. Given that, the
synchronization is achieved by busy-waiting.

###  2.3. Extension to a Non-uniform Scenario

The workload of individual nodes in a training job may not always be balanced.
This is the case, for example, when model parallelism fails to achieve a
balanced workload distribution, or when there is heterogeneity of hardware and
topology. Consequently, emulating the behavior of an arbitrary node subset
(${\mathcal{N}}$) may not adequately represent the behavior of the entire
workload. To overcome this challenge, we propose to classify each node in the
job based on the part of the model it contains, e.g., like having different
stages in model parallelism. We then ensure that one node in each class is in
${\mathcal{N}}$. This approach allows us to infer the behavior of the workload
by observing the collective behavior of each class of nodes. This approach
also solves the heterogeneity of hardware and topology when we classify nodes
with different hardware into different classes.

However, we note that this approach requires more resources. Suppose there are
$m$ classes; in the basic solution, we need to have one representative real
node for each of them. And with $t$ hardware types, we then need $tm$ nodes in
${\mathcal{N}}$. We conjecture that it may be possible to reduce the number of
nodes in ${\mathcal{N}}$, say to $k$, by decoupling the emulation between
different nodes. Assuming nodes in ${\mathcal{N}}$ are in different classes,
if all the communication is interposed by ${\mathcal{E}}$, then we can time-
multiplex the class-based workload and assign each node $\frac{m}{k}$ amount
of load. We leave the exploration of these techniques for future work.

Size | AllreduceB | AllreduceE | AllgatherB | AllgatherE
---|---|---|---|---
1KB | 435.2us | 418.8us | 282.6us | 276.2us
4KB | 526.5us | 511.0us | 306.5us | 300.2us
32KB | 564.9us | 552.3us | 329.0us | 322.6us
256KB | 1326.0us | 1314.0us | 868.9us | 859.6us
2MB | 7661us | 7655us | 4928us | 4929us
16MB | 59.0ms | 58.9ms | 37.5ms | 37.5ms
128MB | 470ms | 469ms | 298ms | 298ms
1GB | 3760ms | 3760ms | 2408ms | 2407ms

Table 1. Average run time per call. B for baseline and E for emulator
(NeuronaBox). NeuronaBox only incurs at most 4%/2% extra time for all-reduce
and all-gather, respectively.

###  2.4. Proof-of-concept Implementation

Our proof-of-concept implementation entails the development of an end-to-end
system using the PyTorch DNN framework and NCCL as the collective
communication library, chosen because of their popularity.

Our implementation is able to run a two-node training using a distributed
data-parallel strategy. In particular, we modify NCCL’s instance in
${\mathcal{E}}$ to emulate the collective operations as per § 2.2. Moreover,
in ${\mathcal{E}}$ we skip the cudaKernelLaunch completely so that no GPU
computations are involved. We also modify the NCCL proxy so that it sends
dummy data in compliance with the internal protocol so that the workload
continues to run and ${\mathcal{N}}$ is not aware of the emulation. In
PyTorch, we mainly alter the autogard and c10d to implement the
synchronization that previously relies on a CUDA kernel now compatible with
the emulator. We also remove computation in backward pass and model weight
update in ${\mathcal{E}}$, given that those computations are redundant in
emulation.

The whole system is about 2000 LoC in CUDA C++ and 50 LoC in Python, exclusive
of experiments and tests. We plan to release NeuronaBox as open source.

##  3\. Preliminary Experiments

We evaluate our prototype NeuronaBox implementation by ($1$) running
microbenchmarks in NCCL level to see the pure performance of collective
communication, ($2$) running an end-to-end system in PyTorch to see the
accuracy of emulation, as well as measuring CPU utilization to evaluate the
overheads of NeuronaBox. We also demonstrate ($3$) an application scenario of
NeuronaBox by performing a “what-if” analysis with latency variations.

Testbed. Our test environment consists of two nodes, each equipped with two
8-core Intel Xeon Silver 4112 CPUs running at 2.60 GHz, 512 GB RAM and is
fitted with a 100 GbE Mellanox ConnectX-5 NIC. In addition, each node contains
two NVIDIA V100 GPUs, although only one is used during evaluation. Each node
runs Ubuntu 22.04 (Linux kernel 5.15.0), CUDA 12.2, PyTorch 2.2.0a0 and NCCL
2.19.4.

If not otherwise stated, we call the two nodes ${\mathcal{N}}=\\{N_{0}\\}$ and
$\mathcal{E}=\\{N_{emu}\\}$. $N_{0}$ always runs the unmodified code.
$N_{emu}$ is configured to run either NeuronaBox’s modified code(as emulator),
or unmodified modified code (as a baseline).

###  3.1. Microbenchmark

Setup. First we assess NeuronaBox’s capability to emulate collective
communication operations. We devise the benchmark by generating input data
tensors of different sizes on GPU and issuing two-node collective operations.
We test ncclAllreduce and ncclAllgather. After warm-up, we measure the time
taken over at least 100 repetitions for each call on $N_{emu}$ and report the
average. $N_{0}$ always runs unmodified code. We compare the result when
$N_{emu}$ is running unmodified NCCL (baseline) and NeuronaBox’s NCCL
(emulator).

Results. Table 1 shows that NeuronaBox only incurs at most 4% overhead; we
attribute this to the mutex lock on the controller and bitmap bookkeeping. The
overhead diminishes as the size increases; when the size is greater than 2MB,
the gap is no more than 1%. Since most data parallel implementations use
buckets to batch all-reduce calls to a larger size (e.g., 25MB in NVIDIA APEX
(NVIDIA, 2024a)), we believe this NCCL-level overhead of NeuronaBox is
acceptable.

###  3.2. End-to-end Training Emulation

Setup. To evaluate NeuronaBox’s ability to accurately emulate end-to-end DNN
training, we conducted experiments using three real-world DNN models,
including computer vision, natural language processing and recommendation
systems. The models details are listed in Table 3. We use PyTorch’s
DistributedDataParallel module for data parallelism. $N_{0}$ runs unmodified
PyTorch; $N_{emu}$ runs NeuronaBox’s PyTorch as emulator and unmodified
PyTorch as baseline.

We measure the metrics and report the average after warm-up. We report
training time per iteration for BERT and ResNet; we report training time per
epoch for DeepLight because it involves model pruning and has variance in
between iterations. We also measure the CPU usage in NeuronaBox to illustrate
the overhead of the emulation.

Model | Task | Dataset | Size
---|---|---|---
BERT (Devlin et al., 2019) | Question Answer | SQuAD (Rajpurkar et al., 2018) | 1.28GB
ResNet152 (He et al., 2016) | Image Classify | ImageNet-1K (Russakovsky et al., 2015) | 230MB
DeepLight (Deng et al., 2021) | Click Predict | Criteo 1TB (Microsoft, 2015) | 2.26GB

Table 2. Characteristics of benchmark DDN models, size represents the total
parameter size of a model.

Model | Time-E | Time-B | CPU-E | CPU-B
---|---|---|---|---
BERT | 629 $\pm$ 3.0 | 628$\pm$1.1 | 12.93% | 14.25%
ResNet152 | 1061$\pm$19.8 | 1063$\pm$16.3 | 12.68% | 12.95%
DeepLight | 727$\pm$15.0 | 726$\pm$ 13.8 | 7.52% | 7.75%

Table 3. End-to-end workload comparison. ‘E’ and ‘B’ stand for emulator-
enabled (NeuronaBox) and the baseline, respectively. ‘Time’ stands for the
training times in milliseconds; and ‘CPU’ stands for the percentage of CPU
usage in a node.

Results. As shown in Table 3, NeuronaBox is quite accurate in a two-node
environment training with data parallelism, with error less than 1%. For CPU
usage, it actually drops a little bit in all scenario. We attribute that to:
($1$) the efficient and lightweight implementation of NeuronaBox, which keeps
the overhead generally low; ($2$) the removal of computation in backward pass,
which eliminates a lot of memory allocation and data movements. So the net
effect is a drop in CPU usage. This is promising in terms of the potential
scalability of NeuronaBox.

###  3.3. What-if Analysis: Latency

Setup. In this experiment, $N_{0}$ runs unmodified code and $N_{emu}$ runs
NeuronaBox. We inject additional delay in each all-reduce call in $N_{emu}$
and train a BERT model. We measure the emulated training time per iteration
for each delay.

Results. As Fig. 4 shows, the iteration time increases linearly with the delay
larger than 2 milliseconds. However, when the delay is small, the overheads
reflected in the end-to-end performance does not grow linearly. We consider
this “smooth slope” as a result of the computation-communication overlap
during the training. The delay injected in each all-reduce call is partly
shadowed by the async computation in the backward pass. Such observation
implies a possible space of improvement in the training, as there is a ”2ms”
space for more communication to happen. This is an example of the kind of
insights that can be obtained from using NeuronaBox.

Figure 4. The end-to-end training time per iteration in BERT model (ms) vs the
additional delay injected in every all reduce call (ms). Error bar is plotted
in black.

##  4\. Related work

DDL simulation. A number of simulators have been developed to study the
behavior of DNN clusters, including DeepFlow(Ardalani et al., 2024), Astra-sim
(Rashidi et al., 2020; Won et al., 2023), vTrain (Bang et al., 2023) and
several others (Rashidi et al., 2022; Robinson M. et al., 2022; Stanić et al.,
2023; Hestness et al., 2017). These simulators use analytical methods combined
with profiling results to make predictions, suffering from limitations
mentioned in § 1.

Network emulation. Emulation has been widely adopted in networking research
(Vahdat et al., 2002; Lantz et al., 2010). MimicNet (Zhang et al., 2021) is a
machine learning based network emulator. It exercises a similar idea by
dividing the datacenter into an “observable” cluster (${\mathcal{N}}$ in our
work) and a blackbox ($\mathcal{E}$ in our work) and it applies a machine
learning model to fit it. However, MimicNet focuses on how to train a model to
better approximate the datacenter network at scale, whereas our work focuses
on emulating end-to-end DNN training behaviors.

Goodput prediction. Currently, NeuronaBox only sends dummy data to
$\mathcal{N}$ during emulation since it only predicts the completion time for
each training iteration. However, lossy training optimization techniques like
compression and quantization (Wang et al., 2024; Lin et al., 2018) require
goodput (accuracy) to be taken into account. To support that, NeuronaBox needs
to communicate meaningful data to $\mathcal{N}$ without incurring much
overhead. One possible solution is to use a proxy model (Coleman et al., 2020)
that generates data with a similar distribution to the dataset and
intermediate results.

##  5\. Conclusion

We proposed a novel approach for estimating time-per-iteration in distributed
DNN training, focusing on executing only a part of the model along with
collective communication operations. To substantiate our proposal, we designed
the NeuronaBox emulator and implement a proof-of-concept system. Through
extensive experimentation, we demonstrated in a two-node setup that NeuronaBox
achieves high accuracy in predicting training time across a variety of DNN
models, with an error margin of less than 1% compared to actual training runs.
Finally, we encourage further research in this direction, recognizing that
many questions remain to be explored.

## References

  * (1)
  * Ardalani et al. (2024) Newsha Ardalani, Saptadeep Pal, and Puneet Gupta. 2024.  DeepFlow: A Cross-Stack Pathfinding Framework for Distributed AI Systems.  ACM Trans. Des. Autom. Electron. Syst. 29, 2 (2024).
  * Bang et al. (2023) Jehyeon Bang, Yujeong Choi, Myeongwoo Kim, Yongdeok Kim, and Minsoo Rhu. 2023.  vTrain: A Simulation Framework for Evaluating Cost-effective and Compute-optimal Large Language Model Training.  (2023).  arXiv:cs.LG/2312.12391
  * Coleman et al. (2020) Cody Coleman, Christopher Yeh, Stephen Mussmann, Baharan Mirzasoleiman, Peter Bailis, Percy Liang, Jure Leskovec, and Matei Zaharia. 2020.  Selection via Proxy: Efficient Data Selection for Deep Learning. In ICLR.
  * Deng et al. (2021) Wei Deng, Junwei Pan, Tian Zhou, Deguang Kong, Aaron Flores, and Guang Lin. 2021.  DeepLight: Deep Lightweight Feature Interactions for Accelerating CTR Predictions in Ad Serving. In WSDM.
  * Devlin et al. (2019) Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2019.  BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding. In NAACL-HLT.
  * He et al. (2016) Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. 2016.  Deep Residual Learning for Image Recognition. In CVPR.
  * Hestness et al. (2017) Joel Hestness, Sharan Narang, Newsha Ardalani, Gregory Diamos, Heewoo Jun, Hassan Kianinejad, Md Mostofa Ali Patwary, Yang Yang, and Yanqi Zhou. 2017.  Deep Learning Scaling is Predictable, Empirically.  (2017).  arXiv:cs.LG/1712.00409
  * Huang et al. (2019) Yanping Huang, Youlong Cheng, Ankur Bapna, Orhan Firat, Dehao Chen, Mia Chen, HyoukJoong Lee, Jiquan Ngiam, Quoc V Le, Yonghui Wu, and zhifeng Chen. 2019.  GPipe: Efficient Training of Giant Neural Networks using Pipeline Parallelism. In NeurIPS.
  * Hwang et al. (2023) Changho Hwang, Wei Cui, Yifan Xiong, Ziyue Yang, Ze Liu, Han Hu, Zilong Wang, Rafael Salas, Jithin Jose, Prabhat Ram, Joe Chau, Peng Cheng, Fan Yang, Mao Yang, and Yongqiang Xiong. 2023.  Tutel: Adaptive Mixture-of-Experts at Scale. In MLSys.
  * Lai et al. (2023) Fan Lai, Wei Zhang, Rui Liu, William Tsai, Xiaohan Wei, Yuxi Hu, Sabin Devkota, Jianyu Huang, Jongsoo Park, Xing Liu, Zeliang Chen, Ellie Wen, Paul Rivera, Jie You, Chun cheng Jason Chen, and Mosharaf Chowdhury. 2023.  AdaEmbed: Adaptive Embedding for Large-Scale Recommendation Models. In OSDI.
  * Lantz et al. (2010) Bob Lantz, Brandon Heller, and Nick McKeown. 2010.  A network in a laptop: rapid prototyping for software-defined networks. In HotNets.
  * Lin et al. (2018) Yujun Lin, Song Han, Huizi Mao, Yu Wang, and William J Dally. 2018.  Deep Gradient Compression: Reducing the Communication Bandwidth for Distributed Training. In ICLR.
  * Liu et al. (2019) Yinhan Liu, Myle Ott, Naman Goyal, Jingfei Du, Mandar Joshi, Danqi Chen, Omer Levy, Mike Lewis, Luke Zettlemoyer, and Veselin Stoyanov. 2019.  RoBERTa: A Robustly Optimized BERT Pretraining Approach.  (2019).  arXiv:cs.CL/1907.11692
  * Microsoft (2015) Microsoft. 2015.  Criteo’s 1TB Click Prediction Dataset.  (2015).  https://docs.microsoft.com/en-us/archive/blogs/machinelearning/now-available-on-azure-ml-criteos-1tb-click-prediction-dataset.
  * Mittal et al. (2018) Radhika Mittal, Alexander Shpiner, Aurojit Panda, Eitan Zahavi, Arvind Krishnamurthy, Sylvia Ratnasamy, and Scott Shenker. 2018.  Revisiting Network Support for RDMA. In SIGCOMM.
  * NVIDIA (2024a) NVIDIA. 2024a.  A PyTorch Extension: Tools for easy mixed precision and distributed training in Pytorch .  (2024).  https://github.com/NVIDIA/apex.
  * NVIDIA (2024b) NVIDIA. 2024b.  Collective Communication Library (NCCL).  (2024).  https://developer.nvidia.com/nccl.
  * Rajpurkar et al. (2018) Pranav Rajpurkar, Robin Jia, and Percy Liang. 2018.  Know What You Don’t Know: Unanswerable Questions for SQuAD. In ACL.
  * Rashidi et al. (2020) Saeed Rashidi, Srinivas Sridharan, Sudarshan Srinivasan, and Tushar Krishna. 2020.  ASTRA-SIM: Enabling SW/HW Co-Design Exploration for Distributed DL Training Platforms. In ISPASS.
  * Rashidi et al. (2022) Saeed Rashidi, William Won, Sudarshan Srinivasan, Srinivas Sridharan, and Tushar Krishna. 2022.  Themis: A Network Bandwidth-Aware Collective Scheduling Policy for Distributed Training of DL Models. In ISCA.
  * Robinson M. et al. (2022) Wilfredo J. Robinson M., Flavio Esposito, and Maria A. Zuluaga. 2022.  DTS: A Simulator to Estimate the Training Time of Distributed Deep Neural Networks. In MASCOTS.
  * Russakovsky et al. (2015) Olga Russakovsky, Jia Deng, Hao Su, Jonathan Krause, Sanjeev Satheesh, Sean Ma, Zhiheng Huang, Andrej Karpathy, Aditya Khosla, Michael Bernstein, Alexander C Berg, and Li Fei-Fei. 2015.  ImageNet Large Scale Visual Recognition Challenge.  International Journal of Computer Vision 115, 3 (2015).
  * Shoeybi et al. (2020) Mohammad Shoeybi, Mostofa Patwary, Raul Puri, Patrick LeGresley, Jared Casper, and Bryan Catanzaro. 2020.  Megatron-LM: Training Multi-Billion Parameter Language Models Using Model Parallelism.  (2020).  arXiv:cs.CL/1909.08053
  * Stanić et al. (2023) Aleksandar Stanić, Dylan Ashley, Oleg Serikov, Louis Kirsch, Francesco Faccio, Jürgen Schmidhuber, Thomas Hofmann, and Imanol Schlag. 2023.  The Languini Kitchen: Enabling Language Modelling Research at Different Scales of Compute.  (2023).  arXiv:cs.LG/2309.11197
  * Thakur et al. (2005) Rajeev Thakur, Rolf Rabenseifner, and William Gropp. 2005.  Optimization of Collective Communication Operations in MPICH.  Int. J. High Perform. Comput. Appl. 19, 1 (2005).
  * Touvron et al. (2023) Hugo Touvron, Thibaut Lavril, Gautier Izacard, Xavier Martinet, Marie-Anne Lachaux, Timothée Lacroix, Baptiste Rozière, Naman Goyal, Eric Hambro, Faisal Azhar, Aurelien Rodriguez, Armand Joulin, Edouard Grave, and Guillaume Lample. 2023.  LLaMA: Open and Efficient Foundation Language Models.  (2023).  arXiv:cs.CL/2302.13971
  * Vahdat et al. (2002) Amin Vahdat, Ken Yocum, Kevin Walsh, Priya Mahadevan, Dejan Kostić, Jeff Chase, and David Becker. 2002.  Scalability and Accuracy in a Large-Scale Network Emulator. In OSDI.
  * Wang et al. (2024) Guanhua Wang, Heyang Qin, Sam Ade Jacobs, Xiaoxia Wu, Connor Holmes, Zhewei Yao, Samyam Rajbhandari, Olatunji Ruwase, Feng Yan, Lei Yang, and Yuxiong He. 2024.  ZeRO++: Extremely Efficient Collective Communication for Large Model Training. In ICLR.
  * Won et al. (2023) William Won, Taekyung Heo, Saeed Rashidi, Srinivas Sridharan, Sudarshan Srinivasan, and Tushar Krishna. 2023.  ASTRA-sim2.0: Modeling Hierarchical Networks and Disaggregated Systems for Large-model Training at Scale. In ISPASS.
  * Xing et al. (2015) Eric P. Xing, Qirong Ho, Wei Dai, Jin Kyu Kim, Jinliang Wei, Seunghak Lee, Xun Zheng, Pengtao Xie, Abhimanu Kumar, and Yaoliang Yu. 2015.  Petuum: A New Platform for Distributed Machine Learning on Big Data.  IEEE Transactions on Big Data 1, 2 (2015).
  * Zhang et al. (2021) Qizhen Zhang, Kelvin K. W. Ng, Charles Kazer, Shen Yan, João Sedoc, and Vincent Liu. 2021.  MimicNet: Fast Performance Estimates for Data Center Networks with Machine Learning. In SIGCOMM.
  * Zhao et al. (2023) Yanli Zhao, Andrew Gu, Rohan Varma, Liang Luo, Chien-Chin Huang, Min Xu, Less Wright, Hamid Shojanazeri, Myle Ott, Sam Shleifer, Alban Desmaison, Can Balioglu, Pritam Damania, Bernard Nguyen, Geeta Chauhan, Yuchen Hao, Ajit Mathews, and Shen Li. 2023.  PyTorch FSDP: Experiences on Scaling Fully Sharded Data Parallel.  Proc. VLDB Endow. 16, 12 (2023).
  * Zheng et al. (2022) Lianmin Zheng, Zhuohan Li, Hao Zhang, Yonghao Zhuang, Zhifeng Chen, Yanping Huang, Yida Wang, Yuanzhong Xu, Danyang Zhuo, Eric P. Xing, Joseph E. Gonzalez, and Ion Stoica. 2022.  Alpa: Automating Inter- and Intra-Operator Parallelism for Distributed Deep Learning. In OSDI.


11institutetext: University of Innsbruck, Technikerstrasse 21a 6020 Innsbruck,
Austria 11email<EMAIL_ADDRESS>
# Duplicate Detection as a Service

Juliette Opdenplatz 11 Umutcan Şimşek 11 Dieter Fensel 11

###### Abstract

Completeness of a knowledge graph is an important quality dimension and factor
on how well an application that makes use of it performs. Completeness can be
improved by performing knowledge enrichment. Duplicate detection aims to find
identity links between the instances of knowledge graphs and is a fundamental
subtask of knowledge enrichment. Current solutions to the problem require
expert knowledge of the tool and the knowledge graph they are applied to.
Users might not have this expert knowledge. We present our service-based
approach to the duplicate detection task that provides an easy-to-use no-code
solution that is still competitive with the state-of-the-art and has recently
been adopted in an industrial context. The evaluation will be based on several
frequently used test scenarios.

###### Keywords:

duplicate detection entity resolution entity matching knowledge graphs

##  1 Introduction

The Knowledge Graph (KG) lifetime contains a cycle of maintenance which is
called KG curation [4]. This cycle consists of an assessment, an enrichment,
and a cleaning step. Knowledge enrichment (KE) tasks aim to identify missing
statements in KGs. A special case of KE tasks is called duplicate detection
(DD) and is about finding instances within KGs that describe the same object
of discourse. Solutions to this task have multiple use cases in various fields
like linking medical records [9] or applications in plagiarism detection [2].

The fact that DD is such a prevalent task across multiple domains, indicates
that there is a need for easy-to-use DD tools. Such tools should be operable
by non-expert users. Creating a configuration for a badly documented tool or
the manual creation of training datasets are usually extremely tedious tasks
at best. Simplification of such processes can be achieved by task automation
that abstracts away the parts that require knowledge and time investment from
users.

Our approach, Duplicate Detection as a Service (DDaaS) aims to provide a
solution to the DD task that does not require any expert knowledge of its
users. It utilizes the schema of a KG automate all the behind-the-scene
processes and almost all processes that are usually left to the user. An
active learning approach is applied to train DDaaS for a KG. The training
process requires user to make yes/no decisions about proposed duplicates. This
is the only action that is really required to be done by the user. A
demonstration is provided111https://ddaas.sti2.at.

The remainder of this paper is structured as follows: Section 2 discusses the
approach DDaaS implements. This implementation is described in Section 3. The
state-of-the art to this paper is then presented in more detail in Section 4.
In Section 5, we conclude the paper and explain our plans for the future of
DDaaS.

##  2 Approach

In this Section, we give an overview on the approach that DDaaS implements. We
divide the approach in three different phases: (1) A pre-processing phase that
is a prerequisite to performing DD. This is described in Section 2.1. (2) The
DD phase which is described in Section 2.2. (3) The active learning phase
which is built on-top of the output of the DD phase. A detailed overview, is
given in Section 2.3. These phases consist of sub-phases as depicted in Figure
1.

Figure 1: Overview of the DD process, active learning, and all necessary
configurations.

As displayed, there are different parameters to each sub-phase. In the
following we give an explanation of these parameters for each sub-phase in the
respective section. This explanation also consists of a description of an
estimate of possible values, which we call the solution space to give an
overview of the complexity.

###  2.1 Pre-processing

The pre-processing phase is composed of two different sub-phases (1) schema
matching which aims to make different KGs comparable and (2) indexing which
enables fast access to the relevant instances of the KGs. These sub-phases are
further described in this section.

####  2.1.1 Schema Matching

Schema matching is the task of aligning KGs by mapping them to a common
schema. It is worth noting, that only a mapping between types and the
properties of interest is required. This common schema allows for DDaaS to
determine what instances and what properties are comparable. As DDaaS does not
provide any schema matching capabilities, there are no parameters for this
sub-phase.

####  2.1.2 Indexing

In this sub-phase, instances and property-values of interest are stored in an
index. An index stores instances of a single type of the KG in a special data
structure that allows for quick access and search of instances. DDaaS stores
property-values up to a specified depth following an instances’ property
paths. Structures like inverted indices are used for text indexing and BKD-
trees [10] are used for indexing numerical values. The capability to search
for instances quickly is crucial for run-time reasons. The parameters of this
pre-processing sub-phase are dependent on technologies used and therefore, we
refer to Section 3.2 where we explain how the indexing is implemented.

###  2.2 Duplicate Detection

The DD phase is composed of four different sub-phases which loosely follow a
commonly used process model that was previously described by Baxter et al.
[1]. We have four sub-phases: (1) Pre-filtering which builds on top of the
indexing phase, (2) property-value standardization which aims to make values
more comparable, (3) instance comparison where instances are compared
property-value by property-value, and (4) decision model application where we
decide whether an instance comparison results in a proposed duplicate.

####  2.2.1 Pre-filtering

This sub-process intends to find candidate duplicates for each instance of a
KG in another or the same KG. It does so by iterating over all instances of
one index (source) and pulling candidate duplicates from another specified
index (target) using a set of properties/property paths from the common schema
and a percentage value that declares the amount of terms that have to match
between two instances’ property-values. These requirements form the parameters
to the pre-filtering phase:

  1. 1.

Property Selection: A solution is a non-empty subset of properties from the
common schema. The solution space is the set of all these subsets.

  2. 2.

Threshold: A solution is a number in the range $[0,100]\in\mathbb{N}$. This
range is the solution space.

The result of this phase is used for a more detailed comparison.

####  2.2.2 Property-value Standardization

Standardization of property-values of a KG transforms these values into a
uniform format. This makes their comparison more consistent. For example,
string values might be more comparable when they are consistently represented
in lowercase format or numbers might be more comparable when they use the same
amount of decimals. We differentiate between multi-value and single-value
standardization. Multi-value properties are standardized on two different
levels: (1) The list level and (2) the element level. Elements are
standardized before the list level standardization is applied in order to make
the list level standardization more efficient. The standardization phase is
configured by listing all the standardization functions that shall be applied
to each property. This leads to the following parameters:

  1. 1.

Property Selection: A solution is a non-empty subset of properties in the
common schema. The solution space is the set of all these subsets. This makes
the problem equivalent to Pre-filtering Property Selection which indicates re-
usability of methods.

  2. 2.

Standardization Functions: A solution is a mapping of the subset of properties
from the common schema to a sequence of standardization functions. There are
two problems with this: (1) Each sequence is potentially unlimited in size as
we can theoretically apply an unlimited amount of standardization functions.
(2) Some of these functions are parameterized with an unclear or infinite
range. As a result we can not provide a limited solution space.

After the standardization phase, the standardized instances are passed to the
instance comparison phase.

####  2.2.3 Instance Comparison

The instance similarity is computed by taking the weighted average similarity
of two instances’ property-values. For this to work we need to define measures
to determine the similarity of two property-values. This can be a tricky
matter as have to differentiate multiple cases depending on the range(s) of a
property:

  1. 1.

Literal to literal: Property-value similarity measures take as input two
property-values $a$ and $b$, their output has to be in the range of $[0,1]$
where values close to $0$ indicate low similarity and values close to $1$ a
higher similarity. Examples for such a measure include the good old
levenshtein similarity for string values, the ratio for number values, or a
measure that checks whether two boolean values are the same.

  2. 2.

Instance to literal: Property-values that can be represented by literals and
instances usually provide the same information in both forms. For the instance
form, the information is likely distributed across multiple properties. To
make these comparable, we indexed whole property paths for an instance to make
them comparable with the functions for literal to literal comparison.

  3. 3.

Instance to instance: We have multiple options for this type of comparison:
(1) Comparison of the URIs that are used to identify the instances. (2) Direct
value comparison of the stored property paths and treating them just like
direct property-values. (3) Individual comparison of their properties, and
aggregation of their similarities. Options (1) and (2) make this type of
comparison a literal to literal comparison while option (3) is the most
sophisticated way of comparing instances but also requires the most effort in
run-time, configuring, and understanding.

In addition to the distinction of literal values and instance identifiers, a
differentiation has to be made between single- and multi-value comparisons.
For those, we first compute similarities between the elements of the lists and
aggregate the resulting similarity scores. This aggregation can consist of
simply taking the highest, average, or lowest similarity for all possible
comparisons between two lists of property-values. Since we give weights to
each property and property path, we have the following parameters:

  1. 1.

Property Selection: A solution is a non-empty subset of properties in the
common schema. The solution space is the set of all these subsets.

  2. 2.

Comparison Functions: A solution is a mapping of the property selection. The
solution space for comparison measures is every possible mapping.

  3. 3.

Weights: A solution is a mapping of the property selection to
$[0,1]\in\mathbb{R}$ limited to two decimals. The solution space is every
possible mapping.

As a result of the instance comparison phase, each pair of instance and
candidate duplicate is assigned a similarity value.

####  2.2.4 Decision Model

During the decision phase, the instance pairs are filtered by applying a
similarity threshold $t\in[0,1]$. This decision threshold is the only
parameter to the decision model. A solution is a number in the range
$[0,1]\in\mathbb{R}$ limited to two decimals. This range is the solution
space. Every instance pair above this threshold is a proposed duplicate. This
finalizes the DD phase.

###  2.3 Active Learning

The active learning phase utilizes the resulting proposed duplicates of the DD
phase. It contains three sub-phases which are described in this section: (1)
user-based labelling, (2) result analysis, and (3) search heuristics
application.

####  2.3.1 User-based Labelling

A learning process requires a training dataset. Such a training dataset
consists of instance pairs and a label that declares a pair as duplicate
(true) or non-duplicate (false). Use-cases usually do not have such a dataset
in advance. The user is required to label the partial result of a DD phase.
This phase does not have any parameters.

####  2.3.2 Result Analysis

To determine whether a configuration is better than another, we provide three
well-known measures to optimize for: (1) Recall, (2) Precision, and (3)
F1-measure. These measures are used as a configurable parameter for the
learning process. We specify a primary parameter, that declares what measure
shall be mainly optimized for. If this value is equal for two setups, we
optimize for the secondary parameter. In order to perform such a result
analysis, apart from the quality measures, a training dataset is required. The
result consists of the quality measures described above.

####  2.3.3 Search Heuristics

Now that the quality of a DD result can be quantified, different setups can be
compared. It also enables the use of search heuristics to find better setups
by iteratively changing the value of DD parameters. Such heuristics include
Forward Selection, Backward Elimination, Hill-Climbing, and Genetic
Algorithms.

For each DD parameter, there is also a brute force option which is viable if
the solution space for that DD parameter is small enough. Forward selection
for property selections works by measuring the results for each property in
isolation, the properties are sorted by quality of result, and incrementally
added to the configuration until the configuration starts to get worse. For
the property comparison configuration this means the outvoted properties’
weights are set to $0$. Backward elimination works the other way around, each
property is evaluated in isolation and the worst properties are incrementally
ruled out. Hill-climbing algorithms work by step-wise increase/decrease
(depending on where the result gets better) of the numerical value of the
percentage, threshold, or weight parameters. Genetic algorithms are used to
randomly change comparison and standardization functions for a property. The
order and amount of times each of these algorithms is applied, is
configurable. This is called the search strategy which is the parameter to the
search heuristic application sub-phase.

Since the strategy is a sequence of search heuristic applications, each of
which includes running the DD phase once, the execution of a strategy is not
interrupted by user-based labelling. Only after the strategy is completed, the
user is prompted to label results again.

##  3 Implementation and Running Example

Since the goal of DDaaS is to provide a user-friendly and accessible approach
to DD, lots of automation has to be performed. To showcase the implementation
and automation of phases, we provide a running example as per Figure 2.

Figure 2: Running example for two instances of the schema:Event type.

To achieve automation, means to set parameters to the approach as automated as
possible. To do so, DDaaS makes use of the schema that is provided by a KG. In
this Section we discuss the implementation details to the presented approach
with a special focus on how most phases are automated.

In the following, we compare two instances of type schema:Event. Both are
based on the same domain specification (see compliesWith property).
Additionally, they both contain values for a name, description, and address
which is differently structured for each instance. The left entity also has
multiple values for the name property whereas the one on the right only has
one value for the same property. These graphs are stored in a
GraphDB222https://www.ontotext.com/products/graphdb/ triple store.

A more detailed description of each phase’s implementation is provided in this
section. Section 3.1 highlights the importance of structural KG information
for automation in DDaaS. In Sections 3.2 and 3.3 it is described how the
indexing is automated and how candidate pairs are generated by utilizing these
indices. We give an overview of the DD phase implementation in Section 3.4.

###  3.1 Schema Information Extraction

Large parts of the automation of processes can be attributed to the
information that the schema of a KG provides. DDaaS currently implements
extraction of schema information for process automation in two different ways:
(1) From SHACL-based domain specifications [4, 12] which usually comes with
the graph itself in form of a URI to the SHACL-formatted resource. The domain-
specifications are patterns of extended subsets of schema.org to facilitate
knowledge creation. Local properties and their constraints are defined on
schema.org types and its extensions [11]. (2) From emergent schemata [6] where
the schema information is inferred directly from the statements of the KG by
using SPARQL queries. Either way the following information is gathered: (1)
Types and respective property paths, (2) Property cardinalities, and (3)
Literal Datatypes.

We exploit knowledge about the XML schema datatypes
(XSD)333https://www.w3.org/TR/xmlschema-2/#built-in-datatypes of a KG. XSDs
are usually the go-to-datatypes for literals in KGs. For instance, lots of
these XSDs are categorized as dd:String, like xsd:string or xsd:anyURI. A
likewise mapping is done for number and boolean types.

This list can be extended in case a KG uses other labels. There is also a loss
of granularity by mapping all the time-related XSD merely to the dd:String
type. The gathered information, independent of whether it came from a DS or
the emergent schema, is stored in an internal minimal domain specification
which is used to generate all kinds default configurations.

###  3.2 Indexing

During the indexing phase, instances stored in the triple store are indexed in
an Elasticsearch444https://www.elastic.co/elastic-stack/ cluster. The
instances are stored in a flat JSON-like document format. Conveniently, in its
enterprise edition, GraphDB comes with a dedicated connector functionality
that automates the indexing process and keeps the created index up-to-date.
Such a GraphDB to Elasticsearch Connector
(GEC)555https://graphdb.ontotext.com/documentation/enterprise/elasticsearch-
graphdb-connector.html can be configured using the Workbench or a SPARQL
query. We create one index per type in the KG which means that there is a GEC
generated for each type.

####  3.2.1 Running Example.

In case of our running example, we create a GEC for the internal minimal
domain specification that was obtained in SHACL format by following the URI
value of the compliesWith property. Any property that has another non-literal
type as range, maps the property paths as fields to the index as follows:
schema:address simply becomes address and the property path
schema:address/schema:postalCode is mapped to a field called
address.postalCode. Additionally, one can specify whether a property is a
multi-value property to the GEC, and therefore, enforce the values of this
field to be stored into an array. This information is also taken from the
domain specification. In our running example this is the case for the name
property. This process is repeated for the specified property path depth. The
default depth is set to $1$ which results in an index where only a second
layer is added to the index. A default depth is applied since we can not rule
out that the graph does not contain cycles, and we end up with an infinitely
large configuration. The resulting generated GEC is uploaded via the GraphDB’s
SPARQL endpoint.

After the process is finished, we end up with indexed instances, which to the
outside are represented by a flat JSON document that lists instances’ property
paths and their values.

###  3.3 Pre-filtering

The pre-filtering approach is based on so called more_like_this
(MLT)666https://www.elastic.co/guide/en/elasticsearch/reference/current/query-
dsl-mlt-query.html queries which finds instances that look similar to a sample
instance with respect to the following parameters: (1) property selection and
(2) threshold. For (1), we simply utilize every available indexed property
(path). The source index provides the samples which are requested via a query
that returns all stores instances, these instances are used as the sample for
the MLT query.

####  3.3.1 Running Example.

The resulting default property selection for the running example looks like:
[address, address.postalCode, ...] and includes every possible property
(path). We also specify an arbitrary default value of $40$% for (2). Iterating
over the source index’s instances and taking them as samples for the MLT query
the resulting query is then sent to the respective Elasticsearch endpoint
which returns a list of candidate duplicate instances from the target index.
So, the pre-filtering step would recognize for dzt-entity:1234 that a similar
instance called dzt-entity:5678 exists and return that.

###  3.4 Instance Standardization, Comparison, and Decision Model

The parameters for instance standardization, comparison, and decision model
form a DD configuration. Standardization and comparison functions are
applicable only to values of certain literal datatypes. To generate defaults
for a property, we apply default functions depending on their literal
datatype.

####  3.4.1 Running Example.

We apply the lowercase standardizer on each value for the name property and
compare each value of one instance to each value of the other instance and
choose the highest similarity as the similarity score for this property. The
description property results in a simple string comparison. A little more
complicated is the comparison of both address values as they differ in
structure for the running example. In such cases, we serialize the values of
the property paths into a single string as needed during the DD process and
compare those values. Whether a value is an instance or not is determined by
checking the property paths’ fields. If they are empty, the property-value is
a literal, if they are not empty the property value is an instance, and they
are serialized. The result is a simple string comparison as if both were
literals. If both property-values are instances, we simply compare each
property path individually. For the weights we simply assign a value of $1$ to
each property since it is hard to determine their importance automatically.
The threshold value is initially arbitrarily set to $0.75$.

Using this configuration, we compare the instances dzt-entity:1234 and dzt-
entity:5678 in more detail. We compare the multi-value property name which for
both instances contains only one value due to the application of the setify
standardizer. By default we select the most similar pair of property-values,
which is now trivial. The elements are compared using levenshtein which is the
default comparator for string typed values. For the description property, we
have a simple string comparison. In case of the address property of dzt-
entity:1234 we see that the sub-properties are populated, whereas for the
other instance they are not. Thus, we serialize the sub-properties of the
source entities into a single string which is then compared to the other
address as a simple string comparison. The compliesWith property is ignored.
The result of this comparison is a list of similarities. Due to the default
weights being $1$ for each property, we take simply the average similarity and
check with the similarity threshold whether the two instances can be
considered duplicates.

###  3.5 Active Learning

The training dataset for an index pair is stored in a
MongoDB777https://www.mongodb.com/ database and consists on the pair of URIs
of two instances and a boolean property that indicates whether the instances
are duplicates. When there was not already any training data provided for the
index pair, we run the duplicate detection process on the automatically
generated default configurations as per Sections 3.3 and 3.4 and set the
decision model threshold very low. The search strategy is applied as explained
in Section 2.3, where we use the newly created training data to analyze the
results. During this search phase, the user-based labelling is skipped until
the whole strategy was applied. After the whole strategy was applied, the user
is prompted to label new pairs, which were not yet labelled. Whether a pair
was already labelled is simply looked up in the database.

####  3.5.1 Running Example.

If our running example was part of a completely new DD process, there might
not have been a training dataset, therefore the result of the comparison of
our two instances would have been prompted to the user for validation sooner
or later (depending on other examples in the same KG).

Depending on the outcome of other possible comparisons, the result analysis
might result in a more or less bad result. The search heuristic strategy would
be applied and iteratively mutate one parameter at a time for the DD phase
until the whole strategy was applied. Then the cycle of labelling, analysis,
and search would continue until the result is satisfying for the use-case.

##  4 Related Work

We discuss and compare the presented approach to the state-of-the-art in the
DD field. This section is limited to approaches that are specifically designed
for KGs. We compare following tools:

  1. 1.

Duke888https://github.com/larsga/Duke [5] is a tool that is not primarily
aimed to DD for KGs, therefore it supports JDBC databases and file formats
like CSV and JSON. The approach is very similar to ours, and also includes
active learning capabilities. However, it requires to do the configuration
manually which includes the connection to the database, the individual
parameters for each property. These require detailed knowledge on about every
aspect of the data. It also lacks the capability to properly compare multi-
value properties. Even though it is capable to compare property paths, the
functionality does not work in a flexible manner.

  2. 2.

SILK999https://github.com/silk-framework/silk [13] does not only focus on
detecting identity links but also other types of RDF links and works in use-
cases where different and inconsistent vocabularies are being used. It comes
with a flexible language which is utilized to configure DD processes. Users
have to specify multiple different things that refer to implementation details
like SPARQL endpoints, whether it should cache instances, output files, and
page sizes for example. Users have to specify property paths themselves. Even
though it is very flexible, it does not seem to differentiate between
property-values for a property that are of different types. The comparison
process and decision models work very similarly to our approach and even offer
more flexibility in some areas such as the pre-filtering options.

  3. 3.

LIMES101010https://github.com/dice-group/LIMES [7] is a link discovery tool
with a primary focus on large-scale and run-time requirements by implementing
a novel approach to the pre-filtering step. Other than that its approach for
the most part follows the common workflow described in Section 2. It also
provides active learning components but does not abstract away its
functionalities such that knowledge about the internals are still necessary
even though their demo version111111https://limes.demos.dice-research.org/ is
quite impressive.

  4. 4.

EAGER121212https://github.com/jonathanschuchart/eager [8] complements the
usual approach described in Section 2 by graph embeddings [3, 14]. The
decision model therefore relies on embedding vectors and attribute comparisons
as input for classification.

We summarize our findings in Table 1 where we list our main requirements for
DDaaS and for each tool evaluate whether it fulfills each requirement.

Table 1: Comparison of the state-of-the-art in DD. |  | Automation Factors | Property Comparison
---|---|---|---
Approach |  supports |  learning |  active learning |  utilizes schema |  multi-value |  property paths |  range-specific
DDaaS |  RDF |  yes |  yes |  yes |  yes |  yes |  partially
Duke |  RDF, JDBC, CSV, JSON |  yes |  yes |  no |  no |  no |  no
Silk |  RDF |  no |  no |  no |  yes |  yes |  no
LIMES |  RDF |  yes |  yes |  no |  no |  yes |  no
EAGER |  RDF |  yes |  no |  no |  no |  no |  no

According to our research, there was no other approach that fulfill all
requirements, we defined for DDaaS. Most approaches disregard the existence of
multi-value properties and focus purely on single-value properties or merely
provide an extremely simplistic method of aggregation. Another commonly
disregarded point is the existence of different ranges for a given property.
All the investigated tools will compare literals with URIs when applied on the
wrong KG131313E.g., see https://schema.org/address. For our approach we wanted
to provide a similar flexibility that KGs provide to us as this is the only
way that two KGs’ instances can be compared properly.

##  5 Conclusion & Future Work

With this paper, we presented a no-code solution to the DD task that helps
non-coders to maintain KGs that power their applications. This is of great
value for any project that aims to keep their KGs up-to-date without having to
get into the technical details of the task. Hence, we named our solution
Duplicate Detection as a Service (DDaaS). We give a final conclusion on DDaaS
in Section 5.1 and an outlook on future plans in Section 5.2.

###  5.1 Discussion

The only necessary configuration DDaaS is not capable of automating is the
necessary schema matching. More precisely the property and type mapping.
Therefore, DDaaS provides a fully automated default functionality for any KGs
that share a schema.

###  5.2 Future Work

We presented an approach that is usable by non-experts, next steps will focus
on enhancing the DD processes efficiency without increasing the expert-
knowledge that is needed to operate DDaaS. A first improvement to be made is
the setting of default weights for property-value comparison. Since we store
configurations per index pair and the respective schema, DDaaS can potentially
make use of its experience on new KGs. One big improvement to be made is the
schema matching which still has to be done completely manually. Active
learning with the help of a well-designed underlying logic could help create
those mappings at least semi-automatically. The greater vision for DDaaS is to
integrate it into a more general knowledge enrichment framework that is
capable of detecting links of any kind.

## Acknowledgements

The initial work for this project was funded by the
MindLab141414https://mindlab.ai/ project.

## References

  * [1] Baxter, R., Christen, P., Epidemiology, C.: A comparison of fast blocking methods for record linkage. Proc. of ACM SIGKDD’03 Workshop on Data Cleaning, Record Linkage, and Object Consolidation (07 2003)
  * [2] Chowdhury, H.A., Bhattacharyya, D.K.: Plagiarism: Taxonomy, tools and detection techniques. arXiv preprint arXiv:1801.06323 (2018)
  * [3] Dai, Y., Wang, S., Xiong, N.N., Guo, W.: A survey on knowledge graph embedding: Approaches, applications and benchmarks. Electronics 9(5), 750 (2020)
  * [4] Fensel, D., Şimşek, U., Angele, K., Huaman, E., Kärle, E., Panasiuk, O., Toma, I., Umbrich, J., Wahler, A.: Knowledge Graphs: Methodology, Tools and Selected Use Cases. Springer (01 2020). https://doi.org/10.1007/978-3-030-37439-6
  * [5] Garshol, L.M., Borge, A.: Hafslund Sesam - An Archive on Semantics. In: Proceedings of the 10th Extending Semantic Web Conference (ESWC2013): Semantics and Big Data, Montpellier, France, May 26-30, 2013. Lecture Notes in Computer Science, vol. 7882, pp. 578–592. Springer (2013), https://doi.org/10.1007/978-3-642-38288-8_39
  * [6] Hogan, A., Blomqvist, E., Cochez, M., d’Amato, C., Melo, G.d., Gutierrez, C., Kirrane, S., Gayo, J.E.L., Navigli, R., Neumaier, S., et al.: Knowledge graphs. Synthesis Lectures on Data, Semantics, and Knowledge 12(2), 1–257 (2021)
  * [7] Ngomo, A.N., Auer, S.: LIMES - A time-efficient approach for large-scale link discovery on the web of data. In: Proceedings of the 22nd International Joint Conference on Artificial Intelligence (IJCAI2011), Barcelona, Spain, July 16–22, 2011. pp. 2312–2317. AAAI Press (2011), https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-385
  * [8] Obraczka, D., Schuchart, J., Rahm, E.: Embedding-assisted entity resolution for knowledge graphs (2021)
  * [9] Sauleau, E.A., Paumier, J.P., Buemi, A.: Medical record linkage in health information systems by approximate string matching and clustering. BMC medical informatics and decision-making 5(1), 1–13 (2005)
  * [10] Sharma, A.: Spatial Indexing, pp. 53–61. Apress, Berkeley, CA (2020). https://doi.org/10.1007/978-1-4842-6345-7_4
  * [11] Simsek, U., Angele, K., Kärle, E., Opdenplatz, J., Sommer, D., Umbrich, J., Fensel, D.: Knowledge graph lifecycle: Building and maintaining knowledge graphs (2021)
  * [12] Şimşek, U., Kärle, E., Holzknecht, O., Fensel, D.: Domain specific semantic validation of schema. org annotations. In: International Andrei Ershov Memorial Conference on Perspectives of System Informatics. pp. 417–429. Springer (2017)
  * [13] Volz, J., Bizer, C., Gaedke, M., Kobilarov, G.: Silk-a link discovery framework for the web of data. In: Ldow (2009)
  * [14] Wang, Q., Mao, Z., Wang, B., Guo, L.: Knowledge graph embedding: A survey of approaches and applications. IEEE Transactions on Knowledge and Data Engineering 29(12), 2724–2743 (2017)