Graph Classification

Suppose we want a GCN that classifies molecules as toxic or harmless.

The network inputs are the adjacency matrix and node embedding matrix $\mathbf{X}$.

• The adjacency matrix $\mathbf{A}\in {\mathbb{R}}^{N\times N}$ derives from the molecular structure.
• The columns of the node embedding matrix $\mathbf{X}\in {\mathbb{R}}^{118\times N}$ are one-hot vectors indicating which of the 118 elements of the periodic table are present.

The node embeddings can be transformed to an arbitrary size $D$ by the first weight matrix ${\Omega }_0\in {\mathbb{R}}^{D\times 118}$. The network equations are:

$$\begin{array}{rl}{\mathbf{H}}_1& =a[{\beta }_0{1}^T+{\Omega }_0\mathbf{X}(\mathbf{A}+\mathbf{I})]\\ {\mathbf{H}}_2& =a[{\beta }_1{1}^T+{\Omega }_1{\mathbf{H}}_1(\mathbf{A}+\mathbf{I})]\\ ⋮& =⋮\\ {\mathbf{H}}_K& =a[{\beta }_{K-1}{1}^T+{\Omega }_{K-1}{\mathbf{H}}_{k-1}(\mathbf{A}+\mathbf{I})]\\ f[\mathbf{X},\mathbf{A},\varphi ]& =\text{sig}[{\beta }_K+{\omega }_K{\mathbf{H}}_{K}1/N]\end{array}$$

where the network output $f[\mathbf{X},\mathbf{A},\varphi ]$ is a single value that determines the probability the molecule is toxic.

Training with batches

Given $I$ training graphs $\{{\mathbf{X}}_i,{\mathbf{A}}_i\}$ and their labels $y_i$, the parameters $\varphi =\{{\beta }_k,{\Omega }_k{\}}_{k=0}^K$ can be learned using SGD and binary cross-entropy loss. We can exploit the parallelism of modern hardware to process an entire batch of training examples concurrently. To do this, the batch elements are concatenated into a higher-dimensional tensor.

However, each graph may have a different number of nodes. Hence, the matrices ${\mathbf{X}}_i$ and ${\mathbf{A}}_i$ have different sizes, and there is no way to concatenate them into 3D tensors. Luckily, a simple trick allows us to process the whole batch in parallel. The graphs in the batch are treated as disjoint components of a single large graph. The network can then be run as a single instance of the network equations. The mean pooling is carried out only over the individual graphs to make a single representation per graph that can be fed into the loss function.