GEDAN: Learning the Edit Costs for Graph Edit Distance
This addresses the limitation of restrictive cost simplifications in graph dissimilarity metrics for applications such as molecular analysis, though it is an incremental improvement over existing neural network methods.
The paper tackles the problem of unrealistic unit-cost assumptions in Graph Edit Distance (GED) by proposing an end-to-end Graph Neural Network framework that learns fine-grained edit costs, aligning topological and task-specific similarity, which yields interpretable graph matchings and shows strong applicability in domains like molecular analysis.
Graph Edit Distance (GED) is defined as the minimum cost transformation of one graph into another and is a widely adopted metric for measuring the dissimilarity between graphs. The major problem of GED is that its computation is NP-hard, which has in turn led to the development of various approximation methods, including approaches based on neural networks (NN). However, most NN methods assume a unit cost for edit operations -- a restrictive and often unrealistic simplification, since topological and functional distances rarely coincide in real-world data. In this paper, we propose a fully end-to-end Graph Neural Network framework for learning the edit costs for GED, at a fine-grained level, aligning topological and task-specific similarity. Our method combines an unsupervised self-organizing mechanism for GED approximation with a Generalized Additive Model that flexibly learns contextualized edit costs. Experiments demonstrate that our approach overcomes the limitations of non-end-to-end methods, yielding directly interpretable graph matchings, uncovering meaningful structures in complex graphs, and showing strong applicability to domains such as molecular analysis.