Condensed representations of changes in dynamic graphs through emerging subgraph mining. (September 2020)

• Record Type: Journal Article
• Authors: Impedovo, Angelo; Loglisci, Corrado; Ceci, Michelangelo; Malerba, Donato
• Is Part Of: Engineering applications of artificial intelligence. Volume 94(2020)
• Publication Date: 2020-09
• Subjects: Emerging subgraph mining -- Closed subgraph mining -- Maximal subgraph mining -- Dynamic graphs; Engineering -- Data processing -- Periodicals; Artificial intelligence -- Periodicals; Expert systems (Computer science) -- Periodicals; Ingénierie -- Informatique -- Périodiques; Intelligence artificielle -- Périodiques; Systèmes experts (Informatique) -- Périodiques; Artificial intelligence; Engineering -- Data processing; Expert systems (Computer science); Periodicals; 620.00285
• DOI: 10.1016/j.engappai.2020.103830
• Languages: English
• ISSNs: 0952-1976

Abstract

Abstract: 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. Highlights: Subgraph mining-based approaches to the problem of change discovery. Redundant and duplicated information present in very large sets of subgraphs. Condensed representations of change-related subgraphs. Emerging, closed and maximal sub-graphs. Empirical evaluation of the space savings and accuracy on real world datasets.