Clade Exchangeability: Choosing Which Microbial Symmetries to Build In

Machine learning on 16S rRNA sequencing data has a sample-size problem. 16S sequencing reads a short, evolving stretch of a bacterial gene, and the result is a table of how many reads came from each of thousands of bacterial variants in each stool or tissue sample. These tables have thousands of columns but only a few hundred patients. Models that can fit complex patterns overfit, and on the best-run benchmark in this area, regularized logistic regression is within about 0.015 AUROC of random forests. Research on building symmetries into networks points to a remedy. If the true prediction rule is unchanged by some group of input transformations, building that invariance into the model removes whole directions of the hypothesis space, and the variance saved is largest when data are scarce. The difficulty is that the symmetries of 16S data are neither Euclidean nor exact. They must be chosen, and a wrong choice introduces bias.

We propose a specific, testable symmetry for these data. Very closely related bacterial variants, such as the sequence variants inside one genus, are often close to interchangeable in their effect on a host phenotype. We call this approximate property clade exchangeability: permuting abundances among the leaves of a small branch of the evolutionary tree should barely change the prediction. This symmetry is broken higher up the tree, at a scale we can estimate. The work has two parts. The first is a data-driven rule, taken from the bias–variance decomposition of equivariant least squares, for deciding which clades to treat as exchangeable given the sample size. The second is a set of models that are exactly invariant to the chosen within-clade permutations. Unlike collapsing counts to the genus level, these models can still read within-clade structure such as evenness and variant richness.

Core Claim

Invariance to within-clade permutation is the symmetry that 16S prediction actually has, and it holds only approximately. Adopting it for a set of clades $C$ removes variance and adds bias. Both terms can be estimated from the tree and a pilot fit, so the best set of clades to treat as exchangeable should shrink toward the leaves as the sample size $n$ grows. We make three falsifiable predictions. First, a symmetry chosen by this rule beats both flat models and fixed taxonomic-rank aggregation, and beats them most clearly at small $n$. Second, models invariant within clades beat aggregation because within-clade diversity carries signal. Third, the sample size at which a clade should stop being collapsed is predicted by the bias–variance ledger, not merely found by trial and error.

Why this symmetry, and not tree automorphisms

The obvious idea at this intersection is to make a network equivariant to phylogenetic tree automorphisms, meaning rotations of the cladogram. For a labeled abundance vector this is mostly an illusion. Each column is a named organism, and swapping two sister taxa changes the biology. The ordering of columns is arbitrary, but flat models already handle that because the columns are labeled. Reordering is therefore a symmetry of how the data are stored, not of the function being learned.

The closest existing work confirms that symmetry-aware phylogenetics addresses a different problem. The symmetry-preserving phylogenetic inference network builds descriptors that are invariant to sister-taxon swaps so that it can infer tree topology from 4–5 aligned sequences without permutation augmentation. It reaches about 60% accuracy under extreme long-branch attraction, where standard methods score 0%. Its accuracy drops to 0.72 at 5 taxa, against 0.94 for maximum likelihood. That paper infers a tree. We take the tree as given and ask which permutations of abundances over its leaves a phenotype predictor should ignore. Nothing in that paper operates on sample abundance profiles or host phenotypes.

Research Program

Representation and exact scale invariance. Reads carry only relative information, a constraint emphasized in Counts: an outstanding challenge for log-ratio analysis. Every model therefore works on log-ratio features, which makes predictions exactly invariant to sequencing depth. Zeros are handled with a fixed pseudocount. Sensitivity to the pseudocount is reported, because that paper identifies zeros as the unresolved weak point of log-ratio methods. A reference tree is built by placing each variant's representative sequence onto a SILVA-based phylogeny.

The symmetry group. For a set $C$ of disjoint clades that together cover every leaf of the tree, let $H_C=\prod_{c\in C}\mathrm{Sym}(\mathrm{leaves}(c))$. This group permutes leaves within each chosen clade. For a linear log-contrast model, $H_C$-invariance forces tied coefficients within each clade. That is equivalent to pooling each clade by its log geometric mean, not by its summed counts as genus aggregation does. This distinction is itself tested.

Choosing the clades. The linear case supplies the method. Provably Strict Generalisation Benefit for Equivariant Models shows that the gap between an unconstrained linear predictor and its symmetrized version equals the norm of its anti-symmetric component. In the overdetermined case the expected variance saving scales as $\sigma^2\dim(\mathcal A)/(n-d-1)$, where $\sigma^2$ is the noise variance, $d$ the input dimension, and $\dim(\mathcal A)$ the dimension of the part the symmetry removes. For a single clade $c$ with $m_c$ leaves, tying coefficients removes $m_c-1$ dimensions. If the true function is only approximately invariant, symmetrizing also costs a bias equal to the within-clade heterogeneity of the true coefficients. We collapse clade $c$ when

$$\hat B_c < \hat\sigma^2 \frac{m_c-1}{n_{\text{eff}}},$$

where $\hat B_c$ is the squared deviation of pilot ridge coefficients from their clade mean, estimated on held-in folds with a split-sample correction, and $n_{\text{eff}}$ is the effective degrees of freedom left by the ridge fit. We need $n_{\text{eff}}$ because Elesedy's exact formula assumes more samples than features ($n>d+1$) and exact symmetry, and neither holds here. The rule is applied bottom-up by dynamic programming over the tree, which avoids cross-validating over the exponentially many possible cuts. We treat the rule as a heuristic whose calibration is itself an experiment. The idea of adapting the symmetry subgroup to the data follows the logic of Any-Subgroup Equivariant Networks via Symmetry Breaking. The difference is that we select the subgroup with an explicit estimate of cost against benefit.

Invariant nonlinear models. Tying coefficients is where aggregation stops. An $H_C$-invariant nonlinear model can also use any symmetric function of the multiset of variant abundances inside a clade, such as the dominant variant's share, evenness, or the count of variants present. We build two such models.

The first is an invariant kernel machine: an RBF kernel applied to within-clade sorted log-ratio vectors, averaged over the finite group. For kernel regression, The Exact Sample Complexity Gain from Invariances for Kernel Regression shows that exact invariance to a finite group multiplies the effective sample size by the group order. Our symmetry is approximate and our input space is discrete, so we test that gain empirically rather than assume it.

The second is a small permutation-invariant set network applied per clade, with shared per-leaf functions in the style of FS-KAN. A second layer combines the clade summaries with the tree's structure. The kernel machine is the primary nonlinear model, because a support vector machine with an RBF kernel is already a benchmarked baseline on these data. The set network is secondary, given the evidence that deep capacity rarely pays off at $n\approx 500$.

Synthetic calibration. We simulate logistic phenotypes on the real Baxter tree and real abundance profiles. Coefficients are drawn by Brownian motion on the tree, and a signal-conservation parameter controls how exchangeable sister variants truly are. This isolates whether the rule's predicted crossover sample sizes match the observed ones.

Baselines

The naive reference point is a classifier that ignores the microbiome, with AUROC 0.5. A second naive reference is $L_2$ logistic regression on raw relative abundances, exactly as in A Framework for Effective Application of Machine Learning to Microbiome-Based Classification Problems. On the Baxter screen-relevant-neoplasia cohort (490 stool samples), that paper reports a median AUROC of 0.680 over 100 splits, with 12 minutes of training.

The strongest reported competitor on 16S data is the random forest from the same paper, at median AUROC 0.695 over 83.2 hours. It is the strongest because it captures interactions without any prior, and it set the benchmark's best number. The support vector machine with an RBF kernel from that paper is the direct non-invariant counterpart of our invariant kernel.

We reproduce all of these through the Topçuoğlu protocol. That means the same 100 splits of 80% training and 20% testing, the same preprocessing, inner cross-validation for hyperparameters, and an equal budget of hyperparameter configurations for every method, including ours. Our clade rule is fitted strictly inside each training fold.

The ablations isolate the key ingredient. The first is the same log-ratio features with no symmetry, which tests the symmetry itself. The second is genus-level and family-level aggregation, by both summed counts and geometric-mean pooling, each followed by $L_2$ logistic regression. The third is a cut chosen by cross-validating over fixed taxonomic ranks, which tests whether our rule adds anything over simple rank selection. The fourth is random sister-swap augmentation of a flat model, which tests hard constraint against augmentation. The fifth is our invariant kernel with within-clade structure replaced by clade means, which tests whether within-clade diversity matters.

Beating the field means a median AUROC above 0.695 on the full Baxter cohort, with a paired per-split win rate clearly above one half over random forest. More important, it means a larger margin at subsampled training sizes of 50, 100, and 200. The secondary cohorts give weaker references. For the Nakatsu mucosal cohort (Gut mucosal microbiome across stages of colorectal carcinogenesis), no reported classification result was found on Lacuna, because that paper reports metacommunity structure, not AUROC. On the metagenomic MetaHit IBD data, the feature-selection study reports a random forest AUC of 0.93 with 14 species and an external accuracy of 0.86 on PRJEB1220. We use these only as a taxonomy-tree transfer check, since they are not 16S data.

Why not just…?

Why not just use $L_2$ logistic regression? It is the model to beat. Topçuoğlu et al. found that it nearly matches random forest and that disease signal is spread thinly across many taxa. Spread-out signal is exactly the case where pooling coefficients within clades should reduce variance without losing much, so our linear model is regularized logistic regression with a better-chosen constraint, not a replacement for it. If our clade-exchangeable linear model does not beat plain $L_2$ logistic regression at small subsampled $n$, the central claim fails.

Why not just aggregate to genus? This is the most serious threat, because genus-level summing is itself a within-genus invariance. Our proposal differs from it in three testable ways. It pools by geometric mean rather than by sum. It chooses the clade level locally from data rather than fixing one rank for the whole tree. It keeps within-clade structure in the nonlinear models. Each difference has its own ablation. If CV-chosen rank aggregation matches our rule at every $n$, we will report that the rule's value is only interpretive.

Why not just use random forests or feature selection? Random forests are the best reported 16S baseline, but they cost 83.2 hours under the benchmark protocol and gain little over linear models. Feature selection reached AUC 0.93 on IBD, but by discarding over 99% of taxa. That makes it fragile to cohort shift, which the external-cohort check measures directly. Both remain in the comparison under matched tuning budgets.

Why not just augment with sister swaps? Augmentation only approximates the invariance and must pass through an exponentially large group. The phylogenetic inference network needed only 8% of the training time of its permutation-augmented predecessor. The kernel theory also argues that hard invariance changes the problem's effective size in ways sampling transformations does not. We test this directly with an augmented flat model given the same compute.

Proposed Experiments

The first decisive check is calibration. On the synthetic phenotypes, we test whether the rule's predicted collapse or no-collapse decision for each clade, and its predicted crossover $n$, match the empirically best decision across conservation levels. A clear mismatch means the Elesedy-derived ledger does not transfer to regularized logistic regression with more features than samples.

The second is learning curves on Baxter. We train on subsamples of 50 to 392 training samples, repeated 100 times, and plot the AUROC gap over plain $L_2$ logistic regression and random forest. The theory predicts that the gap shrinks with $n$ and that the selected clades move toward the leaves.

The third is the within-clade-structure ablation. It asks whether the invariant kernel beats the same model restricted to clade means. It also asks whether the learned clade summaries correspond to interpretable quantities such as variant evenness in Fusobacterium or Parvimonas, the oral taxa Nakatsu et al. linked to early dysbiosis.

The fourth is transfer. We train on Baxter, apply the selected clades, refit on Nakatsu, and ask whether the clades chosen in one cohort are more stable across cohorts than features chosen by feature selection. We report all outcomes, including a null result showing that phylogenetic symmetry adds nothing beyond careful linear regularization.