(2019) Discovering Robustly Connected Subgraphs with Simple Descriptions.
|
Text
rosi-kalofolias,boley,vreeken-mlg.pdf Download (2MB) | Preview |
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.
| Item Type: | Conference or Workshop Item (A Paper) (Paper) |
|---|---|
| Divisions: | Jilles Vreeken (Exploratory Data Analysis) |
| Conference: | KDD ACM International Conference on Knowledge Discovery and Data Mining |
| Depositing User: | Jilles Vreeken |
| Date Deposited: | 09 Dec 2019 14:29 |
| Last Modified: | 10 May 2021 11:33 |
| Primary Research Area: | NRA1: Trustworthy Information Processing |
| URI: | https://publications.cispa.saarland/id/eprint/3000 |
Actions
Actions (login required)
 |
View Item |