单图中的近似频繁子图挖掘算法

doi:10.3969/j.issn.1000-5641.2019.06.008

华东师范大学学报(自然科学版) ›› 2019, Vol. 2019 ›› Issue (6): 73-87.doi: 10.3969/j.issn.1000-5641.2019.06.008

单图中的近似频繁子图挖掘算法

窦建凯¹, 林欣¹, 胡文心²

1. 华东师范大学计算机科学与技术系, 上海 200062;
2. 华东师范大学计算中心, 上海 200062

收稿日期:2018-12-21 出版日期:2019-11-25 发布日期:2019-11-26
通讯作者: 胡文心,女,高级工程师,硕士生导师,研究方向为计算机科学.E-mail:wxhu@cc.ecnu.edu.cn. E-mail:wxhu@cc.ecnu.edu.cn
作者简介:窦建凯,男,硕士研究生,研究方向为频繁图挖掘.E-mail:yirandjk@163.com.

Algorithm for mining approximate frequent subgraphs in a single graph

DOU Jian-kai¹, LIN Xin¹, HU Wen-xin²

1. Department of Computer Science and Technology, East China Normal University, Shanghai 200062, China;
2. Computer Center, East China Normal University, Shanghai 200062, China

Received:2018-12-21 Online:2019-11-25 Published:2019-11-26

摘要/Abstract

摘要： 图数据的挖掘工作是数据挖掘工作中的重要组成部分，已经有许多人在这个领域进行了深入的研究.由于数据获取不可避免噪音数据，故在挖掘频繁图时考虑近似十分重要.然而许多此前的工作只考虑了子图间编辑距离（Graph Edit Distance，GED）的绝对值，而没有考虑子图间编辑距离与子图大小的相对关系.提出了一种在单图中进行近似频繁子图挖掘的新算法，并在计算近似程度时考虑当前子图的大小.该算法通过对近似频繁子图的大小上限进行预测，并通过局部反单调性进行剪枝，提高了算法的效率.实验表明，该算法能够挖掘出传统算法无法发现的近似频繁子图，且相比对比算法具有更好的时间性能.

关键词: 近似, 图, 频繁子图挖掘, 剪枝

Abstract: Graph mining is an important part of data mining, and significant research has been dedicated to the field. Due to the inevitability of noise during data acquisition, it is crucial to address the issue of approximation in mining frequent subgraphs. Previous work has only considered the absolute value of the graph edit distance (GED); however, the relative value between the GED and the size of the subgraph should also be considered. Hence, in this paper, we propose a novel algorithm to mine approximate frequent subgraphs in a single graph; this algortihm takes into account the size of current subgraphs for the calculation of approximations. We increase the efficiency of this algorithm by estimating the upper bound of frequent subgraphs, and pruning according to local anti-monotonicity. Experimental results show that this algorithm can find subgraphs that are missed by traditional mining algorithms, and our proposed approach is relatively efficent compared to other algorithms.

Key words: approximate, graph, frequent subgraph mining, pruning

中图分类号:

TP391.4

窦建凯, 林欣, 胡文心. 单图中的近似频繁子图挖掘算法[J]. 华东师范大学学报(自然科学版), 2019, 2019(6): 73-87.

DOU Jian-kai, LIN Xin, HU Wen-xin. Algorithm for mining approximate frequent subgraphs in a single graph[J]. Journal of East China Normal University(Natural Sc, 2019, 2019(6): 73-87.

参考文献

[1] YAN X F, HAN J W. gSpan:Graph-based substructure pattern mining[C]//Proceedings of the 2002 IEEE International Conference on Data Mining. 2002:721-724.
[2] ELSEIDY M, ABDELHAMID E, SKIADOPOULOS S, et al. GraMi:Frequent subgraph and pattern mining in a single large graph[J]. Proceedings of the VLDB Endowment, 2014, 7:517-528.
[3] CHEN C, YAN X F, ZHU F D, et al. gApprox:Mining frequent approximate patterns from a massive network[C]//7th IEEE International Conference on Data Mining. 2007:445-450.
[4] FLORES-GARRIDO M, CARRASCO-OCHOA J A, MARTÍNEZ-TRINIDAD J F. AGraP:An algorithm for mining frequent patterns in a single graph using inexact matching[J]. Knowledge and Information Systems, 2015,2(44):385-406.
[5] KURAMOCHI M, KARYPIS G. Finding frequent patterns in a large sparse graph[J]. Data Mining and Knowledge Discovery, 2005, 11(3):243-271.
[6] NIJSSEN S, KOK J N. A quickstart in frequent structure mining can make a difference[C]//Proceedings of the 10th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2004:647-652.
[7] ALONSO A G, PAGOLA J E M, CARRASCO-OCHOA J A, et al. Mining frequent connected subgraphs reducing the number of candidates[C]//Joint European Conference on Machine Learning and Knowledge Discovery in Databases. 2008:365-376.
[8] RANU S, SINGH A K. Graphsig:A scalable approach to mining significant subgraphs in large graph databases[C]//2009 IEEE 25th International Conference on Data Engineering. 2009:844-855.
[9] CHENG H, YAN X F, HAN J W. Mining graph patterns[C]//Frequent Pattern Mining, Berlin:Springer, 2014:307-338.
[10] KRISHNA V, SURI N R, ATHITHAN G. A comparative survey of algorithms for frequent subgraph discovery[J]. Current Science, 2011,:190-198.
[11] CHOUDHURY S, PUROHIT S, LIN P, et al. Percolator:Scalable pattern discovery in dynamic graphs[C]//Proceedings of the 11th ACM International Conference on Web Search and Data Mining. 2018:759-762.
[12] INGALALLI V, IENCO D, PONCELET P. Mining frequent subgraphs in multigraphs[J]. Information Sciences, 2018, 451/452:50-66.
[13] ALGULIEV R M, ALIGULIYEV R M, GANJALIYEV F S. Extracting a heterogeneous social network of academic researchers on the Web based on information retrieved from multiple sources[J]. American Journal of Operations Research, 2011, 1(2):33.
[14] LIMA JR D P, GIACOMINI H C, TAKEMOTO R M, et al. Patterns of interactions of a large fish-parasite network in a tropical floodplain[J]. Journal of Animal Ecology, 2012, 81(4):905-913..
[15] GAO X B, XIAO B, TAO D C, et al. A survey of graph edit distance[J]. Pattern Analysis and Applications, 2010, 13(1):113-129.
[16] HIDOVIĆ D, PELILLO M. Metrics for attributed graphs based on the maximal similarity common subgraph[J]. International Journal of Pattern Recognition and Artificial Intelligence, 2004, 18(3):299-313.
[17] DEHMER M, EMMERT-STREIB F. Comparing large graphs efficiently by margins of feature vectors[J]. Applied Mathematics and Computation, 2007, 188(2):1699-1710.
[18] HOLDER L B, COOK D J, DJOKO S. Substucture discovery in the SUBDUE system[C]//KDD Workshop, 1994:169-180.
[19] JIA Y, ZHANG J T, HUAN J. An efficient graph-mining method for complicated and noisy data with real-world applications[J]. Knowledge and Information Systems, 2011, 28(2):423-447.
[20] FLORES-GARRIDO M, CARRASCO-OCHOA J A, MARTÍNEZ-TRINIDAD J F. Extensions to AGraP algorithm for finding a reduced set of inexact graph patterns[J]. International Journal of Pattern Recognition and Artificial Intelligence, 2018, 32(1):1860012.
[21] ACOSTA-MENDOZA N, GAGO-ALONSO A, CARRASCO-OCHOA J A, et al. Extension of canonical adjacency matrices for frequent approximate subgraph mining on multi-graph collections[J]. International Journal of Pattern Recognition and Artificial Intelligence, 2017, 31(8):1750025.
[22] ACOSTA-MENDOZA N, MORALES-GONZáLEZ A, GAGO-ALONSO A, et al. Image classification using frequent approximate subgraphs[C]//Iberoamerican Congress on Pattern Recognition. 2012:292-299.
[23] ACOSTA-MENDOZA N, CARRASCO-OCHOA J A, MARTÍNEZ-TRINIDAD J F, et al. Image clustering based on frequent approximate subgraph mining[C]//Mexican Conference on Pattern Recognition. 2018:189-198.

单图中的近似频繁子图挖掘算法

Algorithm for mining approximate frequent subgraphs in a single graph

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价

[1]	任韩, 吴昊. 图的空间理论：与图有关的线性代数理论（下）[J]. 华东师范大学学报(自然科学版), 20120, 2012(6): 139-156.
[2]	张悦, 田秀霞, 颜赟成, 卢官宇. 一种基于分级策略的电力营销大数据访问控制方案[J]. 华东师范大学学报（自然科学版）, 2021, 2021(5): 169-184.
[3]	付瑞, 李剑宇, 王笳辉, 岳昆, 胡矿. 面向领域知识图谱的实体关系联合抽取[J]. 华东师范大学学报（自然科学版）, 2021, 2021(5): 24-36.
[4]	刘天弼, 冯瑞. 一种基于先验标记特征的精准图像配准算法[J]. 华东师范大学学报（自然科学版）, 2021, 2021(3): 65-77.
[5]	王琼, 吴宾, 姚申君, 吴健平, 周颖, 张静. 城市绿地演化轨迹与变化研究——以上海市外环以内区域为例[J]. 华东师范大学学报（自然科学版）, 2021, 2021(2): 100-109.
[6]	MOGHITHNada. 中国图书在埃及的翻译回顾[J]. 华东师范大学学报（自然科学版）, 2020, 2020(S1): 6-10.
[7]	陈祥恩, 杨伟光. 完全二部图K_{9, n} (93 ≤ n ≤ 216)的点可区别E-全染色[J]. 华东师范大学学报（自然科学版）, 2020, 2020(6): 24-29.
[8]	林晓勤, 毛敏, 宫玲玲, 吉理. 基于语音比对的远程面试身份认证[J]. 华东师范大学学报（自然科学版）, 2020, 2020(6): 164-171.
[9]	张驯, 白万荣, 魏峰, 王蓉, 田秀霞, 刘天顺. 云存储中基于MHT的电力设备图像完整性审计方案[J]. 华东师范大学学报（自然科学版）, 2020, 2020(5): 33-43.
[10]	王俊豪, 罗轶凤. 通过细粒度的语义特征与Transformer丰富图像描述[J]. 华东师范大学学报（自然科学版）, 2020, 2020(5): 56-67.
[11]	赖叶静, 郝珊锋, 黄定江. 深度神经网络模型压缩方法与进展[J]. 华东师范大学学报（自然科学版）, 2020, 2020(5): 68-82.
[12]	王嘉宁, 何怡, 朱仁煜, 刘婷婷, 高明. 基于远程监督的关系抽取技术[J]. 华东师范大学学报（自然科学版）, 2020, 2020(5): 113-130.
[13]	李静云, 任韩. 关于Hamilton图的新的圈结构定理[J]. 华东师范大学学报（自然科学版）, 2020, 2020(4): 45-50.
[14]	徐正则, 张文俊. 基于深度图像预旋转的手势估计改进方法[J]. 华东师范大学学报（自然科学版）, 2020, 2020(4): 124-133.
[15]	牟亚蓉, 刘信生, 姚兵. 基于含圈非连通图优美性的拓扑图密码[J]. 华东师范大学学报（自然科学版）, 2020, 2020(1): 51-57.