Utility-driven free tree mining in graph databases

Frequent subgraph mining is a fundamental task in data mining, widely applied in various domains such as biological networks, social networks, and computing networks. However, existing methods for frequent subgraph mining often rely solely on support as a single metric, considering subgraphs with higher support as more important. This approach overlooks the intrinsic value of subgraphs, such as in citation networks, where users tend to associate with structures related to their own research areas, not only the frequent ones. To address this limitation, we introduce utility pattern mining into the field of subgraph mining. This mining framework considers both the internal and external values of patterns. Additionally, traditional frequent subgraph mining is hindered by isomorphism calculations, including the computational cost of subgraph isomorphism, which is NP-complete. As a connected acyclic graph, free trees play a significant role in fields such as web mining and biology. Their relatively simple structure can significantly reduce the computational cost of subgraph isomorphism calculations. In this paper, we combine utility pattern mining with frequent free tree mining, defining the problem of frequent high utility free tree mining. We design utility upper bounds that satisfy the downward closure property and propose an algorithm, UFTM (utility free tree miner), for effectively and efficiently mining utility free trees. Furthermore, we collect and test our algorithm on four real-world datasets. The results demonstrate that UFTM can discover more valuable patterns and execute the mining task efficiently.