Graph Neural Networks: GCN & GraphSAGE

A Bit of History

Traditional deep learning models like CNNs operate on regular grids (images) and RNNs operate on sequences (text, audio). However, real-world data like social networks, chemical molecules, and knowledge bases are non-Euclidean graphs. In 2017, Thomas Kipf and Max Welling published "Semi-Supervised Classification with Graph Convolutional Networks" (ICLR 2017), simplifying spectral graph convolutions via a 1st-order localized Chebyshev polynomial approximation.

Later that year, William L. Hamilton, Rex Ying, and Jure Leskovec introduced GraphSAGE ("Inductive Representation Learning on Large Graphs", NIPS 2017). GraphSAGE shifted graph machine learning from transductive (requiring the entire static graph at training) to inductive representation learning by sampling fixed-size node neighborhoods and training parameterized aggregator functions.

Graph Convolutional Networks (GCN)

GCN generalizes image convolutions to graph structures using the normalized graph Laplacian $\mathbf{L} = I_N - D^{-1/2} A D^{-1/2}$. Kipf & Welling derived a 1st-order localized approximation of spectral graph convolutions, resulting in the layer-wise propagation rule:

$$H^{(l+1)} = \sigma \left( \tilde{D}^{-\frac{1}{2}} \tilde{A} \tilde{D}^{-\frac{1}{2}} H^{(l)} W^{(l)} \right)$$

• $\tilde{A} = A + I_N$: Adjacency matrix $A$ with added self-loops $I_N$ so a node includes its own feature vector during message passing.
• $\tilde{D}_{ii} = \sum_j \tilde{A}_{ij}$: Degree matrix of $\tilde{A}$.
• $\tilde{D}^{-1/2} \tilde{A} \tilde{D}^{-1/2}$: Symmetric normalized adjacency matrix. Normalizes node features by the square root of neighbor degrees to prevent exploding/vanishing feature scales.
• $H^{(l)} \in \mathbb{R}^{N \times d_l}$: Feature matrix at layer $l$, where $H^{(0)} = X$ (input node features).
• $W^{(l)} \in \mathbb{R}^{d_l \times d_{l+1}}$: Trainable weight matrix.
• $\sigma(\cdot)$: Non-linear activation function (e.g., ReLU).

GraphSAGE: Inductive Learning

Full-batch GCN requires computing matrix multiplications over the entire adjacency matrix $\tilde{A}$, making it transductive and difficult to scale to massive graphs (e.g., Pinterest's billions of nodes). GraphSAGE solves this via **inductive neighborhood sampling** and **aggregators**:

                            flowchart TD
                                Subgraph Sampled Neighborhood
                                    N1((Neighbor 1))
                                    N2((Neighbor 2))
                                    N3((Neighbor 3))
                                end
                                N1 --> AGG[Aggregator Function
Mean / Pool / LSTM]
                                N2 --> AGG
                                N3 --> AGG
                                AGG --> CONCAT[Concat h_v & Aggregated]
                                CONCAT --> Dense[Linear W & ReLU]
                                Dense --> Out((Updated h_v))
                                style AGG fill:#3B9797,stroke:#132440,color:#ffffff
                                style Out fill:#16476A,stroke:#132440,color:#ffffff
                            

GraphSAGE's layer update equation for node $v$:

$$h_{\mathcal{N}(v)}^{(k)} = \text{AGGREGATE}_k \left( \left\{ h_u^{(k-1)}, \forall u \in \mathcal{N}(v) \right\} \right)$$

$$h_v^{(k)} = \sigma \left( W^{(k)} \cdot \text{CONCAT} \left( h_v^{(k-1)}, h_{\mathcal{N}(v)}^{(k)} \right) \right)$$

Common Aggregator Functions:

• Mean Aggregator: Takes the element-wise mean of neighbor feature vectors.
• Pooling Aggregator: Applies a multi-layer perceptron (MLP) to neighbor vectors followed by max-pooling: $\max(\{ \sigma(W_{pool} h_u + b) \})$.
• LSTM Aggregator: Feeds randomly permuted neighbor vectors through an LSTM for higher expressiveness.

Worked Examples

Complexity Analysis

PyTorch & NumPy Implementations

import numpy as np

def gcn_layer_numpy(A, H, W):
    """
    NumPy implementation of a single GCN Layer.
    A: Adjacency matrix (N x N)
    H: Input node features (N x d_in)
    W: Weight matrix (d_in x d_out)
    """
    N = A.shape[0]
    A_tilde = A + np.eye(N)  # Add self-loops
    D_tilde = np.diag(np.sum(A_tilde, axis=1))

    # D_tilde^(-1/2)
    D_inv_sqrt = np.power(D_tilde, -0.5, where=D_tilde!=0)
    D_inv_sqrt[D_tilde == 0] = 0

    # Symmetric Normalization: D^(-1/2) * A_tilde * D^(-1/2)
    norm_A = D_inv_sqrt @ A_tilde @ D_inv_sqrt

    # Forward pass: ReLU( norm_A * H * W )
    out = norm_A @ H @ W
    return np.maximum(0, out)  # ReLU activation

# Test NumPy GCN
A = np.array([[0, 1, 1], [1, 0, 0], [1, 0, 0]])
H = np.array([[1.0, 0.0], [0.0, 1.0], [1.0, 1.0]])
W = np.array([[0.5, -0.5], [1.0, 0.5]])

print("GCN Layer Output (NumPy):")
print(gcn_layer_numpy(A, H, W))


# -------------------------------------------------------------
# PyTorch PyG-style GraphSAGE Aggregator
# -------------------------------------------------------------
import torch
import torch.nn as nn

class GraphSAGELayer(nn.Module):
    def __init__(self, in_features, out_features):
        super(GraphSAGELayer, self).__init__()
        self.W_self = nn.Linear(in_features, out_features, bias=False)
        self.W_neigh = nn.Linear(in_features, out_features, bias=False)
        self.act = nn.ReLU()

    def forward(self, x, adj):
        """
        x: Node features tensor (N, in_features)
        adj: Normalized Adjacency matrix without self-loops (N, N)
        """
        # Mean Neighbor Aggregation: D^(-1) * A * X
        deg = torch.sum(adj, dim=1, keepdim=True).clamp(min=1)
        norm_adj = adj / deg
        h_neigh = torch.matmul(norm_adj, x)

        # Concatenate self and neighbor representations via linear transformations
        out = self.W_self(x) + self.W_neigh(h_neigh)
        return self.act(out)

# Test PyTorch GraphSAGE Layer
sage = GraphSAGELayer(in_features=2, out_features=4)
x_tensor = torch.tensor(H, dtype=torch.float32)
adj_tensor = torch.tensor(A, dtype=torch.float32)

print("\nGraphSAGE Layer Output (PyTorch):")
print(sage(x_tensor, adj_tensor))

Real-World Applications

Exercises

1. Derive why adding self-loops $I_N$ to $A$ is necessary in GCN (what happens during feature aggregation if $A_{ii} = 0$?).
2. Prove that a $k$-layer GCN aggregates node features from a $k$-hop neighborhood.
3. Compare GraphSAGE's Mean, Max-Pooling, and LSTM aggregators in terms of permutation invariance and computational overhead.
4. Challenge: Implement mini-batch neighbor sampling for GraphSAGE using PyTorch Geometric (PyG).

Limitations & Over-Smoothing