Mining frequent correlated graphs with a new measure

• A new measure is proposed to capture more interesting inherent correlations in graph databases.
• Downward closure property of the measure achieves faster mining by pruning several candidates.
• Proposed algorithm efficiently mines correlation by building a hierarchical reduced search space.
• Detailed descriptions with real-life examples are given to explain the usefulness of our approach.
• Extensive performance study shows the efficiency, scalability and effectiveness of the algorithm.

Correlation mining is recognized as one of the most important data mining tasks for its capability to identify underlying dependencies between objects. On the other hand, graph-based data mining techniques are increasingly applied to handle large datasets due to their capability of modeling various non-traditional domains representing real-life complex scenarios such as social/computer networks, map/spatial databases, chemical-informatics domain, bio-informatics, image processing and machine learning. To extract useful knowledge from large amount of spurious patterns, correlation measures are used. Nonetheless, existing graph based correlation mining approaches are unable to capture effective correlations in graph databases. Hence, we have concentrated on graph correlation mining and proposed a new graph correlation measure, gConfidence, to discover more useful graph patterns. Moreover, we have developed an efficient algorithm, CGM (Correlated Graph Mining), to find the correlated graphs in graph databases. The performance of our scheme was extensively analyzed in several real-life and synthetic databases based on runtime and memory consumption, then compared with existing graph correlation mining algorithms, which proved that CGM is scalable with respect to required processing time and memory consumption and outperforms existing approaches by a factor of two in speed of mining correlations.