Gesellschaft für Informatik e.V.

Lecture Notes in Informatics

Datenbanksysteme für Business, Technologie und Web (BTW) P-180, 135-146 (2011).

Gesellschaft für Informatik, Bonn

Copyright © Gesellschaft für Informatik, Bonn


Feature-based graph similarity with co-occurrence histograms and the Earth mover's distance

Marc Wichterich , Anca Maria Ivanescu and Thomas Seidl (Rwth Aachen)


Graph structures are utilized to represent a wide range of objects including naturally graph-like objects such as molecules and derived graph structures such as connectivity graphs for region-based image retrieval. This paper proposes to extend the applicability of the Earth Mover's Distance [RTG98] (EMD) to graph objects by deriving a similarity model with a representation of structural graph features that is compatible with the feature signatures of the EMD. The aim is to support the search for a graph in a database from which the query graph may have originated through limited structural modification. Such query graphs with missing or additional vertices or edges may be the result of natural processes of decay or mutation or may stem from measuring methods that are inherently error-prone, to name a few examples.

Full Text: PDF

Gesellschaft für Informatik, Bonn
ISBN 978-3-88579-274-1

Last changed 24.02.2014 18:54:52