Discovering Robustly Connected Subgraphs with Simple Descriptions

Kalofolias, Janis and Boley, Mario and Vreeken, Jilles
(2019) Discovering Robustly Connected Subgraphs with Simple Descriptions.
In: ACM SIGKDD Workshop on Mining and Learning from Graphs (MLG).
Conference: KDD ACM International Conference on Knowledge Discovery and Data Mining


Download (2MB) | Preview


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.


Actions (login required)

View Item View Item