Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published February 2022 | Submitted
Journal Article Open

Convex graph invariant relaxations for graph edit distance


The edit distance between two graphs is a widely used measure of similarity that evaluates the smallest number of vertex and edge deletions/insertions required to transform one graph to another. It is NP-hard to compute in general, and a large number of heuristics have been proposed for approximating this quantity. With few exceptions, these methods generally provide upper bounds on the edit distance between two graphs. In this paper, we propose a new family of computationally tractable convex relaxations for obtaining lower bounds on graph edit distance. These relaxations can be tailored to the structural properties of the particular graphs via convex graph invariants. Specific examples that we highlight in this paper include constraints on the graph spectrum as well as (tractable approximations of) the stability number and the maximum-cut values of graphs. We prove under suitable conditions that our relaxations are tight (i.e., exactly compute the graph edit distance) when one of the graphs consists of few eigenvalues. We also validate the utility of our framework on synthetic problems as well as real applications involving molecular structure comparison problems in chemistry.

Additional Information

© 2020 Springer-Verlag GmbH Germany, part of Springer Nature and Mathematical Optimization Society. Received 17 April 2019; Accepted 04 September 2020; Published 16 September 2020. The authors were supported in part by NSF Grants CCF-1350590 and CCF-1637598, by AFOSR Grant FA9550-16-1-0210, and by a Sloan research fellowship.

Attached Files

Submitted - 1904.08934.pdf


Files (2.0 MB)
Name Size Download all
2.0 MB Preview Download

Additional details

August 22, 2023
October 20, 2023