Structure-based similarity search with graph histograms

TLDR

Many modern applications represent objects such as road networks, CAD/CAM components, electronic circuits, and molecules as graphs. The authors aim to rapidly identify database graphs similar to a query graph using an efficient graph manipulation technique. They analyze graph similarity measures, encode graphs as multidimensional vectors, and apply an efficient manipulation technique for similarity search. Vector representation introduces no false dismissals, and experiments show substantial savings in computational effort and I/O operations compared to conventional methods.

Abstract

Objects like road networks, CAD/CAM components, electrical or electronic circuits, molecules, can be represented as graphs, in many modern applications. The authors propose an efficient and effective graph manipulation technique that can be used in graph-based similarity search. Given a query graph G/sub q/ (V,E), they would like to determine fast which are the graphs in the database that are similar to G/sub q/ (V,E), with respect to a similarity measure. First, they study the similarity measure between two graphs. Then, they discuss graph representation techniques by means of multidimensional vectors. It is shown that no false dismissals are introduced by using the vector representation. Finally they illustrate some representative queries that can be handled by their approach, and present experimental results, based on the proposed graph similarity algorithm. The results show that considerable savings are obtained with respect to computational effort and I/O operations, in comparison to conventional searching techniques.