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

The paper introduces SPECpp, a conceptual and software framework for bottom-up Petri net discovery in process mining. The core idea is to construct process models by iteratively proposing, evaluating, and composing individual Petri net places, rather than using top-down approaches like the Inductive Miner that impose block-structured constraints. The authors state: "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 framework is structured as a Proposal–Evaluation–Composition (PEC) cycle followed by post-processing. The proposal stage uses an efficient candidate tree to traverse the space of possible places, exploiting subtree-monotonicity properties to prune the search. The paper defines: A set of constraints C is subtree-monotonic w.r.t. generation logic g if for any p, p′ ∈ P with p′ ∈ cand g (p), ¬IC (p) =⇒ ¬IC (p′). This allows constraints to be applied locally, enabling efficient pruning without missing valid candidates. The concrete child generation logic grows places by incremental preset and postset expansions, with the tree rooted at the empty place.

For evaluation, the framework uses both individual and relative evaluators. A key individual evaluator is place fitness, based on token-based replay, which counts fitting, underfed, and overfed behaviors. The paper proves monotonicity properties: If p is underfed (overfed) on σ, any postset (preset) expansion of p is also underfed (overfed) on σ. These properties are lifted to the log level and used to generate constraints that prune the candidate tree. Relative evaluators include implicitness checks (both replay-based and LP-based) to remove redundant places.

Composition is handled by a greedy strategy that maintains an intermediate result set. The paper describes: The core strategy, in addition to generate-constraints as before, now lies in deliberate-acceptance which determines the manner in which the evaluated candidate is incorporated into the intermediate result. Constraints generated during composition include fitness thresholds (τ) and uniwiring constraints.

The implementation is available as an open-source repository on GitHub and as a ProM plugin with an interactive GUI. The plugin guides users through pre-processing, configuration, discovery (with live visualization), and results stages. The framework supports various component instantiations, including heuristic expansion strategies, activity ordering strategies, and multiple composer variants (fitness filtering, uniwired, delta, and implicit place removal).

The evaluation was conducted on synthetic logs (Teleclaims, Repair, Reviewing) and real-life logs (HospitalBilling, Sepsis, RTFM, BPIC12, BPIC20.DomDecl). Parameters varied were τ (fitness threshold), max tree depth, and implicitness calculator type, resulting in 60 combinations per log. Results show that acceptable fitness and precision are achievable on any input log, though complex real-life logs require larger models. The paper notes: good models were often obtained long before exhaustive traversal of the candidate space, indicating that effective ordering and pruning strategies can make incomplete traversals practically useful. For example, on Teleclaims, models with F1-score of 1 were found in as little as 0.5 seconds. The correlation analysis shows that an increase [in max tree depth] seems to always have a positive influence on fitness and precision, while the effect of τ varies between synthetic and real-life logs.

The paper concludes that bottom-up discovery avoids representational bias and can discover complex constructs like long-term dependencies, but suffers from exponential complexity. Future work includes more sophisticated heuristics, support for silent transitions, and relaxing greedy composition to avoid local optima. The authors emphasize the framework's flexibility: "We envision that this kind of discovery approach should be tuned to the user's needs. If there is enough time, a thorough traversal which actually provides some guarantees can be configured, otherwise a more heuristically guided instantiation can be used."

Improvements to AI Systems:

1. Constraint-Driven Search Pruning via Subtree-Monotonicity

• Implement a generic search module that uses formally verified monotonicity properties (e.g., underfed/overfed place expansions) to prune candidate spaces in any combinatorial optimization task.

• The improved AI system can explore exponentially large solution spaces (e.g., in neural architecture search, molecule generation, or program synthesis) by applying local constraints to eliminate entire subtrees without exhaustive evaluation, reducing runtime from hours to seconds.

2. Bottom-Up Composition for Unrestricted Model Discovery

• Replace top-down, block-structured generation (common in sequence-to-sequence models, hierarchical planners, or grammar-based generators) with a bottom-up, incremental composition of atomic components (like places).

• The improved AI system can discover free-choice constructs, long-term dependencies, and non-block-structured patterns in data (e.g., in event logs, user behavior sequences, or biological pathways) that are invisible to top-down approaches, leading to more accurate and expressive models.

3. Adaptive Heuristic Ordering with Early Stopping

• Integrate the paper’s finding that “good models are often obtained long before exhaustive traversal” by implementing an anytime algorithm that ranks candidates by fitness and precision, and stops when a user-defined quality threshold is met.

• The improved AI system can deliver high-quality solutions under strict time constraints (e.g., real-time process monitoring, online recommendation systems) by dynamically balancing exploration depth vs. time budget, with configurable guarantees (e.g., “find a model with F1 ≥ 0.9 within 2 seconds”).

4. Multi-Criteria Evaluation with Relative Redundancy Removal

• Use the paper’s dual evaluation (individual fitness + relative implicitness) to automatically detect and remove redundant components in any generative AI output (e.g., duplicate features in machine learning pipelines, redundant rules in expert systems, or overlapping subroutines in code generation).

• The improved AI system can produce minimal, non-redundant models or solutions, reducing memory footprint and inference latency while maintaining or improving accuracy.

5. Configurable Trade-Off Between Completeness and Speed

• Implement a user-tunable parameter set (e.g., fitness threshold τ, max tree depth, heuristic type) that allows the AI to switch between exhaustive, guaranteed exploration and heuristic, fast approximation.

• The improved AI system can adapt to diverse deployment scenarios: e.g., in safety-critical domains (medical diagnosis) it runs thorough search with formal guarantees, while in interactive settings (chatbots, real-time analytics) it uses aggressive pruning and early stopping.

6. Interactive Visualization and Live Feedback for Human-in-the-Loop AI

• Incorporate the ProM plugin’s live visualization and staged workflow (pre-processing → configuration → discovery → results) into AI systems that require human oversight.

• The improved AI system can show intermediate candidate models in real time, allow users to adjust constraints (e.g., fitness threshold) on the fly, and immediately see the impact on discovered patterns, enabling faster human-AI collaboration in complex decision-making.

7. Cross-Domain Transfer of Place-Based Discovery

• Generalize the concept of “places” to atomic, reusable units in other domains (e.g., latent states in reinforcement learning, motifs in time-series, or functional groups in chemistry).

• The improved AI system can discover hierarchical, non-sequential dependencies in heterogeneous data (e.g., multi-agent interactions, supply chain disruptions) by composing these units bottom-up, without imposing rigid top-down templates.

What the Improved AI System Can Do:

• Discover complex, non-block-structured patterns in event logs, user journeys, or network traces that current top-down miners miss.

• Solve combinatorial search problems (e.g., feature selection, hyperparameter tuning, circuit design) with provable pruning, achieving near-optimal results in seconds.

• Generate minimal, non-redundant models or code with automatic removal of redundant components.

• Operate under user-defined time/quality trade-offs, from exhaustive guaranteed search to fast heuristic approximation.

• Provide interactive, transparent model discovery with live visualization and user-adjustable constraints.

• Transfer its bottom-up composition and pruning logic to other AI subfields (e.g., causal discovery, grammar induction, or neural architecture search) to improve scalability and expressiveness.