Attributed graph mining in the presence of automorphism

作     者：Pasquier, Claude Flouvat, Frederic Sanhes, Jeremy Selmaoui-Folcher, Nazha 

作者机构：Univ Nice Sophia Antipolis I3S UMR 7271 F-06900 Sophia Antipolis France CNRS I3S UMR 7271 F-06900 Sophia Antipolis France Univ New Caledonia Multidisciplinary Res Team Mat & Environm PPME Noumea 98851 New Caledonia 

出 版 物：《KNOWLEDGE AND INFORMATION SYSTEMS》 (知识和信息系统季刊)

年 卷 期：2017年第50卷第2期

页      面：569-584页

核心收录：

学科分类：0711[理学-系统科学] 07[理学] 08[工学] 070105[理学-运筹学与控制论] 081101[工学-控制理论与控制工程] 0701[理学-数学] 071101[理学-系统理论] 0811[工学-控制科学与工程] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：ANR ["FOSTER" ANR-2010-COSI-012-01] 

主　　题：Attributed graph Frequent pattern mining Automorphism Structure mining Itemset mining 

摘      要：Attributed directed graphs are directed graphs in which nodes are associated with sets of attributes. Many data from the real world can be naturally represented by this type of structure, but few algorithms are able to directly handle these complex graphs. Mining attributed graphs is a difficult task because it requires combining the exploration of the graph structure with the identification of frequent itemsets. In addition, due to the combinatorics on itemsets, subgraph isomorphisms (which have a significant impact on performances) are much more numerous than in labeled graphs. In this paper, we present a new data mining method that can extract frequent patterns from one or more directed attributed graphs. We show how to reduce the combinatorial explosion induced by subgraph isomorphisms thanks to an appropriate processing of automorphic patterns.