Feature-Based Graph Similarity with Co-Occurrence Histograms and the Earth Mover's Distance

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.

 

 

[RTG98] Yossi Rubner, Carlo Tomasi, and Leonidas J. Guibas. A Metric for Distributions with Applications to Image Databases. In Proceedings of the IEEE International Conference
on Computer Vision (ICCV), pages 59–66, 1998.

Authors: Wichterich M., Zimmer (née Ivanescu) A., Seidl T.
Published in: Proc. 14th GI Conference on Database Systems for Business, Technology, and the Web (BTW 2011), Kaiserslautern, Germany
Publisher: GI - Bonn, Germany
Language: EN
Year: 2011
Pages: 135-146
ISBN: 978-3-88579-274-1
ISSN: 1617-5468
Conference: BTW
Url:BTW 2011
Type: Conference papers (peer reviewed)
Research topic: Exploration of Multimedia Databases