Direct Estimation of Differences in Causal Graphs
We consider the problem of estimating the differences between two causal directed acyclic graph (DAG) models with a shared topological order given i.i.d. samples from each model. This is of interest for example in genomics, where changes in the structure or edge weights of the underlying causal graphs reflect alterations in the gene regulatory networks. We here provide the first provably consistent method for directly estimating the differences in a pair of causal DAGs without separately learning two possibly large and dense DAG models and computing their difference. Our two-step algorithm first uses invariance tests between regression coefficients of the two data sets to estimate the skeleton of the difference graph and then orients some of the edges using invariance tests between regression residual variances. We demonstrate the properties of our method through a simulation study and apply it to the analysis of gene expression data from ovarian cancer and during T-cell activation.
The goal of this paper is to construct a DAG that represents the differences between two different but related causal DAG models (representing different causal relations in different contexts) from i.i.d. data. The difference graph has an edge from A to B when the coefficient for the edge is different in the two causal DAGs (including the possibility that the coefficient is zero in one of the DAGs.) This problem has been considered for undirected graphs, but not for directed graphs. For the purpose of planning experiments, directed graphs are essential however. The proposed algorithm (Difference Causal Inference or DCI) can be useful in biological problems where in different contexts some edges might have been removed or had their coefficients changed.   DCI first constructs the adjacencies in the difference DAG by searching for regression coefficients that are invariant across the different contexts, and then identifies the direction of (some) of the edges by searching for regression coefficients that are invariant across the contexts. The obvious alternative to the proposed algorithm is to use standard algorithms such as PC or GES to construct both DAGs from the two different data sets, and then take their difference. However, this naive algorithm only finds edges that occur in only one DAG, rather than edges that appear in both DAGs but differ in their linear coefficients. In addition, because the difference DAG is often much sparser than the two original DAGs in different contexts, there are a number of statistical advantages to estimating the difference directly, as opposed to calculating the difference from estimates of the two original DAGs. (There has been similar work on inferring parts of two DAGs that are invariant across contexts, but it is not possible to infer the difference DAG from these invariants unless the two original DAGs are known.)   One limitation of the algorithm proposed in the paper is that it makes a large number of strong assumptions: 1. Linearity 2. Gaussianity (which can be weakened at the expense of computational complexity). 3. The two causal DAGs have a common super-DAG (i.e. there are no edge reversals). 4. No latent confounders (which can be weakened to no changes in the latent confounder connections). 5. All differences in linear coefficients between the two DAGs entail differences in a certain set of regression coefficients. 6. All differences in noise terms between the two DAGs entail differences in a certain set of conditional variances.  The last two assumptions are similar in spirit to the commonly made faithfulness assumption, in that they assume that certain polynomials are not equal to zero unless they are identically zero for all parameter values. However, they neither entail faithfulness nor are entailed by faithfulness.  In terms of comparing the naive algorithms versus DCI, the paper makes a solid case that where their set of assumptions is applicable, DCI widely outperforms the naive algorithms. However, the paper should mention that these there are conditions under which the naive algorithms based on PC and GES algorithms can be applied where DCI cannot. For example, both of PC and GES can be applied to much larger numbers of variables than DCI can, and PC can be applied to a much wider class of distributions, while modifications of PC drop the assumption of no latent variables.   The paper argues that assumptions 5 and 6 are generally weaker than the faithfulness assumption because the surfaces in the parameter space where the assumptions are violated are fewer in number for assumptions 5 and 6 than for the Faithfulness Assumption. However, the surfaces violating assumptions 5 and 6 are not a subset of the surfaces where faithfulness is violated. Both assumptions 5 and 6 on the one hand and faithfulness on the other hand have surfaces where they are violated of Lebesgue measure 0. If (as is more statistically relevant) one considers the volume of space close to a surface where the assumptions are violated, that depends on the shape of the surface as well as the number of surfaces. So while it seems like a reasonable conjecture that assumptions 5 and 6 are weaker than the faithfulness assumption, it seems like just a conjecture at this point.   The paper notes that the standard version of the DCI algorithm does not have a complete set of orientation rules, since it does not orient edges to prevent cycles to reduce the computational complexity of the algorithm. The article states this is "computationally intractable in the presence of long paths." However, it is not clear why adding this rule would be a computational bottleneck for the algorithm or why the length of paths matter. It would seem that this would only require calculating the transitive closure of the directed part of the graph, which should be no worse than n^3, and could certainly be performed for hundreds of variables, which is in the range that the article applies the algorithm to.   DCI was tested on both simulated and real data. The simulations used both 10 node DAGs and 100 node DAGs. In both cases, DCI significantly outperformed the naive algorithms. My only criticism of these tests is that they made all of the strong assumptions presupposed by DCI. This is quite commonly done, but given that DCI is applied to data where many of these assumptions are certainly false, it would be instructive to see how much violations of these assumptions affect the results, and the comparison with other algorithms. DCI was also applied to several real data sets, including one where there were two groups of ovarian cancer patients with different survival rates, and on where there were activated naive T cells. In each case the results were compared to an algorithm that computed a difference graph for undirected graphs. (It is not clear why the results were not also compared to the naive algorithms based on GES or PC). In each case they found nodes of importance (e.g. hub nodes) that were found to play an important role in the external literature. It is not clear from the exposition whether they found any part of the output surprising or likely to be wrong, or how systematically the output was compared to what was already in the literature.   Overall, the article was written quite clearly. The general approach of DCI is similar to other algorithms which construct graphs representing edges that are invariant across different contexts (rather than different across different contexts) and also uses algorithms for constructing difference graphs for undirected edges. However, the particular application is both novel and significant, and both simulation tests and applications to real data show promise.