Physical Sciences and Mathematics Commons^™

Gprune: A Constraint Pushing Framework For Graph Pattern Mining, Feida Zhu, Xifeng Yan, Jiawei Han, Philip S. Yu

Research Collection School Of Computing and Information Systems

In graph mining applications, there has been an increasingly strong urge for imposing user-specified constraints on the mining results. However, unlike most traditional itemset constraints, structural constraints, such as density and diameter of a graph, are very hard to be pushed deep into the mining process. In this paper, we give the first comprehensive study on the pruning properties of both traditional and structural constraints aiming to reduce not only the pattern search space but the data search space as well. A new general framework, called gPrune, is proposed to incorporate all the constraints in such a way that they …