Graph Convolutional Network (GCN)

GCNs are broadly categorized by their mathematical approach to convolution. Spectral methods define convolution via the graph Fourier transform, operating in the eigenbasis of the graph Laplacian. This provides a rigorous mathematical foundation but is computationally expensive and inherently transductive. Spatial methods define convolution directly on the graph topology as a weighted aggregation of neighbor features, bypassing the expensive eigendecomposition.

• Spectral: ChebNet approximates filters using Chebyshev polynomials of the Laplacian, avoiding full eigendecomposition.
• Spatial: GraphSAGE samples and aggregates features from a node's local neighborhood, enabling inductive learning on unseen nodes.
• Molecular Relevance: Spatial methods dominate in drug discovery because they naturally handle variable molecular sizes and enable batch training across diverse graphs.

The core operation in Kipf & Welling's GCN is the symmetric normalization of the adjacency matrix: D⁻¹/² A D⁻¹/². This normalization serves two critical purposes. First, it prevents numerical instability by scaling feature vectors to prevent their magnitude from exploding during repeated aggregation. Second, it gives higher weight to neighbors with lower degree, preventing high-degree 'hub' nodes from dominating the learning signal.

• Self-loops: Adding the identity matrix (A + I) ensures a node retains its own feature information during the update.
• Renormalization trick: Using (D + I)⁻¹/² (A + I) (D + I)⁻¹/² further improves gradient flow in deep networks.
• Molecular context: This normalization is analogous to accounting for the varying valency and coordination numbers of atoms in a molecule.

The forward pass of a GCN layer is defined as H⁽ˡ⁺¹⁾ = σ( H⁽ˡ⁾ W⁽ˡ⁾), where  is the normalized adjacency with self-loops, H⁽ˡ⁾ is the node feature matrix at layer l, W⁽ˡ⁾ is a learnable weight matrix, and σ is a non-linear activation like ReLU. This operation is a first-order approximation of spectral graph convolution.

• Message Passing: Each node's new representation is a non-linear transformation of the weighted sum of its neighbors' previous representations.
• Weight Sharing: The same weight matrix W is applied across all nodes, making the operation permutation invariant and independent of graph size.
• Stacking Layers: A 2-layer GCN aggregates information from 2-hop neighborhoods. In molecules, this means an atom 'sees' its bonded neighbors and their neighbors, capturing functional group context.

As GCN layers are stacked deeper, node representations become increasingly similar and converge to a stationary point, losing discriminative power. This over-smoothing occurs because repeated Laplacian smoothing acts as a low-pass filter, averaging away high-frequency signals that encode local structural differences.

• Theoretical limit: Node features converge to a linear subspace determined by the graph topology, independent of input features.
• Mitigation strategies: Residual connections (adding input to output), Jumping Knowledge Networks (aggregating all intermediate layers), and DropEdge (randomly dropping edges during training) all combat over-smoothing.
• Molecular design: For property prediction, shallow 2-4 layer GCNs are standard. Deep GCNs require explicit regularization to capture long-range dependencies in large molecules or crystal structures.

GCNs are fundamentally permutation invariant at the graph level and permutation equivariant at the node level. If the node ordering of the input adjacency matrix is permuted, the graph-level output (e.g., molecular property) remains unchanged, while the node-level outputs permute identically. This is a direct consequence of the message-passing operation being independent of node indexing.

• Invariance: f(P A Pᵀ, P X) = f(A, X) for any permutation matrix P.
• Equivariance: f(P A Pᵀ, P X) = P f(A, X).
• Contrast with 3D: Standard GCNs are invariant to node permutations but not to 3D rotations. For molecular conformers, E(3)-equivariant networks like NequIP are required to respect physical symmetries.

For graph-level tasks like predicting molecular solubility or toxicity, node-level features must be aggregated into a single graph representation. The readout function performs this aggregation. Simple methods include sum, mean, or max pooling of all node features. More sophisticated approaches learn hierarchical representations.

• Sum pooling: Preserves total count information, making it sensitive to graph size. Preferred for molecular property prediction where atom count matters.
• Mean pooling: Normalizes for graph size, useful when comparing graphs of different sizes.
• Set2Set: A learnable readout using an LSTM-based attention mechanism that iteratively aggregates a weighted sum of node features.
• DiffPool: Learns a differentiable soft assignment of nodes to clusters, building a hierarchical coarsened graph before final readout.

A general framework that unifies many GNN architectures, including GCNs. MPNNs operate in two phases: a message function computes information to send from each neighbor, and an update function integrates these messages into a new node state. The GCN is a specific instance of an MPNN where the message is the normalized feature vector of the neighbor and the update is a weighted sum followed by a non-linear activation.

A classical graph isomorphism heuristic that defines the theoretical upper bound for the discriminative power of standard GCNs. The test iteratively aggregates and hashes the labels of a node's neighbors to create refined labels. A GCN is at most as powerful as the 1-WL test, meaning it cannot distinguish certain non-isomorphic graphs. Architectures like Graph Isomorphism Networks (GIN) are explicitly designed to achieve WL-equivalent power.

An evolution of the GCN that replaces the fixed, structure-based normalization with a learnable self-attention mechanism. Instead of weighting neighbors solely by graph degree, GAT computes dynamic attention coefficients for each edge, allowing the model to implicitly assign different importance to different neighbors. This provides greater flexibility for heterophilic graphs where dissimilar nodes connect.

GCNs can be derived from two perspectives:

• Spectral: Defines convolution via the graph Laplacian's eigendecomposition and the Fourier transform on graphs. The original GCN by Kipf & Welling uses a first-order Chebyshev approximation of a spectral filter.
• Spatial: Defines convolution directly on the graph topology by aggregating features from local neighborhoods. This is the dominant modern interpretation and the basis for MPNNs.

A theoretically maximally powerful GNN under the WL test. GIN addresses the representational limitations of GCNs by using an injective multiset aggregation function. Its update rule is: h_v = MLP((1 + ε) · h_v + Σ_{u∈N(v)} h_u), where ε is a learnable parameter. This ensures distinct neighborhood multisets map to distinct embeddings, a property that mean-pooling GCNs lack.

A fundamental limitation of deep GCNs where node representations become indistinguishable as the number of layers increases. Because each convolution layer acts as a low-pass filter and a local averaging operator, stacking many layers causes all node features to converge to the same value. Solutions include skip connections, Jumping Knowledge Networks, and Graph U-Nets that preserve local information from earlier layers.