Aleksandar Bojchevski

Hi, I’m Aleks I’m a tenure-track faculty at the CISPA Helmholtz Center for Information Security. I’m broadly interested in trustworthy machine learning, that is models and algorithms that are not only accurate or efficient but also robust, privacy-preserving, fair, uncertainty-aware, interpretable, etc.

I completed my PhD on machine learning for graphs at the DAML group at TU Munich, advised by Stephan Günnemann. I have a MSc in computer science from TU Munich where I worked at Rostlab on natural language mutation mentions.

Research interests: adversarial robustness, provable guarantees, fairness, privacy-preserving machine learning, uncertainty estimation, interpretability, graph neural networks, graph representation learning, and (deep) generative models. If you are interested in working with us on these (or adjacent) topics don’t hesitate to get in touch. We have multiple open positions!

news

Sep 22	Two papers on robustness, one on adaptive attacks and one on robustness certificates, were accepted at NeurIPS 2022.
Sep 22	This semester I am co-teaching the Elements of Machine Learning lecture with Prof. Jilles Vreeken.
Jan 22	Our paper on generalization of combinatorial solvers was accepted at ICLR 2022.
Oct 21	This semester I am teaching the Trustworthy Graph Neural Networks seminar.
Sep 21	Our paper on robustness of GNNs at scale was accepted at NeurIPS 2021.
Sep 21	I have joined CISPA as a tenure-track faculty . We have multiple open positions!
Jun 21	I gave a talk on Trustworthy Machine Learning for Graphs with Guarantees at the Math of AI Seminar @ LMU.
Mar 21	I gave a talk on Trustworthy Machine Learning for Graphs at CISPA.
Mar 21	I gave a talk on Provably Robust Machine Learning on Graphs at NEC Labs Europe.
Feb 21	Our paper on the curse of dimensionality for randomized smoothing was accepted at AISTATS 2021.

selected publications [full list]

NeurIPS

Are Defenses for Graph Neural Networks Robust?

Felix Mujkanovic, Simon Geisler, Stephan Günnemann, and Aleksandar Bojchevski

In Neural Information Processing Systems, NeurIPS 2022

Abs

A cursory reading of the literature suggests that we made a lot of progress in designing effective adversarial defenses for Graph Neural Networks (GNNs). Yet, the standard methodology has a serious flaw – virtually all of the defenses are evaluated against non-adaptive attacks leading to overly optimistic robustness estimates. We perform a thorough robustness analysis of 7 of the most popular defenses spanning the entire spectrum of strategies, i.e. aimed at improving the graph, the architecture, or the training. The results are sobering – most defenses show no or only marginal improvement compared to an undefended baseline. We advocate using custom adaptive attacks as a gold standard and we outline the lessons we learned from successfully designing such attacks. Moreover, our diverse collection of perturbed graphs forms a (black-box) unit test offering a first glance at a model’s robustness.
ICLR

Collective Robustness Certificates: Exploiting Interdependence in Graph Neural Networks

Jan Schuchardt, Aleksandar Bojchevski, Johannes Klicpera, and Stephan Günnemann

In International Conference on Learning Representations, ICLR 2021

Abs HTML PDF Code Poster Slides Talk

In tasks like node classification, image segmentation, and named-entity recognition we have a classifier that simultaneously outputs multiple predictions (a vector of labels) based on a single input, i.e. a single graph, image, or document respectively. Existing adversarial robustness certificates consider each prediction independently and are thus overly pessimistic for such tasks. They implicitly assume that an adversary can use different perturbed inputs to attack different predictions, ignoring the fact that we have a single shared input. We propose the first collective robustness certificate which computes the number of predictions that are simultaneously guaranteed to remain stable under perturbation, i.e. cannot be attacked. We focus on Graph Neural Networks and leverage their locality property - perturbations only affect the predictions in a close neighborhood - to fuse multiple single-node certificates into a drastically stronger collective certificate. For example, on the Citeseer dataset our collective certificate for node classification increases the average number of certifiable feature perturbations from 7 to 351.
ICML

Efficient Robustness Certificates for Discrete Data: Sparsity-Aware Randomized Smoothing for Graphs, Images and More

Aleksandar Bojchevski, Johannes Klicpera, and Stephan Günnemann

In International Conference on Machine Learning, ICML 2020

Abs arXiv Code Slides Talk

Existing techniques for certifying the robustness of models for discrete data either work only for a small class of models or are general at the expense of efficiency or tightness. Moreover, they do not account for sparsity in the input which, as our findings show, is often essential for obtaining non-trivial guarantees. We propose a model-agnostic certificate based on the randomized smoothing framework which subsumes earlier work and is tight, efficient, and sparsity-aware. Its computational complexity does not depend on the number of discrete categories or the dimension of the input (e.g. the graph size), making it highly scalable. We show the effectiveness of our approach on a wide variety of models, datasets, and tasks – specifically highlighting its use for Graph Neural Networks. So far, obtaining provable guarantees for GNNs has been difficult due to the discrete and non-i.i.d. nature of graph data. Our method can certify any GNN and handles perturbations to both the graph structure and the node attributes.
NeurIPS

Certifiable Robustness to Graph Perturbations

Aleksandar Bojchevski, and Stephan Günnemann

In Neural Information Processing Systems, NeurIPS 2019

Abs arXiv Code Poster

Despite the exploding interest in graph neural networks there has been little effort to verify and improve their robustness. This is even more alarming given recent findings showing that they are extremely vulnerable to adversarial attacks on both the graph structure and the node attributes. We propose the first method for verifying certifiable (non-)robustness to graph perturbations for a general class of models that includes graph neural networks and label/feature propagation. By exploiting connections to PageRank and Markov decision processes our certificates can be efficiently (and under many threat models exactly) computed. Furthermore, we investigate robust training procedures that increase the number of certifiably robust nodes while maintaining or improving the clean predictive accuracy.
ICML Oral

Adversarial Attacks on Node Embeddings via Graph Poisoning

Aleksandar Bojchevski, and Stephan Günnemann

In International Conference on Machine Learning, ICML 2019

Abs arXiv Code Poster Slides Talk

The goal of network representation learning is to learn low-dimensional node embeddings that capture the graph structure and are useful for solving downstream tasks. However, despite the proliferation of such methods, there is currently no study of their robustness to adversarial attacks. We provide the first adversarial vulnerability analysis on the widely used family of methods based on random walks. We derive efficient adversarial perturbations that poison the network structure and have a negative effect on both the quality of the embeddings and the downstream tasks. We further show that our attacks are transferable since they generalize to many models and are successful even when the attacker is restricted.