On the robustness of graph neural diffusion to topology perturbations
Article No.: 462, Pages 6384 - 6396
Abstract
Neural diffusion on graphs is a novel class of graph neural networks that has attracted increasing attention recently. The capability of graph neural partial differential equations (PDEs) in addressing common hurdles of graph neural networks (GNNs), such as the problems of over-smoothing and bottlenecks, has been investigated but not their robustness to adversarial attacks. In this work, we explore the robustness properties of graph neural PDEs. We empirically demonstrate that graph neural PDEs are intrinsically more robust against topology perturbation as compared to other GNNs. We provide insights into this phenomenon by exploiting the stability of the heat semigroup under graph topology perturbations. We discuss various graph diffusion operators and relate them to existing graph neural PDEs. Furthermore, we propose a general graph neural PDE framework based on which a new class of robust GNNs can be defined. We verify that the new model achieves comparable state-of-the-art performance on several benchmark datasets.
Supplementary Material
Supplemental material.
- Download
- 263.00 KB
References
[1]
X. Yue, Z. Wang, J. Huang, S. Parthasarathy, S. Moosavinasab, Y. Huang, S. M. Lin, W. Zhang, P. Zhang, and H. Sun, "Graph embedding on biomedical networks: methods, applications and evaluations," Bioinformatics, vol. 36, no. 4, pp. 1241-1251, 2019.
[2]
H. Ashoor, X. Chen, W. Rosikiewicz, J. Wang, A. Cheng, P. Wang, Y. Ruan, and S. Li, "Graph embedding and unsupervised learning predict genomic sub-compartments from hic chromatin interaction data," Nat. Commun., vol. 11, 2020.
[3]
T. N. Kipf and M. Welling, "Semi-supervised classification with graph convolutional networks," in Proc. Int. Conf. Learn. Representations, 2017.
[4]
Z. Zhang, P. Cui, and W. Zhu, "Deep learning on graphs: A survey," IEEE Trans. Knowl. Data Eng., vol. 34, no. 1, pp. 249-270, Jan 2022.
[5]
Z. Wu, S. Pan, F. Chen, G. Long, C. Zhang, and P. S. Yu, "A comprehensive survey on graph neural networks," IEEE Trans. Neural Netw. Learn. Syst., vol. 32, no. 1, pp. 4-24, 2021.
[6]
T. N. Kipf and M. Welling, "Variational graph auto-encoders," in Advances Neural Inf. Process. Syst. Workshop, 2016.
[7]
R. Ying, R. He, K. Chen, P. Eksombatchai, W. L. Hamilton, and J. Leskovec, "Graph convolutional neural networks for web-scale recommender systems," in Proc. Int. Conf. Knowledge Discovery and Data Mining, 2018.
[8]
J. Gilmer, S. S. Schoenholz, P. F. Riley, O. Vinyals, and G. E. Dahl, "Neural message passing for quantum chemistry," in Proc. Int. Conf. Mach. Learn., 2017.
[9]
D. Zügner, A. Akbarnejad, and S. Günnemann, "Adversarial attacks on neural networks for graph data," in Proc. Int. Conf. Knowl. Discovery Data Mining, 2018.
[10]
J. Chen, Y. Wu, X. Xu, Y. Chen, H. Zheng, and Q. Xuan, "Fast gradient attack on network embedding," ArXiv, 2018.
[11]
M. Waniek, T. P. Michalak, M. J. Wooldridge, and T. Rahwan, "Hiding individuals and communities in a social network," Nature Human Behaviour, vol. 2, no. 1, pp. 139-147, 2018.
[12]
J. Du, S. Zhang, G. Wu, J. M. F. Moura, and S. Kar, "Topology adaptive graph convolutional networks," ArXiv, vol. abs/1710.10370, 2017.
[13]
J. Wang, M. Luo, F. Suya, J. Li, Z. Yang, and Q. Zheng, "Scalable attack on graph data by injecting vicious nodes," Data Mining Knowl. Discovery, pp. 1 - 27, 2020.
[14]
Q. Zheng, Y. Fei, Y. Li, Q. Liu, M. Hu, and Q. Sun. Kdd cup 2020 ml track 2 adversarial attacks and defense on academic graph 1st place solution. Accessed: May 1, 2022. [Online]. Available: https://github.com/Stanislas0/KDD_CUP_2020_MLTrack2_SPEIT
[15]
X. Zou, Q. Zheng, Y. Dong, X. Guan, E. Kharlamov, J. Lu, and J. Tang, "Tdgia: Effective injection attacks on graph neural networks," in Proc. Int. Conf. Knowl. Discovery Data Mining, 2021, p. 2461-2471.
[16]
D. Zügner and S. Günnemann, "Adversarial attacks on graph neural networks via meta learning," in Proc. Int. Conf. Learn. Representations, 2019.
[17]
Y. Ma, S. Wang, T. Derr, L. Wu, and J. Tang, "Graph adversarial attack via rewiring," in Proc. Int. Conf. Knowl. Discovery Data Mining, 2021, p. 1161-1169.
[18]
Y. Sun, S. Wang, X. Tang, T.-Y. Hsieh, and V. Honavar, "Adversarial attacks on graph neural networks via node injections: A hierarchical reinforcement learning approach," in Proc. Web Conf., 2020, p. 673-683.
[19]
D. Zhu, Z. Zhang, P. Cui, and W. Zhu, "Robust graph convolutional networks against adversarial attacks," in Proc. Int. Conf. Knowl. Discovery Data Mining, 2019, p. 1399-1407.
[20]
W. Feng, J. Zhang, Y. Dong, Y. Han, H. Luan, Q. Xu, Q. Yang, E. Kharlamov, and J. Tang, "Graph random neural networks for semi-supervised learning on graphs," in Advances Neural Inf. Process. Syst., 2020.
[21]
W. Jin, Y. Ma, X. Liu, X. Tang, S. Wang, and J. Tang, "Graph structure learning for robust graph neural networks," in Proc. Int. Conf. Knowl. Discovery Data Mining, 2020, p. 66-74.
[22]
N. Entezari, S. A. Al-Sayouri, A. Darvishzadeh, and E. E. Papalexakis, "All you need is low (rank): Defending against adversarial attacks on graphs," in Proc. Int. Conf. Web Search Data Mining, 2020, p. 169-177.
[23]
X. Zhang and M. Zitnik, "GNNGUARD: Defending graph neural networks against adversarial attacks," in Advances Neural Inf. Process. Syst., 2020.
[24]
H. Yan, J. Du, V. Y. Tan, and J. Feng, "On robustness of neural ordinary differential equations," in Advances Neural Inf. Process. Syst., 2018, pp. 1-13.
[25]
E. Haber and L. Ruthotto, "Stable architectures for deep neural networks," Inverse Problems, vol. 34, no. 1, pp. 1-23, Dec. 2017.
[26]
X. Liu, S. Si, Q. Cao, S. Kumar, and C.-J. Hsieh, "How does noise help robustness? Explanation and exploration under the neural sde framework," in Proc. Conf. Comput. Vision Pattern Recognition, 2020, pp. 282-290.
[27]
Q. Kang, Y. Song, Q. Ding, and W. P. Tay, "Stable neural ODE with Lyapunov-stable equilibrium points for defending against adversarial attacks," in Advances Neural Inf. Process. Syst., 2021.
[28]
R. T. Chen, Y. Rubanova, J. Bettencourt, and D. Duvenaud, "Neural ordinary differential equations," arXiv preprint arXiv:1806.07366, 2018.
[29]
B. P. Chamberlain, J. Rowbottom, M. Goronova, S. Webb, E. Rossi, and M. M. Bronstein, "Grand: Graph neural diffusion," in Proc. Int. Conf. Mach. Learn., 2021.
[30]
B. P. Chamberlain, J. Rowbottom, D. Eynard, F. Di Giovanni, D. Xiaowen, and M. M. Bronstein, "Beltrami flow and neural diffusion on graphs," in Advances Neural Inf. Process. Syst., 2021.
[31]
A. Grigoryan, Heat kernel and analysis on manifolds. Providence: American Mathematical Soc., 2009.
[32]
L. Saloff-Coste, "Uniformly elliptic operators on Riemannian manifolds," J. Differ. Geometry, vol. 36, no. 2, pp. 417-450, 1992.
[33]
Z.-Q. Chen, Z. Qian, Y. Hu, and W. Zheng, "Stability and approximations of symmetric diffusion semigroups and kernels," J. functional anal., vol. 152, no. 1, pp. 255-280, 1998.
[34]
J. Sun, M. Ovsjanikov, and L. Guibas, "A concise and provably informative multi-scale signature based on heat diffusion," Computer graphics forum, vol. 28, no. 5, pp. 1383-1392, 2009.
[35]
J. Nash, "The imbedding problem for Riemannian manifolds," Ann. math., vol. 63, no. 1, pp. 20-63, 1956.
[36]
E. P. Hsu, Stochastic analysis on manifolds. Providence: American Mathematical Soc., 2002.
[37]
E. DiBenedetto, U. P. Gianazza, and V. Vespri, Harnack's inequality for degenerate and singular parabolic equations. London: Springer Science & Business Media, 2011.
[38]
W. Zheng, "Stability of time-dependent diffusion semigroups and kernels," Acta Math. Sinica, vol. 15, no. 4, pp. 575-586, 1999.
[39]
D. Zhou and B. Schölkopf, "Regularization on discrete spaces," in Joint Pattern Recognition Symposium. Springer, 2005, pp. 361-368.
[40]
N. Sochen, R. Kimmel, and R. Malladi, "A general framework for low level vision," IEEE Trans. Image Process., vol. 7, no. 3, pp. 310-318, 1998.
[41]
P. Veličković, G. Cucurull, A. Casanova, A. Romero, P. Liò, and Y. Bengio, "Graph attention networks," in Proc. Int. Conf. Learn. Representations, 2018, pp. 1-12.
[42]
C.-T. Chen and B. Shafai, Linear system theory and design. New York: Oxford university press New York, 1999.
[43]
G. Dasoulas, K. Scaman, and A. Virmaux, "Lipschitz normalization for self-attention layers with application to graph neural networks," in Proc. Int. Conf. Mach. Learning, 2021, pp. 2456-2466.
[44]
A. McCallum, K. Nigam, J. D. M. Rennie, and K. Seymore, "Automating the construction of internet portals with machine learning," Information Retrieval, vol. 3, pp. 127-163, 2004.
[45]
W. L. Hamilton, R. Ying, and J. Leskovec, "Inductive representation learning on large graphs," in Advances Neural Inf. Process. Syst., 2017.
[46]
K. Xu, W. Hu, J. Leskovec, and S. Jegelka, "How powerful are graph neural networks?" in Proc. Int. Conf. Learn. Representations, 2019.
[47]
J. Klicpera, A. Bojchevski, and S. Günnemann, "Predict then propagate: Graph neural networks meet personalized pagerank," in Proc. Int. Conf. Learning Representations, 2019.
[48]
P. Sen, G. Namata, M. Bilgic, L. Getoor, B. Galligher, and T. Eliassi-Rad, "Collective classification in network data," AI Magazine, vol. 29, no. 3, p. 93, Sep. 2008.
[49]
G. M. Namata, B. London, L. Getoor, and B. Huang, "Query-driven active surveying for collective classification," in Workshop Mining and Learn. with Graphs, 2012.
[50]
Q. Zheng, X. Zou, Y. Dong, Y. Cen, D. Yin, J. Xu, Y. Yang, and J. Tang, "Graph robustness benchmark: Benchmarking the adversarial robustness of graph machine learning," Neural Information Processing Systems Track on Datasets and Benchmarks 2021, 2021.
[51]
D. Bhaskar, K. MacDonald, D. Thomas, S. Zhao, K. You, J. Paige, Y. Aizenbud, B. Rieck, I. M. Adelstein, and S. Krishnaswamy, "Diffusion-based methods for estimating curvature in data," in ICLR Workshop Geometrical Topological Representation Learn., 2022.
[52]
J. Topping, F. D. Giovanni, B. P. Chamberlain, X. Dong, and M. M. Bronstein, "Understanding over-squashing and bottlenecks on graphs via curvature," in Proc. Int. Conf. Learn. Representations, 2022.
[53]
S. Zhu, S. Pan, C. Zhou, J. Wu, Y. Cao, and B. Wang, "Graph geometry interaction learning," in Advances Neural Inf. Process. Syst., 2020.
Index Terms
- On the robustness of graph neural diffusion to topology perturbations
Index terms have been assigned to the content through auto-classification.
Recommendations
Transferring Robustness for Graph Neural Network Against Poisoning Attacks
WSDM '20: Proceedings of the 13th International Conference on Web Search and Data MiningGraph neural networks (GNNs) are widely used in many applications. However, their robustness against adversarial attacks is criticized. Prior studies show that using unnoticeable modifications on graph topology or nodal features can significantly reduce ...
Certifiable Robustness of Graph Convolutional Networks under Structure Perturbations
KDD '20: Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data MiningRecent works show that message-passing neural networks (MPNNs) can be fooled by adversarial attacks on both the node attributes and the graph structure. Since MPNNs are currently being rapidly adopted in real-world applications, it is thus crucial to ...
Robustness quantification of recurrent neural network using unscented transform
Artificial recurrent neural network has been proved to be a valuable tool in modeling nonlinear dynamical systems. Robustness study of recurrent neural network is critical to its successful implementation. The goal of robustness study is to reduce the ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
November 2022
39114 pages
ISBN:9781713871088
- Editors:
- S. Koyejo,
- S. Mohamed,
- A. Agarwal,
- D. Belgrave,
- K. Cho,
- A. Oh
Copyright © 2022 Neural Information Processing Systems Foundation, Inc.
Publisher
Curran Associates Inc.
Red Hook, NY, United States
Publication History
Published: 03 April 2024
Qualifiers
- Research-article
- Research
- Refereed limited
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 03 Jan 2025