The Boolean Power of ReLU

We prove that, on finite simple undirected graphs equipped with a single Boolean node feature, the Boolean queries expressible in Σ-MPLang, for any collection Σ of eventually constant activation functions and with arbitrary real coefficients, form a strict subclass of the Boolean queries expressible in ReLU-MPLang. We thereby settle a recently posed open problem: whether ReLU-MPLang is more powerful than TrReLU-MPLang when it comes to Boolean queries. In particular, this implies that ReLU-GNNs are strictly more expressive than TrReLU, id-GNNs with respect to Boolean queries on Boolean-featured graphs.

The paper proves that, on finite simple undirected graphs equipped with a single Boolean node feature, the Boolean queries expressible in Σ-MPLang, for any collection Σ of eventually constant activation functions and with arbitrary real coefficients, form a strict subclass of the Boolean queries expressible in ReLU-MPLang. This settles a recently posed open problem: whether ReLU-MPLang is more powerful than TrReLU-MPLang when it comes to Boolean queries. In particular, this implies that ReLU-GNNs are strictly more expressive than TrReLU, id-GNNs with respect to Boolean queries on Boolean-featured graphs.

The main theorem states: "Let Σ be any collection of eventually constant activation functions. There exists a ReLU-MPLang expression E⋆ such that no Σ-MPLang expression (with arbitrary real coefficients) is Boolean equivalent to it on the class of finite graphs with a single Boolean feature. As a corollary, On finite Boolean-featured graphs, bool(TrReLU-MPLang) ⊊ bool(ReLU-MPLang), and this holds already on graphs with a single Boolean feature."

The separating expression is defined as:

E⋆:= +ReLU(2+P − +1 + 1) − +1 + 4

Its Booleanisation tests, at a node v:

(E⋆)B(G)(v) = 1 ⇐⇒ Σ w∈N(v) max 0, 2·# x ∈ N(w): P(x) = 1 − deg(w) + 1 − deg(v) + 4 > 0.

The proof strategy evaluates expressions on a three-parameter family of graphs GN(u1, u2, α), whose nodes fall into classes that are indistinguishable to Σ-MPLang expressions. On one distinguished node class, denoted O, the expression E⋆ takes the value 2N(u1 + u2 − α) and thus detects on which side of the plane u1 + u2 = α the parameters lie. By contrast, every expression built from eventually constant activations becomes asymptotically local: for all sufficiently large admissible N, its value on O depends only on N and α, not on u1 or u2. Choosing two nearby rational parameter points with the same α but lying on opposite sides of the plane u1 + u2 = α yields two graphs on which any candidate expression takes the same value at O, whereas E⋆ takes values of opposite sign.

The graph family GN(u1, u2, α) is constructed as follows. Let Θ:= (1/4, 1/3) × (1/2, 2/3) and consider θ = (u1, u2, α) ∈ Θ. For rational θ ∈ Θ, an integer N ≥ 1 is θ-admissible if Nu1, Nu2 and 2Nα are integers. Put ri = N(1 + ui), bi = N(1 − ui), t = 2Nα. Then 0 < bi < N < ri < 2N, N < t < 2N, ri + bi = 2N, ri − bi = 2Nui. Take five disjoint classes, each of size 2N: O, W1+, W1−, W2+, W2−. Using regular gadgets, place a t-regular graph inside O, an ri-regular graph inside each Wi±, a bi-regular bipartite gadget between Wi+ and Wi−, and a perfect matching between O and each Wi±. Set the Boolean node feature to P = 1 on W1+ ∪ W2+, P = 0 elsewhere.

A key lemma shows that for every Σ-MPLang expression h, the map h(GN(θ))(·) is constant on each of the five classes. The partition C = O, W1+, W1−, W2+, W2− is equitable, with quotient matrix:

D = [[t, 1, 1, 1, 1], [1, r1, b1, 0, 0], [1, b1, r1, 0, 0], [1, 0, 0, r2, b2], [1, 0, 0, b2, r2]]

In particular, deg(v) = t + 4 for v ∈ O, and deg(v) = ri + bi + 1 = 2N + 1 for v ∈ Wi±.

The paper defines cylindrical polynomials as those in R[α], R[u1, α], or R[u2, α] — never involving both u1 and u2. Sign decompositions partition Θ into cells where each cylindrical polynomial has a fixed sign. Local vectors are class-vectors q = (qO, qW1+, qW1−, qW2+, qW2−) of polynomials in N, u1, u2, α such that qO, w1(q), w2(q) ∈ A0 and qWi± ∈ Ai, where A0 = R + N·R[N, α] and Ai = R + N·R[N, ui, α]. An expression h is asymptotically local if there exist a finite set Ph of nonzero cylindrical polynomials and, for each sign assignment s on Ph with nonempty cell Θs, a local class-vector Φs such that for every rational θ ∈ Θs there is a threshold N0(h, θ) with hX(N, θ) = ΦsX(N, θ) for every class X and every θ-admissible N ≥ N0(h, θ).

The proof of the main theorem uses the fact that if h is asymptotically local then, on each cell Θs, there is a single polynomial Fs:= ΦsO ∈ A0 ⊆ R[N, α], mentioning neither u1 nor u2, with h(GN(θ))(o) = Fs(N, α) for all o ∈ O, all rational θ ∈ Θs, all admissible N ≥ N0(h, θ). The proof selects a base point on the critical surface α = u1 + u2 where all polynomials in P are nonzero, then creates two nearby rational points θ− and θ+ on opposite sides of the critical surface yet inside one cell. Choosing a common admissible N large enough, any candidate expression f takes the same value at O on both graphs, while E⋆ takes values of opposite signs (∓2Nε), contradicting Boolean equivalence.

The final section proves that every Σ-MPLang expression is asymptotically local whenever all activations in Σ are eventually constant, by structural induction. The base cases (1 and P) are trivially local. Linear cases preserve locality since the classes A0, Ai and pair-sum conditions are closed under linear combinations. The aggregation case uses the quotient adjacency operator D: (Dq)O = 2Nα·qO + w1(q) + w2(q), wi(Dq) = 2qO + 2N·wi(q), and (Dq)Wi± = qO + N(1±ui)·qWi+ + N(1∓ui)·qWi−, which preserves locality. The activation case for eventually constant σ enlarges Ph by all nonzero coefficients aX,k of the leading terms; on each cell, the argument either is a parameter-free constant or diverges to +∞ or −∞, so σ(h1)X becomes eventually constant (either σ(cX), C+σ, or C−σ), yielding a local constant vector.

Based on the paper, here are specific improvements for AI systems, particularly graph neural networks (GNNs) and message-passing models:

1. Expressive Power Hierarchy for Activation Functions

• Improvement: Implement a formal verification tool that checks whether a given GNN architecture (with specific activation functions) can express certain Boolean queries on graphs. This tool would use the paper's result that ReLU is strictly more expressive than any eventually constant activation (e.g., sigmoid, tanh, hard tanh, ReLU6).

• Improved AI capability: An AI system can now automatically determine if a proposed GNN architecture is provably incapable of solving a given graph classification task (e.g., detecting a specific substructure), saving training time and avoiding false confidence in model performance.

2. Architectural Search with Expressiveness Constraints

• Improvement: Incorporate the paper's separation result into neural architecture search (NAS). The system can prune candidate architectures that use only eventually constant activations when the target task requires Boolean queries that are provably inexpressible by them.

• Improved AI capability: NAS can now guarantee that the final architecture is not limited by activation-function expressiveness, focusing search on ReLU-based or mixed-activation designs that can theoretically solve the task.

3. Benchmark Generation for GNN Evaluation

• Improvement: Use the paper's separating expression E⋆ and graph family G N(u1, u2, α) to generate hard benchmark instances. These graphs have known ground-truth labels (based on the sign of u1+u2−α) that are provably learnable by ReLU-GNNs but not by TrReLU-GNNs.

• Improved AI capability: A benchmark generator can create datasets that rigorously test whether a GNN implementation actually achieves the theoretical expressiveness of its activation functions, exposing subtle bugs or approximation errors in training.

4. Theoretical Guarantees for Graph Query Answering

• Improvement: Build a query-answering system that, given a Boolean graph query, can decide whether it is expressible in Σ-MPLang (eventually constant activations) or requires ReLU. This uses the paper's proof that Σ-MPLang queries become asymptotically local and cannot distinguish certain parameter families.

• Improved AI capability: The system can provide formal certificates of inexpressibility for a query, preventing users from wasting resources on impossible learning tasks and guiding them toward reformulating the query or using more expressive models.

5. Regularization and Initialization for ReLU-GNNs

• Improvement: Leverage the paper's insight that ReLU's non-saturating behavior is crucial for global (non-local) reasoning. Design training regularizers that encourage ReLU-GNNs to maintain non-zero gradients in deep layers, avoiding accidental saturation that would collapse them to eventually constant behavior.

• Improved AI capability: ReLU-GNNs trained with this regularizer will better preserve their theoretical expressiveness advantage, especially on graphs with large diameters or long-range dependencies, where local information is insufficient.

6. Adaptive Activation Selection in Message Passing

• Improvement: Implement a meta-learning system that, for a given graph dataset, automatically selects between ReLU and eventually constant activations per layer, based on the paper's proof that ReLU enables non-local Boolean queries while others only achieve local ones.

• Improved AI capability: The system can dynamically trade off between expressiveness (ReLU) and smoothness/stability (sigmoid/tanh) depending on the task's global vs. local nature, improving both accuracy and training stability.