微信服务号

微信订阅号

2025-4-6- 4
Home > Archive>Volume 35, Issue 8, 2024 >3878-3896. DOI:10.13328/j.cnki.jos.007065
PDF HTML XML Export Cite reminder
Over-parameterized Graph Neural Network Towards Robust Graph Structure Defending
Author:
Affiliation:

Clc Number:

TP18

  • Article
    • | |
  • Metrics
    • |
  • Reference [40]
    • |
  • Related [20]
    • |
  • Cited by
    • | |
  • Comments
    Abstract:

    Graph data is ubiquitous in real-world applications, and graph neural networks (GNNs) have been widely used in graph data analysis. However, the performance of GNNs can be severely impacted by adversarial attacks on graph structures. Existing defense methods against adversarial attacks generally rely on low-rank graph structure reconstruction based on graph community preservation priors. However, existing graph structure adversarial defense methods cannot adaptively seek the true low-rank value for graph structure reconstruction, and low-rank graph structures are semantically mismatched with downstream tasks. To address these problems, this study proposes the over-parameterized graph neural network (OPGNN) method based on the implicit regularization effect of over-parameterization. In addition, it formally proves that this method can adaptively solve the low-rank graph structure problem and also proves that over-parameterized residual links on node deep representations can effectively address semantic mismatch. Experimental results on real datasets demonstrate that the OPGNN method is more robust than existing baseline methods, and the OPGNN framework is notably effective on different graph neural network backbones such as GCN, APPNP, and GPRGNN.

    Reference
    [1] Bruna J, Zaremba W, Szlam A, LeCun Y. Spectral networks and locally connected networks on graphs. arXiv:1312.6203, 2014.
    [2] 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.
    [3] Kipf TN, Welling M. Semi-supervised classification with graph convolutional networks. arXiv:1609.02907, 2017.
    [4] Wang YH, Min YS, Chen X, Wu J. Multi-view graph contrastive representation learning for drug-drug interaction prediction. In: Proc. of the 2021 Web Conf. Ljubljana: Association for Computing Machinery, 2021. 2921–2933.
    [5] Qiu JZ, Tang J, Ma H, Dong YX, Wang KS, Tang J. DeepInf: Social influence prediction with deep learning. In: Proc. of the 24th ACM SIGKDD Int’l Conf. on Knowledge Discovery and Data Mining. London: Association for Computing Machinery, 2018. 2110–2119.
    [6] Yu B, Yin HT, Zhu ZX. Spatio-temporal graph convolutional networks: A deep learning framework for traffic forecasting. In: Proc. of the 27th Int’l Joint Conf. on Artificial Intelligence. Stockholm: AAAI Press, 2018. 3634–3640.
    [7] Wang Q, Mao ZD, Wang B, Guo L. Knowledge graph embedding: A survey of approaches and applications. IEEE Trans. on Knowledge and Data Engineering, 2017, 29(12): 2724–2743.
    [8] Dai HJ, Li H, Tian T, Huang X, Wang L, Zhu J, Song L. Adversarial attack on graph structured data. In: Proc. of the 35th Int’l Conf. on Machine Learning. Stockholm: JMLR.org, 2018. 1115–1124.
    [9] Gilmer J, Schoenholz SS, Riley PF, Vinyals O, Dahl GE. Neural message passing for quantum chemistry. In: Proc. of the 34th Int’l Conf. on Machine Learning. Sydney: JMLR.org, 2017. 1263–1272.
    [10] Zhu YQ, Xu WZ, Zhang JH, Du YQ, Zhang JY, Liu Q, Yang C, Wu S. A survey on graph structure learning: Progress and opportunities. arXiv:2103.03036, 2022.
    [11] Chung F. Spectral Graph Theory. Providence: American Mathematical Society, 1997.
    [12] Friedland S, Lim LH. Nuclear norm of higher-order tensors. Mathematics of Computation, 2018, 87(311): 1255–1281.
    [13] Entezari N, Al-Sayouri SA, Darvishzadeh A, Papalexakis EE. All you need is low (rank): Defending against adversarial attacks on graphs. In: Proc. of the 13th Int’l Conf. on Web Search and Data Mining. Houston: Association for Computing Machinery, 2020. 169–177.
    [14] Luo DS, Cheng W, Yu WC, Zong B, Ni JC, Chen HF, Zhang X. Learning to drop: Robust graph neural network via topological denoising. In: Proc. of the 14th ACM Int’l Conf. on Web Search and Data Mining. Association for Computing Machinery, 2021. 779–787.
    [15] Ionescu C, Vantzos O, Sminchisescu C. Matrix backpropagation for deep networks with structured layers. In: Proc. of the 2015 IEEE Int’l Conf. on Computer Vision. Santiago: IEEE, 2015. 2965–2973.
    [16] Xu H, Xiang LY, Yu JH, Cao AQ, Wang XB. Speedup robust graph structure learning with low-rank information. In: Proc. of the 30th ACM Int’l Conf. on Information and Knowledge Management. Association for Computing Machinery, 2021. 2241–2250.
    [17] Li RY, Wang S, Zhu FY, Huang JZ. Adaptive graph convolutional neural networks. In: Proc. of the 32nd AAAI Conf. on Artificial Intelligence, the 30th Innovative Applications of Artificial Intelligence Conf. and the 8th AAAI Symp. on Educational Advances in Artificial Intelligence. New Orleans: AAAI Press, 2018. 3546–3553.
    [18] Liu SQ, Chen Y, Xie XF, Siow JK, Liu Y. Retrieval-augmented generation for code summarization via hybrid GNN. arXiv:2006.05405, 2021.
    [19] Zhao T, Liu Y, Neves L, Woodford O, Jiang M, Shah N. Data augmentation for graph neural networks. Proc. of the AAAI Conf. on Artificial Intelligence, 2021, 35(12): 11015–11023.
    [20] Gasteiger J, Bojchevski A, Günnemann S. Predict then propagate: Graph neural networks meet personalized PageRank. arXiv:1810.05997, 2019.
    [21] Chien EL, Peng JH, Li P, Milenkovic O. Adaptive universal generalized PageRank graph neural network. arXiv:2006.07988, 2021.
    [22] Zügner D, Günnemann S. Adversarial attacks on graph neural networks via Meta learning. arXiv:1902.08412, 2019.
    [23] Jin W, Ma Y, Liu XR, Tang XF, Wang SH, Tang JL. Graph structure learning for robust graph neural networks. In: Proc. of the 26th ACM SIGKDD Int’l Conf. on Knowledge Discovery and Data Mining. Association for Computing Machinery, 2020. 66–74.
    [24] Jin W, Derr T, Wang YQ, Ma Y, Liu ZT, Tang JL. Node similarity preserving graph convolutional networks. In: Proc. of the 14th ACM Int’l Conf. on Web Search and Data Mining. Association for Computing Machinery, 2021. 148–156.
    [25] Li K, Liu Y, Ao X, Chi JF, Feng JH, Yang H, He Q. Reliable representations make a stronger defender: Unsupervised structure refinement for robust GNN. In: Proc. of the 28th ACM SIGKDD Conf. on Knowledge Discovery and Data Mining. Washington: Association for Computing Machinery, 2022. 925–935.
    [26] 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.
    [27] Li ZC, Tang JH, Zhang LY, Yang J. Weakly-supervised semantic guided hashing for social image retrieval. Int’l Journal of Computer Vision, 2020, 128(8): 2265–2278.
    [28] Gunasekar S, Woodworth B, Bhojanapalli S, Neyshabur B, Srebro N. Implicit regularization in matrix factorization. In: Proc. of the 31st Int’l Conf. on Neural Information Processing Systems. Long Beach: Curran Associates Inc., 2017. 6152–6160.
    [29] Arora S, Cohen N, Hu W, Luo YP. Implicit regularization in deep matrix factorization. In: Proc. of the 33rd Int’l Conf. on Neural Information Processing Systems. Vancouver: Curran Associates Inc., 2019. 7413–7424.
    [30] Vaškevičius T, Kanade V, Rebeschini P. Implicit regularization for optimal sparse recovery. In: Proc. of the 33rd Int’l Conf. on Neural Information Processing Systems. Vancouver: Curran Associates Inc., 2019. 2972–2983.
    [31] Zhao P, Yang Y, He QC. High-dimensional linear regression via implicit regularization. Biometrika, 2022, 109(4): 1033–1046.
    [32] You C, Zhu ZH, Qu Q, Ma Y. Robust recovery via implicit bias of discrepant learning rates for double over-parameterization. In: Proc. of the 34th Int’l Conf. on Neural Information Processing Systems. Vancouver: Curran Associates Inc., 2020. 17733–17744.
    [33] Liu S, Zhu ZH, Qu Q, You C. Robust training under label noise by over-parameterization. In: Proc. of the 39th Int’l Conf. on Machine Learning. Baltimore: JMLR.org, 2022. 14153–14172.
    [34] Ortega A, Frossard P, Kovačević J, Moura JMF, Vandergheynst P. Graph signal processing: Overview, challenges, and applications. Proc. of the IEEE, 2018, 106(5): 808–828.
    [35] Wang XY, Zhang MH. How powerful are spectral graph neural networks. In: Proc. of the 39th Int’l Conf. on Machine Learning. Baltimore: JMLR.org, 2022. 23341–23362.
    [36] Zhu DY, Zhang ZW, Cui P, Zhu WW. Robust graph convolutional networks against adversarial attacks. In Proc. of the 25th ACM SIGKDD Int’l Conf. on Knowledge Discovery and Data Mining. Anchorage: Association for Computing Machinery, 2019. 1399–1407.
    [37] Wu HJ, Wang C, Tyshetskiy Y, Docherty A, Lu K, Zhu LM. Adversarial examples for graph data: Deep insights into attack and defense. In: Proc. of the 28th Int’l Joint Conf. on Artificial Intelligence. Macao: AAAI Press, 2019. 4816–4823.
    [38] Liu XR, Jin W, Ma Y, Li YX, Liu H, Wang YQ, Yan M, Tang JL. Elastic graph neural networks. In: Proc. of the 38th Int’l Conf. on Machine Learning. Virtual Event: JMLR.org, 2021. 6837–6849.
    [39] Veličković P, Cucurull G, Casanova A, Romero A, Liò P, Bengio Y. Graph attention networks. arXiv:1710.10903, 2018.
    [40] Li YX, Jin W, Xu H, Tang JL. DeepRobust: A PyTorch library for adversarial attacks and defenses. arXiv:2005.06149, 2020.
    Cited by
    Comments
    Comments
    分享到微博
    Submit
Get Citation

初旭,马辛宇,林阳,王鑫,王亚沙,朱文武,梅宏.面向鲁棒图结构防御的过参数化图神经网络.软件学报,2024,35(8):3878-3896

Copy
Share
Article Metrics
  • Abstract:381
  • PDF: 1241
  • HTML: 458
  • Cited by: 0
History
  • Received:May 04,2023
  • Revised:September 16,2023
  • Online: February 28,2024
  • Published: August 06,2024
Links:Institute of Software, CASChina Computer FederationCASNSFC
You are the first2033286Visitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-4
Address：4# South Fourth Street, Zhong Guan Cun, Beijing 100190,Postal Code：100190
Phone：010-62562563 Fax：010-62562533 Email：jos@iscas.ac.cn
Technical Support：Beijing Qinyun Technology Development Co., Ltd.

Beijing Public Network Security No. 11040202500063