§5.3, eq. (35), pp. 78–79 — the message-passing GNN layer is permutation equivariant
ProvedGeomDL.EGNN.eq_35_perm_equivariantgeometric-deep-learninggraph-neural-networkp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-bookp2o-v1permutation-equivariance
Let be an adjacency matrix with neighbourhoods , let assign a feature to each node , and let be the message-passing layer (35),
for arbitrary functions , and an arbitrary aggregator of the multiset of messages. Then for every permutation of the nodes, with permutation matrix ,
This is the equivariance property (10) of §4.1 for the message-passing flavour, the property the book requires of every GNN layer it studies.
Formalization Note Row of is row of , and . The aggregator is any function of a multiset, which is how the book's "permutation-invariant function " is encoded.
Preamble
import Mathlib import Definitions.Def_GeomDL_EGNN_Defs
Formal statement
namespace GeomDL.EGNN
/-- §5.3, pp. 78–79: the message-passing layer (35), `h_u = φ(x_u, ⊕_{v ∈ N_u} ψ(x_u, x_v))`,
is permutation equivariant in the sense of (10): `F(PX, PAPᵀ) = P F(X, A)` for every
permutation `σ` (convention: row `u` of `PX` is row `σ⁻¹(u)` of `X`). -/
theorem eq_35_perm_equivariant {n : ℕ} {α M M' β : Type*} (φ : α → M' → β)
(agg : Multiset M → M') (ψ : α → α → M) (σ : Equiv.Perm (Fin n)) (X : Fin n → α)
(A : Matrix (Fin n) (Fin n) ℝ) :
mpLayer φ agg ψ (permRows σ X) (GeomDL.Sets.permAdj σ A) = permRows σ (mpLayer φ agg ψ X A) := by sorry
end GeomDL.EGNN
Source
Bronstein et al., Geometric Deep Learning (arXiv:2104.13478v2), §5.3, p. 78 ("permutation equivariant functions F(X, A) constructed by applying shared permutation invariant functions") and eq. (35), p. 79; property (10), §4.1, p. 33
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.