Factorized Graph Neural Networks (With Some Algebraic Cheating)
summary
Claims a method called distant compatibility estimation that recovers class compatibilities from extremely sparse labels (examples down to 1 in 10,000) by linearizing belief propagation, using Taylor expansions and spectral-radius damping to get closed-form updates. It builds factorized graph representations (constant-size sketches) and computes statistics over non‑backtracking paths, letting learning run on tiny sketches instead of full graphs. End-to-end is orders of magnitude faster than hold-out tuning, propagation is linear in edges, and final accuracy matches using gold compatibilities.
AI-written summary · about
chapters (9)
- 0:00Introduction to the problem
- 0:44Semi-supervised classification
- 3:00Belief propagation limitations
- 7:22Linearized equation systems
- 10:48Convergence and implementation
- 13:13Fast learning and inference
- 16:14Compact graph representations
- 20:20Path-based statistical learning
- 25:11Discussion and future outlook
related talks
01h 03mTowards Foundation Models for Graphs
41mEnhancing LLMs with Graph Technology
51mFactorized Databases
12mTopology Over Predictions: Using Graph Context to Drive Real-Time Lending Decisions
24mUnlocking AI's Hidden Connections With Graphs
01h 00mTensor Graphical Models For Complex And High Dimensional Data
06mCloud-Native GraphRAG: AI’s Logical Edge
27mImproved Frequency Estimation Algorithms with and without Predictions