Probabilistic Programming Interfaces for Random Graphs: Markov Categories, Graphons, and Nominal Sets - POPL 2024

Explore a 19-minute video presentation from the POPL 2024 conference that delves into semantic models of probabilistic programming languages over graphs and their connection to graphons. Learn how researchers establish that every well-behaved equational theory for graph probabilistic programming languages corresponds to a graphon, and conversely, how every graphon arises from such theories. Discover three constructions demonstrating this correspondence: an abstract approach using Markov categories and monoidal indeterminates, a concrete measure-theoretic probability method for 'black-and-white' graphons, and a nominal sets-based approach for Erdős-Rényi graphons. Gain insights into how these findings contribute to building new models of graph probabilistic programming from graphons, bridging the fields of graph theory, combinatorics, and probabilistic programming.