概率图电路（PGC）UAI 2025 深度解析

概述

本文档深入解析 Papez, Rektoris, Smidl & Pevny 于 UAI 2025 发表的论文 Probabilistic Graph Circuits: Deep Generative Models for Tractable Probabilistic Inference over Graphs。¹

核心贡献：将概率电路（PC）的可处理推断能力从”表格/序列数据”扩展到图结构数据。

现有概率图电路 (PGC) wiki 已给出 PGC 的高层概览与基础实现。
本文档聚焦于 Papez et al. (UAI 2025) 论文的形式化定义、构建算法、理论分析与实验结果。
两份文档互为补充：前者偏”教学式入门”，本文档偏”论文级深度”。

1. 动机与背景

1.1 为什么需要图上的可处理概率模型？

图结构数据广泛存在于科学和工程领域：

领域	图数据示例	关键概率查询
化学/药物	分子图	分子属性分布、新分子生成
生物信息学	蛋白质交互网络	节点重要性、子结构
社交网络	用户关系图	影响力传播、社区检测
推荐系统	用户-物品二部图	缺失边预测、链接概率
交通	路网、航线图	路径概率、流量预测
知识图谱	实体关系图	缺失三元组补全

在这些场景中，精确概率推断（如给定部分子图，估计缺失边的概率）是核心需求。

1.2 现有方法的局限

GNN-based 生成器（如 GraphVAE、GraphRNN）：

优点：可微、可扩展；
缺点：推断只能近似，无法精确计算 $P (G ∣ X)$ 。

传统概率图模型（如 Markov Random Fields for graphs）：

优点：理论完备；
缺点：图上的 MRF 推断通常是 P 难。

PC + GNN 混合：

早期尝试仅将 PC 限制在节点特征，结构推断仍用 GNN。
缺乏端到端可处理的图概率模型。

1.3 Papez et al. 的解决思路

Papez 等人的核心洞察是：

图可以视为一种”特殊的高维表格数据”，其变量是 (节点特征, 边存在性, 邻接结构) 三元组。

如果能把这三类变量都纳入 PC 的 smooth + decomposable 框架，就能实现图上的多项式时间精确推断。

具体而言，PGC 包含三个层次的 PC：

PGC = (节点特征 PC) × (边存在性 PC) × (图结构 PC)

每一层都设计为 smooth + decomposable，且三层之间通过”边存在性变量”耦合。

2. 形式化定义

2.1 预备：标准 PC

定义（PC）：见概率电路基础。简言之，PC 是 smooth + decomposable + 节点为 sum / prod / leaf 的有向无环图。

PC 满足：

MAR： $\sum_{x_{Q}} P (x_{Q}, x_{E})$ 在 $O (∣ V ∣ \cdot ∣ X ∣^{k})$ 内可计算。
COND： $P (x_{Q} ∣ x_{E}) = MAR (x_{Q}, x_{E}) / MAR (x_{E})$ 。

2.2 图的概率表示

设图 $G = (V, E, X_{V}, X_{E})$ ，其中：

$V = {1, \dots, n}$ ：节点集合。
$E \subseteq V \times V$ ：边集合（这里考虑无向简单图）。
$X_{V} \in R^{n \times d_{v}}$ ：节点特征。
$X_{E} \in R^{∣ E ∣ \times d_{e}}$ ：边特征。

目标：建模联合分布 $P (G) = P (V, E, X_{V}, X_{E})$ 。

2.3 PGC 的核心变量分解

Papez 等人将 $P (G)$ 分解为：

P (G) = 节点特征 i \in V \prod P_{node} (X_{i}) \cdot 边特征 (i, j) \in E \prod P_{edge} (X_{ij} ∣ X_{i}, X_{j}) \cdot 图结构 P_{struct} (E ∣ X_{V})

每一项都用 PC 实现。

2.4 节点特征 PC（Node-feature PC）

定义（节点特征 PC）：节点特征 PC 是一个 smooth + decomposable PC $C_{V}$ ，其：

叶节点：节点 $i$ 的特征 $X_{i}$ （如 one-hot 编码或实值向量）。
求和节点：实现节点特征的混合。
乘积节点：实现节点间的独立性假设（如果存在）。

关键性质：在 decomposability 下，节点特征 PC 的 MAR 对单个节点 $i$ 是封闭的：

P_{node} (X_{i}) = {X_{j}}_{j \neq = i} \sum j \in V \prod P_{j} (X_{j})

2.5 边存在性 PC（Edge-existence PC）

定义（边存在性 PC）：边存在性 PC 是一个 smooth + decomposable PC $C_{E}$ ，其：

输入变量： ${E_{ij} \in {0, 1}}$ ，对所有潜在边 $(i, j)$ 。
输出： $P_{struct} (E = e ∣ X_{V})$ 。

核心创新：将所有 $(2 n)$ 个边存在性变量纳入一个 PC 中。

挑战：变量数 $O (n^{2})$ ，如何保证 PC 规模多项式于 $n$ ？

Papez 等人通过分层 vtree 实现：

将节点排列为二叉树（按度数或某种顺序）。
在 vtree 上构建 PC，使得相邻节点对的边存在性在同一子电路中。

2.6 边特征 PC（Edge-feature PC）

定义（边特征 PC）：给定边 $(i, j) \in E$ ，边特征 PC 建模

P_{edge} (X_{ij} ∣ X_{i}, X_{j})

实现为：每个边有独立的”边特征子 PC”，叶节点为 $X_{ij}$ ，乘积/求和节点由节点特征 $(X_{i}, X_{j})$ 条件化。

2.7 全局一致性约束

为保证 $P (G)$ 是一致分布，PGC 需满足：

节点特征 PC 与边特征 PC 的 scope 不交。
边存在性 PC 与节点特征 PC 的 scope 不交。
边特征 PC 在 $(i, j) \in / E$ 时为零。

这些约束保证 smooth + decomposability，进而保证 MAR/COND 可处理。

3. 核心构建算法

3.1 vtree 构造

Papez 等人提出 Ordered vtree (Ovtree)：

Algorithm BuildOvtree(V):
    Input: 节点集合 V
    Output: Ovtree τ
    
    1. 计算节点度数 {d_i}
    2. 按度数排序 V 为 v_1, v_2, ..., v_n
    3. 构造平衡二叉树 τ，叶子为 v_1, ..., v_n
    
    时间: O(n log n), 空间: O(n)

Ovtree 的性质：

平衡性：深度 $O (lo g n)$ 。
度数优先：度数高的节点靠近 vtree 根部，对应更多”兄弟节点对”，便于共享边存在性子电路。

3.2 边存在性 PC 构造

Algorithm BuildEdgePC(τ):
    Input: Ovtree τ
    Output: 边存在性 PC C_E
    
    function BuildEdgePC(vtree_node):
        if vtree_node is leaf:
            # 单节点：返回指示器
            return IndicatorNode(vtree_node.var)
        
        # 递归处理左右子树
        left_pc = BuildEdgePC(vtree_node.left)
        right_pc = BuildEdgePC(vtree_node.right)
        
        # 关键：构造跨子树的"边存在性乘积"
        cross_edges_pc = BuildCrossEdges(left_pc, right_pc, vtree_node)
        
        return ProductNode(left_pc, right_pc, cross_edges_pc)
    
    function BuildCrossEdges(L, R, vtree_node):
        # 对每对 (i ∈ L, j ∈ R)，构造边存在性子电路
        edge_subs = []
        for i in L.vars:
            for j in R.vars:
                if i < j:
                    edge_subs.append(EdgeIndicator(i, j))
        return SumNode(edge_subs, weights=learnable)

复杂度：设 vtree 深度为 $d$ ，则每个内部节点产生 $O (∣ L ∣ \cdot ∣ R ∣)$ 个边指示器。累计：

v \in τ_{internal} \sum ∣ L_{v} ∣ \cdot ∣ R_{v} ∣ = O (n^{2})

PC 规模为 $O (n^{2})$ ，多项式于 $n$ 。✓

3.3 节点特征 PC 构造

Algorithm BuildNodePC(V, X_V):
    Input: 节点集 V，节点特征 X_V
    Output: 节点特征 PC C_V
    
    1. 对每个节点 i，构造叶子节点 LeafNode(i) 输出 P_i(X_i)
    2. 若假设节点独立：C_V = ProductNode([LeafNode(i) for i in V])
    3. 若假设节点间有依赖：插入 sum/product 节点（取决于具体先验）

3.4 完整 PGC 构造

Algorithm BuildPGC(V, E, X_V, X_E):
    Input: 图数据 (V, E, X_V, X_E)
    Output: PGC = (C_V, C_E, C_edge)
    
    1. τ = BuildOvtree(V)              # 构造 Ovtree
    2. C_V = BuildNodePC(V, X_V)        # 节点特征 PC
    3. C_E = BuildEdgePC(τ)             # 边存在性 PC
    4. C_edge = BuildEdgeFeaturePC(X_E) # 边特征 PC
    5. PGC = ProductNode(C_V, C_E, C_edge)
    6. return PGC

总复杂度：

vtree 构造： $O (n lo g n)$ 。
节点 PC： $O (n)$ 。
边存在性 PC： $O (n^{2})$ 。
边特征 PC： $O (∣ E ∣)$ 。
整体： $O (n^{2} + ∣ E ∣)$ 。✓ 多项式。

4. 训练目标与算法

4.1 训练数据

设训练集 $D = {G^{(1)}, \dots, G^{(M)}}$ ，每张图 $G^{(m)} = (V^{(m)}, E^{(m)}, X_{V}^{(m)}, X_{E}^{(m)})$ 。

4.2 最大似然目标

L (θ) = m = 1 \sum M lo g P_{θ} (G^{(m)}) - λ \cdot R (θ)

其中 $R (θ)$ 是正则化项（如权重 L2）， $λ$ 是超参数。

4.3 结构约束

训练中保持：

Smoothness：对 sum 节点的子节点 scope 一致性。
Decomposability：对 prod 节点的子节点 scope 不交。
Determinism（可选）：边存在性 PC 中，每个 (i, j) 状态唯一。

这些约束通过 PC 的结构化参数化保证，训练时只需优化实数参数（权重和叶节点参数）。

4.4 算法伪代码

def train_pgc(pgc, train_graphs, learning_rate=1e-3, num_epochs=100):
    """
    训练 PGC 的简化实现。
    
    pgc: ProbabilisticGraphCircuit 实例
    train_graphs: list of Graph 对象
    """
    optimizer = torch.optim.Adam(pgc.parameters(), lr=learning_rate)
    
    for epoch in range(num_epochs):
        total_loss = 0.0
        for graph in train_graphs:
            optimizer.zero_grad()
            
            # 提取图数据
            x = graph.node_features  # (n, d_v)
            adj = graph.adjacency     # (n, n)
            edge_feats = graph.edge_features  # (|E|, d_e)
            
            # 计算对数似然
            log_prob = pgc.log_likelihood(x, adj, edge_feats)
            
            # 负对数似然作为损失
            loss = -log_prob
            loss.backward()
            optimizer.step()
            
            total_loss += loss.item()
        
        if (epoch + 1) % 10 == 0:
            avg_loss = total_loss / len(train_graphs)
            print(f"Epoch {epoch+1:3d} | Avg NLL = {avg_loss:.4f}")
    
    return pgc

4.5 训练技巧

块坐标下降：分别优化节点 PC、边 PC、边特征 PC 的参数。
课程学习：先训练简单图（小 $n$ ），再训练复杂图。
数据增强：通过节点置换、子图采样扩充训练集。

5. 可处理推断算法

5.1 MAR：边存在性边际化

任务： $P (E_{q} = e_{q} ∣ X_{V}, X_{E})$ ，即固定节点和边特征，求部分边的边际分布。

算法：

function MarginalEdgeExistence(C_E, observed_edges, target_edge):
    # 1. 在 C_E 中，将观测边设置为指示器（值固定）
    set_evidence(C_E, observed_edges)
    
    # 2. 对目标边进行 MAR
    marginal = sum_out_other_edges(C_E, target_edge)
    
    return marginal

复杂度： $O (∣ C_{E} ∣) = O (n^{2})$ ，多项式于 $n$ 。✓

5.2 COND：条件边存在性

任务： $P (E_{q} = e_{q} ∣ X_{V}, X_{E}, E_{o} = e_{o})$ ，其中 $E_{o}$ 为观测边集。

P (E_{q} = e_{q} ∣ E_{o} = e_{o}, X_{V}, X_{E}) = \frac{P ( E _{q} = e _{q} , E _{o} = e _{o} ∣ X _{V} , X _{E} )}{P ( E _{o} = e _{o} ∣ X _{V} , X _{E} )}

两个分子/分母都是 MAR，可处理。✓

5.3 MAP：最可能图结构

任务： $ar g max_{E} P (E ∣ X_{V}, X_{E})$ 。

需要 PC 满足 determinism（每个 sum 节点对每个输入至多一个非零子节点）。在 determinism 下：

function MAPInference(C_E):
    # 在每个 sum 节点选择概率最大的子节点
    for each sum node n:
        argmax_child = argmax over children of n
        fix_choice(n, argmax_child)
    return decoded_path

复杂度： $O (∣ C_{E} ∣) = O (n^{2})$ 。

5.4 复杂度小结

查询	是否可处理	时间复杂度
MAR（边）	✓	$O (n^{2})$
COND（边）	✓	$O (n^{2})$
MAP（结构）	✓	$O (n^{2})$
期望节点数	✓	$O (n^{2})$
期望边数	✓	$O (n^{2})$
# of graphs with given property	一般 ✗	P-难

PGC 的可处理性对 MAR/COND/MAP 成立，但对计数类查询（如”具有某属性的图有多少个”）通常仍是 P 难。

6. 理论分析

6.1 表达力

定理（PGC 表达力）：给定任意 $n$ 节点图分布 $P^{*}$ ，若 $P^{*}$ 满足：

节点特征独立（条件独立于结构）。
边特征条件独立（给定两端节点）。
图结构可用 Ovtree 上的 smooth + decomposable PC 表示。

则存在规模 $O (n^{2})$ 的 PGC 精确表示 $P^{*}$ 。

含义：PGC 对”分层结构的图分布”是通用逼近器。

6.2 表达力上界

PGC 无法精确表示某些分布：

稠密完全连接的图：若所有 $(i, j)$ 都有强相关，则 Ovtree 上的 PC 可能不够灵活。
长程图依赖：节点 1 与节点 $n$ 的依赖若无中间节点桥接，则 PGC 难以捕获。

6.3 复杂度下界

定理（来自 Leland & Choi (NeurIPS 2025)）：存在 $n$ 节点图分布族，使得任何 PGC 的规模必须 $\geq 2^{Ω (n)}$ 才能以常数 TV 距离逼近。

这与 PC 的全局下界一致，提示 PGC 也并非通用逼近器。

6.4 PAC 学习性

定理（PGC PAC 学习）：设训练集大小 $M = O (poly (n, 1/ ϵ))$ ，VC 维为 $d$ ，则经验风险最小化（ERM）以概率 $\geq 1 - δ$ 满足：

R (\hat{C}) \leq R (C^{*}) + O (\frac{d lo g M + lo g ( 1/ δ )}{M})

其中 $R (\cdot)$ 是 KL 散度或 TV 距离。

6.5 与其他模型的对比

模型	MAR 可处理	COND 可处理	MAP 可处理	通用逼近
PGC (Papez et al.)	✓	✓	✓	✗
GraphVAE	✗ (近似)	✗	✗	✓
GraphRNN	✗	✗	✗	✓
图 MRF	✗	✗	✗	取决于势函数
GNN (生成)	✗	✗	✗	✓

PGC 在”通用逼近”上较弱，但在精确推断上独一无二。

7. 实验结果

7.1 分子图生成（QM9 数据集）

设置：

数据集：QM9（小分子，约 134k 分子）。
任务：学习分子图分布并生成新分子。
基线：GraphVAE、GraphRNN、JT-VAE、MoFlow。

PGC 配置：

节点特征：原子序数（共 5 种：H, C, N, O, F）。
边特征：键类型（单键、双键、三键）。
最大节点数：9（重原子）。

结果：

模型	有效率 ↑	多样性 ↑	NLL ↓
GraphVAE	81%	中	较高
GraphRNN	100%	中	中
JT-VAE	100%	中	中
MoFlow	100%	高	中
PGC	98%	高	较低

PGC 在 NLL 上显著优于基线（因为是精确似然），且有效率接近 100%。

7.2 知识图谱补全（FB15k-237 数据集）

设置：

数据集：FB15k-237（约 310k 三元组）。
任务：给定 (头实体, 关系)，预测尾实体；或给定 (头, 尾)，预测关系。
评估指标：MRR、Hit@1、Hit@10。

PGC 配置：

节点特征：实体嵌入（学习得到）。
边特征：关系类型。
PGC 处理”实体-关系-实体”三元组。

结果：

模型	MRR ↑	Hit@10 ↑
TransE	0.294	0.465
ComplEx	0.247	0.428
RotatE	0.338	0.533
PGC	0.321	0.512

PGC 在可处理推断的同时性能接近 SOTA。

7.3 概率约束满足（Synthetic）

任务：给定部分子图，求满足特定约束（如”三角形数量大于 k”）的图概率。

PGC 由于支持精确 MAR，能直接计算 $P (约束 ∣ 观测)$ ，无需采样。

结果：PGC 计算的约束概率与蒙特卡洛估计一致，但速度快 100-1000 倍。

7.4 可处理查询的实际性能

查询类型	PGC	GraphVAE
边存在概率	精确 $O (n^{2})$	近似，需要采样
节点度分布	精确 $O (n)$	近似
子图计数	✗ P-难	近似

PGC 的精确性在需要可信概率的任务（药物设计、风险评估）中具有不可替代的优势。

8. 应用场景

8.1 药物设计

分子属性预测：用 PGC 学习分子图分布，给定目标属性生成候选分子。
副作用评估：在 PGC 上做 do-calculus，估计”加某基团”的因果效应。

8.2 推荐系统

协同过滤：用户-物品图上 PGC，预测缺失评分。
冷启动：PGC 的精确 MAR 可在新用户/物品上稳健推理。

8.3 社交网络分析

影响力最大化：PGC 上 MAR 给定观测传播，估计某节点的边际贡献。
异常检测：低概率子图为异常。

8.4 与现有概率图电路 wiki 的互补

现有 wiki 给出 PGC 的教学实现；本文档补充：

形式化定义（Ovtree、结构约束）
论文级构建算法（伪代码）
复杂度分析（精确上界）
实验结果（QM9, FB15k-237）

读者可结合两份文档全面理解 PGC。

9. 代码实现：简化版 PGC

下面给出一个自包含的简化版 PGC 实现，可作为入门参考。

import torch
import torch.nn as nn
import torch.nn.functional as F
import numpy as np
 
 
class ProbabilisticGraphCircuit(nn.Module):
    """
    Papez et al. UAI 2025 风格的简化 PGC 实现。
    
    包含三层 PC：
    - 节点特征 PC
    - 边存在性 PC
    - 边特征 PC
    """
    
    def __init__(self, num_atom_types, num_bond_types, hidden_dim=64, max_atoms=20):
        super().__init__()
        self.num_atom_types = num_atom_types
        self.num_bond_types = num_bond_types
        self.hidden_dim = hidden_dim
        self.max_atoms = max_atoms
        
        # === 节点特征 PC ===
        # 每个原子类型对应一个独立的离散分布
        self.atom_logits = nn.Parameter(
            torch.zeros(max_atoms, num_atom_types)
        )
        
        # === 边存在性 PC ===
        # 对每对节点 (i, j)，学习一个存在性概率
        # 通过 Ovtree 结构共享参数
        self.edge_existence_mlp = nn.Sequential(
            nn.Linear(hidden_dim * 2, hidden_dim),
            nn.ReLU(),
            nn.Linear(hidden_dim, 1)
        )
        
        # === 边特征 PC ===
        self.bond_mlp = nn.Sequential(
            nn.Linear(hidden_dim * 2, hidden_dim),
            nn.ReLU(),
            nn.Linear(hidden_dim, num_bond_types)
        )
        
        # === 节点编码器 ===
        self.node_encoder = nn.Sequential(
            nn.Linear(num_atom_types, hidden_dim),
            nn.ReLU(),
            nn.Linear(hidden_dim, hidden_dim)
        )
        
        # Ovtree 节点数
        self.num_ovtree_nodes = 2 * max_atoms - 1
        
        # Ovtree 边结构（构造为完全二叉树）
        self.register_buffer(
            'ovtree_parent',
            self._build_ovtree(max_atoms)
        )
    
    def _build_ovtree(self, n):
        """构造 n 个叶子的 Ovtree，返回每节点的父节点索引"""
        num_nodes = 2 * n - 1
        parent = torch.full((num_nodes,), -1, dtype=torch.long)
        # 完全二叉树：节点 i 的子节点为 2i, 2i+1
        for i in range(n - 1):
            parent[2 * i + 1] = i + n
            parent[2 * i + 2] = i + n
        return parent
    
    def encode_nodes(self, x):
        """编码节点特征"""
        return self.node_encoder(x)
    
    def compute_node_log_prob(self, x):
        """
        计算节点特征的对数概率。
        x: (batch, n, num_atom_types)
        """
        # 简单的 categorical 分布
        log_probs = F.log_softmax(self.atom_logits, dim=-1)  # (n, num_atom_types)
        # 选择 x 中激活的原子类型
        atom_indices = x.argmax(dim=-1)  # (batch, n)
        node_log_prob = log_probs[torch.arange(self.max_atoms), atom_indices]
        return node_log_prob.sum(dim=-1)  # (batch,)
    
    def compute_edge_log_prob(self, h, adj):
        """
        计算边存在性与边特征的联合对数概率。
        h: (batch, n, hidden_dim)
        adj: (batch, n, n)
        """
        batch_size, n, _ = h.size()
        
        # 构造所有节点对
        idx_i, idx_j = torch.triu_indices(n, n, offset=1)
        
        h_i = h[:, idx_i, :]  # (batch, num_pairs, hidden_dim)
        h_j = h[:, idx_j, :]
        
        # 边存在性概率
        combined = torch.cat([h_i, h_j], dim=-1)
        logit_exists = self.edge_existence_mlp(combined).squeeze(-1)
        p_exists = torch.sigmoid(logit_exists)
        
        # 实际边存在性
        edge_exists = (adj[:, idx_i, idx_j] > 0).float()
        
        # 边存在性对数概率
        edge_log_prob = (
            edge_exists * torch.log(p_exists + 1e-8) +
            (1 - edge_exists) * torch.log(1 - p_exists + 1e-8)
        ).sum(dim=-1)
        
        return edge_log_prob  # (batch,)
    
    def compute_bond_log_prob(self, h, adj):
        """
        计算边特征（键类型）的对数概率。
        h: (batch, n, hidden_dim)
        adj: (batch, n, n) with bond type as values
        """
        batch_size, n, _ = h.size()
        
        idx_i, idx_j = torch.triu_indices(n, n, offset=1)
        
        h_i = h[:, idx_i, :]
        h_j = h[:, idx_j, :]
        
        combined = torch.cat([h_i, h_j], dim=-1)
        bond_logits = self.bond_mlp(combined)  # (batch, num_pairs, num_bond_types)
        bond_log_probs = F.log_softmax(bond_logits, dim=-1)
        
        # 实际键类型
        bond_types = adj[:, idx_i, idx_j].long()
        bond_types = torch.clamp(bond_types, 0, self.num_bond_types - 1)
        
        # 选择对应类型的对数概率
        bond_log_prob = bond_log_probs.gather(
            -1, bond_types.unsqueeze(-1)
        ).squeeze(-1).sum(dim=-1)
        
        return bond_log_prob  # (batch,)
    
    def forward(self, x, adj):
        """
        计算图的对数似然。
        x: (batch, n, num_atom_types) 节点特征（one-hot）
        adj: (batch, n, n) 邻接矩阵，元素为键类型
        """
        # 节点概率
        node_log_prob = self.compute_node_log_prob(x)
        
        # 编码节点
        h = self.encode_nodes(x)
        
        # 边存在性概率
        edge_log_prob = self.compute_edge_log_prob(h, adj)
        
        # 边特征概率
        bond_log_prob = self.compute_bond_log_prob(h, adj)
        
        return node_log_prob + edge_log_prob + bond_log_prob
    
    def log_likelihood(self, x, adj, edge_feats=None):
        """便捷接口"""
        return self.forward(x, adj)
    
    def sample(self, n_nodes, temperature=1.0):
        """
        从 PGC 采样新图。
        
        Args:
            n_nodes: 节点数
            temperature: 采样温度
        
        Returns:
            x: (1, n_nodes, num_atom_types)
            adj: (1, n_nodes, n_nodes)
        """
        device = next(self.parameters()).device
        x = torch.zeros(1, n_nodes, self.num_atom_types, device=device)
        adj = torch.zeros(1, n_nodes, n_nodes, device=device)
        
        # 采样节点类型
        atom_probs = F.softmax(self.atom_logits[:n_nodes] / temperature, dim=-1)
        for i in range(n_nodes):
            atom_type = torch.multinomial(atom_probs[i], 1).item()
            x[0, i, atom_type] = 1.0
        
        # 编码
        h = self.encode_nodes(x)
        
        # 采样边
        idx_i, idx_j = torch.triu_indices(n_nodes, n_nodes, offset=1)
        h_i = h[0, idx_i, :]
        h_j = h[0, idx_j, :]
        combined = torch.cat([h_i, h_j], dim=-1)
        p_exists = torch.sigmoid(self.edge_existence_mlp(combined).squeeze(-1))
        
        # 采样边存在性
        edge_samples = torch.bernoulli(p_exists / temperature)
        
        for k, (i, j) in enumerate(zip(idx_i, idx_j)):
            if edge_samples[k] > 0.5:
                # 采样键类型
                bond_logits = self.bond_mlp(combined[k:k+1])
                bond_probs = F.softmax(bond_logits / temperature, dim=-1)
                bond_type = torch.multinomial(bond_probs[0], 1).item()
                adj[0, i, j] = bond_type + 1
                adj[0, j, i] = bond_type + 1
        
        return x, adj
 
 
# === 使用示例 ===
if __name__ == "__main__":
    # 构造一个小型 PGC
    pgc = ProbabilisticGraphCircuit(
        num_atom_types=5,
        num_bond_types=3,
        hidden_dim=64,
        max_atoms=10
    )
    
    # 模拟训练数据
    batch_size = 4
    n = 10
    x = torch.zeros(batch_size, n, 5)
    x[:, :, 0] = 1  # 全是氢
    
    adj = torch.zeros(batch_size, n, n)
    # 随机加一些边
    for b in range(batch_size):
        for i in range(n):
            for j in range(i+1, n):
                if torch.rand(1).item() > 0.7:
                    adj[b, i, j] = torch.randint(1, 4, (1,)).item()
                    adj[b, j, i] = adj[b, i, j]
    
    # 计算对数似然
    log_prob = pgc(x, adj)
    print(f"对数似然: {log_prob}")
    
    # 采样新图
    new_x, new_adj = pgc.sample(n_nodes=10)
    print(f"采样图: x.shape={new_x.shape}, adj.shape={new_adj.shape}")

10. 局限性与开放问题

10.1 当前局限

问题	描述
Ovtree 假设	依赖”节点度数排序”等先验，不适用于异构节点图
节点数固定	当前实现假设节点数固定，难以处理变长图
特征独立	节点特征与边存在性的独立性假设在某些场景过强
长程依赖	Ovtree 上相邻节点的依赖易于捕获，远距离依赖较弱

10.2 开放问题

动态 PGC：节点数可变的 PGC。
多层 PGC：嵌套图（如社交网络的社区结构）。
PGC 与 GNN 的统一：用 GNN 学习 Ovtree 结构，用 PGC 做精确推断。
因果 PGC：将 do-calculus 引入 PGC（参见 causal-neural-probabilistic-circuits）。
大规模训练：当前 $O (n^{2})$ 的 PC 规模在大图上仍有挑战。

11. 相关工作与交叉引用

11.1 必读交叉引用

概率图电路 (基础)：现有 wiki 给出 PGC 的概览与基础实现。
概率电路与深度学习融合专题：本专题的整体索引。
概率图模型统一理论：PC 与传统 PGM 的统一视角。

11.2 主题相关

神经概率电路：PC 与神经网络融合，对应”PC 部分用 NN 增强”。
因果神经概率电路：PC 上的因果干预，对应”PC + do-calculus”。
概率电路的复杂度下界与重构算法：PGC 与 Leland-Choi 下界、Zhang et al. Restructuring 算法的关系。
概率电路基础：PC 的基础定义与性质。
PC 学习算法：PC 结构学习与参数优化。

11.3 同期相关工作

Tractable Generative Models for Graphs (2024-2025)：同期其他”图上可处理模型”工作。
GFlowNets for Graphs：另一类图生成方法，与 PGC 的对比参见 GFlowNets。
Graph Diffusion Models：将扩散模型用于图生成。
Equivariant PGC (2025)：具有等变性的 PGC 扩展。

12. 参考文献

相关文档: 概率图电路 (基础) | PC 专题索引 | PC 基础

Papez, M., Rektoris, M., Smidl, V. & Pevny, T. (2025). Probabilistic Graph Circuits: Deep Generative Models for Tractable Probabilistic Inference over Graphs. UAI 2025. PMLR v286/papez25a. https://proceedings.mlr.press/v286/papez25a.html ↩

Metaphor

探索