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

Introduction to the show: ident: Paper Radio. Generated commentary on the latest Artificial Intelligence papers.

Tom: Next we'll be talking about the paper "Monotonicity-Guided Bottom-Up Petri Net Discovery: The SPECpp Framework".

Jane: The paper was written by Leah Tacke genannt Unterberg, Lisa L. Mannel and Wil M. P. van der Aalst from RWTH Aachen University.

Tom: Stay tuned as we take you through the paper and discuss its implications.

Paper summary: Tom: We're talking about a really compelling paper today. It's about discovering Petri nets from event logs, but instead of decomposing the process from the top down, the authors build the model up, place by place. That bottom-up perspective is what makes the whole thing distinctive.

Jane: What makes it work is monotonicity. If a candidate place fails a quality test, you can discard a whole family of related places without evaluating each one individually. That's a powerful pruning mechanism.

Lu: The framework is organized as a proposal, evaluation, and composition loop. You propose a candidate place, you score it against the log, and then you decide whether to add it to the growing set of accepted places. It's iterative, so the set expands until the search space is exhausted or a time limit stops the run.

Meng: On the software side, there's a full open-source implementation and a ProM plugin with a live discovery view. That's rare in this area, and it makes the ideas directly usable.

Lalam: This matters because process discovery has been dominated by block-structured methods like the Inductive Miner. Those methods impose a tree structure on the model, which means they can't represent dependencies that cross block boundaries. That's a real limitation in practice.

Tom: The paper's opening example is a delivery process where the order type and the invoice type are linked, but with deliveries in between. Only the eST-Miner-based approach captures both that long-term dependency and the delivery loop. The Alpha Miner, the Inductive Miner, and the ILP Miner all fail on that tiny log.

Jane: So the expressiveness gain is concrete, not just theoretical. But it comes at a computational cost, because the space of possible places is exponential in the number of activities.

Lu: The paper confronts that head on. Most of the technical content is about pruning, and the monotonicity properties are the key to making the search tractable.

Meng: They also handle long runs gracefully, with time limits and a usable intermediate result. That's an engineering choice that makes the approach much more practical.

Lalam: The broader implication is that expressiveness and practicality aren't mutually exclusive. If you can prune well, bottom-up discovery becomes a genuine alternative to the established top-down algorithms.

Jane: That sets up the first page of the paper nicely, where they explain exactly why top-down structure assumptions are so restrictive.

Tom: Let's look at that page now, because it's the entrance to the whole argument.

Page 1 of the paper: Jane: So page one is the introduction. The authors begin by observing that directly-follows graphs are popular in practice, but they aren't executable, and they can't express the concurrency you need for simulation or prediction. That motivates the search for richer models.

Tom: They also spell out a key weakness of top-down discovery. If you recursively split the process into blocks, you can never see dependencies between activities that live in different blocks. That's a structural blind spot.

Lu: The Inductive Miner is the canonical example. It gives you a lot of structure and guarantees, but that structure is exactly what prevents it from finding long-term dependencies. The authors call this representational bias.

Meng: And that's why they turn to a bottom-up design. You don't assume any global shape; you start with the smallest meaningful building block, a place, and see which places fit the observed behavior.

Jane: The paper describes that as a proposal, evaluation, and composition cycle, followed by post-processing. So there are three iterative steps and one final cleanup step.

Tom: I like the detail that the "S" in SPECpp comes from the implementation, not from the conceptual architecture. It's a small thing, but it shows the authors care about the software as much as the theory.

Lu: They also lay out the central difficulty clearly. The number of possible places is exponential in the number of activities, and the number of combinations of places is another exponential on top of that. So brute force is completely hopeless.

Meng: The design answer is pruning. If a property is monotonic along the candidate tree, you can evaluate one place and infer something about all its descendants.

Lalam: The delivery example makes the failure mode tangible. A regular order leads to a regular invoice, a VIP order to a VIP invoice, and in between you can have any number of deliveries. Directly-follows relations will never connect the order and invoice, because they never appear next to each other.

Tom: And the loop makes it even worse. The whole thing looks like a tangled knot to any algorithm that only looks at local relations.

Jane: So the paper's central claim is that the place is the right unit of reasoning. Individual places are cheap to check, and a whole model is just the intersection of their constraints.

Lu: That's a strong claim, and it depends on a precise definition of what it means for a single place to fit a log. That's exactly what page seven provides.

Tom: Let's go there. The token-based replay definition is surprisingly intuitive once you see it.

Page 2 of the paper: Tom: Page seven introduces the fitness of a single place using token-based replay. You take a trace and watch a token count that moves as activities fire. Activities in the preset add a token, and activities in the postset remove one. The count is the only thing you track, which makes evaluation very fast.

Jane: For the replay to be fitting, that token count must never go negative. You can't consume a token that isn't there. The authors call this condition non-negativity.

Lu: And at the end, the count has to be balanced. The total number of preset firings has to equal the postset firings, so no tokens are left over and none are missing. Both conditions together give you the place fitness.

Meng: They call those two conditions non-negativity and balanced. Together they match the classic token-based replay used in conformance checking, which is a nice link to existing practice.

Tom: What's elegant is how sets of places behave. A trace fits a whole set of places if and only if it fits each place individually, because every place is just a separate constraint. The intersection of constraints is the model behavior.

Jane: That implies an empty set of places fits everything. Places add restrictions, and the model's behavior is the intersection of those restrictions. It's a very clean formal starting point.

Lu: This locality is what makes the pruning strategy plausible. Evaluating one place is cheap, but evaluating the whole global net would be infeasible. The framework leverages that contrast.

Meng: The paper also normalizes traces with unique start and end activities. That makes the Petri net conversion cleaner later. It's a practical detail that simplifies the definitions.

Lalam: These fitness notions have monotonicity built in. If a place is underfed or overfed on a behavior, adding more preset or postset activities only makes it worse. That monotonicity is the anchor for the whole pruning machinery.

Tom: The authors do note that each place is initially and finally unmarked, and the final net adds dedicated start and end places. So the conversion from a set of places to a marked net is straightforward.

Jane: That's the foundation, but the really important part is the proof that pruning with such constraints is sound. Let's look at that proof, because it's the formal backbone of the approach.

Page 3 of the paper: Tom: Page thirteen is all about the constrained child generation theorem. The claim is that if a constraint is subtree-monotonic, then filtering children that violate it doesn't lose any candidates. That's a completeness result, not just a heuristic.

Jane: Subtree-monotonic means that if a constraint fails at a place, it also fails for every place below it. The contrapositive is that any candidate that passes the constraint must have all its ancestors passing too. That's the property the proof exploits.

Lu: The proof looks at the unique path from the root to a candidate place. If the candidate meets the constraint, every place on that path meets it, so every edge on the path survives the restricted child generation logic. The candidate is still reachable.

Meng: And if the candidate fails the constraint, then its own parent won't generate it under the restricted logic. So it can never appear in the traversal. That's exactly what you want from a pruning rule.

Tom: The figure on that page shows this nicely. A passing descendant can't have a failing ancestor, and failing places are blocked at the boundary. The restricted tree is a perfect slice of the original.

Jane: The framework can then choose different expansion strategies, like depth-first or best-first, while keeping this completeness property, as long as the constraints remain monotonic. That's a beautiful separation between search strategy and pruning logic.

Lu: The tree state keeps track of which children have already been visited. That prevents the same place from being proposed twice, which is an important detail in practice.

Meng: The authors are also honest that you can drop monotonicity, but then you lose the completeness guarantee. That's a trade-off the framework explicitly supports.

Lalam: What's appealing here is that the pruning isn't something bolted on afterwards. It's deep in the structure of the tree and the constraints, which is why the framework can claim both efficiency and rigor.

Tom: But all of this lives in an abstract tree. You need concrete rules for growing places, and that's where the paper defines preset and postset expansions.

Jane: That's page nineteen. Let's see how the tree actually grows.

Page 4 of the paper: Tom: Page nineteen defines how the candidate tree actually grows. The root is the empty place, and every expansion step adds one activity either to the preset or the postset. The tree is not precomputed; it's unfolded lazily as the search proceeds.

Jane: They use strict orderings on activities, so expansions are incremental in a specific sense. You can only add an activity larger than the ones already present, which guarantees every place has exactly one parent. That keeps the tree structure coherent.

Lu: The clever part is the case distinction in the generation logic. From the root, you start with postset expansions, and then depending on the sizes of the preset and postset, the generator switches between the two expansion types.

Meng: The postset is expanded first whenever possible. That makes the tree asymmetrical, with larger, more homogeneous postset expansion subtrees that get explored earlier in the traversal.

Tom: And that's a deliberate performance choice. Underfedness is monotonic under postset expansion, so those subtrees tend to be pruned sooner. The paper says postset expansions are ordered before preset expansions because they can lead to earlier pruning.

Jane: The activity orderings are also part of the configuration. You can use lexicographic ordering, random ordering, or orderings derived from the event log, like the average first occurrence index.

Lu: There's a built-in initial constraint that excludes places where the start activity appears in the postset or the end activity in the preset. Those places can never have fitting behavior, so there's no point in generating them.

Meng: That's a nice example of domain knowledge being embedded directly into the generator. It reduces the search space before any evaluation happens.

Lalam: The whole tree design anticipates the monotonic properties that make pruning sound. The structure and the constraints are aligned, which is not accidental. It's the core of the framework's efficiency.

Tom: So we now have a supply of candidate places, each with fitness scores. The next challenge is deciding which ones actually remain in the final model.

Jane: That's the composition stage, and the paper's greedy version is on page twenty-five.

Page 5 of the paper: Tom: Page twenty-five introduces the greedy composing algorithm. Each proposed place gets evaluated, and then a deliberate acceptance function decides its fate. The decision can be to accept, reject, or replace an existing place in the result set.

Jane: The replacement option is interesting, because it lets the algorithm correct earlier choices. If a new place dominates an old one on the relevant metrics, you can swap it in.

Lu: The evaluation combines individual metrics, like the fitness fractions, with relative metrics that look at the current intermediate result. The relative part is where implicitness checking comes in.

Meng: An implicit place is one that doesn't change the fitting behavior of the already accepted set. Adding it would increase complexity without adding any constraint, so it's usually filtered out.

Tom: The paper also restates Theorem three, which is the engine behind constraint generation. If a place is underfed on a behavior, any postset expansion is also underfed on that behavior.

Jane: So when a candidate fails the fitness threshold on enough traces, the algorithm can generate a constraint that prunes its postset descendants. That's exactly how evaluation feeds back into proposal.

Lu: The same idea works for overfedness with preset expansions, though the tree structure makes that case more limited. The paper discusses why that asymmetry exists.

Meng: The greedy approach is online, so it makes local decisions without seeing the future. That's a known weakness, but it's also what makes the algorithm very fast.

Lalam: And the framework isn't limited to this greedy baseline. There are relaxed greedy variants that postpone decisions using a priority queue, which helps with infrequent behavior.

Tom: After the cycle ends, there's a post-processing stage that can remove implicit places structurally and merge self-loop places. That's a global cleanup pass that compensates for the local decisions made during the cycle.

Jane: We've covered the conceptual framework, but we haven't yet seen what the implementation actually looks like. The next page, thirty-one, dives into the software.

Page 6 of the paper: Tom: Page thirty-one is about the implementation, and the standout feature is the supervision system. Because the execution is so dynamic, with heuristics, constraints, and greedy decisions interacting, the authors wanted a way to observe what actually happened during a run.

Jane: They let components emit custom events that are collected asynchronously. Supervisors can then inspect those events, even while the discovery is still running.

Lu: That's what powers the live view in the ProM plugin. You can watch the accepted places change in real time, which is a great way to understand the effect of parameter changes.

Meng: The same system provides detailed timing information per task. When you're testing a new variant, that's invaluable for finding bottlenecks.

Tom: The framework uses a requirement management system underneath. Components can request and provide data dynamically, which keeps interfaces minimal but still allows a lot of flexibility.

Jane: And there are several component instantiations already available. On the proposal side there's depth-first and breadth-first traversal, heuristic expansion using scoring metrics, and different activity ordering strategies.

Lu: On the composition side, they have fitness filtering, uniwired nets, the delta variant, and both replay-based and LP-based implicit place removal. Some of these can be nested, so you can build complex strategies from simpler pieces.

Meng: The plugin itself guides users through pre-processing, configuration, discovery, and results. The discovery view is constantly updated, and you can cancel gracefully and still go to post-processing.

Lalam: The real significance here is that this is a prototyping environment for researchers. You can swap one evaluator or one constraint and immediately see the consequences, without reimplementing the whole search framework.

Tom: And that's exactly what the evaluation section does. It takes the available components, runs them over a diverse set of logs, and measures runtime and model quality.

Jane: The runtime summary is on page thirty-seven, and it reveals a lot about where the approach is practical and where it struggles.

Page 7 of the paper: Tom: Page thirty-seven has the runtime summary across all sixty parameter combinations. The three synthetic logs, Teleclaims, Repair, and Reviewing, are mostly fast, with PEC cycling often finishing within seconds.

Jane: But the real-life logs show the cost of complexity. HospitalBilling times out in about a third of the runs, and BPIC12 times out in more than half. The hardest logs are the ones with many unique activities.

Lu: The table separates PEC cycling from post-processing. Post-processing is often the bottleneck, because the LP-based implicit place removal has to solve a huge number of linear programs.

Meng: They set a ten-minute limit for each stage, and termination is cooperative, so the recorded times can slightly exceed the limit. Still, a timeout is a strong signal that the intermediate model is too large.

Tom: The paper also looks at the median number of collected places for the runs that didn't finish. It's in the thousands, sometimes over six thousand for BPIC12. That's why post-processing can't terminate.

Jane: The authors don't treat this as a fundamental failure. They argue it shows the need for more sophisticated filters and acceptance rules.

Lu: And on the opposite end, some excellent models are found very quickly. Teleclaims reaches perfect F1 in half a second at depth limit three.

Meng: That's a really encouraging pattern. The best models often appear early, which suggests that a complete traversal isn't always necessary.

Lalam: The practical takeaway is that you can choose between a thorough search with guarantees and a quick heuristic run, depending on your time budget and the noise level of the data.

Tom: Now, how do the parameters, τ and tree depth, affect quality? The correlation analysis on page forty-three has some surprising results, especially for noisy logs.

Jane: Let's dig into that.

Page 8 of the paper: Tom: Page forty-three examines the effect of τ, the fitness threshold, and the maximum tree depth on model quality. The paper computes Spearman rank correlations while controlling for the other parameter, so you get a cleaner picture.

Jane: And there's a real inversion. For the synthetic logs, increasing τ tends to improve fitness, but for the real-life noisy logs, it actually hurts fitness.

Lu: That's intuitive once you think about it. Noisy logs contain lots of infrequent and exceptional behavior, so requiring every place to fit most traces leaves you with very few places, and the model underfits.

Meng: Precision always benefits from a lower τ, because you need more, looser places to properly constrain the model. That's consistent across all the logs.

Tom: Tree depth, on the other hand, almost always helps. More depth means places with more arcs, which can express more precise constraints. The effect is especially strong for fitness on real-life logs.

Jane: There's also a neat practical observation. The best models are often discovered in the fastest runs, which means you don't have to wait for the full traversal to get a high-quality result.

Lu: The paper shows that maximal fitness and precision are frequently reached at low tree depths. That's a strong argument for setting depth limits explicitly to control runtime.

Meng: The percentile analysis is very useful. It shows that the runs reaching the top quality metrics are consistently among the faster executions, so early stopping isn't just a gamble.

Lalam: This kind of parameter analysis is exactly what practitioners need, because the right settings depend heavily on the log's complexity and noise.

Tom: And the paper grounds these findings in concrete models. The road traffic fine model on page forty-nine is a great example of both the strengths and the quirks of the approach.

Jane: Let's take a look at that model.

Page 9 of the paper: Tom: Page forty-nine shows one of the best models for the Road Traffic Fine Management log. It achieves a fitness of 0 point 93 and a precision of 1, and it perfectly fits 68 percent of the traces.

Jane: What's remarkable is that this model was discovered by three different runs with τ equal to 0 point 7, at depth limits three, four, and five. The runtimes were quite different, but the model quality was essentially the same.

Lu: There's a strange detail though. The activity "Appeal to Judge" can never actually occur in a model trace, because of a connected self-loop place.

Meng: Why does that happen? Because that behavior appears in fewer than seventy percent of the traces, so the self-loop place passes the τ filter even though it's effectively dead.

Tom: In other words, the place fits enough traces locally, but when combined with the whole model, it becomes unreachable. The global behavior is stricter than the local fitness suggests.

Jane: The paper calls it a strictly-said dead part and says it should be regarded as an approximation. That's an honest acknowledgment of the gap between place-local thresholds and model-level semantics.

Lu: It's a limitation of the greedy, threshold-based composition, and it points directly to the need for more global acceptance criteria.

Meng: Still, the model is precise and simple enough to be human-readable, and it was found in under two seconds at the shallowest depth. That's a real selling point.

Lalam: The example is instructive because it shows both the expressiveness and the residual weaknesses. The framework can find models that other miners can't, but it still doesn't have full control over the global semantic consequences of local decisions.

Tom: That fits neatly with the future work the authors outline in the conclusion. They want to move to more global composition strategies and better constraints.

Jane: So let's wrap up with what the paper contributes and where this line of research is going.

Conclusion: Tom: To wrap up, the paper delivers a complete framework for bottom-up Petri net discovery, formalized as a proposal, evaluation, and composition cycle, followed by post-processing.

Jane: The central technical contribution is the use of monotonicity to prune the candidate tree while preserving completeness guarantees. That's what makes the exponential search space manageable.

Lu: They provide concrete child generation logic, greedy composition, and a post-processing pipeline, all backed by an open-source implementation and a ProM plugin.

Meng: The evaluation shows that the framework can produce high-quality models on both synthetic and real-life logs, and often does so in the early stages of the search.

Lalam: For the field, the paper demonstrates that bottom-up discovery doesn't have to be an academic curiosity. With the right pruning, it can compete with established top-down methods on expressiveness.

Tom: There are honest limitations. The current version only handles uniquely labeled transitions, and noisy logs can generate huge intermediate results. Both are acknowledged in the paper.

Jane: What stuck with me is the simple example that most miners get wrong, the delivery with the order-and-invoice dependency. That one tiny log shows why bottom-up synthesis is worth the extra complexity.

Lu: And the evaluation's parameter analysis gives concrete guidance. You need a lower τ for noisy logs, and higher tree depth for better precision.

Meng: The ProM plugin means these insights are not locked in a paper. People can actually run the framework and see the trade-offs for themselves.

Lalam: That's the kind of transition process mining needs, from closed algorithms to open, configurable frameworks.

Tom: We're looking forward to seeing where this line of work goes next.

Jane: And with that, we'll say goodbye to this paper and get ready for the next one.

Tom: Thanks for listening, and we'll catch you on the next episode.