An improved unique canonical labeling for frequent subgraph mining

摘要

Frequent subgraph mining is a fundamental task and widely explored in many research application domains such as computational biology, social network analysis, chemical structure analysis and web mining. The problem of frequent subgraph mining is a challenge as the number of possible subgraphs and verifying the isomorphism of the subgraphs is exponential problem. Canonical labeling is a standard approach to handle graph (subgraph) isomorphism that has high complexity and is NP-complete. In this paper we propose a systematic approach and formulate an algorithm to construct canonical label for a graph (subgraph) that uniquely identifies a graph based on the special invariant properties of graphs. Our experimental evaluation shows that this algorithm effectively addresses canonical labeling, isomorphism of graphs and reduces the computational cost.