  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\H{o}s-R\'enyi
graphons. In this way, we build new models of graph probabilistic programming
from graphons.
