Md. Asif Uddin

Chapter 14 I.14

Graph Neural Networks

Message passing is permutation-equivariant, and no amount of it can distinguish graphs that the 1-WL test cannot.

Each node repeatedly summarises its neighbours; after k rounds it knows its k-hop neighbourhood.

How this chapter is built

M3Load-bearing

The content is mathematics. Understanding is demonstrated by computation, not recall.

basics3/11what the words mean
concept2/2what to picture
theory0/4why it works, and when it does not
mathematics0/15derive it, then compute it
practice0/9build it, break it, read the papers

Five strands, not one. Mathematics is the spine; the other four are the body. A chapter cannot pay its way out of teaching with problems, nor out of problems with teaching.

Before you start

The problem

Grids and sequences are graphs with a fixed, regular neighbourhood. Molecules, interaction networks and citation graphs are not. Generalising convolution to an arbitrary neighbourhood is the last piece of neural machinery Elementa needs.

Masking a convolution, and the collapse it causesOn the left, a masked grid with a kernel window straddling the boundary: an ordinary convolution reads across the hole. In the middle, sparse convolution treats visible patches as sparse data. On the right, channel responses collapse toward each other until global response normalisation forces them to compete.the problemFCMAEGRNa kernel spans the holeand leaks the answervisible patches only,as sparse datacollapsedcompetingchannels forced apartby normalisationNeither half works alone. Bolting MAE onto plain ConvNeXt made things worse.
Fig. 14 — A kernel slides across a masked hole and leaks the answer; sparse convolution stops it, and global response normalisation stops the channels collapsing. Neither half works alone.

Apparatus

The mathematics this chapter leans on, held in Book 0 so it can be assumed here without being taught here. Not a gate — follow a link when a step stops making sense.

Graphs, vertices and edges 0.GR.01 · Representing a graph 0.GR.02 · The identity, the inverse and the transpose 0.LA.02 · Rank, eigenvalues and the singular value decomposition 0.LA.04

Notation

  • WA weight matrix
  • XA batch of token representations, T×d, rows are tokens
  • λA regularisation coefficient, or an eigenvalue where the context is linear algebra
  • dModel width

Propositions

Not yet written. The topics above are the plan for this chapter; each will become a proposition with its own figure.

Worked problems

0/5 problems0/4 variants0/10 exercisesowes 15 more

Not yet written. At M3 this chapter owes 5 worked problems across 4 distinct variants, and 10 exercises, every one with a published solution. The build enforces that from the day the chapter is marked published.