概率图电路

引言

深度生成模型处理图结构数据的挑战

图结构数据广泛存在于分子设计、社交网络分析、蛋白质结构预测等众多领域。深度生成模型（Deep Generative Models, DGMs）在捕获复杂图分布方面取得了巨大成功¹。然而，现有图生成模型面临以下核心挑战：

• C1. 组合空间的复杂性：图存在于庞大而复杂的组合空间中，例如分子领域可能的图数量是巨大的²。
• C2. 可变大小特性：图不仅在节点和边的特征值上是随机的，而且在节点和边的数量上也是随机的。
• C3. 置换不变性：图是置换不变的，即单个图有阶乘数量的可能配置。
• C4. 语义有效性：图需要满足领域特定的语义有效性约束（如化学价规则）。

PGC的提出背景

尽管现代图DGMs在采样方面表现出色，但它们本质上是不可追踪的概率模型——无法高效回答边缘概率计算、条件概率查询等基本推断任务¹。这种不可追踪性源于神经网络中的非线性变换。

为了解决这一根本性限制，Papež等人于2025年在UAI会议上提出了概率图电路（Probabilistic Graph Circuits, PGC），这是一种可追踪的深度生成模型框架，能够在图结构数据上实现精确且高效的边缘概率、条件概率和期望计算¹。

---

概率电路基础

概率电路的定义

概率电路（Probabilistic Circuits, PCs）是一个统一的可追踪概率模型框架³，由三种类型的计算单元组成：

单元类型	定义	公式
输入单元	计算用户定义的参数化函数	$c_u(G_u):=f_u(G_u)$
求和单元	计算输入的加权求和	$c_u(G_u):={\sum }_{i\in \text{in}(u)}{w}_i{c}_i(G_i)$
乘积单元	计算输入的乘积	$c_u(G_u):={\prod }_{i\in \text{in}(u)}{c}_i(G_i)$

其中，$G_u$ 称为单元的作用域（scope），表示该单元操作对应的子图。

可分解分布

概率电路编码一个非负函数 $c(X)\ge 0$，可以被解释为概率分布。要实现可追踪推断，概率电路需要满足以下结构约束⁴：

假设1（平滑性）：每个求和单元的输入具有相同的作用域。

$X_a=X_b,\forall a,b\in \text{in}(u)$

假设2（可分解性）：每个乘积单元的输入具有互不相交的作用域。

$X_a\cap X_b=\varnothing ,\forall a,b\in \text{in}(u)$

假设3（可追踪输入单元）：每个输入单元的积分具有代数闭式解。

${\int }_{\text{dom}(Z_u)}{c}_u(y_u,z_u)d{Z}_u$

可追踪推断

可追踪性是概率电路的核心特征，允许在单次前向传播中回答广泛的推断查询⁵。

定义1（概率电路的可追踪性）：

设 $p(X_n|n)$ 是一个编码固定大小集合 $X_n$ 上概率分布的PC，其满足平滑性、可分解性和可追踪输入单元。此外，将 $X_n$ 分为两个固定大小的子集 $X_n:=\{X_{n-k}^a,X_k^b\}$。则积分

$\int p(x_{n-k}^a,X_k^b|n)d{x}_{n-k}^a$

可以精确计算（A），并在 $O(\text{poly}(|p|))$ 时间内高效完成（B）。

---

概率图电路定义

图结构编码

一个 $N$ 节点图被定义为元组 $G:=\{X,A\}$：

• 节点特征矩阵 $X\in {\mathbb{R}}^{N\times n_X}$：每行表示一个节点的 $n_X$ 维特征（通常使用独热编码）
• 邻接张量 $A\in {\mathbb{R}}^{N\times N\times n_A}$：表示节点间的边类型

图分布 $p(G)$ 需要满足置换不变性（$S_n$- invariance），即对于任意置换 $\pi \in S_n$：

$p(\pi G|n)=p(G|n)$

PGC的层次结构

PGC的核心架构如图1所示¹：

┌─────────────────────────────────────────────────────────────┐
│                    PGC (完整模型)                            │
│  p(G) = p(G_n | n) × p(N)                                   │
│                                                             │
│  ┌─────────────────┐     ┌─────────────────┐                │
│  │   节点-PC       │     │   边-PC         │                │
│  │ (n-conditioned) │     │ (n-conditioned) │                │
│  └────────┬────────┘     └────────┬────────┘                │
│           │                       │                         │
│           └───────────┬───────────┘                         │
│                       │                                      │
│                 ┌─────▼─────┐                               │
│                 │  乘积层    │ (n_c 个单元)                   │
│                 └─────┬─────┘                               │
│                       │                                      │
│                 ┌─────▼─────┐                               │
│                 │  求和层    │ (1 个单元)                     │
│                 └───────────┘                                │
└─────────────────────────────────────────────────────────────┘

关键组件：

1. 节点-PC：对节点特征 $X^n$ 建模，输入为 $n$ 条件化的节点特征
2. 边-PC：对邻接关系 $L^n$ 建模，输入为 $A^n$ 的下三角部分的展平
3. 乘积层：连接节点-PC和边-PC的输出，$n_c$ 个单元捕获节点-边的相关性
4. 求和层：最终聚合，输出 $n$ 条件化的联合分布 $p(X^n,L^n|n)$
5. 基数分布 $p(N)$：描述图的随机大小

与PC的关系

PGC继承并扩展了传统概率电路的能力：

特性	传统PC	PGC
数据类型	固定大小向量	可变大小图
置换不变性	部分不变	完全不变（多种策略）
推断查询	边缘/条件/期望	同PC + 图特定查询
节点相关性	独立建模	联合建模

---

推断算法

边缘概率计算

PGC支持对图的任意部分进行边缘化。设 $G=\{G_a,G_b\}$，边缘概率计算为：

$\int p(g_a,G_b)d{g}_a={\sum }_{n=k}^{\infty }\int p(g_{n-k}^a,G_k^b|n)p(n)d{g}_{n-k}^a$

通过**边际填充（Marginalization Padding）**机制，PGC假设图最多有 $m$ 个节点，当实例包含 $n<m$ 个节点时，边缘化”空”节点及其相关边¹。

条件概率查询

PGC可以计算任意图子结构上的条件概率。通过 omni-compatible 图电路，可以精确计算：

• 证据查询：$p(G_s|G_{\setminus s})$
• 边缘查询：对特定节点或边的概率积分
• 高阶矩查询：$\mathbb{E}[X_i^r]$、$\mathbb{E}[A_{ij}^r]$

梯度计算

PGC的参数通过梯度下降优化。负对数似然损失函数为：

$\mathcal{L}=-\log p(G)=-\log \left({\sum }_{n}p(G_n|n)p(n)\right)$

由于PGC的可追踪性，梯度可以通过反向传播精确计算，无需变分近似。

---

训练方法

变分推断

对于不可精确计算的情况，PGC可以使用变分推断。证据下界（ELBO）为：

$\log p(G_n|n)\ge {\mathbb{E}}_{q(\pi |G_n)}[\log p(G,\pi |n)]+H(q(\pi |G_n))$

其中 $q(\pi |G_n)$ 是变分后验分布，$H$ 是熵。

EM算法

期望最大化算法可用于训练PGC：

1. E步：计算隐变量的后验分布
2. M步：最大化期望下界更新参数

结构学习

PGC支持两种结构学习方式：

1. 固定结构：使用预定义的区域图（Region Graph）构建架构：

   • 二叉树（BT）
   • 线性树（LT）
   • 随机树（RT）
   • 随机同步树（RT-S）
   • 隐Chow-Liu树（HCLT）¹

2. 学习结构：如HCLT变体，从数据中学习最优的树结构

---

应用场景

图生成

PGC可以在单次前向传播中生成完整的图样本：

# PGC 生成过程示意
sample = pgc.generate()  # 单次前向传播

在QM9数据集上的无条生成性能：

模型	有效性↑	NSPDK↓	FCD↓	唯一性↑
RT-S (PGC)	88.83%	0.002	1.11	99.38%
GDSS	95.72%	0.003	2.90	98.46%
DiGress	99.00%	0.005	0.36	96.20%

链接预测

通过条件概率查询，PGC可以评估在图中添加或删除边的概率：

$p(A_{ij}|G_{\setminus A_{ij}})$

分子生成

PGC在分子图生成任务中表现出色。实验表明，基于排序的PGC变体（π PGC）在NSPDK和FCD指标上与现有不可追踪模型具有竞争力¹。

---

与其他方法比较

vs 图神经网络

方面	图神经网络 (GNN)	概率图电路 (PGC)
任务类型	判别/半监督	生成/概率建模
推断能力	单次前向传播	多查询可追踪
输出	节点/图嵌入	概率分布
可解释性	注意力权重	显式概率路径

vs VAE/GAN

方面	GraphVAE/GraphGAN	PGC
似然评估	近似/隐式	精确
条件生成	需要额外设计	原生支持
推断查询	受限	广泛支持
训练稳定性	对抗训练挑战	纯似然训练

vs 归一化流/扩散模型

方面	GraphAF/GraphDF/GDSS	PGC
生成方式	自回归或迭代去噪	单次采样
似然评估	需要额外近似	原生精确
推断能力	主要用于生成	多任务支持
计算效率	多步推理	单次前向

---

参考文献

---

本文档基于 PGC 论文（UAI 2025）编写。代码实现见 GitHub: mlnpapez/PGC。

Footnotes

1. Papež M, Rectoris M, Šmídl V, Pevný T. Probabilistic Graph Circuits: Deep Generative Models for Tractable Probabilistic Inference over Graphs. UAI 2025. (arXiv:2503.12162) ↩ ↩² ↩³ ↩⁴ ↩⁵ ↩⁶ ↩⁷

2. Reymond JL, Ruddigkeit L, Blum L, Van Deursen R. The enumeration of chemical space based on GDB-17 data. Wiley Interdisciplinary Reviews: Computational Molecular Science. 2012. ↩

3. Choi Y, Vergari A, Van den Broeck G. Probabilistic Circuits: A Unifying Framework for Tractable Probabilistic Models. UCLA. 2020. ↩

4. Darwiche A, Marquis P. A Knowledge Compilation Map. Journal of Artificial Intelligence Research. 2002;17:229-264. ↩

5. Vergari A, et al. A Compositional Atlas of Tractable Circuit Operations. NeurIPS 2021. ↩