KENN: 线性结构熵的图核神经网络
作者:
基金项目:

国家自然科学基金(62176085,62172458);国家自然科学基金区域(安徽)联合基金(U20A20229)


KENN: Graph Kernel Neural Network Based on Linear Structural Entropy
Author:
  • 摘要
  • | |
  • 访问统计
  • |
  • 参考文献 [48]
  • |
  • 相似文献 [20]
  • | | |
  • 文章评论
    摘要:

    图神经网络(graph neural network, GNN)是一种利用深度学习直接对图结构数据进行表征的框架, 近年来受到人们越来越多的关注. 然而传统的基于消息传递聚合的图神经网络(messaging passing GNN, MP-GNN)忽略了不同节点的平滑速度, 无差别地聚合了邻居信息, 易造成过平滑现象. 为此, 研究并提出一种线性结构熵的图核神经网络分类方法, 即KENN. 它首先利用图核方法对节点子图进行结构编码, 判断子图之间的同构性, 进而利用同构系数来定义不同邻居间的平滑系数. 其次基于低复杂度的线性结构熵提取图的结构信息, 加深和丰富图数据的结构表达能力. 通过将线性结构熵、图核和图神经网络三者进行深度融合提出了图核神经网络分类方法. 它不仅可以解决生物分子数据节点特征的稀疏问题, 也可以解决社交网络数据以节点度作为特征所产生的信息冗余问题, 同时还使得图神经网络能够自适应调整对图结构特征的表征能力, 使其超越MP-GNN的上界(WL测试). 最后, 在7个公开的图分类数据集上实验验证了所提出模型的性能优于其他的基准模型.

    Abstract:

    Graph neural network (GNN) is a framework for directly characterizing graph structured data by deep learning, and has caught increasing attention in recent years. However, the traditional GNN based on message passing aggregation (MP-GNN) ignores the smoothing speed of different nodes and aggregates the neighbor information indiscriminately, which is prone to the over-smoothing phenomenon. Thus, this study proposes a graph kernel neural network classification method KENN based on linear structural entropy. KENN firstly adopts the graph kernel method to encode node subgraph structure, determines isomorphism among subgraphs, and then utilizes the isomorphism coefficient to define the smoothing coefficient among different neighbors. Secondly, it extracts the graph structural information based on the low-complexity linear structural entropy to deepen and enrich the structural expression capability of the graph data. This study puts forward a graph kernel neural network classification method by deeply integrating linear structural entropy, graph kernel and GNN, which can solve the sparse node features of biomolecular data and information redundancy generated by leveraging node degree as features in social network data. It also enables the GNN to adaptively adjust its ability to characterize the graph structural features and makes GNN beyond the upper bound of MP-GNN (WL test). Finally, experiments on seven public graph classification datasets verify that the proposed model outperforms other benchmark models.

    参考文献
    [1] Ou MD, Cui P, Pei J, Zhang ZW, Zhu WW. Asymmetric transitivity preserving graph embedding. In:Proc. of the 22nd ACM SIGKDD Int'l Conf. on Knowledge Discovery and Data Mining. San Francisco:ACM, 2016. 1105-1114.
    [2] Xu LX, Bai L, Xiao J, Liu Q, Chen EH, Wang XF, Tang YY. Multiple graph kernel learning based on GMDH-type neural network. Information Fusion, 2021, 66:100-110.
    [3] Bai L, Zhang ZH, Wang CY, Bai X, Hancock ER. A graph kernel based on the Jensen-Shannon representation alignment. In:Proc. of the 24th Int'l Conf. on Artificial Intelligence. Buenos Aires:AAAI Press, 2015. 3322-3328.
    [4] Zhang XY, Zou JH, He KM, Sun J. Accelerating very deep convolutional networks for classification and detection. IEEE Trans. on Pattern Analysis and Machine Intelligence, 2016, 38(10):1943-1955.
    [5] Dong C, Loy CC, He KM, Tang XO. Image super-resolution using deep convolutional networks. IEEE Trans. on Pattern Analysis and Machine Intelligence, 2016, 38(2):295-307.
    [6] You JX, Ying R, Leskovec J. Position-aware graph neural networks. In:Proc. of the 36th Int'l Conf. on Machine Learning. Long Beach:JMLR.org, 2019. 7134-7143.
    [7] Wijesinghe WOK, Wang Q. DFNets:Spectral CNNs for graphs with feedback-looped filters. In:Proc. of the 33rd Int'l Conf. on Neural Information Processing Systems. Vancouver:Curran Associates Inc., 2019. 6009-6020.
    [8] Bianchi FM, Grattarola D, Alippi C. Spectral clustering with graph neural networks for graph pooling. In:Proc. of the 37th Int'l Conf. on Machine Learning. Online:JMLR.org, 2020. 874-883.
    [9] 刘鹏举, 李好洋, 王天一, 刘欢, 孙路明, 任逸飞, 李翠平, 陈红. 基于谱聚类的在线数据库垂直分区多阶段生成方法. 软件学报, 2023, 34(6):2804-2832. http://www.jos.org.cn/1000-9825/6496.htm
    Liu PJ, Li HY, Wang TY, Liu H, Sun LM, Ren YF, Li CP, Chen H. Multi-stage method for online vertical data partitioning based on spectral clustering. Ruan Jian Xue Bao/Journal of Software, 2023, 34(6):2804-2832 (in Chinese with English abstract). http://www.jos.org.cn/1000-9825/6496.htm
    [10] 周纯英, 曾诚, 何鹏, 张龑. GKCI:改进的基于图神经网络的关键类识别方法. 软件学报, 2023, 34(6):2509-2525. http://www.jos.org.cn/1000-9825/6846.htm
    Zhou CY, Zeng C, He P, Zhang Y. GKCI:An improved GNN-based key class identification method. Ruan Jian Xue Bao/Journal of Software, 2023, 34(6):2509-2525 (in Chinese with English abstract). http://www.jos.org.cn/1000-9825/6846.htm
    [11] Long QQ, Jin YL, Wu Y, Song GJ. Theoretically improving graph neural networks via anonymous walk graph kernels. In:Proc. of the 2021 Web Conf. Ljubljana:ACM, 2021. 1204-1214.
    [12] Bruna J, Zaremba W, Szlam A, LeCun Y. Spectral networks and deep locally connected networks on graphs. In:Proc. of the 2nd Int'l Conf. on Learning Representations. Banff, 2014.
    [13] Defferrard M, Bresson X, Vandergheynst P. Convolutional neural networks on graphs with fast localized spectral filtering. In:Proc. of the 30th Int'l Conf. on Neural Information Processing Systems. Barcelona:Curran Associates Inc., 2016. 3844-3852.
    [14] Kipf TN, Welling M. Semi-supervised classification with graph convolutional networks. arXiv:1609.02907, 2017.
    [15] Zhang WT, Sheng ZA, Yang MY, Li Y, Shen Y, Yang Z, Cui B. NAFS:A simple yet tough-to-beat baseline for graph representation learning. In:Proc. of the 39th Int'l Conf. on Machine Learning. Baltimore:PMLR, 2022. 26467-26483.
    [16] 闫昭, 项欣光, 李泽超. 基于交互序列商品相关性建模的图卷积会话推荐. 中国科学:信息科学, 2022, 52(6):1069-1082.
    Yan Z, Xiang XG, Li ZC. Item correlation modeling in interaction sequence for graph convolutional session recommendation. Scientia Sinica Informationis, 2022, 52(6):1069-1082 (in Chinese with English abstract).
    [17] 胡雨涛, 王溯远, 吴月明, 邹德清, 李文科, 金海. 基于图神经网络的切片级漏洞检测及解释方法. 软件学报, 2023, 34(6):2543-2561.
    Hu YT, Wang SY, Wu YM, Zou DQ, Li WK, Jin H. Slice-level vulnerability detection and interpretation method based on graph neural network. Journal of Software, 2023, 34(6):2543-2561 (in Chinese with English abstract). http://www.jos.org.cn/1000-9825/6849.htm
    [18] Li ZC, Tang JH. Semi-supervised local feature selection for data classification. Science China Information Sciences, 2021, 64(9):192108.
    [19] Li ZC, Tang JH, Mei T. Deep collaborative embedding for social image understanding. IEEE Trans. on Pattern Analysis and Machine Intelligence, 2019, 41(9):2070-2083.
    [20] Xu KYL, Hu WH, Leskovec J, Jegelka S. How powerful are graph neural networks? arXiv:1810.00826, 2019.
    [21] Murphy R, Srinivasan B, Rao V, Ribeiro B. Relational pooling for graph representations. In:Proc. of the 36th Int'l Conf. on Machine Learning. Long Beach:PMLR, 2019. 4663-4673.
    [22] Sato R, Yamada M, Kashima H. Random features strengthen graph neural networks. In:Proc. of the 2021 SIAM Int'l Conf. on Data Mining (SDM). Virtual Event:Society for Industrial and Applied Mathematics, 2021. 333-341.
    [23] Li P, Wang YB, Wang HW, Leskovec J. Distance encoding:Design provably more powerful neural networks for graph representation learning. In:Proc. of the 34th Int'l Conf. on Neural Information Processing Systems. Vancouver:Curran Associates Inc., 2020. 4465-4478.
    [24] Wijesinghe A, Wang Q. A new perspective on "how graph neural networks go beyond Weisfeiler-Lehman?" In:Proc. of the 10th Int'l Conf. on Learning Representations. OpenReview.net, 2022. 1-23.
    [25] Passerini F, Severini S. The von Neumann entropy of networks. arXiv:0812.2597, 2012.
    [26] Chen PY, Wu LF, Liu SJ, Rajapakse I. Fast incremental von Neumann graph entropy computation:Theory, algorithm, and applications. In:Proc. of the 36th Int'l Conf. on Machine Learning. Long Beach:PMLR, 2019. 1091-1101.
    [27] Shervashidze N, Schweitzer P, van Leeuwen EJ, Mehlhorn K, Borgwardt KM. Weisfeiler-Lehman graph kernels. The Journal of Machine Learning Research, 2011, 12:2539-2561.
    [28] Borgwardt K, Ghisu E, Llinares-López F, O'Bray L, Rieck B. Graph kernels:State-of-the-art and future challenges. Foundations and Trends® in Machine Learning, 2020, 13(5-6):531-712.
    [29] Debnath AK, Lopez de Compadre RL, Debnath G, Shusterman AJ, Hansch C. Structure-activity relationship of mutagenic aromatic and heteroaromatic nitro compounds. Correlation with molecular orbital energies and hydrophobicity. Journal of Medicinal Chemistry, 1991, 34(2):786-797.
    [30] Wale N, Watson IA, Karypis G. Comparison of descriptor spaces for chemical compound retrieval and classification. Knowledge and Information Systems, 2008, 14(3):347-375.
    [31] Sutherland JJ, O'Brien LA, Weaver DF. Spline-fitting with a genetic algorithm:A method for developing classification structure-Activity relationships. Journal of Chemical Information and Computer Sciences, 2003, 43(6):1906-1915.
    [32] Kriege NM, Giscard PL, Wilson RC. On valid optimal assignment kernels and applications to graph classification. In:Proc. of the 30th Int'l Conf. on Neural Information Processing Systems. Barcelona:Curran Associates Inc., 2016. 1623-1631.
    [33] Yanardag P, Vishwanathan SVN. Deep graph kernels. In:Proc. of the 21st ACM SIGKDD Int'l Conf. on Knowledge Discovery and Data Mining. Sydney:ACM, 2015. 1365-1374.
    [34] Lin J. Divergence measures based on the Shannon entropy. IEEE Trans. on Information Theory, 1991, 37(1):145-151.
    [35] Xu LX, Bai L, Jiang XY, Tan M, Zhang DQ, Luo B. Deep Rényi entropy graph kernel. Pattern Recognition, 2021, 111:107668.
    [36] Oku K, Nakajima S, Miyazaki J, Uemura S. Context-aware SVM for context-dependent information recommendation. In:Proc. of the 7th Int'l Conf. on Mobile Data Management (MDM 2006). Nara:IEEE, 2006. 109-109.
    [37] Du SS, Hou KC, Póczos B, Salakhutdinov RR, Wang RS, Xu KYL. Graph neural tangent kernel:Fusing graph neural networks with graph kernels. In:Proc. of the 33rd Int'l Conf. on Neural Information Processing Systems. Vancouver:Curran Associates Inc., 2019. 5723-5733.
    [38] Togninalli M, Ghisu E, Llinares-López F, Rieck B, Borgwardt K. Wasserstein Weisfeiler-Lehman graph kernels. In:Proc. of the 33rd Int'l Conf. on Neural Information Processing Systems. Vancouver:Curran Associates Inc., 2019. 6439-6449.
    [39] Titouan V, Courty N, Tavenard R, et al. Optimal transport for structured data with application on graphs. In:Proc. of the 36th Int'l Conf. on Machine Learning. Long Beach:PMLR, 2019. 6275-6284.
    [40] Zhang MH, Cui ZC, Neumann M, Chen YX. An end-to-end deep learning architecture for graph classification. Proc. of the AAAI Conf. on Artificial Intelligence, 2018, 32(1):4438-4445.
    [41] Hamilton WL, Ying R, Leskovec J. Inductive representation learning on large graphs. In:Proc. of the 31st Int'l Conf. on Neural Information Processing Systems. Vancouver:Curran Associates Inc., 2017. 1025-1035.
    [42] Chen DX, Jacob L, Mairal J. Convolutional kernel networks for graph-structured data. In:Proc. of the 37th Int'l Conf. on Machine Learning. Virtual Event:JMLR. org, 2020. 1576-1586.
    [43] Zhu YK, Zhang K, Wang J, Ling HB, Zhang J, Zha H. Structural landmarking and interaction modelling:A "SLIM" network for graph classification. Proc. of the AAAI Conf. on Artificial Intelligence, 2022, 36(8):9251-9259.
    [44] Li JX, Sun QY, Peng H, Yang BN, Wu J, Yu PS. Adaptive subgraph neural network with reinforced critical structure mining. IEEE Trans. on Pattern Analysis and Machine Intelligence, 2023, 45(7):8063-8080.
    引证文献
    网友评论
    网友评论
    分享到微博
    发 布
引用本文

徐立祥,许巍,陈恩红,罗斌,唐远炎. KENN: 线性结构熵的图核神经网络.软件学报,2024,35(5):2430-2445

复制
分享
文章指标
  • 点击次数:
  • 下载次数:
  • HTML阅读次数:
  • 引用次数:
历史
  • 收稿日期:2023-04-03
  • 最后修改日期:2023-05-29
  • 在线发布日期: 2024-01-10
  • 出版日期: 2024-05-06
文章二维码
您是第19818443位访问者
版权所有:中国科学院软件研究所 京ICP备05046678号-3
地址:北京市海淀区中关村南四街4号,邮政编码:100190
电话:010-62562563 传真:010-62562533 Email:jos@iscas.ac.cn
技术支持:北京勤云科技发展有限公司

京公网安备 11040202500063号