Efficient similarity join for certain graphs

Graphs have been widely applied in many real applications like knowledge mining of social networks, pattern recognition, biological analysis, etc. However, precise matching for large graphs has been proven to be a NP-hard problem. In the context, an efficient similarity join method is proposed to quickly seek similar candidate graph pairs from a large number of graphs in the paper. It is a new method, where local sensitive hash (LSH) and Minhash are used to sharply reduce the time needed to compare candidate graph pairs as well as improve the quality of similarity matching through graph associated vertex degree matrix. Furthermore, the bound filtering strategy is adopted to avoid invalid comparing between graph pairs, which can improve graph similarity join efficiency. To test the advantages of our method, various experiments on synthetic data and real data were conducted. The results of these experiments illustrate that the method in this paper has both good efficiency and effectiveness. In terms of the running time and the precision of the algorithm, the new method yields better results than the other similar methods.