MIT 6.7960 Deep Learning — Lec 05. Architectures: Graphs

Overview

This portion explains how diverse real‑world problems—recommendation, drug safety, routing, physics simulation, and optimization—can be encoded as graph structures and tackled with graph neural networks. It contrasts classical algorithms with learned heuristics, emphasizing speed‑accuracy trade‑offs. This section explains how nodes and whole graphs can be represented as vectors

Chapter breakdown

Key points

• 00:35Phillip Isola expresses his passion for deep learning, calling it the most beautiful kind of math and intelligence.
• 02:17GNNs are not universal like MLPs; instead, their architectural constraints define the families of functions they can approximate.
• 07:14Bipartite graphs model users and interests for recommender systems.
• 10:45Physical simulations (e.g., fluids) model particles as graph nodes with force‑based edges.
• 15:57Graph Neural Networks (GNNs) learn functions from adjacency matrices and node attributes to produce node embeddings, graph embeddings, or predictions.
• 21:14A desirable property of graph models is permutation invariance: the output should not change if node indices are permuted.
• 23:41Use permutation invariance for predictions about the entire graph and permutation equivariance for node‑level predictions.
• 29:11CNNs and GNNs both rely on local operations that update representations based on neighboring data.
• 33:02A GNN layer consists of two main steps: message passing (aggregation) and node representation update.
• 38:34Bellman‑Ford shortest‑path can be implemented as a GNN where the aggregate is min and the update is a trivial MLP that adds edge cost.
• 44:37Update function implemented as a one-layer MLP combining self and neighbor messages with a pointwise non-linearity.
• 47:07Unrolling message-passing reveals it to be an MLP where neurons are vector embeddings and aggregation replaces scalar sums.
• 51:06Choosing whether to share parameters across message‑passing iterations or use a time‑dependent set of weights defines two regimes: shared (unbounded depth) vs fixed depth.
• 54:01The message‑passing steps form the forward computation graph; training proceeds by backpropagating through this unrolled graph.
• 58:17The aggregate function combines all incoming messages before sending a single message to the node.
• 01:02:20A training data point for molecule toxicity consists of node embeddings, the adjacency matrix, and a binary label for the whole graph.
• 01:07:06GNNs can only distinguish graphs that have different neighborhood tree structures; graphs with identical tree structures are equivalent from a GNN’s perspective.
• 01:121‑WL distinguishes graphs by iteratively coloring nodes; if two graphs produce the same final coloring, they are considered isomorphic.
• 01:16Simple aggregations such as sum+ReLU or mean fail to reach the same accuracy because they are not universal approximators of multiset functions.
• 19:02These limitations arise because isomorphic graphs with identical local neighborhoods can have different global properties.

Key terms

• Deep Learning — A subset of machine learning that uses neural networks with multiple layers to model complex patterns in data.
• Graph Neural Network (GNN) — A neural network architecture that operates on graph-structured data, typically using message passing with aggregation and update steps.
• Message Passing — The process by which nodes send and receive information (messages) to aggregate features from neighbors.
• Universality — The theoretical ability of a model to approximate any function given sufficient capacity and data.
• Hidden Markov Model — A probabilistic graphical model describing systems that transition between hidden states over time.
• PageRank — An algorithm that ranks web pages based on hyperlink structure, modeling importance as a probability distribution over nodes.
• Node Classification — Predicting labels or attributes for individual nodes within a graph.
• Graph Classification — Predicting a single label that describes an entire graph.
• Edge Classification — Predicting labels or attributes for individual edges within a graph.
• Architecture Constraints — Design choices that limit the hypothesis space of a model, preventing it from fitting undesirable functions.
• Approximation Power — The ability of a model to approximate a class of functions to a desired accuracy.
• Transformers — A type of neural network that uses attention mechanisms, often framed as a special case of graph networks.
• Bipartite Graph — A graph whose vertices can be divided into two disjoint sets such that edges only connect vertices from different sets.
• Drug Interaction Graph — A graph modeling relationships between drugs and the proteins they target, used to predict adverse interactions.
• Shortest Path — The path between two nodes in a graph that has the smallest total edge weight.
• Combinatorial Optimization — A class of problems that seek an optimal object from a finite, but often exponentially large, set of candidates.
• Heuristic — An approximate strategy that finds good solutions quickly but without guarantees of optimality.
• Attribute Vector — A numerical representation of node features used as input to graph algorithms.
• Node Embedding — A learned vector representation of a single graph node that captures its properties for downstream tasks.
• Graph Embedding — A single vector summarizing an entire graph, useful for graph‑level predictions.
• Adjacency matrix — A matrix representing connections between nodes in a graph; entry (i,j) indicates an edge from node i to node j.
• Permutation Invariant — A property of a function where its output remains unchanged under reordering of its input elements.
• Fully Connected Neural Network (MLP) — A neural network where each layer’s neurons are connected to all neurons in the previous layer.
• Serialization — Converting structured data, such as a graph, into a flat vector that can be processed by standard neural networks.
• Dense Graph — A graph in which many pairs of nodes are connected, leading to a high number of edges.
• Permutation matrix — A square binary matrix with exactly one 1 in each row and column; used to reorder the rows and columns of another matrix.
• Permutation invariance — The property that a graph neural network’s output remains unchanged under any reordering of the node indices.
• Permutation equivariance — Property where permuting the input indices results in the same permutation applied to the output.
• Node attribute — Feature vector associated with each node in a graph, often stored as rows of a matrix.
• Convolutional Neural Network (CNN) — A neural network that applies convolution operations to grid‑structured data, such as images.
• Invariant — A property that remains unchanged under a specified transformation.
• Equivariant — A property where a transformation of the input induces a corresponding transformation of the output.
• Local Operations — Procedures that process data by focusing on a node and its immediate neighbors, as in convolutional filters or graph message passing.
• Receptive Field — The area of the input that influences a particular node’s output, growing with each layer.
• Convolutional Filter — A small matrix (kernel) that slides over an image to produce feature maps.
• Aggregate function — A permutation‑invariant operation (e.g., sum, mean, attention) that combines messages from a node’s neighbors.
• update function — A neural mapping that updates a node embedding based on its current state and aggregated neighbor messages.
• Set Function — A function that operates on a set (unordered collection) of items.
• Multiset — A set that allows duplicate elements, often used when neighbors may share identical attributes.
• Embedding — The vector representation of a node or pixel that captures learned features.
• Stride — The step size with which a kernel moves across the input grid.
• Multiset function — A function that accepts a multiset (a set that may contain duplicate elements) and outputs a vector, ignoring the order of elements.
• Bellman‑Ford algorithm — An algorithm for computing shortest paths in a graph that can include negative edge weights, iteratively relaxing edges.
• MLP (Multi‑Layer Perceptron) — A feed‑forward neural network with at least one hidden layer, capable of universal function approximation.
• Universal Approximator — A function (or network) capable of approximating any function from a given function class to arbitrary precision.
• aggregation operator — An operation that combines a set of vectors into a single vector, e.g., sum or mean.
• readout — The final aggregation step that converts node embeddings into a graph-level representation.
• attention head — A component of a transformer that computes weighted sums of values using query-key similarities.
• Graph net — A neural network that operates on graph‑structured data via iterative message passing.
• Parameter sharing — Using the same set of weights across all message‑passing iterations.
• Time‑dependent parameters — Using a distinct set of weights for each iteration (or layer) in a depth‑unrolled graph net.
• Edge attribute — Feature vector associated with an edge, used to modulate message passing.
• Backpropagation — Gradient‑based optimization that flows through the unrolled message‑passing computation graph.
• Attention aggregation — Weighted summation of neighbor messages where weights depend on node embeddings.
• Asymptotic convergence — Property that repeated application of shared‑parameter message passing approaches a stable state.
• Readout Function — A function that summarizes node-level representations into a graph-level prediction.
• Weight Sharing — The practice of using the same parameters for all instances of a function across different nodes or edges.
• Tree Perspective — Viewing a node’s receptive field as a growing tree of neighboring nodes over successive message‑passing layers.
• Graph label pair — A representation where the entire graph has a single target label, used in graph-level prediction tasks.
• Node label pair — A representation that assigns a label to each individual node in a graph, used in node-level tasks.
• GNN — Graph Neural Network, a neural architecture that processes graph‑structured data by iteratively aggregating and updating node features.
• Neighborhood tree structure — The rooted, layered view of a node’s local subgraph, capturing how information propagates in a GNN.
• Equivalence class — A set of graphs that are indistinguishable by a particular GNN because they share the same neighborhood tree structures.
• One‑hot encoding — A binary vector that uniquely identifies each element (e.g., node) by setting one entry to one and the rest to zero.
• Graph Isomorphism — Determining whether two graphs are structurally identical up to relabeling of nodes.
• Weisfeiler–Leman Algorithm — An iterative graph coloring algorithm used to test graph isomorphism, particularly in its 1‑dimensional form.
• Aggregation Function — A neural operation that combines information from a set of nodes (or neighbors) into a single representation.
• Node Coloring — Assigning labels (colors) to nodes during the iterative WL process to capture local structure.
• Expressivity — The ability of a model to represent a wide variety of functions or patterns.
• Distinguishability — The property that two graphs can be differentiated by a given algorithm or model.
• Positional encoding — Supplementary information attached to each node that indicates its position within the graph, breaking permutation invariance.
• Graph Laplacian — A matrix representation of a graph capturing connectivity; its eigenvectors can serve as a coordinate system for nodes.
• Isomorphic graphs — Two graphs that have the same structure but possibly different node labeling; they are indistinguishable by purely structural features.
• Longest cycle — The maximum length of a simple cycle within a graph, a global property difficult for conventional GNNs to predict.
• Diameter — The greatest distance between any pair of nodes in a graph.

← All MIT OpenCourseWare course notes