All normalized antimonotonic overlap graph measur

Authors: Toon Calders Jan Ramon Dries Van Dyck

Publish Date: 2011/02/27

Volume: 23, Issue: 3, Pages: 503-548

PDF Link

Abstract

In graph mining a frequency measure for graphs is antimonotonic 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 frequent subgraphs have to be found in one graph Vanetik et al Data Min Knowl Disc 132243–260 2006 already gave sufficient and necessary conditions for antimonotonicity of graph measures depending only on the edgeoverlaps between the instances 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 edgeoverlap We show a set of reductions between the different morphisms that preserve overlap As a secondary contribution we prove that the popular maximum independent set measure assigns the minimal possible normalized frequency and we introduce a new measure based on the minimum clique partition that assigns the maximum possible normalized frequency In that way we obtain that all normalized antimonotonic overlap graph measures are bounded from above and below We also introduce a new measure sandwiched between the former two based on the polynomial time computable Lovász θfunction

Keywords: