# Lec 05. Architectures: Graphs Source: https://www.youtube.com/watch?v=0niIwb37nF0 Recap page: https://rapidrecap.app/video/0niIwb37nF0 Generated: 2026-02-11T15:05:42.616+00:00 --- ## Quick Overview Graph Neural Networks (GNNs) function as a generalization of Convolutional Networks (ConvNets) designed for data structured as graphs, operating via a message-passing algorithm involving aggregation of neighbor information followed by a node update, which fundamentally introduces constraints into function approximation that guide the system to fit data in desired structural ways, rather than aiming for universal approximation like MLPs. **Key Points:** - Graph Nets generalize ConvNets to non-grid topologies and are appropriate for problems naturally specified by graphs, such as social networks, gene interactions, and website cross-referencing (PageRank). - Architecture design, including GNNs, involves adding constraints to function approximators, meaning GNNs are not universal approximators like MLPs, and this constraint is where their power comes from. - A single layer of a GNN involves two steps: an aggregate function (a permutation-invariant multiset function like summation or min) that produces a message M from neighbors' node vectors (h), and an Update function combining M and the node's current vector to create a new representation. - The Bellman-Ford shortest-path algorithm can be implemented using a GNN structure where the aggregate function is 'min' aggregation. - GNNs share commonalities with ConvNets as both rely on local operations stacked iteratively to propagate information globally, and both operate on inputs of arbitrary size. - The core difference between GNNs and ConvNets is that GNN neighborhoods have variable shapes and lack the inherent spatial structure found in grid-based ConvNet neighborhoods. - Getting a graph embedding (prediction about the entire graph) requires a final 'readout' step, which is another aggregate operator applied over all final node embeddings. **Context:** Phillip Isola, a professor in EECS, introduces Graph Neural Networks (GNNs) as the next topic in a sequence of architecture lectures, following Convolutional Networks (ConvNets). He expresses deep enthusiasm for deep learning generally and frames GNNs as a powerful generalization capable of handling graph-structured data, contrasting their constrained nature with the universality of Multi-Layer Perceptrons (MLPs). The lecture outlines covering problem suitability, the message-passing mechanism, and approximation power. ## Detailed Analysis Phillip Isola introduces Graph Neural Networks (GNNs) as a generalization of ConvNets suitable for data represented as graphs, covering applications like social networks, gene interactions, and molecular structures. He emphasizes that architecture design, exemplified by GNNs, deliberately introduces constraints to rule out certain functions, meaning GNNs are not universal approximators like MLPs, which is considered a strength for fitting data in the right ways. The core mechanism of a GNN layer is message passing: first, an 'aggregate' function (a permutation-invariant multiset function like summation or min) pools information from a node's neighbors to create a message vector (M); second, an 'Update' function combines this message M with the node's current representation (h) to generate a new, refined node embedding. This process is repeated iteratively (k steps), increasing the receptive field across the graph, analogous to stacking layers in a ConvNet. Isola notes that GNNs are analogous to ConvNets applied to non-grid graphs, differing in that GNN neighborhoods have variable sizes and lack inherent spatial structure. He demonstrates that classical algorithms like Bellman-Ford for shortest path can be formulated using only the aggregate function (min aggregation). Finally, if a prediction about the entire graph is needed (graph embedding), a final 'readout' aggregation step combines all final node embeddings into a single vector. ### GNN Overview and Purpose - Graph Nets generalize ConvNets for non-grid topologies - They introduce constraints to function approximation, unlike universal MLPs - Problems suitable for GNNs include social networks, gene interactions, and shortest path algorithms. ### Message Passing Mechanism - One layer involves two steps: Aggregate (a permutation-invariant multiset function acting on neighbors' node vectors h to produce message M) - Update (combining M with the node's current h to get a new representation). ### Aggregation Functions - Aggregate functions are constrained multiset functions, examples include summation, average, max, or min - Min aggregation allows implementation of the Bellman-Ford shortest-path algorithm. ### Relationship to ConvNets - Both rely on stacking local operations to achieve global information propagation - Both share parameters identically across local regions (like filters in ConvNets) - GNNs handle arbitrary size inputs, unlike fixed-size MLPs. ### GNN vs. ConvNet Differences - GNN neighborhoods have variable numbers of neighbors, unlike fixed patches in ConvNets - GNN neighborhoods lack the spatial structure (like up/down/left/right) present in grid graphs. ### Unrolling and MLP Analogy - Unrolling message passing steps makes the GNN look like an MLP where neurons are vectors (node embeddings) - This perspective connects GNNs to Transformers, where attention is a specific aggregation operator. ### Output and Readout - Node classification uses final node embeddings directly - Graph-level prediction requires a final 'readout' step, which is an aggregate operator over all final node embeddings.