Transformers are the basis of modern large language models, but relatively little is known about their precise expressive power on graphs. We study the expressive power of graph transformers (GTs) by Dwivedi and Bresson (2020) and GPS-networks by Rampásek et al. (2022), both under soft-attention and average hard-attention. Our study covers two scenarios: the theoretical setting with real numbers and the more practical case with floats. With reals, we show that in restriction to vertex properties definable in first-order logic (FO), GPS-networks have the same expressive power as graded modal logic (GML) with the global modality. With floats, GPS-networks turn out to be equally expressive as GML with the counting global modality. The latter result is absolute, not restricting to properties definable in a background logic. We also obtain similar characterizations for GTs in terms of propositional logic with the global modality (for reals) and the counting global modality (for floats).

Abstract We investigate the expressive power of neural networks from the point of view of descriptive complexity. We study neural networks that use floating-point numbers and piecewise polynomial activation functions from two perspectives: (i) the general scenario where neural networks run for an unlimited number of computation steps and have unrestricted topologies, and (ii) classical feedforward neural networks that have the topology of layered acyclic graphs and run for only a constant number of computation steps. We characterize these neural networks via Boolean networks formalized via a recursive rule-based logic. In particular, we show that the sizes of the neural networks and the corresponding Boolean rule formulae are polynomially related. In fact, in the translation from Boolean rules to neural networks, the blow-up is only linear. Our translations result in a time delay, defined as the number of computation steps that the output-object of the translation (e.g. a neural network or Boolean rule formula) uses to simulate a single computation step of the input-object. In the translation from neural networks to Boolean rules, the time delay of the resulting formula is polylogarithmic in the size of the neural network. In the converse translation, the time delay of the neural network is linear in the formula size. Ultimately, we obtain translations between neural networks, Boolean networks, the diamond-free fragment of modal substitution calculus and a class of recursive Boolean circuits. Our translations offer a method, for almost any activation function F, of translating any neural network in our setting into an equivalent neural network that uses F at each node. This even includes linear activation functions, which is possible due to using floats rather than actual reals!

Abstract We investigate distributed computing with identifiers in the realistic scenario where the local computations in a distributed message passing setting are operated by Boolean circuits. We call this framework the message passing circuit model. We capture the expressive power of the model with a recursive rule-based logic called modal substitution calculus MSC. The result is established via constructing translations that are highly efficient in relation to size and computation time. In particular, the worst size blow-up is quadratic and becomes linear in the bounded-degree scenario. Computation time delays are similarly modest. As a concrete demonstration of how our setting works, we establish that a very fast coloring algorithm based on Cole–Vishkin can be specified by logarithmic size programs (and thus also logarithmic size circuits) in the bounded-degree scenario.

We investigate the expressive power of neural networks from the point of view of descriptive complexity. We study neural networks that use floating-point numbers and piecewise polynomial activation functions from two perspectives: 1) the general scenario where neural networks run for an unlimited number of rounds and have unrestricted topologies, and 2) classical feedforward neural networks that have the topology of layered acyclic graphs and run for only a constant number of rounds. We characterize these neural networks via Boolean networks formalized via a recursive rule-based logic. In particular, we show that the sizes of the neural networks and the corresponding Boolean rule formulae are polynomially related. In fact, in the direction from Boolean rules to neural networks, the blow-up is only linear. Our translations result in a time delay, which is the number of rounds that it takes to simulate a single computation step. In the translation from neural networks to Boolean rules, the time delay of the resulting formula is polylogarithmic in the size of the neural network. In the converse translation, the time delay of the neural network is linear in the formula size. Ultimately, we obtain translations between neural networks, Boolean networks, the diamond-free fragment of modal substitution calculus, and a class of recursive Boolean circuits. Our translations offer a method, for almost any activation function F, of translating any neural network in our setting into an equivalent neural network that uses F at each node. This even includes linear activation functions, which is possible due to using floats rather than actual reals!

In pioneering work from 2019, Barceló and coauthors identified logics that precisely match the expressive power of constant iteration-depth graph neural networks (GNNs) relative to properties definable in first-order logic. In this article, we give exact logical characterizations of recurrent GNNs in two scenarios: (1) in the setting with floating-point numbers and (2) with reals. For floats, the formalism matching recurrent GNNs is a rule-based modal logic with counting, while for reals we use a suitable infinitary modal logic, also with counting. These results give exact matches between logics and GNNs in the recurrent setting without relativising to a background logic in either case, but using some natural assumptions about floating-point arithmetic. Applying our characterizations, we also prove that, relative to graph properties definable in monadic second-order logic (MSO), our infinitary and rule-based logics are equally expressive. This implies that recurrent GNNs with reals and floats have the same expressive power over MSO-definable properties and shows that, for such properties, also recurrent GNNs with reals are characterized by a (finitary!) rule-based modal logic. In the general case, in contrast, the expressive power with floats is weaker than with reals. In addition to logic-oriented results, we also characterize recurrent GNNs, with both reals and floats, via distributed automata, drawing links to distributed computing models.

We consider distributed algorithms in the realistic scenario where distributed message passing is operated by circuits. We show that within this setting, modal substitution calculus MSC precisely captures the expressive power of circuits. The result is established via constructing translations that are highly efficient in relation to size. We also observe that the coloring algorithm based on Cole-Vishkin can be specified by logarithmic size programs (and thus also logarithmic size circuits) in the bounded-degree scenario.