Introduction — Machine Learning with Graphs

Slide 3 is the map of the whole quarter. The course is about machine learning and representation learning for graph data, and it moves through these families of methods:

• Node embeddings: DeepWalk, node2vec (lecture 2).
• Graph neural networks (GNNs): GCN, GraphSAGE, GAT and their design space.
• Graph Transformers.
• Knowledge graphs and reasoning: TransE and related embedding models.
• Generative models for graphs: GraphRNN.
• Relational Deep Learning (RDL): learning directly on relational databases.
• GNNs + LLMs, and applications in biomedicine, science and technology.

Slide 5 sets expectations: the course is self-contained and no single topic is hard by itself, but the breadth is what makes it hard. Useful background: machine learning, algorithms and graph theory, probability and statistics, linear algebra, and Python programming (PyTorch is a plus).

Slide 6 names the tools. The main library is PyG (PyTorch Geometric), a library for GNNs. GraphGym is a platform for designing GNNs: modular GNN implementations, simple hyperparameter tuning and flexible customization. For classical network analytics the slide also lists SNAP.PY and NetworkX.

For your SNA work: NetworkX/SNAP compute classical statistics (degree, centrality, clustering) that later reappear as hand-made features; PyG is where the learned versions live.

Slide 22 states the thesis of the course: graphs are a general language for describing and analyzing entities with relations or interactions. Whenever the interesting information is in how things connect, a graph is the natural data structure.

Slides 23–25 are a gallery of domains that are naturally graphs:

• Slide 23: event graphs, computer networks, disease pathways, food webs (who eats whom), particle networks, and underground (metro) networks such as the London Underground map.
• Slide 24: social networks, economic networks, communication networks, citation networks, the Internet, and networks of neurons.
• Slide 25: knowledge graphs, gene regulatory networks, scene graphs (objects in an image and their relations), code graphs, molecules (atoms and bonds) and 3D shapes (meshes).

The gallery mixes two kinds of graphs. Some are natural networks, where the graph is the system (social networks, the Internet, neurons). Others are graphs as a representation, where we choose to describe data as a graph (scene graphs, code, 3D meshes).

Slide 26 adds an important new member: relational databases are graphs. It shows database schemas from commerce, finance and clinical trials, each made of many tables linked by primary/foreign keys. Slide 27 shows the idea of Relational Deep Learning: three tables (Users, Sales, Products) become a graph. Each row is a node; each foreign-key reference (a sale points to a user and a product) is an edge. So a person on the left, the sales in the middle and the products (a shirt, shoes, sunglasses) on the right form one connected graph. The RelBench benchmark (relbench.stanford.edu) is built on this idea. This matters because most of the world's business data sits in such databases.

Slide 28 gives the main motivation: complex domains have a rich relational structure, which can be represented as a relational graph. By explicitly modeling relationships we get better performance. The main question of the course is: how do we take advantage of relational structure for better prediction?

Slides 29–30 describe the modern deep learning toolbox. It is built for simple data types: images are fixed-size 2D grids (processed by convolutional networks), and text and speech are 1D sequences (processed by sequence models). Slide 30 shows audio signals, text and an image (the Mona Lisa) as examples of sequences and grids.

Slide 31 explains why graphs do not fit this toolbox. Networks are complex:

• Arbitrary size and complex topology. There is no spatial locality like in grids. A pixel always has the same 8 neighbours; a node can have 1 neighbour or a million.
• No fixed node ordering or reference point. There is no "top-left corner" and no "first word". Any ordering of the nodes is arbitrary, so a model must give the same answer for every ordering (this idea becomes permutation invariance/equivariance in later lectures).
• Often dynamic and with multimodal features. Graphs change over time, and nodes can carry text, images or numbers.

Slide 32 asks how we can build neural networks that are much more broadly applicable, and answers: graphs are the new frontier of deep learning. Slide 33 supports this with a bar chart of the 50 most frequent keywords at ICLR 2023: "graph neural network" is highlighted in fourth place, after reinforcement learning, deep learning and representation learning, and just ahead of "transformer".

Slide 35 shows four graphs that look different but have exactly the same structure: actors linked by the movies they played in together, people linked by relations (friend, brothers, co-worker), proteins linked by interactions, and an abstract graph on nodes 1–4. All four have \(|N| = 4\) nodes and \(|E| = 4\) edges: a triangle (1, 2, 3) plus a pendant node 4 attached to node 2.

The vocabulary:

• Objects: nodes, vertices, written \(N\) (or \(V\)).
• Interactions: links, edges, written \(E\).
• System: network, graph, written \(G(N, E)\).

The point of the slide is abstraction. Once a domain is written as a graph, the same mathematics and the same algorithms apply to movies, friendships and proteins. A method that predicts a missing friendship can, in principle, predict a missing protein interaction.

Slide 36 defines a heterogeneous graph as

• nodes with node types: \(v_i \in V\);
• edges with relation types: \((v_i, r, v_j) \in E\);
• a node type \(T(v_i)\) for each node;
• a set of relation types, \(r \in R\).

Nodes and edges can also carry attributes (features). So an edge is a triple: head node, relation, tail node. This triple form returns in the knowledge-graph lectures.

Slide 37 gives two examples that are naturally heterogeneous:

• Biomedical knowledge graphs. Example node: Migraine. Example edge: (fulvestrant, Treats, Breast Neoplasms). Example node type: Protein. Example relation type: Causes.
• Academic graphs. Example node: ICML. Example edge: (GraphSAGE, NeurIPS), i.e., a paper published at a venue. Example node type: Author. Example relation type: pubYear.

The Users–Sales–Products graph from slide 27 is heterogeneous too: three node types and two relation types.

Slide 38 asks the modeling question that comes before any learning: how do we build the graph? What are the nodes, and what are the edges? The choice of representation determines whether we can use networks successfully:

• In some cases there is a unique, unambiguous representation (for example, atoms and bonds).
• In other cases the representation is not unique at all.
• The way you assign links determines the kind of question you can study. Linking people who emailed each other gives a different network, and answers different questions, than linking people who work at the same company.

Slide 39 contrasts the two basic edge types. In an undirected graph, links are symmetrical and reciprocal (collaboration, friendship on Facebook). In a directed graph, every link has a direction (phone calls, following on Twitter/X). The figure shows an undirected graph and a directed graph with arrows. Other things a link can carry: weights, properties, types and attributes.

Slide 40 defines a bipartite graph: its nodes split into two disjoint sets \(U\) and \(V\) so that every link connects a node in \(U\) to a node in \(V\). Hence \(U\) and \(V\) are independent sets (no edges inside them). The figure shows nodes A–E on the left (\(U\)) and green nodes on the right (\(V\)). Examples: authors-to-papers (authored), actors-to-movies (appeared in), users-to-movies (rated), recipes-to-ingredients (contain).

A bipartite graph can be folded (projected) onto one side: connect two nodes of \(U\) if they share at least one neighbour in \(V\). Folding author–paper gives an author collaboration network; folding user–movie ratings gives a movie co-rating network.

Folding loses information: three authors on one paper and three pairwise two-author papers give the same triangle after folding. Keep this in mind when you build co-retweet or co-hashtag networks from X/Twitter data.

Slide 42 shows one graph with the four levels at which we can ask questions:

• Node level: a property of one node.
• Edge level: a property of a pair of nodes, usually whether a link exists or will form.
• Community (subgraph) level: a property of a group of nodes, such as a dense cluster.
• Graph level: one prediction for a whole graph, and also graph generation (produce a new graph).

Slide 43 reviews the three classic tasks on a small graph with nodes A–H: node-level prediction (the "?" next to node B), link-level prediction (the dashed "?" between A and B), and graph-level prediction (a "?" for the whole graph, circled). The rest of the lecture gives real applications of each level.

Slide 45 shows node classification: some nodes are labelled (green or red), others are unknown (grey with "?"). A machine learning model fills in the missing labels. This is semi-supervised: the labelled and unlabelled nodes live in the same graph.

Slide 46 says what a node-level model must capture: the structure and position of a node in the network. Examples:

• node degree;
• node importance and position, e.g., the number of shortest paths passing through a node, or its average shortest-path length to other nodes;
• substructures around the node.

Slide 47 is a business example: user churn. Training labels with timestamps are attached to the Users–Sales–Products graph. Each user has a history like "May '23: Churn, June '23: Active", and sales carry amounts ($15, $20, $80). The task is to predict whether a user will churn (stop buying) next month. Because labels have times, training must use only information from before each label's time.

Slide 48 states the protein folding problem: computationally predict a protein's 3D structure from its amino-acid sequence alone. As a node-level task: for each node (amino acid), predict its 3D coordinates. The figure overlays experimental structures (green) with computational predictions (blue) for two targets (T1037 and T1049); they almost coincide.

Slide 49 shows the impact: a bar chart in which DeepMind's AlphaFold scores far above earlier methods in the protein-structure competition, plus news headlines saying it "could change the world of biological science" and asking whether AI has "solved" biology's protein-folding problem. Slide 50 shows the 2024 Nobel Prize in Chemistry, awarded to David Baker, Demis Hassabis and John Jumper for protein design and protein-structure prediction.

Slide 51 gives the key idea that makes it a graph problem: a spatial graph.

• Nodes: amino acids (residues) in the protein sequence.
• Edges: proximity between residues.

The architecture diagram passes information between a sequence-like representation (from a multiple sequence alignment, MSA) and a residue–residue pair representation, refines both over many blocks, and outputs the 3D structure. The pair representation is essentially a learned, dense "who is near whom" graph.

Why a graph? Two residues far apart in the sequence can be close in space, and it is these spatial contacts that determine the shape. A sequence model sees only the chain; a graph can represent the folded contacts directly.

Slide 53 defines link prediction: predict new, missing or unknown links based on the existing links. At test time, node pairs with no existing link are ranked, and the top \(K\) pairs are predicted as links. So the task is a prediction for a pair of nodes; the figure shows two dashed "?" edges, between A and B and between C and E.

Slide 54 applies it to recommender systems. Users interact with items: they watch movies, buy merchandise, listen to music.

• Nodes: users and items (a bipartite graph).
• Edges: user–item interactions.
• Goal: recommend items a user might like; the red dashed arrows ("You might also like") are predicted new edges.

Slide 55 is the industrial case PinSage (Ying et al., KDD 2018) at Pinterest. Task: recommend related pins. Given a query pin (a cake), another cake is a successful recommendation and a sweater is a bad one. The learning task is to learn node embeddings \(z_i\) so that

Related nodes should be close in the embedding space. The bottom of the slide shows the pin–board bipartite graph (pins on top, boards below) and the computation tree that aggregates a pin's neighbourhood into its embedding \(z\). This is exactly the "learn embeddings, then compare distances" idea of lecture 2.

Slide 56 motivates polypharmacy: many patients take multiple drugs to treat complex or co-existing diseases. 46% of people aged 70–79 take more than 5 drugs, and many patients take more than 20 drugs to treat heart disease, depression, insomnia, etc. Drug combinations can cause side effects that neither drug causes alone. Task: given a pair of drugs, predict their adverse side effects; the cartoon shows a probability for each possible side effect (30%, 65%).

Slide 57 shows the graph (Zitnik et al., Bioinformatics 2018):

• Nodes: drugs (triangles) and proteins (circles).
• Edges: interactions: protein–protein, drug–protein (a drug targets a protein), and drug–drug edges whose type is the side effect (e.g., \(r_1\) gastrointestinal bleeding, \(r_2\) bradycardia).

So this is a heterogeneous, multi-relational link prediction problem: predict a typed edge \((c, r, d)\). Example query: how likely is it that Simvastatin and Ciprofloxacin, taken together, break down muscle tissue?

Slide 58 shows the model's top-10 de novo predictions (pairs not in the training data), with drug \(c\), drug \(d\) and side effect \(r\). Five of the ten (ranks 1, 4, 6, 8, 9) were later supported by evidence in the medical literature, e.g., rank 1 Pyrimethamine + Aliskiren → sarcoma (Stage et al. 2015) and rank 8 Atorvastatin + Amlodipine → muscle inflammation (Banakh et al. 2017). A case report at the bottom describes severe rhabdomyolysis (muscle breakdown) due to a presumed interaction between atorvastatin and amlodipine.

Slide 60 defines the graph-level task: make a prediction for an entire graph or for a subgraph of it.

Slide 61 shows the use case: a Google Maps route between two places in the San Francisco Bay Area, with an estimated travel time. Slide 62 shows how the road network becomes a graph:

• Nodes: road segments.
• Edges: connectivity between road segments.
• Prediction: estimated time of arrival (ETA) for a route from A to B.

The route is a subgraph, so the ETA is a subgraph-level prediction. Each node carries features (small bar charts in the figure, e.g., current traffic on that segment).

Slide 63 shows DeepMind's pipeline used in Google Maps: anonymised travel data is analysed into supersegments (groups of adjacent road segments with shared traffic); these form training data for a graph neural network; its predictions rank candidate routes (from the Google Maps routing system, A→B) by ETA, and the result is surfaced in the Google Maps app and API.

Why a graph? Traffic spreads: a jam on one segment slows its neighbours a few minutes later. A model that passes information along road connections can capture this.

Drug discovery (slides 64–65). Antibiotics are small molecular graphs: nodes are atoms and edges are chemical bonds (slide 64 shows β-lactam structures such as penicillin, and bacteria on agar plates). Stokes et al. (Cell 2020) trained a GNN graph classification model to predict which molecules inhibit bacterial growth, then used it to rank a pool of candidates. Slide 65's figure shows the pipeline: a directed message-passing neural network builds bond vectors by summing and concatenating neighbouring bond vectors; it is trained on about \(10^4\) molecules; predictions are validated in the lab with iterative re-training; and the model can screen a chemical landscape of up to \(10^8\) molecules or more. For comparison, conventional lab screening handles about \(10^5\)–\(10^6\) molecules with a 1–3% hit rate.

Physics simulation (slides 66–67). Sanchez-Gonzalez et al. (ICML 2020) treat a physical system as a graph: nodes are particles and edges are interactions between nearby particles. Slide 66 shows learned simulations of water, sand and goop. Slide 67 frames it as a graph evolution task: predict how a graph will evolve over time. A learned simulator \(s_\theta\) maps state \(X^{t_0}\) to the next state again and again. Inside, an encoder builds a graph \(G^0\) (connect nearby particles), a processor applies \(M\) rounds of message passing \(G^0 \to G^1 \to \dots \to G^M\), and a decoder reads out each particle's dynamics (e.g., acceleration) \(y_i\).

Weather forecasting (slide 68). DeepMind's GraphCast uses the same encode–process–decode pattern. The input is the current weather state on a latitude–longitude grid. The encoder maps it onto a multi-resolution icosahedral mesh over the globe (meshes \(M^0\) to \(M^6\), from coarse to fine); the processor does message passing on all mesh levels simultaneously, so coarse edges carry information over long distances; the decoder maps back to the grid to get the next state \(\hat X^{t+1}\). Applying it repeatedly rolls out a forecast \(\hat X^{t+T}\).

Physics and weather are really "predict the next graph state", so they also involve node-level outputs at every step. The slides group them as graph-level because the whole system is one object.

Slide 69 closes the loop with the Users–Sales–Products database from slide 27. Typical business problems map directly onto graph tasks:

• Node-level: churn, lifetime value, next best action.
• Link-level: product affinity, recommendations.
• Graph-level: fraud, money laundering.

The main lessons of lecture 1: graphs are a general language for relational data; standard deep learning does not fit them because of arbitrary size, no node ordering and dynamic, multimodal features; the representation (what are nodes, what are edges, directed or not, typed or not, bipartite or folded) is a modeling choice that decides which questions you can answer; and almost every application is a node-, link- or (sub)graph-level prediction.