Document Server@UHasselt >
Research >
Research publications >

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
Citation: 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.
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:

Description SizeFormat
Published version69.11 kBAdobe PDF

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