Anti-Monotonic Overlap-Graph Support Measures

In graph mining, a frequency measure is anti-monotonic if the frequency of a pattern never exceeds the frequency of a subpattern. The efficiency and correctness of most graph pattern miners relies critically on this property. We study the case where the dataset is a single graph. Vanetik, Gudes and Shimony already gave sufficient and necessary conditions for anti-monotonicity of measures depending only on the edge-overlaps between the intances of the pattern in a labeled graph. We extend these results to homomorphisms, isomorphisms and homeomorphisms on both labeled and unlabeled, directed and undirected graphs, for vertex and edge overlap. We show a set of reductions between the different morphisms that preserve overlap.

ISBN:978-0-7695-3502-9

Publication year:2008

Keywords:graph support measure, overlap graph, anti-monotinicity

BOF-keylabel:yes

IOF-keylabel:yes

Accessibility:Open