  The graphical structure of Probabilistic Graphical Models (PGMs) encodes the
conditional independence (CI) relations that hold in the modeled distribution.
Graph algorithms, such as d-separation, use this structure to infer additional
conditional independencies, and to query whether a specific CI holds in the
distribution. 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. 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 prove an
approximation guarantee for independence relations derived from marginal CIs.
