Skip navigation
Skip navigation

Graph Edit Distance from Spectral Seriation

Robles-Kelly, Antonio; Hancock, Edwin R

Description

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 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...[Show more]

dc.contributor.authorRobles-Kelly, Antonio
dc.contributor.authorHancock, Edwin R
dc.date.accessioned2015-12-13T22:52:10Z
dc.identifier.issn0162-8828
dc.identifier.urihttp://hdl.handle.net/1885/81444
dc.description.abstractThis 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.
dc.publisherInstitute of Electrical and Electronics Engineers (IEEE Inc)
dc.sourceIEEE Transactions on Pattern Analysis and Machine Intelligence
dc.source.urihttp://ieeexplore.ieee.org/iel5/34/30209/01388263.pdf?isnumber=30209=JNL&arnumber=1388263&arSt=+365&ared=+378&arAuthor=Robles-Kelly%2C+A.%3B+Hancock%2C+E.R.
dc.subjectKeywords: Computer graphics; Eigenvalues and eigenfunctions; Graph theory; Graphic methods; Mathematical models; Matrix algebra; Object recognition; Pattern recognition; Probability; Graph edit distance; Graph matching; Graph seriation; Graph-spectral methods; Maxi Graph edit distance; Graph seriation; Graph-spectral methods; Maximum a posteriori probability (MAP)
dc.titleGraph Edit Distance from Spectral Seriation
dc.typeJournal article
local.description.notesImported from ARIES
local.description.refereedYes
local.identifier.citationvolume27
dc.date.issued2005
local.identifier.absfor080109 - Pattern Recognition and Data Mining
local.identifier.ariespublicationMigratedxPub9735
local.type.statusPublished Version
local.contributor.affiliationRobles-Kelly, Antonio, College of Engineering and Computer Science, ANU
local.contributor.affiliationHancock, Edwin R, University of York
local.description.embargo2037-12-31
local.bibliographicCitation.issue3
local.bibliographicCitation.startpage365
local.bibliographicCitation.lastpage378
dc.date.updated2015-12-11T10:49:29Z
local.identifier.scopusID2-s2.0-15044365894
CollectionsANU Research Publications

Download

File Description SizeFormat Image
01_Robles-Kelly_Graph_Edit_Distance_from_2005.pdf1.59 MBAdobe PDF    Request a copy


Items in Open Research are protected by copyright, with all rights reserved, unless otherwise indicated.

Updated:  19 May 2020/ Responsible Officer:  University Librarian/ Page Contact:  Library Systems & Web Coordinator