TL;DR
This paper addresses the critical but often overlooked issue of trace encoding in process mining, demonstrating how arbitrary choices can lead to suboptimal results and unfair comparisons. It provides a comprehensive survey and benchmarking of 27 encoding methods across various families, offering a new taxonomy and evaluation metrics to guide practitioners in selecting the most suitable encoding for their specific tasks.
What Problem Does This Paper Address?
Process mining (PM) relies heavily on encoding event log data into a numerical feature space for various tasks like predictive monitoring, anomaly detection, and trace clustering. However, the PM literature often sees encoding methods chosen arbitrarily or with default hyperparameters, without a thorough understanding of their impact. This practice can lead to suboptimal performance, unfair comparisons between algorithms, and misalignment with user goals. The authors highlight that while new PM algorithms are frequently developed, the crucial preprocessing step of encoding receives insufficient attention, leading to a lack of standardized benchmarks and a poor understanding of how different encoding strategies affect downstream tasks.
Methods
The authors conducted a systematic review of encoding methods used in process mining, categorizing them into four families: Baseline, PM-based, Text-inspired, and Graph-based. They developed a new taxonomy to classify these methods based on control-flow, data-flow, intra-case, and inter-case dimensions. To benchmark these methods, they proposed four evaluation criteria: expressivity (how well the encoded space captures complexity), scalability (time and memory efficiency), correlation power (how well the encoding improves task performance), and domain agnosticism (applicability across different domains). They then performed an extensive experimental evaluation using synthetic event logs with injected anomalies, measuring performance using metrics like PCA projections, F1-score, and N2 distance.
Datasets
The authors generated synthetic event logs using the PLG2 tool. They created five different process models and combined them with six anomaly scenarios (skip, insert, rework, early, late, all) and four anomaly injection rates (5%, 10%, 15%, 20%). This resulted in a total of 420 event logs, with varying complexities, trace lengths, and log sizes (1k, 5k, and 10k cases). These logs were labeled as normal or anomalous to facilitate supervised learning for the anomaly detection task.
Key Insights and Ideas
- Encoding is Not Trivial: The choice of encoding method and its hyperparameters significantly impacts the performance of downstream PM tasks, and there's no one-size-fits-all solution.
- Arbitrary Choices Lead to Suboptimal Results: Using default or arbitrarily chosen encoding methods can lead to unfair comparisons and hinder the true performance of PM algorithms.
- A Comprehensive Taxonomy is Needed: The paper introduces a new taxonomy that helps organize and understand the diverse landscape of encoding methods in PM.
- Graph-based and PM-based Methods Show Promise: Graph-based methods generally exhibit high expressivity, while PM-based methods like alignment and token-replay demonstrate strong correlation power (high F1-scores) for anomaly detection.
- Domain Agnosticism Matters: While PM-specific methods can achieve high performance, domain-agnostic methods (like those from the Text and Graph families) offer broader applicability and are crucial for building adaptive data science pipelines.
- Trade-offs are Inevitable: There are inherent trade-offs between expressivity, scalability, and correlation power, requiring careful consideration based on the specific PM task and available resources.
Key Results
- Expressivity: Graph-based methods generally showed the highest expressivity, with methods like GraphWave and alignment performing particularly well. Text-inspired methods like doc2vec showed very low expressivity.
- Scalability: The Text encoding family generally offered the fastest methods with low memory consumption. However, some methods within this family (e.g., doc2vec) exhibited scalability issues. PM-based methods like Log skeleton and token-replay were scalable but had high memory and time costs.
- Correlation Power (F1-score): PM-based methods like Log skeleton and position profile, along with several Graph-based methods, achieved the highest F1-scores for anomaly detection. Surprisingly, the traditional one-hot encoding performed poorly.
- Domain Agnosticism: Baseline methods were considered domain-agnostic. Text and Graph families also showed good domain agnosticism. PM-based methods were found to be domain-specific, excelling in PM tasks but with higher computational costs.
Limitations and Future Work
The authors acknowledge that their evaluation was limited to the anomaly detection task. They suggest that future work should explore the application of these encoding methods to other PM tasks like predictive monitoring and clustering. They also highlight the growing importance of online PM, which introduces new challenges such as real-time processing, reduced memory consumption, and handling partial traces. The paper also points to the potential of self-supervised learning (SSL) and meta-learning for developing more adaptive and efficient encoding strategies. The need for explainability (XAI) in PM is also emphasized, suggesting that encoding methods should ideally contribute to interpretable models.
Summary updated