# Dependency in DAG models with Hidden Variables.

Robin J. Evans Department of Statistics
University of Oxford
Oxford
United Kingdom

###### Abstract

Directed acyclic graph models with hidden variables have been much studied,
particularly in view of their computational efficiency and connection with
causal methods. In this paper we provide the circumstances under which it is
possible for two variables to be identically equal, while all other observed
variables stay jointly independent of them and mutually of each other. We find
that this is possible if and only if the two variables are ‘densely
connected’; in other words, if applications of identifiable causal
interventions on the graph cannot (non-trivially) separate them. As a
consequence of this, we can also allow such pairs of random variables have any
bivariate joint distribution that we choose. This has implications for model
search, since it suggests that we can reduce to only consider graphs in which
densely connected vertices are always joined by an edge.

##  1 Introduction

Informally, a directed acyclic graph (DAG) is a collection of vertices (or
nodes) joined by directed edges ($\to$) such that there is no directed path
from a vertex to itself. DAGs can be used to describe _Bayesian Networks_ by
allowing each vertex to depend stochastically on its parent nodes.

We may hypothesize the existence of vertices which we cannot see, and these
are referred to as _hidden_ or _latent_ nodes or variables.

######  Example 1.1.

Consider the instrumental variables model in Figure 1(a). In this case we have
a DAG over four variables, of which one ($h$) is hidden. Suppose all the
variables are binary, and that $H$ (the random variable associated with $h$)
is Bernoulli with probability $1/2$; we select some value for $X_{a}$. Then
define each of $X_{b}$ and $X_{c}$ to be an ‘xor’ gate of their two parents;
we denote this addition modulo 2 using the symbol $\oplus$. Then we find that:

$\displaystyle X_{b}$ $\displaystyle=X_{a}\oplus H$ $\displaystyle X_{c}$
$\displaystyle=X_{b}\oplus H=(X_{a}\oplus H)\oplus H=X_{a}.$

Hence, $X_{a}=X_{c}$ with probability 1, but $X_{b}$ involves $H$, and is
therefore (marginally) independent of $X_{a}$ and $X_{c}$. This is shown in
Table 1, where the marginal distributions of $X_{a},X_{b}$ and of
$X_{b},X_{c}$ are just the Cartesian products $\\{0,1\\}^{2}$, but
$X_{a}=X_{c}$ for all values.

$H$ | $X_{a}$ | $X_{b}$ | $X_{c}$
---|---|---|---
0 | 0 | 0 | 0
1 | 0 | 1 | 0
0 | 1 | 1 | 1
1 | 1 | 0 | 1
Table 1: Table showing the possible values for $X_{b}=X_{a}\oplus H$ and
$X_{c}=X_{b}\oplus H$ given combinations of $X_{a}$ and $H$.
$a$$b$$c$$h$(a)$a$$b$$c$(b) Figure 1: The _instrumental variables_ model. (a)
A directed acyclic graph on four vertices, one of which is unobserved. (b) The
latent projection of this graph to an ADMG over the observed vertices.

This is a surprising result, since $X_{a}$ and $X_{c}$ do not share any edge
nor a latent parent, so we might expect such a distribution not to be
achievable. This can be easily extended to a sequence of bits of arbitrary
cardinality, just by concatenating the values and applying the arithmetic in a
bitwise fashion. In this paper we will give a generalization of this result to
precisely characterize when it is possible for two variables to be equal, and
independent of all other observed variables (which themselves will all be
mutually independent). We will show that it is possible if and only if there
is no ‘nested’ Markov constraint between the two variables in question.

###  1.1 Previous Work and Contribution

The question of which distributions can be realized from a directed acyclic
graph model with hidden variables has been a topic of considerable interest in
recent years. Its roots lie a century back in the structural diagrams of
Wright (1921), later formalized as Bayesian Networks by Pearl (1986), and
their Markov properties derived by Dawid, Geiger, Pearl, Lauritzen, Verma and
others. Hidden variables were introduced in the 1980’s, and in this context
Pearl and Verma derived the so-called ‘Verma constraint’, a constraint that is
similar in form to, but distinct from, conditional independence; this
restriction had been noted earlier by Robins (1986). This was later turned
into an algorithm by Tian and Pearl (2002) and a _nested Markov_ model by
Richardson et al. (2017), proven algebraically complete in the discrete case
by Evans (2018).

In this paper we show a different kind of completeness result for the nested
Markov property to that given by Evans: approximately, we show that two
vertices are ‘densely connected’ (see Definition 4.2), if and only if their
associated variables can be made to be equal to one another, while remaining
independent of all other observed variables. In fact, we can always reduce the
nested Markov property to a _maximal arid graph_ (MArG) in the same nested
Markov equivalence class. This graph has edges precisely between densely
connected vertices in the original graph, and advertises a nested constraint
between every non-adjacent pair.

There are three reasons why this result is interesting. First, it gives a
quick way of checking whether a particular class of distributions is
compatible with a hidden variable model; this is a topic of considerable
interest, particularly among computer scientists (see, e.g. Wolfe et al.,
2019; Navascués and Wolfe, 2020). Second, it reinforces the importance of the
nested Markov property, because it shows that it precisely characterizes when
two variables can be made to have an arbitrary joint distribution, independent
of all other (observed) variables. The rest of the paper is organized as
follows. Finally, it suggests that we ought to restrict the class of
structures that we consider in a causal model search to maximal arid graphs.

The rest of the paper is organized as follows. Section 2 gives preliminary
definitions, Section 3 discusses the models and Section 4 introduces arid
graphs. Then Sections 5 and 6 give our main results. Section 7 discusses
finding minimal graphs, and Section 8 gives some worked examples. We end with
a discussion. Code to replicate many of the analyses is contained in the R
package dependence (Evans, 2021).

##  2 Preliminaries

In this paper we consider two classes of graph: directed acyclic graphs
(DAGs), and acyclic directed mixed graphs (ADMGs). Directed acyclic graphs
have a set of vertices $V$, and a collection of directed ($\to$) edges between
pairs of distinct vertices. The only condition in these edges is that one
cannot follow a path that coheres with the direction of the edges and end up
back where one started. An ADMG is a DAG together with a collection of
unordered pairs of bidirected ($\leftrightarrow$) edges. These (informally)
represent hidden variables, and so are used in circumstances where one does
not believe that all variables have been observed. Note, therefore, that a DAG
is an ADMG, but not the other way around in general. Examples of DAGs are
given in Figures 1(a) and 2(a), and of ADMGs in Figures 1(b), 2(b), 3 and 7.

Any pair of vertices connected by an edge is said to be _adjacent_. A pair of
vertices may be connected by either a bidirected edge or a directed edge, or
both; the latter configuration is called a _bow_ (see $b$ and $c$ in Figure
1(b), for example).

A _path_ is a sequence of incident edges between adjacent, distinct vertices
in a graph; note that two distinct paths in a mixed graph may have the same
vertex set if a bow is present. The path is _directed_ if all the edges are
directed, and oriented to point away from the first vertex towards the last.

###  2.1 Familial Definitions

We will use standard genealogical terminology for relations between vertices.
Given a vertex $v$ in an ADMG $\mathcal{G}$ with a vertex set $V$, define the
sets of _parents_ , _children_ , _ancestors_ , and _descendants_ of $v$ as

$\displaystyle\operatorname{pa}_{\mathcal{G}}(v)$
$\displaystyle\equiv\\{w:w\to v\text{ in }\mathcal{G}\\}$
$\displaystyle\operatorname{ch}_{\mathcal{G}}(v)$
$\displaystyle\equiv\\{w:v\to w\text{ in }\mathcal{G}\\}$
$\displaystyle\operatorname{an}_{\mathcal{G}}(v)$
$\displaystyle\equiv\\{w:w=v\text{ or }w\to\cdots\to v\text{ in
}\mathcal{G}\\}$ $\displaystyle\operatorname{de}_{\mathcal{G}}(v)$
$\displaystyle\equiv\\{w:w=v\text{ or }v\to\cdots\to w\text{ in
}\mathcal{G}\\},$

respectively. These definitions also apply disjunctively to sets, e.g. for a
set of vertices $C\subseteq V$,
$\operatorname{pa}_{\mathcal{G}}(C)\equiv\bigcup_{v\in
C}\operatorname{pa}_{\mathcal{G}}(v)$. In addition, we define the _district_
of $v$ to be the set of vertices reachable by paths of bidirected edges:

$\operatorname{dis}_{\mathcal{G}}(v)\equiv\\{v\\}\cup\\{w:w\leftrightarrow\ldots\leftrightarrow
v\text{ in }\mathcal{G}\\}.$

The set of districts of an ADMG $\mathcal{G}$ always partitions the set of
vertices $V$. If the graph is unambiguous, we may omit the subscript
$\mathcal{G}$: e.g. $X_{\operatorname{pa}(v)}$.

Given an ADMG $\mathcal{G}$, and a subset $S$ of vertices $V$ in
$\mathcal{G}$, the _induced subgraph_ $\mathcal{G}_{S}$ is the graph with
vertex set $S$, and those edges in $\mathcal{G}$ between elements in $S$. A
set $S\subseteq V$ is called _bidirected-connected_ in $\mathcal{G}$ if every
vertex in $S$ can be reached from every other using only a bidirected path
that is contained entirely in $S$.

We sometimes abbreviate (e.g.) $\operatorname{an}_{\mathcal{G}_{S}}(v)$ and
$\operatorname{dis}_{\mathcal{G}_{S}}(v)$ to $\operatorname{an}_{S}(v)$ and
$\operatorname{dis}_{S}(v)$ where the graph is clear.

##  3 Markov Models

We consider random variables $X_{V}\equiv(X_{v}:v\in V)$ taking values in the
product space ${\mathcal{X}}_{V}=\times_{v\in V}{\mathcal{X}}_{v}$, for finite
dimensional sets ${\mathcal{X}}_{v}$. For any $A\subseteq V$ we denote the
subset $(X_{v}:v\in A)$ by $X_{A}$. For a particular value
$x_{V}\in{\mathcal{X}}_{V}$ we similarly denote a subvector over the set $A$
by $x_{A}$.

We will say that a distribution $p$ is _Markov_ with respect to a DAG
$\mathcal{G}$, if for each $v\in V$, we can write

$\displaystyle X_{v}=f_{v}(X_{\operatorname{pa}_{\mathcal{G}}(v)},E_{v})$

for some measurable function $f_{v}$, and independent noise variables $E_{v}$.
That is, each variable depends on its predecessors only through the value of
its direct parents in the graph. If the resulting joint distribution admits a
density $p$, then this implies the usual factorization:

$\displaystyle p(x_{V})$ $\displaystyle=\prod_{v\in V}p(x_{v}\mid
x_{\operatorname{pa}(v)}),$ $\displaystyle x_{V}\in{\mathcal{X}}_{V}.$

This corresponds to a set of conditional independences over the space
${\mathcal{X}}_{V}$. See Lauritzen et al. (1990) for more details.

###  3.1 Canonical DAGs and Latent Projection

Given an ADMG $\mathcal{G}$, we define the _canonical DAG_ ,
$\overline{\mathcal{G}}$ as the DAG in which each bidirected edge is replaced
by a hidden variable with exactly two children, being the same vertices that
were the endpoints of the bidirected edge. Note that now all bidirected edges
have been replaced with two directed edges; since the directed part of the
ADMG is acyclic, then certainly the resulting graph is acyclic. Hence, the
canonical DAG is—as its name implies—always a DAG. For example, the DAG in
Figure 1(a) is the canonical DAG for the graph in Figure 1(b), and similarly
Figure 2(a) for 2(b).

Given a DAG, we can transform it into an ADMG that captures most of the causal
structure by performing a _latent projection_. Simple examples correspond to
the pairs of graphs in Figures 1 and 2, but we provide a definition and
another example in the Appendix, Section B.1.

Given an ADMG $\mathcal{G}$ with vertices $V$, we define the _marginal model_
as the set of distributions which can be realized as a margin over $X_{V}$ for
distributions that are Markov with respect to the canonical DAG
$\overline{\mathcal{G}}$. In doing this, we make no assumption about the
statespace of the hidden variables, though for discrete models it is
sufficient to have the same cardinality as all the observed variables, and in
general it is both necessary and sufficient for the latent variables we use to
be continuous.

We now define sets which are _intrinsic_ for a particular ADMG. Take a set
$B\subseteq V$, and set $B^{(0)}=V$; then alternately apply the operations:

$\displaystyle B^{(i+1)}=\operatorname{dis}_{B^{(i)}}(B)\qquad
B^{(i+2)}=\operatorname{an}_{B^{(i+1)}}(B),$

increasing $i$ at each step. Each time we apply these steps either at least
one vertex will be removed from $B^{(i)}$, or else the process will terminate
at a superset of $B$, which we will denote by $\langle
B\rangle_{\mathcal{G}}$. This is called the _closure_ of $B$. If $\langle
B\rangle_{\mathcal{G}}$ is bidirected-connected, then we say it is an
_intrinsic_ set, and the _intrinsic closure_ of $B$.

For convenience we generally abbreviate $\langle\\{v\\}\rangle_{\mathcal{G}}$
as $\langle v\rangle_{\mathcal{G}}$, and (for example)
$\operatorname{pa}_{\mathcal{G}}(\langle\\{v\\}\rangle_{\mathcal{G}})$ as
$\operatorname{pa}_{\mathcal{G}}(\langle v\rangle)$.

##  4 Arid Graphs

The main result of this section is taken from Shpitser et al. (2018), and says
that the nested Markov model associated with _any_ ADMG $\mathcal{G}$ can be
associated, without loss of generality, with a closely related _maximal arid
graph (MArG)_ $\mathcal{G}^{{\dagger}}$. In particular, the nested Markov
models associated with $\mathcal{G}$ and $\mathcal{G}^{\dagger}$ are the same.
Note that MArGs are themselves just a restricted class of ADMGs.

###  4.1 Arid Graphs

######  Definition 4.1.

Let $\mathcal{G}$ be an ADMG. We say that $\mathcal{G}$ is _arid_ if $\langle
v\rangle_{\mathcal{G}}=\\{v\\}$ for each $v\in V$.

The word ‘arid’ is used because it implies that the graph lacks any (non-
trivial) ‘C-trees’ or ‘converging aborescences’.

######  Definition 4.2.

A pair of vertices $a\neq b$ in an ADMG $\mathcal{G}$ is _densely connected_
if either $a\in\operatorname{pa}_{\mathcal{G}}(\langle b\rangle)$, or
$b\in\operatorname{pa}_{\mathcal{G}}(\langle a\rangle)$, or
$\langle\\{a,b\\}\rangle_{\mathcal{G}}$ is a bidirected-connected set.

An ADMG $\mathcal{G}$ is called _maximal_ if every pair of densely connected
vertices in $\mathcal{G}$ are adjacent.

Densely connected pairs of vertices form the nested Markov analogue of
_inducing paths_ (Verma and Pearl, 1990). The existence of an inducing path
between two vertices means that (almost) no distribution that is Markov with
respect to the graph will have _any_ conditional independence between the
associated variables. Analogously, a densely connected pair of vertices means
that (almost) no distributions that are nested Markov with respect to the
graph will have _any_ conditional independences within _any_ ADMG
corresponding to a valid combination of intrinsic sets. In effect, a densely
connected pair cannot be made independent, by any combination of conditioning
and identifiable intervention operations.

As an example, note that the pair $\\{a,c\\}$ is densely connected in Figure
1(b), because $\operatorname{pa}_{\mathcal{G}}(\langle
c\rangle)=\operatorname{pa}_{\mathcal{G}}(\\{b,c\\})=\\{a,b\\}$. Further
details are given in the Appendix, Section C.

######  Definition 4.3.

Let $\mathcal{G}$ be an ADMG. We define its _maximal arid_ projection as
$\mathcal{G}^{{\dagger}}$, the ADMG with edges:

  * •

$a\to b$ if and only if $a\in\operatorname{pa}_{\mathcal{G}}(\langle
b\rangle)$;

  * •

$a\leftrightarrow b$ if and only if the set
$\langle\\{a,b\\}\rangle_{\mathcal{G}}$ is bidirected-connected, and both
$a\notin\operatorname{pa}_{\mathcal{G}^{{\dagger}}}(b)$ and
$b\notin\operatorname{pa}_{\mathcal{G}^{{\dagger}}}(a)$; that is, there is no
directed edge between $a$ and $b$.

Note that, in particular, all directed edges in $\mathcal{G}$ are preserved in
$\mathcal{G}^{\dagger}$, though some may be added if they preserve ancestral
sets. Bidirected edges will be removed if connecting a vertex to something in
its intrinsic closure, and added if they are required for maximality. For
example, the MArG projection of the graph in Figure 2(b) adds a bidirected
edge between the vertices 3 and 4. A further example is found in the Appendix,
Section B.2.

######  Proposition 4.4 (Shpitser et al., 2018).

The maximal arid projection is arid and maximal.

######  Theorem 4.5 (Shpitser et al., 2018).

The nested model associated with an ADMG $\mathcal{G}$ is the same as the
nested model associated with $\mathcal{G}^{{\dagger}}$.

######  Corollary 4.6.

Let $p$ be a distribution that is nested Markov with respect to $\mathcal{G}$.
Then for $v,w\in V$ the variables $X_{v}$ and $X_{w}$ have a nested constraint
between them if and only if $v$ and $w$ are not adjacent in the arid
projection $\mathcal{G}^{\dagger}$.

##  5 Perfect Correlation

We now come to the main content of this paper.

We have already seen in Example 1.1 that it is possible for two vertices which
are neither joined by an edge, nor share a latent parent, nevertheless to be
perfectly correlated. We now give a slightly more complicated example of this
phenomenon.

######  Example 5.1.

Consider the DAG in Figure 2(a). Suppose that each hidden variable
($H_{1},H_{2},H_{3}$) is again a Bernoulli random variable with probability
$1/2$, and all the observed variables are again ‘xor’ gates. Then:

$\displaystyle X_{a}$ $\displaystyle=H_{1}\oplus H_{2}$ $\displaystyle X_{b}$
$\displaystyle=H_{1}\oplus H_{3}$ $\displaystyle X_{c}$
$\displaystyle=X_{b}\oplus H_{2}$ $\displaystyle X_{d}$
$\displaystyle=X_{a}\oplus H_{3},$

and hence $X_{c}=X_{d}=H_{1}\oplus H_{2}\oplus H_{3}$. It follows from Lemma
A.1 (in Appendix A) that if $H_{1},H_{2},H_{3}$ are all independent, then so
are $X_{a},X_{b},X_{c}$. Naturally, the same result also holds for
$X_{a},X_{b},X_{d}$.

$a$$b$$c$$d$$h_{1}$$h_{2}$$h_{3}$(a)$a$$b$$c$$d$(b) Figure 2: (a) A directed
acyclic graph on seven vertices, three of which are unobserved. (b) The latent
projection of this graph to an ADMG over the observed vertices.

Again, the result seems surprising given the lack of any form of adjacency
between the vertices $c$ and $d$.

###  5.1 Minimal Closures

In our main result (Theorem 6.4) we will claim that it is possible to have a
distribution in the marginal model of an ADMG, with two variables identical to
one another and independent of all other observable variables if and only if
they are densely connected. If these vertices are adjacent in the ADMG, then
the result is obvious; if we have $w\to v$ then the value can be directly
transmitted, and if $w\leftrightarrow v$ then the latent parent in the
canonical DAG can just give the same value to both $v$ and $w$. We will show
that, in fact, this can be applied much more generally.

######  Proposition 5.2.

Let $\mathcal{G}$ be an ADMG, and $B=\\{v_{1},\ldots,v_{k}\\}\subseteq V$.
Then assume that $C:=\langle B\rangle_{\mathcal{G}}$ is a bidirected-connected
(and hence intrinsic) set.

Now consider the following edge subgraph of $\mathcal{G}_{C}$, which we call
$\widetilde{\mathcal{G}}_{C}$: the directed edges only contain a forest over
$C$ that converges on $B$, and bidirected edges only contain a spanning tree
over $C$. Then $\langle B\rangle_{\mathcal{G}}=C=\langle
B\rangle_{\widetilde{\mathcal{G}}_{C}}$.

###### Proof.

Since every element of $\langle B\rangle_{\mathcal{G}}$ is an ancestor of some
$v\in B$ in $\widetilde{\mathcal{G}}_{C}$, and also in the same district as
everything in $B$, it is clear that the result holds. ∎

Note that this loosely defined procedure will generally lead to many different
graphs, but they will always have the same total number of edges; that is,
there will always be $|C|-1$ bidirected edges, and $|C|-|B|$ directed edges.
However, the particular choice of the trees will affect which edges can be
removed by the next result. In the Appendix (Section D) we give some
algorithms for formally determining how to pick the trees in an efficient way.

Suppose we have a graph whose bidirected edges form a spanning tree, and a set
of vertices $D\subseteq V$ that divides into $d$ districts. We say that $D$ is
_almost encapsulated_ in $\mathcal{G}$ if for every bidircted edge with an
endpoint in $D$, the other endpoint is also in $D$, with the exception of
exactly $d$ edges, one for each connected component.

######  Proposition 5.3.

Consider an ADMG $\mathcal{H}=\widetilde{\mathcal{G}}_{C}$ obtained by
application of Proposition 5.2, and let
$B=C\setminus\operatorname{pa}_{\mathcal{H}}(C)$ be the vertices without
children. Suppose that there is a subset of vertices $A\subseteq C\setminus B$
such that $\operatorname{an}_{\mathcal{H}}(A)$ is almost encapsulated. Then if
we remove $\operatorname{an}_{\mathcal{H}}(A)$ from the graph to obtain (say)
$\widetilde{\mathcal{H}}$ we have $\langle
B\rangle_{\widetilde{\mathcal{H}}}=\langle
B\rangle_{\mathcal{H}}\setminus\operatorname{an}_{\mathcal{H}}(A)$.

###### Proof.

Since the set we remove is almost encapsulated, this means that the remaining
vertices still have a spanning tree of bidirected edges. In addition, since
the subset is ancestral, every remaining vertex is still an ancestor of an
element of $B$. Hence we have the result given. ∎

This is a very useful result, since it will enable us to find a minimal graph
which we can apply our results to. However, finding that set may be
computationally difficult, as the next example illustrates.

######  Example 5.4.

Consider the graph in Figure 3, and suppose we wish to have $X_{v}=X_{w}$ and
all other variables independent. This is clearly very easy, since there is a
directed edge $w\to v$; however, we cannot reach this minimal graph all that
easily by using Proposition 5.3. No set will work except for $\\{c,e\\}$, and
we can make this problem have exponential complexity very easily (see Section
D.2).

$w$$v$$e$$d$$c$$b$$a$ Figure 3: An ADMG which is not minimal w.r.t. $(v,w)$
but for which we cannot apply Corollary 5.5. See Example 5.4.

As a result of this problem, we present two much easier to apply corollaries.

######  Corollary 5.5.

Let $\mathcal{H}=\widetilde{\mathcal{G}}_{C}$ be an ADMG chosen using
Proposition 5.2, and let $B=C\setminus\operatorname{pa}_{\mathcal{H}}(C)$.
Suppose there is a vertex $a$ such that
$\operatorname{ch}_{\mathcal{H}}(a)\neq\emptyset$, and such that
$\operatorname{an}_{\mathcal{H}}(a)$ is almost encapsulated within
$\mathcal{H}$.

Then we can remove $\operatorname{an}_{\mathcal{H}}(a)$ from the graph to
obtain (say) $\widetilde{\mathcal{H}}$, and still have
$C\setminus\operatorname{an}_{\mathcal{H}}(a)=\langle
B\rangle_{\widetilde{\mathcal{H}}}$.

###### Proof.

This is just a special case of Proposition 5.3 with a single vertex $a$
instead of a set $A$. ∎

In a graph we say that a vertex is a _leaf_ if it only has a single neighbour.

######  Corollary 5.6.

Let $\mathcal{H}=\widetilde{\mathcal{G}}_{C}$ be an ADMG chosen using
Proposition 5.2, and let $B=C\setminus\operatorname{pa}_{\mathcal{H}}(C)$. If
some $a\in C\setminus B$ is a leaf in both the directed and the bidirected
trees, then we can remove it from the graph and still have
$C\setminus\\{a\\}=\langle B\rangle_{\mathcal{H}_{-a}}$.

###### Proof.

This is just a special case of Corollary 5.5 with a single vertex acting as
the set of ancestors. ∎

The complexity of identifying a minimal set using Proposition 5.3 motivates us
to describe a linear time algorithm for determining the an inclusion minimal
subgraph in Section 7 (see Algorithm 1).

##  6 Main Results

In this section we deal with our main concern, which is to show that if two
vertices ($v$ and $w$) are densely connected, then we can set them to be
equal, provided that all the other variables we need to set have at least the
same cardinality as $X_{v}$ and $X_{w}$.

######  Definition 6.1.

Given a graph $\mathcal{G}$ and two vertices $v,w\in V$ that are densely
connected, we define the subgraph $\mathcal{G}^{vw}$ as follows:

  * •

if $w\in\operatorname{pa}_{\mathcal{G}}(\langle v\rangle)$ then use the
induced subgraph $\mathcal{G}_{\langle v\rangle\cup\\{w\\}}$;

  * •

if $v\in\operatorname{pa}_{\mathcal{G}}(\langle w\rangle)$ then take
$\mathcal{G}_{\langle w\rangle\cup\\{v\\}}$;

  * •

if $\langle\\{v,w\\}\rangle_{\mathcal{G}}$ is bidirected-connected, then take
the induced subgraph $\mathcal{G}_{\langle\\{v,w\\}\rangle}$.

Note that it is possible that _both_
$w\in\operatorname{pa}_{\mathcal{G}}(\langle v\rangle)$ _and_
$\langle\\{v,w\\}\rangle_{\mathcal{G}}$ is bidirected-connected, in which case
we have a choice about which graph to select. Typically we would prefer
$\mathcal{G}_{\langle v\rangle\cup\\{w\\}}$, but it may be that
$\mathcal{G}_{\langle\\{v,w\\}\rangle}$ enables us to select different
variables to be used in the final distribution. Such greater flexibility could
be useful in some circumstances (e.g. if one of the variables used in the
directed case does not have sufficiently high cardinality).

######  Proposition 6.2.

Let $\mathcal{G}$ be a ADMG with $v,w\in V$ such that
$w\in\operatorname{pa}_{\mathcal{G}}(\langle v\rangle)$. Then there is a
distribution, Markov with respect to the canonical DAG
$\overline{\mathcal{G}}$, such that $X_{v}=X_{w}$ and these are independent of
all other observed variables. These other variables may be chosen to be
mutually independent.

###### Proof.

We first assume that all variables are binary, and prove this for a single
bit. The extension to multiple bits is obvious, provided that all the
variables have sufficiently large cardinality. We will ignore any vertices
other than those in $\langle v\rangle_{\mathcal{G}}\cup\\{w\\}$, since these
are just set to be independent of all other random variables.

Reduce the graph to $\mathcal{G}^{vw}$ and then apply Proposition 5.2; we can
then choose to remove any unnecessary variables from $\langle
v\rangle_{\mathcal{G}}$ using Proposition 5.3 if we want to111Applying this
result isn’t strictly necessary, but it will reduce the number of variables
that need to have the minimal cardinality..

In this new smaller graph, say $\mathcal{H}$, consider the canonical DAG
$\overline{\mathcal{H}}$. Set all hidden variables in $\overline{\mathcal{H}}$
to be independent Bernoulli r.v.s with parameter $1/2$, and select some
arbitrary $x_{w}\in\\{0,1\\}$. Now, let every other observed variable,
including $X_{v}$, be the sum of its parents modulo 2. There is a unique
directed path that carries the value of $X_{w}$ down to $X_{v}$ (though, of
course, it will generally be encoded with various additions).

Every hidden variable has exactly two children, and since these children are
both ancestors of $v$ by exactly one path, this means that their value will
have been cancelled out at the node where the two paths first meet.
Consequently, the value of every bidirected edge will have been removed by the
time we reach $v$, and so $X_{v}=x_{w}$ as required.

Now ignore $X_{w}$, and consider some subset $D\subseteq C$ of the other
variables in the intrinsic closure of $v$. Remember that there is a spanning
tree of bidirected edges, so in order to obtain that a set of variables is
jointly dependent we always need _both_ the endpoints of any bidirected edge.
This clearly implies that we need the whole tree, and hence all of $C$; but
recall that (exactly) one variable has $X_{w}$ as a parent, so therefore even
the entire set $C$ consists of independent random variables. ∎

The next proposition deals with the other way in which two vertices can be
densely connected.

######  Proposition 6.3.

Let $\mathcal{G}$ be an ADMG with $v,w\in V$ such that
$\langle\\{v,w\\}\rangle_{\mathcal{G}}$ is bidirected-connected. Then there is
a distribution, Markov with respect to the canonical DAG
$\overline{\mathcal{G}}$, such that $X_{v}=X_{w}$ and these are independent of
all other observed variables. Again, these variables may be chosen to be
mutually independent.

###### Proof.

First, obtain $\mathcal{G}^{vw}$ from Definition 6.1, and then find
$\mathcal{H}=\widetilde{\mathcal{G}}^{vw}$ from Proposition 5.2. Then again
(optionally) choose $\langle\\{v,w\\}\rangle_{\mathcal{H}}$ to be minimal by
applying Proposition 5.3. Then set all latent variables in
$\overline{\mathcal{H}}$ to be independent Bernoulli random variables with
parameter $1/2$.

Set all observed variables to be the sum modulo 2 of their parents. Now, each
latent variable has two children, and by minimality of the directed edges,
each of these is an ancestor of exactly one of $v$ or $w$. If both are
ancestors of $v$ (or of $w$), then the value of the latent variable will
cancel out at the vertex where the two descending paths meet. Otherwise, the
latent variable appears in the sums for both $X_{v}$ and $X_{w}$. Hence
$X_{v}=X_{w}$.

For the other variables, any subset that (possibly) includes $v$ will involve
only one end of at least one bidirected edge. Hence by Lemma A.1 these
variables are all independent. ∎

Note that if neither of these conditions of Propositions 6.2 or 6.3 hold, then
there must be a (nonparametric) nested constraint between $X_{v}$ and $X_{w}$
(Shpitser et al., 2018).

######  Theorem 6.4.

We can obtain any joint distribution on $(X_{v},X_{w})$ independently of all
other variables if and only if in the MArG projection there is an edge between
$v$ and $w$.

###### Proof.

This follows from the two propositions above and the fact that if there is no
edge in the MArG projection, then there is a nested constraint between $X_{v}$
and $X_{w}$ (Shpitser et al., 2018). This amounts to a marginal independence
constraint when other variables are mutually independent, so it is clearly
incompatible with the distribution described. ∎

######  Remark 6.5.

We can easily extend the result to arbitrary discrete random variables by
using essentially the same method; assume that all the variables have exactly
$k$ states, and set bidirected edges to be uniformly sampled from
$\\{0,1,\ldots,k-1\\}$. If both ends of the bidirected edge are ancestors of
the same vertex (e.g. $v$) then one end of the bidirected edge must subtract
its value (this way that quantity will still cancel out when the two paths
meet again). If the edges are ancestors of distinct vertices then both
children must add the number to their total.

###  6.1 Arbitrary Continuous Distributions

As we have already discussed, it is also easy to extend the result to
continuous random variables by using bitwise operations; suppose that the
equation to determine $X_{v}$ is
$X_{v}=\bigoplus_{i\in\operatorname{pa}_{\overline{\cal H}}(v)}Y_{i}$; here
$Y_{i}$ can represent either an observed or a latent variable, and we have
just proven that the right hand side is the same as $X_{w}$. To obtain an
arbitrary joint distribution we can just replace the structural equation with
$X_{v}=f(X_{w},U)$ for an independent uniform $(0,1)$ random variable $U$, and
a suitable measurable function $f$ (Chentsov, 1982, Theorem 2.2). We
illustrate this with the scatter plots in Figure 4, which shows data generated
from the IV model in this manner, with the marginal distributions set to be
standard normal and the correlation between $X_{a}$ and $X_{c}$ set to be 0.9.

Figure 4: Scatter plot showing normal random variables simulated from the
hidden variable DAG in Figure 1.

##  7 Algorithms for Minimality

If we have applied Proposition 5.3 as much as possible, then the graph we end
up with is minimal. However, the result is not computationally efficient to
use, since (in principal) we may have to try every ancestral subset of
$C\setminus B$. In Algorithm 1 we give a fast algorithm to obtain a minimal
set, by building it up from the two vertices $v,w$. In particular, the
algorithm has worst-case linear complexity in the number of vertices.

Recall that the bidirected edges in a graph output from Proposition 5.2 are in
the form of a tree, so there is a unique path between any two vertices. We
denote by $\operatorname{dis}^{v}(A)$ the set of vertices on the unique
bidirected paths from each $a\in A$ to $v$ (inclusive of $A$ and $v$).

Input: vertices $v,w$, graph $\mathcal{G}$ from Proposition 5.2

Result: A minimal set $W$.

1 if  _$w\in\operatorname{dis}_{\mathcal{G}}(v)$_ then

2 initialize $A=\\{v,w\\}$;

3 pick $a\leftrightarrow b$ such that $a\in\operatorname{an}_{\mathcal{G}}(v)$
and $b\in\operatorname{an}_{\mathcal{G}}(w)$;

4 initialize
$W=\\{a,b\\}\cup\operatorname{dis}^{v}(a)\cup\operatorname{dis}^{w}(b)$;

5

6else

7 initialize $W=A=\\{v,w\\}$;

8

9 end if

10while  _$A\neq\emptyset$_ do

11 $A:=\operatorname{de}(W)\setminus W$;

12 $A:=(A\cup\operatorname{dis}^{v}(A))\setminus W$;

13 $W:=W\dot{\cup}A$;

14

15 end while

return _$W$_

Algorithm 1 Find minimal set $W$ that allows $X_{v}$ and $X_{w}$ to be
perfectly correlated.
$w$$b$$c$$v$$a$$d$(a)$w$$b$$c$$v$$a$$d$(b)$w$$b$$c$$v$$d$$a$$h_{2}$$h_{1}$$h_{4}$$h_{3}$$h_{5}$(c)$w$$b$$c$$v$$a$$d$(d)$w$$b$$c$$v$$a$(e)$w$$b$$c$$v$$a$$h_{2}$$h_{1}$$h_{3}$(f)
Figure 5: An illustration of the construction in Proposition 6.2, for the
vertices $v$ and $w$. (a) An ADMG $\mathcal{G}$, (b) its MArG projection
$\mathcal{G}^{\dagger}$, and (c) its canonical DAG $\overline{\mathcal{G}}$.
In (d) we reduce the directed and bidirected edges from (a) to spanning trees,
as well as removing incoming edges to $z$; in (e) we remove the vertex $d$
using Corollary 5.5, and in (f) we give the canonical DAG for the graph in
(e). $v$$a$$b$$w$$c$(a)$v$$a$$b$$w$$c$(b)$v$$a$$b$$w$$h_{2}$$h_{3}$$h_{1}$(c)
Figure 6: An illustration of the construction in Proposition 6.3, for the
vertices $v$ and $w$. (a) An ADMG; (b) here we reduce the bidirected edges to
a spanning tree; (c) we apply Corollary 5.6 to remove $c$ and take the
canonical DAG. $a$$b$$c$$d$(a)$a$$b$$c$$d$(b) Figure 7: (a) A graph in which
it is not possible to have $X_{a}=X_{c}=X_{d}$ almost surely and independent
of $X_{b}$, even though this clearly is possible in its arid projection (b).

######  Proposition 7.1.

The complexity of Algorithm 1 is $O(|V|)$, where $V$ is the vertex set of
$\mathcal{G}$.

###### Proof.

Note that, since the graph consists of two trees, there are only $2(|V|-1)$
edges in total. Suppose we have the children and spouses of each vertex
(otherwise we may need to run an $O(|V|)$ algorithm to obtain these, e.g. from
the parent sets). Finding the district in a particular direction may involve
rearranging the spouses so that the one towards $v$ (or $w$) is listed first.
Again, this can be done in $O(|V|)$ time.

If the ‘if’ condition is satisfied, then we must find a bidirected edge that
is an ancestor of both $v$ and $w$. These two sets can be determined in linear
time, and the check for an edge will also be linear. If the ‘else’ condition
is satisfied, then there is essentially nothing to do.

Then we just run the algorithm to find the descendants of $w$, or of $W$ in
the ‘if’ case and then take the first entry in each list of spouses to find
bidirected paths to $v$. Since we ignore any vertices that we have seen before
(or stop at this point), this entire procedure will be worst case linear in
the number of vertices. ∎

##  8 Examples

######  Example 8.1.

Consider the graph in Figure 5(a), and consider the pair $v,w$. Note that, in
the arid projection of this graph (see (b)), there is an edge $w\to v$; hence,
by Theorem 6.4, we know it must is possible to set up a distribution, Markov
with respect to the canonical DAG $\overline{\mathcal{G}}$ in 5(c), such that
$X_{v}=X_{w}$ and these are independent of all the other observed variables.

To do this, we simply apply Propositions 5.2 and Corollary 5.5 to obtain the
graph in (e), and then follow the rules stated in the proof of Proposition
6.2. We select a value $X_{w}=x_{w}$, sample independent Bernoulli random
variables for each of $H_{1}$, $H_{2}$ and $H_{3}$, and then let all other
variables be xor-gates of their parents. We therefore have:

$\displaystyle X_{a}$ $\displaystyle=H_{1}\oplus H_{2}\qquad\qquad
X_{b}=H_{1}\oplus H_{3}$ $\displaystyle X_{c}$ $\displaystyle=H_{3}\oplus
X_{b}\oplus x_{w}=H_{1}\oplus x_{w}$ $\displaystyle X_{v}$
$\displaystyle=H_{2}\oplus X_{a}\oplus X_{c},$

and note that by substituting in, we find:

$\displaystyle X_{v}$ $\displaystyle=H_{2}\oplus(H_{1}\oplus
H_{2})\oplus(H_{1}\oplus x_{w})=x_{w}.$

We also note that Lemma A.1 implies that all the other variables are
independent.

######  Example 8.2.

Consider the graph in Figure 6(a); we can reduce this to the graph in (c)
using Propositions 5.2 and 5.3. Then if we set the latent variables to be
$H_{1}$, $H_{2}$, $H_{3}$ (as indicated in Figure 6(c)), we have:

$\displaystyle X_{a}$ $\displaystyle=H_{1}\oplus H_{2}\qquad\qquad
X_{b}=H_{1}\oplus H_{3}$ $\displaystyle X_{v}$ $\displaystyle=X_{a}\oplus
H_{3}=H_{1}\oplus H_{2}\oplus H_{3}$ $\displaystyle\text{and}\quad X_{w}$
$\displaystyle=H_{2}\oplus X_{b}=H_{2}\oplus H_{1}\oplus H_{3};$

hence, we indeed have $X_{v}=X_{w}$. In addition, we clearly have joint
independence just by applying Lemma A.1.

Note that, if we had removed the $a\leftrightarrow w$ edge when obtaining a
spanning tree, we would still have been able to obtain the result. In this
case everything reduces to essentially be the same as the IV model: we can
remove $a$ as well as $c$, and we have $X_{v}=H_{3}$ and (if the new latent
variable above $X_{b}$ and $X_{w}$ is $H_{4}$) we have $X_{w}=X_{b}\oplus
H_{4}=(H_{3}\oplus H_{4})\oplus H_{4}=H_{3}$. By similar reasoning to before,
the other variables $X_{a},X_{c}$ are jointly independent of each other and
$X_{v}$.

######  Remark 8.3.

Note that the case where the arid graph induces a directed edge allows us to
choose the value that the two variables take by intervening on the parent
variable. However, in the case where a bidirected edge is introduced it is
just a function of some hidden variables that we may not be able to control.

##  9 Discussion

This paper demonstrates that DAG models with hidden variables may display some
surprising and counterintuitive relationships between the variables in them.
In terms of causal model search, these results suggest that we may be better
off restricting all ADMGs to only maximal arid graphs, since their
counterparts which are not maximal and arid may exhibit spurious dependencies
that do not reflect the overall structure. Note also that arid graphs are
precisely those that are globally identifiable under the assumption of linear
structural equations (Drton et al., 2011).

The results also provide further justification for the nested Markov model,
since they show that the nested model precisely characterizes which pairs of
variables can—and cannot—be made to be perfectly dependent. In other words,
either two vertices possess a nested Markov constraint between them, or they
can be made to be exactly equal and independent of all other variables. It
also gives fast methods for checking whether certain distributions are
compatible with a given hidden variable model.

###  9.1 Extension to multiple variables

An obvious extension to this work is to consider the possibility of
simultaneously setting all $(X_{a}:a\in A)$ for some set $A\subseteq V$ to be
equal, with joint independence of all other variables.

The graph in Figure 7(a) shows that the results for pairwise equality do not
extend in a simple way to larger sets. Consider the triple $\\{a,c,d\\}$, for
example. In the MArG projection of $\mathcal{G}$ (see Figure 7(b)) it clearly
_is_ possible to set these three variables to be equal, since $c,d$ are both
children of $a$. However, in fact this is not possible using the canonical DAG
for $\mathcal{G}$, which can be verified by applying the results of Wolfe et
al. (2019) or Fraser (2020) (Elie Wolfe, personal communication.)

Acknowledgements. We thank Elie Wolfe for confirming that the graph in Figure
7(a) cannot represent the three-way perfect dependence.

## References

  * Chentsov [1982] N. N. Chentsov.  _Statistical Decision Rules and Optimal Inference_.  American Mathematical Society, 1982.  Translated from Russian.
  * Drton et al. [2011] M. Drton, R. Foygel, and S. Sullivant.  Global identifiability of linear structural equation models.  _Annals of Statistics_ , 39(2):865–886, 2011\.
  * Evans [2018] R. J. Evans.  Margins of discrete Bayesian networks.  _Annals of Statistics_ , 46(6A):2623–2656, 2018\.
  * Evans [2021] R. J. Evans.  dependence v0.1.2, 2021.  URL https://github.com/rje42/dependence.  Accessed 2021-06-10.
  * Fraser [2020] T. C. Fraser.  A combinatorial solution to causal compatibility.  _Journal of Causal Inference_ , 8(1):22–53, 2020\.
  * Lauritzen et al. [1990] S. L. Lauritzen, A. P. Dawid, B. N. Larsen, and H.-G. Leimer.  Independence properties of directed markov fields.  _Networks_ , 20(5):491–505, 1990.
  * Navascués and Wolfe [2020] M. Navascués and E. Wolfe.  The inflation technique completely solves the causal compatibility problem.  _Journal of Causal Inference_ , 8(1):70–91, 2020\.
  * Pearl [1986] J. Pearl.  Fusion, propagation, and structuring in belief networks.  _Artificial Intelligence_ , 29:241–288, 1986.
  * Richardson [2003] T. S. Richardson.  Markov properties for acyclic directed mixed graphs.  _Scandinavial Journal of Statistics_ , 30(1):145–157, 2003.
  * Richardson et al. [2017] T. S. Richardson, R. J. Evans, J. M. Robins, and I. Shpitser.  Nested Markov properties for acyclic directed mixed graphs.  arXiv:1701.06686, 2017.
  * Robins [1986] J. M. Robins.  A new approach to causal inference in mortality studies with sustained exposure periods – application to control of the healthy worker survivor effect.  _Mathematical Modeling_ , 7:1393–1512, 1986.
  * Shpitser et al. [2018] I. Shpitser, R. J. Evans, and T. S. Richardson.  Acyclic linear SEMs obey the nested Markov property.  In _Proceedings of the 34th Conference on Uncertainty in Artificial Intelligence (UAI-18)_ , pages 735–745, 2018.
  * Tian and Pearl [2002] J. Tian and J. Pearl.  On the testable implications of causal models with hidden variables.  In _Proceedings of the Eighteenth Conference on Uncertainty in Artificial Intelligence (UAI-02)_ , volume 18, pages 519–527. AUAI Press, Corvallis, Oregon, 2002.
  * Verma and Pearl [1990] T. S. Verma and J. Pearl.  Equivalence and synthesis of causal models.  In _Proceedings of the Sixth Conference on Uncertainty in Artificial Intelligence (UAI-90)_ , 1990.
  * Wolfe et al. [2019] E. Wolfe, R. W. Spekkens, and T. Fritz.  The inflation technique for causal inference with latent variables.  _Journal of Causal Inference_ , 7(2), 2019.
  * Wright [1921] S. Wright.  Correlation and causation.  _Journal of Agricultural Research_ , 20:557–585, 1921.

##  Appendix A Probabilistic Result

######  Lemma A.1.

Consider a collection of variables $X_{1},\ldots,X_{k}$, where each $X_{i}$ is
a sum modulo 2 of some subset of its predecessors, and a number of independent
Bernoulli random variables with parameter $1/2$.

The Bernoulli random variables are each added to exactly two of the $X_{i}$s,
and the edges induced by this graph form a tree over $\\{1,\ldots,k\\}$.

Then any subset of the random variables $X_{1},\ldots,X_{k-1}$ contains
mutually (and jointly) independent $\operatorname{Bernoulli}(1/2)$ variables,
but

$\sum_{i=1}^{k}X_{i}=0\;\operatorname{mod}2.$

###### Proof.

We proceed by induction. $X_{1}=\sum_{j\in T_{1}}Z_{j}\mod 2$ for some non-
empty set $T_{1}$ of independent Bernoulli random variables, so $X_{1}$ itself
must be a $\operatorname{Bernoulli}(1/2)$ r.v. Now, suppose that
$X_{1},\ldots,X_{\ell-1}$ are independent $\operatorname{Bernoulli}(1/2)$
r.v.s, and consider $X_{\ell}$ for $\ell<k$. Since the random variables form a
tree, then

$\displaystyle X_{\ell}=\sum_{i\in S_{\ell}}X_{i}+\sum_{i\in
T_{\ell}}Z_{i}\mod 2$

is independent of $X_{1},\ldots,X_{\ell-1}$ if and only if

$\displaystyle X_{\ell}^{*}:=\sum_{i\in T_{\ell}}Z_{i}\mod 2$

is independent of $X_{1}^{*},\ldots,X_{\ell-1}^{*}$. Note, however, that since
the $Z_{i}$s form a tree, there must be at least one of these variables that
includes a $Z_{i}$ not seen elsewhere, so we know that this variable is
independent of the rest. When we remove this variable, we then have a sub-
tree, so we can repeat the argument until we have shown that all the variables
are independent.

When we get to $X_{k}$ however, note that we have an invertible transformation
between the $X_{i}$s and the $Z_{i}$s, and since the $Z_{i}$s form a tree over
the $X_{i}$s, there is one fewer of them. It follows that the full collection
of $X_{i}$s is dependent. ∎

##  Appendix B Graphs

The first concept we will need is an extension to ADMGs in which we allow some
vertices to be ‘fixed’. We define the _siblings_ of a vertex to be its
neighbours via bidirected edges:

$\displaystyle\operatorname{sib}_{\mathcal{G}}(v)$
$\displaystyle\equiv\\{w:v\leftrightarrow w\text{ in }\mathcal{G}\\}.$

A CADMG $\mathcal{G}(V,W)$ is an ADMG with a set of _random_ vertices $V$ and
_fixed_ vertices $W$, with the property that
$\operatorname{sib}_{\mathcal{G}}(w)\cup\operatorname{pa}_{\mathcal{G}}(w)=\emptyset$
for every $w\in W$. An example can be found in Figure 10(b); note that we
depict fixed vertices with rectangular nodes, and random vertices with round
nodes. Random vertices in a CADMG correspond to random variables, as in
standard graphical models, while fixed vertices correspond to variables that
were fixed to a specific value by some operation, such as conditioning or
causal interventions. The genealogical relations in Section 2 generalize in a
straightforward way to CADMGs by ignoring the distinction between $V$ and $W$;
the only exception is that districts are only defined for random vertices, so
that the districts in the graph partition only $V$, rather than $V\cup W$.

###  B.1 Latent Projection

The _latent projection_ of a CADMG $\mathcal{G}(V\dot{\cup}L,W)$ to another
graph $\mathcal{G}^{\prime}(V,W)$ is given by following the rules:

  * •

if there is a directed path from $a\in V\cup W$ to $b\in V$, and any interior
vertices are in $L$, then add $a\rightarrow b$;

  * •

if there is a path between $a,b\in V$ without any adjacent arrowheads, and any
interior vertices are in $L$, that starts and ends with an arrow at $a$ and
$b$, then add $a\leftrightarrow b$.

As an example, consider the ADMG in Figure 8(a), with variable $h$ designated
as latent. Then the projection of this is given by the ADMG in Figure 8(b).

$h$$a$$b$$c$$d$(a)$a$$b$$c$$d$(b) Figure 8: (a) An ADMG in which $h$ is
latent; (b) its latent projection over $\\{a,b,c,d\\}$.

###  B.2 Arid Projection

######  Example B.1.

The _maximal arid projection_ of the ADMG $\mathcal{G}$ in Figure 9(a) is
given in 9(b). In the graph (a) we have $\langle
d\rangle_{\mathcal{G}}=\\{b,d\\}$, so $\operatorname{pa}_{\mathcal{G}}(\langle
d\rangle)=\\{a,b,c\\}$. As a result, in (b) all these vertices are parents of
$d$. In addition, $\langle\\{d,e\\}\rangle_{\mathcal{G}}=\\{b,c,d,e\\}$ which
is bidirected connected, so we add the edge $d\leftrightarrow e$ into (b). All
other adjacencies are as in (a).

$a$$b$$c$$d$$e$(a)$a$$b$$c$$d$$e$(b) Figure 9: (a) An ADMG $\mathcal{G}$ which
is neither maximal nor arid; (b) its maximal arid projection.

##  Appendix C The Nested Markov Model

###  C.1 Fixing

A vertex $r\in V$ is said to be _fixable_ in a CADMG $\mathcal{G}(V,W)$ if
$\operatorname{dis}_{\mathcal{G}}(r)\cap\operatorname{de}_{\mathcal{G}}(r)=\emptyset$.
For instance, the vertices $a$, $c$ and $d$ are all fixable in the graph in
Figure 10(a), but $b$ is not because $d$ is both its descendant and its
sibling.

For any $v\in V$, such that $\operatorname{ch}_{\mathcal{G}}(v)=\emptyset$,
the _Markov blanket_ of $v$ in a CADMG $\mathcal{G}$ is defined as

$\displaystyle\operatorname{mb}_{\mathcal{G}}(v)\equiv(\operatorname{dis}_{\mathcal{G}}(v)\cup\operatorname{pa}_{\mathcal{G}}(\operatorname{dis}_{\mathcal{G}}(v)))\setminus\\{v\\};$

that is, the set of vertices that are connected to $v$ by paths with an arrow
at $v$ and two arrowheads at each internal vertex. We can generalize this
definition to any vertex that is childless within its own district.

Given a CADMG $\mathcal{G}(V,W)$, and a fixable $r\in V$, the fixing operation
$\phi_{r}(\mathcal{G})$ yields a new CADMG
$\widetilde{\mathcal{G}}(V\setminus\\{r\\},W\cup\\{r\\})$ obtained from
$\mathcal{G}(V,W)$ by removing all edges of the form $\to r$ and
$\leftrightarrow r$, and keeping all other edges. Given a kernel
$q_{V}(x_{V}\,|\,x_{W})$ associated with a CADMG $\mathcal{G}(V,W)$, and a
fixable $r\in V$, the fixing operation $\phi_{r}(q_{V};\mathcal{G})$ yields a
new kernel

$\widetilde{q}_{V\setminus\\{r\\}}(x_{V\setminus\\{r\\}}\,|\,x_{W},x_{r})\equiv\frac{q_{V}(x_{V}\,|\,x_{W})}{q_{V}(x_{r}\,|\,x_{\operatorname{mb}_{\mathcal{G}}(r)})}.$

A result in Richardson et al. [2017] allows us to unambiguously define

$\displaystyle\phi_{R}(\mathcal{G})$
$\displaystyle\equiv\phi_{r_{k}}(\ldots\phi_{r_{2}}(\phi_{r_{1}}(\mathcal{G}))\ldots),$

and similarly the kernel $\phi_{R}(p;\mathcal{G})$ for distributions that are
nested Markov with respect to $\mathcal{G}$ (defined below). Consequently, we
just use sets to index fixings from now on.

If a fixing sequence exists for a set $R\subseteq V$ in $\mathcal{G}(V,W)$, we
say $V\setminus R$ is a _reachable set_. Such a set is called _intrinsic_ if
the vertices in $V\setminus R$ are bidirected-connected (so that
$\phi_{V\setminus R}(\mathcal{G})$ has only a single district); this
definition is equivalent to the definition in the main paper. We denote the
collections of reachable and intrinsic sets in $\mathcal{G}$ respectively by
${\cal R}(\mathcal{G})$ and ${\cal I}(\mathcal{G})$.

For a CADMG $\mathcal{G}(V,W)$, a (reachable) subset ${C}\subseteq{V}$ is
called a _reachable closure_ for ${S}\subseteq{C}$ if the set of fixable
vertices in $\phi_{V\setminus C}(\mathcal{G})$ is a subset of ${S}$. Every set
${S}$ in $\mathcal{G}$ has a unique reachable closure, which we denote
$\langle S\rangle_{\mathcal{G}}$ [Shpitser et al., 2018]. Note that this set
is generally a subset of what we earlier called the ‘closure’.

###  C.2 Nested Markov Model

We are now ready to define the nested Markov model
${\mathcal{M}}_{n}(\mathcal{G})$. Given an ADMG $\mathcal{G}$, we say that a
distribution $p$ obeys the _nested Markov property_ with respect to
$\mathcal{G}$ if for any reachable set $R$, we have that $\phi_{V\setminus
R}(p;\mathcal{G})$ factorizes into kernels as

$\displaystyle\phi_{V\setminus R}(p;\mathcal{G})$
$\displaystyle=\prod_{D\in\mathcal{D}(\phi_{V\setminus
R}(\mathcal{G}))}\phi_{V\setminus D}(p;\mathcal{G}).$

In other words, for any reachable graph, the associated kernel factorizes into
a product of the districts in that graph conditional on the parents of those
districts.

Note that this also means that $\phi_{V\setminus R}(p;\mathcal{G})$ will be
Markov with respect to the CADMG $\phi_{V\setminus R}(\mathcal{G})$ for each
reachable set $R$; see Richardson [2003] for more details on this.

######  Example C.1.

Consider the ADMG in Figure 10(a). The vertices $a$, $c$ and $d$ all satisfy
the condition of being fixable, but $b$ does not since $d$ is both a
descendant of, and in the same district as, $b$. The CADMG
$\mathcal{G}(\\{b,d\\},\\{a,c\\})$ obtained after fixing $a$ and $c$ is shown
in Figure 10(b). Notice that fixing $c$ removes the edge $b\to c$, but that
the edge $c\to d$ is preserved. Applying m-separation to the graph shown in
Figure 10(b), yields

$\displaystyle X_{d}\mathchoice{\mathrel{\hbox
to0.0pt{$\displaystyle\perp$\hss}\mkern
2.0mu{\displaystyle\perp}}}{\mathrel{\hbox
to0.0pt{$\textstyle\perp$\hss}\mkern 2.0mu{\textstyle\perp}}}{\mathrel{\hbox
to0.0pt{$\scriptstyle\perp$\hss}\mkern
2.0mu{\scriptstyle\perp}}}{\mathrel{\hbox
to0.0pt{$\scriptscriptstyle\perp$\hss}\mkern
2.0mu{\scriptscriptstyle\perp}}}X_{a}\mid
X_{c}\quad[\phi_{ac}(p(x_{abcd});\mathcal{G})].$

In addition, one can see easily that if an edge $a\to d$ had been present in
the original graph, then we would not have obtained this m-separation.

$a$$b$$c$$d$(a)$a$$b$$c$$d$(b) Figure 10: (a) An ADMG ${\cal G}$ that is not
ancestral; (b) a CADMG obtained from ${\cal G}$ in (a) by fixing $a$ and $c$.

###  C.3 Densely Connected Vertices

Here we give a couple of slightly more detailed examples than in the main
text.

######  Example C.2.

The vertices $a$ and $c$ in Figure 1(b) are ‘densely connected’, because they
cannot be separated by any combination of conditioning or fixing, except by
fixing $c$ (which just amounts to marginalizing it from the graph).
Separately, for ‘gadget’ graph in Figure 2(b) the vertices $c$ and $d$ are
also ‘densely connected’. Naturally, any pair of vertices joined by an edge is
also densely connected.

##  Appendix D Algorithms

###  D.1 Spanning Tree

Given a set $C$ and its subset of childless nodes $B$ (in our case this will
be either $\\{v\\}$ or $\\{v,w\\}$), pick a topological order on the vertices
that places all elements of $B$ at the end. Then, the last vertex before $B$
must be a parent of some element of $B$; pick the largest such element under
the topological order.

We then move backwards in the topological order, and each time a vertex has
more than one child, we join it to the vertex which has the shortest path to
an element of $B$; if there is a tie, then we pick the largest element under
the topological order. This ensures that each vertex is joined to $B$ by the
shortest possible directed path.

###  D.2 Difficult Graphs

Consider the graph shown in Figure 11. This can clearly be reduced to the
graph $w\to v$, but the application of Proposition 5.3 is computationally
difficult. Note that no subset will work apart from
$\\{z_{1},\ldots,z_{k}\\}$, and there are $3^{k}-1$ possible sets to choose.

Algorithm 1 (with complexity proven to be $O(|V|)$) can be applied instead and
will immediately return the graph $w\to v$.

$y_{1}$$z_{1}$$y_{2}$$z_{2}$$y_{3}$$z_{3}$$\dots$$\dots$$y_{k}$$z_{k}$$v$$w$
Figure 11: An ADMG for which a search for a set to satisfy Proposition 5.3 is
computationally difficult.


# Can Encrypted DNS Be Fast?

Austin Hounsel  Princeton University  ,  Paul Schmitt  Princeton Univeristy  ,
Kevin Borgolte  TU Delft  and  Nick Feamster  University of Chicago

###### Abstract.

In this paper, we study the performance of encrypted DNS protocols and
conventional DNS from thousands of home networks in the United States, over
one month in 2020. We perform these measurements from the homes of 2,768
participating panelists in the Federal Communications Commission’s (FCC)
Measuring Broadband America program. We found that clients do not have to
trade DNS performance for privacy. For certain resolvers, DoT was able to
perform faster than DNS in median response times, even as latency increased.
We also found significant variation in DoH performance across recursive
resolvers. Based on these results, we recommend that DNS clients (e.g., web
browsers) should periodically conduct simple latency and response time
measurements to determine which protocol and resolver a client should use. No
single DNS protocol nor resolver performed the best for all clients.

##  1\. Introduction

The Domain Name System (DNS) is responsible for translating human-readable
domain names (e.g., nytimes.com) to IP addresses. It is a critical part of the
Internet’s infrastructure that users must interact with before almost any
communication can occur. For example, web browsers may require tens to
hundreds of DNS requests to be issued before a web page can be loaded. As
such, many design decisions for DNS have focused on minimizing the response
times for requests. These decisions have in turn improved the performance of
almost every application on the Internet.

In recent years, privacy has become a significant design consideration for the
DNS. Research has shown that conventional DNS traffic can be passively
observed by network eavesdroppers to infer which websites a user is visiting
(Zhu et al., 2015; Bortzmeyer, 2015). This attack can be carried out by anyone
that sits between a user and their recursive resolver. As a result, various
protocols have been developed to send DNS queries over encrypted channels. Two
prominent examples are DNS-over-TLS (DoT) and DNS-over-HTTPS (DoH) (Hu et al.,
2016; Hoffman and McManus, 2018). DoT establishes a TLS session over port 853
between a client and a recursive resolver. DoH also establishes a TLS session,
but unlike DoT, all requests and responses are encoded in HTTP packets, and
port 443 is used. In both cases, a client sends DNS queries to a recursive
resolver over an encrypted transport protocol (TLS), which in turn relies on
the Transmission Control Protocol (TCP). Encrypted DNS protocols prevent
eavesdroppers from passively observing DNS traffic sent between users and
their recursive resolvers. From a privacy perspective, DoT and DoH are
attractive protocols, providing confidentiality guarantees that DNS lacked.

Past work has shown that typical DoT and DoH query response times are
typically marginally slower than DNS (Lu et al., 2019; Böttger et al., 2019;
Hounsel et al., 2020). However, these measurements were performed from
university networks, proxy networks, and cloud data centers, rather than
directly from homes. It is crucial to measure DNS performance from home
networks in situ, as they may be differently connected than other networks. An
early study on encrypted DNS performance was conducted by Mozilla at-scale
with real browser users, but they did not study DoT, and they did not explore
the effects of latency to resolvers, throughput, or Internet service provider
(ISP) choice on performance (McManus, 2018). Thus, the lack of controlled
measurements prevents the networking community from fully understanding how
encrypted DNS protocols perform for real users.

In this work, we provide a large-scale performance study of DNS, DoT, and DoH
from thousands of home networks dispersed across the United States. We perform
measurements from the homes of 2,768 participating panelists in the Federal
Communications Commission’s (FCC) Measuring Broadband America program from
April 7th, 2020 to May 8th, 2020. We measure query response times using
popular, open recursive resolvers, as well as resolvers provided by local
networks. We also use our dataset to study the effects of latency to resolvers
and throughput on query response times.

##  2\. Method

In this section, we outline our analyses and describe the measurement platform
we used to collect data. We then describe the experiments we conduct and their
limitations.

###  2.1. Analyses

We studied DNS, DoT, and DoH performance across several dimensions: connection
setup times, query response times for each resolver and protocol, and query
response times relative to latency to resolvers, throughput, and ISPs. Our
analyses are driven by choices that DNS clients are able to make (e.g., which
protocol and resolver to use) and how these choices affect DNS performance.

####  2.1.1. Connection Setup Times.

Before any query can be issued for DoT or DoH, the client must establish a TCP
connection and a TLS session. As such, we measure the time to complete a 3-way
TCP handshake and a TLS handshake. Additionally, for DoH, we measure the time
to resolve the domain name of the resolver itself. The costs associated with
connection establishment are amortized over many DoT or DoH queries as the
connections are kept alive and used repeatedly once they are open. We study
connection setup times in sec:connection.

####  2.1.2. DNS Response Times.

Query response times are crucial for determining the performance of various
applications. Before any resource can be downloaded from a server, a DNS query
often must be performed to learn the server’s IP address (assuming a response
is not cached). As such, we study query response times for each resolver and
protocol. We remove TCP and TLS connection establishment time from DoT and DoH
query response times. The DNS query tool we use closes and re-establishes
connections after ten queries (detailed in sec:measurement_protocol). As this
behavior is unlikely to mimic that of stub resolvers and web browsers (getdns
Team, 2019; Mozilla, 2020b, a), we remove connection establishment times to
avoid negatively biasing the performance of DoT and DoH.

While 41 Whiteboxes had latency measurements to cloud resolvers of up to 100
ms, they had median DNS query resolution times of less than 1 ms. We
investigated and found that this behavior can be attributed to DNS
interception by middleboxes between the client and the recursive resolver. For
example, customer-premises equipment can run DNS services (e.g., dnsmasq) that
can cache DNS responses to achieve such low query response times. Although we
were not able to verify this behavior in our data, SamKnows confirmed having
observed such behavior in previous measurements. Furthermore, previous reports
from the United Kingdom indicate that ISPs can provide customer-premises
equipment that is capable of passively observing and interfering with DNS
queries (Jackson, 2019). Additionally, 29 of the 41 Whiteboxes are connected
to the Internet by the same ISP. We also identified two Whiteboxes that
reported median latencies to DoH resolvers below 1 ms, and one Whitebox that
reported a median DNS response time below 1 ms for DoT resolvers.

####  2.1.3. DNS Response Times Relative to Latency and Throughput.

Conventional DNS performance depends on latency, as the protocol is relatively
lightweight; therefore, latency to the DNS resolver can have a significant
effect on overall performance. Furthermore, encrypted DNS protocols may
perform differently than conventional DNS in response to higher latency, as
they are connection-oriented protocols. We study the effect of latency on
query response times for each open resolver and protocol in
sec:networkperformance. SamKnows also provides us with the subscribed
downstream and upstream throughput for each Whitebox. We use this information
to study the effect of downstream throughput on query response times in
sec:networkperformance.

####  2.1.4. DNS Response Times Relative to ISP Choice.

Lastly, SamKnows provides us with the ISP for each Whitebox. We study query
response times for a selection of ISPs in sec:isp_comparison.

###  2.2. Measurement Platform

Our measurements were performed continuously over 32 days from April 7th, 2020
through May 8th, 2020 in collaboration with SamKnows and the FCC. The FCC
contracts with SamKnows (SamKnows, 2020b) to implement the operational and
logistical aspects of the Measuring Broadband America (MBA) program (Federal
Communications Commission, 2020b). SamKnows specializes in developing custom
software and hardware (also known as “Whiteboxes”) to evaluate the performance
of broadband access networks. Whiteboxes act as Ethernet bridges that connect
directly to existing modems/routers, which enables us to control for poor Wi-
Fi signals and cross-traffic. In collaboration with the FCC, SamKnows has
deployed Whiteboxes to thousands of volunteers’ homes across the United
States. We were granted access to the MBA platform through the FCC’s MBA-
Assisted Research Studies program (MARS) (Federal Communications Commission,
2020a), which enables researchers to run measurements from the deployed
Whiteboxes. We utilize the platform to evaluate how DNS, DoT, and DoH perform
from home networks across the United States.

Resolver | Observations | Min Latency (ms) | Median Latency (ms) | Max Latency (ms) | Std Dev (ms)
---|---|---|---|---|---
X DNS and DoT | 1,593,506 | 0.94 | 20.38 | 5,935.80 | 43.61
X DoH | 1,567,337 | 0.14 | 22.75 | 8,929.88 | 43.25
Y DNS and DoT | 1,596,964 | 2.00 | 20.90 | 9,701.82 | 46.79
Y DoH | 1,552,595 | 0.14 | 20.50 | 10,516.31 | 40.68
Z DNS and DoT | 1,579,605 | 2.35 | 31.41 | 516,844.73 | 414.26
Z DoH | 1,533,380 | 0.14 | 33.00 | 9,537.42 | 41.11
Default DNS | 2,009,086 | 0.13 | 0.85 | 8,602.39 | 22.93
Table 1. Recursive resolver latency characteristics.

In total, we collected measurements from 2,825 Whiteboxes, each of which use
the latest generation of hardware and software (8.0) (SamKnows, 2020c). We
removed 26 Whiteboxes from our analysis that were connected over satellite and
1 Whitebox that we did not know the access technology for. We also removed 30
Whiteboxes from our analysis for which we did not know the ISP speed tier.
This left us with 2,768 Whiteboxes to analyze. Overall, 96% of queries were
marked as successful, and 3.5% of queries were marked as failures with an
NXDOMAIN response.

The SamKnows DNS query tool reports a success/failure status (and failure
reason, if applicable), the DNS resolution time excluding connection
establishment (if the query was successful), and the resolved record
(SamKnows, 2020a). For DoT and DoH, the tool separately reports the TCP
connection setup time, the TLS session establishment time, and the DoH
resolver lookup time. For this study, we only study queries for ’A’ and ’AAAA’
records. We note that DoH queries are asynchronous, functionality that is
enabled by the underlying HTTP protocol, but DNS and DoT queries are
synchronous.

The query tool handles failures in several ways. First, if a response with an
error code is returned from a recursive resolver (e.g., NXDOMAIN or SERVFAIL),
then the matching query is marked as a failure. Second, if the tool fails to
establish a DoT or DoH connection, then all queries in the current batch
(explained in sec:experiment) are marked as failures. Third, the query tool
times out conventional DNS queries after three seconds, at which point it re-
sends them. If three timeouts occur for a given query, the tool marks the
query as a failure. Finally, lost DoT and DoH queries rely on the re-
transmission policy of the underlying TCP protocol, rather than a fixed timer.
If TCP hits the maximum number of re-transmissions allowed by the operating
system’s kernel, then the query is marked as a failure.

###  2.3. Experiment Design

We describe below our experiment design and the steps we take to perform
measurements.

####  2.3.1. DNS Resolvers.

For each Whitebox, we perform measurements using three popular open recursive
DNS resolvers (anonymized as X, Y, and Z, respectively111We anonymize the
resolvers as per our agreement with the FCC.), as well as the recursive
resolver automatically configured on each Whitebox (the “default” resolver).
Typically, the default resolver is set by the ISP that the Whitebox is
connected to. Resolvers X, Y, and Z all offer public name resolution for DNS,
DoT, and DoH. The default resolvers typically only support DNS, so we do not
measure DoT or DoH with them.

In tab:latency, we include the latency to each recursive resolver across all
clients in the dataset. We measure latency by running five ICMP ping tests for
each resolver at the top of each hour. We separate latency to DoH resolvers
from latency to DNS and DoT resolvers because the domain names of DoH
resolvers must be resolved in advance. As such, the IP addresses for the DoH
resolvers are not always the same as DNS and DoT resolvers. We note that the
latencies for the default resolvers are particularly low because they are
often DNS forwarders that are configured on home routers.

####  2.3.2. Domain Names.

Our goal was to collect DNS query response times for domain names found in
websites that users are likely to visit. We first selected the top 100
websites in the Tranco top-list, which averages the rankings of websites in
the Alexa top-list over time (L. Pochat et al., 2019). We extracted the domain
names of all included resources found on each homepage. We obtained this data
from HTTP Archive Objects (or “HARs”) that we collected from a previous study.

Importantly, we needed to ensure that the domain names were not sensitive in
nature (e.g., pornhub.com) so as to not trigger DNS-based parental controls.
As such, after we created our initial list of domain names, we used the
Webshrinker API to filter out domains associated with adult content, illegal
content, gambling, and uncategorized content (Webshrinker, 2020). We then
manually reviewed the resulting list. In total, our list included 1,712 unique
domain names.222This list will be made publicly available upon publication.

####  2.3.3. Measurement Protocol.

(a) DoH Resolver Lookup

(b) TCP Connect Time

(c) TLS Setup Time

Figure 1. Connection setup times for DoT and DoH.

The steps we take to measure query response times from each Whitebox are as
follows:

  1. (1)

We randomize the input list of 1,712 domain names at the start of each hour.

  2. (2)

We compute the latency to each resolver with a set of five ICMP ping tests.

  3. (3)

We begin iterating over the randomized list by selecting a batch containing
ten domain names.

  4. (4)

We issue queries for all 10 domain names in the batch to each resolver /
protocol combination. For DoT and DoH, we re-use the TLS connection for each
query in the batch, and then close the connection. If a batch of queries has
not completed within 30 seconds, we pause, check for cross-traffic, and retry
if cross-traffic is present. If there is no cross traffic, we move to the next
resolver/protocol combination.

  5. (5)

We select the next batch of 10 domain names. If five minutes have passed, we
stop for the hour. Otherwise, we return to step four.

####  2.3.4. Limitations.

Due to bandwidth usage concerns and limited computational capabilities on the
Whiteboxes, we do not collect web page load times while varying the underlying
DNS protocol and resolver. Additionally, while we conducted our measurements,
the COVID-19 pandemic caused many people to work from home. We did not want to
perturb other measurements being run with the Measuring Broadband America
platform or introduce excessive strain on the volunteers’ home networks. Due
to these factors, we focus on DNS response times.

Figure 2. Aggregate query response times across all Whiteboxes.

##  3\. Results

This section presents the results of our measurements. We organize our results
around the following questions: (1) How much connection overhead does
encrypted DNS incur, in terms of resolver lookup (in the case of DoH), TCP
connect time, and TLS setup time; (2) How does encrypted DNS perform versus
conventional DNS?; (3) How does latency affect encrypted DNS performance?; and
(4) How does encrypted DNS resolver performance depend on broadband access
ISP? Our results show that in the case of certain resolvers—to our
surprise—DoT had lower median response times than conventional DNS, even as
latency to the resolver increases. We also found significant variation in DoH
performance across resolvers. We then compare how DoT and DoH perform compared
to conventional DNS. Finally, we analyze how each protocol performs as latency
to a given resolver increases.

(a) Resolver X

(b) Resolver Y

(c) Resolver Z

Figure 3. DNS response times based on median latency to resolvers.

###  3.1. How Much Connection Overhead Does Encrypted DNS Incur?

We first study the overhead incurred by encrypted DNS protocols, due to their
requirements for TCP connection setup and TLS handshakes. Before any batch of
DoT queries can be issued with the SamKnows query tool, a TCP connection and
TLS session must be established with a recursive resolver. In the case of DoH,
the IP address of the resolver must also be looked up (e.g., resolverX.com).
In fig:dot_doh_setup_times, we show timings for different aspects of
connection establishment for DoT and DoH. The results show that lookup times
were similar for all three resolvers (fig:doh_resolver_lookup_time). This
result is expected because the same default, conventional DNS resolver is used
to look up the DoH resolvers’ domain names; the largest median DoH resolver
lookup time was 17.1 ms. Depending on the DNS time to live (TTL) of the DoH
resolver lookup, resolution of the DoH resolver may occur frequently or
infrequently.

Next, we study the TCP connection establishment time for DoT and DoH for each
of the three recursive resolvers (fig:tcp_connect_time). For each of the three
individual resolvers, TCP establishment time for DoT and DoH are similar.
Resolvers X and Y are similar; Z experienced longer TCP connection times. The
largest median TCP connection establishment time across all resolvers and
protocols (Resolver Z DoH) was 30.8 ms.

Because DoT and DoH rely on TLS for encryption, a TLS session must be
established before use. fig:tls_connect_time shows the TLS establishment time
for the three open resolvers. Again, Resolver Z experienced higher TLS setup
times compared to X and Y. Furthermore, DoT and DoH performed similarly for
each resolver. The largest median TLS connection establishment time across all
recursive resolvers and protocols (Resolver Z DoH) was 105.2 ms. As with
resolver lookup overhead, the cost of establishing a TCP and TLS connection to
the recursive resolver for a system would ideally occur infrequently, and
should be amortized over many queries by keeping the connection alive and
reusing it for multiple DNS queries.

Connection-oriented, secure DNS protocols will incur additional latency, but
these costs can be (and are) typically amortized by caching the DNS name of
the DoH resolver, as well as multiplexing many DNS queries over a single TLS
session to a DoH resolver. Many browser implementations of DoH implement these
practices. For example, Firefox establishes a DoH connection when the browser
launches, and it leaves the connection open (Mozilla, 2020b, a). Thus, the
overhead for DoH connection establishment in Firefox is amortized.

In the remainder of this paper we do not include connection establishment
overhead when studying DNS query response times. We omit connection
establishment time for the rest of our analysis because the DNS query tool
closes and reopens connections for each batch of queries. Thus, inclusion of
TCP and TLS connection overheads may negatively skew query response times.

(a) Resolver X

(b) Resolver Y

(c) Resolver Z

Figure 4. Ridge regression models comparing median latency to resolvers to
median DNS response times (alpha = 1).

###  3.2. How Does Encrypted DNS Perform Compared With Conventional DNS?

We next compare query response times across each protocol and recursive
resolver. fig:overall_dns_timings shows box plots for DNS response times
across all Whiteboxes for each resolver and protocol. “Default” refers to the
resolver that is configured by default on each Whitebox (which might typically
be the DNS resolver operated by the Whitebox’s upstream ISP).

##### DNS performance varies across resolvers.

First of all, conventional DNS performance varies across recursive resolvers.
For the default resolvers configured on Whiteboxes, the median query response
time using conventional DNS is 24.8 ms. For Resolvers X, Y, and Z, the median
query response times using DNS are 23.2 ms, 34.8 ms, and 38.3 ms,
respectively. Although X performs better than the ISP default resolvers, Y and
Z perform at least 10 ms slower. This variability could be attributed to
differences in deployments between open resolvers.

##### DoT performance nearly matches conventional DNS.

Interestingly DoT lookup times are close to those of conventional DNS. For
Resolvers X, Y, and Z, the median query response times for DoT are 20.9 ms,
32.2 ms, and 45.3 ms, respectively. Interestingly, for X and Y, we find that
DoT performs 2.3 ms and 2.6 ms _faster_ than conventional DNS, respectively.
For both of these resolvers, the best median DNS query performance could be
attained using DoT. Z’s median response time was 7 ms slower. The performance
improvement of DoT over conventional DNS in some cases is interesting because
conventional wisdom suggests that the connection overhead of TCP and TLS would
be prohibitive. On the other hand, various factors, including transport-layer
optimizations in TCP, as well as differences in infrastructure deployments,
could explain these discrepancies. Explaining the causes of these
discrepancies is an avenue for future work.

Resolver | Coefficient | Intercept | MAE | MSE
---|---|---|---|---
X DNS | 0.79 | 6.07 | 3.84 | 66.37
X DoT | 0.72 | 7.65 | 4.59 | 45.18
X DoH | 1.28 | 19.75 | 11.90 | 255.70
Y DNS | 0.76 | 13.42 | 7.29 | 131.38
Y DoT | 0.81 | 14.17 | 9.39 | 218.30
Y DoH | 1.51 | 19.34 | 11.43 | 726.25
Z DNS | 0.92 | 5.02 | 4.61 | 211.30
Z DoT | 0.89 | 10.38 | 6.03 | 83.39
Z DoH | 1.54 | 11.26 | 15.36 | 549.99
Table 2. Coefficients, intercepts, mean absolute errors (MAE), and mean
squared errors (MSE) for ridge regression models.

##### DoH response times were higher than those for DNS and DoT.

DoH experienced higher response times than conventional DNS or DoT, although
this difference in performance varies significantly across DoH resolvers. For
Resolvers X, Y, and Z, the median query response times for DoH are 37.7 ms,
46.7 ms, and 60.7 ms, respectively. Resolver Z exhibited the biggest increase
in response latency between DoH and DNS (22.4 ms). Resolver Y showed the
smallest difference in performance between DoH and DNS (11.9 ms). Median DoH
response times between resolvers can differ greatly, with X DoH performing 23
ms faster than Z DoH. The performance cost of DoH may be due to the overhead
of HTTPS, as well as the fact that DoH implementations are still relatively
nascent, and thus may not be optimized. For example, an experimental DoH
recursive resolver implementation by Facebook engineers simply terminates DoH
connections to a reverse web proxy before forwarding the query to a
conventional DNS recursive resolver (Facebook Experimental, 2020).

###  3.3. How Does Network Performance Affect Encrypted DNS Performance?

We next study how network latency and throughput characteristics affect the
performance of encrypted DNS.

##### DoT can meet or beat conventional DNS despite high latencies to
resolvers, offering privacy benefits for no performance cost.

fig:median_latency_dns_timings, shows that DoT performs better than DNS as
latency increases for Resolver X; in the case of Resolvers Y and Z, DoT nearly
matches the performance of conventional DNS. We observe similar behavior with
the linear ridge regression models shown in fig:latency_rtt_regression. This
result can be explained by the fact that the cost of symmetric encryption is
small compared to network latency.

##### DoH performs worse than conventional DNS and DoT as latencies to
resolvers increase.

fig:median_latency_dns_timings shows that DoH performs substantially worse
when latency between the client and recursive resolver is high;
fig:latency_rtt_regression shows a similar result with a ridge regression
model. As discussed in sec:protocolperformance, this result could be explained
by either HTTPS overhead, nascent DoH implementations and deployments, or
both.

(a) Default

(b) Resolver X

(c) Resolver Y

(d) Resolver Z

Figure 5. Query response times based on downstream access ISP throughput.

##### Subscribed throughput affects DNS performance.

fig:package_down_dns_timings shows DNS response times across each of the open
resolvers as well as the default resolver. We group the downstream throughput
into four bins using clustering based on kernel density estimation. The
performance for all protocols tends to improve as downstream throughput
increases, with DoH experiencing the most relative improvement. For example,
for users with downstream throughput that is less than 25 Mbps, the median
query response times for Resolver Y DoH and Y DNS are 75.2 ms and 48.9 ms,
respectively. As throughput increases from 25 Mbs to 400 Mbps, the median
query response times for Y DoH and Y DNS are 41.2 ms and 31.4 ms,
respectively. DoT performs similarly to conventional DNS regardless of
downstream throughput. Across all groups, the absolute performance difference
between Resolver X DoT and X DNS by 0.3 ms, 1.9 ms, 0.1 ms, and 1.4 ms,
respectively. For Resolver Y, DoT again performs faster than DNS in median
query response times when throughput is less than 800 Mbps. At lower
throughputs, Y DoT performs faster than Y DNS by 1.4 ms, 2.5 ms, and 1.7 ms
for each respective protocol.

###  3.4. Does Encrypted DNS Resolver Performance Vary Across ISPs?

(a) Resolver X

(b) Resolver Y

(c) Resolver Z

Figure 6. Per-ISP query response times.

fig:isp_timings shows how encrypted DNS response times vary across different
resolvers and ISPs. In short, the choice of resolver matters, and the “best”
encrypted DNS resolver also may depend on the user’s ISP. For instance, while
ISP C is comparable to the other ISPs for queries sent to Resolver X, ISP C
has significantly lower query response times to Resolver Y, and is one of the
poorest performing ISPs on Resolver Z. The difference in median query response
times between Resolver X DoH and X DNS was 20.9 ms for customers on ISP D, and
8.9 ms for customers on ISP E; for Z DoH, the difference in median times was
34.6 ms for customers on ISP D, and 48 ms for customers on ISP E.

Resolver performance can also differ across ISPs. For ISP B, the median query
response time for Z DoT is 11 ms faster than Z DNS. However, for ISP C, Z DoT
is significantly slower than DNS, with a difference of 30.7 ms. We attribute
this difference in performance to high latency to Resolver Z via ISP C. The
average latency to Z across cable customers on ISP C was 54.3 ms, as compared
to 26.5 ms across cable customers on ISP B.

##  4\. Related Work

Researchers have compared the performance of DNS, DoT, and DoH in various
ways. Zhu et al. proposed DoT to encrypt DNS traffic between clients and
recursive resolvers (Zhu et al., 2015). They modeled its performance and found
that DoT’s overhead can be largely eliminated with connection re-use. Böttger
et al. measured the effect of DoT and DoH on query response times and page
load times from a university network (Böttger et al., 2019). They find that
DNS generally outperforms DoT in query response times, and DoT outperforms
DoH. Hounsel et al. also measure query response times and page load times for
DNS, DoT, and DoH using Amazon EC2 instances (Hounsel et al., 2020). They find
that despite higher query response times, page load times for DoT and DoH can
be _faster_ than DNS on lossy networks. Lu et al. utilized residential TCP
SOCKS proxy networks to measure query response times from 166 countries and
found that, in the median case with connection re-use, DoT and DoH queries
were slower than DNS over TCP by 9 ms and 6 ms, respectively (Lu et al.,
2019).

Researchers have also studied in depth how DNS influences application
performance. Sundaresan et al. use a deployment of 4,200 home gateways by
SamKnows and the FCC to identify performance bottlenecks for residential
broadband networks (Sundaresan et al., 2013). This study found that page load
times for users in home networks are significantly influenced by slow DNS
response times. Wang et al. introduced WProf, a profiling system that analyzes
factors that contribute to page load times (Wang et al., 2013). They found
that queries for uncached domain names at recursive resolvers can account for
up to 13% of the critical path delay for page loads. Otto et al. found that
CDN performance was significantly affected by clients choosing recursive
resolvers that are far away from CDN caches (Otto et al., 2012). As a result,
Otto et al. proposed namehelp, a DNS proxy that sends queries for CDN-hosted
content to directly to authoritative servers. Allman studied conventional DNS
performance from 100 residences in a neighborhood and found that only 3.6% of
connections were blocked on DNS with lookup times greater than either 20 ms or
1% of the application’s transaction time (Allman, 2020).

Past work studied the performance impact of “last mile” connections to home
networks in various ways. Kreibich et al. proposed Netalyzr as a Java applet
that users run from devices in their home networks to test debug their
Internet connectivity. Netalyzr probes test servers outside of the home
network to measure latency, IPv6 support, DNS manipulation, and more. Their
system was run from over 99,000 public IP addresses, which enabled them to
study network connectivity at scale (Kreibich et al., 2010). Dischinger et al.
measured bandwidth, latency, and packet loss from 1,894 hosts and 11 major
commercial cable and DSL providers in North America and Europe. This work
found that the “last mile” connection between an ISP and a home network is
often a performance bottleneck, which they could not have captured by
performing measurements outside of the home network. However, their
measurements were performed from hosts located within homes, rather than the
home gateway. This introduces confounding factors between hosts and the home
gateway, such as poor Wi-Fi performance.

##  5\. Conclusion

In this paper, we studied the performance of encrypted DNS protocols and DNS
from 2,768 home networks in the United States, between April 7th 2020 and May
8th 2020. We found that clients do not have to trade DNS performance for
privacy. For certain resolvers, DoT was able to perform faster than DNS in
median response times, even as latency increased. We also found significant
variation in DoH performance across recursive resolvers. Based on these
results, we recommend that DNS clients (e.g., web browsers) measure latency to
resolvers and DNS response times determine which protocol and resolver a
client should use. No single DNS protocol nor resolver performed the best for
all clients.

There were some limitations to our work that point to future research. First,
due to bandwidth restrictions, we were unable to perform page loads from the
Whiteboxes. Future work could utilize a platform of similar scale to SamKnows
to perform page loads, such as telemetry from browser vendors. Second, future
work should perform measurements from mobile devices. DoT was implemented in
Android 10, but to our knowledge, its performance has not been studied ”in the
wild.” Finally, future work could study how encrypted DNS protocols perform
from networks that are especially far away from popular recursive resolvers.
This is particularly important for web browsers that deploy DoH to users
outside of the United States.

## References

  * (1)
  * Allman (2020) Mark Allman. 2020\.  Putting DNS in Context. In _Proceedings of the 2020 Internet Measurement Conference (IMC)_ (20 ed.) (2020-10), Nicolas Chritin, Konstantinos Pelechrinis, and Vyas Sekar (Eds.). Association for Computing Machinery (ACM), Virtual Event, 1–8.
  * Bortzmeyer (2015) Stephane Bortzmeyer. 2015\.  _DNS Privacy Considerations_.  RFC 7626. RFC Editor.  http://www.ietf.org/rfc/rfc7626.txt (Informational).
  * Böttger et al. (2019) Timm Böttger, Felix Cuadrado, Gianni Antichi, Eder Leao Fernandes, Gareth Tyson, Ignacio Castro, and Steve Uhlig. 2019.  An Empirical Study of the Cost of DNS-over-HTTPS. In _Proceedings of the 2019 Internet Measurement Conference_ (19 ed.) (2019-10), Anna Sperotto, Roland van Rijswijk-Deij, and Cristian Hesselman (Eds.). Association for Computing Machinery (ACM), Amsterdam, Netherlands, 15–21.  https://doi.org/10.1145/3355369.3355575
  * Facebook Experimental (2020) Facebook Experimental. 2020\.  DOH Proxy.  https://facebookexperimental.github.io/doh-proxy/
  * Federal Communications Commission (2020a) Federal Communications Commission. 2020a.  MBA Assisted Research Studies.  https://www.fcc.gov/general/mba-assisted-research-studies
  * Federal Communications Commission (2020b) Federal Communications Commission. 2020b.  Measuring Broadband America.  https://www.fcc.gov/general/measuring-broadband-america
  * getdns Team (2019) getdns Team. 2019\.  getdns/stubby.  https://github.com/getdnsapi/stubby
  * Hoffman and McManus (2018) Paul Hoffman and Patrick McManus. 2018.  _DNS Queries over HTTPS (DoH)_.  RFC 8484. RFC Editor.  http://www.ietf.org/rfc/rfc8484.txt (Proposed Standard).
  * Hounsel et al. (2020) Austin Hounsel, Kevin Borgolte, Paul Schmitt, Jordan Holland, and Nick Feamster. 2020.  Comparing the Effects of DNS, DoT, and DoH on Web Performance. In _Proceedings of the 28th The Web Conference (WWW)_ (28 ed.) (2020-04), Yennun Huang, Irwin King, Tie-Yan Liu, and Maarten van Steen (Eds.). Association for Computing Machinery (ACM), Taipei, Taiwan, 562–572.  https://doi.org/10.1145/3366423.3380139
  * Hu et al. (2016) Zi Hu, Liang Zhu, John Heidemann, Allison Mankin, Duane Wessel, and Paul Hoffman. 2016\.  _Specification for DNS over Transport Layer Security (TLS)_.  RFC 7858. RFC Editor.  http://www.ietf.org/rfc/rfc7858.txt (Proposed Standard).
  * Jackson (2019) Mark Jackson. 2019\.  Firmware Update for UK Sky Broadband ISP Routers Botches DNS UPDATE.  https://www.ispreview.co.uk/index.php/2019/04/firmware-update-for-uk-sky-broadband-isp-routers-botches-dns.html
  * Kreibich et al. (2010) Christian Kreibich, Nicholas Weaver, Boris Nechaev, and Vern Paxson. 2010.  Netalyzr: illuminating the edge network. In _Proceedings of the 10th ACM SIGCOMM Conference on Internet Measurement (IMC)_ (10 ed.) (2010-11), Mark Allman (Ed.). Association for Computing Machinery (ACM), Melbourne, Australia, 246–259.  https://doi.org/10.1145/1879141.1879173
  * L. Pochat et al. (2019) Victor L. Pochat, Tom V. Goethem, Samaneh Tajalizadehkhoob, Maciej Korczyński, and Wouter Joosen. 2019.  Tranco: A Research-Oriented Top Sites Ranking Hardened Against Manipulation. In _Proceedings of the 26th Network and Distributed System Security Symposium (NDSS)_ (26 ed.) (2019-02), Alina Oprea and Dongyan Xu (Eds.). Internet Society (ISOC), San Diego, CA, USA, 1–15.  https://doi.org/10.14722/ndss.2019.23386
  * Lu et al. (2019) Chaoyi Lu, Baojun Liu, Zhou Li, Shuang Hao, Haixin Duan, Mingming Zhang, Chunying Leng, Ying Liu, Zaifeng Zhang, and Jianping Wu. 2019\.  An End-to-End, Large-Scale Measurement of DNS-over-Encryption: How Far Have We Come?. In _Proceedings of the 2019 Internet Measurement Conference_ (19 ed.) (2019-10), Anna Sperotto, Roland van Rijswijk-Deij, and Cristian Hesselman (Eds.). Association for Computing Machinery (ACM), Amsterdam, Netherlands, 22–35.  https://doi.org/10.1145/3355369.3355580
  * McManus (2018) Patrick McManus. 2018\.  Firefox Nightly Secure DNS Experimental Results.  https://blog.nightly.mozilla.org/2018/08/28/firefox-nightly-secure-dns-experimental-results/
  * Mozilla (2020a) Mozilla. 2020a.  All.js.  https://searchfox.org/mozilla-central/source/modules/libpref/init/all.js#1425
  * Mozilla (2020b) Mozilla. 2020b.  TRRServiceChannel.cpp.  https://searchfox.org/mozilla-central/source/netwerk/protocol/http/TRRServiceChannel.cpp#512
  * Otto et al. (2012) John S. Otto, Mario A. Sánchez, John P. Rula, and Fabián E. Bustamante. 2012.  Content Delivery and the Natural Evolution of DNS: Remote DNS Trends, Performance Issues and Alternative Solutions. In _Proceedings of the 2012 Internet Measurement Conference (IMC)_ (12 ed.) (2012-11), Ratul Mahajan and Alex Snoeren (Eds.). Association for Computing Machinery (ACM), Boston, MA, USA, 523–536.  https://doi.org/10.1145/2398776.2398831
  * SamKnows (2020a) SamKnows. 2020a.  DNS resolution.  https://samknows.com/technology/tests/dns-resolution
  * SamKnows (2020b) SamKnows. 2020b.  SamKnows.  https://www.samknows.com/
  * SamKnows (2020c) SamKnows. 2020c.  SamKnows Whitebox.  https://samknows.com/technology/agents/samknows-whitebox#specifications
  * Sundaresan et al. (2013) Srikanth Sundaresan, Nick Feamster, Renata Teixeira, and Nazanin Magharei. 2013.  Measuring and Mitigating Web Performance Bottlenecks in Broadband Access Networks. In _Proceedings of the 2013 Internet Measurement Conference (IMC)_ (13 ed.) (2013-10), Krishna Gummadi and Craig Partidge (Eds.). Association for Computing Machinery (ACM), Barcelona, Spain, 213–226.  https://doi.org/10.1145/2504730.2504741
  * Wang et al. (2013) Xiao Sophia Wang, Aruna Balasubramanian, Arvind Krishnamurthy, and David Wetherall. 2013.  Demystifying Page Load Performance with WProf. In _Proceedings of the 10th USENIX Symposium on Networked Systems Design and Implementation (NSDI)_ (10 ed.) (2013-04), Nick Feamster and Jeff Mogul (Eds.). USENIX Association, Lombard, IL, USA, 473–487.  https://www.usenix.org/conference/nsdi13/technical-sessions/presentation/wang_xiao
  * Webshrinker (2020) Webshrinker. 2020\.  APIs - Webshrinker.  https://www.webshrinker.com/apis/
  * Zhu et al. (2015) Liang Zhu, Zi Hu, John Heidemann, Duane Wessels, Allison Mankin, and Nikita Somaiya. 2015\.  Connection-oriented DNS to Improve Privacy and Security. In _Proceedings of the 36th IEEE Symposium on Security & Privacy (S&P)_ (36 ed.) (2015-05), Vitaly Shmatikov and Lujo Bauer (Eds.). Institute of Electrical and Electronics Engineers (IEEE), San Jose, CA, USA, 171–186.  https://doi.org/10.1109/sp.2015.18