G-Hash: Towards Fast Kernel-Based Similarity Search in Large Graph Databases

Introduction

Structured data including sets, sequences, trees and graphs, pose significant challenges to fundamental aspects of data management such as efficient storage, indexing, component search (e.g. subgraph/ supergraph search) and similarity search. Among these structured data, the use of graph representations has gained popularity in pattern recognition and machine learning. The main advantage of graphs is that they offer a powerful way to represent structured data. Querying and mining of the graphs can contribute to our understanding in numerous ways: understanding of new connectivity patterns, evolutionary changes and discovery of topological features. Queries in graph databases can be broadly classified into two categories: (i) subgraph query and (ii) similarity query. The aim of subgraph query is to identify a set of graphs that contain a query graph. The aim of similarity query is to identify similar graphs in a graph database to a query, according to a distance metric. There are two types of similarity query, i.e. k-NNs query and range query. In k-NNs query, the k most similar graphs are reported. In range query, all graphs within a predefined distance to the query graph are reported. In this chapter, we address the problem of k-NNs similarity search in large database of graphs.