1997 OnARelBetwGraphEditDistAndMaxCommonSub

(Bunke, 1997) ⇒ Horst Bunke. (1997). “On a Relation Between Graph Edit Distance and Maximum Common Subgraph.” In: Pattern Recognition Letters, 18(9).

Subject Headings: Graph Edit Distance Function, Approximate Graph Matching Algorithm, Maximum Common Subgraph Algorithm, Graph Edit Operation, Cost Function.

Notes

Cited By

(Bunke & Shearer, 1998) ⇒ Horst Bunke, and Kim Shearer. (1998). “A Graph Distance Metric Based on the Maximal Common Subgraph.” In: Pattern Recognition Letters, 19(3-4).

Quotes

Abstract

In approximate, or error-correcting, graph matching one considers a set of graph edit operations, and defines the edit distance of two graphs g_1 and g_2 as the shortest (or least cost) sequence of edit operations that transform g_1 into g_2. A maximum common subgraph of two graphs g_1 and g_2 is a subgraph of both g1 and g2 such that there is no other subgraph of g1 and g2 with more nodes. Graph edit distance and maximum common subgraph are well known concepts that have various applications in pattern recognition and machine vision. In this paper a particular cost function for graph edit distance is introduced, and it is shown that under this cost function graph edit distance computation is equivalent to the maximum common subgraph problem.

1. Introduction

Graphs are general and powerful data structures useful for the representation of various objects and concepts. In pattern recognition and machine vision, for example, graphs are often used to represent object models, which are known a priori and stored in a database, and also unknown objects, which are to be recognized. Using graphs as a representation formalism, the recognition problem turns into a graph matching problem. An input graph representing an unknown object is compared to the database in order to find the most similar model graph. Applications where this concept has been successfully applied include Chinese character recognition (Lu et al., 1991), schematic diagram interpretation (Lee et al., 1990), seal verification (Lee and Kim, 1989), shape analysis (Pearce et al., 1994), image recognition (Christmas et al., 1995), and 3-D object recognition (Cho and Kim, 1992; Wong, 1992).

Algorithms for graph matching include graph and subgraph isomorphism (Read and Corneil, 1977; Ullman,

1976). However, due to errors and distortions in the input data, approximate, or error-correcting, graph matching methods are needed in most applications (Shapiro and Haralick, 1981; Bunke and Allerman, 1983; Sanfeliu and Fu, 1983). Another way to cope with distorted input graphs is to use the maximum common subgraph in order to measure graph similarity (Levinson, 1992; Horaud and Skordas, 1989). Subgraph isomorphism, error-correcting graph isomorphism and maximum common subgraph computation are NP-complete problems. Nevertheless, in many applications constraints and heuristics can be found that cut down the computational effort to a manageable size.

In this paper we first formally define error-correcting graph matching and graph edit distance. Then we

introduce a special cost function for error-correcting graph matching and show that under this cost function the graph edit distance problem is equivalent to maximum common subgraph computation. A similar relation is known to hold between the string edit distance and the length of the longest common subsequence of two strings (Wagner and Fischer, 1974). The main contribution of the paper is the formal proof of the equivalence. But there are potential practical consequences of this result in the sense that any known algorithm for graph edit distance becomes applicable for computing maximum common subgraphs, and vice versa.

Definition 8. The edit distance d(gl, g2) of two graphs g l and g2 is the minimum cost taken over all ecgm's

from gl to g2, i.e., d(gl,g2)=min{c(f)l f is an ecgm from gl to g2}.

…

3. Conclusions

In this paper, we have formally defined graph edit distance and introduced a special cost function under which graph edit distance computation is equivalent to the maximum common subgraph problem. That is, any function f that minimizes the cost of mapping the nodes and edges of a graph gl to those of another graph g2 is a graph isomorphism between a subgraph gl of gl and a subgraph g2 of g2, and both gl and g2 are a maximum common subgraph of gl and ge. This result is not only interesting from the theoretical point of view, but it may be of practical relevance, too. An immediate consequence is that any algorithm that computes graph edit distance may be used for maximum common subgraph computation if it is run under the cost function introduced in this paper, and vice versa. Recently, some new algorithms for graph edit distance computation have been proposed (Bunke and Messmer, 1997). These algorithms make use of intensive preprocessing in order to reduce the computation time needed on-line. With the result derived in the present paper, these algorithms become applicable to the maximum common subgraph problem, too. Error-correcting graph matching is a generalization of approximate string matching. A relation between string edit distance and the longest common subsequence of two strings, similar to the relation that has been derived for graphs in this paper, has been known for long (Wagner and Fischer, 1974). Recently, it has been shown that this relation holds true not only for the particular cost function given by Wagner and Fischer (1974), but for a whole class of cost functions (Rice et al., 1997). That is, there are infinitely many cost functions under which string edit distance computation is equivalent to finding the longest common subsequence of two strings. It is an interesting open question whether a similar class of cost functions exists for graph edit distance. …

References

Bunke, H., Allerman, G., (1983). Inexact graph matching for structural pattern recognition. Pattern Recognition Letters 1 (4), 245-253.
Bunke, H., Messmer, B., (1997). Recent advances in graph matching. Internat. J. Pattern Recognition Artif. Intell. 11 (1), 169-203.
Cho, C.J., Kim, J.J., (1992). Recognizing 3-D objects by forward checking constrained tree search. Pattern Recognition Letters 13 (8), 587-597.
Christmas, W.J., Kittler, J., Petrou, M., (1995). Structural matching in computer vision using probabilistic relaxation. IEEE Trans. Pattern Anal. Machine Intell. 17 (8), 749-764.
Horaud, R., Skordas, T., (1989). Stereo correspondence through feature grouping and maximal cliques. IEEE Trans. Pattern Anal. Machine lntell. 11 (11), 1168-1180.
Lee, S., Kim, J.H., (1989). Attributed stroke graph matching for seal imprint verification. Pattern Recognition Letters 9, 137-145.
Lee, S.W., Kim, J.H., Groen, F.C.A., (1990). Translation-, rotation-, and scale invariant recognition of hand-drawn symbols in schematic diagrams. Internat. J. Pattern Recognition Artif. Intell. 4 (1), 1-15.
Levinson, R., (1992). Pattern associativity and the retrieval of semantic networks. Comput. Math. Appl. 23, 573-600.
Lu, S.W., Ren, Y., Suen, C.Y., (1991). Hierarchical attributed graph representation and recognition of handwritten Chinese characters. Pattern Recognition 24, 617-632.
Pearce, A., Caelli, T., Bischof, W.F., (1994). Rulegraphs for graph matching in pattern recognition. Pattern Recognition 27 (9), 1231-1246.
Read, R.C., Corneil, D.G., 1977. The graph isomorphism disease. J. Graph Theory 1,339-363.
Rice, S., Bunke, H., Nartker, T., (1997). Classes of cost functions for string matching. Algorithmica 18 (2), 271-280.
Sanfeliu, A., Fu, K.S., (1983). A distance measure between attributed relational graphs for pattern recognition. IEEE Trans. Systems Man Cybernet. 13, 353-363.
Shapiro, L.G., Haralick, R.M., (1981). Structural descriptions and inexact matching. IEEE Trans. Pattern Anal. Machine Intell. 3, 504-519.
Ullman, J.R., 1976. An algorithm for subgraph isomorphism. J. ACM 23 (1), 31-42.
Wagner, R.A., Fischer, M.J., 1974. The string-to-string correction problem. J. ACM 21 (1), 168-173.
Wong, E.K., (1992). Model matching in robot vision by subgraph isomorphism. Pattern Recognition 25 (3), 287-304.

,

	Author	volume	Date Value	title	type	journal	titleUrl	doi	note	year
1997 OnARelBetwGraphEditDistAndMaxCommonSub	Horst Bunke			On a Relation Between Graph Edit Distance and Maximum Common Subgraph		Pattern Recognition Letters	http://dx.doi.org/10.1016/S0167-8655(97)00060-3	10.1016/S0167-8655(97)00060-3		1997