Publication Type

Conference Proceeding Article

Version

Preprint

Publication Date

5-2007

Abstract

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 recursively reinforce each other through the entire mining process. A new concept, Pattern-inseparable Data-antimonotonicity, is proposed to handle the structural constraints unique in the context of graph, which, combined with known pruning properties, provides a comprehensive and unified classification framework for structural constraints. The exploration of these antimonotonicities in the context of graph pattern mining is a significant extension to the known classification of constraints, and deepens our understanding of the pruning properties of structural graph constraints.

Keywords

Antimonotonicities, Pruning properties, Constraint theory, Data reduction, Data structures, Pattern recognition

Discipline

Databases and Information Systems | Numerical Analysis and Scientific Computing

Research Areas

Data Management and Analytics

Publication

Advances in knowledge discovery and data mining: 11th Pacific-Asia Conference, PAKDD 2007, Nanjing, China, May 22-25: Proceedings

First Page

388

Last Page

400

ISBN

9783540717003

Identifier

10.1007/978-3-540-71701-0_38

Publisher

Springer Verlag

City or Country

Heidelberg

Copyright Owner and License

Authors

Creative Commons License

Creative Commons Attribution-Noncommercial-No Derivative Works 4.0 License
This work is licensed under a Creative Commons Attribution-Noncommercial-No Derivative Works 4.0 License.

Additional URL

https://doi.org/10.1007/978-3-540-71701-0_38

Share

COinS