Redescription Mining: An Overview Esther Galbrun and Pauli Miettinen

Abstract-In many real-world data analysis tasks, we have different types of data over the same objects or entities, perhaps because the data originate from distinct sources or are based on different terminologies. In order to understand such data, an intuitive approach is to identify the correspondences that exist between these different aspects. This is the motivating principle behind redescription mining, a data analysis task that aims at finding distinct common characterizations of the same objects. This paper provides a short overview of redescription mining; what it is and how it is connected to other data analysis methods; the basic principles behind current algorithms for redescription mining; and examples and applications of redescription mining for real-world data analysis problems.

Index Terms-Redescription mining, alternative characterizations, visualizations, data mining.

I. INTRODUCTION

C ONSIDER an ecologist who wants to understand the bioclimatic conditions that define species' habitats. 1 She has data on the regions where the species live and on the bioclimatic conditions (e.g. monthly average temperatures and precipitation) of those regions, and she would like to find explanations such as the following.

The areas inhabited by either the Eurasian lynx or the Canada lynx are approximately the same areas as those where the maximum March temperature ranges from -24.4 • C to 3.4 • C. The above is an example of a redescription. It describes regions of the earth in two different ways; on the one hand, by the fact that certain species inhabit them, and on the other hand, by the fact that they have a certain climate. We can see the areas described above in Figure 1. The medium purple colour denotes the areas where both of the above conditions hold (inhabited by one of the lynx species and with maximum March temperatures in the correct range), light red denotes the areas inhabited by one of the lynx species but where March temperatures are out of the range, and dark blue denotes the areas where the maximum March temperature is in the correct range but neither of the lynxes is found.

Informally, a redescription is a pair of descriptions, both describing roughly the same entities (here, geographical regions). And, as we can see from this example, both the descriptions and what they describe can be of interest. The ecologist is interested in the descriptions in order to understand the model of the niche and in the geographical areas in order to understand E. Galbrun is with Aalto University, Finland. email: esther.galbrun@aalto.fi P. Miettinen is with Max Planck Institute for Informatics, Germany. email: pauli.miettinen@mpi-inf.mpg. de This article is based on our recent tutorials called An Introduction to Redescription Mining at ECMLPKDD '16 and SDM '17, and on our upcoming book Redescription Mining [START_REF] Galbrun | Redescription Mining[END_REF]. 1 In ecology, the task is known as bioclimatic niche (or envelope) finding [START_REF] Soberón | Niches and distributional areas: Concepts, methods, and assumptions[END_REF][START_REF] Grinnell | The niche-relationships of the california thrasher[END_REF]. where the niche is (or is not). While such redescriptions could be constructed manually, the goal of redescription mining is to find them automatically without any information other than the raw data (and some user-provided constraints). For instance, the ecologist should not have to define the species she is interested in. Rather, the goal of redescription mining is to find all redescriptions that characterize sufficiently similar sets of entities and adhere to some simple constraints regarding, for example, their type and complexity and how many entities they cover.

In this article, we present a brief overview of redescription mining. We start by giving the formal definition of the task in the next section. In Section III, we explain the main algorithmic ideas used in redescription mining, before discussing the techniques for removing redundant redescriptions, in Section IV. Sections V, VI, and VII contain, respectively, a brief study of the existing redescription mining tools, an outline of some example applications, and a summary of related methods. We present some open problems and directions to future work in the concluding Section VIII. We will not delve into the details of the different algorithms, tools, or applications. Such details can be found in the original publications, as well as in our recent tutorials 2 and book [START_REF] Galbrun | Redescription Mining[END_REF].

II. FORMALIZING THE TASK

Redescription mining can, of course, be applied to other use cases than bioclimatic niche finding, but we will use that example as our running example throughout this article. In this section we provide the formal definition of redescription mining. Our definition uses the so-called table-based model [START_REF] Galbrun | Redescription Mining[END_REF]; other, more general, formulations exist (see [START_REF] Galbrun | Redescription Mining[END_REF]), but that generality is unnecessary for the discussion in this article.

In the table-based model, the data are arranged as a table (or tables; we will discuss that below). The rows of the table D correspond to the entities in the data and the columns correspond to the attributes; for example, in the bioclimatic niche finding example, the geographical regions are the entities, the table contains one row for each location where observations have been recorded, and the species and bioclimatic variables (that is, the observations) are the attributes. The value of attribute j in entity i is denoted as d ij . The attributes can be of different types, such as binary, categorical, or numerical, and some entity-attribute values might be missing. In our example, the presence or absence of a species in a region constitutes a binary attribute, whereas the bioclimatic variables, such as temperatures or precipitations, are recorded as continuous numerical attributes.

A redescription is a pair of descriptions, and we formalize the descriptions as Boolean queries over the attributes. Each predicate in the queries assigns a truth value to (observed) entity-attribute pairs, that is, to the elements of a column of the data table. The queries over the predicates and their negationstogether known as literals -in turn assign a truth value to each entity. The query can, in principle, be an arbitrary Boolean function of the literals, but it is common to restrict the queries to some query language for the sake of interpretability and efficiency of computation. Common query languages include monotone conjunctive queries, linearly parsable queries (where each variable can appear at most once and both conjunction and disjunction operators have the same precedence), and treeshaped queries (a special case of disjunctive normal forms, encoding the paths from the root to the leaves in a decision tree).

Applying this formalism to our example niche redescription, the query corresponding to 'The areas inhabited by either Eurasian lynx or Canada lynx' could be written as Eurasian lynx ∨ Canada lynx , and the query 'maximum March temperature ranges from -24.4

• C to 3.4 • C' as [-24.4 ≤ t + 3 ≤ 3.4] .
To avoid tautological redescriptions (e.g. 'Eurasian lynx lives where Eurasian lynx lives'), we require that the queries do not share any attributes. In many applications, the attributes have a natural division into two disjoint sets. In our running example, the species form one set of attributes and the bioclimatic variables form the other set. In these cases, it is natural to model the data, not as a one, but as two data tables; one table for the species and one table for the bioclimatic variables, in our example. In this setup, the queries of a redescription are required to be over attributes from different tables.

The support of a query q, supp(q), is the set of entities (rows) that satisfy the query. 3 The support of the query Eurasian lynx ∨ Canada lynx contains the regions depicted in light red and in purple in Figure 1, while the support of the query [-24.4 ≤ t + 3 ≤ 3.4] contains the regions depicted in dark blue and in purple.

To form a good redescription, the queries should explain roughly the same entities, that is, their supports should be similar. The most common choice for measuring the similarity of the supports is the Jaccard (similarity) index J, defined as

J(p, q) = J(supp(p), supp(q)) = |supp(p) ∩ supp(q)| |supp(p) ∪ supp(q)| .
The Jaccard index is by no means the only possible similarity measure, but it is by far the most common one. Its use can be motivated in many ways. For example, when using algorithms based on decision-tree (see Section III), it has a natural connection to the information gain splitting criteria [START_REF] Ramakrishnan | Turning CARTwheels: An alternating algorithm for mining redescriptions[END_REF].

On the other hand, if we consider redescription mining as mining bi-directional association rules (see again Section III), the Jaccard index of a redescription can be interpreted as the lower bound on the confidence of the corresponding association rules conf(p ⇒ q) and conf(q ⇒ p).

How similar should their supports be for the pair (p, q) to be considered a valid redescription is something the user must decide, depending on the data and her needs. Therefore, we say that the supports of p and q are similar enough if J(p, q) ≥ τ for some user-specified constant τ ∈ [0, 1], and write p ∼ q.

We can now define what a redescription is. For data that consist of two tables, D 1 and D 2 , a redescription is a pair of queries (p, q) expressed over attributes from D 1 and D 2 , respectively, such that p ∼ q. In addition, a redescription might have to satisfy other constraints specified by the user, such as limitations on the size of the support, the maximum p-value, or the complexity of the queries (in terms of the number of variables involved, for instance). Then, the goal of redescription mining is to find all valid redescriptions p i ∼ q i that also satisfy the other potential constraints.

III. ALGORITHMS

Readers familiar with classification and association rule mining might have noticed similarities between redescription mining and these two core data mining tasks. These two tasks provide basic techniques that have been adapted to develop algorithms for mining redescriptions.

Consider a case where one query is fixed and the goal is to find a matching query to make a good redescription: this can be seen as a binary classification problem [START_REF] Aggarwal | Chapter 10[END_REF]. This fact has inspired a family of iterative algorithms that alternate between the views to build the redescriptions. These algorithms derive target labels from a query obtained at a previous iteration and use classification techniques, typically decision tree induction, to build a matching query in the next iteration. The first algorithm proposed for redescription mining, the CARTwheels algorithm [START_REF] Ramakrishnan | Turning CARTwheels: An alternating algorithm for mining redescriptions[END_REF], is based on the idea of alternatively growing decision trees over one data table with only binary attributes. The decision-tree-based methods for arbitrary data types introduced by Zinchenko et al. [START_REF] Zinchenko | Mining predictive redescriptions with trees[END_REF] also belong to this family of redescription mining algorithms. Predictive clustering trees were used in a similar manner for mining redescriptions by Mihelčić et al. [START_REF] Mihelčić | Redescription mining with multi-target predictive clustering trees[END_REF].

On the other hand, association rule mining [START_REF] Agrawal | Mining association rules between sets of items in large databases[END_REF] can be seen as a precursor of redescription mining, with the latter allowing for more complex descriptions and focusing on equivalences instead of implications [START_REF] Ramakrishnan | Turning CARTwheels: An alternating algorithm for mining redescriptions[END_REF]. This inspired algorithms that first mine queries separately from the different views before combining the obtained queries across the views into redescriptions. The method proposed by Zaki and Hsiao [START_REF] Zaki | Efficient algorithms for mining closed itemsets and their lattice structure[END_REF] and the MID algorithm of Gallo et al. [START_REF] Gallo | Finding subgroups having several descriptions: Algorithms for redescription mining[END_REF] both belong to this second family of algorithms. Along similar lines, Zaki and Ramakrishnan [START_REF] Zaki | Reasoning about sets using redescription mining[END_REF] studied exact and conditional redescriptions over binary data, focusing on conjunctive queries, while Parida and Ramakrishnan [START_REF] Parida | Redescription mining: Structure theory and algorithms[END_REF] studied the theory of exact redescriptions over binary attributes, where the queries are pure conjunctions, whether in monotone conjunctive normal form or monotone disjunctive normal form.

A third approach for mining redescriptions consists in growing them greedily. Such a strategy of progressively extending the descriptions by appending new literals to either query, always trying to improve the quality of the redescription, was first introduced as the Greedy algorithm of Gallo et al. [START_REF] Gallo | Finding subgroups having several descriptions: Algorithms for redescription mining[END_REF]. Building upon this work, the ReReMi algorithm Galbrun and Miettinen [START_REF] Galbrun | From black and white to full color: Extending redescription mining outside the Boolean world[END_REF] extended the approach to handle categorical and numerical attributes along with binary ones and use a beam search to keep the current top candidates at each step instead of focusing on the single best improvement.

The proposed algorithms can also be divided between exhaustive and heuristic strategies. Mine-and-pair algorithms based on association rule mining techniques are typically exhaustive. Alternating algorithms based on decision tree induction and algorithms that grow the queries greedily typically rely on heuristics.

While the first algorithms only considered binary attributes, more recent ones also allow to handle numerical and categorical attributes, possibly including missing entries. In this latter case, when calculating the supports of the queries and the similarity of the supports, a choice needs to be made about how to handle the entities for which the status of the queries cannot be determined due to missing values. Potential approaches include -but are not limited to -assuming that the queries always evaluate false on such entities [START_REF] Mihelčić | Redescription mining with multi-target predictive clustering trees[END_REF] or assuming that they evaluate true or false depending on what is the most or the least favorable in terms of support similarity [START_REF] Galbrun | From black and white to full color: Extending redescription mining outside the Boolean world[END_REF]. In fact, evaluating whether there is a way the query can evaluate true is NP-hard in general, though this is not the case with any of the query languages that are used with the existing algorithms. Of course, the actual mining algorithm also has to support missing values. For example, in algorithms using decision tree induction, the induction procedure must be able to handle missing values.

IV. SETS OF REDESCRIPTIONS

Redescription mining, as defined above, is an exhaustive enumeration task, the goal being to output all valid redescriptions that satisfy the constraints. This is a common approach in data mining (cf. frequent pattern mining), but it can yield many redundant redescriptions. Filtering away the redundant redescriptions, however, requires us to define what redescriptions are redundant.

Perhaps the simplest approach is to consider the supports of the queries. We can order all (valid) redescriptions descending in their similarity, take the topmost redescription, move it to the list of non-redundant redescriptions, and mark the entities in its support 'used'. We can then re-evaluate the remaining redescriptions while only taking into account the non-used entities. All redescriptions that are deemed invalid (e.g. their support becomes too small or their Jaccard index too low) are considered redundant and removed. We repeat the process with the remaining redescriptions and entities until either the list of redescriptions or the set of entities becomes empty.

This simple approach can filter out too many redescriptions, as it only considers their support and not the attributes that appear in the descriptions. Kalofolias et al. [START_REF] Kalofolias | From sets of good redescriptions to good sets of redescriptions[END_REF] presented another approach for defining redundant redescriptions based on maximum-entropy distributions and the subjective interestingness approach of De Bie [START_REF] Bie | Maximum entropy models and subjective interestingness: an application to tiles in binary databases[END_REF]. They model the data using a maximum-entropy distribution that is constrained so that the already-observed redescriptions have a high probability (or are certain) to occur. The other redescriptions are then ranked based on their likelihood of being true in a data following this model. The redescription that is the least-likely (i.e. the most surprising) is added as a constraint, the model is re-learned, and the remaining redescriptions are re-evaluated.

V. TOOLS

The Siren tool was developed for mining, visualizing, and interacting with redescriptions [START_REF] Galbrun | A case of visual and interactive data analysis: Geospatial redescription mining[END_REF][START_REF]Siren: An interactive tool for mining and visualizing geospatial redescriptions[END_REF][START_REF]Interactive redescription mining[END_REF]. It provides a complete environment for redescription mining, from loading the data to finally exporting the results into various formats, through mining, visualizing, and editing the redescriptions.

Having good visualizations is crucial, of course, when designing a tool for visual data analysis. Indeed, visualization is the key to understanding the results of the mining process and we designed several visualizations for redescriptions. Maps, like the one presented in Figure 1, are a great way to understand where the queries hold (and do not hold), but require, naturally, that the entities are associated with geographical locations. Parallel coordinates plots are especially useful to understand the conditions appearing in the queries, as they allow to visualize the range of values selected by the predicates. Our example redescription depicted in a parallel coordinates plot is shown in Figure 2.

For redescriptions using decision tree induction and for treeshaped queries more generally, tree diagrams reveal the tree structure underlying the queries, facilitating the interpretation of descriptions that can otherwise appear rather convoluted. A tree-shaped equivalent of our example redescription depicted in a tree diagram is shown in Figure 3.

Visualizations in Siren are linked, so that the user can highlight an entity across different visualizations of the same redescription, or interactively adjust the thresholds in the queries through the parallel coordinate plot, for instance. In addition, the tool allows to use different levels of automation when mining redescriptions, from letting the algorithm run fully automatically given a set of parameters, to letting the user edit the results fully manually, through partial automation where Figure 2. Parallel coordinates plot of our example redescription. Every line corresponds to one geographical location (entity) and the colours of the lines are as in Figure 1, except that grey correspond to locations where neither of the queries hold. The plot has three vertical axes corresponding to the three attributes in the redescriptions. The grey boxes in these axes correspond to the range of the values of the corresponding variable in the query; if a line passes through a gray box, the predicate corresponding to the attribute evaluates true for this entity. Figure 3. Tree diagram of a tree-shaped equivalent of our example redescription. Solid leaf nodes correspond to paths in the tree where the queries evaluate true, while empty leaves correspond to paths where the queries evaluate false. Lines between the two trees are as in Figure 2. the algorithm extends and optimizes candidate redescriptions provided by the user.

Siren also allows to perfom support-based filtering on a set of redescriptions as explained in Section IV: the redescriptions are reranked and the redundant ones are marked.

Recently, Mihelčić and Šmuc [START_REF] Mihelčić | InterSet: Interactive redescription set exploration[END_REF] proposed a tool called InterSet for visualizing and working with sets of redescriptions. The tool allows to cluster redescriptions based on their shared attributes and shared entities. The user can also visualize the statistics of a set of redescriptions, such as the distribution of their Jaccard indices or of their pairwise support overlap, and filter the redescriptions based on those statistics.

VI. APPLICATIONS

Redescription mining has been applied in various domains. Here, we present three examples from ecology, from biology and from social and policital sciences, respectively.

Instead of modelling the distributions of species directly, as in the niche finding example presented earlier, one might look at the distributions of functional traits of species. Galbrun et al. [START_REF] Galbrun | Computational biomes: The ecometrics of large mammal teeth[END_REF] consider dental traits of large plant eating mammals and bioclimatic variables (derived from temperature and precipitation records) from around the globe, looking for associations between teeth features and climate. The teeth of plant-eating mammals constitute an interface between the animal and the plant food available in its environment. Hence, teeth are expected to match the types of plant food present in the environment, and dental traits are thus expected to carry a signal of environmental conditions. In this study, three global zones are identified, namely a boreal-temperate moist zone, a tropical moist zone, and a tropical-subtropical dry zone, each associated to particular teeth characteristics and a specific climate.

Mihelčić et al. [START_REF] Mihelčić | Using redescription mining to relate clinical and biological characteristics of cognitively impaired and alzheimer's disease patients[END_REF] use redescription mining to relate clinical and biological characteristics of cognitively impaired patients, with the aim of improving the early diagnosis of Alzheimer's disease. In this study, one data table consists of biological attributes derived from neuroimaging, from blood tests, and from genetic markers, for instance, while the other data table contains clinical attributes that record patients' answers to several questionnaires, observations by physicians, and results of cognition tests. The results obtained largely confirmed the findings of previous studies. In addition, they highlighted some additional biological factors whose relationships with the disease require further investigation, such as the pregnancyassociated plasma protein-A (PAPP-A), which they found to be highly associated with cognitive impairment in Alzheimer's disease.

Galbrun and Miettinen [START_REF] Galbrun | Analysing political opinions using redescription mining[END_REF] applied redescription mining to analysing political opinion polls. Specifically, they used data from Finnish on-line voting advice applications, where candidates in the Finnish parliamentary elections have answered to a number of questions regarding their opinions on political matters, and had also provided socio-economical background data. Galbrun and Miettinen [START_REF] Galbrun | Analysing political opinions using redescription mining[END_REF] analysed, first, the correlations between the socio-economical status and the political opinions of candidates, and, second, compared the answers of candidates who run for both 2011 and 2015 elections between these years. Their findings partially followed the party platforms, but they also found unsuspected connections; for example, candidates who were over 37 years old or who had children were not strongly supporting legalizing euthanasia, and vice versa.

VII. RELATED METHODS

As we have seen, the work on redescription mining has significantly expanded and diversified since the task was first formalized by Ramakrishnan et al. [START_REF] Ramakrishnan | Turning CARTwheels: An alternating algorithm for mining redescriptions[END_REF]. Problem variants have also been introduced: storytelling aims at building a chain of redescriptions linking given objects or queries while relational redescription mining aims to find redescriptions in heterogenous networks.

Beside classification and association rule mining (see Section III), the task also has connections with subgroup discovery, clustering and multi-view approaches, in particular.

In subgroup discovery [START_REF] Wrobel | An algorithm for multi-relational discovery of subgroups[END_REF], the input contains features and a target variable over observations, and the goal is to find queries that describe groups that have an 'interesting' behaviour in the target variable, that is, groups of entities that have different statistical properties (e.g. average) in the target variable when compared to the rest of the observations.

Clustering is a classical unsupervised data analysis method with the goal of grouping the entities in such a way that entities in the same group are as similar to each other as possible, and the objects in different groups are as dissimilar from each other as possible. A query can be interpreted as selecting a subset of the attributes and a group of entities that are in some sense 'similar' to each other, although not in the classical sense (e.g. of having short Euclidean distance). Among clustering techniques, redescription mining is most related to subspace clustering [START_REF] Kröger | Subspace clustering techniques[END_REF] and biclustering [START_REF] Madeira | Biclustering algorithms for biological data analysis: A survey[END_REF].

An important feature of redescriptions is their ability to describe data from different points of view, i.e. their 'multiview' aspect. Other examples of multi-view data mining methods include multi-view clustering [START_REF] Bickel | Multi-view clustering[END_REF], where the attributes are divided into two views and the clustering is done separately over each view; multi-view subgroup discovery [START_REF] Umek | Subgroup discovery in data sets with multi-dimensional responses: A method and a case study in traumatology[END_REF], where the subgroup discovery is done over multiple views; and various multi-view matrix and tensor factorization [START_REF] Miettinen | On finding joint subspace Boolean matrix factorizations[END_REF][START_REF] Gupta | Regularized nonnegative shared subspace learning[END_REF][START_REF] Khan | Bayesian multi-view tensor factorization[END_REF], which use (partially) the same factors to decompose multiple matrices or tensors.

VIII. CONCLUSION AND FUTURE WORK

Redescription mining is a powerful data analysis technique that is gathering wider interest, among data analysis researchers and practitioners alike. The availability of efficient algorithms that can handle heterogeneous data types has undoubtably contributed to the increasing adoption. Yet, redescription mining is, in many ways, in its infancy, and there are still many interesting open questions to be addressed. Developing redescription mining methods that work over time series data is one important future direction. Another interesting direction is to add predicates that are functions of the attributes, such as square roots, logarithms, squares, and so on, and perhaps also multivariate composite attributes. This would naturally allow the query to capture more complex structures, but the exact functions would have to be application-dependant. Finally, redescription mining could also be extended to more complex data (relational redescription mining [START_REF] Galbrun | Finding relational redescriptions[END_REF] can be seen as one step in that direction), such as graphs and multimodal (e.g. tensor) data.

Figure 1 .

 1 Figure 1. Map of a bioclimatic niche. The areas inhabited by either the Eurasian lynx or the Canada lynx (light red and medium purple) and the areas where the maximum March temperature is between -24.4 • C and 3.4 • C (dark blue and medium purple).

Slides available at http://siren.mpi-inf.mpg.de/tutorial/

Some sources call this set the support set and reserve the term support for what we call the size of the support.


Esther Galbrun
email: esther.galbrun@inria.fr

Aristides Gionis
email: aristides.gionis@aalto.fi

Nikolaj Tatti
email: nikolaj.tatti@aalto.fi

Top-k overlapping densest subgraphs

Finding dense subgraphs is an important problem in graph mining and has many practical applications. At the same time, while large real-world networks are known to have many communities that are not well-separated, the majority of the existing work focuses on the problem of finding a single densest subgraph. Hence, it is natural to consider the question of finding the top-k densest subgraphs. One major challenge in addressing this question is how to handle overlaps: eliminating overlaps completely is one option, but this may lead to extracting subgraphs not as dense as it would be possible by allowing a limited amount of overlap. Furthermore, overlaps are desirable as in most realworld graphs there are vertices that belong to more than one community, and thus, to more than one densest subgraph. In this paper we study the problem of finding top-k overlapping densest subgraphs, and we present a new approach that improves over the existing techniques, both in theory and practice. First, we reformulate the problem definition in a way that we are able to obtain an algorithm with constant-factor approximation guarantee. Our approach relies on using techniques for solving the max-sum diversification problem, which however, we need to extend in order to make them applicable to our setting. Second, we evaluate our algorithm on a collection of benchmark datasets and show that it convincingly outperforms the previous methods, both in terms of quality and efficiency.

 [START_REF] Zachary | An information flow model for conflict and fission in small groups[END_REF]. k = 3, β = 2.

Introduction

Finding dense subgraphs is a fundamental graph-mining problem, and has applications in a variety of domains, ranging from finding communities in social networks [START_REF] Kumar | Trawling the Web for emerging cyber-communities[END_REF][START_REF] Sozio | The community-search problem and how to plan a successful cocktail party[END_REF], to detecting regulatory motifs in DNA [START_REF] Fratkin | Mo-tifCut: regulatory motifs finding with maximum density subgraphs[END_REF], to identifying real-time stories in news [START_REF] Angel | Dense subgraph maintenance under streaming edge weight updates for real-time story identification[END_REF].

The problem of finding dense subgraphs has been studied extensively in theoretical computer science [START_REF] Andersen | Finding dense subgraphs with size bounds[END_REF][START_REF] Charikar | Greedy approximation algorithms for finding dense components in a graph[END_REF][START_REF] Feige | The dense k-subgraph problem[END_REF][START_REF] Khuller | On finding dense subgraphs[END_REF], and recently, due to the relevance of the problem in real-world applications, it has attracted considerable attention in the data-mining community [START_REF] Oana | Finding subgraphs with maximum total density and limited overlap[END_REF][START_REF] Tatti | Density-friendly graph decomposition[END_REF][START_REF] Tsourakakis | The k-clique densest subgraph problem[END_REF][START_REF] Tsourakakis | Denser than the densest subgraph: Extracting optimal quasi-cliques with quality guarantees[END_REF][START_REF] Sozio | The community-search problem and how to plan a successful cocktail party[END_REF]. In a domain where most interesting problems are NP-hard, much of the recent work has leveraged the fact that under a specific definition of density, the average-degree density, finding the densest subgraph is a polynomially-time solvable task [START_REF] Andrew | Finding a maximum density subgraph[END_REF]. Furthermore, there is a linear-time greedy algorithm that provides a factor-2 approximation guarantee [START_REF] Charikar | Greedy approximation algorithms for finding dense components in a graph[END_REF].

The exact polynomial algorithm [START_REF] Andrew | Finding a maximum density subgraph[END_REF] and its fast approximation counterpart [START_REF] Charikar | Greedy approximation algorithms for finding dense components in a graph[END_REF], apply only to the problem of finding the single densest subgraph. On the other hand, in most applications of interest we would like to find the top-k densest subgraphs in the input graph. Given an efficient algorithm for finding the single densest subgraph, there is a straightforward way to extend it in order to obtain a set of k dense subgraphs. This is a simple iterative method, in which we first find the densest subgraph, remove all vertices contained in that densest subgraph, and iterate, until k subgraphs are found or only an empty graph is left.

This natural heuristic has two drawbacks: First it produces a solution in which all discovered subgraphs are disjoint. Such disjoint subgraphs are often not desirable, as real-world networks are known to have not well-separated communities and hubs that may belong to more than one community [START_REF] Leskovec | Community structure in large networks: Natural cluster sizes and the absence of large well-defined clusters[END_REF], and hence, may participate in more than one densest subgraph. Second, when searching for the top-k densest subgraphs, we would like to maximize a global objective function, such as the sum of the densities over all k subgraphs and, as shown by Balalau et al. [START_REF] Oana | Finding subgraphs with maximum total density and limited overlap[END_REF], enforcing disjointness may lead to solutions that have very low total density, compared to solutions that allow some limited overlap among the discovered subgraphs.

From the above discussion it follows that it is beneficial to equip a topk densest-subgraph discovery algorithm with the ability to find overlapping subgraphs. This is precisely the problem on which we focus in this paper. The challenge is to control the amount of overlap among the top-k subgraphs; otherwise one can find the densest subgraph and produce k-1 slight variations of it by adding or removing a very small number of vertices -so that the k -1 almost-copies are also very dense.

A simple example that demonstrates the concept of finding the top-k densest subgraphs with overlap is shown in Figure 1. The example is the famous Zachary karate club dataset [START_REF] Zachary | An information flow model for conflict and fission in small groups[END_REF], and the result is an actual execution of our algorithm, with k = 3. The importance of allowing overlap between dense subgraphs is immediate: subgraphs 1 and 2 overlap on vertices 33 and 34. Had those vertices been assigned only to subgraph 1, which was discovered first, subgraph 2 would fall apart.

Our paper follows up on the recent work of Balalau et al. [START_REF] Oana | Finding subgraphs with maximum total density and limited overlap[END_REF]: finding topk densest subgraphs with overlap. The main difference of the two papers is that here we use a distance function to measure overlap of subgraphs and penalize for overlap as part of our objective, while Balalau et al. are enforcing a hard constraint. Our approach allows to obtain a major improvement over the results of Balalau et al., both in theory and in practice. On the theoretical side, we provide an algorithm with worst-case approximation guarantee, while the method of Balalau et al. offers guarantees only for certain input cases. On the empirical side, our method outperforms the previous one in practically all datasets we experimented, with respect to all measures. In addition, in terms of computation time, our method is more scalable.

From the technical point of view, our approach is inspired by the results of Borodin et al. [START_REF] Borodin | Max-sum diversification, monotone submodular functions and dynamic updates[END_REF] for the max-sum diversification problem. In particular, Borodin et al. designed a greedy algorithm in order to find, in a ground set U , a set of elements S that maximizes a function of the form f (S) + λ {x,y}:x,y∈S d (x, y), subject to |S| = k. Here f is a submodular function and d is a distance function. To apply this framework, we set S to be the set of k subgraphs we are searching for, f to capture the total density of all these subgraphs, and d to capture the distance between them -the larger the overlap the smaller the distance.

Yet, the greedy algorithm of Borodin et al. cannot be applied directly; there are a number of challenges that need to be addressed. The most important is that, for our problem, the iterative step of the greedy algorithm results in an NP-hard problem. This is a major difficulty, as the basic scheme of the algorithm of Borodin et al. assumes that the next best item in the greedy iteration can be obtained easily and exactly. To overcome this difficulty, we design an approximation algorithm for that subproblem. Then, we show that an approximation algorithm for the greedy step yields an approximation guarantee for the overall top-k densest-subgraph problem.

We apply our algorithm on a large collection of real-world networks. Our results show that our approach exhibits an excellent trade-off between density and overlap and outperforms the previous method. We also note that density and overlap are not comparable measures, and balancing the two is achieved via the parameter λ. As demonstrated in our experiments, executing the algorithm for a sequence of values of λ creates a density vs. overlap "profile" plot, which reveals the trade-off between the two measures, and allows the user to select meaningful values for the parameter λ.

The contributions of our work can be summarized as follows:

-We consider the problem of finding top-k overlapping densest subgraphs on a given graph. Our problem formulation relies on a new objective that provides a soft constraint to control the overlap between subgraphs. -For the proposed objective function we present a greedy algorithm. This is the first algorithm with an approximation guarantee for the problem of finding top-k overlapping densest subgraphs. -We evaluate the proposed algorithm against state-of-the art methods on a wide range of real-world datasets. Our study shows that our algorithm, in addition to being theoretically superior, it also outpeforms its main competitors in practice, in both quality of results and efficiency.

The rest of the paper is organized as follows. We start by reviewing the related work in Section 2. In Section 3 we define our problem, and in Section 4 we present an overview of background techniques that our approach relies upon. Our method is presented in Section 5, while the experimental evaluation of our algorithm and the comparison with state-of-the-art methods is provided in Section 6. Finally, Section 7 is a short conclusion. For convenience of presentation the proofs of the main claims are given in the Appendix.

Related work

Dense-subgraph discovery. As already discussed, the problem of finding dense subgraphs, and its variations, have been extensively studied in the theoretical computer science and graph mining communities. The complexity of the problem depends on the exact formulation. The quintessential dense graph is the clique, but finding large cliques is a very hard problem [START_REF] Håstad | Clique is hard to approximate within n 1[END_REF]. On the other hand, if density is defined as the average degree of the subgraph, the problem becomes polynomial. This was observed early on by Goldberg, who gave an algorithm based on a transformation to the minimum-cut problem [START_REF] Andrew | Finding a maximum density subgraph[END_REF]. For the same problem, Asahiro et al. [START_REF] Asahiro | Greedily finding a dense subgraph[END_REF] and Charikar [START_REF] Charikar | Greedy approximation algorithms for finding dense components in a graph[END_REF] provided a greedy lineartime factor-2 approximation algorithm, making the problem tractable for very large datasets.

The previous algorithms do not put any constraint on the size of the densest subgraph. Requiring the subgraph to be of a certain size makes the problem NP-hard. Feige et al. show that, for a fixed k, the problem of asking for the dense subgraph of size exactly k can be approximated within a factor of

O(|V |

α ), for α < 1 3 [START_REF] Feige | The dense k-subgraph problem[END_REF]. The problems of asking for a densest subgraph of size at most k or at least k are also NP-hard, and the latter problem can be approximated within a constant factor [START_REF] Andersen | Finding dense subgraphs with size bounds[END_REF][START_REF] Khuller | On finding dense subgraphs[END_REF].

Other notions of density have been considered. Tsourakakis et al. provide algorithms for the problem of finding α-quasicliques and evidence that such subgraphs are, in practice, "more dense than the densest subgraph" [START_REF] Tsourakakis | Denser than the densest subgraph: Extracting optimal quasi-cliques with quality guarantees[END_REF]. Recently, Tsourakakis showed that finding triangle-dense subgraphs is also a polynomial problem, and gave a faster approximation algorithm [START_REF] Tsourakakis | The k-clique densest subgraph problem[END_REF] similar to Charikar's approach [START_REF] Charikar | Greedy approximation algorithms for finding dense components in a graph[END_REF].

All of the above papers focus on the problem of finding a single densest subgraph. Seeking to find the top-k densest subgraphs is a much less studied problem. Tsourakakis et al. [START_REF] Tsourakakis | Denser than the densest subgraph: Extracting optimal quasi-cliques with quality guarantees[END_REF] address the question, but they only considered the naïve algorithm outlined in the introduction-remove and repeat. Balalau et al. [START_REF] Oana | Finding subgraphs with maximum total density and limited overlap[END_REF] are the first to study the problem formally, and demonstrate that the naïve remove-and-repeat algorithm performs poorly. Their problem formulation is different than ours, as they impose a hard constraint on overlap. Their algorithm is also greedy, like ours, but there is no theoretical guarantee. On the other hand, our formulation allows to prove an approximation guarantee for the problem of top-k overlapping densest subgraphs. Furthermore, our experimental evaluation shows that our algorithm finds denser subgraphs for the same amount of overlap.

Finally, extracting top-k communities that can be described by conjunctions of labels was suggested by Galbrun et al. [START_REF] Galbrun | Overlapping community detection in labeled graphs[END_REF]. In this setup, the communities can overlap but an edge can be assigned to only one community. In addition, a community should be described with a label set. However, the algorithm can be easily modified such that it operates without labels and we use this modified algorithm as one of our baselines.

Community detection. Community detection is one of the most well-studied problems in data mining. The majority of the works deal with the problem of partitioning a graph into disjoint communities. A number of different methodologies have been applied, such as hierarchical approaches [START_REF] Girvan | Community structure in social and biological networks[END_REF], methods based on modularity maximization [START_REF] Vincent D Blondel | Fast unfolding of communities in large networks[END_REF][START_REF] Clauset | Finding community structure in very large networks[END_REF][START_REF] Girvan | Community structure in social and biological networks[END_REF][START_REF] White | A spectral clustering approach to finding communities in graph[END_REF], graph theory [START_REF] William Flake | Efficient identification of web communities[END_REF], random walks [START_REF] Pons | Computing communities in large networks using random walks[END_REF][START_REF] Stijn Van Dongen | Graph Clustering by Flow Simulation[END_REF][START_REF] Zhou | Network Brownian motion: A new method to measure vertex-vertex proximity and to identify communities and subcommunities[END_REF], label propagation [START_REF] Stijn Van Dongen | Graph Clustering by Flow Simulation[END_REF], and spectral graph partitioning [START_REF] Karypis | Multilevel algorithms for multi-constraint graph partitioning[END_REF][START_REF] Ng | On spectral clustering: Analysis and an algorithm[END_REF][START_REF] Von | A tutorial on spectral clustering[END_REF]. A popular suite of graph-partitioning algorithms, which is accompanied by highquality software, includes the Metis algorithm [START_REF] Karypis | Multilevel algorithms for multi-constraint graph partitioning[END_REF]. The Metis algorithm is one of the baselines against which we benchmark our approach in our experimental evaluation.

A considerable amount of work has also been devoted into the problem of finding overlapping communities. Different methods have been proposed to address this problem, relying on clique percolation [START_REF] Palla | Uncovering the overlapping community structure of complex networks in nature and society[END_REF], extensions to the modularity-based approaches [START_REF] Chen | Extension of modularity density for overlapping community structure[END_REF][START_REF] Gregory | An algorithm to find overlapping community structure in networks[END_REF][START_REF] Pinney | Betweenness-based decomposition methods for social and biological networks[END_REF], label propagation [START_REF] Gregory | Finding overlapping communities in networks by label propagation[END_REF][START_REF] Xie | SLPA: Uncovering overlapping communities in social networks via a speaker-listener interaction dynamic process[END_REF], analysis of ego-networks [START_REF] Coscia | DEMON: a localfirst discovery method for overlapping communities[END_REF], game theory [START_REF] Chen | A game-theoretic framework to identify overlapping communities in social networks[END_REF], non-negative matrix factorization [START_REF] Yang | Overlapping community detection at scale: a nonnegative matrix factorization approach[END_REF] or edge clustering [START_REF] Ahn | Link communities reveal multiscale complexity in networks[END_REF]. A comprehensive survey on the topic of overlapping community detection has been compiled by Xie et al. [START_REF] Xie | Overlapping community detection in networks: The state-of-the-art and comparative study[END_REF]. Our problem formulation is different than most existing work in community detection, as we focus solely in subgraph density, while typically communitydetection approaches consider a combination of high density inside the communities and small cuts across communities. In fact, there has been experimental evidence that most real-world networks do not exhibit such structure of dense and relatively isolated communities [START_REF] Leskovec | Community structure in large networks: Natural cluster sizes and the absence of large well-defined clusters[END_REF]. To contrast our approach with methods for overlapping community detection, we experimentally compare our algorithm with the state-of-the-art method of Ahn et al. (Links) [START_REF] Ahn | Link communities reveal multiscale complexity in networks[END_REF].

Preliminaries and problem definition

Throughout the paper we consider a graph G = (V, E), where V is a set of vertices and E is a set of undirected edges. Given a subset of vertices W ⊆ V , we write

E(W ) = {(u, v) ∈ E | u, v ∈ W } ,
for the edges of G that have both end-points in W , and

G(W ) = (W, E(W ))
for the subgraph induced by W .

As we are interested in finding dense subgraphs of G, we need to adopt a notion of density. Note that dens(G) is half of the average degree of G. If the graph G = (V, E) is known from the context and we are given a subset of vertices W ⊆ V , we define the density of W by dens(W ) = dens(G(W )), that is, the density of the induced subgraph G(W ). Additionally, we refer to the set X ⊆ V that maximizes dens(X) as the densest subgraph of G.

Next we define the density of a collection of subsets of vertices.

Definition 2 Given a graph G = (V, E) and a collection of subsets of vertices W = {W 1 , . . . , W k }, W i ⊆ V , we define the density of the collection W to be the sum of densities of the individual subsets, that is,

dens(W) = k i=1 dens(W i ) . (1)
Example 1 Consider the graph given in Figure 2 with three subgraphs W = {W 1 , W Our goal is to find a set of subgraphs W with high density dens(W). At the same time we want to allow overlaps among the subgraphs of W. Allowing overlaps without any restriction is problematic though, as the obvious solution is to find the densest subgraph of G and repeat it k times. Therefore we need a way to control the amount of overlap among the subgraphs of W. To control overlaps we use a distance function defined over subsets of vertices. Let d : 2 V × 2 V → R + denote such a distance function. We are then asking to find a set of subgraphs W so that the overall density dens(W) is high, and the subgraphs in W are far apart, according to the distance function d .

More precisely, the problem definition that we work with in this paper is the following.

Problem 1 (Dense-Overlapping-Subgraphs) Given a graph G = (V, E), a distance function d over subsets of vertices, a parameter λ, and an integer k, find k subgraphs

W = {W 1 , . . . , W k }, W i ⊆ V , which maximize a combined reward function r (W) = dens(W) + λ k i=1 k j=i+1 d (W i , W j ) .
A few remarks on our problem definition. First note that the parameter λ is necessary as the two terms that compose the reward function, density and distance, are quantitatively and qualitatively different. Even if one normalizes them to take values in the same range, say, between 0 and 1, they would still not be directly comparable. In fact, the parameter λ provides a weight between density and distance. A small value of λ places the emphasis on density and gives solutions with high overlap, but as λ increases the subgraphs of the optimal solution need to be more distant, at the expense of the density term. In our experimental evaluation we illustrate the effect of the parameter λ by drawing a "profile" of the solution space. By displaying the evolution of the two terms of the reward function as λ varies, such plots also allow to select meaningful values for this parameter.

Second, observe that we are not asking to assign every vertex of V in a subgraph of W. The fraction of vertices assigned to at least one subgraph is controlled by both parameters λ and k. The higher the value of λ, the less overlap between the subgraphs, and thus, the higher the coverage. Similarly, the higher the value of k, the more subgraphs are returned, and thus, coverage increases.

Finally, we restrict the family of functions used to define the distance between subgraphs. As is common, we work with metric and relaxed-metric functions.

Definition 3 Assume a function d mapping pairs of objects to a non-negative real number. If there is a constant c ≥ 1 such that (i) d (x, y) = d (y, x), (ii) d (x, x) = 0, and (iii)

d (x, y) ≤ c(d (x, z) + d (z, y)),
we say that the function d is a c-relaxed metric. If (iii) holds for c = 1, the function d is a metric.

The distance function we use to measure distance between subgraphs in this paper is a metric. However, our approach applies more generally to any c-relaxed metric. We formulate our results in their generality, so that the dependency on the parameter c of a c-relaxed metric becomes explicit.

Overview of background methods

In this section we provide a brief overview of some of the fundamental concepts and algorithmic techniques that our approach relies upon.

The densest-subgraph problem. We first discuss the problem of finding the densest subgraph, according to the average-degree density function, given in Definition 1. This problem of finding the densest-subgraph can be solved in polynomial time. An elegant solution that involves a mapping to a series of minimum-cut problems was given by Goldberg [START_REF] Andrew | Finding a maximum density subgraph[END_REF]. However, since the fastest algorithm to solve the minimum-cut problem runs in O(|V ||E|) time, this approach is not scalable to very large graphs. On the other hand, there exists a linear-time algorithm that provides a factor-2 approximation to the densest-subgraph problem [START_REF] Asahiro | Greedily finding a dense subgraph[END_REF][START_REF] Charikar | Greedy approximation algorithms for finding dense components in a graph[END_REF]. This is a greedy algorithm, which starts with the input graph, and iteratively removes the vertex with the lowest degree, until left with an empty graph. Among all subgraphs considered during this vertex-removal process, the algorithm returns the densest. Hereinafter, we refer to this greedy algorithm as the Charikar algorithm.

Max-sum diversification. Our approach is inspired by the results of Borodin et al. [START_REF] Borodin | Max-sum diversification, monotone submodular functions and dynamic updates[END_REF] for the max-sum diversification problem, which, in their general form, extend the classic Nemhauser et al. approximation results [START_REF] Nemhauser | An analysis of approximations for maximizing submodular set functions-I[END_REF] for the problem of submodular function maximization. A brief description of the problem setting and the methods of Borodin et al. follows.

Let U be a ground set, let d : U × U → R + be a metric distance function over pairs of U , and f : 2 U → R + be a monotone submodular function over subsets of U . Recall that a set function [START_REF] Schrijver | Combinatorial optimization[END_REF]. Also the function f is monotonically increasing if for all S ⊆ T ⊆ U f (T ) ≥ f (S) holds. For the rest of the paper, we write monotone to mean monotonically increasing.

f : 2 U → R is submodular if for all S ⊆ T ⊆ U and u ∈ T we have f (T ∪ {u})-f (T ) ≤ f (S ∪ {u})-f (S)
The max-sum diversification problem is defined as follows.

Problem 2 (Max-Sum-Diversification) Let U be a set of items, f : 2 U → R + a monotone submodular function on subsets of U , and d : U × U → R + a distance function on pairs of U . Let k be an integer and λ ≥ 0. The goal is to find a subset S ⊆ U that maximizes

f (S) + λ {x,y}:x,y∈S d (x, y) , subject to |S| = k.
Here, λ is a parameter that specifies the desired trade-off between the two objectives f (•) and d (•, •). Borodin et al. [START_REF] Borodin | Max-sum diversification, monotone submodular functions and dynamic updates[END_REF] showed that under the conditions specified above, there is a simple linear-time factor-2 approximation greedy algorithm for the max-sum diversification problem. The greedy algorithm works as follows. For any subset S ⊆ U and any element x ∈ S the marginal gain is defined as

φ(x; S) = 1 2 (f (S ∪ {x}) -f (S)) + λ y∈S d (x, y) . (2)
The greedy starts with the empty set S = ∅ and proceeds iteratively. In each iteration it adds to S the element x which is currently not in S and maximizes the marginal gain φ(x; S). Note that due to the 1/2-factor in the first term, φ(x; S) is not equal to the actual gain of the score upon adding x to S. The algorithm stops after k iterations, when the size of S reaches k. As already mentioned, this simple greedy algorithm provides a factor-2 approximation to the optimal solution of the max-sum diversification problem.

The proposed method

As suggested in the previous section, our method for solving Problem 1 and finding dense overlapping subgraphs relies on the techniques developed for the max-sum diversification problem. First note that, in the Dense-Overlapping-Subgraphs problem, the role of function f is taken by the density function dens. The density of a collection of subgraphs is a simple summation (Definition 2) therefore it is clearly monotone and submodular. The other components needed for applying the method of Borodin et al. [START_REF] Borodin | Max-sum diversification, monotone submodular functions and dynamic updates[END_REF] in our setting are not as simple. A number of challenges need to be addressed:

(1) While in the max-sum diversification problem we are searching for a set of elements in a ground set U , in the Dense-Overlapping-Subgraphs problem we are searching for a collection of subsets of vertices V . Thus, U = P(V ) (the powerset of V ) and the solution space is P(V ) k .

(2) Adapting the max-sum diversification framework discussed in the previous section requires selecting the item in U that maximizes the marginal gain φ in each iteration of the greedy algorithm. Since U is now the powerset of V , the marginal gain computation becomes φ(W, W), where W is a subset of vertices, and W is the set of subgraphs previously selected by the greedy algorithm. Finding the subgraph W that maximizes the marginal gain now becomes a difficult computational problem. Thus, we need to extend the framework to deal with the possibility that we are only able to find a subgraph that maximizes the marginal gain approximately.

(3) We need to specify the distance function d (•, •) that will be used to measure overlap between subsets of vertices. There are many natural choices, but not all are applicable to the general max-sum diversification framework.

Challenges ( 2) and ( 3) are intimately connected. The problem of finding the set of vertices that maximizes the marginal gain φ in each iteration of the greedy algorithm crucially depends on the distance function d chosen for measuring distance between subgraphs. Part of our contribution is to show how to incorporate a distance function, which, on the one hand, is natural and intuitive, and, on the other hand, makes the marginal gain-maximization problem tractable. We present our solution in Section 5.2.

But before, we discuss how to extend the greedy algorithm in order to deal with approximations of the marginal gain-maximization problem and with crelaxed metrics.

Extending the greedy algorithm

Consider the Max-Sum-Diversification problem, defined in Problem 2. To simplify notation, if X and Y are subsets of U we define

d (X, Y ) = x∈X y∈Y d (x, y) and d (X) = 1 2
x,y∈X d (x, y) , so, the objective function in Problem 2 can be written as

r (S) = f (S) + λd (S) .
The algorithm of Borodin et al. [START_REF] Borodin | Max-sum diversification, monotone submodular functions and dynamic updates[END_REF], discussed in the previous section, is referred to as Greedy. As already mentioned, Greedy proceeds iteratively: in each iteration it needs to find the item x * of U that maximizes the marginal gain with respect to the solution set S found so far. The marginal gain is computed according to Equation (2). The problem is formalized below.

Problem 3 (Gain) Given a ground set U , a monotone, non-negative, and submodular function f , a c-relaxed metric d , and a set S ⊆ U , find x ∈ U \ S maximizing

φ(x; S) = 1 2 (f (S ∪ {x}) -f (S)) + λd ({x} , S) .
Now consider the case where the Gain problem cannot be solved optimally, but instead an approximation algorithm is available. In particular, assume that we have access to an oracle that solves Gain with an approximation guarantee of α. In this case, the Greedy algorithm still provides an approximation guarantee for the Max-Sum-Diversification problem. The quality of approximation of Greedy depends on α as well as the c parameter of the c-relaxed metric d . We prove the following proposition in Appendix.

Proposition 1 Given a non-negative, monotone and submodular function f , a c-relaxed metric d , and an oracle solving Gain with an approximation guarantee of α, the Greedy algorithm yields an approximation guarantee of α/(2c).

Greedy discovery of dense subgraphs

We now present the final ingredients of our algorithm: (i) defining a metric between subsets of vertices; and (ii) formulating the problem of maximizing marginal gain, establishing its complexity, and giving an efficient algorithm for solving it. We first define the distance measure between subgraphs. Definition 4 Assume a set of vertices V . We define the distance between two subsets X, Y ⊆ V as

D(X, Y ) = 2 -|X∩Y | 2 |X||Y | if X = Y, 0 otherwise.
The distance function D resembles very closely the cosine distance (1 -cosine similarity), but unlike the cosine distance, the distance function D is a metric.

Proposition 2

The distance function D is a metric.

Proof Clearly, D is symmetric and D(X, X) = 0. To prove the triangle inequality consider X, Y, Z ⊆ V . It is easy to see that the triangle inequality holds if at least two of the three sets are identical. So, assume that X, Y , and Z are all distinct. Note that 0 ≤ 1

-|X∩Y | 2 |X||Y | ≤ 1. This gives D(X, Y ) ≤ 2 ≤ D(X, Z) + D(Z, Y ) ,
which is the desired inequality.

Example 2 Let us consider again the graph given in Figure 2 with W = {W 1 , W 2 , W 3 }. We already know that dens(W) = 15/4. Let us adopt D as our metric. Then we have

D(W 1 , W 2 ) = D(W 2 , W 3 ) = 2 - 1 3 × 4 = 23 12
and D(W 1 , W 3 ) = 2. We can now compute the reward of W, r (W) = 15 4 + λ 2 + 2 × 23 12 .

Next we formulate the problem of selecting the set of vertices that maximizes the marginal gain, in the iterative step of the greedy process, given a set of subgraphs selected so far. The following problem statement specializes Problem 3 in the context of the Dense-Overlapping-Subgraphs problem. We denote the marginal gain with χ(•; •), instead of φ(•; •), to emphasize that it is a function of a vertex set given a collection of vertex sets.

Problem 4 (Dense-Subgraph) Given a graph G = (V, E) and a collection of vertex sets W = {W 1 , . . . , W k }, W i ⊆ V , find a set of vertices U ⊆ V and U / ∈ W maximizing the marginal gain

χ(U ; W) = 1 2 dens(U ) + λD({U }, W) = 1 2 dens(U ) + λ W ∈W D(U, W ) .
Example 3 Let us consider again the graph given in Figure 2. Set W = {W 1 , W 2 } and consider adding W 3 . In this case, the gain is equal to

χ(W 3 ; W ) = 1 2 dens(W 3 )+λ(D(W 3 , W 1 )+D(W 3 , W 2 )) = 1 2 × 5 4 +λ 2 + 23 12 .
We should stress that χ(W 3 ; W ) is not equal to the difference in rewards r (W ∪ {W 3 }) -r (W ). This is due to the 1/2-factor in the density term.

In the definition of the Dense-Subgraph problem, dens is the density function given in Definition 1, while D is the subgraph distance function defined above. Had the term λD(•, •) been absent from the objective, the Dense-Subgraph problem would have been equivalent with the densest-subgraph problem, discussed in Section 4. In that case, the problem could be solved in polynomial time with Goldberg's algorithm, or approximated efficiently with Charikar's algorithm.

However, as we show next, adding the λD(•, •) term in the objective changes the complexity of the problem. In other words, in contrast to the densestsubgraph problem, Dense-Subgraph is not solvable in polynomial time.

Proposition 3 Dense-Subgraph is NP-hard.
Proof We consider the decision version of the problem. The problem is obviously in NP. To prove the completeness, we will use Regular-Clique. An instance of Regular-Clique consists of a regular graph (all vertices have the same degree) and an integer c. We are then asked to decide whether the graph contains a clique of size at least c [START_REF] Garey | Computers and intractability: a guide to the theory of NP-completeness[END_REF].

Assume that we are given a d-regular graph G = (V, E) with n = |V | and m = |E|, and an integer c > 2. Define W as follows: for each (x, y) / ∈ E, add a set {x, y} to W. Finally, set λ = m.

Let U be a subgraph and let p = |U |

2

-|E(U )| be equal to the number of non-edges in U . A straightforward calculation shows that the gain χ(U ; W) can be written as

χ(U ; W) = |E(U )| 2|U | + 2λ|W| -λ(n -d) 1 2 - λp |U | .
If we assume that U is a singleton set {u}, then the gain is equal to χ({u};

W) = α = 2λ|W | -λ(n -d)/2.
Let U be the subgraph with the optimal gain. Assume that p ≥ 1. Then, since |E(U )| ≤ m = λ the gain is at most α -m/(2|U |), which is less than the gain of a singleton. Hence, p = 0 and the gain is equal to (|U | -1)/4 + α. Algorithm 1: DOS; Algorithm for finding top-k overlapping densest subgraphs (problem Dense-Overlapping-Subgraphs)

Input: G = (V, E), λ, k Output: set of subgraphs W s.t. |W| = k and maximizing r (W) 1 W ← ∅ ; 2 foreach i = 1, . . . , k do W ← W ∪ Peel(G, W, λ) ; 3 return W ;
Hence, U will be the largest clique. It follows that the graph G contains a clique of size c if and only if Dense-Subgraph has a solution for which the gain is at least (c -1)/4 + α.

Despite this hardness result, it is still possible to devise an approximation algorithm for the Dense-Subgraph problem. Our algorithm, named Peel, is a variant of the Charikar algorithm for the densest-subgraph problem. Peel, similar to Charikar, starts with the whole graph and proceeds iteratively, removing one vertex in each step. Peel stops when there is no vertex left, and it returns the set of vertices that maximizes the gain function, selected among all vertex sets produced during the execution of the algorithm.

Peel has two main differences when compared to Charikar. First, instead of removing the minimum-degree vertex in each iteration, Peel removes the vertex that minimizes the following adjusted degree expression

deg(v; V i ) -4λ Wj v |V i ∩ W j | |W j | .
Here V i stands for the set of vertices that constitute the candidate in the current iteration-after removing some vertices in earlier iterations. The intuition for using this adjusted degree is to lower the gain associated to vertices that belong to subgraphs selected in earlier steps of the greedy process. Indeed, we want to favor high-degree vertices but we want to penalize such vertices that are contained in previously selected subgraphs and thereby generate overlap with (i.e. reduce the distance to) the current subgraph. A further difficulty is that we do not know the current subgraph (since we are currently searching for it!) so we use as a proxy the set of vertices still contained in the candidate at that step (V i ). Despite making this seemingly crude approximation, as we will see shortly, the Peel algorithm provides an approximation guarantee to the Dense-Subgraph problem.

The second difference between Peel and Charikar is the following: it is possible that Peel returns a subgraph that has been selected previously. This could happen if the value of the parameter λ is small compared to dense subgraphs that may be present in the input graph. When Peel returns a previouslyselected subgraph U , it is sufficient to modify U : we can either add one vertex, remove one vertex, or just replace U with a trivial subgraph of size 3; among all these options we select the best solution according to our marginal gain objective χ. A detailed description of this process is given in Algorithm 3. Algorithm 2: Peel; finds a dense subgraph U of the graph G, overlapping with a collection of previously discovered subgraphs W. For the quality of approximation of Peel, which is detailed in Algorithm 2, we can show the following result, which is proved in Appendix.

Input: G = (V, E), W, λ Output: U maximizing χ(U ; W) 1 Vn ← V ; 2 foreach i = n, . . . , 2 do 3 v ← arg minv deg(v; V i ) -4λ W j v |Vi∩Wj| |Wj| ; 4 V i-1 ← V i \ {v}; 5 foreach i = 1, . . . , n do 6 if V i ∈ W then V i ← Modify(V i , G, W, λ); 7 return arg max V j {χ(V j ; W)}; Algorithm 3: Modify; modifies U if U ∈ W Input: U, G, W, λ Output: modified U 1 X ← {U ∪ {x} | x / ∈ U, U ∪ {x} / ∈ W}; 2 Y ← {U \ {y} | y ∈ U, U \ {y} / ∈ W}; 3 if X = ∅ and
Proposition 4 Assume that we are given a graph G = (V, E), a collection of previously discovered vertex sets W and λ > 0. Assume that |W| < |V | and G contains more than |W| wedges, i.e. connected subgraphs of size 3. Then Peel yields 2/10 approximation for Dense-Subgraph.

The approximation guarantee of 2/10 is rather pessimistic due to pathological cases, and we can obtain a better ratio if we consider these cases separately. In particular, if Peel does not call Modify, then the approximation ratio is 1/2. If X = ∅ during Modify, then the approximation ratio is at least

|U | 2(|U |+1) ,
otherwise the ratio is at least 2/10. We note that the main function of Modify is to allow us to prove a worstcase approximation guarantee; i.e., for all possible values of λ. In practice, if Modify is called for a certain value of λ, the user should perceive this as a signal that λ is too small (as overlaps are not penalized enough) and should increase it.

The DOS algorithm

Finally, we consider the specialization of the generic Greedy algorithm studied above for the problem at hand in this paper. To obtain an algorithm for the Dense-Overlapping-Subgraphs problem, we instantiate f and d with functions whose domains consist of collections of vertices. Specifically, we let f = dens and d = D. The resulting overall algorithm for the Dense-Overlapping-Subgraphs problem, named DOS, is shown as Algorithm 1. By combining Propositions 1 and 4 we obtain the following result.

Theorem 1 DOS is an 110 -approximation algorithm for the Dense-Overlapping-Subgraphs problem.

Computational complexity: DOS consists of k successive runs of Peel, iteratively removing the vertex with minimum adjusted degree. To perform this operation fast, vertices are stored into separate worker queues according to the previous subgraphs they belong to. Since such vertices incur the same distance penalty, we keep the queues sorted by degree. There are at most t = min{2 k , |V |} such queues. In practice, the number is much smaller. To find the next vertex, we compare the top vertex of every worker queue. The search can be done in O(t) time. Upon deletion of a vertex, updating a single adjacent vertex in a worker queue can be done in constant time, 1 while updating the distance penalties can be done in O(k) time. If we are forced to call Modify, then finding the best subgraph in X and Y can be done in O(|E| + |V |k) time. In a rare pathological case we are forced to return a wedge. We can do this by first computing k wedges before invoking DOS. If we ever need a wedge, we simply select a wedge from this list that is not yet in W. Consequently, we can execute

DOS in O(k(|E| + |V |(t + k))) time.

Experiments

In this section we report on the experimental evaluation of our proposed algorithm DOS. Our python implementation of the DOS algorithm is publicly available online. 2First, we explore the behavior of the algorithms in a controlled setting, using synthetic networks with planted ground-truth subgraphs. Then, we evaluate the algorithms on real-world networks for which the ground-truth is not accessible. In these two parts, we use different evaluation measures, as required by the distinct goals of the two scenarios.

Algorithms. In both parts, our primary baseline is the MAR algorithm recently proposed by Balalau et al. [START_REF] Oana | Finding subgraphs with maximum total density and limited overlap[END_REF]. Similarly to our approach, their goal is to extract dense overlapping subgraphs while controlling the Jaccard coefficient between the discovered subgraphs.

Both methods MAR and DOS allow/require to adjust the overlap permitted between subgraphs in the solution. In MAR, this is done by fixing a strict maximum threshold for the Jaccard coefficient between two subgraphs, while in DOS, by setting the value of the parameter λ, which balances density and distance.

For DOS, note that the density of subgraphs vary from dataset to dataset, while the distance function D is always below 2. Consequently, in practice it is easier to set the value of λ relative to the density of the first subgraph discovered by the algorithm. Note that when extracting the first subgraph, λ has no effect since the distance part of the score given in Problem 4 is 0. Thus, when running the algorithm we provide a value β and we set λ = βdens(W 1 ).

For MAR, we denote the Jaccard threshold by σ. Note that larger values of σ result in increased overlap with MAR but larger values of β reduce overlap with DOS.

Finding planted subgraphs

In the first part of our experiments, we consider synthetic networks and evaluate how well the algorithms are able to recover planted ground-truth subgraphs.

Datasets. Our synthetic networks are generated as follows: each network consists of a backbone of five subsets of vertices. We generate networks both with and without overlaps. In networks without overlap, the subgraphs simply consists of five disjoint subsets of 30 vertices. In configurations with overlap, the subgraphs are arranged in a circle, they are assigned 20 vertices of their own plus 10 vertices shared with the subgraph on one side and 10 shared vertices with the other side.

We consider two families of networks depending on whether connections are generated using the Erdős-Rényi model with fixed densities between 0.6 and 0.9, or using the Barabási-Albert preferential attachment model.

This way, we obtain four types of noise-free networks. We also consider noisy variants, that is, networks where noise is added on top of the backbone. Specifically, we double the number of vertices in the network by adding new vertices that do not belong to any of the subsets, and the connections are flipped with the probability of 0.01.

For each of the eight configurations, we generate ten synthetic networks, each containing five planted subgraphs. 3Statistics. We adopt an approach similar to [START_REF] Yang | Community-affiliation graph model for overlapping network community detection[END_REF] and compare the sets of subgraphs detected by the algorithms to the planted ground-truth using the following measures. NMI : the Normalized Mutual Information between the ground-truth and the detected subgraphs, F 1 [t/d]: the average F 1 -score of the best-matching ground-truth subgraph to each detected subgraph ("truth to d etected"), F 1 [d/t]: the average F 1 -score of the best-matching detected subgraph to each ground-truth subgraph ("d etected to truth"), Ω: the Omega index, i.e., the fraction of vertex pairs that share the same number of communities in the solution and the ground-truth. Each of these four measures takes value between 0 and 1, with values closer to 1 indicating highest similarity between the detected subgraphs and the planted ground-truth.

Results. The averages of these statistics over ten datasets for each configuration are shown in Table 1. We observe that the MAR algorithm performs better in the absence of overlap and noise, and is able to recover the ground truth perfectly in the case of the Erdős-Rényi graphs. This result can be explained by the fact that MAR handles overlaps with a hard constraint. However, our method is clearly superior when the backbone communities overlap, and also more resistant to noise, that is, for graphs that resemble better real-world application scenarios. Further experiments, in a setup where the five planted subgraphs have different sizes, show that the difference between the two algorithms is less pronounced. In particular, in the absence of overlap and noise, the improved performance of DOS gets closer to the relatively stable performance of MAR, while in the presence of overlap and noise the performance of MAR is improved compared to the balanced case and gets closer to the performance of DOS, which remains relatively stable.

Comparison on real-world networks

We now turn to an empirical evaluation of our proposed algorithm on realworld datasets.

Datasets. We use the following networks.

Co-authorship networks:

The first dataset is the DBLP network, 4 where vertices represent researchers, and edges represent co-authorship relations.

From this co-authorship network we extract smaller instances. First, we consider some ego-net graphs. We start with 13 high-profile computer scien-tists, 5 and consider their ego-nets of radius 2. We collectively refer to this collection of ego-nets as DBLP.E2. Second, we consider the subgraphs induced by researchers who have published in the ICDM and KDD conferences, respectively, giving rise to two networks that form the DBLP.C dataset.

The remaining collections consist of networks distributed via the Stanford network analysis project. 6Social circles: Ego-nets collected from Google+ users who have shared their circles are divided into two collections. The first one, G+.S, contains relatively small ego-nets, having fewer than 42 000 edges, while the second, G+.L, contains ego-nets with larger numbers of edges. The FB collection contains 10 ego-nets representing friend lists from Facebook.

Location-based social networks: We also consider a collection of location-based networks from Brightkite and Gowalla, two websites that allow there users to share their location. We extract smaller instances by applying the following procedure: we assign each user to their most frequent location and divide the network into 8 broad geographic areas. 7 We denote this collection of 16 networks as BKGW.

Large graphs: Finally, denoted by XL, we consider a number of large graphs that were used by Balalau et al. [START_REF] Oana | Finding subgraphs with maximum total density and limited overlap[END_REF]: web graphs from Stanford and Google, the YouTube social network, and the internet topology graph from Skitter.

Statistics on all datasets are provided in Table 2.

Statistics. Again we compare our algorithm to its main competitor, the MAR algorithm. We apply both algorithms on every dataset to extract the top-k overlapping subgraphs, while varying the overlap parameters β and σ. For each run we obtain a set of subgraphs W = {W 1 , . . . , W k }. In some cases, MAR returns fewer than k subgraphs, therefore |W| can be smaller than k.

For each solution W, we compute its coverage, that is, the ratio of vertices that belong to at least one subgraph C (W) = ∪ k i=1 W i /|V |, the average size of the subgraphs |W | and the average vertex multiplicity over covered vertices, where the multiplicity of vertex v, denoted as µ(v), is the number of subgraphs it belongs to.

In addition, for each solution we compute (i ) the average density dens(W i ) over all subgraphs, (ii ) the average distance D(W i , W j ) over all pairs of subgraphs, (iii ) the average Jaccard distance

J (W i , W j ) = 1 - |W i ∩ W j | |W i ∪ W j |
over all pairs of subgraphs, and (iv ) the modularity

Q(W) = 1 2|E| W ∈W u,v∈W A uv - δ(u)δ(v) 2|E| 1 µ(u)µ(v) ,
where µ(v) is the number of subgraphs that vertex v belongs to, δ(v) its degree, and A the graph adjacency matrix.

Results. Tables 3456provide summaries of our experimental comparison for DBLP and G+ datasets. We report the number of subgraphs (|W|), average density (dens), average distance (D), average Jaccard distance (J ), modularity(Q), coverage (C ), average subgraph size (|W |) and average vertex multiplicity (µ(v)) averaged across all networks in the collection. Results for the remaining collections are similar, and are thus omitted.

The profile of solutions obtained on five networks from different collections, for a wide range of values of β and σ are shown in Figure 3. Each row corresponds to the profile of one network: the ego-net of C. Papadimitriou from DBLP.E2, the KDD network from DBLP.C, the 1183. . . 6467 ego-net from G+.S, the 1684 ego-net from FB, and the Brightkite network of Latin-America from BKGW. The columns show the average distance (D), average Jaccard distance (J ) and coverage (C ) of solutions plotted against average density (dens).

For reference, we added three points to the profiles, representing the solutions obtained respectively with three baseline methods which do not allow to adjust the overlap tolerance. Namely, we considered Links: The algorithm of Ahn et al. [START_REF] Ahn | Link communities reveal multiscale complexity in networks[END_REF] discovers overlapping subgraphs by performing a hierarchical clustering on the edges rather than the vertices of the input graph. We consider the top 20 densest subgraphs returned by this method. Metis: We apply the popular spectral graph-partitioning algorithm by Karypis and Kumar [START_REF] Karypis | Multilevel algorithms for multi-constraint graph partitioning[END_REF] to obtain a complete partition of the graph vertices into k disjoint sets. Dense This algorithm, used as a baseline by Galbrun et al. [START_REF] Galbrun | Overlapping community detection in labeled graphs[END_REF], extracts dense subgraphs in the same iterative process similar to the DOS algorithm but edges are allowed to contribute to at most one subgraph and are assigned where they benefit most.

At one end of the range of solutions returned by DOS lies the solution that corresponds to setting λ = 0, i.e., focusing entirely on density. This solution consists of copies of the densest subgraph. At the other end, for large values of λ, lies the solution that does not tolerate any overlap.

Expectedly, we observe that the density of the subgraphs returned increases as the distance decreases, that is, as more overlap is allowed, both algorithms can find denser subgraphs. However, we note that DOS exploits the overlap allowance better, returning subgraphs with greater average densities than MAR for similar values of distance D and Jaccard distance. Additionally, we see that DOS tends to return larger subgraphs and to achieve better coverage scores.

Running times

Finally, we evaluate the scalability of our method. Figure 4 shows running times for DOS and MAR, as a function of the size of the network, measured by the number of edges, for different values of their overlap parameters.

The same figure also provide running times for the baseline methods and we can observe that both MAR and DOS scale better than Links and Dense but not as well as Metis.

On average, our algorithm is faster than MAR. An added advantage is the better stability of the running time across values of the overlap parameter, with the extreme value σ = 0.95 resulting in much larger running time for MAR. We should also note here that Balalau et al. [START_REF] Oana | Finding subgraphs with maximum total density and limited overlap[END_REF] offer a heuristic that is faster than MAR, but at the expense of quality.

Concluding remarks

We studied the problem of discovering dense and overlapping subgraphs. Our approach optimizes density as well as the diversity of the obtained collection. Our solution, inspired by the work of Borodin et al. [START_REF] Borodin | Max-sum diversification, monotone submodular functions and dynamic updates[END_REF] and Charikar [START_REF] Charikar | Greedy approximation algorithms for finding dense components in a graph[END_REF], is an efficient greedy algorithm with an approximation guarantee of 1/10. Our method improves significantly the previous work on the problem by Balalau et al. [START_REF] Oana | Finding subgraphs with maximum total density and limited overlap[END_REF]. Not only do we provide an approximation guarantee, while the baseline is a heuristic, but it also yields practical improvements, both in terms of quality and efficiency. Our experiments, especially Figure 3, demonstrate that we obtain denser and more diverse subgraphs.

Our approach has two parameters: the number of subgraphs k and the parameter λ controlling the relative importance of density and overlap. Since our method is greedy, the problem of selecting k is somewhat alleviated as the first k subgraphs will remain constant if we increase k. Selecting λ is more difficult as the relation between the density and the diversity terms is not obvious. We approach this problem by computing profiles as in Figure 3 by varying λ and selecting values that provides a good trade-off between density and overlap.

This work opens several new directions for future work. We have shown that a subproblem, Dense-Subgraph, is NP-hard, however, we did not establish the hardness of the main problem Dense-Overlapping-Subgraphs. We conjecture that it is also NP-hard. Another open question is to improve the approximation guarantee, as well as to study what other types of density functions and overlap distances can be used in our framework.

A Proof of Proposition 1

Let us first define

h(x; Y ) = [f (x ∪ Y ) -f (Y )] /2 and g(x; Y ) = h(x; Y ) + d(Y ∪ x) -d(Y ) = h(x; Y ) + d(x, Y ) .
For proving the proposition, we will need Lemma 1. For a given x ∈ X, there are exactly |X| -1 pairs (x, z) such that x = z ∈ X. Consequently, summing over all x, z ∈ X such that x = z gives us 2c(|X| -1)d(X, y) ≥ 2d(X) .

Summing over y ∈ Y proves the lemma.

Proof (Proof of Proposition 1) Let G 1 ⊂ • • • ⊂ G k be the sets during Greedy. Fix 1 ≤ i ≤ k.
Then G i is the current solution after i-th iteration of Greedy.

Let O be the optimal solution. Write Let u i be the item added at the i + 1th step, G i+1 = {u i } ∪ G i . Then, since g(u i ; G i ) ≥ αg(v; G i ) for any v ∈ C,

A = O ∩ G i , C = O \ A, and B = G i \ A. Lemma 1 implies that c(|A| -1)d(A, C) ≥ |C|d(A) ,
g(u i ; G i ) ≥ α 2k [f (O) -f (G k )] + iα ck(k -1) d(O) .
Summing over i gives us

1 2 f (G k ) + d(G k ) = k-1 i=0 g(u i ; G i ) ≥ α 2 [f (O) -f (G k )] + α 2c d(O) .
Since α ≤ 1 and c ≥ 1, we have

r (G k ) = f (G k ) + d(G k ) ≥ α 2 f (O) + α 2c d(O) ≥ α 2c r (O) ,
which completes the proof.

B Proof of Proposition 4

To prove the proposition we need to first show that Modify does not decrease the gain of a set significantly. Proof Write r = |U | and α = r r+1 . We will split the proof in two cases. Case 1: Assume that X, as given in Algorithm 3, is not empty. Select B ∈ X. We will show that Let us define β as the fraction of the numerators,

β = 2p(1 + r) -(1 + q) 2 2rp -q 2 .
We wish to show that β ≥ 1. Since p ≥ q + 1, β = 2p(1 + r) -(1 + q) 2 2rp -q 2 = 2rp -q 2 + 2p -2q -1 2rp -q 2 ≥ 2rp -q 2 + 2(q + 1) -2q -1 2rp -q 2 = 2rp -q 2 + 1 2rp -q 2 ≥ 1.

The ratio of distances is now

D(B, W ) ∆ = β r r + 1 ≥ r r + 1 = α.
This proves the first case. Let S be the set returned by Peel.

If R / ∈ W, then (R; W) = 0. Moreover, R is not modified, and is one of the graphs that is tested for gain. Consequently, χ(S; W) ≥ χ(R; W), proving the statement.

If R ∈ W, then it is modified by Modify to, say, R . Lemma 2 implies that 5/2 × χ(R , W) ≥ χ(R; W) + (R; W). Since, χ(S; W) ≥ χ(R ; W), this completes the proof.

Fig. 1

 1 Fig.1Densest overlapping subgraphs on Zachary karate club dataset[START_REF] Zachary | An information flow model for conflict and fission in small groups[END_REF]. k = 3, β = 2.

2 W 3 Fig. 2

 232 Fig. 2 Toy example

Definition 1

 1 The density of a graph G = (V, E) is defined as dens(G) = |E|/|V |.

4 U 6 U

 46 dens(U ) ≤ 5/3 then ← {a wedge of size 3 not in W}; 5 else ← arg max C∈X∪Y {χ(C; W)}; 7 return U ;

Fig. 3

 3 Fig. 3 Solution profiles for five networks. Each row corresponds to the profile of one network, as indicated on the left.

Fig.

  Fig. Running times of DOS and MAR with different values of their overlap parameters, as well as the three baselines, on networks of increasing sizes sampled from the seven datasets.

Lemma 1

 1 Let d be a c-relaxed metric. Let X and Y be two disjoint sets. Then c(|X| -1)d(X, Y ) ≥ |Y |d(X) . Proof Let y ∈ Y and x, z ∈ X. By definition, c(d(x, y) + d(z, y)) ≥ d(x, z) .

  which in turn implies|C|i(d(A) + d(A, C)) ≤ ci(|A| -1)d(A, C) + |C|id(A, C) = ci(|A| -1 + |C|)d(A, C) = ci(k -1)d(A, C) . Moreover, Lemma 1 implies that c(|C| -1)d(B, C) ≥ |B|d(C) c(|C| -1)d(A, C) ≥ |A|d(C) , which, together with |C| = |B| + k -i, implies |C|id(C) = (k -i)id(C) + |B|id(C) = (k -i)(|A| + |B|)d(C) + |B|id(C) = (k -i)|A|d(C) + |B|kd(C) ≤ c(k -i)(|C| -1)d(A, C) + ck(|C| -1)d(B, C) ≤ c(k -i)(k -1)d(A, C) + ck(k -1)d(B, C) .Combining these two inequalities leads us to|C|id(O) = |C|id(A) + |C|id(C) + |C|id(A, C) ≤ ck(k -1)(d(A, C) + d(B, C)) = ck(k -1)d(G i , C) .Submodularity and monotonicity implyv∈C g(v; G i ) = v∈C [h(v; G i ) + d({v} , G i )] = v∈C h(v; G i ) + d(C, G i ) O) -f (G k )] + i|C| ck(k -1) d(O) .

Lemma 2

 2 Assume a graph G = (V, E). Assume a collection of k distinct subgraphs W of G, and let U ∈ W. Assume that k < |V | and G contains more than k wedges, i.e. connected subgraphs of size 3. Let M = Modify(U, G, W, λ). Then χ(V ; W) ≥ 2/5 × (χ(U, W) + λ).

  dens(B) ≥ αdens(U ) and D(B, W ) ≥ α(D(U, W ) + I[U = W ]), for any W ∈ W, where I[U = W ] = 1 if U = W , and 0 otherwise. This automatically guarantees that χ(B; W, λ) ≥ α(χ(U ; W, λ) + λ),proving the result since α ≥ 1/2 and the gain of M is at least as good as the gain of B.To prove the first inequality, note thatdens(B) = |E(B)| r + 1 ≥ |E(U )| r + 1 = α |E(U )| r = αdens(U ) .To prove the second inequality fix W ∈ W, and letp = |W |, q = |W ∩ U |. Define ∆ = D(U, W ) + I[U = W ] = 2 -q 2 rp = 2rp -q 2 rp , Let v be the only vertex in B \ U . If v / ∈ W , then D(B, W ) ≥ ∆.Hence, we can assume that v ∈ W . This leads toD(B, W ) = 2 -|B ∩ W | 2 r) -(1 + q) 2(1 + r)p .

Case 2 := 3 )

 23 Assume that X = ∅. Then we must have Y = ∅ and r ≥ 2, as otherwise |W| ≥ |V |, which violates the assumption of the lemma.We can express the (weighted) degree of a vertex in H asdeg H (v; U ) = s(v) + w∈U w =v c(v, w) = deg G (v; U )deg G (v; U ) -λ j|v∈W j 4|U ∩ W j | -2 |W j | .(Write k = |W|. These equalities lead to the following identity,dens(U ; H) deg H (v; U ) + s(v) = 4λk + dens(U ; G) -1 2|U | v∈U λ j|v∈W j 4|U ∩ W j | |W j | = dens(U ; G) -2λ k j=1 2 -|U ∩ W j | 2 |U ||W j | = 2χ(U ; W, λ) + (U, W),(4)where (U, W) is a correction term, equal to 2λ if U ∈ W, and 0 otherwise. Let O be the densest subgraph in H. Next we show that during the for-loop Peel finds a graph whose density clost to dens(O; H). Let o be the first vertex in O deleted by Peel. We must have deg H (o; O) ≥ dens(O; H) , as otherwise we can delete o from O and obtain a better solution. Let R = V i be the graph at the moment when o is about to be removed. Let us compare deg H (o; O) and deg H (o; R). We can lower-bound of the second term of the right-hand side in Equation (3) by -4kλ -s(v). Since O ⊆ R, this gives us deg H (o; O) ≤ deg G (o; O) ≤ deg G (o; R) ≤ deg H (o; R) + s(o) + 4kλ. To upper-bound the first two terms, note that by definition of Peel, the vertex o has the smallest deg H (o; R) + s(o) among all the vertices in R. Hence, deg H (o; R) + s(o) ≤v∈R deg H (v; R) + s(v) |R| = 2 c(R) |R| = 2dens(R; H) . To complete the proof, let O be the graph outside W, maximizing the gain. Due to Eq. 4, we have 2χ O ; W, λ = dens O ; H + 4kλ ≤ dens(O; H) + 4kλ ≤ 2dens(R; H) + 8kλ = 2(dens(R; H) + 4kλ) = 4χ(R; W, λ) + 2 (R; W).

  2 , W 3 }. The collective density of W is then equal

	dens(W) = dens(W 1 ) + dens(W 2 ) + dens(W 3 ) =	6 4	+	3 3	+	5 4	=	15 4	.

Table 1

 1 Performance of DOS and MAR on synthetic data. For each dataset, we compare the detected subgraphs to the ground truth using the Normalized Mutual Information (NMI), F 1 scores (F 1 [t/d] and F 1 [d/t]) and Omega index (Ω).

	method param.	NMI F 1 [t/d] F 1 [d/t]	Ω	NMI F 1 [t/d] F 1 [d/t]	Ω
				Erdős-Rényi		Barabási-Albert
					No overlap, noise-free
	DOS	2.0	0.94	0.95	0.93	0.95	0.96	0.87	0.86	0.91
		1.0	0.94	0.96	0.96	0.95	0.65	0.75	0.79	0.73
		0.5	0.93	0.97	0.97	0.93	0.70	0.64	0.76	0.80
	MAR	0.1	1.00	1.00	1.00	1.00	1.00	0.92	0.92	0.95
		0.5	1.00	1.00	1.00	1.00	0.81	0.54	0.81	0.88
		0.75	0.92	0.82	0.97	0.94	0.79	0.54	0.85	0.86
						No overlap, noisy
	DOS	2.0	0.84	0.83	0.72	0.87	0.72	0.71	0.69	0.93
		1.0	0.69	0.87	0.81	0.62	0.66	0.65	0.70	0.95
		0.5	0.81	0.91	0.90	0.95	0.57	0.61	0.68	0.93
	MAR	0.1	0.90	0.93	0.88	0.98	0.98	0.90	0.89	0.98
		0.5	0.88	0.93	0.92	0.98	0.57	0.67	0.76	0.93
		0.75	0.74	0.83	0.87	0.94	0.45	0.57	0.73	0.92
					With overlap, noise-free
	DOS	2.0	0.27	0.72	0.72	0.41	0.34	0.71	0.69	0.75
		1.0	0.27	0.82	0.79	0.20	0.33	0.72	0.73	0.75
		0.5	0.25	0.87	0.83	0.22	0.24	0.70	0.72	0.66
	MAR	0.1	0.19	0.56	0.51	0.51	0.24	0.56	0.56	0.68
		0.5	0.28	0.66	0.70	0.44	0.12	0.58	0.60	0.68
		0.75	0.22	0.71	0.72	0.33	0.04	0.53	0.56	0.63
						With overlap, noisy
	DOS	2.0	0.26	0.58	0.54	0.45	0.34	0.67	0.64	0.93
		1.0	0.28	0.74	0.72	0.79	0.31	0.68	0.69	0.92
		0.5	0.26	0.87	0.84	0.79	0.21	0.65	0.67	0.90
	MAR	0.1	0.16	0.53	0.27	0.84	0.16	0.49	0.37	0.87
		0.5	0.12	0.56	0.51	0.83	0.11	0.56	0.58	0.91
		0.75	0.04	0.53	0.51	0.79	0.03	0.51	0.54	0.89

Table 2

 2 Datasets statistics. For each dataset, we indicate how many graphs it consists of (#G), the number of edges (|E|) and vertices (|V |), as well as the density (dens(G)) across all graphs in the collection.

	Set	#G		|E|			|V |	dens(G)
			min	max	avg	min	max	avg min max avg
	DBLP.E2 13	1 427	13 251	6 435.77	721	4 598 2 197.38 1.98 3.69 2.84
	DBLP.C	2	10 689	11 208	10 948.50 2 891	3 140 3 015.50 3.40 3.88 3.64
	G+.S	41	204	41 123	13 146.22	35	1 842	479.34 3.75 68.52 23.48
	G+.L	22	42 810	176 691	96 124.32 1 007	3 799 1 840.68 15.85 103.28 55.05
	FB	10	146	30 025	8 508.70	52	1 034	408.90 2.81 40.19 14.31
	BKGW	12	555	218 434	46 152.67	358	46 942 11 785.25 1.55 5.38 3.29
	XL	4 1 992 636 11 095 298 5 099 402.25 281 903 1 696 415 997 230.25 2.63 7.07 5.29

Table 3

 3 Results for DBLP.E2, k = 20. For each algorithm/parameter pair we report the number of subgraphs (|W|), average density (dens), average distance (D), average Jaccard distance (J ), modularity(Q), coverage (C ), average subgraph size (|W |) and average vertex multiplicity (µ(v)) averaged across all networks in the collection.

	method	param.	|W|	dens	D	J	Q	C	|W |	µ(v)
	DOS	1.0	20	5.09	2.00	0.99	0.098	0.71	96	1.33
		0.1	20	7.59	1.93	0.90	0.034	0.50	168	3.08
		0.01	20	9.72	1.50	0.49	0.008	0.24	232	9.52
		0.001	20	10.01	1.06	0.06	0.003	0.11	200	15.91
	MAR	0.25	20	4.64	2.00	0.98	0.142	0.63	81	1.22
		0.5	20	4.97	1.96	0.93	0.111	0.66	118	1.66
		0.75	20	6.28	1.85	0.81	0.066	0.49	140	2.77
		0.95	20	8.82	1.55	0.52	0.017	0.21	156	6.92

Table 4

 4 Results for DBLP.C, k = 20. Columns as in Table3.

	method	param.	|W|	dens	D	J	Q	C	|W |	µ(v)
	DOS	1.0	20	6.45	2.00	0.99	0.117	0.62	117	1.27
		0.1	20	10.92	1.92	0.88	0.049	0.49	216	2.94
		0.01	20	14.97	1.40	0.39	0.005	0.17	301	11.97
		0.001	20	15.39	1.03	0.03	0.003	0.11	299	18.11
	MAR	0.25	20	5.84	2.00	0.99	0.115	0.40	74	1.23
		0.5	20	6.69	1.95	0.92	0.098	0.45	114	1.71
		0.75	20	8.70	1.84	0.79	0.054	0.34	147	2.85
		0.95	20	13.17	1.38	0.36	0.011	0.15	206	9.46

Table 5

 5 Results for G+.S, k = 20. Columns as in Table3.

	method	param.	|W|	dens	D	J	Q	C	|W |	µ(v)
	DOS	1.0	20	11.08	2.00	0.99	0.036	0.98	37	1.71
		0.1	20	42.81	1.83	0.78	0.010	0.96	130	6.38
		0.01	20	67.41	1.22	0.21	0.002	0.55	172	14.67
		0.001	20	68.60	1.04	0.04	0.001	0.43	168	18.53
	MAR	0.25	14	13.11	1.98	0.96	0.059	0.91	36	1.29
		0.5	17	16.45	1.91	0.87	0.038	0.90	42	1.91
		0.75	19	27.42	1.75	0.71	0.020	0.79	62	3.55
		0.95	20	55.74	1.34	0.32	0.005	0.53	121	10.81

Table 6

 6 Results for G+.L, k = 20. Columns as in Table3.

	method	param.	|W|	dens	D	J	Q	C	|W |	µ(v)
	DOS	1.0	20	30.58	2.00	0.99	0.035	0.91	124	1.55
		0.1	20	111.37	1.85	0.81	0.010	0.90	406	5.27
		0.01	20	175.83	1.25	0.24	0.001	0.45	545	14.10
		0.001	20	178.91	1.04	0.04	0.001	0.33	531	18.89
	MAR	0.25	20	25.50	1.98	0.96	0.051	0.84	96	1.31
		0.5	20	40.77	1.90	0.86	0.032	0.76	128	1.93
		0.75	20	72.69	1.73	0.69	0.015	0.62	190	3.57
		0.95	20	147.08	1.31	0.30	0.003	0.40	380	11.34

Here we use the fact that edges are not weighted, and consequently the queue can be implemented as an array of linked lists of vertices.

http://research.ics.aalto.fi/dmg/dos_code.tgz

The synthetic networks used in our experiments are available at http://research.ics. aalto.fi/dmg/dos_synth.tgz

http://dblp.uni-trier.de/xml/

Namely, S. Abiteboul, E. Demaine, M. Ester, C. Faloutsos, J. Han, G. Karypis, J. Kleinberg, H. Mannila, K. Mehlhorn, C. Papadimitriou, B. Shneiderman, G. Weikum and P. Yu.

http://snap.stanford.edu

Namely, Oceania, Latin-America, the USA, Europe, the Middle-East and East Asia

Assume that dens(U ) ≥ 5/3. Let B ∈ Y . Removing a single item of U decreases the density by 1, at most. This gives us dens(B) dens(U ) ≥ dens(U ) -1 dens(U ) ≥ 5/3 -1 5/3 = 2 5 .

To bound the distance term, fix W ∈ W, and let

Hence, assume that v / ∈ W . This implies that q ≤ min p, r -1, or q 2 ≤ p(r -1). As before, we can express the distance term as

The ratio is then

where the first inequality follows from the fact that the ratio is decreasing as function of q.

Assume that dens(U ) < 5/3. By assumption there is a wedge B outside W. Since dens(B) ≥ 2/3, we have dens(B) /dens(U ) ≥ 2/5. The distance terms decrease by a factor of 1/2, since

Combining the inequalities proves that

which proves the lemma.

Proof (Proof of Proposition 4)

To prove the proposition, we will first form a new graph H, and show that the density of a subgraph in H is closely related to the gain. This then allows us to prove the statement. Let us first construct the graph H: given a vertex v let us define