Hub Swaps for Non-Convex Hub Graphical Models

Biologists often want the "hub genes" of a disease: the few genes in a gene interaction network that connect to many others and may drive the disease state. A common statistical route estimates a sparse inverse covariance matrix (the precision matrix, whose nonzero entries mark genes that remain correlated after accounting for all others) under a penalty designed to favor a few densely connected columns. The best-known version, the Hub Graphical Lasso, keeps that penalty convex so the optimizer always finds the global optimum Learning graphical models with hubs. Convex penalties have a known cost: they shrink large true effects toward zero. They do this most to the strongest hubs, and the damage is worst in the small-sample regime where transcriptomics actually operates. Swapping in a non-convex penalty removes that shrinkage, but it creates many local optima. This note argues that in the hub problem those local optima have a specific, discrete form. Each one corresponds to a different choice of which genes are hubs. A fixed-point optimizer cannot move between them.

We propose to solve a non-convex hub penalty with majorization-minimization. That is an optimizer that repeatedly replaces the hard objective with a simpler upper bound touching it at the current point, so each step is guaranteed not to increase the true objective. We add two ingredients. First, a continuation schedule starts at the convex Hub Graphical Lasso and gradually makes the penalty more non-convex. Second, at each stationary point the method tries cheap, surrogate-scored "hub swap" moves that exchange one hub gene for one non-hub gene, keeping a swap only when the true objective goes down. The question we aim to settle is narrow. In the sample range where hub recovery is statistically hard but not hopeless, does escaping hub-set local optima change which genes get called hubs, and does it beat the simple one-step fix from a convex start?

Core Claim

The objective is the hub-penalized Gaussian likelihood with the Hub Graphical Lasso decomposition $\Theta = Z + V + V^T$. Here $\Theta$ is the $p\times p$ precision matrix, $Z$ is a sparse matrix of ordinary edges, and the columns $V_j$ of $V$ carry hub-specific connections. The convex group norm on the columns of $V$ is replaced by a concave function of each column norm:

$$ \min_{\Theta \succ 0}\; -\log\det\Theta + \mathrm{tr}(S\Theta) + \lambda_1\|Z\|_1 + \lambda_2\sum_{j=1}^{p}\rho_\gamma\big(\|V_j\|_2\big). $$

In this formula $S$ is the sample covariance and $\lambda_1,\lambda_2$ are penalty weights. The function $\rho_\gamma$ is a minimax-concave penalty whose concavity parameter $\gamma$ controls the shape: as $\gamma\to\infty$ it reduces to the plain norm, which recovers Hub Graphical Lasso exactly. Because $\rho_\gamma$ is concave in the column norm, linearizing it at the current iterate gives a majorizer. Minimizing that majorizer is a weighted Hub Graphical Lasso with column weights $w_j=\rho_\gamma'(\|V_j^{k}\|_2)$, which the existing ADMM solver handles directly. This is the standard majorization construction described in Optimization with First-Order Surrogate Functions and analyzed for concave-convex splits in On the Convergence of the Concave-Convex Procedure. That theory guarantees only convergence to a stationary point, and it says nothing about which one.

The claim specific to this proposal concerns where the stationary points sit. Once the weights $w_j$ settle, columns with large norm receive small weights and stay hubs, while columns with small norm receive large weights and stay suppressed. Each stationary point therefore largely locks in a hub set. Moving between hub sets requires a coordinated change that no single majorization step makes. The same combinatorial difficulty is what forced A Scale-Free Structure Prior for Graphical Models with Applications in Functional Genomics to add node-label permutations to its sampler's state. We borrow that insight: explicit label moves escape structural modes. We implement it as deterministic, monotone moves inside the majorization scheme, which avoids that paper's restriction to decomposable graphs and its sampling cost.

Research Program

The algorithm has three nested loops. The outer loop is continuation. It lowers $\gamma$ geometrically from a value where the penalty is effectively convex down to a strongly non-convex target, and warm-starts each stage from the previous solution. This follows the logic of tracking a minimizer from a smoothed problem to the original, as analyzed by A Theoretical Analysis of Optimization by Gaussian Continuation and On Graduated Optimization for Stochastic Non-Convex Problems. Those methods smooth by random perturbation in unconstrained Euclidean space, which would break positive definiteness and sparsity. Our continuation instead moves along a family of penalties and never leaves the positive-definite cone.

The middle loop runs majorization steps to a stationary point. The inner move is the hub swap. We rank non-hub columns by the norm of the gradient of the smooth likelihood with respect to $V_j$, and rank current hubs by their column norm. For the top few candidate pairs, we exchange their weights and run a small number of warm-started ADMM iterations. A swap is accepted only if the true non-convex objective decreases. Descent therefore stays monotone, and the swaps can only improve on the continuation path.

The cost per ADMM iteration is cubic in $p$ because of an eigendecomposition. This is a limitation inherited from Learning graphical models with hubs. We therefore scope the work to $p$ in the hundreds to roughly two thousand genes. We treat whole-genome scaling as out of scope rather than claim it.

Analysis runs alongside the algorithm. For every instance we record how many distinct hub sets plain majorization reaches across random starts. We also record the objective gap between each method's answer and the best objective found by an expensive exhaustive search (many restarts plus swaps). This directly tests the premise that the local optima here are hub-set optima. If restarts all reach the same hub set, the premise is false and the swap move is unnecessary.

The sample-size regime is the organizing variable. Learning Graphs with a Few Hubs shows that neighborhood estimators need samples scaling roughly with the cube of the maximum degree. It also shows that edges touching hubs "flip-flop" across subsamples when samples are short. That paper constrains our design: we do not trust individual hub-incident edges at small $n$. We therefore make the hub set our primary output and score it, rather than edge lists. We predict that the non-convex method helps only in an intermediate window of $n$. At large $n$ the convex shrinkage bias is harmless. At very small $n$ no hub signal survives. Mapping that window is a central deliverable.

Baselines

The naive reference point is graphical lasso followed by ranking genes by degree in the estimated graph. Learning graphical models with hubs argues this suppresses hubs because a uniform penalty treats every edge as equally likely. We also include an even simpler floor that ranks genes by marginal correlation degree, which tells us whether any graphical model is needed at all.

The strongest existing convex method is Hub Graphical Lasso itself. We run it through the same ADMM code and the same tuning-selection rule, with the same grid over $\lambda_1,\lambda_2$ and the same compute budget. On synthetic data we select by held-out likelihood and also report the best-case oracle setting, so a win cannot come from favorable tuning. We found no reported numerical hub- or edge-recovery result for Hub Graphical Lasso on Lacuna; the paper reports gains over graphical lasso qualitatively. Beating it means higher hub-set F-score at matched hub-set size. The improvement must exceed the across-replicate standard error, and it must appear in at least the intermediate-$n$ window.

The strongest number we can anchor against comes from the scale-free prior method. On synthetic scale-free trees with $p=250$ and $n=75$ it reports sensitivity 0.79, against 0.54 for a random-graph prior, and on star networks it reports 0.86 against 0.30 (A Scale-Free Structure Prior for Graphical Models with Applications in Functional Genomics). We will regenerate trees and stars at those sizes and report sensitivity at matched false-positive rate. Two caveats apply. Those graphs are decomposable, which favors that method, so matching 0.79 there counts as parity. Exceeding it on non-decomposable hub-plus-grid and preferential-attachment graphs would count as a win.

We include the subsampling hub detector from Learning Graphs with a Few Hubs, adapted to Gaussian data by using lasso neighborhood regressions. Its sufficiency-based hub calls are a direct competitor for hub-set identification. We give it its published 60 subsamples and report its wall-clock cost next to ours. No reported numerical Hamming error for it is found on Lacuna. We also run JIC-HD Identifying Common Hubs in Multiple Gaussian Graphical Models with a single population, as a fast spectral hub ranker. No reported F-score value for it is found on Lacuna.

The ablations isolate the key ingredient. One-step reweighting runs a single weighted Hub Graphical Lasso, with weights computed from the convex solution. Continuation without swaps tests whether the schedule alone suffices. Swaps without continuation start directly at the target $\gamma$. Random restarts give plain majorization the same total ADMM-iteration budget as the full method. If the full method does not beat one-step reweighting and budget-matched restarts on hub-set recovery, the proposal's central claim fails.

Why not just…?

Why not just do one reweighting step from the convex solution? This is the most serious threat, and it may well work as well as our method. Initializing at Hub Graphical Lasso and reweighting once is cheap, and it already removes much of the shrinkage on columns the convex fit got right. Its weakness is that it inherits the convex fit's hub set. A true hub that convex shrinkage pushed below threshold gets a large weight and stays suppressed. Whether this happens in practice is exactly what the planted-hub experiments measure. We report the fraction of true hubs that are missed by the convex fit and recovered by swaps. If that fraction is near zero across the $n$ sweep, we will conclude that one-step reweighting suffices, and the paper becomes a negative result about local optima in hub models.

Why not just use random restarts? Recursive Decomposition for Nonconvex Optimization - IJCAI-15 Distinguished Paper shows restarts scale badly when the number of local optima grows combinatorially. Hub sets are combinatorial, because choosing $h$ hubs from $p$ genes gives a huge number of possible sets. Random initial matrices also rarely land near the right set. Rather than rely on that argument, we give restarts the identical iteration budget and compare objective gaps and hub-set F-score directly.

Why not just bootstrap the convex method and take stable hubs? Stability over subsamples, in the spirit of Learning Graphs with a Few Hubs, reduces variance but not bias. A consistently over-shrunk hub is consistently missed. We include bootstrapped Hub Graphical Lasso with stability thresholding as an extra baseline. A combination may also be best, and we will test our method with the same bootstrap wrapper.

Proposed Experiments

The synthetic study plants $h\in\{3,10,30\}$ hubs in Gaussian graphical models with $p\in\{250,500,1000\}$. We use three background structures: hub-plus-grid, preferential attachment, and the tree and star families above. The sample size sweeps from $n=25$ to $n=2000$. Metrics are hub-set precision, recall, and F-score; edge F-score restricted to non-hub edges; objective gap to the best-found solution; and wall-clock time. Results are averaged over 50 replicates.

The decisive check is a plot of hub F-score gain over Hub Graphical Lasso against $n$. We expect a positive window. Inside that window, the gain should be explained by hubs recovered through accepted swaps, which we can attribute instance by instance.

The real-data study uses three datasets. The first is the breast cancer ESR1 cohort with 150 genes and $n=49$, where we check whether SLC39A6 is recovered, as the scale-free prior reported. The second is the TCGA lung adenocarcinoma ($n=540$) and squamous ($n=511$) data on $p=426$ genes, where we analyze each subtype alone and check SFTPA1 and SFTPA2, the shared hubs reported by JIC-HD. The third is a subsampling-reproducibility test on those cohorts. For each method we draw subsamples of size 50 to 200 and measure overlap of the hub sets called on disjoint halves. Higher reproducibility at equal hub-set size is the criterion, since real hub truth is unknown.

The scale-limitation test uses The TCGA Meta-Dataset Clinical Benchmark, which has 174 tasks with 50 training samples each. There we ask whether restricting features to genes selected via each method's hubs and their neighbors helps logistic regression. The benchmark reports average accuracy of 71.19% for an MLP, 68.78% for logistic regression, and 66.18% for the majority class. This is a secondary check. Hub selection is not designed for prediction, and we will report a null result here without reinterpreting it.