Uniformly most powerful unbiased test for conditional
independence in Gaussian graphical model

arXiv:1610.00316v1 [math.ST] 2 Oct 2016

Koldanov Petr 1 , Koldanov Alexander, Kalyagin Valeriy; Pardalos Panos
National Research University Higher School of Economics, Laboratory of Algorithms and
Technologies for Network Analysis, Rodionova 136, Nizhny Novgorod, Russia; Preeminent
Professor in Industrial and Systems Engineering, Director, CAO Industrial and Systems
Engineering, University of Florida, Gainesville

Abstract
Model selection for Gaussian concentration graph is based on multiple testing of
pairwise conditional independence. In practical applications partial correlation
tests are widely used. However it is not known whether partial correlation test
is uniformly most powerful for pairwise conditional independence testing. This
question is answered in the paper. Uniformly most powerful unbiased test of
Neymann structure is obtained. It turns out, that this test can be reduced to
usual partial correlation test. It implies that partial correlation test is uniformly
most powerful unbiased one.
Keywords: Conditional independence, Exponential families, Multivariate
normal distribution, Sample partial correlation test, Tests of Neyman
structure, Uniformly most powerful unbiased tests.

1. Introduction.
Let X = (X1 , X2 , . . . , XN ) be a random vector with multivariate Gaussian distribution.

Concentration graph is defined as follows: nodes of the

graph are associated with random variables X1 , X2 , . . . , XN , edge (i, j) is in5

cluded in the graph iff random variables Xi , Xj are conditionally dependent
[Lauritzen 1996], [Anderson 2003]. Model selection for Gaussian concentration
1 Corresponding

author, pkoldanov@hse.ru

Preprint submitted to Elsevier

October 4, 2016

graph consists of identification of concentration graph from observations. This
problem has a practical importance in biology and genetics [Edwards 2000],
[Drton and Perlman 2004]. Common approach for model selection is based on
10

multiple testing of individual hypotheses of pairwise conditional independence
[Drton and Perlman 2007], [Drton and Perlman 2008].
Conditional independence of Xi , Xj given Xk , k ∈ N (i, j) = {1, 2, . . . , N } \
{i, j} is equivalent to the equation ρi,j•N (i,j) = 0, where ρi,j•N (i,j) is the partial correlation of Xi and Xj given Xk , k ∈ N (i, j). For testing hypothesis

15

ρi,j•N (i,j) = 0 for multivariate normal distributions the test of sample partial
correlation is largely used [Anderson 2003]. At the same time, as far as we know,
there are no results concerning uniformly most powerful unbiased (UMPU) tests
for conditional independence. Such test is of own interest and could improve
multiple testing procedures for model selection. In the present paper we con-

20

struct a uniformly most powerful unbiased test of Neyman structure for testing
pairwise conditional independence. It turns out that this test can be reduced
to the sample partial correlation test. Therefore the sample partial correlation
test is uniformly most powerful unbiased one. This fact has some important
consequences for multiple testing with additive loss function.

25

The paper is organized as follows. Section 2 contains basic definition and
problem statement. In Section 3 a general description of the tests of Neyman
structure is given. In Section 4 the UMPU test for testing pairwise conditional
independence is constructed. In Section 5 it is proved that the UMPU test can
be reduced to the sample partial correlation test.

30

2. Basic notations and problem statement.
Let random vector X = (X1 , X2 , . . . , XN ) have a multivariate normal distribution N (µ, Σ), where µ = (µ1 , µ2 , . . . , µN ) is the vector of means and
Σ = (σi,j ) is the covariance matrix, σi,j = cov(Xi , Xj ), i, j = 1, 2, . . . , N . Let
x(t), t = 1, 2, . . . , n be a sample of the size n from the distribution of X and
si,j =

1 n
Σ (xi (t) − xi )(xj (t) − xj ),
n t=1
2

be the sample covariance between Xi , Xj , where xi = (1/n)
by S = (si,j ) the matrix of sample covariances.

Pn

t=1

xi (t). Denote

The inverse matrix for Σ, Σ−1 = (σ i,j ) is known as the concentration or
precision matrix for the distribution of X. For simplicity we use the notation
35

ρi,j = ρi,j•N (i,j) . The problem of pairwise conditional independence testing has
the form:
hi,j : ρi,j = 0 vs ki,j : ρi,j 6= 0

(1)

According to [Lauritzen 1996] the partial correlation can be calculated as
σ i,j
ρi,j = − √
σ i,i σ j,j
Therefore the problem of pairwise conditional independence testing (1) can be
formulated as
hi,j : σ i,j = 0, vs ki,j : σ i,j 6= 0.

(2)

3. Test of Neyman structure.
40

To construct UMPU test for the problem (2) we use a test of Neyman structure for natural parameters of exponential family [Lehmann and Romano 2005].
Let f (x; θ) be the density of the exponential family:


M
X
f (x; θ) = c(θ)exp 
θj Tj (x) m(x)

(3)

j=1

where c(θ) is a function defined in the parameters space, m(x), Tj (x) are functions defined in the sample space, and Tj (X) are the sufficient statistics for
45

θj , j = 1, . . . , M .
Suppose that hypothesis has the form:
hj : θj = θj0 vs kj : θj 6= θj0 ,
where θj0 is fixed.

3

(4)

The UMPU test for hypotheses (4) is (see [Lehmann and Romano 2005], Ch.
4, theorem 4.4.1):

 0, if c′ (t , . . . , t , t , . . . , t ) < t < c′′ (t , . . . , t , t , . . . , t )
j−1 j+1
M
j
j−1 j+1
M
j 1
j 1
ϕj =
 1,
otherwise
(5)

50

where ti = Ti (x), i = 1, . . . , M . The constants c′j , c′′j are defined from the
equations
Z

c′′
j

c′j

and

f (tj ; θj0 |Ti = ti , i = 1, . . . , M ; i 6= j)dtj = 1 − α

R c′j

t f (tj ; θj0 |Ti = ti , i =
−∞ j
R +∞
+ c′′ tj f (tj ; θj0 |Ti = ti , i
j

=α

R +∞
−∞

(6)

1, . . . , M ; i 6= j)dtj +
= 1, . . . , M ; i 6= j)dtj =

(7)

tj f (tj ; θj0 |Ti = ti , i = 1, . . . , M ; i 6= j)dtj

where f (tj ; θj0 |Ti = ti , i = 1, . . . , M ; i 6= j) is the density of conditional distribution of statistic Tj given Ti = ti , i = 1, 2, . . . , N , i 6= j, and α is the significance
55

level of the test.

4. Uniformly most powerful unbiased test for conditional independence.
Now we construct the UMPU test for testing hypothesis of conditional independence (2). Consider statistics
Sk,l =

1 n
Σ (Xi (t) − Xi )(Xj (t) − Xj ),
n t=1

Joint distribution of statistics Sk,l , k, l = 1, 2, . . . , N , n > N is given by Wishart
density function [Anderson 2003]:
f ({sk,l }) =

P P
[det(σ k,l )]n/2 × [det(sk,l )](n−N −2)/2 × exp[−(1/2) k l sk,l σ k,l ]
2(N n/2) × π N (N −1)/4 × Γ(n/2)Γ((n − 1)/2) · · · Γ((n − N + 1)/2)

if the matrix S = (sk,l ) is positive definite, and f ({sk,l }) = 0 otherwise. It

implies that statistics Sk,l are sufficient statistics for natural parameters σ k,l .

4

Wishart density function can be written as:
f ({sk,l }) = C({σ k,l }) exp[−σ i,j si,j −

1
2

X

(k,l)6=(i,j);(k,l)6=(j,i)

sk,l σ k,l ]m({sk,l })

where
k,l n/2
C({σ k,l }) = c−1
1 [det(σ )]

c1 = 2(N n/2) × π N (N −1)/4 × Γ(n/2)Γ((n − 1)/2) · · · Γ((n − N + 1)/2)
m({sk,l }) = [det(sk,l )](n−N −2)/2
According to (5) the UMPU test for hypothesis (2) has the form:

 0, if c′ ({s }) < s < c′′ ({s }), (k, l) 6= (i, j)
k,l
i,j
k,l
i,j
i,j
ϕi,j ({sk,l }) =
 1, if s ≤ c′ ({s }) or s ≥ c′′ ({s }), (k, l) 6= (i, j)
i,j
k,l
i,j
k,l
i,j
i,j
(8)
where the critical values c′i,j , c′′i,j are defined from the equations (according to
60

(6),(7))
R

]
I∩[c′i,j ;c′′
i,j

R

I

Z

[det(sk,l )](n−N −2)/2 dsi,j

[det(sk,l )](n−N −2)/2 dsi,j

=1−α

(9)

si,j [det(sk,l )](n−N −2)/2 dsi,j +

′ ]
I∩(−∞;c
i,j
Z

+

si,j [det(sk,l )](n−N −2)/2 dsi,j =

(10)

I∩[c′′
;+∞)
i,j

=α

R

I

si,j [det(sk,l )](n−N −2)/2 dsi,j

where I is the interval of values of si,j such that the matrix S = (sk,l ) is positive
definite and α is the significance level of the test.
Let S = (sk,l ) be positive definite (this is true with probability 1 if n > N ).
65

Consider det(sk,l ) as a function of the variable si,j only, when fixing the values
of all others {sk,l }. This determinant is a quadratic polynomial of si,j :
det(sk,l ) = −as2i,j + bsi,j + c

(11)

Let K = (n − N − 2)/2. Denote by x1 , x2 (x1 < x2 ) the roots of the equation

−ax2 + bx + c = 0. One has
Z

f

d

2

K

K K

2K+1

(ax − bx − c) dx = (−1) a (x2 − x1 )
5

Z

d−x1
x2 −x1
f −x1
x2 −x1

uK (1 − u)K du

Therefore the equation (9) takes the form:
Z

c′′ −x1
x2 −x1
c′ −x

1
x2 −x1

uK (1 − u)K du = (1 − α)

or
Γ(2K + 2)
Γ(K + 1)Γ(K + 1)

Z

c′′ −x1
x2 −x1
c′ −x1
x2 −x1

Z

1

uK (1 − u)K du

(12)

uK (1 − u)K du = (1 − α)

(13)

0

It means that conditional distribution of Si,j when all other Sk,l are fixed,
70

Sk,l = sk,l is the beta distribution Be(K + 1, K + 1).
Beta distribution Be(K + 1, K + 1) is symmetric with respect to the point 12 .
Therefore the significance level condition (9) and unbiasedness condition (10)
are satisfied if and only if:
c′ − x1
c′′ − x1
=1−
x2 − x1
x2 − x1
Let q be the
α
2.

α
2 -quantile

of beta distribution Be(K + 1, K + 1), i.e. FBe (q) =

Then thresholds c′ , c′′ are defined by:
c′ = x1 + (x2 − x1 )q

c′′ = x2 − (x2 − x1 )q

(14)

Finally, the UMPU test for testing conditional independence of Xi , Xj has
the form
ϕi,j

75


asi,j − 2b


< 1 − 2q
 0, 2q − 1 < q
b2
+ ac
=
4



1, otherwise

(15)

where a, b, c are defined in (11).

5. Sample partial correlation test.
It is known [Lauritzen 1996] that hypothesis σ i,j = 0 is equivalent to the
hypothesis ρi,j = 0, where ρi,j is the partial correlation between Xi and Xj
given Xk , k ∈ N (i, j) = {1, 2, . . . , N } \ {i, j}:
ρi,j = − √

σ i,j
σ i,i σ j,j
6

−Σi,j
= √
Σi,i Σj,j

where for a given matrix A = (ak,l ) we denote by Ai,j the cofactor of the element
ai,j . Denote by ri,j sample partial correlation
−S i,j
ri,j = √
S i,i S j,j
where S i,j is the cofactor of the element si,j in the matrix S of sample covariances.
Well known sample partial correlation test for testing hypothesis ρi,j = 0
80

has the form [Anderson 2003]:
ϕi,j


 0, |ri,j | ≤ ci,j
=
 1, |ri,j | > c
i,j

(16)

where ci,j is (1 − α/2)-quantile of the distribution with the following density
function
1 Γ(n − N + 1)/2)
(1 − x2 )(n−N −2)/2 ,
f (x) = √
π Γ((n − N )/2)

−1 ≤ x ≤ 1

Note, that in practical applications the following Fisher transformation is applied:
zi,j =



√
1 + ri,j
n
ln
2
1 − ri,j

Under condition ρi,j = 0 statistic Zi,j has asymptotically standard normal
distribution. That is why the following test is largely used in applications
[Drton and Perlman 2004], [Drton and Perlman 2007], [Drton and Perlman 2008]:

 0, |z | ≤ c
i,j
i,j
ϕi,j =
(17)
 1, |z | > c
i,j
i,j

where the constant ci,j is (1 − α/2)-quantile of standard normal distribution.
85

In this section we prove that the UMPU test (15) can be reduced to the
sample partial correlation test (16), and therefore the well known sample partial
correlation test for conditional independence is the UMPU one.
Theorem: Sample partial correlation test (16) is equivalent to UMPU test (15)
for testing hypothesis ρi,j = 0 vs ρi,j 6= 0.

7

90

Proof: it is sufficient to prove that
asi,j − 2b
S i,j
√
= q
b2
S i,i S j,j
+ ac

(18)

4

To prove this equation we introduce some notations. Let A = (ak,l ) be an
(N × N ) symmetric matrix. Fix i < j, i, j = 1, 2, . . . , N . Denote by A(x) the
matrix obtained from A by replacing the elements ai,j and aj,i by x. Denote by
Ai,j (x) the cofactor of the element (i, j) in the matrix A(x). Then the following
95

statement is true
Lemma: One has [detA(x)]′ = −2Ai,j (x).
Proof of the Lemma: one has from the general Laplace decomposition of det A(x)
by two rows i and j:

ai,i
det(A(x)) = det 
x
+

X

k>j

X

k>i,k6=j



det 


det 

x
aj,j

ai,k

aj,j

aj,k


ai,k

x

aj,k

{i,j},{i,j}

A

+



X

k<j,k6=i



x

ai,i



X

 A{i,j},{j,k} +

 A{i,j},{i,k} +

k<i



det 

X

k<l,k,l6=i,j



where A{i,j},{k,l} is the cofactor of the matrix 

det 

ai,k

x

aj,k

aj,j

ai,k

ai,i

aj,k


x

[det(A(x))]′ = −2xA{i,j},{i,j} −
+

X
k<i

ak,i A{i,j},{k,i} −

 A{i,j},{k,i} +

det 

ai,l

aj,k

aj,l

ai,k

ai,l

aj,k

aj,l



 A{i,j},{k,l}



 in the matrix A.

X

aj,k A{i,j},{k,j} +

X

ak,i A{i,j},{k,i} = −2Ai,j (x)

k<j,k6=i

k>i,k6=j

 A{i,j},{k,j} +



ai,k

Taking the derivative of det A(x) one get



X

aj,k A{i,j},{j,k} +

k>j

The last equation follows from the symmetry conditions ak,l = al,k and from
Laplace decompositions of Ai,j (x) by the row j and the column i. Lemma is
proved. Note, that similar result is proved in ([Anderson 2003], Appendix A).
Now we come back to the proof of the theorem. One has det(S(x)) =
−ax2 + bx + c, where a, b, c are the same as in (11). Therefore by Lemma
8

one has [det S(x)]′ = −2ax + b = −2S i,j (x), i.e. S i,j (x) = ax − b/2. Let

x = si,j then asi,j − 2b = S i,j . To prove the theorem it is sufficient to prove that
q
√
√
2
2
S i,i S j,j = b4 + ac. Let x2 = b+ b2a+4ac be the maximum root of equation
q
2
ax2 − bx − c = 0. Then ax2 − 2b = b4 + ac. Consider
−S i,j (x)
ri,j (x) = √
S i,i S j,j
According to Silvester determinant identity one can write :
S {i,j},{i,j} det S(x) = S i,i S j,j − [S i,j (x)]2
Therefore for x = x1 and x = x2 one has
S i,i S j,j − [S i,j (x)]2 = 0
That is for x = x1 and x = x2 one has ri,j (x) = ±1. The equation S i,j (x) =

ax − 2b implies that when x is increasing from x1 to x2 then ri,j (x) is decreasing
√
from 1 to −1. That is ri,j (x2 ) = −1, i.e. ax2 − 2b = S i,i S j,j . Therefore
r
√
b2
i,i
j,j
+ ac
S S =
4
100

The Theorem is proved.
Finally, the UMPU test for testing conditional independence of Xi and Xj
can be written in the following form

 0, 2q − 1 < ri,j < 1 − 2q
ϕi,j =
 1 otherwise

where ri,j is the sample partial correlation, and q is the

distribution

105

(19)
α
2 -quantile

of beta

n−N
Be( n−N
2 , 2 ),

6. Concluding remarks
In general optimality of tests for individual hypotheses testing does not
imply optimality of multiple testing procedures. However if the losses from
false decisions are supposed to be additive then it is possible to prove optimality from decision-theoretic point of view of some multiple testing procedures
9

110

[Lehmann 1957], [Koldanov et al 2013], [Hochberg 1987]. Application of this
approach for Gaussian graphical model selection is a subject of further investigations.
Acknowledgment: The work was conducted at National Research University
Higher School of Economics, Laboratory of Algorithms and Technologies for

115

Network Analysis. Partly supported by RFFI 14-01-00807.

References
References
[Anderson 2003] Anderson T. (2003). An introduction to multivariate statistical
analysis.3-d edition. Wiley-Interscience, New York.
120

[Drton and Perlman 2004] Drton M. Perlman M.(2004). Model selection for
Gaussian concentration graph. Biometrika 91(3), 591–602.
[Drton and Perlman 2007] Drton M. Perlman M.(2007). Multiple Testing and
Error Control in Gaussian Graphical Model Selection. Statistical Science
22(3), 430–449.

125

[Drton and Perlman 2008] Drton M. Perlman M.(2008). A SINful approach to
Gaussian graphical model selection. Journal of Statistical Planning and
Inference 138, 1179–1200.
[Edwards 2000] Edwards D.(2000). Introduction to graphical modeling.
Springer-Verlag New York, Inc.

130

[Lauritzen 1996] Lauritzen S.L. (1996). Graphical models. Oxford university
press.
[Lehmann and Romano 2005] Lehmann E.L. Romano J.P. (2005). Testing statistical hypotheses. 3-d edition. Springer, New York.
[Lehmann 1957] Lehmann E.L. (1957). A theory of some multiple decision prob-

135

lems, I. The Annals of Mathematical Statistics, 1-25.
10

[Koldanov et al 2013] Koldanov A.P., Koldanov P.A., Kalyagin V.A., Pardalos P.M. (2013) Statistical procedures for the market graph construction.
Computational Statistics & Data Analysis 68, 17–29, Elsevier.
[Hochberg 1987] Hochberg, Y., Tamhane, A. Multiple comparison procedures.
140

John Wiley & Sons, Inc. 1987.

11

