A comparative study of three graph edit distance algorithms

Gao, X; Xiao, B; Tao, D; Li, X

A comparative study of three graph edit distance algorithms

Gao, X Xiao, B Tao, D

Li, X

Permalink

Publication Type:: Chapter
Citation:: 2009, 205 pp. 223 - 242
Issue Date:: 2009-08-06

Closed Access

	Filename	Description	Size
	2011000266OK.pdf		688.57 kB	Adobe PDF	View/Open

Copyright Clearance Process

Recently Added
In Progress
Closed Access

This item is closed access and not available.

Full metadata record

Field	Value	Language
dc.contributor.author	Gao, X	en_US
dc.contributor.author	Xiao, B	en_US
dc.contributor.author	Tao, D https://orcid.org/0000-0001-7225-5449	en_US
dc.contributor.author	Li, X	en_US
dc.date.issued	2009-08-06	en_US
dc.identifier.citation	2009, 205 pp. 223 - 242	en_US
dc.identifier.isbn	9783642015359	en_US
dc.identifier.uri	http://hdl.handle.net/10453/17242
dc.description.abstract	Graph edit distance (GED) is widely applied to similarity measurement of graphs in inexact graph matching. Due to the difficulty of defining cost functions reasonably, we do research on two GED algorithms without cost function definition: the first is combining edge direction histogram (EDH) and earth mover's distance (EMD) to estimate the GED; the second is introducing hidden Markov model (HMM) and Kullback-Leibler distance (KLD) into GED algorithm. These algorithms are evaluated theoretically and experimentally, and are compared with the GED from spectral seriation, one of the leading methods for computing GED with cost functions. Theoretical comparison shows that the proposed two cost function free GED algorithms have less complexity and characterize graph structure more effectively than spectral seriation method. Experimental results on image classification demonstrate that time occupied by the EDH-based method is 4.4% that of the spectral seriation method with the same correct classification rate, and correct classification rate of HMM-based method is 3.4% greater than that of the other two methods with 3.3% the time consumed by spectral seriation method. Clustering rate of these three methods is basically the same, but HMM-based and EDH-based methods only consume 3.17% and 5.43% the time of spectral seriation method. © 2009 Springer-Verlag Berlin Heidelberg.	en_US
dc.relation.isbasedon	10.1007/978-3-642-01536-6_10	en_US
dc.subject.classification	Artificial Intelligence & Image Processing	en_US
dc.title	A comparative study of three graph edit distance algorithms	en_US
dc.type	Chapter
utslib.citation.volume	205	en_US
utslib.for	0801 Artificial Intelligence and Image Processing	en_US
pubs.embargo.period	Not known	en_US
pubs.organisational-group	/University of Technology Sydney
pubs.organisational-group	/University of Technology Sydney/Faculty of Engineering and Information Technology
utslib.copyright.status	closed_access
pubs.publication-status	Published	en_US
pubs.volume	205	en_US

Abstract:

Graph edit distance (GED) is widely applied to similarity measurement of graphs in inexact graph matching. Due to the difficulty of defining cost functions reasonably, we do research on two GED algorithms without cost function definition: the first is combining edge direction histogram (EDH) and earth mover's distance (EMD) to estimate the GED; the second is introducing hidden Markov model (HMM) and Kullback-Leibler distance (KLD) into GED algorithm. These algorithms are evaluated theoretically and experimentally, and are compared with the GED from spectral seriation, one of the leading methods for computing GED with cost functions. Theoretical comparison shows that the proposed two cost function free GED algorithms have less complexity and characterize graph structure more effectively than spectral seriation method. Experimental results on image classification demonstrate that time occupied by the EDH-based method is 4.4% that of the spectral seriation method with the same correct classification rate, and correct classification rate of HMM-based method is 3.4% greater than that of the other two methods with 3.3% the time consumed by spectral seriation method. Clustering rate of these three methods is basically the same, but HMM-based and EDH-based methods only consume 3.17% and 5.43% the time of spectral seriation method. © 2009 Springer-Verlag Berlin Heidelberg.

Please use this identifier to cite or link to this item:

http://hdl.handle.net/10453/17242