WIXLIB

CS246: Mining Massive DatasetsJure Leskovec, Stanford UniversityMina Ghashami, Amazonhttp://cs246.stanford.edu

ImagesText/SpeechModern deep learning toolbox is designedfor simple sequences & gridsJure Leskovec & Mina Ghashami, Stanford University2

But networks are far more complex!§ Arbitrary size and complex topological structure (i.e.,no spatial locality like grids)vs.TextNetworksImages§ No fixed node ordering or reference point§ Often dynamic and have multimodal featuresJure Leskovec & Mina Ghashami, Stanford University3

A naïve approach Take adjacency matrixand feature matrix[A, X]¡ Join adjacency matrix and features Feedthem intodeepinto(fully aconnected)neural net¡ Feedthemdeep neuralnet: Concatenate them 10111E0101010?Issues with this idea:Issues with this idea:Problems: § 𝑂( 𝑉 ) parametersHuge number of parameters§ Not applicable to graphs of different sizesNo inductive learning possible§ Sensitive to node orderingJure Leskovec & Mina Ghashami, Stanford University5

Graph-structured dataHidden layerHidden lGraph-structured dataWhat if our data looks like this?InputBut Whatourlooklikelikethis:ifgraphsour data looksthis?Inputor orthis:this:ReLUReLUor this: § There is no fixed notion of locality or slidingwindow on the graph§ Graph is permutation invariantCredit: Stanford CS224WJure Leskovec & Mina Ghashami, Stanford University6

Convolutional neural networks (on grids)SingleConvolutionalneuralnetwork (CNN) layerSingleCNN layer with3x3 filter:with 3x3 filter:(Animation byVincent Dumoulin)GraphImageIdea: transform information at the neighbors and combine it:§ Transform “messages” ℎ! from neighbors: 𝑊! ℎ!§ Add them up: ! 𝑊! ℎ!Credit: Stanford CS224WJure Leskovec & Mina Ghashami, Stanford University7

[Kipf and Welling, ICLR 2017]Idea: Node’s neighborhood defines acomputation graph𝑖Determine nodecomputation graph𝑖Propagate andtransform informationLearn how to propagate information across thegraph to compute node featuresCredit: Stanford CS224WJure Leskovec & Mina Ghashami, Stanford University8

¡Key idea: Generate node embeddings basedon local network neighborhoodsACBBTARGET NODEAACBACEFDFEDAINPUT GRAPHCredit: Stanford CS224WJure Leskovec & Mina Ghashami, Stanford University9

¡Intuition: Nodes aggregate information fromtheir neighbors using neural networksACBBTARGET NODEAACBCAEFDFEDAINPUT GRAPHNeural networksCredit: Stanford CS224WJure Leskovec & Mina Ghashami, Stanford University10

¡Intuition: Network neighborhood defines acomputation graphEvery node defines a computationgraph based on its neighborhood!Credit: Stanford CS224WJure Leskovec & Mina Ghashami, Stanford University11

¡Model can be of arbitrary depth:§ Nodes have embeddings at each layer§ Layer-0 embedding of node 𝑢 is its input feature, 𝑥𝑢§ Layer-𝑘 embedding gets information from nodes thatare K hops awayLayer-1Layer-2AACBBTARGET NODELayer-0ACBACEFDFEDAINPUT GRAPHJure Leskovec & Mina Ghashami, Stanford UniversityxAxCxAxBxExFxA12

¡Neighborhood aggregation: Key distinctionsare in how different approaches aggregateinformation across the layersBTARGET NODEAWhat is in the box?CAF?BA?CACB?DEFEDINPUT GRAPH?ACredit: Stanford CS224WJure Leskovec & Mina Ghashami, Stanford University13

¡Basic approach: Average information fromneighbors and apply a neural networkBTARGET NODE(1) average messagesfrom neighborsACBAACBACEFDFEDINPUT GRAPH(2) apply neural networkACredit: Stanford CS224WJure Leskovec & Mina Ghashami, Stanford University14

¡Assume we have a graph 𝑮:§§§§§𝑉 is the vertex set𝑨 is the adjacency matrix (assume binary)𝑿 ℝ! is a matrix of node features𝑣: a node in 𝑉; 𝑁 𝑣 : the set of neighbors of 𝑣.Node features:§ Social networks: User profile, User image§ Biological networks: Gene expression profiles, genefunctional information§ When there is no node feature in the graph dataset:§ Indicator vectors (one-hot encoding of a node)§ Vector of constant 1: [1, 1, , 1]Jure Leskovec & Mina Ghashami, Stanford University15

¡Basic approach: Average neighbor messagesand apply a neural networkh&% x%(* ,)h%Initial 0-th layer embeddings areequal to node featuresembedding of𝑣 at layer 𝑙(*) 𝜎(W* 2- /(%)h(*) B* h% ), 𝑙 {0, , 𝐿 1}N(𝑣)(()Average of neighbor’s Total numberprevious layer embeddings of layersEmbedding after Llayers of neighborhood Non-linearity(e.g., ReLU)Credit: Stanford CS224Waggregationz% h %Jure Leskovec & Mina Ghashami, Stanford University16

How do we train the model togenerate embeddings?𝒛0Need to define a loss function on the embeddingsCredit: Stanford CS224WJure Leskovec & Mina Ghashami, Stanford University17

(#)h! x!(&'()h!z! Trainable weight matrices(i.e., what we learn) 𝜎(W& ((%)h!) (!)(&)h)N(𝑣) (&)B& h! ), 𝑙 {0, , 𝐿 1}Final node embeddingWe can feed these embeddings into any loss functionand run SGD to train the weight parametersℎ!" : the hidden representation of node 𝑣 at layer 𝑙¡ 𝑊# : weight matrix for neighborhood aggregation¡ 𝐵# : weight matrix for transforming hidden vector ofselfCredit: Stanford CS224WJure Leskovec & Mina Ghashami, Stanford University18

¡¡Node embedding 𝒛! is a function of input graphSupervised setting: we want to minimize the lossℒ (see also slide 15):min ℒ(𝒚, 𝑓 𝒛" )!§ 𝒚: node label§ ℒ could be L2 if 𝒚 is real number, or cross entropyif 𝒚 is categoricalCredit: Stanford CS224WJure Leskovec & Mina Ghashami, Stanford University19

Directly train the model for a supervised task(e.g., node classification)Safe or toxicdrug?Safe or toxicdrug?E.g., a drug-druginteraction networkJure Leskovec & Mina Ghashami, Stanford University20

Directly train the model for a supervised task(e.g., node classification)¡ Use cross entropy loss (slide 16)ℒ ( 𝑦! log(𝜎(z!- 𝜃)) 1 𝑦! log(1 𝜎 z!- 𝜃 )! ,Encoder output:node embeddingSafe or toxic drug?ClassificationweightsNode classlabelCredit: Stanford CS224WJure Leskovec & Mina Ghashami, Stanford University21

CS246: Mining Massive DatasetsJure Leskovec, Stanford Universityhttp://cs246.stanford.edu

J. You, R. Ying, J. Leskovec. Design Space of Graph Neural Networks, NeurIPS 2020GNN Layer Message AggregationCB Different instantiationsunder this perspectiveA GCN, GraphSAGE,GAT,B CABTARGET NODEACAEFDFEDAINPUT GRAPHGNN Layer 1(2) Aggregation(1) MessageJure Leskovec & Mina Ghashami, Stanford University23

J. You, R. Ying, J. Leskovec. Design Space of Graph Neural Networks, NeurIPS 2020Connect GNN layersinto aC GNNB Stack layers sequentiallyAB Ways of addingC skip connectionsABTARGET NODEACAEFDFEDAINPUT GRAPHGNN Layer 1(3) LayerconnectivityGNN Layer 2Jure Leskovec & Mina Ghashami, Stanford University24

J. You, R. Ying, J. Leskovec. Design Space of Graph Neural Networks, NeurIPS 2020AIdea: Raw input graph computationalgraphCB Graph feature augmentationAB Graph structureaugmentationCBTARGET NODEACAEFDFEDAINPUT GRAPH(4) Graph augmentationJure Leskovec & Mina Ghashami, Stanford University25

J. You, R. Ying, J. Leskovec. Design Space of Graph Neural Networks, NeurIPS 2020AACBBTARGET NODEA(5) Learning objectiveBCACEFDFEDAINPUT GRAPHHow do we train a GNN Supervised/Unsupervisedobjectives Node/Edge/Graph levelobjectivesJure Leskovec & Mina Ghashami, Stanford University26

J. You, R. Ying, J. Leskovec. Design Space of Graph Neural Networks, NeurIPS 2020AACBBTARGET NODEA(5) Learning objectiveBCACEFDFEDAINPUT GRAPHGNN Layer 1(2) Aggregation(1) Message(3) LayerconnectivityGNN Layer 2(4) Graph augmentationJure Leskovec & Mina Ghashami, Stanford University27

CS246: Mining Massive DatasetsJure Leskovec, Stanford Universityhttp://cs246.stanford.edu

J. You, R. Ying, J. Leskovec. Design Space of Graph Neural Networks, NeurIPS 2020GNN Layer Message AggregationCB Different instantiationsunder this perspectiveA GCN, GraphSAGE,GAT,B CABTARGET NODEACAEFDFEDAINPUT GRAPHGNN Layer 1(2) Aggregation(1) MessageJure Leskovec & Mina Ghashami, Stanford University29

¡Idea of a GNN Layer:§ Compress a set of vectors into a single vector§ Two step process:§ (1) Message§ (2) Aggregation"Output node embedding 𝐡!Node 𝒗𝒍-th GNN Layer(2) Aggregation(1) Message"# "# Input node embedding 𝐡!, 𝐡% '(!)(from node itself neighboring nodes)Jure Leskovec & Mina Ghashami, Stanford University30

¡(1) Message computation(*)𝐦-§ Message function: MSG*2,𝐡-*§ Intuition: Each node will create a message, which will besent to other nodes later(&)&()§ Example: A Linear layer 𝐦 𝐖 & 𝐡 § Multiply node features with weight matrix 𝐖!ANode 𝒗ACBBTARGET NODEA(2) AggregationCBACFE(1) MessageFDEDINPUT GRAPHJure Leskovec & Mina Ghashami, Stanford UniversityA31

¡(2) Aggregation§ Intuition: Each node will aggregate the messages fromnode 𝑣’s neighbors(&)𝐡 AGG&*𝐦-,𝑢 𝑁 𝑣§ Example: Sum( ), Mean( ) or Max( ) aggregator§ 𝐡*& Sum({𝐦 & , 𝑢 𝑁(𝑣)})ANode 𝒗BTARGET NODECBAACACB(2) AggregationEFDFEDINPUT GRAPHJure Leskovec & Mina Ghashami, Stanford University(1) MessageA32

¡Issue: Information from node 𝑣 itself could get lost(&)(&())§ Computation of 𝐡* does not directly depend on 𝐡*¡Solution: Include(*2,)𝐡%when computing(*)𝐡%§ (1) Message: compute message from node 𝒗 itself§ Usually, a different message computation will be performed(!)(!)!%&!%&𝐦" 𝐁 ! 𝐡"𝐦' 𝐖 ! 𝐡'§ (2) Aggregation: After aggregating from neighbors, we canaggregate the message from node 𝒗 itself§ Via concatenation or summation&𝐡* CONCAT AGG&𝐦 Then aggregate from node itself,𝑢 𝑁 𝑣&, 𝐦*First aggregate from neighborsJure Leskovec & Mina Ghashami, Stanford University33

¡Putting things together:§ (1) Message: each node computes a message(*)𝐦- MSG * 𝐡-*2, , 𝑢 {𝑁 𝑣 𝑣}§ (2) Aggregation: aggregate messages from neighbors(&)𝐡 AGG&𝐦(& , 𝑢 𝑁 𝑣, 𝐦 &§ Nonlinearity (activation): Adds expressiveness§ Often written as 𝜎( ): ReLU( ), Sigmoid( ) , § Can be added to message or aggregation(2) Aggregation(1) MessageJure Leskovec & Mina Ghashami, Stanford University34

T. Kipf, M. Welling. Semi-Supervised Classification with Graph Convolutional Networks, ICLR 2017¡(1) Graph Convolutional Networks (GCN)(&)𝐡* 𝜎 𝐖&𝐡 &()H𝑁 𝑣 , *¡How to write this as Message Aggregation?Message(&)𝐡* 𝜎H 𝐖& , *𝐡 &()𝑁 𝑣(2) Aggregation(1) MessageAggregationJure Leskovec & Mina Ghashami, Stanford University35

¡(1) Graph Convolutional Networks (GCN)&()(&)𝐡* 𝜎H 𝐖& , *¡Message:§ Each¡𝐡 𝑁 𝑣(&)Neighbor: 𝐦 Aggregation:), *𝐖&𝐡 &()(2) Aggregation(1) MessageNormalized by node degree(In the GCN paper they use a slightlydifferent normalization)§ Sum over messages from neighbors, then apply activation&§ 𝐡* 𝜎 Sum&𝐦 , 𝑢 𝑁 𝑣Jure Leskovec & Mina Ghashami, Stanford University36

Hamilton et al. Inductive Representation Learning on Large Graphs, NeurIPS 2017¡(2) GraphSAGE(&)𝐡* 𝜎 𝐖 (&) I CONCAT 𝐡*&() , AGG¡𝐡 &() , 𝑢 𝑁 𝑣How to write this as Message Aggregation?§ Message is computed within the AGG § Two-stage aggregation§ Stage 1: Aggregate from node neighbors(!)𝐡((") AGG(!%&)𝐡', 𝑢 𝑁 𝑣§ Stage 2: Further aggregate over the node itself(!)!%&𝐡" 𝜎 𝐖 (!) CONCAT(𝐡"Jure Leskovec & Mina Ghashami, Stanford University(!), 𝐡((") )37

¡Mean: Take a weighted average of neighborsAGG 2Aggregation - E(%)¡(*2,)𝐡-𝑁(𝑣)Message computationPool: Transform neighbor vectors and applysymmetric vector function Mean( ) or Max( )(*2,)AGG Mean({MLP(𝐡Aggregation), 𝑢 𝑁(𝑣)})Message computationJure Leskovec & Mina Ghashami, Stanford University38