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

Nate Ackerman, Cameron Freer, Younesse Kaddar, Jacek Karwowski, Sean Moss, Daniel Roy, Sam Staton, Hongseok Yang

Research output: Contribution to journalConference articlepeer-review

235 Downloads (Pure)

Abstract

We study semantic models of probabilistic programming languages over graphs, and establish a connection to graphons from graph theory and combinatorics. We show that every well-behaved equational theory for our graph probabilistic programming language corresponds to a graphon, and conversely, every graphon arises in this way.

We provide three constructions for showing that every graphon arises from an equational theory. The first is an abstract construction, using Markov categories and monoidal indeterminates. The second and third are more concrete. The second is in terms of traditional measure theoretic probability, which covers 'black-and-white' graphons. The third is in terms of probability monads on the nominal sets of Gabbay and Pitts. Specifically, we use a variation of nominal sets induced by the theory of graphs, which covers Erdős-Rényi graphons. In this way, we build new models of graph probabilistic programming from graphons.
Original languageEnglish
Article number61
Pages (from-to)1819–1849
JournalProceedings of the ACM on Programming Languages
Volume8
Issue numberPOPL
DOIs
Publication statusPublished - 5 Jan 2024

Bibliographical note

This material is based on work supported by a Royal Society University Research Fellowship, ERC Project BLAST and AFOSR Award No. FA9550–21–1–003. This work was supported in part by CoCoSys, one of seven centers in JUMP 2.0, a Semiconductor Research Corporation (SRC) program sponsored by DARPA. HY was supported by the National Research Foundation of Korea (NRF) grant funded by the Korea government (MSIT) (No. RS-2023-00279680), and also by the Engineering Research Center Program through the National Research Foundation of Korea (NRF) grant funded by the Korea government (MSIT) (No. NRF-2018R1A5A1059921).

Fingerprint

Dive into the research topics of 'Probabilistic Programming Interfaces for Random Graphs: Markov Categories, Graphons, and Nominal Sets'. Together they form a unique fingerprint.

Cite this