Dimensionality reduction method of graph kernel based on KLDA

doi:10.3969/j.issn.0253-2778.2016.09.006

Abstract

Abstract: Graph structure has strong expression ability and high flexibility. The identification and classification of graph structure data fall into the category of structural pattern recognition. The research idea of the graph structure data is to transform the graph structure data to the vector in the vector space, then the traditional machine learning algorithm is used to analyze the vector. Data representation and analysis based on graph structure has become a hot research topic in the field of machine learning. The classical graph kernel method was extended. The kernel linear discriminant analysis (KLDA) was employed to reduce the dimension of the high dimension feature space, and the low dimensional feature space corresponding to the original graph structure data was obtained. Then the traditional machine learning algorithm was used to analyze these new data. The effectiveness of the proposed method is verified by the experimental results on standard data sets.

Key words: graph classification, graph kernel, kernel linear discriminant analysis, dimensionality reduction

CLC Number:

TP18

YU Yajun, PAN Zhisong, HU Guyu, MO Xiaoyong, XUE Jiao. Dimensionality reduction method of graph kernel based on KLDA[J]. Journal of University of Science and Technology of China, 2016, 46(9): 749-756.

References

［1］
蒋强荣. 图核及其在模式识别中应用的研究[D]. 北京工业大学, 2011.
[2] SHARAN R, IDEKER T. Modeling cellular machinery through biological network comparison [J]. Nature Biotechnology, 2006, 24(4): 427-433.
[3] KUBINYI H. Drug research: Myths, hype and reality[J]. Nature Reviews: Drug Discovery, 2003, 2(8): 665-668.
[4] KUMAR R, NOVAK J, TOMKINS A. Structure and evolution of online social networks[A]// Link Mining: Models, Algorithms, and Applications. New York: Springer, 2010: 337-357.
[5] VISHWANATHAN S V N, SCHRAUDOLPH NN, KONDOR R, et al. Graph kernels[J]. Journal of Machine Learning Research, 2010, 11(2): 1201-1242.
[6] CONTE D, FOGGIA P, SANSONE C, et al. Thirty years of graph matching in pattern recognition[J]. International Journal of Pattern Recognition and Artificial Intelligence, 2004, 18(3): 265-298.
[7] 吴遐, 张道强. 半监督图核降维方法[J]. 计算机科学与探索, 2010, 4(7): 629-636.
[8] BORGWARDT K M, KRIEGEL H P. Shortest-path kernels on graphs[C]// Proceedings of the 5th International Conference on Data Mining. Houston: IEEE Computer Society, 2005:74-81.
[9] HORVTH T, GRTNER T, WROBEL S. Cyclic pattern kernels for predictive graph mining[C]// Proceedings of the 10th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. Seattle: ACM Press, 2004: 158-167.
[10] SHERVASHIDZE N, BORGWARDT K. Fast subtree kernels on graphs[A]// Advances in Neural Information Processing Systems. Vancouver, 2009: 1660-1668.
[11] KRAMER S, DE RAEDT L. Feature construction with version spaces for biochemical applications[C]// Proceedings of the 18th International Conference on Machine Learning. Williamstown: Morgan Kaufmann, 2001: 258-265.
[12] 吴遐. 基于约束的图核方法的研究[D]. 南京航空航天大学, 2011.
[13] MIKA S,RTSCH G, WESTON J, et al. Fisher discriminant analysis with kernels[C]// Proceedings of the Neural Networks for Signal Processing. IEEE Press, 1999: 41-48.
[14] SHERVASHIDZE N, SCHWEITZER P, VAN LEEUWEN E J, et al. Weisfeiler-lehman graph kernels[J]. Journal of Machine Learning Research, 2011, 12(9): 2539-2561.
[15] DUDA R O, HART P E, STORK D G. Pattern Classification[M]. 2ed, New York: Wiley-Interscience, 2000.
[16] SCHLKOPF B, HERBRICH R, SMOLA A J. A Generalized Representer Theorem[A]// Computational Learning Theory. Berlin Heidelberg: Springer, 2001: 416-426.
[17] HELMA C, KING R D, KRAMER S, et al. The predictive toxicology challenge[J]. Bioinformatics, 2001, 17(1): 107-108.
[18] SCHLKOPF B, SMOLA A J. Learning with Kernels[M]. Cambridge, MA: MIT Press, 2002.

()
()

[1]	Ma Yulian, Cui Wenquan. An end-to-end multitask method with two targets for high-frequency price movement prediction [J]. Journal of University of Science and Technology of China, 2021, 51(3): 246-258.
[2]	. Differential privacy protection method for deep learning based on WGAN feedback [J]. Journal of University of Science and Technology of China, 2020, 50(8): 1064-1071.
[3]	GAO Xiang, CHEN Li. Group stochastic gradient descent: A tradeoff between straggler and staleness [J]. Journal of University of Science and Technology of China, 2020, 50(8): 1156-1161.
[4]	. UAV target tracking based on visual attention mechanism [J]. Journal of University of Science and Technology of China, 2020, 50(8): 1162-1169.
[5]	WANG Yue, LI Jing. Research on optimization method of convolutional neural network based on visualization [J]. Journal of University of Science and Technology of China, 2020, 50(7): 959-967.
[6]	. Focused loss-based for imbalanced data scenarios integrated classification methods for CGAN [J]. Journal of University of Science and Technology of China, 2020, 50(7): 968-976.
[7]	ZHANG Yikai, PENG Yong, KONG Wanzeng, WEN Yimin. Fuzzy local coordinate concept factorization with graph regularization [J]. Journal of University of Science and Technology of China, 2020, 50(7): 993-1002.
[8]	SU Shoubao, CHEN Qiuxin, WANG Chishe, LI Zhi. Adaptive fractional order particle swarm optimization using swarm activity feedback and mutation operator [J]. Journal of University of Science and Technology of China, 2020, 50(7): 1026-1034.
[9]	SHI Lukui, GUO Linlin, FANG Zizhe, ZHANG Jun. Parallel ISOMAP algorithm based on Spark [J]. Journal of University of Science and Technology of China, 2019, 49(10): 842-850.
[10]	ZHANG Huimin, YANG Ming, LV Jing. Multifeature hyperspectral image classification based on adaptive kernel joint sparse representation [J]. Journal of University of Science and Technology of China, 2018, 48(4): 298-306.
[11]	RAO Qi, YANG Yan*, TENG Fei. Condition recognition of high-speed train based on multi-view weighted clustering ensemble [J]. Journal of University of Science and Technology of China, 2018, 48(1): 35-41.
[12]	ZHANG Hao, WU Jianxin,. Ensemble max-pooling: Is only the maximum activation useful when pooling [J]. Journal of University of Science and Technology of China, 2017, 47(10): 799-807.
[13]	SHI Lukui, YUAN Bin, LIU Wenhao. Parallel ISOMAP algorithm based on Spark [J]. Journal of University of Science and Technology of China, 2016, 46(9): 711-718.
[14]	QUAN Xin, GU Yuanhua, ZHENG Guansheng, GU Bin. An incremental cost-sensitive support vector machine [J]. Journal of University of Science and Technology of China, 2016, 46(9): 727-735.
[15]	LAI Yuecong, HUANG Tianqiang, LIN Jing. A fast algorithm of image moments in copy-move forgery detection [J]. Journal of University of Science and Technology of China, 2016, 46(9): 743-748.