吉林大学学报(工学版) ›› 2018, Vol. 48 ›› Issue (4): 1199-1205.doi: 10.13229/j.cnki.jdxbgxb20170600

Previous Articles     Next Articles

Measurement of graph similarity based on vertical dimension sequence dynamic time warping method

WANG Xu1,2, OUYANG Ji-hong1,2, CHEN Gui-fen3   

  1. 1.College of Computer Science and Technology, Jilin University, Changchun 130012, China;
    2.Key Laboratory of Symbolic Computation and Knowledge Engineering of Ministry of Education, Jilin University, Changchun 130012, China;
    3.College of Information Technology, Jilin Agricultural University, Changchun 130118, China
  • Received:2017-05-12 Online:2018-07-01 Published:2018-07-01

Abstract: To solve the problems of high complexity and information loss in the process of measuring graph similarity, a method to calculate the distance of vertical dimensional sequences is proposed, which is used to measure graph similarity. Using this method, the graph is converted into the generalized tree, which is regarded as the vertical dimensional sequences. This method simplifies the graph similarity measurement to the distance calculation of the sequences. The vertical dimensional sequences not only obtain labels, in-degrees and out-degrees information of vertices, reflect level structural property of vertices, but also reserve the path information of graph. Compared with the existing graph similarity methods, this method involves more graph information in the process of graph similarity measurement, and decreases the time complexity to O(n2).

Key words: artificial intelligence, graph similarity measure, dynamic time warping, vertical dimensional sequences, distance calculating, time complexity

CLC Number: 

  • TP18
[1] Ahmed A, Shervashidze N, Narayanamurthy S, et al.Distributed large-scale natural graph factorization[C]∥22nd International Conference on World Wide Web, Rio de Janeiro, Brazil,2013:37-48.
[2] Shanavas N, Wang H, Lin Z, et al.Supervised graph-based term weighting scheme for effective text classification[C]∥Proceedings of the 22nd European Conference on Artificial Intelligence, Hague, Netherlands, 2016: 1710-1711.
[3] Macropol K,Singh A.Reachability analysis and modeling of dynamic event networks[C]∥European Conference of Machine Learning and Knowledge Discovery in Databases, Bristol, UK, 2012: 442-457.
[4] Sugiyama M, Llinares F, Kasenburg N, et al.Significant subgraph mining with multiple testing correction[C]∥Proceedings of the SIAM International Conference on Data Mining, Vancouver, Canada, 2015: 37-45.
[5] Vishwanathan S, Schraudolph N, Kondor R, et al.Graph kernels[J]. Journal of Machine Learning Research, 2010, 11:1201-1242.
[6] Sugiyama M, Borgwardt K.Halting in random walk kernels[C]∥28th International Conference on Neural Information Processing Systems, Montreal, Canada, 2015: 1639-1647.
[7] Borgwardt K, Kriegel H.Shortest-path kernels on graphs[C]∥Proceedings of IEEE International Conference on Data Mining, Houston, USA, 2005: 74-81.
[8] Elzinga C, Wang H.Kernels for acyclic digraphs[J]. Pattern Recognition Letters, 2012, 33(16): 2239-2244.
[9] Forster D, Bittner L, Karkar S, et al. Testing ecological theories with sequence similarity networks: marine ciliates exhibit similar geographic dispersal patterns as multicellular organisms[J].BMC Biology, 2015, 13: doi: 10.1186/s12915-015-0125-5.
[10] Yanardag P, Vishwanathan S.A structural smoothing framework for robust graph comparison[C]∥Proceedings of Neural Information Processing Systems, Montreal, Canada, 2015: 2134-2142.
[11] Shervashidze N, Schweitzer P, Leeuwen E, et al.Weisfeiler-Lehman graph kernels[J].Journal of Machine Learning Research, 2011, 12: 2539-2561.
[12] Yanardag P, Vishwanathan S.Deep graph kernels[C]∥Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Sydney, Australia, 2015: 1365-1374.
[13] Sakoe H, Chiba S.Dynamic programming algorithm optimization for spoken word recognition[J]. IEEE Transactions on Acoustics, Speech, and Signal Processing, 1978, 26(1): 43-49.
[14] Kurbalija V, Radovanovic M, Geler Z, et al.The influence of global constraints on similarity measures for time-series databases[J].Knowledge-Based Systems, 2014, 56: 49-67.
[15] Wang Q, Korkin D, Shang Y.A fast multiple longest common subsequence(MLCS) algorithm[J].IEEE Transactions on Knowledge and Data Engineering, 2011, 23(3): 321-334.
[16] Wang H.All common subsequences[C]∥Proceeding 20th International Joint Conference on Artificial Intelligence, Hyderabad, India, 2007: 635-640.
[17] Lin Z, Wang H, McClean S. A multidimensional sequence approach to measuring tree similarity[J]. IEEE Transactions on Knowledge and Data Engineering, 2012, 24(2): 197-208.
[18] Li Tao, Dong Han, Shi Yong-tang, et al.A comparative analysis of new graph distance measures and graph edit distance[J]. Information Sciences, 2017, 403: 15-21.
[19] Zhu Gang-gao, Iglesias C.Computing semantic similarity of concepts in knowledge graphs[J]. IEEE Transactions on Knowledge and Data Engineering, 2017, 29(1): 72-85.
[1] DONG Sa, LIU Da-you, OUYANG Ruo-chuan, ZHU Yun-gang, LI Li-na. Logistic regression classification in networked data with heterophily based on second-order Markov assumption [J]. Journal of Jilin University(Engineering and Technology Edition), 2018, 48(5): 1571-1577.
[2] GU Hai-jun, TIAN Ya-qian, CUI Ying. Intelligent interactive agent for home service [J]. Journal of Jilin University(Engineering and Technology Edition), 2018, 48(5): 1578-1585.
[3] ZHANG Hao, ZHAN Meng-ping, GUO Liu-xiang, LI Zhi, LIU Yuan-ning, ZHANG Chun-he, CHANG Hao-wu, WANG Zhi-qiang. Human exogenous plant miRNA cross-kingdom regulatory modeling based on high-throughout data [J]. 吉林大学学报(工学版), 2018, 48(4): 1206-1213.
[4] HUANG Lan, JI Lin-ying, YAO Gang, ZHAI Rui-feng, BAI Tian. Construction of disease-symptom semantic net for misdiagnosis prompt [J]. 吉林大学学报(工学版), 2018, 48(3): 859-865.
[5] LI Xiong-fei, FENG Ting-ting, LUO Shi, ZHANG Xiao-li. Automatic music composition algorithm based on recurrent neural network [J]. 吉林大学学报(工学版), 2018, 48(3): 866-873.
[6] LIU Jie, ZHANG Ping, GAO Wan-fu. Feature selection method based on conditional relevance [J]. 吉林大学学报(工学版), 2018, 48(3): 874-881.
[7] WANG Xu, OUYANG Ji-hong, CHEN Gui-fen. Heuristic algorithm of all common subsequences of multiple sequences for measuring multiple graphs similarity [J]. 吉林大学学报(工学版), 2018, 48(2): 526-532.
[8] YANG Xin, XIA Si-jun, LIU Dong-xue, FEI Shu-min, HU Yin-ji. Target tracking based on improved accelerated gradient under tracking-learning-detection framework [J]. 吉林大学学报(工学版), 2018, 48(2): 533-538.
[9] LIU Xue-juan, YUAN Jia-bin, XU Juan, DUAN Bo-jia. Quantum k-means algorithm [J]. 吉林大学学报(工学版), 2018, 48(2): 539-544.
[10] QU Hui-yan, ZHAO Wei, QIN Ai-hong. A fast collision detection algorithm based on optimization operator [J]. 吉林大学学报(工学版), 2017, 47(5): 1598-1603.
[11] LI Jia-fei, SUN Xiao-yu. Clustering method for uncertain data based on spectral decomposition [J]. 吉林大学学报(工学版), 2017, 47(5): 1604-1611.
[12] SHAO Ke-yong, CHEN Feng, WANG Ting-ting, WANG Ji-chi, ZHOU Li-peng. Full state based adaptive control of fractional order chaotic system without equilibrium point [J]. 吉林大学学报(工学版), 2017, 47(4): 1225-1230.
[13] WANG Sheng-sheng, WANG Chuang-feng, GU Fang-ming. Spatio-temporal reasoning for OPRA direction relation network [J]. 吉林大学学报(工学版), 2017, 47(4): 1238-1243.
[14] MA Miao, LI Yi-bin. Multi-level image sequences and convolutional neural networks based human action recognition method [J]. 吉林大学学报(工学版), 2017, 47(4): 1244-1252.
[15] ZHOU Bing-hai, PENG Tao. Optimal schedule of just-in-time part distribution for mixed-model assembly lines [J]. 吉林大学学报(工学版), 2017, 47(4): 1253-1261.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
[1] HE Lei,ZONG Chang-fu,TIAN Cheng-wei,WU Ren-jun,Zhang Tai-wu. DC motor fault diagnosis and fault tolerance control method for steer-by-wire car[J]. 吉林大学学报(工学版), 2011, 41(03): 608 -612 .
[2] LIU Song-shan, WANG Qing-nian, WANG Wei-hua, LIN Xin. Influence of inertial mass on damping and amplitude-frequency characteristic of regenerative suspension[J]. 吉林大学学报(工学版), 2013, 43(03): 557 -563 .
[3] CHU Liang, WANG Yan-bo, QI Fu-wei, ZHANG Yong-sheng. Control method of inlet valves for brake pressure fine regulation[J]. 吉林大学学报(工学版), 2013, 43(03): 564 -570 .
[4] LI Jing, WANG Zi-han, YU Chun-xian, HAN Zuo-yue, SUN Bo-hua. Design of control system to follow vehicle state with HIL test beach[J]. 吉林大学学报(工学版), 2013, 43(03): 577 -583 .
[5] ZHU Jian-feng, LIN Yi, CHEN Xiao-kai, SHI Guo-biao. Structural topology optimization based design of automotive transmission housing structure[J]. 吉林大学学报(工学版), 2013, 43(03): 584 -589 .
[6] HU Xing-jun, LI Teng-fei, WANG Jing-yu, YANG Bo, GUO Peng, LIAO Lei. Numerical simulation of the influence of rear-end panels on the wake flow field of a heavy-duty truck[J]. 吉林大学学报(工学版), 2013, 43(03): 595 -601 .
[7] WANG Tong-jian, CHEN Jin-shi, ZHAO Feng, ZHAO Qing-bo, LIU Xin-hui, YUAN Hua-shan. Mechanical-hydraulic co-simulation and experiment of full hydraulic steering systems[J]. 吉林大学学报(工学版), 2013, 43(03): 607 -612 .
[8] ZHANG Chun-qin, JIANG Gui-yan, WU Zheng-yan. Factors influencing motor vehicle travel departure time choice behavior[J]. 吉林大学学报(工学版), 2013, 43(03): 626 -632 .
[9] MA Wan-jing, XIE Han-zhou. Integrated control of main-signal and pre-signal on approach of intersection with double stop line[J]. 吉林大学学报(工学版), 2013, 43(03): 633 -639 .
[10] YU De-xin, TONG Qian, YANG Zhao-sheng, GAO Peng. Forecast model of emergency traffic evacuation time under major disaster[J]. 吉林大学学报(工学版), 2013, 43(03): 654 -658 .