Edges: An expressive and efficient model for learning Graph Edit Distance

In this paper, we introduce Edges , a novel deep architecture that aims at predicting the Graph Edit Distance (GED). Edges reformulates the quadratic assignment problem (QAP) associated to the GED problem as an edge prediction task within a GED instance graph constructed from the input graph pair. It uses a 3-Weisfeiler-Lehman expressive GNN, enabling to embed structural information at the edge level on this GED instance graph . It bypasses the need for costly matching solvers by directly predicting a soft assignment matrix through an end-to-end architecture. Extensive experiments on benchmark datasets demonstrate that the method enhances prediction accuracy through structural awareness while maintaining computational efficiency. • Reframe graph edit distance as edge-level regression on a single instance graph. • Use a 3-WL edge-centric GNN with a quadratic readout built on metric embeddings. • Train end-to-end without combinatorial solvers and enable fast, batched inference. • Achieve state-of-the-art accuracy on AIDS, LINUX, and IMDB with low latency. • Offer a simple, scalable pipeline grounded in quadratic assignment for GED.