Towards Constraint-Based Subgraph Mining

The traditional motivations for constraint-based pattern mining, i.e., user-controlled focus in the mining process and gain in efficiency, are even stronger when dealing with graphs. On the one hand, mining graphs faces larger computational demands than itemsets or sequences, on the other hand, there are many application domains, such as cheminformatics or proteomics, where meaningful constraints naturally arise. Thus it is important to develop a framework for constraint-based graph mining, individuating properties of interesting constraints and developing adequate computational techniques. In this paper we first introduce a large variety of constraints on graphs and we show that they are all either anti-monotone or monotone; we then provide preliminary results on subgraph mining under a conjunction of these kinds of constraints.