2
$\begingroup$

In Probabilistic Graphical Models by Koller and Friedman, there is a proposition -

The PDAG $\mathcal K$ returned by Build-PDAG is necessarily chordal.

Build-PDAG is an algorithm that builds the equivalence-class-PDAG for the perfect map, if one exists.

My confusion is with the definition of chordal graph.

If a PDAG is chordal, when its undirected version is chordal (which is the definition the text also gives), it implies that a perfect map of below type is not possible. Whence my question - do BN perfect maps need to be chordal.

enter image description here

However, if chordal graph is only for undirected graphs, then the above theorem is appropriate. The loop $A-B-X-C-A$ will definitely contain an immorality and hence the edges for the immorality will become oriented by Build-PDAG.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
3
$\begingroup$

No. Bayesian Network perfect maps need not be chordal. And your example is a case in point. At least, if chordality is really defined as the chordality of the undirected version.

So this is a bit confusing. But in the text following the cited statement, what they actually use is the fact that the undirected components of the chain graph $\mathcal K$ are chordal. So my guess is that that's what they refer to by "$\mathcal K$ is chordal".

Then, in your example, $\mathcal K$ would be the chain graph:

enter image description here

and the only nontrivial undirected component present is:

enter image description here

And this component is indeed chordal. And that, IIUC, is all they need in their proof of Theorem 3.10.

Improve this answer
$\endgroup$
2
  • $\begingroup$ I agree to frank's take on the interpretation of chordality for PDAG(s) in this context; it makes sense here. However, I also found the exact portion where they define chordal graphs for graphs that contain directed edges. Definition 2.25 in the text- A graph $\mathcal K$ is said to be chordal if its underlying undirected graph is chordal. So I think the author's definition of chordal graphs, for graphs with directed edges, is not very clear here. $\endgroup$
    – Anirban Chakraborty
    Commented Oct 22, 2022 at 14:05
  • 1
    $\begingroup$ @AnirbanChakraborty Yes, I read this definition. But I could not find a definition of "underlying undirected graph". $\endgroup$
    – frank
    Commented Oct 22, 2022 at 14:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.