在概率图模型中很少有真正的数学图论，其中真正的数学图论是指关于团、顶点顺序、最大流最小割定理等的证明。甚至没有使用像欧拉定理和握手引理这样基本的东西，尽管我想人们可能会调用它们来检查用于更新概率估计的计算机代码的某些属性。此外，概率图模型很少使用超过图类的子集，例如多图。概率图模型中不使用关于图中流的定理。

如果学生 A 是概率专家但对图论一无所知，学生 B 是图论专家但对概率一无所知，那么 A 肯定会比 B 更快地学习和理解概率图模型。

从严格意义上讲，图论似乎与 PGM 松散地联系在一起。然而，图算法派上用场了。PGM 始于消息传递推理，它是图上一般类消息传递算法的一个子集（可能是其中出现“图形”一词的原因）。图割算法广泛用于计算机视觉中的马尔可夫随机场推断；它们基于类似于 Ford-Fulkerson 定理的结果（最大流量等于最小切割）；最流行的算法可能是 Boykov-Kolmogorov 和 IBFS。

参考。[Murphy, 2012 , §22.6.3] 涵盖了用于 MAP 推理的图割。另见[Kolmogorom 和 Zabih，2004 年；Boykov 等人，PAMI 2001]，其中涵盖了优化而不是建模。

已经有一些工作调查了低密度奇偶校验码的易于解码（当您将其视为概率图并应用循环信念传播时，它会得到很好的结果）与奇偶校验矩阵形成的图的周长之间的联系. 这种与周长的联系可以追溯到 LDPC 被发明的时候[1]，但在 Mackay 等人 [4] 分别重新发现并注意到它们的特性之后，在过去十年左右 [2][3] 有进一步的工作.

我经常看到珍珠关于信念传播的收敛时间取决于被引用图的直径的评论。但我不知道有什么工作可以查看非树形图中的图直径以及它有什么影响。

1. RG加拉格。低密度奇偶校验码。麻省理工学院出版社，1963
2. IE Bocharova、F. Hug、R. Johannesson、BD Kudryashov 和 RV Satyukov。基于超图的大周长低密度奇偶校验码。In Information Theory Proceedings (ISIT), 2010 IEEE International Symposium on, pages 819 – 823, 2010。
3. SC Tatikonda。和积算法的收敛。在信息理论研讨会上，2003 年。论文集。2003 IEEE，第 222 – 225 页，2003
4. 大卫 JC 麦凯和 RM 尼尔。低密度奇偶校验码的接近香农极限性能。电子快报，33（6）：457–458，1997。

图算法在概率图模型中的一种成功应用是Chow-Liu 算法。它解决了寻找最优（树）图结构的问题，基于最大生成树（MST）算法。

树形图模型上的联合概率可以写成：

$$\begin{equation} p(x|T) = \prod_{t\in V} p(x_t) \prod_{(s,t) \in E} \frac{p(x_s, x_t)}{p(x_s)p(x_t)} \end{equation}$$ 我们可以写下一个标准化的对数似然如下： $$\begin{equation} \frac{1}{N}\log P(D|\theta, T) = \sum_{t\in V}\sum_k p_{ML}(x_t=k) \log p_{ML}(x_t=k) + \sum_{(s,t)\in E} I(x_s; x_t|\theta_{st}) \end{equation}$$ 在哪里$I(x_s;x_t|\theta_{st})$是之间的互信息$x_s$和$x_t$给定计算节点次数的经验最大似然 (ML) 分布$x$处于状态$k$. 由于第一项与拓扑无关$T$，我们可以忽略它，专注于最大化第二项。

通过计算最大权重生成树来最大化对数似然，其中边权重是成对互信息项$I(x_s;x_t|\theta_{st})$. 使用Prim 算法和Kruskal 算法可以找到最大权重生成树。