Lec 05. Architectures: Graphs

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.