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/dataset: | 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 | Size | Format | |
---|---|---|---|---|
amogm.mlg08.pdf | Published version | 69.11 kB | Adobe PDF | View/Open |
Google ScholarTM
Check
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.