1、Graph Neural Networks:Combing Deep Learning&Symbolic ReasoningLe SongPrincipal Engineer,Ant FinancialAssociate Professor,Georgia TechFundamental problem and challengeRepresent?Entire graphEach nodeApplyVectorRepresentationGraph TopologyNode attributeEdge attribute2!#!$!%!&!(#($(%(&GCN/GNN/MPN/Struct

2、ure2Vec)$(+)#(+)(+)%(+)(+)&(+)Obtain embedding viaiterative update algorithm:1.Initialize)-(+)=/0+!-,32.Iterate 4 times)-(5)/0#)-(57#)+0$9:!3($-.)Residual:!($)!($-.)+:;.!($-.)+Attention:!($):+;73 3!3($-.),3 3=1Gating:!($)1 E !($-.)+E :;.!($-.)+Many papers!#!$!%!&!(#($(%(&Different message passing sc

3、heme)#(+)1.Initialize)-.,1,22.Iterate 3 times3.Aggregate)-=5%9-)-(:),1)-.(;)=5#)-.(;#)+5$9-B)-(;#),(1,2)#(+)#$(+)Parameterized as neural networkDai,et al.ICML 16Obtain embedding viaiterative update algorithm:6Lecture-Style TutorialBenefit of GNN for Benefit of GNN for Graph Feature Extraction Algori

4、thmGraph Feature Extraction AlgorithmFraudulent account detectionAlipay:new accounts in a month:millions of nodes and edges.Fake account can increase system level risk?BadGooddeviceLeverage account activity+connectivity?8Liu,et al.CCS 17,CIKM17Fraudulent account patternFake accountNormal accountDevi

5、ce ConnectivityAccountActivity9Results215 years,trillion of eventsTime-varying dependency structureTemporal knowledge graph:What will happen next?Trivedi et al.ICML 201717Enemys friend is an enemyCAIROCAIROCROATIACROATIAMANCHESTERMANCHESTERPROTESTORPROTESTORNEW ZEALANDNEW ZEALANDSOMALIASOMALIATEHRAN

6、TEHRANSINGAPORESINGAPOREASSAULTASSAULT302015062015ASSAULT:062015CONSULTCONSULTCONSULTCONSULTCOOPERATECOOPERATE062015292015(predicted event)(predicted event)THREATENTHREATENPROVIDE AIDPROVIDE AID0720015FIGHTFIGHTFIGHTFIGHT05201518COLOMBIAOTTAWAOTTAWANEW DELHINEW DELHIBELGIUMBELGIUMLIBYALIB

7、YAVENEZUELAVENEZUELAUAEUAEGAUTEMALAGAUTEMALAREDUCE RELATIONREDUCE RELATION5MATERIAL COOP.:022015FIGHTFIGHTCONSULTCONSULTPROVIDE AIDPROVIDE AID262015032015(predicted event)(predicted event)TRADE COOP.TRADE COOP.DIPLOMATIC COOP.DIPLOMATIC COOP.0320015FIGHTFIGHTTRADE COOP.TRADE CO

8、OP.282015Friends friend is a friend,common enemy strengthen the tie19Lecture-Style TutorialGNN to Parametrize GNN to Parametrize Variational Inference AlgorithmVariational Inference Algorithmfor Probabilistic Logicfor Probabilistic Logic!Factor graph representation for knowledge baseEntity,#=%,(,)Pr

9、edicate(attribute|relation),+:#0,1Eg.Smoke(x),Friend(x,x),Like(x,x)F(A,B)=1F(A,C)=1S(B)=1S(A)=1F(A,D)=1ABCDF(B,C)F(B,D)F(C,D)S(C)S(D)34predicatebinary variablelatent variable 21!Markov logic networksUse logic formula#:&0,1 for potential functionsEg.formula#(x,x):Friend(x,x)Smoke(x)Smoke(x)F(A,B)=1F(

10、A,C)=1S(B)=1S(A)=1F(A,D)=1F(B,C)F(B,D)F(C,D)S(C)S(D)#(A,B)#(A,C)#(A,D)#(B,C)#(B,D)#(C,D)/012!,=14exp 89:98;=9(?9):9:formula weight,eg.=9A,A:F(x,x)S(x)S(x)22!Challenges in inferenceA large grounded network,#$%in the number$of entities!Enumerate configuration over#($%)binary variables,with#2)*possibil

11、ities.F(A,B)=1F(A,C)=1S(B)=1S(A)=1F(A,D)=1F(B,C)F(B,D)F(C,D)S(C)S(D)+(A,B)+(A,C)+(A,D)+(B,C)+(B,D)+(C,D),-./F B,C!/S C!5=7899:;9?;A=)8B=;);C:D?E=8B?F89G?exp 7CKC78LMC(NC)23Use GNN for variational inferenceGNN on original KB(!)to get embedding#$,#&,#,#(for entities#$,#&,#,#(=*+(!;.)0F(A,B)=1F(A,C)=1S

12、(B)=1S(A)=1F(A,D)=1ABCD#$#&#(!Similar structure=similar GNN embedding(Dai ICML16,Xu ICLR19)#1(2)56#1(276)+59:;=1#;(276)neural network24Use GNN for variational inferenceGNN on original KB(!)to get embedding#$,#&,#,#(for entities#$,#&,#,#(=*+(!;.)0 F B,C=1 5:=7789:;?B,0 S C=1 5:=7789:;DEA,BA5F(A,B)=1F

13、(A,C)=1S(B)=1S(A)=1F(A,D)=1FF(B,C)F(B,D)F(C,D)S(C)S(D)ABCD#$#&#(!GTrain the parameters.,I,.J,.and GNN using mean field variational inferenceSimilar structure=similar GNN embedding(Dai ICML16,Xu ICLR19)25OverviewVariational InferencePosteriorEncodingLikelihoodDecodingGCNGCNMLNMLNKnowledgeKnowledgeGra

14、phGraph!()formula potentialpredicate posterior26Large Facebook15K-237 dataset#entity:15K,#ground predicate:50M,#ground formula:679BIncrease training data for target predicates27UW-CSE dataset details22 relationsTeach,publish Task goalPredict who is whose advisorZeroobserved facts for query predicate

15、s94 crowd-sourced FOL formulasadvisedBy(s,p)professor(p)advisedBy(s,p)yearsInProgram(s,Year_1)professor(x)student(y)publication(p,x)v publication(p,y)v student(x)v student(y)professor(y)student(x)v advisedBy(x,y)tempAdvisedBy(x,y)S1S3P2Paper1publishpublishCourse1teachadvisedBy?advisedBy?28Cora datas

16、et details(CS paper citations)10 relation typesAuthor,Title,Venue,HasWordTitle,Task goal(entity resolution)De-duplicate citations,authors,and venuesZeroobserved facts for query predicates46 crowd-sourced FOL formulasA1A2W1Paper1HasWordTitleAuthorHasWordAuthorSameAuthor?AuthorAuthor(bc1,a1)v Author(b

17、c2,a2)v SameAuthor(a1,a2)SameBib(bc1,bc2)HasWordAuthor(a1,w)v HasWordAuthor(a2,w)SameAuthor(a1,a2)Title(bc1,t1)v Title(bc2,t2)v SameBib(bc1,bc2)SameTitle(t1,t2)SameVenue(v1,v2)v SameVenue(v2,v3)SameVenue(v1,v3)Title(bc1,t1)v Title(bc2,t2)v HasWordTitle(t1,+w)v HasWordTitle(t2,+w)SameBib(bc1,bc2)29In

18、ference accuracy and timeArea under precision-recall curve(AUC-PR)Inference wall clock timeExpressGNNExpressGNN30Lecture-Style TutorialConclusionConclusionGNN/Structure2Vec=Parametrized algorithm!,!Supervised Learning GenerativeModelsReinforcementLearning32#$(&)*+,$+*./02$#0(&3+)Open new possibility

19、 to bridgeDeep learning&Structures(Graph,Logic,Algorithm)ReferencesH.Dai,B.Dai and L.Song.Structure2Vec:Discriminative Embedding of Latent Variable Models for Structured Data,ICML 2016.Y.Zhang,X.Chen,Y.Yang,A.Ramamurthy,B.Li,Y.Qi and L.Song.Can Graph Neural Networks Help Logic Reasoning?Arxiv2019.J.

20、Chen,J.Zhu,and L.Song.Stochastic Training of Graph Convolutional Networks.ICML 2018.R Trivedi,H Dai,Y Wang,L Song.Know-Evolve:Deep Temporal Reasoning for Dynamic Knowledge Graph.ICML 2017.H Dai,Y Wang,R Trivedi,L Song.Deep CoevolutionaryNetwork:Embedding User and Item Features for Recommendation.Rec

21、sysWorkshop on Deep Learning.2017.(BEST PAPER)H.Dai,E.Khalil,Y.Zhang,B.Dilkinaand L.Song.Learning Combinatorial Optimizations over Graphs.NIPS 2017.X.Xu,C.Liu,Q.Feng,H.Yin,L.Song,D.Song.Neural Network-based Graph Embedding for Cross-Platform Binary Code SimilarityDetection.CCS.2017.H.Dai,Z.Kozareva,

22、B.Dai,A.Smola,and L.Song.Learning Steady States of Iterative Algorithms over Graphs.ICML 2018.H.Dai,H.Li,T.Tian,X.Huang,L.Wang,J.Zhu,and L.Song.Adversarial Attack on Graph Structured Data.ICML 2018.Y.Zhang,H.Dai,Z.Kozareva,A.Smola,and L.Song.VariationalReasoning for Question Answering with Knowledge

23、 Graph.AAAI 2018.Z.Liu,C.Chen,X.Yang,J.Zhou,X.Long and L.Song.Heterogeneous Graph Neural Networks for Malicious Account Detection.CCS2017,CIKM 2018.Z.Liu,C.Chen,L.Li,J.Zhou,X.Li and L.Song.Geniepath:Graph Neural Networks with Adaptive Receptive Paths.AAAI 2019.H.Dai,Y.Tian,B.Dai,S.Skienaand L.Song.Syntax Directed VariationalAutoencoderfor Structured Data.ICLR 2018.X.Si,H.Dai,M.Raghothanman,M.Naikand L.Song.Learning Loop Invariants for Program Verification.NIPS 2018.33THANKS!THANKS!