| \section{Proofs and Algorithm Details}\label{appdx:proof_algo} |
| This section contains full proofs of the main theoretical results and detailed algorithm specifications. |
|
|
| \subsection{Proofs} |
|
|
| \begin{theorem}[Restatement of Theorem~\ref{thm:polyilr}] |
| Let $\mathcal{T}$ be any rooted tree with $d$ leaves. The matrix $V \in \mathbb{R}^{d \times (d-1)}$ from Algorithm~\ref{alg:polyilr} satisfies: |
| \begin{enumerate} |
| \item $V^\top \mathbf{1} = 0$ \textup{(contrast property)}, |
| \item $V^\top V = I_{d-1}$ \textup{(orthonormality)}. |
| \end{enumerate} |
| Consequently, $\varphi(x) = V^\top \log x$ is an isometry from $(\Delta^{d-1}, \langle \cdot, \cdot \rangle_A)$ to $(\mathbb{R}^{d-1}, \langle \cdot, \cdot \rangle_2)$. |
| \end{theorem} |
|
|
| \begin{proof} |
| Let $T$ be a rooted tree with $d$ leaves. For each internal node $u$ with $k_u$ children, let $C_u^{(r)}$ denote the set of leaves descending from child $r$, and let $n_r = |C_u^{(r)}|$. The construction produces a local basis $\tilde{H}^{(u)} \in \mathbb{R}^{k_u \times (k_u - 1)}$ that is orthonormal under the weighted inner product $\langle h, h' \rangle_w = \sum_{r=1}^{k_u} h_r h'_r / n_r$ and satisfies the contrast condition $\sum_{r=1}^{k_u} \tilde{H}^{(u)}_{r,m} = 0$ for all $m$. Each local vector is spread to a global vector $v^{(u,m)} \in \mathbb{R}^d$ via |
| \[ |
| v^{(u,m)}_i = |
| \begin{cases} |
| \tilde{H}^{(u)}_{r,m} / n_r & \text{if } i \in C_u^{(r)} \text{ for some } r \in \{1, \ldots, k_u\}, \\ |
| 0 & \text{otherwise}. |
| \end{cases} |
| \] |
| The precise procedure is given in Algorithm~\ref{alg:polyilr}. It suffices for us to show that $V$ (i) satisfies the contrast property (hence its columns span the tangent space $\mathcal{H}$), (ii) is orthonormal within each node, and (iii) is orthonormal across distinct nodes. |
|
|
| \emph{(i) Contrast property.} |
| For any internal node $u$ and contrast index $m$, |
| \[ |
| \sum_{i=1}^{d} v^{(u,m)}_i |
| = \sum_{r=1}^{k_u} \sum_{i \in C_u^{(r)}} \frac{\tilde{H}^{(u)}_{r,m}}{n_r} |
| = \sum_{r=1}^{k_u} n_r \cdot \frac{\tilde{H}^{(u)}_{r,m}}{n_r} |
| = \sum_{r=1}^{k_u} \tilde{H}^{(u)}_{r,m} = 0, |
| \] |
| where the last equality holds because $\tilde{H}^{(u)}$ is obtained by applying Gram-Schmidt to Helmert contrasts, which lie in the subspace $S_u = \{h \in \mathbb{R}^{k_u} : \sum_r h_r = 0\}$, and Gram-Schmidt preserves this subspace. |
|
|
| \emph{(ii) Within-node orthonormality.} |
| For any internal node $u$ and contrast indices $m_1, m_2 \in \{1, \ldots, k_u - 1\}$, |
| \begin{align*} |
| \langle v^{(u,m_1)}, v^{(u,m_2)} \rangle |
| &= \sum_{i=1}^{d} v^{(u,m_1)}_i \, v^{(u,m_2)}_i |
| = \sum_{r=1}^{k_u} \sum_{i \in C_u^{(r)}} \frac{\tilde{H}^{(u)}_{r,m_1}}{n_r} \cdot \frac{\tilde{H}^{(u)}_{r,m_2}}{n_r} \\ |
| &= \sum_{r=1}^{k_u} n_r \cdot \frac{\tilde{H}^{(u)}_{r,m_1} \, \tilde{H}^{(u)}_{r,m_2}}{n_r^2} |
| = \sum_{r=1}^{k_u} \frac{\tilde{H}^{(u)}_{r,m_1} \, \tilde{H}^{(u)}_{r,m_2}}{n_r} \\ |
| &= \langle \tilde{H}^{(u)}_{\cdot, m_1}, \tilde{H}^{(u)}_{\cdot, m_2} \rangle_w |
| = \delta_{m_1, m_2}, |
| \end{align*} |
| where the last equality holds by construction of $\tilde{H}^{(u)}$ as an orthonormal basis under $\langle \cdot, \cdot \rangle_w$. |
|
|
| \emph{(iii) Across-node orthogonality.} |
| Consider two distinct internal nodes $u \neq u'$ with contrast indices $m$ and $m'$ respectively. We consider two cases. (a) If the subtrees rooted at $u$ and $u'$ share no leaves, then $v^{(u,m)}$ and $v^{(u',m')}$ have disjoint supports, so $\langle v^{(u,m)}, v^{(u',m')} \rangle = 0$. (b) Suppose without loss of generality that $u'$ is a descendant of $u$. Then $u'$ lies entirely within the subtree of exactly one child of $u$, say child $s$, so the support of $v^{(u',m')}$ is contained in $C_u^{(s)}$. On $C_u^{(s)}$, the vector $v^{(u,m)}$ takes the constant value $\tilde{H}^{(u)}_{s,m} / n_s$. Since $v^{(u',m')}_i = 0$ for $i \notin C_u^{(s)}$, |
| \[ |
| \langle v^{(u,m)}, v^{(u',m')} \rangle |
| = \sum_{i \in C_u^{(s)}} v^{(u,m)}_i \, v^{(u',m')}_i |
| = \frac{\tilde{H}^{(u)}_{s,m}}{n_s} \sum_{i \in C_u^{(s)}} v^{(u',m')}_i |
| = \frac{\tilde{H}^{(u)}_{s,m}}{n_s} \cdot 0 = 0, |
| \] |
| where the last equality uses (i): the entries of $v^{(u',m')}$ sum to zero, and all nonzero entries lie within $C_u^{(s)}$. |
|
|
| \emph{Conclusion.} |
| (i), (ii), and (iii) establish that $V^\top \mathbf{1} = 0$ and $V^\top V = I_{d-1}$. For the dimension count, let $N_{\mathrm{int}}$ denote the number of internal nodes. Every non-root node has exactly one parent, so the number of edges satisfies $|E| = d + N_{\mathrm{int}} - 1$. Since $|E| = \sum_u k_u$, we have |
| \[ |
| \sum_u (k_u - 1) = \sum_u k_u - N_{\mathrm{int}} = (d + N_{\mathrm{int}} - 1) - N_{\mathrm{int}} = d - 1 = \dim(\mathcal{H}). |
| \] |
| By standard ILR theory, any $V \in \mathbb{R}^{d \times (d-1)}$ satisfying $V^\top \mathbf{1} = 0$ and $V^\top V = I_{d-1}$ has columns forming an orthonormal basis of $\mathcal{H}$, the image of $\mathrm{clr}$. Thus $\phi(x) = V^\top \log x$ is an isometry from $(\Delta^{d-1}, \langle \cdot, \cdot \rangle_A)$ to $(\mathbb{R}^{d-1}, \langle \cdot, \cdot \rangle_2)$. |
| \end{proof} |
|
|
| \begin{proposition}[Restatement of Proposition~\ref{prop:recovery}] |
| Given a rooted tree $\mathcal{T}$ with fixed leaf labels, fixed child orderings, \textcolor{black}{and a fixed ordering $\pi$ of internal nodes (e.g., DFS)}, PolyILR produces a unique basis $V(\mathcal{T})$. Moreover, $\mathcal{T} \mapsto V(\mathcal{T})$ is injective: $\mathcal{T}$ can be recovered constructively from $V$. |
| |
| \end{proposition} |
|
|
| \begin{proof}[Proof] |
| We prove uniqueness and recoverability separately. |
|
|
| \emph{(i) Uniqueness.} |
| The PolyILR construction (Algorithm~\ref{alg:polyilr}) is deterministic given the tree $T$, leaf labels, child orderings at each internal node, and an ordering $\pi$ of internal nodes. At each node $u$ with $k_u$ children, the construction follows: |
| \begin{itemize} |
| \item The descendant sets $C_u^{(r)}$ and counts $n_r = |C_u^{(r)}|$ are determined by $T$ and the leaf labels, and the corresponding weighted inner product $\langle h, h' \rangle_w = \sum_r h_r h'_r / n_r$ is determined by $\{n_r\}$. |
| \item The Helmert matrix $H^{(u)} \in \mathbb{R}^{k_u \times (k_u - 1)}$ is determined by $k_u$ and the child ordering. The weighted-orthonormal basis $\tilde{H}^{(u)}$ is obtained by applying Gram-Schmidt to $H^{(u)}$ under $\langle \cdot, \cdot \rangle_w$. Gram-Schmidt is made unique by normalizing each output vector to unit $w$-norm and adopting a fixed sign convention (e.g., the first nonzero entry in child order is positive). Gram-Schmidt works as the weighted inner product forms a Hilbert space over the subspace $\mathcal{S}_u$. |
| \item The spreading operation is deterministic given $C_u^{(r)}$ and $n_r$. |
| \end{itemize} |
| Thus $V(T)$ is uniquely determined. This makes PolyILR \emph{canonical}, i.e., the construction does not incur intractable randomness. |
|
|
| \emph{(ii) Recoverability.} |
| We show that the tree topology can be recovered from $V$. |
|
|
| \emph{Support structure:} By the structure of Helmert contrasts, column $m$ of $H^{(u)}$ has nonzero entries only in rows $1, \ldots, m+1$. Since Gram-Schmidt orthonormalizes sequentially, $\tilde{H}^{(u)}_{\cdot,m}$ is a linear combination of $H^{(u)}_{\cdot,1}, \ldots, H^{(u)}_{\cdot,m}$, so $\tilde{H}^{(u)}_{r,m} = 0$ for $r > m+1$. Moreover, columns $1, \ldots, m-1$ of $H^{(u)}$ have zeros in row $m+1$, so orthogonalizing against them does not affect entry $(m+1, m)$; thus $\tilde{H}^{(u)}_{m+1,m} = H^{(u)}_{m+1,m} \neq 0$. After spreading, the support of $v^{(u,m)}$ is $\bigcup_{r=1}^{m+1} C_u^{(r)}$, and the supports at node $u$ form a \emph{strictly nested chain}: |
| \[ |
| \mathrm{supp}(v^{(u,1)}) \subsetneq \mathrm{supp}(v^{(u,2)}) \subsetneq \cdots \subsetneq \mathrm{supp}(v^{(u,k_u-1)}) = \bigcup_{r=1}^{k_u} C_u^{(r)}. |
| \] |
|
|
| {\color{black} |
| |
|
|
| \emph{Recovering the child clades of a fixed node.} |
| Fix an internal node $u$ with children $C_u^{(1)},\dots,C_u^{(k_u)}$. From the support-structure argument above, |
| \[ |
| \mathrm{supp}\!\bigl(v^{(u,m)}\bigr)=\bigcup_{r=1}^{m+1} C_u^{(r)}. |
| \] |
| For $m=2,\dots,k_u-1$, the child clades $C_u^{(m+1)} = \mathrm{supp}\!\bigl(v^{(u,m)}\bigr)\setminus \mathrm{supp}\!\bigl(v^{(u,m-1)}\bigr)$ are determined by the support chain alone. It remains to recover $C_u^{(1)}$ and $C_u^{(2)}$ from $\mathrm{supp}(v^{(u,1)}) = C_u^{(1)} \cup C_u^{(2)}$. Since there are no previous columns to orthogonalize against, the first weighted Gram-Schmidt output satisfies $\tilde H^{(u)}_{\cdot,1} = \alpha \, H^{(u)}_{\cdot,1}$ for some $\alpha>0$. The first Helmert column has opposite signs in rows $1$ and $2$, so $\tilde H^{(u)}_{1,1} > 0$ and $\tilde H^{(u)}_{2,1} < 0$. After spreading, the values $\tilde H^{(u)}_{1,1}/n_1 > 0 > \tilde H^{(u)}_{2,1}/n_2$ are distinct, so the two level sets of $v^{(u,1)}$ on its support are precisely $C_u^{(1)}$ and $C_u^{(2)}$. |
|
|
| |
|
|
| \emph{Recovering the full tree.} |
| Applying the preceding child-clade recovery argument at the root and then recursively |
| to each non-singleton child clade recovers all clades of $\mathcal{T}$. A rooted |
| tree with labeled leaves is uniquely determined by its clades via inclusion: |
| $u'$ is a child of $u$ iff the clade of $u'$ is a maximal proper subset of the |
| clade of $u$ (i.e., a strict subset $C' \subsetneq C$ with no clade $C''$ satisfying $C' \subsetneq C'' \subsetneq C$), and leaves are singleton clades. Thus $\mathcal{T}$ is recoverable |
| from $V$.} |
| \end{proof} |
|
|
| Here, we comment on child orderings. Different child orderings at node $u$ yield local bases that differ by an orthogonal transformation on $(S_u, \langle \cdot, \cdot \rangle_w)$. This induces an orthogonal transformation on the $(k_u-1)$-dimensional coordinate block of $V$ corresponding to $u$. The geometry is preserved; only coordinate labels change. Now, we present the proof for Proposition~\ref{prop:logit-clr}. |
|
|
| \begin{proposition}[Restatement of Proposition~\ref{prop:logit-clr}] |
| Let $\mathcal{L} = \mathbb{R}^d / {\sim_{\ell}}$ be the quotient space of logits under shift equivalence. Then $\mathcal{L} \cong \mathcal{H}$ (linear isomorphism). Concretely, for $\mathbf{p} = \mathrm{softmax}(\mathbf{z})$, we have |
| \[ |
| \mathbf{z} - \bar{z}\mathbf{1} = \mathrm{clr}(\mathbf{p}), \quad \text{where } \bar{z} = \tfrac{1}{d}\textstyle\sum_i z_i, |
| \] |
| and $[\mathbf{z}] \to \mathbf{z} - \bar{z}\mathbf{1}$ is well-defined. |
| \end{proposition} |
|
|
| \begin{proof} |
| We establish both the concrete identity and the isomorphism. |
|
|
| \emph{(i) Centered logits equal CLR coordinates.} |
| Let $p = \mathrm{softmax}(z)$, so $p_i = e^{z_i} / \sum_j e^{z_j}$. Taking logarithms, |
| \[ |
| \log p_i = z_i - \log \sum_j e^{z_j}. |
| \] |
| The CLR transform is $\mathrm{clr}(p)_i = \log p_i - \frac{1}{d}\sum_k \log p_k$. Substituting, |
| \begin{align*} |
| \mathrm{clr}(p)_i |
| &= \left( z_i - \log \sum_j e^{z_j} \right) - \frac{1}{d} \sum_k \left( z_k - \log \sum_j e^{z_j} \right) \\ |
| &= z_i - \log \sum_j e^{z_j} - \bar{z} + \log \sum_j e^{z_j} \\ |
| &= z_i - \bar{z}, |
| \end{align*} |
| where $\bar{z} = \frac{1}{d}\sum_k z_k$. Thus $\mathrm{clr}(p) = z - \bar{z}\mathbf{1}$. |
|
|
| \emph{(ii) Isomorphism.} |
| Define the centering map $\pi \colon \mathbb{R}^d \to \mathcal{H}$ by $\pi(z) = z - \bar{z}\mathbf{1}$. We show $\pi$ induces a linear isomorphism from $\mathcal{L} = \mathbb{R}^d/{\sim_\ell}$ to $\mathcal{H}$. If $z' = z + c\mathbf{1}$ for some $c \in \mathbb{R}$, then $\bar{z'} = \bar{z} + c$, so |
| \[ |
| \pi(z') = z + c\mathbf{1} - (\bar{z} + c)\mathbf{1} = z - \bar{z}\mathbf{1} = \pi(z). |
| \] |
| Thus $\pi$ is constant on equivalence classes and descends to a map $\tilde{\pi} \colon \mathcal{L} \to \mathcal{H}$. For any $z \in \mathbb{R}^d$, $\mathbf{1}^\top \pi(z) = \sum_i (z_i - \bar{z}) = d\bar{z} - d\bar{z} = 0$, so $\pi(z) \in \mathcal{H}$. Now, for any $h \in \mathcal{H}$, we have $\bar{h} = 0$, so $\pi(h) = h - 0 \cdot \mathbf{1} = h$. Thus $\pi$ is surjective onto $\mathcal{H}$. Suppose $\pi(z) = \pi(z')$. Then $z - \bar{z}\mathbf{1} = z' - \bar{z'}\mathbf{1}$, which gives $z - z' = (\bar{z} - \bar{z'})\mathbf{1}$. Thus $z \sim_\ell z'$, so $\tilde{\pi}$ is injective. Since $\pi$ is linear and constant on equivalence classes, the induced map $\tilde{\pi}$ is linear. Thus, $\tilde{\pi} \colon \mathcal{L} \to \mathcal{H}$ is a linear isomorphism. Moreover, equipping $\mathcal{L}$ with the quotient metric $d_\mathcal{L}([z], [z']) = \inf_{c \in \mathbb{R}} \|z - z' + c\mathbf{1}\|$, the infimum is attained at $c = \bar{z'} - \bar{z}$, which gives $d_\mathcal{L}([z], [z']) = \|\pi(z) - \pi(z')\|_2$. Thus $\tilde{\pi}$ is an isometry. |
| \end{proof} |
|
|
| \subsection{Algorithm Details} |
|
|
| \paragraph{Time complexity and runtime of PolyILR.} |
| Algorithm~\ref{alg:polyilr} constructs $V$ in $O(d^2)$ time. For each internal node $u$ with $k_u$ children, building the Helmert matrix takes $O(k_u^2)$ time, Gram-Schmidt orthonormalization takes $O(k_u^3)$ time, and spreading to the $d$-dimensional vectors takes $O(n_u \cdot k_u)$ time where $n_u = \sum_r n_r$ is the number of leaves in the subtree rooted at $u$. Summing over all internal nodes, the total cost is dominated by the spreading step: $\sum_u n_u \cdot k_u \leq d \cdot \sum_u k_u = O(d^2)$ in the worst case (e.g., a star tree). For balanced trees, the complexity reduces to $O(d \log d)$. In practice, $V$ is computed once as a preprocessing step, so this cost is negligible compared to downstream tasks such as model training or statistical inference, which typically scale with sample size $N$ and involve iterative optimization. In all of our experiments, constructing $V$ using PolyILR took $<5$ seconds. |
|
|
| \paragraph{On Gram-Schmidt.} |
| The weighted Gram-Schmidt procedure orthonormalizes the columns of the Helmert matrix $H^{(u)}$ under the inner product $\langle h, h' \rangle_w = \sum_{r=1}^{k_u} h_r h'_r / n_r$. This is well-defined since $(S_u, \langle \cdot, \cdot \rangle_w)$ is a finite-dimensional Hilbert space. Explicitly, for $m = 1, \ldots, k_u - 1$: |
| \[ |
| \tilde{H}^{(u)}_{\cdot, m} = H^{(u)}_{\cdot, m} - \sum_{j=1}^{m-1} \langle H^{(u)}_{\cdot, m}, \tilde{H}^{(u)}_{\cdot, j} \rangle_w \, \tilde{H}^{(u)}_{\cdot, j}, \quad \text{then normalize: } \tilde{H}^{(u)}_{\cdot, m} \leftarrow \frac{\tilde{H}^{(u)}_{\cdot, m}}{\|\tilde{H}^{(u)}_{\cdot, m}\|_w}. |
| \] |
| The weighting by $1/n_r$ accounts for clade sizes: larger clades contribute less per-component to the inner product, ensuring that the resulting ILR coordinates treat leaves uniformly regardless of tree imbalance. |
|
|
| \paragraph{On Child ordering conventions.} |
| The child ordering at each internal node affects which contrasts appear in which columns of $V$, but does not affect the subspace spanned or the geometric properties as mentioned before. Two natural conventions are: (i) \emph{Lexicographic:} Order children by the smallest leaf index in each subtree. This is deterministic given leaf labels. (ii) \emph{By clade size:} Order children by descending $n_r$. This places contrasts involving larger clades in earlier columns. As noted in Proposition~\ref{prop:recovery}, different child orderings yield bases related by orthogonal transformations within each node's coordinate block. For reproducibility, we used the lexicographic ordering in all of our experiments. |
|
|
| \paragraph{Reduction to PhILR.} |
| When the tree $\mathcal{T}$ is strictly binary (every internal node has exactly $k_u = 2$ children), PolyILR reduces to PhILR \citep{silverman2017phylogenetic}. We verify this algebraically. For a binary node $u$ with child clades $C_u^{(1)}$ and $C_u^{(2)}$ of sizes $n_1$ and $n_2$, the Helmert matrix is $H^{(u)} = [1/\sqrt{2}, -1/\sqrt{2}]^\top$. Under the weighted inner product $\langle h, h' \rangle_w = h_1 h'_1 / n_1 + h_2 h'_2 / n_2$, the squared norm is |
| \[ |
| \|H^{(u)}\|_w^2 = \frac{1/2}{n_1} + \frac{1/2}{n_2} = \frac{n_1 + n_2}{2n_1 n_2}. |
| \] |
| Applying Gram-Schmidt under $\langle \cdot, \cdot \rangle_w$ gives $\tilde{H}^{(u)} = [1/\sqrt{2}, -1/\sqrt{2}]^\top \cdot \sqrt{2n_1 n_2 / (n_1 + n_2)}$. After spreading via $v_i = \tilde{H}_r / n_r$: |
| \[ |
| v^{(u)}_i = \begin{cases} |
| +\sqrt{\dfrac{n_2}{n_1(n_1 + n_2)}} & \text{if } i \in C_u^{(1)}, \\[6pt] |
| -\sqrt{\dfrac{n_1}{n_2(n_1 + n_2)}} & \text{if } i \in C_u^{(2)}, \\[6pt] |
| 0 & \text{otherwise}. |
| \end{cases} |
| \] |
| This matches the PhILR balance formula exactly \citep{silverman2017phylogenetic}. Thus PolyILR is a strict generalization of PhILR to arbitrary tree structures, with the binary case recovering the original method. {\color{black} We note that PhILR also supports optional weighting schemes: taxon weights \citep{egozcue2016changing} that modify the simplex metric itself, and branch length weights that scale coordinates. These define a different but well-posed weighted geometry on the simplex \citep{egozcue2016changing}, rather than the standard Aitchison geometry. PolyILR is built on the standard (unweighted) Aitchison geometry to make the construction directly comparable to canonical ILR; integrating weighted-simplex variants is compatible in principle and left to future work.} |
|
|
|
|
| |
