  Graph kernels based on the $1$-dimensional Weisfeiler-Leman algorithm and
corresponding neural architectures recently emerged as powerful tools for
(supervised) learning with graphs. However, due to the purely local nature of
the algorithms, they might miss essential patterns in the given data and can
only handle binary relations. The $k$-dimensional Weisfeiler-Leman algorithm
addresses this by considering $k$-tuples, defined over the set of vertices, and
defines a suitable notion of adjacency between these vertex tuples. Hence, it
accounts for the higher-order interactions between vertices. However, it does
not scale and may suffer from overfitting when used in a machine learning
setting. Hence, it remains an important open problem to design WL-based graph
learning methods that are simultaneously expressive, scalable, and
non-overfitting. Here, we propose local variants and corresponding neural
architectures, which consider a subset of the original neighborhood, making
them more scalable, and less prone to overfitting. The expressive power of (one
of) our algorithms is strictly higher than the original algorithm, in terms of
ability to distinguish non-isomorphic graphs. Our experimental study confirms
that the local algorithms, both kernel and neural architectures, lead to vastly
reduced computation times, and prevent overfitting. The kernel version
establishes a new state-of-the-art for graph classification on a wide range of
benchmark datasets, while the neural version shows promising performance on
large-scale molecular regression tasks.
