Fast Top-K Graph Similarity Search Via Representative Matrices

Abstract

Graph similarity search is a crucial problem in many applications, such as cheminformatics, data mining, and pattern recognition. Top-k graph similarity search aims to find the most similar k graphs to a query graph in graph databases. In this paper, we present a fast top-k graph similarity search algorithm with high classification accuracy. We introduce a new graph similarity measure based upon the number of occurrences of subtree patterns in graphs. In order to accelerate search, we also construct hierarchical representative matrices for graph databases, where each row of the matrices represents a graph set. Using representative matrices, we can derive a similarity upper bound of a query graph and the graph set so as to reduce search space. Comprehensive experiments on real data sets demonstrate that our algorithm has a better performance than compared methods on classification accuracy and query time, and it also can scale to large data sets including 15 million chemical structure graphs.

Keywords

• Graph similarity search
• top-k
• representative matrix