Abstract. To a given gene tree topology $G$ and species tree topology $S$ with leaves labeled bijectively from a fixed set $X$, one can associate a set of ancestral configurations, each of which encodes a set of gene lineages that can be found at a given node of a species tree. We introduce a lattice structure on ancestral configurations, studying the directed graphs that provide graphical representations of lattices of ancestral configurations. For a matching gene tree topology and species tree topology, we present a method for defining the digraph of ancestral configurations from the tree topology by using iterated cartesian products of graphs. We show that a specific set of paths on the digraph of ancestral configurations is in bijection with the set of labeled histories — a well-known phylogenetic object that enumerates possible temporal orderings of the coalescences of a tree. For each of a series of tree families, we obtain closed-form expressions for the number of labeled histories by using this bijection to count paths on associated digraphs. Finally, we prove that our lattice construction extends to nonmatching tree pairs, and we use it to characterize pairs $(G,S)$ having the maximal number of ancestral configurations for a fixed $G$. We discuss how the construction provides new methods for performing enumerations of combinatorial aspects of gene and species trees.

Key words: ancestral configurations, gene trees, labeled histories, lattices, partial orders, species trees

Mathematics subject classification (2020): 05A15, 05A19, 05C05, 05C30, 92D15

§ INTRODUCTION

A central problem in phylogenetics is the inference of a species tree, representing evolutionary descent of species, from gene trees that describe the evolution of genealogical lineages within species. To perform this inference, procedures for estimating species trees often make use of computations of a likelihood function for species trees given information on gene trees. The  computation is performed by evaluating a probabilistic expression over each element of a set encoding purely combinatorial relations between gene tree and species tree topologies. These sets can in turn be studied mathematically to advance the theoretical understanding of species tree estimation, and of the relationships of gene trees and species trees more generally.

The computation of probabilities of gene tree topologies conditional on species trees can make use of any of a rich variety of combinatorial structures that describe pairwise relationships between tree topologies <cit.>. One type of structure that has been shown to be promising for computation is the ancestral configuration <cit.>. Consider a species tree and a gene tree that evolves along the branches of that species tree. For each node of the species tree topology, an ancestral configuration lists the lineages of the gene tree present at a point right before that node, when viewed backward in time.

An algorithm of <cit.> performs a probability calculation over sets of ancestral configurations possible for a given gene tree topology and species tree topology; mathematical properties of ancestral configurations inform the calculation. For a matching gene tree and species tree topology, <cit.> obtained enumerative results on the number of root ancestral configurations, or ancestral configurations present at the species tree root. They showed that the number of ancestral configurations present at a species tree node can be obtained recursively from corresponding values at its immediate descendant nodes. They also obtained a variety of results concerning exponential growth in the tree size of the number of ancestral configurations. Further features of this exponential growth have been obtained by <cit.>.

In this paper, we introduce a new way to view ancestral configurations that is based on introducing a lattice structure on the set of ancestral confgurations at a given node. We show that the set of root ancestral configurations for a given pair of trees possesses a rich algebraic structure that mirrors the recursive nature of binary trees. The lattice formulation enables us to prove novel enumerative results connecting ancestral configurations and another set of structures, the labeled histories.

In Section <ref>, we give the necessary biological and mathematical preliminaries. In Section <ref>, we define a lattice structure on the set of ancestral configurations for matching gene trees and species trees, and in Section <ref>, we introduce a visual representation of lattices of ancestral configurations in the form of Hasse diagrams. In Section <ref>, we prove a bijection between the set of maximal chains in the lattice of ancestral configurations for a given tree and its set of labeled histories. Section <ref> shows examples of Hasse diagrams associated with ancestral configurations for all unlabeled tree topologies with eight or fewer leaves. In Section <ref>, we prove a recurrence relation for Hasse diagrams analogous to that for sets of ancestral configurations. Applications of the recurrence to specific families of trees appear in Section <ref>. Finally, in Section <ref>, we extend the lattice structure to include nonmatching tree pairs. We conclude with a discussion in Section <ref>.

§ DEFINITIONS

We focus on leaf-labeled binary rooted trees. In this paper, a tree is assumed to mean a binary rooted tree with leaves labeled uniquely by elements of a set of labels $X = \{a, b, c, \ldots\}$.

In our definitions of ancestral configurations, we closely follow <cit.>; see <cit.> for general terminology. Consider a gene tree $G$ and species tree $S$, both of which represent labeled topologies. For a given gene tree $G$ and species tree $S$ with labels in bijective correspondence, a realization $R$ of $G$ in $S$ is one of the evolutionary possibilities of $G$ appearing on $S$. If we consider the edges of $S$ to be populations, then $R$ specifies the lineages, or edges, of $G$ that are present in each of the edges of $S$.

For a given node $v$ of $S$, we let $C(v, G, S, R)$ denote a set of lineages of $G$ present in $S$ at a point right before $v$, when viewed backward in time. We say that $C(v,G,S,R)$ is an ancestral configuration of $G$ at a node $v$ of $S$. Denote by $\mathcal R(G,S)$ the set of all realizations of $G$ in $S$. We can define a set

\[
C(v, G, S) = \{C(v, G, S, R) \mid R \in \mathcal R(G,S)\}
\]

of ancestral configurations at node $v$. The elements of $C(v, G, S)$ enumerate the ways that lineages of $G$ can reach the point right before node $v$ in $S$, viewed backward in time. Figure <ref> presents example realizations of $G$ in $S$ when trees have matching topologies.

Two example realizations of a gene tree $G$ in a species tree $S$ having matching topology. We identify each lineage of $G$ by its immediate descendant node. (A) In this realization, the ancestral configuration is $\{c,d\}$ at node $h$ of $S$; $\{e,f\}$ at node $i$ of $S$; $\{a,b\}$ at node $g$ of $S$; $\{h,e,f\}$ at node $\ell$ of $S$; $\{g,h,i\}$ at node $m$ of $S$. (B) In this realization, the ancestral configuration is $\{c,d\}$ at node $h$ of $S$; $\{e,f\}$ at node $i$ of $S$; $\{a,b\}$ at node $g$ of $S$; $\{c,d,i\}$ at node $\ell$ of $S$; $\{a,b,h,i\}$ at node $m$ of $S$.

Of particular interest are root ancestral configurations, for which $v$ is the root node of $S$. <cit.> showed that knowing the number of root ancestral configurations of a gene tree $G$ enables a calculation of an upper bound on the sum across nodes $v$ of $S$ of its numbers of ancestral configurations at $v$. We denote the set of root ancestral configurations for a pair $(G,S)$ by $C(G,S)$, and its cardinality by $c(G, S) \equiv |C(G,S)|$. We often refer to root ancestral configurations as root configurations for short, and to ancestral configurations simply as configurations.

Finally, in most of the paper,  we restrict ourselves to the case of equal topologies of a gene and species tree, $G=S$; in this case, we denote $C(S,S)$ and $c(S,S)$ by $C(S)$ and $c(S)$, respectively.

§ LATTICE OF ANCESTRAL CONFIGURATIONS

Let $S$ be a tree with $n$ leaves. We introduce the structure of a partially-ordered set, or poset, on the set of root ancestral configurations $C(S)$ for a pair consisting of an identical, or matching, gene tree topology and species tree topology.

Recall that a poset $P$ is a set together with a binary relation $\prec$ that satisfies, for all $a,b,c \in P$:

* $a \prec a$;

* If $a \prec b$ and $b \prec a$ then $a = b$;

* If $a \prec b$ and $b \prec c$ then $a \prec c$.

The relation $\prec$ is a partial order. A poset $(P,\prec)$ is termed  a lattice if each pair of elements of $P$ has both a greatest lower bound and a least upper bound with respect to $\prec$. A lattice is bounded if it has both a maximal and a minimal element <cit.>.

In the case of ancestral configurations, for $a,b \in C(S)$ we introduce a relation $\prec$. We say $a \prec b$ if by coalescing some (possibly none) lineages from the ancestral configuration $a$, we can obtain the ancestral configuration $b$, as illustrated in Figure <ref>. Verification of the three properties (i), (ii), and (iii)  is immediate, so that $(C(S),\prec)$ is a poset.

A visual representation of the partial order relation on ancestral configurations. (A) At the internal node of the species tree represented by the dashed line, the ancestral configuration is $\{a,b,c\}$. (B) At the internal node of the species tree, the ancestral configuration is $\{a,d\}$. By the partial order relation, $\{a,b,c\} \prec \{a,d\}$. Comparing (A) and (B), coalescing lineages of the ancestral configuration corresponds to moving a gene tree node, $d$ in this case, across a species tree node.

In fact, $C(S)$ has an even richer structure: it is a bounded lattice, possessing both a least element and a greatest element. A least upper bound for $a,b \in C$ is obtained by separately coalescing lineages in $a$ and lineages in $b$ until both procedures reach the same configuration, as shown in Figure <ref>. This process of repeated coalescence necessarily terminates, giving a root ancestral configuration containing two lineages—the immediate descendant lineages of the root. This configuration, which we can denote $c_{\max}$, satisfies $a \prec c_{\max}$ and $b \prec c_{\max}$, and hence is an upper bound for $a,b$. Because the sets $A = \{c \in C\mid a \prec c\}$ and $B = \{c \in C\mid b \prec c\}$ are finite, $A \cap B$ has a minimal element, which is the required least upper bound. The proof of existence of an infimum follows a similar argument, noting that the configuration $c_{\min}$ containing all leaf nodes satisfies $c_{\min} \prec c$ for all $c \in C$.

We have therefore demonstrated the following proposition.

The set $C(S)$ of root ancestral configurations for the matching pair of labeled topologies $(G,S)$ is a bounded lattice.

We illustrate the proposition with an example. Consider the labeled topology $S = ((a,b)_g,((c,d)_h,(e,f)_i)_\ell)_m$ on $6$ leaves in Figure <ref>, where the subscripts label the nodes. The set $C(S)$ of root ancestral configurations is

\[
C = \left\{\begin{array}{c}
\{g,\ell\}, \{a,b,\ell\}, \{g,c,d,e,f\}, \{g,c,d,i\}, \\
\{a,b,c,d,e,f\}, \{g,h,e,f\}, \{a,b,h,e,f\}, \\
\{a,b,c,d,i\}, \{g,h,i\}, \{a,b,h,i\}
\end{array}\right\}.
\]

In particular, $\{a,b,c,d,e,f\}$ is the minimal element and $\{g,\ell\}$ is the maximal element. By coalescing lineage pairs, we see that we have relations, $\{a,b,h,i\}\prec\{a,b,\ell\}$, $\{g,c,d,e,f\}\prec\{g,c,d,i\}$, and $\{g,c,d,e,f\}\prec\{g,h,e,f\}$, among others.

Now that we have defined a lattice algebraic structure on $C(S)$, we can use ideas of lattice theory to prove results about ancestral configurations. We next focus on representations of lattices by diagrams or graphs.

§ DIAGRAMS ASSOCIATED TO LATTICES OF ANCESTRAL CONFIGURATIONS

Recall that for a lattice $L$, one can associate a directed graph, or digraph, $D(L)$. This digraph $D(L)$ has a node for each element $x$ in $L$, and an edge from $x$ to $y$ if and only if $y$ covers $x$—that is, if and only if (i) $x \prec y$, (ii) no $z$ exists such that $x \prec z \prec y$. A visual representation of $D(L)$ with all of the directed edges oriented in the same direction (say, upward) is the Hasse diagram of $L$ <cit.>.

For convenience, we denote simply by $D(S)$ the digraph $D(C(S))$ associated with the lattice of root ancestral configurations of the species tree $S$. To illustrate this concept, we consider two examples. Figure <ref> shows the labeled topology $S = ((a,b),c),(d,e))$ and a corresponding Hasse diagram for its set $C(S)$ of root configurations. We see that $S$ has six root configurations, with maximal element $\{g,h\}$ and minimal element $\{a,b,c,d,e\}$. An edge is drawn only between pairs of ancestral configurations that differ by substituting two lineages with one coalesced lineage. We sometimes use $D(S)$ to refer to both a digraph and its visual representation as a Hasse diagram.

Figure <ref> shows the balanced labeled topology $S = (((a,b),(c,d)),((e,f),(g,h)))$ and its corresponding Hasse diagram. We see that $S$ has $25$ root configurations; like $S$, the Hasse diagram is symmetric. The subsets of $C(S)$ with 8, 7, 6, 5, 4, 3, and 2 elements have sizes

1, 4, 6, 6, 5, 2, and 1, respectively.

We note that the Hasse diagram for the set $C(S)$ of root ancestral configurations subsumes the ancestral configurations at each of the nodes of $S$. Let $e \in S$ be an internal node of $S$, and let $S|_e$ be the tree descended from it. We have a natural inclusion $C(S|_e) \hookrightarrow C(S)$ that takes an ancestral configuration $x$ in $C(S|_e)$ and associates to it an ancestral configuration $x \cup \{\text{leaves of $S$ that are not in $S|_e$}\}$. The Hasse diagram for $C(S|_e)$ can then be viewed as contained in the Hasse diagram for $C(S)$.

[b]0.45 A

[b]0.45 B

A labeled topology on 5 leaves and its corresponding Hasse diagram. (A) A labeled topology $S$ on $5$ leaves. (B) The corresponding Hasse diagram for $D(S)$.

[b]0.45 A

[b]0.45 B

A balanced labeled topology on 8 leaves and its associated Hasse diagram. (A) A balanced labeled topology $S$ on $8$ leaves. (B) The corresponding Hasse diagram for $D(S)$.

§ MAXIMAL CHAINS AND LABELED HISTORIES

The bounded lattice structure for the set $C(S)$ immediately suggests an enumerative question: what are the maximal chains in $C(S)$? For elements $x$, $y$, $z$ of a partial order with $x \neq y$, we say that $y$ covers $x$ if $x \prec z \prec y$ implies $z = x \text{ or } z = y$. The maximal chains in the lattice $C(S)$ are the sequences $x_1, x_2, \ldots, x_k$ of elements of $C(S)$, such that $x_1$ is the minimal element, $x_k$ is the maximal element, and for each $i$ from 1 to $k-1$, $x_{i+1}$ covers $x_i$.

Each successive entry in the sequence $x_1, x_2, \ldots, x_k$ represents a coalescence of two nodes in the previous entry. For a labeled topology with $n$ leaves, $n-1$ coalescences take place. The minimal element of a maximal chain in the lattice $C(S)$ has $n$ nodes, and the maximal element has 2 nodes, so that the maximal chains of $C(S)$ all have length $n-1$.

Geometrically, we can reinterpret this question in terms of diagrams, noting that the maximal chains of a lattice correspond to the paths from the minimal to the maximal element of its associated Hasse diagram. We trivially obtain the following proposition.

The enumeration of maximal chains in the lattice $C(S)$ is equivalent to the enumeration of paths in the digraph $D(S)$ that start at the minimal element and end at the maximal element.

Consider the labeled topology $S$ from Figure <ref>A. We see that $C(S)$ has exactly three maximal chains: $\{a,b,c,d,e\} \prec \{f,c,d,e\} \prec \{g,d,e\} \prec \{g,h\}$,  $\{a,b,c,d,e\} \prec \{f,c,d,e\} \prec \{f,c,h\} \prec \{g,h\}$,  $\{a,b,c,d,e\} \prec \{a,b,c,h\} \prec \{f,c,h\} \prec \{g,h\}$. These maximal chains are in bijective correspondence with the three paths from the bottom to the top in the diagram in Figure <ref>B.

One consequence of this construction is a connection of maximal chains of $C(S)$ with labeled histories for $S$. Recall that a labeled history for a tree $S$ is a sequence of its coalescences. We have the following theorem.

For a labeled topology $S$, the following three sets are in bijective correspondence: (i) the maximal chains of the lattice $C(S)$, (ii) the paths from the minimal element to the maximal element of the Hasse diagram of $D(S)$, and (iii) the labeled histories of $S$.

This statement is almost trivial, as it is simply a reformulation of the definition of labeled histories. First, the equivalence of (i) and (ii) is a restatement of Proposition <ref>. For equivalence of (ii) and (iii), note that each labeled history is a sequence of coalescences, so to each labeled history we can associate a sequence of edges of the diagram of $D(S)$: as described in Section <ref>, an edge from $x$ to $y$ corresponds to the covering of $x$ by $y$, which, according to our definition of the poset relation in $C(S)$, involves precisely one coalescence of lineages of $S$. These edges of $D(S)$ form a path from the minimal element to the maximal element of $C(S)$. (If the edges do not align to form a path, then the labeled history includes coalescences of lineages that are not produced by previous coalescences — a contradiction.) Conversely, given a path in $D(S)$ from the minimal to the maximal element, we can read off a labeled history from the sequence of edges in the path, as each edge is associated to some coalescence of lineages of $S$.

Henceforth, we let $H(S)$ denote the set of labeled histories of $S$, and we let $h(S)\equiv|H(S)|$ denote the cardinality of this set. Because the paths on a digraph $D(S)$ correspond to the labeled histories of $S$ by Theorem <ref>, we use $h(S)$ interchangeably with $h(D(S))$ to count paths of $D(S)$. We use the same conventions for $H(S)$ and $H(D(S))$.

The number $h(S)$ of labeled histories for a given labeled topology $S$ on $n$ lineages is equal to

\begin{equation}
\label{eq:steel_exp}
h(S) = \frac{(n-1)!}{\prod_{r = 3}^n (r-1)^{d_r(S)}},
\end{equation}

where $d_r(S)$ is the number of internal nodes of $S$ from which exactly $r$ taxa descend <cit.>. With the help of Theorem <ref>, this formula can be given a visual interpretation as the number of paths from the minimal element to the maximal element of the Hasse diagram of $D(S)$.

For example, suppose $S = \mathcal{C}_n$ is a caterpillar tree on $n$ leaves. Then $\mathcal C_n$ possesses a unique linear ordering of its internal nodes. The Hasse diagram for a caterpillar tree is a linear graph with $n-1$ nodes and $n-2$ edges connecting adjacent nodes. Hence, $h(\mathcal C_n) = 1$. In eq. <ref>, we also see that $h(\mathcal C_n)=1$, as the factorial in the numerator is canceled in the denominator.

More generally, for any seed tree $S$ we can form a caterpillar-like family $S_k$ by successively adjoining $k \geq 1$ caterpillar branches to the root of $S$, where a caterpillar branch is an edge that connects to a single leaf. The caterpillar branches introduce a linear ordering of the additional internal nodes ancestral to the root of the seed tree $S$, so that $h(S_k)$ does not depend on $k$ and always equals $h(S)$. Geometrically, adding caterpillar branches to $S$ corresponds to adding one edge and one vertex to the top of the Hasse diagram for $S$, an operation that does not change the number of paths from the minimal element to the maximal element.

§ EXAMPLES

To begin to understand the structure of lattices of ancestral configurations for labeled topologies, we provide Hasse diagrams (or digraphs $D(S)$) for all trees $S$ of size $n \leq 8$ (Tables <ref> and <ref>). For each of these small trees, to construct the associated digraph, we enumerate all ancestral configurations and characterize their relationship according to $\prec$. For each tree, we list the number of ancestral configurations $c(S)$, representing the number of vertices in the digraph, and the number of labeled histories $h(S)$ (eq. <ref>), representing the number of paths from the minimal to the maximal element.

Informally, we can observe a number of features of the digraphs. For example, the digraphs of ancestral configurations for caterpillar trees are simply lines. For trees that possess an internal node $v$ all of whose ancestral nodes each have a leaf as an immediate descendant, the digraph has a subgraph associated with $v$ and a line for the ancestors of $v$. For trees whose two immediate subtrees of the root are a caterpillar tree and a cherry, the digraph can be described as having two lines from the minimal to maximal element, with paths connecting these two lines. Trees for which the two immediate subtrees of the root are both caterpillars have a planar grid for their digraphs, and all monotonic paths on the grid from the minimal to the maximal element are permissible paths.

We explore some of these features further in subsequent sections.

$n$     Tree $S$    $D(S)$     $c(S)$     $h(S)$

3               2     1

4                3     1

4     2

5                4     1

5     2

6     3

6                5     1

6     2

7     3

8     4

10     8

9     6

$n$     Tree $S$    $D(S)$     $c(S)$     $h(S)$

7                6     1

7     2

8     3

9     4

11     8

10     6

10     5

12     10

14     15

12     10

15     20

Hasse diagrams $D(S)$ of the lattice of root ancestral configuations of $S$, for all trees $S$ of size $3 \leq n \leq 7$. A representative labeling for each unlabeled topology can be assumed, with the labels omitted for convenience. $c(S)$ is the number of root ancestral configurations of $S$, equal to the number of vertices in the Hasse diagram $D(S)$. $h(S)$ is the number of labeled histories of $S$, equal to the number of paths from the minimal element to the maximal element of $D(S)$.

$n$     Tree $S$    $D(S)$     $c(S)$     $h(S)$

8                7     1

8     2

9     3

10     4

12      8

11     6

11     5

13     10

15     15

13     10

16     20
12     6

$n$     Tree $S$    $D(S)$     $c(S)$     $h(S)$

14     12

16     18

18     24

22     48

20     36

15     15

18     30

21     45

16     20

20     40

25     80

Hasse diagrams $D(S)$ of the lattice of root ancestral configuations of $S$, for all trees $S$ of size $n=8$. As in Table <ref>, a representative labeling for each unlabeled topology can be assumed, with the labels omitted for convenience. $c(S)$ is the number of root ancestral configurations of $S$, equal to the number of vertices in the Hasse diagram $D(S)$. $h(S)$ is the number of labeled histories of $S$, equal to the number of paths from the minimal element to the maximal element of $D(S)$.

§ A STRUCTURE THEOREM

Based on the examples in Section <ref>, we see that the Hasse diagrams $D(S)$ possess a recursive structure that mimics a recurrence for $C(S)$. Recall that a recurrence exists for root ancestral configurations of a given tree $S$ <cit.>. First, for some sets of sets $A$ and $B$, define a binary (associative, commutative) operation $\otimes$ by

\[ A \otimes B = \{ a \cup b \mid a \in A, b\in B\}.\]

For a tree $S$ whose two nodes immediately descended from the root are labeled $r_\ell$ and $r_r$, the root ancestral configurations of $S$ can be written

\begin{equation}
\label{eq:recur_enum}
C(S) = \{
\left[C(S|_{r_\ell}) \otimes C(S|_{r_r})\right] \cup
\left[\{\{r_\ell\}\} \otimes C(S|_{r_r})\right] \cup
\left[C(S|_{r_\ell}) \otimes \{\{r_r\}\}\right] \cup
\{r_\ell,r_r\}\},
\end{equation}

where $S|_{r_\ell}$ and $S|_{r_r}$ represent the subtrees of $S$ rooted at $r_{\ell}$ and $r_r$, respectively. The cardinalities satisfy

\begin{equation}
\label{eq:recur_count}
c(S) = \left[c(S|_{r_\ell})+1\right] \left[c(S|_{r_r})+1\right].
\end{equation}

We prove an analogous recurrence for the construction of the lattices $D(S)$. First, a definition of the cartesian product of graphs <cit.> is required.

Given two directed graphs $G$ and $H$, their cartesian product is a graph $\cp G H$ such that

* The vertex set $V(\cp G H)$ is a cartesian product $V(G) \times V(H)$, and

* There is an edge from a vertex $(u,v)$ in $\cp G H$ to a vertex $(u',v')$ if either (i) $u=u'$ and there is an edge from $v$ to $v'$ in $H$ or (ii) $v=v'$ and there is an edge from $u$ to $u'$ in $G$.

We also need some language for describing digraphs in the context  of ancestral configurations. Let $\mathcal{D}$ be the set of all directed graphs that arise as $D(S)$ for some labeled topology $S$.

We say that a digraph $D \in \mathcal D$ has a caterpillar-like maximal node if the maximal node of $D$ has only one incoming edge.

We introduce notation for appending and removing caterpillar-like maximal nodes. For a digraph $D\in \mathcal D$, let $\widehat D$ be a digraph obtained by adding a new node $m'$ and an edge from the maximal node $m$ of $D$ to $m'$. Naturally, $m'$ is now a caterpillar-like maximal node of $\widehat D$. If $D$ is an empty graph, then we let $\widehat{D}$ be the graph with a unique node $m'$ and no edges.

Similarly, for a digraph $D \in \mathcal D$ that already possesses a caterpillar-like maximal node, let $\widecheck{D}$ be a digraph obtained from $D$ by removing the caterpillar-like maximal node and the unique edge directed to it.

For trees $S$, we interpret $\widehat{D(S)}$ as $D(S_1)$, where $S_1$ is the first tree in the caterpillar-like family with a seed tree $S$, as defined in Section <ref>. With these definitions, the main result of the section can now be stated.

Consider a tree $S$ with $n\geq 2$ leaves. Let $r_\ell$ and $r_r$ be the two immediate descendants of its root, and let $S|_{r_\ell}$ and $S|_{r_r}$ be the subtrees of $S$ induced by $r_\ell$ and $r_r$.  Then

\[
D(S) = \cp{\widehat{D(S|_{r_\ell})}}{\widehat{D(S|_{r_r})}}.
\]

Taking cardinalities of the vertex sets of the diagrams, we obtain eq. <ref>, as $|\widehat{D(S)}| = |D(S)| + 1 = c(S) + 1$ for all $S$, so that $c(S) = |D(S)|= |\widehat{D(S|_{r_\ell})}| |\widehat{D(S|_{r_r})}| = \left[c(S|_{r_\ell})+1\right] \left[c(S|_{r_r})+1\right]$.

Eq. <ref> gives a bijection between the vertex sets $V(D(S))$ and $V\left(\cp{\widehat{D(S|_{r_\ell})}}{\widehat{D(S|_{r_r})}}\right)$ by interpreting caterpillar-like maximal nodes added by the “hat”-operation as $r_r$ and $r_\ell$ in eq. <ref>.  This bijection allows us to formally identify the vertices of the two digraphs.

To conclude that $D(S) = \cp{\widehat{D(S|_{r_\ell})}}{\widehat{D(S|_{r_r})}}$, we must show that the sets of edges of digraphs are equal. We first show containment of edge sets, and then prove by contradiction that containment cannot be strict.

We claim that edge sets satisfy $E\left(\cp{\widehat{D(S|_{r_\ell})}}{\widehat{D(S|_{r_r})}}\right) \subseteq E(D(S))$ under the identification of vertices via eq. <ref>. The digraph $\cp{\widehat{D(S|_{r_\ell})}}{\widehat{D(S|_{r_r})}}$ has an edge between $(u,v)$ and $(u',v')$ if either (1) $u=u'$ and $\widehat{D(S|_{r_r})}$ has an edge from $v$ to $v'$ or (2) if $v = v'$ and $\widehat{D(S|_{r_\ell})}$ has an edge from $u$ to $u'$. This means that each edge of $\cp{\widehat{D(S|_{r_\ell})}}{\widehat{D(S|_{r_r})}}$, viewed as an edge between vertices of $D(S)$, corresponds to precisely one coalescence, happening either in the right subtree $S_r$ (case 1), or in the left subtree $S_\ell$ (case 2), including the root coalescences of the two subtrees. Such an edge is in $E(D(S))$ by definition of $D(S)$.

Finally, if there is an edge $e \in E(D(S)) - E\left(\cp{\widehat{D(S|_{r_\ell})}}{\widehat{D(S|_{r_r})}}\right)$, then it corresponds to a coalescence that happens in neither of the root subtrees $S_\ell$, $S_r$. There is only one such coalescence, namely the root of $S$. However, by definition of $D(S)$, root coalescences are not reflected in the digraph, so we have a contradiction. We conclude that $D(S) = \cp{\widehat{D(S|_{r_\ell})}}{\widehat{D(S|_{r_r})}}$.

To simplify notation, we define a binary operation on digraphs $D_1$ and $D_2$, $\widehat\square$, by
\[\cphat{D_1}{D_2} = \cp{\widehat{D_1}}{\widehat{D_2}}.\]

This operation combines the operations of adding ancestral nodes and taking cartesian products. Hence, Theorem <ref> allows us to encode a graph as a $\widehat\square$-product of simpler graphs.

First, recall that for a tree consisting of only one leaf, we define the set of ancestral configurations, $C(S)$, to be empty. Correspondingly, $D(S)$ is an empty graph. For a tree with two leaves, $S = (a,b)$, the set of ancestral configurations $C(S)$ has only one element, and $D(S)$ is a graph with one node and no edges.

If we recursively decompose a tree $S$ into left and right subtrees $S|_{r_\ell}$ and $S|_{r_r}$, then we eventually arrive either at a tree with one leaf, or a tree with two leaves (a cherry node). Of course, a tree with two leaves decomposes into two one-leaf trees, but it is convenient not to need to make this decomposition.

Repeated application of Theorem <ref> gives us the following result.

Let $\emptyset$ denote an empty graph, and let $I$ denote the graph with a single node and no edges. Then any digraph $D \in \mathcal D$ can be obtained by repeated application of the $\widehat\square$ operator to $\emptyset$ and $I$.

The decomposition can be “read” directly from a tree by writing $I$ for each cherry node and $\emptyset$ for each single edge, including $\widehat\square$ products accordingly. For example, for a caterpillar tree $\mathcal C_n$ with $n\geq 2$, we write

\begin{equation}\label{eq:decomp_cat}
D(\mathcal C_n) = (((I \house \emptyset) \ldots) \house \emptyset) \house \emptyset,
\end{equation}

with the $\widehat \square$-product applied $n-2$ times. As $\widehat{\emptyset} = I$, $D(\mathcal C_n)$ is equal to $I$ with $n-2$ caterpillar-like nodes added, giving us a linear path graph, as seen in Section <ref>.

In the next section, we present a series of examples of the application of Theorem <ref> and Proposition <ref>.

§ SPECIFIC FAMILIES

With the connection between sets of ancestral configurations and lattices established, we now examine the diagrams produced by special families of trees. As noted in Section <ref>, the diagrams for the caterpillar trees are trivial path graphs, with a unique maximal chain. Here, we consider $p$-pseudocaterpillar trees, bicaterpillar trees, two types of lodgepole trees, and balanced trees. In the figures of this section, we omit leaf and node labels on trees and diagrams for visual clarity.

§.§ Pseudocaterpillar trees

First, we consider $p$-pseudocaterpillar trees, as defined by <cit.>. For $p \geq 4$, a $p$-pseudocaterpillar tree has two cherries; it is encoded by integers $(n,p)$, where $n$ is the number of taxa, and $p$ is an index that denotes the location of one of the cherries. More precisely, we label the leaves from left to right by labels 1 to $n$; one cherry contains leaves 1 and 2, and the other contains leaves $p-1$ and $p$. For $p=3$, a $p$-pseudocaterpillar tree has only one cherry, consisting of leaves labeled 2 and 3. The $p$-pseudocaterpillar trees encoded by $(n,n)$ are $(a,(b,c))$ for $n=3$, $((a,b),(c,d))$ for $n=4$, and $(((a,b),c),(d,e))$ for $n=5$. We denote the $p$-pseudocaterpillar tree encoded by $(n,n)$ with the symbol $\mathcal P_n$ (Figure <ref>).

Hasse diagrams for the sets of root configurations for the pseudocaterpillar family $\mathcal P_n$ appear in Figure <ref>. Recall that the number of nodes in a Hasse diagram is the number of root configurations; the number of paths in a Hasse diagram is the number of labeled histories.

The diagrams have a structure in which a path from bottom to top on the left side of the diagram represents coalescence of the caterpillar branches prior to coalescence of the cherry containing leaves $n-1$ and $n$, and a path from bottom to top on the right side of the diagram represents coalescence of the caterpillar branches after coalescence of the cherry. The edges connecting the path on the left and the path on the right represent coalescence of the cherry. Using Theorem <ref>, this pattern can be summarized by

\begin{equation}\label{eq:decomp_pcat}
D(\mathcal P_n) = \cphat{D(\mathcal C_{n-2})}{I}.
\end{equation}

The number of root ancestral configurations $c(\mathcal{P}_n)$, or the number of nodes in the Hasse diagram of $\mathcal{P}_n$, is computed by eq. <ref>, and we obtain $c(\mathcal{P}_n) = 2(n-2)$.
Similarly, the number of labeled histories $h(\mathcal{P}_n)$, or the number of paths in the Hasse diagram of $\mathcal{P}_n$, is calculated by eq. <ref>, equaling $n-2$. The values of $c(\mathcal{P}_n)$ and $h(\mathcal{P}_n)$ are given in Table <ref>.

3     4     5     6     7     8

$c(\mathcal P_n)$     2     4     6     8     10     12

$h(\mathcal P_n)$     1     2     3     4     5      6

The number of root ancestral configurations $c(\mathcal P_n)$ and the number of paths $h(\mathcal P_n)$ for $p$-pseudocaterpillar trees $\mathcal P_n$.

$p$-pseudocaterpillar trees $\mathcal P_n$ for $n=3,4,5,6,7,8$.

Hasse diagrams corresponding to $p$-pseudocaterpillar trees $\mathcal P_n$ for $n = 3, 4, 5, 6, 7, 8$.

§.§ Bicaterpillars

For our next family, we consider symmetric bicaterpillar trees, defined as trees whose two root subtrees—trees induced by immediate descendants of the root—are caterpillar trees $\mathcal C_n$. We denote by $\mathcal{C}_{n,n}$ the symmetric bicaterpillar tree with two caterpillar subtrees $\mathcal{C}_n$ immediately descended from the root. In particular, $\mathcal C_{1,1} = (a,b)$, $\mathcal C_{2,2} = ((a,b),(c,d))$, $\mathcal C_{3,3} = (((a,b),c),(d,(e,f)))$, and so on, as shown in Figure <ref>.

1     2     3     4     5     6

$c(\mathcal C_{n,n})$     1     4     9     16     25     36

$h(\mathcal C_{n,n})$     1     2     6     20     70     252

The number of root ancestral configurations $c(\mathcal C_{n,n})$ and the number of paths $h(\mathcal C_{n,n})$ for bicaterpillar trees $\mathcal C_{n,n}$.

The Hasse diagrams for the sets of root configurations are presented in Figure <ref>. In the Hasse diagrams, edges moving up from left to right represent coalescences on say, the left side of the tree, and edges moving up from right to left represent coalescences on the right side of the tree.

The symmetry of the symmetric bicaterpillars generates a symmetry in the edges of the Hasse diagram, so that the Hasse diagram can be viewed as a square grid. This equivalence to paths from one corner of a square grid to an opposite corner is convenient for counting the paths. In particular, the number of nodes in the Hasse diagram, obtained by eq. <ref>, is $c(\mathcal{C}_{n,n}) = n^2$. The number of paths, obtained by eq. <ref>, is $h(\mathcal{C}_{n,n})={2n-2 \choose n-1}$. The values of $c(\mathcal{C}_{n,n})$ and $h(\mathcal{C}_{n,n})$ appear in Table <ref>.

Note that this example naturally extends to the case of general bicaterpillar trees $\mathcal C_{p,q}$, in which the two immediate subtrees of the root are caterpillars of size $p$ and $q$ leaves. The diagram is a rectangle with $pq$ nodes, and the number of paths on it is $\binom{p+q-2}{q-1}$.

Theorem <ref> gives a quick proof of this result. By definition of $\mathcal C_{p,q}$, we have

\begin{equation}\label{eq:decomp_bicat}
D(\mathcal C_{p,q}) = \cphat{\mathcal C_p}{\mathcal C_q},
\end{equation}

so that $D(\mathcal C_{p,q})$ is a cartesian product of two path graphs with $p$ and $q$ vertices, respectively, or a “$p \times q$ grid.”

The bicaterpillar example can be extended still further, to trees for which one of the two immediate subtrees of the root is a caterpillar.

Consider a tree whose two subtrees immediately descended from the root are $S$ and
$\mathcal{C}_p$, with $|S| \geq 1$ and $\mathcal{C}_p$ a caterpillar with $p$ leaves. Then $h(\cphat{D(S)}{D(\mathcal C_p)}) = \binom{n+p-1}{p-1} \,h(D(S))$, where $n=|S|-1$, the number of coalescences of $S$.

Given a path in $h(D(S))$ (of length $n-1$), we can construct $\binom{n+p-1}{p-1}$ distinct paths in $h(\cphat{D(S)}{D(\mathcal C_p)})$, each with length $n+p-1$, by choosing the location of $p-1$ (linearly ordered) edges of $D(\mathcal C_p)$ among the $n+p-1$ total edges. Of course, paths constructed from distinct elements of $h(D(S))$ are distinct as well, which allows us to conclude that $h(\cphat{D(S)}{D(\mathcal C_p)}) = \binom{n+p-1}{p-1} \,h(D(S))$.

Bicaterpillar trees $\mathcal C_{n,n}$ for $n=1,2,3,4,5,6$.

Hasse diagrams corresponding to symmetric bicaterpillar trees $\mathcal C_{n,n}$ for $n = 1, 2, 3, 4, 5, 6$. The diagram for $\mathcal C_{1,1}$ consists of a single node and no edges.

§.§ Lodgepole trees

We now consider two families of “lodgepole” trees. First, let $\mathcal L_n$ be the family of lodgepole trees defined as in <cit.>. In particular, $\mathcal L_1 = (a,(b,c))$, $\mathcal L_2 = ((a,(b,c)),(e,f))$, $\mathcal L_3 = (((a,(b,c)),(e,f)),(g,h))$, and so on, as shown in Figure <ref>.

Hasse diagrams for the sets of root configurations for the lodgepole trees appear in Figure <ref>. Using eq. <ref>, we notice that the number of nodes in the Hasse diagrams, or the number of root ancestral configurations, is $c(\mathcal{L}_n)=2^{n+1} - 2$. The number of paths, or number of labeled histories, is the double factorial $h(\mathcal{L}_{n})=(2n-1)!!$, as obtained by eq. <ref>. The number of root ancestral configurations $c(\mathcal{L}_n)$ and the number of labeled histories $h(\mathcal{L}_{n})$ appear in  Table <ref>.

1     2     3     4     5

$c(\mathcal L_{n})$     2     6     14     30      62

$h(\mathcal L_{n})$     1     3     15     105     945

The number of root ancestral configurations $c(\mathcal L_n)$ and the number of paths $h(\mathcal L_n)$ for lodgepole trees $\mathcal L_n$.

Using Theorem <ref>, we can define the class of diagrams coming from lodgepole trees as

\begin{equation}\label{eq:decomp_lodg1}
D(\mathcal L_n) = ((\emptyset \house I)\house \ldots)\house I,
\end{equation}

where the $\widehat \square$-product is applied $n$ times. Because the right root subtree of $\mathcal L_n$ is a caterpillar $\mathcal C_2$, Proposition <ref> can be applied to show that

\[
h(\mathcal L_n) = (2n-1) \, h(\mathcal L_{n-1}).
\]

An inductive argument then gives a proof of the fact that $h(\mathcal{L}_{n})=(2n-1)!!$ purely in the language of lattice diagrams, without referencing eq. <ref>.

Lodgepole trees $\mathcal L_n$ for $n=1,2,3,4,5$.

Hasse diagrams corresponding to lodgepole trees $\mathcal L_n$ for $n = 1,2,3,4,5$.

§.§ A modified lodgepole family

For our second family of lodgepole-like trees, let $\mathcal M_n$ be a family akin to lodgepoles, but with a cherry instead of the leftmost leaf. In particular, $\mathcal M_1 = ((a,b),(c,d))$, $\mathcal M_2 = (((a,b),(c,d)),(e,f))$, $\mathcal M_3 = ((((a,b),(c,d)),(e,f)),(g,h))$, and so on, as in Figure <ref>.

Hasse diagrams for the sets of root configurations for the modified lodgepole family appear in Figure <ref>. The number of nodes in the diagrams, or the number of root ancestral configurations, as calculated by eq. <ref>, is $h(\mathcal M_n) = 3\times 2^{n} - 2$. The number of paths, or number of labeled histories, is $h(\mathcal M_n) = (2n)!!$ by eq. <ref>, again a double factorial, but now including only even numbers. We provide the number of root ancestral configurations $c(\mathcal{M}_n)$ and the number of labeled histories $h(\mathcal{M}_{n})$ in Table <ref>.

1     2     3     4     5

$c(\mathcal M_{n})$     4     10     22     46      94

$h(\mathcal M_{n})$     2     8      48     384     3840

The number of root ancestral configurations $c(\mathcal M_n)$ and the number of paths $h(\mathcal M_n)$ for modified lodgepole trees $\mathcal M_n$.

Similarly to Section <ref>, Theorem <ref> gives us the following general description of the diagrams for the modified lodgepole family:

\begin{equation}\label{eq:decomp_lodg2}
D(\mathcal M_n) = ((I \house I)\house \ldots)\house I,
\end{equation}

where the $\widehat \square$-product is applied $n$ times. Analogously, Proposition <ref> can be applied to show that

\[
h(\mathcal M_n) = (2n) \, h(\mathcal M_{n-1}),
\]

so that the fact that $h(\mathcal M_{n})=(2n)!!$ is established without reference to eq. <ref>.

Modified lodgepole trees $\mathcal M_n$ for $n=1,2,3,4,5$.

Hasse diagrams corresponding to modified lodgepole trees $\mathcal M_n$ for $n = 1,2,3,4,5$.

§.§ Balanced trees

We define the family of fully balanced trees $\mathcal B_n$ by $\mathcal B_1 = (a,b)$, $\mathcal B_2 = ((a,b),(c,d))$, $\mathcal B_3 = (((a,b),(c,d)),((e,f),(g,h)))$, and so on, where the tree $\mathcal B_n$ has $2^n$ leaves (Figure <ref>).

The Hasse diagrams for the sets of root ancestral configurations for $\mathcal B_1$, $\mathcal B_2$, $\mathcal B_3$, and $\mathcal B_4$ appear in Figure <ref>. The number of root ancestral configurations for $\mathcal B_n$ is obtained from eq. <ref>, and it is described by a quadratic recurrence $c(\mathcal B_n) = [1 + c(\mathcal B_{n-1})]^2$ with $c(\mathcal B_1)=1$ (A004019 in OEIS). It is also the number of nodes in the diagrams in Figure <ref>.

1     2     3     4

$c(\mathcal B_n)$     1     4     25     676

$h(\mathcal B_n)$     1     2     80     21964800

The number of root ancestral configurations $c(\mathcal{B}_n)$ and the number of paths $h(\mathcal{B}_n)$ for balanced trees $\mathcal{B}_n$.

The number of labeled histories for  $\mathcal B_n$ is obtained from eq. <ref>:

\begin{equation}
h(\mathcal{B}_n) = \frac{(2^n-2)!}{\prod_{k=1}^{n-2} (2^{n-k}-1)^{2^k}}.
\end{equation}

It is the number of paths on the diagrams in Figure <ref> (A056972 in OEIS).
We provide the number of root ancestral configurations $c(\mathcal{B}_n)$ and the number of labeled histories $h(\mathcal{B}_n)$ in Table <ref>.

Theorem <ref> gives us a recurrent description of the diagrams $D(\mathcal B_n)$:

\[
D(\mathcal B_1) = I,
\]

\begin{equation} \label{eq:decomp_balances}
D(\mathcal B_n) = \cphat{D(\mathcal B_n)}{D(\mathcal B_n)}.
\end{equation}

Note that the example of balanced trees shows that the $\widehat \square$-operator is not associative, as

\[
(I\house I)\house(I\house I) = D(\mathcal B_3) \neq  D(\mathcal M_3) = ((I\house I)\house I)\house I.
\]

Balanced trees $\mathcal B_n$ for $n=1,2,3,4$.

Hasse diagrams corresponding to balanced trees $\mathcal B_n$ for $n=1,2,3,4$. The diagram for $\mathcal B_1$ consists of a single node and no edges.

§ NONMATCHING TREE PAIRS

We have been considering gene trees and species trees that have the same topology. However, a benefit of the lattice construction for ancestral configurations is that the approach can be extended to cases in which the topologies of the gene tree and species tree do not necessarily match.

In biological settings involving tree pairs, the species tree $S$ is generally treated as fixed and the gene tree $G$ as varying, as a gene tree can be viewed as a random quantity conditional on a species tree <cit.>. The species tree is determined by a history of population subdivisions, and gene trees evolve conditionally on that history.

However, when considering lattices of ancestral configurations, the mathematically natural point of view is to instead treat $G$ as fixed and to consider its realizations on many different species trees. We will show that in this setting, no “anomalies” happen; that is, for a fixed gene tree, the maximal number of ancestral configurations across all species tree topologies is attained by the matching pair.

For a pair of trees $(G,S)$ with leaf labels bijectively assigned from the same label set, define $C(G,S)$ to be the lattice of root ancestral configurations that appear in realizations of a gene tree $G$ on a species tree $S$. Similarly, we use corresponding notation for other sets and counts we have associated to lattices—reverting to $c(G,S)$, $H(G,S)$, and $h(G,S)$ in place of $c(G)$, $H(G)$, and $h(G)$, and so on.

We will need the concept of antipodal leaves, following <cit.>.

Consider a pair of trees $(G,S)$ with leaves bijectively labeled by the same label set $X = \{x_1,x_2,\ldots, x_n\}$. $S_\ell$ denotes the “left” subtree of the root of $S$, and $S_r$ denotes the “right” subtree of the root of $S$. We call two leaves $x_i$, $x_j$ of $G$ antipodal if the corresponding leaves in $S$ belong to different subtrees of the root of $S$, with $x_i \in S_\ell$ and $x_j \in S_r$ or vice versa. Similarly, we call two edges $e_1,e_2$ of $G$ antipodal if at least one pair of leaves $(v_1, v_2)$, with $v_1$ descended from $e_1$ and $v_2$ descended fom $e_2$, has its two constituent leaves in opposite subtrees of the root of $S$.

Now we characterize $C(G,S)$; an example appears in Figure <ref>. First, a trivial proposition states that no “new” ancestral configurations arise if we consider a non-matching rather than a matching species tree.

Consider a pair of trees $(G,S)$ with leaves bijectively labeled by the same label set $X = \{x_1,x_2,\ldots, x_n\}$. As a set, $C(G,S) \subseteq C(G,G)$.

Let $c \in C(G,S)$ be an ancestral configuration, $c = \{\ell_1,\ell_2,\ldots, \ell_k\}$; $c$ is a set of lineages of $G$ that, looking backward in time, can appear right before the root in a realization of gene tree $G$ on species tree $S$. We prove $c \in C(G,G)$ by examining a specifically constructed realization, $R$, of gene tree $G$ on species tree $G$.

In the realization $R$ of gene tree $G$ on species tree $S=G$, for each $\ell_i$ in configuration $c$ that consists of a single leaf of $G$, the leaf simply does not engage in any coalescences in $R$. Next, consider each $\ell_i$ in configuration $c$ that consists of an internal node of $G$. In $R$, for each such $\ell_i$, each coalescence required for producing the lineage $\ell_i$ happens immediately ancestral to the corresponding node $\ell_i$ of a species tree $G$, i.e. immediately ancestral to the most-recent-common-ancestor node of the descendant leaves of $\ell_i$. It is always possible to arrange this, because, with $G$ as a species tree, each lineage of gene tree $G$ with the exception of the root lineage (which does not appear in ancestral configurations) does not contain antipodal pairs among its descendant leaves.

The constructed realization $R$ displays ancestral configuration $c \in C(G,G)$ at the root.

On the level of lattice diagrams, $D(G,S)$ has the following description:

Let $(G,S)$ be a tree pair. Let $\mathbf c \in C(G,G)$ be the unique ancestral configuration in which all non-antipodal pairs of leaves in $G$, and only those pairs, have coalesced. Then $D(G,S)$ is a subgraph of $D(G,G)$, defined as the subset of edges and vertices that appear in at least one path from a minimal element, the ancestral configuration consisting of all leaf lineages, to $\mathbf c$.

It is clear that $\mathbf c$ is unique: by specifying what coalescences of lineages led to $\mathbf c$ being displayed at the root, we specify what lineages are present in $\mathbf c$.

First, applying Proposition <ref>, we claim that $C(G,S)$ forms a sublattice of $C(G,G)$ or, equivalently, $D(G,S)$ is a subgraph of $D(G,G)$. We can see this by noting that an edge $e$ of $D(G,S)$ corresponds to a coalescence of certain lineages of $G$, so it can be found in $D(G,G)$.

We finish the proof by showing that $D(G,S)$ is precisely the subgraph $D_{\mathbf{c}}$, where $D_{\mathbf c}$ is defined as the subset of edges and vertices that appear in at least one path from a minimal element, the ancestral configuration consisting of all leaf lineages, to $\mathbf c$. We show $D(G,S) \subseteq D_{\mathbf c}$ and $D_{\mathbf c} \subseteq D(G,S)$.

Each ancestral configuration in $C(G,S)$ contains only lineages that can appear below (that is, “descended from”) the root of $S$. Hence, each configuration $d$ in $C(G,S)$ precedes $\mathbf c$ with respect to the poset relation, because if $d \not\prec \mathbf c$, then $d$ contains a lineage belonging to an antipodal pair, and such a lineage cannot appear below the species tree root in a realization of $G$ on $S$. Thus, $D(G,S) \subseteq D_{\mathbf c}$.

For the reverse direction, each configuration $d$ with $d \prec \mathbf c$ must contain only lineages produced by coalescences of non-antipodal lineages of $G$. We claim that it therefore is a valid root configuration for $G$ realized in $S$. The proof of this claim is similar to the proof of Proposition <ref>: define a realization $R$ of $G$ on $S$ by letting each $\ell_i \in d = \{\ell_1, \ell_2, \ldots, \ell_k\}$ happen immediately above (that is, “ancestral to”) the most recent node of $S$ ancestral to all descendants of $\ell_i$ in $G$. The fact that all lineages are produced by non-antipodal coalescences implies that each $\ell_i$ is placed below the root of $S$ in realization $R$. Hence, $D_{\mathbf c} \subseteq D(G,S)$, completing the proof.

An example lattice of ancestral configurations in the case of nonmatching $G$ and $S$. (A) The gene tree $G = \mathcal C_{4,4}$. (B) A species tree $S$, different from $G$, but having the same leaf labels. (C) Diagrams of ancestral configurations. The digraph $D(G,G)$ is shown in black, as in Figure <ref>, and $D(G,S)$ is a subgraph shown in red. We observe that the coalescence $(\ell_7, \ell_8)$ is possible below the root of $S$, while $\ell_6$ and $\ell_7$ form an antipodal pair, forcing $(\ell_6,(\ell_7,\ell_8))$ to happen above the root and the corresponding edges of $D(G)$ to not be included in $D(G,S)$.

We now characterize pairs of trees having the maximal number of root ancestral configurations for fixed $G$. Because $c(G,S) \leq c(G,G)$ for all choices of $S$, the trees $S$ for which $c(G,S) = c(G,G)$ are the pairs that have the maximum possible number of root ancestral configurations.

The species trees $S$ in pairs $(G,S)$ that for a fixed $G$ have the largest number of root ancestral configurations are exactly the species trees $S$ for which $(G,S)$ has the same set of pairs of antipodal leaves as $(G,G)$.

In other words, decomposing the leaves of a tree at the root into two subsets—those in one subtree of the root and those in the other—the pairs $(G,S)$ that for a fixed $G$ have the largest number of root ancestral configurations are those for which $S$ produces the same decomposition as $G$.

Proposition <ref> gives $c(G,S) \leq c(G,G)$. Suppose $G$ and $S$ have the same decomposition at the root,
Theorem <ref> gives $c(G,S) = c(G,G)$, as the ancestral configuration $\mathbf c$ of $(G,G)$ in which all non-antipodal pairs of lineages have coalesced is the maximal element of both $C(G,G)$ and $C(G,S)$. Hence, $D(G,S) = D(G, G)$.

Now we show that these are the only $S$ for which $c(G,S) = c(G,G)$. Suppose $c(G,S) = c(G,G)$. Then we must have $D(G,S)=D(G,G)$; because $D(G,S)$ is a sublattice of $D(G,G)$, this equality can hold only if the maximal elements of the two lattices are the same. In other words, $\mathbf c$—the maximal element of $D(G,S)$—is also the maximal element of $D(G,G)$. We conclude that all coalescences of $G$ on $S$ involve only non-antipodal pairs of lineages with respect to $S$, so that $S$ and $G$ possess the same decomposition at the root.

The pair $(G,S) = (\mathcal P_n, \mathcal C_n)$ with $n\geq 5$ satisfies the property in Corollary <ref>, and therefore $c(\mathcal P_n, \mathcal C_n) = c(\mathcal P_n, \mathcal P_n)$.

Note that although the lattice construction quickly enables the result $c(G,S) \leq c(G,G)$ (Proposition 10), and Corollary <ref> and Example <ref> show that $c(G,S)=c(G,G)$ for some $S \neq G$, it does not follow from these results that $c(G,S) \leq c(S,S)$ for $G \neq S$; indeed, <cit.> reported a counterexample, showing that $c(\mathcal P_n,\mathcal C_n) > c(\mathcal C_n, \mathcal C_n)$ for $n \geq 6$.

§ DISCUSSION

We have demonstrated that the set of ancestral configurations $C(G,S)$ for a rooted bifurcating gene tree $G$ and bijectively labeled species tree $S$ can be described by a lattice structure (Proposition <ref>). For matching gene trees and species trees, we have constructed Hasse diagrams and  digraphs for lattices of ancestral configurations, finding a correspondence between the maximal chains of the lattice $C(S,S)$ and the labeled histories for $S$ (Theorem <ref>).

For a matching tree pair $(S,S)$, we provided the recursive decomposition of the associated digraph of its ancestral configurations (Theorem <ref>). For a series of examples—$p$-pseudocaterpillars (Section <ref>), bicaterpillars (Section <ref>), lodgepole trees (Section <ref>), a modification of lodgepole trees (Section <ref>), and fully balanced trees (Section <ref>)—the recursive decomposition enabled us to describe the lattices associated with ancestral configurations of specific types of trees. For each tree family, we counted the associated numbers of root ancestral configurations and paths from the minimal element to the maximal element of the lattice. The recursive decomposition can be extended to nonmatching tree pairs (Theorem <ref>), suggesting the possibility of extending our numerical evaluations for matching families to a variety of nonmatching cases.

Our work can be seen as an extension of the work of <cit.> to define a recurrence for the number (eq. <ref>) of ancestral configurations and for the set of ancestral configurations (eq. <ref>). Here, we have extended the recurrence to lattices, as represented by digraphs, by using a cartesian product of graphs. This recurrence provides a quick way of building digraphs of ancestral configurations algorithmically.

By uncovering a lattice structure for ancestral configurations, we have seen that the root ancestral configurations for a pair of matching trees encode the information about labeled histories. Through path-counting on digraphs associated to ancestral configurations, we have obained visual proofs of special cases of the general eq. <ref> on the number of labeled histories associated with a labeled topology. For example, we proved that the number of labeled histories is $h(\mathcal C_{n,n}) = \binom{2n-2}{n-1}$ for bicaterpillars (Section <ref>), and $h(\mathcal L_n) = (2n-1)!!$ for lodgepole trees (Section <ref>).

Several enumerative problems arise directly from the bijection between paths on digraphs $D(S)$ and labeled histories. For example, how many labeled histories of $S$ are possible such that the realization of gene tree $S$ on species tree $S$ can display root ancestral configuration $c$? In the language of digraphs, each labeled history corresponds to a path, and each ancestral configuration corresponds to a vertex, so that this enumerative problem is equivalent to a problem of counting paths from the minimal to the maximal element that pass through a chosen node. As a path counting problem, the problem is similar to some considered for “coalescent histories” <cit.>, a combinatorial structure that, like ancestral configurations, is defined for gene trees and species trees <cit.>.

Similarly, suppose partial information about the temporal ordering of some (possibly all) of the coalescences of $S$ on $S$ is assumed: for example, suppose coalescence $\ell_i$ precedes $\ell_j$. In this case, we ask for the number of root ancestral configurations $c$ such that there exists a realization of $S$ on $S$ that displays $c$ and that satisfies given conditions on temporal ordering of coalescences. The lattice interpretation of root ancestral configurations then allows us to reinterpret this problem as counting the number of vertices that are encountered by paths in a given subset of paths from the minimal to the maximal element.

Interestingly, lattices have recently appeared in a related study, in which  <cit.> formalized a sense of “refinement” for “perfect phylogenies.” The lattices of <cit.> are similar to ours, in that in both cases, the “covering relations,” corresponding to edges of Hasse diagrams, arise from a “collapse” of objects on a tree—tree edges collapse to a point for <cit.> and lineages collapse to an ancestor in our case. <cit.> used the lattice construction to count certain classes of perfect phylogenies; taken together with that study, our work illustrates that partial orders and lattices have much potential to contribute to the formulation and resolution of enumeration problems in mathematical phylogenetics.

Acknowledgments. We acknowledge support from NIH grant R01 GM131404.


# Identifying and Mitigating Gender Bias in Hyperbolic Word Embeddings

Vaibhav Kumar Tenzin Singhay Bhotia††footnotemark:  Vaibhav
Kumar††footnotemark:
Delhi Technological University, India
{kumar.vaibhav1o1, tenzinbhotia0<EMAIL_ADDRESS>Tanmoy Chakraborty
Indraprastha Institute of Information Technology Delhi
<EMAIL_ADDRESS>Authors have contributed equally.

###### Abstract

Euclidean word embedding models such as GloVe and Word2Vec have been shown to
reflect human-like gender biases. In this paper, we extend the study of gender
bias to the recently popularized hyperbolic word embeddings. We propose
gyrocosine bias, a novel measure for quantifying gender bias in hyperbolic
word representations and observe a significant presence of gender bias. To
address this problem, we propose Poincaré Gender Debias (PGD), a novel
debiasing procedure for hyperbolic word representations. Experiments on a suit
of evaluation tests show that PGD effectively reduces bias while adding a
minimal semantic offset.

##  1 Introduction

Word embeddings are often used for word representation in a wide variety of
tasks. However, they have been shown to acquire gender stereotypes from the
data which they are trained on Bolukbasi et al. (2016); Caliskan et al.
(2017). For instance, Bolukbasi et al. (2016) showed that a Word2Vec Mikolov
et al. (2013a) model trained on Google news
corpus111https://code.google.com/archive/p/word2vec/, generates analogy such
as “man is to computer programmer as woman is to homemaker". Therefore, given
their pervasive usage, a large number of debiasing methods Bolukbasi et al.
(2016); Kaneko and Bollegala (2019); Bordia and Bowman (2019); Zhao et al.
(2018); Maudslay et al. (2019) have recently been proposed.

The existing literature on mitigating gender bias exclusively focuses on word
vectors which are embedded in an Euclidean space. However recently, non-
Euclidean space has also been investigated for embedding words. For instance,
motivated by the latent hierarchical structure of words, Tifrea et al. (2018)
generalize GloVe Pennington et al. (2014) to the hyperbolic space. As a
result, they obtain Poincaré GloVe embedding, which achieves superior
performance w.r.t GloVe in analogy, hypernymy detection, and word similarity
tasks simultaneously. Despite the performance gain achieved, we observe that
the issue of gender bias persists, as indicated by the biased analogies shown
in Table 1.

Gender Biased Analogies
---
man $\rightarrow$ doctor | woman $\rightarrow$ nurse
male $\rightarrow$ supervisor | female $\rightarrow$ assistant
man $\rightarrow$ programmer | woman $\rightarrow$ storyteller
he $\rightarrow$ surgeon | she $\rightarrow$ nurse
man $\rightarrow$ chairman | woman $\rightarrow$ secretory

Table 1: Gender biased analogies generated by Poincaré GloVe Tifrea et al.
(2018) trained on the English Wikipedia dump containing 1.4 billion tokens.

In order to address this issue, we extend the study of gender bias to the
hyperbolic space. We introduce gyrocosine bias, a metric for quantifying the
differential association of a given gender neutral word with a set of male and
female definitional words using gyrovector-based Ungar (2008) formalism.
Further, we propose Poincaré Gender Debias (PGD), a post-processing method for
debiasing words embedded on the hyperbolic space. Experiments on a suite of
evaluation tests show that PGD successfully mitigates gender bias while
introducing minimal semantic and syntactic offset. To the best of our
knowledge, this is the first work that addresses the issue of gender bias in
hyperbolic word embeddings.

##  2 Preliminaries

#### Hyperbolic Space and Poincaré Ball.

An $n$-dimensional Hyperbolic space $\mathbb{H}^{n}$ is a non-Euclidean space
with a constant negative curvature. Since a hyperbolic space cannot be
embedded into an Euclidean space Krioukov et al. (2010), several isometric
models have been proposed. Following Tifrea et al. (2018), we use the Poincaré
ball model of hyperbolic space. Formally, a Poincaré ball
$\left(\mathbb{D}^{n}_{c},g^{\mathbb{D}}\right)$ of a radius $1/\sqrt{c},c>0$
is defined by an $n$-dimensional manifold:

$\mathbb{D}^{n}_{c}=\left\\{x\in\mathbb{R}^{n}:c\|x\|<1\right\\}$

having the Riemannian metric $g_{x}^{\mathbb{D}}$ as
$g_{x}^{\mathbb{D}}=\lambda_{x}^{2}g^{E}$, where
$\lambda_{\mathbf{x}}=2/\left(1-c\|\mathbf{x}\|^{2}\right)$ is the conformal
factor, and $g^{E}=\mathbf{I}_{n}$ is the Euclidean metric tensor.

#### Gyrovector Space.

Gyrovector space provides the algebraic setting for hyperbolic geometry
(analogous to vector space for Euclidean geometry) Ungar (2008). We use
gyrovector operations to quantify the bias in hyperbolic space. A brief
description of the concepts used is given below222For a complete discussion,
refer to Ungar (2008)..

#### Möbius Addition and Subtraction.

The Möbius addition for $x,y\in\mathbb{D}^{n}_{c}$ is defined as:

$x\oplus_{c}y=\frac{\left(1+2c\langle
x,y\rangle+c\|y\|^{2}\right)x+\left(1-c\|x\|^{2}\right)y}{1+2c\langle
x,y\rangle+c^{2}\|x\|^{2}\|y\|^{2}}$

where $\|\cdot\|$ denotes the Euclidean norm, and $\langle\cdot,\cdot\rangle$
is the Euclidean dot product. The Möbius subtraction $\ominus$ is then defined
as $a\ominus z=a\oplus(-z)$. Note that in all cases, $c>0$ can be reduced to
$c=1$ without any loss of generality. We refer to $\oplus_{1}$ as $\oplus$.

#### Rooted Gyrovectors.

Any two ordered points $x,y\in\mathbb{D}^{n}$ give rise to a unique rooted
gyrovector $v=\ominus x\oplus y$, which has its tail as $x$ and head as $y$.
Additionally, any $z\in\mathbb{D}^{n}$ can be identified as a rooted
gyrovector with its tail at origin $O$ and head at $z$, which we represent as:
$z^{\prime}=O\oplus z$.

#### Gyrocosine Function.

The gyrocosine is a measure of the gyroangle $\alpha$ ($0\leq\alpha\leq\pi$)
between two non-zero rooted gyrovectors $\ominus{A_{1}}\oplus{B_{1}}$ and
$\ominus{A_{2}}\oplus{B_{2}}$, as given by:

$\cos\alpha=\frac{\ominus A_{1}\oplus B_{1}}{\|\ominus A_{1}\oplus
B_{1}\|}\cdot\frac{\ominus A_{2}\oplus B_{2}}{\|\ominus A_{2}\oplus B_{2}\|}$

#### Riemannian Optimization.

Let $f:\mathcal{M}\rightarrow\mathbb{R}$ be a smooth function to be optimized
over the Riemannian manifold ($\mathcal{M},p$). The Riemannian stochastic
gradient descent update Bonnabel (2013) is then defined as:

$x_{t+1}\leftarrow exp_{x_{t}}(-\alpha g_{t})$

where $g_{t}\in T_{x_{t}}\mathcal{M}$ is the Riemannian gradient of $f_{t}$ at
$x_{t}\in\mathcal{M}$, and $\alpha>0$ is the learning rate. In this work, we
use the Riemannian ADAM optimizer Bécigneul and Ganea (2018)333We use the
implementations provided by the open source library: geoopt Kochurov et al.
(2020).

##  3 Gender Bias and its Mitigation

###  3.1 Bias in Hyperbolic Word Embeddings

In this section, we first propose a pair of rooted gyrovectors to capture the
differential gender information in the embedding space and then use them to
quantify bias for any arbitrary word vector.

#### Gender Gyrovectors.

Given a set of words $\mathbb{W}$ embedded in an $n$-dimensional Poincaré ball
$\mathbb{D}^{n}$, the gender gyrovectors are defined as follows:

$\displaystyle{g}_{mf}=\ominus\mu_{M}\oplus\mu_{F}$ $\displaystyle\newline
{g}_{fm}=\ominus\mu_{F}\oplus\mu_{M}$

where, $\mu_{F}$ and $\mu_{M}$ denote the intrinsic mean Karcher (1977);
Fréchet (1948) of a set of male definitional and female definitional
hyperbolic word representations444We use the same set of gender definitional
words as Bolukbasi et al. (2016). respectively (see Appendix 1.1 for details).
We propose two gyrovectors for capturing the gender information because of the
non-commutative property of the binary Möbius addition operator.

Figure 1:  Comparison of gender bias across GloVe and Poincaré GloVe (vectors
of size $100D$ and trained on the English Wikipedia dump); x-axis denotes
gyrocosine bias, and y-axis denotes direct bias. Each point in the scatter
plot indicates a profession-related word.

#### Gyrocosine Bias.

For a gender-neutral word $w$ embedded in an $n$-dimensional Poincaré ball
$\mathbb{D}^{n}$, the gyrocosine bias is defined as follows:

$\gamma(w)=\frac{\cos({{w^{\prime}}},{{g}_{mf}})-\cos({{w^{\prime}}},{{g}_{fm}})}{2}$

where $\cos(.)$ is the gyrocosine function and $w^{\prime}$ is the rooted
gyrovector for $w$ as explained in Section 2. Here, a positive value of
$\gamma(w)$ implies that $w$ is female biased, while a negative value
indicates male bias. To validate our metric w.r.t its Euclidean counterpart,
we compare the gender bias for a set of profession words 555We use the list of
professions provided by Bolukbasi et al. (2016). across GloVe and Poincaré
GloVe in Figure 1, using direct bias Bolukbasi et al. (2016) and gyrocosine
bias respectively. We obtain a high Pearson correlation ($\rho=0.952$) which
indicates the competence of our metric in quantifying gender bias.

###  3.2 Proposed Bias Mitigation Method

We propose Poincaré Gender Debias (PGD), a multi-objective optimization based
method for reducing gyrocosine bias in hyperbolic word embeddings while
keeping the embeddings usable. To obtain the debiased counterpart ${w_{d}}$ of
a given word ${w}$, PGD solves the following multi-objective optimization
problem:

$argmin_{{w^{\prime}_{d}}}\big{(}F_{s}({w^{\prime}_{d}}),F_{g}({w^{\prime}_{d}})\big{)}$

We use the weighted sum method to solve this optimization problem. More
formally, we minimize the single objective function $F({w^{\prime}_{d}})$
which can be expressed as follows:

$\begin{split}&F({w^{\prime}_{d}})\ =\
\lambda_{1}.F_{s}({w^{\prime}_{d}})+\lambda_{2}.F_{g}({w^{\prime}_{d}})\\\
&\text{such that\
}\lambda_{i}\in[0,1]\>\text{and}\>\sum_{i}\lambda_{i}=1\end{split}\vspace{-4mm}$
(1)

$F({{w^{\prime}_{d}}})$ is minimized using Riemannian optimization as
described in Section 2. We use the learning rate of $3\times 10^{-4}$ and
equal objective weights, $\lambda_{1}=0.5$ and $\lambda_{2}=0.5$. We now
explain each component of Equation 1; the range of each can be observed to be
$[0,1]$.

####  $\boldsymbol{F_{g}({w^{\prime}_{d}})}$:

This objective function aims to equalize word gyrovectors with the notion of
male and female gender in the embedding space. It does so by minimizing the
absolute difference of the gyrocosine values of the given word gyrovector and
the two gender gyrovectors. The objective function is defined as follows:

$\displaystyle
F_{g}({w}^{\prime}_{d})=\left|\cos({w^{\prime}_{d}},{g}_{mf})-\cos({w^{\prime}_{d}},{g}_{fm})\right|/2$

####  $\boldsymbol{F_{s}({w^{\prime}_{d}})}$:

This objective function aims to minimize the semantic offset caused by the
debiasing procedure by maximizing the gyrocosine value between the rooted
gyrovectors for a given word and its debias counterpart, thereby ensuring that
the gyroangle between the two is minimum. The objective is defined as follows:

$\displaystyle F_{s}({w}^{\prime}_{d})$
$\displaystyle=|\cos({w}^{\prime}_{d},{w}^{\prime})-\cos({w}^{\prime},{w}^{\prime})|/2$
$\displaystyle=|\cos({w}^{\prime}_{d},{w}^{\prime})-1|/2$

Embedding | (a) WEAT | (b) SemBias
---|---|---
$B_{1}$: Career vs Family |  $B_{2}$: Math vs Art |  $B_{3}$: Science vs Art |  Def $\uparrow$ |  Ster $\downarrow$ |  None $\downarrow$
$p\uparrow$ | $d\downarrow$ | $p\uparrow$ | $d\downarrow$ | $p\uparrow$ | $d\downarrow$ |  |  |
E-Glove | 0.0773 | 0.7423 | 0.4186 | 0.1716 | 0.5443 | -0.1131 | 79.5 | 14.8 | 5.7
P-GloVe | 0.0418 | 0.8929 | 0.3045 | 0.2929 | 0.2138 | 0.4568 | 75.3 | 7.0 | 17.7
PGD-GloVe | 0.2827 | 0.3054 | 0.8292 | -0.5379 | 0.6015 | -0.1984 | 83.0 | 0.0 | 17.0

Table 2: Comparison of different embedding models on (a) WEAT for different
sets of target words - $B_{i}$ and (b) SemBias dataset. $\uparrow(\downarrow)$
indicates that higher (lower) value is better. In (a), a $p$-value $>$ 0.5
denotes insignificant bias, and a lower Cohen’s $d$ shows lesser bias. We use
(negative) Poincaré distance as a measure of similarity for P-GloVe and PGD-
GloVe (see Appendix 2.1 for details).

Embedding | (a) Semantic | (b) Analogy
---|---|---
RW | WordSim | SimLex | SimVerb | MC | RG | Google-Sem | Google-Syn | MSR
E-Glove | 0.3787 | 0.5668 | 0.2964 | 0.1639 | 0.6562 | 0.6757 | 0.6427 | 0.5950 | 0.4826
P-GloVe | 0.4190 | 0.6207 | 0.3210 | 0.1915 | 0.7883 | 0.7596 | 0.6629 | 0.6086 | 0.4958
PGD-GloVe | 0.4170 | 0.6152 | 0.3215 | 0.1914 | 0.7873 | 0.7569 | 0.6635 | 0.6069 | 0.4938

Table 3: Comparison of different embedding models in (a) semantic and (b)
analogy tests. The performance of PGD-GloVe is at par with other baselines,
indicating the addition of minimal semantic disturbance.

##  4 Experiments and Results

###  4.1 Dataset and Baselines

We use the following pre-trained word embedding models provided by Tifrea et
al. (2018) as our baseline, each of which is trained on the English Wikipedia
dump and consists of 189,533 tokens: $100D$ Poincaré GloVe,
$h(x)=\cosh^{2}(x)$, with init trick666Refer Tifrea et al. (2018). – referred
to as P-GloVe; $100D$ Euclidean GloVe, with init trick – referred to as
E-Glove. We debias Poincaré GloVe using PGD to obtain PGD\- GloVe. Similiar to
Bolukbasi et al. (2016), we split the vocabulary into a set of gender specific
$S$ and gender neutral words $N$. Only $N$, consisting of $126,065$ words, is
debiased.

###  4.2 Evaluation Metrics and Results

#### Word Embedding Association Test (WEAT):

Caliskan et al. (2017) introduce WEAT, a hypothesis testing method for
analyzing stereotypical biases present in word embeddings. WEAT comprises two
sets of equal-sized target words – $X$ (like ‘engineer’, ‘warrior’) and $Y$
(like ‘nurse’, ‘receptionist’), and two sets of equal sized attribute words –
$A$ (like ‘he’, ‘male’) and $B$ (like ‘she’, ‘female’) 777Refer Appendix 2.2
for the complete list of words.. The aim of the test is to determine if the
set $X$ or $Y$ is more biased towards one gender than the other. We report
Cohen’s $d$ and $p$-value for three categories of target words in Table 2(a).
Evidently, PGD-GloVe achieves consistent performance for all sets of target
words, reflecting the efficient reduction in bias (see Appendix 2.2 for more
details). Further, we observe that Poincaré GloVe is more biased than
Euclidean GloVe, having a lower $p$-value and a higher Cohen’s $d$ for all the
target word categories. Since, the training data and variable configurations
like the dimensions and initialization were same, a higher bias could be due
to the negative curvature of hyperbolic space and would remain as an
interesting future direction.

#### SemBias:

SemBias Zhao et al. (2018) is a word analogy dataset used for measuring the
ability of word embeddings to generate biased analogies. Each instance of
SemBias consists of four types of word pairs – gender-definition word pair
(Def; e.g., ‘wizard-witch’), gender-stereotype word pair (Ster; e.g., ‘doctor-
nurse’) and two other word pairs having similar meanings but no gender-based
relation (None; e.g., ‘salt-pepper’). For each instance, we choose the most
probable analogy estimated by the embedding model. The analogy computation for
word embeddings in Poincaré ball model uses a hyper-parameter 888Refer
Appendix 2.3 for more details. $t\in[0,1]$ Tifrea et al. (2018). Following
Levy et al. (2015); Tifrea et al. (2018), we use 2-fold cross-validation over
the gender-definition word pair analogies to estimate the value of $t$ as
$0.3$. From Table 2(b), we can observe that Ster analogies are completely
inhibited for PGD-GloVe along with a 10.2 % relative improvement in Def w.r.t
P-GloVe. This implies that PGD dramatically mitigates the preference of a
gender-neutral word between male and female words, thereby improving its
efficacy to form correct analogies. We further observe that P-GloVe has a
lesser (Ster) score as compared to E-GloVe. However, this result is attained
by a lower performance in Def and None, indicating the superiority of E-GloVe.

#### Semantic Tests:

Word semantic similarity tests determine the correlation between the
similarity of word pairs obtained through the word embeddings and the
similarity ratings given by humans. We report Spearman’s correlations for the
following benchmark datasets: RW Luong et al. (2013), WordSim Agirre et al.
(2009), SimLex Hill et al. (2015), SimVerb Gerz et al. (2016), MC Miller and
Charles (1991), and RG Rubenstein and Goodenough (1965). Following Tifrea et
al. (2018), we use the negative Poincaré distance as the similarity metric for
P-GloVe and PGD-GloVe while for E-GloVe, we use the regular cosine similarity.
Table 3(a) shows that PGD-GloVe successfully retains most of semantic
information. Therefore, PGD produces minimal semantic offset.

#### Analogy Tests:

Analogy tests assess the efficacy of a word embedding model to answer the
following question : ‘$w_{1}$ is to $w_{2}$ as $w_{3}$ is to ?’. Here, unknown
word $w_{4}$ is estimated as the closest word vector to the arithmetic:
$w_{2}-w_{1}+w_{3}$. Following Tifrea et al. (2018), we estimate the closest
word vector $w_{4}$ using gyro-translations and the cosine similarity metric
for the following benchmarks: Google Sem, Syn Mikolov et al. (2013b) and MSR
Mikolov et al. (2013c). Table 3(b) shows that PGD-GloVe closely follows
P-GloVe in all the analogy measures. The offsets are so minimal that PGD-GloVe
retains the semantic and analogy advantages of P-GloVe over E-GloVe.

##  5 Conclusion

In this paper, we presented the first study of gender bias in a non-Euclidean
space. We proposed gyrocosine bias, a metric for quantifying gender bias in
hyperbolic embedding. We observed that stereotypical gender biases permeate
the Poincaré GloVe model. We also proposed Poincaré Gender Debias, a post-
processing method for debiasing hyperbolic word embeddings. Experimental
results indicated that our method successfully minimizes gender bias while
retaining the practical usability of word embeddings.

## References

  * Agirre et al. (2009) Eneko Agirre, Enrique Alfonseca, Keith Hall, Jana Kravalova, Marius Paşca, and Aitor Soroa. 2009.  A study on similarity and relatedness using distributional and WordNet-based approaches.  In _Proceedings of Human Language Technologies: The 2009 Annual Conference of the North American Chapter of the Association for Computational Linguistics_ , pages 19–27, Boulder, Colorado. Association for Computational Linguistics.
  * Bécigneul and Ganea (2018) Gary Bécigneul and Octavian-Eugen Ganea. 2018.  Riemannian adaptive optimization methods.  _arXiv preprint arXiv:1810.00760_.
  * Bolukbasi et al. (2016) Tolga Bolukbasi, Kai-Wei Chang, James Y Zou, Venkatesh Saligrama, and Adam T Kalai. 2016.  Man is to computer programmer as woman is to homemaker? debiasing word embeddings.  In _Advances in neural information processing systems_ , pages 4349–4357.
  * Bonnabel (2013) Silvere Bonnabel. 2013.  Stochastic gradient descent on riemannian manifolds.  _IEEE Transactions on Automatic Control_ , 58(9):2217–2229.
  * Bordia and Bowman (2019) Shikha Bordia and Samuel R. Bowman. 2019.  Identifying and reducing gender bias in word-level language models.  _CoRR_ , abs/1904.03035.
  * Caliskan et al. (2017) Aylin Caliskan, Joanna J Bryson, and Arvind Narayanan. 2017.  Semantics derived automatically from language corpora contain human-like biases.  _Science_ , 356(6334):183–186.
  * Fréchet (1948) Maurice Fréchet. 1948.  Les éléments aléatoires de nature quelconque dans un espace distancié.  In _Annales de l’institut Henri Poincaré_ , volume 10, pages 215–310.
  * Gerz et al. (2016) Daniela Gerz, Ivan Vulić, Felix Hill, Roi Reichart, and Anna Korhonen. 2016\.  Simverb-3500: A large-scale evaluation set of verb similarity.  _arXiv preprint arXiv:1608.00869_.
  * Hill et al. (2015) Felix Hill, Roi Reichart, and Anna Korhonen. 2015.  Simlex-999: Evaluating semantic models with (genuine) similarity estimation.  _Computational Linguistics_ , 41(4):665–695.
  * Kaneko and Bollegala (2019) Masahiro Kaneko and Danushka Bollegala. 2019.  Gender-preserving debiasing for pre-trained word embeddings.  _Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics_ , page 1641–1650.
  * Karcher (1977) Hermann Karcher. 1977.  Riemannian center of mass and mollifier smoothing.  _Communications on pure and applied mathematics_ , 30(5):509–541.
  * Kochurov et al. (2020) Max Kochurov, Rasul Karimov, and Sergei Kozlukov. 2020.  Geoopt: Riemannian optimization in pytorch.  _arXiv preprint arXiv:2005.02819_.
  * Krioukov et al. (2010) Dmitri Krioukov, Fragkiskos Papadopoulos, Maksim Kitsak, Amin Vahdat, and Marián Boguná. 2010.  Hyperbolic geometry of complex networks.  _Physical Review E_ , 82(3):036106.
  * Levy et al. (2015) Omer Levy, Yoav Goldberg, and Ido Dagan. 2015.  Improving distributional similarity with lessons learned from word embeddings.  _Transactions of the Association for Computational Linguistics_ , 3:211–225.
  * Luong et al. (2013) Minh-Thang Luong, Richard Socher, and Christopher D Manning. 2013.  Better word representations with recursive neural networks for morphology.  In _Proceedings of the Seventeenth Conference on Computational Natural Language Learning_ , pages 104–113.
  * Maudslay et al. (2019) Rowan Hall Maudslay, Hila Gonen, Ryan Cotterell, and Simone Teufel. 2019.  It’s all in the name: Mitigating gender bias with name-based counterfactual data substitution.  _Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP)_ , page 5267–5275.
  * Mikolov et al. (2013a) Tomas Mikolov, Kai Chen, Greg Corrado, and Jeffrey Dean. 2013a.  Efficient estimation of word representations in vector space.  _1st International Conference on Learning Representations, ICLR 2013,Workshop Track Proceedings_ , pages 1–12.
  * Mikolov et al. (2013b) Tomas Mikolov, Ilya Sutskever, Kai Chen, Greg S Corrado, and Jeff Dean. 2013b.  Distributed representations of words and phrases and their compositionality.  In _Advances in neural information processing systems_ , pages 3111–3119.
  * Mikolov et al. (2013c) Tomáš Mikolov, Wen-tau Yih, and Geoffrey Zweig. 2013c.  Linguistic regularities in continuous space word representations.  In _Proceedings of the 2013 conference of the north american chapter of the association for computational linguistics: Human language technologies_ , pages 746–751.
  * Miller and Charles (1991) George A Miller and Walter G Charles. 1991.  Contextual correlates of semantic similarity.  _Language and cognitive processes_ , 6(1):1–28.
  * Pennington et al. (2014) Jeffrey Pennington, Richard Socher, and Christopher Manning. 2014.  Glove: Global vectors for word representation.  In _Proceedings of the 2014 conference on empirical methods in natural language processing (EMNLP)_ , pages 1532–1543.
  * Rubenstein and Goodenough (1965) Herbert Rubenstein and John B Goodenough. 1965.  Contextual correlates of synonymy.  _Communications of the ACM_ , 8(10):627–633.
  * Tifrea et al. (2018) Alexandru Tifrea, Gary Bécigneul, and Octavian-Eugen Ganea. 2018.  Poincare glove: Hyperbolic word embeddings.  _arXiv preprint arXiv:1810.06546_.
  * Ungar (2008) Abraham Albert Ungar. 2008.  A gyrovector space approach to hyperbolic geometry.  _Synthesis Lectures on Mathematics and Statistics_ , 1(1):1–194.
  * Zhao et al. (2018) Jieyu Zhao, Yichao Zhou, Zeyu Li, Wei Wang, and Kai-Wei Chang. 2018.  Learning gender-neutral word embeddings.  _Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing_ , page 4847–4853.