An efficient heuristic approach for learning a set of composite graph classification rules

Article type: Research Article

Authors: Nguyen, Viet Anh^* | Nguyen, Long Giang

Affiliations: Institute of Information Technology, Vietnam Academy of Science and Technology, Hanoi, Vietnam

Correspondence: [*] Corresponding author: Viet Anh Nguyen, Institute of Information Technology, Vietnam Academy of Science and Technology, 18 Hoang Quoc Viet, Hanoi, Vietnam. Tel.: +84 917626028; E-mail: anhnv@ioit.ac.vn.

Abstract: We propose in this paper an efficient heuristic method to learn a set of classification rules from a set of graph objects. Graph classification has various real-life applications, however, this is a very challenging problem due to the intrinsic complex structure of graphs. The proposed rule constructing method is based on two lines of research. The first line of research is on Boosting [11] in which a weak-hypothesis is regarded as a rule and is assigned with a real-valued confidence. In our research, a rule is comprised by a set of subgraphs that maximize an objective function in each round of boosting. The second line of research is on utilizing the poset order of the Formal Concept Lattice of subgraphs to accelerate the process of generating rule candidates. The learned rule set is compact, comprehensible and obtains high classification accuracy on tested datasets.

Keywords: Graph classification, formal concept analysis, confidence-rated boosting, approximation method

DOI: 10.3233/IDA-163343

Journal: Intelligent Data Analysis, vol. 22, no. 3, pp. 581-596, 2018