NUS's Xavier Bresson releases Lecture 9 on Graph Transformers, from Laplacian encodings to O(n) hierarchical attention
xbresson · x · 2026-10-19
Xavier Bresson (NUS) published Lecture 9 of his Graph Machine Learning course, covering Graph Transformers. Key topics:
- Graph positional encodings: Laplacian and random-walk encodings, plus the distinction between geometric positional and structural encodings (node degree, motif/graphlet counts)
- Message passing and over-squashing, with a unified view of CNNs/RNNs/Transformers/GNNs as message-passing over different domains
- Sparse vs. dense graph self-attention trade-offs: dense GT costs O(n²) on large graphs while sparse GT worsens over-squashing
- Trilinear edge features, hierarchical Graph Transformers, heavy-edge matching, and O(n) hierarchical attention
Slides are freely available — a complete, systematic resource on graph Transformers.
More from Research
- Anthropic researcher shows models pick the rhyme word early, hiding the plan from output — thetripathi58 · 2026-10-19
- Why computational programs likely can't be conscious: Anna Ciaunica's embodied-mind argument — AnnaCiaunica · 2026-10-19
- DNA language models and AlphaGenome answer different questions about variants — Fair-Rain3366 · 2026-10-19
- MIT builds multimodal AI that 'sees' crystalline bonding to find battery materials — MacrinePhD · 2026-10-19
- Pearl-Chat: an 8.5M-param Luganda LLM built from scratch in JAX, with 2x tokenizer efficiency over LLaMA-3 — weskambale · 2026-10-19
- IRIS reconstructs cell-signaling histories via perturbation screens and transfer learning — Dorian182 · 2026-10-19