关键词: 图挖掘, 图分类, 子图模式, 区分子图, 多样性

Abstract: Discriminative subgraph can be used to characterize complex graph structures and construct efficient graph classification model. This paper proposes the Top-K discriminative subgraph mining problem based on diversity measure. The diversity measure can be used to mine low correlation subgraph patterns in the mining result, which can enhance the usefulness of the discriminative subgraph patterns. By exploiting the graph structure similarity and support set similarity restraints, this paper introduces the criterion of graph pattern diversity measure. Then this paper proposes two efficient algorithms, Greedy-TopK and Leap-TopK, for the problem. Greedy-TopK algorithm employs two step strategies to incrementally and greedily mine K discriminative subgraphs. By limiting the structure similarity graph pattern extension in the discriminative subgraph mining process, Leap-TopK algorithm can leap the graph pattern searching space. Extensive experimental results demonstrate that Leap-TopK algorithm is more efficient than Greedy-TopK algorithm. Besides, when the mining results of discriminative subgraphs are considered, the classification accuracies of the two algorithms are almost the same. But they are all superior to the traditional discriminative subgraph mining algorithm in terms of usefulness.

Key words: graph mining, graph classification, subgraph pattern, discriminative subgraph, diversity