Scalable Graph Edit Distance with Deep Reinforcement Learning

In this talk, we will tackle the Graph Edit Distance (GED) problem. Given two labeled graphs, how many edits does one need to get from one graph to the other (e.g. remove edge, add node, relabel nodes…)? This is an NP-hard problem for which exact solvers can’t scale past graphs with ~20 nodes. In recent years, graph machine learning has shown good performances in the supervised learning setting for the GED. GNN models are trained on graph edit distance instances with up to ~20 nodes, for which exact labels can be computed, and then are used at test time to solve larger and larger instances. Unsuprisingly, performances decay with problem size. In parallel, optimal transport approaches were also studied. They formulate GED as a graph matching problem that can be approximated in cubic time and quadratic space and where supervised training labels are not necessary. The OT quadratic space complexity prohibits scaling to 1000s nodes. We propose to use deep reinforcement learning to train policies that can approximate GED in quadratic time and linear space. We show empirically that our approach can compute GED at scale better than all other existing work.