Boot camp on logic and graph learning
summary
Boot camp defines node-colored graphs, fixes GNNs that use sum aggregation with bias and one-hot inputs, and gives precise expressiveness claims: node-level distinguishability by these GNNs matches graded modal logic (GML = WL power); uniformly, any FO definable unary property a GNN can learn is equivalent to a GML formula. Allowing counting/linear combinations yields a Presburger-extended GML that captures what eventually-constant activations can do; ReLU is strictly more powerful, polynomial activations fail, and softmax/precise ReLU limits remain open.
AI-written summary · about
chapters (11)
- 0:00Boot camp intro
- 0:42First-order logic over graphs
- 14:12Unary relations by FO formulas
- 17:55Restricting FO logic variables
- 23:13Counting quantifiers in logic
- 35:05GNNs formal definition
- 44:50Logical expressiveness notions
- 58:06FO properties with GNNs
- 1:09:16GNNs beyond first-order logic
- 1:17:44ReLU vs truncated ReLU GNNs
- 1:20:09Open problems and future
related talks
23mGNN-RAG: Bridging Graph Reasoning and Language Understanding for Knowledge Retrieval
06mCloud-Native GraphRAG: AI’s Logical Edge
31mGraph-Based Machine Learning with Python
16mPreview: Graph NNs
29mGraph Neural Networks + LLM on
01h 05mLogic and Probabilistic Circuits 1
39mUsing Graph Neural Networks to Embrace the Dependency Within Your Data
15mPL4XGL: A Programming Language Approach to Explainable Graph Learning