zbMATH — the first resource for mathematics

Graph matching using spectral seriation and string edit distance. (English) Zbl 1040.68562
Hancock, Edwin (ed.) et al., Graph based representations in pattern recognition. 4th IAPR international workshop, GbRPR 2003, York, UK, June 30 – July 2, 2003. Proceedings. Berlin: Springer (ISBN 3-540-40452-X/pbk). Lect. Notes Comput. Sci. 2726, 154-165 (2003).
Summary: This paper is concerned with computing graph edit distance. One of the criticisms that can be leveled at existing methods for computing graph edit distance is that it lacks the formality and rigour of the computation of string edit distance. Hence, our aim is to convert graphs to string sequences so that string matching techniques can be used. To do this we use graph spectral seriation method to convert the adjacency matrix into a string or sequence order. We show how the serial ordering can be established using the leading eigenvector of the graph adjacency matrix. We pose the problem of graph-matching as maximum a posteriori probability alignment of the seriation sequences for pairs of graphs. This treatment leads to an expression in which for edit cost is the negative logarithm of the a posteriori sequence alignment probability. To compute the string alignment probability we provide models of the edge compatibility error and the probability of individual node correspondences.
For the entire collection see [Zbl 1027.00030].

68T10 Pattern recognition, speech recognition
68R10 Graph theory (including graph drawing) in computer science
68P05 Data structures
Full Text: Link