An Efficient Method for Computing Similarity Between Frequent Subgraphs

摘要

Frequent sub graph mining and graph similarity measures are fundamental and prominent graph analytical techniques. These techniques are often applied together in many graph mining techniques such as clustering and classification. However, these techniques suffer from long running times because frequent sub graph mining and graph similarity measures have been applied independently. In this paper, we propose an efficient method that measures similarity between frequent sub graphs. Our method exploits byproducts of frequent sub graph mining for avoiding costly common sub graph search required in similarity measures. Through experiments on real world graph data, we show that our method measures similarities among all pair of frequent sub graphs within practical time.