An Efficient Probabilistic Approach for Graph Similarity Search
Preprint
Abstract
Graph similarity search is a common and fundamental operation in graph databases. One of the most popular graph similarity measures is the Graph Edit Distance (GED) mainly because of its broad applicability and high interpretability. Despite its prevalence, exact GED computation is proved to be NP-hard, which could result in unsatisfactory computational efficiency on large graphs. However, exactly accurate search results are usually unnecessary for real-world applications especially when the responsiveness is far more important than the accuracy. Thus, in this paper, we propose a novel probabilistic approach to efficiently estimate GED, which is further leveraged for the graph similarity search. Specifically, we first take branches as elementary structures in graphs, and introduce a novel graph similarity measure by comparing branches between graphs, i.e., Graph Branch Distance (GBD), which can be efficiently calculated in polynomial time. Then, we formulate the relationship between GED and GBD by considering branch variations as the result ascribed to graph edit operations, and model this process by probabilistic approaches. By applying our model, the GED between any two graphs can be efficiently estimated by their GBD, and these estimations are finally utilized in the graph similarity search. Extensive experiments show that our approach has better accuracy, efficiency and scalability than other comparable methods in the graph similarity search over real and synthetic data sets.Keywords
All Related Versions
This publication has 13 references indexed in Scilit:
- Graph edit distance as a quadratic assignment problemPattern Recognition Letters, 2017
- Approximate Graph Edit Distance in Quadratic TimeIEEE/ACM Transactions on Computational Biology and Bioinformatics, 2015
- Fast computation of Bipartite graph matchingPattern Recognition Letters, 2014
- Efficient processing of graph similarity queries with edit distance constraintsThe VLDB Journal, 2013
- Efficiently Indexing Large Sparse Graphs for Similarity SearchIEEE Transactions on Knowledge and Data Engineering, 2010
- Approximate graph edit distance computation by means of bipartite graph matchingImage and Vision Computing, 2009
- A survey of graph edit distancePattern Analysis and Applications, 2009
- A binary linear programming formulation of the graph edit distanceIEEE Transactions on Pattern Analysis and Machine Intelligence, 2006
- An eigenspace projection clustering method for inexact graph matchingIEEE Transactions on Pattern Analysis and Machine Intelligence, 2004
- The Hungarian method for the assignment problemNaval Research Logistics Quarterly, 1955