Generalization of machine learning models can be severely compromised by data poisoning, where adversarial changes are applied to the training data, as well as backdoor attacks that additionally manipulate the test data. These vulnerabilities have led to an interest in certifying (i.e., proving) that such changes up to a certain magnitude do not affect test predictions. We, for the first time, certify Graph Neural Networks (GNNs) against poisoning and backdoor attacks targeting the node features of a given graph. Our certificates are white-box and based upon (i) the neural tangent kernel, which characterizes the training dynamics of sufficiently wide networks; and (ii) a novel reformulation of the bilevel optimization problem describing poisoning as a mixed-integer linear program. Consequently, we leverage our framework to provide fundamental insights into the role of graph structure and its connectivity on the worst-case robustness behavior of convolution-based and PageRank-based GNNs. We note that our framework is more general and constitutes the first approach to derive white-box certificates for NNs, which can be of independent interest beyond graph-related tasks.
@article{gosch2024provable,title={Provable robustness of (graph) neural networks against data poisoning and backdoor attacks},author={Gosch, Lukas and Sabanayagam, Mahalakshmi and Ghoshdastidar, Debarghya and G{\"u}nnemann, Stephan},journal={arXiv:2407.10867},year={2024},}
Relaxing Graph Transformers for Adversarial Attacks
Philipp Foth, Lukas Gosch, Simon Geisler, and
2 more authors
ICML 2024’ Differentiable Almost Everything Workshop, 2024
Existing studies have shown that Graph Neural Networks (GNNs) are vulnerable to adversarial attacks. Even though Graph Transformers (GTs) surpassed Message-Passing GNNs on several benchmarks, their adversarial robustness properties are unexplored. However, attacking GTs is challenging due to their Positional Encodings (PEs) and special attention mechanisms which can be difficult to differentiate. We overcome these challenges targeting three representative architectures based on (1) random-walk PEs, (2) pair-wise-shortest-path PEs, and (3) spectral PEs – and propose the first adaptive attacks for GTs. We leverage our attacks to evaluate robustness to (a) structure perturbations on node classification; and (b) node injection attacks for (fake-news) graph classification. Our evaluation reveals that they can be catastrophically fragile and underlines our work’s importance and the necessity for adaptive attacks.
@article{dfoth2024relaxing,title={Relaxing Graph Transformers for Adversarial Attacks},author={Foth, Philipp and Gosch, Lukas and Geisler, Simon and Schwinn, Leo and G{\"u}nnemann, Stephan},journal={ICML 2024' Differentiable Almost Everything Workshop},year={2024},}
2023
Adversarial Training for Graph Neural Networks: Pitfalls, Solutions, and New Directions
Lukas Gosch, Simon Geisler, Daniel Sturm, and
3 more authors
In Thirty-seventh Conference on Neural Information Processing Systems (NeurIPS), 2023
Despite its success in the image domain, adversarial training did not (yet) stand out as an effective defense for Graph Neural Networks (GNNs) against graph structure perturbations. In the pursuit of fixing adversarial training (1) we show and overcome fundamental theoretical as well as practical limitations of the adopted graph learning setting in prior work; (2) we reveal that more flexible GNNs based on learnable graph diffusion are able to adjust to adversarial perturbations, while the learned message passing scheme is naturally interpretable; (3) we introduce the first attack for structure perturbations that, while targeting multiple nodes at once, is capable of handling global (graph-level) as well as local (node-level) constraints. Including these contributions, we demonstrate that adversarial training is a state-of-the-art defense against adversarial structure perturbations.
@inproceedings{gosch2023adversarial,title={Adversarial Training for Graph Neural Networks: Pitfalls, Solutions, and New Directions},author={Gosch, Lukas and Geisler, Simon and Sturm, Daniel and Charpentier, Bertrand and Z{\"u}gner, Daniel and G{\"u}nnemann, Stephan},booktitle={Thirty-seventh Conference on Neural Information Processing Systems (NeurIPS)},year={2023},}
Revisiting Robustness in Graph Machine Learning
Lukas Gosch, Daniel Sturm, Simon Geisler, and
1 more author
In The Eleventh International Conference on Learning Representations (ICLR), 2023
Many works show that node-level predictions of Graph Neural Networks (GNNs) are unrobust to small, often termed adversarial, changes to the graph structure.
However, because manual inspection of a graph is difficult, it is unclear if the
studied perturbations always preserve a core assumption of adversarial examples:
that of unchanged semantic content. To address this problem, we introduce a
more principled notion of an adversarial graph, which is aware of semantic con-
tent change. Using Contextual Stochastic Block Models (CSBMs) and real-world
graphs, our results uncover: i) for a majority of nodes the prevalent perturba-
tion models include a large fraction of perturbed graphs violating the unchanged
semantics assumption; ii) surprisingly, all assessed GNNs show over-robustness
- that is robustness beyond the point of semantic change. We find this to be a
complementary phenomenon to adversarial examples and show that including the
label-structure of the training graph into the inference process of GNNs signif-
icantly reduces over-robustness, while having a positive effect on test accuracy
and adversarial robustness. Theoretically, leveraging our new semantics-aware
notion of robustness, we prove that there is no robustness-accuracy tradeoff for
inductively classifying a newly added node.
@inproceedings{gosch2023revisiting,title={Revisiting Robustness in Graph Machine Learning},author={Gosch, Lukas and Sturm, Daniel and Geisler, Simon and G{\"u}nnemann, Stephan},booktitle={The Eleventh International Conference on Learning Representations (ICLR)},year={2023},url={https://openreview.net/forum?id=h1o7Ry9Zctm},}
2022
Training Differentially Private Graph Neural Networks with Random Walk Sampling
Morgane Ayle, Jan Schuchardt, Lukas Gosch, and
2 more authors
Deep learning models are known to put the privacy of their training data at risk, which poses challenges for their safe and ethical release to the public. Differentially private stochastic gradient descent is the de facto standard for training neural networks without leaking sensitive information about the training data. However, applying it to models for graph-structured data poses a novel challenge: unlike with i.i.d. data, sensitive information about a node in a graph cannot only leak through its gradients, but also through the gradients of all nodes within a larger neighborhood. In practice, this limits privacy-preserving deep learning on graphs to very shallow graph neural networks. We propose to solve this issue by training graph neural networks on disjoint subgraphs of a given training graph. We develop three random-walk-based methods for generating such disjoint subgraphs and perform a careful analysis of the data-generating distributions to provide strong privacy guarantees. Through extensive experiments, we show that our method greatly outperforms the state-of-the-art baseline on three large graphs, and matches or outperforms it on four smaller ones.
Revisiting Robustness in Graph Machine Learning
Lukas Gosch, Daniel Sturm, Simon Geisler, and
1 more author
NeurIPS 2022’ TSRML Workshop and NeurIPS 2022’ ML Safety Workshop, 2022
Many works show that node-level predictions of Graph Neural Networks (GNNs) are unrobust to small, often termed adversarial, changes to the graph structure. However, because manual inspection of a graph is difficult, it is unclear if the studied perturbations always preserve a core assumption of adversarial examples: that of unchanged semantic content. To address this problem, we introduce a more principled notion of an adversarial graph, which is aware of semantic content change. Using Contextual Stochastic Block Models (CSBMs) and real-world graphs, our results uncover: i) for a majority of nodes the prevalent perturbation models include a large fraction of perturbed graphs violating the unchanged semantics assumption; ii) surprisingly, all assessed GNNs show over-robustness - that is robustness beyond the point of semantic change. We find this to be a complementary phenomenon to adversarial robustness related to the small degree of nodes and their class membership dependence on the neighbourhood structure.
2021
On Modelling and Solving Green Collaborative Transportation Planning
Lukas Gosch, Matthias Prandtstetter, and Karl F. Doerner
Proceedings of the 8th International Physical Internet Conference IPIC 2021, 2021
This paper presents a new mathematical model for tactical transportation planning in a horizontal collaboration defined by warehouse sharing and the joint organization of transport. The model features intermodal transport, handling and storage capacities, diverse products and realistic tariff structures with volume discounts. Furthermore, it allows for sustainable planning by associating estimated CO2 equivalent (CO2e) emissions to each logistic operation and then either optimize for transportation costs, emissions or both objectives. Subsequently, we derive a mixed-integer formulation for exact solution approaches and a hybrid heuristic to solve large-scale instances. The hybrid heuristic is composed of a slope scaling matheuristic we generalized to non-negative integer variables and a second local search based refinement step, which reroutes flow of multiple products at once along lowest-cost paths in the network. Results obtained from simulating collaboration in the Danube Region using the regional available transportation infrastructure including railway and shipping networks reveal significant saving potentials in both costs and CO2e emissions. Cost minimizing solutions always lead to reductions of the carbon footprint. However, minimizing for emissions can significantly further this reduction but requires a minimum size of the collaboration to operate cost-efficiently.
2020
DeepNOG: fast and accurate protein orthologous group assignment
Roman Feldbauer, Lukas Gosch, Lukas Lüftinger, and
3 more authors
Protein orthologous group databases are powerful tools for evolutionary analysis, functional annotation or metabolic pathway modeling across lineages. Sequences are typically assigned to orthologous groups with alignment-based methods, such as profile hidden Markov models, which have become a computational bottleneck.We present DeepNOG, an extremely fast and accurate, alignment-free orthology assignment method based on deep convolutional networks. We compare DeepNOG against state-of-the-art alignment-based (HMMER, DIAMOND) and alignment-free methods (DeepFam) on two orthology databases (COG, eggNOG 5). DeepNOG can be scaled to large orthology databases like eggNOG, for which it outperforms DeepFam in terms of precision and recall by large margins. While alignment-based methods still provide the most accurate assignments among the investigated methods, computing time of DeepNOG is an order of magnitude lower on CPUs. Optional GPU usage further increases throughput massively. A command-line tool enables rapid adoption by users.Source code and packages are freely available at https://github.com/univieCUBE/deepnog. Install the platform-independent Python program with \$pip install deepnog.Supplementary data are available at Bioinformatics online.