一句话：建立图上概率编程语义与 graphon 的对应，并给出三种构造证明每个 graphon 均可由等式理论产生。
本文研究图上概率编程语言的语义模型，并将其与图论和组合学中的 graphon 联系起来。作者证明：该语言中每个良行为的等式理论都对应一个 graphon；反过来，每个 graphon 都能由这样的等式理论产生。为证明反向方向，论文给出三种构造：第一种是抽象构造，基于马尔可夫范畴与幺半不定元；第二种使用传统测度论概率，覆盖黑白 graphon；第三种使用 Gabbay 和 Pitts 名义集合上的概率单子，并采用由图理论诱导的名义集合变体，覆盖 Erdős–Rényi graphon。由此，论文从 graphon 构造出图概率编程的新语义模型。
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.
@article{paperbot2601,
title = {Probabilistic Programming Interfaces for Random Graphs: Markov Categories, Graphons, and Nominal Sets},
author = {Nate Ackerman and Cameron E. Freer and Younesse Kaddar and Jacek Karwowski and Sean Moss and Daniel Roy and Sam Staton and Hongseok Yang},
journal = {Proceedings of the ACM on Programming Languages},
volume = {8},
number = {POPL},
year = {2024},
doi = {10.1145/3632903}
}