Discovering Robustly Connected Subgraphs with Simple Descriptions

Kalofolias, Janis and Boley, Mario and Vreeken, Jilles
(2019) Discovering Robustly Connected Subgraphs with Simple Descriptions.
In: IEEE International Conference on Data Mining (ICDM).
Conference: ICDM IEEE International Conference on Data Mining

[img] Text
rosi-kalofolias,boley,vreeken.pdf

Download (439kB)

Abstract

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

Actions (login required)

View Item View Item