Anti-monotonic overlap-graph support measures

T.G.K. Calders, J. Ramon, D. Van Dyck

    Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

    13 Citations (Scopus)


    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 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. We also prove that the popular maximum independent set measure assigns the minimal possible meaningful frequency, introduce a new measure based on the minimum clique partition that assigns the maximum possible meaningful frequency and introduce a new measure sandwiched between the former two based on the poly-time computable Lovasz thetas-function.
    Original languageEnglish
    Title of host publicationProceedings 8th IEEE International Conference on Data Mining (ICDM'08, Pisa, Italy, December 15-19, 2008)
    PublisherInstitute of Electrical and Electronics Engineers
    ISBN (Print)978-0-7695-3502-9
    Publication statusPublished - 2008


    Dive into the research topics of 'Anti-monotonic overlap-graph support measures'. Together they form a unique fingerprint.

    Cite this