Aleksandar Bojchevski

I am a tenured professor for Computer Science at the University of Cologne where I lead the research group on Trustworthy Artificial Intelligence. Broadly speaking my research is about models and algorithms that are not only accurate or efficient, but also robust, uncertainty-aware, privacy-preserving, fair, and interpretable. One focus area of my research is trustworthy graph-based models such as graph neural networks. Previously I was faculty at the CISPA Helmholtz Center for Information Security. Before that I did a PostDoc and completed my PhD on machine learning for graphs at the Technical University of Munich, advised by Stephan Günnemann.

We have multiple open positions in our research group on a variety of (trustworthy) machine learning topics.

news

Mar '23	I will join the University of Cologne as a tenured professor for Computer Science.
Jan '23	Our paper on probing graph-based models was accepted at AISTATS.
Jan '23	Two papers accepted at ICLR 2023, one on robustness and one on geometric graphs.
Jan '23	Our paper on adversarial weight perturbation was accepted at AAAI (oral).
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!

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 arXiv Code Talk

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