Graph-based substructure pattern mining with edge-weight

doi:10.1007/s10489-024-05356-7

2024-03-08

PRE

Md. Ashraful Islam *

Chowdhury Farhan Ahmed

Md. Tanvir Alam

Carson K. Leung

DOI：10.1007/s10489-024-05356-7

原文链接

原文求助

摘要

En 中文

To represent complex inter-relationships among entities, weighted graphs are more useful than their unweighted counterparts. In a transactional graph setting, researchers have made several attempts to mine weighted frequent subgraphs from a collection of edge-weighted graphs, which will serve as the representative feature of the underlying graph database and can be further used for analysis. As weighted support of any pattern does not hold downward closure property, a property that is often used in frequent pattern mining to control search space, has made weighted frequent substructure mining a tremendously difficult task. This article proposes an efficient weighted frequent subgraph mining framework called WFSM-MaxPWS for graphs with static edge weights. We introduce a new pruning technique called MaxPWS pruning along with canonical labeling of subgraphs, which helps reduce the search space significantly without compromising completeness. Extending the WFSM-MaxPWS framework, we propose another framework called DewgSpan that is capable of mining graphs with dynamic edge weight. DewgSpan utilizes a summarized edge-weight distribution table to overcome the new challenges of dynamic edge-weight settings. Evaluation results show that WFSM-MaxPWS and DewgSpan are significantly faster than the existing MaxW pruning technique of weighted pattern mining.

Keyword:

Data mining

Pattern mining

Substructure mining

Weighted subgraph