Towards Knowledge-Centric Process Mining

Processes deployed inside and across an enterprise, when executed can leave an operational data footprint in the form of an event logs, which if analyzed can be a valuable source of insights to support the management and improvement of business processes. This Process execution data can transformed into an event log describing the sequence of activities that were performed, along with the resources involved in the execution. Each entry of the process execution log(also known as event logs) represents an event, which records the occurrence of an activity at a particular point in time and belongs to precisely one case (case represents a unique process instance). Events can be characterised by multiple descriptors (attributes), including an event (or activity name), a unique case identifier (e.g case ID), a timestamp and optionally details of resource responsible for executing the task of the process instance. An event refers to an activity (or a step) in the process and belongs to a process instance or a case [10]. The sequence of ordered events within a case forms a trace.

Definition 1 (Event Log) [2]: An event $e$ is tuple $e=(c,a,t,r)\in$ $\mathcal{U}_{\text{case }}\times\mathcal{U}_{\text{act }}\times\mathcal{U}_{\text{time }}\times\mathcal{U}_{\text{res }}$ referring to case $c$, activity a, timestamp $t$, and resource $r$ of event e. An event $\log L$ is a multiset of events, i.e., $L\in\mathcal{B}\left(\mathcal{U}_{\text{case }}\times\mathcal{U}_{\text{act }}\times\mathcal{U}_{\text{time }}\times\mathcal{U}_{\text{res }}\right)$.

data as well).

The process discovery phase involves analyzing business processes based on event logs (which are generated by most of today’s information systems) to extract a process model and insights into the historical performance [3]. Process Discovery algorithms can extract a business process model from an event log, which captures the control-flow relations between tasks recorded in the event log. Such models and insights can allow analysts to analyse performance and understand the behaviour of deployed processes.

Over the past few years, Knowledge Graphs (KG) have emerged as a compelling abstraction for organizing enterprise knowledge [15]. Knowledge Graphs employ a graph-based data model to capture knowledge in a concise and intuitive abstraction for a wide variety of domains. In its simplest form, a knowledge graph is represented by a directed edge-labelled graph composed of nodes and edges. Nodes represent entities of interest and edges capture potentially complex relations between the entities of a given domain [15]. Formally, given a set of nodes $N$, and a set of labels $L$, a knowledge graph is a subset of the cross product $N\times L\times N$. Each member of this set is referred to as a triple and labels capture meanings of the relationships between the entities represented by notes.

Knowledge graphs are an effective tool for modeling interconnected, real-world scenarios while representing an ever-evolving substrate of knowledge within an organization. Knowledge graphs can be applied for integrating, managing and extracting value from diverse sources of data at large scale to present a unified view of enterprise knowledge [17]. Knowledge acquisition tasks that are commonly performed to generate or extract implied information from Knowledge graph are knowledge graph completion, triple classification, entity recognition, and relation extraction [11].

A core step in process discovery is mining a dependency graph (also known as a directly-follows graph), which represents causal dependencies between tasks. The dependency graph is a key abstraction of event data that is subsequently used to discover a process model. The dependency graph is defined as $DG=\{(a,b)\mid(a\in E\wedge b\in a\square)\vee(b\in E\wedge a\in\square b)\}$ Here $E$ is the finite set of activities, representing events that are recorded in the event $\log,\square b$ denotes the activities preceding $b$, and $a\square$ consists of the activities succeeding $a$ [29]. Computing the correct directly/eventually-follows relations from the event log can greatly improve the quality of the mined model. In this section, we investigate the application of knowledge graphs to enable constraint-based filtering of atypical behaviour during dependency graph mining. Automated filtering based on constraint checking (over domain knowledge and business rules) ensures that the dependency candidates generated by the process mining algorithm are correct and conform to a set of desired restrictions (e.g. defined by domain rules, policies etc).

A knowledge graph (KG) offers a flexible way to conceptualise, represent and integrate process knowledge. From an organizational perspective, knowledge graph is useful for modeling explicit knowledge that typically represents process context, subject matters expertise of knowledge workers along with business rules and constraints. In this work, we assume the availability of a knowledge graph that encodes knowledge about the domain, business policies and regulations. In scenarios, where modeling a domain knowledge graph completely from scratch isn’t feasible, we can use machine learning based methods for automated construction of a knowledge graph. Knowledge graph can be massively be scaled using natural language processing techniques, where we can build custom models that identify entities and relationships unique to a particular domain from unstructured text [17].

To rule out infeasible possibilities (and combinations thereof) in dependency relations, we consider a rule-based reasoning approach where we apply automated symbolic learning to learn a model of logical formulae in the form of closed-path rules. Considering our sepsis example, these rules maybe be based on clinical guidelines developed by the medical community. In our sepsis example, the mined model incorrectly allows us to skip all activities between registration and discharge. A rule based on sepsis guidelines of the form For adults suspected of having sepsis, perform immediate sepsis screening test and admission during wait period can constraint the model and prevent this from happening. Overall, rules provide a layer of conceptual knowledge needed to analyse event logs and to infer agreement/disagreement between observed and true behaviour and reach conclusions about unrealistic possibilities. We note that true behaviour is not characterised by the designed process model rather by a set of all activities and their subsequent effects (post-conditions) that occurred on-ground during process execution. Automated rule discovery has a rich history and over the past few years, several scalable rule learners for knowledge graphs have been developed [15]. In work we consider AMIE+, an efficient rule mining approach [13], which allows us to mine closed-path rules(a language bias that is well-suited for rule learning in the context of knowledge graphs) in a self-supervised manner. To deal with an incompleteness aspect of the knowledge graph, we rely on Partial Completeness Assumption (PCA) and each rule has an associated confidence degree.

Definition 2 - Closed-path rules [23] A CP rule (or simply a rule) $r$ is of the form

Here $x,y$ and $z_{i}$ ’s are variables, each $P(u,v)$ is called an atom, and $u$ and $v$ are called respectively, the subject and object argument for $P$. Intuitively the task of searching for CP rules can be reduced to that of finding plausible paths represented as sequences of predicates with high support and confidence. The derived rules capture the most representative constraints while considering the both structural and semantic features in the KG.

To mine the dependency gtearaph from a given event log $W$, process discovery algorithms typically compute directly-follows and eventually-follows relations between two events a and b. For example flexible heuristic miner uses a frequency-based metric is used to capture the extent of dependency relation between two events A and B (represented by $a\Rightarrow_{W}b$) [29].

The frequency metrics indicate the certainty level of a dependency relationship between two events $a$ and $b$ (high values indicate a strong relation) [29]. During this step we perform consistency checking in directly-follows relations against the mined rule-base. We rule out infeasible pairs if a directly-follows relationships is not entailed by the rule-base. Formally, for a given event log consisting of a set sequential event traces, constraint-base filtering involves finding pairs $(a,b)$ of sets of activities such that every element $\mathbf{a}\in\mathrm{A}$ and every element $\mathrm{b}\in\mathrm{B}$ are causally related (i.e., $a\rightarrow_{L}b$ ) and are consistent with each of the closed-path rules. This allows us ensure that the mining algorithm extracts the correct (feasible) event dependency patterns. Similar strategy is used for computing loops and long term dependencies.

Process execution traces exhibit a high degree of variability, representing deviating behaviour, especially in flexible environments such as the healthcare domain. In a medical context, variations can occur due to patients’ and clinicians’ agency, scientific and clinical evidence, and personal or organizational capacity [26]. For treating sepsis patients, deviations from clinical guidelines are fairly common in practice, to make allowance, for instance, for varying demographics (age, medical history) or for co-occurring conditions (sometimes, co-morbidities preclude the application of the standard protocol). Here, process owners are interested in identifying, quantifying, and reducing unwarranted clinical variation. To better understand the medical decisions underlying individual treatments, process analysts often carefully partition the data (care-flow instances) into cohorts based on the treatment provided by existing medical guidelines, patient profile (characterized by criteria like age group) and, the evidence base for prescribed treatment or patient’s medical history.

Knowledge graphs have widely been applied for constructing context aware-based recommender systems where we use historic data to model item and user interactions. In our work, we construct a knowledge-graph base recommender system that encodes past variant behaviour as well as events annotated with contextual information to address the challenge of characterising deviating behavior. Our proposed machinery can assist the process analyst in classifying the traces based on the control-flow, shared cohort profile and contextual similarities and differences, associated with a given process instance. Formally, given an event log $L\subseteq\mathcal{E}^{*}$ as a set of traces $\sigma\in\mathcal{E}^{*}$, where each trace is sequence of events annotated with relevant context and each trace is labelled with a variant class (as a training example) our machinery learns to partition the event log into a set of groups called process variants $\varsigma_{1},\varsigma_{2},\ldots,\varsigma_{n}$, such that $L=\varsigma_{1}\cup\varsigma_{2}\cup\ldots\varsigma_{n}$. Here process executions in the same group must share the same contextual attribute value pair, and each process execution belongs only to one process variant.

In our sepsis example, we can consider mapping each input trace to three major patient cohort classes namely, effective care, where trace variation implies the underuse of valid treatment or preference-sensitive care, where variation implies availability of multiple care options and patient exercising choice), and supply-sensitive care, where variation implies the volume of care provided is a reflection of organizational capacity rather than patient need [26]. We argue that process context mainly influences variant configuration and a wealth of relevant information can be found in non-process data (such as patient demographics and medical histories) which do not routinely appear in process logs, and which are not easily amenable to process mining. We consider event log augmentation which allows for a useful way to characterize the process context, enabling automated identification and classification of process variants. We therefore, annotate event logs with contextual features (attributes) representing exogenous knowledge potentially relevant to the execution of the process that is available at the start of the execution of the process, and that is not impacted or modified during the execution of the process. We identify similar cases in logged data, that have been classified in the past and can form the basis for the current recommendation (annotated by process analyst as training examples). Each input trace is enriched by associating each event in the trace with a relevant attribute value pairs. Formally, given a event $e=(c,a,t,r)$, and a context $C$ of a process instance, we augment the event with attribute-value pairs.

To understand variations, we consider labeled property graphs to encode behavioral and causal inter-dependencies of objects and actors over time in the context of process flows to symbolically represent a given situation for context-aware predictions. We model multi-dimensional event data as a labeled property graph in a manner similar to described in [12].

Definition 4: (Labeled Property Graph: [12]) A labeled property graph (LPG) is a data structure where $K$ is a set of keys, $V$ is a set of values and Label be a set of labels. An LPG $G=(N,R$, label, prop ) consists of nodes $N$ (vertices) and relationships $R$ (edges) where each relationship $r\in R$ defines a directed edge $\vec{r}=\left(n_{1},n_{2}\right)$ where $n_{1},n_{2}\in N$.

The labeling function label : $N\cup R\rightarrow 2^{\text{Label }}$ assigns to each node and each relationship a non-empty set of labels designating their type, e.g., label $(n)=\{$ shock_index, 0.5 $\}$. Function prop : $(N\cup R)\times K\rightarrow V$ assigns each node or relationship an arbitrary number of key-value pairs, called properties. For the value $\operatorname{prop}(x,k)=v$ of a property key $k$ of a node or relationship $x\in N\cup R$, we also write $x.k=v$ [12].

Next, we consider embedding based models for scoring trace-class associations. For feature representation, we first generate the graph embeddings, where we to fuse the trace-level and class-level representations to generate a knowledge-aware embedding vector. We apply TransD [16] method for entity representation learning. This allows us to embed knowledge graph into a D-dimensional vector space using a distributional representation that captures semantic similarities among entities and predicates. Formally, given an input graph $G=(N,R$, label, prop ), the encoding component maps entities to their distributed embedding representations. During training, the goal is to preserve local structure whereby vertices sharing similar edges in the graph are mapped to similar locations in the embedding. The distance between any pair vertices of as a measure of their relatedness and can be used to identify the presence or absence of a relationship.

Next, we cast the recommendation problem as a link prediction problem where the model learns the high-order connectivity between an unseen event trace and associated class. We adapt the content-based model proposed by [28] to learn a scoring function capable of generating class recommendations. Learned entity embeddings are taken as the input for a given an event $\log L$ we learn a prediction function $\widehat{y}_{\sigma\varsigma}=\mathcal{F}(\sigma,\varsigma\mid,\Theta,G)$ $\hat{y}_{\sigma i}$ which provides a relevancy score that predicts the probability that instance $\sigma_{n}$ belongs to particular cohort $\varsigma_{i}$. The model uses an attention module to learn high-order semantic relationship between each traces aggregated historical representation and associated variant class. During training it recursively propagates the embeddings from a node’s neighbors to refine the node’s embedding, and employs the attention mechanism to discriminate the importance of the neighbors for providing accurate recommendations. Overall, the model allows context-aware characterization of process variants based on their cohort profile.

Considering that the event log is the main input for process mining techniques, the quality of event logs is critical to the success of the process mining efforts. Process discovery from event logs remains a challenging problem as real-world process logs are often incomplete and don’t explicitly capture all the behaviour of deployed processes. A domain expert might have a bunch of rules or facts about her domain, which can be useful for deducing more knowledge from the event log than what has been explicitly recorded. For example, reasoning on an available medical knowledge graph of infectious diseases along with patient data (like white blood cell count) will allow us to infer that patients who are compromised hosts(due immune problems) often also have gram-negative infections (caused by bugs like pesudo-monas). This kind of reasoning is challenging as; first, we require explicit specification of the conceptualisation of the given domain domain. Second reasoning mechanism must be robust to errors in the inputs to the system, to uncertainty in the knowledge, or to the gradual changes in the truth of various pieces of knowledge. The problem of Knowledge reasoning over knowledge graphs for inferring new conclusions from existing data has been well studied [6]. Using this existing work as our foundation, we investigate the use of knowledge graphs for discovering missing events. Specifically, we address the semantic incompleteness of an event trace, by inferring potential relations between entity pairs to automatically identify missing events, based on existing knowledge with the purpose of complementing the event log. For a partially complete trace $\sigma$,over a event log $L$, our machinery generates a set of candidate event traces $\sigma^{\prime}$ as a superset of $\sigma$ as output with the intent of improving the utility of mined models.

Similar to the approach taken in previous sections, we assume our knowledge graph encodes event data along with enterprise domain knowledge and business rules. To accurately capture the temporal patterns of event traces, we make use of a a temporal knowledge graph of the form $r(h,t\mid\tau)$ (where $h$ and $t$ represent entities, $\tau$ is a time stamp, and $r$ represents a relation that holds between these entities at the time specified by $\tau$). We adapt the technique proposed by Messner et al. [21] where we use the box embedding approach to learn latent representations for events represented as entities, relations, and time stamps and then use the learned representations to predict missing events. We cast the event deduction problem as a temporal knowledge graph completion (TKGC) task where given the head (partially complete trace), we predict missing tail entity. Formally, our machinery computes the directly-follows degree score representing the probability of missing successor event $e_{j}$ occurring after predecessor event $e_{i}$ $\left(e_{i}\rightarrow e_{j}\right)$ in the trace $\left\langle\ldots,e_{i},e_{j},\ldots\right\rangle\in\mathcal{E}$. i.e Given the event log as premises along with general domain rules which are known apriori, we perform deductive reasoning to find new relations among graph entities in order to derive missing events. Overall, our machinery helps overcome the incompleteness aspect of event log and enables intelligent inferences from limited (or incomplete) amounts of recorded process data in order to guide process analysts better understand the process behaviour.