Aleksandar Bojchevski

I am a full professor for Computer Science at the University of Cologne where I lead the research group on Trustworthy Artificial Intelligence. Broadly speaking our 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 our 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

Dec '23	I attended the Dagstuhl seminar on Scalabale Graph Mining and Learning.
Sep '23	Two papers, one on certificates and one on GATs, were accepted at NeurIPS 2023.
Sep '23	I joined the Center for Data and Simulation Science as a core scientist.
Apr '23	One paper on conformal predictions sets for GNNs was accepted at ICML 2023.
Apr '23	Our group joined the key profile area “Intelligent Methods for Earth System Sciences”.
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.

selected publications [full list]

ICML

Conformal Prediction Sets for Graph Neural Networks

Soroush H. Zargarbashi, Simone Antonelli, and Aleksandar Bojchevski

In International Conference on Machine Learning, ICML 2023

Abs HTML PDF Code

Despite the widespread use of graph neural networks (GNNs) we lack methods to reliably quantify their uncertainty. We propose a conformal procedure to equip GNNs with prediction sets that come with distribution-free guarantees – the output set contains the true label with arbitrarily high probability. Our post-processing procedure can wrap around any (pretrained) GNN, and unlike existing methods, results in meaningful sets even when the model provides only the top class. The key idea is to diffuse the node-wise conformity scores to incorporate neighborhood information. By leveraging the network homophily we construct sets with comparable or better efficiency (average size) and significantly improved singleton hit ratio (correct sets of size one). In addition to an extensive empirical evaluation, we investigate the theoretical conditions under which smoothing provably improves efficiency.
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.