A study on $$k$$-$$walk$$ generation algorithm to prevent the tottering in graph edit distance heuristic algorithms

Abstract Graph edit distance is usually used for graph similarity checking due to its low information loss and flexibility advantages. However, graph edit distance can’t be used efficiently because it is an NP-Hard problem. Many graph edit distance heuristic algorithms have been proposed to solve this problem. However, some heuristic algorithms for generating $$walk$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>walk</mml:mi> </mml:mrow> </mml:math> generate unnecessary sequences because of the tottering, which leads to many problems. Because of this, various problems arise, like a decrease in approximation accuracy and an increase in execution time. In this paper, we propose an accurate and efficient graph edit distance heuristic algorithm that prevents tottering when generating $$walk$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>walk</mml:mi> </mml:mrow> </mml:math> . When generating $$walk$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>walk</mml:mi> </mml:mrow> </mml:math> , the traversed node‘s information is saved into the queue and then proceeds to traverse the next node. Then, it is possible to prevent the tottering by comparing an existing traversed node with an enqueued one. Through this, we propose a new $$walk$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>walk</mml:mi> </mml:mrow> </mml:math> generation algorithm that prevents generating unnecessary $$walk$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>walk</mml:mi> </mml:mrow> </mml:math> and applies it to existing algorithms to prevent the tottering.