NeuraGED: A GNN estimation for Graph–Edit Distance

Graph generative models often lack a proper reconstruction loss to evaluate the distance between the generated graph and the target graph. This is particularly important for molecular graph generators based on autoencoders, which should reconstruct the input graphs as precisely as possible. Though, the distance estimation can be useful for any graph generator based on reconstruction, including sequential methods relying on Graph Neural Networks. Since graphs are discrete entities by nature, general graph spaces lack a reliable, general, and computationally affordable distance function. Graph Edit Distance is of course an exact, general, and permutation–invariant method for evaluating the difference between two graphs defined in the same graph space. Since it needs all the possible combinations of pairs of nodes from the two graphs, its exact computation is a NP-complete problem and cannot be carried out for graphs larger than ten nodes. As a consequence, a comprehensive soft–estimation method for Graph Edit Distance based on siamese Graph Neural Networks is proposed. A theoretical discussion is carried out, showing that the proposed method can provide a reliable and precise soft–estimation of the Graph Edit Distance on molecular graphs. Molecular graph generators can therefore use this distance estimation as a powerful non–permutation–invariant reconstruction loss. Moreover, the experimental results show that the distance estimation is accurate, with a very low Mean Squared Error loss value.