General theory for stochastic admixture graphs and F-statistics

Samuele Soraggi 111Department of Biology, University of Copenhagen, Carsten
Wiuf 222Department of Mathematical Sciences, University of
Copenhagen333Corresponding author. Email<EMAIL_ADDRESS>
July 18, 2018

————————————————————————————————–

Abstract: We provide a general mathematical framework based on the theory of
graphical models to study admixture graphs. Admixture graphs are used to
describe the ancestral relationships between past and present populations,
allowing for population merges and migration events, by means of gene flow. We
give various mathematical properties of admixture graphs with particular focus
on properties of the so-called $F$-statistics. Also the Wright-Fisher model is
studied and a general expression for the loss of heterozygosity is derived.

Keywords: introgression, genetic drift, Wright-Fisher model, heterozygosity,
F-statistic, Markov graphical model. MSC: 92D15, 92D25.

————————————————————————————————–

##  1 Introduction

Inference on human demographic history from a genetic perspective has been a
topic of wide interest in population genetics [2, 3, 16, 7, 13, 18, 17].
Methods for the assessment of migration between populations, and the
identification of admixture and splitting events have recently been proposed
based on the study of gene flow and introgression between populations [16, 13,
14]. The postulated demographic relationships between populations are
described by a graph, generally referred to as an admixture graph, where each
node represents a population, ancient or extant, and each directed edge
represents an ancestral relationship between two populations. Allele
frequencies or other genetic quantities characterising the populations are
associated to the nodes, thereby creating, what we name, a stochastic
admixture graph. The difference in allele frequencies between two nodes
quantifies the gene flow between the two populations represented by the nodes.

The goal of this paper is to provide a stringent mathematical definition and
treatment of stochastic admixture graphs and their properties. We use the
theory of graphical models [6, 10, 19] to develop a general mathematical
framework to describe stochastic admixture graphs and their associated
variables (such as gene frequencies). In the literature stochastic admixture
graphs and their properties are often studied with a particular population
genetic model in mind. We abstract properties that generalise properties of
particular models, using the theory of graphical models.

Many popular computational tools, building on admixture graphs, quantify
similarities in genetic composition between populations by means of moment
statistics, called $F$-statistics [13, 16, 14]. These tools rely on properties
of the $F$-statistics that are not always motivated, but nonetheless have
proven essential to disentangle complicated genetic ancestries of populations
[1, 13, 15, 11]. We deduce general properties of the $F$-statistics, in
particular the $F_{2}$-statistic, and show that the $F$-statistics can be
decomposed in terms of the admixture paths between populations. Furthermore,
we give conditions under which the $F_{2}$-statistic is additive (in a sense
to be made precise later) and forms a metric on the nodes of the graph. In the
final section of the paper, we consider the Wright-Fisher diffusion model and
give a general formula for the decline of heterozygosity over time in a
stochastic admixture graph.

We envisage that the general theory developed here and the vast amount of
exiting literature on model selection and inference on graphical models will
be useful to understand inferential properties of stochastic admixture graphs,
what can be done and how. All proofs are given in the appendix.

##  2 Admixture graphs

We consider labeled graphs with _directed_ and _undirected_ edges, and use the
notations $i\leftrightarrow j$ (equivalently $j\leftrightarrow i$) and $i\to
j$ (equivalently $j\leftarrow i$) for an undirected edge between two nodes $i$
and $j$, and a directed edge from $i$ to $j$, respectively. An edge $i\to j$
is said to be ingoing to $j$ and outgoing of $i$. The _parents_ of $j$ is the
set $par(j)=\\{i\,|\,i\to j\,\,\text{is an edge}\\}$. The node $i$ is a
_child_ of $j$ if $j$ is a parent of $i$.

######  Definition 1.

An _admixture graph_ is an edge labeled graph
$\mathcal{G}=(\mathcal{V},\mathcal{E},\mathcal{L})$ without directed cycles.
The triplet consists respectively of the set of nodes, edges and labels. The
set of nodes $\mathcal{V}$ is divided into:

  * (i)

_roots_ $\mathcal{R}$, nodes without ingoing edges. All pairs of roots, and
only these, are connected by an undirected edge,

  * (ii)

_admixed nodes_ $\mathcal{A}$, nodes with ingoing directed edges,

  * (iii)

_leaves_ $\mathcal{A}_{0}\subseteq\mathcal{A}$, admixed nodes without outgoing
directed edges.

The label $\alpha_{ij}$ of an edge $i\to j$ is positive and fulfils

$\sum\limits_{i\in par(j)}\alpha_{ij}=1.$ (1)

An edge between two roots $r_{1},r_{2}\in\mathcal{R}$ has label
$\alpha_{r_{1}r_{2}}=1$.

In the genetic context, an admixed node, say $j$, represents a population that
is a mixture of several populations, such that $100\alpha_{ij}$ percent of the
size of population comes from population $i$, $i\in par(j)$. The roots
represents populations that are ancestral to the other populations in the
graph, whereas the ancestral relationship between the root populations are
assumed unknown and left unspecified.

By definition, an admixture graph is connected. We assume an admixture graph
is not trivial, meaning that it does not consist of only roots and undirected
edges. For convenience, we define $\alpha_{ji}=\alpha_{ij}$, $\alpha_{ii}=1$,
and $\alpha_{e}=\alpha_{ij}$, if $e$ is an edge connecting the nodes $i,j$.
See Figure 1 for examples.

In the following $\mathcal{G}$ denotes an admixture graph
$\mathcal{G}=(\mathcal{V},\mathcal{E},\mathcal{L})$.

Figure 1: Examples of admixture graphs. (A) An admixture graph where nodes
$1,2,3$ are roots, $4$ an admixed node and $5,6$ a leaves. (B) An admixture
graph with three leaves. From $3$ to $5$ there is as an a-path of type (b),
namely $(3,5)$ with label $\alpha_{35}$, and one of type (c), namely
$(3,1,2,5)$ with label $1\cdot 1\cdot\alpha_{36}=\alpha_{36}$.

######  Definition 2.

Given an admixture graph $\mathcal{G}$ and two nodes $i,j\in\mathcal{V}$, an
_admixture path_ (or simply an _a-path_) $\gamma$ from $i$ to $j$ is a
sequence of edges with distinct nodes,

$i_{k}\leftarrow i_{k-1},\ldots,i_{1}\leftarrow i_{0},\qquad j_{0}\to
j_{1},\ldots,j_{m-1}\to j_{m},$

where $i_{k}=i,\,j_{m}=j$, $k,m\geq 0$, and $i_{0}\neq j_{0}$ only if
$i_{0},j_{0}$ are roots, in which case there is an edge $i_{0}\leftrightarrow
j_{0}$. The set of a-paths from $i$ to $j$ is denoted by $\Gamma_{ij}$.

The label $p_{\gamma}$ of an a-path $\gamma\in\Gamma_{ij}$ is the product of
the labels of its edges,

$p_{\gamma}:=\prod\nolimits_{e\in\gamma}\alpha_{e},$

where $e\in\gamma$ means $e$ is an edge in the sequence $\gamma$.

An a-path contains at most two roots. We might think of three types of a-paths
between two nodes: (a) those where all directed edges have direction
$\leftarrow$ ($k>0,m=0$), (b) those where all directed edges have direction
$\to$ ($k=0,m>0$), and (c) those with both directions ($k,m>0$). If both nodes
are roots, then there is only one a-path consisting of an undirected edge
($k=m=0$). There cannot be both type (a) and type (b) a-paths between two
nodes as this would create a directed loop. Retuning to the genetic context,
an a-path between two populations implies that one of the populations is
ancestral to the other (a,b) or that they share a common ancestor (c). Due to
the nature of the graph, there can be two types of a-paths between two
populations, as in Figure 1(B).

The set $\Gamma_{ii}$ contains only the empty sequence with label one. An
a-path $\gamma\in\Gamma_{ij}$, $i\not=j$, is not symmetric, meaning that it is
not considered the same as the a-path $\gamma^{\prime}\in\Gamma_{ji}$ composed
by the edges of $\gamma$ in the opposite order. Therefore
$\Gamma_{ij}\neq\Gamma_{ji}$. However, the labels of $\gamma$ and
$\gamma^{\prime}$ are identical.

For convenience, we often write an a-path as an ordered sequence of nodes
$(i_{k},\ldots,i_{0},j_{0},\ldots,j_{m})$, leaving out $j_{0}$ if
$i_{0}=j_{0}$. If $\gamma=(i,\ldots,k,\ldots,j)\in\Gamma_{ij}$, then the
subsequences $\gamma_{1}=(i,\ldots,k)\in\Gamma_{ik}$ and
$\gamma_{2}=(k,\ldots,j)\in\Gamma_{kj}$ are a-paths as well.

An a-path $\gamma$ is not a path in standard graph terminology [8].

######  Proposition 1.

Consider two nodes $i,j\in\mathcal{V}$ of an admixture graph $\mathcal{G}$.
Then $\Gamma_{ij}\neq\emptyset$. Further, the sum of the labels over
$\Gamma_{ij}$ is one, $\sum_{\gamma\in\Gamma_{ij}}p_{\gamma}=1$.

A tree is a connected subgraph of an admixture graph with only directed edges
and at most one incoming edge to each node. In what follows we characterize -
in terms of a-paths and labels - when an admixture graph is a tree or a
forest. Here a forest is a set of trees with roots connected by undirected
edges.

######  Theorem 1.

For an admixture graph $\mathcal{G}$, the following statements are equivalent:

  1. (i)

for any pair of nodes, there is only one a-path connecting them,

  2. (ii)

every a-path has probability one,

  3. (iii)

the admixture graph consists of a forest of $R$ trees, where $R$ is the number
of roots.

######  Definition 3.

Let $\ell\in\mathcal{A}$ be an admixed node and $r\in\mathcal{R}$ a root of an
admixture graph $\mathcal{G}$. Let $\Omega_{\ell r}\subseteq\Gamma_{\ell r}$
be the set of a-paths from $\ell$ to $r$ that do not contain another root. The
_root weight_ of $r$ with respect to $\ell$ is the probability

$q_{\ell r}=\sum\nolimits_{\gamma\in\Omega_{\ell r}}p_{\gamma}.$

######  Proposition 2.

Given an admixture graph, the root weights with respect to an admixed node
form a probability distribution.

The probability $q_{\ell r}$ is the proportion of the ancestry of the node
$\ell$ stemming from the root $r$. If the admixture graph is a forest, then
$q_{\ell r}$ is one if the node $\ell$ is in the tree with root $r$, and
otherwise $q_{\ell r}=0$.

######  Definition 4.

Let $\mathcal{G}=(\mathcal{V},\mathcal{E},\mathcal{L})$ be an admixture graph
and let $C\subseteq\mathcal{V}$. We define the _admixture graph spanned by
$C$_ as the graph
$\mathcal{G}_{C}=\big{(}\mathcal{V}_{C},\mathcal{E}_{C},\mathcal{L}_{C}\big{)}$,
where

$\begin{split}\mathcal{V}_{C}&=\big{\\{}i\;|\;i\text{ is in an a-path of
$\Gamma_{jk}$ for some $j,k\in C$}\big{\\}},\\\
\mathcal{E}_{C}&=\big{\\{}e\;|\;e\in\mathcal{E}\text{ connects two nodes of
$\mathcal{V}_{C}$ }\big{\\}},\end{split}$

and $\mathcal{L}_{C}$ is the set of labels inherited from $\mathcal{G}$. In
particular, $\mathcal{G}_{\mathcal{V}}=\mathcal{G}$.

It is immediate to verify that the graph $\mathcal{G}_{C}$ is an admixture
graph.

######  Proposition 3.

Let $\mathcal{G}$ be an admixture graph, $\mathcal{A}_{0}\subseteq\mathcal{V}$
the leaves and $\mathcal{G}_{\mathcal{A}_{0}}$ the admixture graph spanned by
$\mathcal{A}_{0}$. Furthermore, assume every root has a child. One of the
following two equivalent conditions holds

  1. (i)

for each node $k\in\mathcal{V}\backslash\mathcal{A}_{0}$, there is a pair of
nodes $i,j\in\mathcal{A}_{0}$ and two a-paths
$\gamma\in\Gamma_{ik},\,\delta\in\Gamma_{kj}$, such that $\gamma$ and $\delta$
only have $k$ in common,

  2. (ii)

for each node $k\in\mathcal{V}\backslash\mathcal{A}_{0}$, there are two nodes
$i,j\in\mathcal{A}_{0}$ and an a-path from $i$ to $j$ that includes $k$,

if and only if $\mathcal{G}=\mathcal{G}_{\mathcal{A}_{0}}$. Moreover
$\mathcal{A}_{0}$ is the smallest set spanning the graph $\mathcal{G}$, in the
sense that any other set that spans $\mathcal{G}$ contains $\mathcal{A}_{0}$.

An a-path of $\mathcal{G}$ between two nodes of $C$ is also an a-path of
$\mathcal{G}_{C}$ by definition.

##  3 Stochastic admixture graphs

We will assume an admixture graph expresses conditional independencies of a
random vector. Specifically, an admixture graph is a chain graph (a graph with
directed and undirected edges and no directed cycles), which gives rise to a
special type of Markov graphical models, called chain graph models [10, 6,
19], see Appendix A. Many models in population genetics and phylogenetics are
assumed to fulfil the conditional independences expressed by a tree, which is
a special type of chain graph. Here we make the natural extension to admixture
graphs.

Given an admixture graph $\mathcal{G}$, we define the augmented graph
$\mathcal{G}^{*}=(\mathcal{V}^{*},\mathcal{E}^{*})$ by

$\mathcal{V}^{*}=\mathcal{V}\cup\big{\\{}(i,j)\,|\,i\to
j\in\mathcal{E}\big{\\}},$ $\mathcal{E}^{*}=\\{i\leftrightarrow
j\,|\,i\leftrightarrow j\in\mathcal{E}\\}\cup\\{i\to(i,j)\,|\,i\to
j\in\mathcal{E}\\}\cup\\{(i,j)\to j\,|\,i\to j\in\mathcal{E}\\},$

see Figure 2. Note that $\mathcal{G}^{*}$ is an admixture graph except for the
labelling and that an a-path of $\mathcal{G}$ between two nodes
$i,j\in\mathcal{V}$ corresponds to a unique a-path of $\mathcal{G}^{*}$
between the same two nodes $i,j\in\mathcal{V}\subseteq\mathcal{V}^{*}$, and
vice versa.

Here and elsewhere, an equality between two random variables means equality
almost surely with respect to the underlying probability measure. If $X$ is a
random variable with finite expectation, then $E(X|Y)$ denotes the conditional
expectation of $X$ given the random variable $Y$.

######  Definition 5.

Let $\mathcal{G}$ be an admixture graph and $(V_{i}\mid i\in\mathcal{V})$ a
random vector with finite expectation. Then, $(V_{i}\mid i\in\mathcal{V})$ is
a _stochastic admixture graph_ over $\mathcal{G}$ if there exists a random
vector $(C_{ij}\mid i\to j\in\mathcal{E})$, defined on the same space as
$(V_{i}\mid i\in\mathcal{V})$, with finite expectation and such that

  1. (i)

$(V_{j},C_{ij}\,|\,i\in\\!par(j),j\in\\!\mathcal{V})$ is a chain graph model
over $\mathcal{G}^{*}$,

  2. (ii)

$V_{j}=\sum\nolimits_{i\in par(j)}\alpha_{ij}C_{ij}$, $j\in\mathcal{A}$,

  3. (iii)

$E(C_{ij}|V_{i})=V_{i}$ for $i\in par(j)$, $j\in\mathcal{A}$.

The variables $C_{ij}$, $(i,j)\in\mathcal{V}^{*}$, are called contribution
variables.

The requirement that expectations are finite ensures the existence of
conditional expectations [9]. In the genetic context, where the variables are
allele frequencies, Definition 5(i) is a mathematical formalisation of the
statement that evolution and gene flow happens independently along distinct
lineages. Definition 5(ii) states that the allele frequency of a population is
a weighted sum of the allele frequencies of the admixted populations. These
frequencies are themselves the result of neutral evolution in the sense that
their expectation is constant over time, Definition 5(iii).

######  Example 1.

Assume $(V_{i}\mid i\in\mathcal{V})$ is a _Gaussian graphical model_ over a
directed acyclic graph (DAG) $\mathcal{G}$ [19]. The conditional distribution
of $V_{j}$ given the parent variables, $(V_{i}\mid i\in par(j))$, has a
Gaussian distribution with form

$\sum_{i\in par(j)}\alpha_{ij}V_{i}+\epsilon_{j},$

where $\alpha_{ij}\not=0$ and the error terms $\epsilon_{j}$ are independent
with expectation zero and variance $\sigma_{j}^{2}>0$. If $\alpha_{ij}>0$ and
$\sum_{i\in par(j)}\alpha_{ij}=1$, then $\epsilon_{j}$ can be realised as a
weighted sum of independent terms $\epsilon_{j}=\sum_{i\in
par(j)}\alpha_{ij}\epsilon_{ij}$, where $\epsilon_{ij}$ has expectation zero
and variance $\sigma_{j}^{2}/\alpha_{ij}$. By defining
$C_{ij}=V_{i}+\epsilon_{ij}$, the three conditions of Definition 5 can be
verified. If an arbitrary Gaussian distribution are specified for the
variables of the roots of $\mathcal{G}$, then $(V_{i}\mid i\in\mathcal{V})$ is
a stochastic admixture graph over $\mathcal{G}$ (assuming the roots are
connected by undirected edges).

A similar remark could be said about _Structural equation models_ (SEMs),
where the distribution of $(V_{i}\mid i\in\mathcal{V})$ is allowed to take a
general form while preserving (1).

######  Example 2.

The Wright-Fisher model with two alleles, say $A$ and $B$, assumes a
population of constant size $N$. The frequency of the $A$ allele evolves
according to random sampling with replacement (without mutation)

$P(X_{n+1}=\ell\mid
X_{n}=k)=\binom{N}{\ell}\left(\frac{k}{N}\right)^{\\!\ell}\left(1-\frac{k}{N}\right)^{\\!N-\ell},$

where $X_{n}$ denotes the number of $A$ alleles in generation $n$ [5]. The
conditional expectation of $X_{n+m}$ given $X_{n}$ is $E(X_{n+m}\mid
X_{n})=X_{n}$.

Assume evolution occurs on the edges of an admixture graph according to the
Wright-Fisher model and that the nodes $i$ and $(i,j)$ in the augmented graph
represent a population at different time points. Let $V_{i}$ and $C_{ij}$ be
the relative frequencies of the $A$ allele at these time points, and assume
the population at node $j$ is the admixture of its parent populations with
respective frequencies $\alpha_{ij}$, $i\in par(j)$. Then Definition
5(ii)-5(iii) hold.

The same conclusion can be made if mutation between $A$ and $B$ is allowed,
and in the diffusion limit as $N\to\infty$. We will return to this model in
Section 5.

Figure 2: Contribution nodes. An example of an admixture graph (A) and its
augmented graph (B). Black dots represent nodes associated with contribution
variables.

Definition 5(iii) does not in general hold for variables associated to the
roots.

######  Theorem 2.

Let $\mathcal{G}$ be a stochastic admixture graph, and assume
$V_{1},\dots,V_{k}$ are the variables associated with the roots. Then
$E(V_{i}\,|\,V_{j})=V_{j}$ holds for any pair of roots if and only if
$V_{1}=V_{2}=\dots=V_{k}$.

For reasons of exposition, we assume an order on the set of the roots,
$(\mathcal{R},\prec)$, of an admixture graph. This provides a natural way of
writing undirected edges with the smallest node first, $k\leftrightarrow\ell$,
if $k\prec\ell$ and $k,\ell\in\mathcal{R}$.

For two nodes $i,j\in\mathcal{V}$, the _drift_ from $i$ to $j$ is defined as

$D_{ij}:=V_{j}-V_{i}.$

Note that $D_{ji}=-D_{ij}$. Similarly, we define the _partial drift_ of an
edge $e=k\to\ell\in\mathcal{E}$ as

$d_{e}=d_{k\ell}:=C_{k\ell}-V_{k},$

and of an edge $e=k\leftrightarrow\ell\in\mathcal{E}$, $k\prec\ell$, between
two roots as

$d_{e}=d_{k\ell}:=V_{\ell}-V_{k}.$

If $k\leftrightarrow\ell$ is an undirected edge or if $k$ is the only parent
of $\ell$, then the partial drift $d_{k\ell}$ coincides with the drift
$D_{k\ell}$ from $k$ and $\ell$.

Let $e=k\to\ell$ or $k\leftrightarrow\ell$, $k\prec\ell$, be an edge in an
a-path $\gamma$. The sign of $e$ with respect to $\gamma$ is defined as

$\text{sign}_{\gamma}(e)=\left\\{\begin{array}[]{cl}\text{sign}_{\gamma}(e)=+1&\quad\text{if}\quad\gamma=(\ldots
k,\,\ell\ldots),\\\
\text{sign}_{\gamma}(e)=-1&\quad\text{if}\quad\gamma=(\ldots\ell,\,k\ldots),\\\
\text{sign}_{\gamma}(e)=\phantom{+}0&\quad\text{if}\quad
e\not\in\gamma.\end{array}\right.$

######  Theorem 3.

Let $(V_{i}\,|\,i\in\mathcal{V})$ be a stochastic admixture graph over
$\mathcal{G}$ and let $i,j\in\mathcal{V}$. The drift $D_{ij}$ from $i$ to $j$
decomposes as

$D_{ij}=\sum\nolimits_{\gamma\in\Gamma_{ij}}\Big{(}p_{\gamma}\sum\nolimits_{e\in\gamma}d^{\gamma}_{e}\Big{)},$
(2)

where $d_{e}^{\gamma}=\text{sign}_{\gamma}(e)d_{e}$ is the signed partial
drift with respect to $\gamma$.

If $\gamma_{1}\in\Gamma_{ij}$ is an a-path from $i$ to $j$, and
$\gamma_{2}\in\Gamma_{ji}$ is the ‘reversed’ a-path from $j$ to $i$, then
$d_{e}^{\gamma_{1}}=-d_{e}^{\gamma_{2}}$. The signed partial drift of an
undirected edge along an a-path is independent of the order defined on
$\mathcal{R}$.

######  Lemma 1.

Let $(V_{i}\,|\,i\in\mathcal{V})$ be a stochastic admixture graph over
$\mathcal{G}$ and let $e_{1},e_{2}\in\mathcal{E}$ be two distinct edges, where
at least one is directed. The product of their partial drifts is zero in
expectation,

$E(d_{e_{1}}d_{e_{2}})=0.$ (3)

Furthermore, for any edge $e=i\to j\in\mathcal{E}$, we have
$E(d_{e}^{2})=\text{Var}(C_{ij})-\text{Var}(V_{i})$.

The second part of the lemma implies that
$\text{Var}(C_{ij})\geq\text{Var}(V_{i})$, which was first shown for the
Wright-Fisher model [14].

######  Example 3.

Continuing with Example 1, for an edge $k\to\ell$, the expectation of the
squared partial drift is
$E(d_{k\ell}^{2})=\text{Var}(V_{k}+\epsilon_{k\ell})-\text{Var}(V_{k})=\sigma_{k}^{2}/\alpha_{k\ell}$.

##  4 $F$-statistics

In this section we discuss the $F$-statistics $F_{2}$, $F_{3}$ and $F_{4}$
[13, 16, 14], and give various results for these. We assume $(V_{i}\mid
i\in\mathcal{V})$ has finite second moments.

######  Definition 6.

Let $(V_{i}\,|\,i\in\mathcal{V})$ be a stochastic admixture graph over
$\mathcal{G}$ and $i,j\in\mathcal{V}$. The _$F_{2}$ -statistic_ between $i$
and $j$ is

$F_{2}(i,j)=E(D_{ij}^{2}).$ (4)

The $F_{2}$-statistic is non-negative and symmetric by definition. Using
Theorem 3 and Lemma 1, we might rewrite (4) in terms of squared partial drifts
along the a-paths of $\Gamma_{ij}$, see below.

For two edges $e_{1},e_{2}\in\mathcal{E}$ and four nodes
$i,j,k,\ell\in\mathcal{V}$ of an admixture graph, define the _$B$
-coefficient_ of $(e_{1},e_{2})$ with respect to the pairs $(i,j),(k,\ell)$ as

$\displaystyle B_{e_{1},e_{2}}^{(i,j)(k,\ell)}$
$\displaystyle=\sum\limits_{(\gamma_{1},\gamma_{2})\in\Gamma_{ij}^{e_{1}}\times\Gamma_{k\ell}^{e_{2}}}\text{sign}_{\gamma_{1}}\\!(e_{1})\,\text{sign}_{\gamma_{2}}\\!(e_{2})p_{\gamma_{1}}p_{\gamma_{2}}$
$\displaystyle=\left(\sum\nolimits_{\gamma_{1}\in\Gamma_{ij}^{e_{1}}}\text{sign}_{\gamma_{1}}\\!(e)p_{\gamma_{1}}\right)\left(\sum\nolimits_{\gamma_{2}\in\Gamma_{k\ell}^{e_{2}}}\text{sign}_{\gamma_{2}}\\!(e)p_{\gamma_{2}}\right).$
(5)

For an edge $e\in\mathcal{E}$, the _$A$ -coefficient_ of $e$ with respect to
the pairs $(i,j),(k,\ell)$ is defined as

$\displaystyle A_{e}^{(i,j)(k,\ell)}$ $\displaystyle=B_{e,e}^{(i,j)(k,\ell)}.$
(6)

For convenience, we write $A_{e}^{(i,j)}$ and $B_{e_{1},e_{2}}^{(i,j)}$ if
$(k,\ell)=(i,j)$. In that case the coefficients are symmetric in $i,j$.

######  Lemma 2.

Let $\mathcal{G}$ be an admixture graph and $i,j,k,\ell\in\mathcal{V}$. For
two edges $e_{1},e_{2}\in\mathcal{E}$, the following holds:

  1. (i)

$-1\leq B^{(i,j)(k,\ell)}_{e_{1},e_{2}}\leq 1$,

  2. (ii)

$B_{e_{1},e_{2}}^{(i,j)(k,\ell)}=\pm 1$ if and only if
$\Gamma_{ij}^{e_{1}}=\Gamma_{ij}$, $\Gamma_{k\ell}^{e_{2}}=\Gamma_{k\ell}$,
$\text{sign}_{\gamma_{1}}\\!(e_{1})$ is independent of
$\gamma_{1}\in\Gamma_{ij}$ and $\text{sign}_{\gamma_{2}}\\!(e_{2})$ is
independent of $\gamma_{2}\in\Gamma_{k\ell}$,

  3. (iii)

$B_{e_{1},e_{2}}^{(i,j)(k,\ell)}=0$ for all positive values of
$\alpha_{e},\,e\in\mathcal{E}$, such that (1) is fulfilled, if and only if
$\Gamma_{ij}^{e_{1}}=\emptyset$ or $\Gamma_{k\ell}^{e_{2}}=\emptyset$.

The lemma implies that $0\leq A_{e}^{(i,j)}\leq 1$ for any edge and
$-1<B^{(i,j)}_{e_{1},e_{2}}\leq 1$ for two undirected edges. The latter
follows from (ii) and the fact that an a-path cannot pass through two distinct
undirected edges.

Let $\mathcal{E}_{ij}\subseteq\mathcal{E}$ be the set of edges that appear in
at least one path of $\Gamma_{ij}$. Further, let
$\mathcal{E}_{ij}^{u}\subseteq\mathcal{E}_{ij}$ be the set of undirected edges
and $\mathcal{E}_{ij}^{d}\subseteq\mathcal{E}_{ij}$ the set of directed edges.

######  Theorem 4.

Let $(V_{i}\,|\,i\in\mathcal{V})$ be a stochastic admixture graph over
$\mathcal{G}$ and $i,j\in\mathcal{V}$. The $F_{2}$-statistic $F_{2}(i,j)$
decomposes as

$F_{2}(i,j)=\sum\limits_{e\in\mathcal{E}^{d}_{ij}}A^{(i,j)}_{e}\,E(d_{e}^{2})+\sum\limits_{(e_{1},e_{2})\in\mathcal{E}^{u}_{ij}\times\mathcal{E}^{u}_{ij}}B^{(i,j)}_{e_{1},e_{2}}\,E(d_{e_{1}}d_{e_{2}})$
(7)

If $\mathcal{G}_{\\{i,j\\}}$ has at most two roots, (7) might be written
compactly as

$F_{2}(i,j)=\sum\limits_{e\in\mathcal{E}_{ij}}A^{(i,j)}_{e}\,E(d_{e}^{2}).$

If $\mathcal{G}$ is a Gaussian admixture graph, then
$A^{(i,j)}_{e}\,E(d_{e}^{2})=\sigma^{2}_{k}A^{(i,j)}_{e}/\alpha_{k\ell}$ is a
polynomial in the labels, that is, $\alpha_{k\ell}$ cancels out, see Example
3.

We next characterise the additivity of the $F_{2}$-statistic [12, 16, 13].

######  Proposition 4.

Consider a stochastic admixture graph $(V_{i}\mid i\in\mathcal{V})$ over
$\mathcal{G}$, and let $i,j,k\in\mathcal{V}$. If all a-paths of $\Gamma_{ij}$
pass through $k$, then $F_{2}(i,j)=F_{2}(i,k)+F_{2}(k,j)$.

Assume $\mathcal{G}_{\\{i,j\\}}$ has at most two roots. If
$F_{2}(i,j)=F_{2}(i,k)+F_{2}(k,j)$ for all positive values of $E(d_{e}^{2})$
and $\alpha_{e}$, $e\in\mathcal{E}$, such that (1) is fulfilled, then all
a-paths of $\Gamma_{ij}$ pass through $k$.

If additivity holds for any node on the a-paths between any two nodes, then
and only then is the admixture graph a forest (Theorem 1).

######  Example 4.

Consider the admixture graph in Figure 1B. The only a-path of $\Gamma_{57}$
goes through node 2, so $F_{2}(5,7)=F_{2}(5,2)+F_{2}(2,7)$. For node 6 we have
$F_{2}(5,7)=F_{2}(5,6)+F_{2}(6,7)-2F_{3}(6;5,7)$, but $F_{3}(6;5,7)$ is only
zero for certain values of the parameters. In fact,

$\displaystyle E(D_{65}D_{67})$
$\displaystyle=\alpha_{36}^{2}E(d_{36}^{2})+\alpha_{46}^{2}E(d_{46}^{2})-2\alpha_{36}\alpha_{46}E(d_{23}^{2}+d_{24}^{2}),$

which is zero for certain choices of parameters.

The $F_{3}$\- and $F_{4}$-statistics are defined analogously to the
$F_{2}$-statistic

$F_{3}(i;j,k)=E(D_{ij}D_{ik})\quad\text{and}\quad
F_{4}(i,j;k,l)=E(D_{ij}D_{k\ell}),$

for four nodes $i,j,k,\ell\in\mathcal{V}$. Similarly to the decomposition of
the $F_{2}$-statistic, the $F_{3}$\- and $F_{4}$-statistics decompose as

$\displaystyle
F_{3}(i;j,k)=\sum\limits_{e\in\mathcal{E}^{d}_{ij}\cap\mathcal{E}_{ik}^{d}}\\!\\!\\!A_{e}^{(i,j)(i,k)}E(d_{e}^{2})+\sum\limits_{(e_{1},e_{2})\in\mathcal{E}^{u}_{ij}\times\mathcal{E}_{ik}^{u}}\\!\\!\\!B_{(e_{1},e_{2})}^{(i,j)(i,k)}E(d_{e_{1}}d_{e_{2}})$
(8) $\displaystyle
F_{4}(i,j;k,\ell)=\sum\limits_{e\in\mathcal{E}^{d}_{ij}\cap\mathcal{E}_{k\ell}^{d}}\\!\\!\\!A_{e}^{(i,j)(k,\ell)}E(d_{e}^{2})+\sum\limits_{(e_{1},e_{2})\in\mathcal{E}^{u}_{ij}\times\mathcal{E}_{k\ell}^{u}}\\!\\!\\!B_{(e_{1},e_{2})}^{(i,j)(k,\ell)}E(d_{e_{1}}d_{e_{2}}).$
(9)

(the proofs are similar to the proof for the $F_{2}$-statistic).

A visual method to decompose the $F$-statistics is introduced in [13] and
[16]. This is formally motivated here as a consequence of the decompositions.
The steps to calculate the $F_{2}$-statistic between two nodes
$i,j\in\mathcal{V}$ are the following, see Example 5:

  1. 1.

Consider all pairs $(\gamma_{1},\gamma_{2})\in\Gamma_{ij}\times\Gamma_{ij}$,
including coincident pairs,

  2. 2.

For each pair $(\gamma_{1},\gamma_{2})$, multiply the sum of the squared
partial drifts of the directed edges that are in both a-paths by
$p_{\gamma_{1}}p_{\gamma_{2}}$,

  3. 3.

For each pair $(\gamma_{1},\gamma_{2})$, sum the products of partial drifts
$d_{e_{1}}^{\gamma_{1}}d_{e_{2}}^{\gamma_{2}}$ over the undirected edges
$e_{1}\in\gamma_{1}$ and $e_{2}\in\gamma_{2}$, and multiply by
$p_{\gamma_{1}}p_{\gamma_{2}}$,

  4. 4.

Sum all terms above and take the expectation of the sum.

An analogous procedure is followed to calculate the $F_{3}$\- and
$F_{4}$-statistics, by considering the pairs of a-paths
$(\gamma_{1},\gamma_{2})$ between the pairs of nodes $(i,j),(i,k)$ and
$(i,j),(k,\ell)$ for $F_{3}(i;j,k)$ and $F_{4}(i,j;k,\ell)$, respectively.

######  Example 5.

Consider $F_{2}(5,6)$ in the admixture graph of Figure 1A. There are two
a-paths in $\Gamma_{56}$, namely $\gamma_{1}=(5,4,1,3,6)$ and
$\gamma_{2}=(5,4,2,3,6)$, resulting in four pairs of a-paths, see Figure 3A.
Applying the visual method yields:

$\begin{split}F_{2}(5,6)=E\Big{(}&p_{\gamma_{1}}^{2}(d_{45}^{2}+d_{14}^{2}+d_{13}^{2}+d_{36}^{2})+p_{\gamma_{2}}^{2}(d_{45}^{2}+d_{24}^{2}+d_{23}^{2}+d_{36}^{2})\\\
&+2p_{\gamma_{1}}p_{\gamma_{2}}(d_{45}^{2}+d_{36}^{2}+d_{13}d_{23})\Big{)}.\end{split}$

By collecting terms with the same partial drifts, we obtain

$\begin{split}F_{2}(5,6)&=E(d_{45}^{2})+E(d_{36}^{2})+p_{\gamma_{1}}^{2}E(d_{14}^{2})+p_{\gamma_{1}}^{2}E(d_{13}^{2})+p_{\gamma_{2}}^{2}E(d_{24}^{2})\\\
&+p_{\gamma_{2}}^{2}E(d_{23}^{2})+2p_{\gamma_{1}}p_{\gamma_{2}}E(d_{13}d_{23}).\end{split}$

We recognize the $A$\- and $B$-coefficients,

$\displaystyle A^{(5,6)}_{4\to 5}=A^{(5,6)}_{3\to 6}=1,\quad A^{(5,6)}_{1\to
4}=A^{(5,6)}_{2\to 4}=p_{\gamma_{1}}^{2},$ $\displaystyle
B^{(5,6)}_{2\leftrightarrow 3,2\leftrightarrow
3}=p_{\gamma_{2}}^{2},\quad\quad B^{(5,6)}_{1\leftrightarrow
3,1\leftrightarrow 3}=p_{\gamma_{1}}^{2},\quad\quad
B^{(5,6)}_{1\leftrightarrow 3,2\leftrightarrow 3}=B_{2\leftrightarrow
3,1\leftrightarrow 3}=p_{\gamma_{1}}p_{\gamma_{2}}.$

Figure 3:  Visual method for the $F$-statistic. Illustration of the visual
method to calculate $F_{2}(5,6)$ in the admixture graphs of Figure 1A. A pair
of paths is represented by a blue and a green lines connecting adjacent nodes.
(A-B) Pairs of coincident admixture paths sharing all their edges. (C-D) A
pair of different paths where the shared directed edges are $4\to 5$, $3\to
6$. The product of partial drifts of the two undirected edges on the blue and
green paths appears in $F_{2}(5,6)$ (see step 3 of the visual method).

The $F_{3}$-statistics can be given in terms of the $F_{2}$-statistics,

$\displaystyle F_{2}(i,j)=F_{2}(i,k)+F_{2}(k,j)-2F_{3}(k;i,j)$

[16]. This shows that the $F_{2}$-statistic is a metric on $\mathcal{V}$ (that
is, it fulfils the triangular inequality) if and only if $F_{3}(k;i,j)\geq 0$,
for all $i,j,k\in\mathcal{V}$.

If there are at most two roots then there is at most one undirected edge and
$F_{3}(i;j,k)$ can be written as a sum involving only $A$-coefficients, see
(6) and (8). Express $F_{3}(i;j,k)$ as the sum $F_{3+}(i;j,k)+F_{3-}(i;j,k)$,
where

$\displaystyle
F_{3+}(i;j,k)=\sum\limits_{e\in\mathcal{E}_{ij}\cap\mathcal{E}_{ik}}A_{e+}^{(i,j)(i,k)}E(d_{e}^{2}),\quad
F_{3-}(i;j,k)=\sum\limits_{e\in\mathcal{E}_{ij}\cap\mathcal{E}_{ik}}A_{e-}^{(i,j)(i,k)}E(d_{e}^{2}),$

and $A_{e+}^{(i,j)(i,k)}$ and $A_{e-}^{(i,j)(i,k)}$ collect the terms with
same and opposite sign of $e$ in
$(\gamma_{1},\gamma_{2})\in\Gamma_{ij}^{e}\times\Gamma_{ik}^{e}$,
respectively.

The next statement relates the sign of the $F_{3}$-statistic to the topology
of the admixture graph.

######  Proposition 5.

Let $\mathcal{G}$ be an admixture graph and
$C=\\{i,j,k\\}\subseteq\mathcal{V}$ such that $\mathcal{G}_{C}$ has at most
two roots. Then $F_{3-}(i;j,k)\neq 0$ if and only if there exist
$e\in\mathcal{E}_{ij}\cap\mathcal{E}_{ik}$ and a pair of a-paths
$(\gamma_{1},\gamma_{2})\in\Gamma^{e}_{ij}\times\Gamma^{e}_{ik}$ such that

$\displaystyle\gamma_{1}$ $\displaystyle=i\leftarrow\dots\to j\quad\text{ or
}\quad\gamma_{1}=i\leftarrow\dots\leftrightarrow j,$ $\displaystyle\gamma_{2}$
$\displaystyle=i\leftarrow\dots\to k\quad\text{ or
}\quad\gamma_{2}=i\leftarrow\dots\leftrightarrow k,$

and $\text{sign}_{\gamma_{1}}(e)=-\text{sign}_{\gamma_{2}}(e)$.

##  5 The Wright-Fisher model

In this section we consider the Wright-Fisher model in the diffusion limit as
the population size becomes infinite [5], see also Example 2.

######  Definition 7.

A _Wright-Fisher admixture graph_ $(V_{i}|i\in\mathcal{V})$ over $\mathcal{G}$
is a stochastic admixture graph such that $V_{i}$, $i\in V$, are the
frequencies of a particular allele in the populations represented by the nodes
of the graph, and such that $C_{ij}$ conditional on $V_{i}=v\in[0,1]$, $i\in
par(j)$, $j\in\mathcal{V}$, is distributed as the frequency in a Wright-Fisher
diffusion process at time $\tau_{ij}$, given it starts at frequency $v$, and
$\tau_{ij}$ is the population scaled time between the nodes $i$ and $(i,j)$.

[12, chapter 13] showed that the expected heterozygosity of an allele declines
exponentially over time,

$E(V_{1}(1-V_{1}))=(1-e^{-\tau_{12}})E(V_{2}(1-V_{2})),$

where $V_{1}$ is the frequency at time zero and $V_{2}$ the frequency
$\tau_{12}$ population scaled time units later. We generalise this formula to
a Wright-Fisher admixture graph.

######  Proposition 6.

Consider a Wright-Fisher admixture graph $(V_{i}\mid i\in\mathcal{V})$ over
$\mathcal{G}$. Then the expected heterozygosities fulfil

$\displaystyle E(V_{j}(1-V_{j}))$
$\displaystyle=\sum_{(r_{1},r_{2})\in\mathcal{R}\times\mathcal{R}}D_{r_{1},r_{2}}^{j}E(V_{r_{1}}(1-V_{r_{2}})),\quad
j\in\mathcal{V},$

where $D^{j}_{r_{1},r_{2}}$ are non-negative constants depending on the edge
labels and the population scaled times. Furthermore,

$\sum_{r_{1},r_{2}}D^{j}_{r_{1},r_{2}}\leq 1,\quad j\in\mathcal{V}.$

If all population scaled times $\tau_{ij}$, $i\to j\in\mathcal{E}$, between
two nodes are set to zero, then the sum of $D^{j}_{r_{1},r_{2}}$ over
$r_{1},r_{2}$ is precisely one (see the proof of the. proposition). In that
case, $E(V_{j}(1-V_{j}))$ is the probability of drawing two different alleles
from the root populations. With probability $D_{r_{1},r_{2}}^{j}$, alleles
from population $r_{1}$ and $r_{2}$ are drawn. In general, when
$D_{r_{1},r_{2}}^{j}$ does not sum to one, heterozygosity is lost.

If there is only one root, then the sum consists of just one term, hence all
expected heterozygosities can be expressed in terms of the expected
heterozygosity of the root variable. [12] showed that the partial drift of an
edge $e=i\to j$ fulfils

$E(d_{e}^{2})=(1-e^{-\tau_{ij}})E(V_{i}(1-V_{i})),$ (10)

so that the $F_{2}$-statistics can be expressed in terms of the expected
heterozygosities of the root variables (Theorem 4).

To end we consider a few examples. The linear Wright-Fisher admixture graph
with edges $1\to 2$, $2\to 3$ was already studied in [12, chapter 13] and it
was found that

$F_{2}(2,3)=e^{-\tau_{12}}(1-e^{-\tau_{23}})E(V_{1}(1-V_{1})).$

It is also a consequence of (10) and additivity of the $F_{2}$-statistic.

In a Wright-Fisher admixture graph with edges $1\to 2$, $2\to 3$, $2\to 4$,
$3\to 5$, $4\to 5$, such that there are two overlapping a-paths from $1$ to
$5$, we have

$\displaystyle F_{2}(1,5)$
$\displaystyle=\big{(}1-\alpha_{35}^{2}e^{-\hat{\tau}_{1}}-\alpha_{45}^{2}e^{-\hat{\tau}_{2}}-2\alpha_{35}\alpha_{45}e^{-\tau_{12}}\big{)}E(V_{1}(1-V_{1})),$

where $\hat{\tau}_{1}=\tau_{12}+\tau_{23}+\tau_{35}$ and
$\hat{\tau}_{2}=\tau_{12}+\tau_{24}+\tau_{45}$.

## Acknowledgement

CW acknowledges support from the Danish Research Council.

## References

  * [1] Castelo, R., Roverato, A., 2006\.  A robust procedure for gaussian graphical model search from microarray data with p larger than n.  Journal of Machine Learning Research 7, 2621–2650.
  * [2] Cavalli-Sforza, L.L., 1966.  Population structure and human evolution.  Proceedings of the Royal Society of London. Series B, Biological sciences 164, 362–79.  doi:10.1098/rspb.1966.0038.
  * [3] Cavalli-Sforza, L.L., Edwards, A.W., 1967\.  Phylogenetic analysis. models and estimation procedures.  American Journal of Human Genetics 19, 233–57.  doi:10.1111/j.1558-5646.1967.tb03411.x.
  * [4] Cox, D.A., Little, J.B., O’Shea, D., 2007.  Ideals, varieties, and algorithms: an introduction to computational algebraic geometry and commutative algebra.  Springer.
  * [5] Ewens, W.J., 1979.  Mathematical population genetics.  Springer-Verlag.
  * [6] Frydenberg, M., 1990.  The chain graph markov property.  Scandinavian Journal of Statistics 17, 333–353.
  * [7] Green, R.E., Krause, J.e.a., 2010\.  A draft sequence of the neandertal genome.  Science 328, 710–22.  doi:10.1126/science.1188021.
  * [8] Harary, F., 1969.  Graph theory.  Addison Wesley.
  * [9] Hoffmann-Jørgensen, J., 1994.  Probability with a view toward statistics.  Chapman & Hall.
  * [10] Lauritzen, S., Richardson, T., 2002\.  Chain graph models and their causal interpretations.  J. R. Statist. Soc. 64, 321–361.  doi:10.1111/1467-9868.00340.
  * [11] Lipson, M., Loh, P.R., Levin, A., Reich, D., Patterson, N., Berger, B., 2013\.  Efficient moment-based inference of admixture parameters and sources of gene flow.  Molecular Biology and Evolution 30, 1788–1802.  doi:10.1093/molbev/mst099.
  * [12] Nei, M., 1987.  Molecular evolutionary genetics.  Columbia University Press.
  * [13] Patterson, N.J., Moorjani, P., Luo, Y., Mallick, S., Rohland, N., Zhan, Y., Genschoreck, T., Webster, T., Reich, D., 2012.  Ancient admixture in human history.  Genetics 192, 1065–1093.  doi:10.1534/genetics.112.145037.
  * [14] Peter, B.M., 2016.  Admixture, population structure and f-statistics.  Genetics 202, 1485–1501.  doi:10.1534/genetics.115.183913.
  * [15] Pickrell, J.K., Pritchard, J.K., 2012\.  Inference of population splits and mixtures from genome-wide allele frequency data.  PLoS Genetics 8, 1–17.  doi:10.1371/journal.pgen.1002967.
  * [16] Reich, D., Thangaraj, K., Patterson, N., Price, A., Singh, L., 2009.  Reconstructing indian population history.  Nature 461, 489–94.  doi:10.1038/nature08365.
  * [17] Skoglund, P., Mallick, S., Bortolini, M.C., Chennagiri, N., Hünemeier, T., Petzl-Erler, M.L., Salzano, F.M., Patterson, N., Reich, D., 2015.  Genetic evidence for two founding populations of the americas.  Nature 525, 104–108.  doi:10.1038/nature14895.
  * [18] Wall, J.D., Yang, M.A., Jay, F., Kim, S.K., Durand, E.Y., Stevison, L.S., Gignoux, C., Woerner, A., Hammer, M.F., Slatkin, M., 2013\.  Higher levels of neanderthal ancestry in east asians than in europeans.  Genetics 194, 199–209.  doi:10.1534/genetics.112.148213.
  * [19] Whittaker, J., 1990.  Graphical models in applied multivariate statistics.  Wiley.

## Appendix A

Consider a graph $\mathcal{G}=(\mathcal{V},\mathcal{E})$, where
$\mathcal{V},\mathcal{E}$, are the nodes and the edges, respectively, and
edges are directed or undirected. A directed edge from $i$ to $j$ and an
undirected edge between $i$ and $j$ are written as $i\to j$ and
$i\leftrightarrow j$, respectively. A _path_ from node $i$ to node $j$ is a
sequence of adjacent nodes $i_{0},i_{1},......,i_{K}$, where
$i_{0}=i,i_{K}=j$, and either $i_{k}\to i_{k+1}$ or $i_{k}\leftrightarrow
i_{k+1}$, for $k=0,\dots,K-1$. A _cycle_ is a path with $i=j$. A cycle is
directed if $i_{k}\to i_{k+1}$ for $k=0,\dots,K-1$. (A path is _not_ the same
as an a-path.)

A graph where the nodes are connected by either directed or undirected edges
and without directed cycles is called a _chain graph_.

The node set $\mathcal{V}$ of a chain graph $\mathcal{G}$ can be partitioned
into unique _blocks_ $B_{1},\dots,B_{N}$ such that $B_{1}=\mathcal{R}$, and if
two nodes $i,j\in\mathcal{V}$ are connected by a sequence of directed edges
$i\to i_{1},i_{1}\to i_{2},\ldots,i_{k}\to j$ in $\mathcal{E}$, then $i\in
B_{n_{i}},\,j\in B_{n_{j}}$ and $n_{i}<n_{j}$. Two nodes $i,j$ are said to be
in the same _component_ if they are connected by an undirected or directed
path from $i$ to $j$ and from $j$ to $i$. Note that a component does not
coincide with a block. In Figure 1B each node is a distinct component, but the
blocks are $B_{1}=\\{1\\}$, $B_{2}=\\{2,8\\}$, $B_{3}=\\{3,4\\}$,
$B_{4}=\\{5,6,7\\}$.

A subset $A\subseteq\mathcal{V}$ of a chain graph $\mathcal{G}$ induces a
graph $\mathcal{G}(A)=(A,\mathcal{E}(A))$, where $\mathcal{E}(A)$ contains the
edges of $\mathcal{G}$ whose nodes are in $A$

The _border_ of a subset $\mathcal{A}\subseteq\mathcal{V}$ is defined as

$bd(\mathcal{A}):=\big{\\{}i\in\mathcal{V}\;:\;i\rightarrow j\text{ or
}i\leftrightarrow j\,\text{for some $j\in A$}\big{\\}},$

and the moral graph of $\mathcal{G}$ is
$\mathcal{G}^{m}=(\mathcal{V},\mathcal{E}^{m})$, where $\mathcal{E}^{m}$
consists of the union of

  * •

the set $\mathcal{E}^{u}$ consisting of the edges of $\mathcal{E}$ made
undirected,

  * •

the set of undirected edges of $\mathcal{E}$ that connect pairs of nodes that
are in the border of a component of $\mathcal{G}$.

In Figure 1B the moral graph is obtained by making all edges undirected, and
by adding an undirected edge between $3$ and $4$.

Let $A,B,C$ be three disjoint subsets of $\mathcal{V}$. The sets $A$ and $B$
are _separated_ by $C$ when every path from $i\in A$ to $j\in B$ (or vice
versa) includes at least one node of $C$. Given $A\subseteq V$, the set of
ancestors of $A$, $an_{G}(A)$, is the subset of nodes of $\mathcal{V}$ having
at least one path to some node of $A$.

A random vector $(U_{i}|i\in\mathcal{V})$ is a chain graph model over
$\mathcal{G}$ if it fulfils the _global $\mathcal{G}$-Markovian_ (GM)
property,

$(U_{i}|i\in A)\,\,\perp\,\,(U_{i}|i\in B)\quad|\quad(U_{i}|i\in C),$

whenever $C$ separates $A$ and $B$ in $\mathcal{G}_{an(A\cup B\cup C)}^{m}$
and $X\perp Y|Z$ denotes that the random vectors $X$ and $Y$ are conditionally
independent given $Z$.

Let $(V_{i}|i\in\mathcal{V})$ be a stochastic admixture graph over
$\mathcal{G}$. The Markov structure of the chain graph implies in particular
that two contribution variables $C_{ij},C_{k\ell}$, where $i,k$ are not
necessarily distinct, are conditionally independent given the variables
$V_{i},V_{k}$ of their parents, that is,

$C_{ij}\perp C_{k\ell}\mid(V_{i},V_{k}).$ (11)

Further, for a contribution variable $C_{ij}$, let $B_{n_{i}}$ be the block in
which node $i$ is located. Then

$C_{ij}\perp\left(V_{k}\mid k\in\bigcup\nolimits_{n=1}^{n_{i}}B_{n}\right)\mid
V_{i}.$ (12)

As a consequence of (12), if a node $k$ is in
$\bigcup\nolimits_{n=1}^{n_{i}}B_{n}$, it follows that

$C_{ij}\perp V_{k}\mid V_{i}.$ (13)

## Appendix B

Proofs of statements in the main text are presented here. We start by listing
in Table 1 the possible forms of an a-path between two distinct nodes
$i,j\in\mathcal{V}$. In a,e) there might be only one edge, in the others at
least two. For two a-paths $\gamma,\delta$, the concatenation of $\gamma$ with
$\delta$ is the sequence of edges in $\gamma$ followed by those of $\delta$.
It might or might not be an a-path.

a) | $i$ | $\leftarrow$ | $\ldots$ | $\leftarrow$ | $j$ | d) | $i$ | $\leftrightarrow$ | $\ldots$ | $\to$ | $j$
---|---|---|---|---|---|---|---|---|---|---|---
b) | $i$ | $\leftarrow$ | $\ldots$ | $\leftrightarrow$ | $j$ | e) | $i$ | $\to$ | $\ldots$ | $\to$ | $j$
c) | $i$ | $\leftarrow$ | $\ldots$ | $\to$ | $j$ |  |  |  |  |  |
Table 1: Possible admixture paths according to Definition 2.

######  Lemma 3.

Let $i,j\in\mathcal{V}$ be two distinct nodes of an admixture graph
$\mathcal{G}$, such that not both of them are roots. Then either all a-paths
$\gamma\in\Gamma_{ij}$ end with a directed edge $k\to j$, for some
$k\in\mathcal{V}$, or all a-paths $\gamma\in\Gamma_{ij}$ start with a directed
edge $i\leftarrow k$, for some $k\in\mathcal{V}$, where $k$ might depend on
$\gamma$. ∎

Proof of Lemma 3. It follows by inspecting the possibilities for a-paths.

######  Lemma 4.

Let $i,j\in\mathcal{V}$ be two distinct nodes of an admixture graph
$\mathcal{G}$, such that $i\not\in\mathcal{R}$ and assume that all a-paths
$\gamma\in\Gamma_{ij}$ start with an edge $i\leftarrow k$, for some
$k\in\mathcal{V}$ (as in Lemma 3). Then

$\Gamma_{ij}=\cup_{\ell\in
par(i)}\\{(i\leftarrow\ell,\gamma)\mid\gamma\in\Gamma_{\ell j}\\},$

where $(i\leftarrow\ell,\gamma)$ denotes the concatenation of the a-path
$i\leftarrow\ell$ with $\gamma$. ∎

Proof of Lemma 4. It follows trivially that $\Gamma_{ij}$ is included in the
right hand side of the equality. To prove the converse we need to show that
$(i\leftarrow i^{\prime},\gamma)$, $\gamma\in\Gamma_{i^{\prime}j}$ is an
a-path from $i$ to $j$, that is, the edges are directed according to
Definition 2 (see Table 1) and $i$ does not belong to $\gamma$. By inspection
of the possibilities for $\gamma$, it shows that the edges have the correct
directions (including undirected). Assume $i$ is in $\gamma$. It cannot be a
root by assumption. Then by inspection, either there is a subsequence
$i^{\prime}\leftarrow\ldots\leftarrow i$ of $\gamma$, or a subsequence
$i\to\ldots\to j$. In the former case, this yields a directed cycle from $i$
to $i$ via $i^{\prime}$ by adding the edge $i^{\prime}\to i$. In the latter
case, it yields an a-path from $i$ to $j$, violating the assumption of the
starting edge. Hence the proof is completed. ∎

######  Lemma 5.

Let $i,j,k\in\mathcal{V}$ be distinct nodes of an admixture graph
$\mathcal{G}$, and assume any a-path of $\Gamma_{ij}$ passes through $k$. Then
it holds that

$\Gamma_{ij}=\Gamma_{ik}\times\Gamma_{kj},$

where $(\gamma,\delta)\in\Gamma_{ik}\times\Gamma_{kj}$ denotes concatenation
of $\gamma$ and $\delta$. ∎

Proof of Lemma 5.  We will prove the two sets are included into each other. It
trivially holds that $\Gamma_{ij}\subseteq\Gamma_{ik}\times\Gamma_{kj}$. Next
we prove the converse inclusion. According to Lemma 3, we might assume all
a-paths $\gamma\in\Gamma_{ik}$ start with a directed edge $i\leftarrow
i^{\prime}$, $i^{\prime}\in par(i)$, hence the same is true for the a-paths of
$\Gamma_{ij}$. According to Table 1 this yields $3\cdot 5=15$ possibilities
for the forms of $(\gamma,\delta)$. In the cases (a,a), (a,b), (a,c), (a,d),
(a,e), (b,e), (c,e) the concatenation of $\gamma$ with $\delta$ is an a-path
from $i$ to $j$. The cases (b,a), (b,b), (b,c), (c,d) give impossible
constraints on $k$, hence they cannot occur. The case (b,d) gives
$i\leftarrow\ldots\leftarrow k_{1}\leftrightarrow k\leftrightarrow
k_{2}\to\ldots\to j$ for two roots $k_{1},k_{2}\in\mathcal{R}$. Hence there is
an a-path $i\leftarrow\ldots\leftarrow k_{1}\leftrightarrow k_{2}\to\ldots\to
j$, not going though $k$, which is impossible. The remaining three cases are

|  |  | $\gamma$ |  |  |  | $\delta$ |  |  |
---|---|---|---|---|---|---|---|---|---|---
(c,a) | $i$ | $\leftarrow$ | $\ldots$ | $\to$ | $k$ | $\leftarrow$ | $\ldots$ | $\leftarrow$ | $j$ |
(c,b) | $i$ | $\leftarrow$ | $\ldots$ | $\to$ | $k$ | $\leftarrow$ | $\ldots$ | $\leftrightarrow$ | $j$ |
(c,c) | $i$ | $\leftarrow$ | $\ldots$ | $\to$ | $k$ | $\leftarrow$ | $\ldots$ | $\to$ | $j$ |

The node $k$ cannot be a root, $k\not\in\mathcal{R}$. We will construct an
a-path from $i$ to $j$, based on $\gamma$ and $\delta$, that does not go
through $k$, hence (c,a), (c,b), (c,c) cannot occur. Specifically, there are
three possibilities for the a-path $\gamma$,

$i$ | $\leftarrow$ | $\ldots$ | $\leftarrow$ | $i^{\prime}$ | $\to$ | $\ldots$ | $\to$ | $k$
---|---|---|---|---|---|---|---|---
$i$ | $\leftarrow$ | $\ldots$ | $\leftarrow$ | $r$ | $\to$ | $\ldots$ | $\to$ | $k$
$i$ | $\leftarrow$ | $\ldots$ | $\leftarrow$ |  $r$ $\leftrightarrow$ $r^{\prime}$ | $\to$ | $\ldots$ | $\to$ | $k$

In the first case, there is $r\in\mathcal{R}$ and an a-path $r\to\ldots\to
i^{\prime}$ by definition of an admixture graph. It does not contain $k$ as
this would create a directed cycle. Consequently, in all three cases, there is
$r\in\mathcal{R}$ and an a-path $r\to\ldots\to i$, not containing $k$.

For $\delta$ we can do similarly. In the first case above, there exists
$r^{\prime}\in\mathcal{R}$ and an a-path $r^{\prime}\to\ldots\to j$, not
containing $k$ as this would create a directed cycle. In the second case,
$j\in\mathcal{R}$ and we define $r^{\prime}=j$. In the third case, we proceed
as for $\gamma$ and conclude there is $r^{\prime}\in\mathcal{R}$ and an a-path
$r^{\prime}\to\ldots\to j$, not containing $k$.

Now consider the a-path $\eta$ from $r$ to $i$, and the a-path $\eta^{\prime}$
from $r^{\prime}$ to $j$, constructed above ($r=r^{\prime}$ or
$r\not=r^{\prime}$). If $\eta$ and $\eta^{\prime}$ do not share any nodes,
except perhaps for $r,r^{\prime}$, then their concatenation is an a-path
$(\eta,\eta^{\prime})\in\Gamma_{ij}$, not containing $k$. If they do share
nodes, chose sub-a-paths $\zeta\colon\ell\to\ldots\to i$ and
$\zeta^{\prime}\colon\ell\to\ldots\to j$, sharing only the node $\ell$. Then
their concatenation is an a-path $(\zeta,\zeta^{\prime})\in\Gamma_{ij}$, not
containing $k$. Hence, none of the cases (c,a), (c,b), (c,c) are valid, and
the lemma holds.

Proof of Proposition 1. If $i=j$ then the statements are true by definition.
Given distinct $i,j\in\mathcal{A}$, there exists $r_{1},r_{2}\in\mathcal{R}$
and two a-paths $r_{1}\to i_{1}\to\ldots\to i_{k-1}\to i$ and $r_{2}\to
j_{1}\to\ldots\to j_{k^{\prime}-1}\to j$ for some nodes
$i_{1},\ldots,i_{k-1},j_{1},\ldots,\\\ j_{k^{\prime}-1}\in\mathcal{A}$, and
$k,k^{\prime}\geq 1$ (because the admixture graph is connected and there are
no directed cycles). Either all these nodes are distinct (except perhaps for
$r_{1},r_{2}$) in which case they form an a-path from $i$ to $j$ by
concatenation, or there is $i_{\ell}=i^{\prime}_{\ell^{\prime}}$ for some
$\ell,\ell^{\prime}$. Choose $\ell,\ell^{\prime}$ such that
$\ell+\ell^{\prime}\leq k+k^{\prime}$ is as large as possible. Then
$i\leftarrow i_{k-1}\leftarrow\ldots\leftarrow i_{\ell+1}\leftarrow
i_{\ell}\to i^{\prime}_{\ell^{\prime}+1}\to\ldots\to
i^{\prime}_{k^{\prime}-1}\to j$ is an a-path from $i$ to $j$ by definition of
an a-path. There cannot be any repeated nodes, otherwise $\ell+\ell^{\prime}$
is not as large as possible. If $i,j\in\mathcal{R}$, then they are trivially
connected by an a-path. If $i\in\mathcal{R}$ and $j\in\mathcal{A}$, then there
is an a-path $j\leftarrow i_{k-1},\ldots\leftarrow i_{1}\leftarrow i$
(potentially with $i_{1}\leftrightarrow i$ and $i_{1}$ a root) for some
$i_{1},\ldots,i_{k-1}\in\mathcal{A}$ (as before). Hence
$\Gamma_{ij}\not=\emptyset$.

To prove the second part of the proposition, we proceed by induction in the
length of the a-paths. For $i,j\in\mathcal{V}$, consider $\Gamma_{ij}$ and let
$l_{\gamma}$ denote the number of edges in an a-path $\gamma\in\Gamma_{ij}$.
Assume $l_{\gamma}\leq 0$ for all $\gamma\in\Gamma_{ij}$. Hence $i=j$ and
$\sum_{\gamma\in\Gamma_{ij}}p_{\gamma}=1$ by definition.

Assume now the statement holds if $\sum_{\gamma\in\Gamma_{ij}}p_{\gamma}=1$
and $l_{\gamma}\leq k$, $\gamma\in\Gamma_{ij}$, for some $k\geq 1$. Consider
two nodes $i,j\in\mathcal{V}$ such that all a-paths between them fulfil
$l_{\gamma}\leq k+1$ and start with an edge $i\leftarrow k$ for some
$k\in\mathcal{V}$ (otherwise exchange the roles of $i$ and $j$). Then, using
Lemma 4 to decompose the a-paths according to the parents of $i$, we obtain

$\sum_{\gamma\in\Gamma_{ij}}p_{\gamma}=\sum_{\ell\in
par(i)}\sum_{\gamma\in\Gamma_{\ell j}}\alpha_{i\ell}p_{\gamma}=\sum_{\ell\in
par(i)}\alpha_{i\ell}\sum_{\gamma\in\Gamma_{\ell j}}p_{\gamma}=\sum_{\ell\in
par(i)}\alpha_{i\ell}=1,$

as all a-paths in $\Gamma_{\ell j}$ must have length at most $k$. ∎

Proof of Theorem 1. We will prove
$(ii)\Rightarrow(i)\Rightarrow(iii)\Rightarrow(ii)$. Assume (ii). If the label
$p_{\gamma}$ of an a-path between $i$ and $j$ is one, then
$\Gamma_{ij}=\\{\gamma\\}$, according to Proposition 1. It proves (i). Let
$\mathcal{A}_{r}$ be the nodes in $\mathcal{A}$ for which there is an a-path
from $r\in\mathcal{R}$ to a node in $\mathcal{A}$, not involving any other
root. Any $i\in\mathcal{A}$ is in at least one $\mathcal{A}_{r}$, and cannot
be in two such sets $\mathcal{A}_{r_{1}},\mathcal{A}_{r_{2}}$, because then
there would be a-paths $(r_{1},\ldots,i)$ and $(r_{1},r_{2},\ldots,i)$ from
$r_{1}$ to $i$, contradicting uniqueness of a-paths (i). The set
$\\{r\\}\cup\mathcal{A}_{r}$ with the inherited edges form a tree. It proves
(iii). The last implication is straightforward using the definition of a
forest and taking into account the undirected edges between the roots, so (ii)
is proven. ∎

Proof of Proposition 2. Consider $r_{1}\in\mathcal{R}$. Any a-path
$\gamma_{1}\in\Gamma_{\ell r_{1}}$ contains one root or two roots. In the
latter case, the a-path is the concatenation of an a-path
$\gamma^{\prime}\in\Omega_{\ell r_{2}}$, $r_{2}\not=r_{1}$, with the edge
$r_{2}\leftrightarrow r_{1}$ and $p_{\gamma}=p_{\gamma^{\prime}}$. It follows
that

$\sum\limits_{r\in\mathcal{R}}q_{\ell
r}=\sum\limits_{r\in\mathcal{R}}\sum\limits_{\gamma\in\Omega_{\ell
r}}p_{\gamma}=\sum\limits_{\gamma\in\Gamma_{\ell r_{1}}}p_{\gamma}=1.$

∎

Proof of Proposition 3. For the if and only if, assume (ii). By Definition 4,
we have $\mathcal{V}_{\mathcal{A}_{0}}=\mathcal{V}$ and
$\mathcal{E}_{\mathcal{A}_{0}}=\mathcal{E}$. Oppositely, if
$\mathcal{G}_{\mathcal{A}_{0}}=\mathcal{G}$, then again by Definition 4, (ii)
holds.

We next prove the equivalence between (i) and (ii). (ii) trivially implies
(i). To prove the converse, let $\gamma\in\Gamma_{ik}$, $\delta\in\Gamma_{kj}$
be as stated, sharing only the node $k\in\mathcal{V}\setminus\mathcal{A}_{0}$
and $i,j\in\mathcal{A}_{0}$. There are five possibilities for a-paths, see
Table 1. As $i,j\in\mathcal{A}_{0}$, then d,e) are not an option for $\gamma$,
and a,b) are not an option for $\delta$, yielding nine possible combinations.
By inspection, (a,c), (a,d), (a,e), (b,e), (c,e) yield valid a-paths from $i$
and $j$, hence (ii) holds in these case. The cases (b,c), (c,d) yield
impossible constraint on $k$, and thus cannot occur. The two remaining cases
(b,d), (c,c) give

|  |  | $\gamma$ |  |  |  | $\delta$ |  |  |
---|---|---|---|---|---|---|---|---|---|---
(b,d) | $i$ | $\leftarrow$ | $\ldots$ | $\leftrightarrow$ | $k$ | $\leftrightarrow$ | $\ldots$ | $\to$ | $j$ |
(c,c) | $i$ | $\leftarrow$ | $\ldots$ | $\to$ | $k$ | $\leftarrow$ | $\ldots$ | $\to$ | $j$ |

Since $k\not\in\mathcal{A}_{0}$ then there is an a-path, say $\eta$,
$k\to\ldots\to k^{\prime}$, with $k^{\prime}\in\mathcal{A}_{0}$ (in the first
case we use that every root has a child). If this a-path does not share a node
with $\gamma$ (similarly, with $\delta$) except from $k$, then $\gamma$
concatenated with $\eta$ is an a-path from $i$ to $k^{\prime}$ through $k$, as
required. Otherwise, if $\eta$ shares nodes with both a-paths, let
$k^{\prime\prime}\not=k$ (say in $\delta$, similar if in $\gamma$) be the
first such node counting from $k$. Let $\eta^{\prime}$ be the a-path from $k$
to $j$ given by $k\to\ldots\to k^{\prime\prime}\to\ldots\to j$ by
concatenating the part of $\eta$ ending at $k^{\prime\prime}$ with the part of
$\delta$ beginning at $k^{\prime\prime}$. The edge from $k^{\prime\prime}$
towards $j$ cannot be $\leftrightarrow$ nor $\leftarrow$ for the following
reasons. In the former case, $\to k^{\prime\prime}\leftrightarrow$ which is
impossible. In the latter case, $\delta$ takes the form
$k\leftarrow\ldots\leftarrow k^{\prime\prime}\leftarrow\ldots\leftarrow j$,
creating a directed loop from $k$ to $k^{\prime\prime}$ and back to $k$ via
$\eta^{\prime}$. Finally, $\gamma$ concatenated with $\eta^{\prime}$ is an
a-path from $i$ to $j$ through $k$, as required.

Proof of Theorem 2. A general reference is [9]. Let $V_{i},V_{j}$ be two root
variables, corresponding to distinct roots in $\mathcal{R}$. By definition of
conditional expectation (first equality) and by assumption (second equality)

$\int_{A}V_{i}\,dP=\int_{A}E(V_{i}\mid V_{j})\,dP=\int_{A}V_{j}\,dP$

for all $R_{j}$-measurable subsets $A$. Similarly, by exchanging the role of
$V_{i}$ and $V_{j}$, the same holds for all $V_{i}$-measurable subsets. Hence,

$\int_{A}V_{i}\,dP=\int_{A}V_{j}\,dP$

for all $(V_{i},V_{j})$-measurable subsets $A$. Consequently, using that
$V_{i},V_{j}$ have finite expectation by assumption, it follows that
$V_{i}=V_{j}$. ∎

Proof of Theorem 3. We prove the statement by induction on the maximum number
of edges $n$ of the a-paths $\gamma\in\Gamma_{ij}$. If $n=0$, then $i=j$ and
there is nothing to prove. Assume now (2) for is true for $n=\ell$ and
consider $n=\ell+1$ for some $\ell\geq 1$. Further, assume that $i$ is such
that any a-path of $\Gamma_{ij}$ involves a parent of $i$ as the first node
(Lemma 3). Then using the inductive hypothesis, Proposition 1, Definition
5(ii), Lemma 4 and (1), it holds that

$\displaystyle\sum\limits_{\gamma\in\Gamma_{ij}}p_{\gamma}\sum\limits_{e\in\gamma}d^{\gamma}_{e}$
$\displaystyle=\sum\limits_{i^{\prime}\in
par(i)}\sum\limits_{\gamma^{\prime}\in\Gamma_{i^{\prime}j}}\alpha_{i^{\prime}i}p_{\gamma^{\prime}}\Big{(}d_{i^{\prime}i}^{(i,i^{\prime})}+\sum\limits_{e\in\gamma^{\prime}}d_{e}^{\gamma^{\prime}}\Big{)}$
$\displaystyle=\sum\limits_{i^{\prime}\in
par(i)}\alpha_{i^{\prime}i}\Big{(}d_{i^{\prime}i}^{(i,i^{\prime})}+\sum\limits_{\gamma^{\prime}\in\Gamma_{i^{\prime}j}}p_{\gamma^{\prime}}\sum\limits_{e\in\gamma^{\prime}}d_{e}^{\gamma^{\prime}}\Big{)}$
$\displaystyle=\sum\limits_{i^{\prime}\in
par(i)}\alpha_{i^{\prime}i}\Big{(}C_{i^{\prime}i}-V_{i^{\prime}}+V_{i^{\prime}}-V_{j}\Big{)}$
$\displaystyle=\sum\limits_{i^{\prime}\in
par(i)}\alpha_{i^{\prime}i}C_{i^{\prime}i}-\sum\limits_{i^{\prime}\in
par(i)}\alpha_{i^{\prime}i}V_{j}=V_{i}-V_{j}.$

If any a-path of $\Gamma_{ij}$ does not involve a parent of $i$ as the first
node after $i$, then it holds that any a-path involves a parent of $j$ as
second last node (Lemma 4). Note that $D_{ij}=-D_{ji}$, and that the
decomposition holds for $D_{ji}$. Thus

$\displaystyle D_{ij}$
$\displaystyle=-\sum\limits_{\gamma\in\Gamma_{ji}}p_{\gamma}\sum\limits_{e\in\gamma}d_{e}^{\gamma}=\sum\limits_{\gamma\in\Gamma_{ij}}p_{\gamma}\sum\limits_{e\in\gamma}d_{e}^{\gamma},$

using that the partial drifts change sign when an a-path is reversed. ∎

Proof of Lemma 1.  Let $e_{1}=i\to j$ and $e_{2}=k\to\ell$ (with one of the
two potentially being undirected). Further, assume that the blocks
$B_{n_{i}},B_{n_{k}}$, associated to the nodes $i,k$ are such that $n_{i}\geq
n_{k}$. The expected value in (3) can be rewritten as

$E(d_{ij}d_{k\ell})=E(C_{ij}C_{k\ell})-E(C_{ij}V_{k})-E(C_{k\ell}V_{i})+E(V_{i}V_{k}).$

Consider the first expectation,

$\displaystyle E(C_{ij}C_{k\ell})$
$\displaystyle=E(E(C_{ij}C_{k\ell}|V_{i},V_{k}))=E(E(C_{ij}|V_{i},V_{k})E(C_{k\ell}|V_{i},V_{k}))$
(14)
$\displaystyle=E(E(C_{ij}|V_{i})E(C_{k\ell}|V_{i},V_{k}))=E(V_{i}E(C_{k\ell}|V_{i},V_{k})).$
(15)

Here we used (11), (13) to derive (14), and Definition 5 to derive (15). With
similar considerations, it follows that

$\displaystyle E(C_{k\ell}V_{i})$
$\displaystyle=E(E(C_{k\ell}V_{i}|V_{i},V_{k}))=E(V_{i}E(C_{k\ell}|V_{i},V_{k})).$

Finally,

$\displaystyle E(C_{ij}V_{k})$ $\displaystyle=E(E(C_{ij}V_{k}|V_{i}))$ (16)
$\displaystyle=E(E(C_{ij}|V_{i})E(V_{k}|V_{i}))$ (17)
$\displaystyle=E(V_{i}E(V_{k}|V_{i}))=E(E(V_{i}V_{k}|V_{i}))=E(V_{i}V_{k}),$
(18)

using (13) and Definition 5(ii) to derive (16) and (17), respectively, and
properties of the conditional expectation to derive (18). Combining it all
yields $E(d_{ij}d_{k\ell})=0$. Finally consider
$E(d_{ij}^{2})=E(C_{ij}^{2}+V_{i}^{2}-2C_{ij}V_{i})$. Using the definition of
variance and Definition 5(ii), it follows that

$E(C_{ij}^{2})=Var(C_{ij})+E(V_{i})^{2}\quad\text{and}\quad
E(V_{i}^{2})=Var(V_{i})+E(V_{i})^{2}.$

By conditioning on $V_{i}$ and using Definition 5(ii) again, we have
$E(C_{ij}V_{i})=-Var(V_{i})-E(V_{i})^{2}$. Using the linearity of the
expectation it can be concluded that $E(d_{ij}^{2})=Var(C_{ij})-Var(V_{i})$. ∎

Proof of Theorem 4. Rewrite the definition of $F_{2}(i,j)$ using the
decomposition of drift in (2),

$\begin{split}F_{2}(i,j)&=E\Biggl{[}\;\left(\sum\limits_{\gamma_{1}\in\Gamma_{ij}}\left(p_{\gamma_{1}}\sum\limits_{e_{1}\in\gamma_{1}}d^{\gamma_{1}}_{e_{1}}\right)\right)\left(\sum\limits_{\gamma_{2}\in\Gamma_{ij}}\left(p_{\gamma_{2}}\sum\limits_{e_{2}\in\gamma_{2}}d^{\gamma_{2}}_{e_{2}}\right)\right)\;\Biggr{]}.\end{split}$
(19)

Distributing the products and exploiting the linearity of the expectation,
(19) is equivalent to

$\displaystyle F_{2}(i,j)$
$\displaystyle=\sum\limits_{(\gamma_{1},\gamma_{2})\in\Gamma_{ij}\times\Gamma_{ij}}\sum\limits_{e_{1}\in\gamma_{1}}\sum\limits_{e_{2}\in\gamma_{2}}p_{\gamma_{1}}p_{\gamma_{2}}E(d^{\gamma_{1}}_{e_{1}}d^{\gamma_{2}}_{e_{2}}),$
$\displaystyle=\sum\limits_{(e_{1},e_{2})\in\mathcal{E}_{ij}\times\mathcal{E}_{ij}}\;\sum\limits_{(\gamma_{1},\gamma_{2})\in\Gamma_{ij}^{e_{1}}\times\Gamma_{ij}^{e_{2}}}p_{\gamma_{1}}p_{\gamma_{2}}E(d^{\gamma_{1}}_{e_{1}}d^{\gamma_{2}}_{e_{2}}).$

Observe that $\mathcal{E}_{ij}$ is the disjoint union of
$\mathcal{E}_{ij}^{d}$ and $\mathcal{E}_{ij}^{u}$. Moreover, the product of
two distinct edges, where at least one is directed, has expectation zero, see
Lemma 1. Thus

$\displaystyle F_{2}(i,j)$
$\displaystyle=\sum\limits_{e\in\mathcal{E}^{d}_{ij}}\;\sum\limits_{(\gamma_{1},\gamma_{2})\in\Gamma_{ij}^{e}\times\Gamma_{ij}^{e}}\text{sign}_{\gamma_{1}}\\!(e)\,\text{sign}_{\gamma_{2}}\\!(e)p_{\gamma_{1}}p_{\gamma_{2}}\,E(d_{e}^{2})$
$\displaystyle+\sum\limits_{(e_{1},e_{2})\in\mathcal{E}^{u}_{ij}\times\mathcal{E}^{u}_{ij}}\;\sum\limits_{(\gamma_{1},\gamma_{2})\in\Gamma_{ij}^{e_{1}}\times\Gamma_{ij}^{e_{2}}}\text{sign}_{\gamma_{1}}\\!(e_{1})\,\text{sign}_{\gamma_{2}}\\!(e_{2})\,p_{\gamma_{1}}p_{\gamma_{2}}\,E(d_{e_{1}}d_{e_{2}})$
$\displaystyle=\sum\limits_{e\in\mathcal{E}^{d}_{ij}}A_{e}^{(i,j)}E(d_{e}^{2})+\sum\limits_{(e_{1},e_{2})\in\mathcal{E}^{u}_{ij}\times\mathcal{E}^{u}_{ij}}B_{e_{1},e_{2}}^{(i,j)}E(d_{e_{1}}d_{e_{2}}).$

∎

Proof of Lemma 2.  (i) Let $i,j\in\mathcal{V}$ and $e\in\mathcal{E}$. Using
Proposition 1, $\Gamma_{ij}^{e_{1}}\subseteq\Gamma_{ij}$ and the definition of
the sign function, it follows that

$\displaystyle
1=\sum\nolimits_{\gamma_{1}\in\Gamma_{ij}}p_{\gamma_{1}}\geq\sum\nolimits_{\gamma_{1}\in\Gamma^{e_{1}}_{ij}}p_{\gamma_{1}}\geq\sum\nolimits_{\gamma_{1}\in\Gamma^{e_{1}}_{ij}}\text{sign}_{\gamma_{1}}\\!(e_{1})p_{\gamma_{1}}.$
(20)

An analogous inequality holds by changing the sign of each term. The same
results apply to the pair of nodes $k,\ell\in\mathcal{V}$. Therefore

$\displaystyle-1\leq\big{(}\sum\nolimits_{\gamma_{1}\in\Gamma^{e_{1}}_{ij}}\text{sign}_{\gamma_{1}}\\!(e_{1})p_{\gamma_{1}}\big{)}\big{(}\sum\nolimits_{\gamma_{2}\in\Gamma^{e_{2}}_{k\ell}}\text{sign}_{\gamma_{2}}\\!(e_{2})p_{\gamma_{2}}\big{)}\leq+1,$

hence the statement is proved. (ii) The value of
$|B_{e_{1},e_{2}}^{(i,j)(k,\ell)}|$ is $1$ if and only if each of the two
factors of the $B$-coefficient assumes the value $\pm 1$. Equivalently, (20)
and the analogous with changed sign, has an equality for both pairs of nodes
$(i,j)$ and $(k,\ell)$. This is verified only under the conditions
contemplated in statement (ii), hence (ii) is proved. (iii) Observe that, if
two distinct a-paths of $\Gamma_{ij}$ share some edges, they must go through
two different outgoing edges of a shared node, thus their path labels differ
for at least one edge label in their factorization. An analogous statement
holds for a-paths of $\Gamma_{k\ell}$. Hence there are no terms resulting from
the product in (5) that can sum to zero. Therefore it holds that
$B_{e_{1},e_{2}}^{(i,j)(k,\ell)}=0$ for all $\alpha_{e},\,e\in\mathcal{E}$, if
and only if one of the two factors in (5) is equal to zero for all
$\alpha_{e},\,e\in\mathcal{E}$ (see [4, p. 4]). Thus at least one of these
factors is equal to zero [4, p. 510]. This condition is verified if and only
if one or both sets $\Gamma_{ij}^{e_{1}}$ and $\Gamma_{k\ell}^{e_{2}}$ do not
contain any a-path. ∎

Proof of Proposition 4.  Assume that all a-paths of $\Gamma_{ij}$ pass through
$k$, and that $i,j,k$ are all distinct, otherwise there is nothing to prove.
By Lemma 5,

$\Gamma_{ij}=\Gamma_{ik}\times\Gamma_{kj},$

where $(\gamma,\delta)\in\Gamma_{ik}\times\Gamma_{kj}$ denotes concatenation
of $\gamma$ and $\delta$. By Lemma 1, we have

$\displaystyle D_{ij}$
$\displaystyle=\sum\nolimits_{\eta\in\Gamma_{ij}}\Big{(}p_{\eta}\sum\nolimits_{e\in\eta}d^{\eta}_{e}\Big{)}$
$\displaystyle=\sum\nolimits_{\gamma\in\Gamma_{ik}}\sum\nolimits_{\delta\in\Gamma_{kj}}\Big{(}p_{\gamma}p_{\delta}\left(\sum\nolimits_{e\in\gamma}d^{\gamma}_{e}+\sum\nolimits_{e\in\delta}d^{\delta}_{e}\right)\Big{)}$
$\displaystyle=D_{ik}+D_{kj},$

using Lemma 4, the definition of path label and drift. Hence
$D_{ij}^{2}=D_{ik}^{2}+D_{kj}^{2}+2D_{ik}D_{kj}$. Note that no edge can be
shared between $\gamma\in\Gamma_{ik}$ and $\delta\in\Gamma_{kj}$, as
$(\gamma,\delta)\in\Gamma_{ij}$ is an a-path. Similarly, there can at most be
one undirected edge in $(\gamma,\delta)$, hence by Lemma 1,
$E(D_{ik}D_{kj})=0$, and

$F_{2}(i,j)=E(D_{ij}^{2})=E(D_{ik}^{2})+E(D_{kj}^{2})=F_{2}(i,k)+F_{2}(k,j).$

For the reverse statement, assume there exists an a-path
$\gamma\in\Gamma_{ij}$ that does not pass through $k$, and assume that all
a-paths of $\Gamma_{ij}$ start with an edge of type $i\leftarrow i^{\prime}$,
for some $i^{\prime}\in par(i)$, i.e. they are of type (a,b,c,d) (see Table
1). Then there is at least one pair of a-paths
$\gamma_{1}\in\Gamma_{ik},\,\gamma_{2}\in\Gamma_{kj}$ sharing edges. In fact,
denote by $\delta_{1},\delta_{2}$ the two subpaths of $\gamma$ from $i$ to
$k^{\prime}$ and from $k^{\prime}$ to $j$, respectively. Here, $k^{\prime}$ is
the first node not having parents in $\gamma$, so that $\delta_{1}$ is fixed
as an a-path of type (a), whereas $\delta_{2}$ can be of type (d) or (e). From
Proposition 1, there is an a-path $\delta_{1}^{\prime}\in\Gamma_{k^{\prime}k}$
that can be of any type. Let $\delta_{2}^{\prime}\in\Gamma_{kk^{\prime}}$ be
the reverse a-path of $\delta_{1}^{\prime}$. It is possible to verify by
inspection that the concatenations
$\gamma_{1}=(\delta_{1},\delta_{1}^{\prime}),\gamma_{2}=(\delta_{2}^{\prime},\delta_{2})$,
are two a-paths of $\Gamma_{ik},\,\Gamma_{kj}$, respectively, and share the
edges of $\delta_{1}^{\prime}$ and $\delta_{2}^{\prime}$. With an analogous
construction, the same holds for the other possible types of a-paths of
$\Gamma_{ij}$.

Since $F_{2}(i,j)=F_{2}(i,k)+F_{2}(k,j)$, then $E(D_{ik}D_{kj})=0$. Note that

$\displaystyle E(D_{ik}D_{kj})$
$\displaystyle=\sum\limits_{\begin{subarray}{c}\gamma_{1}\in\Gamma_{ik}\\\
\gamma_{2}\in\Gamma_{kj}\end{subarray}}p_{\gamma_{1}}p_{\gamma_{2}}\sum\limits_{e\in\mathcal{E}_{ik}\cap\mathcal{E}_{kj}}\text{sign}_{\gamma_{1}}(e)\text{sign}_{\gamma_{2}}(e)E(d_{e}^{2})$
$\displaystyle=\sum\limits_{e\in\mathcal{E}}\Bigg{(}\sum\limits_{\gamma_{1}\in\Gamma_{ik}}\text{sign}_{\gamma_{1}}(e)p_{\gamma_{1}}\Bigg{)}\Bigg{(}\sum\limits_{\gamma_{2}\in\Gamma_{kj}}\text{sign}_{\gamma_{2}}(e)p_{\gamma_{2}}\Bigg{)}E(d_{e}^{2})$

where we have used the definition of sign and the linearity of expectation.
The expression is linear in $E(d_{e}^{2})$, $e\in\mathcal{E}$, hence if
$E(D_{ik}D_{kj})=0$ for arbitrary (positive) values of $E(d_{e}^{2})$, then
the coefficient of $E(d_{e}^{2})$, $e\in\mathcal{E}$, is zero. The argument in
the proof of Lemma 2(iii) also applies here to conclude that either of the two
factors in the coefficient is zero. Since $\Gamma_{ik}\not=\emptyset$ and
$\Gamma_{kj}\not=\emptyset$ (assuming $i,j,k$ are different), then
$\text{sign}_{\gamma_{1}}(e)=\text{sign}_{\gamma_{2}}(e)=0$, contradicting the
existence of a pair of overlapping a-paths. Therefore all a-paths of
$\Gamma_{ij}$ go through $k$. ∎

Proof of Proposition 5.  Assume $F_{3-}(i;j,k)\neq 0$. Then there is at least
one edge $e\in\mathcal{E}$ for which $A_{e-}^{(i,j)(i,k)}\neq 0$. It follows
that there is a pair of a-paths
$(\gamma_{1},\gamma_{2})\in\Gamma_{ij}^{e}\times\Gamma_{ik}^{e}$ such that
$\text{sign}_{\gamma_{1}}(e)\neq\text{sign}_{\gamma_{2}}(e)$. Let us consider
the possible combinations of two a-paths
$(\gamma_{1},\gamma_{2})\in\Gamma_{ij}\times\Gamma_{ik}$ from Table 1, and
verify for which pairs it is possible to have
$\text{sign}_{\gamma_{1}}(e)\neq\text{sign}_{\gamma_{2}}(e)$. By inspection,
it is immediate to verify that $e$ has the same sign in the combinations
(a,a), (a,b), (a,c), (b,d), (d,d) (e,e). Combination (a,d) is not possible,
because $i$ would be a root and an admixed node at the same time. Combinations
(a,e), (b,e), (c,e) and (d,e) imply that
$e\notin\Gamma_{ij}^{e}\cap\Gamma_{ik}^{e}$. There remains combinations (b,b),
(b,c) and (c,c), that admit one or more shared edges of opposite sign in the
two paths. The opposite implication is immediate by definition of
$F_{3-}(i;j,k)$ and $A_{e-}^{(i,j)(i,k)}$. ∎

Proof of Proposition 6. We will prove a slightly stronger statement, namely

$E(V_{j}(1-V_{j^{\prime}}))=\sum_{(r,r^{\prime})\in\mathcal{R}\times\mathcal{R}}D_{r,r^{\prime}}^{j,j^{\prime}}E(V_{r}(1-V_{r^{\prime}})),\quad
j,j^{\prime}\in\mathcal{V},$

by induction on the block index (Appendix A), and where
$D_{r,r^{\prime}}^{j,j^{\prime}}$ are non-negative and sum to at most one over
$r,r^{\prime}$ for any $j,j^{\prime}$.

First consider nodes $j,j^{\prime}\in B_{1}=\mathcal{R}$. By defining
$D^{j,j^{\prime}}_{r,r^{\prime}}=1$ if $r=j$, $r^{\prime}=j^{\prime}$, and
zero otherwise, we have

$E(V_{j}(1-V_{j^{\prime}}))=\sum_{(r,r^{\prime})\in\mathcal{R}\times\mathcal{R}}D_{r,r^{\prime}}^{j,j^{\prime}}E(V_{r}(1-V_{r^{\prime}})),$

and the claim holds for $j,j^{\prime}\in B_{1}$. Now assume the statement
holds for nodes in $\cup_{k=1}^{m}B_{k}$, $m\geq 1$, and consider
$j,j^{\prime}\in\cup_{k=1}^{m+1}B_{k}$ such that at least one of
$j,j^{\prime}$ is in $B_{m+1}$, say $j\in B_{m+1}$ (similar if $j^{\prime}\in
B_{m+1}$). If $j\not\in B_{1}$ then

$\displaystyle E(V_{j}(1-V_{j^{\prime}}))$ $\displaystyle=E\left(\sum_{i\in
par(j)}\alpha_{ij}C_{ij}\left(1-\sum_{i^{\prime}\in
par(j^{\prime})}\alpha_{i^{\prime}j^{\prime}}C_{i^{\prime}j^{\prime}}\right)\right)$
(21) $\displaystyle=\sum_{(i,i^{\prime})\in par(j)\times
par(j^{\prime})}\alpha_{ij}\alpha_{i^{\prime}j^{\prime}}E(C_{ij}(1-C_{i^{\prime}j^{\prime}})),$

using that $1=\sum_{i^{\prime}\in
par(j^{\prime})}\alpha_{i^{\prime}j^{\prime}}$. If
$(i,j)\not=(i^{\prime},j^{\prime})$ then
$E(C_{ij}(1-C_{i^{\prime}j^{\prime}}))=E(V_{i}(1-V_{i^{\prime}}))$ by
conditioning on $(V_{i},V_{i^{\prime}})$ and using Definition 5(iii). If
$(i,j)=(i^{\prime},j^{\prime})$ then
$E(C_{ij}(1-C_{ij})=e^{-\tau_{ij}}E(V_{i}(1-V_{i})$, where $\tau_{ij}$ is the
population scaled time from $i$ and $j$ [12]. Define
$P(j,j^{\prime})=par(j)\times par(j^{\prime})$. Then

$\displaystyle E(V_{j}(1-V_{j^{\prime}}))$
$\displaystyle=\sum_{(i,i^{\prime})\in
P(j,j^{\prime})}e^{-\tau_{ij}\delta_{ii^{\prime}}}\alpha_{ij}\alpha_{i^{\prime}j^{\prime}}E(V_{i}(1-V_{i^{\prime}}))$
$\displaystyle=\sum_{(i,i^{\prime})\in
P(j,j^{\prime})}e^{-\tau_{ij}\delta_{ii^{\prime}}}\alpha_{ij}\alpha_{i^{\prime}j^{\prime}}\sum_{(r,r^{\prime})\in\mathcal{R}\times\mathcal{R}}D_{r,r^{\prime}}^{i,i^{\prime}}E(V_{r}(1-V_{r^{\prime}}))$
$\displaystyle=\sum_{(r,r^{\prime})\in\mathcal{R}\times\mathcal{R}}\left[\sum_{(i,i^{\prime})\in
P(j,j^{\prime})}e^{-\tau_{ij}\delta_{ii^{\prime}}}\alpha_{ij}\alpha_{i^{\prime}j^{\prime}}D_{r,r^{\prime}}^{i,i^{\prime}}E(V_{r}(1-V_{r^{\prime}}))\right]$
$\displaystyle=\sum_{(r,r^{\prime})\in\mathcal{R}\times\mathcal{R}}D_{r,r^{\prime}}^{j,j^{\prime}}E(V_{r}(1-V_{r^{\prime}}))$

where the second line holds by induction hypothesis since
$i,i^{\prime}\in\cup_{k=1}^{m}B_{k}$, $\delta_{ii^{\prime}}=1$ if
$i=i^{\prime}$ and zero otherwise, and

$D_{r,r^{\prime}}^{j,j^{\prime}}=\sum_{(i,i^{\prime})\in
P(j,j^{\prime})}e^{-\tau_{ij}\delta_{ii^{\prime}}}\alpha_{ij}\alpha_{i^{\prime}j^{\prime}}D_{r,r^{\prime}}^{i,i^{\prime}}.$

It is easily seen that the constants above have the desired properties. If
$j\in B_{1}$ (similar if $j^{\prime}\in B_{1}$) then we do the same as above
except only $V_{j^{\prime}}$ is replaced by a sum in (21). We obtain similarly
to (21),

$\displaystyle E(V_{j}(1-V_{j^{\prime}}))$ $\displaystyle=\sum_{i^{\prime}\in
par(j^{\prime})}\alpha_{i^{\prime}j^{\prime}}E(V_{j}(1-C_{i^{\prime}j^{\prime}}))$
$\displaystyle=\sum_{i^{\prime}\in
par(j^{\prime})}\alpha_{i^{\prime}j^{\prime}}E(V_{j}(1-V_{i^{\prime}}))$
$\displaystyle=\sum_{i^{\prime}\in
par(j^{\prime})}\alpha_{i^{\prime}j^{\prime}}\\!\\!\\!\sum_{(r,r^{\prime})\in\mathcal{R}\times\mathcal{R}}D_{r,r^{\prime}}^{j,i^{\prime}}E(V_{r}(1-V_{r^{\prime}}))$
$\displaystyle=\sum_{(r,r^{\prime})\in\mathcal{R}\times\mathcal{R}}D_{r,r^{\prime}}^{j,j^{\prime}}E(V_{r}(1-V_{r^{\prime}})),$

where

$D_{r,r^{\prime}}^{j,j^{\prime}}=\sum_{i^{\prime}\in
par(j^{\prime})}\alpha_{i^{\prime}j^{\prime}}D_{r,r^{\prime}}^{j,i^{\prime}}.$

If $j^{\prime}\in B_{1}$ then the role of $j$ and $j^{\prime}$ is reversed,
yielding a similar answer. In both cases the constants fulfil the desired
requirements.

Letting $j=j^{\prime}$ yields the desired result. ∎


#  solo-learn: A Library of Self-supervised Methods
for Visual Representation Learning

Victor G. Turrisi da Costa<EMAIL_ADDRESS>
University of Trento - Trento, Italy Enrico Fini††footnotemark:
<EMAIL_ADDRESS>
University of Trento - Trento, Italy Moin Nabi<EMAIL_ADDRESS>
SAP AI Research - Berlin, Germany Nicu Sebe<EMAIL_ADDRESS>
University of Trento - Trento, Italy Elisa Ricci<EMAIL_ADDRESS>
University of Trento and Fondazione Bruno Kessler - Trento, Italy Victor G.
Turrisi da Costa and Enrico Fini contributed equally.

###### Abstract

This paper presents solo-learn, a library of self-supervised methods for
visual representation learning. Implemented in Python, using Pytorch and
Pytorch lightning, the library fits both research and industry needs by
featuring distributed training pipelines with mixed-precision, faster data
loading via Nvidia DALI, online linear evaluation for better prototyping, and
many additional training tricks. Our goal is to provide an easy-to-use library
comprising a large amount of Self-supervised Learning (SSL) methods, that can
be easily extended and fine-tuned by the community. solo-learn opens up
avenues for exploiting large-budget SSL solutions on inexpensive smaller
infrastructures and seeks to democratize SSL by making it accessible to all.
The source code is available at https://github.com/vturrisi/solo-learn.

Keywords: Self-supervised methods, contrastive learning

##  1 Introduction

Deep networks trained with large annotated datasets have shown stunning
capabilities in the context of computer vision. However, the need for human
supervision is a strong limiting factor. Unsupervised learning aims to
mitigate this issue by training models from unlabeled datasets. The most
prominent paradigm for unsupervised visual representation learning is Self-
supervised Learning (SSL), where the intrinsic structure of the data provides
supervision for the model. Recently, the scientific community devised
increasingly effective SSL methods that match or surpass the performance of
supervised methods. Nonetheless, implementing and reproducing such works turns
out to be complicated. Official repositories of state-of-the-art SSL methods
have very heterogeneous implementations or no implementation at all. Although
a few SSL libraries (Goyal et al., 2021; Susmelj et al., 2020) are available,
they assume that larger-scale infrastructures are available or they lack some
recent methods. When approaching SSL, it is hard to find a platform for
experiments that allows running all current state of the art methods with low
engineering effort and at the same time is effective and straightforward to
train. This is especially problematic because, while the SSL methods seem
simple on paper, replication of published results can involve a huge time and
effort from researchers. Sometimes official implementations of SSL methods are
available, however, releasing standalone packages (often incompatible with
each other) is not sufficient for the fast-paced progress in research and
emerging real-world applications. There is no toolbox offering a genuine off-
the-shelf catalog of state-of-the-art SSL techniques that is computationally
efficient, which is essential for in-the-wild experimentation.

To address these problems, we present solo-learn, an open-source framework
that provides standardized implementations for a large number of state-of-the-
art SSL methods. We believe solo-learn will enable a trustworthy and
reproducible comparison between the state of the art methods. The code that
powers the library is written in Python, using Pytorch (Paszke et al., 2019)
and Pytorch Lightning(PL) (Team, 2019) as back-ends and Nvidia
DALI111https://github.com/NVIDIA/DALI for fast data loading, and supports more
modern methods than related libraries. The library is highly modular and can
be used as a complete pipeline, from training to evaluation, or as standalone
modules.

##  2 The solo-learn Library: An Overview

Currently, we are witnessing an explosion of works on SSL methods for computer
vision. Their underlying idea is to unsupervisedly learn feature
representations by enforcing similar feature representations across multiple
views from the same image while enforcing diverse representations for other
images. To help researchers have a common testbed for reproducing different
results, we present solo-learn, which is a library of self-supervised methods
for visual representation learning. The library is implemented in Pytorch,
providing state-of-the-art self-supervised methods, distributed training
pipelines with mixed-precision, faster data loading, online linear evaluation
for better prototyping, and many other training strategies and tricks
presented in recent papers. We also provide an easy way to use the pre-trained
models for object detection, via DetectronV2 (Wu et al., 2019). Our goal is to
provide an easy-to-use library that can be easily extended by the community,
while also including additional features that make it easier for researchers
and practitioners to train on smaller infrastructures.

###  2.1 Self-supervised Learning Methods

We implemented 13 state-of-the-art methods, namely, Barlow Twins (Zbontar et
al., 2021), BYOL (Grill et al., 2020), DeepCluster V2 (Caron et al., 2020),
DINO (Caron et al., 2021), MoCo V2+ (Chen et al., 2020b), NNCLR (Dwibedi et
al., 2021), ReSSL (Zheng et al., 2021), SimCLR (Chen et al., 2020a),
Supervised Contrastive Learning (Khosla et al., 2020), SimSiam (Chen and He,
2021), SwAV (Caron et al., 2020), VICReg (Bardes et al., 2021) and W-MSE
(Ermolov et al., 2021).

###  2.2 Architecture

Figure 1: Overview of solo-learn.

In Figure 1, we present an overview of how a training pipeline with solo-learn
is carried out. In the bottom, we show the packages and external data at each
step, while at the top, we show all the defined variables on the left and an
example of the newest defined variable on the right. First, the user interacts
with solo.args, a subpackage that is responsible for handling all the
parameters selected by the user and providing automatic setup. Then,
solo.methods interacts with solo.losses to produce the selected self-
supervised method. While solo.methods contains all implemented methods,
solo.losses contains the loss functions for each method. Afterwards,
solo.utils handles external data to produce the pretrain dataloader, which
contains all the transformation pipelines, model checkpointer, automatic UMAP
visualization of the features, other backbone networks, such as ViT
(Dosovitskiy et al., 2021) and Swin (Liu et al., 2021), and many other utility
functionalities. Lastly, this is given to a PL trainer, which provides
hardware support and extra functionality, such as, distributed training,
automatic logging results, mixed precision and much more. We note that
although we show all subpackages working together, they can be used in a
standalone fashion with minor modifications. Apart from that, we have
documentations in the folder docs, downstream tasks in downstream, unit tests
in tests and pretrained models in zoo.

###  2.3 Comparison to Related Libraries

The most related libraries to ours are VISSL (Goyal et al., 2021) and Lightly
(Susmelj et al., 2020), which lack some of our key features. First, we support
more modern SSL methods, such as BYOL, NNCLR, SimSiam, VICReg, W-MSE and
others. Second, we target researchers with fewer resources, namely from 1 to 8
GPUs, allowing much faster data loading via DALI. Lastly, we provide
additional utilities, such as automatic linear evaluation, support to custom
datasets and automatically generating UMAP (McInnes et al., 2020)
visualizations of the features during training.

##  3 Experiments

#### Benchmarks.

We benchmarked the available SSL methods on CIFAR-10 (Krizhevsky et al.,
2009), CIFAR-100 Krizhevsky et al. (2009) and ImageNet-100 (Deng et al., 2009)
and made public the pretrained checkpoints. For Barlow Twins, BYOL, MoCo V2+,
NNCLR, SimCLR and VICReg, hyperparameters were heavily tuned, reaching higher
performance than reported on original papers or third-party results. Tab. 1
presents the top-1 and top-5 accuracy values for the online linear evaluation.
For ImageNet-100, traditional offline linear evaluation is also reported. We
also compare with the results reported by Lightly in Tab. 3.

#### Nvidia DALI vs traditional data loading.

We compared the training speeds and memory usage of using traditional data
loading via Pytorch Vision222https://github.com/pytorch/vision against data
loading with DALI. For consistency, we ran three different methods (Barlow
Twins, BYOL and NNCLR) for 20 epochs on ImageNet-100. Tab. 3 presents these
results.

Table 1: Online linear evaluation accuracy on CIFAR-10, CIFAR-100 and ImageNet-100. In brackets, offline linear evaluation accuracy is also reported for ImageNet-100. Method | CIFAR-10 | CIFAR-100 | ImageNet-100
---|---|---|---
Acc@1 | Acc@5 | Acc@1 | Acc@5 | Acc@1 | Acc@5
Barlow Twins | 92.10 | 99.73 | 70.90 | 91.91 | 80.38 (80.16) | 95.28 (95.14)
BYOL | 92.58 | 99.79 | 70.46 | 91.96 | 80.16 (80.32) | 94.80 (94.94)
DeepCluster V2 | 88.85 | 99.58 | 63.61 | 88.09 | 75.36 (75.40) | 93.22 (93.10)
DINO | 89.52 | 99.71 | 66.76 | 90.34 | 74.84 (74.92) | 92.92 (92.78)
MoCo V2+ | 92.94 | 99.79 | 69.89 | 91.65 | 78.20 (79.28) | 95.50 (95.18)
NNCLR | 91.88 | 99.78 | 69.62 | 91.52 | 79.80 (80.16) | 95.28 (95.28)
ReSSL | 90.63 | 99.62 | 65.92 | 89.73 | 76.92 (78.48) | 94.20 (94.24)
SimCLR | 90.74 | 99.75 | 65.78 | 89.04 | 77.04 (77.48) | 94.02 (93.42)
Simsiam | 90.51 | 99.72 | 66.04 | 89.62 | 74.54 (78.72) | 93.16 (94.78)
SwAV | 89.17 | 99.68 | 64.88 | 88.78 | 74.04 (74.28) | 92.70 (92.84)
VICReg | 92.07 | 99.74 | 68.54 | 90.83 | 79.22 (79.40) | 95.06 (95.02)
W-MSE | 88.67 | 99.68 | 61.33 | 87.26 | 67.60 (69.06) | 90.94 (91.22)

Table 2: Speed and memory comparison with and without DALI on ImageNet-100. Method |  DALI | 20 epochs | 1 epoch | Speedup | Memory
---|---|---|---|---|---
Barlow Twins |  | 1h 38m 27s | 4m 55s | - | 5097 MB
✓ | 43m 2s | 2m 10s | 56% | 9292 MB
BYOL |  | 1h 38m 46s | 4m 56s | - | 5409 MB
✓ | 50m 33s | 2m 31s | 49% | 9521 MB
NNCLR |  | 1h 38m 30s | 4m 55s | - | 5060 MB
✓ | 42m 3s | 2m 6s | 64% | 9244 MB

Table 3: Comparison with Lightly on CIFAR10. Method | Ours | Lightly
---|---|---
SimCLR | 90.74 | 89.0
MoCoV2+ | 92.94 | 90.0
SimSiam | 90.51 | 91.0

##  4 Conclusion

Here, we presented solo-learn, a library of self-supervised methods for visual
representation learning, providing state-of-the-art self-supervised methods in
Pytorch. The library supports distributed training, fast data loading and
provides many utilities for the end-user, such as online linear evaluation for
better prototyping and faster development, many training tricks, and
visualization techniques. We are continuously adding new SSL methods,
improving usability, documents, and tutorials. Finally, we welcome
contributors to help us at https://github.com/vturrisi/solo-learn.

Acknowledgments. This work was supported by a joint project under Grant No.
JQ18012, by the EU H2020 AI4Media No. 951911 project and the European
Institute of Innovation & Technology (EIT).

## References

  * Bardes et al. (2021) Adrien Bardes, Jean Ponce, and Yann LeCun.  Vicreg: Variance-invariance-covariance regularization for self-supervised learning.  _arXiv:2105.04906_ , 2021.
  * Caron et al. (2020) Mathilde Caron, Ishan Misra, Julien Mairal, Priya Goyal, Piotr Bojanowski, and Armand Joulin.  Unsupervised learning of visual features by contrasting cluster assignments.  In _NeurIPS_ , 2020.
  * Caron et al. (2021) Mathilde Caron, Hugo Touvron, Ishan Misra, Hervé Jégou, Julien Mairal, Piotr Bojanowski, and Armand Joulin.  Emerging properties in self-supervised vision transformers.  _arXiv:2104.14294_ , 2021.
  * Chen et al. (2020a) Ting Chen, Simon Kornblith, Mohammad Norouzi, and Geoffrey Hinton.  A simple framework for contrastive learning of visual representations.  In _ICML_ , 2020a.
  * Chen and He (2021) Xinlei Chen and Kaiming He.  Exploring simple siamese representation learning.  In _CVPR_ , 2021.
  * Chen et al. (2020b) Xinlei Chen, Haoqi Fan, Ross Girshick, and Kaiming He.  Improved baselines with momentum contrastive learning.  _arXiv:2003.04297_ , 2020b.
  * Deng et al. (2009) Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei.  Imagenet: A large-scale hierarchical image database.  In _2009 IEEE conference on computer vision and pattern recognition_ , 2009.
  * Dosovitskiy et al. (2021) Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, Jakob Uszkoreit, and Neil Houlsby.  An image is worth 16x16 words: Transformers for image recognition at scale.  _ICLR_ , 2021.
  * Dwibedi et al. (2021) Debidatta Dwibedi, Yusuf Aytar, Jonathan Tompson, Pierre Sermanet, and Andrew Zisserman.  With a little help from my friends: Nearest-neighbor contrastive learning of visual representations.  _arXiv:2104.14548_ , 2021.
  * Ermolov et al. (2021) Aleksandr Ermolov, Aliaksandr Siarohin, Enver Sangineto, and Nicu Sebe.  Whitening for self-supervised representation learning.  In _ICML_ , 2021.
  * Goyal et al. (2021) Priya Goyal, Quentin Duval, Jeremy Reizenstein, Matthew Leavitt, Min Xu, Benjamin Lefaudeux, Mannat Singh, Vinicius Reis, Mathilde Caron, Piotr Bojanowski, Armand Joulin, and Ishan Misra.  Vissl.  _GitHub. Note: https://github.com/facebookresearch/vissl_ , 2021.
  * Grill et al. (2020) Jean-Bastien Grill, Florian Strub, Florent Altché, Corentin Tallec, Pierre Richemond, Elena Buchatskaya, Carl Doersch, Bernardo Avila Pires, Zhaohan Guo, Mohammad Gheshlaghi Azar, Bilal Piot, koray kavukcuoglu, Remi Munos, and Michal Valko.  Bootstrap your own latent - a new approach to self-supervised learning.  In _NeurIPS_ , 2020.
  * Khosla et al. (2020) Prannay Khosla, Piotr Teterwak, Chen Wang, Aaron Sarna, Yonglong Tian, Phillip Isola, Aaron Maschinot, Ce Liu, and Dilip Krishnan.  Supervised contrastive learning.  _NeurIPS_ , 2020.
  * Krizhevsky et al. (2009) Alex Krizhevsky, Vinod Nair, and Geoffrey Hinton.  Learning multiple layers of features from tiny images.  2009\.
  * Liu et al. (2021) Ze Liu, Yutong Lin, Yue Cao, Han Hu, Yixuan Wei, Zheng Zhang, Stephen Lin, and Baining Guo.  Swin transformer: Hierarchical vision transformer using shifted windows.  _International Conference on Computer Vision (ICCV)_ , 2021.
  * McInnes et al. (2020) Leland McInnes, John Healy, and James Melville.  Umap: Uniform manifold approximation and projection for dimension reduction.  _arXiv:1802.03426_ , 2020.
  * Paszke et al. (2019) Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang, Zachary DeVito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala.  Pytorch: An imperative style, high-performance deep learning library.  In _NeurIPS_ , 2019.
  * Susmelj et al. (2020) Igor Susmelj, Matthias Heller, Philipp Wirth, Jeremy Prescott, and Malte Ebner et al.  Lightly.  _GitHub. Note: https://github.com/lightly-ai/lightly_ , 2020.
  * Team (2019) Pytorch Lightning Development Team.  Pytorch lightning.  _GitHub. Note: https://github.com/PyTorchLightning/pytorch-lightning_ , 3, 2019.
  * Wu et al. (2019) Yuxin Wu, Alexander Kirillov, Francisco Massa, Wan-Yen Lo, and Ross Girshick.  Detectron2.  https://github.com/facebookresearch/detectron2, 2019.
  * Zbontar et al. (2021) Jure Zbontar, Li Jing, Ishan Misra, Yann Lecun, and Stephane Deny.  Barlow twins: Self-supervised learning via redundancy reduction.  In _ICML_ , 2021.
  * Zheng et al. (2021) Mingkai Zheng, Shan You, Fei Wang, Chen Qian, Changshui Zhang, Xiaogang Wang, and Chang Xu.  Ressl: Relational self-supervised learning with weak augmentation.  _arXiv:2107.09282_ , 2021.