On Graph Transformer Expressivity: A Monadic Second-Order Perspective

We characterize the expressive power of graph transformers by showing that transformers express monadic second-order logic (MSO) for bounded-treewidth graphs. MSO is a powerful logic for graph-related tasks, as it allows to decide many problems for graphs with bounded treewidth in linear fixed-parameter-tractable (FPT) time, such as connectivity, planarity, and $p$-colorability for fixed $p$. The expressive power of general transformers is often quantified by their ability to simulate certain formal languages in the context of natural language processing. In this paper, we focus on graph representation learning and MSO: We show that transformers with $\log n$-precision and average-hard attention can produce distinct embeddings for bounded-treewidth graphs that differ in MSO-definable properties in near-linear FPT time if the tree decomposition is given as input, and in near-cubic FPT time if the tree decomposition is not given. We establish this expressivity lower bound by showing that transformers have sufficient expressive power to compute bounded-width tree decompositions and simulate tree automata for graphs equipped with simple structural encodings. Our proofs are constructive and provide upper bounds on the required size of the transformers, scaling with the size of the input graph, the treewidth as well as the length of the MSO formula.