Semi-Supervised GCN

Train a two layer graph convolutional network to label the nodes of a graph when only 10 nodes of each class have labels.

The graph has three communities. Nodes link mostly inside their own community. The node features are so noisy that a classifier on the features alone gets about 50%. The edges carry the missing information. A GCN layer mixes each node's features with its neighbours' features:

A_hat = D^-1/2 (A + I) D^-1/2          # D is the degree matrix of A + I
H1    = relu(A_hat @ X @ W1)
logits = A_hat @ H1 @ W2

First write normalized_adjacency, which builds A_hat from an edge list. Then write train_gcn. It trains on the labelled nodes only and returns a predicted class for every node.

Function signature

def normalized_adjacency(edge_index, num_nodes):
def train_gcn(x, edge_index, labels, train_mask):

Example

Input

edge_index = torch.tensor([[0, 1, 1, 2],
                           [1, 0, 2, 1]])     # the path 0 - 1 - 2
normalized_adjacency(edge_index, 3)

Output

tensor([[0.5000, 0.4082, 0.0000],
        [0.4082, 0.3333, 0.4082],
        [0.0000, 0.4082, 0.5000]])

Reasoning

With self loops, nodes 0 and 2 have degree 2 and node 1 has degree 3. Entry (i, j) is 1 / sqrt(d_i * d_j) where A + I has a 1. So the corners are 1/2, the centre is 1/3, and each edge is 1 / sqrt(6) = 0.4082.

Constraints and notes

• edge_index is an int64 tensor of shape (2, E). It lists every edge in both directions and has no self loops. Some nodes can have no edges.
• normalized_adjacency can return a dense (n, n) tensor or a sparse one. The tests call .to_dense() on a sparse result.
• train_gcn gets x of shape (n, f), labels of shape (n,) and a boolean train_mask of shape (n,). Compute the loss on the masked nodes only. The labels of the other nodes are not reliable, and the tests change them to check that you do not use them.
• Return int64 predictions of shape (n,). On the unlabelled nodes, they must be at least 85% correct.