EUGENE: Explainable Structure-aware Graph Edit Distance Estimation with Generalized Edit Costs
This addresses the need for accurate and explainable graph distance estimation in domains like biology and social networks, offering a novel approach that overcomes limitations of existing neural methods.
The paper tackles the NP-hard problem of computing Graph Edit Distance (GED) by proposing EUGENE, an optimization-based method that estimates GED and provides explanatory edit paths, achieving state-of-the-art performance with superior scalability across diverse datasets and cost settings.
The need to identify graphs with small structural distances from a query arises in domains such as biology, chemistry, recommender systems, and social network analysis. Among several methods for measuring inter-graph distance, Graph Edit Distance (GED) is preferred for its comprehensibility, though its computation is hindered by NP-hardness. Optimization based heuristic methods often face challenges in providing accurate approximations. State-of-the-art GED approximations predominantly utilize 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 EUGENE, an efficient, algebraic, and structure-aware optimization based method that estimates GED and also provides edit paths corresponding to the estimated cost. Extensive experimental evaluation demonstrates that EUGENE achieves state-of-the-art GED estimation with superior scalability across diverse datasets and generalized cost settings.