Notes on: Kipf, T. N., & Welling, M. (2016): Semi-Supervised Classification With Graph Convolutional Networks

Table of Contents

Notation

  • kipf16_semi_super_class_with_graph_convol_networ_e5a9b79bf764a03f7bb21c9b0c297741700a9fdc.png denotes supervised loss wrt. labeled part of graph
  • kipf16_semi_super_class_with_graph_convol_networ_a8a87b931e8db55bcb596578ebfc43cf3a267473.png denotes differentiable function (e.g. neural network)
  • kipf16_semi_super_class_with_graph_convol_networ_339c704fc9bf0c2f6780a0a0e68b51e128bb7f74.png is a weighting factor
  • kipf16_semi_super_class_with_graph_convol_networ_0207be880056b9a69e22e729dd37bced29cd174a.png matrix of node feature vectors kipf16_semi_super_class_with_graph_convol_networ_42b3c8f6ed56c7cfb60e6194029bee525c549d11.png
  • kipf16_semi_super_class_with_graph_convol_networ_be9bef8c9a4029212f1fe3fa07da21ccbe6ffa3e.png denotes unnormalized graph Laplacian of an undirected graph kipf16_semi_super_class_with_graph_convol_networ_0a240de060e0e7dfbc19b4886ffa4b861d3ca8ef.png
  • kipf16_semi_super_class_with_graph_convol_networ_e10e2b430f95617381cdd6d6b52aed29fb971dff.png denotes # of nodes in kipf16_semi_super_class_with_graph_convol_networ_892982d5999047c0afd7bb10305003bf4a4dde7d.png
  • edges kipf16_semi_super_class_with_graph_convol_networ_7106de52a40dd2d9a6f60ab9b2eaaf495334070d.png
  • adjacency matrix kipf16_semi_super_class_with_graph_convol_networ_752aba310cec2bc6631305bfda7861cfe845b706.png (binary or weighted)
  • kipf16_semi_super_class_with_graph_convol_networ_1ce0127424f0e6a52f04f3e00b80d6a88f963ad4.png is the adjaceny matrix of the undirected graph with added self-connections
  • kipf16_semi_super_class_with_graph_convol_networ_42bd9a385c727f8df068ab6d7adc755499bf10d1.png
  • kipf16_semi_super_class_with_graph_convol_networ_d11d0062b33fc47d97b067aabf9556eda9cddc31.png is a layer-specific trainable weight matrix
  • kipf16_semi_super_class_with_graph_convol_networ_0caf7f021b652c27be5d0abcb90c1ed62647c3df.png denotes activation function, e.g. kipf16_semi_super_class_with_graph_convol_networ_05f40b6975b11df89a01dfe23d78fb7ddec2d731.png
  • kipf16_semi_super_class_with_graph_convol_networ_25f1719050484f5bf5d9520afb08e1cc5d6ff37b.png is the matrix of activations in the l-th layer; kipf16_semi_super_class_with_graph_convol_networ_4e8bfc0366aea620cbb8d2bc5c6928db213db6be.png.
  • kipf16_semi_super_class_with_graph_convol_networ_8a42046c9f9a58c9864b919c1d7d01f56b3ec2b6.png is the set of node indices that have labels

Update rule

kipf16_semi_super_class_with_graph_convol_networ_14ae5cb85ca4c828bde0f221a591886e17143f9e.png

  • Normalized Laplacian with self-loops, and then we multiply it by the activations of the previous layer (kipf16_semi_super_class_with_graph_convol_networ_7e72fb5c0184b739a92fbbff2c8d6f99b8b5c59e.png) and the weight matrix connecting the previous layer to the current one (kipf16_semi_super_class_with_graph_convol_networ_d11d0062b33fc47d97b067aabf9556eda9cddc31.png)
  • I like to "visualize" it as:
    1. Flatten input graph
    2. Activations of the hidden layer is then the another graph, so we've basically projected the input-graph onto another graph by the use of the weight-matrix kipf16_semi_super_class_with_graph_convol_networ_d11d0062b33fc47d97b067aabf9556eda9cddc31.png

Spectral Graph Convolutions

Example: 2-layer GCN

  • kipf16_semi_super_class_with_graph_convol_networ_61cf5e7119ec11fd49e026d931582b8361cb75e7.png is an input-to-hidden weight matrix for a hidden layer with kipf16_semi_super_class_with_graph_convol_networ_f1330523c697c7f312e3dcdd0386cfbf0532a867.png feature maps
  • kipf16_semi_super_class_with_graph_convol_networ_7cacce225b21d6b2d0d2970a3dba097dad0fd5f7.png is an hidden-to-output weight matrix
  • kipf16_semi_super_class_with_graph_convol_networ_2b69d94b7228ba0192cf11efa4025fea0a438454.png with kipf16_semi_super_class_with_graph_convol_networ_ad2e63471d6579c71c99a79734ac5cbad849ccb7.png, is applied row-wise
  • Semi-supervised multi-class classification, we evaluate cross-entropy error over all labeled examples:

    kipf16_semi_super_class_with_graph_convol_networ_ca34e724cb565db02dee8332dd05bbdc6cd89774.png

    where kipf16_semi_super_class_with_graph_convol_networ_8a42046c9f9a58c9864b919c1d7d01f56b3ec2b6.png is the set of node indices that have labels, and kipf16_semi_super_class_with_graph_convol_networ_cdd1cc131da6040eca078917132a377727053c44.png denotes the outputs, and since we're using sigmoid it represents a distribution, and the sum then becomes the expectation over our output.