Weisfeiler–Leman for embedded graphs: Topological message passing on surfaces

We study message passing architectures for graphs embedded on surfaces and thereby connect graph machine learning with topological graph theory. While previous Topological Deep Learning methods study the intrinsic topology of graphs/complexes determined by their combinatorics, we make use of the topology of their embeddings and position our approach between the abstract combinatorial and the explicit geometric settings. This is relevant for many application areas such as drug design. On the one hand, the pure connectivity information of molecules is often not sufficient for chemically interesting predictions; on the other hand, the full 3D structure is not needed and can in many cases hinder learning. For graphs on surfaces, we propose three methods to exploit the embedding via its induced rotation system. We prove the following: (i) Sparse cyclic aggregations identify all embedded trees, (ii) Dense, with a ternary relations on the vertices identify all embedded graphs at dimension three and not below, (iii) Binary relations on the oriented edges achieve the same result already at dimension two. Finally, we fully characterize how these methods compare in expressivity. We propose graph neural networks motivated by these results and evaluate them on topological property prediction tasks and chirality-sensitive molecular tasks. Our experiments show that our approach is not only theoretically interesting but also practically relevant.