Back to Search
Start Over
Graph edit distance as a quadratic assignment problem
- Source :
- Pattern Recognition Letters, Pattern Recognition Letters, Elsevier, 2017, 87, pp.38-46. ⟨10.1016/j.patrec.2016.10.001⟩
- Publication Year :
- 2017
- Publisher :
- Elsevier BV, 2017.
-
Abstract
- Definition of the equivalence between assignments and edit paths.Graph edit distance formulation as a quadratic assignment problem.New quadratic cost function for computing graph edit distance.Improvement of the accuracy of the approximation of graph edit distance.Approximation computable in reasonable time. The Graph Edit Distance (GED) is a flexible measure of dissimilarity between graphs which arises in error-correcting graph matching. It is defined from an optimal sequence of edit operations (edit path) transforming one graph into another. Unfortunately, the exact computation of this measure is NP-hard. In the last decade, several approaches were proposed to approximate the GED in polynomial time, mainly by solving linear programming problems. Among them, the bipartite GED received much attention. It is deduced from a linear sum assignment of the nodes of the two graphs, which can be efficiently computed by Hungarian-type algorithms. However, edit operations on nodes and edges are not handled simultaneously, which limits the accuracy of the approximation. To overcome this limitation, we propose to extend the linear assignment model to a quadratic one. This is achieved through the definition of a family of edit paths induced by assignments between nodes. We formally show that the GED, restricted to the paths in this family, is equivalent to a quadratic assignment problem. Since this problem is NP-hard, we propose to compute an approximate solution by adapting two algorithms: Integer Projected Fixed Point method and Graduated Non Convexity and Concavity Procedure. Experiments show that the proposed approach is generally able to reach a more accurate approximation of the exact GED than the bipartite GED, with a computational cost that is still affordable for graphs of non trivial sizes.
- Subjects :
- Combinatorial optimization
String-to-string correction problem
Linear programming
Quadratic assignment problem
[INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS]
Relaxation methods
02 engineering and technology
Wagner–Fischer algorithm
01 natural sciences
[INFO.INFO-AI]Computer Science [cs]/Artificial Intelligence [cs.AI]
Combinatorics
Artificial Intelligence
0103 physical sciences
0202 electrical engineering, electronic engineering, information engineering
Structural pattern recognition
010306 general physics
Time complexity
ComputingMilieux_MISCELLANEOUS
Mathematics
Discrete mathematics
Edit paths
[INFO.INFO-CV]Computer Science [cs]/Computer Vision and Pattern Recognition [cs.CV]
Graph edit distance
Software
Signal Processing
1707
Bipartite graph
020201 artificial intelligence & image processing
Edit distance
Computer Vision and Pattern Recognition
Graph operations
Subjects
Details
- ISSN :
- 01678655
- Volume :
- 87
- Database :
- OpenAIRE
- Journal :
- Pattern Recognition Letters
- Accession number :
- edsair.doi.dedup.....5b3201bd19e28bdd166261ed91172c40