Full duplicate candidate pruning for frequent connected subgraph mining

Article type: Research Article

Authors: Gago-Alonso, Andrés^a | Carrasco-Ochoa, Jesús A.^{b; *} | Medina-Pagola, José E.^a | Martínez-Trinidad, José Fco.^b

Affiliations: [a] Advanced Technologies Application Center, Havana, Cuba | [b] Computer Science Department, National Institute of Astrophysics, Optics and Electronics, Puebla, México

Correspondence: [*] Corresponding author: Dr. Jesús Ariel Carrasco-Ochoa, Full time researcher, National Institute of Astrophysics, Optics and Electronics, Computer Science Department, Luis Enrique Erro No. 1, Sta María Tonanzintla, Puebla, México, CP: 72840. Tel.: +52 (222) 266 31 00, ext 8311; Fax: +52 (222) 266 34 52; E-mail: ariel@inaoep.mx.

Abstract: Support calculation and duplicate detection are the most challenging and unavoidable subtasks in frequent connected subgraph (FCS) mining. The most successful FCS mining algorithms have focused on optimizing these subtasks since the existing solutions for both subtasks have high computational complexity. In this paper, we propose two novel properties that allow removing all duplicate candidates before support calculation. Besides, we introduce a fast support calculation strategy based on embedding structures. Both properties and the new embedding structure are used for designing two new algorithms: gdFil for mining all FCSs; and gdClosed for mining all closed FCSs. The experimental results show that our proposed algorithms get the best performance in comparison with other well known algorithms.

Keywords: Data mining, graph mining, frequent subgraph, labeled graph, DFS code

DOI: 10.3233/ICA-2010-0342

Journal: Integrated Computer-Aided Engineering, vol. 17, no. 3, pp. 211-225, 2010