The graphical structure of Probabilistic Graphical Models (PGMs) represents
the conditional independence (CI) relations that hold in the modeled
distribution. Every separator in the graph represents a conditional
independence relation in the distribution, making them the vehicle through
which new conditional independencies are inferred and verified. The notion of
separation in graphs depends on whether the graph is directed (i.e., a Bayesian
Network), or undirected (i.e., a Markov Network).
The premise of all current systems-of-inference for deriving CIs in PGMs, is
that the set of CIs used for the construction of the PGM hold exactly. In
practice, algorithms for extracting the structure of PGMs from data discover
approximate CIs that do not hold exactly in the distribution. In this paper, we
ask how the error in this set propagates to the inferred CIs read off the
graphical structure. More precisely, what guarantee can we provide on the
inferred CI when the set of CIs that entailed it hold only approximately? It
has recently been shown that in the general case, no such guarantee can be
provided.
In this work, we prove new negative and positive results concerning this
problem. We prove that separators in undirected PGMs do not necessarily
represent approximate CIs. That is, no guarantee can be provided for CIs
inferred from the structure of undirected graphs. We prove that such a
guarantee exists for the set of CIs inferred in directed graphical models,
making the $d$-separation algorithm a sound and complete system for inferring
approximate CIs. We also establish improved approximation guarantees for
independence relations derived from marginal and saturated CIs.

本文研究了概率图模型中近似条件独立性的推断和验证问题，发现无向概率图并不能提供准确的条件独立性推断保证，而有向概率图可以通过 $d$-separation 算法准确推断近似条件独立性。此外，还提出了改进的近似保证方法和独立关系推断算法。