Discovering robustly connected subgraphs with simple descriptions

Janis Kalofolias, Mario Boley, Jilles Vreeken

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

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.

Original languageEnglish
Title of host publicationProceedings - 19th IEEE International Conference on Data Mining, ICDM 2019
EditorsJianyong Wang, Kyuseok Shim, Xindong Wu
Place of PublicationPiscataway NJ USA
PublisherIEEE, Institute of Electrical and Electronics Engineers
Pages1150-1155
Number of pages6
ISBN (Electronic)9781728146034, 9781728146041
ISBN (Print)9781728146058
DOIs
Publication statusPublished - 2019
EventIEEE International Conference on Data Mining 2019 - Beijing, China
Duration: 8 Nov 201911 Nov 2019
Conference number: 19th
http://icdm2019.bigke.org/

Publication series

NameProceedings - IEEE International Conference on Data Mining, ICDM
PublisherIEEE, Institute of Electrical and Electronics Engineers
Volume2019-November
ISSN (Print)1550-4786
ISSN (Electronic)2374-8486

Conference

ConferenceIEEE International Conference on Data Mining 2019
Abbreviated titleICDM 2019
CountryChina
CityBeijing
Period8/11/1911/11/19
Internet address

Keywords

  • Dense subgraph mining
  • K core decomposition
  • Pattern mining
  • Robust connectedness
  • Subgroup discovery

Cite this