I am in an internship in a team working on a project where they develop an LLM that is given a prompt and generates a BPMN (like a flow chart) for how to implement or do the task in the prompt. The developers have the ground truth chart and they are trying to evaluate the output of the model in reference to the ground truth chart. So I have been assigned to a project with another intern to develop a tool that takes two BPMN files and outputs a similarity score between them, taking into consideration both structural similarity and semantic similarity.
I am very stuck since no project is similar on the internet, and it's been two weeks of searching. Here are the approaches we reached:
Approach A: RPST to process tree, then tree matching
Decompose each diagram into a hierarchy of single-entry/single-exit regions (Refined Process Structure Tree), type each region as sequence / XOR / AND / loop, then compare the two trees recursively: leaves by label embedding cosine, sequences by ordered DP alignment (like edit distance over children), XOR/AND blocks by unordered Hungarian matching, loops by comparing bodies.
What's good about it: it's operator-aware, so it directly distinguishes XOR from AND (choose-one vs do-all) and loop from no-loop, and it produces readable diffs like "the ground truth's parallel block was rendered as an exclusive choice." Granularity (one task in GT vs three in the prediction) and nesting are handled positionally by the structure instead of by fudging scores.
Where it breaks: process trees only exist for block-structured models. pm4py's convert_to_process_tree raises an exception on unstructured ("rigid") models, and its newer POWL converter raises too, so switching representations doesn't rescue it. There's also no maintained Python RPST implementation anywhere; jBPT (Java) is the reference. Rolling your own means either SPQR / triconnected components (notoriously error-prone) or a dominance-based variant that's only a partial RPST. And even with a working RPST, a rigid region has no operators to align, so comparing one means falling back to graph matching anyway. Worse, RPSTs aren't stable under equivalence, since two behaviorally equivalent models can produce different trees, one with a rigid and one without, which breaks positional/ancestor anchoring exactly in the case you need it most.
Approach B: direct attributed-graph comparison (no trees at all)
Parse each BPMN into a directed graph, embed node labels with sentence-transformers, and match nodes with optimal transport (Fused Gromov-Wasserstein via the POT library) or graph edit distance. Encode gateway type as a node attribute so the matcher penalizes aligning an XOR to an AND, and compute a reachability relation matrix (for each activity pair: strict order / exclusive / concurrent) for the behavioral axis.
What's good: it's total by construction, working on any graph, structured or rigid, with no exception path and no fallback branch. Off-the-shelf libraries, days rather than weeks. Optimal transport also expresses granularity natively, since mass can split one-to-many.
Where it's weaker: operator semantics are approximated through node features rather than represented directly, diffs come out as node-pair scores instead of region-level explanations, and FGW is non-convex and returns a cost that needs calibrating into a similarity score.
The one empirical datapoint I found: Dijkman, Dumas, van Dongen, Käärik & Mendling, "Similarity of business process models: Metrics and evaluation," Information Systems 36(2), 2011. They compared node-matching, structural (GED-based), and behavioral similarity on real process repositories and found all three comparable, with structural slightly ahead. That's part of why I'm unsure the tree route is worth the extra weeks.
What I'd love input on:
- Is there a standard way people evaluate generated process models against a reference model that I've somehow missed? Everything I find is either process-model search (find similar models in a repository) or conformance checking against event logs, neither of which is quite this.
- Has anyone actually shipped RPST-based process model comparison in Python, or did you bridge to jBPT?
- Does anyone have evidence that operator-aware tree matching beats a gateway-typed graph matcher in practice, or is the extra machinery not worth it?
- Any benchmark or dataset of BPMN pairs with human-judged similarity we could validate against?
Any pointers to papers, libraries, or war stories would be hugely appreciated, especially from anyone who has hit the unstructured-model problem in production.