GraphMDL+: Interleaving the Generation and MDL-based Selection of Graph Patterns - Archive ouverte HAL Access content directly
Conference Papers Year : 2021

GraphMDL+: Interleaving the Generation and MDL-based Selection of Graph Patterns

(1) , ,
1
Peggy Cellier
Sébastien Ferré

Abstract

Graph pattern mining algorithms ease graph data analysis by extracting recurring structures. However, classic pattern mining approaches tend to extract too many patterns for human analysis. Recently, the GraphMDL algorithm has been proposed, which reduces the generated pattern set by using the Minimum Description Length (MDL) principle to select a small descriptive subset of patterns. The main drawback of this approach is that it needs to first generate all possible patterns and then sieve through their complete set. In this paper we propose GraphMDL+, an approach based on the same description length definitions as GraphMDL but which tightly interleaves pattern generation and pattern selection (instead of generating all frequent patterns beforehand), and outputs a descriptive set of patterns at any time. Experiments show that our approach takes less time to attain equivalent results to GraphMDL and can attain results that GraphMDL could not attain in feasible time. Our approach also allows for more freedom in the pattern and data shapes, since it is not tied to an external approach.
Fichier principal
Vignette du fichier
sac2021-graphmdlplus (1).pdf (517.34 Ko) Télécharger le fichier

Dates and versions

hal-03508797 , version 1 (11-01-2022)

Identifiers

Cite

Francesco Bariatti, Peggy Cellier, Sébastien Ferré. GraphMDL+: Interleaving the Generation and MDL-based Selection of Graph Patterns. SAC '21: The 36th ACM/SIGAPP Symposium on Applied Computing, Mar 2021, Virtual Event, South Korea. pp.355-363, ⟨10.1145/3412841.3441917⟩. ⟨hal-03508797⟩
68 View
44 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More