11institutetext: Chair of Process and Data Science (PADS)
RWTH Aachen University, Aachen, Germany
11email: {peeva<EMAIL_ADDRESS>
# Grouping Local Process Models

Viki Peeva  Wil M.P. van der Aalst

###### Abstract

In recent years, process mining emerged as a proven technology to analyze and
improve operational processes. An expanding range of organizations using
process mining in their daily operation brings a broader spectrum of processes
to be analyzed. Some of these processes are highly unstructured, making it
difficult for traditional process discovery approaches to discover a start-to-
end model describing the entire process. Therefore, the subdiscipline of Local
Process Model (LPM) discovery tries to build a set of LPMs, i.e., smaller
models that explain sub-behaviors of the process. However, like other pattern
mining approaches, LPM discovery algorithms also face the problems of model
explosion and model repetition, i.e., the algorithms may create hundreds if
not thousands of models, and subsets of them are close in structure or
behavior. This work proposes a three-step pipeline for grouping similar LPMs
using various process model similarity measures. We demonstrate the usefulness
of grouping through a real-life case study, and analyze the impact of
different measures, the gravity of repetition in the discovered LPMs, and how
it improves after grouping on multiple real event logs.

###### Keywords:

Local process models Model grouping Model clustering Model similarity Process
model comparison.

##  1 Introduction

Process mining is a scientific discipline for discovering, monitoring, and
improving processes via readily-available data from different data management
systems. The three main pillars of process mining are process discovery,
conformance checking, and process enhancement [1]. As the interest in process
mining grows, new applications pose new challenges. One such challenge is
discovering a single start-to-end model for highly unstructured processes
([19, Figure 7]). To resolve this problem, one usually focuses on frequent
behavior because of the $80/20$ rule of data variability. However, in some
domains, especially ones covering human behavior, the rule does not hold and
better solutions are needed. A relatively new field is Local Process Model
(LPM) discovery [19], where the idea is to build smaller process models
explaining fragments of the behavior instead of one overall model. Yet,
current LPM discovery approaches return hundreds or thousands of models for
one event log (_model explosion_), with highly similar models repeating
between them (_model repetition_) as shown in Figure 1. Although this is
desirable in some use cases [7, 14], it does not help with a better
understanding of highly variable processes.

To alleviate this problem, in this work, we propose a pipeline that groups
similar LPMs, and for each group, one representative LPM is chosen. By doing
so, highly similar models that describe small differences in behavior are
grouped together, allowing analysts to focus on the bigger picture by
examining a smaller diverse set of LPMs and only dive deeper into the
differences when necessary. More specifically, we start with an LPM discovery
approach that returns a set of LPMs. These LPMs are then clustered such that
model similarity, using different process model similarity measures, is
measured, and for each cluster, a representative LPM is chosen. We evaluate
the proposed approach on multiple event logs by comparing model diversity
between the originally returned set of LPMs and the representative set
obtained after grouping. Additionally, we demonstrate the benefit of
clustering LPMs by inspecting a smaller set of models on the BPIC2012-res10939
event log.

((a)) Three highest ranked LPMs discovered by [19].

((b)) Three highest ranked LPMs discovered by [16].

Figure 1: LPMs discovered using [19] and [16] on the filtered and transformed
BPIC2012 event log for resource $10939$ as explained in [19].

The rest of the paper is structured as follows. In Section 2, we introduce the
needed preliminaries to follow the rest of the paper. Section 3 introduces
what LPMs are and in Section 4 we present different process model similarity
measures. We explain the framework in Section 5 and we present the obtained
results in Section 6. We conclude the paper with final remarks in Section 7.

##  2 Preliminaries

###  2.1 General

We define sets ($X=\\{a,b\\}$), multisets ($M=[a^{2},b^{3}]$), sequences
($\sigma=\langle a,b,c\rangle$), and tuples ($t=(a,b,c)$) as usual. Given a
set $X$, $\mathcal{P}(X)$ is the power set of $X$, $X^{*}$ represents the set
of all sequences over $X$, and $\mathbb{M}(X)$ is the set of all multisets
over $X$. We use $\sigma(i)$ to denote the $i$-th element of the sequence
$\sigma$ and $M(a)=2$ to denote that item $a$ appears twice in the multiset
$M$.

We use $f(X)=\\{f(x)|x\in X\\}$ (and $f(\sigma)=\langle
f(\sigma(1)),f(\sigma(2)),...,f(\sigma(n))\rangle$) to apply the function $f$
to every element in the set $X$ (the sequence $\sigma$) and
$f_{\upharpoonright_{X}}$ (respectively $\sigma_{\upharpoonright_{X}}$) to
denote the projection of the function $f$ (respectively the sequence $\sigma$)
on the set $X$.

###  2.2 Process Mining

Normally, the collected data used for process analysis is transformed in the
form of _event logs_. Hence, in Definition 1, we formally define _traces_ and
_event logs_. Note that although traces are usually defined as sequences of
events, in this work, we are only interested in the activity executed by each
event.

######  Definition 1 (Trace, Event Log)

Given the universe of activities $\mathcal{A}$, we define
$\rho\in\mathcal{A}^{*}$ as a _trace_ , and $L\in\mathbb{M}(\mathcal{A}^{*})$
as an _event log_.

In Definition 2, we define _labeled Petri nets_. Note that a transition $t\in
T$ with $l(t)=\tau$ is called silent and that there may be duplicate
transitions $t_{1},t_{2}\in T$ such that $l(t_{1})=l(t_{2})$.

######  Definition 2 (Labeled Petri net)

A _labeled Petri net_ $N=(P,T,F,l)$ is a tuple, where $P$ is a set of places
and $T$ is a set of transitions such that $P\cap T=\emptyset$.
$F\subseteq(P\times T)\cup(T\times P)$ is the flow relation, and
$l:T\to\mathcal{A}\cup\\{\tau\\}$ the labeling function.

Now, given a node $x\in P\cup T$, we define the _preset_ of $x$ as $\bullet
x=\\{y\in P\cup T|(y,x)\in F\\}$ and the _postset_ of $x$ as $x\bullet=\\{y\in
P\cup T|(x,y)\in F\\}$.

To attach behavior to labeled Petri nets we use a _marking_ and the _firing
rule_. A marking $M$ denotes the state of a Petri net as a multiset of places
($M\in\mathbb{M}(P)$) and the firing rule allows for changes between states
(i.e., markings). Given a marking $M$, a transition $t$ is _enabled_ in the
marking $M$ if and only if $\bullet t\subseteq M$. If a transition $t$ is
enabled in the marking $M$, it can fire and change the state of the net to a
new marking $M^{\prime}=(M\setminus\bullet t)\cup t\bullet$. We write
$M\xrightarrow{t}M^{\prime}$. A sequence of transitions $\sigma=\langle
t_{1},\dots,t_{n}\rangle\in T^{*}$ is enabled in $M$ and by firing it marking
$M^{\prime}$ is reached if and only if there exist $M_{0}$, $M_{1}$, $\dots$,
$M_{n}$ such that $M_{0}=M$, $M_{n}=M^{\prime}$, and
$M_{i-1}\xrightarrow{t_{i}}M_{i}$ for $1\leq i\leq n$. We write
$M\xrightarrow{\sigma}M^{\prime}$.

Now, we formally define an _accepting Petri net_ in Definition 3 and the set
of all its firing sequences in Definition 4.

######  Definition 3 (Accepting Labeled Petri Net)

An _accepting labeled Petri net_ is a triple $(N,M_{i},M_{f})$ such that
$N=(P,T,F,l)$ is a labeled Petri net, $M_{i}\in\mathbb{M}(P)$ is the initial
marking, and $M_{f}\in\mathbb{M}(P)$ is the final marking.

######  Definition 4 (Complete Firing Sequences)

Let $\textrm{AN}=(N,M_{i},M_{f})$ be an accepting Petri net,
$\mathcal{F}(\textrm{AN})=\\{\sigma\in
T^{*}|M_{i}\xrightarrow{\sigma}M_{f}\\}$ is the set of complete firing
sequences for AN.

##  3 Local Process Models

In contrast to process discovery, whose task is to discover one model that
explains the traces of an event log from start to end, LPM discovery tries to
mine a set of models each matching some particular sub-behavior represented by
subsequences in the event log.

LPMs were first introduced in [19] as a replacement for process discovery of
highly unstructured processes. However, afterward, the use cases where LPMs
are used expanded (e.g., [6, 7, 10, 12, 13, 14, 17]) and multiple approaches
and extensions for LPM discovery followed [3, 16, 5].

All existing approaches [3, 16, 19], with the exception of [5], suffer from
the _model explosion_ problem. The approach in [5] first finds common
subsequences and then discovers models on them. This, however, makes it
predisposed to similar problems as the traditional process discovery
approaches and restricts the set of LPMs use-case scenarios the approach can
be applied to. Still, as everyone else, they are prone to the _model
repetition_ problem. The approach in [19] incrementally extends process trees
by adding new nodes, in [3] two existing LPMs (represented with process trees)
differing only in one node are joined together to create a larger LPM. In the
new model, the differing nodes are added as children to one of the process
tree operators. Finally, in [16], LPMs are created by joining place nets
together. This makes it clear that all approaches would build highly similar,
i.e., repetitive models. Additionally, if one focuses on frequent behavior,
the highly similar models would all explain highly similar behavior making
highly-ranked models contain clusters of repetitive models. The
implementations of [19] and [16] offer a rudimentary grouping of the models.
However, it becomes evident this is not sufficient when one considers human
analysts manually inspecting and analyzing hundred of LPMs. Therefore, with
this work, we try to alleviate this shortcoming of LPM discovery approaches.

In this work, we focus on LPMs discovered with [16]. Therefore, although LPMs
can, in general, be represented by any modeling language (Petri nets, process
trees, BPMNs, etc.), in this work we restrict to a subclass of accepting
labeled Petri nets. We show a few example LPMs in Figure 1(b) and we give a
formal definition in Definition 5. We use $T_{in}=\\{t\in T|\bullet
t=\emptyset\\}$ to denote the transitions that have an empty preset and we
call them _unrestricted transitions_. We define the set of complete valid
firing sequences of such LPMs in Definition 6 by restricting that each place
in the net can receive at most one token from unrestricted transitions.

######  Definition 5 (Local Process Models)

A _Local Process Model_ (LPM) is an accepting labeled Petri net
$\textit{lpm}=(N_{\textit{lpm}},M_{i},M_{f})$ such that
$N_{\textit{lpm}}=(P,T,F,l)$ is a labeled Petri net that satisfies the
following restrictions:

  1. 1.

$\forall_{x,x^{\prime}\in P\cup T}\,\exists_{\langle
x_{1},\dots,x_{n}\rangle}(x=x_{1}\land x^{\prime}=x_{n}\land\forall_{1\leq
i<n}((x_{i},x_{i+1})\in F)\lor(x_{i+1},x_{i})\in F))$, i.e., there is only one
connected component, and

  2. 2.

$\forall_{p\in P}(\bullet p\neq\emptyset\land p\bullet\neq\emptyset)$, i.e.,
each place has at least one incoming and one outgoing arc,

and $M_{i}\in\mathbb{M}(P)$ and $M_{f}\in\mathbb{M}(P)$ are the initial and
final marking. We use $\mathbb{U}_{\textit{LPM}}$ to denote the universe of
such LPMs.

######  Definition 6 (Local Process Model Behavior)

Given an LPM $\textit{lpm}=(N_{\textit{lpm}},M_{i},M_{f})$ such that
$N_{\textit{lpm}}=(P,T,F,l)$, we define
$\mathcal{F}_{\textit{LPM}}(\textit{lpm})=\\{\sigma\in\mathcal{F}(\textit{lpm})|\forall_{1\leq
i<j\leq|\sigma|}(\sigma(i)\in T_{in}\land\sigma(j)\in
T_{in}\implies\sigma(i)\bullet\cap\sigma(j)\bullet=\emptyset)\\}$ to be all
valid complete firing sequences of lpm.

The _language_ of an LPM lpm is obtained by projecting all valid complete
firing sequences on the transition labels and removing $\tau$-skips, i.e.,
$\mathcal{L}(\textit{lpm})=\\{l(\sigma)_{\upharpoonright_{\mathcal{A}}}|\sigma\in\mathcal{F}_{\textit{LPM}}(\textit{lpm})\\}$.
We use
$\mathcal{L}^{n}(\textit{lpm})=\\{l(\sigma)_{\upharpoonright_{\mathcal{A}}}|\sigma\in\mathcal{F}_{\textit{LPM}}(\textit{lpm})\land|\sigma|\leq
n\\}$ to denote the language restricting to complete firing sequences of
length at most $n$. We can use the language to measure conformance with
respect to an event log $L$ and rank the LPMs. The ranking can take into
consideration different quality measures, such as fitness, precision, and
simplicity. We write
$\textit{rank}_{L}\in\mathbb{U}_{\textit{LPM}}\not\to\mathbb{N}$ to denote a
ranking function, and $\mathbb{U}_{\textit{rank}}$ to denote the universe of
all such ranking functions.

We later use these definitions to extract features from the LPMs and formalize
the different similarity measures.

##  4 Process Model Similarity Measures

To get an overview of existing similarity measures, we considered multiple
survey papers [8, 9, 18, 20, 4]. Although there can be small differences in
how they categorize different similarity measures, all of them agree, the
basic split is into measures that compare the structure of the process model
and those that compare the behavior. Subsequently, one can consider the level
of abstraction used, e.g., complete language versus weak order relations.
Therefore, we choose five representative similarity measures. Before
introducing the specific measures, we first define what a similarity measure
is in Definition 7.

######  Definition 7 (Similarity Measure)

A _similarity measure_
$\mathit{sim}_{\mathit{name}}\in\mathbb{U}_{\textit{LPM}}\times\mathbb{U}_{\textit{LPM}}\to[0,1]$
is a function that calculates the similarity between two LPMs. We use
$`\mathit{name}`$ to distinguish a specific measure, and $\mathbb{U}_{sim}$ to
denote the universe of all similarity measures.

To introduce the similarity measures, we assume we are given two LPMs
$\textit{lpm}_{A}=(N^{A}_{\textit{lpm}},[\hskip 1.00006pt\hskip
1.00006pt],[\hskip 1.00006pt\hskip 1.00006pt])$ s.t.
$N^{A}_{\textit{lpm}}=(P_{A},T_{A},F_{A},l_{A})$ and
$\textit{lpm}_{B}=(N^{B}_{\textit{lpm}},[\hskip 1.00006pt\hskip
1.00006pt],[\hskip 1.00006pt\hskip 1.00006pt])$ s.t.
$N^{B}_{\textit{lpm}}=(P_{B},T_{B},F_{B},l_{B})$. In the following, we
illustrate the measures we use in this work with the help of
$\textit{lpm}_{A}$ and $\textit{lpm}_{B}$.

_Transition label comparison_ is the most simple measure we investigate. The
measure calculates the transition label overlap between the models.

$\mathit{sim}_{\textit{transition}}(\textit{lpm}_{A},\textit{lpm}_{B})=\frac{2*|l_{A}(T_{A})\cap
l_{B}(T_{B})|}{|l_{A}(T_{A})|+|l_{B}(T_{B})|}$

_Node comparison_ is somewhat more complex, in that it includes place overlap
as well. We use this measure to represent structural measures using
abstraction. The measure calculates the similarity between two models by
combining transition label comparison and place matching between the nets. We
assign to each pair of places a matching gain
$g(p_{1},p_{2})=\frac{1}{2}*\frac{2*|l_{A}(\bullet p_{1})\cap l_{B}(\bullet
p_{2})|}{|l_{A}(\bullet p_{1})|+|l_{B}(\bullet
p_{2})|}+\frac{1}{2}*\frac{2*|l_{A}(p_{1}\bullet)\cap
l_{B}(p_{2}\bullet)|}{|l_{A}(p_{1}\bullet)|+|l_{B}(p_{2}\bullet)|}$ and we use
the Hungarian algorithm [11] to solve the assignment problem. We use
$G_{\textit{places}}$ to represent the gain of the optimal assignment. Then,
we define the measure as

$\mathit{sim}_{\textit{node}}(\textit{lpm}_{A},\textit{lpm}_{B})=\frac{2*|l_{A}(T_{A})\cap
l_{B}(T_{B})|+2*G_{\textit{places}}}{|l_{A}(T_{A})|+|l_{B}(T_{B})|+|P_{A}|+|P_{B}|}$

_Eventually-follow graph similarity_ is a behavioral abstraction measure that
measures the overlap of the eventually-follows relation in the languages of
the two models. We calculate it as

$\mathit{sim}_{\textit{efg}}^{n}(\textit{lpm}_{A},\textit{lpm}_{B})=\frac{2*|\textit{EF}^{\,n}_{A}\cap\textit{EF}^{\,n}_{B}|}{|\textit{EF}^{\,n}_{A}|+|\textit{EF}^{\,n}_{B}|}$

such that
$\textit{EF}_{A}^{\,n}=\\{(a,b)|\exists_{\rho\in\mathcal{L}^{n}(\textit{lpm}_{A})}(\exists_{1\leq
i<j\leq|\rho|}(a=\rho_{i}\land b=\rho_{j}))\\}$ and $\textit{EF}^{\,n}_{B}$ is
defined correspondingly.

_Full trace matching comparison_ represents the more sophisticated behavioral
measures. We define it as

$sim^{n}_{\textit{full}}(\textit{lpm}_{A},\textit{lpm}_{B})=\frac{2*G_{\textit{traces}}}{|\mathcal{L}^{n}(\textit{lpm}_{A})|+|\mathcal{L}^{n}(\textit{lpm}_{B})|}$

where $G_{\textit{traces}}$ represents the gain of the optimal trace
assignment. To calculate the gain between two traces we invert the normalized
Levenshtein distance.

Finally _graph edit model comparison_ represents sophisticated structural
measures. It calculates model similarity by using the graph edit distance
(ged) as defined in [2], where the node substitution cost is $1$ if the nodes
differ in type, i.e., one is a place and the other transitions, or if the
compared nodes are differently labeled transitions. The node substitution cost
between two places is calculated as $1-g(p_{1},p_{2})$, where $g(p_{1},p_{2})$
is the gain defined as before. The edge substitution cost takes the average of
the node substitution cost between the source and sink nodes of the two edges.
To convert the ged to a similarity measure, we use the formula below.

$sim_{\textit{ged}}(\textit{lpm}_{A},\textit{lpm}_{B})=1-ged(\textit{lpm}_{A},\textit{lpm}_{B})$

In the remainder, we also use the term distance measure, which we always
consider to be the inverse of the similarity, i.e.,
$\textit{dist}_{\textit{name}}(\textit{lpm}_{A},\textit{lpm}_{B})=1-\mathit{sim}_{\textit{name}}(\textit{lpm}_{A},\textit{lpm}_{B})$
for any
$\textit{name}\in\\{\textit{transition},\textit{node},\textit{efg},\textit{full},\textit{ged}\\}$

##  5 Method to Group LPMs

In this work, we propose a three-step pipeline that starts with an event log
and a multitude of process model comparison measures and ends with groups of
similar LPMs, as shown in Figure 2. The first step is discovering LPMs (Step
$1$), which can also be omitted, starting the pipeline with a set of LPMs
instead. Then, the models are clustered such that the similarity between them
is determined by the previously defined process model similarity measures
(Step $2$). Finally, for each cluster, we choose a representative model (Step
$3$).

Figure 2: Illustration of the proposed three-step pipeline.

###  5.1 Local Process Model Discovery (Step 1)

In the first step, we focus on discovering a set of LPMs $\textit{LPM}_{L}$
given an event log $L$. Although multiple approaches are available, in this
work, we use the approach presented in [16]. The produced models are ranked
from highest to lowest using a rank function $\textit{rank}_{L}$ as previously
defined.

###  5.2 Clustering (Step 2)

In the clustering step, we accept a set of LPMs and a similarity measure and
return a set of clusters. We define the _universe of LPM cluster sets_ in
Definition 8, and a _clustering algorithm_ in Definition 9.

######  Definition 8 (Universe of Local Process Model Cluster Sets)

We define
$\mathbb{U}_{\sqcap}=\\{X_{\textit{LPM}}\subseteq\mathcal{P}(\textit{LPM}_{L})|\textit{LPM}_{L}\subseteq\mathbb{U}_{\textit{LPM}}\land\emptyset\not\in
X_{\textit{LPM}}\land\bigcup X_{\textit{LPM}}=\textit{LPM}_{L}\\}$ to be the
universe of LPM cluster sets.

######  Definition 9 (Clustering Algorithm)

We define
$\textit{clust}\in\mathcal{P}(\mathbb{U}_{\textit{LPM}})\times\mathbb{U}_{sim}\not\to\mathbb{U}_{\sqcap}$
to be a _clustering algorithm_. To denote a clustering algorithm given some
set of parameters $P$, we write $\textit{clust}_{P}$.

The goal of the clustering algorithm is to return the LPMs in homogeneous
groups, such that the similarity is high within the individual groups and low
between them. One clustering algorithm can produce different cluster sets for
the same model set based on the parameters $P$. In our work, we focus on
hierarchical clustering and consider distance threshold and linkage as
possible parameters. In particular, we use linkage to determine how the
distance between two clusters containing multiple models is calculated and the
distance threshold to determine the maximum merging distance. For the
traditional hierarchical clustering algorithm, we use the returned clusters in
$\sqcap_{\textit{LPM}_{L}}=\textit{clust}_{P}(\textit{LPM}_{L},sim_{\textit{name}})$
for an LPM set $\textit{LPM}_{L}$ discovered on an event log $L$ and a
similarity measure $sim_{\textit{name}}$ are pairwise disjoint, i.e.,
$\forall_{\textit{LPM}_{i},\textit{LPM}_{j}\in\sqcap_{\textit{LPM}_{L}}}\textit{LPM}_{i}\cap\textit{LPM}_{j}=\emptyset$.
We overload the notation $\sqcap_{\textit{LPM}_{L}}(\textit{lpm})$ to denote
the cluster in the cluster set $\sqcap_{\textit{LPM}_{L}}$ in which the LPM
lpm belongs. That is, it holds
$\textit{lpm}\in\sqcap_{\textit{LPM}_{L}}(\textit{lpm})\in\sqcap_{\textit{LPM}_{L}}$.

###  5.3 Choosing Cluster Representatives (Step 3)

In Step 3, we take a set of LPMs
$\textit{LPM}_{L}\subseteq\mathbb{U}_{\textit{LPM}}$ discovered on an event
log $L$ in Step 1, and a computed cluster set
$\sqcap_{\textit{LPM}_{L}}=\textit{clust}(\textit{LPM}_{L},sim_{\textit{name}})$
from Step 2. We return an LPM set $\sqcap_{\textit{LPM}_{L}}^{\textit{repr}}$
in which we keep only one representative LPM per cluster. In this work, we
choose representative models either by taking the highest-ranked LPM in each
cluster considering some ranking function
$\textit{rank}_{L}\in\mathbb{U}_{\textit{rank}}$ or the LPM with the minimal
mean distance to all other LPMs in the cluster. In Definition 10, we formally
define _representative projection_ as a function that maps a set of LPMs to
one model.

######  Definition 10 (Representative projection)

A _representative projection_
$\textit{repr}\in\mathcal{P}(\mathbb{U}_{\textit{LPM}})\not\to\mathbb{U}_{\textit{LPM}}$
is a function that takes an LPM set $\textit{LPM}_{L}$ and returns one
representative LPM. We use $\textit{repr}_{\textit{rank}}$ and
$\textit{repr}_{\textit{dist}}$ to denote the representation projections based
on the highest ranking and minimal mean distance respectively.

Now, for the set of LPMs $\textit{LPM}_{L}\subseteq\mathbb{U}_{\textit{LPM}}$,
we create the set
$\sqcap_{\textit{LPM}_{L}}^{\textit{repr}_{x}}=\\{\textit{repr}_{x}(\textit{LPM}_{i})|\textit{LPM}_{i}=\sqcap_{\textit{LPM}_{L}}(\textit{lpm})\land\textit{lpm}\in\textit{LPM}_{L}\\}$
and we call it the _cluster representatives_ , where
$x\in\\{\textit{rank},\textit{dist}\\}$. This way, we significantly reduce the
number of LPMs from the original set $\textit{LPM}_{L}$, but still keep the
essence of the entire set.

##  6 Evaluation Results

The evaluation is performed on six LPM sets, discovered on real event logs. In
Table 1, we give a summary of the LPM sets and the corresponding event logs
used in the experiments. For clustering, we use the agglomerative clustering
algorithm of the scikit-learn package [15]. For all experiments, we use the
complete linkage and iterate the distance thresholds between $0.1$ and $1.0$.
For each combination of an LPM set, similarity measure, and clustering
algorithm parameter, we rerun the clustering $100$ times, resulting in $30000$
experiments. Whenever single values are shown, the most compact clustering
according to the silhouette score was taken unless otherwise specified. All
used cluster representatives we calculated using
$\textit{repr}_{\textit{dist}}$.

Table 1: Local process model sets used in the evaluation Event Log | LPM set | Number of models
---|---|---
BPI Challenge 2012 | $\textit{LPM}_{\textit{BPIC2012}}$ | $1096$
BPI Challenge 2012 - resource 10939 | $\textit{LPM}_{\textit{BPIC2012-res10939}}$ | $4496$
BPI Challenge 2017 | $\textit{LPM}_{\textit{BPIC2017}}$ | $600$
Sepsis | $\textit{LPM}_{\textit{Sepsis}}$ | $601$
Road Traffic Fine Management | $\textit{LPM}_{\textit{RTFM}}$ | $1694$
Hospital Billing | $\textit{LPM}_{\textit{HB}}$ | $2051$

Due to space limitations, in the remainder, we only show the results of some
of the experiments. All analogous graphs (on other LPM sets, measures,
representative choosing strategies, or parameters), together with all
resources needed to replicate the experiments, can be found on
https://github.com/VikiPeeva/CombiningLPMDandPMSM.

###  6.1 Case Study

We focus on the BPIC2012-res10939 event log in this part of the evaluation. In
[19], Tax et al. showed how we can use LPMs to see different frequently
appearing behavioral patterns that could not be seen on the start-to-end model
because of too unstructured behavior. However, as shown in Figure 1, the
highest-ranked models for both [19] and [16] focus on different behavioral
variants of O_SELECTED, O_CREATED, and O_SENT. Such repetition appears for
lower-ranked models as well. In Figure 3, we show the three highest-ranked
representative LPMs after grouping the original set of LPMs. It is clear that
the behavioral span of these three models is significantly larger than the
behavior described by the three highest-ranked original models discovered by
both Peeva et al. and Tax et al (see Figure 1). If we map back the ranks of
the three representative models to the original set, one would have to
consider $1$, $17$, and $20$ higher ranked, but at the same time, more
repetitive models before reaching them.

Figure 3: The three highest-ranked representative LPMs for BPIC2012-res10939.

###  6.2 Local Process Model Diversity Analysis

In Section 5, we introduced how to reduce a set of LPMs LPM to a subset of
representative models $\sqcap_{\textit{LPM}}^{\textit{repr}}$ given a cluster
set $\sqcap_{\textit{LPM}}$. In this part, we show how significant is the
decrease from the original to the representative set for the most compact
clusterings, and whether the set of $n$ highest-ranked LPMs in the
representative set is more diverse than the set of $n$ highest-ranked LPMs in
the original set.

We start by considering the $5$, $10$, $20$, $50$, $100$, and $500$ highest-
ranked LPMs obtained on each of the event logs, that is, the sets
$\textit{LPM}^{(5)}_{L}$, $\textit{LPM}^{(10)}_{L}$,
$\textit{LPM}^{(20)}_{L}$, $\textit{LPM}^{(50)}_{L}$,
$\textit{LPM}^{(100)}_{L}$, and $\textit{LPM}^{(500)}_{L}$, where $L$
represents the event logs in Table 1. In Figure 4, we illustrate the decrease
in the number of LPMs discovered on the BPIC2012-res10939 and Sepsis event
logs for the different similarity measures. The number $n$, denoting the $n$
highest-ranked models in the original set $\textit{LPM}^{(n)}_{L}$, is shown
on the x-axis and the number of representative models in
$\sqcap^{\textit{repr}_{\textit{dist}}}_{\textit{LPM}^{(n)}_{L}}$, is on the
y-axis. It is clear that according to all similarity measures, the most
compact clusterings of the LPMs for the Sepsis event log tend to have more
clusters. Meaning, the original set already contains more diverse LPMs, and
correspondingly the decrease in the number of models is lower. On the
contrary, when considering the BPIC2012-res10939 event log, it is noticeable
that there is a mismatch between what different similarity measures consider
compact grouping. The node measure prefers a few clusters, while the full
measure favors much more clusters. Nevertheless, in both cases, the most
conservative reduction still reduces the number of models by at least half.
Additionally, it is worth mentioning that although these computations are done
for the most compact clusterings in our experiments, in general, the number of
clusters is something that can be controlled.

Figure 4: The number of models in the original set (x-axis) versus the number
of representative models after clustering (y-axis).

In the second part, we compare the mean distance between all pairs of the $n$
highest-ranked models in the original sets $\textit{LPM}^{(n)}_{L}$, versus
the mean distance between all pairs of the $n$ highest-ranked models in the
representative sets
${(\sqcap^{\textit{repr}_{\textit{dist}}}_{\textit{LPM}_{L}})}^{(n)}$ for
$n=\\{5,10,50,100\\}$. Figure 5 shows the differences between
$\textit{LPM}^{(10)}_{L}$ and
${(\sqcap^{\textit{repr}_{\textit{dist}}}_{\textit{LPM}_{L}})}^{(10)}$ for
each of the event logs and the efg measure. It is clear that in all cases the
mean distance of the representative set is higher than the mean distance on
the original set, meaning the set is more diverse. The highest increase can be
noticed for the BPIC2017 event log and the smallest for the BPIC2012-res10939
event log. The distance increase happens for almost all $n$, measure and event
log combinations, while for a few no significant change could be noticed.

Figure 5: The mean distance between all pairs of LPMs in the original set
$\textit{LPM}^{(10)}_{L}$ versus the cluster representative set
${(\sqcap^{\textit{repr}_{\textit{dist}}}_{\textit{LPM}_{L}})}^{(10)}$ and the
_efg_ measure.

##  7 Conclusion

In this paper, we used process model similarity measures to group similar LPMs
together. We proposed a three-step approach consisting of LPM discovery,
clustering, and choosing LPM cluster representatives. In the evaluation, we
showed how grouping similar LPMs together improves process understandability
on a real-life case study and we showcased LPM repetition decrease and
diversity improvement on six real event logs.

There are numerous possibilites for future work. Currently, we experimented
only on one LPM discovery approach, hence, we can expand this work by
considering LPMs discovered with different algorithms. To further advance the
method, one can also organize the LPMs in each cluster set in hierarchies for
more structured navigation between the models. Additionally, the framework
could be extended with new similarity measures and different clustering
algorithms. Finally, a natural extension would be to test whether LPMs can be
used to compare process model similarity measures in an unsupervised manner.

## Acknowledgment

We thank the Alexander von Humboldt (AvH) Stiftung for supporting our
research. The authors gratefully acknowledge the financial support by the
Federal Ministry of Education and Research (BMBF) for the joint project
AIStudyBuddy (grant no. 16DHBKI016).

## References

  * [1] van der Aalst, W.M.P.: Process Mining - Data Science in Action, Second Edition
  * [2] Abu-Aisheh, Z., Raveaux, R., Ramel, J., Martineau, P.: An exact graph edit distance algorithm for solving pattern recognition problems. In: ICPRAM 2015\. vol. 1, pp. 271–278
  * [3] Acheli, M., Grigori, D., Weidlich, M.: Efficient discovery of compact maximal behavioral patterns from event logs. In: CAiSE 2019
  * [4] Becker, M., Laue, R.: A comparative survey of business process similarity measures. Comput. Ind. 63(2), 148–167
  * [5] Brunings, M., Fahland, D., Verbeek, E.: Discover context-rich local process models (extended abstract). In: ICPM-D 2022
  * [6] Deeva, G., Weerdt, J.D.: Understanding automated feedback in learning processes by mining local patterns. In: BPM 2018 International Workshops. vol. 342, pp. 56–68
  * [7] Delcoucq, L., Lecron, F., Fortemps, P., van der Aalst, W.M.P.: Resource-centric process mining: clustering using local process models. In: SAC ’20: The 35th ACM/SIGAPP Symposium on Applied Computing, online event, [Brno, Czech Republic], March 30 - April 3, 2020. pp. 45–52
  * [8] Dijkman, R.M., van Dongen, B.F., Dumas, M., García-Bañuelos, L., Kunze, M., Leopold, H., Mendling, J., Uba, R., Weidlich, M., Weske, M., Yan, Z.: A short survey on process model similarity. In: Seminal Contributions to Information Systems Engineering, 25 Years of CAiSE, pp. 421–427
  * [9] Dumas, M., García-Bañuelos, L., Dijkman, R.M.: Similarity search of business process models. IEEE Data Eng. Bull. 32(3), 23–28
  * [10] Kirchner, K., Markovic, P.: Unveiling hidden patterns in flexible medical treatment processes - A process mining case study. In: ICDSST 2018. vol. 313, pp. 169–180
  * [11] Kuhn, H.W.: The hungarian method for the assignment problem. In: 50 Years of Integer Programming 1958-2008 - From the Early Years to the State-of-the-Art, pp. 29–47
  * [12] Leemans, S.J.J., Tax, N., ter Hofstede, A.H.M.: Indulpet miner: Combining discovery algorithms. In: OTM 2018. vol. 11229, pp. 97–115
  * [13] Mannhardt, F., de Leoni, M., Reijers, H.A., van der Aalst, W.M.P., Toussaint, P.J.: Guided process discovery - A pattern-based approach. Inf. Syst. 76, 1–18
  * [14] Mannhardt, F., Tax, N.: Unsupervised event abstraction using pattern abstraction and local process models. In: RADAR+EMISA 2017. vol. 1859, pp. 55–63
  * [15] Pedregosa, F., et al.: Scikit-learn: Machine learning in Python. Journal of Machine Learning Research 12, 2825–2830
  * [16] Peeva, V., Mannel, L.L., van der Aalst, W.M.P.: From place nets to local process models. In: PETRI NETS 2022
  * [17] Pijnenborg, P., Verhoeven, R., Firat, M., Laarhoven, H.v., Genga, L.: Towards evidence-based analysis of palliative treatments for stomach and esophageal cancer patients: a process mining approach. In: ICPM 2021. pp. 136–143
  * [18] Schoknecht, A., Thaler, T., Fettke, P., Oberweis, A., Laue, R.: Similarity of business process models - A state-of-the-art analysis. ACM Comput. Surv. 50(4), 52:1–52:33
  * [19] Tax, N., Sidorova, N., Haakma, R., van der Aalst, W.M.P.: Mining local process models. J. Innov. Digit. Ecosyst. 3(2), 183–196
  * [20] Thaler, T., Schoknecht, A., Fettke, P., Oberweis, A., Laue, R.: A comparative analysis of business process model similarity measures. In: BPM 2016 International Workshops. vol. 281, pp. 310–322


suppression of small carbonaceous grains in gas-rich galaxies, which
guarantees the good agreement with the extinction curves of the Magellanic
Clouds.

Those simulations have been performed in a idealized context without
considering the effect of fresh gas replenishment by halo-scale gas accretion.
A natural direct extension of this work is to test the validity of the dust
model in fully cosmological hydrodynamical simulations to understand the
influence of cosmic infall and mergers on the properties of dust. In
particular, such cosmological simulations could be used to understand the
cosmological build up of dust in galaxies, and test the fraction of galaxies
with obscured star formation (Magnelli et al. 2020; Pozzi et al. 2021;
Fudamoto et al. 2021; Inami et al. 2022). In this work, we have limited
ourselves to testing extinction curves of simulated galaxies, which gives a
direct insight on dust properties. Although attenuation curves are the result
of the complex interplay between the dust properties, and the ISM and stellar
distributions (Narayanan et al. 2018), the flurry of observational evidence
might serve as an important testbed for the cosmic evolution of dust
properties.

The dust model introduced in this paper is currently extended to track PAHs,
as well as to include a self-consistent coupling of the dust and ISM non-
equilibrium thermo-chemistry in ramses-rtz (Katz 2022) with radiation-
hydrodynamics (Rodríguez Montero, et al., in prep.). This ‘Dusty-PRISM’ model
would be capable of exploring the influence of radiation, chemistry, gas
properties and dust grains on the properties of PAHs, shedding light on the
origin of the correlations between mid-IR bands and the properties of the ISM
across cosmic time.

## Acknowledgments

We thank Hakim Atek, Benoît Commerçon, Pierre Cox, Frédéric Galliano, Pierre
Guillard, Patrick Hennebelle, Harley Katz, Guillaume Laibe, Ugo Lebreuilly,
Guillaume Pineau des Forêts, and Nicolas Prantzos for useful discussions. This
work has made use of the Infinity cluster on which the simulation was run and
post-processed, hosted by the Institut d’Astrophysique de Paris. We warmly
thank S. Rouberol for running it smoothly. FRM is supported by the Wolfson
Harrison UK Research Council Physics Scholarship. This project has received
funding from the European Research Council (ERC) under the European Union’s
Horizon 2020 research and innovation programme (grant agreement No 693024). MT
acknowledges support from the NWO grant 016.VIDI.189.162 (”ODIN”). SKY
acknowledges support from the Korean National Research Foundation
(2020R1A2C3003769, 2022R1A6A1A03053472). Part of the interpretation was based
on the calculations using KIST’s Nurion (KSC-2022-CRE-0088, KSC-2022-CRE-0344,
KSC-2023-CRE-0343).

## References

  * Aoyama et al. (2019) Aoyama, S., Hirashita, H., Lim, C.-F., et al. 2019, MNRAS, 484, 1852
  * Aoyama et al. (2020) Aoyama, S., Hirashita, H., & Nagamine, K. 2020, MNRAS, 491, 3844
  * Aoyama et al. (2017) Aoyama, S., Hou, K.-C., Shimizu, I., et al. 2017, MNRAS, 466, 105
  * Asano et al. (2013a) Asano, R. S., Takeuchi, T. T., Hirashita, H., & Inoue, A. K. 2013a, Earth, Planets and Space, 65, 213
  * Asano et al. (2013b) Asano, R. S., Takeuchi, T. T., Hirashita, H., & Nozawa, T. 2013b, MNRAS, 432, 637
  * Asplund et al. (2009) Asplund, M., Grevesse, N., Sauval, A. J., & Scott, P. 2009, ARA&A, 47, 481
  * Bakes & Tielens (1994) Bakes, E. L. O. & Tielens, A. G. G. M. 1994, ApJ, 427, 822
  * Bekki (2013) Bekki, K. 2013, MNRAS, 432, 2298
  * Bohren & Huffman (1983) Bohren, C. F. & Huffman, D. R. 1983, Absorption and scattering of light by small particles
  * Boquien et al. (2019) Boquien, M., Burgarella, D., Roehlly, Y., et al. 2019, A&A, 622, A103
  * Brooker et al. (2022) Brooker, E. S., Stangl, S. M., Mauney, C. M., & Fryer, C. L. 2022, ApJ, 931, 85
  * Brüns et al. (2005) Brüns, C., Kerp, J., Staveley-Smith, L., et al. 2005, A&A, 432, 45
  * Calzetti et al. (2000) Calzetti, D., Armus, L., Bohlin, R. C., et al. 2000, ApJ, 533, 682
  * Camps & Baes (2015) Camps, P. & Baes, M. 2015, Astronomy and Computing, 9, 20
  * Cardelli et al. (1989) Cardelli, J. A., Clayton, G. C., & Mathis, J. S. 1989, ApJ, 345, 245
  * Casey et al. (2014) Casey, C. M., Narayanan, D., & Cooray, A. 2014, Phys. Rep, 541, 45
  * Chaabouni et al. (2012) Chaabouni, H., Bergeron, H., Baouche, S., et al. 2012, A&A, 538, A128
  * Chabrier (2005) Chabrier, G. 2005, The Initial Mass Function: From Salpeter 1955 to 2005, ed. E. Corbelli, F. Palla, & H. Zinnecker, Vol. 327, 41
  * Chevallard & Charlot (2016) Chevallard, J. & Charlot, S. 2016, MNRAS, 462, 1415
  * Choban et al. (2022) Choban, C. R., Kereš, D., Hopkins, P. F., et al. 2022, MNRAS, 514, 4506
  * Choban et al. (2024) Choban, C. R., Kereš, D., Sandstrom, K. M., et al. 2024, arXiv e-prints, arXiv:2401.04766
  * Chokshi et al. (1993) Chokshi, A., Tielens, A. G. G. M., & Hollenbach, D. 1993, ApJ, 407, 806
  * Choudhury et al. (2021) Choudhury, S., de Grijs, R., Bekki, K., et al. 2021, MNRAS, 507, 4752
  * Choudhury et al. (2018) Choudhury, S., Subramaniam, A., Cole, A. A., & Sohn, Y. J. 2018, MNRAS, 475, 4279
  * Clark et al. (2019) Clark, P. C., Glover, S. C. O., Ragan, S. E., & Duarte-Cabral, A. 2019, MNRAS, 486, 4622
  * Cole et al. (2005) Cole, A. A., Tolstoy, E., Gallagher, John S., I., & Smecker-Hane, T. A. 2005, AJ, 129, 1465
  * Compiègne et al. (2011) Compiègne, M., Verstraete, L., Jones, A., et al. 2011, A&A, 525, A103
  * Croiset et al. (2016) Croiset, B. A., Candian, A., Berné, O., & Tielens, A. G. G. M. 2016, A&A, 590, A26
  * Cuppen & Herbst (2007) Cuppen, H. M. & Herbst, E. 2007, ApJ, 668, 294
  * Curti et al. (2020) Curti, M., Mannucci, F., Cresci, G., & Maiolino, R. 2020, MNRAS, 491, 944
  * Dalgarno & McCray (1972) Dalgarno, A. & McCray, R. A. 1972, ARA&A, 10, 375
  * De Cia et al. (2016) De Cia, A., Ledoux, C., Mattsson, L., et al. 2016, A&A, 596, A97
  * De Cia et al. (2013) De Cia, A., Ledoux, C., Savaglio, S., Schady, P., & Vreeswijk, P. M. 2013, A&A, 560, A88
  * De Vis et al. (2017) De Vis, P., Gomez, H. L., Schofield, S. P., et al. 2017, MNRAS, 471, 1743
  * De Vis et al. (2019) De Vis, P., Jones, A., Viaene, S., et al. 2019, A&A, 623, A5
  * Desert et al. (1990) Desert, F. X., Boulanger, F., & Puget, J. L. 1990, A&A, 237, 215
  * Devriendt et al. (1999) Devriendt, J. E. G., Guiderdoni, B., & Sadat, R. 1999, A&A, 350, 381
  * Draine (2003) Draine, B. T. 2003, ARA&A, 41, 241
  * Draine et al. (2007) Draine, B. T., Dale, D. A., Bendo, G., et al. 2007, ApJ, 663, 866
  * Draine & Lee (1984) Draine, B. T. & Lee, H. M. 1984, ApJ, 285, 89
  * Draine & Li (2007) Draine, B. T. & Li, A. 2007, ApJ, 657, 810
  * Draine & Salpeter (1979) Draine, B. T. & Salpeter, E. E. 1979, ApJ, 231, 77
  * Dubois et al. (2021) Dubois, Y., Beckmann, R., Bournaud, F., et al. 2021, A&A, 651, A109
  * Dwek (1998) Dwek, E. 1998, ApJ, 501, 643
  * Dwek & Werner (1981) Dwek, E. & Werner, M. W. 1981, ApJ, 248, 138
  * Egorov et al. (2023) Egorov, O. V., Kreckel, K., Sandstrom, K. M., et al. 2023, ApJ, 944, L16
  * Federrath & Klessen (2012) Federrath, C. & Klessen, R. S. 2012, ApJ, 761, 156
  * Fioc & Rocca-Volmerange (1997) Fioc, M. & Rocca-Volmerange, B. 1997, A&A, 326, 950
  * Fioc & Rocca-Volmerange (2019) Fioc, M. & Rocca-Volmerange, B. 2019, A&A, 623, A143
  * Fitzpatrick & Massa (2007) Fitzpatrick, E. L. & Massa, D. 2007, ApJ, 663, 320
  * Fudamoto et al. (2020) Fudamoto, Y., Oesch, P. A., Faisst, A., et al. 2020, A&A, 643, A4
  * Fudamoto et al. (2021) Fudamoto, Y., Oesch, P. A., Schouws, S., et al. 2021, Nature, 597, 489
  * Galametz et al. (2011) Galametz, M., Madden, S. C., Galliano, F., et al. 2011, A&A, 532, A56
  * Galliano et al. (2018) Galliano, F., Galametz, M., & Jones, A. P. 2018, ARA&A, 56, 673
  * Galliano et al. (2021) Galliano, F., Nersesian, A., Bianchi, S., et al. 2021, A&A, 649, A18
  * Geen et al. (2015) Geen, S., Rosdahl, J., Blaizot, J., Devriendt, J., & Slyz, A. 2015, MNRAS, 448, 3248
  * Girardi et al. (2000) Girardi, L., Bressan, A., Bertelli, G., & Chiosi, C. 2000, A&AS, 141, 371
  * Gjergo et al. (2018) Gjergo, E., Granato, G. L., Murante, G., et al. 2018, MNRAS, 479, 2588
  * Gordon et al. (1997) Gordon, K. D., Calzetti, D., & Witt, A. N. 1997, ApJ, 487, 625
  * Gordon et al. (2003) Gordon, K. D., Clayton, G. C., Misselt, K. A., Landolt, A. U., & Wolff, M. J. 2003, ApJ, 594, 279
  * Granato et al. (2000) Granato, G. L., Lacey, C. G., Silva, L., et al. 2000, ApJ, 542, 710
  * Granato et al. (2021) Granato, G. L., Ragone-Figueroa, C., Taverna, A., et al. 2021, MNRAS, 503, 511
  * Grassi et al. (2014) Grassi, T., Bovino, S., Schleicher, D. R. G., et al. 2014, MNRAS, 439, 2386
  * Graziani et al. (2020) Graziani, L., Schneider, R., Ginolfi, M., et al. 2020, MNRAS, 494, 1071
  * Guhathakurta & Draine (1989) Guhathakurta, P. & Draine, B. T. 1989, ApJ, 345, 230
  * Guillard et al. (2009) Guillard, P., Boulanger, F., Pineau Des Forêts, G., & Appleton, P. N. 2009, A&A, 502, 515
  * Hennebelle & Chabrier (2011) Hennebelle, P. & Chabrier, G. 2011, ApJ, 743, L29
  * Hirashita (2015) Hirashita, H. 2015, MNRAS, 447, 2937
  * Hirashita & Aoyama (2019) Hirashita, H. & Aoyama, S. 2019, MNRAS, 482, 2555
  * Hirashita & Murga (2020) Hirashita, H. & Murga, M. S. 2020, MNRAS, 492, 3779
  * Hoang (2020) Hoang, T. 2020, Galaxies, 8, 52
  * Hollenbach et al. (2009) Hollenbach, D., Kaufman, M. J., Bergin, E. A., & Melnick, G. J. 2009, ApJ, 690, 1497
  * Hollenbach & McKee (1979) Hollenbach, D. & McKee, C. F. 1979, ApJS, 41, 555
  * Hou et al. (2019) Hou, K.-C., Aoyama, S., Hirashita, H., Nagamine, K., & Shimizu, I. 2019, MNRAS, 485, 1727
  * Hou et al. (2017) Hou, K.-C., Hirashita, H., Nagamine, K., Aoyama, S., & Shimizu, I. 2017, MNRAS, 469, 870
  * Hu et al. (2021) Hu, C.-Y., Sternberg, A., & van Dishoeck, E. F. 2021, ApJ, 920, 44
  * Hu et al. (2019) Hu, C.-Y., Zhukovska, S., Somerville, R. S., & Naab, T. 2019, MNRAS, 487, 3252
  * Inami et al. (2022) Inami, H., Algera, H. S. B., Schouws, S., et al. 2022, MNRAS, 515, 3126
  * Inoue (2005) Inoue, A. K. 2005, MNRAS, 359, 171
  * Iwamoto et al. (1999) Iwamoto, K., Brachwitz, F., Nomoto, K., et al. 1999, ApJS, 125, 439
  * Jenkins (2009) Jenkins, E. B. 2009, ApJ, 700, 1299
  * Jones et al. (2017) Jones, A. P., Köhler, M., Ysard, N., Bocchio, M., & Verstraete, L. 2017, A&A, 602, A46
  * Jones et al. (1996) Jones, A. P., Tielens, A. G. G. M., & Hollenbach, D. J. 1996, ApJ, 469, 740
  * Kaiser et al. (2015) Kaiser, R. I., Parker, D. S. N., & Mebel, A. M. 2015, Annual Review of Physical Chemistry, 66, 43
  * Karakas (2010) Karakas, A. I. 2010, MNRAS, 403, 1413
  * Katz (2022) Katz, H. 2022, MNRAS, 512, 348
  * Katz et al. (2022) Katz, H., Liu, S., Kimm, T., et al. 2022, arXiv e-prints, arXiv:2211.04626
  * Kemper et al. (2004) Kemper, F., Vriend, W. J., & Tielens, A. G. G. M. 2004, ApJ, 609, 826
  * Kennicutt (1998) Kennicutt, Robert C., J. 1998, ARA&A, 36, 189
  * Kim et al. (1998) Kim, S., Staveley-Smith, L., Dopita, M. A., et al. 1998, ApJ, 503, 674
  * Kimm & Cen (2014) Kimm, T. & Cen, R. 2014, ApJ, 788, 121
  * Kirchschlager et al. (2022) Kirchschlager, F., Mattsson, L., & Gent, F. A. 2022, MNRAS, 509, 3218
  * Kirchschlager et al. (2023) Kirchschlager, F., Schmidt, F. D., Barlow, M. J., De Looze, I., & Sartorio, N. S. 2023, MNRAS, 520, 5042
  * Kirchschlager et al. (2019) Kirchschlager, F., Schmidt, F. D., Barlow, M. J., et al. 2019, MNRAS, 489, 4465
  * Krumholz & McKee (2005) Krumholz, M. R. & McKee, C. F. 2005, ApJ, 630, 250
  * Le Bourlot et al. (2012) Le Bourlot, J., Le Petit, F., Pinto, C., Roueff, E., & Roy, F. 2012, A&A, 541, A76
  * Lebreuilly et al. (2019) Lebreuilly, U., Commerçon, B., & Laibe, G. 2019, A&A, 626, A96
  * Leger & Puget (1984) Leger, A. & Puget, J. L. 1984, A&A, 137, L5
  * Leitch-Devlin & Williams (1985) Leitch-Devlin, M. A. & Williams, D. A. 1985, MNRAS, 213, 295
  * Lewis et al. (2023) Lewis, J. S. W., Ocvirk, P., Dubois, Y., et al. 2023, MNRAS, 519, 5987
  * Li et al. (2019) Li, Q., Narayanan, D., & Davé, R. 2019, MNRAS, 490, 1425
  * Li et al. (2021) Li, Q., Narayanan, D., Torrey, P., Davé, R., & Vogelsberger, M. 2021, MNRAS, 507, 548
  * Limongi & Chieffi (2018) Limongi, M. & Chieffi, A. 2018, ApJS, 237, 13
  * Lisenfeld & Ferrara (1998) Lisenfeld, U. & Ferrara, A. 1998, ApJ, 496, 145
  * Macciò et al. (2008) Macciò, A. V., Dutton, A. A., & van den Bosch, F. C. 2008, MNRAS, 391, 1940
  * Madden et al. (2006) Madden, S. C., Galliano, F., Jones, A. P., & Sauvage, M. 2006, A&A, 446, 877
  * Magnelli et al. (2020) Magnelli, B., Boogaard, L., Decarli, R., et al. 2020, ApJ, 892, 66
  * Maoz & Mannucci (2012) Maoz, D. & Mannucci, F. 2012, PASA, 29, 447
  * Marassi et al. (2019) Marassi, S., Schneider, R., Limongi, M., et al. 2019, MNRAS, 484, 2587
  * Markov et al. (2024) Markov, V., Gallerani, S., Ferrara, A., et al. 2024, arXiv e-prints, arXiv:2402.05996
  * Mathis et al. (1977) Mathis, J. S., Rumpl, W., & Nordsieck, K. H. 1977, ApJ, 217, 425
  * McKinnon et al. (2016) McKinnon, R., Torrey, P., & Vogelsberger, M. 2016, MNRAS, 457, 3775
  * McKinnon et al. (2018) McKinnon, R., Vogelsberger, M., Torrey, P., Marinacci, F., & Kannan, R. 2018, MNRAS, 478, 2851
  * Micelotta (2009) Micelotta, E. R. 2009, PhD thesis, -
  * Micelotta et al. (2016) Micelotta, E. R., Dwek, E., & Slavin, J. D. 2016, A&A, 590, A65
  * Min et al. (2007) Min, M., Waters, L. B. F. M., de Koter, A., et al. 2007, A&A, 462, 667
  * Montier & Giard (2004) Montier, L. A. & Giard, M. 2004, A&A, 417, 401
  * Moseley et al. (2023) Moseley, E. R., Teyssier, R., & Draine, B. T. 2023, MNRAS, 518, 2825
  * Narayanan et al. (2018) Narayanan, D., Conroy, C., Davé, R., Johnson, B. D., & Popping, G. 2018, ApJ, 869, 70
  * Narayanan et al. (2023) Narayanan, D., Smith, J. D. T., Hensley, B. S., et al. 2023, ApJ, 951, 100
  * Navarro et al. (1997) Navarro, J. F., Frenk, C. S., & White, S. D. M. 1997, ApJ, 490, 493
  * Noll et al. (2009) Noll, S., Burgarella, D., Giovannoli, E., et al. 2009, A&A, 507, 1793
  * Nozawa et al. (2006) Nozawa, T., Kozasa, T., & Habe, A. 2006, ApJ, 648, 435
  * Ormel et al. (2009) Ormel, C. W., Paszun, D., Dominik, C., & Tielens, A. G. G. M. 2009, A&A, 502, 845
  * Padoan & Nordlund (2011) Padoan, P. & Nordlund, Å. 2011, ApJ, 730, 40
  * Parente et al. (2022) Parente, M., Ragone-Figueroa, C., Granato, G. L., et al. 2022, MNRAS, 515, 2053
  * Parvathi et al. (2012) Parvathi, V. S., Sofia, U. J., Murthy, J., & Babu, B. R. S. 2012, ApJ, 760, 36
  * Pei (1992) Pei, Y. C. 1992, ApJ, 395, 130
  * Pilleri et al. (2012) Pilleri, P., Montillaud, J., Berné, O., & Joblin, C. 2012, A&A, 542, A69
  * Pointecouteau et al. (2009) Pointecouteau, E., da Silva, A., Catalano, A., et al. 2009, Advances in Space Research, 44, 440
  * Poppe & Blum (1997) Poppe, T. & Blum, J. 1997, Advances in Space Research, 20, 1595
  * Popping et al. (2017) Popping, G., Somerville, R. S., & Galametz, M. 2017, MNRAS, 471, 3152
  * Pozzi et al. (2021) Pozzi, F., Calura, F., Fudamoto, Y., et al. 2021, A&A, 653, A84
  * Prantzos et al. (2018) Prantzos, N., Abia, C., Limongi, M., Chieffi, A., & Cristallo, S. 2018, MNRAS, 476, 3432
  * Reizer et al. (2022) Reizer, E., Viskolcz, B., & Fiser, B. 2022, Chemosphere, 291, 132793
  * Rémy-Ruyer et al. (2014) Rémy-Ruyer, A., Madden, S. C., Galliano, F., et al. 2014, A&A, 563, A31
  * Rémy-Ruyer et al. (2015) Rémy-Ruyer, A., Madden, S. C., Galliano, F., et al. 2015, A&A, 582, A121
  * Richings et al. (2022) Richings, A. J., Faucher-Giguère, C.-A., Gurvich, A. B., Schaye, J., & Hayward, C. C. 2022, MNRAS, 517, 1557
  * Roman-Duval et al. (2022) Roman-Duval, J., Jenkins, E. B., Tchernyshyov, K., et al. 2022, ApJ, 928, 90
  * Rosdahl et al. (2017) Rosdahl, J., Schaye, J., Dubois, Y., Kimm, T., & Teyssier, R. 2017, MNRAS, 466, 11
  * Safranek-Shrader et al. (2017) Safranek-Shrader, C., Krumholz, M. R., Kim, C.-G., et al. 2017, MNRAS, 465, 885
  * Salim & Narayanan (2020) Salim, S. & Narayanan, D. 2020, ARA&A, 58, 529
  * Sánchez et al. (2019) Sánchez, S. F., Barrera-Ballesteros, J. K., López-Cobá, C., et al. 2019, MNRAS, 484, 3042
  * Sandstrom et al. (2013) Sandstrom, K. M., Leroy, A. K., Walter, F., et al. 2013, ApJ, 777, 5
  * Sarangi & Cherchneff (2015) Sarangi, A. & Cherchneff, I. 2015, A&A, 575, A95
  * Schneider & Maiolino (2023) Schneider, R. & Maiolino, R. 2023, arXiv e-prints, arXiv:2310.00053
  * Schreiber et al. (2018) Schreiber, C., Elbaz, D., Pannella, M., et al. 2018, A&A, 609, A30
  * Seok et al. (2014) Seok, J. Y., Hirashita, H., & Asano, R. S. 2014, MNRAS, 439, 2186
  * Shivaei et al. (2024) Shivaei, I., Alberts, S., Florian, M., et al. 2024, arXiv e-prints, arXiv:2402.07989
  * Silvia et al. (2010) Silvia, D. W., Smith, B. D., & Shull, J. M. 2010, ApJ, 715, 1575
  * Slavin et al. (2020) Slavin, J. D., Dwek, E., Mac Low, M.-M., & Hill, A. S. 2020, ApJ, 902, 135
  * Sofia et al. (2011) Sofia, U. J., Parvathi, V. S., Babu, B. R. S., & Murthy, J. 2011, AJ, 141, 22
  * Springel et al. (2005) Springel, V., Di Matteo, T., & Hernquist, L. 2005, MNRAS, 361, 776
  * Stanimirović et al. (2004) Stanimirović, S., Staveley-Smith, L., & Jones, P. A. 2004, ApJ, 604, 176
  * Sutherland & Dopita (1993) Sutherland, R. S. & Dopita, M. A. 1993, ApJS, 88, 253
  * Teyssier (2002) Teyssier, R. 2002, A&A, 385, 337
  * Tielens (2013) Tielens, A. G. G. M. 2013, Reviews of Modern Physics, 85, 1021
  * Tielens et al. (1994) Tielens, A. G. G. M., McKee, C. F., Seab, C. G., & Hollenbach, D. J. 1994, ApJ, 431, 321
  * Trebitsch et al. (2021) Trebitsch, M., Dubois, Y., Volonteri, M., et al. 2021, A&A, 653, A154
  * Tsai & Mathews (1995) Tsai, J. C. & Mathews, W. G. 1995, ApJ, 448, 84
  * Vallini et al. (2018) Vallini, L., Pallottini, A., Ferrara, A., et al. 2018, MNRAS, 473, 271
  * Vassiliadis & Wood (1993) Vassiliadis, E. & Wood, P. R. 1993, ApJ, 413, 641
  * Vogelsberger et al. (2019) Vogelsberger, M., McKinnon, R., O’Neil, S., et al. 2019, MNRAS, 487, 4870
  * Weingartner & Draine (1999) Weingartner, J. C. & Draine, B. T. 1999, ApJ, 517, 292
  * Weingartner & Draine (2001a) Weingartner, J. C. & Draine, B. T. 2001a, ApJ, 548, 296
  * Weingartner & Draine (2001b) Weingartner, J. C. & Draine, B. T. 2001b, ApJS, 134, 263
  * Wiseman et al. (2017) Wiseman, P., Schady, P., Bolmer, J., et al. 2017, A&A, 599, A24
  * Witstok et al. (2023) Witstok, J., Shivaei, I., Smit, R., et al. 2023, Nature, 621, 267
  * Witt & Gordon (2000) Witt, A. N. & Gordon, K. D. 2000, ApJ, 528, 799
  * Yan et al. (2004) Yan, H., Lazarian, A., & Draine, B. T. 2004, ApJ, 616, 895
  * Zhukovska (2014) Zhukovska, S. 2014, A&A, 562, A76
  * Zhukovska et al. (2016) Zhukovska, S., Dobbs, C., Jenkins, E. B., & Klessen, R. S. 2016, ApJ, 831, 147
  * Zubko et al. (2004) Zubko, V., Dwek, E., & Arendt, R. G. 2004, ApJS, 152, 211

##  Appendix A Released metallicities and dust

Figure 23: Evolution of the SSP yield adopted in this work for total
metallicity and different individual elements. The blue lines are for the
total elemental release (gas plus dust). Red lines are the contribution from
intermediate stars. Purple lines are the contribution from SNIa. Green lines
are for dust. Lines goes from dark to light for an initial SSP metallicity of
$Z_{\rm ZAS}=10^{-3},10^{-2},10^{-1},1\,\rm Z_{\odot}$.

The time evolution of the resulting chemical and dust yields for a simple
stellar population of different initial metallicities $Z_{\rm
ZAS}=10^{-3},10^{-2},10^{-1},1\,\rm Z_{\odot}$ are shown in Fig. 23 with
assumptions for stellar tracks, IMF, stellar rotations, and dust condensation
efficiencies as described in sections 2.4 and 3.1. It shows that the total
mass return, and that of O, Mg, Si, S and Ne are overall largely dominated by
SNII. N mass release is largely dominated by AGB winds. C has an important
contribution from AGB while still dominated by SNII, and, finally, Fe has an
equal mass contribution from SNIa and SNII. For dust release, we see as much
carbonaceous dust released by AGN as by SNII, while silicate dust is mostly
produced by SNII.

##  Appendix B Ejecta sizes in low mass galaxies

We show in Fig. 24, the changes in the UV-to-optical slope and bump strength
of the extinction curves of the G8HG_VVLZ and G8HG_VLZ for different values of
small grain size fraction in stellar ejecta $f_{\rm ej,S}=0$ (default value),
$0.5$, and $1$. G8HG_VVLZ has been selected for its important contribution of
SNII ejecta component (as opposed to accretion) for both carbonaceous and
silicate grains in the fiducial model, and G8HG_VLZ because of its significant
SNII ejecta component for carbonaceous grains (only). As expected, these two
low mass and low metallicity galaxies are very sensitive to the grain size
mixture of their stellar ejecta for both the UV-to-optical slope and bump
strength for G8_VVLZ, but only significantly for the bump strength for G8_VLZ
since G8_VLZ has silicate grain (mainly responsible for the UV-to-optical
slope) growth dominated by ISM accretion.

Figure 24: Bump strength and UV-to-optical slope of the extinction curve for
the low mass galaxies with initial gas metallicity $0.03\,\rm Z_{\odot}$
(G8_VVLZ) and $0.1\,\rm Z_{\odot}$ (G8_VLZ) for different fractions of small
grain mass in stellar ejecta $f_{\rm ej,S}$ as indicated in the panel. Values
of the extinction curve features for the Milky Way (‘MW’), the Large
Magellanic Cloud (‘LMC’), and the Small Magellanic Cloud (‘SMC’) are also
shown.

##  Appendix C Sputtering times

Table 3: Coefficients of the fifth-order polynomial fit for the sputtering rate ($i=$ silicate or carbonaceous grains) $\log(Y_{i}/(\mu{\rm m}\,{\rm yr^{-1}}\,{\rm cm}^{3}))=\sum_{n=0}^{5}a_{n}(\log(T/{\rm K}))^{n}$ of Hu et al. (2019) to the values predicted by Nozawa et al. (2006). grain type | $a_{0}$ | $a_{1}$ | $a_{2}$ | $a_{3}$ | $a_{4}$ | $a_{5}$
---|---|---|---|---|---|---
silicate | -234.791 | 133.209 | -31.3027 | 3.71345 | -0.221824 | 0.00531746
carbonaceous | -234.334 | 138.486 | -33.9022 | 4.17705 | -0.258281 | 0.00638828

Figure 25 compares the sputtering times as a function of the gas temperature
for a grain size of $a=0.1\,\mu\rm m$ and a gas density of $n=1\,\rm
H\,cm^{-3}$ from Tielens et al. (1994), Tsai & Mathews (1995), and Hu et al.
(2019). Hu et al. (2019) provides a convenient fifth-order polynomial fit to
the predictions of the sputtering rates $Y(T)$ from Nozawa et al. (2006). The
values of the Hu et al. (2019) fit with sufficient digits are reported in
table 3 (private communication with C.-Y. Hu). The formula from Tsai & Mathews
(1995) is intermediate to the sputtering times of carbonaceous and silicate
grains from Tielens et al. (1994) and Hu et al. (2019), which both show a
general good agreement up to a temperature of $T\sim 10^{8}\,\rm K$. Note that
these calculations are all for a semi-infinite target, however, the finite
size of the grain modifies the sputtering rates for grains with size smaller
than the penetration depth of the impinging ion (e.g. Kirchschlager et al.
2019).

Figure 25: Sputtering time as a function of temperature for a gas density of
$n=1\,\rm H\,cm^{-3}$ and a grain size of $a=0.1\,\mu\rm m$. In red and blue
solid and dotted are the results of Tielens et al. (1994) for respectively Si
and C grains using their fitting functions valid up to $T\simeq 2\times
10^{8}\,\rm K$. The black line is the fitting formula from Tsai & Mathews
(1995). The red and blue dashed lines are the fitting formulas for
respectively Si and C grains from Hu et al. (2019).

##  Appendix D Sticking coefficient

There are various predictions for the sticking coefficient $\alpha$, which
value depends on the temperature of the gas (and grains), e.g.:

  1. 1.

$\alpha_{\rm C}(T)=0.95(1+\beta T/T_{0})/(1+T/T_{0})^{\beta}$, $\beta=2.22$
and $T_{0}=56$ K measured from laboratory experiments for chemisorption of H2
molecules on silicate surfaces (Chaabouni et al. 2012).

  2. 2.

$\alpha_{\rm LB}(T)=(1+10^{-4}T^{1.5})^{-1}$ from theoretical considerations
from Le Bourlot et al. (2012).

  3. 3.

$\alpha_{\rm L}(T)=1.9\times 10^{-2}T(1.7\times 10^{-3}T_{\rm
D}+0.4)\exp(-7\times 10^{-3}T)$ taken from the fit to the data from quantum
calculations of Leitch-Devlin & Williams (1985) in Grassi et al. (2014), and
where $T_{\rm D}$ is the dust temperature. The dust temperature for big grains
is at local thermodynamical equilibrium around 20 K for local galaxies (e.g.
Schreiber et al. 2018), however very small grains can be stochastically heated
(Draine 2003) to large temperatures of about 1000 K.

We present in Fig. 26 the behaviour of each of these predictions of the
behaviour of sticking coefficient with $T$. They all show an increase of
$\alpha$ with a decrease in temperature down to $T\sim 200\,\rm K$, where
$\alpha$ ranges from 0.3 to 0.9 at this temperature. Below this temperature,
the values from Leitch-Devlin & Williams (1985) predicts a decrease of
$\alpha$ with a decrease of $T$, while the values from Le Bourlot et al.
(2012) and Chaabouni et al. (2012) show an increase of $\alpha$ with a
decrease of $T$ up to $\alpha=1$.

Since the exact value and rate of change with temperature of the sticking
coefficient $\alpha$ remains highly uncertain (see the discussion in Zhukovska
et al. 2016), we adopt a constant value of $\alpha=1/3$ for our unresolved
high-gas density regime driven by turbulence (see Section 3.4). For
comparison, the turbulence-driven subgrid model for dust accretion is driven
for $\lambda_{\rm J}<4\Delta x$ and the effective temperature-density relation
in our simulations is $T\simeq 10^{4}(n/0.1\,\rm H\,cm^{-3})^{-2/3}$ (see Fig.
9) for $n>0.1\,\rm H\,cm^{-3}$ and $T<10^{4}\,\rm K$, hence, the temperature
at which the subgrid model is triggered for a fiducial resolution of $\Delta
x=20\,\rm pc$ is $T\simeq 750\,\rm K$. This temperature gives a value of
$\alpha$ from Le Bourlot et al. (2012) that is close to our adopted constant
value of $\alpha$ in the subgrid model. We have run a G10LG simulation with an
increased value of $\alpha=1$ in that regime: the DTM increases by $5\%$,
mostly driven by an increase in the fraction of carbonaceous grains, which
goes from a fiducial value of $f_{\rm C}=0.34$ to $f_{\rm C}=0.38$, and
produces a significant decrease of the depletion factor of C by a factor of 2
at $n\simeq 10\,\rm H\,cm^{-3}$.

The turbulence-driven subgrid model for gas accretion onto dust grains has a
maximum density above which the accretion of new refractory elements is
impossible (either $n_{\rm max}=10^{3}$ or $10^{4}\,\rm H\,cm^{-3}$ (see
section 3.4). This value modifies the behaviour of the effective accretion
timescale as a function of the turbulent Mach number and is shown in Fig. 27
for the case of accretion onto carbonaceous dust grains. The effective time
scale for accretion $t_{\rm acc,eff}$ exhibits a decrease with turbulent Mach
number above $\mathcal{M}>1$ until it reaches a minimum for strong
$\mathcal{M}\simeq 5-10$ after which the effective timescale increase. The
exact behaviour is driven by the maximum value $n_{\rm max}$. To guide the
eye, we show the corresponding free-fall time of the gas at the given mean gas
densities $\bar{n}$, and the (single) time delay for SNII adopted in this
work.

Figure 26: Sticking coefficient for gas accretion onto dust as a function of
the gas temperature $T$ for different models: Le Bourlot et al. (2012) in
black, Chaabouni et al. (2012) in blue, and Leitch-Devlin & Williams (1985) in
red for different dust temperatures $T_{\rm D}=10,20,40,80,300\,\rm K$ for the
dotted, solid, dashed, dot-dashed, and triple dot-dashed red lines
respectively. The magenta line at $\alpha=1/3$ is our preferred value for
unresolved gas densities (see Section 3.4). Figure 27: The effective accretion
rate of refractory materials onto grains (here for carbonaceous grains) as a
function of the turbulent Mach number for two different mean density
$\bar{n}=1$ and $100\,\rm H\,cm^{-3}$ (respectively in solid blue and in
dashed blue). The various colors stand for different density cut-offs $n_{\rm
max}=10^{3}$ and $10^{4}\,\rm H\,cm^{-3}$ (respectively in dark and light
blue). For comparison we show the free-fall time corresponding to the quoted
gas density $\bar{n}$ in black, and the SN time delay in red dot-dashed.

##  Appendix E Sizes and extinction curves for low mass galaxies

In this appendix we show in Figs. 28 and 29 the dust grain size distribution
and the extinction curves of the G9HG, G9LG, and G8LG listed in table 2.

Figure 28: Size distribution of grains and extinction curves at different
times for different simulations as indicated in the panel. The colors (red and
blue) indicate the contribution from different chemical compositions of the
dust (resp. silicate and carbonaceous grains), and we only show this
decomposition in the extinction curve for the final time of the simulation.

Figure 29: Continued from Fig. 28.