Source-linked AI summary
Structure-Aware Message Passing on Petri Nets through Directed Walks and Incidence Diffusion
Geri Skenderi
TL;DR
Learned Petri-net representations have left directed cycles and incidence-based invariants implicit, despite their structural relevance to process models. The paper exposes them through walk-based positional encodings and incidence-diffusion-gated messages; the constructions improve results on both benchmarks, including PDC factor prediction and ProcRosetta retrieval.
Problem
Learned Petri-net representations leave directed-cycle structure and incidence-matrix invariants implicit, motivating the question of whether exposing these structures can improve process-model representations.
Source: §1 · p. 1Method
The paper adds return-probability positional encodings for alternating place-transition walks and incidence-diffusion kernels that gate same-type messages in GNNs.
Source: §1 · p. 2Results
Macro balanced accuracy on PDC 2023 rises from 0.751 to 0.832 when both constructions are used, while DA-PNGNN improves ProcRosetta net-to-tree retrieval by up to 5.9 top-1 accuracy points.
Source: §1 · p. 2Takeaways & Limitations
The diffusion kernels improve both supervised generation-factor prediction and self-supervised multimodal alignment, with the ProcRosetta configuration selected on PDC used without retuning.
Source: §1 · p. 2, §6.2 · p. 20Both benchmarks use unit arc weights, so whether the kernels help with arc multiplicity distinctions remains untested.
Source: §6.1 · p. 20
Abstract
from arXiv · showhide
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.
1 Introduction
The paper asks whether Petri-net structure can improve learned process-model representations, then introduces cycle-aware walk encodings and incidence-based diffusion messages for GNNs. Both constructions improve benchmark results, with diffusion kernels improving performance on both tasks.
1 Introduction
- Prior work learns Petri-net representations for retrieval and classification, and aligns nets with generating process trees and associated event logs.Petri nets are directed bipartite process models whose incidence matrices encode conservation.Source: §1 · p. 1
- The motivating gap is that existing approaches leave directed-cycle position and incidence-based conservation implicit in learned Petri-net representations.The paper asks whether exposing these structural biases can improve learned process-model representations.Source: §1 · p. 1
- PNRWPE extends random-walk positional encoding using return probabilities of alternating place-transition walks, with a teleportation variant for acyclic nets.Both encodings are equivariant to node reordering and can be computed for a new net.Source: §1 · p. 2
- DA-PNGNN uses incidence-matrix diffusion kernels to gate same-type messages, encoding token-balance structure alongside ordinary messages.The construction is compatible with any message-passing architecture and can be combined with PNRWPE.Source: §1 · p. 2
- Macro balanced accuracy rises from 0.751 to 0.832 on PDC 2023 when both constructions are used, and DA-PNGNN improves ProcRosetta net-to-tree retrieval by up to 5.9 top-1 accuracy points.The ProcRosetta configuration chosen on PDC 2023 was used without retuning.Source: §1 · p. 2
2 Preliminaries
The preliminaries establish message passing and random-walk positional encoding on graphs, then define the Petri-net structure and incidence matrix used in the paper. The incidence matrix records token changes as transitions fire.
2.1 Graph neural networks
- Message passing learns graph representations by repeatedly aggregating neighboring node features with differentiable, permutation-invariant functions.A positional encoding can supplement node features with structural-role information; random-walk encodings use return probabilities at different walk lengths.Source: §2.1 · p. 3
2.2 Petri net structure
- A Petri net has place and transition partitions, nonnegative integer arc multiplicities, and incidence matrix B = E+ − E− encoding each place’s token change when a transition fires.Inhibitor, timed, and colored-net semantics are outside this study’s scope.Source: §2.2 · pp. 3–4
- An enabled transition firing sequence with transition-count vector x updates marking m to m′ = m + Bx.Source: §2.2 · p. 4
3 Petri net random-walk encodings
PNRWPE represents places and transitions through return probabilities of alternating walks, correcting for sinks so probability mass is retained. A teleportation variant adds return routes in acyclic nets, though long horizons converge toward stationary behavior.
3 Petri net random-walk encodings
- PNRWPE records return probabilities after 2, 4, …, 2K steps for alternating place-transition walks, with sink absorption keeping missing probability mass at the current node.The two-step operators separately describe returns for places and transitions; odd-step returns are impossible in the bipartite graph.Source: §3 · p. 4
3.1 Acyclic nets
- On acyclic nets, the original encoding’s return signatures can be highly correlated because returns rely on added self-loops, limiting discrimination between different structures.Source: §3.1 · p. 5
- Teleportation lets the walker jump uniformly to the opposite node type, creating return paths even in acyclic nets and capturing more than stopping probabilities alone.Because the two-step chains converge to stationarity, short finite horizons are preferable; distinct nodes are not guaranteed to receive distinct encodings.Source: §3.1 · p. 5
4 Diffusion-augmented message passing on Petri nets
Incidence diffusion distinguishes token-balance structure that random-walk signatures can miss, then supplies same-type pair features for gated messages in DA-PNGNN. The diffusion is symmetric and does not directly encode execution direction, so ordinary arc messages remain part of the architecture.
4.1 Incidence diffusion
- Incidence diffusion is motivated by nets whose token-production difference is invisible to PNRWPE but whose incidence matrices distinguish their conservation behavior.Place and transition invariants correspond to the left and right null spaces of the incidence matrix; diffusion suppresses imbalanced signal components while retaining invariant ones.Source: §4.1 · pp. 6–7
- The diffusion operators implement discrete updates based on the place and transition Gram matrices, with zero modes fixed and positive modes contracted.The step scale γ is chosen larger than the squared spectral norm of B, supporting the contraction property.Source: §4.1 · p. 7
4.2 Diffusion-augmented Petri net graph neural networks
- DA-PNGNN adds messages from every same-type node, gated by learned functions of diffusion pair features, alongside standard message passing.This makes all same-type nodes available in one round, including nodes beyond the reach of the original arc-message rounds.Source: §4.2 · p. 8
- The diffusion kernels are symmetric and do not directly encode direction or execution semantics, so the architecture retains the original arc messages.Reordering nodes transforms the operators equivariantly, and a permutation-invariant readout yields a node-order-independent graph representation.Source: §4.2 · pp. 8–9
5 Experiments
The experiments evaluate directed-walk positional encodings and incidence-diffusion messages for Petri-net learning across supervised factor prediction and ProcRosetta net-query tasks. They use benchmark comparisons and controlled ablations to examine the contributions of these structural signals.
5.1 Experimental setting
- The benchmarks comprise 96 PDC 2023 process models and self-supervised ProcRosetta datasets with 4,000 training, 512 validation, and 512 test processes per setting, generated once with seed 13 and frozen.The loops setting extends the original acyclic setting; both benchmarks use ProcRosetta optimization settings without tuning, and no arm received a hyperparameter search.Source: §5.1 · pp. 9, 11, 12
5.2 Supervised factor prediction on PDC 2023
- 0.832 macro BA is achieved on PDC by combining PNRWPE with either DA-PNGNN gate; DA-PNGNN alone gains 0.078 over the plain PNGNN with the linear gate.PNRWPE alone raises macro BA by 0.044 and nearly doubles loop-factor B balanced accuracy, from 0.275 to 0.506; the combined-method margin over the linear gate alone is within seed deviation.Source: §5.2 · p. 13, Table 1 · p. 14
- Zeroing DA-PNGNN’s diffusion kernels drops macro BA to 0.686 ± 0.039 with the linear gate and 0.698 ± 0.025 with tanh, below the plain PNGNN.The control retains parameters, pairwise connections, and sum aggregation, indicating that the incidence-kernel content—not merely all-pairs connectivity—supports the gain.Source: §5.2 · p. 14
- PNRWPE signatures rarely identify individual nodes, yet net-specific pooled descriptors preserve useful cycle information: pooled PNRWPE separates loop factor B perfectly.The encoding’s signatures are identical under changes to silent-transition visibility and activity labels because those changes leave the incidence matrices unchanged; undirected RWPE yields only +0.010 ± 0.024 macro BA at 16 steps and no loop-factor difference.Source: §5.2 · pp. 15–16
5.3 Self-supervised multimodal alignment on ProcRosetta
- +5.9 points in net→tree top-1 retrieval on acyclic ProcRosetta nets and +4.1 points with loops accompany DA-PNGNN improvements across retrieval directions.With loops, decoding and reconstruction also improve: the net-to-tree loss falls by 0.012 in every seed, while the exact-tree rate rises 0.7 points to 36.0% in 8 of 10 seeds.Source: §5.3 · pp. 16–17
- Against the zero-kernel control, the full model improves net→tree, net→log, behavior ρ, and normalized edit distance, with consistent results across seeds.In the paper setting, the gains are 5.5 points on net→tree, 1.8 on net→log, 0.017 on behavior ρ, and 0.008 on normalized edit distance, each in at least 9 of 10 seeds; the control is only 0.4 points above baseline on net→tree. With loops, the control is 0.6 points below baseline on net→tree, and the full model beats it in at least 9 of 10 seeds on edit distance, behavior L1, ρ, NN behavior, net→tree, tree→net, net→log, and loss.Source: §5.3 · p. 17
- On acyclic nets, PNRWPE signatures are constant across 16 steps and offer negligible downstream gains; with loops, they vary and yield small, consistent improvements on select metrics.On the paper setting’s 4,000 training nets, signatures are 87.9% all-zero and 12.1% all-one, averaging four distinct signatures per net. With loops, at K = 16, 43.8% of nodes are all-zero, 54.0% are constant, and there are 7.8 distinct signatures per net; PNRWPE improves normalized edit distance by 0.004, behavior L1 by 0.006, and NN behavior by 0.003 in 9 of 10 seeds, while ρ and retrieval remain within noise.Source: §5.3 · pp. 17–18
- Although PNRWPE beats its shuffled version, the shuffle is worse than the plain baseline, so this comparison does not show that correctly placed signatures help.The shuffled configuration underperforms the plain baseline by 1.3 and 1.0 points on net→tree in the two settings, respectively; the comparison shows the signatures act as noise, not that they help beyond no positional input.Source: §5.3 · p. 18
- Teleportation removes PNRWPE’s feature degeneracy, but the added variation does not translate into useful downstream performance.At K = 8, all-zero signatures disappear, constant signatures fall to a few percent, and distinct signatures per net rise from 4.0 to 12.3 in the paper setting and from 7.6 to 15.8 with loops. Despite these diagnostics, downstream changes are at most two points or about 0.01; against the width-matched original encoding, gains shrink to within a point while behavior ρ declines by 0.018 to 0.023 in all ten seeds with loops.Source: §5.3 · pp. 18–19, Table 4 · p. 19
- Teleportation’s extra variation is largely redundant and semantically fictitious, limiting its value as a positional encoding.The two α values separate exactly the same nodes in more than 99.5% of training nets, while the first principal direction carries 97.9% of coordinate variance in the paper setting and 93.0% with loops; the added return routes have no counterpart in Petri-net semantics.Source: §5.3 · p. 19
6 Conclusion
The paper exposes directed-cycle position and incidence-matrix token balance to Petri-net GNNs, with diffusion kernels improving results on both benchmarks and walk encodings helping most on cyclic nets.
6.1 Limitations and future work
- The evidence covers two synthetic net families; whether the constructions help other self-supervised objectives or behavior-based process-similarity tasks remains untested.The benchmarks measure generation-factor recovery and the geometry of a self-supervised latent space shared with two other process views.Source: §6.1 · pp. 19–20
- Pair kernels require O(n^2 P + n^2 T) storage per exponent and dense matrix powers cost cubic time, limiting the demonstrated scaling to nets of tens of nodes.Industrial-scale models would need sparse structures or a low-rank factorization; the linear gate costs 2.6 times the plain encoder’s PDC epoch time.Source: §6.1 · p. 20
6.2 Concluding remarks
- Diffusion kernels improve both supervised generation-factor recovery on PDC 2023 and ProcRosetta’s self-supervised multimodal objective, using the PDC configuration on ProcRosetta without retuning.Zeroing the kernels while retaining parameters and same-type connections loses the entire gain.Source: §6.2 · p. 20
- PNRWPE helps most when nets contain directed cycles and carries almost no information on acyclic nets, as its derivation predicts.Source: §6.2 · p. 20
- The paper frames Petri-net learning as a promising, largely unexplored direction at the intersection of geometric deep learning and process mining.Source: §6.2 · p. 20
A Experimental arms
The appendix lists the experimental arms run on both benchmarks, with the teleportation PNRWPE arms treated separately on PDC.
A Experimental arms
- Table 5 enumerates every arm run on the two benchmarks; each PDC arm trains one model per fold and seed, while each ProcRosetta arm trains one joint multimodal model per seed and setting.Source: A Experimental arms · p. 23, Table 5 · p. 23
- Teleportation PNRWPE was also run on PDC under the same protocol, but those arms are omitted because the construction targets acyclic nets and ProcRosetta’s paper setting was its design target.Source: Table 5 · p. 23
B Additional results on PDC
The additional PDC results show a consistent paired advantage for real diffusion kernels over zero-kernel controls, while the walk-length study finds no added gain beyond K = 8.
B Additional results on PDC
- Real kernels beat the zero-kernel control in all ten seeds across all four configurations, by 0.126 to 0.143 macro BA.Table 6 reports paired macro-BA differences as mean ± standard deviation, with the positive-seed count in parentheses.Source: B Additional results on PDC · p. 23, Table 6 · p. 24
- The PNRWPE gain is in place by K = 8, and a longer walk of K = 24 adds nothing.Figure 4 compares macro-BA gains for PNGNN + PNRWPE and fused PetriNet2Vec, and pooled-descriptor BA on B.Source: B Additional results on PDC · p. 23, Figure 4 · p. 25
- PNRWPE as a pooled descriptor scores 0.083 balanced accuracy on factor D because 80 arc-duplicate nearest neighbors carry the opposite D label and the other 16 cases land at chance.The validation split does not group nets differing only in D; all 80 exact arc-duplicates are therefore misclassified by 1-NN.Source: B Additional results on PDC · p. 23, Figure 3 · p. 24
C Depth of message passing
Table 7 lists the depth-of-message-passing variants and their values under the main protocol.
C Depth of message passing
- Table 7 reports values for plain PNGNN, linear-gate DA-PNGNN, and DA-PNGNN with PNRWPE across one to five message-passing rounds, with other settings unchanged from the main protocol.Source: C Depth of message passing · p. 25
L PNGNN DA-PNGNN DA-PNGNN + PNRWPE
Table 7 reports PDC balanced-accuracy results across message-passing depths, with separate summaries for macro BA and BA on B.
L PNGNN DA-PNGNN DA-PNGNN + PNRWPE
- Table 7 reports macro BA in its top half and BA on B in its bottom half.Source: Table 7 · p. 25
- The table compares models using L = 1 to 5 message-passing rounds.Source: Table 7 · p. 25
- Results are mean ± standard deviation over ten seeds, and the L = 3 rows reproduce Table 1.Source: Table 7 · p. 25
D Computational cost
The section compares training costs across PNGNN variants and reports that DA-PNGNN’s overhead depends strongly on the gate, while PNRWPE adds little time or memory.
D Computational cost
- The reported costs do not establish scaling behavior because the evaluated nets are small, which hides asymptotics.Source: D Computational cost · p. 25
- On PDC, the linear gate multiplies plain-encoder epoch time by 2.6 and memory by 1.9, while the tanh gate multiplies them by 10 and 17.PDC runs show no accuracy advantage for tanh, so the linear gate is treated as the default.Source: D Computational cost · pp. 25–26
- On ProcRosetta, the linear gate adds 4 to 5% per epoch and little memory, while tanh adds 11% and 2.4 to 4.3 times the memory.Source: D Computational cost · p. 26
- PNRWPE adds a few milliseconds per PDC epoch, at most 6% per ProcRosetta epoch, and no memory.Table 8 reports that PNRWPE changes PDC time per epoch by at most 0.007 s and peak memory by at most 1 MB.Source: D Computational cost · p. 26, Table 8 · p. 26
- Figure 5 plots seconds per epoch against peak GPU memory for each variant, measured alone after one warm-up epoch and averaged over three timed training-and-validation epochs.The PDC results are on the left and ProcRosetta results on the right; ProcRosetta shows paper and loops settings.Source: Figure 5 · p. 26
E Teleportation results on ProcRosetta
Table 9 summarizes paired ProcRosetta comparisons for teleportation PNRWPE at K = 8 across two settings and α values. Its final rows isolate slower mixing and report no consistent effect.
E Teleportation results on ProcRosetta
- Table 9 reports paired mean differences over seeds 13 to 22 for both ProcRosetta settings and both α values.Source: E Teleportation results on ProcRosetta · p. 27, Table 9 · p. 27
- The comparisons cover behavior L1, net-to-tree loss, exact-tree rate, and top-1 retrieval in both net-to-tree and tree-to-net directions.Lower is better for behavior L1 and net-to-tree loss; retrieval and exact-tree differences are in percentage points.Source: Table 9 · p. 27
- The final row for each setting isolates slower mixing and finds no consistent effect.Source: Table 9 · p. 27