CS Paper Radar

Monotonicity-Guided Bottom-Up Petri Net Discovery: The SPECpp Framework

Leah Tacke genannt Unterberg, Lisa L. Mannel, Wil M. P. van der Aalst

cs.DB cs.AI ·submitted 2026-08-10 10:23 UTC · v1

Abstract

Process discovery is one of the central challenges in process mining. Petri nets are particularly attractive because simple local constructs can express complex behavior, including concurrency. While their global behavior may be difficult to analyze, individual places can be efficiently characterized using monotonic properties, enabling bottom-up discovery. Unlike top-down approaches such as the Inductive Miner, which rely on predefined constructs for sequences, choices, loops, and concurrency, our approach allows such structures to emerge organically and can exploit the full expressive power of Petri nets, including free-choice constructs and long-term dependencies. The main challenge is the exponential number of candidate places and their combinations. We present the SPECpp framework which implements strategies to obtain high-quality models under time and resource constraints. SPECpp supports rapid experimentation and is used to evaluate these strategies using both synthetic and real-life event data.

Comment
59 pages, 15 figures

Closest papers

Nearest neighbours by meaning across the whole index.

Extending the MM-AR Metamodeling Platform with Process Mining Capabilities

cs.SE cs.DBcs.HC ·2026-11-03 ·Geraldine Hürzeler, Hans-Georg Fill, Daniel Borcard
code/data similarity 0.70
Abstract

Process mining derives process models from event data recorded by information systems, but its results are usually presented as two-dimensional visualizations that are separate from the environments in which enterprise models are created and maintained. Metamodeling platforms for extended reality (XR), such as MM-AR, allow users to define modeling languages and to display models in 2D and 3D, but they do not provide access to event data or mining algorithms so far. In this paper we therefore present a first proof-of-concept for showing how an XR-based metamodeling platform can be extended with process discovery capabilities without changes to the platform core through a separate Python service based on the open source PM4Py process mining library. We demonstrate the approach using three common discovery algorithms for obtaining Petri nets and BPMN models based on CSV or XES event logs. A technical evaluation using four public event logs shows that the element counts of the created model instances match those of the PM4Py models in all 16 configurations. The integration adds between about 8 and 53 seconds per run, and this overhead grows with the size of the discovered model rather than the size of the event log. Although the prototype does not yet use the third dimension to encode process information, it established the foundations for studying such approaches.

0.30

Structure-Aware Message Passing on Petri Nets through Directed Walks and Incidence Diffusion

cs.LG cs.AI ·2026-10-21 ·Geri Skenderi
benchmark similarity 0.68
Abstract

A common application of the process mining discipline is to connect observed event data with Petri nets, which are bipartite, directed graphical process models with rich formal underpinnings. Recent work learns vector representations of Petri nets to retrieve process models and relate them to event logs, but leaves implicit two key aspects hidden within the net's structure: directed cycles (process loops) and invariants recorded by the net's incidence matrix. We expose both of these to message-passing graph neural networks, through a positional encoding built from return probabilities of directed place-transition walks (PNRWPE), and through same-type messages gated by diffusion kernels of the incidence matrix (DA-PNGNN). Our constructions raise macro balanced accuracy in predicting the generation factors of the 96 Process Discovery Contest 2023 models from 0.751 to 0.796 with PNRWPE, which nearly doubles accuracy on process loops, and to 0.830 with DA-PNGNN, which, without retuning, also improves net-to-tree retrieval top-1 accuracy on the self-supervised ProcRosetta benchmark by 4.1 to 5.9 points.

0.15

Inductive Process Discovery from Partially Ordered Event Data

cs.DB ·2026-08-20 ·Humam Kourani, Tom Breuer, Gyunam Park, Wil M. P. van der Aalst
similarity 0.67
Abstract

The Inductive Miner (IM) family is a prominent class of process discovery techniques, combining efficient recursive decomposition with soundness-by-construction guarantees. However, IM techniques usually assume traces to be totally ordered sequences of activity occurrences. This assumption is convenient, but can introduce systematic bias: activities may have durations, events may share coarse timestamps, or the data may constrain only some event pairs. Forcing such executions into arbitrary sequences hides inherent concurrency and may introduce sequential dependencies that were never observed as causal constraints. Partial orders provide a more faithful representation, but integrating them into IM discovery is challenging because standard abstractions are sequence-based; directly reusing them would require linearizing each partial order, which becomes prohibitively expensive under high concurrency. We introduce a lifting of IM discovery from total orders to partially ordered traces. Instead of redesigning the miner and its cut detection logic, we redefine the trace abstraction layer and the recursive projections to operate directly on partial orders. The approach is conservative over totally ordered traces, avoids linearization explosion, and preserves the recursive structure and guarantees that make IM attractive. Experimental results show that the proposed lifting avoids the combinatorial overhead of linearization, reduces sensitivity to arbitrary tie-breaking in timestamped event data, and allows process behavior to be learned from fewer observations by preserving concurrency at the trace level.

0.17

A Node Embedding Framework for Model-Centric Conformance Checking in Process Mining

cs.AI ·2026-10-13 ·Mostafa Abbasi, Homayoun Najjaran
code/data similarity 0.66
Abstract · 34 pages, 13 figures, 8 tables. Code: https://github.com/mstabc/cc_node2vec

Evaluating the quality of process models discovered from event logs is a fundamental challenge in process mining. Traditional evaluation relies on conformance metrics such as fitness and precision, which are highly sensitive to noise and deviations in event logs and therefore often fail to give a consistent assessment of discovery algorithms. We introduce a model-centric evaluation framework that combines node embeddings with Procrustes alignment to enable cross-graph comparability, since embeddings derived from different graphs reside in distinct vector spaces. The proposed PetriNetGraph method transforms Petri net process models into graph representations compatible with embedding algorithms. Comparing the node embeddings of ground-truth and discovered models through a parameterized cosine distance yields a unified and bounded metric for evaluating process discovery across datasets and methods. We evaluate the framework under static and context-aware scenarios to examine how prior knowledge of activity existence influences the assessment of structural similarity. The framework also integrates a compliance checking mechanism that localizes deviations at the activity level and an entropy-regularized node distance aggregation function that quantifies global deviations across the model. Experiments on nine publicly available event logs show that the approach provides a reliable embedding-based conformance indicator that reflects the behavior of fitness and precision. Experiments on synthetic logs with controlled noise levels confirm that it is substantially more robust to log deviations than traditional conformance metrics, PetriNet2Vec, and its dynamic-window and Procrustes-aligned variants, while remaining sensitive to process model degradation. All implementation details and datasets are publicly available.

0.32

String Diagrams for Process Mining

cs.LO cs.DBmath.CT ·2026-09-17 ·Antony R. Lee, Peter Tiňo, Iain B. Styles
similarity 0.64
Abstract · 67 pages, 22 figures, 4 tables

Run two process-discovery algorithms on the same event log and they return two different pictures of the same process. Petri nets, causal nets, process trees and BPMN each rely on routing machinery of their own, and their only common ground is the traces they generate. A trace lists activities one after another, so it discards the concurrency the notations exist to express, and two models with identical trace languages can describe genuinely different processes. Whether two discovered models mean the same thing therefore has no notation-independent answer. We show that all four notations admit one canonical presentation, a signature recording a model's activities and the typed interfaces along which they compose, and nothing of the routing machinery. Four construction theorems establish this presentation notation by notation, so two models are compared in a form that each notation determines on its own. Signature equality implies trace equivalence and is strictly finer, separating genuine concurrency from interleaved choice, which a trace comparison cannot, and signature inclusion implies trace inclusion. In a recovery study on one object-centric log, the discovered causal net has exactly the ground-truth signature, while the discovered Petri net's signature strictly contains it and locates every behaviour the Petri net adds in its silent structure. The gain is largest for object-centric data, where a single log supports several notations at once. The four notations become one calculus, in which a translation between them is a claim that can be checked.

0.35

Concurrency-Aware Process Model Forecasting with Causal Nets

cs.LG cs.DB ·2026-09-18 ·Yongbo Yu, Jari Peeperkorn, Johannes De Smedt, Jochen De Weerdt
similarity 0.60
Abstract · 13 pages, 2 figures

Process model forecasting (PMF) aims to predict the process model that will characterize a future period, thereby providing a process-level view of how behavior is expected to evolve. Existing PMF methods, however, forecast directly-follows graphs, which cannot explicitly represent concurrency. We extend PMF to causal nets by forecasting time series of relation and binding counts and using these forecasts to reconstruct future process models with AND/XOR semantics. To evaluate the resulting models, we introduce a protocol that accounts for partial traces and constructs the workflow nets required for conformance checking. Experiments on four event logs show that the forecasted models achieve conformance levels close to those of models re-mined from observations in the corresponding future windows. They also outperform static discovery baselines, which retain high precision on the structurally stable log but exhibit substantial precision losses on the other three logs. Filtering infrequent bindings improves most conformance metrics, although it also removes much of the concurrent behavior captured by the models.

0.29

PetriBench: Benchmarking LLM Reasoning over Dynamic State Spaces

cs.CL cs.AIcs.LO ·2026-09-17 ·Pyrros Koussios, Benjamin Jäger, John Hua Yao, Ajay Sridhar, Violet Xiang +1 more
benchmark similarity 0.60
Abstract

Characterizing LLM reasoning remains an open challenge, as many existing benchmarks isolate specific reasoning skills, rely on external knowledge, or are costly to extend. We introduce PetriBench, a compact, fully self-contained, and scalable benchmark for evaluating LLM reasoning over dynamic state spaces using Petri nets, a mature formalism for modeling real-world concurrent and distributed systems. PetriBench organizes reasoning into four task families varying by scope and temporal horizon, with Easy, Medium, and Hard levels generated by increasing structural complexity and evaluated against exact ground truth. Across a diverse set of proprietary and open-weight models, accuracy decreases consistently with difficulty, while harder instances expose increasingly distinct task-specific capability profiles. Additional analyses show that test-time compute improves performance but interacts differently with different reasoning tasks, and that procedural generation yields smooth scaling with structural complexity. Together, these results show that PetriBench provides a unified and extensible setting for probing the strengths, limits, and scaling behavior of LLM reasoning.

0.14

Resolution limits for process comparison from event data

cs.DB cs.LGstat.ML ·2026-09-17 ·Antony R. Lee, Peter Tiňo, Iain B. Styles
similarity 0.59
Abstract · 35 pages, 4 figures; 13-page supplementary material as an ancillary file

One hospital runs bloods and imaging at the same time. Another runs them one after the other, in either order, equally often. Knowing which actually happened, and how it is recorded in data, is critical for all operational managers. In process mining, the standard approach is to construct an event log, and attempt to discover concurrent and sequential processes in a data-driven way. We show this standard approach, built on the stochastic language of an event log, reports only the assumptions of its discovery algorithm, because every such log is explained equally well by a model with no concurrency at all. Further, before any data is acquired, we characterise when data can and cannot distinguish concurrent behaviour. Where it cannot, the distinction is recoverable from evidence the stochastic language discards, such as the times at which activities start and end, or object-centric records that fix an order within an execution. The remedy is therefore a choice of what is recorded, rather than a larger sample. This impacts decision making, as planning resource for truly concurrent services is very different from sequential services.

0.33