An Efficiently Computable Support Measure for Frequent Subgraph Pattern Mining
Abstract
Graph support measures are functions measuring how frequently a given subgraph pattern occurs in a given database graph. An important class of support measures relies on overlap graphs. A major advantage of the overlap graph based approaches is that they combine anti-monotonicity with counting occurrences of a pattern which are independent according to certain criteria. However, existing overlap graph based support measures are expensive to compute. In this paper, we propose a new support measure which is based on a new notion of independence. We show that our measure is the solution to a linear program which is usually sparse, and using interior point methods can be computed efficiently. We show experimentally that for large networks, in contrast to earlier overlap graph based proposals, pattern mining based on our support measure is feasible.
Cite
Text
Wang and Ramon. "An Efficiently Computable Support Measure for Frequent Subgraph Pattern Mining." European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases, 2012. doi:10.1007/978-3-642-33460-3_29Markdown
[Wang and Ramon. "An Efficiently Computable Support Measure for Frequent Subgraph Pattern Mining." European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases, 2012.](https://mlanthology.org/ecmlpkdd/2012/wang2012ecmlpkdd-efficiently/) doi:10.1007/978-3-642-33460-3_29BibTeX
@inproceedings{wang2012ecmlpkdd-efficiently,
title = {{An Efficiently Computable Support Measure for Frequent Subgraph Pattern Mining}},
author = {Wang, Yuyi and Ramon, Jan},
booktitle = {European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases},
year = {2012},
pages = {362-377},
doi = {10.1007/978-3-642-33460-3_29},
url = {https://mlanthology.org/ecmlpkdd/2012/wang2012ecmlpkdd-efficiently/}
}