Why Stability Selection Is Used
Sparse graph estimators can change their selected edges when a few observations change. Stability selection makes this sensitivity visible: repeatedly fit a specified edge-selection procedure to subsamples, record how often each edge is selected, and retain edges whose selection frequency is high enough. The result is a way to prioritize reproducible edges, not a replacement for specifying the estimator, tuning rule, and sampling design.
For a graph with \(p\) vertices, there are \(M=p(p-1)/2\) possible undirected edges. Write \(\mathcal E\) for this candidate set. A base procedure might be a graphical lasso fit or a symmetrized nodewise regression procedure. Its selected edge set depends on the data supplied to it and, in general, on its tuning parameter.
In computation, the frequency is estimated using \(B\) subsamples: \(\widehat\Pi_e(D)\) is approximated by \(B^{-1}\sum_{b=1}^B \mathbf 1\{e\in\widehat S(I_b)\}\). A frequency is therefore tied to the whole procedure: subsample size, fitting method, tuning rule, and any rule for converting directed neighborhood selections into undirected edges. Changing one of these changes the quantity being measured.
Choosing and Applying a Frequency Threshold
A threshold above one half is common when using a stability-selection error bound. It means an edge must be selected in a strict majority of the subsamples; a threshold such as \(0.9\) imposes a much stronger reproducibility requirement. The threshold does not turn the frequency into a \(p\)-value or a posterior probability that the edge is real. It is a cutoff applied to the selection behavior of a particular procedure.
Worked Example: Thresholding Edge Frequencies
Suppose a four-vertex graph has six candidate edges, and 100 subsamples produce these selection counts:
| Edge | Selections | Frequency |
|---|---|---|
| \((1,2)\) | 96 | 0.96 |
| \((1,3)\) | 84 | 0.84 |
| \((1,4)\) | 53 | 0.53 |
| \((2,3)\) | 47 | 0.47 |
| \((2,4)\) | 15 | 0.15 |
| \((3,4)\) | 5 | 0.05 |
At \(\tau=0.8\), the stable set is \(\{(1,2),(1,3)\}\), because \(0.96\ge0.8\) and \(0.84\ge0.8\), while every other frequency is below \(0.8\). At \(\tau=0.5\), edge \((1,4)\) is also retained. Thus the threshold changes graph size directly; it does not change the underlying fitted frequencies.
What Error Control Can Be Claimed?
Let \(S\subseteq\mathcal E\) be the true edge set, and let \(\mathcal N=\mathcal E\setminus S\) denote the set of null edges. The number of false stable edges is \(V=|\widehat S_{\mathrm{stab}}(\tau)\cap\mathcal N|\). An expected bound on \(V\) is a bound on the expected number of false inclusions (often called PFER control). It is not, by itself, a bound on the probability of any false edge, nor does it control the false discovery proportion in every realized graph.
First there is a deterministic inequality. It requires no exchangeability assumption. For \(\tau>1/2\), each null edge with frequency at least \(\tau\) contributes at least \(2\tau-1\) to the sum of squared null frequencies:
Proof. For \(x\in[0,1]\), \(x^2-(2x-1)=(1-x)^2\ge0\). If \(x\ge\tau\), then \(x^2\ge2x-1\ge2\tau-1\), so \(1\le x^2/(2\tau-1)\). Apply this with \(x=\widehat\Pi_e(D)\) to each stable null edge. For a null edge that is not stable, its indicator in the count is zero and is also no greater than \(\widehat\Pi_e(D)^2/(2\tau-1)\). Summing these inequalities over \(\mathcal N\) proves the result. \(\square\)
To obtain an expectation bound in terms of the average size of the base model, a further condition is needed. Here is one explicit sufficient version. Let \(D\) be random under the data-generating distribution, and define \(q=E_D E_*[|\widehat S(I)|\mid D]\), the expected number of edges selected by the base procedure on a random subsample. Assume the null frequencies satisfy the second-moment condition \(E_D[\sum_{e\in\mathcal N}\widehat\Pi_e(D)^2]\le q^2/M\). This assumption is stated on the second moments of the frequencies themselves; exchangeability of null edges alone does not establish it.
Proof. Apply the deterministic proposition for each data set and take expectation over \(D\). Since the sum has finitely many terms, $$ E_D[V] \le \frac{1}{2\tau-1}E_D\left[\sum_{e\in\mathcal N}\widehat\Pi_e(D)^2\right] \le \frac{q^2}{(2\tau-1)M}, $$ where the last inequality is precisely the stated second-moment condition. \(\square\)
This is a sufficient MB-type error bound, not a consequence of merely having exchangeable null edges or selecting at most half the null edges on average. Versions of classical stability-selection bounds use specific assumptions on null-selection probabilities. The exact assumption must match the theorem being invoked; a first-moment statement about the expected number of selected nulls cannot be substituted for the second-moment condition above.
Worked Example: Using the Explicit Error Bound
Suppose a graph has \(p=5\) vertices, so \(M=5(4)/2=10\) candidate edges. Let the expected base-model size be \(q=2\), and take \(\tau=0.8\). If the second-moment condition holds, then \(2\tau-1=0.6\), and $$ E[V]\le \frac{2^2}{0.6(10)}=\frac{4}{6}\approx0.667. $$ The result bounds the expected count of false stable edges under the stated condition. It does not say that each fitted graph has fewer than one false edge, and it does not guarantee that the condition holds for a particular data set or tuning scheme.
Why a Weaker Null-Selection Condition Is Not Enough
A tempting argument says that if the base procedure selects no more than half the null edges on average, then the stability-selection bound follows. That reasoning ignores how selection can be concentrated across repeated subsamples. A procedure could select many nulls together in some outcomes and none in others. Its mean number selected may look moderate while the frequencies of many null edges are nevertheless high.
Worked Example: Why the Half-Null Condition Fails
Consider \(M\) candidate edges, all null. Suppose that, conditional on the data, the base procedure selects all \(M\) edges with probability \(1/2\) and selects none with probability \(1/2\), with the same outcome across subsamples. The expected number selected is \(q=M/2\), exactly half the number of null edges. Yet each edge has frequency \(1/2\) when viewed over this random mechanism; if instead the random all-or-none outcome is a data-level outcome shared by subsamples, each realized data set has frequencies either all one or all zero. On the all-selected data outcomes, every edge passes any \(\tau\le1\). Across data sets the expected stable false-edge count is \(M/2\).
For \(\tau=0.99\), the often-quoted expression using only this half-null condition would be $$ \frac{q^2}{(2\tau-1)M} =\frac{(M/2)^2}{0.98M} \approx0.255M, $$ which is less than \(M/2\), so it cannot be justified by that condition. The explicit second-moment condition also fails: the sum of expected squared frequencies is \(M/2\), while \(q^2/M=M/4\). This example shows why the stronger condition cannot be silently replaced by a bound on the expected null count.
A simpler bound is always available when the expected number of base-procedure null selections is known. Since a stable edge has frequency at least \(\tau\), its indicator is no greater than its frequency divided by \(\tau\). Summing and taking expectations gives $$ E[V]\le \frac{1}{\tau}E_D\left[\sum_{e\in\mathcal N}\widehat\Pi_e(D)\right]. $$ This first-moment bound may be weaker, but it needs only the corresponding expected null-selection count. It should not be confused with the sharper second-moment bound.
Sensitivity to Tuning and Subsampling Choices
Stability frequencies are conditional on the procedure used to generate them. If each subsample uses a fixed penalty, the frequencies measure reproducibility at that penalty. If the penalty is reselected on every subsample, they measure reproducibility of the combined fitting-and-tuning rule. These are different procedures, and their frequencies need not agree. The expected base size \(q\) and any null-frequency assumptions must refer to the same rule that generated the stable set.
Worked Example: A Tuning Rule Changes the Stable Graph
Suppose edge \(e\) is selected in 72 of 100 subsamples when every fit uses a fixed penalty \(\lambda_0\), giving frequency \(0.72\). If the penalty is chosen separately in each subsample by a validation rule, the edge is selected in 91 of 100 fits, giving frequency \(0.91\). With threshold \(\tau=0.8\), the fixed-penalty analysis excludes \(e\), while the retuned analysis includes it. Neither frequency is an error: they answer different questions about different selection procedures.
Likewise, changing from half-samples to smaller subsamples can alter selection rates. Smaller subsamples contain less information and may select a different set of edges. A threshold calibrated for one subsampling scheme should not automatically be carried over to another, especially if an error-bound assumption was justified for the original scheme.
Several practical checks help interpret a stable graph responsibly:
- Report the base estimator, tuning rule, subsample size, number of subsamples, symmetrization rule, and threshold.
- Show how the stable edge count changes over a reasonable range of thresholds, rather than presenting one cutoff as inevitable.
- Distinguish empirical frequency estimates from exact subsampling probabilities; a finite \(B\) introduces Monte Carlo variability.
- Do not interpret high frequency as proof of a true conditional dependence or as calibrated edgewise significance.
- When making a formal error-control claim, state the exact null-selection assumptions and check that their definitions match the implemented procedure.
Check Your Understanding
Use the definitions and conditions in this tutorial to answer the following.
- What does an edge-selection frequency condition on, and which sources of randomness does it average over?
- Why is the deterministic false-edge inequality restricted to \(\tau>1/2\)?
- State the second-moment condition used in the theorem and explain why exchangeability alone does not imply it.
- For \(M=20\), \(q=3\), and \(\tau=0.75\), calculate the theorem's expected-error bound, assuming its condition holds.
- How does choosing a tuning parameter separately within each subsample change the interpretation of the resulting frequencies?