Approximate Network Motif Mining Via Graph Learning
Frequent and structurally related subgraphs, also known as network motifs,
are valuable features of many graph datasets. However, the high computational
complexity of identifying motif sets in arbitrary datasets (motif mining) has
limited their use in many real-world datasets. By automatically leveraging
statistical properties of datasets, machine learning approaches have shown
promise in several tasks with combinatorial complexity and are therefore a
promising candidate for network motif mining. In this work we seek to
facilitate the development of machine learning approaches aimed at motif
mining. We propose a formulation of the motif mining problem as a node
labelling task. In addition, we build benchmark datasets and evaluation metrics
which test the ability of models to capture different aspects of motif
discovery such as motif number, size, topology, and scarcity. Next, we propose
MotiFiesta, a first attempt at solving this problem in a fully differentiable
manner with promising results on challenging baselines. Finally, we demonstrate
through MotiFiesta that this learning setting can be applied simultaneously to
general-purpose data mining and interpretable feature extraction for graph
classification tasks.