Provable Robustness Certification of Graph Neural Networks

• Applicant: Professor Dr. Stephan Günnemann
• Subject Area: Image and Language Processing, Computer Graphics and Visualisation, Human Computer Interaction, Ubiquitous and Wearable Computing
• Term: since 2021
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 463892539

Graph Neural Networks (GNNs), alongside CNNs and RNNs, have become a fundamental building block in many deep learning models, with ever stronger impact on domains such as chemistry (molecular graphs), social sciences (social networks), biomedicine (gene regulatory networks), and many more. Recent studies, however, have shown that GNNs are highly non-robust: even only small perturbations of the graph’s structure or the nodes’ features can mislead the predictions of these models significantly. This is a show-stopper for their application in real-world environments, where data is often corrupted, noisy, or sometimes even manipulated by adversaries.The goal of this project is to increase trust in GNNs by deriving principles for their robustness certification, i.e. to provide provable guarantees that no perturbation regarding a specific corruption model will change the predicted outcome. It, thus, explicitly tackles one of the core pillars of the priority programme, which focuses on safety and robustness. We propose to investigate new theoretical guarantees for important (node-level and graph-level) tasks and corruption models, significantly expanding beyond the few existing certificates and addressing their critical limitations. Specifically we aim to develop certification techniques taking fundamental yet overlooked characteristics of graph learning tasks into account such as collective prediction of multiple outputs and permutation invariance. In all these cases we aim to improve the certificates by additionally incorporating model-specific information. Moreover, since some of the most important applications of GNNs are posed as regression tasks, e.g. predicting the energy potential of molecules, we propose to tackle for the first time certification in the challenging setting of discrete input and continuous output. Researching these novel certificates will go hand in hand with the study of their inherent limitations, e.g. due to the curse of dimensionality or relaxations of the underlying hard optimization problems.Overall, by deriving formal robustness guarantees our project provides a cornerstone for the theoretical foundations of GNNs. Each work package tackles different and necessary aspects of robustness. Given the many diverse applications of GNNs we expect our results to have a broad impact for both research and application.

• DFG Programme: Priority Programmes
• Subproject of: SPP 2298: Theoretical Foundations of Deep Learning