Flexible and Hierarchical Decomposition of Workflow Nets for Process Analysis

Tsung-Hao Huang, Lukas M. Jansen, Marco Pegoraro, Gyunam Park, Wil M. P. Van Der Aalst
June, 2026
PDF Cite DOI

Abstract

Decomposition is widely used in process mining to enhance scalability, facilitate focused analysis, and mitigate the cognitive complexity of large-scale models. While both process discovery and conformance checking benefit from decomposition, existing approaches—especially those based on single-entry single-exit (SESE) fragments—impose structural constraints that limit diagnostic value. This paper proposes a complementary decomposition technique that partitions a WF-net into isolated subnets, i.e., internally coherent fragments with clear interfaces. The decomposition is hierarchical, independent of SESE assumptions, and compatible with valid system net decompositions, enabling divide-and-conquer conformance checking. Experiments show that our approach improves alignment runtime and yields fitness approximations that are closer to the true values than existing decomposition methods.

Type
Conference paper
Publication
Advanced Information Systems Engineering

Practical problem

Analysts who check whether recorded process executions conform to a large process model face two problems: the computation becomes very slow for models with hundreds of activities and long traces, and a single global conformance score says little about where in the process the deviations occur. The standard remedy is to cut the model into fragments and check each one, but the dominant technique only recognizes fragments with exactly one entry and one exit. Real models with multi-entry or multi-exit routing therefore fall apart into trivial pieces, which neither speed things up much nor correspond to anything an analyst would recognize as a subprocess, and the per-fragment fitness values can be far too optimistic.

Research questions

  1. How can a workflow net be partitioned into internally coherent subnets with clear interfaces without assuming single-entry single-exit structure?
  2. Can such a decomposition be made compatible with valid decompositions so that conformance checking can be split across subnets while giving faster runtimes and fitness estimates closer to the true value than existing decompositions?

Contributions

  • Formalizes isolated subnets, transition-bordered fragments of a workflow net whose start transitions share one input place set and end transitions share one output place set, and a decomposition into disjoint isolated subnets covering all transitions.
  • An integer linear programming (ILP) formulation, solved iteratively with PySCIPOpt, that extracts the maximal non-trivial isolated subnet around a seed transition and yields a hierarchical, recursively refinable decomposition.
  • Proves that sub-workflow nets derived from isolated subnets inherit soundness and free-choiceness from the original net.
  • A construction (extended and induced valid decomposition) that adds place-induced subnets and merges fragments sharing silent transitions so the result is a valid decomposition for divide-and-conquer conformance checking.
  • An implementation and experimental artifacts published in a public repository, evaluated against general decomposition, single-entry single-exit (SESE) decomposition, and non-decomposed alignments on synthetic models, PLG-generated models, and BPI Challenge 2015 logs.

Key findings

  • All decomposed approaches align faster than non-decomposed alignment on every synthetic dataset (models with 100 to 300 transitions), though no decomposed method is fastest everywhere.
  • The proposed decomposition yields fitness values closer to true non-decomposed fitness than SESE decomposition on both the pr[A-G]m6 models and the A/E 100-300 models; fewer subnets give closer approximations for both methods.
  • On the real-life BPI Challenge 2015 logs 1-4, SESE decomposition becomes slow because silent transitions in every fragment force merges, whereas the proposed subnets stay small.
  • With noisy logs and longer traces, the decomposed method slows down only slightly while non-decomposed alignment degrades substantially; limiting maximum subnet size speeds alignment but over-approximates fitness.
  • The ILP step scales poorly: decomposition takes about 2 s for 100 transitions, 9 s for 200, and 27 s for 300, exceeding SESE overhead, and validation on large real-world logs (around 300 activities) remains open.