Condensed representations of changes in dynamic graphs through emerging subgraph mining

Change mining is one of the main subjects of analysis on time-evolving data. Regardless of the distribution of the changes over the data, often the algorithms return very large sets of results. In fact, one class of algorithms designed for change mining is based on pattern mining, which notoriously suffers from the problem of a huge number of returned patterns. Moreover, the complexity of some types of data, like dynamic graphs, could make the size of the final changes even larger, which makes interpretation difficult or even impossible. This paper represents the first attempt, to our knowledge, to build condensed representations of changes from dynamic graphs. We study changes captured with the pattern (subgraph) mining framework and focus on the discovery of subgraphs able to (i) represent evident changes and (ii) convey graph-based information that is not already expressed by other subgraphs. To do this, we revise an existing approach by introducing the notion of emerging subgraphs, used to remove uninteresting changes and the notions of closed and maximal subgraphs, used to remove redundant changes. Experiments performed on real-world dynamic graphs show that the condensed representations maintain the accuracy levels of the original approach and often offer a loss-less representation of the detected changes.