Maier et al. (2010) introduced the relational causal model (RCM) for representing and inferring causal relationships in relational data. A lifted representation, called abstract ground graph (AGG), plays a central role in reasoning with and learning of RCM. The correctness of the algorithm proposed by Maier et al. (2013a) for learning RCM from data relies on the soundness and completeness of AGG for relational dseparation to reduce the learning of an RCM to learning of an AGG. We revisit the definition of AGG and show that AGG, as defined in Maier et al. (2013b), does not correctly abstract all ground graphs. We revise the definition of AGG to ensure that it correctly abstracts all ground graphs. We further show that AGG representation is not complete for relational d-separation, that is, there can exist conditional independence relations in an RCM that are not entailed by AGG. A careful examination of the relationship between the lack of completeness of AGG for relational d-separation and faithfulness conditions suggests that weaker notions of completeness, namely adjacency faithfulness and orientation faithfulness between an RCM and its AGG, can be used to learn an RCM from data.
Discovery of causal relationships from observational and
experimental data is a central problem with applications
across multiple areas of scientific endeavor. There has been
considerable progress over the past decades on algorithms
for eliciting causal relationships from data under a broad
range of assumptions
Motivated by the limitations of traditional approaches to
learning causal relationships from relational data, Maier
and his colleagues introduced the relational causal model
(RCM)
We follow notational conventions introduced in
Every relationship class Ri have two or more distinct
entity classes.2 We denote by I all item classes E [ R . We
denote by IX an item class that has an attribute class X
assuming, without loss of generality, that the attributes of
different item classes are disjoint. Participation of an entity
class Ej in a relationship class Ri is denoted by Ej 2Ri
1The examples are taken from
2In general, the same entity class can participate in a relationship class in two or more different roles. For simplicity, we only consider relationship classes only with distinct entity classes. [Prod, Dev, Emp] .competence ! [Prod] .success
[Emp] .competence ! [Emp] .salary salary competence employee develops success product
Definition 2. A relational skeleton is an instantiation of
relational schema S , represented by a graph of entities and
relationships. Let (I ) denote a set of items of item class
I 2 Iin . Let ij , ik 2 such that ij 2 (Ij ), ik 2 (Ik),
and Ij , Ik 2 I, then we denote ij ⇠ ik if there exists an
edge between ij and ik in .
Relational causal model
Definition 3. A relational path P = [Ij , . . . , Ik] is an alternating sequence of entity class E 2 Eand relationship class R 2 R. An item class Ij is called base class or perspective and Ik is called a terminal class. A relational path should satisfy: 1. for every [E, R] or [R, E], E 2R; 2. for every [E, R, E0], E 6= E0; and 3. for every [R, E, R0], if R = R0, then card (R, E) = many.
All valid relational paths on the given schema S are debnyotPedi:bjy=P[SP.kW]jke=ideonr oPtei:th=e [lPenkg]|ktPh=|ioffoPr 1b y |Pi |, ajs u|bpPat|h, and the reversed path by P˜ = [P|P |, . . . , P2, P1]. Note that all subpaths of a relational path as well as the corresponding reverse paths are valid. A relational variable P.X is a pair of a relational path P and an attribute class X for the terminal class of P . A relational variable is said to be canonical if its relational path has a length equal to 1. A relational dependency is of the form [Ij , . . . , Ik].Y ! [Ij ].X such that its cause and effect share the same base class and its effect is canonical.
Given a relational schema S , a relational (causal) model M⇥ is a pair of a structure M = hS , Di, where D is the set of relational dependencies, and ⇥ is a set of parameters. We assume acyclicity of the model so that the attribute classes can be partially ordered based on D. The parameters ⇥ define conditional distributions, p([I ].X |Pa([I ].X )), for each pair (I , X ) where I 2 I, X 2 A(I ), and Pa([I ].X ) is a set of causes of [I ].X , i.e., {P.Y |P.Y ! [I ].X 2D}. This paper focuses on the structure of RCM. Hence we often omit parameters ⇥ from M.
Terminal Set and Ground Graph Because a skeleton is an instantiation of an underlying schema, a ground graph is an instantiation of the underlying RCM given a skeleton translating relational dependencies to every entity and relationship in the skeleton. It is obtained by interpreting the dependencies defined by the RCM on the skeleton using the terminal sets of each of the instances in the skeleton. Given a relational skeleton , the terminal set of a relational path P given a base b 2 (P1), denoted by P |b, is the set of terminal items reachable from b when we traverse the skeleton along P . Formally, a terminal set P |b is defined recursively, P 1:1|b = {b} and P 1:`|b = {i 2
S (P`) | j 2P 1:` 1|b, i ⇠ j}\ 1 k<`P 1:k|b.
This implies that P 1:`|b and P |b will be disjoint for 1
` < |P |. Restricting the traversals so as not to revisit any
previously visited items corresponds to the bridge
burning semantics (hereinafter, BBS)
Throughout this paper, unless specified otherwise, we assume a relational schema S , a set of relational dependencies D, and an RCM M = hS , Di. 3
An RCM can be seen as a meta causal model or a
template whose instantiation, a ground graph, corresponds to a
traditional causal model (e.g., a causal Bayesian network).
Reasoning with causal models relies on conditional
independence (CI) relations among variables. Graphical
criteria such as d-separation
Definition 4 (Relational d-separation
There are two things implicit in this definition: (i) allground-graphs semantics which implies that d-separation must be hold over all instantiations of the model; (ii) the terminal set items of two different relational variables may overlap (which we refer to as intersectability). In other words, two relational variables U = P.X and V = P 0.X of the same perspective B and the same attribute, are said to be intersectable if and only if: 9 2 ⌃ S 9 b2 (B)P |b \ P 0|b 6= ; . (1) In order to allow testing of conditional independence on all ground graphs, Maier et al. (2013a) introduced an abstract ground graph (AGG), which abstracts all ground graphs and is able to cope with the intersectability of relational variables. We first recapitulate the original definition of AGGs. 3.1
An abstract ground graph AGGMB is defined for a given
relational model M and a perspective B 2 I
We denote by RVB the set of all relational variables (RV) whose paths originate in B. We denote by RVEB the set of all edges between the relational variables in RVB . A relational variable edge (RVE) implies direct influence arising from one or more dependencies in D. There is an RVE P.X ! Q.Y if there exists a dependency R.X ! [IY ].Y 2 D that can be interpreted as a direct influence from P.X to Q.Y from perspective B. Such an interpretation is implemented by an extend function, which takes two relational paths and produces a set of relational paths: If P 2extend(Q, R), then there exists an RVE P.X ! Q.Y P no1 Q E1 Ra E2 Rb E3 Rb E2 Rc E4
P
Q E1 Ra E2 Rc E4
P
Rb Q
E3
We denote by IVB the set of intersection variables (IVs),
i.e., unordered pairs of intersectable relational variables in
RVB. Given two RVs P.X and P 0.X that are intersectable
with each other, we denote the resulting intersection
variable by P.X \ P 0.X (Here, the intersection symbol ‘\ ’
denotes intersectability of the two relational variables). By
the definition
Two AGGs with different perspectives share no vertices nor edges. Hence, we view all AGGs, {AGGB}B2I , as a collection or a single multi-component graph AGG = SB2I AGGB. We similarly define RV, IV, RVE, and IVE as the unions of their perspective-based counterparts. For any mutually disjoint sets of relational variables U, V, and W, one can test U ? V | W, conditional independence admitted by the underlying probability distribution, by checking U¯? ? V¯ | W¯ (traditional) d-separation on an AGG3, where V¯ includes V and their related IVs, V¯ = V [ { V \ T 2IV | V 2V}. Figure 3 illustrates relational d-separation on an AGG.
We later show that the preceding definition of AGG does 3We denote conditional independence by ‘? ’ in general. We use ? ‘? ’ to represent (traditional) d-separation on a directed acyclic graph., e.g., AGGM or GGM . Furthermore, we parenthesize conditional independence and use a subscript to specify the scope of the conditional independence, if necessary.
[Emp].comp
Y [[EEmmpp,,DDeevv,,PPrroodd,,FDuenvd\,,EBmizp,,FDuenvd,,PPrroodd]]..ssuucccc
not properly abstract all ground graphs; nor does it
guarantee the correctness of reasoning about relational
dseparation in an RCM. We revise the definition of AGG
(Section 3.2) so as to ensure that the resulting AGG
abstracts all ground graphs. However, we find that even with
the revised definition of AGG, the AGG representation is
not complete for relational d-separation, that is, there can
exist conditional independence relations in an RCM that
are not entailed by AGG (Section 4.1). A careful
examination of the lack of completeness of AGG for relational
d-separation with respect to causal faithfulness yields
useful insights that allow us to make use of weaker notions of
faithfulness to learn RCM from data (Section 4.2).
Because of the importance of IV and IVE in AGG in
reasoning about relational d-separation, it is possible that
errors in abstracting all ground graphs could lead to errors
in CI relations inferred from an AGG. We proceed to show
that 1) the criteria for determining intersectability
The declarative characterization of intersectability (Eq. 1)
does not offer practical procedural criteria to determine
intersectability. Based on the criteria
R|ij \ P |b 6= ; 2) 9 2 ⌃ S 9 b2 (B) P |b \ P 0|b 6= ; 3) 9 2 ⌃ S 9 b2 (B)9 ij2 Q|b
R|ij \ P |b \ P 0|b 6= ; not a prefix of the other. We will prove that the preceding criteria are not sufficient. In essence, we will show the conditions under which non-emptiness of P |b \ Q|b for any b 2 (B) in any skeleton always contradicts the BBS. For the proof, we define LLRSP(P, Q) (the length of the longest required shared path) for two relational paths P and Q of the common perspective as
max{` | P 1:` = Q1:`, 8 2 ⌃ S 8 b2 (B) P 1:`|b = 1}.
LLRSP(P, Q) is computed as follows. Initially set ` = 1
since P1 = Q1. Repeat incrementing ` by 1 if P`+1 = Q`+1
and either P` 2 Ror P` 2 Ewith card(P`, P`+1) = one.
Lemma 1. Given a relational schema S, let P and Q
be two different relational paths satisfying the (necessary)
criteria of
The lemma demonstrates the criteria by
Based on the definition
Example 1. Let S be a relational schema where E = {Ij , Ik, B, E1, E2, E3}, R = {Ri}i5=1 such that R1 = hB, E1i, R2 = hE1, E3i, R3 = hE1, E2i, R4 = hE2, E3, Iki, R5 = hIk, Ij i with the cardinality of each relationship and each entity in the relationship being one. Let • Q = [B, R1, E1, R2, E3, R4, Ik, R5, Ij ], • R = [Ij , R5, Ik, R4, E3, R2, E1, R3, E2, R4, Ik], • P = [B, R1, E1, R3, E2, R4, Ik], and • P 0 = [B, R1, E1, R2, E3, R4, Ik].
Observe that 1. P 2extend (Q, R); 2. P 0 and P are intersectable; and 3. P 0 is a subpath of Q.
This example satisfies Eq. 1 and Eq. 4. Assume for contradiction that there exists a skeleton satisfying Eq. 3. Since, in this example, the cardinality of each relationship and each entity in the relationship is one, for each b 2 (B), there exists only one ij 2Q|b and only one ik 2P |b. By the assumption, P 0|b = {ik}. Since P 0 is a subpath of Q, P 0|b will end at i0k = R1:3|ij (see Figure 5). Due to BBS, R|ij \ R1:3|ij = ; , that is, {ik}\{ i0k} = ; . This contradicts the assumption that ik = i0k.
This counterexample clearly represents there is an interdependency between intersection variables and RVEs. Therefore, we revise the definition of IVE accompanying co-intersectability.
Definition 6 (IVE). There exists an IVE edge, P.X \ P 0.X ! Q.Y (or P.X ! Q.Y \ Q0.Y ), if and only if there exists a relational path R such that R.X ! [IY ].Y 2 D, P 2 Q on R, and hQ, R, P, P 0i (or hP, R˜, Q, Q0i) is cointersectable.
To determine IVEs, co-intersectability of a tuple can be computed by solving a constraint satisfaction problem involving four paths in the tuple.
Implications of Co-intersectability We investigated the
necessary and sufficient criteria for intersectability and
revised the definition of IVE so as to guarantee that AGG
correctly abstracts all ground graphs as asserted (although
incorrectly) by Theorem 4.5.2
We first revisit the definition of relational d-separation. Given three disjoint sets of relational variables U, V, and W of a common perspective B 2 I, U and V are relational d-separated given W, denoted by (U ? V | W) , M if and only if 8 2 ⌃ S 8 b2 (B) (U|b? ?
V|b | W|b)GGM .
From Theorem 4.5.4 of
V | W)M ) ¯ U? ?
The completeness can be proved by the construction of a skeleton 2 ⌃ S demonstrating d-connection (U|b? 6? V|b | W|b)GGM for some b 2 (B) if (U¯? 6? V¯ | W¯ )AGGM . In other words, we might disprove the completeness by showing iy ( U¯? 6?
V | W¯ )AGGM ^ ¯ 8 2 ⌃ S 8 b2 (B) (U|? b ?
V|b | W|b)GGM . 4.1
The following counterexample shows that AGG is not complete for relational d-separation.
Example. Let S = hE , R, A, cardi be a relational schema such that: E = {Ei}i5=1; R = {Rj }j3=1 with R1 = hE1, E2, E4i, R2 = hE2, E3i, and R3 = hE3, E4, E5i; A = {E2 : {Y } , E3 : {X} , E5 : {Z}}; and 8 R2R 8 E2 Rcard (R, E) = one. Let M = hS, Di be a relational model with
D = {D1.X ! [IY ].Y, D2.Z ! [IY ].Y } such that D1 = [E2, R2, E3, R3, E4, R1, E2, R2, E3] and D2 = [E2, R2, E3, R3, E5]. Let P.X, Q.Y , S.Z, and S0.Z be four relational variables of the same perspective B = E1 where their relational paths are distinct where • P = [E1, R1, E2, R2, E3], • Q = [E1, R1, E4, R3, E3, R2, E2], • S = [E1, R1, E4, R3, E5], and • S0 = [E1, R1, E2, R2, E3, R3, E5].
Given the above example, we can make two claims. Claim 1. P.X? 6? S0.Z | Q.Y .
AGGM Proof. See Appendix.
Assuming that AGG is complete for relational dseparation, we can infer (P.X 6? S0.Z | Q.Y )M and there must exist a pair of a skeleton and a base b 2 (B) that satisfies (P.X|b? 6? S0.Z|b | Q.Y |b)GGM . However, we claim that such a skeleton and base may not exist. iy ix
The counterexample demonstrates that a d-connection path captured in an AGGM might not have a corresponding d-connection path in any ground graph.
Corollary 1. The revised (as well as the original) abstract ground graph for an RCM is not complete for relational d-separation.
It is possible that an additional test can be utilized to check whether there exists such a ground graph that can represent a d-connection path captured in AGGM. However, the efficiency of such an additional test is unknown and designing such a test is beyond the scope of this paper. 4.2
In light of the preceding result that AGG is not complete for relational d-separation, we proceed to examine the relationship between an RCM and its lifted representation in terms of the sets of conditional independence relationships that they admit. In RCM, there are several levels of relationship regarding the sets of conditional independence: between the underlying probability distributions and the ground graphs, between the ground graphs of an RCM and the RCM, and between the RCM and its AGG:
{p $ GGM⇥ } 2 ⌃ S $ M ⇥ $ AGGM In RCM, the causal Markov condition and causal faithfulness condition (see below) can be applied between a ground graph GGM and its underlying probability distribution p. Both conditions are assumed for learning an RCM from relational data. Relational d-separation requires a set of conditional independence of M⇥ using those deduced from every ground graph GGM⇥ for every 2 ⌃ S . In light of the lack of completeness of AGG for relational d-separation, the set of conditional independence relations admitted by M⇥ and its lifted representation AGGM are not necessarily equivalent (see Corollary 1).
We will relate M and AGGM using an analogy of causal
Markov condition and faithfulness
Definition 7 (Causal Markov Condition
The causal Markov condition (i.e., local Markov condition) is not directly translated into the relationship between AGGM and M since they refer to different variables. However, the soundness of AGGM for relational d-separation of M (i.e., global Markov condition) would be sufficient to interpret causal Markov condition between AGGM and M. That is,
¯ 8 U,V,W 2 RV U? ?
V | W¯ ¯
AGGM ) (U ? V | W )M where U , V , and W are distinct relational variables sharing a common perspective.
Definition 8 (Causal Faithfulness Condition
By the counterexample above, M is not strictly faithful to AGGM, because more conditional independences hold in M than those entailed by AGGM. 4.2.1
Definition 9 (Adjacency-Faithfulness
Let U , V be two distinct relational variables of the same perspective B. We limit U and V to be non-intersectable to each other. Otherwise, they must not be adjacent to each other by the definition of RCM since an edge between intersectable relational variables yields a feedback in a ground graph. If there is an edge U ! V in AGGM, 8 W✓ RVB\{U,V } (U 6?
V | W)M
We can construct a skeleton 2⌃ S where its
corresponding ground graph GGM satisfies that U |b and V |b are
singletons and U |b [ V |b are disjoint to (RVB \ {U, V }) |b
for b 2 (B). Lemma 4.4.1 by
Definition 10 (Orientation-Faithfulness
Let U , V , and W be three distinct relational variables of the same perspective B forming an unshielded triple in AGGM. Similarly, V is not intersectable to both U and W . The condition (O1) can be written as 8 T✓ RVB\{U,W }(U 6?
W | T [ { V })M if edges are oriented as U ! wise, V
W in AGGM. Other8 T✓ RVB\{U,W }(U 6?
W | T \ {V })M for the condition (O2). Again, constructing a minimal skeleton for U , V , and W guarantees that no T 2RVB \ {U, V, W } can represent any item in {U |b, V |b, W |b}. Thus, the existence of V in the conditional determines (in)dependence in the ground graph induced from the minimal skeleton.
Learning RCM with Non-complete AGG RCD (Relational Causal Discovery, Maier et al. (2013a)) is an algorithm for learning the structure of an RCM from relational data. In learning RCM, AGG plays a key role: AGG is constructed using CI tests to obtain the relational dependencies of an RCM. The lack of completeness of AGG for relational d-separation in RCM raises questions about the correctness of RCD. A careful examination of AGG through the lens of faithfulness suggests that adjacency-faithful and orientation-faithful conditions can be applied to AGGM to recover correct partially-oriented dependencies for an RCM. However, it is still unclear whether RCD recovers maximally-oriented dependencies with the acyclicity of AGG (i.e., relational variables) not the acyclicity of RCM (i.e., attribute classes). This raises the possibility of an algorithm for learning the structure of an RCM from relational data that does not require the intermediate step of constructing a lifted representation. 5
There is a growing interest in relational causal models
We first prove Lemma 1 in Section 3.2.1.
Lemma. Given a relational schema S , let P and Q be
two different relational paths satisfying the (necessary)
criteria of
p = hp1, . . . , pm, p|P | n+1, . . . , p|P |i and
q = hq1, . . . , q|Q|i, where {q`} = Q1:`|b and {p`} = P 1:`|b for 1 ` m, and p|P | l+1 2 P˜1:l|c for 1 l n. We can see that p1 = q1 = b and p|P | = q|Q| = c. Moreover,
pm = qm = q|Q| (|Q| m) = p|P | (|Q| m) by the definition of LLRSP. If |Q| < |P |, then m 6= |P | |Q| + m and mth item for P is repeated at |P | (|Q| m)th, which violates the BBS. Otherwise, it is not the case, since |P | = |Q| implies p = q and, hence, P = Q by the definition of LLRSP, which contradicts the assumption that P and Q are different relational paths.
We provide proofs for two claims regarding the counterexample in Section 4.1.
Claim. P.X? 6?
S0.Z | Q.Y
AGGM .
Proof. By the definition of RVE, there are RVEs P.X ! Q.Y and Q.Y S.Z in AGGM since P = Q on6 D1 and S 2 Q on4 D2. Moreover, there is an IVE Q.Y S.Z \ S0.Z in AGGM since 1) S and S0 are intersectable, 2) there is an RVE Q.Y S.Z, and 3) hQ, D2, S, S0i is co-intersectable (see Figure 6).4 Since P.X ! Q.Y S.Z \ S0.Z and S.Z \ S0.Z 2 S0.Z, we derive P.X? 6? S0.Z | Q.Y , which implies P.X? 6? S0.Z | Q.Y AGGM conditioning on Q.Y , compared to Q.Y , does not block any possible d-connection paths between P.X to S0.Z since there are only incoming edges to Q.Y . Finally, P.X? 6? S0.Z | Q.Y holds.
AGGM . Furthermore,
AGGM Claim. There is no
Proof. Suppose that there exist such a skeleton b 2 (B) satisfying (P.X|b? 6? and base S0.Z|b | Q.Y |b)GGM .
4Note that the original definition of AGGM does not check co-intersectability and Q.Y S.Z \ S0.Z is granted. Every terminal set for P , Q, and S0 given the base must not be empty because of the definition of d-separation and the fact that attribute classes X and Z are connected only through Y (i.e., Y is a collider). Since every cardinality is one, terminal sets must be singletons. Let {ix} = P.X|b, {iy} = Q.Y |b, and {iz} = S0.Y |b. Furthermore, since ix and iz must be d-connected given iy, GGM must have two edges ix ! iy iz, which requires ix 2 D1|iy and iz 2D2|iy . However, due to BBS and cardinality constraints (i.e., one), there exists only one possible structure (see Figure 7) where ix and iz are the cause of iy while satisfying all previously mentioned conditions except {iz} = S0.Y |b. In other words, the constraint {iz} = S0.Y |b violates with the set of the rest of conditions. Hence, there exists no such skeleton and base.
This research was supported in part by the Edward Frymoyer Endowed Professorship held by Vasant Honavar and in part by the Center for Big Data Analytics and Discovery Informatics which is co-sponsored by the Institute for Cyberscience, the Huck Institutes of the Life Sciences, and the Social Science Research Institute at the Pennsylvania State University.