Grasping frequent subgraph mining for bioinformatics applications

MaNIACS: Approximate Mining of Frequent Subgraph Patterns through Sampling

We present MaNIACS, a sampling-based randomized algorithm for computing high-quality approximations of the collection of the subgraph patterns that are frequent in a single, large, vertex-labeled graph, according to the Minimum Node Image-based (MNI) frequency measure. The output of MaNIACS comes with strong probabilistic guarantees, obtained by using the empirical Vapnik-Chervonenkis (VC) dimension, a key concept from statistical learning theory, together with strong probabilistic tail bounds on the difference between the frequency of a pattern in the sample and its exact frequency. MaNIACS leverages properties of the MNI-frequency to aggressively prune the pattern search space, and thus to reduce the time spent in exploring subspaces that contain no frequent patterns. In turn, this pruning leads to better bounds to the maximum frequency estimation error, which leads to increased pruning, resulting in a beneficial feedback effect. The results of our experimental evaluation of MaNIACS on real graphs show that it returns high-quality collections of frequent patterns in large graphs up to two orders of magnitude faster than the exact algorithm.

Detecting Incremental Frequent Subgraph Patterns in IoT Environments

As graph stream data are continuously generated in Internet of Things (IoT) environments, many studies on the detection and analysis of changes in graphs have been conducted. In this paper, we propose a method that incrementally detects frequent subgraph patterns by using frequent subgraph pattern information generated in previous sliding window. To reduce the computation cost for subgraph patterns that occur consecutively in a graph stream, the proposed method determines whether subgraph patterns occur within a sliding window. In addition, subgraph patterns that are more meaningful can be detected by recognizing only the patterns that are connected to each other via edges as one pattern. In order to prove the superiority of the proposed method, various performance evaluations were conducted.