A spanning hypertree theory for support measures in single graphs

Graph mining has become popular for discovering valuable information as graph databases grow. Two primary challenges in graph mining within large-scale graph databases include designing effective support measures and managing computational resource costs. Specifically, it is difficult to achieve a balance between fast runtime, low memory consumption, and practical support because of issues such as isomorphism and overlap. This paper focuses on frequent pattern extraction and mining optimization in single graphs. We introduce a novel spanning hypertree framework that unifies support measures and elucidates the interrelationships among four measures: maximum independent edge set (MIES), minimum vertex cover (MVC), minimum instance (MI), and minimum-image-based (MNI). Within this framework, we preserve vertex information for pattern extension while reducing redundancy from hyperedges covering the same vertices, thereby improving search efficiency. Although MIES and MVC are NP-hard in hypergraphs, we prove that MIES is polynomial-time solvable in the spanning hypertree setting and that MVC admits a polynomial-time linear programming relaxation. We show that support measures hold the anti-monotonicity property in this framework and establish bounding theorems between hypergraphs and spanning hypertree. Experiments demonstrate that the hypertrees framework significantly outperforms the hypergraph framework in runtime and memory usage, especially for MVC.