Consider a binary node classification task in a transductive setting.
We start with a commercial-sized graph with millions of nodes. Some nodes have ground truth binary labels, and the goal is to label the remaining unlabeled nodes. The body of the network will be the same as in the graph classification example but with a different final layer that produces an output vector of size :
where the function applies the sigmoid function independently to every element of the row input. We use binary cross-entropy loss, but now only at nodes where we know the ground truth label .
- Note that this is just a vectorized version of the basic node classification loss
Training this network has two problems:
- It’s logistically difficult to train a graph neural network of this size. We must store the node embeddings at every network layer in the forward pass. This will involve both storing and processing a structure several times the size of the entire graph (which is quite big).
- We only have a single graph, so it’s not obvious how to perform stochastic gradient descent. How can we form a batch if there is only a single object?
Batching methods
K-hop neighborhood
One way to form a batch is to choose a random subset of labeled nodes at each training step. In a GCN architecture, each node depends on its neighbors in the previous layer. These, in turn, depend on their neighbors in the layer before, so each node has a receptive field. The receptive is called the k-hop neighborhood. We can hence perform a gradient descent using the graph that forms the union of the k-hop neighborhoods of the batch nodes; the remaining inputs do not contribute.
Unfortunately if there are many layers and the graph is densely connected, every input node may be in the receptive field of every output, and this may not reduce the graph size at all. This is called the graph expansion problem. Two approaches that tackle this problem are neighborhood sampling and graph partitioning.