Mining Association Rules from a Single Large Graph

Abstract

Knowledge mining from single graph plays an important role in decision support systems on single graphs such as social networks, bioinformatics, etc. In recent years, the problem of Frequent Subgraph Mining (FSM) from a single graph have been developed and attracted several studies. However, the problem of mining association rules or links from frequent subgraphs has not had many contributions. In this article, we state the problem of direct mining association rules from frequent subgraphs. Existing approaches on this topic perform the task in two phases. First, they traverse the search space to directly discover parent-child relationships from the discovered frequent subgraphs, then association rules are generated. We propose a one-phase algorithm, named So-GPARs, to generate rules as soon as frequent supergraphs are constructed from already existing frequent subgraphs. Our experiments on three single graph datasets show that the one-phase algorithm is more efficient than the two-phase algorithm in terms runtime of the rules generating phase.

Keywords:

• Association rule
• data mining
• frequent subgraph mining
• link mining
• single large graph

Notes

1 Source: spark.apache.org

2 Source: networkrepository.com/citeseer.php

3 Source: github.com/ehab-abdelhamid/GraMi/

4 Source: github.com/ehababdelhamid/ScaleMine/

Additional information

Funding

This work was supported by Institute for Computational Science and Technology (ICST) – Ho Chi Minh City and the Department of Science and Technology (DOST) – Ho Chi Minh City under grant no. 23/2021/HĐ-QKHCN.