A binary linear programming formulation of the graph edit distance
- 19 June 2006
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Pattern Analysis and Machine Intelligence
- Vol. 28 (8), 1200-1214
- https://doi.org/10.1109/tpami.2006.152
Abstract
A binary linear programming formulation of the graph edit distance for unweighted, undirected graphs with vertex attributes is derived and applied to a graph recognition problem. A general formulation for editing graphs is used to derive a graph edit distance that is proven to be a metric, provided the cost function for individual edit operations is a metric. Then, a binary linear program is developed for computing this graph edit distance, and polynomial time methods for determining upper and lower bounds on the solution of the binary program are derived by applying solution methods for standard linear programming and the assignment problem. A recognition problem of comparing a sample input graph to a database of known prototype graphs in the context of a chemical information system is presented as an application of the new method. The costs associated with various edit operations are chosen by using a minimum normalized variance criterion applied to pairwise distances between nearest neighbors in the database of prototypes. The new metric is shown to perform quite well in comparison to existing metrics when applied to a database of chemical graphsKeywords
This publication has 38 references indexed in Scilit:
- A (sub)graph isomorphism algorithm for matching large graphsIeee Transactions On Pattern Analysis and Machine Intelligence, 2004
- Recognition of shapes by editing their shock graphsIeee Transactions On Pattern Analysis and Machine Intelligence, 2004
- A fast algorithm for the maximum clique problemDiscrete Applied Mathematics, 2002
- RASCAL: Calculation of Graph Similarity using Maximum Common Edge SubgraphsThe Computer Journal, 2002
- Graph-based method for face identification from a single 2D line drawingIEEE Transactions on Pattern Analysis and Machine Intelligence, 2001
- Symbol recognition by error-tolerant subgraph matching between region adjacency graphsIEEE Transactions on Pattern Analysis and Machine Intelligence, 2001
- Bayesian graph edit distanceIEEE Transactions on Pattern Analysis and Machine Intelligence, 2000
- Error correcting graph matching: on the influence of the underlying cost functionIEEE Transactions on Pattern Analysis and Machine Intelligence, 1999
- A constrained edit distance between unordered labeled treesAlgorithmica, 1996
- A linear programming approach for the weighted graph matching problemIEEE Transactions on Pattern Analysis and Machine Intelligence, 1993