# Process Discovery for Event Logs with Multi-Occurrence Event Types
## 3 Proposed Schema Induction Method  
The set of event types is given by  
\[T=\{t_{i}\},\ i=1,\ldots,N_{t} \tag{1}\]  
The workflow model is defined by a directed graph containing action nodes and control nodes:  
\[M=(M_{N},\ M_{E}) \tag{2}\]  
\[M_{N}=P_{e}\ \cup P_{c} \tag{3}\]  
\[P_{e}=\{e_{i}\} \tag{4}\]  
\[P_{c}=\left\{c_{f},c_{m},c_{s},c_{t}\right\} \tag{5}\]  
where each node \(e_{i}\) has one input and one output edge, \(c_{f}\) is the fork node (one input edge, more output edges), \(c_{m}\) is the merge node (more input edges and one output edge), \(c_{s}\) is the start node (no input edge, one output edge), and \(c_{t}\) is the terminal node (one input edge and no output edge).  
\[M_{E}\subseteq M_{N}\times M_{N} \tag{6}\]  
Each node in the model is uniquely identified by its index value: \(i(e)\). We assign to each action node an event type:  
\[\lambda:P_{e}\to T \tag{7}\]In our model, different nodes in the workflow model may have the same event type. In the model, two activity nodes \(e_{1}\), \(e_{2}\) are in adjacency relation \(e_{1}Ae_{2}\) if  
\[(e_{1},e_{2})\in M_{E} \tag{8}\]  
or there is a \(\left(e_{1},\ e_{1}^{\prime},\ldots,e_{n}^{\prime},e_{2}\right)\) path in the model, where each \(e_{i}^{\prime}\) is a control node.  
A trace related to model M is defined as a sequence of elementary events:  
\[s=e_{1},\ldots,e_{m}, \tag{9}\]  
where  
\[\forall i:\ e_{i}\in M_{N} \tag{10}\]  
\[\forall i\ (1<i<m):e_{i}Ae_{i+1},\ c_{s}Ae_{1},\ e_{m}Ac_{t} \tag{11}\]  
The corresponding model node for a trace node \(e\) is denoted by \(mn(e)\). The m-identifier of trace event \(e\) is defined with  
\[mi(e)=index\ (mn(e)) \tag{12}\]  
The input dataset, an event log, is given by a set of traces related to the same model.  
\[L=\{s_{i}\} \tag{13}\]  
The set of events on \(L\) is defined as  
\[L_{E}=\cup_{i}\{e\mid e\in s_{i}\} \tag{14}\]  
We define an equivalence relation \(e_{1}\Lambda e_{2}\) on \(L_{E}\), where  
\[e_{1}\Lambda e_{2}\ \Leftrightarrow mi(e_{1})=mi(e_{2}) \tag{15}\]  
Regarding the investigated task, we can see that our process discovery problem domain differs from the standard graph mining methods in many aspects:  
* The input graph and the output graph are disjoint;
* The resulting graph is a new graph generated during the prediction process;
* The input graph is a set of traces, where each trace is a sequence of nodes;
* Each node in the input graph has a one-dimensional neighborhood.  
Thus, our task is not a standard node or edge classification task; rather, it is the clustering of the input nodes where each cluster corresponds to a node in the resulting schema graph. The outline of the proposed method consists of the following steps:  
1. Develop a link prediction method for mining the equivalence pairs on the nodes of the incoming traces;
2. Determine the best fitting equivalence classes on the event set;
3. Link prediction between the equivalence classes;
4. Finalization of the workflow graph model.  
The \(\Lambda\) equivalence relation plays a crucial role in the schema induction, as each node in the workflow schema model corresponds to an equivalence class, and the links in the schema are generated from the links between the equivalence classes.