MDS-FSM: Coverage-Based Frequent Subgraph Mining in Single Graphs

Frequent subgraph mining (FSM) in a single large graph remains challenging because pervasive embedding overlap exposes a gap between rigor and tractability: MIS-style supports enforce strict deduplication but are NP-hard and enumeration-dependent, whereas MNI-style supports are polynomial-time yet systematically inflate frequency under distributed overlap.We propose Minimum Density Support (MDS), a coverage-based measure that minimizes coverage density over vertex subsets, uniformly penalizes redundant overlap, and preserves anti-monotonicity. MDS is theoretically bounded between MIS and MNI and can be computed in polynomial time via submodular minimization. We further develop MDS-FSM with orbit compression, separability, and progressive bound tightening to avoid exhaustive embedding enumeration. Experiments on six real graphs show that MDS reduces overestimation and cross-topology estimation bias while scaling to million-node graphs.