Semi-Supervised Classification with Graph Convolutional Networks

时间：2017

Intro

要解决的问题：图上的结点分类，其中只有小部分结点有label。

这是一个基于图的半监督学习，可以通过在损失函数中额外加一项graph-based regularization来解决：
Semi-Supervised Classification with Graph Convolutional Networks
其中 $\mathcal{L}_0$ 表示label的损失， $f$ 表示神经网络， $X$ 是结点特征矩阵， $\Delta=D-A$ 表示unnormalized graph Laplacian(???)， $A$ 是邻接矩阵， $D_{ii}=\sum_jA_{ij}$ ，这个方程假设了连接的结点更可能有一样的label，但因为边的存在除了表示结点之间的相似性外还有别的信息，所以这一假设可能限制模型的表达能力

本文通过直接用神经网络来encode图结构并在 $\mathcal{L}_0$ 上训练来避免在损失函数中包括graph-based regularization，以邻接矩阵 $A$ 为条件的神经网络会使得模型将监督学习损失的梯度信息传递到其他图的其他结点上，使得无论是否有标签的结点都能学习到好的representation

本文贡献有以下两点

提出了一个直接在图上作用的神经网络
使用提出的网络在图上进行半监督学习，得到了更好的效果

Fast Approximate convolutions on graphs

multi-layer GCN的一层传播规则如下
Semi-Supervised Classification with Graph Convolutional Networks
其中 $\tilde{A}=A+I_N$ ，是无向图 $\mathcal{G}$ 的邻接矩阵加上每个结点自连接， $\tilde{D}_{ii}=\sum_j{\tilde{A}_{ij}}$ ， $W^{(l)}$ 是训练参数， $H^{(l)}\in R^{N\times D}$ 是第 $l$ 层的**矩阵，且 $H^{(l)}=X$ ，接下来证明这个形式是受到图上局部光谱滤波（localized spectral filter）的一阶逼近得到的

Spectral Graph Convolutions

图上的谱卷积定义为对信号 $x\in R^N$ 和卷积核 $g_\theta=diag(\theta)$ 的乘积
Semi-Supervised Classification with Graph Convolutional Networks
其中 $U$ 是normalized graph Laplacian $L=I_N-D^{-\frac{1}{2}}AD^{\frac{1}{2}}=U\Lambda U^T$ 的特征向量，其中 $\Lambda$ 是特征值的对角矩阵， $U^Tx$ 是图傅里叶变换，可以将 $g_\theta$ 看做 $L$ 的特征值的函数 $g_\theta(\Lambda)$ ，上图的计算复杂度很高，因此通过truncated expansion来逼近
Semi-Supervised Classification with Graph Convolutional Networks
此时计算复杂度由 $O(\mathcal{N}^2)$ 降低到了 $O(|\varepsilon|)$