Not All Causal Inference is the Same
Authors: Matej Zečević
Devendra Singh Dhami
Kristian Kersting
Venue: Accepted by TMLR ()

Abstract: Neurally-parameterized Structural Causal Models in the Pearlian notion to causality, referred to as NCM, were recently introduced as a step towards next-generation learning systems. However, said NCM are only concerned with the learning aspect of causal inference
and totally miss out on the architecture aspect. That is, actual causal inference within NCM is intractable in that the NCM won’t return an answer to a query in polynomial time. This insight follows as corollary to the more general statement on the intractability of arbitrary structural causal model (SCM) parameterizations, which we prove in this work through classical 3-SAT reduction. Since future learning algorithms will be required to deal with both high dimensional data and highly complex mechanisms governing the data, we ultimately believe work on tractable inference for causality to be decisive. We also show that not all “causal” models are created equal. More specifically, there are models capable of answering causal queries that are not SCM, which we refer to as partially causal models
(PCM). We provide a tabular taxonomy in terms of tractability properties for all of the different model families, namely correlation-based, PCM and SCM. To conclude our work, we also provide some initial ideas on how to overcome parts of the intractability of causal inference
with SCM by showing an example of how parameterizing an SCM with SPN modules can at least allow for tractable mechanisms. With this work we hope that our insights can raise awareness for this novel research direction since achieving success with causality in real world downstream tasks will not only depend on learning correct models but also require having the practical ability to gain access to
model inferences.

Published in Transactions on Machine Learning Research (09/2023)
Not All Causal Inference is the Same
Matej Zečevié
Computer Science Deportment, TU Dormstadt, Germany
Devendra Singh Dhami
Computer Science Department, TU Dormstadt, Germany Hessian Center for AI (hessian.AT), Germany
Kristian Kersting
kersting@cs. www.aesstttdddddddt......m
Computer Science Deportment, TU Dormstadt, Germany
Centre for Cognétive Science, TU Dormstadt, Germony Hessian Center for Al (hessian.Al), Germany German Research Center for Artificial Intellgence (DFKI), Germany
Reviewed on OpenReview: https: // openreview. net/ forun? id= ySW
Abstract
Neurally-parramotoriiee Structural Causal Models in the Pearlian notion to causality, re- lerred to as NCM, were recently introduced as slep lowards next-generation learning systems. However, said NCM are only concerned with the learning aspect of causal infer- ence and totally miss out on the architecture aspect. That is, actual causal inference within NCM is intractable in that the NCM won't return answer to query in polynomial time. This insight follows corollary to the more general statement on the intractability of arbitrary structural causal model (SCM) parameterizations, which we prove in this work through classical 3-SAT reduction. Since future learning algorithms will be required to deal with both high dimensional data and highly complex mechanisms governing the data, we ultimately believe work on tractable inference for causality to be decisive. We also show that not all "causal" models are created equal. More specifically, there are models capable of answering causal queries that are not SCM, which we refer to as partially causal models (PCM). We provide tabular taxonomy in terms of tractability properties for all of the dif- ferent model families, namely correlation-bast basod, PCM and SCM. To conclude our work, we also provide some initial ideas on how lo overcome parts of the intractability of causal infer- ence with SCM by showing an example of how parameterizing an SCM with SPN modules can at least allow for tractable mechanisms.
With this work we hope that our insights can raise awareness for this novel research direction since achieving success with causality real world downstream tasks will not only depend on learning correct models but also require having the practical ability to gain access to model inferences.
1 Introduction
Causal interactions stand at the center of human cognition thus being of high value to science, engineering, business, and law (Penn & Povinelli 2007). Questions like "What if?" and "Why?" were discovered to be central to how children perform exploration,
recent strides in developmental psychology suggest Gooniik 2012 Buchsbaum et al. 2012 Pearl & Mackenzie, 2018), and similar to the scientific method.
Whereas artificial intelligence research dreams of an automatation to the scientist's manner (McCarthy 1998 McCarthy & Hayes 1981; Steinruecken et al. (019).. Deep learning's advance brought universality approximation i.c., for any function there will exist neural network that is close in approximation arbitrary precision (Cybenko) 1989 Hornik 1991). The field has tremendous progress ever since, see

---

Published in Transactions on Machine Learning Research (09/2023)
for instance (Krizhevsky et al. 2012 Mnih et al. 2013
Vaswani et al. 2017). Thereby, the integration of Preliminary attempts, for the
causality with deep learning is crucial for achieving human-level intelligence.
so-called neural-causal models (Xia et al. 2021
Pawlowski et al. 2020 Zečević et al. 2021a) suggest to be
a promising step in this direction.
While causality has been thoroughly formalized within the last decade (Pearl 2009 Peters et al. 2017 , and
deep learning has advanced at a breakneck speed, the issue of tractability of inference (Cooper) 1990 Roth
1996 Choi et al., 2020) has been left relatively unscathed. It is generally known that semantic graphs like Bayesian Networks (BNs, Pearl 1995 scale exponentially for marginal inference, while computation graphs (or probabilistic circuits) like sum-product networks (SPNs. Poon & Domingos (2011)) scale in polynomial (if not linear) time. A conversion method developed by Zhhoo et al. (2015) showed how to compile back and forth between SPNs and BNs. Yet, diverging views on tractable causal inference were reported, as discussed in Papantonis Belle (020) and Zečović al. (2021a). The former argues using the aforementioned conversion scheme, which leads to a degenerate BN with no causal semantics, while the latter proposes a partial neural- causal model that leverages existing interventional data to perform tractable causal inferences. Motivated by these discrepancies and the resulting lack of clarity, this work focuses investigating systematically if, when, how and also under what cost the different types of causal inference occur in tractable manner. Our investigation of causal models reveals a tabular taxonomy to summarize recent research efforts and clarifies what should be subject of further research. Going a step further we also reveal a newly proposed model, Linear Time Neural Causal Model (LTNCM) as an initial step towards the said goal.
We make the following contributions: (1) We prove the general impossibility result of tractable inference within parameterized SCM, (2) we identify the differences in existing causal models out of which we arrive at and define the new class of partially cousal models, (3) we provide comprehensive view onto the different trade-offs between model expressivity and inference tractability, classifying our models along with their properties within tabular taxonomy, and finally (4) based on our taxonomy we propose a new model called LTNCM that can perform linear time mechanism inference opposed to polynomiality of a standard NCM.
We make our code repository for reproducing the empirical part with the LTNCM and visualizations publicly available at: http:://ggttbb.co////eevcc/c////
Incu-IInfreee Inffraaaeeaaeeeeeee-eeeeeeeeeeee the Same
2 Brief Overview on Background and Related Work
Let us briefly review the background on both key concepts from causality and the main tractable model class of concern, sum-product networks (SPNs). Because SPNs will play a central rolc in the discussion of this paper, since they take a singular role in model families that are truly tractable, we refer readers unfamiliar with the model family to the overview provided by París et al. (2020).
Causal Inference. Following the Pearlian notion of Causality (Pearl 2009 , an SCM is defined as 4-tuple M: :
where the so-called structural equations
U/- < fe u:) E F
(1)
assign values (denoted by lowercase letters) to the respective endogenous/systen variables V; E V based on the values of their parents Pa; S VV,, and the values of their respective exogenous/noie hwte//noiiinnnnnreeeeeee /nature variables U, S U, and P(U) denotes the probability function defined over U. An intervention do( (), WcV on an SCM M occurs when (multiple) structural equations are being replaced through new non-parametric functions thus elfectively creating an alternate SCM. Interventions are referred to as imperfecl if the parental relation is kept intact, as perfect if not, and even atomic when additionally the intervened values are being kept constant. It is important to realize that interventions are of fundamentally local nature, and the structural equations (variables and their causes) dictate this locality. This further suggests that mechanisms remain invariant. to changes in other mechanisms. An important consequence of said autonomic principles is the truncated factorization
1 MM = 1l p(v; pa.)
(2)
derived by Pearl (2009), which suggests that an intervention do (W) introduces an independence of set of in- tervened nodes W to its causal parents. For completion we mention more interesting properties of any SCM,
2

---

Published in Transactions on Machine Learning Research (09/2023)
they induce causal graph G as directed acyclic graph (DAG), they induce an obsevattioal//asooattionn distribution denoted yMM and they can generate infinitely many interventional and counterfactual distribu- tions using the do-operator which "overwrites" " structural equations. NNte that, opposed to the Markovian SCM discussed in for instance (Peters et al. 2017), the definition of M is semi-Markovian thus allowing for shared U wetn the different V₁2 Such a is also called hidden confounder since it is a common cause of at least. two Vi, V + j). Opposite to that, a " "common" confounder would be a common cause from within V. The SCM's applicability to machine learning has been shown in marketing (Hair Jr & Sarstedt 2021) healthcare [Bica et a 2020) and education (Hoiles & Schaar 2016). As suggested by the Causal Hierarchy Theorem (CHT) (Bareinboim et al. 2020), the properties of an SCM form the Pearl Causal Hierarchy (PCH) consisting of different levels of distributions being L1 associational, L2 interventional and L3 counterfactual. The PCH suggests that causal quantities (Li, i ε {2,33) are in fact richer in information than statistical quantities (C1), and the necessity of causal information (e.g. structural knowledge) for inference based on lower rungs c.g. L1 + L2. Finally, to query for samples of a given SCM, the structural equations are be- ing simulated sequentially following the underlying causal structure starting from independent, exogenous variables Uj and then moving along the causal hierarchy of endogenous variables V.
Sum- Cum-Product Networks. To readers unfamiliar with SPN literature, the present paragraph should serve as general, high-level introduction to the topic. Note however that this paragraph should not be considered as an in-depth dive/tutorial tutorial into the topic, for further consideration please do consider the provided survey and original references. We cover the basics only up to the point that they are relevant for this present manuscript. Wile some other details like the definition of a 'scope' or 'indicator variables' are integral for actually implementing SPNs and SPN-based causal models, the reader is safe to ignore those since they won't be relevant for the (tochnical) arguments given in this paper. We follow suit with existing literature and the recent strides on tractable causal inference mainly revolving around sum-product networks (SPN) as introduced by Poon & Domingos (2011). SPNs generalized the notion of network polynomials based on indicator variables xx==(x) E {0. 1J for (finite-state) RVs X from (Darwiche) 2003)_ The indicator variable (IV) À simply denotes whether a certain state x is present for a random variable (RV) X that is part of a collection of RVs denoted X and if so, then xx==(x) = 1. Sun-product networks (SPN) represent a special type of probabilistic model that allows for a variety of exact and efficient inference routines. SPNs are considered as DAG consisting of product, sum and leaf (or distribution) nodes whose structure and parameterization can be elficiently learned from data to allow for efficient modelling of joint probability distributions p(X). Formally a SPN S = (G, w) consists of non-negative parameters w and a DAG G = (V, E) with a multivariate indicator variable X leaf nodes and exclusively internal sum (denoted S) and product nodes (denoted P) given by,
S(A) = Σ C(ACC(A) P(A) = II C(A), CEch(S)
(3)
CEch(S)
where S(A) and P(A) denote the evaluation of sum and product nodes using the leaf node (A) propagation respectively, and each of these nodes is being computed recursively based on their children denoted by ch(+), and Ws.c denotes the summation weights (as convex combination, so Σw w =1 for any parent-child pair. is simply a placeholder to denote a child node and C must be either a leaf, sum or product node itself. Regarding the SPN output S, it is computed at the root node (that is, the evaluation of x is the post-propagation result at the root of the DAG and we have S(\) = S(x)) and the probability density for x is then given by p(x) = Exer S(x)' They are members of the family of probabilistic circuits (Van den Broeck et al.] 2019). A special class, to be precise, that satisfies properties known as completeness and decomposability. Let N simply denote a node in SPN S, then
Six)
[X} UUEECh(N sc(C)
if N is an indicator node else
sc(NN=
(4)
is called the scope of N and
VS S: (VC, C2 e ch(S): sc(C,) sc(C2))
(5)
yP S: (VC,, C2 E ch(S): C1 # C2
2)
(6)
3

---

Published in Transactions on Machine Learning Research (09/2023)
are the completeness (i) and docomposability (ii) properties respectively. While the two properties are crucial for what is meant. by SPN, they are not of interest for any further consideration in this work. Nonetheless, to briefly mention the intuition: (i) is a property on the sum nodes which enforces that any children pair for any given sum node needs to have the same scope and (ii) is a property on product nodes which enforces that any children pair for any given product node must have disjoint scopes (unless we consider duplicate nodes). Both conditions (i) and (ii) together make an SPN have the well-known tractability properties, for example if one were to consider marginal inference, that is, computing the integral [p(x)dx, then (i) will allow to "push down" integrals onto children (fp(x))xx E. w, S (x) for each child e), whereas (fi) will allow to decompose complicated integrals into more manageable ones p[ y)dxdy - [[p(x)xx 5 p(y)dy). Since their introduction, SPNs have been heavily studied such as by (Tapp et al.
2019) that present a way
to learn SPNs in a Bayesian realm whereas (Kalra et al. 2018) learn SPNs in an online setting. Several different types of SPNs have also been studied such as Random SPN (Peharz et al. 2020b), Credal SPNs (Levray & Belle, 2020) and Sum-Product- Networks (Sharir & Shashua 20188) to name a few. More recently, on the intersection of machine learning and causality, ZZčević et al. (2021a) proposed an extension to the conditional SPN (CSPN, Shao et al. (2019)) capable of adhering to interventional queries. Formally, an iSPN is being defined as
I ===(f()) s.t. f(Gm) and Dom(S) -M
for some SCM M, that need not be known (only its graph and arbitrary many interventional data sets), where VM are M'ss endogenous variables (all variables with 'names') and Gm is the causal graph implicd by M. Meaning that &b provides parameters to the SPN S by knowing which causal graph to consider, whereas S generates distributions for variables VM based on parameters &/ (note: we drop the notation for both f and S to reduce clutter, f == So.5: = Sp i.c., communication between the two sub models of I happens via +). In this sense, the iSPN is special case to the standard CSPN formulation proposed by (Shao et al., 2019) where the neural net parameterizer f and the generative SPN S are chosen in a particular way to correspond to some SCM M. That is, consider the general formulation of a CSPN C = =(f,) modelling a conditional distribution p | X) with foed-forward neural network f X - V and SPN S: Y [0. 1]. By realizing that an intervention do(x) comes with the mutilation of the causal graph G = (V, E)) such that new graph is G' (V, ((i,5) : (i.j) E E FAA i & Pa:], the iSPN is able to formulate an intervention for SPN natural to the occurrence of interventions in structural causal model. The neural net parameterizer (sometimes also referred to gate model) orchestrates the do-queries such that the density estimator (SPN) can easily switch between different interventional distributions. An alternate approach to causality but also through the lens of tractability was recently considered by (Darwiche] 2021).
These computational models (SPN) oppose the classical notion of semantic models (e.g. BNs, see Fig 2 they trade off interpretability with efficiency. That is, an SPN might be difficult decipher, similar to other neural methods like the multi-layer perceptron (MLP), but offer even linear time inference- while the BN (like the Pearlian SCM) directly reasons about qualitative relationships, similar to finger-pointing child, but at exponential cost.
3 Are There Even Different Types of Causal Models?
Before we can realize our discussion of the important matter around tractability of inference, we need to take a step back and look at causal model (families) themselves. That is, it is important. for us to understand that causal models themselves are not matter of choosing between black or white (metaphorically, for being causal or not) but rather live on a continuous spectrum that defines different extents to which causal model can be considered 'causal? Only if we start differentiating between these different models, it will become apparent how they naturally exhibit different inference procedures and help making the case as suggested by the title that "not all causal inference is the same."
If we consider the literature in AI/ML research before the introduction of SCMs by Pearl 2009), we typically only find tangential references to causality through concepts such as 'invariance' or 'manipulation'' Many concepts such as counterfactuals have been used in robotics and planning literature prior to Pearl without the actual naming or any direct reference to the idea of causality (even in broader sense beyond Pearl's
4

---

Published in Transactions on Machine Learning Research (09/2023)
1
61
L2
C1
C2
L1
C2
4s
La
4
L2
C2
L
C2
Associational
CBN
PCM- SEM-SCM Hybrid
PCM
SCM
Figure Classifying Causal Models based on PCH Expressivity. Legend (top left): C, denote the
PCH levels, mid-point denotes [(model) fi, whereas outer-point denotes L(model) Li. Partial Causal Models are those models that span area that is neither minimal (Associational) maximal (SCM). Note how the classical CBN falls into the category of PCM. (Best viewed in color.)
formalism). Fortunately, the AI/ML literature has been free of stigmata regarding the 'C-word', opposed the long controversies in the medical sciences and econometrics (see Hernán (2018)), lending itself a rather quick adaption. Nonetheless, most of the literature ever since the introduction of SCMs has treated the property of model being 'causal' as binary, ef. Kaddour et al. (2022) which discuss various that lie at the intersection of causality and classical ML approaches. In our first contribution with this paper we propose to think of causal models in a more diverse manner. Not just the inference processes are different (as we will see in subsequent sections), but the models themselves. Actually, the former is necessary consequence of the latter. Similar to the analysis various intricacies of the SCM family by [Bongers et al. (2021) (cf. Fig.7 giving an overview on "causal graphical models"), we make the suggestion that one can classify different types of causal models using their expressivity with respect to the PCH levels. We illustrate this classification in Fig [ by visualizing the three levels (associational, interventional and counterfactual) simplex and then drawing areas, for the different models, within these simplices to illustrate their expressivity. Since C22 L3 are uncountably infinite, the outer-point of those levels are reserved to generative models like the SCM that can generate infinitely many such distributions. The mid-point naturally illustrates that given model only partially expresses this level, thus we give the the name of partially causal models (PCM). We see that the SCM spans the maximal area (the full simplex), whereas any associational model (which includes classical models like variational autoencoder) will simply form line to Li. Thus, we propose that PCM are indeed all those models that lie in between. Interestingly, this class of models is richer than one would initially suspect, we examine this now
models
Arguably the most interesting case is the historic one i.e., the Causal Bayesian Network. The CBN was introduced before the SCM and also a 'causal' model, however, it never stood on the same rung as the SCM since it incapable of defining and therefore expressing counterfactual quantitics. This further gives justification to the synonym of SCM, namely Functional BNs since they expose the structural equations which make possible counterfactuals (and also formal notion of hidden confounders). Next, is the class of

---

Published in Transactions on Machine Learning Research (09/2023)
finite PCMs, that is, models that can provide interventional and/or counterfactual distributions but never generate infinitely many (thus finite). Recent models that fall into this class include the Causal VAF (Yang) et al. 2020) or the interventional SPN (Zečević et al. 2021a) (why we think this should be the case and how our definition captures this will be presented in the following). Finally, we recognize a third class of hybrid models (denoted "PCM-SCM Hybrid" in Fig T which generate both a finite and infinite set of distributions for the causal levels of the PCH but never for both simultancously (like SCM). For this third class, to the best of our knowledge no models have been proposed yet. Whether such models can be constructed remains to be investigated/ /proven, however, in the conceptualization presented they take clear position.
While a proper formal coverage of the idea presented in this section deserves attention in a separate line of work, we want to close off this discussion by providing a more formal, first definition of PCM based on the model classification in terms of PCH levels:
Definition 1 (Partially Causal Model). Let M be model capable of generating distributions that fall into the distinct levels of the PCH (C: for i E (1,2,3)) and let L.(M) denote said set of level i distributions. Further, let M denote the ground truth (or reference) SCM with (.(M*) like before. If the conditions (i) (M( * Ø, (ti) C2(M) x La(M) = =2(M*) x fa(M*), and (iii) at most one causal level [L,(M) = 00 are met, then M is called partially causal (w.r.t. M*)
Let us briefly consider each of the formal aspects presented in the above definition.
Mcaning of L operator: First off the Pcarlian causal hicrarchy and its Levels. As before, the operator L M. - X is a mapping from generative models (e.g. neural net, sum-product net elc. are all examples of potential choices M E M) to their generated distributions (e.g. a latent space capable of producing images of cats and dogs X' E X). Therefore, L(M) a set of distributions generated by some model M and this set is possibly infinite. Finally, the i in L, brings in the knowledge on causality by labelling all the distributions within said set according to some level on the causal hierarchy being associational (i 1), interventional (i 2) and counterfactual (i 3). To answer the question where this 'label' comes from, it is basically an implicit assumption that there exists some SCM MScM which is our underlying data generating process (therefore, we often times just omit to mention this underlying ground truth model i.e., we simply define -- (i-s(Mscci))- Since (1-3(MsCM) are well defined, we simply check whether the corresponding (.MMaare)) for some model of interest MLeamned match. Unfortunately, since MMSM is generally (or typically) unknown, there no way to check this correspondence in practice. However, with consideration of the existence of such ground truth model MscM (which is reasonable and standard practice in causality rescarch), we can state sensible definition as done above.
Meaning of bound on cardinality of (>1(-): The presented definition should capture models that lie between 'non-causal" and structural causal models which requires two conditions (a) that they can generate some causal quantities (as measured by some ground truth SCM Mscx),, therefore either Lg(Meearned) or (a(Mtoorrned) must be defined/ non-eelll/o--eppll since only interventional/ /counterfactus distributions are consid- wewenniionnl/onneeffraaeee
ered causal (this part (a) therefore corresponds to (ii) in the definition and the following part (b) then to (iii)) and (b) either one of the levels is not allowed to be infinite because we can prove by contradiction that if there was PCM that was not an SCM but has both [C2( (La(Meear)))) 00 and (MLLameed) ists some SCM M' which matches both levels, that is, L2(MMtcarned) = L2(M') and La (M(Maaarned)) = La(M)), therefore being indistinguishable from the given SCM, which is a contradiction to the premise that MLearned is not an SCM. Put differently, this proof by contradiction also gives meaning to what we mcan by 'partial' from the other end of the spectrum i.e., while (a) lower bounded our 'causalness' to be non-zero, (b) upper bounded it to not be fully causal like SCM, thus being right in-between somewhere as a partially cansal model.
00, then there ex-
While we will not make any further use of this definition subsequently, it is still worth pointing out how the PCMs in Sec all abide by the above definition. To revisit our PCM examples from carlier, both the CausalVAE and the iSPN can be considered as PCM following our definition. If we trust our definition to capture the essence of what it means to be 'partially' causal, which we made sure is the case through the thorough discussion the previous paragraphs, then satisfying the criteria in our definition both necessary and sufficient for a model to be considered a PCM. Next, we will exemplify this with the iSPN model. The iSPN, further denoted as V, is a generative model based on neural net parameterizer and generative
6

---

Published in Transactions on Machine Learning Research (09/2023)
SPN that jointly allow for modelling both observational and interventional distributions (as suggested by the i in the name of iSPN). Therefore, any iSPN V models (i()) and (2(V) with |<2()>) - N where N is the number of experimental distributions available for training, according to the regime discussed in the original paper. Since counterfactuals cannot be covered, Lx(V) is undefined. Thus V satisfies conditions (i-iii) and is considered a PCM. An analogue analysis can be performed for the CausalVAE, as it is also capable of generating interventional distributions but not counterfactual ones, therefore, it could never be an SCM since L3 distributions are a necessary condition. Hypothetically speaking, however, if the CausalVAB on the other hand were able to generate L3 distributions, then it might be considered as an SCM. This would not be the case if one allowed the same for the iSPN (i.e., to generate La distributions) since the iSPN can only produce causal distributions up to the training data available, whereas any model that can idendify causal distributions from observational data and other assumptions like the causal graph (like the CausalVAE) would automatically fall out of the PCM into the SCM class of models.
To briefly mention the following structure of the paper. In this section we answered the question whether different causal model existed in the first. place affirmatively by providing first classification in visual terms and then formal definition of PCM. In the next three sections (Secs 4 456 6 we will discuss the three key causal model families (non-causal, partially causal and structurally causal) in terms of inference. Then we summarize our insights in terms of a taxonomy in Sec and subsequently use it to propose a new model (as addenum to the main discussion) in See 7.1
4 Inference in Non-Causal (or Correlation-Basedd) Models
To expand further on the boundaries of the integration between causality and machine learning, we first perform an inspection on how causal inference can occur with correlation-based models. Fig schematizes the basie, "naïve" approach to classical causal inference that we investigale in this section. One takes the do- calculus to perform the actual "causal" inference, and then takes the available observational data and a model of choice (e.g. NN/MLP, SPN, BN) to acquire the actual estimate of the query of interest. More specifically, we will focus on SPN from the previous section, since they come with guarantees regarding probabilistic reasoning (opposed to e.g- MLPs) and guarantees regarding their inference tractability (opposed to e.g. BNs). This investigation is important since assuming the wrong causal structure or ignoring it altogether could be fatal w.r.t. any form of generalization out of data support as suggested in (Peters et al. 2017). Central to said (assumed) causality is the concept of intervention. Although being a wrong statement suggested by results on identifiability, the famous motto of Peter Holland and Don Rubin "No causation without manipulation" (Holland 1986) phrases interventions the core concept in causality. In agreement with this view that distributional changes present in the data due to experimental circumstances need be accounted for, we focus our analysis on queries Q = p(y] do(x)) with (x.y) E Val(X) x Val(Y), X,Y V respectively. Q lies on the second (interventional) level Le of the PCH (Pearl & Mackenzie, 2018 Bareinboim et al. 2020).
We first define the concept of statistical estimand (Ln) for SPN as the application of the rules of probability theory (and Bayes Theorem) to the induced joint distribution.
Definition 2. An SPN-estimand is any aggregation in terms of sums or products of conditionals, p(xly), and marginals, p(x), where p(v) E Li is the joint distribution of SPN S and X, Y c V respectively.
Before continuing with our insights on SPN-estimands, a short detour on an important assumption. In the most general case, we require a positive support assumption to ensure that an arbitrary SPN-estimand will actually be estimable from data. This is a simple consequence of computing probabilistic ratios P/Q where P. Q represent probabilities and the operation P/o generally being undefined. More formally, the assumption is given as:
Assumption 1 (Support). Let p(v) represent an SPN's modelled joint distribution. Then for any proba- bilistic quantity p(x y) (with Y possibly empty) derivable via the laws of probability and Bayes' rule from p(v) it holds that p(x yy)= > 0.
While the above assumption is arguably a standard assumption of probabilistic modelling, it is nonetheless of practical relevance since we might not always be able to ensure that it holds i.e., often times we might
7

---

Published in Transactions on Machine Learning Research (09/2023)
only be given data that covers subset and not the full set of possible instantiations of the covariates. This certainly amounts to drawback of purely "correlation-based" considerations for estimating causal quantities and will become apparent in the subsequent section. On a comparitive note, this assumption is closely aligned with the common 'positivity' assumption in causal inference. That is, in causal inference we are often times interested in the causal effect of a given treatment on some oulcome of interest (e-g. a drug on a patient's ' discase) and one critical assumption commonly employed for estimating this effect is said 'positivity' assumption where we require that all treatments of interest be observed in every patient subgroup (which is similar to Assumption D]. Returning to SPN-estimands, our first insight guarantees that can do causal inference with SPN-estimands as depicted in Fig
Proposition 1. Let Q L2 be an identifiable query (that is, Q con be purely written in Ln terms). There ewists an SPN-estimand that answers Q.
Proof. Under Assumption trivially follows from SPN being universal density approximators Poon & Domingos 2011 and Q being identifiable.
Since SPN will act as our estimation model, it turns out that any interventional query derived from a Markovian SCM can be modelled in terms of statistical terms represented by the SCM. Due to hidden confounding, this guarantee does not hold in semi-Markovian models. Prop ultimately suggests that inter- layer inference from L to L2 remains intact when choosing SPN as means of parameterization. A simple but important realization thereof is that the do-caleulus (Pearl 2009) can be used as the identification tool for SPN-based causal inference. While unsurprising from causal viewpoint, from the perspective of tractable models research the result in Prop [ provides new incentive for research on the integration of both fields. A possible explanation for this surprising observation is the skeptical view by Paapantonis & Belle (2020). They considered the usage of the SPN-BN compilation method from (Zhao et al. 2015) for causal inference within SPN that failed due the resulting BN being a bipartite graph in which the variables of interest were not connected (connectivity being crucial to non-trivial causal inference). Before investigating this issue of (in)tractability of causal inference, let's define formally what we mean by tractable inference.
Definition 3. Let R denole the variable in which the model's 's runlime scales (e-g- the number of edges in the DAG for an SPN, the number of variables in the DAG for BN). A scoling of ((poly( of polynomial time is called tractable.
Note that poly includes high-degrce polynomials (c.g. x 2,3044 and that for SPN we usually have poly := that is, linear time complexity. It is also important lo note that R is different for different models, but interestingly, the number of edges for SPNs does not "explode" exponentially so indeed, SPNs are far more efficient computation-win even in practice. To reap initial rewards, we now prove that causal inference with SPN is in fact tractable.
Corollary 1. Let Q E L2 be an identifiable query, |Q] be its number of aggregating terms in Li and R be the number of edges in the DAG of SPN S. If I R, then Q is tractable.
Proof. From (Poon & Domingos 2011) we have that S does single term, bottom-up computation linearly in R. Through Prop|] and [Q| < R it follows that O(R).
Opposed to (Causal) BN where inference is generally intractable (#P complexity), Cor [ suggests that any estimand can be computed efficiently using SPN even if the estimand identifies an interventional quantity, thereby trausferring tractability of inference also to causal inference.
5 Inference in Partially Causal Models
An important restricttin of SPN-based causal inference is that the joint distribution p(v) of SPN S optimizes all possibly derivable distributions, thereby diminishing single distribution expressivity. That is, how "easily" and how preciscly& S can in fact approximate our underlying distribution with p(v). Returning to cansal inference we observe that any causal inference will hold but actual estimation from data will suffer in quality a consequence thereof. In addition, violations of the positive support assumption might render some
8

---

Published in Transactions on Machine Learning Research (09/2023)
Example
Example Models
Query
ply)do(x))
NN
-olCallu
Estimand
,(1(,,,))p(ss
SPN
Data + Model
Estimate
2)
BN
Figure 2: "Naïve" Causal Inference Schematic. For any causal query could use the do-calculus (Pearl 2009) to identify statistical estimand (grey), for which there exists a model-based estimate (purple). Various model choices are available e.g. a NN, an SPN or BN. (Best viewed in color.)
practical inference undefined. Therefore, in the following we extend our analysis to portially causal models, models that actually extend the SPN model class with capabilities from causal inference. More specifically, consider interventional SPN (iSPN) firstly introduced by (Zečević et al. 2021a). Our first observation is that the iSPN allows for a compressed model description over the SCM, while trading in expressivity since the iSPN has no means of computing the highest level of the PCH L3 being counterfactuals. The iSPN ( 7 is more "powerful" than the SPN by construction, we state formally.
Proposition 2. Let E denote an SPN-estimand @ There erists a graph G for which the SPN-estimand of iSPN evaluated at G is E.
Proof. There exist always an SCM M with induced graph G such that the observational distribution of M and SPN-estimand E correspond accordingly. Since iSPN extend regular SPN via arbitrary causal graphs. simply select G as the graph of choice.
Prop 2 further suggests that iSPN are also joint density estimators, although being defined as special case of conditional estimators (CSPN), and that any SPN will be covered by the observational distribution (C1) of corresponding iSPN. In the following, assuming corresponding data D, P2 we prove that iSPN allow for direct causal estimation of the interventional query (C2)- This sets iSPN apart from the setting in the previous section with regular SPN that were dependent on a "causal inference engine" such as Pearl's do-calculus. To illustrate the difference between the approaches, consider the following example,
M:= (114222000.050222220000000000100
and we try inferring the query Q defined as
plul do(x)) = Σ. p(y|1, 2)p(2),
where the identification equality is given by the nackdoo-aadjustaae formula M (Pearl 2009 Peters et al. 2017p. The l.h.s. will be modelled by an iSPN, while the r.h.s. consisting of multiple terms will be modelled by the SPN and required the badjseer- formula.
An important consequence of modelling the l.h.s. is that the shortcomings of single distribution expressivity and positive support are being resolved. To claborate: the l...s. expresses a single distribution, whercas the r.h.s. expresses combination (through means of products, quotients, sums etc.) of distributions, and although they are equal in terms of the content they describe (i.e., the actual values probability) they
9

---

Published in Transactions on Machine Learning Research (09/2023)
are unequal in terms of implementation. An SPN models joint distribution and thereby any derivable "sub" -distribution,, thus in consequence, modelling single distribution like on the lh..s. is more difficult for an SPN than for e.g. an ISPN. Furthermore, since there are no ratios involved in computing the Lh.s. which could otherwise render the computation undefined, Assumption | from the previous section does not apply to partially causal models like e-g. the iSPN. What might come as a surprise is that, although we overcome previous shortcomings and dependencies, we do not loose tractability. We observe:
Proposition 3. (TCI with iSPN.) Let (Qi) L2 be a set of queries with i I N and R (as in Corl for iSPN I. Any {Qk}& with k K KEI I is tructable.
Proof- There is two cases to consider (1) any fixed Qi and (2) when we switch between different (Q:); for E N. For (1), since any iSPN reduces to SPN upon paraaeter-evallationn, we can apply Cor and thereby have that (R). For (2), we know the iSPN (Zéčević et al. 2021a uses neural net, therefore we have Oppoly(R))
Prop 3 seems to suggest that iSPN should always be the first choice they don't seem to compromise while being superior to the the non-causal models that rely causal inference engines, however, the iSPN from (Zečvić et al.) 2021a) comes with strict assumptions. Specifically, we don't assume causal inference engine but we require interventional data-whichh in a lot of practical settings is too restrictive. Also, in the case of semi-Markovian models, the iSPN falls short. Further, we observe a "switching" restriction, which the non-causal models did not have. That is, when we have to consider multiple interventional distributions the cost will scale w.r.t. to the size of the gate model (either quadratically or cubically for standard feed-forward neural networks).
6 Inference in (Parameterized) Structural Causal Models
In the previous sections we discussed non-causal and partially cansal models (based on SPN), showing that they are tractable mostly trading on cerlain aspects such as assumptions on the data and how many queries we ask for. Although they have tractable causal inference, these methods actually lack in terms of causal erpressivity. All our previous observations were restricted to queries from L2, that is, interventional distributions. Why not counterfactuals? Since these models are not Structural Causal Models. The Pearlian SCM extended historically the notion of Causal BNs (CBN) by providing both modelling capabilities for counterfactuals but also hidden confounders.
Now, in the following, we will move onto this more general class of models that is fully expressive in terms of the PCH. For this, consider a recent stride in neural-causal based methods ignited by the theoretical findings in (Xia et al., 2021), where the authors introduced a parometerized SCM. Since this term was never coined in the general sense, provide it here for convenience.
Definition 4. Let V,, P(U)) be an SCM. We call M parameterized if for any I E F we have that f(,00) where 0 are model parameters.
In the case of (Xia et al. 2021 the ʃ were chosen to be neural nets. Note that Def actually allows for different function approximators (e.g. combination of neural nets and other models), however, so far in the litcrature we usually have the model class F be only of one such model choice (c.g. F being the class of MLP, therefore, each f is simply a standard feed-forward net). It is further important to note that any parameterized SCM is fact an SCM s0, an NCM is a valid SCM, furthermore, implies the complete PCH.
Since SCMs extended CBNs, and since CBNs are not computation graphs (like an SPN is) but rather semantic graphs, we might conclude that SCMs inherit properties of the CBNs when it comes to inference. Unfortunately, it turns out, this heritage of a parameterized SCM is valid and leads to their intractability for causal (marginal) inference.
Theorem 1. Causal (marginal) inference in porameterized SCM is NP-hard.
10

---

Published in Transactions on Machine Learning Research (09/2023)
Proof. The herein presented proof can be considered a natural (maybe even simple) consequence of long standing results in computation theory by means of (Cooper) 1990). It. has been long understood that exact inference in BNs is computationally hard and since SCM historically derive from BN, the presented result might not come as a surprise. Nevertheless, we present a more concrete proof in the following and try to stress that this result is important after all since there has been arguably a disconnect between computation theory and research around causality. Put differently, the importance of SCM for causality opposed to BN is what makes the Theorem important in the view of the authors of this manuscript. As foreword to the conceptual portion of the proof and especially readers unfamiliar with computational complexity theory, Cooper made use of a proof technique referred to as reduction. That is, problem A is being reduced to problem B by showing that a solution to B will solve A. Naturally, this transfers the complexity i.., if B is a difficult problem, then successfully reducing A to B shows that A is also a difficult problem. The phrase "A is at least as hard as B" is often times used to convey said idea. More specifically for this result, we will use a 3-SAT reduction where 3-SAT is the problem of evaluating whether the Boolean expression of multiple clauses with literals (a clause, typically written in paranthesis, consists of multiple literals connected by Boolean operators,
example is shown in the following) is satisfiabile not, for example, is there a combination of Z s.t. B= ;= (I) V 22 V z3) A (I4 I5 v z6) evalutes to true (B 1)? Since it has been established by Cook [177]] that 3-SAT (satisfiability of 3-literal-clause expressions) is NP-hard, we can deduce that our problem A is also NP-hard if we can reduce it to 3-SAT s.t. solving A requires solving 3-SAT. This is being done in the following. The simple proof might only involve reasoning that SCM extend BN such that any inferred solution for any given causal query holds in a corresponding BN if and only if it holds in the SCM because then we simply apply (Cooper 1990) which showed that BN inference is NP-hard, thus also SCM inference. To write down the full argument, we apply the same technique of 3-SAT reduction. In the first step, we require mapping between clauses from 3-SAT and SCM. As a reminder, in 3-SAT we talk of literals
Qn for n E N with Qi E {0, 1} and clauses of 3 literals each CI...., Cm for m E N with C,(Qu, Q2 Qi) for j, each clause in the set of all clanses C' == {Ci)m= evaluates to 1 (read, "true"). We know since (Cook) 1971 that 3-SAT is NP-hard. So it suffices to show a reduction from 3-SAT to SCM inference i.e., that SCM inference is "at least as hard" as 3-SAT or that an oracle of the latter would subsequently solve the former. Let M- V F, P(U)) be our SCM. We do the following mapping: (1) each literal Q: will be in V and only depend on its "nature" term in U, so for each Q2 - fq. flips (2) each clause C2 will be an effect of its causes Qi, so for each C; - (C; Qj, Qi, Uc;)) such that Sc; is an indicator function of the clause. Since all clauses in C' need be satisfied, we create a reversed, binary tree denoted by A; - fA,(PA (Pa UA.) (where at the leaves we have Рaa. = |Caa Cb} for arbitrary two clauses and for internal nodes Рa = {AA-1,, C.. for some arbitrary clause C.). Finally, we have X- - -x((A-22 Ux) (note m- - 2 since we had m clauses). This completes the mapping, the second step is to show equivalence of p(X = 1) to the satisfaction of C. Our construction implies p(X- = 1) > p(X = (CC))p(C,U,,)((C where U, denotes "true" for variables in U satisfying every clause in C' and C, correspondingly, and we have p(X = 1|C,)= 1, p( p(C,)U,), P(U.) = (1)" so p(X X = =) > 0 when C is satisfiable. Tf C is not satisfiable, then there must be a term p(X = 1lCg) for some E f1...., m) such that p(X = 1|Cg) = 0. We have p(X = 1) iff. C is satisfiall.. Since 3-SAT is NP-hard, we have that marginal inference in SCMs, that is computing queries of the type p(X= = x) for any X s V, is Na-hard as well. Since a causal query involves an intervention (e.g. via Pearl's do-operator such as p(X = x do(YY- = y)) for some SCM MM) but amounts to a regular marginal query in the modified SCM Madly) where the structural equations of Y have been replaced to evaluate to y, we subsequently also have that causal marginal inference in SCMs is NP-hard. Finally, since parameterized SCMs are all instances of the general class of SCM, where the structural equations FF and the exogenous distribution P(U) are simply parameterized for sake of implementation on general purpose computers, that is F A Fg and P(U)& A (U) with 0 representing free parameters (e.g. the weights of a neural net work),),, we also have that causal marginal inference in parameterized SCMs is Na-hard which concludes our proof. ]
The goal is then to find a configuration of literals (qI...., (n) such that
U, where the U, = =B))) are random coin
From a computational perspective, the result in Thm I is a protest against the original formulation of the SCM in terms of long-term suitability for next generation learning systems. Although being an arguably simple consoquence of the BN-hcritage of the SCM, still, Thm [ strongly adviscs against any efforts of using parameterized SCM for real-world impact. Even if the parameterization comes from powerful approximators like neural nets-causal inference remains notoriously intractable. However, for both the sake of completion
11

---

Published in Transactions on Machine Learning Research (09/2023)
(a)
(b) Zečević et al., 2021
(c) ours
X < Ux)
Y (y(X,
fx(Uz)
SCM M
M
Figure 3: Tractable Causal Inference Models. (a) The unobserved SCM M implies causal graph G and generates the data to be used for estimation, (b) shows an iSPN (Zečević et al. 2021a) that uses gate model to estimate causal effects, whereas (c) is a LTNCM (Def partially tractable approximation to M. (Best viewed in color.)
and the interest of establishing the theoretical connection in the scope of this systematic investigation, we present for the first time a new parameterization of the NCM using SPN. In spite of Thm this idea is indeed sensible since any partial inference within the paramcterized SCM might still be efficient. Effectively, the SPN could thereby still offer more pragmatic alternative to e.g. a neural net since it would not necessarily compromise in terms of predictive performance (model capacity). We believe this to be true since often times the structural equations of an SCM describe reasonably simple mechanisms because of their local and thereby somehow restricted nature. Another argument to the same point would be that of causal abstraction (as discussed by for instance (Rubenstein et al. 2017)), which simply means that if our structural equation is not simple, then we can still abstract further into a more fine-grained SCM. That is, an SCM as a collective might be complex, but not its single components similar to how a neuron in mammalian cortex shows simple activity, but human cognition in total capable of highly complex decisions. Therefore, we now present the Linear Time Neural Causal Model (LTNCM) formally.
Definition 5 (LTNCM).. Let AMMU, P(U)) be parameterized SCM. If F exclusively defines SPN, then M is Linear Time (Mechanism Inference) Newral Causal Model.
An alternate definition of LTNCM invovles the "General NCM" definition given by Xia et al. (022)), by which the LTNCM is indeed an NCM but with SPN modules instead of classical feed-forward nets. While (General) NCM are still tractable terms of mechanism inference, they are polynomial because of the neural net modules and as we will see simply using SPN modules allows for linear time mechanism inference (thus the naming). We also stick the name neural over structural since SPN can (a) be viewed as special type of neural/deep model (see Vergari et al.) (2019)), and (b) the term "structural" so far seems exclusive to the general formalism of SCM and not to specific (ML) estimators.
Fig 3 provides schematic comparison of the two causal models based on SPN units i.e., the iSPN Zečević et al. 2021a) from the section on partially causal models and the LTNCM (Def Evidently, the LTNCM is concerned with a more complex model description (put simply, it requires more models), yet because of that it becomes a causal model fully expressive in terms of the PCH as it poses a subset of the of all SCMs. On a different note, in Fig 4 we show a visual schematic on the different inference processes that additionally features NCM (Xia et al.) 2021). We now state the simple consequence of defining SCM with SPN units instead of neural nets, which will further reveal one more advantage for preferring SPN over neural nets for parameterized SCM.
Corollary (NCM versus LTNCM, informal). Evaluating any structural equation for some SCM M is non-linear in NCM [Xia et al. 2021) and linear in LTNCM.
Proof. The forward pass for the neural nets (as used by the classic NCM) has polynomial runtime com- plexity and the concrete polynomial expression will depend on the concrete architecture given. We take this observation as a fact based on results also reported by (Bienstock et al.) 2018), where the authors make use of polyhedral representation to obtain new and better computational complexity results for
12

---

Published in Transactions on Machine Learning Research (09/2023)
pl D ddo
((U)
ours
Zečević et al., 2021
et al., 2021
S
f
S
S
f
ft
do
Figure 4: Schematic Overview of the Inference Processes for Selected Causal Models. From left
to right: LTNCM (Def iSPN (Zečević al. 2021a), and NCM (Xia et al. 2021 White circles denote SPN, purple quadrangles are NN. (Best viewed in color.)
training problems of well-known neural network architectures with the polyhedron being an encoding scheme for capturing the different neural network training problems that can be considered considered/parameteriza parameteerized through architecture, activation functions, loss function, and sample-size. An arguably more easily di- gestible (or casual) reference is following scientific online post by Luna Lux (https://lunalux 1o/ that describes exactly the forward pass scenario of standard MLP. For regular MLP architectures, the polynomial term is generally lower bounded by a quadratic term. For SPN, previously established, exact inference time will be linear in the size of the network. ]
Cor. 2 suggests that restricted causal inference (e.g. not general marginal inference) even with NCM is tractable but inefficient when compared to LTNCM since the former has at least quadratic runtime com- plexity opposed to linear for the latter. Said comparison behaves the same for the iSPN, since Prop suggests that (for a fixed iSPN state) any inference will also be linear. Further extending the comparison to other neural-causal models as suggested by (Zéčević et al.] (021b), namely NCM-Type and iVGAF. For the NCM-Type 2 we observe (as expected) worse, cubic runtime complexity since modelling occurs on edge- opposed to structural equation level. For the iVGAE (which partially causal model), which compa- rable the iSPN in terms of model description, the time complexity is bad as for the NCM. Therefore, iSPN (Eq 7 offer clear advantage over other neural-causal models in terms of inference efficiency since any causal query will be answered in linear time, whereas NCM-variants and CBNs have worse time complexities. However, it is important to note that NCM-variants might offer for more expressivity in terms of the PCH.
7 Summarizing the Key Differences for Causal Inferences
Conclusively, a researcher might choose one model over the other based on the specific application interest (e.g. efficacy versus expressivity). Upon investigating these various scenarios for tractable causal inference, offer a conclusive overview of our tabular taxonomy for inferences in different. model families in Tab including neural-causal inferences. Legend: OLS Ordinary Least Squares, CNN Convolutional Neu- ral Networks, GAN = Generative Adversarial Networks, FBN Functional Bayesian Network, iVGAE
interventional Variational Graph Autoencoder (Zéčević et al. 2021b), "Causal Circuits" (Darwiche) 2021
CausalGAN (Kocaoglu et al. 2017). NCM (Xia et al. 2021
Deep SCM (Pawlowski et al. 2020
7.1 'Bonus:' An Easy Solution Speeding Up Mechanism Inference in SCM
After evaluating the taxonomy from Tab. D we arrive at the realization that mechanism inference in SCM, while tractable, is still non-linear. Looking closely, we realize that this is due to the neural networks
13

---

Published in Transactions on Machine Learning Research (09/2023)
Model Family
PCH
Identification
Mechanisu Inference
Marginal Inference
OLS, CNN, GAN
C1
polynomial
SPN
C1
linear (Cor
CausalVAF.
IVGAE
4
CausaGGAN
CT 9
C2
polynomial
ISPN
C2
linear (Prop
CFQP 10
DinSCM
La
polynomial
NCM
DeepSCM
CAREFL
La
polynomial (Cor 2
intractable (Thml
LTNCM
C3
lincar (Cor
intractable (Thm
Table 1: Taxonomy of Inference in Causal Model Families. Top: the three classes perspective of non-causal, partially causal and structural causal models with known models (non-cxhaustive list). Bot- tom: Summarizing tractability properties discussed throughout the paper. PCH layer L; with i being the upper bound on causal quantitics expressible (c.g. i = 3 means any causal quantity according to Pearl can be generated). Identification suggests that cross-layer inferences can performed (e.g. no external identification engine like do-calculus is necessary). A dash (+) denotes that the structural equations of a corresponding SCM can even be defined in the given model family. Marginal inference refers whether the general computation scheme p(z) = V p(æ, v) is computable tractably. Mechanism inference refers to the tractability of the computation of any single sub-module (i.e., structural equation). The original paper references as labelled within the "Model Family" column of the table above: [1] (Goodfellow et al.
2015
[]]
Poon & Domingos, 2011), [3] Yang et al. 2020 [4] (Zečević et al. 2021b). [5] (Kocaoglu et al.
2017
66 Zečević et al., 2021a), ) [7]
Xia et al.] 2021 8 Pawlloskk et al. 2020). [9] (Melnychuk et al.
2022
[10] (De Brouwer 2022), [11] Sanchez & Tsaftaris 2022 [12] [Khemakhem et al. 2021
parameterizing the mechanisms. we look at SPN as base L1 models, then we see how marginal inference is linear. A simple solution we arrive at by having this quick look at the taxonomy is that SCM parameterized by SPN should lead to inner-time mechanism inference. Indcod, this is the case as we show this quick empirical illustration.
Training and Estimation with LTNCM. Since LTNCM are a special case of SCM with SPN as param- eterizing units, we can apply inference in the same way. That is, we make use of the truncated factorization formula Pearl 2009) by choosing a sample (or Monte Carlo) based approximation thercof,
1 E. flv.x
p(V do x))
(8)
m
where mn is the number of samples for the unmodelled/ behind this formula is that an intervention will mutilate the original causal graph deleting dependence on X's parents. To perform training, one can simply resort to the maximization of the probability in terms of the negative log- likeliidddood to account for numerical stability, that is 8* = arg mingee - 1 Σ. log(p(v] do(x))) where n the number of data points. The consistency criterion refers to the assumption that a query like ply 1, 1 do(x 0)) should automatically evaluate to zero since it would be inconsistent to observe æ opposing the intervention.
terms U; and as in Dell The intuition
We investigate the newly-introduced LTNCM (Def specifically. We first "sanity check" the model by checking for causal effect and general density estimation. Then we conduct two experiments regarding tractability of cansal inference. More specifically, we answer the following questions:
Q1. To which degree are causal effects being captured on qualitatively different structures?
Q2. How is the estimation quality for interventional distribution modelling?
Q3. How does time complexity scale when increasing the SCM's size, that is, number of modelling units (?
Q4. How does time complexity scale when increasing the size of each unit per SCM structural equation )
14

---

Published in Transactions on Machine Learning Research (09/2023)
ATE
Mean-Sal
Mi
NCM
SCM Families
M2
SCM
L1
Coo(X=0)
42
Mi
M2
Mg
MA
M
.011
.010
.026
Ma
LTNCM NCM
M
.017
.011
.020
M
M3
.012
.009
.030
X
M4
.006
.010
.005
M
LTNCM
M
.075
.040
.310
7
M2
.012
.032
.022
M2
Ma
.032
.024
.033
Ma
M₁
.029
.021
.011
M₁
Density Estimation. Averaged Jensen-Shannon divergence values three dif- ferent distributions for each of the four SCM fam- ilies and for both NCM and LTNCM.
Table 2:
0
0.05
0.1
Figure 5: ATE. Averaged over multiple random seeds over multiple paramterizations of the given SCM. Both NCM and LTNCM perform well in estimating causal effects. (Best viewed color.)
Questions Q1-2 serve to validate that the presented model is indeed causal, whereas questions Q3-4 to show the intended speed up in terms of mechanism inference. For details regarding our synthetic data sets (that is, the used SCM families), the overall protocol and hyperparameters
point to appendix A.1
TL;DR. The questions Q1-2 are both answered in favor of LTNCM (see Fig and Tab that is, both causal effect estimation as well as general density estimation are competitive with standard NCM, while Q3- 4 confirm our previous discussions in terms of general inference being intractable and mechanism inference being linear for the LTNCM (see 6)g
Q1. Causal Effeect Estimation. We observe adequate modelling of the ATEs in both neural-causal models. The worst score on ATE for this binary setting would be 2, while the observed values are in the range [0, 0.09] thus significantly less. The confounded cases (Ma/4) are indeed inferred correctly. LTNCM with chosen hyperparameterss achieves sligthly worse score than the NCM but with the tendency of reduced variance in the estimates. We argue that the observed variances stem from the choice of SCM parametorizations.
Q2. Densily Estimation. We observe adequate modelling of the different densities (the actual plots for NCM are provided CLICK HERE, NCM Plots] and for LTNCM are provided [CLCKK HERE, LTNCM Plots] since error rates lie mostly in the low single digit domain. Most notably is the increased variance of the do(X = distribution for LTNCM on Mi. Observing closely, see that even the other distributions already show less-optimal performance. Since all experiments are conducted with the same, simple architectures, we argue that this non-optimization is explanatory.
Q3. Increasing Ny- Consider Fig 6 Left. We increase the size of the system which is arguably the most common form of scaling and relevant to the development of c.g. complex social networks or for biomedical analysis of complex proteins. As predicted by our intractability result in Thm both NCM (Xia et al.) 2021 and LTNCM (Def scale exponentially, since they are both parameterized SCM that do not represent computational but rather semantic relations of the variables. The offset difference stems from the specifics of our experimental setup and is negligible.
Q4. Increasing Sy. Consider Fig 6 Right. We increase the size of each the system's models (each structural equation) with the reasoning that nature it might occur for a causal relation be notoriously complex, for instance again in the medical domain the causal mechanism that revolves around risks of smoking long-standing example (Pearl & Mackenzie 2018- although one might argue that at
15

---

Published in Transactions on Machine Learning Research (09/2023)
(a)
Intractable Marginals
(b)
Tractable Equations
both NCM LTNCM
only LTNCM
N =1
Nu n
Su =
Se = =
Runttow (fn (eccodd)
30
Ranline (an secooda) seconds)
.02
t
107
.00
...
10
250
500
Number Undts/ Structurd Equations NU
Unit per Structund Equation Sy
Figure 6: Experiments Showing Different "Dimensions" of Tractability. (a) log-scale plot of NCM (iia et al. (021) versus LTNCM (De(ā) inference runtime (in seconds) when increasing the size of the SCM i.., the number of causal variables and thereby both the number of structural equations and subsequent models to be trained. We observe intractability as predicted by Thm [ (b) regular-scale plot of runtimes for LTNCM and NCM when incrcasing the capacity of the models to be learned for cach of the structural equation. We observe linear tractability only for LTNCM. (Best viewed in color.)
fine-grained view of the mechanisms they might again become simple. As suggested by our simple corollary (Cor only the LTNCM (Def(5) is linear tractable.
"What the LTNCM can and cannot do." The LTNCM provides tractable mechamism inference. That is, if one wants to evaluate any specific causal effect on a direct link between two variables, then this can be done in linear time. However, arguably most of the time in practice we are interested in general causal effect paths (where we do not know whether the pair we are considering are indeed a cause-effect pair). While one can consider the LTNCM further evaluation for use in practice with more demanding benchmarks needs to be consulted before making definite statement, however, theoretically LTNCM gain the advantage at least on mechanism level. As noted in the beginning parts of this manuscript, however, direct link mechanisms might often times not be too complex to bogin with, thus rendering the importance of these gain possibly negligible.
clear winner over the classic NCM, it needs to be noted that
Concluding Remarks to LTNCM. As suggested by the title of this subsection, we've considered the presentation of this new LTNCM model as a 'Bonus! The purpose of the presented experimental primer was to provide a proof of concept for both capturing the diffcrences in causal model inferences as well actually implementing such different models. Further study of specifically the LTNCM model and its derivalives is purposefully left for study in future work.
8 Concluding Discussion and Future Directions
To establish our discussion of causal inference and tractability, first identified the necessary distinctions between existing models. Our proposed 'spectrum' of causal models, which was classified in terms of expres- sivity on the PCH, was comprised of "non-causal", "partially causal" and "structural causal" models. Since the middle class has never been discussed in the literature prior to this work, we provided a first technical definition as a foundation for further investigation. We then delved into each of these model families with our discussion of tractable causal inference. We highlighted the importance of tractability for long-term development of practical, gexeraencottonn lcarning systems while providing a broad, comprehensive overview of the discriminative properties for the existing 'zoo' of models (see our summary section). Establishing this overview involved, among other things, that we proved the general intractability result for parameterized SCM (see Thm T -which we did using the classical techniques previously used for belief networks. As a 'bonus,' we also showed ways of coping with existing intractability as revealed by our tabular taxonomy. We did so by demonstrating a new model, called LTNCM, which is a NCM that uses SPN-modules to boost mechanism inference to linear time (opposed to polynomials in standard NCM).
We believe that future models will fall into the defined spectrum of causal models and with them their tractability properties. Since future models will require both number-wise more interactions and also more
16

---

Published in Transactions on Machine Learning Research (09/2023)
complex interactions, research at the integration of causality and AI/ML will inevitably encounter the tractability question. Causal inference engines like the do-caloulus are a tremendously powerful tool, yet ultimately, complete automation is what Al seems to aim for. As suggested in Tab making partially causal models like iSPN (Zéčović et al. 2021a) "less partial" or structural causal models like NCM (Xia et al. 2021 "more tractable" both aim at the same end result- Imalaale causal models. Coming from the
tractability perspective, the original introduction of SPNs from ACs (Darwiche 2003) Poon & Domingos 2011) that allowed for replacing semantic relations through computational ones might provide hints for a
tractable view onto the Pearlian notion of causality. Also, providing large-scale example akin to ImageNet
KKrihevsky et al. 2012). might be beneficial for future investment into tractable causal inference rescarch.
Final Remarks. We hope that our definition of partially causal models, the impossibility result for param- eterized SCM, alongside the taxonomy for tractability in causal models and its initial model (the LTNCM) can raise awareness for this novel research direction. We dearly hope so since achieving success with causality in real world downstream tasks will not only depend on learning correct models as we also require having the practical ability to gain access in finite resources to model inferences, ideally as efficiently as possible.
Acknowledgements
The work was supported by the Hessian Ministry of Higher Education Research, Science and the Arts (HMWK) via the DEPTH group CAUSE of the Hessian Center for Al (hessian.ai). This work was partly funded by the ICT-48 Network of AI Research Excellence Center "TAILOR" (EU Horizon 2020, GA No 952215) and by the Federal Ministry of Education and Research (BMBF; project "PlexPlain", FK2 011S19081). It benefited from the Hessian research priority programme LOEWE within the project White- Box, the HMWK cluster project "The Third Wave of AI." and the Collaboration Lab * *AI in Construction" (AICO) of the TC Darmstadt and HOCHTIEF.
References
Elias Bareinboim, Juan D Correa, Duligur Ibeling, and Thomas Icard. lon pearl's hicrarchy and, Technical Report, 2020.
Toana Bica, Ahmed Alaa, and Mihaela Van Der Schaar. Time series deconfounder. Estimating mrettment effects over time in the presence of hidden confounders. In ICML, 2020.
Daniel Bienstock, Gonzalo Muñoz, and Sebastian Pokutta. Principled deep neural network training through lincar programming. arXio preprint arxiv: 1810:1110..0218, 2018.
Stephan Bongers, Patrick Forré, Jonas Peters, and Joris M Mooij. Foundations of structural causal models with cycles and latent variables. The Annals of Statistics, 49(5)22885 2915, 2021.
Daphna Buchsbaum, Sophie Bridgers, Deena Skolnick Weisberg, and Alison Gopnik. The power of possibility: Causal learning, counterfactual reasoning, and pretend play. Philosophical Transactions of the Royal Sociely B: Biological Sciences, 367(1599):2202 2212, 2012.
YooJung Choi, Antonio Vergari, and Guy Van den Broeck. Probabilistic circuits: A unifying framework for tractable probabilistic models. Technical report, Technical report, 2020.
Stephen A Cook. The complexity of theorem-proving procedures. In Proceedings of the third annual ACM symposium on Theory of computing, pp. 151-158, 1971
Gregory F Cooper. The computational complexity of probabilistic inference using bayesian belicf networks. Arlificial intelligence, 42(2-3):393 405, 1990.
George Cybenko. Approximation by superpositions of sigmoidal function. Mathematics of control, signals and systems, 2(4):303-31) 314, 1989.
Adnan Darwiche. A differential approach to inference in bayesian networks. Journal of the ACM (JACM), 50(3):280-300) 2003.
17

---

Published in Transactions on Machine Learning Research (09/2023)
Adnan Darwiche. Causal inference using tractable circuits. In NeurIPS 2021 Workshop "Causal Inference & Machine Learning: Why now?", 2021.
Edward De Brouwer. Deep counterfactual estimation with categorical background variables. Neural Information Processing Systems, 1135213-35225 2022.
Advances in
lan J Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversarial examples. ICLR, 2015.
Alison Gopnik. Scientific thinking in young children: Theoretical advances, empirical research, and policy implications. Science, 337(6102):1623 1627, 2012.
Joseph F Hair Jr and Marko Sarstedt. Data, measurement, and causal inferences in machine learning: opportunities and challenges for marketing. Journal of Marketing Theory and Practice, 2021.
Miguel A Hernán. The c-word: scientific euphemisms do not improve causal inference from observational data. American journal of public health, 108(5):616-619, 2018.
William Hoiles and Mihaela Schaar. Bounded off- off-po evaluation with missing data for course recommen- dation and curriculum design. In ICML, 2016.
Paul W Holland. Statistics and causal inference. Journal of the American statistical Association, (1(66)): 945 960, 1986.
Kurt Hornik, Approximation capabilities of multilayer feedforward networks. Neural networks, 4(2):251-22) 257, 1991.
Jean Kaddour, Aengus Lynch, Qi Liu, Matt J Kusner, and Ricardo Silva. Causal machine learning: A survey and open problems. arXiv preprint arXiv:2206. 15475, 2022.
Agastya Kalra, Abdullah Rashwan, Wei-Shou Hsu, Pascal Poupart, Prashant Doshi, and Georgios Trim- ponias. Online structure learning for feed-forward and recurrent sum-product nelworks. NewrIPS, 2018.
llyes Khemakhem, Ricardo Monti, Robert Leech, and Aapo Hyvarinen. Causal autoregressive flows. International conference on artificial intelligence and statistics, pp. 3520-353 PMLR, 2021.
Diederik P Kingma and Jimmy Ba. arXiv:1412.6900 2014.
Adam: A method for stochastic optimization. arXiv preprint
Murat Kocaoglu, Christopher Snyder, Alexandros Dimakis, and Sriram Vishwanath. Causalgan: Learning causal implicit gencrative models with adversarial training. arXiv preprint arXiv:1700 179.00000,,,2,, 2017.
Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton. Imagenet classification with deep convolutional neural networks. Advances in neural information processing systems, 25:1097-1105, 2012.
Amélie Levray and Vaishak Belle. Learning credal sum sum-produce networks. AKBC, 2020.
John McCarthy. What is artificial intelligence? 1998.
John McCarthy and Patrick J Hayes. Some philosophical problems from the standpoint of artificial intelli- gence. In Readings in artificial intelligence, pp. 431-450 Elsevier, 1981.
Valentyn Melnychuk, Dennis Frauen, and Stefan Feuerriegel. Causal transformer for estimating counterfac- tual outcomes. In International Conference on Machine Learning, pp.
PMLR, 2022.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Alex Graves, loannis Antonoglou, Daan Wierstra, and Martin Riedmiller. Playing atari with deep reinforcement learning. arXie preprinl arXin:132255002 2013.
Joannis Papantonis and Vaishak Belle. Interventions and counterfactuals in tractable probabilistic models: Limitations of contemporary transformations. arXiv preprint ar arXi::2001.100 10905. 2020.
18

---

Published in Transactions on Machine Learning Research (09/2023)
lago París, Raquel Sänchez-Caucee and Francisco Javier Diez. Sum-product networks: A survey. arXiv preprint ar arx::2200400116 2020.
Nick Pawlowski, Daniel C Castro, and Ben Glocker. Deep structural causal models for tractable counterfac- tual inference. arXiv preprint Xix:00000 X7x::2006.06485, 2020.
Judea Pearl. From bayesian networks to causal networks. In Mathematical models for handling portial knowledge in artificial inlelligence. 1995.
Judea Pearl. Causalily. Cambridge university press, 2009.
Judea Pearl and Dana Mackenzie. The book of why: the new science of couse and effect. Basic books, 2018.
Robert Peharz, Steven Lang, Antonio Vergari, Karl Stelzne, Alejandro Molina, Martin Trapp, Guy Van den Broeck, Kristian Kersting, and Zoubin Ghahramani. Finsum networks: Fast and scalable learning of tractable probabilistic circuits. ICML, 2020a.
Robert Peharz, Antonio Vergari, Karl Stelzner, Alejandro Molina, Xiaoting Shao, Martin Trapp, Kristian Kersting, and Zoubin Ghahramani. Random sum-product networks: A simple and effective approach to probabilistic deep learning. In UAI, 2020b.
Derek Penn and Daniel J Povinelli. Causal cognition in human and nonhuman animals: comparative, critical review. Annu. Rev. Psychol., 58:97 118, 2007.
Jonas Peters, Dominík Janzing, and Bernhard Schölkopf. Elements of cousal inference. The MIT Press, 2017.
Hoifung Poon and Pedro Domingos. Sum-product networks: A new deep architecture. In 2011 IEEE International Conference on Computer Vision Workshops (ICCV Workshops), pp. 689 690. IEEE, 2011.
Dan Roth. On the hardness of approximate reasoning. Artificial Intelligence, 82(1-2):273 302, 1996.
Paul K Rubenstein, Sebastian Weichwald, Stephan Bongers, Joris M Mooij, Dominik Janzing, Moritz Grosse- Wentrup, and Bernhard Schölkopf. Causal consistency of structural equation models. arXiv preprint wvXiv:170.00019, 2017.
Pedro Sanchez and Sotirios A Tsaftaris. Diffusion causal models for counterfactual estimation. arXiv preprint arXiv:220..1011 2022.
Xiaoting Shao, Alejandro Molina, Antonio Vergari, Karl Stelzner, Robert Pcharz, Thomas Liebig, and Kris- tian Kersting. Conditional sum-product networks: Imposing structure on deep probabilistic architectures. arXiv preprint Xrx:::1005 900.00550, 2019.
Or Sharir and Amnon Shashua. Sum-product-quotien networks. In ATSTATS, 2018.
Christian Steinruecken, Emma Smith, David Janz, James Lloyd, and Zoubin Ghahramani. The automatic statistician. In Automated Machine Learning, pp. 161-173. Springer, Cham, 2019.
Martin Trapp, Robert Peharz, Hong Ge, Franz Pernkopf, and Zoubin Ghahramani. Bayesian learning of sum-product networks. NewrIPS, 2019.
G Van den Broeck, N Di Mauro, and A Vergari. Tractable probabilistic models: Representations, algorithms, learning, and applications. Tutorial at UAT, 2019.
Ashish Vaswani, Noam Shazcer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. In NewrIPS, 2017.
Antonio Vergari, Nicola Di Mauro, and Floriana Esposito. Visualizing and understanding sum-product networks. Machine Learning, 108(4):5511577 2019.
19

---

Published in Transactions on Machine Learning Research (09/2023)
Kevin Xia, Kai-Zhan Lee, Yoshua Bengio, and Elias Barcinboim. The causal-neural connection: Expressive- ness, learnability, and inference. Aduances in Neural Informalion Processing Systems, 1210823-10833 2021.
Mengyue Yang, Furui Liu, Zhitang Chen, Xinwei Shen, Jianye Hao, and Jun Wang. Causalvae: Structured causal disentanglement in variational autoencoder. arXiv e-prints, pp. arXiv-2004, 2020.
Matej Zečević, Devendra Singh Dhami, Athresh Karanam, Sriraam Natarajan, and Kristian Kersting, In- terventional sum-product networks: Causal inference with tractable probabllistic models. In NeurIPS, 2021a.
Matej Zečević, Devendra Singh Dhami, Petar Veličković, and Kristian Kersting. Relating graph neural networks to structural causal models. arXiv preprint arXiv:2109.04175 2021b.
Han Zhao, Mazen Melibari, and Pascal Poupart. On the relationship between sun-product networks and bayesian networks. In JCML, 2015.
20

---

Published in Transactions on Machine Learning Research (09/2023)
A Further Details
We make use of this appendix following the main paper to provide some additional material.
A.1 Details for the 'Bonus' Experiments Speeding Up Mechanism Inference in NCM
Data Sets. Since are interested in qualitative behavior in light of the theoretical results established previously, we consider custom SCM simulations. For instance consider the following four families: the collider SCM given by
X (x(W,Ux) W. Ux
Y fy(Uy)=U)
M =
Z fz(X,Y,U2) =X v (Y U2) Sw(Uw) =Uw
W -
and a simple chain SCM which has no confounding given by
X fx(Ux) =Ux
Y fx(,UUy) =X Uy
M2
Z - [z((,Uz)= =Y Uz
W - fw(2,Uw) =0 A UW.
and the confounded SCM is given by
X fx(2,Ux) =Z Ux
Y -
=(X (r) Z - fu(U2)=44
M3
W - (w(XUUw) =X A Uw,
and the backdoor SCM given by
X+ - fx(Z,Ux) =Z
Y - fr, Uv) =X (W a Uv)
M4
- (z(Uz) =Uz
W fw(Z,Uw) =Z A Uw,
where @ v, A denole logical XOR, OR, and AND. Note that (for simplicity of analysis) we consider binary variables, however, (LT)NCM naturally extend to the categorical and continuous variables. Note that the collider is unconfounded structure, thereby conditioning amounts to intervening, p(y]=) p(yl do(x)), while for the backdoor this equality does not
the causal effect from X on Y is confounded via the backdoor X - over nodes Z, W. We choose U ~ Unif(a, b) to be uniform random variables each, and we randomize parameters a,
To account for reproducibility and stability the presented results, we used learned models for four different random seeds and for each parameterization of any given underlying SCM. For the NCM's neural networks, input//ontput-layers are Pa, + 1 and respectively. For the LTNCM's SPNs, we deploy simple two-layer SPNs (following the layerwise principle introduced in Peharz of Icaf nodes, the second layer of product nodes, the third layer of sum nodes and final product node aggregation. The number of channels is set to 30. We use ADAM (Kingma & Ba 2014) optimization, and train up to three passes of 10k data points sampled from the observational distribution of any SCM. For experiments in which the size of the SCM is being increased, we use simple chain and extend it itcratively. For experiments in which the capacity of the mechanism (or units) of the parameterized SCM are being increased, fixed chain SCM structure and scale the model capacity linearly. Le., the MI.Ps increase
Protocol and Parameters.
deploy simple MLP with three hidden layers of 10 neurons each, and the
all (2020a)) where the first layer consists
21

---

Published in Transactions on Machine Learning Research (09/2023)
their hidden layers neurons number while SPNs increase their layer channel. For causal effect estimation, we focus the average treatment effect given by ATE F) :- R[F] do(T = - do( 1)] that for the
binary setting reduces to probabilistic difference p(Y = 1 do = 1)) p(Y - do 0)) = AT E.) (JSD) with base 2
For mcasuring density estimation quality, we resort to the that is bounded [0, 1] where indicales identical probability density functions i.e., an optimal match terms of JSD.
A.2 Code Repository and Details of Technical Setup
This brief section provides anchor points for any further relevant information.
Code Repo. Our code repository alongside visualizations publically available at: https://githhb: http://cc..aactooooo///aaaaaaaaa
Technical Details. All experiments being performed MacBook Pro (13-inch, 2020, Four Thun- derbolt 3 ports) laptop rumning a 2,3 GHz Quad-Core Intel Core i7 CPU with a 16 GB 3733 MHz LPDDRAX RAM on time scales ranging from few seconds to an hour for the longest experiment setting.
22


Reviews:
[{"review_id": "sbLVpLqWBS", "reviewer": "Reviewer_KHeR", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- This paper is novel and might be promising in future research on causality.\n- This paper is well-organized and generally reasonable.\n\nWeaknesses:\n- The writing of this paper needs to be further polished. Many descriptions and demonstrations are not straightforward, which makes it quite hard to capture the true intention.\n- Too much informal theoretical proof. For example, Theorem 1, and Corollary 2, which are two major theoretical contributions of this paper, their derivations lack rigorous mathematical derivation, which makes the results unconvincing. It is suggested to provide formal derivation in future versions.\n- Many abbreviations are not carefully introduced, which largely confuses the readers. For example, what are “clauses” and “3-SAT reduction” in Theorem 1? \n- It is great to make a bald move to promote causality research, however, the experiments of this paper is quite inadequate, it is suggested to conduct more experiments on both effectiveness and efficiency in future versions.\n- Minor issues: Typos: “Before investigating the this tractability of causal inference issue”, “so far in the literature we usually have F be only of one such model choice.”, “since the functions of the structural equations often times describe reasonably simple mechanisms”, “We find that for the NCM-Type 2 worse”, and error symbol “[b!]” in Figure 4 and Table 1.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper provides a theoretical perspective to show that neurally-parameterized structural causal models (NCM) cannot return an answer to a query in polynomial time. Moreover, the authors also claim that a model can still answer a causal query even if it is not an SCM, which indicates partially causal models (PCM). By carefully demonstrating the background works and discussing the theoretical properties of PCM, a novel direction of causality is proposed by this paper. Additionally, several experiments are conducted to validate the tractability of NCM and TLNCM.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "- Please polish the paper writing for better demonstration.\n- The theoretical analyses are not formal and solid enough for proposing a novel causal direction.\n- It is suggested to provide more empirical evidence for both effectiveness and efficiency.", "broader_impact_concerns": "There are no ethical implications.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "g0kJTKopBX", "reviewer": "Reviewer_6CSs", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n1. This paper offers valuable insights for enhancing the efficiency of existing causal inference methods. \n2. The proposed model, LTNCM, demonstrates the capability of performing causal inference with linear time complexity. By integrating SPN modules into NCM, LTNCM leverages the simplicity and efficiency of SPN to achieve efficient causal inference.\n\nWeaknesses:\n\n1. In Section 3, the definition of finite PCMs is not clear. The authors mentioned that finite PCMs are models that can provide interventional and/or counterfactual distributions but never generate infinitely many. Can the author provide an example and discuss the definition of finite PCMs further? Why does CausalVAE belong to this class of model?\n2. The definition of $\\mathcal{L}_i$ is not clear, especially conditions ii and iii. It would be better to explain them more in detail.\n3. For the definition of LTNCM, why does LTNCM need multiple models? what do these models represent?\n4. What is the cost of LTNCM to reduce the time complexity of causal inference to linear? Theorem 1 shows that Causal (marginal) inference in parameterized SCM is NP-hard, but Definition 5 and Corollary 2 show that LTNCM could reduce the time complexity of causal inference to linear. This is a counter-intuitive conclusion.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper explores the tractability of existing causal inference methods and proposes potential approaches that are more manageable. It highlights that not all \"causal\" models are equal, distinguishing between SCM and partially causal models (PCM) capable of answering causal queries. The authors present a tabular taxonomy that categorizes different model families, including correlation-based, PCM, and SCM, based on their tractability properties. Then, they propose Linear Time Neural Causal Model (LTNCM) in conjunction with SPN, which enables linear time mechanism inference. By leveraging the simplicity of individual components described using SPN, LTNCM achieves efficient causal inference.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "I hope the authors can address the weaknesses mentioned above.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "eAHUJPR2Zz", "reviewer": "Reviewer_dmSA", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### Strengths:\nThe exploration of partially causal models and the investigation of tractability in causal models make valuable contributions to the research field.\n\n\n### Weaknesses:\n1. The paper is not well-written and hard to follow. Several concepts and notations are introduced unclearly or confusingly. For example, the section on sum-product networks in Section 2 is perplexing. The following points highlight some areas of confusion:\n\n- When ‘IV’ is first introduced in equation (4), it would be helpful to provide the full meaning or expand its acronym to ensure clarity and understanding for readers.\n\n- Please clarify the meaning of $S(\\lambda)$ and $C(\\lambda)$ in equation (3). Additionally, explain the concept of 'scope' of a node in equation (4). When introducing new concepts, please provide adequate explanations. Please address the role of $P$ in equation (6).\n\n- The meaning of 'iSPN' and equation (7) remains unclear.\n\n2. One area that requires improvement is the inclusion of relevant related works. For instance, the paper should discuss the identifiability of interventional/counterfactual probabilities across more types of models, like the one based on VAE, GAN and normalizing flow.\n\n3. The contribution and novelty of the paper appear limited. The proposed LTNCM method seems to be a specific case of NCM, lacking distinctiveness.\n\n4. In Section 3, during the introduction of 'finite PCMs', it is ambiguous what is meant by 'models that can provide interventional and/or counterfactual distributions but never generate infinitely many.' Specify what is generated. Moreover, in Definition 1, clarify the meaning of the operator 'X' and the absolute value of a certain level of PCH.\n\n\n### Minor concerns:\n- In the third line of the last paragraph in Section 3, 'pf' should be corrected to 'of'.\n\n- In Table 1, it would be better to explicitly show the legend and citation of each model instead of including it within the paragraph.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The authors delve into the tractability of different types of causal inference, examining the conditions, costs, and feasibility of such inferences. They present an impossibility result for tractable inference within parameterized SCM and introduce the concept of partially causal models, shedding light on the trade-offs between model expressivity and inference tractability. Additionally, they propose LTNCM, a linear time mechanism inference method, as an alternative to the polynomial complexity of standard NCM.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Please refer to the weaknesses and minor issues above.", "broader_impact_concerns": "Not applicable.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper offers a theoretical vantage point to establish that the feasibility of providing a polynomial-time response to a query is unattainable for neurally-parameterized structural causal models (NCM). Furthermore, the paper asserts the possibility for models beyond the realm of structural causal models (SCM), illustrating the concept of partially causal models (PCM) as a means to address causal queries. The exposition encompasses thorough elucidation of the foundational groundwork and comprehensive examination of the theoretical attributes of PCM, thereby introducing a fresh avenue in the domain of causality. 

The reviewers expressed their primary apprehension regarding the presentation of the paper, attributed to the inclusion of technical terminology spanning both causal inference and SAT. The revised version demonstrated substantial enhancements in presentation. Nonetheless, a reviewer still voiced concerns about the clarity of the theoretical segment. Although my review didn't identify any significant issues, I would recommend the authors to refine this section for improved readability. For instance, in the proof of Proposition 1, the authors referenced a straightforward outcome from a prior paper based on the positive support assumption. However, this assumption's explanation is absent in the current paper. It would enhance the self-contained nature of the paper to incorporate a definition for the positive assumption.
Decision: Accept (poster)