Probabilistic programming interfaces for random graphs: Markov categories, graphons, and nominal sets
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916084988248064 |
|---|---|
| author | Ackerman, Nathanael L. Freer, Cameron E. Kaddar, Younesse Karwowski, Jacek Moss, Sean K. Roy, Daniel M. Staton, Sam Yang, Hongseok |
| author_facet | Ackerman, Nathanael L. Freer, Cameron E. Kaddar, Younesse Karwowski, Jacek Moss, Sean K. Roy, Daniel M. Staton, Sam Yang, Hongseok |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2312_17127 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Probabilistic programming interfaces for random graphs: Markov categories, graphons, and nominal sets Ackerman, Nathanael L. Freer, Cameron E. Kaddar, Younesse Karwowski, Jacek Moss, Sean K. Roy, Daniel M. Staton, Sam Yang, Hongseok Programming Languages Logic in Computer Science Probability 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. |
| title | Probabilistic programming interfaces for random graphs: Markov categories, graphons, and nominal sets |
| topic | Programming Languages Logic in Computer Science Probability |
| url | https://arxiv.org/abs/2312.17127 |