CISPA
Browse

Discovering Robustly Connected Subgraphs with Simple Descriptions

Download (617.79 kB)
conference contribution
posted on 2023-11-29, 18:11 authored by Janis KalofoliasJanis Kalofolias, Mario Boley, Jilles VreekenJilles Vreeken
We study the problem of discovering robustly connected subgraphs that have simple descriptions. Our aim is, hence, to discover vertex sets which not only a) induce a subgraph that is difficult to fragment into disconnected components, but also b) can be selected from the entire graph using just a simple conjunctive query on their vertex attributes. Since many subgraphs do not have such a simple logical description, first mining robust subgraphs and post-hoc discovering their description leads to sub-optimal results. Instead, we propose to optimise over describable subgraphs only. To do so efficiently we propose a non-redundant iterative deepening approach, which we equip with a linear-time tight optimistic estimator that allows pruning large parts of the search space. Extensive empirical evaluation shows that our method can handle large real-world graphs, and discovers easily interpretable and meaningful subgraphs.

History

Preferred Citation

Janis Kalofolias, Mario Boley and Jilles Vreeken. Discovering Robustly Connected Subgraphs with Simple Descriptions. In: European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Database (ECML PKDD). 2019.

Primary Research Area

  • Algorithmic Foundations and Cryptography

Secondary Research Area

  • Empirical and Behavioral Security

Name of Conference

European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Database (ECML PKDD)

Legacy Posted Date

2019-12-09

Open Access Type

  • Unknown

BibTeX

@inproceedings{cispa_all_3001, title = "Discovering Robustly Connected Subgraphs with Simple Descriptions", author = "Kalofolias, Janis and Boley, Mario and Vreeken, Jilles", booktitle="{European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Database (ECML PKDD)}", year="2019", }

Usage metrics

    Categories

    No categories selected

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC