GPU-Based Graph Matching for Accelerating Similarity Assessment in Process-Oriented Case-Based Reasoning

Maximilian Hoffmann, Lukas Malburg, Nico Bach, Ralph Bergmann

In: Mark T. Keane, Nirmalie Wiratunga (Hrsg.). Case-Based Reasoning Research and Development. International Conference on Case-Based Reasoning (ICCBR) Springer Cham 2022.


In Process-Oriented Case-Based Reasoning (POCBR), determining the similarity between cases represented as semantic graphs often requires some kind of inexact graph matching, which generally is an NP-hard problem. Heuristic search algorithms such as A* search have been successfully applied for this task, but the computational performance is still a limiting factor for large case bases. As related work shows a great potential for accelerating A* search by using GPUs, we propose a novel approach called AMonG for efficiently computing graph similarities with an A* graph matching process involving GPU computing. The three-phased matching process distributes the search process over multiple search instances running in parallel on the GPU. We develop and examine different strategies within these phases that allow to customize the matching process adjusted to the problem situation to be solved. The experimental evaluation compares the proposed GPU-based approach with a pure CPU-based one. The results clearly demonstrate that the GPU-based approach significantly outperforms the CPU-based approach in a retrieval scenario, leading to an average speedup factor of 16.


2022_ICCBR__A_Star_GPU.pdf (pdf, 844 KB )

Deutsches Forschungszentrum für Künstliche Intelligenz
German Research Center for Artificial Intelligence