Fast Similar Subgraph Search with Maximum Common Connected Subgraph Constraints

Similar sub graph search has attracted considerable attention recently with the widespread usage of graph data. Existing methods used graph edit distance or Maximum Common Sub graph (MCS) to quantify graph similarity. However they either are very expensive to compute the results or involve many meaningless disconnected sub graph structures. To address these limitations, in this paper we study the similar sub graph search problem with Maximum Common Connected Sub graph (MCCS) constraints, which not only generates high-quality results but also efficiently identifies the results. To achieve our goal, we propose the concept of edge matching and develop two efficient filters to effectively prune dissimilar graphs. We combine the backtracking algorithm of calculating MCCS with the edge matching and then embed them into our method. Experimental results show that our method performs well on both real and synthetic datasets.