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.
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.
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.