Pattern vectors from algebraic graph theory

PatternVectorsfromAlgebraicGraphTheoryRichardC.Wilson,EdwinR.HancockDepartmentofComputerScience,UniversityofYork,YorkY015DD,UKBinLuo∗AnhuiUniversity,P.R.ChinaAbstractGraphstructureshaveprovedcomputationallycumbersomeforpatternanaly-sis.Thereasonforthisisthatbeforegraphscanbeconvertedtopatternvectors,correspondencesmustbeestablishedbetweenthenodesofstructureswhicharepotentiallyofdifferentsize.Toovercomethisproblem,inthispaperweturntothespectraldecompositionoftheLaplacianmatrix.WeshowhowtheelementsofthespectralmatrixfortheLaplaciancanbeusedtoconstructsymmetricpolynomialsthatarepermutationinvariants.Thecoefficientsofthesepolynomialscanbeusedasgraphfeatureswhichcanbeencodedinavectorialmanner.Weextendthisrep-resentationtographsinwhichthereareunaryattributesonthenodesandbinaryattributesontheedgesbyusingthespectraldecompositionofaHermitianprop-ertymatrixthatcanbeviewedasacomplexanalogueoftheLaplacian.Toembedthegraphsinapatternspace,weexplorewhetherthevectorsofinvariantscanbeembeddedinalowdimensionalspaceusinganumberofalternativestrategiesincludingprincipalcomponentsanalysis(PCA),multidimensionalscaling(MDS)andlocalitypreservingprojection(LPP).Experimentally,wedemonstratethattheembeddingsresultinwelldefinedgraphclusters.Ourexperimentswiththe∗ThisresearchispartiallysupportedbytheNationalNaturalScienceFoundationofChina(No.60375010)1spectralrepresentationinvolvebothsyntheticandrealworlddata.Theexperi-mentswithsyntheticdatademonstratethatthedistancesbetweenspectralfeaturevectorscanbeusedtodiscriminatebetweengraphsonthebasisoftheirstructure.Therealworldexperimentsshowthatthemethodcanbeusedtolocateclustersofgraphs.1IntroductionTheanalysisofrelationalpatterns,orgraphs,hasproventobeconsiderablymoreelu-sivethantheanalysisofvectorialpatterns.Relationalpatternsarisenaturallyintherepresentationofdatainwhichthereisastructuralarrangement,andareencounteredincomputervision,genomicsandnetworkanalysis.Oneofthechallengesthatarisesinthesedomainsisthatofknowledgediscoveryfromlargegraphdatasets.Thetoolsthatarerequiredinthisendeavourarerobustalgorithmsthatcanbeusedtoorganise,queryandnavigatelargesetsofgraphs.Inparticular,thegraphsneedtobeembed-dedinapatternspacesothatsimilarstructuresareclosetogetheranddissimilaronesarefarapart.Moreover,ifthegraphscanbeembeddedonamanifoldinapatternspace,thenthemodesofshapevariationcanbeexploredbytraversingthemanifoldinasystematicway.Theprocessofconstructinglowdimensionalspacesormanifoldsisaroutineprocedurewithpattern-vectors.Avarietyofwellestablishedtechniquessuchasprincipalcomponentsanalysis[12],multidimensionalscaling[7]andindepen-dentcomponentsanalysis,togetherwithmorerecentlydevelopedonessuchaslocallylinearembedding[28],isomap[36]andtheLaplacianeigenmap[2]existforsolvingtheproblem.Inadditiontoprovidinggenericdataanalysistools,thesemethodshavebeenextensivelyexploitedincomputervisiontoconstructshape-spacesfor2Dor3Dobjects,andinparticularfaces,representedusingcoordinateandintensitydata.Collectivelythesemethodsaresometimesreferredtoasmanifoldlearningtheory.However,therearefewanalogousmethodswhichcanbeusedtoconstructlowdimensionalpatternspacesormanifoldsforsetsofgraphs.Therearetworeasonswhypattern-vectorsaremoreeasilymanipulatedthangraphs.2First,thereisnonaturalorderingforthenodesinagraph,unlikethecomponentsofavector.Hence,correspondencestoareferencestructuremustbeestablishedasaprerequisite.Thesecondproblemisthatthevariationinthegraphsofaparticularclassmaymanifestitselfassubtlechangesinstructure,whichmayinvolvedifferentnumbersofnodesordifferentedgestructure.Evenifthenodesortheedgesofagraphcouldbeencodedinavectorialmanner,thenthevectorswouldbeofvariablelength.Onewayofcircumventingtheseproblemsistodevelopgraph-clusteringmethodsinwhichanexplicitclassarchetypeandcorrespondenceswithitaremaintained[25,31].Graphclusteringisanimportantprocesssinceitcanbeusedtostructurelargedatabasesofgraphs[32]inamannerthatrendersretrievalefficient.Oneoftheproblemsthathindersgraphclusteringistheneedtodefineaclassarchetypethatcancaptureboththesalientstructureoftheclassandthemodesofvariationcontainedwithinit.Forinstance,Munger,BunkeandJiang[22]haverecentlytakensomeimportantstepsinthisdirectionbydevelopingageneticalgorithmforsearchingformediangraphs.Variationsinclassstructurecanbecapturedandlearnedprovidedasuitableprobabilitydistributioncanbedefinedoverthenodesandedgesofthearchetype.Forinstance,therandomgraphsofWong,ConstantandYou[40]capturethisdistributionusingadiscretelydefinedprobabilitydistribution,andBagdanovandWorring[1]haveovercomesomeofthecomputationaldifficultiesassociatedwiththismethodbyusingcontinuousGaussiandistributions.ThereisaconsiderablebodyofrelatedliteratureinthegraphicalmodelscommunityconcernedwithlearningthestructureofBayesiannetworksfromdata[11].Moreover,inrecentworkwehaveshownthatifreliablecorrespondenceinformationistohandthentheedgestructureofthegraphcanbeencodedasalong-vectorandembeddedinalowdimensionalspaceusingprincipalcomponentsanalysis[20].Analternativetousingaprobabilitydistributionoveraclassarchitype,istousepairwise