Skip to main content

Graph Convolutional Networks (GCN)

Learn Graph Convolutional Networks (GCN) with spectral theory, message passing, and node classification for geometric deep learning.

How does a node combine its neighbors’ features into an updated vector? Nodes represent entities, edges specify which entities exchange messages, and each node has a vector of numeric features. Begin with node 2 and its four neighbors in the worked graph.

The first view calculates a mean, sum, maximum or feature-weighted aggregate from the displayed inputs, applies the displayed 3×2 matrix W, and then ReLU. These are comparison message-passing operators. A standard GCN instead uses symmetric degree-normalized adjacency with self loops; the spectral tab separately derives the normalized Laplacian of this graph without self loops. The architecture tab is a shape schematic, not a trained model output.

Graph convolution
Aggregation
Step 1 / 100

Node 2: mean aggregate → W projection → ReLU

Node 2: input → aggregate → transform

Authored features, analytically calculated; neighbors 0, 1, 3, 4, no self loop. mean aggregate [0.5500, 0.4750, 0.3750]. W = [[1, −0.5], [0.5, 1], [−0.5, 0.5]], bias 0. ReLU(aggregate W) = [0.6000, 0.3875]. Mean/sum/max and feature-sum softmax are comparison operators, not the symmetric normalization of a standard GCN.

Scroll the table horizontally to inspect all columns.

NeighborInput features
00.8, 0.2, 0.5
10.3, 0.9, 0.1
30.2, 0.7, 0.3
40.9, 0.1, 0.6

Aggregation: mean pooling.

What are Graph Convolutional Networks?

Graph Convolutional Networks (GCNs) are neural networks designed to work directly on graph-structured data. They generalize the concept of convolution from regular grids (like images) to irregular graph structures, enabling deep learning on social networks, molecular structures, knowledge graphs, and more.

Core Concepts

The Python examples below form one runnable sequence using PyTorch. Run them in order. They use a separate five-node synthetic graph for implementation practice; its random features are not measurements or the six-node explorer output.

1. Graph Structure

A graph G = (V, E) consists of:

  • Vertices (V): Nodes representing entities
  • Edges (E): Connections between nodes
  • Features (X): Node attributes/features
  • Adjacency Matrix (A): Encodes graph structure
python
# Runnable graph representation
import torch
import torch.nn as nn
import torch.nn.functional as F

torch.manual_seed(7)
nodes = 5
edges = [(0, 1), (0, 2), (1, 2), (2, 3), (3, 4)]
adjacency = torch.zeros(nodes, nodes)
for source, target in edges:
    adjacency[source, target] = adjacency[target, source] = 1
G = {
    "nodes": list(range(nodes)),
    "edges": edges,
    "features": torch.randn(nodes, 16),
    "adjacency": adjacency,
}

2. Spectral Convolution

GCNs perform convolution in the spectral domain using the graph Laplacian:

text
Graph Laplacian: L = D - A
Normalized Laplacian: L_norm = I - D^(-1/2) A D^(-1/2)

Where:
- D: Degree matrix (diagonal)
- A: Adjacency matrix
- I: Identity matrix

3. Layer-wise Propagation Rule

The key GCN equation:

text
H^(l+1) = σ(D̃^(-1/2) Ã D̃^(-1/2) H^(l) W^(l))

Where:
- Ã = A + I (adjacency with self-loops)
- D̃: Degree matrix of Ã
- H^(l): Node features at layer l
- W^(l): Trainable weight matrix
- σ: Activation function

Message Passing Framework

Neighborhood Aggregation

GCNs follow a message-passing paradigm:

  1. Message: Information from neighbor nodes
  2. Aggregate: Combine neighbor messages
  3. Update: Transform aggregated information
python
def mean_neighbor_layer(features, adj_matrix, weight):
    # A row-normalized mean baseline; not symmetric GCN normalization.
    messages = adj_matrix @ features
    degree = adj_matrix.sum(dim=1, keepdim=True).clamp_min(1)
    aggregated = messages / degree
    return F.relu(aggregated @ weight)

weight = torch.eye(16)
mean_output = mean_neighbor_layer(G["features"], adjacency, weight)
assert mean_output.shape == (5, 16)

Aggregation Functions

Different aggregation strategies:

python
# Actual neighbor rows for node 0, excluding a self-loop.
neighbor_features = G["features"][adjacency[0].bool()]
aggregates = {
    "mean": neighbor_features.mean(dim=0),
    "sum": neighbor_features.sum(dim=0),
    "max": neighbor_features.max(dim=0).values,
}
# Authored logits illustrate a weighted sum; this is not a trained GAT.
alpha = torch.tensor([0.2, 0.8]).softmax(dim=0)
aggregates["weighted"] = (alpha[:, None] * neighbor_features).sum(dim=0)
assert all(value.shape == (16,) for value in aggregates.values())

Spectral Graph Theory

Graph Fourier Transform

The graph Fourier transform uses eigenvectors of the Laplacian:

text
Graph Fourier Transform: x̂ = U^T x
Inverse Transform: x = U x̂

Where U contains eigenvectors of L

Spectral Filtering

Convolution as multiplication in spectral domain:

text
g * x = U((U^T g) ⊙ (U^T x))

Simplified (ChebNet): g * x ≈ Σ_k θ_k T_k(L̃) x

Eigenvalue Properties

  • λ = 0: One zero mode per connected component. For D−AD-A, the mode is constant on that component; for the symmetric normalized Laplacian it is proportional to di\sqrt{d_i}.
  • Small λ: Low-frequency, smooth signals
  • Large λ: High-frequency, varying signals

Architecture Design

Typical GCN Architecture

python
class GCNLayer(nn.Module):
    def __init__(self, input_dim, output_dim):
        super().__init__()
        self.linear = nn.Linear(input_dim, output_dim, bias=False)

    def forward(self, x, adj):
        # This example accepts a dense, undirected, loop-free adjacency.
        looped = adj + torch.eye(adj.size(0), device=adj.device, dtype=adj.dtype)
        inv_sqrt = looped.sum(dim=1).rsqrt()
        normalized = inv_sqrt[:, None] * looped * inv_sqrt[None, :]
        return normalized @ self.linear(x)


class GCN(nn.Module):
    def __init__(self, input_dim, hidden_dims, output_dim, dropout=0.5):
        super().__init__()
        dims = [input_dim] + hidden_dims + [output_dim]
        self.layers = nn.ModuleList([
            GCNLayer(left, right) for left, right in zip(dims, dims[1:])
        ])
        self.dropout = dropout

    def forward(self, x, adj):
        for layer in self.layers[:-1]:
            x = F.relu(layer(x, adj))
            x = F.dropout(x, self.dropout, training=self.training)
        return F.log_softmax(self.layers[-1](x, adj), dim=1)

Depth Considerations

text
Receptive field after k layers: k-hop neighborhood

Issues with deep GCNs:
- Over-smoothing: Features become indistinguishable
- Gradient vanishing: Training becomes difficult
- Computational cost: Sampled receptive neighborhoods can grow rapidly with depth; a full-graph sparse layer still processes its edge list once.

Solutions:
- Residual connections
- Jumping knowledge networks
- DropEdge regularization

Training Strategies

Semi-supervised Learning

python
# A tiny illustrative split, not a statistically meaningful benchmark.
features = G["features"]
adj = adjacency
labels = torch.tensor([0, 0, 1, 1, 1])
train_mask = torch.tensor([True, True, True, False, False])
val_mask = torch.tensor([False, False, False, True, False])
test_mask = torch.tensor([False, False, False, False, True])
model = GCN(16, [8], 2)
optimizer = torch.optim.Adam(model.parameters(), lr=0.01)
optimizer.zero_grad()
output = model(features, adj)
loss = F.nll_loss(output[train_mask], labels[train_mask])
loss.backward()
optimizer.step()
assert torch.isfinite(loss)

Regularization Techniques

python
# A fresh forward pass allows a second optimization step.
x = F.dropout(features, p=0.5, training=model.training)


def drop_edge(adj, drop_rate=0.5):
    # Share the sampled decision across both directions of each edge.
    keep_upper = torch.triu(torch.rand_like(adj) > drop_rate, diagonal=1)
    keep = keep_upper | keep_upper.T
    return adj * keep.to(adj.dtype)


thinned = drop_edge(adj)
assert torch.equal(thinned, thinned.T)
optimizer.zero_grad()
output = model(x, thinned)
l2_reg = sum(parameter.square().sum() for parameter in model.parameters())
loss = F.nll_loss(output[train_mask], labels[train_mask]) + 5e-4 * l2_reg
loss.backward()
optimizer.step()

Variants and Extensions

GraphSAGE

Samples and aggregates from local neighborhoods:

text
h_i = σ(W · [h_i || AGG({h_j : j ∈ N(i)})])

Graph Attention Networks (GAT)

Uses attention mechanism for aggregation:

text
α_ij = softmax(LeakyReLU(a^T [W h_i || W h_j]))
h_i' = σ(Σ_j α_ij W h_j)

Graph Isomorphism Network (GIN)

With injective aggregation and suitable update functions, GIN can match the distinguishing power of the 1-WL test:

text
h_i = MLP((1 + ε) · h_i + Σ_j h_j)

Applications

1. Node Classification

  • Social network analysis
  • Protein function prediction
  • Document categorization in citation networks

2. Graph Classification

  • Molecular property prediction
  • Scene graph classification
  • Program analysis
  • Recommendation systems
  • Knowledge graph completion
  • Drug-drug interaction prediction

4. Graph Generation

  • Molecule design
  • Network synthesis
  • Scene generation

Implementation Best Practices

Data Preprocessing

python
features = (features - features.mean(dim=0)) / features.std(dim=0).clamp_min(1e-8)


def normalize_adj(adj):
    looped = adj + torch.eye(adj.size(0), dtype=adj.dtype, device=adj.device)
    inv_sqrt = looped.sum(dim=1).rsqrt()
    return inv_sqrt[:, None] * looped * inv_sqrt[None, :]


normalized = normalize_adj(adj)
assert torch.isfinite(normalized).all()

Efficient Implementation

python
# Sparse multiplication agrees with the dense calculation.
sparse_adj = normalized.to_sparse_coo().coalesce()
sparse_result = torch.sparse.mm(sparse_adj, features)
assert torch.allclose(sparse_result, normalized @ features)

# Two independent copies can be batched with block-diagonal adjacency.
batched_adj = torch.block_diag(normalized, normalized).to_sparse_coo()
batched_features = torch.cat([features, features], dim=0)
batched_result = torch.sparse.mm(batched_adj, batched_features)
assert batched_result.shape == (10, 16)

Neighbor sampling can bound the per-batch neighborhood size on larger graphs. Its sampling policy and fanouts change the estimator and should be evaluated separately from this full-graph example.

Hyperparameter Tuning

python
# Common hyperparameters
config = {
    'hidden_dims': [16, 16],    # Hidden layer sizes
    'dropout': 0.5,              # Dropout rate
    'lr': 0.01,                  # Learning rate
    'weight_decay': 5e-4,        # L2 regularization
    'epochs': 200,               # Training epochs
    'early_stopping': 10         # Patience for early stopping
}

Performance Considerations

Computational Complexity

text
Sparse GCN forward pass: O(|V| · F_in · F_out + |E| · F_out)
Storage: O(|E| + |V| · (F_in + F_out) + F_in · F_out)

Assumptions: transform XW first; sparse normalized adjacency is already available.
Dense adjacency examples above instead store O(|V|²) adjacency entries.
Training additionally stores intermediate activations and gradients.

Scalability Solutions

  1. Sampling-based methods: GraphSAINT, FastGCN
  2. Cluster-based methods: ClusterGCN
  3. Simplified models: SGC, SIGN
  4. Hardware acceleration: GPU, TPU optimization

Common Challenges

Over-smoothing

python
class ResGCN(nn.Module):
    def __init__(self, width):
        super().__init__()
        self.gcn = GCNLayer(width, width)

    def forward(self, x, adj):
        return x + F.relu(self.gcn(x, adj))


residual_output = ResGCN(16)(features, adj)
assert residual_output.shape == features.shape

Heterophily

python
# A two-relation illustration, not a general solution to heterophily.
class SignedGCN(nn.Module):
    def __init__(self, input_dim, output_dim):
        super().__init__()
        self.positive = nn.Linear(input_dim, output_dim, bias=False)
        self.negative = nn.Linear(input_dim, output_dim, bias=False)

    def forward(self, x, adj_pos, adj_neg):
        return adj_pos @ self.positive(x) - adj_neg @ self.negative(x)


positive_edges = adj.clone()
negative_edges = torch.zeros_like(adj)
negative_edges[0, 1] = negative_edges[1, 0] = 1
positive_edges[0, 1] = positive_edges[1, 0] = 0
signed_output = SignedGCN(16, 8)(features, positive_edges, negative_edges)
assert signed_output.shape == (5, 8)

Evaluation Metrics

Node Classification

  • Accuracy, F1-score, AUC-ROC
  • Per-class metrics for imbalanced datasets

Graph Classification

  • Accuracy, precision, recall
  • Matthews correlation coefficient
  • AUC, Average Precision
  • Hits@K, Mean Reciprocal Rank

Future Directions

  1. Dynamic Graphs: Temporal graph networks
  2. Heterogeneous Graphs: Multi-relational GCNs
  3. Explainability: GNNExplainer, PGExplainer
  4. Robustness: Adversarial training, certified defenses
  5. Pre-training: Self-supervised graph learning

Conclusion

Graph Convolutional Networks bridge the gap between deep learning and graph-structured data, enabling powerful representations for complex relational systems. Understanding both the spectral theory and message-passing perspectives provides insight into their effectiveness and guides architectural choices for specific applications.

Further Reading

What comes next

Next, graph attention replaces fixed structural weighting with feature-dependent, neighborhood-normalized coefficients.

If you found this explanation helpful, consider sharing it with others.

Mastodon