On the unification of the graph edit distance and graph matching problems

Romain RaveauxarXiv 2021 · arXiv

Introduction

In structural data analysis, comparing two graphs is a fundamental task. Because real-world data is often noisy, researchers rely on "error-tolerant" matching. Historically, this has been approached through two distinct frameworks: Graph Edit Distance (GED), which minimizes the cost of transforming one graph into another, and Graph Matching (GM), which maximizes a similarity score between correspondences.

Conceptual unification of GED and GM through a single integer quadratic model.

For decades, these communities operated in parallel, leading to fragmented benchmarks and algorithms. This research provides a formal mathematical proof that GED and GM are equivalent under a specific reformulation, allowing solvers from one field to be applied to the other.

Theoretical Unification

The core contribution is a theoretical bridge built by transforming the standard Integer Linear Program (ILP) for GED. The author demonstrates that the "slack" variables traditionally used to represent node/edge deletions and insertions can be algebraically removed.

By incorporating these costs directly into the substitution costs, the paper defines a new similarity function ($s'$). Specifically, the similarity of matching node $u_i$ to node $v_k$ is defined as the negative of the "net cost" (the cost of substitution minus the costs of deleting $u_i$ and inserting $v_k$). This transformation effectively turns a GED minimization problem into a GM maximization problem (specifically, a Quadratic Assignment Problem).

Mapping of edit operations and costs to unified similarity scores.

Key Insights: Implicit vs. Explicit Errors

A major conceptual takeaway is that while GM does not explicitly feature "deletion" or "insertion" operations, these are handled implicitly when the similarity function is tuned correctly. Deleting a node in GED is mathematically identical to leaving it unmatched in a GM model where the similarity of a match is weighed against the cost of non-matching. This suggests that modern machine learning models designed to learn graph similarities are likely already learning implicit edit costs.

Empirical Validation

To verify the theoretical proof, the author conducted experiments using the GREC "MIXED" dataset from the ICPR GED contest. This dataset includes graphs with 5 to 20 nodes, allowing for the calculation of optimal solutions.

The results were definitive: the average difference between GED values calculated by traditional methods and the objective values from the new unified model was exactly zero. This empirical "zero-gap" confirms that the mathematical unification holds true in practice across various graph sizes and complex cost functions.

Conclusion and Future Work

While this unification allows for the interchange of solvers, it does not reduce the underlying computational complexity; both problems remain NP-hard. Future research is needed to determine whether machine learning algorithms perform better when learning insertion/deletion costs separately or as a unified similarity score. Furthermore, extensive benchmarking is required to see which specific GM solvers provide the best performance on traditional GED datasets.

Summary updated

Abstract

Error-tolerant graph matching gathers an important family of problems. These problems aim at finding correspondences between two graphs while integrating an error model. In the Graph Edit Distance (GED) problem, the insertion/deletion of edges/nodes from one graph to another is explicitly expressed by the error model. At the opposite, the problem commonly referred to as "graph matching" does not explicitly express such operations. For decades, these two problems have split the research community in two separated parts. It resulted in the design of different solvers for the two problems. In this paper, we propose a unification of both problems thanks to a single model. We give the proof that the two problems are equivalent under a reformulation of the error models. This unification makes possible the use on both problems of existing solving methods from the two communities.
BibTeX
@misc{raveaux2021unification,
  author = {Romain Raveaux},
  title = {{On the unification of the graph edit distance and graph matching problems}},
  year = {2021},
  eprint = {2104.06186},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2104.06186},
}
Figure