Abstract
<title>Abstract</title> <p>Weighted frequent subgraph mining over transactional multigraph databases must prune by frequency and by edge weight at once. Every algorithm proposed to date for this setting inherits the gSpan framework and with it an embedding-store strategy: each pattern carries the full list of its embeddings and is extended incrementally from its parent’s list. This is fast, but peak memory grows with the number of embeddings and blows up exactly at the low thresholds and large databases that users need most. This paper proposes Pivot-WFSM, which discards the embedding store altogether and replaces it with on-demand re-matching: no pattern stores embeddings; each candidate is tested for existence only when needed, by adopting the known pivot-anchored matching primitivefrom subgraph isomorphism, with the pivot chosen from the pattern’s own structure and data vertices pruned by a local signature. Memory then scales with the single embedding being probed rather than with the whole embedding set. The substitution is proved to preserve soundness and completeness, including the edge injectivity that multigraphs require. On four standard datasets under twoweight distributions, Pivot-WFSM cuts peak live heap by 12–68 times while returning the same pattern set, and is 2.5–10 times faster at selective thresholds, though 1.9–4.3 times slower at very low ones. On the entire Yeast database of 79,601 graphs under an 8 GB heap, the embedding store runs out of memory while Pivot-WFSM completes with about 1 GB, so memory decides feasibility at this scale.</p>