Graph Neural Networks: GCN & GraphSAGE

A Short History of GCN and GraphSAGE

Images and sequences come with a regular notion of “nearby.” Graphs do not: every node can have a different number of neighbors, and vertex labels carry no spatial meaning. Modern graph neural networks emerged by turning spectral graph filters into localized, reusable neighborhood operations.

The Message-Passing Lens

Forget matrices for a moment. At layer $\ell$, every node owns a vector $h_v^{(\ell)}$. A message-passing layer performs three conceptual moves:

$$m_v^{(\ell)}=\operatorname{AGG}_{\ell}\!\left(\{h_u^{(\ell)}:u\in\mathcal N(v)\}\right),\qquad h_v^{(\ell+1)}=\operatorname{UPDATE}_{\ell}\!\left(h_v^{(\ell)},m_v^{(\ell)}\right).$$

Graph Convolutional Networks (GCN)

Kipf and Welling begin from spectral graph convolution, use a localized first-order approximation, and apply a “renormalization trick.” The resulting layer is compact:

$$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$: self-loops preserve each node's own state while neighbor information arrives.
• $\tilde D_{ii}=\sum_j\tilde A_{ij}$: degree after self-loops are added.
• $S=\tilde D^{-1/2}\tilde A\tilde D^{-1/2}$: fixed, symmetric propagation weights determined by graph structure.
• $H^{(\ell)}\in\mathbb R^{n\times d_\ell}$: node representations, with $H^{(0)}=X$.
• $W^{(\ell)}\in\mathbb R^{d_\ell\times d_{\ell+1}}$: learned feature transformation shared by every node.

Why GCN Adds Self-Loops and Normalizes

A raw sum gives hubs a much larger magnitude simply because they have more neighbors. Symmetric normalization scales an edge contribution using degrees at both endpoints. This keeps the propagation operator balanced across irregular neighborhoods; it is not the same as an unweighted arithmetic mean.

The matrix order is associative: implementations may compute $SHW$ or $S(HW)$. On sparse graphs, multiplying by $S$ should use sparse edge operations—materializing a dense $n\times n$ matrix defeats the method's edge-linear scaling.

GraphSAGE: Inductive Learning

GraphSAGE learns a function for producing embeddings, not a lookup table containing one learned vector per training node. At inference time, the same parameters can embed an unseen node—or a new compatible graph—from its features and local neighborhood.

For layer $k$:

$$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)$$

Sampling & Receptive Fields

Without sampling, an $L$-layer mini-batch may need almost the whole graph: every seed requests neighbors, then neighbors of neighbors. GraphSAGE caps this expansion with a fanout $S_k$ at each layer.

GCN vs. GraphSAGE

Worked Examples

A Three-Node GCN Pass

Let node 0 connect to nodes 1 and 2. After adding self-loops, adjusted degrees are $(3,2,2)$ and

$$S=\tilde D^{-1/2}\tilde A\tilde D^{-1/2}=\begin{bmatrix}1/3&1/\sqrt6&1/\sqrt6\\1/\sqrt6&1/2&0\\1/\sqrt6&0&1/2\end{bmatrix}.$$

Use $H=\begin{bmatrix}1&0\\0&1\\1&1\end{bmatrix}$ and $W=\begin{bmatrix}0.5&-0.5\\1&0.5\end{bmatrix}$. First transform features, then propagate:

The values differ even though nodes 1 and 2 have the same degree: their own features differ, and the self-loop preserves that distinction.

A GraphSAGE Mean Input

For target 0, suppose the sampled neighbors are 1 and 2. Their mean is $((0,1)+(1,1))/2=(0.5,1)$. Mean GraphSAGE concatenates the target's own vector $(1,0)$ with that summary, producing $(1,0,0.5,1)$ before the learned linear map. The parameters—not a stored node ID embedding—decide how much self versus neighbor information to keep.

Complexity Analysis

Let $n=|V|$, $m=|E|$, input width $d$, output width $d'$, batch size $B$, depth $L$, and fanout $S_\ell$ at layer $\ell$.

Neighborhood overlap often reduces the actual sampled-node count below the tree bound. Conversely, high feature dimensions and storing activations for backpropagation can dominate memory even after sampling controls topology.

PyTorch & NumPy Implementations

The NumPy routine exposes every GCN matrix step. The PyTorch layer consumes an explicit sampled-neighbor list so the implementation matches GraphSAGE's bounded-fanout description. Production libraries replace the teaching loops with sparse kernels and batched index operations.

import numpy as np

def gcn_layer_numpy(A, H, W):
    """One dense teaching layer: ReLU(D^-1/2 (A+I) D^-1/2 H W)."""
    A = np.asarray(A, dtype=float)
    H = np.asarray(H, dtype=float)
    W = np.asarray(W, dtype=float)
    if A.ndim != 2 or A.shape[0] != A.shape[1]:
        raise ValueError("A must be square")
    n = A.shape[0]
    if H.ndim != 2 or H.shape[0] != n:
        raise ValueError("H must have one row per node")
    if W.ndim != 2 or W.shape[0] != H.shape[1]:
        raise ValueError("W has incompatible input width")
    if np.any(A < 0) or not np.allclose(A, A.T):
        raise ValueError("A must be symmetric and nonnegative")
    if not np.allclose(np.diag(A), 0):
        raise ValueError("pass A without self-loops; this layer adds them")

    A_tilde = A + np.eye(n)
    degree = A_tilde.sum(axis=1)
    inv_sqrt = degree ** -0.5
    norm_A = inv_sqrt[:, None] * A_tilde * inv_sqrt[None, :]
    return np.maximum(0, norm_A @ (H @ W))


def sample_neighbors(adj_list, fanout, rng):
    """Uniformly sample at most fanout distinct neighbors per node."""
    if fanout < 1:
        raise ValueError("fanout must be positive")
    sampled = []
    for neighbors in adj_list:
        neighbors = np.asarray(sorted(set(neighbors)), dtype=int)
        size = min(fanout, len(neighbors))
        choice = rng.choice(neighbors, size=size, replace=False)
        sampled.append(choice.tolist())
    return sampled

import torch
import torch.nn as nn

class MeanGraphSAGELayer(nn.Module):
    def __init__(self, in_features, out_features):
        super().__init__()
        self.linear = nn.Linear(2 * in_features, out_features)

    def forward(self, x, sampled_neighbors):
        summaries = []
        for v, neighbors in enumerate(sampled_neighbors):
            if neighbors:
                index = torch.as_tensor(neighbors, device=x.device)
                summaries.append(x.index_select(0, index).mean(dim=0))
            else:
                summaries.append(torch.zeros_like(x[v]))
        neighbor_mean = torch.stack(summaries)
        return torch.relu(self.linear(torch.cat([x, neighbor_mean], dim=1)))


# Three-node example used in the worked calculation
A = np.array([[0, 1, 1], [1, 0, 0], [1, 0, 0]], dtype=float)
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 output:\n", gcn_layer_numpy(A, H, W))

adj_list = [[1, 2], [0], [0]]
sampled = sample_neighbors(adj_list, fanout=1,
                           rng=np.random.default_rng(7))
sage = MeanGraphSAGELayer(in_features=2, out_features=4)
x_tensor = torch.tensor(H, dtype=torch.float32)
print("Sampled neighbors:", sampled)
print("GraphSAGE output:\n", sage(x_tensor, sampled))

Real-World Applications

GCN and GraphSAGE are architectural templates. The prediction head and loss determine whether the model classifies nodes, scores edges, or summarizes an entire graph.

Exercises

Limitations & Over-Smoothing

Also watch for train–test feature drift, disconnected or featureless nodes, information leakage through graph construction, and evaluation splits that place near-duplicate neighborhoods on both sides of the test boundary.