caa a22 4500 445871296 CHVBK 20180317145512.0 cr unu---uuuuu 170323e20111101xx s 000 0 eng 10.1007/s10618-011-0217-y doi (NATIONALLICENCE)springer-10.1007/s10618-011-0217-y All normalized anti-monotonic overlap graph measures are bounded [Elektronische Daten] [Toon Calders, Jan Ramon, Dries Van Dyck] In graph mining, a frequency measure for graphs 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 frequent subgraphs have to be found in one graph. Vanetik etal. (Data Min Knowl Disc 13(2):243-260, 2006) already gave sufficient and necessary conditions for anti-monotonicity of graph measures depending only on the edge-overlaps 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 edge-overlap. 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 anti-monotonic 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. The Author(s), 2011 Graph mining nationallicence Large network setting nationallicence Support measure nationallicence Anti-monotonicity nationallicence Morphism reductions nationallicence Calders Toon Eindhoven University of Technology, Eindhoven, The Netherlands aut Ramon Jan Katholieke Universiteit Leuven, Kortrijk, Belgium aut Van Dyck Dries Hasselt University, Transnational University of Limburg, Diepenbeek, Belgium aut Data Mining and Knowledge Discovery Springer US; http://www.springer-ny.com 23/3(2011-11-01), 503-548 1384-5810 23:3<503 2011 23 10618 https://doi.org/10.1007/s10618-011-0217-y text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s10618-011-0217-y text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Calders Toon Eindhoven University of Technology, Eindhoven, The Netherlands aut NATIONALLICENCE 700 1- Ramon Jan Katholieke Universiteit Leuven, Kortrijk, Belgium aut NATIONALLICENCE 700 1- Van Dyck Dries Hasselt University, Transnational University of Limburg, Diepenbeek, Belgium aut NATIONALLICENCE 773 0- Data Mining and Knowledge Discovery Springer US; http://www.springer-ny.com 23/3(2011-11-01), 503-548 1384-5810 23:3<503 2011 23 10618 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer