You are an expert at summarizing long articles. Proceed to summarize the following text: 
graphical representations of complex multivariate systems are increasingly prevalent within systems biology . in general a graph or _ network _ @xmath0 is characterised by a set @xmath1 of vertices ( typically associated with molecular species ) and a set @xmath2 of edges , whose interpretation will be context - specific . in many situations the edge set or _ @xmath3 is taken to imply conditional independence relationships between species in @xmath1 @xcite . for fixed and known vertex set @xmath1 , the data - driven characterisation of network topology is commonly referred to as _ network inference_.    in the last decade many approaches to network inference have been proposed and exploited for several different purposes @xcite . in some settings it is desired to infer single edges with high precision ( e.g. * ? ? ? * ) , whereas in other applications it is desired to infer global connectivity , such as subnetworks and clusters ( e.g. * ? ? ? * ) . in cellular signalling systems , the scientific goal is often to identify a set of upstream regulators for a given target , each of which is a candidate for therapeutic intervention designed to modulate activity of the target @xcite . the output of network inference algorithms are increasingly used to inform the design of experiments @xcite and may soon enter into the design of clinical trials @xcite . it is therefore important to establish which network inference algorithms work best for each of these distinct scientific goals . assessment of algorithm performance can be achieved _ in silico _ by comparing inferred networks to known data - generating networks . it can also be achieved using data obtained _ in vitro _ ; however this requires that the underlying biology is either known by design @xcite , well - characterised by interventional experiments @xcite , or estimated from larger corpora of data @xcite . in either case an estimated network @xmath4 , typically represented as a weighted adjacency matrix , is compared against a known or assumed benchmark network @xmath5 . community - wide blind testing of network inference algorithms is performed at the regular dream challenges ( see http://www.the-dream-project.org/ ; * ? ? ? * ; * ? ? ? there is broad agreement in the network inference literature regarding the selection of suitable performance scores ( described below ) , facilitating the comparison of often disparate methodologies across publications . in this literature , the quality of an estimated network @xmath4 with respect to a benchmark @xmath5 is assessed using techniques from classifier analysis . that is , each possible edge @xmath6 has an associated class label @xmath7 , where @xmath8 is the indicator function . a network estimator @xmath4 may then be seen as an attempt to estimate @xmath9 for each pair @xmath10 . two of the main performance scores from classifier analysis are area under the receiver operating characteristic curve ( auroc ) and area under the precision - recall curve ( aupr ) , though alternative performance scores for classification also exist ( e.g. @xcite ) . these scores , formally defined in sec .  [ classification ] , are based on _ confusion matrices _ of true / false positive / negative counts and represent essentially the only way to quantify performance at a local level ( i.e. based on individual edges ) . at present , performance assessment in the network inference literature does not typically distinguish between the various scientific purposes for which network inference algorithms are to be used . yet network inference algorithms are now frequently employed to perform diverse tasks , including identifying single edges with high precision @xcite , eliciting network motifs such as cliques @xcite or learning a coherent global topology such as connected components @xcite . whilst performance for local ( i.e. edge - by - edge ) recovery is now standardised , there has been comparatively little attention afforded to performance scores that capture ability to recover higher - order features such as cliques , motifs and connectivity . recent studies , including @xcite , proposed to employ spectral distances as a basis for comparing between two networks on multiple length scales . in this article we present several additional multi - scale scores ( msss ) for network inference algorithms , each of which reflects ability to solve a particular class of inference problem . much of the popularity of existing scores derives from their objectivity , interpretability and invariance to rank - preserving transformation . unlike previous studies , we restrict attention only to mss that satisfy these desiderata . the remainder of this paper proceeds as follows : in section [ methods ] we formulate the assessment problem , state our desiderata and present novel performance scores that satisfy these requirements whilst capturing aspects of network reconstruction on multiple scales . using a large corpus of estimated and benchmark networks from the dream5 challenge in section [ results ] , we survey estimator performance and conduct an objective , data - driven examination of the statistical power of each mss . the proposed msss provide evidence that the `` wisdom of crowds '' approach , that demonstrated superior ( local ) performance in the dream5 challenge , also offers gains on multiple length scales . sections [ discussion ] and [ conclude ] provide a discussion of our proposals and suggest directions for future work . matlab r2013b code ` net_assess ` is provided in the supplement , to accelerate the dissemination of ideas discussed herein . we proceed as follows : sections [ assumptions ] and [ desiderata ] clarify the context of the assessment problem for network inference algorithms amd list certain desiderata that have contributed to the popularity of local scores . sections [ notation ] and [ classification ] introduce graph - theoretic notation and review standard performance assessment based on recovery of individual edges . in sections [ mss one ] and [ mss two ] we introduce several novel msss for assessment of network inference algorithms . we require each mss to satisfy our list of desiderata ; however these scores differ from existing scores by assessing inferred network structure on several ( in fact all ) scales . for each mss we discuss associated theoretical and computational issues . finally section [ test ] describes computation of @xmath11-values for the proposed msss . performance assessment for network inference algorithms may be achieved by comparing estimated networks against known benchmark information . the interpretation of the estimated networks themselves has often been confused in existing literature , with no distinction draw between the contrasting notions of significance and effect size . in this section we therefore formally state our assumptions on the interpretation of both the benchmark network @xmath5 and the network estimators or estimates @xmath4 .    * all networks are directed , unsigned and contain no self - edges . a network is _ signed _ if each edge carries an associated @xmath12 symbol . ( a1 ) is widely applicable since an undirected edge may be recast as two directed edges and both signs and self - edges may simply be removed . the challenge of inferring signed networks and more generally the problem of predicting interventional effects requires alternative performance scores that are not dealt with in this contribution , but are surveyed briefly in sec .  [ discussion ] . the preclusion of self - edges aids presentation but it not required by our methodology .    the form of this benchmark information will influence the choice of performance score and we therefore restrict attention to the most commonly encountered scenario :    * the benchmark network @xmath5 is unweighted .    a network is _ weighted _ if each edge has an associated weight @xmath13 . note that the case of unweighted benchmark networks is widely applicable , since weights may simply be removed if necessary . we will write @xmath14 for the space of all directed , unweighted networks that do not contain self - edges and write @xmath15 for the corresponding space of directed , weighted networks that do not contain self - edges . * the benchmark network @xmath5 contains at least one edge and at least one non - edge . * network estimators @xmath4 are weighted ( @xmath16 ) , with weights having the interpretation that larger values indicate a larger ( marginal ) probability of the corresponding edge being present in the benchmark network . in particular we do not consider weights that instead correspond to effect size ( see sec . [ discussion ] ) . * in all networks , edges refer to a _ direct _ dependence of the child on the parent at the level of the vertex set @xmath1 ; that is , not occurring via any other species in @xmath1 .    assumptions ( a1 - 5 ) are typical for comparative assessment challenges such as dream @xcite .      fix a benchmark network @xmath5 . a _ performance score _ is defined as function @xmath17 that accepts an estimated network @xmath16 and a benchmark network @xmath18 and returns a real value @xmath19 that summarises some aspect of @xmath4 with respect to @xmath5 . examples of performance scores are given below . our approach revolves around certain desiderata that any ( i.e. not just multi - scale ) performance score @xmath20 ought to satisfy :    * ( interpretability ) @xmath21 $ ] for all @xmath16 , @xmath18 , with larger values corresponding to better performance at some specified aspect of network reconstruction . * ( computability ) @xmath20 should be readily computable . * ( objectivity ) @xmath20 should contain no user - specified parameters .    a network estimate @xmath16 is called @xmath20-_optimal _ for a benchmark network @xmath5 if it maximises the performance score @xmath22 over all networks in @xmath15 .    * ( consistency ) the oracle estimator @xmath23 is @xmath20-optimal . a _ rank - preserving _ transformation @xmath24 of a collection of real values @xmath25 satisfies @xmath26 whenever @xmath27 .    * ( invariance ) @xmath20 should be invariant to rank - preserving transformations of the weights associated with an estimate @xmath4 . the criteria ( d0 - 3 ) are important for practical reasons ; ( d4 ) is more technical and reflects the fact that we wish to compare estimators whose weights need not belong to the same metric space . i.e. different algorithms may be compared on the same footing , irrespective of the actual interpretation of edge weights ( subject to ( a4 ) ) . given that much of the popularity of standard classifier scores derives from ( d0 - 4 ) , it is important that any proposed mss also satisfies the above desiderata . as we will see below , previous studies , such as @xcite , do not satisfy ( d2,4 ) , precluding their use in objective assessment such as the dream challenges . in secs . [ mss one ] , [ mss two ] below we present novel mss that satisfy each of ( d1 - 4 ) . the local performance scores that have become a standard in the literature , defined in sec . [ classification ] below , are easily shown to satisfy the above desiderata . to date , the challenge of assessing network inference algorithms over multiple scales has received little statistical attention ; yet there are several general proposals for quantifying higher order network structure . notably @xcite assessed spectral distances for suitability in application to biological networks . the authors recommended use of the ipsen - mikhailov distance ( imd ) due to its perceived stability and robustness properties , as quantified on randomly generated and experimentally obtained networks @xcite . imd evaluates the difference of the distribution of laplacian eigenvalues between two networks and therefore could be considered an mss . there has , to date , been no examination of imd and related spectral metrics in the context of performance assessment for network inference applications . however imd and related constructions ( e.g. * ? ? ? * ) fail to satisfy the above desiderata : ( i ) imd itself fails to satisfy ( d4 ) since eigenvalues are not invariant to rank - preserving transformations ; ( ii ) the imd formula contains a user - specified parameter , invalidating ( d2 ) . @xcite recently introduced `` structural intervention distance '' ( sid ; actually a pre - distance ) which interprets inferred networks @xmath28 as estimators of an underlying causal graph @xmath5 , where both @xmath28 and @xmath5 must be acyclic @xcite . specifically , sid is the count of pairs of vertices @xmath10 for which the estimate @xmath28 incorrectly predicts intervention distributions ( in the sense of @xcite ) within the class of distributions that are markov with respect to @xmath5 . as such , sid is closely related to the challenge of predicting the effect of unseen interventions . however sid fails to satisfy ( d0 ) due to the requirement that estimated and benchmark networks must be acyclic ( i.e. a causal interpretation will not be justified in general ) and is therefore unsuitable for this application . below we introduce notation that will be required to define our proposed scores : throughout this paper an unweighted network @xmath18 on vertices @xmath29 ( where @xmath30 ) is treated as a binary matrix @xmath31 with @xmath10th entry denoted @xmath32 . when @xmath33 or @xmath34 we say that @xmath5 contains or does not contain the edge @xmath10 , respectively . write @xmath35 for the set of parents for vertex @xmath36 . in this paper we do not allow self - edges ( a1 ) , so that @xmath37 for all @xmath38 . a path @xmath39 from @xmath40 to @xmath41 in @xmath31 is characterised by a sequence of vertices @xmath42 such that @xmath43 and @xmath44 for all @xmath45 . note that a path @xmath39 may contain cycles , but these cycles may not involve @xmath46 . we say that this path has length @xmath47 where @xmath48 . let @xmath49 denote the set of all paths in @xmath5 from @xmath40 to @xmath41 , so that in particular @xmath50 . we identify weighted , unsigned networks @xmath16 with non - negative real - valued matrices @xmath51^{p \times p}$ ] and denote the @xmath10th entry by @xmath52 . should a network inference procedure produce edge weights in @xmath53 then by dividing through by the largest weight produces a network with weights in @xmath54 $ ] . this highlights the importance of property ( d4 ) , invariance to rank preserving transformations . it will be required to map @xmath4 into the space of unweighted networks by thresholding the weights at a certain level @xmath55 . for @xmath56 we write @xmath28 for the unweighted network corresponding to a matrix with entries @xmath57 .      in this section we briefly review local scoring , which has become an established standard in the network inference literature .    * definition : * classification performance scores are defined as functions of confusion matrices , that count the number of true positive ( tp ) , false positive ( fp ) , true negative ( tn ) and false negative ( fn ) calls produced by a classifier . from ( a4 ) it follows that the @xmath58 largest entries in a network estimate @xmath4 correspond to the @xmath58 pairs of vertices with largest marginal probabilities of being present as edges in the benchmark network @xmath5 ; it is therefore reasonable to threshold entries of @xmath4 , say at a level @xmath55 , and to consider confusion matrices corresponding to the classifier @xmath28 . in the standard case of _ local _ estimation , confusion matrices are given by tp@xmath59 , fp@xmath60 , tn@xmath61 and fn@xmath62 . based on these quantities , ( local ) performance scores may be defined . in particular , one widely used score is the area under the receiver operating characteristic ( roc ) curve @xmath63 where @xmath64 is the _ true positive rate _ and @xmath65 is the _ false positive rate_. @xmath66 has an interpretation as the probability that a randomly selected pair from @xmath67 is assigned a higher weight @xmath52 that a randomly selected pair from @xmath68 @xcite . as such @xmath66 takes values in @xmath54 $ ] with 1 representing perfect performance and @xmath69 representing performance that is no better than chance . for finitely many test samples , @xmath70 curves may be estimated by linear interpolation of points @xmath71 in roc - space . precision - recall ( pr ) curves are an alternative to roc curves that are useful in situations where the underlying class distribution is skewed , for example when the number of negative examples greatly exceeds the number of positive examples @xcite . for biological networks that exhibit sparsity , including gene regulatory networks @xcite and metabolic networks @xcite , the number of positive examples ( i.e. edges ) is frequently smaller than the number of negative examples ( i.e. non - edges ) . in this case performance is summarised by the area under the pr curve @xmath72 where @xmath73 is the _ positive predictive value_. ( in this paper we adopt the convention that @xmath74 whenever @xmath75 . ) @xmath76 also takes values in @xmath54 $ ] , with larger values representing better performance . for finitely many test samples in pr - space , unlike roc - space , linear interpolation leads to over - optimistic assessment of performance . the matlab code provided in the supplement follows @xcite in using nonlinear interpolation to achieve correct , unbiased estimation of area under the pr curve . * captures : * local scores capture the ability of estimators to recover the exact placement of individual edges . both @xmath66 and @xmath76 summarise the ability to correctly infer local topology across a range of thresholds @xmath55 , with pr curves prioritising the recovery of positive examples in the `` top @xmath58 edges '' @xcite . * desiderata : * ( d1 ; computability ) , ( d2 ; objectivity ) and ( d3 ; consistency ) are clearly satisfied . ( d4 ; invariance ) is satisfied , since the image of a parametric curve is invariant to any monotone transformation of the parameter ( in this case @xmath55 ) . we now introduce the first of our msss , which targets ability to infer the connected components of the benchmark network @xmath5 , through the existence or otherwise of directed paths between vertices . * definition : * in the notation of sec .  [ notation ] , local performance scores are based on estimation of class labels @xmath77 associated with individual edges . a natural generalisation of this approach is to assign labels @xmath78 to pairs of vertices @xmath6 , such that @xmath79 , based on _ descendancy _ ; that is , based on the presence or otherwise of a directed path from vertex @xmath40 to vertex @xmath41 in the benchmark network . i.e. @xmath80 . by comparing descendancies in @xmath28 against descendancies in @xmath5 , we can compute confusion matrices and , by analogy with local scores , we can construct area - under - the - curve scores by allowing the threshold @xmath55 to vary . we denote these scores respectively as @xmath81 and @xmath82 . by analogy with local scores , both @xmath81 , @xmath82 take values in @xmath54 $ ] , and @xmath81 is characterised as the probability that a randomly selected pair from @xmath83 is assigned a higher weight @xmath84 than a randomly selected pair from @xmath85 . * captures : * mss1 captures the ability to identify ancestors and descendants of any given vertex . mss1 scores therefore capture the ability of estimators to recover connected components on all length scales . * desiderata : * ( d1 ; computability ) is satisfied due to the well - known warshall algorithm for finding the transitive closure of a directed , unweighted network @xcite , with computational complexity @xmath86 . for the estimated network @xmath4 it is required to know , for each pair @xmath10 the value of @xmath87 , i.e. the largest value of the threshold @xmath55 at which @xmath88 . to compute these quantities we generalised the warshall algorithm to the case of weighted networks ; see sec . [ theory results ] . ( d2 - 4 ) are automatically satisfied analogously to local scores , by construction of confusion matrices and area under the curve statistics . whilst mss1 scores capture the ability to infer connected components , they do not capture the graph theoretical notion of _ differential connectivity _ ( i.e. the minimum number of edges that must be removed to eliminate all paths between a given pair of vertices ) . our second proposed mss represents an attempt to explicitly prioritise pairs of vertices which are highly connected over those pairs with are weakly connected :    * definition : * for each pair @xmath6 we will compute an _ effect _ @xmath89 that can be thought of as the importance of variable @xmath40 on the regulation of variable @xmath41 according to the network @xmath5 ( in a global sense that includes indirect regulation ) . to achieve this we take inspiration from recent work by @xcite as well as @xcite , who exploit spectral techniques from network theory . since the effect @xmath90 , which is defined below , includes contributions from all possible paths from @xmath40 to @xmath41 in the network @xmath4 , it explicitly captures differential connectivity . we formally define effects for an arbitrary unweighted network @xmath91 ( which may be either @xmath5 or @xmath28 ) . specifically the effect @xmath90 of @xmath40 on @xmath41 is defined as the sum over paths @xmath92 where @xmath93 is the kronecker delta . effects @xmath90 quantify direct and indirect regulation on all length scales . to illustrate this , notice that eqn . [ effects def ] satisfies the recursive property @xmath94 ( see sec .  [ theory results ] ) . intuitively , eqn . [ recurse ] states that the fraction of @xmath41 s behaviour explained by @xmath40 is related to the combined fractions of @xmath41 s parents behaviour that are explained by @xmath40 . rephrasing , in order to explain the behaviour of @xmath41 it is sufficient to explain the behaviour of each of @xmath41 s parents . moreover , if a parent @xmath58 of @xmath41 is an important regulator ( in the sense that @xmath41 has only a small number of parents ) then the effect @xmath95 of @xmath40 on @xmath58 will contribute significantly to the combined effect @xmath90 . [ recurse ] is inspired by @xcite and later @xcite , but differs from these works in two important respects : ( i ) for biological networks it is more intuitive to consider normalisation over incoming edges rather than outgoing edges , since some molecular species may be more influential than others . mathematically , @xcite corresponds to replacing @xmath96 in eqn . [ recurse ] with @xmath97 . ( ii ) @xcite employed a `` damping factor '' that imposed a multiplicative penalty on longer paths , with the consequence that effects were readily proved to exist and be well - defined . in contrast our proposal does not include damping on longer paths ( see discussion of d2 below ) and the theory of @xcite and others does not directly apply in this setting . below we write @xmath98 for the matrix that collects together all effects for the benchmark network @xmath5 ; similarly denote by @xmath99 the matrix of effects for the thresholded estimator @xmath28 . any well - behaved measure of similarity between @xmath99 and @xmath100 may be used to define a mss . we constructed an analogue of a confusion matrix as tp@xmath101 , fp@xmath102 , tn@xmath103 , fn@xmath104 . repeating the construction across varying threshold @xmath55 , we compute analogues of roc and pr curves . ( note that , unlike conventional roc curves , the curves associated with mss2 need not be monotone ; see supp . sec . [ auc con ] . ) finally scores @xmath105 , @xmath106 are computed as the area under these curves respectively . * captures : * mss2 is a spectral method , where larger scores indicate that the inferred network @xmath4 better captures the _ eigenflows _ of the benchmark network @xmath5 @xcite . in general neither @xmath105 nor @xmath106 need have a unique maximiser ( see sec . [ theory results ] ) . as such , mss2 scores do not require precise placement of edges , provided that higher - order topology correctly captures differential connectivity . * desiderata : * eqn . [ effects def ] involves an intractable summation over paths : nevertheless ( d1 ; computability ) is ensured by an efficient iterative algorithm related but non - identical to @xcite , described in sec . [ theory results ] . in order to ensure ( d2 ; objectivity ) we did not include a damping factor that penalised longer paths , since the amount of damping would necessarily depend on the nature of the data and the scientific context . it is important , therefore , to establish whether effects @xmath90 are mathematically well defined in this objective limit . this paper contributes novel mathematical theory to justify the use of mss2 scores and prove the correctness of the associated algorithm ( see sec .  [ theory results ] ) . as with mss1 , the remaining desiderata ( d3 - 4 ) are satisfied by construction .      in performance assessment of network inference algorithms we wish to test the null hypothesis @xmath107 : @xmath108 for an appropriate null model @xmath109 . we will construct a one - sided test based on a performance score @xmath20 and we reject the null hypothesis @xmath107 when @xmath110 $ ] for an appropriately chosen critical value @xmath111 . in general the distribution of a score @xmath112 under a network - valued random variable @xmath113 displays a nontrivial dependence on the benchmark network @xmath5 . we therefore follow @xcite and propose a monte carlo approach to compute significance levels , though alternative approaches exist including @xcite . specifically , significance of an inferred network @xmath4 under a null model @xmath109 is captured by the @xmath11-value @xmath114 and given by the strong law of large numbers as @xmath115 where the @xmath116 are independent samples from @xmath109 . the choice of null model @xmath109 is critical to the calculation and interpretation of @xmath11-values @xmath117 . in most biological applications , the null would ideally encompass biological sample preparation , experimental data collection , data preprocessing and network estimation ; however in practice it is convenient to define a null model @xmath118 conditional upon the inferred network @xmath4 ( e.g. * ? ? ? * ) . for brevity , we restrict attention to the following choice : a random network @xmath119 is obtained from @xmath4 by applying a uniformly random permutation @xmath120 to the vertex labels @xmath1 ; that is , @xmath113 is a uniform sample from the space of graph isomorphisms of @xmath4 . this choice has the interpretation that , for deterministic network inference algorithms , the null @xmath121 corresponds to randomly permuting the variable labels in the experimental dataset , prior to both data preprocessing and network inference . note that @xmath121 results in a trivial ( @xmath116-independent ) hypothesis test when @xmath4 is either empty or complete ; we do not consider these degenerate cases in this paper .    in sec . [ signif ] we empirically assess the power of this test based on both existing and proposed scores @xmath20 . matlab r2013b code ` net_assess ` , that was used to compute all of the scores and associated @xmath11-values used in this paper , is provided in the supplement . in sec .  [ theory results ] below we present theoretical results relating to the proposed scores , demonstrating that mss and local scores can yield arbitrarily different conclusions in settings where local topology is recovered very well but higher - order topology is recovered very poorly and vice versa . in sec . [ dream info ] , in order to empirically assess the statistical power our proposed scores , we appeal to the large corpus of data available from the dream community , that represents a large and representative sample of network estimators used by the community . whilst distributional results are difficult to obtain , we are able to characterise the behaviour of mss in both favourable and unfavourable limits . our first result proves non - uniqueness of @xmath20-optimal estimates :    [ nonunique ] for each score @xmath81 , @xmath82 , @xmath105 and @xmath106 , the benchmark network @xmath5 is always @xmath20-optimal ( d3 ) . however , for mss1 and mss2 , @xmath20-_optimal _ estimates are not unique . this result contrasts with local performance scores , where @xmath66 and @xmath76 are uniquely maximised by the benchmark network @xmath5 . intuitively , theorem [ nonunique ] demonstrates that it is possible to add or remove individual edges from a network without changing its higher - order features , such as its connected components . our second result proves that the mss are fundamentally different from existing scores by demonstrating it is possible to simultaneously recover local topology with arbitrary accuracy yet fail to correctly accurately recover the higher - order topology ( and vice versa ) :    [ different ] ( a ) for any @xmath122 there exist a benchmark network @xmath18 and an estimate @xmath16 that satisfy ( i ) @xmath66 , @xmath123 , ( ii ) @xmath81 , @xmath124 , and ( iii ) @xmath82 , @xmath125 . \(b ) for any @xmath122 there exist a benchmark network @xmath18 and an estimate @xmath16 that satisfy ( i ) @xmath81 , @xmath105 , @xmath82 , @xmath126 , ( ii ) @xmath127 , and ( iii ) @xmath128 . an important consequence of this result is that estimators that perform well locally , including dream challenge winners , may not be appropriate for scientific enquiry regarding non - local network topology . given the increasing use of network inference algorithms in systems biology ( e.g. * ? ? ? * ; * ? ? ? * ) , this highlights the need to study performance of network inference algorithms on multiple length scales .    our final theoretical contribution is to propose and justify efficient algorithms for computation of both mss1 and mss2 . for mss1 we generalise the warshall algorithm to compute the transitive closure of a directed , weighted graph :    [ warshall ] for a fixed weighted network @xmath91 , let @xmath129 be the largest value of the threshold parameter @xmath55 for which there exists a path from @xmath40 to @xmath41 in the network @xmath130 . then @xmath131 may be computed as follows :    @xmath132 @xmath133 @xmath134    for mss2 , following @xcite we formulate effects @xmath90 as solutions to an eigenvalue problem . however our approach is non - identical to @xcite ( see sec . [ mss two ] ) ; as a consequence we must prove that ( i ) effects are mathematically well - defined , and ( ii ) an appropriately modified version of the algorithm of @xcite converges to these effects . below we contribute the relevant theory :    [ compute ] the effects @xmath135 for an unweighted network @xmath91 exist , are unique , satisfy eqn . [ recurse ] and may be computed as @xmath136 where @xmath137 is the @xmath40th row of @xmath100 and @xmath138 is defined by ( i ) @xmath139 , ( ii ) @xmath140 for all @xmath141 and @xmath142 , ( iii ) @xmath143 otherwise . theorem [ compute ] facilitates highly efficient numerical computation of the effect matrices @xmath100 required for mss2 . in practice eqn . [ algo ] requires convergence diagnostics ; for experiments in this paper we used the stopping rule @xmath144 .      for an objective comparison covering a wide range of network inference methodologies , we exploited the results of the dream5 challenge , where 36 methodologies were blind - tested against both simulated and real transcription factor data @xcite . the network inference challenge included ( i ) _ in silico _ data generated using genenetweaver @xcite , ( ii ) experimentally validated interactions from a curated database for _ e. coli _ , and ( iii ) transcription - factor binding data and evolutionarily conserved binding motifs for _ s. cerevisiae_. data were provided on the genomic scale , involving ( i ) 1643 , ( ii ) 4297 and ( iii ) 5667 genes respectively . for each of these systems , benchmark information was provided in the form of targets for a subset of genes . for assessment purposes we restricted attention to predictions made regarding these subnetworks only , satisfying ( a1 - 3 ) , consisting of ( i ) 195 , ( ii ) 334 and ( iii ) 333 genes respectively . the dream5 data are well - suited for this investigation , representing a wide variety of network reconstruction algorithms contributed by the community and containing sufficiently many samples to provide a definitive assessment of statistical power .    in each challenge , participants were required to provide a list of inferred edges @xmath10 , together with associated weights @xmath145 . such edges were directed , unsigned and excluded self - edges , satisfying ( a1 ) . participants were asked to `` _ infer the structure of the underlying transcriptional regulatory networks _ '' , so that edges were ranked in terms of their probability of existence , rather than their inferred effect size ( a4 ) . for dream5 , ( a5 ; direct dependence ) appears to be implicit . the algorithms used to obtain edge lists and weights varied considerably , being classified according to their statistical formulation as either _ bayesian _ , _ correlation _ , _ meta _ , _ mutual information _ ( mi ) , _ regression _ or _ other_. for each methodology we obtained performance scores for datasets ( i - iii ) using the ` net_assess ` package ( supp . figs . [ silico bar ] , [ ecoli bar ] , [ sc bar ] ) . we also investigated the overall score reported by @xcite , that summarises performance by combining local auroc and aupr scores across all 3 datasets ( further details in supp . [ overall def ] ) .    in section [ participant ] below we examine the characteristics of our proposed scores in an aggregate sense based on the full dream5 data . section [ indiv ] then considers estimator - specific score profiles in order to understand the multi - scale properties of different network inference algorithms . in particular section [ community ] focusses on a `` wisdom of crowds '' approach that has previously demonstrated strong local performance in this setting . finally section [ signif ] quantifies the statistical power of our proposed scores in the context of hypothesis testing . local and mss scores may be arbitrarily different in principle ( theorem [ different ] ) , however in practice these scores may be highly correlated . to investigate this we produced scatter plots between the existing and proposed performance scores over all 36 estimators and all 3 datasets ( a total of @xmath146 samples ; fig . [ dream ] , supp . [ dream2 ] ) . our findings , based on spearman correlation ( table [ corr table ] ) , showed that all scores were significantly correlated under aupr on the _ in silico _ and _ e. coli _ datasets ( @xmath147 ) , but not on the _ s. cereviviae _ dataset . indeed results for the _ s. cerevisiae _ dataset were less impressive for all methods , under all performance scores , in line with the general poor performance on this dataset reported by @xcite . on the combined data , both mss1 and mss2 was significantly correlated with the local score under auroc ( @xmath148 , @xmath149 ; @xmath150 in each case ) suggesting that accurate reconstruction of local topology is associated with accurate reconstruction of higher - order topology . on the other hand , on all 3 datasets and both auroc and aupr statistics , mss2 was less highly correlated with the local score compared to mss1 ( e.g. on the combined data and aupr , @xmath151 versus @xmath152 ) . this suggests that estimated local topology is more predictive of descendancy relationships than predictive of differential connectivity and spectral features . in many cases mss1 and mss2 were significantly correlated ; this was expected since both estimators target multiple scales by design . network inference algorithms are predominantly employed in contexts where there is considerable uncertainty regarding the data - generating network topology . in such settings attention is often restricted to the `` most significant '' aspects of inferred topology ; we therefore similarly restrict attention to individual estimator performance as quantified by scores based on aupr , reserving auroc results for supp . sec .  [ auroc results ] .    under mss1 the best performing methods included _ bayesian 1,2,6 _ and _ meta 1,5 _ ( fig . [ dream ] ) . for mss2 many methods attained similarly high scores ; these included _ bayesian 1,2,6 _ and _ meta 1,5_. interestingly these 5 best performing algorithms did not rank highly according to the ( local ) overall score of @xcite ( placing 8th , 24th , 20th , 22nd and 34th respectively out of 36 ) . similarly _ regression 2 _ , which almost maximised @xmath76 on the _ in silico _ dataset , was among algorithms with the lowest @xmath106 . this appears to be a real example of the conclusion of theorem [ different ] , where _ regression 2 _ recovers several individual edges yet fails faithfully reconstruct higher - order topology , including connected components . [ meta5 ] displays inferred and benchmark topology for _ regression 2 _ ; it is visually clear that the algorithm fails to distinguish between different connected components in the true data - generating network . conversely , estimators such as _ bayesian 1,2 _ simultaneously achieve strong multi - scale performance and unimpressive local performance ( fig . [ dream ] ) . it is well understood that bayesian estimators are well suited to recovery of a coherent joint graphical model , compared to estimators that decompose network inference into independent neighbourhood selection problems @xcite . these results suggest that this intuition is manifest in the multi - scale performance of bayesian network inference algorithms as quantified by both @xmath82 and @xmath106 . a key finding of @xcite was that the _ community _ network , a principled aggregation of the dream5 participants predictions , was able to maximise the overall score for local performance ( the so - called `` wisdom of crowds '' phenomenon ) . interestingly , we found that this _ community _ network also performed well over multiple length scales ( supp . [ silico bar],[ecoli bar],[sc bar ] ) . in fact the _ community _ network was almost @xmath105 and @xmath106-optimal over all 36 methodologies on all 3 datasets and was ranked highly under @xmath81 in all experiments . these results suggest that aggregation of estimators that perform well locally ( e.g. _ regression 2 _ ) and well on higher - order topology ( e.g. _ bayesian 2 _ ) may be a successful strategy to achieve strong performance over multiple length scales . a common fault of complex test statistics is that they lack power relative to simpler statistics ( e.g. @xcite ) . in order to explore the relative statistical power of existing and proposed performance scores @xmath20 in hypothesis testing , we computed monte carlo @xmath11-values for each network estimate @xmath4 in the dream5 challenge , taking each score in turn as a test function ( see sec . [ test ] ) . under the assumption that all dream5 participants were capable , in principle , of recovering some aspects of structural information ( i.e. estimators were not simply random samples from @xmath109 ) , we may estimate statistical power by treating the dream5 data as cases where @xmath107 should be rejected . results ( fig .  [ pvals ] ) showed that , over all 36 participants and all 3 datasets , @xmath153 assigned a significance level @xmath154 to 88% of the networks , @xmath82 achieved 73% whilst @xmath106 achieved 71% at this threshold . varying the threshold @xmath155 we see that @xmath76 is roughly 25% more powerful compared to both @xmath82 and @xmath106 . given that challenge participants likely developed methodology to optimise local performance scores rather than multi - scale scores , these findings support the conclusion that the multi - scale scores @xmath82 , @xmath106 offer comparable power relative to @xmath76 . from the perspective of methodology , these results show that most dream5 algorithms are better suited to identifying local rather than higher - order topology . results for roc - based scores demonstrated a more considerable decrease in statistical power between local and multi - scale test statistics ; it may therefore be prudent to restrict attention to multi - scale results based on pr - scores . network inference algorithms are increasingly used to facilitate diverse scientific goals , including prediction of single interactions with high precision , identifying motifs such as cliques or clusters , and uncovering global topology such as connected components . yet performance assessment of these algorithms does not currently distinguish between these contrasting goals ; we do not know which algorithms are most suited to which tasks . widely used local scores based on classifier analysis capture the ability of an algorithm to exactly recover a benchmark network at the local level . in this paper we proposed novel multi - scale scores ( msss ) that instead capture ability to infer connectivity patterns simultaneously over all length scales . unlike previous multi - scale proposals , our mss satisfy desiderata that have contributed to the popularity of local performance scores , including invariance to rank - preserving transformation . theoretical results demonstrated the potential for local and multi - scale analyses to draw arbitrarily different conclusions . empirical results , based on a comprehensive analysis of the dream5 challenge data , confirmed that whilst local and multi - scale performance were correlated , in several cases an estimator recovered local topology well but recovered higher - order topology poorly and _ vice versa_. these results highlight the importance of performance assessment on multiple length scales , since apparently promising methodologies may be highly unsuitable for inference of non - local network topology . notably the _ community _ network proposed by @xcite enjoyed both good local and good multi - scale performance . finally we demonstrated that one proposed score ( @xmath106 ) possesses comparable statistical power with respect to local scores . our proposals extend scores based on individual edges by considering paths of length @xmath156 . multi - scale analysis of networks is now an established research field ; indeed techniques based on @xcite have recently come to light in both gene regulatory network @xcite and protein signalling network @xcite analyses . this work differs to these within - network studies by focussing on the challenge of performance assessment . the statistical comparison of two unweighted networks has recently been considered by @xcite . in related work , @xcite constructed an _ ad - hoc _ null distribution over residue interaction graphs based on degree - distribution , clustering coefficient , clustering spectrum , average network diameter and spectrum of shortest path lengths . however these are _ mean field _ statistics , which do not respect vertex labels , making their use inappropriate for many scientific applications . existing and proposed scores capture complementary aspects of performance , so that it is misleading to speak of a universally `` best '' methodology . mss was specifically designed to capture aspects of higher - order network reconstruction that have been relatively neglected by the community , however in general the existing and proposed scores together still fail to capture many important aspects of estimator performance . in that respect , this paper represents a small step towards more comprehensive characterisation of estimator performance . mss1 required a factor of @xmath157 more computation than existing local scores , with mss2 requiring a factor of @xmath158 . ( computational times are presented in supp . [ times ] . ) given that in practice it may be desirable to restrict attention to a single measure of multi - scale performance , and given that @xmath82 and @xmath106 provide similar statistical power , it may be preferable to favour mss1 over mss2 .    whilst multi - scale analysis has the potential to complement local analyses and deepen our understanding of the applicability and limitations of network inference algorithms , there are two commonly encountered settings where multi - scale analyses may actually be preferred over local analyses :    1 . * time series data : * @xcite and others have noticed that , in the setting of causal graphical models and time series data , the `` true '' causal graph @xmath5 depends crucially on the time scale at which the process is described . to see this , notice that the simple multivariate process defined by the causal graph @xmath5 , equal to @xmath159 and distributions @xmath160 with @xmath161 independent @xmath162 random variables , satisfies @xmath163 with @xmath164 independent @xmath165 random variables . thus any consistent estimator of a linear gaussian vector autoregressive process will , based on data from even time points only , infer the causal graph @xmath166 equal to @xmath167 . i.e. the apparently natural estimator demonstrates the worst possible performance under @xmath168 . this is undesirable since it remains the case that all descendancy relationships in @xmath4 are all contained in @xmath5 . however @xmath4 is readily seen to be @xmath169-optimal , so that the proposed scores are robust to the problem of inappropriate sampling frequency . real - world examples of this problem arise in the ( frequently encountered ) settings where no natural time scale is available for experimental design , or the sampling frequency is limited by resource constraints . * interventional experiments : * in experimental settings , network topology is frequently inferred through targeted interventions ( e.g. knock - downs , knock - outs , small molecule inhibitors , monoclonal antibodies etc . ) . differential analysis with respect to a control sample in this case does not reveal the direct children of the interventional target , but rather specifies the descendants of that target . thus benchmark information is naturally available on descendants , whereas additional experimental work is required to uncover direct edges . in these settings performance assessment using descendancy ( i.e. mss1 ) rather than using individual edges facilitates a reduction in experimental cost . this paper focused on the problem of inference for network structure , but an alternative viewpoint is to assess networks by their predictive power @xcite . in this setting ( a4 ) is replaced by an assumption that estimator weights correspond to effect size ( and may be signed ) . for example these weights may be average causal effects ( ace ; * ? ? ? * ; * ? ? ? . however this setting is less common as many popular network inference methodologies do not entail a predictive statistical model . moreover , prediction is often computationally intensive , whereas assessment of the inferred topology is relatively cheap . this paper lays statistical and conceptual foundations for the analysis of network inference algorithms on multiple scales . we restricted attention to the important problem of comparing between inference procedures , as in the dream challenges , and proposed novel multi - scale scores ( msss ) for this setting . an empirical study based on the dream5 data demonstrated that multi - scale analysis provides additional insight into the character and capability of network inference algorithms and suggested that a crowd - source approach to inference may offer improved reconstruction of higher - order topology . in this paper we focussed on connectivity , but multi - scale scores may be designed to capture ability to infer specific motifs such as cliques , or particular feedback circuits , for example . this work is exploratory and should not be used to form conclusions regarding the performance of specific teams in the dream5 challenge . the authors are grateful to gustavo stolovitzky and sach mukherjee for feedback on an earlier draft of this manuscript . this work was supported by the centre for research in statistical methodology grant ( epsrc ep / d002060/1 ) . cjo was involved in designing the dream8 challenge . cjo , ra , sefs were not involved in the dream5 challenge . @xmath20-optimality of the benchmark network @xmath5 follows immediately from the definition of each score . to prove nonuniqueness we begin by considering mss1 . for this , take @xmath5 to be the network @xmath170 and take @xmath171 to be the network @xmath172 ; then both networks entail the same descendancy relationships . it follows from ( d3 ; consistency ) that both @xmath5 and @xmath171 maximise @xmath81 and @xmath82 , demonstrating that the maximiser will be non - unique in general . the argument for mss2 is analogous , using the same pair of networks . \(a ) given @xmath122 . we proceed by constructing a sequence of pairs @xmath173 indexed by @xmath11 , the number of vertices , such that the scores associated with @xmath4 end simultaneously to the required limits as @xmath174 . define a data - generating network @xmath5 on @xmath11 vertices by the edge set @xmath175 and consider an unweighted network @xmath4 with topology @xmath176 . i.e. @xmath4 differs to @xmath5 in the addition of a single edge @xmath177 . the roc curve corresponding to @xmath4 is defined by the three points @xmath178 so that by linear interpolation the area under the curve is @xmath179 . the pr curve is similarly defined by @xmath180 here @xmath181 is the number of true examples ; for local scores this is @xmath182 , for mss1 this is @xmath183 and for mss2 this is @xmath184 . to compute the area under this curve we must use nonlinear interpolation @xcite . specifically , interpolation between the two points @xmath185 , @xmath186 with true / false positive values @xmath187 , @xmath188 respectively we create new points for each of @xmath189 , increasing the false positives for each new point by @xmath190 . by direct calculation we have that the area under this interpolated curve is @xmath191}.\end{aligned}\ ] ]    fix @xmath122 . for ( i ) , since @xmath4 differs to @xmath5 by just a single edge we have tp @xmath192 , fp @xmath193 , @xmath194 , tpr @xmath195 , fpr @xmath196 , ppv @xmath197 . it is then easily checked that @xmath198 ^ 2}{[2(p-2)][2(p-2)-1 ] } \rightarrow 1 \ ; \ ; \ ; \text{as } \ ; \ ; \ ; p \rightarrow \infty.\end{aligned}\ ] ] thus @xmath199 .    for ( ii - iii ) and mss1 note that @xmath200 for all @xmath79 , so that @xmath4 predicts every possible descendancy . thus tp @xmath201 , fp @xmath202 , @xmath203 , tpr @xmath195 , fpr @xmath195 , ppv @xmath204 and @xmath205 ^ 2}{[3(p-2)][3(p-2)+(p^2 - 4p+1 ) ] } \rightarrow 0 \ ; \ ; \ ; \text{as } \ ; \ ; \ ; p \rightarrow \infty.\end{aligned}\ ] ] thus @xmath206 . for mss2 note that the estimated effects are @xmath207 whereas the benchmark effects are @xmath208\end{aligned}\ ] ] leading to tp @xmath209 , fp @xmath210 , @xmath211 , tpr @xmath195 , fpr @xmath195 , ppv @xmath212 and @xmath213 ^ 2}{[2p][2p+p(p-2 ) ] } \rightarrow 0 \ ; \ ; \ ; \text{as } \ ; \ ; \ ; p \rightarrow \infty.\end{aligned}\ ] ] thus @xmath214 . taking @xmath215 , we have shown that @xmath173 satisfy the conclusions of the theorem . \(b ) the converse result is proved similarly , taking @xmath5 to be the cycle @xmath216 and @xmath4 to be the reverse @xmath217 . let @xmath218 be a path from @xmath46 to @xmath219 . define the intermediate vertices in the path to be the vertices @xmath220 . for each pair of vertices @xmath40 and @xmath41 we wish to calculate @xmath87 , the largest threshold @xmath55 for which @xmath40 and @xmath41 are connected by a path in @xmath130 .    for @xmath221 , let @xmath222 represent the largest value of the threshold @xmath55 for which @xmath130 contains a path from @xmath40 to @xmath41 with intermediate vertices in the set @xmath223 . from this definition , we have @xmath224 , the weighted adjacency matrix and @xmath225 . next we show that for @xmath226 , @xmath227 to see this , note that @xmath228 unless there is a more strongly connected path which goes through @xmath58 . such a path must first connect @xmath40 to @xmath58 , and then connect @xmath58 to @xmath41 , with both paths involving intermediate vertices in @xmath229 . this connection is broken in @xmath130 once the threshold @xmath55 is raised above the minimum of these two connections , that is when @xmath230 . the conclusion of the theorem follows by iterative application of eqn . [ recurse ] .    _ remarks on the proof of theorem [ warshall ] : _ to make the algorithm more memory efficient , we note that it is not necessary to store more than @xmath158 values for @xmath55 at any point . this stems from the fact that each iteration is calculated only from the results of the previous one , reducing the necessary storage to @xmath231 . this can be improved further by noting that if @xmath232 or @xmath233 then @xmath58 can not be an intermediate vertex in a path connecting @xmath40 to @xmath41 and hence @xmath228 . these @xmath234 index values are the only elements needed to calculate the @xmath58th iteration , and they themselves do not need to be updated . hence , the remaining elements in the matrix are needed only for their own update and can be safely over - written . a corollary to this is that the @xmath40 and @xmath41 loops in the algorithm can be completed in any order or even in parallel . note that this algorithm works whether or not the weight matrix @xmath91 is allowed to contain loops . irrespective of whether loops are permitted or not , @xmath235 represents the largest value of the edge threshold for which node @xmath40 is contained in a cycle .    for theorem [ compute ] we require a series of lemmas :    [ converge ] the effects @xmath236 are well - defined and satisfy @xmath89 . we show the sum in eqn . [ effects ] converges absolutely . since all terms are non - negative , it is sufficient to prove that , for each @xmath79 such that @xmath237 , the sum is bounded above . consider the partial sums @xmath238 if eqn . [ effects ] diverges , so must @xmath239 since all paths are of finite length , so it is sufficient to prove @xmath240 is bounded above by one as @xmath241 . we proceed inductively , with base case @xmath242 suppose @xmath243 . then for @xmath244 we have @xmath245 since a path @xmath39 of length @xmath246 can be decomposed into a path from @xmath247 to @xmath248 and an edge from @xmath248 to @xmath249 . therefore @xmath250 as required . the case where @xmath251 is similar , leading to @xmath252 from which we again conclude @xmath250 . therefore @xmath253 for all @xmath254 by induction . [ equivalent ] effects , as defined in eqn . [ effects ] , satisfy ( i ) @xmath255 for all @xmath256 s.t . @xmath257 , ( ii ) @xmath258 for all @xmath256 s.t . @xmath237 . the first statement follows immediately from eqn . [ effects ] . for the second statement , consider two cases : firstly , for @xmath79 such that @xmath244 we have @xmath259 note that absolute convergence ( lemma [ converge ] ) ensures the manipulation of infinite sums is valid . the proof for @xmath251 is similar but requires slightly more care : @xmath260    [ character ] define a matrix @xmath138 by ( i ) @xmath139 , ( ii ) for @xmath261 and @xmath141 , set @xmath140 , ( iii ) @xmath143 otherwise . then the conclusions of lemma [ equivalent ] are equivalent to the following : for each @xmath40 , the vector @xmath262 where @xmath263 satisfies @xmath264 . equivalence may be verified directly . suppose @xmath262 satisfies @xmath264 . then for all @xmath58 we must have @xmath265 . [ nonzero ]    suppose not . then there exists @xmath58 such that ( i ) @xmath266 and ( ii ) @xmath267 is maximal . without loss of generality @xmath261 since otherwise @xmath268 . then @xmath269 for all @xmath141 , since @xmath270 and @xmath271 . by induction on a path from @xmath40 to @xmath58 we arrive at @xmath272 , contradicting ( i ) . there exists a unique solution to @xmath264 with @xmath273 .    _ existence : _ the @xmath40th row of @xmath138 contains only zeros , except for the @xmath40th entry which is equal to 1 . hence the characteristic polynomial contains a root ( eigenvalue ) @xmath274 with corresponding eigenvector @xmath275 . from lemma [ nonzero ] we must have @xmath276 ( else @xmath277 for all @xmath41 , implying that @xmath278 ) . taking @xmath279 proves existence . _ uniqueness : _ suppose @xmath262 and @xmath280 both satisfy the criteria . then @xmath281 is also an eigenvector of @xmath138 with unit eigenvalue . from lemma [ nonzero ] we have @xmath282 for all @xmath58 , implying that @xmath283 . together lemmas 1 - 5 prove that the effect matrix @xmath98 exists and is unique . moreover , the @xmath40th row @xmath137 of @xmath100 may be computed as the unique eigenvector of @xmath138 corresponding to unit eigenvalue .    for moderate dimensional matrices @xmath138 , eigenvectors may be calculated using any valid algorithm . one such algorithm , suitable for high dimensional problems , is the `` power iteration '' method . specifically we compute the leading eigenvector @xmath262 of @xmath138 as @xmath284 efficient computation in this setting is reviewed in @xcite . banerjee , a. , jost , j. ( 2009 ) graph spectra as a systematic tool in computational biology . _ discrete appl math _ * 157*(10):2425 - 2431 . berkhin , p. ( 2005 ) a survey on pagerank computing , _ internet mathematics _ * 2*(1):73 - 120 . breitkreutz _ et al . _ ( 2012 ) molecular signaling network complexity is correlated with cancer patient survivability , _ proc natl acad sci usa _ * 109*(23):9209 - 9212 . cantone _ et al . _ ( 2009 ) a yeast synthetic network for in vivo assessment of reverse - engineering and modeling approaches , _ cell _ * 137*(1):172 - 181 . chuang _ et al . _ ( 2007 ) network - based classification of breast cancer metastasis , _ mol syst biol _ * 3*:140 . dash , d. ( 2003 ) caveats for causal reasoning with equilibrium models , phd thesis , intelligent systems program , university of pittsburgh . davis , j. , goadrich , m. ( 2006 ) the relationship between precision - recall and roc curves . _ proceedings of the 23rd international conference on machine learning . _ acm press new york pp.233 - 240    drummond , c. , holte , r.c . ( 2004 ) what roc curves ca nt do ( and cost curves can ) . 1st workshop roc analysis in ai _ , pp.19 - 26 . fawcett , t. ( 2006 ) an introduction to roc analysis . _ pattern recogn _ * 27 * , 861 - 874 . feiglin _ et al . _ ( 2012 ) static network structure can be used to model the phenotypic effects of perturbations in regulatory networks . _ bioinformatics _ * 28*(21):2811 - 2818 . feizi _ et al . _ ( 2013 ) network deconvolution as a general method to distinguish direct dependencies in networks , _ nat biotechnol _ * 31*:726 - 733 . goadrich , m. , oliphant , l. , shavlik , j. ( 2004 ) learning ensembles of first - order clauses for recall - precision curves : a case study in biomedical information extraction . _ proceedings of the 14th international conference on inductive logic programming ( ilp)_.    heiser _ et al . _ ( 2012 ) subtype and pathway specific responses to anticancer compounds in breast cancer . _ proc natl acad sci usa _ * 109*(8):2724 - 2729 . ( 2012 ) bayesian inference of signaling network topology in a cancer cell line . _ bioinformatics _ * 28*(21):2804 - 2810 .    iwasaki , y. , simon , h.a . ( 1994 ) causality and model abstraction . _ artif intell _ * 67*(1 ) , 143 - 194 . jeong _ et al . _ ( 2000 ) the large - scale organization of metabolic networks . _ nature _ * 407*(6804):651 - 654 . johannes _ et al . _ ( 2010 ) integration of pathway knowledge into a reweighted recursive feature elimination approach for risk stratification of cancer patients . _ bioinformatics _ * 26*(17):2136 - 2144 . jurman _ et al . _ ( 2011a ) biological network comparison via ipsen - mikhailov distance . arxiv:1109.0220 . jurman , g. , visintainer , r. , furlanello , c. ( 2011b ) an introduction to spectral distances in networks . _ fr art in _ * 226*:227 - 234 . lakhina _ et al . _ ( 2004 ) structural analysis of network traffic flows . _ proceedings of international conference on measurement and modeling of computer systems , acm new york usa _ , pp 61 - 72 . maathuis _ et al . _ ( 2010 ) predicting causal effects in large - scale systems from observational data . _ nat methods _ * 7*(4):247 - 248 . marbach _ et al . _ ( 2009 ) generating realistic in silico gene networks for performance assessment of reverse engineering methods . _ j comp biol _ * 16*(2):229 - 239 . marbach _ et al . _ ( 2010 ) revealing strengths and weaknesses of methods for gene network inference . _ proc natl acad sci usa _ * 107*(14):6286 - 6291 . marbach d , _ et al . _ ( 2012 ) wisdom of crowds for robust gene network inference . _ nat methods _ * 9*:796 - 804 . milenkovi _ et al . _ ( 2009 ) optimized null models for protein structure networks . _ plos one _ * 4*(6):e5967 . ( 2005 ) generank : using search engine technology for the analysis of microarray experiments . _ bmc bioinformatics _ * 6*:233 .    nelander _ et al . _ ( 2008 ) models from experiments : combinatorial drug perturbations of cancer cells . _ mol syst biol _ * 4*(1):216 . oates , c. , mukherjee , s. ( 2012a ) network inference and biological dynamics . _ ann appl stat _ * 6*(3):1209 - 1235 . page _ et al . _ ( 1999 ) the pagerank citation ranking : bringing order to the web . _ technical report , stanford infolab . _ pearl , j. ( 2000 ) causality : models , reasoning , and inference . _ cambridge university press , cambridge uk . _    peters , j. , bhlmann , p. ( 2013 ) structural intervention distance ( sid ) for evaluating causal graphs . arxiv:1306.1043 . prill _ et al . _ ( 2010 ) towards a rigorous assessment of systems biology models : the dream3 challenges . _ plos one _ * 5*(2):e9202 .    prill _ et al . _ ( 2011 ) crowdsourcing network inference : the dream predictive signaling network challenge . _ sci signal _ * 4*(189):mr7 . scutari , m. , nagarajan , r. ( 2013 ) identifying significant edges in graphical models of molecular networks . _ artif intell med _ * 57*(3):207 - 217 . simon , n. , tibshirani , r. ( 2012 ) comment on `` detecting novel associations in large datasets '' by reshef _ et al._. _ technical report , stanford , ca , usa . _    stdler , n. , mukherjee , s. ( 2013 ) two - sample testing in high - dimensional models . arxiv:1210.4584 . tong _ et al . _ ( 2004 ) global mapping of the yeast genetic interaction network . _ science _ * 303*(5659):808 - 813 . wang _ et al . _ ( 2008 ) motif - directed network component analysis for regulatory network inference . _ bmc bioinformatics _ * 9*(suppl . 1):s21 . warshall , s. ( 1962 ) a theorem on boolean matrices . _ j acm _ * 9*(1):11 - 12 . weile _ et al . _ ( 2012 ) bayesian integration of networks without gold standards . _ bioinformatics _ * 28*(11):1495 - 1500 . winter , c. ( 2012 ) google goes cancer : improving outcome prediction for cancer patients by network - based ranking of marker genes . _ plos comput biol _ * 8*(5):e1002511 . yates , p.d . , mukhopadhyay , n.d . ( 2013 ) an inferential framework for biological network hypothesis tests . _ bmc bioinformatics _ * 14*(1):94 . for mss2 only , the analogue of the confusion matrix does not respect monotonicity of the entries tp , fp , tn , fn with respect to varying threshold parameter @xmath55 . as a consequence both the roc and pr curves constructed by interpolation have the potential to exhibit self - intersection and hence there may exist estimates @xmath4 such that the area @xmath20 under the associated roc and pr curves ( auc ) need not be bounded by @xmath285 , invalidating the definition of a score function having image in @xmath54 $ ] . to construct a consistent performance measure we instead define auc as follows : let @xmath286 denote the coordinates of points on the curve whose auc is to be calculated . reorder the sequence as @xmath287 such that the x - coordinates form an increasing sequence @xmath288 . then auc is defined using the trapezium rule as @xmath289 . note that whilst an ordering @xmath290 may in general be non - unique , the expression for @xmath20 does not depend on which particular ordering is selected . the ` net_assess ` package for matlab r2013b is provided to compute all of the scores and associated @xmath11-values discussed in this paper . in the case of mss2 we compute roc and pr curves based on 100 uniformly spaced thresholds @xmath291 defined implicitly by @xmath292 . this package can be used as shown in the following example :                typical computational times for the package , based on the dream5 data analysis performed in this paper , are displayed in supp . [ times ] . note that local scores require @xmath158 operations to evaluate , whereas mss1 requires @xmath86 and mss2 requires @xmath293 . we briefly summarise the approach of @xcite that assigns each network inference algorithm an `` overall score '' . for each network inference algorithm a combined auroc score was calculated as the ( negative logarithm of the ) geometric mean over @xmath11-values corresponding to 3 individual auroc scores ( _ in silico _ , _ e. coli _ , _ s. cerevisiae _ respectively ) . likewise a combined aupr score was assigned to each network inference algorithm . for each algorithm an overall score was computed as the arithmetic mean of the combined auroc and combined aupr scores . note that @xcite report the overall score over all 3 datasets , whereas the performance scores which we report in this paper were computed for each dataset individually . note also that @xmath11-values used by @xcite were computed using a common null distribution , rather than the estimator - specific nulls @xmath121 that are used in this paper . supp . figs . [ silico bar ] , [ ecoli bar ] , [ sc bar ] display the scores @xmath20 obtained by each of the 36 dream methodologies on , respectively , the _ in silico _ , _ e. coli _ and _ s. cerevisiae _ datasets . [ dream2 ] compares results for the dream5 challenge data based on both local and multi - scale scores and roc analysis . [ meta5 ] displays both inferred benchmark topology for the _ in silico _ dataset using _
graphical models are widely used to study complex multivariate biological systems . 
 network inference algorithms aim to reverse - engineer such models from noisy experimental data . 
 it is common to assess such algorithms using techniques from classifier analysis . 
 these metrics , based on ability to correctly infer individual edges , possess a number of appealing features including invariance to rank - preserving transformation . 
 however , regulation in biological systems occurs on multiple scales and existing metrics do not take into account the correctness of higher - order network structure .    in this paper novel performance scores 
 are presented that share the appealing properties of existing scores , whilst capturing ability to uncover regulation on multiple scales . 
 theoretical results confirm that performance of a network inference algorithm depends crucially on the scale at which inferences are to be made ; in particular strong local performance does not guarantee accurate reconstruction of higher - order topology . applying these scores to a large corpus of data from the dream5 challenge , 
 we undertake a data - driven assessment of estimator performance . 
 we find that the `` wisdom of crowds '' network , that demonstrated superior local performance in the dream5 challenge , is also among the best performing methodologies for inference of regulation on multiple length scales . 
 matlab r2013b code ` net_assess ` is provided as supplement . 
 key words : performance assessment , multi - scale scores , network inference .