Andrea Burattin
Associate Professor
Technical University of Denmark
Graph-based similarity measures for the structural comparison of process traces
C. Schreiber, A.A. Andaloussi, A. Burattin, A. Oberweis, B. Weber
Abstract
Similarity measures are commonly applied for a variety of process mining techniques, such as trace clustering, conformance checking, and event abstraction. Yet, these measures generally fail to recognize similarity based on structural process features, such as the order of activities, loops, skips, choices, and parallelism. To make this more explicit, we propose a set of properties that allow to evaluate, what kind of structural features are reflected by a similarity measure. We further propose a novel approach leveraging existing graph-based algorithms and instance graphs to extract high-level structural features (loops, skips, choices, and parallelism) from traces, such that they can be used to extend and improve existing similarity measures. These algorithms are well-established in graph theory and can be computed efficiently. Finally, we provide an evaluation of the proposed approach based on synthetic and real-world datasets. The evaluation provides evidence that the additional graph-based features can substantially improve the similarity comparison of traces in several cases. This applies in particular for the comparison of user behavior (e.g., based on eye tracking data) where structural features enable the detection of specific behavioral patterns.
Paper Information and Files
In Information Systems, vol. 138 (2026).
- DOI: 10.1016/j.is.2025.102671
- BibTeX: see at DBLP
- Download text © 2026. This manuscript version is made available under the CC-BY-NC-ND 4.0 license http://creativecommons.org/licenses/by-nc-nd/4.0/./.
General rights
Copyright and moral rights for the publications made accessible in the public website are retained by the authors and/or other copyright owners and it is a condition of accessing publications that users recognise and abide by the legal requirements associated with these rights.
- Users may download and print one copy of any publication from the website for the purpose of private study or research.
- You may not further distribute the material or use it for any profit-making activity or commercial gain.
If you believe that this document breaches copyright please contact us providing details, and we will remove access to the work immediately and investigate your claim.