# Unlocking Non-Block-Structured Decisions: Inductive Mining with Choice Graphs

- Type: Conference paper
- URL: https://www.gyunam.com/publication/2025-bpm-powl/
- Date: 2025-08-31
- Authors: Humam Kourani, Gyunam Park, Wil M. P. van der Aalst
- Venue: Business Process Management
- DOI: https://doi.org/10.1007/978-3-032-02867-9_10
- PDF: https://www.gyunam.com/publication/2025-bpm-powl/paper.pdf
- Research lines: [Process discovery and diagnostics](https://www.gyunam.com/research-line/process-discovery-and-diagnostics/index.md)

## Abstract

Process discovery aims to automatically derive process models from event logs, enabling organizations to analyze and improve their operational processes. Inductive mining algorithms, while prioritizing soundness and efficiency through hierarchical modeling languages, often impose a strict block-structured representation. This limits their ability to accurately capture the complexities of real-world processes. While recent advancements like the Partially Ordered Workflow Language (POWL) have addressed the block-structure limitation for concurrency, a significant gap remains in effectively modeling non-block-structured decision points. In this paper, we bridge this gap by proposing an extension of POWL to handle non-block-structured decisions through the introduction of choice graphs. Choice graphs offer a structured yet flexible approach to model complex decision logic within the hierarchical framework of POWL. We present an inductive mining discovery algorithm that uses our extension and preserves the quality guarantees of the inductive mining framework. Our experimental evaluation demonstrates that the discovered models, enriched with choice graphs, more precisely represent the complex decision-making behavior found in real-world processes, without compromising the high scalability inherent in inductive mining techniques.

## Practical problem

Analysts who want to see how a process really runs let discovery algorithms draw a model from the event log, and inductive miners are popular because their models are always free of deadlocks and are produced quickly even for large logs. The price is that these miners can only express decisions as neatly nested blocks: every split must be closed by a matching join. Real processes rarely behave that way; an order may be cancelled on one branch while the other branch rejoins the main flow, and a block-structured model then has to allow impossible behavior such as cancelling and shipping the same order. Directly-follows graphs capture such branching naturally but become imprecise as soon as activities run in parallel or repeat, so practitioners currently choose between a model that is sound but too permissive and one that is faithful to branching but unsound and over-general.

## Research questions

1. How can non-block-structured decision points be represented within the hierarchical Partially Ordered Workflow Language (POWL) without losing soundness?
2. Can the Inductive Miner be extended to discover such decision structures while keeping its formal fitness guarantee?
3. Do the discovered models become more precise on real-life event logs, and does the extension affect the scalability of inductive mining?

## Contributions

- Formalizes choice graphs, a directed start-to-end graph over sub-models that generalizes the exclusive-choice operator, and defines POWL 2.0 together with its language semantics.
- A discussion of conversion of POWL 2.0 to workflow nets and of its expressiveness, covering sound state-machine and marked-graph workflow nets within the free-choice class.
- A discovery algorithm that replaces the exclusive-choice cut of the POWL Inductive Miner with a valid choice graph cut computed from the directly-follows graph, restricted to acyclic graphs.
- Proves, by induction over the recursion, that the extended miner preserves the Inductive Miner's fitness guarantee for every trace in the log.
- An implementation in the Python library `powl` (pip-installable, Zenodo archived), a Streamlit web demo, and a published collection of all discovered models.

## Key findings

- On 17 real-life event logs from data.4tu.nl, the choice-graph miner achieves equal or higher precision and F-score than the standard POWL Inductive Miner in every case; in 21 of 30 non-timeout cases the models are strictly more precise.
- With directly-follows noise filtering at threshold 0.2, F-score gains are large on several logs, e.g. BPIC2012 from 0.41 to 0.62, BPIC2017 from 0.48 to 0.70, Hospital Billing from 0.71 to 0.95, Road Traffic Fine from 0.82 to 0.99.
- On the Receipt Phase WABO log both fitness (0.81 to 0.88) and precision (0.25 to 0.55) improve; on BPIC2017 Offer Log F-score rises from 0.91 to 1.00 because offers can no longer be accepted before being sent and returned.
- Runtime is unaffected without filtering and sometimes improves with filtering, e.g. BPIC2019 discovery drops from 287 seconds to 20 seconds.
- Limitations: fitness occasionally drops slightly after filtering, conformance checking timed out on BPIC2018 and BPIC2019, discovery handles only acyclic choice graphs, and POWL 2.0 still forbids arbitrary interleaving of choice and concurrency splits and joins.