A SINful Approach to Gaussian Graphical Model Sele

ASINfulApproachtoGaussianGraphicalModelSelectionMATHIASDRTONANDMICHAELD.PERLMANAbstract.MultivariateGaussiangraphicalmodelsaredenedintermsofMarkovprop-erties,i.e.,conditionalindependencesassociatedwiththeunderlyinggraph.Thus,modelselectioncanbeperformedbytestingtheseconditionalindependences,whichareequiva-lenttospeciedzeroesamongcertain(partial)correlationcoecients.Forconcentrationgraphs,covariancegraphs,acyclicdirectedgraphs,andchaingraphs(bothLWFandAMP),weapplyFisher'sz-transformation,Sidak'scorrelationinequality,andHolm'sstep-downprocedure,tosimultaneouslytestthemultiplehypothesesobtainedfromtheMarkovproperties.Thisleadstoasimplemethodformodelselectionthatcontrolstheoverallerrorrateforincorrectedgeinclusion.Inpractice,weadvocatepartitioningthesimultaneousp-valuesintothreedisjointsets,asignicantsetS,anindeterminatesetI,andanon-signicantsetN.ThenourSINmodelselectionmethodselectstwographs,agraphwhoseedgescorrespondtotheunionofSandI,andamoreconservativegraphwhoseedgescorrespondtoSonly.Priorinformationaboutthepresenceand/orabsenceofparticularedgescanbeincorporatedreadily.1.IntroductionGraphicalmodelsusegraphstorepresentdependenciesbetweenstochasticvariables.Thisgraphicalapproachyieldsdependencemodelsthatareeasilyvisualizedandcommu-nicated.Ingraphicalmodelselectiononewishestorecoverthegraphthatdeterminesthedependencestructureofasetofvariablesfromdata.Twoapproachestographicalmodelselectionarecommonlytaken.Oneisascore-basedsearchinwhichonemovesinthespaceofconsideredgraphicalmodelsandscoresthedier-entmodelsbyacriterionthatcaptureshowwellthemodeltstheobserveddata;e.g.seeChickering(2002).Onesuchscoringcriterionis,forexample,theBayesianInformationCriterion.Thesecondapproachistotesttheconditionalindependencesthatareimpliedbymissingedges.Thisapproachhasbeenconsidered,forexample,bySpirtesetal.(2000).Inthispaper,wefollowthelatterapproachoftestingconditionalindependencesandshowhowinthecaseofcontinuousvariableswithamultivariatenormaldistributionthismultipletestingproblemcanbesolvedinasimultaneousway.ThisleadstoasimplemethodforDate:April9,2004.Keywordsandphrases.Graphicalmodelselection,simultaneoustests,concentrationgraphs,covariancegraphs,ADG,DAG,chaingraphs.12MATHIASDRTONANDMICHAELD.PERLMANmodelselectionthatcontrolstheoverallerrorrateforincorrectedgeinclusion.Sinceourmethodisbasedonthepartitioningofthesimultaneousp-valuesintoasignicantsetS,anindeterminatesetI,andanon-signicantsetN,wecallthismethodologySINmodelselection.Thisarticleisorganizedasfollows.Section2givesabriefoverviewofseveralimportanttypesofGaussiangraphicalmodelsthathavebeenconsideredintheliterature.InSection3,wedescribeandimproveSINmodelselectionforundirectedgraphsconcentrationgraphs,asintroducedinDrtonandPerlman(2003,2004).InSection4,weshowhowSINmodelselectioncanbeadaptedtobidirectedgraphscovariancegraphs.InSection5,weturntothecaseofacyclicdirectedgraphs(ADGDAG),forwhichSINmodelselectioncanbecarriedoutifanaprioritotalordering(e.g.time-ordering)ofthevariablesisavailable.InSection6,weconsiderchaingraphs(bothLWFandAMP),forwhichSINmodelselectionisapplicableifthevariablescanbemeaningfullyblockedintoatotallyordereddependencechain.Thismeansthatatotalorderingoftheblocksisspeciedapriori,butnoorderingofthevariableswithineachblockisspecied.Finally,inSection7,weshowhowpriorinformationabouttheabsenceorpresenceofcertainedgescanbeincorporatedintoSINmodelselection,illustratedbythecaseofundirectedgraphs.SomeproofsaredeferredtotheAppendix.2.GaussiangraphicalmodelsLetY:=(Y1;:::;Yp)t2RpbearandomvectordistributedaccordingtothemultivariatenormaldistributionNp(;).Itisassumedthroughoutthatthecovariancematrixisnonsingular.LetG:=(V;E)beagraphwithvertexsetV:=f1;:::;pgandedgesetE.IftheverticesVofthisgraphareidentiedwiththevariablesY1;:::;Yp,thentheedgesetEinducesconditionalindependencesviaso-calledMarkovproperties.Inthissection,wereviewseveraldierenttypesofgraphsthathavebeenconsideredintheliteratureandshowhowtheirMarkovpropertiesdeterminestatisticalmodels.ForintroductionstographicalmodelsseethemonographsbyEdwards(2000),Lauritzen(1996),andWhittaker(1990)thatprovidegeneraltheoryaswellasmethodologyforparameterestimationandmodeltesting.2.1.Undirectedgraphs.LetG=(V;E)beanundirectedgraph(UG)whoseedgesarespeciedbytheedgeindicatorsE=(eijj1i6=jp),whereeij=eji=1or0accordingtowhetherverticesiandjareadjacentinGornot.ThepairwiseundirectedMarkovpropertydeterminedbyGstatesthatforall1ijp,eij=0=)Yi??YjjYVnfi;jg:(2.1)(FortheUGinFigure1(a),(2.1)speciesthatY1??Y4jY2;Y3andY2??Y3jY1;Y4.)SinceYNp(;),Yi??YjjYVnfi;jg()ij:V=0;(2.2)GAUSSIANGRAPHICALMODELSELECTION3(a)1243tttt(b)1243-66-??tttt(c)1243??--tttt(d)1243??ttttFigure1.(a)Anundirectedgraph,(b)abidirectedgraph,(c)anacyclicdirectedgraph,and(d)achaingraph.whereij:V=ijpiijj(2.3)denotestheij-thpartialcorrelation,i.e.,thecorrelationbetweenYiandYjintheircondi-tionaldistributiongivenYVnfi;jg;compareLauritzen(1996,p.130).Here,1:=fijgistheconcentrationprecisionmatrix.Therefore,foranUGG=(V;E),theGaussiangraphicalmod