Symmetry Pitfalls In Combining Nodewise Regressions

Why Symmetrizing Nodewise Selections Is a Statistical Choice

A Gaussian graphical model describes an undirected graph: an edge between variables \(i\) and \(j\) represents conditional dependence given the other variables. Nodewise lasso, however, fits one regression for each variable in turn. The regression of \(X_i\) on the remaining variables can select \(j\), while the regression of \(X_j\) on the remaining variables does not select \(i\). Turning these directional selections into an undirected graph therefore requires a rule.

The two common rules are the union rule and the intersection rule. Union retains an edge if either direction selects it; intersection retains it only if both directions select it. This choice affects the balance between false-positive edges and missed true edges. It is not merely a way to tidy up a fitted graph.

Directional Selections and the Population Target

Let \(X=(X_1,\ldots,X_p)^\mathsf{T}\) have a nonsingular multivariate normal distribution with covariance matrix \(\Sigma\) and precision matrix \(\Omega=\Sigma^{-1}\). In nodewise lasso, the regression for node \(i\) uses \(X_i\) as its response and the other variables as predictors. For centered observations, one common form of the fitted problem is

\hat{\beta}^{(i)} \in \arg\min_{b\in\mathbb{R}^{p-1}} \left\{ \frac{1}{2n}\|X_i-X_{-i}b\|_2^2+\lambda_i\|b\|_1 \right\}.

Here \(X_i\) denotes the vector of \(n\) observed values of variable \(i\), and \(X_{-i}\) contains the other variables. Define \(A_{ij}=1\) if the fitted regression for node \(i\) selects variable \(j\), and \(A_{ij}=0\) otherwise. This is a directional indicator: \(A_{ij}\) refers to the regression with response \(i\), whereas \(A_{ji}\) refers to a different regression.

Definition: For an unordered pair \(\{i,j\}\), the union rule selects the edge if \(A_{ij}=1\) or \(A_{ji}=1\). The intersection rule selects the edge if \(A_{ij}=1\) and \(A_{ji}=1\). The true Gaussian graph contains \(\{i,j\}\) exactly when \(\Omega_{ij}\ne 0\).

The population target is symmetric even though the fitted selections need not be. The reason is that the two regression coefficients for a pair have different denominators but the same zero pattern.

Result: If \(X\) is nonsingular multivariate normal, then the population regression coefficient of \(X_j\) in the conditional mean of \(X_i\) given \(X_{-i}\) is \(-\Omega_{ij}/\Omega_{ii}\). Consequently, the population coefficient is nonzero in one direction exactly when it is nonzero in the other, and this occurs exactly when \(\Omega_{ij}\ne 0\).

To derive the coefficient, write the Gaussian density in terms of the precision matrix. Holding all coordinates other than \(x_i\) fixed, the terms in its log density that depend on \(x_i\) are

-\frac{1}{2}\Omega_{ii}(x_i-\mu_i)^2 -(x_i-\mu_i)\sum_{j\ne i}\Omega_{ij}(x_j-\mu_j),

up to terms constant in \(x_i\). Completing the square in \(x_i\) gives the conditional mean

E[X_i\mid X_{-i}] =\mu_i-\frac{1}{\Omega_{ii}}\sum_{j\ne i}\Omega_{ij}(X_j-\mu_j).

Thus the coefficient for \(X_j\) is \(-\Omega_{ij}/\Omega_{ii}\). Since \(\Omega\) is symmetric and its diagonal entries are positive, \(\Omega_{ij}\ne0\) if and only if \(\Omega_{ji}\ne0\); both directional population coefficients are therefore nonzero together. This is a statement about the population model, not a guarantee that two penalized regressions fitted to finite data will make matching selections. \(\square\)

How the Two Rules Change Edge Errors

For each pair, define its true-edge indicator \(T_{ij}=1\{\Omega_{ij}\ne0\}\). A selected edge with \(T_{ij}=0\) is a false positive; an unselected edge with \(T_{ij}=1\) is a missed edge, or false negative. The selection rule determines which directional disagreements become one of these errors.

Truth and directional selections	Union rule	Intersection rule
True edge, both directions selected	Retained	Retained
True edge, exactly one direction selected	Retained	Missed
True edge, neither direction selected	Missed	Missed
Nonedge, both directions selected	False positive	False positive
Nonedge, exactly one direction selected	False positive	Excluded
Nonedge, neither direction selected	Excluded	Excluded

The table reveals the basic trade-off. With a true edge selected in only one direction, union avoids a miss while intersection creates one. With a nonedge selected in only one direction, union creates a false positive while intersection avoids it. If both directions agree, the rules agree too.

Theorem: For any fixed set of directional selections and any fixed true undirected graph, the union-selected edge set contains the intersection-selected edge set. Therefore union has at least as many selected false positives and no more missed edges than intersection.

Proof. For each unordered pair, if intersection selects it, then \(A_{ij}=A_{ji}=1\), so at least one direction is selected and union also selects it. Hence every intersection edge is a union edge. Among true nonedges, every edge selected by intersection is consequently also selected by union, so the number of union false positives cannot be smaller. Among true edges, every edge missed by union is also missed by intersection: if union does not select a true edge, both directional indicators are zero, which also fails the intersection rule. Thus union cannot have more missed edges. \(\square\)

These comparisons are guaranteed for the same directional selections. They do not say which rule has lower total error, because false positives and missed edges may have different costs. Nor do they imply that either rule recovers the true graph well; that depends on how the directional regressions perform.

Worked Example: One-Asided Selections on a Three-Node Graph

Suppose the true model is \(X\sim N_3(0,\Sigma)\) with precision matrix

\Omega= \begin{pmatrix} 2 & -0.5 & 0\\ -0.5 & 2 & -0.4\\ 0 & -0.4 & 2 \end{pmatrix}.

This matrix is positive definite: its leading principal minors are \(2\), \(4-0.25=3.75\), and \(2(3.75)-0.16(2)=7.18\), all positive. The true edges are \(\{1,2\}\) and \(\{2,3\}\), since those and only those off-diagonal precision entries are nonzero. The population regression coefficients are \(\beta_{12}=0.5/2=0.25\), \(\beta_{21}=0.25\), \(\beta_{23}=0.4/2=0.20\), and \(\beta_{32}=0.20\); there is no population edge between 1 and 3.

Now suppose a particular data set and tuning choice give the directional selections \(A_{12}=1\), \(A_{21}=1\), \(A_{23}=1\), \(A_{32}=0\), \(A_{13}=0\), and \(A_{31}=1\). Thus the true edge \(\{2,3\}\) is selected in only one direction, and the nonedge \(\{1,3\}\) is also selected in only one direction.

Union. It retains \(\{1,2\}\), \(\{2,3\}\), and \(\{1,3\}\). It has one false positive, \(\{1,3\}\), and no missed true edges.

Intersection. It retains only \(\{1,2\}\). It has no false positives, but it misses the true edge \(\{2,3\}\). The disagreement is not evidence that the underlying Gaussian graph is directed; it is a difference between finite-sample fitted selections.

Counting the Trade-Off Explicitly

The next example shows how the same basic comparison appears when more than one pair is discordant. The directional selections are treated as the observed output of the fitted nodewise regressions; no claim is made that any particular selection pattern is guaranteed by the model.

Worked Example: A Four-Node Model With False Positives and Misses

Let the true precision matrix be block diagonal, with two blocks

\Omega= \begin{pmatrix} 2 & -0.6 & 0 & 0\\ -0.6 & 2 & 0 & 0\\ 0 & 0 & 2 & -0.5\\ 0 & 0 & -0.5 & 2 \end{pmatrix}.

Each block has positive eigenvalues (respectively \(1.4,2.6\) and \(1.5,2.5\)), so \(\Omega\) is positive definite. The true graph has edges \(\{1,2\}\) and \(\{3,4\}\). Suppose the selected predictor sets are: node 1 selects 2 and 3; node 2 selects neither 1 nor 4; node 3 selects 4; node 4 selects 3 and 2.

For \(\{1,2\}\), only \(A_{12}=1\); for \(\{3,4\}\), both directions are selected. For the nonedges, only \(A_{13}=1\) and \(A_{42}=1\); the pair \(\{2,4\}\) is otherwise unselected. Union therefore selects \(\{1,2\},\{1,3\},\{2,4\},\{3,4\}\): two false positives and no missed true edges. Intersection selects only \(\{3,4\}\): no false positives and one missed true edge, \(\{1,2\}\). The counts follow pair by pair from the rule, rather than from a claim that the two regressions estimate identical coefficients.

Worked Example: Why There Is No Universally Best Rule

Consider a four-node true path with edges \(\{1,2\},\{2,3\},\{3,4\}\), and nonedges \(\{1,3\},\{1,4\},\{2,4\}\). For example, this is the graph of the positive-definite precision matrix with diagonal entries 2, entries \(-0.4\) at pairs \(\{1,2\},\{2,3\},\{3,4\}\), and zeros at all other off-diagonal pairs. Positive definiteness follows from strict diagonal dominance with positive diagonal.

Suppose both directions select \(\{1,2\}\) and the nonedge \(\{1,3\}\); exactly one direction selects \(\{2,3\}\) and the nonedge \(\{1,4\}\); neither direction selects \(\{3,4\}\) or \(\{2,4\}\). Union then has two false positives and one miss. Intersection has one false positive and two misses.

If each false positive costs 2 units and each miss costs 1 unit, the total error cost is \(2(2)+1=5\) for union and \(2(1)+2=4\) for intersection. If each false positive costs 1 unit and each miss costs 2 units, the costs are \(2+2(1)=4\) for union and \(1+2(2)=5\) for intersection. The directional selections and the true graph have not changed; only the relative cost of the two error types has changed. Thus neither rule is optimal for every objective.

Common Pitfalls and Practical Interpretation

A common mistake is to reason that because the true Gaussian graph is undirected, the fitted nodewise selections must be symmetric. The population zero patterns are symmetric, but separate penalized regressions are fitted to different responses and predictor sets. Their finite-sample estimates can differ, so this reasoning incorrectly treats a population property as a finite-sample identity.

A second mistake is to say that union is simply “more accurate” because it finds more true edges, or that intersection is simply “more reliable” because it selects fewer edges. Union cannot have more misses than intersection for the same directional results, but it can have more false positives. Intersection cannot have more false positives than union, but it can have more misses. Accuracy depends on the loss being used and on the purpose of the graph.

Finally, symmetrizing selected supports is not the same operation as averaging two coefficient estimates. The regression coefficients have node-specific denominators, \(-\Omega_{ij}/\Omega_{ii}\) and \(-\Omega_{ij}/\Omega_{jj}\), so even the population coefficients need not be equal in magnitude. The union and intersection rules act on whether a coefficient was selected, not on whether two directional coefficient estimates are numerically identical.

Key takeaway: Union keeps an edge selected in either direction, trading fewer missed edges for potentially more false positives. Intersection requires agreement in both directions, trading fewer false positives for potentially more missed edges. Both rules combine the same directional fits; neither removes the need to state what kind of graph error matters.

Check Your Understanding

Use the definitions and error comparisons above to answer these questions.

For a true edge selected in only one direction, which rule retains it, and which rule misses it?
For a true nonedge selected in only one direction, which rule creates a false positive?
Why can \(A_{ij}\) and \(A_{ji}\) differ in a finite sample even though the Gaussian graph is undirected?
Can union have fewer false positives than intersection for the same directional selections? Explain.
Give a reason why the preferred symmetrization rule can depend on the application.