Semi-Supervised Classification with Graph Convolutional Networks

Semi-Supervised Classification with Graph Convolutional Networks

Thomas N. Kipf, Max Welling

Intro

考虑的问题是node classification，且只有部分的node有label。也就是semi-supervised问题。

$$ \mathcal{L} = \mathcal{L}0 + \lambda \mathcal{L}{reg}\ \mathcal{L}{reg} = \sum{ij} A_{ij} | f(X_i) - f(X_j) |^2 = f(X)^T \Delta f(X)

$$

其中$$\mathcal{L}0$$对应的是图中的labelled部分，$$f$$ 可以是neural network，$$\Delta = D - A$$是laplacian matrix。$$D$$是degree diagonal matrix，$$D{ii} = \sumj A{ij}$$。

注：这个formulation的意思是如果两个节点相连，那么就用他们feature之差进行regularize。即为文中所说， label information is smoothed over the graph via some form of explicit graph-based regularization。这个假设有一个前提，就是相连的node很可能也有相同的label；这会带来另外一个问题，就是node feature可能会有其他额外的信息。

这里我们使用neural network $$f(X, A)$$ 直接编码graph structure，避免使用graph－based regularization，从而来避免这个问题。

我们的贡献主要有两个

  1. 引入了一个简单，但是性能不错的layer－wise propagation rule给neural network，使得它能够直接在graph上进行操作，且展示了它是如何根据first-order approximation of spectral graph convolutions中得到的。
  2. 其次我们展示了这种形式的graph－based neural network如何用于fast & scalable semi－supervised learning。

Fast Approximate Convolutions on Graphs

给一个theoretical motivation。我们考虑到gcn使用以下layer-wise propagation:

$$ H^{l+1} = \sigma(\tilde D^{-1/2} \tilde A \tilde D^{-1/2} H^{(l)} W^{(l)})

$$

这里$$\tilde A = A + IN$$是adjacency matrix加上self-loop，即$$I_N$$是identity matrix。$$\tilde D{ii} = \sumj \tilde A{ij}$$，而$$W$$是每一层trainable parameter。$$H^{(l)} \in \mathbb{R}^{N \times D}$$是第$$l$$层activation之后的layer；$$H_0 = X$$。

下面我们会展示这种形式的propagation rule如何通过first-order approximation of localized spectral filters来启发的。

Spectral Graph Convolutions

graph上的spectral convolution定义为Fourier domain下的signal $$x$$乘积上filter $$g_\theta = diag(\theta)$$，这个filter是通过$$\theta \in \mathbb{R}^N$$进行参数化。也就是

$$ g\theta * x = U g\theta U^T x

$$

其中$$U$$是normalized Laplacian matrix的eigenvalue matrix，而normalized Laplacian matrix $$L=IN - D^{-1/2} A D^{-1/2} = U \Lambda U$$。$$\Lambda$$是eigenvalue matrix的diagonal，而$$U^T x$$ 是 $$x$$ 的graph Fourier transform(?)。我们可以把$$g\theta$$当作是关于diagonal matrix $$\Lambda$$的函数，即 $$g_\theta(\Lambda)$$。

但是计算$$L$$的eigenvalue是非常贵的，这里使用了一个approximation，Chebyshev polynomials $$T_k(x)$$ （一直到K阶）

$$ g{\theta'} (\Lambda) \approx \sum{k=0}^K \theta'_k T_k(\tilde \Lambda)

$$

这里有一个rescaling factor $$\tilde \Lambda = \frac{2}{\lambda{max}} \Lambda - I_N$$。$$\theta'$$是Chebyshev 系数中的一个向量。而Chebyshev polynomials是通过迭代的定义为$$T_k(x) = 2T{k-1}(x) - T_{k-2}(x), T_0(x) = 1, T_1(x) = x$$。

回到关于signal $$x$$上的convolution定义（with filter $$g_\theta$$)，我们有

$$ g\theta * x = U g\theta U^T x \approx \sum{k=1}^K U \theta_k T_k(\tilde \Lambda) U^T x = \sum{k=1}^K \theta_k T_k(\tilde L) x

$$

最后一个等式可以由$$(L)^k = (U \Lambda U^T)^k = U \Lambda^k U^T$$得到。注意这里的等式是K－localized，因为Laplacian的K阶多项式仅仅依赖于nodes最多距离central nodes K步远。这里的复杂度为$$\mathcal{O}(\mathcal{E})$$，也就是边的个数。

Layer-Wise Linear Model

graph convolution就可以通过将convolutional layers按照上述公式stack。每一层都跟着non-linear activation。

现在想象将layer－wise operation限制为$$K=1$$，也就是关于Laplacian spectrum的线性函数。通过这样的方式，我们如果stack多层layer，仍然能够得到非常丰富的信息，但不会被Chebyshev polynomials提供的explicit parameters限制住(?)。

直观上我们希望能够通过这种方法来减缓local neighborhood structure的overfitting，尤其是比较dense（degree比较大）的图，比如social network、citation network、knowledge graph。

而且当计算资源比较紧缺的时候，这种layer-wise linear formulation允许我们构造更加深的模型，也就是增强model的capacity。

在这个GCN的linear formualtion中，我们还假设$$\lambda_{max} \approx 2$$，因为neural network的参数会自动scale到相对应的范围。

有了假设之下，我们有

$$ g_\theta * x = \theta_0 x + \theta_1 (L - I_N) x = (\theta_0 - \theta_1 D^{-1/2} A D^{-1/2} ) x

$$

这个filter parameter可以整个图共享。后续的应用就可以延伸到k阶，比如连续k个filtering operators或者k层layers。

实际中，通过限制parameter个数来避免overfitting。比如如果我们假设$$\theta_0 = - \theta_1$$，就有

$$ g_\theta * x = \theta (I_N + D^{-1/2} A D^{-1/2}) x

$$

并且注意到现在$$IN + D^{-1/2} A D^{-1/2}$$的eigenvalue在$$[0, 2]$$之间。重复这个操作在数值上会带来不稳定性，从而产生exploding／vanishing gradient的问题。为了解决这个问题，我们提出了renormalization rick: $$I_N + D^{-1/2} A D^{-1/2} \to \tilde D^{-1/2} \tilde A \tilde D^{-1/2}$$，其中 $$\tilde A = I_N + A, \tilde D_i = \sum_j \tilde A{ij}$$。（但这个是怎么解决数值上的不稳定性？）

我们可以将这个从scalar generalize到vector，$$X \in \mathbb{R}^{N \times C}$$有C个channel。

$$ Z = \tilde D^{-1/2} \tilde A \tilde D^{-1/2} \Theta

$$

其中$$\Theta \in \mathbb{R}^{C \times F}$$是filter parameter matrix，而$$Z \in \mathbb{R}^{N \times F}$$是convolved signal matrix (?)。

Semi-Supervised Node Classification

首先预处理的时候，计算$$\hat A = \tilde D^{-1/2} \tilde A \tilde D^{-1/2}$$。那么forward neural network model就可以表示为

$$ Z = f(X, A) = \text{softmax} \bigg( \hat A \text{ReLU} (\hat A X W^{(0)}) W^{(1)} \bigg)

$$

对于semi－supervised问题，就对所有有label的node求cross entropy。

Appendix

几个问题

  1. 公式2中的$$^-1/2$$是哪里来的？为什么是这个形式？这个在Kipf的blog里面解释的很好，就是为了进行normalization，$$D^{-1}$$是为了在neighbor中取平均。这里需要注意的是，在node level的任务可以进行这种normalization，但是graph level的任务是否需要就得看具体情况而定。
  2. 公式3中的filter?$$$$是什么意思？是相对应于graph filter，$$$$就是convolution操作。

这几个blog补充材料很不错

  1. CSDN blog
  2. CSDN blog
  3. 知乎

关于Laplacian matrix

  • $$L=D-A$$, Combinatorial Laplacian
  • $$L = D^{-1/2} A D^{-1/2}$$, Symmetric Normalized Laplacian
  • $$L = D^{-1} A$$, Random Walk Normalized Laplacian
  • $$Laplacian$$ matrix是半正定对称矩阵，有如下的性质
    1. 对称矩阵一定有N个线性无关的特征向量
    2. 半正定矩阵的特征值非负
    3. 对称矩阵的特征向量相互正交, $$UU^T=E$$

results matching ""

    No results matching ""