Please use this identifier to cite or link to this item: http://hdl.handle.net/1942/9440
Title: Min, Max and PTIME Anti-Monotonic Overlap Graph Measures
Authors: Calders, Toon
Ramon, Jan
VAN DYCK, Dries 
Issue Date: 2008
Source: Proceedings of 6th International Workshop on Mining and Learning with Graphs.
Abstract: 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.
Keywords: graph support measure, overlap graph, anti-monotinicity
Document URI: http://hdl.handle.net/1942/9440
Link to publication: http://www.cis.hut.fi/MLG08/papers/session1/paper20.pdf
Category: C2
Type: Proceedings Paper
Appears in Collections:Research publications

Files in This Item:
File Description SizeFormat 
amogm.mlg08.pdfPublished version69.11 kBAdobe PDFView/Open
Show full item record

Page view(s)

12
checked on May 20, 2022

Download(s)

6
checked on May 20, 2022

Google ScholarTM

Check


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.