CISPA
Browse
cispa_all_3813.pdf (713.31 kB)

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

Download (713.31 kB)
conference contribution
posted on 2023-11-29, 18:23 authored by Yan Scholten, Jan Schuchardt, Simon Geisler, Aleksandar Bojchevski, Stephan Günnemann
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.

History

Preferred Citation

Yan Scholten, Jan Schuchardt, Simon Geisler, Aleksandar Bojchevski and Stephan Günnemann. Randomized Message-Interception Smoothing: Gray-box Certificates for Graph Neural Networks. In: Conference on Neural Information Processing Systems (NeurIPS). 2022.

Primary Research Area

  • Trustworthy Information Processing

Name of Conference

Conference on Neural Information Processing Systems (NeurIPS)

Legacy Posted Date

2022-10-13

Open Access Type

  • Green

BibTeX

@inproceedings{cispa_all_3813, title = "Randomized Message-Interception Smoothing: Gray-box Certificates for Graph Neural Networks", author = "Scholten, Yan and Schuchardt, Jan and Geisler, Simon and Bojchevski, Aleksandar and Günnemann, Stephan", booktitle="{Conference on Neural Information Processing Systems (NeurIPS)}", year="2022", }

Usage metrics

    Categories

    No categories selected

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC