GraphConvolutionalRecurrentNeuralNetworkData-DrivenTrafficForecasting

arXiv:1707.01926v1cs.LG6Jul20171GraphConvolutionalRecurrentNeuralNetwork:Data-DrivenTracForecastingYaguangLiRoseYuCyrusShahabiYanLiuDepartmentofComputerScience,UniversityofSouthernCaliforniayaguang,qiyu,shahabi,AbstractSpatiotemporalforecastinghassignicantimplicationsinsustainability,transportationandhealth-caredomain.Tracforecastingisonecanonicalexampleofsuchlearningtask.Thistaskischallengingdueto(1)non-lineartemporaldynamicswithchangingroadconditions,(2)complexspatialdependenciesonroadnetworkstopologyand(3)inherentdicultyoflong-termtimeseriesforecasting.Toaddressthesechallenges,weproposeGraphConvolutionalRecurrentNeuralNetworktoincorporatebothspatialandtemporaldependencyintracow.Wefurtherintegratetheencoder-decoderframeworkandscheduledsamplingtoimprovelong-termforecasting.Whenevaluatedonreal-worldroadnetworktracdata,ourapproachcanaccuratelycapturespatiotemporalcorrelationsandconsistentlyoutperformsstate-of-the-artbaselinesby12%-15%.IntroductionSpatiotemporalforecastingisacrucialtaskforalearningsystemthatoperatesinadynamicenvironment.Accuratespatiotemporalforecastinghasawiderangeofapplicationsrangingfromvideocompressionandunderstanding,astoenergyandsmartgridmanagement,economicsandnance,toenvironmentalandhealthcare.Inthispaper,westudyoneexampleofspatiotemporalforecastingtask:tracforecasting,thecorecomponentoftheintelligenttransportationsystems.Webelieveourapproachisnotlimitedtotransportation,andisreadilyapplicabletootherdomainsaswell.Thegoaloftracforecastingistopredictthefuturespeedsofasensornetworkusingprevioustracspeedsaswellastheunderlyingroadnetworksstructure.Thistaskischallengingmainlyduetothecomplexspatialandtemporaldependencies.Ononehand,tractimeseriesdemonstratestrongtemporaldynamic.Recurringincidentssuchasrushhoursoraccidentscancausenon-stationarybehaviorintracspeeds,leadingtodicultyinlong-termforecasting.Ontheotherhand,multivariatetimeseriesfromasensornetworkcontaincomplexspatialcorrelations.Itisoftenthecasethatsuchspatialcorrelationarehighlylocalized.Figure1showstheweightslearnedfromtheauto-regressivemodelusingweightedaverageforasinglesensorprediction.Thelearnedweightshighlyconcentrateonitscloseneighbors.Anotherimportantcharacteristicsoftracisthe“conservationofow”,whichmeansthenumberofvehiclesinaroadnetworkstaysrelativelythesameduringashorttimeperiod.Intheliterature,tracforecastinghasbeenstudiedfordecades,fallingintotwomaincate-gories:data-drivenapproachandknowledge-drivenapproach.Intransportationandoperationalresearch,knowledge-drivenmethodsusuallyapplyqueuingtheoryandsimulateuserbehaviorsintrac5.Intimeseriescommunity,data-drivenmethodssuchasautoregressiveintegratedmovingaverage(ARIMA)modelandKalmanlteringremainpopular15,14.However,simpletimese-riesmodelsusuallyrelyonthestationarityassumptionofthetimeseries,andhavelimitedcapacity1torepresenthighlynonlineardynamics.Mostrecently,deeplearningmodelsfortracforecastingforecastinghavebeendevelopedin16,28.In10,theauthorsdevelopdeepauto-regressivemodelsformoregeneralspatiotemporalforecastingtask,e.g.,inventoryforecasting.However,thesedeeplearningmodelsonlyapplytounivariatetimeseriesorfocusonshort-termforecasting.Deepneuralnetworkmodelsforthedomainofspatiotemporalforecastingstaylargelyelusive.Ourworkservesasanimportantsteptointegratemanyimportantdevelopmentsindeeprecurrentneuralnetworksintotimeseriesanalysis,particularlyforspa-tiotemporalforecasting.Weleveragerecentadvancesingraphconvolution7,21andsequencemodeling6,3todesigntheGraphConvolutionalRecurrentNeuralNetwork(GCRNN).GCRNNmodelsboththespatialandthetemporaldependenceinthetracnetwork.Specically,weresorttorecurrentneuralnetworktocapturethenon-lineardynamics,andmodifytheGatedRecurrentUnittoincorporatetheunderlyingsensornet-workstructure.Thisisdonethroughtransformationofinputsequencethroughagraphconvolutionalkernel.Figure1:LocalspatialdependencyforToaddresstheerrorpropagationissueinlong-termfore-singlesensorlearnedfromweightedav-castingtask,wefurtherintegratetheencoder-decodererage.Largerweightsindicatehigherframeworkandscheduledsamplingtechnique3.Whencorrelation.evaluatedonthereal-worldtracdata,GCRNNconsistentlyoutperformsstate-of-the-arttracforecastingbaselinesbyalargemargin.Ourcontributionscanbesummarizedasfollows:Weinvestigatedtracforecasting,animportantmultivariatespatiotemporalforecastingtask,andidentieditsuniquespatiotemporaldependencystructure.Weproposedgraphconvolutionrecurrentneuralnetworkasawholisticframeworktoecientlycapturebothspatialandtemporalstructure.Theproposedapproachachievesthebestreportedresultsonreal-worldtracforecastingandobtainedsignicantimprovementoverstate-of-the-artmethods.2RelatedWorkTracforecastingisaclassicproblemintransportationandoperationalresearchwhicharelargelybasedonqueuingtheoryandsimulations9.Data-drivenapproachesfortracforecastinghavereceivedconsiderableattention,detailscanbefoundinarecentsurveypaper25andthereferencestherein.However,existingmachinelearningmodelseitherimposestrongstationaryassumptionsofthedata(e.g.,auto-regressivemodel)orfailtoaccountforhighlynon-lineartemporaldependency(e.g.,latentspacemodel27,8).Recently,deeplearningmodelsdelivernewpromisefortimeseriesforecastingproblem.Forexample,in28,theauthorsstudyunivaritetimeseriesforecastingusingdeepLSTMnetwork.In10,theauthorsproposeaprobabilisticdeepauto-regressiverecurrentframeworktoforecastinventorytimeseriesacrossdierentdomains.Theforecastingproblemwearefacinghereisspatiallycorrelatedtimeseries,whichrequirescarefulmodelingofbothspatialandtemporaldependency.Intermsofgeneralsequencemodeling,RecurrentNeuralNetworks(RNNs)havebecomethestate-of-the-artchoice,leadingtosuccessfulapplicationsinlanguagemodeling2,videogeneration23,speechrecognition17andweathernowcasting26.However,mostexisting2GraphConvolutionalGraphConvolutionalRecurrentLayerRecurrentLayerGraphConvolutionalGraphConvolutionalRecurrentLayerRecurrentLayerInputGraphSignalsPredictions.TimeDelay=1EncoderCopyStatesDecoderFigure2:SystemarchitectureforGraphConvolutionalRecurrentNeuralNetworkdesignedforspatiotemporaltracforecasting.deepsequencemodelsdealswitheitherdiscretetimesequenceorsequencesthatareevenlydistributedoveraregulargrid.Forinstance,convolutionalLSTMnetwork26capturesthespatiotemporalstructureamongpixelsbyapplyingaconvolutionallterovereachframeofthevideostream.Thelanguagesequencesareoftenencodedasdiscretetimeseries.Onthecontrary,timeseriesfromsensornetworksintracforecastingarecontinuoustimesequencesdistributedoveragraph.Closelyrelatedtoourworkisthedeeplearningmodelsfornon-Euclideanstructureddata.Forexample,in20,theauthorsproposeGraphNeuralNetworks(GNN)modelinthevertexspace,whichlearnsnoderepresentationsforthegraph.Lietal.13extendsGNNforsequencemodeling.TheresultingGatedGraphSequenceNeuralnetworkachievesthestate-of-the-artperformanceforprogramverication.Goingfromvertexdomaintospectraldomain,spectralgraphconvolutionalneuralnetworks(GCN)arerstintroducedin4,whichbridgesthespectralgraphtheoryanddeepneuralnetworks.In7,theauthorsfurtherimproveGCNwithfastlocalizedconvolutionslters.OurmodelextendsGCNtomodelmultivariatetimeseriesdistributedonanetwork.OurmodelcoincideswitharecentworkonsequentialgeneralizationofGCN21,however,wefocusoncontinuoustimepredictionandlong-termforecastingbyincorporatingencoder-decoderarchitecture24andscheduledsampling3techniques.3MethodologyWerstformalizethelearningproblemoftracforecastingandidentifyuniquespatiotemporaldependencystructures.Wethenproposeavariationofthedeeprecurrentneuralnetworkmodel.Givenaseriesofroadnetworksnapshots,ourmodeladdressesthreetechnicaldiculties:(1)localizedspatialdependency,(2)temporaldynamicsingraphs,and(3)long-termforecasting.3.1TracForecastingProblemThegoaloftracforecastingistopredictthefuturetracspeedbasedonpreviouslyobservedtracow.Thetracowismeasuredbynspatiotemporalcorrelatedsensorsontheroadnetwork.Thepair-wiserelationshipbetweenthosesensorscanbemodeledasaweightedgraphG=(V,E,A),whereVisanitesetof|V|=nvertices,whileEisasetofedgesandARnnis3Htimesteps,i.e.,Xt+1,Xt+H,whereHistheforecastinghorizon.aweightedadjacencymatrixrepresentingtheconnectivitybetweensensors.Thus,anobservationoftracspeedsatatimetcanbeviewedasagraphsignal,Xt:VRdx,wheredxisthedimensionofsignalineachnode.Thetracforecastingproblemcanbeformulatedasfollows:givensensorgraphGandhistoricaltracmeasurementsofsensors,inferthemostlikelytracmeasurementsinthenextXt+H,Xt+1=argmaxlogP(Xt+H,Xt+1|Xt,XtK+1;G,)Xt+H,Xt+1Supposethateachtimestepis5minutesandHis12,theoutputsofthemodelwillbethetracmeasurementofevery5minutesforallthesensorsinthenexthour.Notethattheaforementionedtracforecastingproblemisdierentfromthesingle-steptimeseriesforecastingproblem.ThepredictiontargetofourproblemisasequenceofmultivariatetimeseriesdistributedoveragraphGwhichcontainsbothspatialandtemporalstructures.Moreover,thepredictionproblemdenedin26canbeconsideredasaspecialcaseofthisproblemwhereGisaregulargrid.3.2SpatialDependencyModelingTractimeseriesfromroadnetworksensorsdemonstratestrongspatialdependency.Itismainlydueto(1)networkconnectivity:highwaynetworksusuallyhavesensorsinstalledevery1-2miles,andtracowofadjacentsensorsarehighlycorrelated;(2)owconservation:thenumberofvehiclesenteringandexitingtheroadsareapproximatelythesame.Unfortunately,recurrentneuralnetworks(RNNs)donotexplicitlymodelsuchspatialdependency.Inthiswork,weaugmentRNNsbyconsideringspatialcorrelationsamongmultivariatetimeseries.GraphAttentionMechanismInRNNs,theactivationisaweightedcombinationofallthehistoricalobservationsandhiddenstates,whilethespatialdependencyoftracisratherlocalized.Inordertoaccountforsuchlocaldependency,wegeneralizetheattentionmechanismfromsequencemodelingtospatialmodeling.Inparticular,weallowthemodeltolearntofocusoncloseneighborhoodsinsteadoftheentirenetwork.Thisisachievedbyrepresentingthehiddenstateofasensorusingacombinationofthehiddenstatesfromnearbysensorsweightedbyattention.Theattentionmechanismisdenedas:fatt(hi,hj)=hiWahj,aij=exp(fatt(hi,hj)knb(i,K)exp(fatt(hi,hk),gi=jnb(i,K)aijhj,(1)wherehidenotesthehiddenstatesofsensoriwhichisextractedusingaRNNsharedacrossallthenodes.nb(i,K)returnsthesetofneighborsthatarewithinK-hopfromnodei,andgirepresentstheaggregatedhiddenstatefornodeithatincorporatesinformationfromneighborhoodnodes.Then,theforecastingtaskofnodeiisimplementedusingafullyconnectedfeedforwardnetworkwithgiastheinput.GraphLaplacianTransformationGraphattentionmechanismenablesexplicitnetworkstructuremodeling,butinpracticeitonlyleadstomarginalperformanceimprovement.Thisispartlybecauseofthedicultyintrainingsuchmodelasitistimeconsumingtocomputepair-wiseattentionforlargenumberofnodes.Anotherreasonisthatgraphattentiononlymodelsthetopologicaldependencyinthevertexdomain,andyetitfailstocapturethe“conservationofow”propertyintrac.WeresolvethisissuebytransformingthetractimeseriesfromvertexdomainintothespectraldomainusinggraphLaplacian.4Figure3:Visualizationofeigen-functions.(a)showssensorlocationsonthemap.(b)and(c)correspondtoeigen-functionswithsmalleigenvalue(lowfrequencyandsmooth)while(d)and(e)correspondtooneswithlargeeigenvalues(highfrequencyandnon-smooth).GraphLaplacianisadiscreteversionofLaplacianoperator,whichcharacterizesthecon-nectivityofthegraph.ApplyingLaplacianoperatory=Lxtothesignalrepresentsone-stepdiusionofthesignalonthegraph.WearguethatitisnaturaltouseGraphLaplacianoperatorfortracforecastingproblems.Ifwemodelthechangeoftracowasxti(t)=jAij(xixj),wehavexti(t)=cLix,whereAijistheelementoftheadjacencymatrixofthegraph,ListhegraphLaplacianandcisaconstant.Thissharessimilarformastheheatequation,whichisgivenbythelaw“conservationofenergyinphysics.Inimageprocessing,thistransformationisknownasgraphconvolutionalkernel,denotedasg.Tracforecastingproblemprovidesanalternativemotivationofperformingsuchtransformation.ToobtaintheLaplacianmatrix,weconstructtheadjacencymatrixbasedonroadnetworkdistancewithathresholdedGaussiankernel22.Figure3visualizestheeigen-functionsofthenormalizedLaplacianmatrixforpartoftheroadnetworkinLosAngeles.Smalleigen-functionsrepresentsmoothspatialdependencywhilelargeonesdenotehighoscillation.WecanmakesomeinterestingobservationsinFigure3,whichcouldhelpexplainthespatialdependencycapturedbyLaplacian.Forexample,in(c)NearUniversalStudiosHollywood,atthecrossingofhighway101,134and170(d)NearRoseBowlStadium,atthecrossingofhighway2and134.Todealwithspatialdependencyatdierentresolutions,wecomputeaweightedsumofkthpowerofLaplacianasthespectraltransformation.ThisisbasedonthefactthatkthpowerofLaplacianissupportedbyexactlyk-hopneighbors22,representingthespreadoftracowatdierentscale.ComputingthekthpowerLaplacianmatrixcanbecomputationallyexpensive,soweapplyChebyshevpolynomialexpansion7forecientapproximation.K1K1K1y=gw(L)x=wkLx=UwkUxwkTk()xtttktkt(2)k=0k=0k=0ofChebyshevcoecientswhileTk()RnnistheChebyshevpolynomialoforderkevaluatedat=2/maxI.ThisapproximationreducesthelteringcomputationalcostfromO(|V|2)wherethegw(L)isthelearnedlterbasedonLaplacianmatrix.parameterwRKisavectortoO(K|E|).3.3TemporalDynamicsModelingWemodelthetemporaldynamicsintheframeworkofrecurrentneuralnetworks.OneofthevariantsofRNNistheGatedRecurrentUnits(GRU)6whichhasasimplerstructureandcompetitiveperformancecomparingwithLSTM.GatedGraphConvolutionWeincorporatespatialdependencyintoGRUbyreplacingthematrixmultiplicationwiththegraphconvolutionGdenedinEquation2.Thisgraphconvolu-5Figure4:Visualizationof24hoursroadnetworktractimeseriesevolutioninspectraldomainwithLaplaciantransformedinput(toprow)andvertexdomainwithrawinput(bottomrow).Spectraldomainenjoysbettersparsity.Theskewnessofthedistributionofthetransformedinputreectsthetraccongestioncondition.tionaloperationisappliedtobothinputsandhiddenstatestoobtainaGraphConvolutionalGatedRecurrentUnit(GCGRU).rt=(WrGxt+UrGht1+br)ut=(WuGxt+UuGht1+bu)ct=tanh(WcGxt+UcG(rtht1)+bc)ht=utht1+(1ut)ctWestackGRUandunrolltherecurrenceforaxednumberofstepsTanduseback-propagationthroughtimeinordertocomputegradients.Figure4showstheroadnetworktracevolutionin24hours,goingthroughmorningrushhourandafternoonrushhour.Wecanseethatinspectraldomain,thetracspeedtimeseriesenjoysbettersparsitythaninthevertexdomain.Thedistributionofthetransformedinputreectthetraccongestioncondition.Withheavycongestioninrushhour,thespectraldistributionofthetimeseriesbecomemoreheavy-tailed.Long-TermForecastingInlong-termforecasting,simplytrainingthemodelforonestepaheadprediction,andthenback-feedingthepredictionsattesttimeispronetoerrorpropagation.Theforecastingerrorinearlierstepscouldbequicklyampliedoverlong-timespan.Wedrawinspirationfromtheencoder-decoderarchitecture24aswellasscheduledsam