Discovering Robustly Connected Subgraphs with Simple Descriptions

Kalofolias, Janis and Boley, Mario and Vreeken, Jilles
(2019) Discovering Robustly Connected Subgraphs with Simple Descriptions.
In: ECMLPKDD Workshop on Graph Embedding and Mining (GEM).
Conference: ECML PKDD European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Database (PKDD and ECML combined from 2008)

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

Download (632kB)

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