1. MIIT Key Laboratory of Pattern Analysis and Machine Intelligence, College of Computer Science and Technology, Nanjing University of Aeronautics and Astronautics, Nanjing 211100
Abstract：In the existing graph kernels, local attributes of graphs are concerned and local topological features are utilized to compute the similarity measurement of graphs. However, hierarchical structure information of the graph is ignored. To handle this problem, optimal transport based hierarchical graph kernel is proposed. Firstly, each graph is represented as a hierarchical graph structure. During the constructive process of hierarchical graph structure, K-means clustering algorithm is employed to construct new nodes and probabilities of connections between new nodes is regarded as edges of graph at each layer. Then, the optimal transport distance between paired graphs in the special hierarchical structure is calculated using optimal transport with entropic constraints. Finally, the optimal transport distance based hierarchical graph kernel is calculated. The experimental results on six graph datasets show that the classification performance is significantly improved by the proposed graph kernel.
[1] YOU J X, LIU B W, YING R, et al.Graph Convolutional Policy Network for Goal-Directed Molecular Graph Generation // Proc of the 32nd International Conference on Neural Information Processing Systems. Cambridge, USA: The MIT Press, 2018: 6412-6422. [2] XUE J L, YANG Z, YANG X Y, et al. VoteTrust: Leveraging Friend Invitation Graph to Defend against Social Network Sybils // Proc of IEEE INFOCOM. Washington, USA: IEEE, 2013: 2400-2408. [3] LEYDESDORFF L, WAGNER C S, BORNMANN L.Betweenness and Diversity in Journal Citation Networks as Measures of Interdisciplinarity-A Tribute to Eugene Garfield. Scientometrics, 2018, 114: 567-592. [4] LYNALL M E, BASSETT D S, KERWIN R, et al. Functional Connectivity and Brain Networks in Schizophrenia. The Journal of Neuroscience, 2010, 30(28): 9477-9487. [5] CHEN B, AKSHITA J, HAN P F, et al. Aberrancies of Brain Network Structures in Patients with Anosmia. Brain Topography, 2020, 33(3): 403-411. [6] VISHWANATHAN S V N, SCHRAUDOLPH N N, KONDOR R, et al. Graph Kernels. Journal of Machine Learning Research, 2010, 11(40): 1201-1242. [7] BORGWARDT K M, KRIEGEL H P.Shortest-Path Kernels on Graphs // Proc of the 5th IEEE International Conference on Data Mining. Washington, USA: IEEE, 2005. DOI: 10.1109/ICDM.2005.132. [8] TAMAS H, THOMAS G S W. Cyclic Pattern Kernels for Predictive Graph Mining // Proc of the 10th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York, USA: ACM, 2004: 158-167. [9] KASHIMA H, TSUDA K, INOKUCHI A.Marginalized Kernels between Labeled Graphs// Proc of the 20th International Conference on Machine Learning.New York, USA: ACM, 2003: 321-328. [10] ZHANG Z, WANG M Z, XIANG Y J, et al.RetGk: Graph Kernels Based on Return Probabilities of Random Walks // Proc of the 32nd International Conference on Neural Information Processing Systems.Cambridge, USA: The MIT Press, 2018: 3964-3974. [11] MAHÉ P, VERT J P.Graph Kernels Based on Tree Patterns for Molecules. Machine Learning, 2009, 75: 3-35. [12] SHERVASHIDZE N, SCHWEITZER P, VAN LEEUWEN E J, et al. Weisfeiler-Lehman Graph Kernels. Journal of Machine Lear-ning Research, 2011, 12: 2539-2561. [13] NIKOLENTZOS G, MELADIANOS P, VAZIRGIANNIS M..Ma-tching Node Embeddings for Graph Similarity // Proc of the 31st AAAI Conference on Artificial Intelligence. Palo Alto, USA: AAAI Press, 2017: 2429-2435. [14] LIU J, LI M, LAN W, et al. Classification of Alzheimer's Disease Using Whole Brain Hierarchical Network. IEEE/ACM Transactions on Computational Biology and Bioinformatics, 2018, 15(2): 624-632. [15] MOUSAVI S F, SAFAYANI M, MIRZAEI A, et al. Hierarchical Graph Embedding in Vector Space by Graph Pyramid. Pattern Recognition, 2017, 61: 245-254. [16] FIGALLI A.Optimal Transport: Old and New. Berlin, Germany: Springer, 2009. [17] TOGNINALLI M, GHISU E, LLINARES-LOPEZ F, et al.Wasser-stein Weisfeiler-Lehman Graph Kernels // Proc of the 33rd International Conference on Neural Information Processing Systems. Cambridge, USA: The MIT Press, 2019: 6439-6449. [18] JAYASUMANA S, HARTLEY R, SALZMANN M, et al. Kernel Methods on Riemannian Manifolds with Gaussian RBF Kernels. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2015, 37(12): 2464-2477. [19] KOLOURI S, ZOU Y, ROHDE G K.Sliced Wasserstein Kernels for Probability Distributions // Proc of the IEEE Conference on Computer Vision and Pattern Recognition. Washington, USA: IEEE, 2016: 5258-5267. [20] HESPANHA J P.An Efficient MATLAB Algorithm for Graph Partitioning[C/OL]. [2021-03-15].https://web.ece.ucsb.edu/~hespanha/published/tr-ell-gp.pdf. [21] CUTURI M.Sinkhorn Distances: Lightspeed Computation of Optimal Transportation Distances // BURGES C J C, BOTTOU L, WELLING M, et al., eds. Advances in Neural Information Processing Systems 26. Cambridge, USA: The MIT Press, 2013: 2292-2300. [22] JOHANSSON F D, DUBHASHI D.Learning with Similarity Functions on Graphs using Matchings of Geometric Embeddings // Proc of the 21st ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York, USA: ACM, 2015: 467-476. [23] SHERVASHIDZE N, VISHWANATHAN S V N, PETRI T H, et al. Efficient Graphlet Kernels for Large Graph Comparison // Proc of the 20th International Conference on Artificial Intelligence and Statistics. New York, USA: ACM, 2009: 488-495. [24] FERAGEN A, KASENBURG N, PETERSEN J, et al.Scalable Kernels for Graphs with Continuous Attributes // BURGES C J C, BOTTOU L, WELLING M, et al., eds. Advances in Neural Information Processing Systems 26. Cambridge, USA: The MIT Press,2013: 216-224.
2021, Vol. 34 
