The Descriptive Complexity of Graph Neural Networks

We analyse the power of graph neural networks (GNNs) in terms of Boolean circuit complexity and descriptive complexity.

We prove that the graph queries that can be computed by a polynomial-size boundeddepth family of GNNs are exactly those definable in the guarded fragment GFO+C of first-order logic with counting and with built-in relations. This puts GNNs in the circuit complexity class (non-uniform) TC 0 . Remarkably, the GNN families may use arbitrary real weights and a wide class of activation functions that includes the standard ReLU, logistic "sigmoid", and hyperbolic tangent functions. If the GNNs are allowed to use random initialisation and global readout (both standard features of GNNs widely used in practice), they can compute exactly the same queries as bounded depth Boolean circuits with threshold gates, that is, exactly the queries in TC 0 . Moreover, we show that queries computable by a single GNN with piecewise linear activations and rational weights are definable in GFO+C without built-in relations. Therefore, they are contained in uniform TC 0 .

M. Grohe parameters 𝑎 𝑖 , 𝑏 𝑖 , 𝑡 𝑖 in the minimal representation are dyadic rationals. 1 If 𝐿 is rational, then its bitsize of bsize(𝐿) is the sum of the bitsizes of all the parameters 𝑎 𝑖 , 𝑏 𝑖 , 𝑡 𝑖 of the minimal representation. Oberserve that if 𝐿 is continuous then it is Lipschitz continuous with Lipschitz constant max 0≤𝑖≤𝑛 𝑎 𝑖 .

E X A M P L E 2 .1. The most important example of a rational piecewise linear function for us is the rectified linear unit relu ∶ R → R defined by relu(𝑥) max0, 𝑥.

In fact, it is not hard to see that every piecewise linear function can be written as a linear combination of relu-terms. For example, the identity function id(𝑥) = 𝑥 can be written as relu(𝑥)relu(-𝑥), and the linearised sigmoid function lsig ∶ R → R, defined by lsig(𝑥

∎

We need a notion of approximation between functions on the reals. Let 𝑓 , 𝑔 ∶ R → R and

Note that we allow for both an additive and a multiplicative approximation error. This notion of approximation is not symmetric, but if 𝑔 𝜀-approximates 𝑓 for some 𝜀 < 1 then 𝑓 𝜀 1-𝜀 -approximates 𝑔. The main reason we need to allow for a multiplicative approximation error is that we want to approximate linear functions with irrational coefficients by linear functions with rational coefficients. We call a function 𝑓 ∶ R → R rpl-approximable if for every 𝜀 > 0 there is a continuous rational piecewise linear function 𝐿 of bitsize polynomial in 𝜀 -1 that 𝜀-approximates 𝑓 . E X A M P L E 2 . 2. The logistic function sig(𝑥) = 1 1+𝑒 -𝑥 and the hyperbolic tangent tanh(𝑥) = 𝑒 𝑥 -𝑒 -𝑥 𝑒 𝑥 +𝑒 -𝑥 are rpl-approximable. Examples of unbounded rpl-approximable functions are the soft plus function ln(1 + 𝑒 𝑥 ) and the exponential linear units defined by elu 𝛼 (𝑐) = 𝑥 if 𝑥 > 0 and 𝛼(𝑒 𝑥 -1) if 𝑥 ≤ 0, where 𝛼 > 0 is a constant. We omit the straightforward proofs based on simple calculus. ∎ E X A M P L E 2 . 3. Examples of functions that are not rpl approximable are functions that are not Lipschitz continuous, such as the square function, and periodic functions such as the sine or cosine functions.

∎

Graphs play two different roles in this article: they are the basic data structures on which logics and graph neural networks operate, and they form the skeleton of Boolean circuits and 1 Throughout this article we work with dyadic rationals. For this reason, we are a little sloppy in our terminology. For example, we call a function "rational piecewise linear" when the more precise term would be "dyadic-rational piecwise linear".