By the end of this lecture
Four things you can do.
Explain why graphs are shared
A relation without an order: permutation invariance, variable size, and the matrix view.
Trace message passing
The MPNN template, over-smoothing, over-squashing, and the 1-WL ceiling.
Compare embeddings
Random walks, spectral coordinates, and TransE / ComplEx / RotatE on knowledge graphs.
Connect queries and GNNs
Datalog recursion, logical expressivity, and where the guarantee comes from.