圖神經(jīng)網(wǎng)絡(luò)及其應(yīng)用正式版

微信掃碼

海量資源到手進(jìn)群即領(lǐng)福利《報(bào)告與資源合編》，內(nèi)有近百行業(yè)、上萬(wàn)份行研、管理及其他學(xué)習(xí)資源免費(fèi)下載；每日分享最新6+份精選行研資料；群友信息交流，群主免費(fèi)提供相關(guān)行業(yè)報(bào)告。報(bào)告整理于網(wǎng)絡(luò)，只用于群友學(xué)習(xí)，請(qǐng)勿他用知識(shí)星球行業(yè)與管理資源無(wú)限制下載各行業(yè)研究報(bào)告、咨詢公司管理方案，企業(yè)運(yùn)營(yíng)制度、科技方案及大咖報(bào)告等。每月更新超過(guò)3000份最新行業(yè)資源；涵蓋科技、金融、教育、互聯(lián)網(wǎng)、房地產(chǎn)、生物制藥、醫(yī)療健康等行研報(bào)告、科技動(dòng)態(tài)、管理方案；微信掃碼

學(xué)習(xí)工作無(wú)憂微信掃碼或添加客服微信（微信號(hào)：Teamkon3）免費(fèi)報(bào)告等你領(lǐng)。（添加好友請(qǐng)備注：姓名+單位+業(yè)務(wù)領(lǐng)域）行業(yè)與管理資源微信群業(yè)務(wù)合作聯(lián)系微信：Teamkon3HuaweiShenshenhuawei@

InstituteofComputingTechnology,ChineseAcademyofSciences2021.1.14GraphNeuralNetworksOutlineBriefreviewongraphneuralnetworkSeveralresearchdirectionsonExpressivepowerOver-smoothproblemApplicationsofgraphneuralnetworks4AbriefreviewongraphneuralnetworkConvolutionalNeuralNetworkConvolutionalneuralnetwork(CNN)gainsgreatsuccessonEuclideandata,e.g.,image,text,audio,andvideoImageclassification,objectdetection,machinetranslationThepowerofCNNliesinitsabilitytolearnlocalstationarystructures,vialocalizedconvolutionfilter,andcomposethemtoformmulti-scalehierarchicalpatterns6M.M.Bronstein,J.Bruna,Y.LeCun,A.Szlam,P.Vandergheynst.Geometricdeeplearning:goingbeyondEuclideandata.IEEESignalProcessingMagazine,18-42,2017.TemporalconvolutionalnetworkConvolutionalneuralnetworksonimageConvolutionalNeuralNetworkLocalizedconvolutionalfiltersaretranslation-orshift-invariantWhichareabletorecognizeidenticalfeaturesindependentlyoftheirspatiallocationsOneinterestingproblemishowtogeneralizeconvolutiontonon-Euclideandomain,e.g.,graph?Irregularstructureofgraphposeschallengesfordefiningconvolution7LeCun,Y.,Bengio,Y.,andHinton,G.Deeplearning.Nature,521(7553):436,2015

TemplateMatchingX-ShapeFromCNNtographCNNConvolutioniswelldefinedinEuclideandata,grid-likenetworkNotstraightforwardtodefineconvolutiononirregularnetwork,widelyobservedinrealworld8Grid-likenetworkIrregularnetworksPreliminariesforGNNs

9ExistingmethodstodefineconvolutionSpectralmethods:defineconvolutioninspectraldomainConvolutionisdefinedviagraphFouriertransformandconvolutiontheorem.Themainchallengeisthatconvolutionfilterdefinedinspectraldomainis

notlocalizedinvertexdomain.Spatialmethods:defineconvolutioninthevertexdomainConvolutionisdefinedasaweightedaveragefunctionoverallverticeslocatedintheneighborhoodoftargetvertex.Themainchallengeisthatthesizeofneighborhoodvariesremarkablyacrossnodes,e.g.,power-lawdegreedistribution.10SpectralmethodsforgraphconvolutionalneuralnetworksSpectralmethods

12

GraphFourierTransform

13

Defineconvolutioninspectraldomain

14

Defineconvolutioninspectraldomain

15

Step1:GraphFourierTransformStep3GraphFourierInverseTransformStep2:Convolution

inspectraldomain

SpectralGraphCNNSpectralGraphCNN16

J.Bruna,W.Zaremba,A.Szlam,andY.

LeCun.Spectralnetworksandlocallyconnectednetworksongraphs.ICLR,2014.

ShortcomingsofSpectralgraphCNN17

ChebyNet:parameterizingfilterParameterizingconvolutionfilterviapolynomialapproximationChebyNet18

M.Defferrard,X.Bresson,P.Vandergheynst.Convolutionalneuralnetworksongraphswithfastlocalizedspectralfiltering.NeuraIPS,2016.ChebyNetvs.SpectralGraphCNN

19

M.Defferrard,X.Bresson,P.Vandergheynst.Convolutionalneuralnetworksongraphswithfastlocalizedspectralfiltering.NeuraIPS,2016.Isthismethodgoodenough?Whatcouldwedomore?GWNN:graphwaveletneuralnetwork

20

Fouriervs.Wavelet21FourierBasisDenseNotlocalizedHighComputationalcostB.Xu,H.Shen,Q.Cao,Y.Qiu,X.Cheng.Graphwaveletneuralnetwork.ICLR2019.

WaveletBasisSparseLocalizedLowComputationalcostGWNN:graphwaveletneuralnetworkGraphconvolutionviawavelettransformGraphwaveletneuralnetwork22Replacingbasis

GWNNvs.ChebyNetBenchmarkdatasetsResultsatthetaskofnodeclassification23SpatialmethodsforgraphconvolutionalneuralnetworksSpatialMethodsforGraphCNNByanalogyWhatcanwelearnfromthearchitectureofstandardconvolutionalneuralnetwork?251.DetermineNeighborhood2.ImposeanorderinneighborhoodM.Niepert,M.Ahmed,K.Kutzkov.LearningConvolutionalNeuralNetworksforGraphs.ICML,2016.3.ParametersharingSpatialMethodsforGraphCNNByanalogyForeachnode,selectthefixednumberofnodesasitsneighboringnodes,accordingtocertainproximitymetricImposeanorderaccordingtotheproximitymetricParametersharing26M.Niepert,M.Ahmed,K.Kutzkov.LearningConvolutionalNeuralNetworksforGraphs.ICML,2016.1.DetermineNeighborhood2.Imposeanorderinneighborhood3.ParametersharingSpatialMethodsforGraphCNNGraphSAGESamplingneighborsAggregatingneighbors27GraphSAGE:InductiveLearningW.L.Hamilton,R.Ying,J.Leskovec.InductiveRepresentationLearningonLargeGraphs.NeuraIPS2017Generalframeworkofgraphneuralnetworks:AggregatetheinformationofneighboringnodestoupdatetherepresentationofcenternodeSpatialMethodsforGraphCNNGCN:GraphConvolutionNetworkAggregatinginformationfromneighborhoodviaanormalizedLaplacianmatrixSharedparametersarefromfeaturetransformation28T.N.Kipf,andM.Welling.Semi-supervisedclassificationwithgraphconvolutionalnetworks.ICLR2017ParameterforfeatureTransformationSpatialMethodsforGraphCNNGAT:GraphAttentionNetworkLearningtheaggregationmatrix,i.e.,LaplacianmatrixinGCN,viaattentionmechanism,i.e.,aweightedmeanpooling.SharedparameterscontaintwopartsParametersforfeaturetransformationParametersforattention29AttentionMechanisminGATParameterofAttentionmechanismParameterforfeatureTransformationP.Velickovic,G.Cucurull,A.Casanova,A.Romero,P.Lio,Y.Bengio.GraphAttentionNetworks.NeuraIPS2018.SpatialMethodsforGraphCNNMoNet:AgeneralframeworkforspatialmethodsDefinemultiplekernelfunctions,parameterizedornot,tomeasurethesimilaritybetweentargetnodeandothernodesConvolutionkernelsaretheweightsofthesekernelfunctions30F.Monti,D.Boscaini,J.Masci,E.Rodola,J.Svoboda,M.M.Bronstein.GeometricdeeplearningongraphsandmanifoldsusingmixturemodelCNNs.CVPR2017.ConvolutionkernelSpectralmethodsvs.SpatialmethodsConnectionsSpectralmethodsarespecialcasesofspatialmethodsDifferenceSpectralmethodsdefinekernelfunctionsviaanexplicitspacetransformation,i.e.,projectingintospectralspaceSpatialmethodsdirectlydefinekernelfunctions31SpectralmethodsSpatialMethodsKernelfunction：CharacterizingthesimilarityordistanceamongnodesSpectralmethods:RecapSpectralCNNChebyNetGCN32

FrameworkofGraphNeuralNetwork

31GraphPoolingGraphPoolingviagraphcoarseningGraphcoarseningMergingnodesintoclustersandtakeeachclusterasasupernodeNodemergingcouldbedoneaprioriorduringthetrainingprocessofgraphconvolutionalneuralnetworks,e.g,DiffPooling35Ying,R.,You,J.,Morris,C.,Ren,X.,Hamilton,W.L.,andLeskovec,J.Hierarchicalgraphrepresentationlearningwithdifferentiablepooling,NeuraIPS2018GraphpoolingvianodeselectionNodeselectionLearnametrictoquantifytheimportanceofnodesandselectseveralnodesaccordingtothelearnedmetric36J.Lee,I.Lee,J.Kang.Self-attentionGraphPooling,ICML2019.OutlineBriefreviewongraphneuralnetworkSeveralresearchdirectionsonExpressivepowerOver-smoothproblemApplicationsofgraphneuralnetworks37HowabouttheexpressivepowerofGNNs?GraphNeuralNetworksGraphneuralnetworks(GNNs)gainedremarkablesuccessAchievingstate-of-the-artempiricalperformanceinnodeclassification,linkprediction,andgraphclassification.ThedesignofnewGNNsismostlybasedonempiricalintuition,heuristicsandexperimentaltrial-and-error.WelacktheoreticalunderstandingofthepropertiesandlimitationsofGNNs.OnefundamentalproblemistheexpressivepowerofGNNs39NodeclassificationGraphclassificationAboutExpressivePower

40K.Hornik,M.Stinchcombe,H.White.Multilayerfeedforwardnetworksareuniversalapproximators.Neuralnetworks,2(5):359–366,1989.M.Raghu,B.Poole,J.Kleinberg,S.Ganguli,J.S.Dickstein.OntheExpressivePowerofDeepNeuralNetworks.ICML,2017.GNNsfornodeclassificationExample:1-layerGCN41R.Sato.ASurveyonTheExpressivePowerofGraphNeuralNetworks.arXiv:2003.04078,2020Limitedexpressivepowerof1-layerGCN:itcannotfullydistinguishallnodesGNNsfornodeclassificationExample:2-layerGCN42R.Sato.ASurveyonTheExpressivePowerofGraphNeuralNetworks.arXiv:2003.04078,20202-layerGCNcanfullydistinguishallnodesinthistoyexample.DepthofGNNsmatters.CantheexpressivepowerofGNNsbeimprovedinfinitelyviaimprovingtheirdepth?Isthereabound?Layer0:Layer1:Layer2:Weisfeiler-LehmanIsomorphismTestWLtestiswidelyusedtojudgewhethertwographs,labeledorunlabeled,aretopologicallyidentical,orhowtheyaretopologicallysimilar.43N.Shervashidze,P.Schweitzer,E.J.Leeuwen,K.Mehlhorn,K.M.Borgwardt.Weisfeiler-LehmanGraphKernels.JMLR,2011.Example:similaritymeasurement.WLTest:Subtree-basedGraphKernel

44N.Shervashidze,P.Schweitzer,E.J.Leeuwen,K.Mehlhorn,K.M.Borgwardt.Weisfeiler-LehmanGraphKernels.JMLR,2011.ForWLtest,graphfeaturesareessentiallycountsofdifferentrootedsubtreesinthegraph.ConnectionBetweenGNNandWLTestWLtestprovidesanupperboundfortheexpressivepoweroftheaggregation-basedGNNs.AmaximallypowerfulGNNnevermaptwodifferentneighborhoodstothesamerepresentation,i.e.,theaggregationfunctionovermultisetisinjective.45K.Xu,W.Hu,J.Leskovec,S.Jegelka.Howpowerfularegraphneuralnetworks?ICLR,2019.Injectivefunction

ForpopularGNNs,likeGCNandGraphSAGE,theiraggregationfunctionsareinherentlynotinjective.GraphIsomorphismNetworkBasicidea:composeauniversalinjectiveaggregationfunctionoveranodeandthemultisetofitsneighborsGraphisomorphismnetwork46K.Xu,W.Hu,J.Leskovec,S.Jegelka.Howpowerfularegraphneuralnetworks?ICLR,2019.

①M(fèi)ultiple-layerperceptronoffersuniversalapproximator.②Sumpoolingoffersinjectivecondition.①②PrincipalneighborhoodaggregationPrincipalneighborhoodaggregationforgraphDefinemultipleaggregationfunctionstoimprovetheexpressivepowerofGNN47GabrieleCorso,LucaCavalleri,DominiqueBeaini,PietroLio,andPetarVelickovic.Principalneighbourhoodaggregationforgraphnets.NeurIPS2020.Injectiveaggregationfunctionineachlayertoachievehighexpressivepowerisnotalwaysnecessary.ExperimentalValidationValidatingexpressivepowerorrepresentationcapabilityMetric:trainingaccuracyTask:graphclassificationDatasets:bioinformaticsandsocialnetworks48K.Xu,W.Hu,J.Leskovec,S.Jegelka.Howpowerfularegraphneuralnetworks?ICLR,2019.PerformanceonGraphClassificationDoesthehighexpressivepowerofGNNimplygoodperformanceondown-streamtask,e.g.,graphclassification?Metric:testaccuracy49K.Xu,W.Hu,J.Leskovec,S.Jegelka.Howpowerfularegraphneuralnetworks?ICLR,2019.HighexpressivepowerdoesnotalwaysbringgoodperformanceNotethat:lowexpressivepoweralwaysimpliesbadperformanceIsexpressivepowernecessary?ExpressivepoweroffersusatheoreticalguideforunderstandingthecapabilityofGNNs.Whether,andtowhatdegree,areGNNsuniversalapproximitortofunctionsmappinggraphstoreal-valuedvector?Forgraphclassification,No!!!Fornodeclassification,itisalmost.Forspecifictasks,itisnotpracticallynecessarytoseekhighexpressivepowerforperformanceimprovementThispartlyexplainswhyGCN,GraphSAGEworkswellalthoughtheirexpressivepowerislessthanGIN.Whatwereallyneedisauniversalfunctionthatcanmapsimilarobjects(nodesorgraphs)tocloserepresentations,facilitatingdown-streamtasks.50Over-smoothissueOver-smoothissueOver-smoothphenomenoninGCN52Y.Rong,W.Huang,T.Xu,J.Huang.DropEdge:TowardsDeepGraphConvolutionalNetworksonNodeClassification,ICLR2020.WhydeeperGNNsperformworsethantheirshallowcounterparts?Over-smoothissueTheover-smoothissuesufferedbyGCNrootsinitscross-layershared,hard-codedaggregationmatrixGAT,usingself-attentiontodetermineaggregationmatrix,hasnointrinsicover-smoothissue,especiallymulti-headGATOver-smoothissueconfoundswithover-fittingissue53Y.Rong,W.Huang,T.Xu,J.Huang.DropEdge:TowardsDeepGraphConvolutionalNetworksonNodeClassification,ICLR2020.PotentialapplicationsApplicationsThreemajorscenariosNode-levelNodeclassification:predictthelabelofnodesaccordingtoseverallabelednodesandgraphstructureLinkprediction:predicttheexistenceoroccurrenceoflinksamongpairsofnodesGraph-levelGraphclassification:predictthelabelofgraphsvialearningagraphrepresentationusinggraphCNNSignal-levelSignalclassification,similartoimageclassificationwhichissignal-levelscenarioonagrid-likenetwork55Applications56RecommendationR.Ying,R.He,K.Chen,P.Eksombatchai,W.L.Hamilton,J.Leskovec.GraphConvolutionalNeuralNetworksforWeb-ScaleRecommenderSystems.KDD2018.X.He,K.Deng,X.Wang,Y.Li,Y.Zhang,M.Wang.LightGCN:SimplifyingandPoweringGraphConvolutionNetworkforRecommendation.SIGIR2020.TexclassificationL.Yao,C.Mao,Y.Luo,GraphConvolutionalNetworksforTextClassification.AAAI2019.KnowledgeGraphApplicationsinotherfieldsGNNsforquantumchemistryPredictthequantumpropertiesofmoleculesusingGNNsTraditionalmethods,i.e.,DFT(DensityFunctionalTheory),iscomputationallyexpensiveM