Multiple Testing For Graph Edges

Why Edge Testing Is a Multiple-Testing Problem

In a Gaussian graphical model, an undirected edge between variables \(i\) and \(j\) corresponds to a nonzero off-diagonal entry of the precision matrix \(\Omega\). Testing one edge addresses the null hypothesis \(H_{ij}:\Omega_{ij}=0\). But with \(d\) variables there are \(m=d(d-1)/2\) possible edges. Testing all of them at once creates a multiple-testing problem: even if every null hypothesis is true, some edges may be declared significant by chance.

Suppose an edgewise inferential procedure supplies a p-value \(\pi_e\) for each edge \(e\). The validity condition used below is that each true-null p-value is super-uniform: \(P(\pi_e\le t)\le t\) for every \(t\in[0,1]\). This is a marginal condition; it does not assert that the p-values are independent. The p-values may come from a valid edgewise testing method, such as one based on debiased estimates or sample splitting. Multiple-testing adjustments do not repair invalid edgewise p-values.

FWER control at level \(\alpha\) means \(P(V\ge1)\le\alpha\) for every configuration of true and false nulls. FDR control at level \(q\) means \(E[\operatorname{FDP}]\le q\). FWER is concerned with making even one false discovery; FDR is concerned with the expected proportion of false discoveries among the rejections. Since \(\operatorname{FDP}\le \mathbf{1}\{V\ge1\}\), FWER control at level \(\alpha\) also implies FDR control at level \(\alpha\), but it can be more conservative when many real edges exist.

Familywise Error Control: Bonferroni and Holm

The Bonferroni procedure rejects edge \(e\) when \(\pi_e\le\alpha/m\). Its guarantee needs only marginal validity, not independence. The proof is the union bound.

To verify the claim, let \(\mathcal{H}_0\) be the set of true nulls, with size \(m_0\le m\). A false rejection occurs only if at least one true-null p-value is at most \(\alpha/m\). Therefore

Holm’s step-down procedure is often less conservative while retaining the same dependence-robust guarantee. Order the p-values as \(\pi_{(1)}\le\cdots\le\pi_{(m)}\). Starting at rank \(k=1\), compare \(\pi_{(k)}\) with \(\alpha/(m-k+1)\). Reject sequentially while the p-value is at most its threshold; at the first failure, stop and retain that hypothesis and all hypotheses ranked after it.

For a proof, suppose Holm rejects at least one true null, and let \(k\) be the rank of the first true null it rejects. Every hypothesis at a rank before \(k\) was rejected and is false, so all \(m_0\) true nulls are among the \(m-k+1\) hypotheses ranked at \(k\) or later. Thus \(m-k+1\ge m_0\). Rejection at rank \(k\) entails \(\pi_{(k)}\le\alpha/(m-k+1)\le\alpha/m_0\). Consequently, at least one true-null p-value is at most \(\alpha/m_0\). By the union bound and super-uniformity, the probability of this event is at most \(m_0(\alpha/m_0)=\alpha\). This proves the claim. \(\square\)

False Discovery Rate and Benjamini–Hochberg

When the aim is to identify a useful collection of candidate edges rather than to rule out every false rejection, FDR control may be more appropriate. The Benjamini–Hochberg (BH) procedure at target level \(q\) orders the p-values and finds \(K=\max\{k:\pi_{(k)}\le qk/m\}\). If this set is empty, it rejects nothing; otherwise it rejects the hypotheses ranked \(1,\ldots,K\). The line \(qk/m\) gives a rank-dependent threshold, so higher-ranked p-values can pass when enough small p-values are present.

Here is a proof. Fix a true null \(i\), and hold all p-values other than \(\pi_i\) fixed. Let \(R_i\) be the number of BH rejections when \(\pi_i\) is set to zero. If the actual procedure rejects \(i\), setting its p-value to zero leaves the rejection count unchanged: the p-value was already among the values below the BH cutoff at that count, and reducing it cannot create a larger admissible rank. Conversely, for this fixed configuration of the other p-values, \(i\) is rejected precisely when \(\pi_i\le qR_i/m\). When \(R_i=0\), its contribution is zero. When \(R_i>0\), the conditional expected contribution of \(i\) to FDP is

The inequality follows because independence leaves the conditional distribution of \(\pi_i\) unchanged, and its true-null p-value is super-uniform. Summing the expected contributions over the \(m_0\) true nulls gives \(\operatorname{FDR}\le m_0q/m\). \(\square\)

Independence is sufficient, but edge p-values are often dependent. Edges can share a node, and all edge statistics may use the same observations. A sample split can separate estimation from inference, but it does not by itself make the different edgewise p-values mutually independent. BH also controls FDR under certain positive dependence conditions, commonly formulated as positive regression dependence on a subset (PRDS) corresponding to the true nulls. Such a condition must be justified for the joint p-value distribution; it does not follow merely from using a graphical model or from observing positive correlations among variables.

Arbitrary Dependence: Benjamini–Yekutieli

When a dependence condition for BH cannot be supported, the Benjamini–Yekutieli (BY) procedure provides FDR control under arbitrary dependence, provided the true-null p-values are marginally super-uniform. Define the harmonic number \(H_m=\sum_{r=1}^m1/r\). BY uses the BH step-up rule with thresholds \(qk/(mH_m)\) instead of \(qk/m\). Since \(H_m\ge1\), these thresholds are no larger than the BH thresholds. The arbitrary-dependence guarantee is \(\operatorname{FDR}\le (m_0/m)q\le q\); the price of not requiring a joint dependence condition is reduced power, especially for large \(m\).

What Dependence Changes

Dependence matters in two different ways. First, it can change the probability of particular patterns of rejections, so an argument that multiplies probabilities as if edge p-values were independent may be wrong. Second, it determines which procedure’s guarantee can be invoked: Bonferroni and Holm need only valid marginal p-values for FWER control; standard BH requires independence or a suitable positive-dependence condition for its stated FDR guarantee; BY tolerates arbitrary dependence but is more conservative.

For a simple illustration, imagine two true-null edge tests with perfectly dependent p-values \(\pi_1=\pi_2=U\), where \(U\) is uniform on \([0,1]\). At level \(q=0.05\), BH rejects both if \(U\le0.05\) and rejects neither otherwise, so its FDR is \(0.05\) in this particular dependence configuration: when it rejects, both rejections are false and the FDP is 1. This calculation does not establish general BH validity under arbitrary dependence. It shows that the rejection events move together, and that a dependence pattern must be considered rather than silently replaced by independence.

The family of hypotheses should also be defined before interpreting the adjustment. Testing all \(d(d-1)/2\) possible edges is different from testing only edges selected after looking at the same data. If screening or tuning determines which edges enter the family, ordinary adjusted p-values may not account for that selection. In addition, a test of \(\Omega_{ij}=0\) concerns a conditional association in the specified model, not necessarily a marginal association or a causal effect.

Choosing and Reporting a Procedure

A frequent mistake is to assume that BH is automatically valid because it is widely used, or to assume that sample splitting makes all edge tests independent. Neither conclusion follows. The correction is to separate marginal p-value validity from joint dependence assumptions, then select a procedure whose guarantee matches what is actually established. When a strong familywise guarantee is required, Holm can improve on Bonferroni without needing independence. When the goal is FDR control and dependence is unknown, BY is a principled alternative, with its conservatism made explicit.