在我们关于图模型的推断的讨论中，我们假设图的结构已知且固定。然而，也有一些研究超出了推断问题的范围，关注于从数据推断图结构本身（Friedman and Koller，2003）。这需要我们定义一个可能结构的空间，以及用于对每个结构评分的度量。
从贝叶斯的观点来看，理想情况下，我们需要计算图结构上的后验概率分布，然后关于概率分布求平均，进行预测。如果我们有一个关于第个图的先验概率分布，那么后验概率分布为
其中是一个观测数据集。模型证据提供了每个模型的分数。然而，计算模型证据涉及到对潜在变量的积分或求和，这对于许多模型来说是一个计算量相当大的问题。
探索图结构的空间也是一个问题。由于不同图结构的数量随着结点数量的增加而指数增长，因此通常需要借助启发式方法找到好的候选。