Probabilistic programming interfaces for random graphs: Markov categories, graph...
summary
Proves an equivalence: a well-behaved implementation of an abstract graph type (vertices, new, edge) corresponds exactly to a graphon. Uses Markov categories plus two concrete constructions: measure-theoretic probability for black‑and‑white graphons and probability monads on a nominal sets variant for Erdős–Rényi cases. Ships a lazy probabilistic programming library, demonstrates a geometric sphere implementation (inferred θ ≈ π/6) and a horn property with probability 1/8, and shows grayscale graphons need hidden state or an abstract categorical construction.
AI-written summary · about
chapters (10)
- 0:00Probabilistic programming intro
- 1:48Random graphs importance
- 3:36Graph interfaces in code
- 6:42Horn example interfaces
- 8:06Well-behaved probabilistic programming
- 10:55Formalizing PP structures
- 12:21Proving theorem with programs
- 14:49Programs to graphons and back
- 15:53Broader implications
- 16:58Q&A
related talks
24mHigher order programming with probabilistic effects: A model of stochastic memo...
04mRandom probability distributions as natural transformations
01h 03mA Personal Viewpoint on Probabilistic Programming
18mCompositional imprecise probability: a solution from graded monads and Markov categories
31mProbabilistic Programming: The What, Why and How
29mProbabilistic Programming: What It Is and How It Works
20mProbabilistic Programming with Stochastic Probabilities
49mSemantic Foundations for Probabilistic Programming