Publication
A*-Based Similarity Assessment of Semantic Graphs
Christian Zeyen; Ralph Bergmann
In: Ian Watson; Rosina O. Weber (Hrsg.). Case-Based Reasoning Research and Development - 28th International Conference, Proceedings. International Conference on Case-Based Reasoning (ICCBR-2020), June 8-12, Salamanca, Spain, Pages 17-32, Lecture Notes in Computer Science, Vol. 12311, Springer, 2020.
Abstract
The similarity assessment of graphs is a fundamental problem that is particularly challenging if efficiency is of core importance.
In this paper, we focus on a similarity measure for semantically labeled graphs whose labels are composed in an object-oriented manner. The measure is based on A* search and is particularly suited for case-based reasoning as it can be combined with knowledge-intensive local similarity measures and outputs similarities and corresponding mappings usable for explanation and adaptation. However, particularly for large graphs, the search space must be pruned to improve efficiency of A* search at the cost of sacrificing global optimality. We address this issue and present complementary improvements of the measure, which we systematically evaluate for the similarity assessment of semantic workflow graphs. The experimental results demonstrate that the new measure considerably reduces the computation time and memory consumption while increasing the accuracy.