|
Title
|
|
|
|
Anti-monotonic overlap-graph support measures
| |
|
Author
|
|
|
|
| |
|
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 intances 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 theta-function. |
| |
|
Language
|
|
|
|
English
| |
|
Source (journal)
|
|
|
|
Proceedings. - Los Alamitos, Calif, 2001, currens
| |
|
Source (book)
|
|
|
|
8th IEEE International Conference on Data Mining, December 15-19, 2008, Pisa, Italy
| |
|
Publication
|
|
|
|
Los Alamitos, Calif.
:
IEEE Computer Society
,
2008
| |
|
ISBN
|
|
|
|
978-0-7695-3502-9
| |
|
DOI
|
|
|
|
10.1109/ICDM.2008.114
| |
|
Volume/pages
|
|
|
|
(2008)
, p. 73-82
| |
|
ISI
|
|
|
|
000264173600008
| |
|
Full text (Publisher's DOI)
|
|
|
|
| |
|