Discovering Robustly Connected Subgraphs with Simple Descriptions 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 posthoc discovering their description leads to suboptimal results. Instead, we propose to optimise over describable subgraphs only. To do so efficiently we propose a nonredundant iterative deepening approach, which we equip with a lineartime tight optimistic estimator that allows pruning large parts of the search space. Extensive empirical evaluation shows that our method can handle large realworld graphs, and discovers easily interpretable and meaningful subgraphs.

Optimizing Subgraph Queries by Combining Binary and WorstCase Optimal Joins. We study the problem of optimizing subgraph queries using the new worstcase optimal join plans. Worstcase optimal plans evaluate queries by matching one query vertex at a time using multiway intersections. The core problem in optimizing worstcase optimal plans is to pick an ordering of the query vertices to match. We design a costbased optimizer that (i) picks efficient query vertex orderings for worstcase optimal plans; and (ii) generates hybrid plans that mix traditional binary joins with worstcase optimal style multiway intersections. Our cost metric combines the cost of binary joins with a new cost metric called intersectioncost. The plan space of our optimizer contains plans that are not in the plan spaces based on tree decompositions from prior work. In addition to our optimizer, we describe an adaptive technique that changes the orderings of the worstcase optimal subplans during query execution. We demonstrate the effectiveness of the plans our optimizer picks and adaptive technique through extensive experiments. Our optimizer is integrated into the Graphflow DBMS.