Search

Dense subgraphs convey important information and insights about a graph structure. Several applications, such as graph visualization, graph summarization, and complex network analysis rely on discovering the dense subgraphs available within the target graph. This enumeration problem has been intensively addressed by several research communities but remains a challenging problem because of its importance and use. This problem generalizes the clique problem and is thus NP-hard and not approximable in polynomial time in general graphs. In this paper, we propose to deal with this problem in a specific application case where the type of the discovered dense subgraphs is important. This is the case of graph summarization for example. However, existing dense subgraph discovery algorithms are either dedicated to specific kind of structures such as cliques and bicliques or are too general and list the dense subgraphs without giving their types. To deal with this issue, we provide a unified approach that lists dense subgraphs and provides their types. Our approach relies on deep learning. More precisely, we enrich exiting structural node embedding with extra information, computed on node neighborhoods, to effectively capture their belonging to dense subgraphs. We evaluate our approach on several datasets to attest its efficiency and its effectiveness on two main applications: graph summarization and graph clustering. Our results show that our method significantly improves the compression rate in graph summarization, achieving up to 30% size reduction for the largest graphs tested and exceeding 80% for sparse graphs. Additionally, even for highly dense graphs, our method consistently achieves a non-zero AMI score, outperforming other approaches on the clustering application. • We propose a deep learning approach to dense subgraph mining. • We aim to simply give insights about a graph structure. • We compute a node parameter that reveals how much dense the graph is around it. • We apply this approach successfully in graph summarization and clustering. [ABSTRACT FROM AUTHOR]