SATMargin: Practical Maximal Frequent Subgraph Mining via Margin Space Sampling

• DOI: 10.1145/3485447.3512196
• Publication Date: 2022-04-25T01:11:23Z
• Authors: Muyi Liu; Pan Li
• Keywords: Boolean satisfiability problem; Subgraph isomorphism problem; Satisfiability

Maximal Frequent Subgraph (MFS) mining asks to identify the maximal subgraph that commonly appears in a set of graphs, which has been found valuable many applications social science, biology, and other domains. Previous studies focused on reducing search space MFSs discovered theoretically smallest space. Despite success theory, no practical algorithm can exhaustively as it is huge even for small graphs with only tens nodes hundreds edges. Moreover, deciding whether an MFS needs solve monomorphism (SM), NP-complete problem introduces extra challenges. Here, we propose targets large MFSs, named SATMargin. SATMargin adopts random walk perform efficient utilizes customized conflict learning Boolean Satisfiability (SAT) accelerate SM queries. We design mechanism reuses SAT solutions combine solver effectively. evaluate over synthetic 6 real-world graph datasets. shows superior performance baselines finding more larger MFSs. further demonstrate effectiveness case study RNA graphs. The identified frequent by well matches functional core structure RNAs previously detected biological experiments. Our software be at https://github.com/MuyiLiu2022/SATMargin-and-Baselines.