Graph Machine Learning & Random Graph Models
summary
Describes a random geometric latent-space model with bounded, piecewise-Lipschitz kernel and lower-bounded degree on a compact metric space, uses a sampling operator and MSC norm, and shows adjacency/normalized-Laplacian matrices converge to integral operators. Proves message-passing GNNs converge to a continuous GNN when n → ∞ in the relatively sparse regime alpha_n ~ log n / n, with error bounded roughly by O(d/√n + 1/√(n alpha_n)) for d-dimensional embeddings. Also gives stability under C1 deformations: cGNN deviation is controlled by the sup norm of the deformation gradient.
AI-written summary · about
chapters (8)
- 0:00Introduction
- 1:56Spectral clustering and SBM
- 4:35Latent space and random geometric graphs
- 18:36Graph neural networks
- 24:35GNN convergence to continuous GNNs
- 37:54Main GNN convergence result
- 46:16GNN stability under deformations
- 53:30Summary
related talks
32mLearning Ill-Conditioned Gaussian Graphical Models
01h 31mGraphons and Graph Limits 2
56mTesting Thresholds for High-dimensional Sparse Random Geometric Graphs
17mUniversality of Neural Networks
01h 04mHigher-dimensional Expansion of Random Geometric Complexes
31mGraph-Based Machine Learning with Python
29mGraph Neural Networks + LLM on
19mProbabilistic Lipschitz Analysis of Neural Networks