WIXLIB

Node classification: Predict a property of a node Example: Categorize online users / items Link prediction: Predict whether there are missinglinks between two nodes Example: Knowledge graph completion Graph classification: Categorize different graphs Example: Molecule property prediction Clustering: Detect if nodes form a community Example: Social circle detection Other tasks: Graph generation: Drug discovery Graph evolution: Physical simulation9/22/2021Jure Leskovec, Stanford CS224W: Machine Learning with Graphs42

Node classification: Predict a property of a node Example: Categorize online users / items Link prediction: Predict whether there are missinglinks between two nodes Example: Knowledge graph completion orizeML taskslead to Example:Molecule ng: Detect if nodes form a community Example: Social circle detection Others: Graph generation: Drug discovery Graph evolution: Physical simulation9/22/2021Jure Leskovec, Stanford CS224W: Machine Learning with Graphs43

A protein chain acquires its native 3D structureImage credit: DeepMind9/22/2021Jure Leskovec, Stanford CS224W: Machine Learning with Graphs45

Computationally predict a protein’s 3D structurebased solely on its amino acid sequenceImage credit: DeepMind9/22/2021Jure Leskovec, Stanford CS224W: Machine Learning with Graphs46

Image credit: DeepMindImage credit: SingularityHub9/22/2021Jure Leskovec, Stanford CS224W: Machine Learning with Graphs47

Key idea: “Spatial graph” Nodes: Amino acids in a protein sequence Edges: Proximity between amino acids (residues)Image credit: DeepMindSpatial graph9/22/2021Jure Leskovec, Stanford CS224W: Machine Learning with Graphs48

Users interacts with items Watch movies, buy merchandise, listen to music Nodes: Users and items Edges: User-item interactions Goal: Recommend items users might likeUsersInteractions“You might also like”Items9/22/2021Jure Leskovec, Stanford CS224W: Machine Learning with Graphs50

Ying et al., Graph Convolutional Neural Networks for Web-Scale Recommender Systems, KDD 2018Task: Recommend related pins to usersTask: Learn nodeembeddings such thatQuery pinPredict whether two nodes in a graph are related9/22/2021Jure Les kovec, Stanford CS224W: Ma chine Learning with Graphs8

PrescribedManypatients take multiple drugsDrugto treatdrugsside effectcomplex or co-existing diseases: 46% of people ages 70-79 take more than 5 drugsMany patients take more than 20 drugs to treatheart disease, depression, insomnia, etc.Task: Given a pair of drugs predictadverse side effects,30%9/22/2021Jure Leskovec, Stanford CS224W: Machine Learning with Graphsprob.65%prob.52

Zitnik et al., Modeling Polypharmacy Side Effects with Graph Convolutional Networks, Bioinformatics 2018 Nodes: Drugs & ProteinsEdges: Interactions9/22/2021Jure Leskovec, Stanford CS224W: Machine Learning with GraphsQuery: How likelywill Simvastatin andCiprofloxacin, whentaken together,break down muscletissue?53

Zitnik et al., Modeling Polypharmacy Side Effects with Graph Convolutional Networks, Bioinformatics 2018Drug c9/22/2021Drug dJure Leskovec, Stanford CS224W: Machine Learning with GraphsEvidence found54

a9/22/2021Jure Leskovec, Stanford CS224W: Machine Learning with Graphs56

Nodes: Road segmentsEdges: Connectivity between road segmentsPrediction: Time of Arrival (ETA)Image credit: DeepMind9/22/2021Jure Leskovec, Stanford CS224W: Machine Learning with Graphs57

Predicting Time of Arrival with Graph NeuralNetworks Used in Google MapsImage credit: DeepMind9/22/2021Jure Leskovec, Stanford CS224W: Machine Learning with Graphs58

Antibiotics are small molecular graphs Nodes: Atoms Edges: Chemical bondsKonaklieva, Monika I. "Molecular targets of β-lactam-based antimicrobials:beyond the usual suspects." Antibiotics 3.2 (2014): 128-142.9/22/2021Jure Leskovec, Stanford CS224W: Machine Learning with GraphsImage credit: CNN60

Stokes et al., A Deep Learning Approach to Antibiotic Discovery, Cell 2020 A Graph Neural Network graph classification modelPredict promising molecules from a pool of candidatesStokes, Jonathan M., et al. "A deep learning approach to antibiotic discovery."Cell 180.4 (2020): 688-702.9/22/2021Jure Leskovec, Stanford CS224W: Machine Learning with Graphs61

You et al., Graph Convolutional Policy Network for Goal-Directed Molecular Graph Generation, NeurIPS 2018Graph generation: Generating novel moleculesUse case 1: Generate novel moleculeswith high Drug likeness valueUse case 2: Optimize existing molecules tohave desirable propertiesDrug likeness9/22/2021Jure Leskovec, Stanford CS224W: Machine Learning with Graphs62

Sanchez-Gonzalez et al., Learning to simulate complex physics with graph networks, ICML 2020Physical simulation as a graph: Nodes: Particles Edges: Interaction between particles9/22/2021Jure Leskovec, Stanford CS224W: Machine Learning with Graphs63

Sanchez-Gonzalez et al., Learning to simulate complex physics with graph networks, ICML 2020A graph evolution task: Goal: Predict how a graph will evolve overtime9/22/2021Jure Leskovec, Stanford CS224W: Machine Learning with Graphs64

CS224W: Machine Learning with GraphsJure Leskovec, Stanford Universityhttp://cs224w.stanford.edu

Objects: nodes, verticesInteractions: links, edgesSystem: network, graph9/22/2021Jure Leskovec, Stanford CS224W: Machine Learning with GraphsNEG(N,E)66

Movie 1friendActor 2Actor 1MaryPeterMovie 3Movie 2Actor 4brothersActor 3Protein 1friendco-workerTomAlbertProtein 2Protein 5Protein 99/22/2021 N 4 E 4Jure Leskovec, Stanford CS224W: Machine Learning with Graphs67

If you connect individuals that workwith each other, you will explore aprofessional networkIf you connect those that have asexual relationship, you will beexploring sexual networksIf you connect scientific papersthat cite each other, you will bestudying the citation networkImage credit: Euro ScientistsImage credit: ResearchGateIf you connect all papers with the same word in the title,what will you be exploring? It is a network, nevertheless9/22/2021Jure Leskovec, Stanford CS224W: Machine Learning with Graphs68

How to build a graph: What are nodes? What are edges? Choice of the proper network representationof a given domain/problem determines ourability to use networks successfully: In some cases, there is a unique, unambiguousrepresentation In other cases, the representation is by no meansunique The way you assign links will determine the natureof the question you can study9/22/2021Jure Leskovec, Stanford CS224W: Machine Learning with Graphs69

Undirected DirectedLinks: undirected Links: directed(symmetrical, reciprocal)(arcs)LADBMFCIDGBAHFC Examples: Collaborations Friendship on Facebook9/22/2021EGExamples: Phone calls Following on TwitterJure Les kovec, Stanford CS224W: Ma chine Learning with Graphs70

A heterogeneous graph is defined as Nodes with node types Edges with relation types Node type Relation type9/22/2021Jure Leskovec, Stanford CS224W: Machine Learning with Graphs, http://cs224w.stanford.edu71

Biomedical Knowledge GraphsExample node: MigraineExample edge: (fulvestrant, Treats, Breast Neoplasms)Example node type: ProteinExample edge type (relation): Causes9/22/2021Academic GraphsExample node: ICMLExample edge: (GraphSAGE, NeurIPS)Example node type: AuthorExample edge type (relation): pubYearJure Leskovec, Stanford CS224W: Machine Learning with Graphs, http://cs224w.stanford.edu72

UndirectedNode degree, ki: the numberof edges adjacent to node ikA 4AIn directed networks we definean in-degree and out-degree.DBDirected1 NAvg. degree: k k å ki 2EN i 1NCEGAFSource: Node with kin 0Sink: Node with kout 09/22/2021The (total) degree of a node is thesum of in- and out-degrees.kCin 2Ek NkCout 1Jure Leskovec, Stanford CS224W: Machine Learning with GraphskC 3k in k out73

Bipartite graph is a graph whose nodes can be divided into two disjoint sets U and V such thatevery link connects a node in U to one in V; that is,U and V are independent setsExamples: Authors-to-Papers (they authored)Actors-to-Movies (they appeared in)Users-to-Movies (they rated)Recipes-to-Ingredients (they contain)ABCDEUV“Folded” networks: Author collaboration networks Movie co-rating networks9/22/2021Jure Leskovec, Stanford CS224W: Machine Learning with Graphs74

Projection U9/22/2021UVJure Leskovec, Stanford CS224W: Machine Learning with GraphsProjection V75

44332211Aij 1Aij 0if there is a link from node i to node j 0 1A 0 1 1001otherwise00011 1 1 0 0 1A 0 0 000100011 0 0 0 Note that for a directed graph (right) the matrix is not symmetric.9/22/2021Jure Leskovec, Stanford CS224W: Machine Learning with Graphs76

UndirectedDirected9/22/20214321æ0ç1çAij ç0çè1100001011ö 1 1 0øAij A jiAii 04321 0 1A 0 0 00010001NåAki ijj 1Nk j å Aiji 1NN11L å ki å Aij2 i 12 ij1 0 0 0 outNkoutinj å Aiji 1NAij ¹ A jiAii 0Jure Leskovec, Stanford CS224W: Machine Learning with GraphsL åki 1Nini åkj 1Noutj å Aiji, j77

9/22/2021Jure Leskovec, Stanford CS224W: Machine Learning with Graphs78

Most real-world networks are sparseE Emax (or k N-1)Consequence: Adjacency matrix is filled with zeros!(Density of the matrix (E/N2): WWW 1.51x10-5, MSN IM 2.27x10-8)9/22/2021Jure Leskovec, Stanford CS224W: Machine Learning with Graphs79

Represent graph as a list of edges: 9/22/2021(2, 3)(2, 4)(3, 2)(3, 4)(4, 5)(5, 2)(5, 1)2135Jure Leskovec, Stanford CS224W: Machine Learning with Graphs480

Adjacency list: Easier to work with if network is Large Sparse21 Allows us to quickly retrieve allneighbors of a given node354 1: 2: 3, 4 3: 2, 4 4: 5 5: 1, 29/22/2021Jure Leskovec, Stanford CS224W: Machine Learning with Graphs81

Possible options: 9/22/2021Weight (e.g., frequency of communication)Ranking (best friend, second best friend )Type (friend, relative, co-worker)Sign: Friend vs. Foe, Trust vs. DistrustProperties depending on the structure of the restof the graph: Number of common friendsJure Leskovec, Stanford CS224W: Machine Learning with Graphs82

Unweighted (undirected)Weighted(undirected)441123 0 1Aij 1 01011211000 1 0 0 20140.5100Aii 0Aij A jiAii 01 NE å Aij2 i, j 12Ek N1 NE nonzero( Aij )2 i , j 1Examples: Friendship, Hyperlink9/22/20213 0 2Aij 0.5 0 0 4 0 0 Aij A ji2Ek NExamples: Collaboration, Internet, RoadsJure Leskovec, Stanford CS224W: Machine Learning with Graphs83

Self-edges (self-loops)(undirected) Multigraph(undirected)441123 1 1 Aij 1 0101121100Aii 03 0 2 Aij 1 00 1 0 1 Examples: Proteins, Hyperlinks9/22/2021 11000 3 0 0 Aii 0Aij A jiN1 NE Aii Aij 2 i , j 1,i ji 120131 NE nonzero( Aij )2 i , j 1Aij A ji2Ek NExamples: Communication, CollaborationJure Leskovec, Stanford CS224W: Machine Learning with Graphs84

Connected (undirected) graph: Any two vertices can be joined by a path A disconnected graph is made up by two ormore connected componentsBBAALargest Component:Giant ComponentIsolated node (node H)DFCDFHG9/22/2021CHGJure Leskovec, Stanford CS224W: Machine Learning with Graphs85

ConnectedDisconnectedThe adjacency matrix of a network with severalcomponents can be written in a block- diagonalform, so that nonzero elements are confined tosquares, with all other elements being zero:9/22/2021Jure Leskovec, Stanford CS224W: Machine Learning with Graphs86

Strongly connected directed graph has a path from each node to every other nodeand vice versa (e.g., A-B path and B-A path) Weakly connected directed graph is connected if we disregard the edge directionsEBFAD9/22/2021CGJure Leskovec, Stanford CS224W: Machine Learning with GraphsGraph on the left is connectedbut not strongly connected (e.g.,there is no way to get from F to G byfollowing the edge directions).87

Strongly connected components (SCCs) canbe identified, but not every node is part of anontrivial strongly connected component. SCCBEABFADECFGDCGSCCSCCIn-component: nodes that can reach the SCC,Out-component: nodes that can be reached from the SCC.9/22/2021Jure Leskovec, Stanford CS224W: Machine Learning with Graphs88

Machine learning with Graphs Applications and use cases Different types of tasks: Node level Edge level Graph level Choice of a graph representation: Directed, undirected, bipartite, weighted,adjacency matrix9/22/2021Jure Leskovec, Stanford CS224W: Machine Learning with Graphs89

Machine Learning Algorithms and graph theory Probability and statistics Programming: You should be able to write non-trivial programs (in Python) Familiarity with PyTorch is a plus 9/22/2021 Jure Leskovec, Stanford