Thomas Gärtner 0001

ICML Conference 2025 Conference Paper

Probably Approximately Global Robustness Certification

• Peter Blohm
• Patrick Indri
• Thomas Gärtner 0001
• Sagar Malhotra

We propose and investigate probabilistic guarantees for the adversarial robustness of classification algorithms. While traditional formal verification approaches for robustness are intractable and sampling-based approaches do not provide formal guarantees, our approach is able to efficiently certify a probabilistic relaxation of robustness. The key idea is to sample an $\epsilon$-net and invoke a local robustness oracle on the sample. Remarkably, the size of the sample needed to achieve probably approximately global robustness guarantees is independent of the input dimensionality, the number of classes, and the learning algorithm itself. Our approach can, therefore, be applied even to large neural networks that are beyond the scope of traditional formal verification. Experiments empirically confirm that it characterizes robustness better than state-of-the-art sampling-based approaches and scales better than formal methods.

ICML Conference 2025 Conference Paper

WILTing Trees: Interpreting the Distance Between MPNN Embeddings

• Masahiro Negishi
• Thomas Gärtner 0001
• Pascal Welke

We investigate the distance function learned by message passing neural networks (MPNNs) in specific tasks, aiming to capture the functional distance between prediction targets that MPNNs implicitly learn. This contrasts with previous work, which links MPNN distances on arbitrary tasks to structural distances on graphs that ignore task-specific information. To address this gap, we distill the distance between MPNN embeddings into an interpretable graph distance. Our method uses optimal transport on the Weisfeiler Leman Labeling Tree (WILT), where the edge weights reveal subgraphs that strongly influence the distance between embeddings. This approach generalizes two well-known graph kernels and can be computed in linear time. Through extensive experiments, we demonstrate that MPNNs define the relative position of embeddings by focusing on a small set of subgraphs that are known to be functionally important in the domain.

ICML Conference 2024 Conference Paper

The Expressive Power of Path-Based Graph Neural Networks

• Caterina Graziani
• Tamara Drucks
• Fabian Jogl
• Monica Bianchini
• Franco Scarselli
• Thomas Gärtner 0001

We systematically investigate the expressive power of path-based graph neural networks. While it has been shown that path-based graph neural networks can achieve strong empirical results, an investigation into their expressive power is lacking. Therefore, we propose PATH-WL, a general class of color refinement algorithms based on paths and shortest path distance information. We show that PATH-WL is incomparable to a wide range of expressive graph neural networks, can count cycles, and achieves strong empirical results on the notoriously difficult family of strongly regular graphs. Our theoretical results indicate that PATH-WL forms a new hierarchy of highly expressive graph neural networks.

ICML Conference 2023 Conference Paper

Expectation-Complete Graph Representations with Homomorphisms

• Pascal Welke
• Maximilian Thiessen
• Fabian Jogl
• Thomas Gärtner 0001

We investigate novel random graph embeddings that can be computed in expected polynomial time and that are able to distinguish all non-isomorphic graphs in expectation. Previous graph embeddings have limited expressiveness and either cannot distinguish all graphs or cannot be computed efficiently for every graph. To be able to approximate arbitrary functions on graphs, we are interested in efficient alternatives that become arbitrarily expressive with increasing resources. Our approach is based on Lovász’ characterisation of graph isomorphism through an infinite dimensional vector of homomorphism counts. Our empirical evaluation shows competitive results on several benchmark graph learning tasks.

ICML Conference 2019 Conference Paper

Scalable Learning in Reproducing Kernel Krein Spaces

• Dino Oglic
• Thomas Gärtner 0001

We provide the first mathematically complete derivation of the Nystr{ö}m method for low-rank approximation of indefinite kernels and propose an efficient method for finding an approximate eigendecomposition of such kernel matrices. Building on this result, we devise highly scalable methods for learning in reproducing kernel Krein spaces. The devised approaches provide a principled and theoretically well-founded means to tackle large scale learning problems with indefinite kernels. The main motivation for our work comes from problems with structured representations (e. g. , graphs, strings, time-series), where it is relatively easy to devise a pairwise (dis)similarity function based on intuition and/or knowledge of domain experts. Such functions are typically not positive definite and it is often well beyond the expertise of practitioners to verify this condition. The effectiveness of the devised approaches is evaluated empirically using indefinite kernels defined on structured and vectorial data representations.

ICML Conference 2018 Conference Paper

Learning in Reproducing Kernel Krein Spaces

• Dino Oglic
• Thomas Gärtner 0001

We formulate a novel regularized risk minimization problem for learning in reproducing kernel Kre{ı̆}n spaces and show that the strong representer theorem applies to it. As a result of the latter, the learning problem can be expressed as the minimization of a quadratic form over a hypersphere of constant radius. We present an algorithm that can find a globally optimal solution to this non-convex optimization problem in time cubic in the number of instances. Moreover, we derive the gradient of the solution with respect to its hyperparameters and, in this way, provide means for efficient hyperparameter tuning. The approach comes with a generalization bound expressed in terms of the Rademacher complexity of the corresponding hypothesis space. The major advantage over standard kernel methods is the ability to learn with various domain specific similarity measures for which positive definiteness does not hold or is difficult to establish. The approach is evaluated empirically using indefinite kernels defined on structured as well as vectorial data. The empirical results demonstrate a superior performance of our approach over the state-of-the-art baselines.

ICML Conference 2017 Conference Paper

Nyström Method with Kernel K-means++ Samples as Landmarks

• Dino Oglic
• Thomas Gärtner 0001

We investigate, theoretically and empirically, the effectiveness of kernel K-means++ samples as landmarks in the Nyström method for low-rank approximation of kernel matrices. Previous empirical studies (Zhang et al. , 2008; Kumar et al. ,2012) observe that the landmarks obtained using (kernel) K-means clustering define a good low-rank approximation of kernel matrices. However, the existing work does not provide a theoretical guarantee on the approximation error for this approach to landmark selection. We close this gap and provide the first bound on the approximation error of the Nyström method with kernel K-means++ samples as landmarks. Moreover, for the frequently used Gaussian kernel we provide a theoretically sound motivation for performing Lloyd refinements of kernel K-means++ landmarks in the instance space. We substantiate our theoretical results empirically by comparing the approach to several state-of-the-art algorithms.

UAI Conference 2009 Conference Paper

Probabilistic Structured Predictors

• Shankar Vembu
• Thomas Gärtner 0001
• Mario Boley

1 estimation by imposing a normal prior on θ. This leads to optimising the negative joint likelihood in θ and Y: We consider MAP estimators for structured prediction with exponential family models. In particular, we concentrate on the case that efficient algorithms for uniform sampling from the output space exist. We show that under this assumption (i) exact computation of the partition function remains a hard problem, and (ii) the partition function and the gradient of the log partition function can be approximated efficiently. Our main result is an approximation scheme for the partition function based on Markov Chain Monte Carlo theory. We also show that the efficient uniform sampling assumption holds in several application settings that are of importance in machine learning. θ̂ = argmin [− ln p(θ, Y |X)] θ " # m X 1 = argmin λkθk2 + [ln Z(θ|xi ) − hφ(xi, yi ), θi], m i=1 θ (1) where λ > 0 is the regularisation parameter. Throughout this paper, we assume that the `2 norm of the sufficient statistics and the parameters are bounded, i. e. , kφ(x, y)k ≤ R and kθk ≤ B, where R and B are constants (note that B can be bounded from above as shown in Appendix C). The difficulty in solving (1) lies in the computation of the partition function. The optimisation is typically performed using gradient descent techniques (and advancements thereof). We therefore also need to compute the gradient of the log partition function, which is the first order moment of the sufficient statistics, i. e. , ∇θ ln Z(θ|x) = Ey∼p(y|x, θ) [φ(x, y)].

ICML Conference 2006 Conference Paper

Efficient co-regularised least squares regression

• Ulf Brefeld
• Thomas Gärtner 0001
• Tobias Scheffer
• Stefan Wrobel

In many applications, unlabelled examples are inexpensive and easy to obtain. Semi-supervised approaches try to utilise such examples to reduce the predictive error. In this paper, we investigate a semi-supervised least squares regression algorithm based on the co-learning approach. Similar to other semi-supervised algorithms, our base algorithm has cubic runtime complexity in the number of unlabelled examples. To be able to handle larger sets of unlabelled examples, we devise a semi-parametric variant that scales linearly in the number of unlabelled examples. Experiments show a significant error reduction by co-regularisation and a large runtime improvement for the semi-parametric approximation. Last but not least, we propose a distributed procedure that can be applied without collecting all data at a single site.

ICML Conference 2006 Conference Paper

Simpler knowledge-based support vector machines

• Quoc V. Le
• Alexander J. Smola
• Thomas Gärtner 0001

ICML Conference 2002 Conference Paper

Multi-Instance Kernels

• Thomas Gärtner 0001
• Peter A. Flach
• Adam Kowalczyk
• Alexander J. Smola

ICML Conference 2001 Conference Paper

WBCsvm: Weighted Bayesian Classification based on Support Vector Machines

• Thomas Gärtner 0001
• Peter A. Flach