ML Anthology

Efficient Frequent Connected Induced Subgraph Mining in Graphs of Bounded Tree-Width

Tamás Horváth, Keisuke Otaki, Jan Ramon
ECML-PKDD 2013 pp. 622-637
doi:10.1007/978-3-642-40988-2_40 /ecmlpkdd/2013/horvath2013ecmlpkdd-efficient/

Abstract

We study the frequent connected induced subgraph mining problem, i.e., the problem of listing all connected graphs that are induced subgraph isomorphic to a given number of transaction graphs. We first show that this problem cannot be solved for arbitrary transaction graphs in output polynomial time (if P ≠ NP) and then prove that for graphs of bounded tree-width, frequent connected induced subgraph mining is possible in incremental polynomial time by levelwise search. Our algorithm is an adaptation of the technique developed for frequent connected subgraph mining in bounded tree-width graphs. While the adaptation is relatively natural for many steps of the original algorithm, we need entirely different combinatorial arguments to show the correctness and efficiency of the new algorithm. Since induced subgraph isomorphism between bounded tree-width graphs is NP-complete, the positive result of this paper provides another example of efficient pattern mining with respect to computationally intractable pattern matching operators.

PDF ECML-PKDD Semantic Scholar

Cite

Text

Horváth et al. "Efficient Frequent Connected Induced Subgraph Mining in Graphs of Bounded Tree-Width." European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases, 2013. doi:10.1007/978-3-642-40988-2_40

Markdown

[Horváth et al. "Efficient Frequent Connected Induced Subgraph Mining in Graphs of Bounded Tree-Width." European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases, 2013.](https://mlanthology.org/ecmlpkdd/2013/horvath2013ecmlpkdd-efficient/) doi:10.1007/978-3-642-40988-2_40

BibTeX

@inproceedings{horvath2013ecmlpkdd-efficient,
  title     = {{Efficient Frequent Connected Induced Subgraph Mining in Graphs of Bounded Tree-Width}},
  author    = {Horváth, Tamás and Otaki, Keisuke and Ramon, Jan},
  booktitle = {European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases},
  year      = {2013},
  pages     = {622-637},
  doi       = {10.1007/978-3-642-40988-2_40},
  url       = {https://mlanthology.org/ecmlpkdd/2013/horvath2013ecmlpkdd-efficient/}
}