Robust Identi cation of Subgraphs in a Complete Weighted Graph Associated with a Set of Random Variables

Abstract

A class of distribution free multiple decision statistical procedures is proposed for threshold graph identi cation in a complete weighted graph associated with a set of random variables (random variables network). The decision procedures are based on simultaneous application of sign statistics. It is proved that single step, step down Holm and step up Hochberg statistical procedures for threshold graph identi cation are distribution free in sign similarity network in the class of elliptically contoured distributions.

Introduction

Network model of complete weighted graph associated with a set of random variables is useful in biological and nancial applications. Biological applications are mostly related with probabilistic graphical models [ 5 ], weighted correlation networks [ 3 ] and others. Financial applications are related with market network analysis [ 7 ], [ 2 ]. In this paper we consider a model which we call random variables networks. Random variables network is a pair (X; ), where X = (X1; X2; : : : ; XN ) is a random vector and is a measure of association of random variables. For Gaussian graphical model vector X has a multivariate Gaussian distribution and is the partial correlation. For market network model Xi is an attribute of stock i (return, volume, price and at.) and is the Pearson correlation (in most cases). Main goal of network analysis is to identify a network structures containing a key information about network. Popular network structures studied in the literature are concentration graph in Gaussian graphical models, and, minimum spanning tree, planar maximally ltered graph, threshold (market) graph, cliques and independent sets in market network analysis.

Random variable network is as complete weighted graph where the nodes are associated with random variables and weight of edge are given by a measure of association between them. Threshold graph is a subgraph of random variable network. An edge is included in threshold graph iff its weight is larger than a given threshold. According to the choice of measure of association one get different correlation networks and threshold Copyright ⃝c by the paper's authors. Copying permitted for private and academic purposes. In: A. Kononov et al. (eds.): DOOR 2016, Vladivostok, Russia, published at http://ceur-ws.org graphs. Threshold graph identi cation problem is to identify the threshold graph from observations. In this paper we study threshold graph identi cation problem in sign similarity network and compare it with identi cation problem in Pearson correlation network.

On our study of threshold graph identi cation problem we use a multiple decision statistical approach. The decision procedures considered in this paper are based on simultaneous application of sign tests. Three popular multiple statistical procedures are investigated: single step multiple decision procedure, step down Holm multiple testing procedure and step up Hochberg multiple testing procedure. The quality of the procedures is measured by risk function, and in particular FWER (Family Wise Error Rate). Our main result is: considered multiple decision procedures for threshold graph identi cation are robust (distribution free) in sign similarity network in the class of elliptically contoured distributions. Moreover it is shown that these procedures can be adapted for robust threshold graph identi cation in Pearson correlation network. This result gives a theoretical foundations for practical threshold graph identi cation algorithms in the case where the distribution of the vector X is unknown. 2

Basic de nitions and notations

Let X = (X1; X2; : : : ; XN ) be a random vector. Consider a complete weighted graph associated with X. Nodes of the graph are random variables Xi, i = 1; : : : ; N and weight of edge (i; j) is given by some measure of association (Xi; Xj ) between them. One popular measure of association is Pearson correlation iP;j . Pearson correlation generates a Pearson correlation network. In this paper we study a sign similarity network, where S the measure of association is given by the probability of sign coincidence i;j = P ((Xi E(Xi))(Xj E(Xj )) > 0). This measure of association has a simple interpretation and was shown to be appropriate in market network analysis [ 1 ].

In this paper we assume that distribution of the random vector X belong to the class of elliptically contoured distributions (ECD) with density functions: 1 f (x; ; ) = j j 2 gf(x )′ 1(x )g (1) where is positive de nite matrix, g(y) 0. Multivariate Gaussian and Student distributions are a particular cases of ECD.

Threshold graph is constructed as follows: the edge between two vertices i and j is included in the threshold graph, iff i;j > 0 (where 0 is a threshold). For a given threshold 0 the threshold graph is de ned by its adjacency matrix S = (si;j ), where si;j = 0 if i;j 0 and si;j = 1 if i;j > 0, si;i = 0, i; j = 1; 2; : : : ; N .

Let x(t) be a sample of the size n from distribution of the random vector X: x(t) = (x1(t); x2(t); : : : ; xN (t)); t = 1; 2; : : : ; n Consider the set G of all N N symmetric matrices G = (gi;j ) with gi;j 2 f0; 1g, i; j = 1; 2; : : : ; N , gi;i = 0, i = 1; 2; : : : ; N . Matrices G 2 G represent adjacency matrices of all simple undirected graphs with N vertices. Total number of matrices in G equals to L = 2M with M = N (N 1)=2.

Robust Identi cation of Subgraphs

Multiple decision framework

Threshold graph identi cation problem is to identify the threshold graph from observations. The problem can be formulated as a multiple decision problem of selecting one from a set of L hypotheses:

HG : i;j 0; if gi;j = 0; i;j > 0; if gi;j = 1; i ̸= j (2) Multiple decision statistical procedure for threshold graph identi cation is a map from the sample space RN n to the decision space D = fdG; g 2 Gg, where the decision dG is the acceptance of hypothesis HG, G 2 G.

Let S = (si;j ), Q = (qi;j ), S; Q 2 G. Denote by w(S; Q) the loss from the decision dQ when the hypothesis HS is true

w(HS ; dQ) = w(S; Q); S; Q 2 G It is assumed that w(S; S) = 0; S 2 G. According to general decision theory [ 8 ] the quality of statistical procedure is measured by the risk function. Let fX (x) be the density function for the random vector X. Risk function is then de ned by R(fX ; ) = ∑ w(S; Q)PX ( (x) = dQ=HS );

Q2G where w(fX ; (x)) = w(S; Q) if fX 2 HS ; (x) = dQ.

In multiple hypotheses testing [ 6 ], there are different way to measure errors: percomparison error rate (PCER), per-family error rate (PFER), family wise error rate (FWER), generalized family wise error rate (GFWER), false discovery rate (FDR). These errors can be considered as risk for appropriate choice of losses. For example if the loss w(S; Q) takes two values zero and one: w(S; Q) = 1 if there is at least one incorrect inclusion of edge in the threshold graph. Risk function in this case is equal to the probability of at least one type I error (FWER, Family Wise Error Rate): In multiple decision theory [ 4 ], the losses are supposed to be additive. It means that the loss from misclassi cation of HS is equal to the sum of losses from misclassi cation of individual hypotheses.

Consider the set of individual hypotheses: hi;j : i;j 0

vs ki;j : i;j > 0 (i; j = 1; : : : ; N ; i ̸= j): we shall assume that tests for the individual hypotheses are available. For Pearson correlation network we use a well known correlation test. For sign similarity network we construct a uniformly most powerful tests for individual hypotheses testing. Using these tests one can construct a different multiple testing statistical procedures largely used in the literature: single step procedure S (all tests are applied simultaneously), Holm step down procedure H (at each step either one individual hypothesis hi;j is rejected or all remaining hypotheses are accepted) or Hochberg step up procedure Sg (at each step either one individual hypothesis hi;j is accepted or all remaining hypotheses are rejected).

Robustness of statistical procedures for threshold graph identi cation in sign similarity network

We prove that single step, step down Holm, and step up Hochberg multiple testing procedures for threshold graph identi cation in sign similarity network are distribution free for any loss function.

Theorem. Let random vector (X1; : : : ; XN ) has elliptically contoured distribution with density f (x; 0; ). Then for single step, Holm, Hochberg identi cation statistical procedures the probabilities P ( (x) = dQ=HS ), Q; S 2 G are de ned by the matrix and does not depend on the function g.

Corollary. Let random vector (X1; : : : ; XN ) has elliptically contoured distribution with density f (x; 0; ). Then the risk functions R(fX ; S ), R(fX ; H ), R(fX ; Hg) are de ned by the matrix and does not depend on the function g for any loss function w(S; Q).

In particular for the loss function w(S; Q) such that w(S; Q) = 1 if there is at least one incorrect inclusion of edge in the threshold graph, and w(S; Q) = 0 otherwise the risk is equal to FWER (Family Wise Error Rate). Therefore the FWER of single step, Holm, and Hochberg statistical procedures are de ned by the matrix and does not depend on the function g. The same is true for other type of errors, PCER, PFER, GFWER, FDR and for risk function with additive losses. Using this result it is possible to construct single step, Holm and Hochberg distribution free statistical procedures for threshold graph identi cation in Pearson correlation network too.

Acknowledgement: this work is partly supported by RFFI 14-01-00807 grant.

References

1. Bautin G.A. , Kalyagin V.A. , Koldanov A.P. , Koldanov P.A. , Pardalos P.M. Simple measure of similarity for the market graph construction Computational Management Science , 10 , 105 - 124 ( 2013 ).

2. Boginski V. , Butenko S. , Pardalos P.M. : Statistical analysis of nancial networks , Computational Statistics and Data Analysis . 48 ( 2 ), 431 { 443 ( 2005 ).

3. Horvath S . Weighted Network Analysis: Application in Genomics and Systems Biology , Springer book, 2011 .

4. Hochberg , Y. and Tamhane , A. C. Multiple Comparison Procedures , John Wiley and Sons, Inc., Hoboken, NJ, USA, 1987 .

5. Koller D. Friedman N. Probabilistic Graphical Models , MIT Press, 2009 .

6. Lehmann E.L. , Romano J.P. : Testing statistical hypotheses. Springer, New York, ( 2005 ).

7. Tumminello M. , Lillo F. , Mantegna R.N. ( 2010 ). Correlation, Hierarchies and Networks in Financial Markets // J. of Econ. Behavior Organization . Vol. 75 . P. 40 - 58 .

8. Wald A. : Statistical Decision Function . John Wiley and Sons, New York ( 1950 ).