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.
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).
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