Maximal Ancestral Graphs (MAGs) are probabilistic graphical models that can model the distribution and causal properties of a set of variables in the presence of latent confounders. They are closed under marginalization. Invariant pairwise features of a class of Markov equivalent MAGs can be learnt from observational data sets using the FCI algorithm and its variations (such as conservative FCI and order independent FCI). We investigate the consistency of causal features (causal ancestry relations) obtained by FCI in different marginals of a single data set. In principle, the causal relationships identified by FCI on a data set D measuring a set of variables V should not conflict the output of FCI on marginal data sets including only subsets of V. In practice, however, FCI is prone to error propagation, and running FCI in different marginals results in inconsistent causal predictions. We introduce the term of marginal causal consistency to denote the consistency of causal relationships when learning marginal distributions, and investigate the marginal causal consistency of different FCI variations.Results indicate that marginal causal consistency varies for different algorithms, and is also sensitive to network density and marginal size.
Maximal Ancestral Graphs (MAGs) [
Since MAGs are closed under marginalization, FCI can be
also used in any subset V n L of V to obtain the
corresponding marginal PAG. Naturally, the causal features of
marginal PAGs should not contradict those of the PAG on
the full set of variables: a disagreement between a PAG and
a marginal PAG can only be a result of the sensitivity of
FCI to statistical errors. We use the term marginal causal
consistency to describe the degree of agreement of causal
relationships among a PAG and its marginals. To the best
of our knowledge, this type of consistency of
constraintbased causal discovery has not been examined before. We
examine the outputs of FCI [
In a simulated setting, we found that the algorithms’ consistency is sensitive to network density and number of variables that are marginalized out. To examine whether the consistency of causal relationships correlates with the correctness of the induced causal features, we ranked them according to their frequency of appearance in randomly selected marginals, and compared the resulting AUCs with bootstrapping. While marginal consistency measures the sensitivity of an algorithm to a specific choice of measured variables, bootstrapping measures the sensitivity of an algorithm to the specific sample. Results show that marginal consistency can help identify accurate causal features. However, bootstrapping outperforms marginal-based ranking in all cases.
The rest of this paper is structured as follows: Section 2 introduces basic MAG notions and notation. Section 3 defines marginal causal consistency in FCI outputs, presents a sound and complete method for identifying all pairwise causal ancestry relationships in a PAG, and compares internal consistency of outputs of different FCI variations. Section 4.1 describes work related to obtaining confidence estimates for causal ancestry relations. Section 4 describes an algorithm for ranking causal relationships for a given data set, and compares the AUC of the proposed approach to confidence estimates obtained with bootstrapping. Conclusions and future directions are discussed in Section 5. 2
We use V to denote random variables, and V to denote a set of variables. A graph G, denoted as G = (V; E) is defined over a set of variables V with edges E. A path p is a sequence of adjacent edges, without repetition. A directed path is a path where all edges are directed and have the same direction. We use X 99K Y to denote that there exists a directed path from X to Y (X is an ancestor of Y in G). We use X ??Y jZ to denote variables X and Y to be independent given a set Z. In a graph G a vertex V is a collider on a path u if and only if there are two distinct edges on u containing V as an endpoint and both are into V. Otherwise, V is a non-collider on U. In a graph G, a triplet X V Y is unshielded if X and Y are not adjacent in G.
A Bayesian network is represented by a Directed Acyclic Graph (DAG) G over a set of variables V and a joint probability distribution P. A directed edge denotes a direct causal relationship. We assume that the following two conditions hold: the Causal Markov Condition (CMC), which states that every variable is independent of its non-descendants given it’s parents, and the Faithfulness Condition (FC), which states that all the conditional independencies that hold in P stem from G and the CMC.
MAGs are mixed graphs, i.e. they can have both directed and bi-directed edges. A directed edge X ! Y indicates that X causes Y , while a bi-directed edge X $ Y indicates that X and Y are confounded. Two nodes can be connected with only one type of edge, and ancestry has precedence over confounding: if X causes Y and the two are also confounded, only the directed edge X ! Y is present in the MAG. MAGs can also be used to represent selection bias via undirected edges. For this paper, we assume no selection bias and only consider MAGs with directed and bi-directed edges.
A path is called uncovered if every consecutive triple on the
path is unshielded [
FCI is a sound and complete algorithm for discovering
PAGs from observational data, but it is prone to
statistical errors. Several extensions have been proposed that aim
to tackle the sensitivity of FCI to error propagation:
order independent FCI, conservative FCI and majority rule
FCI among others. Order independent FCI (denoted iFCI
in the rest of this paper), proposed by [
MARGINAL CAUSAL CONSISTENCY IN PAGS We now define the problem of marginal causal consistency of a constraint-based algorithm. Intuitively, we are interested in how much marginalizing out variables and rerunning FCI (or a variation) preserves causal relationships. To help define the problem, we use AnP to be the set of all ancestral relationships that hold in the Markov equivalence class [P] entailed by P. Notice that this set may be different than the set of ancestral relationships T RP that can be identified directly from P by taking the transitive closure of the directed edges: It may include additional pairs that are connected by a different causal path in every member of [P], so that there is no fully oriented path in P. Figure 1 shows an example where an invariant causal relationship does not correspond to a single directed path in the PAG: while T RP for the PAG of Figure 1a is the empty set, AnP = f(X; Y )g.
Identifying AnP is not trivial. [
However, in this work we show that all causal relationships
that are invariant in P but are not in T RP correspond to
a specific pattern, illustrated in Figure 1. The pattern can
be easily found in P to identify all additional relationships
that are causal in P but not present in T RP . Theorem 3.1
proves soundness and completeness of this rule.
Theorem 3.1 Let P be the PAG over a set of variables V
representing the Markov equivalence class of MAGs [P].
Then, if (X; Y ) 62 T RP , X 99K Y 2 AnP if and only if
9U; V; U 6= V such that
1. hX; U; : : : Y i and hX; V; : : : Y i form uncovered
potentially directed paths and
2. hU; X; V i is an unshielded definite non collider in P.
Proof (() Let U; V be distinct variables such that
hX; U; : : : Y i and hX; V; : : : Y i are uncovered p.d paths,
with hU; X; V i an unshielded definite non-collider in P.
Let U X in some MAG in [P], where ? is used as
a meta-symbol denoting any plausible orientation. Then
X ! V (since U, X, V form a definite non collider) and
V 99K Y (since every triple on the path is a definite non
collider). Else if U X, then U 99K Y (since every
triple on the path is a definite non collider). Thus, (X; Y )
in AnP .
()) We will first prove that if there is a directed path from
X to Y in all MAGs in [P], and there is no such directed
path in P then there exist at least two potentially directed
paths (and thus, two uncovered potentially directed paths)
in P:
If there is a directed path from X to Y in every MAG in
[P], then there is a p.d. path from X to Y in P. By Lemma
B.1 in [
1Although theoretically possible, the algorithm assumes that the input PAG and separating sets are correct, that is, that the dependencies and independencies encoded in the PAG are the ones implied by the separating sets. In practice however, as suggested by anecdotal experiments, FCI and its variants rarely produce such output. path p2 = hX; V; V2; : : : Vm, Y i of length m with U 6= V must also exist. Assume there is no such path. If for every MAG in [P], X ! U , then p1 is a directed path in P (since every triple on the path is a definite non collider), and X 2 AnP (Y ), which is a contradiction. Thus, X U in P, and there exists a MAG in [P] where X U and p1 is not a directed path. If p1, is the only p.d. path from X to Y in P, then X 99K Y 62 [P], which is a contradiction. Thus, 9p2 = hX; V; V2; : : : Vm; Y i with U 6= V .
Next we show that hV; X; U i form an unshielded definite non-collider in P: hV; X; U i is not a collider in P (trivially since p1 and p2 are potentially directed paths). We must also show that U; V are not adjacent. If U V in ; then there exists a MAG in [P] such that U ! X in P, which is inconsistent since p1 is a p.d. path.
Apart from (positive) causal relations, a PAG can also have negative and ambiguous causal relations. X and Y share a negative causal relationship in P if X cannot be a cause of Y in P. This happens if (X; Y ) 62 AnP , and there can be no directed path from X to Y in P (i.e. X Y in P, or there is no potentially directed path from X to Y in P). Naturally, this does not mean that Y causes X. An ambiguous causal relationship occurs when a relationship is neither positive nor negative.
We use the notation N AnP to denote the set of negative
causal relationships in a PAG P. The conditions mentioned
above for membership in N AnP can easily be tested in P:
To rule out the existence of a possible directed path, only
uncovered possibly directed paths need to be checked [
We are interested in constraint-based algorithms’ consistency to marginal ancestral sets: Let D be a data set over a set of possibly confounded variables V, and let G be the PAG output of a sound and complete constraint-based algorithm. P defines an ancestral set AnP and a non-ancestral set N AnP . Also, let P[L, L V, be the marginal PAG obtained using the same algorithm (with the same hyperparameters) on the restriction of data set D on variables in L. Each marginal PAG P[L defines a marginal ancestral set AnP[L and a marginal negative ancestral set N AnP[L . Assuming no statistical errors, any marginal ancestral set is a subset of the ancestral set. Thus, there is no pair (X; Y ) present in any AnP [L that is not present in AnP . On the contrary, some ancestral relationships that can be identified in the full data set may not be identifiable in a marginal, due to (a) the fact that some variables are not included in the marginal and (b) the loss of information from excluding variables. Therefore, members of AnP are possibly not present in some AnP[L . Similarly, any marginal nonancestral set is a subset of the non-ancestral set, while some E
F
(a) A
B
C
D
A
B
C
D members of N AnP may not be present in some N AnP[L . In addition, the PAGs should not encode any conflicting causal information: Members of AnP cannot also be members of N AnP[L , and members of N AnP cannot also be members of AnP[L .
For finite samples, however, statistical errors propagate in both the skeleton identification and the orientation steps of constraint-based algorithms, and can result in conflicting orientations. Since the algorithms are run on marginal versions of the same data set, conflicts in the marginal ancestral sets can be viewed as a measure of robustness of the algorithm to statistical errors. We are therefore interested in comparing the marginal causal consistency of different FCI variations. Marginal consistency can also been as a measure of the sensitivity of an algorithm to the specific choice of observed variables.
For a given algorithm, we are interested in how often positive and negative ancestral relationships entailed by the marginal outputs P[L agree or disagree with the output P over the full set of variables. This information is entailed in the confusion matrix described in Table 1.
Some remarks: F (b) c n f 0 11 0 11
p d e 2 0 0 2 For perfect statistical knowledge, c = d = e = f = 0, p = jAnP[L j, n = jN AnP[L j. Notice that ancestral and non-ancestral relationships identified in a marginal PAG are not expected to be ambiguous in the PAG over the complete set of variables V.
The sum p + d + c + n + e + f is different (smaller) than the number of possible causal relationships in the marginal data set, since P [L also has ambiguous edges. We do not take these edges into account here, because they are not an indication of consistency or inconsistency of the marginal. Edges that are (non) ancestral in P can often be ambiguous in P [L, even if the endpoints are present in the marginal.
An example of (non) ancestral relations in a PAG and a corresponding marginal PAG is shown in Figure 2. The corresponding confusion matrix is shown in Table 2 (assuming perfect statistical knowledge).
Notice however, that the confusion matrix in Table 1 only measures the robustness of an algorithm in terms of causal predictions. Other characteristics and uncertainties of FCI outputs are not taken into account. 3.1
We used simulated data to examine the internal consistency
of the FCI algorithm. We used the pcalg package [
We used different variations of the FCI algorithm to retrieve a causal network with significance threshold = 0:05 and unconstrained maximum conditioning set. We also created 100 randomly selected marginal data sets of size 18 and 15 for each DAG, and ran all FCI variations with the same parameters.
The variations of the FCI algorithm we used are the following: order independent FCI (iFCI), FC, FCI with majority rule (mFCI). We did not include the conservative FCI, as the existence of ambiguous triples results in outputs that are not complete PAGs. Hence, Theorem 3.1 can not be applied. Instead, we included the majority rule FCI, which is inspired by conservative FCI, but in which the triplet’s orientation is dictated by a majority vote on the corresponding conditional independence tests. To guarantee that the output is a valid PAG, ambiguous triplets (occurring in a tie vote) are marked as definite non-colliders.
Due to statistical errors, the output of the FCI algorithm
is also not necessarily a valid PAG. A very common
problem is the creation of cycles or almost cycles. To tackle
this problem, we added the option to aggressively prevent
cycles, as implemented in TETRAD [
The results of the experiments are shown in Figures 3 and 4. The ratios were computed by summing over all numerators and dividing by the sum of all denominators (for example, for jAnpP[L j we summed over all correctly identified ancestral relations p and divided by the total number of predicted ancestral relations jAnP[L j over all marginals and datasets). This guarantees that each bar sums to one and avoids divisions by zero, in case no relation is predicted. For all algorithms, the consistency drops for both denser networks and smaller marginals. For networks with density 0.1 all algorithms have more than 50% consistent predictions for both 18 and 15-variable marginals. For denser networks however, the performance of iFCI and FCI drops below 0.2. mFCI has the largest ratio of consistent relationships, and retains a consistency ratio of 0.60 for 18variable marginals. However, its performance drops to 0.38 for 15-variable marginals. For all algorithms, the majority of causal relationships are found non-ancestral in P , and a small ratio is found ambiguous. It is worth noting, however, that the algorithms typically output very few positive causal relationships.
Non-ancestral causal relationships on the other hand are much more consistent, as shown in Figures 5 and 6. The majority of non-ancestral relationships are consistent (blue bars, jAnnP[L j ). Overall, mFCI has the highest ratio of consistent negative relationships.
Overall, results show that (a) the performance of constraintbased algorithms heavily depends on the graph density, particularly for algorithms that are less conservative, and thus more sensitive to error propagation and (b) The causal predictions of the algorithms are sensitive to marginalization. Even for mFCI, removing two out of 20 variables results in 30-40% relations that are not validated in the marginal data set.
RANKING CAUSAL RELATIONSHIPS BASED ON MARGINAL CAUSAL
CONSISTENCY Calculating the marginal ancestral sets indicates a way of ranking pairwise causal relationships according to their frequency of appearance in AnP[L for different marginals. The idea is that causal relationships that frequently appear in marginal PAGs will tend to be true more often, even if they are not consistent with the output of the algorithm on the whole data set. 4.1
Alternative approaches for ranking causal ancestry relations can be categorized into (a) Bayesian model averaging methods and (b) resampling-based methods.
Bayesian model averaging methods compute the posterior
(a)
(a)
(b)
(b)
(c)
(c)
probability of network features by averaging over network
structures. This can be either approximated using MCMC
[
Resampling-based methods repeatedly apply a learning
method on resampled datasets and estimate the confidence
of network features as the proportion of induced networks
in which they appeared. Such methods include parametric
and non-parametric bootstraps [
In this section we compare our approach with the
nonparametric bootstrap by [
Based on these ranking and the status of the relationship in the ground truth network (used to simulate the data), we calculated ROC curves and the corresponding AUCs. Figures 7(a,b) and 8(a,b) show the performance of the algorithms using marginals of 15 and 18 variables for densities 0.1 and 0.2 respectively. For all settings, ROC curves are significantly better than random guessing. Again, the results are better for sparser networks, where AUC ranges from 82.25-91.84%. The AUCs drop for denser networks, ranging from 60.78-83.57%. mFCI has the highest AUCs for all settings.
We compared our method against bootstrapping. For each DAG, 100 data sets with 1000 samples were resampled with replacement from the original data set. FCI was ran on the new data sets, each time calculating the ancestral set AnP on the output PAG. Each order pair of variables was then ranked according to the frequency of appearance in the ancestral sets. The results are shown in figures 7(c) and 8(c), where we can see that bootstrapping outperforms the marginal-based ranking in all cases. Again, the majority rule FCI outperforms the rest of the algorithms. 5
We defined and examined the problem of marginal causal consistency in constraint-based causal discovery. We presented a way to identify all invariant causal relationships entailed in a complete PAG.
We examined how well causal and non-causal relationships predicted by three different variations of FCI are preserved when you marginalize out variables. Results indicate that constraint-based learning methods for causal networks are sensitive to the selected marginal, particularly for dense networks.
The results are important because in most real-life applications researchers may have limited knowledge on the possible unmeasured variables. It is also possible that confidence metrics computed based on marginals could be more helpful in situations where you have ”outlier” variables that do not satisfy the algorithm’s assumptions (e.g. they create cycles, do not satisfy the distributional assumptions of conditional independence tests etc). In such cases, it is possible that taking random marginals could improve the algorithms’ performance (similar to the way bootstrapping is beneficial when you have outlier samples).
We must also point out that PAGs encode much richer information than the causal ancestry relations examined here. Exploring different types of marginal consistency is also an area of interest.
We would like to thank the anonymous reviewers for their comments, particularly reviewer 2 who helped us identify a problem in the simulations in the submitted version of this paper. This work was funded by European Research Council (ERC) and is part of the CAUSALPATH - Next Generation Causal Analysis project, No 617393.