Week 04 — GNN Variants — GAT, GIN, GraphSAGE

The expressive-power hierarchy and the design choices that drive it.

Lecture

Graph attention (Veličković et al. 2018) · GraphSAGE (Hamilton et al. 2017) · graph isomorphism networks and the Weisfeiler-Lehman connection (Xu et al. 2019) · what each variant fixes about plain GCN.

Read before the lecture

• Veličković et al., *Graph Attention Networks* (ICLR 2018)
• Xu et al., *How Powerful are Graph Neural Networks?* (ICLR 2019)

Problem set

PS2 — Expressive power

1. Prove that GIN is at most as powerful as the 1-WL test.
2. Construct two non-isomorphic graphs that no message-passing GNN can distinguish.

Reference text for this week: chapter 04 of the bilingual notes — EN PDF · FR PDF.