Graph Convolutional Networks Oct 26, 2024

Graph Convolutional Networks extend deep learning to graph-structured data by generalizing the convolution operation from regular grids (like images) to irregular graph domains. The key innovation lies in how they aggregate and transform feature information from a node’s local neighborhood through spectral or spatial convolutions. In GCNs, each layer performs neighborhood feature aggregation where a node’s representation is updated by combining its features with those of its adjacent nodes. This aggregation is typically followed by a non-linear transformation. The process can be mathematically represented as a function of the normalized adjacency matrix, feature matrix, and learned weight matrices. Here’s the pseudocode for a basic GCN layer:

def GCN_layer(adjacency_matrix A, feature_matrix X, weight_matrix W):
    # Add self-loops to adjacency matrix
    A_hat = A + identity_matrix(A.shape[0])
    
    # Compute degree matrix
    D = diagonal_matrix([sum(row) for row in A_hat])
    
    # Symmetric normalization
    D_inv_sqrt = inverse_sqrt(D)
    A_norm = D_inv_sqrt @ A_hat @ D_inv_sqrt
    
    # Feature transformation and aggregation
    H = relu(A_norm @ X @ W)
    
    return H

def GCN_forward(G, X):
    # Initialize learnable weight matrices
    W1 = initialize_weights(input_dim, hidden_dim)
    W2 = initialize_weights(hidden_dim, output_dim)
    
    # First GCN layer
    H1 = GCN_layer(G.adjacency, X, W1)
    
    # Second GCN layer
    H2 = GCN_layer(G.adjacency, H1, W2)
    
    # Final node representations
    return H2

The core operation performs message passing through  = D^{(-1/2)(A + I)D}(-1/2), where A is the adjacency matrix, I is the identity matrix (self-loops), and D is the degree matrix. This normalization prevents numerical instabilities and exploding/vanishing gradients. Each layer then applies this normalized adjacency matrix to the node features, followed by a learned weight transformation and non-linearity.

Below is that Â acting on a small two-community graph, with the weight matrix and the non-linearity stripped out so you can see what the propagation alone does. Two things are worth pulling on.

Press Single spike and step the depth up: the signal spreads exactly one hop per layer, so a GCN’s receptive field is precisely its depth — nothing more, nothing less. Then press Two communities and drag the depth all the way. The features start perfectly separated and end up indistinguishable. This is over-smoothing, and it is not a training pathology: Â has a dominant eigenvector proportional to sqrt(deg) with eigenvalue exactly 1, so repeated application drives any signal towards a multiple of that vector, which knows only about degrees and nothing about communities. Depth in a GCN destroys the signal it is supposed to be refining.