Graph Convolutional Networks
Graph convolutional networks generalize convolution to graphs by averaging each node's features with its neighbors' using a normalized adjacency matrix.
Convolution without a grid
Images live on a regular grid, so a convolution can slide a fixed kernel across them. Graphs have no such regularity: nodes have different numbers of neighbors and no canonical ordering. Graph convolutional networks (GCNs) generalize the idea by defining a layer that mixes each node's features with those of its neighbors, weighted by the graph structure rather than by learned spatial positions.
The propagation rule
A GCN layer computes H' = sigma(D^(-1/2) A~ D^(-1/2) H W), where A~ is the adjacency matrix with added self-loops, D is its degree matrix, H is the current node features, W is a learned weight matrix, and sigma is a nonlinearity. The symmetric normalization by node degree keeps feature magnitudes stable so high-degree nodes do not dominate. Each layer aggregates information from one hop away; stacking L layers reaches L-hop neighborhoods.
- Weights are shared across all nodes, like a convolution kernel
- Edge weights come from the graph, not learned per edge as in a GAT
- Self-loops let a node retain its own features during aggregation
- Degree normalization prevents exploding activations on hubs
Over-smoothing
Because each layer averages neighbors, stacking many GCN layers pushes all node representations toward a common value, a failure called over-smoothing. In practice shallow GCNs of two or three layers work best; going deeper requires residual connections, normalization, or techniques that preserve node identity across depth.
Tasks and limits
GCNs handle node classification, link prediction, and graph-level prediction after pooling. They are simple and effective on homophilous graphs, where connected nodes tend to be similar. When edges vary in importance, the learned edge weights of graph attention networks often help. Both are special cases of the general message-passing view, which frames a graph layer as computing, sending, and aggregating messages along edges.