Why Repeat a Sparse Network Fit?
A sparse network estimator returns a set of selected edges, but that set can depend on which observations happen to be used. In multi-omics data, this matters because the number of candidate edges may be large relative to the number of participants, and correlated features can make several competing edges plausible. Repeating the same fitting procedure on subsamples asks a focused question: which edges are selected consistently when the observed participants change?
Stability selection combines repeated subsampling with a sparse base selector, such as a penalized network-fitting procedure. It is a way to summarize persistence, not a claim that a selected edge is true, causal, or free of bias. Its threshold also has a specific theoretical interpretation: the classical false-selection bound concerns the population stable set defined by selection probabilities, not automatically the set produced by a finite number of subsamples.
How the Procedure Is Defined
Before fitting, specify the candidate edges, the base selector, the subsampling scheme, and the threshold. For an undirected network, an edge is an unordered pair of nodes; the fitting and any required symmetrization rule must be applied consistently in every replicate. In a multilayer network, the candidate set can include within-layer and cross-layer edges, provided each edge is represented and counted consistently.
A common design draws subsamples of a fixed fraction of the observations, often half, and applies the same penalized fitting rule to each one. The penalty value may be fixed in advance or chosen by a prespecified rule within each subsample. Whichever choice is made, the full rule—including tuning and edge symmetrization—defines the base selector. Changing that rule across replicates changes what the selection frequencies describe.
Define \(\mathcal E\) and \(p=|\mathcal E|\) before counting selected edges. Use the same candidate universe in every fit.
Draw \(B\) subsamples and apply the prespecified fitting and tuning rule to each one, recording \(\hat S_b\).
For each candidate edge, compute \(\hat\pi_e\), then report edges with \(\hat\pi_e\geq\pi_{\mathrm{thr}}\), along with the threshold and \(B\).
The threshold is a cutoff on a selection probability or its estimate, not a \(p\)-value cutoff. For example, \(\pi_{\mathrm{thr}}=0.8\) means that a population-stable edge is selected in at least 80% of subsamples under the specified procedure. It does not mean an 80% probability that the edge is real.
Worked Example: Calculating Empirical Edge Frequencies
Suppose a hypothetical study has six candidate edges, and a penalized network fit is repeated on \(B=20\) subsamples. Edge \(e_1\) appears in 18 fitted networks, \(e_2\) in 16, and \(e_3\) in 11. With threshold \(\pi_{\mathrm{thr}}=0.8\), calculate the frequencies and identify the empirical stable edges.
For \(e_1\), \(\hat\pi_{e_1}=18/20=0.90\). For \(e_2\), \(\hat\pi_{e_2}=16/20=0.80\). For \(e_3\), \(\hat\pi_{e_3}=11/20=0.55\). The threshold is inclusive, so both \(e_1\) and \(e_2\) meet it; \(e_3\) does not. The other three edges are assessed by the same calculation.
This reports persistence under these 20 fitted subsamples. It does not establish that the two selected edges belong to the true network, nor does it by itself provide a false-selection guarantee for this finite empirical set.
The Population Bound and Its Justification
The classical stability-selection result gives a bound on the expected number \(V\) of null edges in the population stable set. Here a null edge means an edge absent from the target network under the scientific model being considered. The bound uses \(p\), the total number of candidate edges, and \(q\), an upper bound on the expected number of edges selected by one base fit. It is a statement about repeated draws from the subsampling procedure, not a guarantee that any particular selected edge is null or non-null.
The assumptions are substantive. In particular, a null edge must not be systematically favored by the selector relative to the stated \(q/p\) benchmark. Exchangeability means the null candidates are treated symmetrically by the selection mechanism; it can be implausible when some edges have different measurement quality, missingness, or prior weighting. The bound is not valid merely because a sparse penalty was used.
The short argument has two parts. First, if an edge has population selection probability at least \(\pi_{\mathrm{thr}}\), its probability of appearing in both of two independent fits is at least \(2\pi_{\mathrm{thr}}-1\). This follows because the probability it is absent from at least one fit is at most the sum of the two absence probabilities, which is at most \(2(1-\pi_{\mathrm{thr}})\). Therefore the probability of appearing in both fits is at least \(1-2(1-\pi_{\mathrm{thr}})=2\pi_{\mathrm{thr}}-1\).
Second, write \(\pi_e=P(e\in\hat S)\). For null edges, the stated condition gives \(\pi_e\leq q/p\), and the expected selected-set size gives \(\sum_{e\in\mathcal N}\pi_e\leq q\). Independence of the two fits means the expected number of null edges selected in both is \(\sum_{e\in\mathcal N}\pi_e^2\). Thus
Each null edge in the population stable set contributes at least \(2\pi_{\mathrm{thr}}-1\) to the expected overlap. Hence \((2\pi_{\mathrm{thr}}-1)E[V]\leq q^2/p\). Dividing by the positive quantity \(2\pi_{\mathrm{thr}}-1\) gives the stated result. The condition \(\pi_{\mathrm{thr}}>1/2\) is essential for this argument to yield a finite positive bound.
Worked Example: Interpreting a Population Bound
Consider a hypothetical network analysis with \(p=1000\) candidate edges. Suppose the base selector has expected size at most \(q=20\), and choose \(\pi_{\mathrm{thr}}=0.8\). Under the theorem’s assumptions, calculate the upper bound on the expected number of null edges in the population stable set.
Substitute into the bound:
The conclusion is that, under the stated assumptions, the expected number of null edges in the population stable set is at most about 0.667. This is an expectation bound, not a guarantee that every fitted network contains fewer than one false edge. It also does not apply automatically to the empirical stable set computed from a finite \(B\).
Finite Subsamples: Estimation Is Not the Population Result
In practice, \(\pi_e\) is unknown and \(\hat\pi_e\) is calculated from only \(B\) fits. Even when the repeated fits are generated according to the intended subsampling mechanism, \(\hat\pi_e\) varies around \(\pi_e\). An edge with a population probability below the threshold can cross the empirical threshold by chance. Consequently, the classical population bound cannot simply be quoted as a bound for \(E[|\hat{\mathcal S}_{\pi_{\mathrm{thr}}}\cap\mathcal N|]\). A finite number of subsamples estimates the population stable set; thresholding those estimates does not inherit the theorem automatically.
Worked Example: A One-Subsample Counterexample
Consider one null candidate edge, so \(p=1\). Suppose a base fit selects it with probability \(0.5\), giving expected selected-set size \(q=0.5\). The null candidate is exchangeable (there is only one candidate) and its selection probability equals \(q/p=0.5\), so it meets the stated marginal condition. Set \(B=1\) and \(\pi_{\mathrm{thr}}=0.8\).
The population selection probability is \(\pi_e=0.5\), so the population stable set is empty and \(V=0\). The population theorem’s bound is \(0.5^2/\{(2(0.8)-1)(1)\}=0.25/0.6\approx0.417\), which is consistent with \(E[V]=0\).
With only one fit, however, the empirical frequency is either 0 or 1. The empirical stable set contains this null edge whenever it is selected, an event with probability 0.5. Thus the expected number of null edges in the empirical stable set is 0.5, which exceeds 0.417. This example shows why the population theorem cannot be transferred to finite-\(B\) empirical thresholding without an additional Monte Carlo adjustment or procedure.
Increasing \(B\) generally reduces Monte Carlo variation in the estimated frequencies, but it does not repair a misspecified base model, an unsuitable candidate universe, or a failure of the theorem’s assumptions. When independent replicate subsamples are used, a rough Monte Carlo standard error for one frequency is \(\sqrt{\hat\pi_e(1-\hat\pi_e)/B}\). This describes simulation variability in the estimated frequency under that setup; it is not a confidence statement about whether the edge is true. If the subsampling draws are dependent, the independent-binomial calculation is not justified as written.
Diagnostics, Alternatives, and Limitations
Interpret frequencies alongside diagnostics that reveal whether the resampling design and fitting pipeline behave as intended. Check that the candidate-edge set and node definitions remain fixed, that each replicate used the same preprocessing and selection rule, and that the number of selected edges is plausible across fits. Report \(B\), subsample size, threshold, tuning rule, and the distribution of selected-set sizes. Frequencies concentrated just above the threshold deserve particular caution: a small change in the subsamples or the fitting rule could move them below it.
Correlated molecular features can produce groups of substitutable edges. In that setting, one edge may be selected in some subsamples while a correlated alternative is selected in others. Low frequency for an individual edge need not mean that the associated biological signal is absent; it can indicate uncertainty about which edge represents that signal. Conversely, a consistently selected edge can reflect systematic confounding, measurement artifacts, or model misspecification. Selection frequency measures repeatability under the specified procedure, not biological validity.
| Approach | What it summarizes | Important distinction |
|---|---|---|
| One penalized fit | Edges selected in one data set under one fitting run | Does not reveal how much selection changes across subsamples |
| Stability selection | Persistence of edge selection across repeated subsamples | Thresholded frequencies are not \(p\)-values, and finite-\(B\) thresholding has no automatic classical bound |
| Bootstrap edge summaries | Variation in fitted edges across bootstrap resamples, as in edge uncertainty analysis | The resampling scheme and summary answer a related but not identical question; neither converts frequency into truth probability |
Stability selection also has practical limitations. A very high threshold can discard genuine but weak or sample-sensitive edges; a low threshold may retain many unstable edges. If the penalty is tuned independently in each subsample, frequencies reflect both data changes and tuning changes, which may be appropriate but should be stated. Finally, the classical expected-false-selection bound depends on its assumptions and on the population definition. It is not a substitute for checking model fit or evaluating sensitivity to reasonable analysis choices.
Check Your Understanding
Answer each question, then compare your reasoning with the solutions below.
- In 50 subsample fits, an edge is selected 41 times. What is its empirical frequency, and does it meet a threshold of 0.85?
- Why must the classical bound’s \(\pi_{\mathrm{thr}}\) exceed one half?
- For \(p=500\), \(q=10\), and \(\pi_{\mathrm{thr}}=0.75\), calculate the population bound under the theorem’s assumptions.
- Does a frequency of 0.9 mean there is a 90% probability that an edge is true? Explain.
Solutions. (1) \(\hat\pi_e=41/50=0.82\), so it does not meet 0.85. (2) The derivation uses the positive lower bound \(2\pi_{\mathrm{thr}}-1\) on the two-fit overlap probability; this is positive only when \(\pi_{\mathrm{thr}}>0.5\). (3) \(E[V]\leq 10^2/\{(2(0.75)-1)(500)\}=100/(0.5\cdot500)=0.4\), an expected-false-edge bound for the population stable set, conditional on the assumptions. (4) No. It means the edge was selected in 90% of the relevant subsamples, or estimates that population selection probability; it is not a probability that the edge is true.