The need to identify graphs having small structural distance from a query
arises in biology, chemistry, recommender systems, and social network analysis.
Among several methods to measure inter graph distance, Graph Edit Distance
(GED) is preferred for its comprehensibility, yet hindered by the NP-hardness
of its computation. State-of-the-art GED approximations predominantly employ
neural methods, which, however, (i) lack an explanatory edit path corresponding
to the approximated GED; (ii) require the NP-hard generation of ground-truth
GEDs for training; and (iii) necessitate separate training on each dataset. In
this paper, we propose an efficient algebraic unsuper vised method, EUGENE,
that approximates GED and yields edit paths corresponding to the approx imated
cost, while eliminating the need for ground truth generation and data-specific
training. Extensive experimental evaluation demonstrates that the
aforementioned benefits of EUGENE do not come at the cost of efficacy.
Specifically, EUGENE consistently ranks among the most accurate methods across
all of the benchmark datasets and outperforms majority of the neural
approaches.

本文提出了一种高效的代数无监督方法 EUGENE，它近似计算图的编辑距离，并产生对应的编辑路径，同时消除了对真实编辑距离的生成和数据特定训练的需求。广泛的实验评估表明，EUGENE 在各个基准数据集中始终排名最准确的方法之一，并且胜过大部分神经网络方法。