2
$\begingroup$

I am reading CPDAG, can anyone please explain why G1 and G3 are not equivalence classes as in the picture below? Thank you very much!

according to https://www.cs.cmu.edu/afs/cs/project/jair/pub/volume18/acid03a-html/node2.html .

"Theorem 1 [59] Two DAGs are equivalent if and only if they have the same skeleton and the same v-structures.

The skeleton of a DAG is the undirected graph that results from ignoring the directionality of every edge.

A v-structure in a DAG $H$ is an ordered triplet of nodes, $(x,y,z)$, such that (1) $H$ contains the arcs $x\rightarrow y$ and $y \leftarrow z$, and (2) the nodes $x$ and $z$ are not adjacent in $H$. A head-to-head pattern (shortened h-h) in a DAG $H$ is an ordered triplet of nodes, $(x,y,z)$, such that $H$ contains the arcs $x\rightarrow y$ and $y \leftarrow z$. Note that in an h-h pattern $(x,y,z)$ the nodes $x$ and $z$ can be adjacent."

The concept of equivalence of DAGs partitions the space of DAGs into a set of equivalence classes.

enter image description here

Improve this question
$\endgroup$
4
  • 4
    $\begingroup$ Could you please explain/define the term CPDAG in your post? Also what do you think yourself, why aren't G1 and G3 in equivalence class, any idea? $\endgroup$
    – fade2black
    Aug 13 '17 at 11:17
  • $\begingroup$ It's also weird why you ask "why $G_1$ is not in class $G$" when I can read on the fine prints under the picture saying $G_1$ is in class $G$. $\endgroup$
    – Apiwat Chantawibul
    Aug 13 '17 at 12:04
  • $\begingroup$ Thank you. I added the description in the question. Please have a look. Thank you! $\endgroup$
    – user2842390
    Aug 13 '17 at 14:55
  • $\begingroup$ What is a CPDAG? (You've expanded the acronym but not given a definition.) What does "equivalent" mean? $\endgroup$
    – David Richerby
    Jan 11 '18 at 1:25
2
$\begingroup$

They have different v-structures: $G_1$ has the v-structures $(x_3,y,x_4),(x_4,y,x_3)$, whereas $G_3$ has the v-structures $(x_1,x_4,y),(y,x_4,x_1)$.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thank you, however, I can say so with G1 and G4 (but the example said that G1 G4 are in its equivalence class): "$G_1$ has the v-structures $(x_3,y,x_4),(x_4,y,x_3)$ whereas $G_4$ has the v-structures $(x_1,x_4,y),(y,x_4,x_1)$". So why are they sill equivalent? $\endgroup$
    – user2842390
    Aug 14 '17 at 6:25
  • $\begingroup$ It could be a typo. Ask the authors. $\endgroup$
    – Yuval Filmus
    Aug 14 '17 at 7:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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