Randomized Message-Interception Smoothing: Gray-box Certificates for Graph Neural Networks

Yan Scholten, Jan Schuchardt, Simon Geisler, Aleksandar Bojchevski, Stephan Günnemann

Publikation: Beitrag in Buch/Bericht/KonferenzbandKonferenzbeitragBegutachtung

16 Zitate (Scopus)

Abstract

Randomized smoothing is one of the most promising frameworks for certifying the adversarial robustness of machine learning models, including Graph Neural Networks (GNNs). Yet, existing randomized smoothing certificates for GNNs are overly pessimistic since they treat the model as a black box, ignoring the underlying architecture. To remedy this, we propose novel gray-box certificates that exploit the message-passing principle of GNNs: We randomly intercept messages and carefully analyze the probability that messages from adversarially controlled nodes reach their target nodes. Compared to existing certificates, we certify robustness to much stronger adversaries that control entire nodes in the graph and can arbitrarily manipulate node features. Our certificates provide stronger guarantees for attacks at larger distances, as messages from farther-away nodes are more likely to get intercepted. We demonstrate the effectiveness of our method on various models and datasets. Since our gray-box certificates consider the underlying graph structure, we can significantly improve certifiable robustness by applying graph sparsification.

OriginalspracheEnglisch
TitelAdvances in Neural Information Processing Systems 35 - 36th Conference on Neural Information Processing Systems, NeurIPS 2022
Redakteure/-innenS. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, A. Oh
Herausgeber (Verlag)Neural information processing systems foundation
ISBN (elektronisch)9781713871088
PublikationsstatusVeröffentlicht - 2022
Veranstaltung36th Conference on Neural Information Processing Systems, NeurIPS 2022 - New Orleans, USA/Vereinigte Staaten
Dauer: 28 Nov. 20229 Dez. 2022

Publikationsreihe

NameAdvances in Neural Information Processing Systems
Band35
ISSN (Print)1049-5258

Konferenz

Konferenz36th Conference on Neural Information Processing Systems, NeurIPS 2022
Land/GebietUSA/Vereinigte Staaten
OrtNew Orleans
Zeitraum28/11/229/12/22

Fingerprint

Untersuchen Sie die Forschungsthemen von „Randomized Message-Interception Smoothing: Gray-box Certificates for Graph Neural Networks“. Zusammen bilden sie einen einzigartigen Fingerprint.

Dieses zitieren