# Automatic Algorithm Selection in Multi-Agent Pathfinding

Devon Sigurdson
Vadim Bulitko
University of Alberta
dbsigurd<EMAIL_ADDRESS>&William Yeoh
Washington University in St. Louis
<EMAIL_ADDRESS>&Carlos Hernández
Universidad Andres Bello
<EMAIL_ADDRESS>&Sven Koenig
University of Southern California
<EMAIL_ADDRESS>
###### Abstract

In a multi-agent pathfinding (MAPF) problem, agents need to navigate from
their start to their goal locations without colliding into each other. There
are various MAPF algorithms, including Windowed Hierarchical Cooperative A*,
Flow Annotated Replanning, and Bounded Multi-Agent A*. It is often the case
that there is no single algorithm that dominates all MAPF instances.
Therefore, in this paper, we investigate the use of deep learning to
automatically select the best MAPF algorithm from a portfolio of algorithms
for a given MAPF problem instance. Empirical results show that our automatic
algorithm selection approach, which uses an off-the-shelf convolutional neural
network, is able to outperform any individual MAPF algorithm in our portfolio.

##  1 Introduction

Pathfinding is a common task for many applications, such as robotics,
transportation, and video games. Often, paths need to be planned for multiple
game characters, for example, when each one of several game characters needs
to move from its current location to a given goal location. Single-agent
pathfinding is a simpler problem since shortest single-agent paths can be
found optimally in polynomial time with search methods like A* (?). Multi-
agent pathfinding (MAPF) is a more complex problem because one needs to avoid
collisions among the agents. Artificial intelligence and robotics have
developed a large number of MAPF algorithms. Suboptimal complete MAPF
algorithms often implement specific movement rules for agents that guarantee
completeness and run fast since they avoid search. An example is Push and
Swap/Rotate (?; ?). Some optimal or bounded-suboptimal MAPF algorithms reduce
the MAPF problem to other combinatorial problems. Examples include reductions
to CSP (?), SAT (?), ILP (?), and ASP (?). Others are based on heuristic
search. Examples are M* (?), Conflict-Based Search (?; ?; ?) and many others.
A longer recent overview of MAPF algorithms is provided by ? (?).

While finding collision-free paths for multiple agents can be done in
polynomial time (?), in practice, these paths should also be reasonably short.
Finding collision-free paths that optimize solution quality measured as
makespan (the largest arrival time of any agent at its goal location) or
flowtime (the sum of the arrival times of all agents at their goal locations)
is NP-hard (?). In some cases, even approximating the optimal solution quality
is NP-hard (?). Unfortunately, paths with a reasonably good solution quality
often need to be found quickly (e.g., when planning paths for game characters
online). Researchers in artificial intelligence have developed a variety of
MAPF algorithms that can be used for this purpose, such as Windowed
Hierarchical A* (?), Flow Annotated Replanning (?) and Bounded Multi-agent A*
(?). To the best of our knowledge, none of the MAPF algorithms universally
dominates all others.

As a starting point of determining a good MAPF algorithm, we are primarily
interested in ensuring that all agents are successful, in the sense that they
reach their goal locations by a given deadline. Unfortunately, it has recently
been shown to be NP-hard to determine whether all agents can be successful on
arbitrary graphs (?). We thus use real-time MAPF algorithms that do not
guarantee that all agents are successful even if this is possible and evaluate
the algorithms by the number of agents that are successful. One could
experimentally determine the best MAPF algorithm over a representative set of
MAPF instances but one can do better by asking which MAPF algorithm to use
when, a question that has been studied more generally in the context of the
algorithm selection problem (?). This decision also has to be made quickly,
which suggests using classification algorithms from machine learning to define
a fast-to-calculate mapping from features of the MAPF instance to the best
performing MAPF algorithm. Consequently, the contribution of our research is
applying automated algorithm selection techniques to increase completion rate
over using a single algorithm for every problem.

##  2 Problem Formulation

An automatic algorithm selection optimization problem (?) is defined by a
tuple $\langle\mathcal{I},\mathcal{P},Q\rangle$, where
$\mathcal{I}=\\{i_{1},i_{2},\ldots\\}$ is a set of problem instances;
$\mathcal{P}=\\{p_{1},p_{2},\ldots\\}$ is a portfolio of algorithms that can
be used to solve each instance $i\in\mathcal{I}$; and
$Q:\mathcal{P}\times\mathcal{I}\rightarrow\mathbb{R}$ is a function that
returns the quality of the solution found by an algorithm $p\in\mathcal{P}$
when solving problem instance $i\in\mathcal{I}$.

A solution to this problem is a mapping
$\pi:\mathcal{I}\rightarrow\mathcal{P}$ that maps each problem instance
$i\in\mathcal{I}$ to an algorithm $p\in\mathcal{P}$. The quality of a solution
$\pi$ is the sum of the qualities of the solutions found by the algorithm
prescribed by $\pi$ for each problem instance:

$\displaystyle Q(\pi)=\sum_{i\in\mathcal{I}}Q(\pi(i),i).$ (1)

An optimal solution is one that maximizes this value:

$\displaystyle\pi^{*}=\operatornamewithlimits{argmax}_{\pi}Q(\pi).$ (2)

Our set of problem instances $\mathcal{I}$ are multi-agent pathfinding (MAPF)
problems on video game maps. We consider a portfolio $\mathcal{P}$ of MAPF
algorithms as candidate algorithms, and we consider _completion rate_ ,
defined as the number of agents that successfully reach their goals within a
time limit (?; ?), as our quality metric $Q$111We equivalently optimize the
completion rate averaged over all instances in $\mathcal{I}$ instead of the
cumulative one in Equation (1) above.. We break ties in $Q$ in favor of
algorithms that have short _distances traveled_ , defined as the sum of
distances travelled over all agents (?), followed by algorithms that have
small _goal achievement time_ , defined as the average wall-clock time it
takes for agents to reach their goal from the start of the problem (?). Goal
achievement times are recalculated when an agent returns to their goal and are
undefined if the agent is not in their goal.

##  3 MAPF Problem

We provide a description of the _multi-agent pathfinding_ (MAPF) problem that
closely follows the description by ? (?). A MAPF problem is defined by a pair
$\left(G,A\right)$, where $G=(N,E,c,h)$ is a undirected weighted graph of
nodes $N$ that are connected to each other by edges $E\subset N\times N$. The
set of edges includes self-loops, that is, $\forall n\in N:(n,n)\in E$, which
allows all agents to remain on their current node (i.e., wait). We assume that
all edge weights $c:E\to\mathbb{R}$ are strictly positive except self-loop
edges, which have a weight of $0$. The edge weights are symmetrical
$\forall(n,n^{\prime})\in E:c(n,n^{\prime})=c(n^{\prime},n)$.
$A=\\{a_{1},\ldots,a_{n}\\}$ is a set of NPC agents, where each agent
$a_{i}\in A$ is specified by a pair
$(n^{i}_{\text{start}},n^{i}_{\text{goal}})$ that indicates its start node
$n^{i}_{\text{start}}$ and its goal node $n^{i}_{\text{goal}}$. Each goal is
reachable from the start node. The graph is also safely traversable by virtue
of being undirected. An estimate of shortest travel distance between any two
nodes, the heuristic $h:N\times N\to\mathbb{R}$, is available to each agent.
We use the shorthand $h(n)$ for $h(n,n^{i}_{\text{goal}})$ if the goal is
understood in the context. An agent may modify $h$ as it sees fits but does
not share the modified version with other agents.

In our model, time advances in discrete steps. At time step $t$, each agent
$a_{i}$ occupies a node $n^{i}\in N$, also referred to as
$n_{\text{current}}^{i}$ when talking about a specific agent’s location. When
pathfinding, each agent generates a set of moves it plans to execute from its
current state. Agents provide these moves to a controller that attempts to
have the agent execute its plans one step at a time. Plans are represented as
a set of node pairs $P=\\{(n,n^{\prime})\\}$. The pairs represent agent’s
planned actions (i.e., edge traversals) meaning that when the agent is on node
$n$ it intends to go to a neighboring node $n^{\prime}$ by traversing the edge
$(n,n^{\prime})\in E$.

In the event that the agent’s plan is not executable, either because another
agent is occupying the node where it wishes to move or because the plan does
not have an action planned for the agent’s current node, the agent waits in
its current node (i.e., traverses the self loop). Agents can traverse edges
with the following restrictions: (i) two agents cannot swap locations in a
single time step and (ii) each node can be occupied by at most one agent at
any time.

As common in video game pathfinding literature, our search graphs in this
paper are based on rectangular grids with each grid cell being a single node
in the graph (?). Each grid cell has up to eight immediate neighbors. It is
connected to them via cardinal edges of cost $1$ and diagonal edges of cost
$\sqrt{2}$.

##  4 MAPF Algorithms

While researchers have proposed a number of algorithms to solve MAPF problems
(?; ?; ?), in this paper, we focus on using online methods that are better
suited for environments, where agents must take actions within a very small
amount of time(e.g., video games). Our portfolio is then comprised of three
A*-based algorithms: _Windowed Hierarchical Cooperative A*_ (WHCA*) (?), _Flow
Annotation Replanning_ (FAR) (?), and _Bounded Multi-Agent A*_ (BMAA*) (?). We
choose these algorithms because they use different strategies to solve MAPF
problems and, as a result, can excel on different MAPF problems.

###  4.1 Windowed Hierarchical Cooperative A*

? (?) proposed a family of A*-based algorithms for solving MAPF problems: In
_Cooperative A*_ , each agent runs an A* search in a three dimensional graph
($x$-coordinate, $y$-coordinate, and time) to reach its goal and shares its
plan with other agents through reservation tables. Therefore, the agents are
able to avoid collisions since each agent knows where all the other agents
will be and when they will be there. To improve scalability, _Hierarchical
Cooperative A*_ uses hierarchical search, where each agent uses the length of
the shortest path found in an abstracted state space as a guiding heuristic.
Finally, to further improve scalability, _Windowed Hierarchical Cooperative
A*_ (WHCA*) limits the search depth of each agent to within a window. Once a
partial path within the window is found, the agent follows it and searches for
the next partial path by shifting the window along the current path.

###  4.2 Flow Annotation Replanning

Like WHCA*, Flow Annotation Replanning (FAR) (?) also takes account of other
agents plans. However, instead of searching for a new path when the current
one is blocked, agents in FAR simply wait at their current nodes until they
can reserve their next set of moves in a reservation table. FAR also detects
deadlocks, where agents would wait on each other indefinitely, and forces them
to move away from their current nodes. They then must replan paths back to the
node they were forced off of before resuming their original path to their
goal.

To reduce the likelihood of agents blocking each other, FAR annotates at each
node with the direction that agents at that node should follow. These
annotations combined create “highways,” where agents can quickly move from one
end of the map to another without ever stopping to wait for other agents.
Figure 1 shows an example map annotated by FAR which uses the following
strategy: It first creates an edge-less annotated graph $G^{\prime}$ that has
the same set of nodes as the original graph $G$. Then, edges are added to
$G^{\prime}$ in alternating directions, that is, even-numbered rows are
assigned west-bound edges and odd-numbered rows are assigned east-bound edges.
Similarly, even-numbered columns are assigned north-bound edges and odd-
numbered columns are assigned south-bound edges. Additional edges are added in
special cases. For example, nodes on corridors that are only one-node wide
retain their bi-directional connectivity. Self-loops are always retained as
agents always have the ability to wait, however self-loops are not considered
in the search.

Figure 1: Example of Flow Annotations.

###  4.3 Bounded Multi-Agent A*

_Bounded Multi-Agent A*_ (BMAA*) (?) is based on a _Real-Time Adaptive A*_
(RTAA*) (?), a well-known _single-agent_ real-time heuristic search algorithm.
RTAA* runs the following procedures iteratively until the agent reaches its
goal: (1) perform a bounded-depth A* search from the agent’s current position;
(2) update the heuristic values of all nodes in the CLOSED list of that A*
search to make them more informed; and (3) move the agent along the partial
path returned by that A* search. ? (?) extended RTAA* to a _multi-agent_
setting, where other agents are treated as (moving) obstacles during the
search. Additionally, each agent is able to request other agents that are
currently located on its goal cell to vacate. The vacating agent will move to
any available neighboring node and resume its regular search procedures from
its new location.

##  5 Related Work on Algorithm Selection

Performance of planning algorithms can vary substantially based on the problem
(?). In particular, selecting a heuristic search algorithm specific to the
problem can lead to a substantial boost in performance (?; ?). The latter work
showed that the margin for performance improvement over a fixed algorithm
grows with the granularity of the selection: Selecting an algorithm per
problem instance has a better performance potential than selecting an
algorithm per group of problem instances (e.g., problem instances can be
grouped based on maps in video games). Follow-up research exploited the
potential for performance improvement through machine learning techniques by
mapping a problem instance to the best algorithm for that problem instance
(?). This work however was limited to the single agent domain and does not
provide insight in to how the method would perform in the more realistic
multi-agent environment.

Traditionally, machine learning techniques require one to intelligently define
input features in order to be successful. However, more recently, deep
learning techniques have been able to automatically extract features which
allows one to provide low-level problem descriptions. Remarkably, even mapping
ASCII codes of a textual problem description in SAT and CSP problems to grey-
scale pixel values in a square image provided sufficient for deep
convolutional neural networks (?). In pathfinding problems, the encoding can
be even simpler since the map itself is naturally represented by a two-
dimensional image (?). In this paper, we continue the recent line of work and
adapt the latter approach from single-agent to multi-agent pathfinding.

##  6 Our Approach

Before solving our algorithm selection problem defined in Section 2, there are
two key design decisions that must be made: (1) What algorithms to include in
the portfolio $\mathcal{P}$ of algorithms? (2) How should problem instances in
$\mathcal{I}$ be represented as an input to the selection algorithm?

#### Portfolio Algorithms:

Ideally, the selection of algorithms in the portfolio should be sufficiently
diverse so that for each possible problem instance, there exists at least one
algorithm in the portfolio that does well on that problem instance. Larger
portfolios, however, may slow down the learning process as well as result in
lower performance due to errors when selecting algorithms. Therefore, in this
paper, we consider a relatively small but diverse set of algorithms: Windowed
Hierarchical Cooperative A* (WHCA*), Flow Annotation Replanning (FAR), and
Bounded Multi-Agent A* (BMAA*) as described in Section 4. We choose BMAA*
because we anticipate that it will do well in problem instances where well-
informed heuristics are available. In problem instances where heuristics are
more substantially misleading, it performs poorly as it runs only bounded-
depth searches to find partial paths for the agents, which may be in the wrong
direction. Conversely, FAR computes complete paths, but has a limited gridlock
breaking procedure that can lead to failure in particularly congested
problems. Finally, we choose WHCA* as it can solve particularly tricky
problems as it communicates agents plans and takes them into account through a
windowed cooperative search. Doing so, however, is computationally expensive
and is not always necessary.

#### Input Abstraction:

Videogames will frequently have to solve MAPF problems repeatedly on the same
map. Similarities likely extend to patterns in their start and goal locations.
It may be desirable for agents to run a specific MAPF algorithm for a given
problem. In video games, especially, it is reasonable to assume that the game
engine may choose different MAPF algorithms for different games, maps, or even
problem instances. Different algorithms may be used within the same map based
on the agent’s type and priority or even the number of agents. Motivated by
this observation, we use a MAPF problem specification with both the map and
each agent’s start and goal location available.

Figure 2: Two sample MAPF problem types with start (green pixels) and goals (red pixels): tight to wide (left) and outside in (right). Table 1: Algorithm performance on all problems. | Completion Rate(%) |  | Distance |  | Goal Achievement Time (s)
---|---|---|---|---|---
$\pi^{*}$ | $80.8\pm 0.8$ |  | $283.1\pm 7.5$ |  | $15.5\pm 0.2$
$\pi$ | $76.6\pm 1.2$ |  | $261.0\pm 8.8$ |  | $16.2\pm 0.4$
BMAA* | $65.7\pm 0.7$ |  | $465.7\pm 5.9$ |  | $14.4\pm 0.2$
FAR | $66.1\pm 1.0$ |  | $405.7\pm 10.1$ |  | $15.9\pm 0.2$
WHCA* | $54.6\pm 1.1$ |  | $88.3\pm 1.7$ |  | $21.7\pm 0.2$
Worst | $44.3\pm 0.7$ |  | $328.6\pm 11.0$ |  | $19.7\pm 0.2$
Table 2: Completion rate(%) by problem type. Problem Type | BMAA* | FAR | WHCA*
---|---|---|---
Random | 79.4 | $75.3$ | $68.9$
Cross sides | $69.4$ | 83.7 | $56.4$
Swap sides | 64.4 | $48.5$ | $34.5$
Inside out | 76.7 | $75.3$ | $59.9$
Outside in | 73.3 | $72.3$ | $60.7$
Tight to tight | $33.8$ | 37.8 | $36.7$
Tight to wide | $59.2$ | 71.0 | $54.9$

#### Solution Approach:

Our solution approach is motivated by ? (?), who tackled the algorithm-
selection problem for single-agent pathfinding. Similar to their approach, we
treat the MAPF algorithm-selection problem as an image classification problem.
Thus, we classify each image (a representation of a MAPF problem instance)
using a fixed set of possible labels (algorithms from the portfolio). We use
AlexNet (?), a _Convolutional Neural Network_ (CNN), to solve the image
classification problem. We choose a deep learning approach with the
anticipation that it will be able to learn to recognize important features of
the problem (e.g., topologies of the map, distribution of agents, etc.) and
exploit them automatically (?). We choose AlexNet as it is a common, readily-
available CNN, which requires no additional engineering. AlexNet is available
with PyTorch, Cognitive Neural Tool Kit, TensorFlow, MATLAB and other deep
learning frameworks (?; ?; ?; ?). In order to provide MAPF problem instances
as inputs to the CNN, we represent each problem instance as an image, where
blocked and unblocked nodes are represented by white and black pixels,
respectively. A partial agent specification is also provided as part of the
input, represented by a single RGB pixel. A start location is indicated with a
green pixel and a goal location with a red pixel. The mapping between a
specific agent’s start and goal is anonymized as there is no distinction
between which goal belongs to which agent. We resize the image to be equal to
that of the network input ($227\times 227$ pixels) Figure 2.

Finally, to generate the dataset to train our CNN, we used publicly available
game maps (?). Their start and goals were generated as discussed below. For
each problem instance in the dataset, we ran each algorithm in our portfolio
to determine the best algorithm (i.e., the correct image label) as defined in
Section 2.

##  7 MAPF Problem Generation

Rather than using only randomly selected start and goals, we generated
different types of MAPF problems. We ensure that start and goals are connected
for all the problems generated. These problem types are intended to represent
some common video game scenarios. For example, agents _swapping sides_ is
commonly seen in many strategy games where agents are trying to reach an
opposing team’s base. _Tight to wide_ happens when there is a common spawn
location and some general area that the agents are trying to reach. These are
not intended to represent all scenarios that occur in games but rather provide
a more diverse set of MAPF problem types that may commonly occur in games
instead of relying on only a single problem type.

  * •

_Random:_ agents are assigned random start and goals.

  * •

_Cross sides:_ all agents begin on one side (i.e., left, right, top, or
bottom) and must traverse to the other side.

  * •

_Swap sides:_ half the agents start on one side (i.e., left) while the other
half start on the opposite side. Their goals are randomly selected in a region
on the side opposite of their starting location.

  * •

_Inside out:_ all agents start near the center of the map and are assigned
goals near the outer edges of the map.

  * •

_Outside in:_ all agents begin near the outer edges of the map and are
assigned goals near the center of the map(Figure 2).

  * •

_Tight to tight:_ all agents start as close together as possible and are
assigned goals that are as close as possible elsewhere on the map.

  * •

_Tight to wide:_ all agents start as close together as possible and are
assigned goals that are spread out in the same general area of the map(Figure
2).

##  8 Empirical Evaluation

We modified AlexNet by changing its output layer to match the number of
algorithms in our portfolio before training on our dataset of image-label
pairs. We use MATLAB’s implementation of AlexNet, which is pretrained using
the ImageNet dataset (?). We use a random $70\%$ of the data for training and
the other $30\%$ for testing. All of the values are reported for the test set.

We compare our _automatic algorithm selection_ $\pi$ approach against each
algorithm in our portfolio (i.e., WHCA*, FAR, and BMAA*), $\pi^{*}$, which
always selects the best algorithm in our portfolio for each problem instance,
and a _worst selector_ , which always selects the worst algorithm. We set the
parameters for the algorithms in our portfolio to the following: the size of
reservation tables used for FAR is $3$; the window size of WHCA* is $8$, the
lookahead value of BMAA* is $32$ and BMAA* has flow annotations turned off. We
chose these values as they performed well in our initial testing. All
algorithms were implemented in C#.

We use the $20$ video-game maps from _Baulder’s Gate II_ available in the
MovingAI benchmark (?). This included the $10$ largest maps from the game used
to originally evaluate FAR (?) and additional $10$ more small and mid sized
maps. We included more maps to get a more diverse benchmark ranging from $564$
traversable states to $51586$ states. We fixed the number of agents to $300$
for each MAPF problem. For each map we created $20$ MAPF problems for each of
the problem types defined in Section 7. Agents not at their goal at the time
limit have their goal achievement time artificially set to the $30$ second
time limit.

Figure 3 shows completion rate averaged over $10$ random splits of training
and test data to reduce the probability of a favourable split. We provide more
details in Table 1. We report the performance of the algorithms using our
primary completion rate metric, as well as our distances travelled and goal
achievement time tie-breaking metrics.

A perfect selector, which uses the best algorithm, would result in a $80.8\%$
completion rate(Table 1). Our approach achieves a completion rate of $76.6\%$,
which compares favorably to the best single algorithm (FAR), which has a
completion rate of $66.1\%$. FAR is followed by BMAA* with a completion rate
of $65.7\%$ and WHCA* with a completion rate of $54.6\%$. If one were to
consistently select the worst performing algorithm, the completion rate would
drop to $44.3\%$.

On the distance traveled metric, which breaks completion rate ties, $\pi$
significantly improves upon BMAA* and FAR with a $44\%$ (from $465.7$ to
$260.9$) and $36\%$ ($405.7$ to $260.9$) reduction, respectively. However, the
best single algorithm on this metric is WHCA* with $88.3$. Our distance metric
is recorded for all agents and not just agents who reach their goal. In other
words, an algorithm that never moves the agents would have the smallest
distance despite not completing the task. As distance was only for breaking
ties in our model, this was not of great concern.

On the goal achievement time metric, BMAA* is better than $\pi$ with a
$11.1\%$ (from $16.2s$ to $14.4s$) improvement. On this metric, BMAA* is
followed up by WHCA* with a goal achievement time of $15.9s$ and FAR with
$21.7s$. The reason why both WHCA* and FAR are slower despite the agents
traveling smaller distances than BMAA* is that many of the agents end up
waiting for other agents due to their use of reservation tables. WHCA* also
performs a more expensive three-dimensional search.

On average, over the $10$ splits of the training and test data, BMAA*, FAR,
and WHCA* was the best choice for $283.5$, $258.9$, and $296.6$ problems,
respectively. The neural network predicted BMAA*, FAR, and WHCA* to be the
best choice $269.0$, $249.4$, and $321.6$ problems, respectively. $\pi$ used
the correct algorithm $72.9\%$ of the time.

WHCA* is often the best choice despite low completion rate across all problem
types. WHCA* distance traveled makes it the best choice on problems where all
three algorithms achieve $100\%$ completion rate. This leads to its frequent
choosing despite its completion rate.

Figure 3: Completion Rate % for the test data averaged over 10 splits of the
data.

##  9 Current Shortcomings and Future Work

Our current approach has been tested on a limited number of maps and
configurations. Future work will extend the evaluation to more realistic MAPF
problems by mining start and goal locations from actual game logs, to identify
if there is significant pathfinding patterns within games for algorithm
selection to exploit. We will also consider adding more algorithms to the
portfolio as well as assigning algorithms to agents on a per-agent-cluster or
a per-agent bases.

##  10 Conclusions

We demonstrated that using an off-the-shelf deep neural network to
automatically select multi-agent pathfinding (MAPF) algorithms from a
portfolio can improve the performance over the individual algorithms in that
portfolio. This approach is promising since it does not require designing new
MAPF algorithms. Furthermore, with deep learning, human designers do not even
have to handcraft a set of features to describe MAPF problem instances. As a
result, this process is accessible to a broad range of game developers.
Similar ideas were recently explored for SAT/CSP solver selection (?).
However, our approach reduces the engineering effort required by using an off-
the-shelf deep neural network (AlexNet) in place of a custom-built CNN.

## References

  * [Boyarski et al. 2015] Boyarski, E.; Felner, A.; Stern, R.; Sharon, G.; Tolpin, D.; Betzalel, O.; and Shimony, S.  2015\.  ICBS: Improved conflict-based search algorithm for multi-agent pathfinding.  In Proceedings of the International Joint Conference on Artificial Intelligence, 740–746.
  * [Bulitko 2016a] Bulitko, V.  2016a.  Per-map algorithm selection in real-time heuristic search.  In Proceedings of the AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment, 143–148.
  * [Bulitko 2016b] Bulitko, V.  2016b.  Searching for real-time search algorithms.  In Proceedings of the International Symposium on Combinatorial Search, 121–122.
  * [Cohen, Uras, and Koenig 2015] Cohen, L.; Uras, T.; and Koenig, S.  2015\.  Feasibility study: Using highways for bounded-suboptimal multi-agent path finding.  In Proceedings of the International Symposium on Combinatorial Search, 2–8.
  * [de Wilde, ter Mors, and Witteveen 2013] de Wilde, B.; ter Mors, A.; and Witteveen, C.  2013\.  Push and Rotate: Cooperative multi-agent path planning.  In Proceedings of the International Conference on Autonomous Agents and Multiagent Systems, 87–94.
  * [Deng et al. 2009] Deng, J.; Dong, W.; Socher, R.; Li, L.-J.; Li, K.; and Fei-Fei, L.  2009\.  ImageNet: A Large-Scale Hierarchical Image Database.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 248–255.
  * [Erdem et al. 2013] Erdem, E.; Kisa, D.; Oztok, U.; and Schueller, P.  2013\.  A general formal framework for pathfinding problems with multiple agents.  In Proceedings of the AAAI Conference on Artificial Intelligence, 290–296.
  * [Facebook 2017] Facebook.  2017\.  Pytorch.  https://github.com/pytorch/vision/blob/master/torchvision/models/alexnet.py.
  * [Felner et al. 2017] Felner, A.; Stern, R.; Shimony, S.; Boyarski, E.; Goldenberg, M.; Sharon, G.; Sturtevant, N.; Wagner, G.; and Surynek, P.  2017\.  Search-based optimal solvers for the multi-agent pathfinding problem: Summary and challenges.  In Proceedings of the International Symposium on Combinatorial Search, 29–37.
  * [Google 2017] Google.  2017\.  Tensorflow.  https://github.com/tensorflow/models/blob/master/research/slim/nets/alexnet.py.
  * [Hart, Nilsson, and Raphael 1968] Hart, P.; Nilsson, N.; and Raphael, B.  1968\.  A formal basis for the heuristic determination of minimum cost paths.  IEEE Transactions on Systems Science and Cybernetics 4(2):100–107.
  * [Koenig and Likhachev 2006] Koenig, S., and Likhachev, M.  2006\.  Real-time adaptive A*.  In Proceedings of the International Conference on Autonomous Agents and Multiagent Systems, 281–288.
  * [Kornhauser, Miller, and Spirakis 1984] Kornhauser, D.; Miller, G.; and Spirakis, P.  1984\.  Coordinating pebble motion on graphs, the diameter of permutation groups, and applications.  In Proceedings of the IEEE Symposium on Foundations of Computer Science, 241–250.
  * [Kotthoff 2014] Kotthoff, L.  2014\.  Algorithm selection for combinatorial search problems: A survey.  AI Magazine 3(35):48–60.
  * [Krizhevsky, Sutskever, and Hinton 2012] Krizhevsky, A.; Sutskever, I.; and Hinton, G. E.  2012\.  Imagenet classification with deep convolutional neural networks.  In Proceedings of Advances in Neural Information Processing Systems, 1097–1105.
  * [Loreggia et al. 2016] Loreggia, A.; Malitsky, Y.; Samulowitz, H.; and Saraswat, V.  2016\.  Deep learning for algorithm portfolios.  In Proceedings of the AAAI Conference on Artificial Intelligence, 1280–1286.
  * [Luna and Bekris 2011] Luna, R., and Bekris, K.  2011\.  Push and Swap: Fast cooperative path-finding with completeness guarantees.  In Proceedings of the International Joint Conference on Artificial Intelligence, 294–300.
  * [Ma et al. 2016] Ma, H.; Tovey, C.; Sharon, G.; Kumar, T. K. S.; and Koenig, S.  2016\.  Multi-agent path finding with payload transfers and the package-exchange robot-routing problem.  In Proceedings of the AAAI Conference on Artificial Intelligence, 3166–3173.
  * [Ma et al. 2018] Ma, H.; Wagner, G.; Felner, A.; li, J.; Kumar, S.; and Koenig, S.  2018\.  Multi-agent path finding with deadlines: Preliminary results.  In Proceedings of the International Conference on Autonomous Agents and Multiagent Systems.
  * [Microsoft 2017] Microsoft.  2017\.  Cntk.  https://github.com/Microsoft/CNTK/tree/master/Examples/Image/Classification/AlexNet.
  * [Rice 1976] Rice, J. R.  1976\.  The algorithm selection problem.  Advances in Computers 15:65–118.
  * [Ryan 2010] Ryan, M.  2010\.  Constraint-based multi-robot path planning.  In Proceedings of IEEE Conference on Robotics and Automation, 922–928.
  * [Sharon et al. 2015] Sharon, G.; Stern, R.; Felner, A.; and Sturtevant, N.  2015\.  Conflict-based search for optimal multi-agent pathfinding.  Artificial Intelligence 219:40–66.
  * [Sigurdson and Bulitko 2017] Sigurdson, D., and Bulitko, V.  2017\.  Deep learning for real-time heuristic search algorithm selection.  In Proceedings of the AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment, 108–114.
  * [Sigurdson et al. 2018] Sigurdson, D.; Bulitko, V.; Yeoh, W.; Hernandez, C.; and Koenig, S.  2018\.  Real-time multi-agent pathfinding.  In Proceedings of IEEE Conference on Computational Intelligence and Games.
  * [Silver 2005] Silver, D.  2005\.  Cooperative pathfinding.  In Proceedings of the AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment, 117–122.
  * [Sturtevant 2012] Sturtevant, N. R.  2012\.  Benchmarks for grid-based pathfinding.  Transactions on Computational Intelligence and AI in Games 4(2):144 – 148.
  * [Surynek 2012] Surynek, P.  2012\.  Towards optimal cooperative path planning in hard setups through satisfiability solving.  In Proceedings of the AAAI Conference on Artificial Intelligence, 564–576.
  * [Vedaldi and Lenc 2015] Vedaldi, A., and Lenc, K.  2015\.  MatConvNet – convolutional neural networks for MATLAB.  In Proceeding of the ACM International Conference on Multimedia, 689–692.
  * [Wagner and Choset 2015] Wagner, G., and Choset, H.  2015\.  Subdimensional expansion for multirobot path planning.  Journal of Artificial Intelligence Research 219:1–24.
  * [Wang and Botea 2008] Wang, c., and Botea, A.  2008\.  Fast and memory-efficient multi-agent pathfinding.  In Proceedings of the International Conference on Automated Planning and Scheduling, 380–387.
  * [Wang and Botea 2011] Wang, K.-H. C., and Botea, A.  2011\.  MAPP: A scalable multi-agent path planning algorithm with tractability and completeness guarantees.  Journal of Artificial Intelligence Research 42:55–90.
  * [Yu and LaValle 2013a] Yu, J., and LaValle, S.  2013a.  Planning optimal paths for multiple robots on graphs.  In Proceedings of the International Conference on Robotics and Automation, 3612–3617.
  * [Yu and LaValle 2013b] Yu, J., and LaValle, S.  2013b.  Structure and intractability of optimal multi-robot path planning on graphs.  In Proceedings of the AAAI Conference on Artificial Intelligence, 1444–1449.


11institutetext:  InfAI e.V. Leipzig, Germany, 11email<EMAIL_ADDRESS>https://www.infai.org 22institutetext: AKSW research group, https://aksw.org
33institutetext: Leipzig University, Germany, https://www.uni-leipzig.de

# LLM-assisted Knowledge Graph Engineering: Experiments with ChatGPT

Lars-Peter Meyer 112233 0000-0001-5260-5181 Claus Stadler 112233
0000-0001-9948-6458 Johannes Frey 112233 0000-0003-3127-0815 Norman Radtke
1122 0000-0001-9155-8920 Kurt Junghanns 1122 0000-0003-1337-2770 Roy Meissner
2233 0000-0003-4193-8209 Gordian Dziwis 11 0000-0002-9592-418X Kirill Bulert
1122 0000-0002-1459-3754 Michael Martin 1122 0000-0003-0762-8688

###### Abstract

Knowledge Graphs (KG) provide us with a structured, flexible, transparent,
cross-system, and collaborative way of organizing our knowledge and data
across various domains in society and industrial as well as scientific
disciplines. KGs surpass any other form of representation in terms of
effectiveness. However, Knowledge Graph Engineering (KGE) requires in-depth
experiences of graph structures, web technologies, existing models and
vocabularies, rule sets, logic, as well as best practices. It also demands a
significant amount of work.

Considering the advancements in large language models (LLMs) and their
interfaces and applications in recent years, we have conducted comprehensive
experiments with ChatGPT to explore its potential in supporting KGE. In this
paper, we present a selection of these experiments and their results to
demonstrate how ChatGPT can assist us in the development and management of
KGs.

###### Keywords:

ChatGPT knowledge graph engineering RDF large language model use cases AI
application.

##  1 Introduction

In the last years, Artificial Intelligence (AI) has shown great promise in
improving or revolutionizing various fields of research and practice,
including knowledge engineering. The recent big leap in AI-based assistant
chatbots, like ChatGPT (Generative Pre-trained Transformer) model, has created
new opportunities to automate knowledge engineering tasks and reduce the
workload on human experts. With the growing volume of information in different
fields, the need for scalable and efficient methods to manage and extract
knowledge from data that also adapt to new sources is critical. Despite the
advances in research w.r.t. (semi)automation, knowledge engineering tasks
still rely vastly on human experts. On one hand, this process can be time-
consuming, resource-intensive, and susceptible to errors. On the other hand,
the reliance on human expertise in knowledge engineering exposes it to
workforce shortages (as knowledge engineers are scarce and the demand is
growing) and the risk of expertise loss. These factors can impact the
resilience and sustainability of systems and operations that rely on knowledge
engineering. AI-based assistant bot approaches, such as ChatGPT, could bridge
this gap by providing a unified tool for tasks in knowledge engineering, to
reduce the workload of knowledge engineers themselves, but also make knowledge
engineering more accessible to a broader audience. ChatGPT, in particular, has
shown promise in generating responses in a variety of syntactical
representations (including code and markup languages) to user queries or task
descriptions written in natural language.

In this paper, we discuss and investigate the potential of ChatGPT to support
or automate various knowledge engineering tasks (e.g. ontology generation,
SPARQL query generation). We will explore the benefits, pitfalls and
challenges of using it and identify potential avenues for future research.

##  2 Related Work

_ChatGPT_ , a Large Language Model (LLM) published by
OpenAI111https://openai.com/blog/chatgpt, raised the interest in the broad
field of Machine Learning (ML)222https://aiindex.stanford.edu/wp-
content/uploads/2023/04/HAI˙AI-Index-Report˙2023.pdf and especially LLMs[4] on
a broad scale. While there are current discussions and analysis on the
capabilities of LLMs like ChatGPT in general (e.g. [1]), there is little in
the area of knowledge graph engineering. Ekaputra et al.[3] gives a general
overview of current research on the combination of the broad field of ML and
semantic web.

Searching Google Scholar and Semantic Scholar with ”knowledge graph ChatGPT”,
”ontology ChatGPT” and ”rdf ChatGPT” in the beginning of April 2023 results in
only two relevant papers. The first one, [7], reviews the differences between
conversational AI models, prominent ChatGPT, and state-of-the-art question-
answering systems for knowledge graphs. In their survey and experiments, they
detect capabilities of their used frameworks but highlight ChatGPTs
explainability and robustness. The second one, [6], discusses the usage of
ChatGPT for database management tasks when tabular schema is expressed in a
natural language. They conclude among others that ChatGPT is able to assist in
complex semantic integration and table joins to simplify database management
and enhance productivity. The applied approaches and results of these two
papers indicate that the idea of using LLMs like ChatGPT in the field of KG
engineering is encouraging and that the LLMs might assist KG engineers in
their workflows. Still, the research on the usage of LLMs for knowledge graph
engineers is scarce and seems to be a new research area.

There exist some non- and semi-scientific resources which render the topic
from a practical and experience perspective. We want to highlight here a
helpful blog post by Kurt Cagle [2] on ChatGPT for ”knowledge graph workers”
and a blog post by Konrad Kaliciński [5] on knowledgegraph generation in Neo4J
assisted by ChatGPT.

##  3 LLM-Assisted Knowledge Graph Engineering - Potential Application Areas

In discussion rounds with knowledge graph engineering experts we identified
the following preliminary list of potential use cases in the domain of
knowledge graph engineering applicable to LLMs assistance:

  * •

Assistance in knowledge graph usage:

    * –

Generate SPARQL queries from natural language questions (related experiment in
Section 4.1 and Section 4.3)

    * –

Exploration and summarization of existing knowledge graphs (related experiment
in Section 4.5)

    * –

Conversion of competency questions to SPARQL queries

    * –

Code generation or configuration of tool(chain)s for data pipelines

  * •

Assistance in knowledge graph construction

    * –

Populating knowledge graphs (related experiment in Section 4.4) and vice versa

    * –

Creation or enrichment of knowledge graph schemas / ontologies

    * –

Get hints for problematic graph design by analysing ChatGPT usages problems
with a knowledge graph

    * –

Semantic search for concepts or properties defined in other already existing
knowledge graphs

    * –

Creation and adjustment of knowledge graphs based on competency questions

Given the limited space of this paper, we evaluate a subset of the application
areas with experiments in the following section.

##  4 Experiments

To evaluate the capabilities of LLMs at the example of ChatGPT for assisting
with knowledge graph engineering, we present several experiments and their
results. Further details about them is given in the Supplemental Online
Resources. Most experiments were conducted with ChatGPT with the LLM
GPT-3.5-turbo333https://platform.openai.com/docs/models/gpt-3-5 (named
_ChatGPT-3_ from here on), some additionally with ChatGPT with the LLM
GPT-4444https://platform.openai.com/docs/models/gpt-4 (named _ChatGPT-4_ from
here on).

###  4.1 SPARQL Query Generation for a Custom Small Knowledge Graph

For a first evaluation, we designed a small knowledge graph as shown in
Listing 4.1. Specifically, we wanted to know whether (1) GPT can explain
connections between indirectly related entities, (2) create SPARQL queries
over the given model and (3) reconstruct the model if all properties and
classes were relabelled.

⬇

:anne a foaf:Person ; foaf:firstName ”Anne” ; foaf:surname ”Miller” ;

vcard:hasAddress [ a vcard:Home ; vcard:country-name ”UK” ] .

:bob a foaf:Person ; foaf:firstName ”Bob” ; foaf:surname ”Tanner” ;

vcard:hasAddress [ a vcard:Home ; vcard:country-name ”US” ] .

:wonderOrg a org:Organization .

:researchDep a org:OrganizationalUnit ; org:unitOf :wonderOrg ;

rdfs:label ”Research Department” .

:marketingDep a org:OrganizationalUnit ; org:unitOf :wonderOrg ;

rdfs:label ”Marketing Department” .

:chiefResearchOfficer a org:Role . :marketingManager a org:Role .

[ a org:Membership ; org:member :anne ; org:organization :researchDep ;

org:role :chiefResearchOfficer ] .

[ a org:Membership ; org:member :bob ; org:organization :marketingDep ;

org:role :marketingManager ] .

An organizational KG with two people working in different departments of the
same organization.

We issued the following prompt, which includes the knowledge graph from
Section 4.1, on ChatGPT-3 and ChatGPT-4: Prompt 1: Given the RDF/Turtle model
below, are there any connections between US and UK? $<$rdf-model$>$

In the knowledge graph of Section 4.1, there is a connection between the two
countries via the two people living in these, which got a job in different
departments of the same company. While ChatGPT-3 fails to identify this
relation, ChatGPT-4 successfully identifies it in all cases.

We further asked both ChatGPT models with prompt 4.1 and received five SPARQL
queries each, which we analysed for their syntactic correctness, plausible
query structure, and result quality. The results for prompt 4.1 are listed in
table 1 and show that both models produce syntactically correct queries, which
in most cases are plausible and produce corrects results in 3/5 (ChatGPT3) and
2/5 (ChatGPT4) cases.

Prompt 2: Given the RDF/Turtle model below, create a SPARQL query that lists
for every person the country, company and department and role. Please adhere
strictly to the given model. $<$rdf-model$>$

Table 1: Findings in generated SPARQL queries for prompt 4.1. | ChatGPT-3 | ChatGPT-4
---|---|---
syntactically correct | 5/5 | 5/5
plausible query structure | 4/5 | 3/5
producing correct result | 3/5 | 2/5
using only defined classes and properties | 3/5 | 4/5
correct usage of classes and properties | 5/5 | 5/5
correct prefix for the graph | 5/5 | 4/5

In essence, AI-based query generation is possible and it can produce valid
queries. However, the process needs result validation in two dimensions: 1)
validating the query itself by matching to static information, like available
classes and properties in the graph, as well as 2) validating the executed
query results to let ChatGPT generate new queries in case of empty result sets
in order to find working queries in a try & error approach.

As a last prompt on the knowledge graph from Section 4.1, we created a derived
RDF graph by relabelling all classes and properties with sequentially numbered
IRIs in the example namespace, like _eg:prop1_ and _eg:class2_. Given the
relabelled model, we tasked ChatGPT: Prompt 3: Given the RDF/Turtle model
below, please replace all properties and classes with the most likely standard
ones. $<$rdf-model$>$

With ChatGPT-3 only 2/5 iterations succeeded in carrying out all
substitutions. In those succeeding cases, the quality was still not as
expected because of limited ontology reuse: Only IRIs in the example namespace
were introduced, rather than reusing the _foaf_ , _vcard_ , and _org_
vocabularies. Yet, the ad-hoc properties and classes were reasonably named,
such as _eg:firstName_ , _eg:countryName_ or _eg:departmentName_. In contrast,
ChatGPT-4 delivered better results: All classes and properties were
substituted with those from standard vocabularies - foaf, vcard, and org were
correctly identified. For some iterations, ChatGPT-4 used the schema.org
vocabulary instead of the org vocabulary as an alternative approach.

###  4.2 Token Counts for Knowledge Graphs Schemas

After the results with the small custom knowledge graph we wanted to check the
size of some well known knowledge graphs with respect to LLMs.

The LLMs behind ChatGPT can handle at the moment only 4096 tokens (GPT-3.53)
or 8192 respective 32,768 tokens for GPT-44.

We counted tokens for various public knowledge graphs in different
serialization formats with the library _tiktoken_
555https://github.com/openai/tiktoken as recommended for ChatGPT. Table 2
lists the token counts for a couple of combinations ordered by token count.
More data and information is available in the Supplemental Online Resources.
The turtle serialization seem to result in minimal token count, but is still
bigger than the similar SQL schema added for comparison. All knowledge graphs
exceed the token limit for GPT-3.5 and 3 of 4 knowledge graphs listed here
exceed the limit for GPT-4.

Table 2: Token counts for selected knowledge graphs and serialisations Graph | Serialisation Type | Token Count
---|---|---
Mondial Oracle DB schema | SQL schema | 2,608 token
Mondial RDF schema | turtle | 5,339 token
Mondial RDF schema | functional syntax | 9,696 token
Mondial RDF schema | manchester syntax | 11,336 token
Mondial RDF schema | xml/rdf | 17,179 token
Mondial RDF schema | json-ld | 47,229 token
Wine Ontology | turtle | 13,591 token
Wine Ontology | xml/rdf | 24,217 token
Pizza Ontology | turtle | 5.431 token
Pizza Ontology | xml/rdf | 35,331 token
DBpedia RDF schema | turtle | 471,251 token
DBpedia RDF schema | xml/rdf | 2,338,484 token

###  4.3 SPARQL Query Generation for the Mondial Knowledge Graph

In addition to the experiments with the small custom knowledge graph (see
Section 4.1) we tested ChatGPT with the bigger mondial knowledge
graph666https://www.dbis.informatik.uni-goettingen.de/Mondial which is
published since decades with the latest ”main revision” 2015.

We asked ChatGPT to generate a SPARQL query for a natural language question
from a sparql university lecture777https://www.dbis.informatik.uni-
goettingen.de/Teaching/SWPr-SS20/swpr-1.pdf. We used the following prompt five
times with ChatGPT-3 and ChatGPT-4 each: Prompt 4: Please create a sparql
query based on the mondial knowledge graph for the following question: which
river has the most riparian states?

The results are documented in the Supplemental Online Resources together with
detailed comments on the given queries. Table 3 gives some statistics. In
summary, all SPARQL queries given by ChatGPT were syntactically correct, but
none of them worked when executed. Actually all queries had at least one error
preventing the correct execution like referencing a wrong namespace, wrong
usage of properties or referencing undefined classes.

Table 3: Findings in generated sparql queries for prompt 7. | ChatGPT-3 | ChatGPT-4
---|---|---
syntactically correct | 5/5 | 5/5
plausible query structure | 2/5 | 4/5
producing correct result | 0/5 | 0/5
using only defined classes and properties | 1/5 | 3/5
correct usage of classes and properties | 0/5 | 3/5
correct prefix for mondial graph | 0/5 | 1/5

###  4.4 Knowledge Extraction from Fact Sheets

As an experiment to evaluate knowledge extraction capabilities, we used PDF
fact sheets of 3D printer specifications from different additive manufacturing
(AM) vendor websites. The goal is to build a KG about existing 3D printers and
their type as well as capabilities. We fed plaintext excerpts (extracted via
pdfplumber) from these PDFs into ChatGPT-3 and prompted it to: Prompt 5:
Convert the following $$vendor$$ 3d printer specification into a JSON_LD
formatted Knowledge Graph. The node for this KG should be Printer as a main
node, Type of 3d printer such as FDM, SLA, and SLS, Manufacturer, Material,
Applications, and Technique. Since the fact sheets are usually formatted using
a table scheme, the nature of these plain texts is that mostly the printer
entity is mentioned in the beginning of the text which then is further
characterized in a key-value style. As a result, the text typically does not
use full sentences and contains only one entity that is described in detail,
but several dependant entities (like printing materials). However, the format
of the key-value pairs can be noisy. Key names can be separated with colons,
new line feeds, or in contrast multiple key-value pairs can be in the same
line, which could impose a challenge. Nevertheless, ChatGPT was able to
identify the key-value pairs of the evaluation document in a reliably way.
Unfortunately, it delivered out of 5 test runs for this document 4 partial and
1 complete JSON document. In spite of that, we summarize first insights gained
from a knowledge engineering perspective (but for the sake of brevity, we
refer to the output documents in the experiment supplements)

  * •

The JSON-LD output format prioritizes usage of schema.org vocabulary in the 5
evaluation runs. This works good for well-known entities and properties (e.g.
Organization @type for the manufacturer, or the name property), however, for
the AM-specific feature key names or terms like printer ChatGPT-3 invents
reasonable but non-existent property names (in the schema.org namespace)
instead of accurately creating a new namespace or using a dedicated AM
ontology for that purpose.

  * •

Requesting turtle as output format instead, leads to different results. E.g.
the property namespace prefix is based on the printer ID and therefore printer
descriptions are not interoperable and can not be queried in unified way in a
joint KG.

  * •

Successfully splitting x,y and z values of the maximum print dimension
(instead of extracting all dimensions into one string literal) works in 3
runs. Although ChatGPT-3 accurately appends the unit of measurement to all
x,y,z values (which is only mentioned after the z value in the input) in those
cases, this is a modelling flaw, as querying the KG will be more complex. In
one run it addressed this issue by separating units into a separate unit code
field.

  * •

A similar effect was observed when it comes to modelling the dependent
entities. E.g., in 4 runs, the manufacturer was modelled correctly as a
separate typed entity, in 1 as string literal instead.

As a general conclusion of the experiment, ChatGPT-3 has overall solid skills
to extract the key value pairs from the sheets, but the correct modelling or
representation in terms of a KG significantly varies from run to run.
Subsequently, none of the generated JSON documents contained sufficient
information on their own, but only a subset that was modelled accurately. A
question for future research is whether cherrypicking of individual JSON
elements from outputs of several runs and combining them into one final
document or iteratively refining the output by giving ChatGPT generic
modelling feedback (like use an ontology, or separate unit information, etc.)
can be automated in a good and scalable way.

###  4.5 Knowledge Graph Exploration

Experts in the field of knowledge graphs are familiar with concepts from RDF
Schema (RDFS) (domain/range, subPropertyOf, subClassOf) and Web Ontology
Language (OWL) (ObjectProperty, DatatypeProperty, FunctionalProperty, …).
Often, each of these experts has their preferred tools and methods for gaining
an overview of an ontology they are not yet familiar with. We asked ChatGPT-3
two different questions requesting the mermaid888“… a JavaScript-based
diagramming and charting tool …” https://mermaid.js.org/ visualization of the
most important concepts and their connections:

Prompt 6: Can you create me a visualization showing the most important classes
and concepts and how they are linked for dbpedia ontology, serialized for
mermaid?

Prompt 7: Can you create me a visualization of the most common concepts of the
DBpedia ontology and their connections focusing on domain and range defined in
properties.

We expected a graph with at least eight nodes and their corresponding edges.
The identifiers for the nodes and edges are expected to follow the Turtle or
SPARQL prefix:concept notation. If the first question did not achieve the
goal, we asked additional questions or demands to ChatGPT-3. The results are
presented in table 4 and we evaluated the displayed graphs based on the
following criteria:

Prompt 4.5 led to an answer with a hierarchical graph representation of the
important classes defined in the DBpedia ontology. The diagram already met our
requirements regarding the minimum number and labelling after the first answer
and can be seen in the Supplemental Online Resources.

The class hierarchy was represented by the rdfs:subPropertyOf relation, and
the nodes were labelled in prefix notation, as were the edges. By arranging it
as a tree using the subClassOf-pattern, only two different properties were
used for the relations (edges). The root node was of type owl:Thing other
nodes are connected as (sub)classes from the DBpedia ontology. These were:
Place, Organization, Event, Work, Species, and Person. The class Work had one
more subClassOf relation to the class MusicalWork. The class Person had the
most complex representation, with two more subClassOf relations leading to
foaf:Person and foaf:Agent, the latter of which is a subclass of the root node
(owl:Thing).

In the second prompt (Prompt 4.5 ChatGPT-3 referred to a graphic file within
the answer text that no longer existed. Upon further inquiry, a mermaid
diagram was generated. It was of type ”Graph” and contained thirteen common
concepts and seventeen edges, which were all unique. The labels of both, nodes
and edges contain no prefixes, but were addable with further inquiry. Only the
generated concept dbo:Occupation is non-existent. All remaining nodes and
edges comply with the rules of the ontology, even if the concepts used are
derived through further subclass relationships. The resulting diagram is shown
in the Supplemental Online Resources.

Table 4: Diagram content overview.

| Prompt 4.5 | Prompt 4.5
---|---|---
Mermaid Type | graph | graph*
Labels of Nodes | prefix and concept | prefix and concept**
Labels of Edges | prefix and concept | prefix and concept**
Number of Nodes (total/existing/dbo) | 10/10/8 | 13/12/12
Number of Edges (total/unique) | 12/2 | 17/17

  * *

One more prompt was needed to serialize a graph

  * **

One more prompt was needed to add prefixed labels

While prompt 4.5 leads to a result that can be more comprehensively achieved
with conventional tools for visualizing RDF, the result from prompt 4.5
provides an overview of concepts (classes) and properties that can be used to
relate instances of these classes to each other.

##  5 Conclusion and Future Work

From the perspective of a knowledge graph engineer, ChatGPT has demonstrated
impressive capabilities. It successfully generated knowledge graphs from semi-
structured textual data, translated natural language questions into
syntactically correct and well-structured SPARQL queries for the given
knowledge graphs, and even generated overview diagrams for large knowledge
graph schemas, as outlined in section 4. An detailed analysis revealed that
the generated results contain mistakes, of which some are subtle. For some use
cases, this might be harmless and can be tackled with additional validation
steps in general, like with the metrics we used for SPARQL queries. In
general, our conclusion is, that one needs to keep in mind ChatGPT’s tendency
to _hallucinate_ 999Generation of content without any foundation, especially
when applied to the field of knowledge graph engineering where many engineers
are used to mathematical precision and logic.

The closed-source nature of ChatGPT challenges scientific research on it in
two ways:  1. Detailed capability ratings of closed-source probabilistic
models require much effort  2. Result reproducibility is bound to service
availability and results might be irreproducible at a later date (due to
service changes)  Thus, open training corpora and LLMS are mandatory for
proper scientific research.

In the future, metrics are to be found to rate generated ChatGPT answers
automatically, like we broached with SPARQL queries. This again enables to
extend the number of test cases for a specific experiment and to generate
profound statistical results. Another research focus should be given to
methods that let the LLM access a broader/necessary context to increase the
chance for correct answers.

#### Acknowledgements

This work was partially supported by grants from the German Federal Ministry
for Economic Affairs and Climate Action (BMWK) to the CoyPu project
(01MK21007A) and KISS project (01MK22001A) as well as from the German Federal
Ministry of Education and Research (BMBF) to the project StahlDigital
(13XP5116B) and project KupferDigital (13XP5119F).

## References

  * [1] Bubeck, S., Chandrasekaran, V., Eldan, R., Gehrke, J., Horvitz, E., Kamar, E., Lee, P., Lee, Y.T., Li, Y., Lundberg, S., Nori, H., Palangi, H., Ribeiro, M.T., Zhang, Y.: Sparks of artificial general intelligence: Early experiments with gpt-4 (Mar 2023). https://doi.org/10.48550/ARXIV.2303.12712
  * [2] Cagle, K.: Nine chatgpt tricks for knowledge graph workers. https://thecaglereport.com/2023/03/16/nine-chatgpt-tricks-for-knowledge-graph-workers/ (Mar 2023), accessed: 2023-04-14
  * [3] Ekaputra, F.J., Llugiqi, M., Sabou, M., Ekelhart, A., Paulheim, H., Breit, A., Revenko, A., Waltersdorfer, L., Farfar, K.E., Auer, S.: Describing and organizing semantic web and machine learning systems in the swemls-kg (Mar 2023). https://doi.org/10.48550/ARXIV.2303.15113
  * [4] Haque, M.U., Dharmadasa, I., Sworna, Z.T., Rajapakse, R.N., Ahmad, H.: ”i think this is the most disruptive technology”: Exploring sentiments of chatgpt early adopters using twitter data (Dec 2022). https://doi.org/10.48550/ARXIV.2212.05856
  * [5] Kaliciński, K.: Create neo4j database model with chatgpt. https://neo4j.com/developer-blog/create-neo4j-database-model-with-chatgpt/ (Jan 2023), accessed: 2023-04-14
  * [6] Lin, W., Babyn, P., yan, Y., Zhang, W.: Context-based ontology modelling for database: Enabling chatgpt for semantic database management (Mar 2023). https://doi.org/10.48550/ARXIV.2303.07351
  * [7] Omar, R., Mangukiya, O., Kalnis, P., Mansour, E.: Chatgpt versus traditional question answering for knowledge graphs: Current status and future directions towards knowledge graph chatbots (Feb 2023). https://doi.org/10.48550/ARXIV.2302.06466

## Supplemental Online Resources

Details on the experiments described can be found at the following github
repo: https://github.com/AKSW/AI-Tomorrow-2023-KG-ChatGPT-Experiments

##  Appendix 0.A Deutsche Zusammenfassung

Wissensgraphen (englisch _Knowledge Graphs_ , KGs), bieten uns eine
strukturierte, flexible, transparente, systemübergreifende und kollaborative
Möglichkeit, unser Wissen und unsere Daten über verschiedene Bereiche der
Gesellschaft und der industriellen sowie wissenschaftlichen Disziplinen hinweg
zu organisieren. KGs übertreffen jede andere Form der Repräsentation in Bezug
auf die Effektivität. Die Entwicklung von Wissensgraphen (englisch _Knowledge
Graph Engineering_ , KGE) erfordert jedoch fundierte Erfahrungen mit
Graphstrukturen, Webtechnologien, bestehenden Modellen und Vokabularen,
Regelwerken, Logik sowie Best Practices. Es erfordert auch einen erheblichen
Arbeitsaufwand.

In Anbetracht der Fortschritte bei großen Sprachmodellen (englisch _Large
Language Modells_ , LLMs) und ihren Schnittstellen und Anwendungen in den
letzten Jahren haben wir umfassende Experimente mit ChatGPT durchgeführt, um
sein Potenzial zur Unterstützung von KGE zu untersuchen. In diesem Artikel
stellen wir eine Auswahl dieser Experimente und ihre Ergebnisse vor, um zu
zeigen, wie ChatGPT uns bei der Entwicklung und Verwaltung von KGs
unterstützen kann.


M_{\bm{a},j_{r}})\Big{)}=\bigcap_{r=1}^{m}T_{\tilde{y}}(M_{\bm{a},{i_{r}}}\cap
M_{\bm{a},j_{r}})$ for all
$\tilde{y}\in\bigcap_{r=1}^{m}(M_{\bm{a},{i_{r}}}\cap M_{\bm{a},j_{r}})$ for
almost every $\bm{a}\in A$, so

$\tilde{v}\in T_{\tilde{y}}\Big{(}\bigcap_{r=1}^{m}(M_{\bm{a},i_{r}}\cap
M_{\bm{a},j_{r}})\Big{)}$

for almost every $\bm{a}\in A$. Therefore, $v=d\pi_{[m]}(\tilde{v})$ is in
$T_{y}\Big{(}\pi_{[m]}\Big{(}\bigcap_{r=1}^{m}(M_{\bm{a},i_{r}}\cap
M_{\bm{a},j_{r}})\Big{)}\Big{)}=T_{y}\Big{(}\bigcap_{r=1}^{m}I_{\bm{a}}(\sigma_{i_{r}},\sigma_{j_{r}})\Big{)}$,
which implies that

$T_{y}\Big{(}\bigcap_{r=1}^{m}I_{\bm{a}}(\sigma_{i_{r}},\sigma_{j_{r}})\Big{)}\supseteq\bigcap_{r=1}^{m}T_{y}\Big{(}I_{\bm{a}}(\sigma_{i_{r}},\sigma_{j_{r}})\Big{)}\,.$

∎

The following series of lemmas is used to prove Lemma 4.13, which shows that
$\mathcal{Y}_{\bm{a}}$ is locally finite for almost every $\bm{a}\in A$, and
Lemma 4.14, which shows that $\mathcal{Y}_{\bm{a}}$ satisfies the Axiom of the
Frontier for almost every $\bm{a}\in A$. (Recall that $\mathcal{Y}_{\bm{a}}$
is the set of subsets of $B$ that is defined by (15).)

######  Lemma A.6.

If $\bm{a}\in A$ is such that each $Y\in\mathcal{Y}_{\bm{a}}$ is a manifold,
then for any strict partial order $\prec$ on $\mathcal{K}$, there is a unique
subset $\mathcal{Y}^{\prec}_{\bm{a}}\subseteq\mathcal{Y}_{\bm{a}}$ such that
$Z^{\prec}_{\bm{a}}=\bigcup_{Y\in\mathcal{Y}^{\prec}_{\bm{a}}}Y$, where
$Z^{\prec}_{\bm{a}}$ is defined as in (4.2).

###### Proof.

Let $Y\in\mathcal{Y}_{\bm{a}}$ and suppose that $Y\cap
Z_{\bm{a}}^{\prec}\neq\emptyset$. This implies that there is a point $p\in Y$
such that $\prec_{f_{\bm{a}}(\cdot,p)}$ is the same as $\prec$. By Lemma 4.11,
the simplex order induced by $f$ is constant in $Y$, so $Y\subseteq
Z_{\bm{a}}^{\prec}$. ∎

######  Lemma A.7.

Let $\prec$ be a strict partial order on the simplices in $\mathcal{K}$. Let
$\bm{a}\in A$ be such that

  1. (1)

every $Y\in\mathcal{Y}_{\bm{a}}$ is a manifold, where $\mathcal{Y}_{\bm{a}}$
is defined as in (15),

  2. (2)

$M_{\bm{a},i}\pitchfork M_{\bm{a},j}$ for all $i\neq j$, where $M_{\bm{a},i}$
is defined as in (9),

  3. (3)

$\bigcap_{r=1}^{m}I_{\bm{a}}(\sigma_{i_{r}},\sigma_{j_{r}})$ is a manifold for
all sets $\\{(i_{r},j_{r}\\}_{r=1}^{m}$ of index pairs, and

  4. (4)

we have

(28)
$T_{p}\Big{(}\bigcap_{r=1}^{m}I_{\bm{a}}(\sigma_{i_{r}},\sigma_{j_{r}})\Big{)}=\bigcap_{r=1}^{m}T_{p}\Big{(}I_{\bm{a}}(\sigma_{i_{r}},\sigma_{j_{r}})\Big{)}$

for all sets $\\{(i_{r},j_{r}\\}_{r=1}^{m}$ of index pairs and all
$p\in\bigcap_{r=1}^{m}I_{\bm{a}}(\sigma_{i_{r}},\sigma_{j_{r}})$.

Let $\mathcal{Y}^{\prec}_{\bm{a}}$ be the unique subset of
$\mathcal{Y}_{\bm{a}}$ such that
$Z_{\bm{a}}^{\prec}=\bigcup_{Y\in\mathcal{Y}^{\prec}_{\bm{a}}}Y$, which exists
by Lemma A.6. Then every $p\in B$ has a neighborhood that intersects at most
one set $Y\in\mathcal{Y}^{\prec}_{\bm{a}}$.

###### Proof.

Let $S(p)=\\{(\sigma_{i},\sigma_{j})\mid p\in
I_{\bm{a}}(\sigma_{i},\sigma_{j})\\}$. There is a neighborhood $U_{0}$ of $p$
such that $I(\sigma_{i},\sigma_{j})\cap U_{0}\neq\emptyset$ if and only if
$(\sigma_{i},\sigma_{j})\in S(p)$. In a neighborhood of $p$, each
$I(\sigma_{i},\sigma_{j})$ is locally diffeomorphic (via the exponential map,
for example) to $T_{p}(I_{\bm{a}}(\sigma_{i},\sigma_{j}))$, which is an
$(n-1)$-dimensional hyperplane. By (28), these local diffeomorphisms are
compatible with each other, so there is a neighborhood $U$ of $p$, a set
$\\{H(\sigma_{i},\sigma_{j})\\}_{(\sigma_{i},\sigma_{j})\in S(p)}$ of
hyperplanes in $\mathbb{R}^{n}$, and a homeomorphism $\phi:U\to\mathcal{B}$,
where $\mathcal{B}$ is the open unit $n$-ball, such that

$\phi\Big{(}\bigcap_{(\sigma_{i},\sigma_{j})\in
S^{\prime}(p)}I_{\bm{a}}(\sigma_{i},\sigma_{j})\cap
U\Big{)}=\bigcap_{(\sigma_{i},\sigma_{j})\in
S^{\prime}(p)}H(\sigma_{i},\sigma_{j})\cap\mathcal{B}$

for all $S^{\prime}(p)\subseteq S(p)$. See Figure 8 for intuition, where we
illustrate the neighborhood $U$ for a few points $p\in B$.

Figure 8. For each point $p_{i}$, we illustrate the idea behind the
homeomorphism $\phi:U_{i}\to\mathcal{B}$ in the proof of Lemma A.7, where
$U_{i}$ is a neighborhood of $p_{i}$ and $\mathcal{B}$ is an open unit ball in
$\mathbb{R}^{2}$. The base space is $B=\mathbb{R}^{2}$; we show only the sets
$I(\sigma_{1},\tau_{1})$ and $I(\sigma_{2},\tau_{2})$, which are curves in the
plane, for some simplices
$\sigma_{1},\sigma_{2},\tau_{1},\tau_{2}\in\mathcal{K}$ and some fibered
filtration function $f:\mathcal{K}\times B\to\mathbb{R}$.

The hyperplanes induce a stratification of $\mathcal{B}$, with a set
$\mathcal{Y}^{\prime}$ of strata, such that for all
$Y^{\prime}\in\mathcal{Y}^{\prime}$, we have $Y^{\prime}=\phi(Y\cap U)$ for
some $Y\in\mathcal{Y}_{\bm{a}}$. Because $M_{\bm{a},i}\pitchfork M_{\bm{a},j}$
for all $i\neq j$, we have that $\mathcal{B}\setminus
H(\sigma_{i},\sigma_{j})$ is the disjoint union of open sets
$W_{1}(\sigma_{i},\sigma_{j})$ and $W_{2}(\sigma_{i},\sigma_{j})$ such that

$\displaystyle f_{\bm{a}}(\sigma_{i},p^{\prime})$
$\displaystyle<f_{\bm{a}}(\sigma_{j},p^{\prime})\qquad\text{for all
}p^{\prime}\in\phi^{-1}(W_{1}(\sigma_{i},\sigma_{j}))\,,$ $\displaystyle
f_{\bm{a}}(\sigma_{j},p^{\prime})$
$\displaystyle<f_{\bm{a}}(\sigma_{i},p^{\prime})\qquad\text{for all
}p^{\prime}\in\phi^{-1}(W_{2}(\sigma_{i},\sigma_{j}))$

for all $(\sigma_{i},\sigma_{j})\in S(p)$. Suppose that $u_{1}$ and $u_{2}$
are points in $U$ such that $\prec_{f_{\bm{a}}(\cdot,u_{1})}$ and
$\prec_{f_{\bm{a}}(\cdot,u_{2})}$ are both the same as $\prec$. For each
$(\sigma_{i},\sigma_{j})\in S(p)$, define the set

(29)
$V(\sigma_{i},\sigma_{j}):=\begin{cases}H(\sigma_{i},\sigma_{j})\,,&\sigma_{i}\not\prec\sigma_{j}\text{
and }\sigma_{j}\not\prec\sigma_{i}\\\
W_{1}(\sigma_{i},\sigma_{j})\,,&\sigma_{i}\prec\sigma_{j}\\\
W_{2}(\sigma_{i},\sigma_{j})\,,&\sigma_{j}\prec\sigma_{i}\,.\end{cases}$

We define

(30) $V:=\bigcap_{(\sigma_{i},\sigma_{j})\in
S(p)}V(\sigma_{i},\sigma_{j})\neq\emptyset\,,$

which is a stratum in $\mathcal{Y}^{\prime}$. Therefore, there is a
$Y\in\mathcal{Y}_{\bm{a}}$ such that $Y\cap U=\phi^{-1}(V)$, with
$u_{1},u_{2}\in Y\cap U$. Therefore, $Y$ is the only element of
$\mathcal{Y}^{\prec}_{\bm{a}}$ that $U$ intersects. ∎

######  Lemma A.8.

Let $\prec_{0}$ be a strict partial order on the simplices in $\mathcal{K}$,
and define $\mathcal{O}$ to be the set of strict partial orders $\prec$ such
that

  1. (1)

if $\sigma\prec_{0}\tau$ and $\sigma\neq\tau$, then either we have
$\sigma\prec\tau$ or we have $\sigma\not\prec\tau$ and $\tau\not\prec\sigma$,

  2. (2)

if $\sigma\not\prec_{0}\tau$ and $\tau\not\prec_{0}\sigma$, then
$\sigma\not\prec\tau$ and $\tau\not\prec\sigma$, and

  3. (3)

the strict partial order $\prec$ is not the same as $\prec_{0}$.

If $\bm{a}\in A$ is such that

  1. (1)

every $S\in\overline{E_{\bm{a}}^{n-\ell}}$ is an $\ell$-dimensional smooth
submanifold for every $\ell\in\\{1,\ldots,n\\}$, where $n$ is the dimension of
$B$,

  2. (2)

$M_{\bm{a},i}\pitchfork M_{\bm{a},j}$ for all $i\neq j$,

  3. (3)

the set $\bigcap_{r=1}^{m}I_{\bm{a}}(\sigma_{i_{r}},\sigma_{j_{r}})$ is a
manifold for all sets $\\{(i_{r},j_{r})\\}_{r=1}^{m}$ of index pairs, and

  4. (4)

$T_{y}(\bigcap_{r=1}^{m}I_{\bm{a}}(\sigma_{i_{r}},\sigma_{j_{r}})=\bigcap_{r=1}^{m}T_{y}(I_{\bm{a}}(\sigma_{i_{r}},\sigma_{j_{r}}))$
for all sets $\\{(i_{r},j_{r})\\}_{r=1}^{m}$ of index pairs,

then

$\partial Z^{\prec_{0}}_{\bm{a}}=\bigcup_{\prec\text{ in
}\mathcal{O}}Z^{\prec}_{\bm{a}}\,.$

###### Proof.

By Lemma 4.10, every $Y\in\mathcal{Y}_{\bm{a}}$ is a manifold. By Lemmas A.6
and A.7, the sets $Z^{\prec_{0}}_{\bm{a}}$ and $Z^{\prec}_{\bm{a}}$ (for all
$\prec$ in $\mathcal{O}$) are submanifolds of $B$.

Case 1: If $\dim(Z^{\prec_{0}}_{\bm{a}})=0$, then we must have

$Z^{\prec_{0}}_{\bm{a}}=I_{\bm{a}}(\sigma_{i_{1}},\sigma_{j_{1}})\cap\cdots\cap
I_{\bm{a}}(\sigma_{i_{n}},\sigma_{j_{n}})\,.$

for some $I_{\bm{a}}(\sigma_{i_{1}},\sigma_{j_{1}})\cap\cdots\cap
I_{\bm{a}}(\sigma_{i_{n}},\sigma_{j_{n}})\in\overline{E^{n}_{\bm{a}}}$. If
$\prec$ is in $\mathcal{O}$, then there is another pair
$(\sigma_{i_{n+1}},\sigma_{j_{n+1}})$ of distinct simplices such that
$\sigma_{i_{n+1}}\not\prec\sigma_{j_{n+1}}$ and
$\sigma_{j_{n+1}}\not\prec\sigma_{i_{n+1}}$. Therefore,

$Z^{\prec}_{\bm{a}}\subseteq
I_{\bm{a}}(\sigma_{i_{1}},\sigma_{j_{1}})\cap\cdots\cap
I_{\bm{a}}(\sigma_{i_{n}},\sigma_{j_{n}})\cap
I_{\bm{a}}(\sigma_{i_{n+1}},\sigma_{j_{n+1}})\,,$

which is an element of $\overline{E^{n+1}_{\bm{a}}}$. By choice of $\bm{a}$,
every $S\in\overline{E^{n+1}_{\bm{a}}}$ is empty, so
$Z^{\prec}_{\bm{a}}=\emptyset$.

Case 2: If $\dim(Z^{\prec_{0}}_{\bm{a}})\geq 1$, let $\prec$ be any strict
partial order in $\mathcal{O}$. Let $p\in Z^{\prec}_{\bm{a}}$. Let
$S(p)=\\{(\sigma_{i},\sigma_{j})\mid p\in
I_{\bm{a}}(\sigma_{i},\sigma_{j})\\}$. By the same argument as in the proof of
Lemma A.7, there is a neighborhood $U$ of $p$, a set
$\\{H(\sigma_{i},\sigma_{j})\\}_{(\sigma_{i},\sigma_{j})\in S(p)}$ of
hyperplanes in $\mathbb{R}^{n}$, and a homeomorphism $\phi:U\to\mathcal{B}$,
where $\mathcal{B}$ is the open unit $n$-ball, such that

$\phi\Big{(}\bigcap_{(\sigma_{i},\sigma_{j})\in
S^{\prime}(p)}I_{\bm{a}}(\sigma_{i},\sigma_{j})\cap
U\Big{)}=\bigcap_{(\sigma_{i},\sigma_{j})\in
S^{\prime}(p)}H(\sigma_{i},\sigma_{j})\cap\mathcal{B}$

for all $S^{\prime}(p)\subseteq S(p)$. See Figure 8.

Because $M_{\bm{a},i}\pitchfork M_{\bm{a},j}$ for all $i\neq j$, we have that
$\mathcal{B}\setminus H(\sigma_{i},\sigma_{j})$ is the disjoint union of open
sets $W_{1}(\sigma_{i},\sigma_{j})$ and $W_{2}(\sigma_{i},\sigma_{j})$ such
that

$\displaystyle f_{\bm{a}}(\sigma_{i},p^{\prime})$
$\displaystyle<f_{\bm{a}}(\sigma_{j},p^{\prime})\qquad\text{for all
}p^{\prime}\in\phi^{-1}(W_{1}(\sigma_{i},\sigma_{j}))\,,$ $\displaystyle
f_{\bm{a}}(\sigma_{j},p^{\prime})$
$\displaystyle<f_{\bm{a}}(\sigma_{i},p^{\prime})\qquad\text{for all
}p^{\prime}\in\phi^{-1}(W_{2}(\sigma_{i},\sigma_{j}))$

for all $(\sigma_{i},\sigma_{j})\in S(p)$. For each
$(\sigma_{i},\sigma_{j})\in S(p)$, define the set $V(\sigma_{i},\sigma_{j})$
as in (29), and define the set $V$ as in (30). The set $\phi^{-1}(V)$ is a
nonempty subset of $U\cap Z^{\prec_{0}}_{\bm{a}}$. This implies that $p$ is a
limit point of $Z^{\prec_{0}}_{\bm{a}}$, so
$Z_{\bm{a}}^{\prec_{0}}\subseteq\overline{Z^{\prec_{0}}_{\bm{a}}}$. Because
$\prec$ is not the same as $\prec_{0}$, we have that $Z^{\prec}_{\bm{a}}\cap
Z^{\prec_{0}}_{\bm{a}}=\emptyset$. Therefore,
$Z_{\bm{a}}^{\prec_{0}}\subseteq\partial Z^{\prec_{0}}_{\bm{a}}$ and

$\bigcup_{\prec\text{ in }\mathcal{O}}Z^{\prec}_{\bm{a}}\subseteq\partial
Z^{\prec_{0}}_{\bm{a}}\,.$

Now suppose that $p$ is in the complement of
$Z^{\prec_{0}}_{\bm{a}}\cup\Big{(}\bigcup_{\prec\text{ in
}\mathcal{O}}Z^{\prec}_{\bm{a}}\Big{)}$. Because $\prec_{f_{\bm{a}}(\cdot,p)}$
is not the same as $\prec_{0}$ or any $\prec$ in $\mathcal{O}$, there is a
pair $(\sigma_{i},\sigma_{j})$ of simplices such that
$f(\sigma_{i},p)<f(\sigma_{j},p)$ and either we have
$\sigma_{j}\prec_{0}\sigma_{i}$ or we have $\sigma_{j}\not\prec\sigma_{i}$ and
$\sigma_{i}\not\prec\sigma_{j}$. By continuity of $f$, there is a neighborhood
$U_{\sigma_{i},\sigma_{j}}$ of $p$ such that
$f_{\bm{a}}(\sigma_{i},p^{\prime})<f_{\bm{a}}(\sigma_{j},p^{\prime})$ for all
$p^{\prime}\in U_{\sigma_{i},\sigma_{j}}$. Therefore,
$U_{\sigma_{i},\sigma_{j}}$ is in the complement of $Z^{\prec_{0}}_{\bm{a}}$,
so $p$ is not in $\overline{Z^{\prec_{0}}_{\bm{a}}}$. This implies

$\partial Z^{\prec_{0}}_{\bm{a}}\subseteq\bigcup_{\prec\text{ in
}\mathcal{O}}Z^{\prec}_{\bm{a}}\,,$

which completes the proof. ∎

## References

  * [1] Henry Adams, Tegan Emerson, Michael Kirby, Rachel Neville, Chris Peterson, Patrick Shipman, Sofya Chepushtanova, Eric Hanson, Francis Motta, and Lori Ziegelmeier.  Persistence images: A stable vector representation of persistent homology.  Journal of Machine Learning Research, 18(8):1–35, 2017.
  * [2] Pankaj K. Agarwal, Herbert Edelsbrunner, John Harer, and Yusu Wang.  Extreme elevation on a 2-manifold.  Discrete & Computational Geometry, 36:553–572, 2006.
  * [3] Erik J. Amézquita, Michelle Y. Quigley, Tim Ophelders, Jacob B. Landis, Daniel Koenig, Elizabeth Munch, and Daniel H. Chitwood.  Measuring hidden phenotype: quantifying the shape of barley seeds using the Euler characteristic transform.  in silico Plants, 4(1), 2022.
  * [4] Massimo Ferri Patrizio Frosini Claudia Landi Andrea Cerri, Barbara Di Fabio.  Betti numbers in multidimensional persistent homology are stable functions.  Mathematical Methods in the Applied Sciences, 36(12):1543–1557, 2013.
  * [5] Shreya Arya, Justin Curry, and Sayan Mukherjee.  A sheaf-theoretic construction of shape space.  arXiv:2204.09020, 2022.
  * [6] Omer Bobrowski, Sayan Mukherjee, and Jonathan E. Taylor.  Topological consistency via kernel estimation.  Bernoulli, 23(1):288–328, 2017.
  * [7] Magnus Bakke Botnan and Michael Lesnick.  An introduction to multiparameter persistence.  arxiv:2203.14289, 2022.
  * [8] Gunnar Carlsson and Afra Zomorodian.  The theory of multidimensional persistence.  Discrete and Computational Geometry, 42:71–93, 2007.
  * [9] Andrea Cerri, Marc Ethier, and Patrizio Frosini.  A study of monodromy in the computation of multidimensional persistence.  In Rocio Gonzalez-Diaz, Maria-Jose Jimenez, and Belen Medrano, editors, Discrete Geometry for Computer Imagery, volume 7749, pages 192–202, Berlin, Heidelberg, 2013. Springer.
  * [10] Frédéric Chazal, David Cohen-Steiner, and Quentin Mérigot.  Geometric inference for probability measures.  Foundations of Computational Mathematics, 11:733–751, 2011.
  * [11] Yao-li Chuang, Maria R. D’Orsogna, Daniel Marthaler, Andrea L. Bertozzi, and Lincoln S. Chayes.  State transitions and the continuum limit for a 2D interacting, self-propelled particle system.  Physica D: Nonlinear Phenomena, 232(1):33–47, 2007.
  * [12] Moo K. Chung, Peter Bubenik, and Peter T. Kim.  Persistence diagrams of cortical surface data.  In Jerry L. Prince, Dzung L. Pham, and Kyle J. Myers, editors, Information Processing in Medical Imaging, volume 5636, pages 386–397, Berlin, Heidelberg, 2009. Springer.
  * [13] David Cohen-Steiner, Herbert Edelsbrunner, and John Harer.  Stability of persistence diagrams.  Discrete and Computational Geometry, 37:103–120, 2007.
  * [14] David Cohen-Steiner, Herbert Edelsbrunner, and Dmitriy Morozov.  Vines and vineyards by updating persistence in linear time.  In Proceedings of the Twenty-Second Annual Symposium on Computational Geometry, SCG ’06, pages 119–126, New York, NY, USA, 2006. Association for Computing Machinery.
  * [15] Padraig Corcoran and Christopher B. Jones.  Modelling topological features of swarm behaviour in space and time with persistence landscapes.  IEEE Access, 5:18534–18544, 2017.
  * [16] Justin Curry.  Sheaves, Cosheaves, and Applications.  PhD thesis, University of Pennsylvania, 2014.
  * [17] Justin Curry, Haibin Hang, Washington Mio, Tom Needham, and Osman Berat Okutan.  Decorated merge trees for persistent topology.  Journal of Applied and Computational Topology, 6:371–428, 2022\.
  * [18] Justin Curry, Sayan Mukherjee, and Katharine Turner.  How many directions determine a shape and other sufficiency results for two topological transforms.  Transactions of the American Mathematical Society, Series B, 9:1006–1043, 2022.
  * [19] Herbert Edelsbrunner and John Harer.  Computational Topology: An Introduction.  American Mathematical Society, Providence, RI, 2010.
  * [20] Herbert Edelsbrunner, David Letscher, and Afra Zomorodian.  Topological persistence and simplification.  Discrete & Computational Geometry, 28:511–533, 2022.
  * [21] Robert Ghrist.  Elementary Applied Topology.  Createspace, 1st edition, 2014.
  * [22] Jakob Hansen and Robert Ghrist.  Toward a spectral theory of cellular sheaves.  Journal of Applied. and Computational Topology, 3:315–358, 2019\.
  * [23] Abigail Hickok.  Computing persistence diagram bundles.  arXiv:2210.06424, 2022.
  * [24] Abigail Hickok, Deanna Needell, and Mason A Porter.  Analysis of spatial and spatiotemporal anomalies using persistent homology: Case studies with COVID-19 data.  SIAM J. Math. Data Sci., 4(3):1116–1144, 2022.
  * [25] Woojin Kim and Facundo Mémoli.  Spatiotemporal persistent homology for dynamic metric spaces.  Discrete & Computational Geometry, 66:831–875, 2021.
  * [26] Yanjie Li, Dingkang Wang, Giorgio A. Ascoli, Partha Mitra, and Yusu Wang.  Metrics for comparing neuronal tree shapes based on persistent homology.  PLoS ONE, 12(8):e0182184, 2017.
  * [27] Shawn Martin, Aidan Thompson, Evangelos A. Coutsias, and Jean-Paul Watson.  Topology of cyclo-octane energy landscape.  Journal of Chemical Physics, 132(23):234115, 2010.
  * [28] Nina Otter, Mason A. Porter, Ulrike Tillmann, Peter Grindrod, and Heather A. Harrington.  A roadmap for the computation of persistent homology.  EPJ Data Science, 6:17, 2017.
  * [29] Raul Rabadan and Andrew J. Blumberg.  Topological Data Analysis for Genomics and Evolution: Topology in Biology.  Cambridge University Press, Cambridge, 2019.
  * [30] Kristian Strommen, Matthew Chantry, Joshua Dorrington, and Nina Otter.  A topological perspective on weather regimes.  Climate Dynamics, 2022.
  * [31] Chad M. Topaz, Lori Ziegelmeier, and Tom Halverson.  Topological data analysis of biological aggregation models.  PLoS ONE, 10(5):e0126383, 2015.
  * [32] Katharine Turner, Sayan Mukherjee, and Doug M. Boyer.  Persistent homology transform for modeling shapes and surfaces.  Information and Inference: A Journal of the IMA, 3(4):310–344, 2014\.
  * [33] Katherine Turner.  Representing vineyard modules.  arXiv:2307.06020, 2023.
  * [34] Yusu Wang, Pankaj K. Agarwal, Paul Brown, Herbert Edelsbrunner, and Johannes Rudolph.  Coarse and reliable geometric alignment for protein docking.  Pacific Symposium on Biocomputing, 10:64–75, 2005.
  * [35] Schmuel Weinberger.  The Topological Classification of Stratified Spaces.  Chicago Lectures in Mathematics. The University of Chicago Press, 1994\.
  * [36] Lu Xian, Henry Adams, Chad M. Topaz, and Lori Ziegelmeier.  Capturing dynamics of time-varying data via topology.  Foundations of Data Science, 4:1–36, 2022.