EUGENE: Explainable Unsupervised Approximation of Graph Edit Distance
Aditya Bommakanti Harshith Reddy Vonteri Sayan Ranu Panagiotis Karras
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.