Title: Min, max and PTime anti-monotonic overlap graph measures
Authors: Calders, Toon ×
Ramon, Jan
Van Dyck, Dries #
Issue Date: Jul-2008
Host Document: Proceedings of the 6th International Workshop on Mining and Learning with Graphs pages:1-3
Conference: International Workshop on Mining and Learning with Graphs edition:6th location:Helsinki date:4-5 July 2008
Abstract: 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, Gudes and Shimony 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 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 $\theta$-function.
Publication status: published
KU Leuven publication type: IC
Appears in Collections:Informatics Section
× corresponding author
# (joint) last author

Files in This Item:
File Description Status SizeFormat
mlg08.pdfPDF Published 69KbAdobe PDFView/Open


All items in Lirias are protected by copyright, with all rights reserved.