normporntime

AQuantum-inspiredEntropicKernelforMultipleFinancialTimeSeriesAnalysisLuBai1,2,LixinCui1,2,YueWang1,3,YuhangJiao1andEdwinR.
Hancock41CentralUniversityofFinanceandEconomics,Beijing,China2ChinaCenterforFintechStudies,CentralUniversityofFinanceandEconomics,Beijing,China3StateKeyLaboratoryofCognitiveIntelligence,iFLYTEK,Hefei,China4DepartmentofComputerScience,UniversityofYork,York,UK{bailucs,cuilixin,wangyuecs}@cufe.
edu.
cn,edwin.
hancock@york.
ac.
ukAbstractNetworkrepresentationsarepowerfultoolsfortheanalysisoftime-varyingnancialcomplexsystem-sconsistingofmultipleco-evolvingnancialtimeseries,e.
g.
,stockprices,etc.
Inthiswork,wede-velopanewkernel-basedsimilaritymeasurebe-tweendynamictime-varyingnancialnetworks.
Ourideasistotransformeachoriginalnancialnetworkintoquantum-basedentropytimeseriesandcomputethesimilaritymeasurebasedontheclassicaldynamictimewarpingframeworkassoci-atedwiththeentropytimeseries.
Theproposedmethodbridgesthegapbetweengraphkernelsandtheclassicaldynamictimewarpingframeworkformultiplenancialtimeseriesanalysis.
Experi-mentsontime-varyingnetworksabstractedfrom-nancialtimeseriesofNewYorkStockExchange(NYSE)databasedemonstratethatourapproachcaneffectivelydiscriminatetheabruptstructuralchangesintermsoftheextremenancialevents.
1IntroductionNetworkrepresentationsarepowerfultoolstoanalyzethenancialmarketthatcanbeconsideredasatime-varyingcomplexsystemconsistingofmultipleco-evolvingnan-cialtimeseries[ZhangandSmall,2006;Nicolisetal.
,2005;Shimadaetal.
,2008;Silvaetal.
,2015],e.
g.
,thestockmar-ketwiththetradeprice.
Thisisbasedontheideathatthestructureoftheso-calledtime-varyingnancialnetwork-s[BullmoreandSporns,2009]inferredfromthecorrespond-ingtimeseriesofthesystemcanrepresentricherphysicalin-teractionsbetweensystementitiesthantheoriginalindividualtimeseries.
Onemainobjectiveofexistingapproachesistodetecttheextremenancialeventsthatcansignicantlyin-uencethenetworkstructures[Baietal.
,2020].
Inmachinelearning,graphkernelshavebeenwidelyem-ployedforanalyzingstructureddatarepresentedbygraphsornetworks[Xuetal.
,2018].
Themainadvantageofem-ployinggraphkernelsisthattheycanofferusaneffec-tivewayofmappingthenetworkstructuresintoahighdi-mensionalspacesothatthestandardkernelmachineryforCorrespondingAuthorvectorialdataisapplicabletothenetworkanalysis.
Mostexistinggraphkernelsarebasedontheideaofdecompos-inggraphsornetworksintosubstructuresandthenmea-suringpairsofisomorphicsubstructures[Haussler,1999],e.
g.
,graphkernelsbasedoncountingpairsofiso-morphica)paths[BorgwardtandKriegel,2005],b)walk-s[Kashimaetal.
,2003],andc)subgraphs[Baietal.
,2015b]orsubtrees[Shervashidzeetal.
,2009].
Unfortunately,direct-lyadoptingthesegraphkernelstoanalyzethetime-varyingnancialnetworksinferredfromoriginalvectorialtimese-riestendstobeelusive.
Thisisbecausethesenancialnetworkstructuresarebynaturecompleteweightedgraph-s[Yeetal.
,2015;Baietal.
,2020],whereeachvertexrepre-sentsanindividualtimeseriesofastockandisadjacenttoallremaindervertices,andeachedgerepresentstheinterac-tion(e.
g.
,thecorrelationordistance)betweenapairofco-evolvingnancialtimeseries.
Itisdifculttodecomposeacompleteweightedgraphintotherequiredsubstructures,andthusinuencestheeffectivenessofmostexistinggraphker-nelsfornancialnetworkanalysis.
Onewaytoaddresstheaforementionedproblemistocon-structsparsestructuresoftheoriginaltime-varyingnancialnetworks.
Withthisscenario,Cuietal.
[Cuietal.
,2018]haveusedthewell-knownthreshold-basedapproachtopre-servetheweightededgesfallingintothelarger10%oftheweights,andemployedtheclassicalgraphkernelsassociat-edwiththeresultingsparsestructuresfornancialnetworkanalysis.
Baietal.
[Baietal.
,2020]haveabstractedthemin-imumormaximumspanningtreesassociatedwiththecom-mutetimematrixoftheoriginalcompleteweightednancialnetworks,anddevelopedanovelquantumgraphkerneloverthespanningtreesofthenancialnetworks.
Although,boththeapproachesovercometherestrictionofemployinggraphkernelsfortime-varyingnancialnetworkanalysis,theirre-quiredsparsestructuresalsoleadtosignicantinformationloss.
Sincemanyweightededgesoftheoriginalcompleteweightednancialnetworksarediscarded.
Insummary,ana-lyzingtime-varyingnancialnetworksassociatedwithgraphkernelsstillremainschallenges.
Theaimofthispaperistoovercometheaforementionedproblemsbydevelopinganewkernelmeasurebetweentime-varyingnetworksformultipleco-evolvingnancialtimese-riesanalysis.
Overall,themaincontributionsarethreefold.
First,forafamilyoftime-varyingnancialnetwork-s,wecommencebycomputingtheaveragemixingma-trix[Godsil,2013]tosummarizethetime-averagedbe-haviourofcontinuous-timequantumwalks(CTQW)evolvedonthenetworkstructures.
ThereasonofusingtheCTQWisthatitnotonlyaccommodatescompleteweightedgraphs,butalsobetterreectsrichernancialnetworkcharacteris-ticsthantheclassicalrandomwalks[Baietal.
,2015a](seedetailsinSectionII-A).
WeshowhowtheaveragemixingmatrixoftheCTQWallowstocomputeaquantum-baseden-tropyforeachvertexofthenancialnetworksandrepresentstheoriginalnetworksasquantumentropytimeseries.
Second,witheachpairoftime-varyingnancialnetworkstohand,wedeneaQuantum-inspiredEntropicKernelbe-tweentheirquantumentropytimeseriesthroughtheclassicaldynamictimewarpingframework.
Theproposedkernelnotonlyaccommodatesthecompleteweightedgraphsthroughtheentropytimeseries,butalsobridgesthegapbetweengraphkernelsandtheclassicaldynamictimewarpingframe-workfortimeseriesanalysis(seedetailsinSectionIII-B).
Third,weperformtheproposedkernelontime-varyingnancialnetworksabstractedfrommultipleco-evolving-nancialtimeseriesofNewYorkStockExchange(NYSE)database.
Experimentsdemonstratethattheproposedap-proachcaneffectivelydiscriminatetheabruptstructuralchangesintermsoftheextremenancialevents.
2PreliminaryConceptsInthissection,webrieyreviewsomepreliminaryconcepts.
2.
1TheAverageMixingMatrixoftheCTQWThecontinuous-timequantumwalk(CTQW)isthequan-tumanalogueoftheclassicalcontinuous-timerandomwalk(CTRW)[FarhiandGutmann,1998].
TheCTQWmodelsaMarkoviandiffusionprocessovertheverticesofagraphthroughtheirtransitioninformation.
AssumeasamplegraphisG(V,E),whereVisthevertexsetandEistheedgeset.
SimilartotheclassicalCTRW,thestatespaceoftheCTQWisthevertexsetVanditsstateattimetisacom-plexlinearcombinationofthebasisstates|u,i.
e.
,|ψ(t)=∑u∈Vαu(t)|u,whereαu(t)∈Cand|ψ(t)∈C|V|aretheamplitudeandbothcomplex.
Furthermore,αu(t)αu(t)indi-catestheprobabilityoftheCTQWvisitingvertexuattimet.
∑u∈Vαu(t)αu(t)=1andαu(t)αu(t)∈[0,1],foral-lu∈V,t∈R+.
UnliketheclassicalCTRW,theCTQWevolvesbasedontheSchr¨odingerequation/t|ψt=iH|ψt,(1)whereHdenotesthesystemHamiltonian.
Inthiswork,weemploytheadjacencymatrixastheHamiltonian.
WhenaCTQWevolvesonthesamplegraphG(V,E),thebehaviourofthewalkattimetcanbesummarizedusingthemixingmatrix[Godsil,2013]M(t)=U(t)U(t)=eiHteiHt,(2)wheredenotestheSchur-Hadamardproductoftwoma-trices,i.
e.
,[AB]uv=AuvBuv.
SinceUisunitary,M(t)isadoublystochasticmatrixandeachentryM(t)uvindicatestheprobabilityoftheCTQWvisitingvertexvattimetwhenthewalkinitiallystartsfromvertexu.
How-ever,QM(t)cannotconverge,becauseU(t)isalsonorm-preserving.
Toovercomethisproblem,wecanenforcecon-vergencebytakingatimeaverage.
Specically,wetaketheCes`aromeananddenetheaveragemixingmatrixasQ=limT→∞∫T0QM(t)dt,whereeachentryQuvoftheav-eragemixingmatrixQrepresentstheaverageprobabilityforaCTQWtovisitvertexvstartingfromvertexu,andQisstilladoublystochasticmatrix.
Godsil[Godsil,2013]hasindicat-edthattheentriesofQarerationalnumbers.
WecaneasilycomputeQfromthespectrumoftheHamiltonianHthatcanbetheadjacencymatrixAofG.
Letλ1,λ|V|representthe|V|distincteigenvaluesofHandPjbethematrixrepre-sentationoftheorthogonalprojectionontheeigenspaceas-sociatedwiththeλj,i.
e.
,H=∑|V|j=1λjPj.
Then,werewritetheaveragemixingmatrixQasQ=|V|∑j=1PjPj.
(3)Remarks.
TheCTQWhasbeensuccessfullyemployedtodevelopnovelapproachesinmachinelearninganddatamin-ing[Baietal.
,2014;Baietal.
,2016],becauseofthericherstructurethantheirclassicalcounterparts.
Thereasonofuti-lizingtheCTQWinthisworkisthatthestatevectoroftheCTQWiscomplex-valuedanditsevolutionisgovernedbyatime-varyingunitarymatrix.
Bycontrast,thestatevec-toroftheclassicalCTRWisreal-valuedanditsevolutionisgovernedbyadoublystochasticmatrix.
Asaresult,thebehaviouroftheCTQWissignicantlydifferentfromtheirclassicalcounterpartandpossessesanumberofimportantproperties.
Forinstance,theCTQWallowsinterferencetotakeplace,andthusreducesthetotteringproblemarisingintheclassicalCTRW.
Furthermore,sincetheevolutionoftheCTQWisnotdominatedbythelowfrequencycomponentsoftheLaplacianspectrum,ithasbetterabilitytodistinguishdifferentgraphstructures.
Finally,theCTQWcanaccommo-datethecompleteweightedgraph,sincetheHamiltonianoftheCTQWcanbethecompleteweightedadjacencymatrix.
2.
2TheDynamicTimeWarpingFrameworkWereviewtheglobalalignmentkernelbasedonthedynamictimewarpingframeworkproposedin[Cuturi,2011].
LetTbeasetofdiscretetimeseriesthattakevaluesinaspaceX.
ForapairofdiscretetimeseriesP=(p1,pm)∈TandQ=(q1,qn)∈Twithlengthsmandnrespectively,thealignmentπbetweenPandQisdenedasapairofin-creasingintegralvectors(πp,πq)oflengthl≤m+n1,where1=πp(1)πp(l)=mand1=πq(1)≤···≤πq(l)=nsuchthat(πp,πq)isassumedtohaveuni-taryincrementsandnosimultaneousrepetitions.
Notethat,forPandQ,eachoftheirelementscanbeanobservationvectorwithxeddimensionsatatimestep.
Foranyindex1≤i≤l1,theincrementvectorofπ=(πp,πq)satises(πp(i+1)πp(i)πq(i+1)πq(i))∈{(01),(10),(11)}.
(4)Withintheframeworkoftheclassicaldynamictimewarp-ing[Cuturi,2011],thecoordinatesπpandπqofthealign-mentπdenethewarpingfunction.
AssumeA(m,n)cor-respondstoasetofallpossiblealignmentsbetweenPandQ,Cuturi[Cuturi,2011]hasproposedadynamictimewarp-inginspiredkernel,namelytheGlobalAlignmentKernel,byconsideringallthepossiblealignmentsinA(m,n).
Theker-nelisdenedaskGA(P,Q)=∑π∈A(m,n)eDP,Q(π),(5)whereDP,Q(π)isthealignmentcostgivenbyDP,Q(π)=|π|∑i=1φ(pπp(i),qπq(i)),(6)andisdenedthroughalocaldivergenceφthatquantiesthediscrepancybetweeneachpairofelementspi∈Pandqi∈Q.
Ingeneral,φisdenedasthesquaredEuclideandistance.
Notethat,thekernelkGAmeasuresthequalityofboththeoptimalalignmentandallotheralignmentsπ∈A(m,n),thusitispositivedenite.
Moreover,kGAprovidesricherstatisticalmeasuresofsimilaritybyencapsulatingtheoverallspectrumofthealignmentcosts{DP,Q(π),π∈A(m,n)}.
Remarks.
ThedynamictimewarpingbasedGlobalAlign-mentKernelkGAisapowerfultoolforanalyzingvectori-altimeseries[Mikalsenetal.
,2018;Jain,2019].
ToextendkGAintographkerneldomains,Baietal.
[Baietal.
,2018]havedevelopedanestedgraphkernelbymeasuringkGAbetweenthedepth-basedcomplexitytracesofgraph-s[BaiandHancock,2014].
Specically,thecomplexitytraceofeachgraphiscomputedbymeasuringtheentropiesonafamilyofK-layerexpansionsubgraphsrootedatitscentroidvertex.
Although,thenestedgraphkerneloutperformslocalsubstructurebasedgraphkernels[Johanssonetal.
,2014]ongraphclassicationtasks.
Unfortunately,thenancialnet-worksarebynaturecompleteweightedgraphsanditisdif-culttodecomposesuchgraphsintorequiredexpansionsub-graphsrootedatthecentroidvertex.
Thus,directlypreform-ingthedynamictimewarpinginspiredgraphkernelfortime-varyingnancialnetworksstillremainschallenges.
3KernelsforTime-varyingNetworksInthissection,weproposeaQuantum-inspiredEntropicKer-nelbetweentime-varyingnetworksformultipleco-evolvingnancialtimeseriesanalysis.
Wecommencebycharacter-izingeachnancialnetworkasadiscretequantumentropytimeseriesthroughtheCTQW.
Moreover,wedenethenewkernelassociatedwiththeentropytimeseries,intermsoftheclassicaldynamictimewarpingframework[Cuturi,2011].
3.
1TheQuantumEntropyTimeSeriesWeintroducehowtocharacterizeeachnancialnetworkstructureasthequantumentropytimeseriesthroughtheC-TQW.
AssumeG={G1,Gp,Gq,GT}denotesafamilyoftime-varyingnancialnetworksextractedfromacomplexnancialsystemSwithaspecicsetofNco-evolvingnancialtimeseries,i.
e.
,thesystemhasaxednumberofcomponents(e.
g.
,stocks)co-evolvingwithtime.
Gp(Vp,Ep,Ap)isthesamplenetworkextractedfromthesys-temattimestepp.
ForGp,eachindividualvertexv∈Vprep-resentsacorrespondingtimeseriesofadifferentstock(e.
g.
,thestockprice),eachedgee∈Eprepresentstheinteraction(e.
g.
,distancesorcorrelations)betweenapairoftimeseries,andApistheinteractionbasedweightedadjacencymatrix.
Thisisapopularwayofmodellingthemultipleco-evolvingnancialtimeseriesasnetworkstructures[Silvaetal.
,2015;Baietal.
,2020].
Notethat,sincetheverticesofeachnan-cialnetworkGp∈GcorrespondtothesameNcomponentsofthesystemS,allthenetworksinGhavethesamevertexset,whereastheedgesetsEtarequitedifferentwithtimet.
Specically,foreachnancialnetworkGp(Vp,Ep,Ap)fromGattimep,werstcomputetheaveragematrixmatrixQpassociatedwiththeCTQWevolvedonGp.
Foreachi-thvertexvi∈Vp,thei-throwofQpgivesthetime-averagedprobabilitydistributionPifortheCTQWtovisitverticesv1,vN∈V(|Vp|=N)startingfromvi,i.
e.
,Pi={Pi(v1)Pi(vj)Pi(vN)}.
(7)wherePi(vj)=Qpi,jisthetime-averagedprobabilityoftheCTQWvisitingvjfromvi.
ThequantumbasedShannonen-tropy[Baietal.
,2016]ofvertexvicanbedenedasHS(vi)=∑vj∈VpPi(vj)logPi(vj).
(8)Asaresult,theentropycharacteristicvectorofGpassociatedwiththeentropiesoverallitsverticescanbedenedasEp={HS(v1)HS(vi)HS(vN)},(9)whereHS(vi)isthequantumShannonentropyofthei-thvertexviofGpassociatedwiththetime-averagedprobabilitydistributionresidingonthei-throwofQp.
Wemoveatimeintervalofwtimestepsoverallthetime-varyingnetworksofthenancialsystemStoconstructatime-varyingquantumentropytimeseriesforeachnetworkGpattimep.
Inthiswork,wesetthevalueofwas28.
Specically,foreachnetworkGp,wecomputeitsquantumentropytimeseriesStassociatedwithitstimewindowasSp={Epw+1|Etp+2|Es|Ep},(10)whereeachcolumnEsofSpistheentropycharacteristicvec-torofeachnetworkGs∈GattimesandisdenedbyEq.
(9).
s∈{pw+1,pw+2,p}.
Obviously,thequan-tumentropytimeseriesSpofGpencapsulatesafamilyofwtime-varyingentropycharacteristicvectorsfromGpw+1attimepw+1toGpattimet.
3.
2TheQuantum-inspiredEntropicKernelWedevelopanewkernelforanalyzingtime-varyingnan-cialnetworksbasedontheclassicaldynamictimewarpingframework.
Forapairoftime-varyingnetworksGp∈GandGq∈Gattimepandqrespectively,wecommencebycomputingtheirassociatedquantumentropytimeseriesasSp={Epw+1|Epw+2|Ep}andSq={Eqw+1|Eqw+2|Eq},(a)PathforQEK(b)PathforGAK(c)PathforWLSK(d)PathforDTQKFigure1:ColorPathofFinancialNetworksOverAllTradingDays.
basedonthedenitioninSection3.
1.
TheproposedQuantumInspiredEntropicKernelkQEKbetweenGpandGqiskQEK(Gp,Gq)=kGA(Sp,Sq)=∑π∈A(w,w)eDp,q(π),(11)wherekGAisthedynamictimewarpinginspiredGlobalAlignmentKernel(GAK)denedinEq.
(5),πisthewarp-ingalignmentbetweentheentropytimeseriesofGpandGq,A(w,w)isallpossiblealignmentsandDp,q(π)referstothealignmentcostobtainedviaEq.
(6).
Notethat,theproposedk-ernelkQEKispositivedenite.
ThisisbecausekQEKisbasedonthepositivedenitekernelkGA.
Remarks.
AlthoughtheproposedkernelkQEKisrelatedtothegeneralprinciplesoftheGAKkernel.
Theproposedker-nelkQEKstillpossessestwotheoreticaldifferenceswiththeGAKkernel.
First,theoriginalGAKkernelisonlydevelope-dforvectorialtimeseriesandthuscannotcapturestructuralrelationshipsbetweentimeseries.
Bycontrast,theproposedkernelkQEKisexplicitlyproposedfortime-varyingnancialnetworksthatencapsulatephysicalinteractionsbetweenpairsoftimeseries.
Second,unliketheGAKkernel,theproposedkernelkQEKisdenedbasedonthequantumentropytimeseriesthatisdevelopedthroughtheaveragemixingmatrixoftheCTQW.
AswehavestatedinSection2.
1,theCTQWcanaccommodatethecompleteweightedgraphandbetterdistin-guishdifferentnetworkstructuresintermsofthelowfrequen-cycomponentsofitsLaplacianspectrum.
Thus,theproposedkernelkQEKcannotonlyreectthephysicalinteractionsbe-tweentheoriginalvectorialnancialtimeseries,butalsocap-turericherstructureinformationthantheGAKkernelassoci-atedwiththeoriginaltimeseries.
Ontheotherhand,aswehavestated,thestate-of-the-artgraphkernelsmentionedinSection1andSection2.
2cannotdirectlyaccommodatecom-pleteweightedgraphs.
Thus,itisdifculttodirectlyperformthesegraphkernelsonthecompleteweightednancialnet-works,unlessonetransformsthesenetworksintosparsever-sions.
Bycontrast,theproposedkernelkQEKcanencapsu-latethewholestructuralinformationresidingonallweightededges.
Insummary,theproposedkernelkQEKbridgesthegapbetweenstate-of-the-artgraphkernelsandtheclas-sicaldynamictimewarpingframeworkfortime-varyingnetworks,providinganeffectivewaytoanalyzemultipleco-evolvingnancialtimeseries.
TimeComplexity.
Forapairofnetworkseachhavingnvertices,computingthekernelkQEKassociatedwithatimeintervalofwstepsrequirestimecomplexityO(n3+w2).
Be-cause,computingtheentropytimeseriesreliesonthespectraldecompositionofCTQWs,thushastimecomplexityO(n3).
Computingallpossiblealignmentsbetweentheentropytime(a)Dot-comBubbleforQEK(b)Dot-comBubbleforGAK(c)Dot-comBubbleforWLSK(d)Dot-comBubbleforDTQKFigure2:The3DkPCAEmbeddingsofDifferentKernelsforDot-comBubbleBurst.
seriesoverwtimestepshastimecomplexityO(w2).
Thus,kQEKhasapolynomialtimecomplexityO(n3+w2).
4ExperimentsofTimeSeriesAnalysisWeestablishaNYSEdatasetthatconsistsofaseriesoftime-varyingnancialnetworksbasedontheNewYorkStockEx-change(NYSE)database[Silvaetal.
,2015;Yeetal.
,2015].
TheNYSEdatabaseencapsulates347stocksandtheiras-sociateddailypricesover6004tradingdaysfromJanuary1986toFebruary2011,i.
e.
,themarketsystemhas347co-evolvingtimeseriesintermsofthedailystockprices.
ThepricesareallcorrectedfromtheYahoonancialdataset(http://nance.
yahoo.
com).
Toextractthenetworkrepresen-tations,weuseatimewindowof28daysandmovethiswin-dowalongtimetoobtainasequence(fromday29today6004)inwhicheachtemporalwindowcontainsatimese-riesofthedailyreturnstockpricesoveraperiodof28days.
Torepresenttradesbetweendifferentstocksasanetwork,foreachwindowwecomputetheEuclideandistancebetweenthetimeseriesofeachpairofstocksastheirconnection(edge)weight,followingthesamesettingin[Baietal.
,2020].
IthasbeenempiricallyshownthatthenancialnetworksassociatedwiththeEuclideandistancearemoreeffectivethanthoseas-sociatedwiththePearsoncorrelation.
Clearly,thisoperationyieldsatime-varyingnancialnetworkwithaxednumberof347verticesandvaryingedgeweightsforeachofthe5976tradingdays.
Eachnetworkisacompleteweightedgraph.
4.
1KernelEmbeddingsfromkPCAWeevaluatetheperformanceoftheproposedQuantum-inspiredEntropicKernel(QEK)ontime-varyingnetworksoftheNYSEdataset.
Specically,weanalyzewhethertheproposedQEKkernelcandistinguishthestructuralchangesofthenetworkevolutionwithtime.
Furthermore,wealsocomparetheproposedQEKkernelwiththreestate-of-the-artkernelmethods,thatis,thedynamictimewarpingin-spiredGlobalAlignmentKernel(GAK)fororiginalvectori-altimeseries[Cuturi,2011]andtwographkernelsfortime-varyingnancialnetworks.
Thegraphkernelsforcompar-isonsincludetheWeisfeiler-LehmanSubtreeKernel(WL-SK)[Shervashidzeetal.
,2009],andtheDiscrete-timeQuan-tumWalkKernel(DTQK)[Baietal.
,2020].
FortheGAKkernel,wealsoutilizeatimewindowof28daysforeachtrad-ingday.
FortheWLSKkernel,sinceitcanonlyaccommo-dateundirectedandunweightedgraphs,wetransformeacho-riginalnetworkintoaminimumspanningtreeandignoretheweightsonthepreservededges,followingthesamesettinginthework[Baietal.
,2020].
SincetheDTQKkernelcanac-commodateedgeweights,westraightforwardlyperformthiskernelontheoriginalnancialnetworks.
WeperformkernelPrincipleComponentAnalysis(kPCA)[Wittenetal.
,2011]onthekernelmatricesassociatedwithdifferentkernels,and(a)EnronIncidentforQEK(b)EnronIncidentforGAK(c)EnronIncidentforWLSK(d)EnronIncidentforDTQKFigure3:The3DkPCAEmbeddingsofDifferentKernelsforEnronIncident.
embedthenancialnetworksortheoriginaltimeseriesin-toavectorialpatternspace.
Wevisualizetheembeddingre-sultsusingtherstthreeprincipalcomponentsinFig.
1(a),Fig.
1(b),Fig.
1(c),andFig.
1(d)respectively.
Fig.
1exhibitsthepathsofthetime-varyingnancialnet-works(ortheoriginalvectorialtimeseries)indifferentker-nelspaces,andthecolorbarofeachsubgureindicatesthedateinthetimeseries.
WeobservethattheembeddingsfromtheproposedQEKkernelexhibitabettermanifoldstructure.
Moreover,onlytheproposedQEKkernelgeneratesacleartime-varyingtrajectoryandtheneighboringnetworkswithtimeareclosetogetherintheembeddingprincipalspace.
Bycontrast,thealternativemethodshardlyresultinatrajectoryandtheirembeddingstendtodistributeasclusters.
TofurtherdemonstratetheeffectivenessoftheQEKkernel,wecomparethedistancestress(DS)ofthenetworkembeddingsfromd-ifferentkernels.
Specically,theDSisdenedasDS=∑t∥xtxt1∥2∑t∥xtxtn∥2,(12)wheret=2,3,n,xtisthenetworkembeddingvectorattimet,andxtnisthenearestnetworkembeddingvectorofxtinthepatternspace.
Foreachembeddingvectorxtattimet,ifthenearestembeddingvectorisalwaystheembeddingvectoratlasttimestep(i.
e.
,xt1),thevalueofDSwillbe1.
Inotherwords,theDSvaluenearerto1indicatesthebetterMethodsQEKGAKWLSKDTQKDistanceStress1.
09922.
96775.
70534.
7174Table1:TheDistanceStressoftheNetworkEmbeddingsperformanceoftheembeddingstoformacleartime-varyingtrajectory.
TheDSvalueofeachkernelisshowninTable1.
Clearly,onlytheDSvalueoftheproposedQEKkernelisnearerto1,indicatingthebetterperformanceofpreservingtheordinalarrangementofthetime-varyingnetworks.
Totakeourstudyonestepfurther,weexploretheembed-dingsduringdifferentperiodsofthreewell-knownnancialevents,i.
e.
,theBlackMondayperiod(from15thJun1987to17thFeb1988),theDot-comBubbleperiod(from3rdJan1995to31stDec2001),andtheEnronIncidentperiod(from16thOct2001to11thMar2002).
Fordifferenker-nels,Fig.
2correspondstotheDot-comBubbleperiodandFig.
3totheEnronIncidentperiod.
Duetothelimitspace,wedonotexhibittheembeddingsforBlackMonday.
How-ever,wewillobservethesimilarphenomenonwithFig.
2andFig.
3.
TheseguresindicatethattheBlackMonday(17thOct,1987),theDot-comBubbleBurst(13rdMar,2000)andtheEnronIncidentperiodareallcrucialnancialevents,sig-nicantlyinuencingthestructuraltime-varyingevolutionofthenancialnetworksortheoriginalvectorialnancialtimeseries.
ExcludingtheGAKkernel,theembeddingpointsof(a)ForQEKonDot-com(b)ForDTQKonDot-comFigure4:KernelMatrixVisualizations.
MethodsQEKGAKWLSKDTQKBlackMonday0.
90500.
66730.
56670.
6506DotcomBubble0.
64730.
88820.
52790.
7903EnronIncident0.
85040.
49920.
50010.
7042AverageRand0.
80090.
68490.
53150.
7150Table2:TheRandIndexforK-meansClusteringontheEmbeddingPointsof100TradingDaysaroundEachFinancialCrisis.
theremainingkernelsbeforeandaftertheseeventsarewellseparatedintodistinctclusters,andthepointscorrespondingtothecrucialeventsaremidwaybetweentheclusters.
Toplaceouranalysisofthekernelembeddingclustersonamorequantitativefooting,foreachkernelweselectthek-ernelembeddingpointsof100tradingdaysaroundeach-nancialcrisis,i.
e.
,weselectembeddingpointsof50tradingdaysbeforeandaftereachcrisisdaterespectively.
WeapplytheK-meansmethodtothekernelembeddingsof100tradingdaysforeachkerneltoexplorewhethertheclusterscanbecorrectlyseparatedintermsofthetradingdaysbeforeandaf-tereachnancialcrisis.
WecalculatetheRandIndexfortheresultingclustersandtheRandindicatingeachkernelislistedinTable2.
Theresultsindicatethattheembeddingpointsas-sociatedwiththeproposedQEKkernelcanproducethebestclusters,i.
e.
,theembeddingpointsbeforeandafterthenan-cialcrisisareseparatedbetterthanotherkernels.
4.
2EvaluationsoftheKernelMatrixBasedontheearlierevaluation,wendthattheDTQKkernelisthemostcompetitivekernelwiththeproposedQEKkernel.
TofurtherrevealtheeffectivenessoftheproposedQEKker-nel,wevisualizethekernelmatricesofboththekernels.
Duetothelimitedspace,weonlycomputethekernelma-tricesbetweenthenetworksbelongingtotheDot-comBubbleperiod,andtheperiodencapsulate100tradingdays.
Infact,wewillobservesimilarphenomenonsifwecomputetheker-nelmatricesforothernancialeventperiods.
Specically,thekernelmatricesarevisualizedinFig.
4,whereboththex-axisandy-axisrepresentthetimesteps.
Notethat,tocomparethetwokernelsinthesamescaledHilbertspace,weconsiderthenormalizedversionofboththekernelsaskn(Gp,Gq)=k(Gp,Gq)√k(Gp,Gp)k(Gq,Gq),(13)whereknisthenormalizedkernel,andkiseithertheEDTWKortheWLSKkernel.
Asaresult,thekernelval-uesareallboundedbetween0to1,andthecolourbarbesideeachsubgureindicatesthekernelvalueofthekernelmatrix.
Fig.
4indicatesthatthekernelvaluestendtodecreasewhentheelementsofthekernelmatrixarefarawayfromthematrixtrace.
Thisisbecausesuchelementsarecomputedbetweentime-varyingnetworkshavinglongtimespansandtherearemorestructurechangeswhenthenetworkevolveswithalongtimevariation.
Thus,boththeQEKandDTQKkernelsreectstructuralevolutionsofnancialnetworkswithtime.
How-ever,ontheotherhand,thekernelvalueoftheDTQKkerneltendstodropdownmorequicklywhentheelementisalittlefarfromthetrace.
Bycontrast,thekernelvalueoftheQEKkerneltendtodecreasemoreslowlywhentheelementgetsfarerawayfromthetrace.
Thisobservationexplainswhyon-lytheproposedQEKkernelcanformacleartrajectorywithtimevariationandgeneratebetterclustersbeforeandafternancialcrisis,i.
e.
,theproposedQEKkernelcanbetterdis-tinguishandunderstandthestructuralchangesofthenetworkstructuresevolvingwithalongtimeperiod.
5ConclusionInthispaper,wehavedevelopedanewQuantum-inspiredEntropicKernelfortime-varyingcomplexnetworks.
Theproposedkernelbridgesthegapbetweengraphkernelsandtheclassicaldynamictimewarpingframeworkfortimese-riesanalysis.
ExperimentalanalysisofNYSEnancialtimeseriesdemonstratestheeffectivenessofthenewkernel.
AcknowledgmentsThisworkissupportedbytheNationalNaturalScienceFoun-dationofChina(Grantno.
61976235and61602535),theProgramforInnovationResearchinCentralUniversityofFi-nanceandEconomics,theYouthTalentDevelopmentSup-portProgrambyCentralUniversityofFinanceandEco-nomics(No.
QYP1908)andtheFoundationofStateKeyLaboratoryofCognitiveIntelligence(GrantNo.
COGOSC-20190002),iFLYTEK,China.
CorrespondingAuthor:LixinCui(cuilixin@cufe.
edu.
cn).
ThefourthauthorYuhangJiaomainlyparticipatedpartialdiscussionsforthiswork.
References[BaiandHancock,2014]LuBaiandEdwinR.
Hancock.
Depth-basedcomplexitytracesofgraphs.
PatternRecog-nition,47(3):1172–1186,2014.
[Baietal.
,2014]LuBai,LucaRossi,HorstBunke,andEd-winR.
Hancock.
Attributedgraphkernelsusingthejensen-tsallisq-differences.
InProceedingsofECML-PKDD,pages99–114,2014.
[Baietal.
,2015a]LuBai,LucaRossi,AndreaTorsello,andEdwinR.
Hancock.
Aquantumjensen-shannongraphkernelforunattributedgraphs.
PatternRecognition,48(2):344–355,2015.
[Baietal.
,2015b]LuBai,ZhihongZhang,ChaoyanWang,XiaoBai,andEdwinR.
Hancock.
Agraphkernelbasedonthejensen-shannonrepresentationalignment.
InPro-ceedingsofIJCAI,pages3322–3328,2015.
[Baietal.
,2016]LuBai,LucaRossi,LixinCui,andEd-winR.
Hancock.
Anovelentropy-basedgraphsignaturefromtheaveragemixingmatrix.
InProceedingsofICPR,pages1339–1344,2016.
[Baietal.
,2018]LuBai,LixinCui,LucaRossi,LixiangXu,XiaoBai,andEdwinHancock.
Local-globalnestedgraphkernelsusingnestedcomplexitytraces.
PatternRecogni-tionLetters,2018.
[Baietal.
,2020]LuBai,LucaRossi,LixinCui,JianCheng,andEdwinR.
Hancock.
Aquantum-inspiredsimilari-tymeasurefortheanalysisofcompleteweightedgraphs.
IEEETrans.
Cybern.
,50(3):1264–1277,2020.
[BorgwardtandKriegel,2005]KarstenM.
BorgwardtandHans-PeterKriegel.
Shortest-pathkernelsongraphs.
InProceedingsoftheIEEEInternationalConferenceonDa-taMining,pages74–81,2005.
[BullmoreandSporns,2009]EdBullmoreandOlafSporn-s.
Complexbrainnetworks:Graphtheoreticalanalysisofstructuralandfunctionalsystems.
NatureReviewsNeuro-science,10(3):186–198,2009.
[Cuietal.
,2018]LixinCui,LuBai,LucaRossi,ZhihongZhang,YuhangJiao,andEdwinR.
Hancock.
Aprelim-inarysurveyofanalyzingdynamictime-varyingnancialnetworksusinggraphkernels.
InProceedingsofS+SSPR,pages237–247,2018.
[Cuturi,2011]MarcoCuturi.
Fastglobalalignmentkernels.
InProceedingsofICML,pages929–936,2011.
[FarhiandGutmann,1998]E.
FarhiandS.
Gutmann.
Quan-tumcomputationanddecisiontrees.
PhysicalReviewA,58:915,1998.
[Godsil,2013]ChrisGodsil.
Averagemixingofcontinuousquantumwalks.
JournalofCombinatorialTheory,SeriesA,120(7):1649–1662,2013.
[Haussler,1999]DavidHaussler.
Convolutionkernelsondiscretestructures.
InTechnicalReportUCS-CRL-99-10,SantaCruz,CA,USA,1999.
[Jain,2019]BrijneshJ.
Jain.
Makingthedynamictimewarpingdistancewarping-invariant.
PatternRecognition,94:35–52,2019.
[Johanssonetal.
,2014]FredrikD.
Johansson,VinayJetha-va,DevdattP.
Dubhashi,andChiranjibBhattacharyya.
Globalgraphkernelsusinggeometricembeddings.
InPro-ceedingsofICML,pages694–702,2014.
[Kashimaetal.
,2003]HisashiKashima,KojiTsuda,andAkihiroInokuchi.
Marginalizedkernelsbetweenlabeledgraphs.
InProceedingsofICML,pages321–328,2003.
[Mikalsenetal.
,2018]KarlyvindMikalsen,FilippoMari-aBianchi,CristinaSoguero-Ruz,andRobertJenssen.
Timeseriesclusterkernelforlearningsimilaritiesbetweenmultivariatetimeserieswithmissingdata.
PatternRecog-nition,76:569–581,2018.
[Nicolisetal.
,2005]G.
Nicolis,A.
G.
Cantu,andC.
Nicolis.
Dynamicalaspectsofinteractionnetworks.
InternationalJournalofBifurcationandChaos,15:3467,2005.
[Shervashidzeetal.
,2009]N.
Shervashidze,S.
V.
N.
Vish-wanathan,K.
MehlhornT.
Petri,andK.
M.
Borgwardt.
Ef-cientgraphletkernelsforlargegraphcomparison.
Jour-nalofMachineLearningResearch,5:488–495,2009.
[Shimadaetal.
,2008]Y.
Shimada,T.
Kimura,andT.
Ikeguchi.
Analysisofchaoticdynamicsusingmeasuresofthecomplexnetworktheory.
InProceedingsofICANN,pages61–70,2008.
[Silvaetal.
,2015]FilipiN.
Silva,CesarH.
Comin,ThomasK.
Peron,FranciscoA.
Rodrigues,ChengYe,RichardC.
Wilson,EdwinR.
Hancock,andLucianodaF.
Costa.
Modulardynamicsofnancialmarketnetworks.
arXivpreprintarXiv:1501.
05040,2015.
[Wittenetal.
,2011]IanH.
Witten,EibeFrank,andMarkA.
Hall.
DataMining:PracticalMachineLearningToolsandTechniques.
MorganKaufmann,2011.
[Xuetal.
,2018]LixiangXu,XiaoyiJiang,LuBai,JinXiao,andBinLuo.
Ahybridreproducinggraphkernelbasedoninformationentropy.
PatternRecognition,73:89–98,2018.
[Yeetal.
,2015]ChengYe,CesarH.
Comin,ThomasK.
Peron,FilipiN.
Silva,FranciscoA.
Rodrigues,LucianodaF.
Costa,AndreaTorsello,andEdwinR.
Hancock.
Thermodynamiccharacterizationofnetworksusinggraphpolynomials.
PhysicalReviewE,92(3):032810,2015.
[ZhangandSmall,2006]J.
ZhangandM.
Small.
Complexnetworkfrompseudoperiodictimeseries:Topologyver-susdynamics.
PhysicalReviewLetters,96:238701,2006.