Support Measure Admissibility Based on Operations on Instance Graphs

Abstract

The concept of support is central to data mining. While the definition of support in transaction databases is intuitive and simple, that is not the case in graph datasets and databases. Most mining algorithms require the support of a pattern to be no grater than that of its subpatterns, a property called anti-monotonicity or admissibility. This study examines the requirements for admissibility of a support measure. Support measure for mining graphs are usually based on the notion of an instance graph-a graph representing all the instances of the pattern in a database and their intersection properties. Necessary and sufficient conditions for support measure admissibility, based on operations on instance graphs, are developed and proved. The sufficient conditions are used to prove ad admissibility of one support measure-the size of the independent set in the instance graph. Conversely, the necessary conditions are used to quickly show that some other support measures, such as weighted count of instances, are not admissible.