File(s) under permanent embargo
Graph edit distance from spectral seriation
journal contribution
posted on 2005-03-01, 00:00 authored by Antonio Robles-KellyAntonio Robles-Kelly, E R HancockThis 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 they lack some of the formality and rigor 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 a 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 a maximum a posteriori probability (MAP) alignment of the seriation sequences for pairs of graphs. This treatment leads to an expression in which the edit cost is the negative logarithm of the a posteriori sequence alignment probability. We compute the edit distance by finding the sequence of string edit operations which minimizes the cost of the path traversing the edit lattice. The edit costs are determined by the components of the leading eigenvectors of the adjacency matrix and by the edge densities of the graphs being matched. We demonstrate the utility of the edit distance on a number of graph clustering problems.
History
Journal
IEEE transactions on pattern analysis and machine intelligenceVolume
27Issue
3Pagination
365 - 378Publisher
Institute of Electrical and Electronics EngineersLocation
Piscataway, N.J.Publisher DOI
ISSN
0162-8828Language
engPublication classification
C1.1 Refereed article in a scholarly journalCopyright notice
2005, IEEEUsage metrics
Categories
Keywords
Graph edit distancegraph seriationmaximum a posteriori probability (MAP)graph-spectral methodsScience & TechnologyTechnologyComputer Science, Artificial IntelligenceEngineering, Electrical & ElectronicComputer ScienceEngineeringOBJECT RECOGNITIONALGORITHMSHAPERELAXATIONInformation SystemsArtificial Intelligence and Image Processing
Licence
Exports
RefWorks
BibTeX
Ref. manager
Endnote
DataCite
NLM
DC