\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$.
% via the clade supports of its columns.
\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{Identifying clades via value patterns:} Each column $v^{(u,m)}$ is \emph{piecewise constant} on the child clades: for all leaves $i, i' \in C_u^{(r)}$, we have $v^{(u,m)}_i = v^{(u,m)}_{i'} = \tilde{H}^{(u)}_{r,m}/n_r$. This structure allows identification of clades from $V$ as follows. For any support $S$ in $V$, let $J(S) = \{j : \mathrm{supp}(v_j) \subseteq S\}$ be the columns supported within $S$. Here, we restrict $V$ to rows $S$ and columns $J(S)$, and partition the rows by identical row-vectors. If $S$ is a clade of some node $u$, this partition recovers the child clades $\{C_u^{(r)}\}$. If $S$ is merely a prefix union (not a clade), the induced partition will be inconsistent with a valid tree structure. Thus the set of clades is identifiable from $V$.

\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{Tree from clades:} A rooted tree with labeled leaves is uniquely determined by its clades via inclusion: node $u'$ is a child of $u$ iff the clade of $u'$ is a maximal proper subset of the clade of $u$; leaves correspond to singleton clades. Thus $T$ is recoverable from $V$.

\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.}


% We note that PhILR also supports optional weighting schemes: taxon weights \citep{egozcue2016changing} that modify the simplex metric itself and thus break isometry to the standard Aitchison geometry, and branch length weights, which scale coordinates but similarly disrupt the geometric correspondence. In contrast, PolyILR prioritizes a canonical decomposition of the standard Aitchison simplex with full geometry preservation and tree topology alignment, as discussed in Section~\ref{sec:conclusion}.