§5.3, pp. 79–80 — representational containment: convolution ⊆ attention ⊆ message passing
ProvedGeomDL.EGNN.conv_subset_att_subset_mpFix a graph with adjacency matrix and neighbourhoods , node features , an update , a feature map and an aggregator . Then:
- for every attention mechanism , the attentional layer (34) equals the message-passing layer (35) with messages ;
- if the features identify the nodes ( injective), then for every coefficient matrix there is an attention mechanism (a look-up table with ) for which the convolutional layer (33) equals the attentional layer (34);
- under the same hypothesis, for every there is a message function (with ) for which (33) equals (35).
In symbols, writing , , for the three layers on the same input,
This is the book's "convolution ⊆ attention ⊆ message-passing": the message-passing flavour is the most expressive of the three.
Formalization Note The injectivity hypothesis in parts 2 and 3 is added and is necessary: an attention mechanism or message function sees only features, so if two nodes have equal features but for , no look-up table exists (a two-node counterexample is checked in Lean). Part 1 needs no hypothesis. The coefficients act on the messages through a scalar multiplication SMul ℝ M.
import Mathlib import Definitions.Def_GeomDL_EGNN_Defs
namespace GeomDL.EGNN
/-- §5.3, pp. 79–80: the containment "convolution ⊆ attention ⊆ message-passing".
(1) Every attentional layer (34) is the message-passing layer (35) with messages
`ψ(x_u, x_v) = a(x_u, x_v) ψ(x_v)`. (2) On features that identify the nodes (`u ↦ x_u`
injective), the convolutional layer (33) with coefficients `c_{uv}` equals an attentional layer
whose attention is a look-up table `a(x_u, x_v) = c_{uv}`, and (3) equals a message-passing
layer with messages `ψ'(x_u, x_v) = c_{uv} ψ(x_v)`. -/
theorem conv_subset_att_subset_mp {n : ℕ} {α M M' β : Type*} [SMul ℝ M]
(φ : α → M' → β) (agg : Multiset M → M') (ψ : α → M) (X : Fin n → α)
(A : Matrix (Fin n) (Fin n) ℝ) :
(∀ a : α → α → ℝ,
attLayer φ agg a ψ X A = mpLayer φ agg (fun xu xv => a xu xv • ψ xv) X A) ∧
(Function.Injective X → ∀ c : Matrix (Fin n) (Fin n) ℝ,
∃ a : α → α → ℝ, convLayer φ agg c ψ X A = attLayer φ agg a ψ X A) ∧
(Function.Injective X → ∀ c : Matrix (Fin n) (Fin n) ℝ,
∃ ψ' : α → α → M, convLayer φ agg c ψ X A = mpLayer φ agg ψ' X A) := by sorry
end GeomDL.EGNN
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.