FLEXIS: FLEXible Frequent Subgraph Mining using Maximal Independent Sets

Frequent Subgraph Mining (FSM) is the process of identifying common subgraph patterns that occur over a certain threshold. The NP-hardness of FSM makes it a complex and time-consuming task. FSM is generally solved in 2 steps, 1). Generation step: determining the possible patterns that can be frequent and 2). Metric step: determining if the pattern is frequent. In the literature, the generation step is usually solved by vertex or edge extension methods. These methods produce a lot of redundant candidate patterns which must be removed, and hence increasing the latency. To address these challenges, the paper introduces a vertex based merging method which reduces the redundancies, and introduces effective pruning mechanisms. Moreover, the existing metrics to determine if a pattern is frequent or not, either is highly accurate while demanding significant computational time (Maximum Independent Set (MIS)) or overestimates the pattern count while taking less time (Minimum Node Image (MNI)). Thus, the paper introduces ''Maximal Independent Set (mIS)'' metric, which minimizes latency while obtaining accuracy close to MIS, which is controlled by a pattern overlap parameter (łambda).Through extensive experimentation, our proposed method achieves an average of 10.58× speedup when compared to GraMi and an average of 3× speedup when compared to T-FSM.