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

Geri Skenderi

cs.LGOct 21, 2026

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

Authors: Geri Skenderi

Organizations: HASH

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.

Figures & tables

Panel of Figure 1 — Figure 1: A change in token production that PNRWPE cannot detect. Unmarked arc weights are one. Subscripts 1 and 2 in the equations denote the left and right net, respectively.

Shallow embeddings observing every factor
Model	Macro BA $\uparrow$	BA on B, loops $\uparrow$
PetriNet2Vec	$0.808\pm 0.009$	$0.766\pm 0.047$
PetriNet2Vec + pooled PNRWPE	$0.811\pm 0.007$	$1.000\pm 0.000$
1-NN readout on a fixed descriptor, without activity labels
Structural statistics	$0.722$	$0.333$
Pooled PNRWPE	$0.722$	$1.000$

Table 1: PDC 2023: out-of-fold balanced accuracy, mean

\pm

standard deviation over the ten training seeds. The two 1-NN readouts are deterministic and do not depend on the training seed. The best and second-best results are marked within the end-to-end family without activity labels , which is the only group whose members share an information budget. Supervision, information access, and fitting protocol all differ between PetriNet2Vec and the PNGNNs (Section 5.1 ), please consult the text for context.

Figure 2: PDC: macro BA (left) and BA on B (right) against the number of message-passing rounds, mean and one standard deviation over ten seeds.

Paper setting (acyclic nets)
	Decoding from $\mu_{\rm net}$			Embedding		Loss
Encoder	Exact $\uparrow$	Edit $\downarrow$	L1 $\downarrow$	$\rho\uparrow$	NN $\downarrow$	N $\to$ T $\downarrow$
Original study, seed 13	35.9	0.282	0.839	0.574	0.913	0.837
PNGNN	35.9 $\pm$ 0.3	0.278 $\pm$ 0.003	0.833 $\pm$ 0.010	0.593 $\pm$ 0.010	0.935 $\pm$ 0.008	0.845 $\pm$ 0.004
+ PNRWPE	35.9 $\pm$ 0.2	0.276 $\pm$ 0.003	0.828 $\pm$ 0.007	0.584 $\pm$ 0.017	0.932 $\pm$ 0.003	0.842 $\pm$ 0.004
+ PNRWPE, shuffled	36.0 $\pm$ 0.3	0.278 $\pm$ 0.003	0.840 $\pm$ 0.006	0.566 $\pm$ 0.021	0.939 $\pm$ 0.008	0.849 $\pm$ 0.005

Table 2: ProcRosetta: decoding, embedding quality, and test loss of the net view under each encoder, on the 512 test processes. Each cell gives the mean over seeds 13 to 22 with the sample standard deviation. Decoding is from

\mu_{\rm net}

; N and T denote the net and tree views, and the last column is the net-to-tree test loss. The first row is the single published run of the original study, it is shown here for reference only. The best and second-best values of each setting are marked. PNRWPE uses

K=16

, and the shuffle permutes it across all nodes of each net. Retrieval for the same runs is in Table 3 .

Paper setting (acyclic nets)
	Retrieval top-1 (%) $\uparrow$
Encoder	N $\to$ T	T $\to$ N	N $\to$ L	L $\to$ N
Original study, seed 13	34.2	44.3	15.4	14.1
PNGNN	34.6 $\pm$ 1.3	45.0 $\pm$ 1.1	14.5 $\pm$ 1.1	13.5 $\pm$ 0.9
+ PNRWPE	36.0 $\pm$ 1.2	45.6 $\pm$ 1.6	14.7 $\pm$ 1.4	13.4 $\pm$ 0.6
+ PNRWPE, shuffled	33.3 $\pm$ 0.9	43.8 $\pm$ 1.2	13.8 $\pm$ 1.0	12.9 $\pm$ 0.7

Table 3: ProcRosetta: cross-modal retrieval top-1 accuracy with the Petri net modality, for the same runs as Table 2 . Each cell gives the mean over seeds 13 to 22 with the sample standard deviation. N, T, and L denote the net, tree, and log views, and X

\to

Y reads as querying with X against candidates of type Y. Higher is better throughout. The first row is the single published run of the original study, it is shown here for reference only. The best and second-best values of each setting are marked.

Setting	Encoding	All-zero	Constant	Colliding	Distinct	1st dir.
Paper	original	$87.9\%$	$100\%$	$86.9\%$	4.0	$100\%$
	teleport, $\alpha=0.85$	$0$	$5.7\%$	$46.3\%$	12.3	$97.9\%$
	teleport, $\alpha=0.95$	$0$	$5.7\%$	$46.4\%$	12.3	$95.9\%$
Loops	original	$45.7\%$	$55.8\%$	$82.8\%$	7.6	$89.9\%$
	teleport, $\alpha=0.85$	$0$	$4.9\%$	$36.1\%$	15.8	$93.0\%$
	teleport, $\alpha=0.95$	$0$	$4.9\%$	$36.1\%$	15.8	$79.0\%$

Table 4: Feature diagnostics at

K=8

on the 4000 training nets of each ProcRosetta setting. All-zero and Constant : nodes whose eight coordinates are all zero, or all equal. Colliding : nodes sharing their signature, to ten decimal places, with another node of the same type in the same net. Distinct : distinct signatures per net, counted per node type and summed. 1st dir. : share of the variance of the eight coordinates, over all nodes, along the first principal direction. Teleportation eliminates degeneracy on every count, yet the Colliding and Distinct columns are identical across the two values of

\alpha

. Slower mixing changes the values of the encoding, but not node separability.

Appendix figures & tables8 assets

Supplementary material from the paper’s appendix.

Appendix

Model	Node input or variant	Seeds
PDC 2023: supervised factor prediction and the PetriNet2Vec setting

PNGNN	no PE; PNRWPE ( $K=16$ ); PNRWPE shuffled within type or across nodes	0-9
PNGNN	undirected RWPE (16 or 32 steps); out-degree	0-9
DA-PNGNN	linear or tanh gate, sum aggregation, rescaled kernels; real or zero kernels; no PE or PNRWPE	0-9
Depth	PNGNN, DA-PNGNN (linear gate), and DA-PNGNN + PNRWPE at 1 to 5 message-passing rounds	0-9

Appendix

Table 5: Every arm run on the two benchmarks. Teleportation PNRWPE was additionally run on PDC under the same protocol, but we omit those arms since the construction targets acyclic nets and ProcRosetta’s paper setting is the setting it was designed for.

Paired comparison (first $-$ second)	Over 10 seeds
PNGNN + PNRWPE $-$ PNGNN	$+0.044\pm 0.032\ (9)$
PNGNN + PNRWPE $-$ same, shuffled across nodes	$+0.023\pm 0.026\ (9)$
PNGNN + PNRWPE $-$ same, shuffled within type	$+0.025\pm 0.027\ (8)$
PetriNet2Vec + pooled PNRWPE $-$ PetriNet2Vec	$+0.003\pm 0.009\ (6)$
Fusion: own $-$ another net’s descriptor	$+0.093\pm 0.007\ (10)$
DA-PNGNN, linear $-$ PNGNN	$+0.078\pm 0.041\ (10)$

Appendix

Table 6: PDC: paired differences in macro BA, mean

\pm

standard deviation over the ten seeds, with the number of seeds in which the difference is positive given in parentheses. Rows whose labels do not mention PNRWPE use no node input.

Figure 3: PDC: heatmap of the average BA for each factor. Best viewed in color.

Figure 4: PDC: effect of the walk length $K$ . Left: gain in macro BA of PNGNN + PNRWPE over PNGNN. Middle: the same gain for PetriNet2Vec fused with pooled PNRWPE. Right: BA on B of the pooled PNRWPE descriptor. Shaded bands show one standard deviation over ten seeds.

Macro BA $\uparrow$
$L$	PNGNN	DA-PNGNN	DA-PNGNN + PNRWPE
1	$0.580\pm 0.030$	$0.787\pm 0.028$	$0.835\pm 0.020$
2	$0.698\pm 0.026$	$0.833\pm 0.026$	$0.860\pm 0.016$
3	$0.751\pm 0.037$	$0.830\pm 0.011$	$0.832\pm 0.014$
4	$0.794\pm 0.035$	$0.821\pm 0.014$	$0.826\pm 0.009$
5	$0.786\pm 0.034$	$0.814\pm 0.015$	$0.811\pm 0.017$

Appendix

Table 7: PDC: macro BA (top) and BA on B (bottom), mean

\pm

standard deviation over ten seeds, for

L=1

5

message-passing rounds. The rows at

L=3

reproduce Table 1 .

Model	s / epoch	s / run	Epochs	Peak memory (MB)
PNGNN	$0.027$	$1.7$	$63$	82
DA-PNGNN, linear	$0.079$	$4.4$	$55$	159
DA-PNGNN, tanh	$0.152$	$8.0$	$53$	1363

Appendix

Table 8: PDC training cost on the GPU without node input: seconds per epoch and per run, and epochs until early stopping, averaged over the runs of the ten seeds (one per fold and seed). With PNRWPE the time per epoch changes by at most

0.007

s and the peak memory by at most 1 MB.

Figure 5: Seconds per epoch against peak GPU memory of every PNGNN variant, each trained alone on the GPU: one warm-up epoch, then the mean over three epochs, each a training and validation pass, on logarithmic axes. Left: PDC 2023. Right: ProcRosetta, where the joint multimodal model is timed, in the paper (circles) and loops (squares) settings.

Paper setting, $\alpha=0.85$
Comparison (first $-$ second)	Exact (pp)	L1	$\rho$	N $\to$ T (pp)	T $\to$ N (pp)	Loss
Teleport $-$ no PE	$+0.25\,(6)$	$-0.011\,(7)$	$-0.015\,(1)$	$+1.8\,(8)$	$+0.6\,(4)$	$-0.006\,(9)$
Teleport $-$ original $K=8$	$+0.16\,(5)$	$-0.006\,(7)$	$-0.008\,(3)$	$+0.7\,(7)$	$+0.4\,(7)$	$-0.004\,(9)$
Teleport $-$ shuffled	$+0.33\,(8)$	$-0.010\,(8)$	$+0.015\,(9)$	$+2.9\,(10)$	$+1.1\,(7)$	$-0.007\,(10)$
Shuffled $-$ no PE	$-0.08\,(4)$	$-0.002\,(7)$	$-0.030\,(0)$	$-1.1\,(3)$	$-0.5\,(3)$	$+0.002\,(5)$
DA + teleport $-$ DA	$-0.18\,(2)$	$-0.007\,(8)$	$-0.002\,(5)$	$-0.5\,(4)$	$+0.7\,(5)$	$0.000\,(6)$

Appendix

Table 9: ProcRosetta, teleportation PNRWPE at

K=8

: mean paired differences over seeds 13 to 22, with the number of seeds in which the first arm is better given in parentheses (lower is better for behavior L1 and the net-to-tree loss). The exact-tree rate and top-1 retrieval (N

\to

T: net

\to

tree, T

\to

N: tree

\to

net) differ in percentage points. Shuffled : teleportation PNRWPE permuted across all nodes of each net. DA : DA-PNGNN with the linear gate. The final row of each setting isolates the effect of slower mixing, and finds no consistent effect.

Representation Learning

Representation learning develops data transformations that expose useful structure for prediction, transfer, generation, and control.

See all 798 papers

Monotonicity-Guided Bottom-Up Petri Net Discovery: The SPECpp Framework
Aug 10, 2026Leah Tacke genannt Unterberg, Lisa L. Mannel, Wil M. P. van der AalstProcess Mining
Process And Data Science (PADS) RWTH Aachen University D-52074 Aachen, Germany
A Node Embedding Framework for Model-Centric Conformance Checking in Process Mining
Oct 13, 2026Mostafa Abbasi, Homayoun NajjaranProcess Mining Automated Evaluation
Faculty of Engineering and Computer Science, University of Victoria, Victoria, BC, Canada
Neural Petri flows for chemical reactions
Oct 6, 2026Jose Eduardo Escrig Molina, Daniel ProbstAI-Assisted Scientific Research Chemical Reaction Prediction
Bioinformatics Group Bioprocess Engineering Group Wageningen Unversity Wageningen, the Netherlands

Aug 10, 2026J/K move · Enter open · S save

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

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

Process And Data Science (PADS) RWTH Aachen University D-52074 Aachen, Germany

Process Mining

Open paper AskPDF arXiv

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.

Abstract

Representation Learning

Explore similar work

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

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

Neural Petri flows for chemical reactions