Boot Camp on Graph Learning
summary
Half-day boot camp lays out concrete tradeoffs: message‑passing GNNs run in O(nodes+edges) but provably match 1‑WL and miss many cycle/subgraph distinctions; k‑WL–style higher‑order nets are more expressive but blow up in cost; random node features are theoretically universal yet empirically hard to train; graph transformers add positional/centrality encodings and face O(n^2) attention. Examples and fixes: Exphormer uses original edges plus an expander and global sinks to cut cost and improve benchmarks, Graphormer adds centrality and shortest‑path bias, and subgraph GNNs (node‑rooted bags) reach 3‑WL‑level expressivity.
AI-written summary · about
chapters (8)
- 0:00Workshop introduction
- 1:40Workshop scope and agenda
- 5:07Monday bootcamp overview
- 7:40Graph learning fundamentals
- 15:52Node embedding techniques
- 22:38Graph neural networks
- 32:40Graph transformers
- 45:44Expressive power of GNNs
related talks
16mPreview: Graph NNs
31mGraph-Based Machine Learning with Python
39mUsing Graph Neural Networks to Embrace the Dependency Within Your Data
15mIdentifying and Analyzing Pitfalls in GNN Systems
29mGraph Neural Networks + LLM on
47mPyTorch Geometric for Graph Neural Nets
31mGraph Mining with Deep Learning: challenges and pitfalls
01h 02mGraph Powering