This is a sel -a chi ed e sion o an o iginal a icle. This e sion
may di e om he o iginal in pagina ion and ypog aphic de ails.
Au ho (s):
Ti le:
Yea :
Ve sion:
Copy igh :
Righ s:
Righ s u l:
Please ci e he o iginal e sion:
CC BY 4.0
h ps://c ea i ecommons.o g/licenses/by/4.0/
Causal E ec Iden i ica ion om Mul iple Incomple e Da a Sou ces : A Gene al Sea ch-
Based App oach
© Au ho s, 2021
Published e sion
Tikka, San u; Hy inen, An i; Ka anen, Juha
Tikka, S., Hy inen, A., & Ka anen, J. (2021). Causal E ec Iden i ica ion om Mul iple
Incomple e Da a Sou ces : A Gene al Sea ch-Based App oach. Jou nal o S a is ical So wa e, 99,
A icle 5. h ps://doi.o g/10.18637/jss. 099.i05
2021
JSS Jou nal o S a is ical So wa e
Augus 2021, Volume 99, Issue 5. doi: 10.18637/jss. 099.i05
Causal E ec Iden i ica ion om Mul iple
Incomple e Da a Sou ces: A Gene al Sea ch-Based
App oach
San u Tikka
Uni e si y o Jy askyla
An i Hy inen
Uni e si y o Helsinki
Juha Ka anen
Uni e si y o Jy askyla
Abs ac
Causal e ec iden i ica ion conside s whe he an in e en ional p obabili y dis ibu ion
can be uniquely de e mined wi hou pa ame ic assump ions om measu ed sou ce dis-
ibu ions and s uc u al knowledge on he gene a ing sys em. While comple e g aphical
c i e ia and p ocedu es exis o many iden i ica ion p oblems, he e a e s ill challenging
bu impo an ex ensions ha ha e no been conside ed in he li e a u e such as com-
bined anspo abili y and selec ion bias, o mul iple sou ces o selec ion bias. To ackle
hese new se ings, we p esen a sea ch algo i hm di ec ly o e he ules o do-calculus.
Due o he gene ali y o do-calculus, he sea ch is capable o aking mo e ad anced da a-
gene a ing mechanisms in o accoun along wi h an a bi a y ype o bo h obse a ional
and expe imen al sou ce dis ibu ions. The sea ch is enhanced ia a heu is ic and sea ch
space educ ion echniques. The app oach, called do-sea ch, is p o ably sound, and i is
comple e wi h espec o iden i iabili y p oblems ha ha e been shown o be comple ely
cha ac e ized by do-calculus. When ex ended wi h addi ional ules, he sea ch is capa-
ble o handling missing da a p oblems as well. Wi h he e sa ile sea ch, we a e able
o app oach new p oblems o which no o he algo i hmic solu ions exis . We pe o m a
sys ema ic analysis o bi a ia e missing da a p oblems and s udy causal in e ence unde
case-con ol design. We also p esen he Rpackage dosea ch ha p o ides an in e ace
o a C++ implemen a ion o he sea ch.
Keywo ds: causali y, do-calculus, selec ion bias, anspo abili y, missing da a, case-con ol
design, me a-analysis.
1. In oduc ion
In many ields o science, a p ima y in e es is de e mining causal e ec s, ha is, dis ibu ions
P(Y|do(X),Z), whe e a iables Ya e obse ed, a iables Xa e in e ened upon ( o ced o
2Causal E ec Iden i ica ion om Mul iple Incomple e Da a Sou ces
alues i espec i e o hei na u al causes) and a iables Za e condi ioned on (Pea l 2009). In
his pape , ins ead o placing a ious pa ame ic es ic ions based on backg ound knowledge,
we a e in e es ed in he ques ion o iden i iabili y: can he causal e ec be uniquely de e mined
om he dis ibu ions (da a) we ha e and a g aph ep esen ing ou s uc u al knowledge on
he gene a ing causal sys em.
In he mos basic se ing we a e iden i ying causal e ec s om a single obse a ional inpu
dis ibu ion, co esponding o passi ely obse ed da a. To sol e such p oblems mo e gene ally
han wha is possible wi h he back-doo adjus men (Spi es, Glymou , and Scheines 1993;
Pea l 2009;G eenland, Robins, and Pea l 1999), Pea l (1995) in oduced do-calculus, a se
o h ee ules ha oge he wi h p obabili y heo y enable he manipula ion o in e en ional
dis ibu ions. Shpi se and Pea l (2006b) and Huang and Val o a (2006b) showed ha do-
calculus is comple e by p esen ing polynomial- ime algo i hms whose each s ep can be seen
as a ule o do-calculus o as an ope a ion based on basic p obabili y heo y. The algo i hms
ha e a high p ac ical alue because he ules o do-calculus do no by hemsel es p o ide an
indica ion on he o de in which he ules should be applied. The algo i hms sa e us om
manual applica ion o do-calculus, which is a edious ask in all bu he simples p oblems.
Since hen many ex ensions o he basic iden i iabili y p oblem ha e appea ed. In iden i-
iabili y using su oga e expe imen s (Ba einboim and Pea l 2012a), o z-iden i iabili y, an
expe imen al dis ibu ion is a ailable in addi ion o he obse ed p obabili y dis ibu ion.
Fo da a obse ed in he p esence o selec ion bias, bo h algo i hmic and g aphical iden i i-
abili y esul s ha e been de i ed (Ba einboim and Tian 2015;Co ea, Tian, and Ba einboim
2018). Mo e gene ally, he p esence o missing da a necessi a es he ep esen a ion o he
missingness mechanism, which poses addi ional challenges (Mohan, Pea l, and Tian 2013;
Shpi se , Mohan, and Pea l 2015;Bha acha ya, Nabi, Shpi se , and Robins 2019). Ano he
dimension o complexi y is he numbe o a ailable da a sou ces. Iden i ica ion om a mix-
u e o obse a ional and in e en ional dis ibu ions ha o igina e om mul iple concep ual
domains is known as anspo abili y o which comple e solu ions exis in a speci ic se ing
(Ba einboim and Pea l 2014).
While comple eness has been accomplished o a numbe o basic iden i iabili y p oblems,
he e a e s ill many challenging bu impo an ex ensions o he iden i iabili y p oblem ha
ha e no been s udied so a . Table 1 ecaps he cu en s a e o he a iden i iabili y
esul s; i also desc ibes gene aliza ions ha we aim o in es iga e in his pape . To ind
solu ions o he mo e complica ed iden i iabili y p oblems, we p esen a uni ied app oach o
he iden i ica ion o obse a ional and in e en ional causal que ies by cons uc ing a sea ch
algo i hm ha di ec ly applies he ules o do-calculus. We impose no es ic ions on he
numbe o ype o known inpu dis ibu ions: we hus p o ide a solu ion o p oblems o
which no o he algo i hmic solu ions exis (Row 8 in Table 1). We also ex end o iden i iabili y
unde missing da a oge he wi h mechanisms ela ed o selec ion bias and anspo abili y
(Row 11 in Table 1).
The ollowing in oduc o y example does no all unde any o he p e iously sol ed special
cases o Table 1, hus necessi a ing ou app oach. Conside human esou ce managemen
analyzing he emune a ion policy in a company. The g aph o Figu e 1shows he key
a iables. The sala y (Y) o an employee consis o a base sala y (no modeled explici ly)
and a bonus (B). The base sala y depends on educa ion (E) and pe o mance (X) o he
employee. The le el o pe o mance is e alua ed by he supe iso o he employee and i is
one o he ac o s ha a ec s he le el o bonus. The pe o mance depends on he educa ion
Jou nal o S a is ical So wa e 3
X: Pe o mance
E: Educa ion
Y: Sala y
B: Bonus
A: A i ude
Figu e 1: G aph o he example on human esou ce managemen in a company.
as well as he a i ude (A) o he employee and he eam. The a i ude may also ha e a di ec
e ec on he bonus.
We a e in e es ed in es ima ing he o al causal e ec o pe o mance on he sala y, i.e., quan i-
ying how changes in pe o mance a ec he sala y. The sala y (Y), bonus (B), educa ion (E)
and pe o mance (X) o he employees a e a ailable om he egis y o he human esou ce
depa men . Da a on a i ude (A), bonus (B) and pe o mance (X) ha e been collec ed in an
anonymized su ey ha canno be linked o he egis y on he pe sonal le el. The ques ion
o in e es is he iden i iabili y o P(Y|do(X)) om he da a sou ces P(Y, B, E, X)and
P(A, B, X). Using he machine y de eloped in his pape , we can iden i y he causal e ec
wi h he o mula
P(Y|do(X)) = X
B,A
P(A)P(B|X, A)X
E
P(E)P(Y|X, B, E),
whe e he condi ional dis ibu ions can be di ec ly de e mined om he a ailable da a sou ces
(see Sec ion 6 o u he de ails).
To comba he inhe en compu a ional complexi y o he sea ch-based app oach, we de i e
ules and echniques ha a oid unnecessa y compu a ional s eps. We a e able o de ec i ial
que ies whe e non-iden i iabili y can be de e mined di ec ly om he inpu s. We also p esen
a sea ch heu is ic ha conside ably speeds up he sea ch in cases whe e he e ec is indeed
iden i iable. The app oach, called do-sea ch, is p o ably sound and i e ains he comple eness
in he cases p e iously p o en o be sol ed by he ules o do-calculus. We can easily scale
up o he p oblem sizes commonly epo ed in he li e a u e. The Rpackage dosea ch (R
Co e Team 2021;Tikka, Hy inen, and Ka anen 2021) p o ides an implemen a ion o do-
sea ch and is a ailable om he Comp ehensi e RA chi e Ne wo k (CRAN) a h ps://
CRAN.R-p ojec .o g/package=dosea ch.
O he a ailable so wa e o causal e ec iden i iabili y p oblems a e only applicable o a
subse o he p oblems p esen ed in Table 1. The causale ec Rpackage (Tikka and Ka -
anen 2017a) can only be used o p oblems on Rows 1–3 and 5–7 o he able, p o iding
implemen a ions o he ele an algo i hms. Fo he p oblem on Row 1, he gene alized ad-
jus men c i e ion (Pe ko ić, Tex o , Kalisch, and Maa huis 2015) can be applied using he
dagi y package (Tex o , Van de Zande , Gil ho pe, Liśkiewicz, and Ellison 2016) o he pcalg
package (Kalisch, Mächle , Colombo, Maa huis, and Bühlmann 2012) in R. The gene alized
back-doo c i e ion (Maa huis and Colombo 2015) is also a ailable in he pcalg Rpackage.
The s anda d back-doo c i e ion is a ailable in he Py hon package DoWhy (Sha ma and
4Causal E ec Iden i ica ion om Mul iple Incomple e Da a Sou ces
Missing
P oblem Inpu da a Me hod
(Re e ence) Ta ge (assump ions) pa e n (comple e)
1 Causal e ec iden i iabili y P(Y|do(X)) P(V)None ID
(Shpi se and Pea l 2006b) (Yes)
2 Causal e ec iden i iabili y P(Y|do(X),Z)P(V)None IDC
(Shpi se and Pea l 2006a) (Yes)
3z-iden i iabili y P(Y|do(X),Z)P(V),P(V B|do(B)) None zID
(Ba einboim and Pea l 2012a)(NE, ED) (Yes)
4g-iden i iabili y P(Y|do(X)) {P(V Bi|do(Bi)}None gID
(Lee, Co ea, and Ba einboim
2019)
(ED) (Yes)
5 Su oga e ou come P(Y|do(X),Z){P(Ai|do(Bi),Ci)}None TRSO
iden i iabili y (NE, SO) (No)
(Tikka and Ka anen 2019)
6mz- anspo abili y P(Y|do(X),Z){P(V (Bi∪Ti)|do(Bi),Ti)}None TRmz
(Ba einboim and Pea l 2014)(NEDD, ED) (Yes)
7 Selec ion bias eco e abili y P(Y|do(X),Z)P(V S|S)Selec ion RC
(Ba einboim and Tian 2015) (Unknown)
8 Gene alized iden i iabili y P(Y|do(X),Z){P(Ai|do(Bi),Ci)}None do-sea ch
(Unknown)
9 Missing da a eco e abili y P(V)P(V∗)Res ic ed –
(Mohan e al. 2013) (Yes)
10 Missing da a eco e abili y P(V)P(V∗)A bi a y –
(Bha acha ya e al. 2019) (Unknown)
11 Gene alized iden i iabili y P(Y|do(X),Z){P(A∗
i|do(Bi),C∗
i)}A bi a y do-sea ch
wi h missing da a (No)
Table 1: Sol ed and unsol ed p oblems in causal e ec iden i ica ion. Bold-i alic deno es he
p e iously unsol ed p oblems o which do-sea ch can now be used. Inpu P(V)s ands o
passi ely obse ed join dis ibu ion o all a iables. Inpu P(V∗)is he join dis ibu ion wi h
missing da a (see Sec ion 4). The a iable se s p esen in he same dis ibu ion a e disjoin .
Inpu P(V B|do(B)) s ands o an expe imen whe e all a iables a e measu ed and
inpu P(A|do(B)) s ands o an expe imen whe e only a subse A⊂Vo he a iables is
measu ed. No a ion {·} deno es a se o inpu s enume a ed by he index i. The assump ions
o nes ed expe imen s (NE), en i e dis ibu ions (ED) and nes ed expe imen s in di e en
domains (NEDD) a e explained in Sec ion 2. Assump ions ela ed o su oga e ou comes (SO)
can be ound in (Tikka and Ka anen 2019). Inpu P(V|S)means he join dis ibu ion
unde selec ion bias. The las column gi es he name o an algo i hm ha can be used o
sol e he p oblem i one exis s and whe he i (o a heo em when no algo i hm is p o ided)
p o ides a comple e solu ion o he p oblem, o whe he he comple eness s a us is no known.
An algo i hm is comple e i i e u ns a co ec o mula p ecisely when he a ge que y is
iden i iable. P oblems 1–7 a e special cases o P oblem 8 and P oblems 1–10 a e special cases
o P oblem 11.
Kiciman 2019). Algo i hms implemen ed in causale ec un in polynomial ime and can ou -
pe o m dosea ch in hei espec i e es ic ed p oblem se ings especially wi h la ge g aphs.
Fo a comp ehensi e pe o mance compa ison be ween causale ec and a ious adjus men
c i e ia, see (Van de Zande , Liśkiewicz, and Tex o 2019).

Jou nal o S a is ical So wa e 5
The pape is s uc u ed as ollows. Sec ion 2 o mula es ou gene al iden i ica ion p oblem
and explains he scena ios in Table 1and p e ious esea ch in de ail. Sec ion 3p esen s he
sea ch algo i hm, including he ules we use, sea ch space educ ion echniques, heu is ics
and heo e ical p ope ies. Sec ion 4shows how he sea ch can be ex ended o p oblems
ha in ol e missing da a. Sec ion 5demons a es how he sea ch can be used in R ia
he dosea ch package. E icacy o he sea ch is assessed ia simula ions. Sec ion 6shows
a numbe o new p oblems o which we can ind solu ions by using he sea ch including a
eal-wo ld applica ion. These p oblems include combined anspo abili y and selec ion bias,
mul iple sou ces o selec ion bias, and causal e ec iden i ica ion om a bi a y (expe imen al)
dis ibu ions. This sec ion also includes a sys ema ic analysis o missing da a p oblems and
case-con ol designs. Sec ion 7discusses he me i s and limi a ions o he app oach. Sec ion 8
o e s concluding ema ks.
2. The gene al causal e ec iden i ica ion p oblem
Ou p esen a ion is based on s uc u al causal models (SCM) and he language o di ec ed
g aphs. We assume he eade o be amilia wi h hese concep s and e e hem o de ailed
wo ks on hese opics o ex ended discussion and desc ip ions, such as (Pea l 2009) and
(Kolle and F iedman 2009).
Following he s anda d se -up o do-calculus (Pea l 1995), we assume ha he causal s uc-
u e can be ep esen ed by a semi-Ma ko ian causal g aph Go e a se o e ices V(see
Figu e 2(a) o example). The di ec ed edges co espond o di ec causal ela ions be ween
he a iables ( ela i e o V); di ec ed edges do no o m any cycles. Con ounding o any
wo obse ed a iables in Vby some unobse ed common cause is ep esen ed by a bidi-
ec ed edge be ween he a iables. This g aphical ep esen a ion allows us o deal wi h any
causal s uc u es whe e some a iables a e unmeasu ed. We assume a posi i e dis ibu ion
o e he a iables (Huang and Val o a 2006a) ensu ing ha all conside ed causal e ec s and
condi ional dis ibu ions a e well-de ined.
In a non-pa ame ic se ing, he p oblem o exp essing a causal quan i y o in e es in e ms
o a ailable in o ma ion has been desc ibed in a ious ways depending on he con ex . When
a ailable da a a e a ec ed by selec ion bias o missing da a, a ypical goal is o “ eco e ”
a join o ma ginal dis ibu ion. I da a a e a ailable om mul iple concep ual domains, a
dis ibu ion is “ anspo ed” om he sou ce domains, om which a combina ion o bo h
obse a ional and expe imen al da a a e a ailable, o a a ge domain. The a o emen ioned
se ings can be exp essed in he SCM amewo k by equipping he g aph o he model wi h
special e ices. Howe e , on a undamen al le el hese p oblems a e simply a ia ions o he
o iginal iden i iabili y p oblem o causal e ec s and as such, ou goal is o ep esen hem as
a single gene alized iden i iabili y p oblem. Fo mally, iden i iabili y can be de ined as ollows
(Pea l 2009;Shpi se and Pea l 2008).
De ini ion 1 (Iden i iabili y).Le Mbe a se o models wi h a desc ip ion Tand wo objec s
φand θcompu able om each model. Then φis iden i iable om θin Ti φis uniquely
compu able om θin any model M∈M. In o he wo ds, all models in Mwhich ag ee on θ
also ag ee on φ.
In he simples case, he desc ip ion T e e s o he g aph induced by causal model, θis
he join dis ibu ion o he obse ed a iables P(V)and he que y φis a causal e ec
6Causal E ec Iden i ica ion om Mul iple Incomple e Da a Sou ces
P(Y|do(X)). On he o he hand, p o ing non-iden i iabili y o φ om θcan be ob ained by
desc ibing wo models M1, M2∈Msuch ha θis he same in M1and M2, bu objec φin
M1is di e en om φin M2.
The gene al o m o a causal iden i iabili y p oblem ha we conside in his pape is o mu-
la ed as ollows.
Inpu : A se o inpu dis ibu ions o he o m P(Ai|do(Bi),Ci), a que y P(Y|do(X),Z)
and a semi-Ma ko ian causal g aph Go e V.
Task: Ou pu a o mula o he que y P(Y|do(X),Z)o e he inpu dis ibu ions, o decide
ha i is no iden i iable.
He e Ai,Bi,Cia e disjoin subse s o V o all i, and X,Y,Za e disjoin subse s o V. The
causal g aph Gmay con ain e ices which desc ibe mechanisms ela ed o anspo abili y
and selec ion bias. In he ollowing sec ions we explain se e al impo an special cases o his
p oblem de ini ion, some ha ha e been conside ed in he li e a u e and some which ha e
no been.
2.1. P e iously conside ed scena ios as special cases
We es a e he concep s o anspo abili y and selec ion bias unde he causal in e ence
amewo k, and show ha iden i iabili y in he scena ios o Rows 1–7 o Table 1 alls unde
he gene al o m on Row 8. We e u n o p oblems ha in ol e missing da a on Rows 9–11
la e in Sec ion 4.
Causal e ec iden i iabili y
Inpu is es ic ed o a passi e obse a ional dis ibu ion P(V). The a ge is ei he a causal
e ec P(Y|do(X)) o Row 1 o Table 1o a condi ional causal e ec P(Y|do(X),Z) o
Row 2 o Table 1(Shpi se and Pea l 2006b,a).
z-iden i iabili y
Simila ly o o dina y causal e ec iden i ica ion, he inpu consis s o he passi e obse a ional
dis ibu ion P(V)bu also o expe imen al dis ibu ions known as su oga e expe imen s
in e ening on a se B(Ba einboim and Pea l 2012a). Two es ic ing assump ions, which we
call nes ed expe imen s and en i e dis ibu ions, apply o su oga e expe imen s. Expe imen s
a e called nes ed expe imen s (NE) when o each expe imen in e ening a se o a iables B,
expe imen s in e ening on all subse s o Ba e a ailable as well. En i e dis ibu ions (ED)
deno e he assump ion ha he union o obse ed and in e ened a iables is always he se
o all a iables V.
g-iden i iabili y
Unlike z-iden i iabili y, he inpu does no con ain he passi e obse a ional dis ibu ion P(V)
bu consis s ins ead o su oga e expe imen s on he se s {Bi}(Lee e al. 2019) wi hou he
assump ion o nes ed expe imen s. The assump ion o en i e dis ibu ions holds.
Jou nal o S a is ical So wa e 7
Su oga e ou come iden i iabili y
Su oga e ou comes gene alize he no ion o su oga e expe imen s om z-iden i iabili y. Fo
su oga e ou comes, he assump ion o nes ed expe imen s s ill holds, bu he assump ion o
en i e dis ibu ions can be d opped. Some less s ic assump ions (SO) s ill apply (Tikka and
Ka anen 2019). The idea o su oga e ou comes is ha da a om p e ious expe imen s a e
a ailable, bu he a ge Ywas a mos only pa ially measu ed in hese expe imen s and he
expe imen s do no ha e o be disjoin om X.
T anspo abili y
The p oblem o inco po a ing da a om mul iple causal domains is known as anspo abili y
(Ba einboim and Pea l 2013). Fo mally, he goal is o iden i y a que y in a a ge domain
π∗using da a om sou ce domains π1, . . . , πn. The domains a e ep esen ed in he causal
g aph using a special se o anspo abili y nodes Twhich is pa i ioned in o disjoin subse s
T1,...,Tnco esponding o each domain πi. The causal g aph con ains an ex a edge Tij →
Vjwhene e a unc ional disc epancy in Vjo in P(uVj)exis s be ween he a ge domain
π∗and he sou ce domain πi. The disc epancy is ac i e i Tij = 1 and inac i e o he wise. A
dis ibu ion associa ed wi h a domain πiis o he o m P(A|do(B),C,Ti= 1,T−i= 0),
whe e T−ideno es he o he subse s o he pa i ion o Texcep Ti. In o he wo ds, only he
disc epancies be ween he πiand π∗a e ac i e. A dis ibu ion co esponding o he a ge
domain has no ac i e disc epancies meaning ha i is o he o m P(A|do(B),C,T= 0).
Any a iable is condi ionally independen om inac i e anspo abili y nodes since hei
espec i e edges anish. Fu he mo e, since anspo abili y nodes se o 0 anish, we can
assume any p esen anspo abili y node o ha e he alue 1. Thus an inpu dis ibu ion om
a domain πi akes he o m P(A|do(B),C,Ti). In he speci ic case o mz- anspo abili y,
he assump ions o en i e dis ibu ions (ED) and nes ed expe imen s in di e en domains
(NEDD) apply, which means ha P(V (B0
i∪Ti)|do(B0
i),Ti)is a ailable o e e y subse
B0
io Biin each domain πi.
Selec ion bias eco e abili y
Selec ion bias can be seen as a special case o missing da a, whe e he mechanism esponsible
o he p e e en ial selec ion is ep esen ed in he causal g aph by a special sink e ex S
(Ba einboim and Pea l 2012b). Typical inpu o he eco e abili y p oblem is P(V|S= 1),
he join dis ibu ion obse ed unde selec ion bias. Jus as in he case o anspo abili y
nodes, selec ion bias nodes only appea when he mechanism has been enabled. Thus we may
assume ha he inpu is o o m P(V|S). Mo e gene ally, we can conside inpu dis ibu ions
o he o m P(A|do(B),C, S).
2.2. New scena ios as special cases
The ollowing se ings a e special cases o he gene al iden i iabili y p oblem o Row 8 in
Table 1 ha do no all unde any o he p oblems o Rows 1–7. They se e as in e es ing
addi ions o he cases conside ed in he li e a u e. Conc e e examples on hese new scena ios
a e p esen ed in Sec ion 6. Sec ion 4ex ends he gene al p oblem o Row 8 in Table 1 o
he gene al p oblem wi h missing da a on Row 11 while also showcasing he special cases o
Rows 9 and 10.
8Causal E ec Iden i ica ion om Mul iple Incomple e Da a Sou ces
Mul iple da a sou ces wi h pa ially o e lapping a iable se s
The scena io whe e only subse s o a iables a e e e obse ed oge he has been ex ensi ely
conside ed in he causal disco e y li e a u e (Danks, Glymou , and Tillman 2009;Tillman
and Spi es 2011;T ian a illou, Tsama dinos, and Tollis 2010), bu no in he con ex o causal
e ec iden i ica ion. In he basic se ing he inpu consis s o passi ely obse ed dis ibu ions
P(Ai)such ha Ai⊂V. We may also obse e expe imen al dis ibu ions P(Ai|do(Bi))
(Hy inen, Ebe ha d , and Hoye 2012;T ian a illou and Tsama dinos 2015) o e en condi-
ionals P(Ai|do(Bi),Ci). Ou app oach se s no limi a ions o he numbe o ypes o inpu
dis ibu ions.
Combining anspo abili y and selec ion bias
To he bes o ou knowledge, he amewo ks o anspo abili y and selec ion bias ha e
no been conside ed simul aneously. The combina ion o hese scena ios i s in o he gen-
e al p oblem o mula ion. Fo example, we may ha e access o wo obse a ional dis ibu-
ions o igina ing om di e en sou ce domains, bu a ec ed by he same biasing mechanism:
P(A1|C1, T1, S)and P(A2|C2, T2, S), whe e T1and T2a e he anspo abili y nodes
co esponding o he wo sou ce domains and Sis he selec ion bias node.
Reco e ing om mul iple sou ces o selec ion bias
In ecen li e a u e on selec ion bias as a causal in e ence p oblem, he ocus has been on
se ings whe e only a single selec ion bias node is p esen (e.g., Ba einboim, Tian, and Pea l
2014;Co ea and Ba einboim 2017;Co ea e al. 2018). Howe e , mul iple sou ces o selec ion
bias a e ypical in longi udinal s udies whe e d opou occu s a di e en s ages o he s udy.
Ou app oach is applicable o an a bi a y numbe o selec ion bias mechanisms and inpu
dis ibu ions a ec ed by a bi a y combina ions o hese mechanisms. In o he wo ds, i
Sis he se o all selec ion bias nodes p esen in he g aph, he inpu s can ake he o m
P(A|do(B),C,S0), whe e S0is an a bi a y subse o S.
3. A sea ch-based app oach o causal e ec iden i ica ion
The key o iden i ica ion o causal e ec s is ha in e en ional exp essions can be manip-
ula ed using he ules o do-calculus. We p esen hese ules o augmen ed g aphs whe e
an addi ional in e en ion a iable IXsuch ha IX→Xis added o he induced g aph o
each a iable X(Spi es e al. 1993;Pea l 2009;Lau i zen 2000) (see Figu e 2(b)). Now a d-
sepa a ion condi ion (o m-sepa a ion (Richa dson 2003)) o he o m Y⊥⊥ IZ|X,Z,W|| X
means ha nodes Yand in e en ion nodes IZo Za e d-sepa a ed gi en X,Zand Win a
g aph whe e edges incoming o (in e ened) Xha e been emo ed (Hy inen, Ebe ha d , and
Jä isalo 2015;Dawid 2002). The h ee ules o do-calculus (Pea l 1995) can be exp essed as
ollows:
P(Y|do(X),Z,W) = P(Y|do(X),W),i Y⊥⊥ Z|X,W|| X
P(Y|do(X,Z),W) = P(Y|do(X),Z,W),i Y⊥⊥ IZ|X,Z,W|| X
P(Y|do(X,Z),W) = P(Y|do(X),W),i Y⊥⊥ IZ|X,W|| X
(1)
The ules a e o en e e ed o as inse ion/dele ion o obse a ions, exchange o ac ions
and obse a ions, and inse ion/dele ion o ac ions espec i ely. Each ule o do-calculus is
Jou nal o S a is ical So wa e 15
Algo i hm 2 do-sea ch
Inpu : Ta ge Q=P(Y|do(X),W), a semi-Ma ko ian g aph Gand a se o known dis i-
bu ions P={P1, . . . , Pn}.
Ou pu : A o mula F o Qin e ms o Po NA
1: i Q∈P, e u n Q
2: i a ge is non-iden i iable by Theo em 1, hen e u n NA
3: le Ube he se o unexpanded dis ibu ions, ini ially U:= P
4: while U6=∅,do
5: le P0be he unexpanded dis ibu ion closes o he a ge : P0= a gmax
Pi∈U
h(Q, Pi)
6: le Mbe he se o ules o Table 2, wi hou Rules 1±, such ha he e mina ion
condi ions o Table 3do no hold wi h espec o P0.
7: le P∗be he se o all dis ibu ions de i ed om P0using he ules in M
8: o each new candida e dis ibu ion P∗∈P∗,do
9: i P∗is al eady in P, hen con inue
10: i he alidi y condi ions o Table 3a e no sa is ied by P∗, hen con inue
11: i an addi ional inpu is equi ed ha is no in P, hen con inue
12: i Rule 2±o 3±o Table 2is applied and he co esponding d-sepa a ion C i e ion 1
is no sa is ied by G, hen con inue
13: i P∗=Q, hen
14: De i e a o mula F o Qby back acking.
15: e u n F
16: Add P∗ o P, add P∗ o U
17: Ma k P0as expanded: emo e P0 om U
18: e u n NA
The i e a ion o e he unexpanded dis ibu ions Up oceeds as ollows (Lines 4–5). Each
inpu dis ibu ion and e ms de i ed om i a e assigned in o a p io i y queue, whe e he
p io i y is de e mined by he alue gi en by he p oximi y unc ion h. Dis ibu ions closes
o he a ge a e expanded i s . In he implemen a ion, only he ac ual memo y add esses o
he dis ibu ion objec s a e placed in o he queue. The se Pis implemen ed as a hash able
ha se es as a con aine o all inpu dis ibu ions and hose de i ed om hem. Each new
dis ibu ion is assigned a unique index ha also se es as he hash unc ion o his able.
The dis ibu ion objec s con ained in he able a e ep esen ed uniquely by h ee in ege s
co esponding o he se s A,Band Co he gene al o m P(A|do(B),C). A dis ibu ion
objec also con ains addi ional auxilia y in o ma ion such as which ule was used o de i e i ,
whe he i is expanded o no and om which dis ibu ion i was ob ained. This in o ma ion
is used o cons uc he de i a ion i he a ge is ound o be iden i iable.
Mul iple dis ibu ions can sha e he same alue o he p oximi y unc ion h. In he case
ha mul iple candida es sha e he maximal alue, he one ha was de i ed he ea lies akes
p ecedence. When he unexpanded dis ibu ion cu en ly closes o he a ge is de e mined,
he ules o Table 2a e applied sequen ially o all alid subse s dic a ed by Table 3. When
ules wo and h ee o do-calculus a e conside ed, he necessa y d-sepa a ion c i e ia is checked
om G(Line 12). Fo he chain ule, he p esence o he equi ed second inpu is also e i ied.
The e e se lookup is implemen ed by using ano he hash able, whe e he hash unc ion is
based on he unique ep esen a ion o each dis ibu ion objec . The alues con ained in he

16 Causal E ec Iden i ica ion om Mul iple Incomple e Da a Sou ces
able a e he indices o he de i ed dis ibu ions. The same hash able is also used o ensu e
ha we do no a emp o de i e dis ibu ions again ha ha e been p e iously ound o be
iden i iable om he inpu s.
We cons uc a se Mo applicable ules o each unexpanded dis ibu ion P0using he
e mina ion condi ions o Table 3(Line 6). I all he necessa y condi ions ha e been ound
o hold o an applicable ule and a subse , he newly de i ed dis ibu ion P∗is added o he
se o known dis ibu ions and placed in o he p io i y queue as an unexpanded dis ibu ion.
When he applicable ules and subse s ha e been exhaus ed o he cu en dis ibu ion P0, he
e m is ma ked as expanded and emo ed om he queue (Line 17). I he a ge dis ibu ion
is ound a any poin (Line 13), a o mula is e u ned o i in e ms o he o iginal inpu s.
Al e na i ely, we can also con inue de i ing dis ibu ions o ob ain di e en sea ch pa hs o
he a ge ha can possibly p oduce di e en o mulas o i . I ins ead we exhaus he se
o unexpanded dis ibu ions by emp ying he queue, he a ge is deemed non-iden i iable by
he sea ch (Line 18).
We keep ack o he ules ha we e used o de i e each new dis ibu ion in he sea ch. This
allows us o cons uc a di ec ed g aph o he de i a ion whe e each oo node is a membe
o he o iginal inpu se Pand hei descendan s a e he dis ibu ions de i ed om hem
du ing he sea ch. Each edge ep esen s a manipula ion o he pa en node(s) o ob ain he
child node. Fo an iden i iable a ge quan i y, he o mula Fis ob ained by back acking he
chain o manipula ions ecu si ely un il he oo s a e eached (Line 14). The de i a ion o
he example in he beginning o Sec ion 3depic ed in Figu e 2(c) can be e icien ly ound by
applying his p ocedu e.
We assess he wo s case complexi y o do-sea ch in e ms o he inpu g aph size, which is
he p ima y de e mining ac o o he sea ch ime. Checks o sepa a ion and e mina ion
and alida ion condi ions all un in polynomial ime wi h espec o he numbe o e ices,
bu he numbe o dis ibu ions g ows e y apidly. In a hypo he ical absolu e wo s case
scena io, he a ge is no iden i iable, bu e e y o he dis ibu ion is. Supposing a g aph wi h
d e ices, we can de e mine how many dis ibu ions would ha e o be de i ed by he sea ch
in o de o exhaus he sea ch space. Fo a dis ibu ion o he o m P(A|do(B),C), any
a iable in Vcan ei he belong o he se s A,Bo Co no be p esen in he dis ibu ion,
meaning ha he e a e 4dways o ca ego ize e e y a iable. Howe e , we mus accoun o
he ac ha he e mus always be a leas one a iable in he se A. The e a e 3dways
o assign all he a iables in such a way ha no a iable is a membe o se A. Thus he
o al numbe o dis ibu ions conside ed by do-sea ch g ows as O(4d). See he simula ions o
Sec ion 5.1 o unning ime pe o mance in mo e ealis ic se ings.
3.4. Soundness and comple eness p ope ies
We a e eady o es ablish some key heo e ical p ope ies o do-sea ch. The i s heo em
conside s he co ec ness o he sea ch.
Theo em 2 (Soundness).do-sea ch always e mina es: i i e u ns an exp ession o he
a ge Q, i is co ec , i i e u ns NA hen Qis no iden i iable wi h espec o he ules o
do-calculus and s anda d p obabili y manipula ions (in Table 2).
P oo . Each new dis ibu ion is de i ed by using only well-de ined manipula ions as ou lined
by Table 3and by ensu ing ha he equi ed sepa a ion c i e ia hold in Gwhen ules o do-
Jou nal o S a is ical So wa e 17
calculus a e conce ned. I ollows ha i he sea ch e mina es and e u ns a o mula o he
a ge dis ibu ion, i was eached om he se inpu dis ibu ions h ough a sequence o alid
manipula ions. I do-sea ch e mina es as a esul o Theo em 1, we a e done. Suppose now
ha Theo em 1does no apply. By de ini ion, do-sea ch enume a es e e y ule o Table 2 o
e e y well-de ined subse o Table 3. By Lemma 1, no dis ibu ions a e le ou by applying
he e mina ion c i e ia o Table 3. We know ha i Rules 1±o Table 3a e omi ed, he
dis ibu ions gene a ed by hese ules can be ob ained by a combina ion o Rules 2±and 3±.
Fu he mo e, he o de in which he dis ibu ions a e expanded does no ma e , as e e y
possible manipula ion is ca ied ou none heless. The sea ch will e en ually e mina e, since
dis ibu ions ha ha e al eady been de i ed a e no added again o he se o unexpanded
dis ibu ions and he e a e only ini ely many ways o apply he ules o Table 2.
The ollowing heo em p o ides a comple eness esul in connec ion o exis ing iden i iabili y
esul s. Since do-calculus has been shown o be comple e wi h espec o (condi ional) causal
e ec iden i iabili y, z-iden i iabili y, g-iden i iabili y and anspo abili y, i ollows ha do-
sea ch is comple e o hese p oblems as well.
Theo em 3 (Comple eness).I do-sea ch e u ns NA in he se ings in Rows 1–4 and 6 in
Table 1, hen he que y is non-iden i iable.
P oo . Do-calculus has been shown o be comple e in hese se ings. The ules o p obabili y
calculus encode wha is used in he algo i hms as can be seen o example om he p oo s o
Theo em 7 and Lemmas 4–8 o Shpi se and Pea l (2006b).
I is no known whe he he ules implemen ed in do-sea ch a e su icien o o he mo e
gene al iden i iabili y p oblems since i is concei able ha some addi ional ules migh exis
ha would be equi ed o achie e comple eness. One such gene aliza ion is he inclusion o
missing da a in he causal model, which we p esen in Sec ion 4. Howe e , i one we e o
show ha do-calculus (o any o he se o ules included in do-sea ch) is comple e o some
special case o he gene alized iden i iabili y p oblem, hen do-sea ch would be comple e o
his p oblem as well. In he ollowing sec ions we will use he e m “iden i iable by do-sea ch”
o e e o causal que ies ha can be iden i ied by do-sea ch.
4. Ex ension o missing da a p oblems
The SCM amewo k can be ex ended o desc ibe missing da a mechanisms. Fo each a iable
Vi, wo special e ices a e added o he causal g aph. The e ex V∗
iis he obse ed p oxy
a iable which is linked o he ue a iable Vi ia he missingness mechanism (Li le and
Rubin 1986;Mohan e al. 2013):
V∗
i=(Vi,i RVi= 1,
NA,i RVi= 0,(2)
whe e NA deno es a missing alue and RViis called he esponse indica o (o Vi). In o he
wo ds, he a iable V∗
i ha is ac ually obse ed ma ches he ue alue Vii i is no missing
(RVi= 1). We no e ha in his o mula ion, each ue a iable has i s own esponse indica o ,
meaning ha we do no conside sha ed indica o s be ween a iables o mul iple indica o s
18 Causal E ec Iden i ica ion om Mul iple Incomple e Da a Sou ces
o a single a iable. Figu e 11 in Sec ion 6.4 depic s some examples o g aphs con aining
missing da a mechanisms. Fu he mo e, i he e is no missingness associa ed wi h a gi en
a iable Vimeaning ha i is ully obse ed, he co esponding esponse indica o RVialways
has he alue 1. The omission o a p oxy a iable and a esponse indica o s o a speci ic
a iable om a g aph encodes he assump ion ha he a iable in ques ion i ully obse ed.
No e ha in e en ion nodes a e added o ue a iables and esponse indica o s bu no o
p oxy a iables. On a symbolic le el one could in e ene on p oxy a iables, howe e we a e
only in e es ed in in e en ions ha keep Equa ion 2in ac .
The obse ed e ices o he causal diag am can be pa i ioned in o h ee ca ego ies
V=V ∪V∗∪V ,
whe e V is he se o ue a iables, V∗is he se o p oxy a iables and V is he se o
esponse indica o s. Fo any subse Z⊂Vwe de ine he same pa i ion ia Z =Z∩V ,
Z∗=Z∩V∗and Z =Z∩V .
The de ini ion o he esponse indica o connec s a p oxy a iable and a ue a iable. Typi-
cally his connec ion is only o in e es o hose a iables Vi ha ha e missing da a, meaning
ha P(RVi= 1) <1. Fu he mo e, we o en u ilize a p oxy a iable co esponding o a spe-
ci ic ue a iable and con e sely, a ue a iable co esponding o a speci ic p oxy a iable.
We de ine his co espondence explici ly in he ollowing way
Z( →∗)={V∗
i∈V∗|Vi∈Z , P (RVi= 1) <1},
Z(∗→ )={Vi∈V |V∗
i∈Z∗, P (RVi= 1) <1}.
Simila ly, gi en a se Zwe o en equi e he se o he esponse indica o s ha de ine he
missingness mechanism o he ue a iables ha a e membe o Z. This se is de ined as
ollows
RZ={RVi∈V |Vi∈Z , P (RVi= 1) <1}.
I is impo an o no e he di e ence be ween he se s Z and RZ; he i s se deno es he
se o esponse indica o s ha a e membe s o Zwhile he second gi es he co esponding
esponse indica o s o he ue a iables ha a e membe o Z.
Ou me hod is also capable o p ocessing que ies when he causal g aph con ains missing da a
mechanisms whe e he se s Ai,Biand Cio some o he inpu dis ibu ions may be es ic ed
o con ain obse ed a iables in V∗∪V . An ac i e esponse indica o RVi= 1 is deno ed
by R1
Vi. Simila ly, o se s o esponse indica o s R1
Zdeno es ha all indica o s in he se a e
ac i e. P oxy a iables a e no explici ly shown in g aphs o cla i y.
De e mining iden i iabili y is challenging unde missing da a. As e idence o his, e en some
non-in e en ional que ies equi e he applica ion o do-calculus (Mohan and Pea l 2018).
Fu he mo e, he ules used in he sea ch o Table 2a e no longe su icien and de i ing
he desi ed quan i y necessi a es he use o addi ional ules ha s em om he de ini ion o
he p oxy a iables and he esponse indica o . Each new ue a iable also has a highe
impac on compu a ional complexi y, since he co esponding esponse indica o and p oxy
a iable a e always added o he g aph as well. Table 4ex ends he se o ules o Table 2
o missing da a p oblems by p o iding manipula ions ela ed o he missingness mechanism.
Rules 7±and 8±pe o m condi ioning using he chain ule. These ules a e necessa y in he
case ha se Ycon ains missing da a mechanisms ha ha e been enabled and hus canno
be ma ginalized o e by using Rule 5.
Jou nal o S a is ical So wa e 19
Rule Addi ional Inpu Ou pu Desc ip ion
1+ P(Y|do(X),Z,W)Inse ion o obse a ions
1−P(Y|do(X),W Z)Dele ion o obse a ions
2+ P(Y|do(X,Z),W Z)Obs. o ac ion exchange
2−P(Y|do(X Z),Z,W)Ac ion o obs. exchange
3+ P(Y|do(X,Z),W)Inse ion o ac ions
3−P(Y|do(X Z),W)Dele ion o ac ions
4P(Y Z|do(X),W)Ma ginaliza ion
5P(Y Z|do(X),Z,W)Condi ioning
6+ P(Z|do(X),W Z)P(Y,Z|do(X),W Z)Chain ule mul iplica ion
6−P(Z|do(X),Y,W)P(Y,Z|do(X),W)Chain ule mul iplica ion
7+ P(Z|do(X),W)P(Y Z|do(X),Z,W)Chain ule condi ioning (nume a o )
7−P(Z|do(X),W,Y Z)P(Y Z|do(X),W)Chain ule condi ioning (nume a o )
8+ P(Y,Z|do(X),W)P(Z|do(X),W,Y)Chain ule condi ioning (denomina o )
8−P(Y,Z|do(X),W Z)P(Z|do(X),W)Chain ule condi ioning (denomina o )
9+ P(Y|do(X),W RZ,R1
Z)Enable esponse indica o s
9−P(Y RZ,R1
Z|do(X),W)Enable esponse indica o s
10+ P(Y|do(X),W Z∗,Z(∗→ ))P oxy a iable exchange
10−P(Y Z∗,Z(∗→ )|do(X),W)P oxy a iable exchange
Table 4: Ex ended se o ules o missing da a p oblems used o manipula e inpu dis ibu-
ions o he o m P(Y|do(X),W). Rules 1±,2±,3±,4,5and 6±a e he same as in Table 2.
Fo Rules 7±and 8±, he addi ional inpu has also been iden i ied. The se s Y,Xand Wa e
disjoin . Se s Yand Wmay con ain ue a iables, p oxy a iables and esponse indica o s.
Se Xmay only con ain ue a iables and esponse indica o s. The oles o he se s Zand
RZdepend on he ule being applied (see Table 5).
Rules 9±a e used o enable esponse indica o s, which hen acili a es he use o Rules 10±.
These las wo ules exchange p oxy a iables o hei ue coun e pa s when he co espond-
ing esponse indica o s a e enabled. Fo example, unde he condi ions speci ied in Table 5,
Rule 9+ can be applied on P(Y, X∗|RX) o i s ob ain P(Y, X∗|R1
X)by enabling RX.
Then, Rule 10+ can applied o his dis ibu ion o ob ain P(Y, X |R1
X)by exchanging X∗
o X.
Simila ly o Table 3, Table 5ou lines he alid subse s Z o applying he ex ended ules o
Table 4. A majo di e ence o he o iginal alidi y and e mina ion condi ions is he addi ion
o he missing da a condi ion ha ou lines he addi ional equi emen s ha mus be sa is ied
when missingness mechanisms a e p esen . Fo he ules ha a e sha ed by Tables 2and 4, he
missing da a condi ion ensu es ha a ue a iable and i s p oxy coun e pa ne e appea in
he same e m a he same ime. Fo example, we canno add an in e en ion on X o P(X∗).
I also ensu es ha we do no ca y ou summa ion o e enabled esponse indica o s in he
case o ules 4 and 5. When applying Rules 9±, he condi ion also ensu es ha we do no
a emp o enable a esponse indica o ha is al eady enabled. Fo Rules 10±, he condi ions
gua an ee ha a p oxy can only be exchanged o i s ue coun e pa i i s co esponding
esponse indica o is enabled and p esen in he inpu e m.
Addi ional e mina ion condi ions also apply o he new ules and hei co ec ness is easily
e i ied.
Lemma 2. Le Gbe a semi-Ma ko ian g aph and le Y,Xand Wbe disjoin subse s o V.
Then all o he ollowing a e ue:
20 Causal E ec Iden i ica ion om Mul iple Incomple e Da a Sou ces
Rule Validi y cond. Missing da a condi ion Te m. cond.
1+ Z∩T=∅Z∩T(∗→ )∪T( →∗)∪Z(∗→ )∪Z( →∗)=∅
1−Z⊆W W =∅
2+ Z⊆W Z ∩W∗=∅W=∅
2−Z⊆X X =∅
3+ Z∩T=∅Z∩T(∗→ )∪T( →∗)∪Z(∗→ )∪Z( →∗)=∅
3−Z⊆X X =∅
4Z⊂Y Z ∩(Ra∩Y) = ∅ |Y|= 1
5Z⊂Y(Y Z)∩(Ra∩Y) = ∅ |Y|= 1
6+ Z⊆W W =∅
6−Z∩T=∅Z∩T(∗→ )∪T( →∗)∪Z(∗→ )∪Z( →∗)=∅
7+ Z⊂Y|Y|= 1
7−Z⊂Y|Y|= 1
8+ Z∩T=∅
8−Z⊆W W =∅
9+ RZ⊆W ,RZ∩Ra=∅W =∅
9−RZ⊆Y ,RZ∩Ra=∅Y =∅
10+ Z∗⊆W∗,RZ(∗→ )⊆Ra,RZ(∗→ )⊆W Ra=∅
10−Z∗⊆Y∗,RZ(∗→ )⊆Ra,(RZ(∗→ )⊆W o RZ(∗→ )⊆Y )Ra=∅
Table 5: The condi ions o he enume a ed subse Z o applying he ules o Table 4 o a
e m in he inpu column. He e T=Y∪X∪Wand he se s Y,Xand Wa e hose p esen
in he inpu e m P(Y|do(X),W). Ac i e esponse indica o s o he inpu a e deno ed by
Ra. Fo Rules 6±,7±and 8±, he condi ions speci y alid a iables o he second equi ed
e m. Validi y condi ions o Rules 1±,2±,3±,4,5and 6±a e he same as in Table 3.
(i) I |Y|= 1, hen Rules 7±o Table 4canno be used.
(ii) I W=∅, hen Rule 8−o Table 4canno be used.
(iii) I W =∅ hen Rule 9+ o Table 4canno be used.
(i ) I Y =∅ hen Rule 9−o Table 4canno be used.
( ) I Ra=∅, hen Rules 10±o Table 4canno be used.
P oo . Fo (i), he se Yonly has a single e ex, so i canno ha e a non-emp y subse . Fo
(ii), he se Wis emp y so no subse Z⊂Wcan exis o he second inpu . Fo (iii), and
he se W is emp y so no assignmen o alue 1can be pe o med. Simila ly o (i ), he se
Y is emp y so no assignmen o alue 1can be pe o med. Fo ( ) he se o ac i e esponse
indica o s Rais emp y, so no ans o ma ion om p oxy a iables o ue a iables ia he
missingness mechanism in Equa ion 2can ake place.
The ask o selec ing a sui able heu is ic becomes mo e di icul when missing da a a e in-
ol ed wi h he iden i iabili y p oblem. The heu is ic app oach o Sec ion 3.2 is no longe
di ec ly applicable due o he ela ion be ween p oxy a iables, esponse indica o s and ue
a iables. The p oximi y unc ion conside s Xand X∗as en i ely di e en a iables despi e
hei connec ion and does no p e e he inclusion o esponse indica o s. I he heu is ic is
applied as such, he sea ch pa h will o en in ol e a la ge numbe o manipula ions which
in u n leads o complica ed exp essions. Fo hese easons we do no apply a heu is ic o

Jou nal o S a is ical So wa e 21
missing da a p oblems, bu expand e ms in he o de in which hey we e iden i ied. The
imp o emen s desc ibed in Sec ion 3.2 s ill apply.
I is s aigh o wa d o adap do-sea ch o he new ex ended se o ules. In he pseudo-
code shown in Algo i hm 2, we simply eplace all e e ences o Tables 2and 3by e e ences o
Tables 4and Tables 5, espec i ely. When he alidi y condi ion is checked, we also e i y ha
he missing da a condi ion holds. Lemma 2gua an ees he co ec ness o he new e mina ion
c i e ia. Theo em 1is also alid when he se s Aia e eplaced by Ai∪A(∗→ )
i, since i may
be possible o exchange some p oxy a iable o a ue a iable ha is p esen in he se Yo
he a ge P(Y|do(X),W).
5. The dosea ch package
We implemen ed do-sea ch (Algo i hm 2) in C++ and cons uc ed an Rin e ace using he
Rcpp package (Eddelbue el and F ançois 2011). This in e ace is p o ided by he Rpackage
dosea ch. Calling he sea ch om Ris s aigh o wa d ia he p ima y unc ion ha ca ies
he name o package.
dosea ch(da a, que y, g aph,
anspo abili y, selec ion_bias, missing_da a,
con ol)
The equi ed inpu s o he unc ion a e da a,que y and g aph. Pa ame e da a is used o
encode he se Po known inpu dis ibu ions o Algo i hm 2as a cha ac e s ing, whe e each
dis ibu ion is sepa a ed by a new line. Fo example, i we ha e access o a se o dis ibu ions
P={P(W), P (Y|X), P (Z|do(X), W )}, we would w i e
R> da a <- "
+ P(W)
+ P(Y|X)
+ P(Z|do(X),W)
+ "
The do(·)-ope a o can ei he p ecede o succeed condi ioning a iables, bu i mus appea
only once in a gi en e m, meaning ha exp essions such as P(Y|do(A),B,do(C)) a e no
allowed, bu should ins ead be gi en as P(Y|B,do(A,C)) o P(Y|do(A,C),B). I a iable se s
a e desi ed, each membe o he se has o be included explici ly.
Pa ame e que y is used o desc ibe he a ge Qo Algo i hm 2as a cha ac e s ing, simila ly
as he da a. I we a e in e es ed in iden i ying P(Y|do(X), W )we would w i e
R> que y <- "P(Y|do(X),W)"
Ins ead o desc ibing dis ibu ions ia ex , i is also possible o use he ollowing s uc u e
ha encodes he ole o each a iable ia a nume ic ec o :
R> que y <- c(Y = 0, X = 1, W = 2)
Gi en a dis ibu ion o he o m P(A|do(B),C)and a a iable V, a alue 0 means ha
V∈A, alue 1 means ha V∈Band alue 2 means ha V∈C. This o ma can also be
used o inpu da a as a lis o nume ic ec o s:
22 Causal E ec Iden i ica ion om Mul iple Incomple e Da a Sou ces
R> da a <- lis (
+ c(W = 0),
+ c(Y = 0, X = 2),
+ c(Z=0,X=1,W=2)
+ )
Finally, g aph encodes he semi-Ma ko ian g aph Go he causal model as a cha ac e s ing
wi h each edge on i s own line. A di ec ed edge om X o Yis gi en as X -> Y and a
bidi ec ed edge be ween Xand Yis gi en as X <-> Y. In e en ion nodes should no be
gi en explici ly, since hey a e added au oma ically a e calling dosea ch. Fu he mo e,
only e ices wi h incoming o ou going edges should be included in g aph. A a iable wi h
no connec ed edges can s ill appea in he inpu dis ibu ions and is au oma ically added o
he g aph as well. As an example, we can encode he g aph o Figu e 2(a) wi h an added
bidi ec ed edge be ween Xand Yas ollows
R> g aph <- "
+ X -> Y
+ Z -> X
+ Z -> Y
+ X <-> Y
+ "
Al e na i ely, one may use ig aph g aphs (Csa di and Nepusz 2006) in he syn ax o he
causale ec package o DAGs c ea ed using he dagi y package.
R> lib a y("ig aph")
R> g aph <- g aph. o mula(X -+ Y, Z -+ X, Z -+ Y, X -+ Y, Y -+ X)
R> g aph <- se .edge.a ibu e(g aph, "desc ip ion", 4:5, "U")
R> lib a y("dagi y")
R> g aph <- dagi y("dag{X -> Y; Z -> X; Z -> Y; X <-> Y}")
The nex wo op ional pa ame e s o dosea ch, anspo abili y and selec ion_bias, a e
used o deno e hose e ices o G ha should be unde s ood as ei he anspo abili y nodes
o selec ion bias nodes, espec i ely. P o iding hese pa ame e s may inc ease sea ch pe o -
mance in ele an p oblems. Bo h o hese pa ame e s should be gi en as cha ac e s ings,
whe e indi idual a iables a e sepa a ed by a comma, o example anspo abili y =
"S,T". Pa ame e missing_da a, as he name sugges s, is used o de ine missingness mech-
anisms 2as a cha ac e s ing, whe e indi idual mechanisms a e sepa a ed by a comma. In
o de o desc ibe ha RXis he esponse indica o o Xwe would w i e R_X : X, which also
implici ly de ines ha X* is he p oxy a iable o X. P oxy a iables do no need o be man-
ually desc ibed in g aph as hey a e au oma ically cons uc ed based on he missing_da a
a gumen .
The lis con ol can be used o se a ious addi ional pa ame e s ha a e no di ec ly
ela ed o he iden i iabili y p oblem i sel , bu mo e so o he ou pu o he sea ch and o he
auxilia y de ails, such as benchma king and ob aining de i a ions such as Figu e 2(c). One
such con ol pa ame e de e mines whe he o use he sea ch heu is ic o no (heu is ic =
FALSE by de aul ). Documen a ion o he dosea ch package con ains de ailed in o ma ion on
he ull lis o con ol pa ame e s.
Jou nal o S a is ical So wa e 23
The e u n objec o dosea ch is a lis wi h h ee componen s by de aul . The i s componen ,
iden i iabili y, is a logical alue ha akes he alue TRUE when he a ge dis ibu ion
desc ibed by que y is iden i iable om he inpu s o da a. The second componen , o mula,
is a cha ac e s ing desc ibing he a ge dis ibu ion in e ms o he inpu s in L
A
T
EX syn ax
i he a ge is iden i iable. O he wise his componen is jus an emp y cha ac e s ing. The
hi d componen call con ains he a gumen s o he o iginal unc ion call.
5.1. Simula ions
He e we epo he esul s o a simula ion s udy o assess he unning ime pe o mance o do-
sea ch and he impac o he sea ch space educ ion echniques as well as he sea ch heu is ic
ou lined in Sec ion 3.2.
Ou syn he ic simula ion scena io consis ed o 1000 semi-Ma ko ian causal g aphs o 10 e -
ices ha we e gene a ed a andom by i s gene a ing a andom opological o de o he
e ices ollowed by a andom lowe iangula adjacency ma ices o bo h di ec ed and bidi-
ec ed edges. G aphs wi hou a di ec ed pa h om X o Ywe e disca ded. We sampled
sequen ially inpu dis ibu ions o he o m P(A|do(B),C)a andom by gene a ing dis-
join subse s such ha Ais always non-emp y. This was con inued un il he a ge quan i y
P(Y|do(X)) was ound o be iden i iable by he sea ch. Then o each g aph, we eco ded
he sea ch imes o he speci ic se o inpu s ha i s esul ed in he que y o be iden i ied
and o he las se such ha he a ge was non-iden i iable. In o he wo ds, each g aph gen-
e a es wo simula ion ins ances, one o an iden i iable que y and one o a non-iden i iable
que y. This se ing di ec ly co esponds o he se ing o pa ially o e lapping expe imen al
da a se s discussed in Sec ion 2.2 o which no o he algo i hmic solu ions exis .
To unde s and he impac o he sea ch heu is ic and he a ious imp o emen s, we compa e
ou di e en sea ch con igu a ions: he basic do-sea ch wi hou he sea ch heu is ic o im-
p o emen s1, one ha only uses he sea ch heu is ic, one ha only uses he imp o emen s o
Sec ion 3.2 and one ha uses hem bo h.
Figu e 4shows he sea ch imes o he con igu a ions compa ed o he basic con igu a ion
o iden i iable ins ances. Mos impo an ly, a as majo i y o ins ances (96%) a e sol ed
as e han he basic con igu a ion when bo h heu is ics and imp o emen s a e used. The
a e age sea ch ime wi h bo h heu is ics and imp o emen s enabled was 31.5seconds and
80.2seconds o he basic con igu a ion. The sea ch heu is ic p o ides he g ea es bene i
o hese ins ances as can be seen om Figu e 4(b). Using a heu is ic can some imes hinde
pe o mance by leading he sea ch as ay and by causing addi ional compu a ional s eps
h ough he e alua ion o he p oximi y unc ion. Fo example, he e is a small numbe
o ins ances whe e he sea ch is o e en imes slowe han he basic con igu a ion when
using a heu is ic. Fo una ely, he e a e se e al ins ances in he opposi e di ec ion, whe e
he heu is ic p o ides o e one hund ed old educ ion in sea ch ime. Cu iously, e en using
he imp o emen s some imes esul s in slowe sea ch imes. This is mos likely due o he
elimina ion o Rule 1 o do-calculus, since i may be he case ha he basic sea ch is able
o use his ule o each he a ge dis ibu ion as e . Mo e impo an ly, Figu e 4(c) shows
ha he imp o emen s clea ly bene i he sea ch. Fu he mo e, he bene i ends o inc ease
as he ins ances ge ha de .
1In his con igu a ion, e ms a e expanded in he o de hey we e iden i ied; he condi ions in Table 3a e
no checked.
24 Causal E ec Iden i ica ion om Mul iple Incomple e Da a Sou ces
0
100
200
300
400
500
0 100 200 300 400 500
Heu is ic & Imp o emen s (s)
Basic (s)
(a)
0
100
200
300
400
500
0 100 200 300 400 500
Heu is ic only (s)
Basic (s)
(b)
0
100
200
300
400
500
0 100 200 300 400 500
Imp o emen s only (s)
Basic (s)
(c)
Figu e 4: Sca e plo s o he sea ch imes om iden i iable ins ances unde di e en sea ch
con igu a ions compa ed o he basic do-sea ch wi hou a heu is ic o imp o emen s.
0
100
200
300
400
500
0 100 200 300 400 500
Heu is ic & Imp o emen s (s)
Basic (s)
(a)
0
100
200
300
400
500
0 100 200 300 400 500
Heu is ic only (s)
Basic (s)
(b)
0
100
200
300
400
500
0 100 200 300 400 500
Imp o emen s only (s)
Basic (s)
(c)
Figu e 5: Sca e plo s o he sea ch imes om non-iden i iable ins ances unde di e en
sea ch con igu a ions compa ed o he baseline con igu a ion.
Figu e 5shows he sea ch imes o he con igu a ions o non-iden i iable ins ances. Relying
only on a sea ch heu is ic p o ides no bene i he e, as expec ed. The imp o emen s o he
sea ch a e mos aluable o hese ins ances, and in his scena io e e y non-iden i iable in-
s ance was sol ed as e han baseline using he imp o emen s, and when applied wi h he
heu is ic only one non-iden i iable ins ance was slowe han baseline. The a e age sea ch
ime wi h bo h heu is ic and imp o emen s enabled was 134.6seconds and 182.5seconds o
he basic con igu a ion. The almos ze o second ins ances a e a esul o Theo em 1when
no sea ch has o be pe o med in o de o de e mine he ins ance o be non-iden i iable.
The bene i o he imp o emen s ends o inc ease as he ins ances ge ha de also o hese
ins ances.
Finally we examined he a e age un ime pe o mance o do-sea ch, wi h all imp o emen s
and heu is ics enabled. We eplica ed he p e iously desc ibed simula ion scena io wi h he
same numbe o ins ances (1000) o g aphs wi h up o 10 e ices. Figu e 6shows he
boxplo s o sea ch imes on a log-scale o g aphs o di e en size, including bo h iden i iable
and non-iden i iable ins ances. No e ha o e e y g aph size he e a e a numbe o easily
Jou nal o S a is ical So wa e 31
9
5
110
0
17
29
15
0
274
10 0 0 63
0
0
P(X)P(Y | do(X))
P(Y | X)P(Y)
(a) G aphs wi h a ow X→Y.
9
0
0
0
0
89
245
128
373
014 0 0
0
0
P(X)P(Y | do(X))
P(Y | X)P(Y)
(b) G aphs whe e he e is nei he X→Yno
Y→X.
Figu e 10: Venn diag ams indica ing he numbe o g aphs we e di e en dis ibu ions can
be iden i ied do-sea ch. The in e sec ion o P(X)and P(Y|X)shows he numbe o g aphs
we e P(X, Y )can be iden i ied. The o al numbe o possible g aphs is 3072 in bo h cases.
The que ies P(X, Y ),P(X),P(Y),P(Y|X)and P(Y|do(X)) we e e alua ed using do-
sea ch in hese 6144 g aphs wi h he inpu dis ibu ion P(X∗, Y ∗, RX, RY). The esul s
a e summa ized by Venn diag ams in Figu e 10. The esul s a e also a ailable as a da a
se bi a ia e_missingness in he Rpackage dosea ch. Using his da a se we a e able o
showcase examples on non-iden i iabili y and ind in e es ing special cases by di ec e alua ion
o all possible bi a ia e missingness g aphs. The i s example ela es non-iden i iabili y o
he o he numbe o edges p esen in he g aph.
Example 1. Le Kdeno e he numbe o edges in a bi a ia e missingness g aph ha does no
ha e edge Y→X. The join dis ibu ion P(X, Y )is no iden i iable by do-sea ch i K > 5,
ma ginal dis ibu ion P(X)is no iden i iable by do-sea ch i K > 9, ma ginal dis ibu ion
P(Y)and condi ional dis ibu ion P(Y|X)a e no iden i iable by do-sea ch i K > 8.
The nex example speci ies he g aph wi h he la ges numbe o edges whe e bo h he join
dis ibu ion o Xand Yand he causal e ec o Xon Ycan be iden i ied.
Example 2. The g aph in Figu e 11(a) is he only bi a ia e missingness g aph ha (i)
has edge X→Y, (ii) has i e edges, and (iii) allows o he iden i ica ion o P(X, Y )and
P(Y|do(X)) by do-sea ch.
The hi d example speci ies he g aph wi h he la ges numbe o edges whe e he ma ginal
dis ibu ions a e iden i iable while he join dis ibu ion and he causal e ec o Xon Ya e
non-iden i iable.
Example 3. The g aph in Figu e 11(b) is he only bi a ia e missingness g aph ha (i) has
i e edges, and (ii) allows o he iden i ica ion o P(X)and P(Y), and (iii) does no allow
o he iden i ica ion o P(X, Y )o P(Y|do(X)) by do-sea ch. No bi a ia e missingness
g aph ha has mo e han i e edges ul ills he condi ions (ii) and (iii).
Some in e es ing examples a e shown in Figu e 11. G aphs (a) and (b) a e he unique g aphs
ha ul ill he condi ions speci ied in Examples 2and 3, espec i ely. G aph (c) is he g aph

32 Causal E ec Iden i ica ion om Mul iple Incomple e Da a Sou ces
X Y
RXRY
(a)
X Y
RXRY
(b)
X Y
RXRY
(c)
X Y
RXRY
(d)
X Y
RXRY
(e)
X Y
RXRY
( )
Figu e 11: Missingness g aphs used as example cases. P oxy a iables a e omi ed o cla i y.
wi h he smalles numbe o edges whe e ma ginals P(X)and P(Y)can be iden i ied bu he
join dis ibu ion P(X, Y )o causal e ec P(Y|do(X)) canno be iden i ied by do-sea ch.
In G aph (d), P(X),P(Y),P(X, Y )and P(Y|do(X)) a e no iden i iable by do-sea ch bu
he condi ional dis ibu ion P(Y|X)can be iden i ied as ollows
P(Y|X) = P(Y|RY= 1)P(X|Y, RX= 1, RY= 1)
PY0P(Y0|RY= 1)P(X|Y0, RX= 1, RY= 1).(3)
In Equa ion 3, he nume a o esembles he join dis ibu ion P(X, Y |RX= 1, RY= 1) bu
is di e en because Yand RXa e no independen . The denomina o is he ma ginal o his
pseudo join dis ibu ion. In G aph (e), P(X),P(Y)and P(X, Y )a e no iden i iable by
do-sea ch bu P(Y|X)and P(Y|do(X)) a e iden i iable and can be bo h es ima ed wi h
Equa ion 3. In G aph ( ), P(X, Y ),P(X)and P(Y|do(X)) a e no iden i iable by do-sea ch
bu P(Y)and P(Y|X)can be iden i ied as ollows
P(Y) = X
RX,X∗
P(Y|X∗, RX, RY= 1)P(RX, X∗),(4)
P(Y|X) = P(Y|X, RX= 1, RY= 1)
In Equa ion 4, he summa ion also goes o e he cases whe e X∗=NA and he dis ibu ion
o Ymus be es ima ed also on he condi ion ha Xis no obse ed.
6.5. Causal in e ence unde case-con ol design
Case-con ol design (B eslow 1996) is commonly used in epidemiology o s udy isk ac o s o
a e diseases. In he basic se up, a ixed numbe o disease cases and a ixed numbe o con ols
a e selec ed o he isk ac o measu emen s. When he disease is a e, his design leads o
subs an ial sa ings in he sample size compa ed o simple andom sampling. Figu e 12(a)
shows he missingness g aph o a si ua ion whe e he inclusion o he s udy (indica o RY)
Jou nal o S a is ical So wa e 33
X Y
RY
RX
(a) Basic case-con ol design.
X Z Y
RY
RXRZ
(b) Case-con ol design o he on -doo si ua ion.
Figu e 12: Missingness g aph o he case-con ol examples.
depends on he disease endpoin Y. The isk ac o s Xa e measu ed o he subse RY= 1
bu occasionally he alues a e missing (indica o RX). I is immedia ely seen ha nei he he
causal e ec P(Y|do(X)) no condi ional dis ibu ion P(Y|X)can be iden i ied because
o he edge Y→RY. Howe e , i he p e alence o he disease in he popula ion, i.e., he
ma ginal dis ibu ion P(Y), is known, he causal e ec P(Y|do(X)) can be iden i ied. The
esul is p o ided by do-sea ch
P(Y|do(X)) = P(Y)P(X|Y, RY= 1, RX= 1)
PY0P(Y0)P(X|Y0, RY= 1, RX= 1).(5)
In ypical applica ions esponse Yis bina y bu in he non-pa ame ic o mula o Equa ion 5
esponse can be disc e e o con inuous. A mo e complica ed example is shown in Figu e 12(b)
whe e he causal e ec o isk ac o Xon disease endpoin Y ul ills he on -doo c i e ion
(Pea l 1995) wi h espec o media o Zand he da a a e collec ed om a case-con ol design
whe e he selec ion depends Yand he e is occasional i em non- esponse in Xand Z. We
obse e da a P(Y∗, X∗, Z∗, RY, RX, RZ)and know he ma ginal dis ibu ion P(Y) om o he
sou ces. Applying do-sea ch we ob ain he esul
P(Y|do(X)) =
X
Z"PY0P(Y0)P(X, Z |Y0, RX= 1, RY= 1, RZ= 1)
PZ0,Y 0P(Y0)P(X, Z0|Y0, RX= 1, RY= 1, RZ= 1) ×
X
X0
X
Y0,Z0
P(Y0)P(X0, Z0|Y0, RX= 1, RY= 1, RZ= 1) ×
P(Y)P(X0, Z |Y, RX= 1, RY= 1, RZ= 1)
PY0P(Y0)P(X0, Z |Y0, RX= 1, RY= 1, RZ= 1)!#.
(6)
Exp ession 6 ollows he gene al s uc u e o he on -doo adjus men
P(Y|do(X)) = X
Z
P(Z|X)X
X0
P(X0)P(Y|X0, Z),
34 Causal E ec Iden i ica ion om Mul iple Incomple e Da a Sou ces
whe e
P(Z|X) = PY0P(Y0)P(X, Z |Y0, RX= 1, RY= 1, RZ= 1)
PZ0,Y 0P(Y0)P(X, Z0|Y0, RX= 1, RY= 1, RZ= 1),
P(X) = X
Y0,Z0
P(Y0)P(X, Z0|Y0, RX= 1, RY= 1, RZ= 1),
P(Y|X, Z) = P(Y)P(X, Z |Y, RX= 1, RY= 1, RZ= 1)
PY0P(Y0)P(X, Z |Y0, RX= 1, RY= 1, RZ= 1).
No e ha P(X, Y, Z) = P(Y)P(X, Z |Y, RX= 1, RY= 1, RZ= 1). In (Ka anen 2015), a
simila example was s udied assuming ha X,Zand Ya e bina y bu in Exp ession 6 he e
a e no such es ic ions. This ac o iza ion can be ob ained in Ras ollows
R> da a <- "
+ p(x*,y*,z*, _x, _y, _z)
+ p(y)
+ "
R> g aph <- "
+ x -> z
+ z -> y
+ y -> _y
+ x <-> y
+ _y -> _x
+ _y -> _z
+ _y <-> _x
+ _y <-> _z
+ _z <-> _x
+ "
R> md <- " _x : x, _y : y, _z : z"
R> que y1 <- "p(z|x)"
R> que y2 <- "p(x)"
R> que y3 <- "p(y|x,z)"
R> dosea ch(da a, que y1, g aph, missing_da a = md)
ac{ sum_{y} le (p(y)p(x,z| _x = 1,y, _y = 1, _z = 1) igh )}
{ sum_{z} sum_{y} le (p(y)p(x,z| _x = 1,y, _y = 1, _z = 1) igh )}
R> dosea ch(da a, que y2, g aph, missing_da a = md)
sum_{y,z} le (p(y)p(x,z| _x = 1,y, _y = 1, _z = 1) igh )
R> dosea ch(da a, que y3, g aph, missing_da a = md)
ac{ le (p(y)p(x,z| _x = 1,y, _y = 1, _z = 1) igh )}
{ sum_{y} le (p(y)p(x,z| _x = 1,y, _y = 1, _z = 1) igh )}
Jou nal o S a is ical So wa e 35
7. Discussion
The p esen ed algo i hm, do-sea ch, emo es he need o manual applica ion o do-calculus,
which is ime-consuming and p one o e o s. Sys ema ic analyses such as he one in Sec-
ion 6.4 a e p ac ically un eachable wi h manual applica ion o do-calculus. Supe io i y o
do-sea ch o e a simple o wa ds b ead h- i s sea ch was a ained h ough a combina ion o a
sea ch heu is ic and a educ ion o he sea ch space. Some u he app oaches we e a emp ed
bu la e disca ded as non-bene icial. These include caching sepa a ion c i e ia ha hold in
he g aph a e hey a e i s e alua ed, p e-compu ing alid subse s o each subse size and
enume a ing subse s in an o de o inc easing ca dinali y.
As he simula ions showed, ou in ui i e heu is ic yielded signi ican imp o emen s in sea ch
pe o mance. The p oximi y unc ion de ined in Sec ion 3.2 uses only he in o ma ion con-
ained in he dis ibu ions hemsel es. One app oach could be o also ake he s uc u e
o he g aph in o accoun in he p oximi y unc ion. Fu he s udy is needed o inding a
heu is ic ha pe o ms well when missing da a mechanisms a e p esen in he g aph.
The scalabili y o do-sea ch is limi ed due o as sea ch space o possibly iden i ied causal
e ec s. Cu en ly, algo i hms wi h polynomial complexi y cu en ly exis only o he simple
p oblems (see Table 1). Howe e , based on he simula ion esul s, do-sea ch sol es iden i ia-
bili y p oblems in g aphs o en e ices in unde wo minu es on a e age. By ou obse a ion,
g aphs ypically analyzed in li e a u e ela ed o iden i iabili y p oblems ha e ewe e ices.
The heo e ical compu a ional complexi y o he gene al o m o he causal iden i iabili y
p oblem de ined in Sec ion 2 emains an impo an and in e es ing ques ion.
The sea ch could also be used o ob ain o mulas ha a e in some sense simple han hose
p oduced by exis ing iden i iabili y algo i hms. A simpli ica ion algo i hm by Tikka and Ka -
anen (2017b) unc ions as a pos -p ocessing s ep a e he iden i ying o mula has al eady
been ob ained by he ID algo i hm. Gi en a measu e o simplici y, he sea ch heu is ic could
be adjus ed o ind simple o mulas di ec ly wi hou eso ing o sepa a e simpli ica ion p o-
cedu es. In some speci ic scena ios, such as he s anda d causal e ec iden i iabili y p oblem,
an app oach known as p uning (Tikka and Ka anen 2018) could be inco po a ed in o he
sea ch. P uning e e s o he emo al o e ices om he g aph, ha a e no equi ed o
de e mining iden i iabili y.
Finally we no e ha iden i iabili y has also been s udied unde he assump ion ha he
unc ional ela ionships depic ed by he causal model a e linea (Ang is , Imbens, and Rubin
1996;Van de Zande and Liśkiewicz 2016;Chen, Kumo , and Ba einboim 2017) o non-
pa ame ic wi h addi i e e o e ms (Pe e s, Mooij, Janzing, and Schölkop 2014;Peña and
Bend sen 2017) and when he causal g aph is no comple ely known (Maa huis, Kalisch, and
Bühlmann 2009;En ne , Hoye , and Spi es 2013;Hy inen e al. 2015;Pe ko ić e al. 2015;
Malinsky and Spi es 2017;Jabe , Zhang, and Ba einboim 2018). Ex ending he sea ch in
hese di ec ions is an in e es ing line o u u e esea ch.
8. Conclusion
We p esen ed do-sea ch: a do-calculus based sea ch capable o sol ing iden i iabili y p oblems
o which no known solu ions exis . This con ibu ion is especially use ul o esea che s wo k-
ing in he ield o causal in e ence o con i m heo e ical esul s o o ind coun e examples o
iden i iabili y claims. In p ac ical e ms, he sea ch can also p o ide solu ions o complica ed
36 Causal E ec Iden i ica ion om Mul iple Incomple e Da a Sou ces
p oblems such as combining anspo abili y and selec ion bias, eco e ing om mul iple bias
sou ces o iden i ying causal quan i ies in he p esence o missing da a ha canno be sol ed
by any o he exis ing me hod. The Rpackage dosea ch p o iding an implemen a ion o
do-sea ch is a ailable on CRAN.
Acknowledgmen s
This wo k belongs o he hema ic esea ch a ea “Decision analy ics u ilizing causal models
and mul iobjec i e op imiza ion” (DEMO) suppo ed by Academy o Finland (g an numbe
311877). AH was suppo ed by Academy o Finland h ough g an 295673. The au ho s wish
o acknowledge CSC – IT Cen e o Science, Finland, o compu a ional esou ces.
Re e ences
Ang is JD, Imbens GW, Rubin DB (1996). “Iden i ica ion o Causal E ec s Using Ins u-
men al Va iables.” Jou nal o he Ame ican S a is ical Associa ion,91(434), 444–455. doi:
10.2307/2291629.
Ba einboim E, Pea l J (2012a). “Causal In e ence by Su oga e Expe imen s: z-
Iden i iabili y.” In N de F ei as, K Mu phy (eds.), P oceedings o he 28 h Con e ence
on Unce ain y in A i icial In elligence, pp. 113–120. AUAI P ess.
Ba einboim E, Pea l J (2012b). “Con olling Selec ion Bias in Causal In e ence.” In
ND Law ence, M Gi olami (eds.), P oceedings o he 15 h In e na ional Con e ence on
A i icial In elligence and S a is ics, olume 22, pp. 100–108.
Ba einboim E, Pea l J (2013). “A Gene al Algo i hm o Deciding T anspo abili y o Expe -
imen al Resul s.” Jou nal o Causal In e ence,1, 107–134. doi:10.1515/jci-2012-0004.
Ba einboim E, Pea l J (2014). “T anspo abili y om Mul iple En i onmen s wi h Limi ed
Expe imen s: Comple eness Resul s.” In P oceedings o he 27 h Annual Con e ence on
Neu al In o ma ion P ocessing Sys ems, pp. 280–288.
Ba einboim E, Tian J (2015). “Reco e ing Causal E ec s om Selec ion Bias.” In P oceedings
o he 29 h AAAI Con e ence on A i icial In elligence, pp. 3475–3481.
Ba einboim E, Tian J, Pea l J (2014). “Reco e ing om Selec ion Bias in Causal and S a-
is ical In e ence.” In P oceedings o he 28 h AAAI Con e ence on Neu al In o ma ion
P ocessing Sys ems.
Bha acha ya R, Nabi R, Shpi se I, Robins JM (2019). “Iden i ica ion in Missing Da a
Models Rep esen ed by Di ec ed Acyclic G aphs.” In P oceedings o he 35 h Con e ence
on Unce ain y in A i icial In elligence.
B eslow NE (1996). “S a is ics in Epidemiology: The Case-Con ol S udy.” Jou nal o he
Ame ican S a is ical Associa ion,91(433), 14–28. doi:10.2307/2291379.

Jou nal o S a is ical So wa e 37
Chen B, Kumo D, Ba einboim E (2017). “Iden i ica ion and Model Tes ing in Linea S uc-
u al Equa ion Models Using Auxilia y Va iables.” In D P ecup, YW Teh (eds.), P oceedings
o he 34 h In e na ional Con e ence on Machine Lea ning, olume 70, pp. 757–766.
Co ea J, Ba einboim E (2017). “Causal E ec Iden i ica ion by Adjus men unde Con-
ounding and Selec ion Biases.” In P oceedings o he 31s AAAI Con e ence on A i icial
In elligence.
Co ea J, Tian J, Ba einboim E (2018). “Gene alized Adjus men unde Con ounding and
Selec ion Biases.” In P oceedings o he 32nd AAAI Con e ence on A i icial In elligence.
Csa di G, Nepusz T (2006). “The ig aph So wa e Package o Complex Ne wo k Resea ch.”
In e Jou nal,Complex Sys ems, 1695.
Danks D, Glymou C, Tillman RE (2009). “In eg a ing Locally Lea ned Causal S uc u es
wi h O e lapping Va iables.” In Ad ances in Neu al In o ma ion P ocessing Sys ems, pp.
1665–1672.
Dawid AP (2002). “In luence Diag ams o Causal Modelling and In e ence.” In e na ional
S a is ical Re iew,70(2), 161–189. doi:10.2307/1403901.
Eddelbue el D, F ançois R (2011). “Rcpp: Seamless Rand C++ In eg a ion.” Jou nal o
S a is ical So wa e,40(8), 1–18. doi:10.18637/jss. 040.i08.
En ne D, Hoye P, Spi es P (2013). “Da a-D i en Co a ia e Selec ion o Nonpa ame ic
Es ima ion o Causal E ec s.” In P oceedings o he 16 h In e na ional Con e ence on
A i icial In elligence and S a is ics, olume 31, pp. 256–264. PMLR.
G eenland S, Robins JM, Pea l J (1999). “Con ounding and Collapsibili y in Causal In e ence.”
S a is ical Science,14(1), 29–46. doi:10.1214/ss/1009211805.
Huang Y, Val o a M (2006a). “Iden i iabili y in Causal Bayesian Ne wo ks: A Sound and
Comple e Algo i hm.” In P oceedings o he 21s Na ional Con e ence on A i icial In elli-
gence – Volume 2, pp. 1149–1154. AAAI P ess.
Huang Y, Val o a M (2006b). “Pea l’s Calculus o In e en ion Is Comple e.” In P oceedings
o he 22nd Con e ence on Unce ain y in A i icial In elligence, pp. 217–224. AUAI P ess.
Hy inen A, Ebe ha d F, Hoye PO (2012). “Causal Disco e y o Linea Cyclic Models om
Mul iple Expe imen al Da a Se s wi h O e lapping Va iables.” In P oceedings o he 28 h
Con e ence on Unce ain y in A i icial In elligence, pp. 387–396.
Hy inen A, Ebe ha d F, Jä isalo M (2015). “Do-Calculus When he T ue G aph Is Un-
known.” In P oceedings o he 31s Con e ence on Unce ain y in A i icial In elligence, pp.
395–404. AUAI P ess.
Jabe A, Zhang J, Ba einboim E (2018). “Causal Iden i ica ion unde Ma ko Equi alence.”
In P oceedings o he 34 h Con e ence on Unce ain y in A i icial In elligence, pp. 978–987.
AUAI P ess.
Kalisch M, Mächle M, Colombo D, Maa huis MH, Bühlmann P (2012). “Causal In e ence
Using G aphical Models wi h he RPackage pcalg.” Jou nal o S a is ical So wa e,47(11),
1–26. doi:10.18637/jss. 047.i11.
38 Causal E ec Iden i ica ion om Mul iple Incomple e Da a Sou ces
Ka anen J (2015). “S udy Design in Causal Models.” Scandina ian Jou nal o S a is ics,
42(2), 361–377. doi:10.1111/sjos.12110.
Kolle D, F iedman N (2009). P obabilis ic G aphical Models: P inciples and Techniques.
MIT P ess.
Lau i zen SL (2000). “Causal In e ence om G aphical Models.” In OE Ba ndo -Nielsen,
DR Cox, C Klüppelbe g (eds.), Complex S ochas ic Sys ems, pp. 67–107. Chapman &
Hall/CRC. doi:10.1201/9781420035988.
Lee S, Co ea J, Ba einboim E (2019). “Gene al Iden i iabili y wi h A bi a y Su oga e Ex-
pe imen s.” In P oceedings o he 35 h Con e ence on Unce ain y in A i icial In elligence.
Li le RJA, Rubin DB (1986). S a is ical Analysis wi h Missing Da a. John Wiley & Sons,
New Yo k.
Maa huis MH, Colombo D (2015). “A Gene alized Backdoo C i e ion.” The Annals o
S a is ics, pp. 1060–1088. doi:10.1214/14-aos1295.
Maa huis MH, Kalisch M, Bühlmann P (2009). “Es ima ing High-Dimensional In e en ion
E ec s om Obse a ional Da a.” The Annals o S a is ics,37(6A), 3133–3164. doi:
10.1214/09-aos685.
Malinsky D, Spi es P (2017). “Es ima ing Bounds on Causal E ec s in High-Dimensional
and Possibly Con ounded Sys ems.” In e na ional Jou nal o App oxima e Reasoning,88,
371–384. doi:10.1016/j.ija .2017.06.005.
Mohan K, Pea l J (2018). “G aphical Models o P ocessing Missing Da a.” a Xi : 1801.03583
[s a .ME], URL h ps://a xi .o g/abs/1801.03583.
Mohan K, Pea l J, Tian J (2013). “G aphical Models o In e ence wi h Missing Da a.” In P o-
ceedings o he 26 h In e na ional Con e ence on Neu al In o ma ion P ocessing Sys ems,
pp. 1277–1285.
Pea l J (1995). “Causal Diag ams o Empi ical Resea ch.” Biome ika,82(4), 669–688.
doi:10.2307/2337329.
Pea l J (2009). Causali y: Models, Reasoning, and In e ence. 2nd edi ion. Camb idge Uni-
e si y P ess.
Peña JM, Bend sen M (2017). “Causal E ec Iden i ica ion in Acyclic Di ec ed Mixed G aphs
and Ga ed Models.” In e na ional Jou nal o App oxima e Reasoning,90, 56–75. doi:
10.1016/j.ija .2017.06.015.
Pe ko ić E, Tex o J, Kalisch M, Maa huis M (2015). “A Comple e Gene alized Adjus men
C i e ion.” In P oceedings o he 31s Con e ence on Unce ain y in A i icial In elligence,
pp. 682–691. AUAI P ess.
Pe e s J, Mooij JM, Janzing D, Schölkop B (2014). “Causal Disco e y wi h Con inuous
Addi i e Noise Models.” Jou nal o Machine Lea ning Resea ch,15, 2009–2053.
RCo e Team (2021). R: A Language and En i onmen o S a is ical Compu ing.RFounda-
ion o S a is ical Compu ing, Vienna, Aus ia. URL h ps://www.R-p ojec .o g/.
Jou nal o S a is ical So wa e 39
Richa dson T (2003). “Ma ko P ope ies o Acyclic Di ec ed Mixed G aphs.” Scandina ian
Jou nal o S a is ics,30(1), 145–157. doi:10.1111/1467-9469.00323.
Sha ma A, Kiciman E (2019). DoWhy: A Py hon Package o Causal In e ence. URL
h ps://gi hub.com/mic oso /dowhy.
Shpi se I, Mohan K, Pea l J (2015). “Missing Da a as a Causal and P obabilis ic P oblem.”
In M Meila, T Heskes (eds.), P oceedings o he 31s Con e ence on Unce ain y in A i icial
In elligence, pp. 802–811. AUAI P ess.
Shpi se I, Pea l J (2006a). “Iden i ica ion o Condi ional In e en ional Dis ibu ions.” In
P oceedings o he 22nd Con e ence on Unce ain y in A i icial In elligence, pp. 437–444.
AUAI P ess.
Shpi se I, Pea l J (2006b). “Iden i ica ion o Join In e en ional Dis ibu ions in Recu -
si e Semi-Ma ko ian Causal Models.” In P oceedings o he 21s Na ional Con e ence on
A i icial In elligence – Volume 2, pp. 1219–1226. AAAI P ess.
Shpi se I, Pea l J (2008). “Comple e Iden i ica ion Me hods o he Causal Hie a chy.”
Jou nal o Machine Lea ning Resea ch,9, 1941–1979.
Spi es P, Glymou C, Scheines R (1993). Causa ion, P edic ion, and Sea ch. 2nd edi ion.
Sp inge -Ve lag, New Yo k. doi:10.1007/978-1-4612-2748-9.
Tex o J, Van de Zande B, Gil ho pe MS, Liśkiewicz M, Ellison GTH (2016). “Robus
Causal In e ence Using Di ec ed Acyclic G aphs: The Rpackage dagi y.” In e na ional
Jou nal o Epidemiology,45(6), 1887–1894. doi:10.1093/ije/dyw341.
Tikka S, Hy inen A, Ka anen J (2021). dosea ch: Causal E ec Iden i ica ion om Mul iple
Incomple e Da a Sou ces.Rpackage e sion 1.0.8, URL h ps://CRAN.R-p ojec .o g/
package=dosea ch.
Tikka S, Ka anen J (2017a). “Iden i ying Causal E ec s wi h he RPackage causale ec .”
Jou nal o S a is ical So wa e,76(12), 1–30. doi:10.18637/jss. 076.i12.
Tikka S, Ka anen J (2017b). “Simpli ying P obabilis ic Exp essions in Causal In e ence.”
Jou nal o Machine Lea ning Resea ch,18(36), 1–30.
Tikka S, Ka anen J (2018). “Enhancing Iden i ica ion o Causal E ec s by P uning.” Jou nal
o Machine Lea ning Resea ch,18(194), 1–23.
Tikka S, Ka anen J (2019). “Su oga e Ou comes and T anspo abili y.” In e na ional
Jou nal o App oxima e Reasoning,108, 21–37. doi:10.1016/j.ija .2019.02.007.
Tillman R, Spi es P (2011). “Lea ning Equi alence Classes o Acyclic Models wi h La en
and Selec ion Va iables om Mul iple Da ase s wi h O e lapping Va iables.” In P oceedings
o he 14 h In e na ional Con e ence on A i icial In elligence and S a is ics, pp. 3–15.
T ian a illou S, Tsama dinos I (2015). “Cons ain -Based Causal Disco e y om Mul iple
In e en ions o e O e lapping Va iable Se s.” Jou nal o Machine Lea ning Resea ch,16,
2147–2205.
40 Causal E ec Iden i ica ion om Mul iple Incomple e Da a Sou ces
T ian a illou S, Tsama dinos I, Tollis I (2010). “Lea ning Causal S uc u e om O e lapping
Va iable Se s.” In P oceedings o he 13 h In e na ional Con e ence on A i icial In elligence
and S a is ics, pp. 860–867.
Van de Zande B, Liśkiewicz M (2016). “On Sea ching o Gene alized Ins umen al Va i-
ables.” In P oceedings o he 19 h In e na ional Con e ence on A i icial In elligence and
S a is ics.
Van de Zande B, Liśkiewicz M, Tex o J (2019). “Sepa a o s and Adjus men Se s in Causal
G aphs: Comple e C i e ia and an Algo i hmic F amewo k.” A i icial In elligence,270,
1–40. doi:10.1016/j.a in .2018.12.006.
A ilia ion:
San u Tikka
Depa men o Ma hema ics and S a is ics
Facul y o Ma hema ics and Science
Uni e si y o Jy askyla
P.O. Box 35, FI-40014, Finland
E-mail: [email p o ec ed]
Jou nal o S a is ical So wa e h p://www.js a so .o g/
published by he Founda ion o Open Access S a is ics h p://www. oas a .o g/
Augus 2021, Volume 99, Issue 5 Submi ed: 2019-12-05
doi:10.18637/jss. 099.i05 Accep ed: 2020-10-26