Inexact graph matching using genetic search

doi:10.1016/S0031-3203(96)00123-9

Pattern Recognition

Volume 30, Issue 6, June 1997, Pages 953-970

https://doi.org/10.1016/S0031-3203(96)00123-9 Get rights and content

Abstract

This paper describes a framework for performing relational graph matching using genetic search. There are three novel ingredients to the work. Firstly, we cast the optimisation process into a Bayesian framework by exploiting the recently reported global consistency measure of Wilson and Hancock as a fitness measure. The second novel idea is to realise the crossover process at the level of subgraphs, rather than employing string-based or random crossover. Finally, we accelerate convergence by employing a deterministic hill-climbing process prior to selection. Since we adopt the Bayesian consistency measure as a fitness function, the basic measure of relational distance underpinning the technique is Hamming distance. Our standpoint is that genetic search provides a more attractive means of performing stochastic discrete optimisation on the global consistency measure than alternatives such as simulated annealing. Moreover, the action of the optimisation process is easily understood in terms of its action in the Hamming distance domain. We demonstrate empirically not only that the method possesses polynomial convergence time but also that the convergence rate is more rapid than simulated annealing. We provide some experimental evaluation of the method in the matching of aerial stereograms and evaluate its sensitivity on synthetically generated graphs.

References (40)

R.C. Wilson et al.
Graph matching by discrete relaxation
R.C. Wilson et al.
Relational matching by discrete relaxation
Image Vision Comput.
(1995)
J.R. Beveridge et al.
Optimal geometric model matching under full 3D perspective
Comput. Vision Image Understanding
(1995)
L. Eshelman
The CHC adaptive search algorithm: how to have safe search when engaging in non-traditional genetic recombination
Found. Genetic Algorithms
(1991)
S.J. Louis et al.
Syntactic analysis of convergence in genetic algorithms
Found. Genetic Algorithms
(1993)
E.S. Gelsema
Abductive reasoning in Bayesian belief networks using a genetic algorithm
Pattern Recognition Lett.
(1995)
M. Pelillo et al.
An evolutionary approach to training relaxation labelling processes
Pattern Recognition Lett.
(1995)
E.R. Hancock et al.
Discrete relaxation
Pattern Recognition
(1990)
W.E.L. Grimson
The combinatorics of object recognition in cluttered environments using constrained search
Artificial Intell.
(1990)
R.C. Wilson et al.
A Bayesian compatibility model for graph matching
Pattern Recognition Lett.
(1996)

O.D. Faugeras et al.

Improving consistency and resolving ambiguity in relaxation labelling

IEEE PAMI

(1981)

D.B. Fogel

An introduction to simulated evolutionary optimisation

IEEE Trans. Neural Networks

(1994)

S. Geman et al.

Stochastic relaxation, Gibbs distributions and Bayesian restoration of images

IEEE PAMI

(1984)

S. Kirkpatrick et al.

Optimisation by simulated annealing

Science

(1983)

C. Peterson et al.

A new method for mapping optimisation problems

Int. J. Neural Systems

(1989)

X.F. Qi et al.

Theoretical analysis of evolutionary algorithms with an infinite population in continuous space: basic properties of selection and mutation

IEEE Trans. Neural Networks

(1994)

X.F. Qi et al.

Theoretical analysis of evolutionary algorithms with an infinite population in continuous space: analysis of the diversification role of crossover

IEEE Trans. Neural Networks

(1994)

A. Yuille

Generalised deformable models, statistical physics and matching problems

Neural Comput.

(1990)

H.G. Barrow et al.

Relational descriptions in picture processing

Mach. Intell.

(1971)

L.G. Shapiro et al.

A metric for comparing relational descriptions

IEEE PAMI

(1985)

Cited by (119)

Graph matching survey for medical imaging: On the way to deep learning
2022, Methods
The interest on graph matching has not stopped growing since the late seventies. The basic idea of graph matching consists of generating graph representations of different data or structures and compare those representations by searching correspondences between them. There are manifold techniques that have been developed to find those correspondences and the choice of one or another depends on the characteristics of the application of interest. These applications range from pattern recognition (e.g. biometric identification) to signal processing or artificial intelligence. One of the aspects that make graph matching so attractive is its ability to facilitate data analysis, and medical imaging is one of the fields that can benefit from this in a greater extent. The potential of graph matching to find similarities and differences between data acquired at different points in time shows its potential to improve diagnosis, follow-up of human diseases or any other of the clinical scenarios that require comparison between different datasets. In spite of the large amount of papers that were published in this field to the date there is no survey paper of graph matching for clinical applications. This survey aims to fill this gap.
Efficient k-nearest neighbors search in graph space
2020, Pattern Recognition Letters
Citation Excerpt :
In this context, the most well-known paradigm in the literature is the graph edit distance (GED) [20]. Unlike graph matching methods (e.g., [30,31]). In the GED, the graph matching process and the dissimilarity computation are linked through the introduction of a set of graph edit operations.
The k-nearest neighbors classifier has been widely used to classify graphs in pattern recognition. An unknown graph is classified by comparing it to all the graphs in the training set and then assigning it the class to which the majority of the nearest neighbors belong. When the size of the database is large, the search of k-nearest neighbors can be very time consuming. On this basis, researchers proposed optimization techniques to speed up the search for the nearest neighbors. However, to the best of our knowledge, all the existing works compared the unknown graph to each train graph separately and thus none of them considered finding the k nearest graphs from a query as a single problem. In this paper, we define a new problem called multi graph edit distance to which k-nearest neighbor belongs. As a first algorithm to solve this problem, we take advantage of a recent exact branch-and-bound graph edit distance approach in order to speed up the classification stage. We extend this algorithm by considering all the search spaces needed for the dissimilarity computation between the unknown and the training graphs as a single search space. Results showed that this approach drastically outperformed the original approach under limited time constraints. Moreover, the proposed approach outperformed fast graph edit distance algorithms in terms of average execution time especially when the number of graphs is tremendous.
Graph edit distance: Restrictions to be a metric
2019, Pattern Recognition
In the presentation of the graph edit distance in 1983 and other newer bibliography, authors state that it is necessary to apply the distance restrictions (non-negativity, identity of indiscernible elements, symmetry and triangle inequality) to each of the edit functions (insertion, deletion and substitution of nodes and edges) involved in the process of computing the graph edit distance to make the graph edit distance a true distance. Moreover, graph edit distance algorithms presented in the last three decades have been based on mapping the edit path that transforms a graph into the other one into a bijection of the graphs in which some null nodes have been added. In this paper, we show that the triangle inequality does not need to be imposed in each edit function if the graph edit distance is defined through an edit path; however, it is necessary if it is defined as a graph bijection. This is an important finding since the triangle inequality is the only restriction that relates different edit functions and concerns the process of tuning the edit functions given a specific application. Hence, on one hand, it would encourage research to define new algorithms based on the edit path instead of the graph bijection and, on the other hand, use edit functions without the restriction, for instance, that the sum of the costs of insertion and deletion of a pair of nodes has to be larger or equal than the cost of substituting them, which could increase the recognition ratio of a concrete application.
Error-tolerant graph matching using node contraction
2018, Pattern Recognition Letters
Graph matching is the task of computing the similarity between two graphs. It is widely used in graph-based structural pattern recognition. Error-tolerant graph matching is a type of graph matching, in which a similarity between two graphs is computed based on some tolerance value whereas in exact graph matching a strict one-to-one correspondence is required between two graphs. In this paper, we present an approach to error-tolerant graph matching using node contraction where the given graph is transformed into another graph by contracting smaller degree nodes. We use this scheme to extend the notion of graph edit distance, which can be used as a trade-off between execution time and accuracy requirements of various graph matching applications.
Approximating the maximum common subgraph isomorphism problem with a weighted graph
2015, Knowledge-Based Systems
The maximum common subgraph isomorphism problem is a difficult graph problem, and the problem of finding the maximum common subgraph isomorphism problem is NP-hard. This means there is likely no algorithm that will be able to find the maximal isomorphic common subgraph in polynomial time because as the size of the graphs grows the search space for the solution will grow exponentially. This research provides a method that will approximate the maximum common subgraph isomorphism problem by producing a weighted graph, where the weights will give an indication of the probability that the associated link will be in the maximum common subgraph of the two input graphs. The experimental results show that the method can effectively generate a weighted graph containing most of the expected links that would exist in the maximum common subgraph of some given graphs with similar structures.
Computation of graph edit distance: Reasoning about optimality and speed-up
2015, Image and Vision Computing
Citation Excerpt :
Probabilistic relaxation labelling [32,33] adopts a Bayesian perspective on Graph Edit Distance and iteratively applies edit operations to improve a maximum a posteriori criterion. As an alternative to this hill climbing approach, genetic algorithms have been proposed for optimization in [34]. In [35] a randomized construction of initial mappings is followed by a local search procedure.
Bipartite graph matching has been demonstrated to be one of the most efficient algorithms to solve error-tolerant graph matching. This algorithm is based on defining a cost matrix between the whole nodes of both graphs and solving the nodes' correspondence through a linear assignment method (for instance, Hungarian or Jonker–Volgenant methods). Recently, two versions of this algorithm have been published called Fast Bipartite and Square Fast Bipartite. They compute the same distance value than Bipartite but with a reduced runtime if some restrictions on the edit costs are considered. In this paper, we do not present a new algorithm but we compare the three versions of Bipartite algorithm and show how the violation of the theoretically imposed restrictions in Fast Bipartite and Square Fast Bipartite do not affect the algorithm's performance. That is, in practice, we show that these restrictions do not affect the optimality of the algorithm and so, the three algorithms obtain similar distances and recognition ratios in classification applications although the restrictions do not hold. Moreover, we conclude that the Square Fast Bipartite with the Jonker–Volgenant solver is the fastest algorithm.

View all citing articles on Scopus

View full text

Inexact graph matching using genetic search

Abstract

Image Vision Comput.

Comput. Vision Image Understanding

Found. Genetic Algorithms

Found. Genetic Algorithms

Pattern Recognition Lett.

Pattern Recognition Lett.

Pattern Recognition

Artificial Intell.

Pattern Recognition Lett.

Improving consistency and resolving ambiguity in relaxation labelling

IEEE PAMI

An introduction to simulated evolutionary optimisation

IEEE Trans. Neural Networks

Stochastic relaxation, Gibbs distributions and Bayesian restoration of images

IEEE PAMI

Optimisation by simulated annealing

Science

A new method for mapping optimisation problems

Int. J. Neural Systems

Theoretical analysis of evolutionary algorithms with an infinite population in continuous space: basic properties of selection and mutation

IEEE Trans. Neural Networks

Theoretical analysis of evolutionary algorithms with an infinite population in continuous space: analysis of the diversification role of crossover

IEEE Trans. Neural Networks

Generalised deformable models, statistical physics and matching problems

Neural Comput.

Relational descriptions in picture processing

Mach. Intell.

A metric for comparing relational descriptions

IEEE PAMI