Non-Convex Selection for Rank-Based Microbial Networks Under Phylogenetic Collinearity

Microbiome studies built on 16S rRNA gene sequencing (reading one marker gene to count which bacteria are in a sample) routinely try to draw interaction networks. In these networks, two taxa are linked when their abundances stay related after accounting for every other taxon. The best current pipelines handle the awkward properties of these counts well. The counts are relative rather than absolute, they are mostly zeros, and they are heavily skewed. These pipelines still finish with the same step, an L1 (lasso) penalty that decides which links survive. The lasso has a known weakness: it picks the wrong variables when an irrelevant variable is strongly correlated with a relevant one. Closely related bacteria, such as two species in the same genus, are often exactly that kind of correlated pair. Our claim is that the main damage done by the lasso in microbial networks is selection error, not shrunken edge weights. The typical failure is a "sibling swap": the lasso links a taxon to the close relative of its true partner. A non-convex penalty fixes this kind of error. Simply refitting the lasso's chosen links does not.

The proposal has three parts. We build a single symmetric estimator that feeds the zero-robust, rank-based correlation estimate from SPRING into a penalized-likelihood network estimator with a concave penalty. A concave penalty such as MCP or SCAD stops penalizing an edge once it is large. We keep the estimator well-posed by adding an operator-norm bound, which caps the size of the estimated network matrix. We show that the same bound fixes how much concavity can be used while the problem stays convex. Finally, we test whether real 16S data actually falls in the regime where any of this matters.

Core Claim and Mechanism

SPRING models zero-heavy counts as a latent Gaussian variable that is cut off at a detection limit. It estimates Kendall's τ between taxa, maps τ to latent correlations through bridge functions, and selects edges by running a separate lasso regression for each taxon. This last step is Meinshausen–Bühlmann neighborhood selection. Its outputs are not symmetric, so the two directions of each edge are reconciled with an ad hoc AND/OR rule. The rank-based correlation matrix $\hat R$ that SPRING produces is not guaranteed to be positive semidefinite. That is the reason a standard graphical lasso cannot simply be run on it.

Precision Matrix Estimation with Noisy and Missing Data supplies our solver. It handles indefinite covariance inputs by restricting the precision matrix $\Theta$ to $\|\Theta\|_2 \le R$. It then solves the problem with an ADMM algorithm that converges linearly for L1, SCAD and MCP penalties. We solve

$$\hat\Theta = \arg\min_{\Theta \succ 0,\ \|\Theta\|_2 \le R}\ \mathrm{tr}(\hat R\,\Theta) - \log\det\Theta + \sum_{i\neq j}\rho_{\lambda,a}(|\Theta_{ij}|),$$

where $\hat R$ is the SPRING latent correlation matrix and $\rho_{\lambda,a}$ is MCP with threshold $\lambda$ and concavity parameter $a$.

The step that is new connects two results that were not linked before. The Log-Shift Penalty proves that a concave penalty can leave the total objective convex if the likelihood's curvature outweighs the penalty's negative curvature. That proof needs a positive definite sample covariance, which fails here. The operator-norm bound restores the condition differently. The trace term is linear, so an indefinite $\hat R$ adds no curvature. The curvature of $-\log\det\Theta$ in any direction $\Delta$ is at least $\|\Delta\|_F^2/R^2$ on the bounded set. MCP's curvature is $-1/a$ per entry. So the problem stays convex roughly when $a$ exceeds a constant times $R^2$.

This gives a useful and testable tension. When sibling taxa are strongly collinear, the true precision matrix has a large largest eigenvalue, so $R$ must be large. A large $R$ forces $a$ to be large, and the penalty then behaves almost like the lasso. In other words, the convexity guarantee is weakest exactly where non-convexity should help most. The research question is whether the convex-certified regime is enough. If it is not, the alternative is the genuinely non-convex regime, solved by local linear approximation (repeatedly solving weighted lasso problems) started from the L1 solution.

We also address one candidate idea directly and set it aside. The research file suggests that centered log-ratio data, whose rows sum to zero, inherit the "lasso paradox" of Nonconvex Sparse Graph Learning under Laplacian Constrained Graphical Model. That paper shows the L1 penalty yields complete graphs under Laplacian constraints. Its argument depends on off-diagonal entries being sign-constrained. Under that constraint the L1 norm collapses to a function of the diagonal. Centered log-ratio precision matrices have no such sign constraint, so the paradox does not transfer directly. We run a cheap check of this on the synthetic benchmarks: we track graph density as λ grows. We do not build the project on that premise.

Research Program

The first part is diagnostic. On latent correlation matrices estimated by SPRING from the American Gut Project data (6,482 samples) and the HMP body-site data used by PGLasso, we compute irrepresentability constants for the neighborhood of each taxon. To do this, we fit a dense reference network on the full data and treat its strongest edges as a working support. We then ask how often violations involve sibling taxa within the same genus or family.

Aragam et al. prove that MCP achieves exact support recovery without incoherence at sample complexity $\Omega(s\log p)$. Sakata and Xu analyze how lasso bias interacts with the stability of SCAD algorithms. Both motivate the claim, but only for continuous Gaussian designs. The diagnostic tells us whether real 16S data is in the regime those results address. If irrepresentability broadly holds, the selection argument fails and we report that as the result.

The second part is the estimator and its analysis. We implement the constrained ADMM with MCP and SCAD on $\hat R$. We characterize the region of $(R, a)$ where the problem is certified convex. We compare solutions inside that region with local linear approximation solutions outside it. We also borrow the warning from Sakata and Xu that coordinate descent stalls at a phase boundary of the solution landscape. Following that warning, we record how far solutions spread across random restarts as $a$ shrinks, which gives an empirical map of where the landscape becomes rugged.

The third part chooses $R$ from the data, which Fan et al. leave as a manual choice. Our proposal is the smallest $R$ at which the constraint becomes inactive on bootstrap resamples. We test it against an oracle choice of $R$.

Baselines

The naive reference point is the routine analysis pipeline. It adds a pseudo-count of one to every cell, applies the centered log-ratio transform, and runs a graphical lasso. SPRING argues that this pseudo-count distorts covariance structure. This baseline shows how much any principled pipeline gains before penalty choice even enters. We also run SparCC as the marginal-correlation reference. PGLasso reports a Buccal Mucosa ARI of 0.016 for SparCC against 0.194 for PGLasso.

The strongest existing method is SPRING itself, run with its own transform, bridge functions and lasso neighborhood selection, under both AND and OR rules. Every competitor receives the same $\hat R$, the same samples and the same stability-based tuning budget. That budget is a fixed number of subsamples and an equal-size grid over λ, plus $a$ for the non-convex methods so that the extra hyperparameter is paid for. No reported AUPR or Hamming value for SPRING on its synthetic protocol was found on Lacuna, so we reproduce SPRING ourselves. Beating it means a higher AUPR and a lower rate of sibling-swap errors over repeated simulation seeds, with intervals that do not overlap.

On HMP community detection, the strongest reported competitor is PGLasso. PGLasso reports an adjusted Rand index of 0.194 on buccal mucosa, against Humann2 metabolic-pathway ground truth, compared with 0.022 for GLasso. We follow its Louvain clustering and ground-truth protocol. Beating it means exceeding 0.194 on buccal mucosa and matching or exceeding PGLasso on the other four body sites. We also run a phylogenetically weighted version of our estimator, so that we can separate the effect of phylogenetic weights from the effect of concavity.

The ablation that isolates the key ingredient is the same constrained ADMM on the same $\hat R$ with the L1 penalty in place of MCP. Differences between it and our method come from the penalty alone. We also include a positive-semidefinite-projected graphical lasso. This separates the benefit of the operator-norm route from the benefit of the penalty.

Why not just…?

Why not just refit the lasso's chosen edges without a penalty to remove shrinkage bias? Refitting corrects edge magnitudes but cannot correct which edges were chosen. If the lasso linked a taxon to the sibling of its true partner, the refit estimates the wrong edge without bias. We therefore run lasso-plus-refit as a baseline. If it matches our estimator on AUPR and sibling-swap rate, then the problem is magnitude rather than selection, and our core claim is wrong.

Why not just use the adaptive lasso? This is the most serious threat, because one step of local linear approximation is essentially an adaptive lasso. If a single reweighting fixes the sibling swaps, a fully concave penalty adds nothing. We include one-step and fully converged versions under the same tuning budget. The experiment that settles this is the high-collinearity range of the synthetic sweep. The fully concave method should win there if multiple reweighting steps matter, and the two should tie if they do not.

Why not just swap MCP into SPRING's per-taxon regressions? That is the minimal change and needs no new solver. It keeps the heuristic AND/OR rule, and it does not use the likelihood structure that makes convexity certifiable. We run it as a baseline. A joint estimator that only ties this swap would mean the joint formulation contributes interpretability and guarantees but no accuracy, and we would report it that way.

Proposed Experiments

The synthetic study follows the SPRING protocol. It draws zero-inflated counts from a truncated Gaussian copula whose margins match the empirical distributions of real taxa. We add a controlled "sibling" structure: pairs of taxa with latent correlation swept from 0.5 to 0.95, where only one member of each pair carries a true edge. We vary sample size from 50 to 500 at roughly 200 taxa. Metrics are AUPR, Hamming distance, the sibling-swap rate, and relative error on the true edge weights.

The decisive check is a crossover. At low sibling correlation all methods should tie. At high sibling correlation, both the L1-penalty ADMM and lasso-plus-refit should accumulate sibling swaps that MCP avoids. If no such separation appears, the claim is refuted.

On real data, the Vandeputte quantitative cohort (106 subjects) has both relative profiles and absolute counts from cell counting. A good estimator should give similar networks from the two. We score the overlap between the network estimated from relative data and the one estimated from absolute data. The Phascolarctobacterium–Dialister negative association reported by SPRING serves as a sanity anchor. On the American Gut data, we measure how well edges found in subsamples of 100 to 500 samples reproduce in the full-sample network. On HMP, we report adjusted Rand index against PGLasso's protocol.

A final check bears directly on the convexity analysis. We report whether the best-performing $a$ lies inside the certified-convex region. If it lies inside, the method is both accurate and globally solvable. If it lies outside, the accuracy gain comes at the cost of losing the guarantee.