1 非欧数据
欧几里得数据：具有规则空间结构的数据，如一维的语音序列，二维的点阵图像，三维体素模型等。
CNN非常擅长处理欧几里得数据，卷积核扫到底，根据误差的反向传播优化卷积核的系数，实现特征提取。但CNN对非欧几里得数据很难处理。非欧数据，顾名思义，数据不是分布在欧式空间上的，自然也不满足一些欧式变换的不变性，如平移不变性——卷积核可就没法好好扫了。
非欧几里得数据：不具有规则空间结构的数据，如社交网络，知识图谱。
上述非欧几里得数据实际上是拓扑图。为了能够对这种数据也进行特征提取/卷积运算，图卷积诞生。
2 图卷积
2.1 图的拉普拉斯矩阵
图G=(V,E)，邻接矩阵A描述了各顶点两两之间的连接情况，度矩阵D描述了各顶点所连接的边数。拉普拉斯矩阵L有若干种定义：
- $L = D - A$
- $L^{sys} = D^{-1/2}AD^{-1/2}$
- $L^{rw} = D^{-1}A$
L是对称阵，可以进行特征分解：
$L=U{\rm diag}(\lambda_1,…,\lambda_n)U^{-1}$。$U=(u_1,…,.u_n)$是以列向量为特征向量的正交阵。因为U是正交阵，转置和逆相同，所以L的特征分解也可以写为$L=U{\rm diag}(\lambda_1,…,\lambda_n)U^{T}$
2.2 傅里叶变换
在信号处理中，傅里叶变换是采用不同频率的正弦波的线性组合表示一个信号，从而将时域信号在频域上表示。想想傅里叶变换是怎么表达的：$F(\omega)=\mathcal F(f(t))=\int f(t)e^{-i\omega t}dt$。对拉普拉斯算子$\Delta$而言，基函数$e^{-i\omega t}$实际上就是它的特征函数。离散的拉普拉斯算子就是拉普拉斯矩阵，因此图上的傅里叶变换就可以表示为$F(\lambda) = \sum^N_{i=1}f(i)u^*_l(i)$。这个u正好是拉普拉斯矩阵特征分解中U的特征向量，所以进一步可以表示为$F=\mathcal F_G(f)=U^Tf$。同样可以推出图的傅里叶逆变换为$f=\mathcal F_G^{-1}(f)=UF$
2.3 卷积
傅里叶变换和卷积关系密切，两个时域上函数的卷积可以表示为频域乘积的傅里叶逆变换：$f*h=\mathcal F^{-1}(F(w)H(w))$。那么推广到图，$(f*h)_G=\mathcal F_G^{-1}(FH)=U(U^Th \cdot U^Tf)=U{\rm diag}(H(\lambda_1),…,H(\lambda_n))U^Tf$
3 深度学习中的图卷积
3.1 图卷积的演进
和深度学习中的卷积一样，图卷积也并不是和理论定义完全一致的。最初DL中的图卷积就是直接将${\rm diag}(H(\lambda_1),…,H(\lambda_n))$作为卷积参数，即$y=\sigma(U\Theta U^Tx)$。但显然，此种图卷积方法在反向传播时要计算$U\Theta U^T$，且卷积核和整个图一样大，计算效率很低。
后来出了改进版本，也是最常用的版本：$y=\sigma(\sum^K_{j=0} \alpha_j L^jx)$。K是卷积核大小，$\alpha$是卷积核参数，L是拉普拉斯矩阵。这样一来，连特征分解都不需要了。
改进版本还有个特点就是有很好的空间定位性——可以保证每次卷积，都是对顶点K深度的相邻顶点以$\alpha$为权重加权求和。
3.2 图卷积网络
将上述内容整理下，图卷积网络定义如下：
- 总输入为图G=(V,E)，特征矩阵X和邻接矩阵A。这里的特征矩阵不是特征分解的矩阵，而是每个节点的特征所构成的矩阵，即$X \in \mathbb R_{N \times D}$，N是输入节点的数量，D是每个节点的特征数量。
- 图卷积一般公式$H^{(l+1)} = f(Z,A)$。Z是第L层的输出$Z=H^{(l)}\in \mathbb R_{N \times F}$，F是输出的特征的维度。f是非线性函数，如$f(H^{(l)},A) = \sigma (A^{(l)}H^{(l)}W^{(l)})$。可以看出，图卷积层在运算过程中将节点周围N个节点的特征进行了加权。
- 对第一层，令$H^0=X$
不过对于$f(H^l,A) = \sigma (A^lH^lW^l)$而言还是有一些小问题的：
- 邻接矩阵A的结构注定导致计算中不会算上节点自己的特征。解决方法：加上个单位阵I，即用$\hat A = A+I$代替A
- $\hat A$不是标准化的，相乘以后特征的尺度就会被改变了。怎么办？求$\hat A$的对角化度矩阵$\hat D$，然后上拉普拉斯矩阵$L^{sys} = \hat D^{-1/2}\hat A \hat D^{-1/2}$
经过以上trick，图卷积层的公式就变为
$$
H^{(l+1)} = \sigma (\hat D^{-1/2}\hat A \hat D^{-1/2}H^{(l)}W^{(l)})
$$
写成向量化表示，就是
$$
h_{v_i}^{(l+1)}=\sigma(\sum_j \frac{1}{c_{ij}} h^{(l)}_{v_j}W^{(l)})
$$
$c_{ij}$就是从$\hat D^{-1/2}\hat A \hat D^{-1/2}$计算得到的系数。这个式子和3.1中的改进版本是一样的。
3.3 GCN代码
有了上述基础，就可以着手构建图卷积神经网络GCN。先把$\hat D^{-1/2}\hat A \hat D^{-1/2}$搞定：
import numpy as np
import scipy.sparse as sp
# 将稀疏矩阵转化为数组
def sparse_to_tuple(sparse_mx):
# The zeroth element of the tuple contains the cell location of each
# non-zero value in the sparse matrix
# The first element of the tuple contains the value at each cell location
# in the sparse matrix
# The second element of the tuple contains the full shape of the sparse
# matrix
def to_tuple(mx):
if not sp.isspmatrix_coo(mx):
mx = mx.tocoo()
coords = np.vstack((mx.row, mx.col)).transpose()
values = mx.data
shape = mx.shape
return coords, values, shape
if isinstance(sparse_mx, list):
for i in range(len(sparse_mx)):
sparse_mx[i] = to_tuple(sparse_mx[i])
else:
sparse_mx = to_tuple(sparse_mx)
return sparse_mx
# 行标准化特征矩阵并转化为数组
def preprocess_features(features):
rowsum = np.array(features.sum(1))
r_inv = np.power(rowsum, -1).flatten()
r_inv[np.isinf(r_inv)] = 0.
r_mat_inv = sp.diags(r_inv)
features = r_mat_inv.dot(features)
return sparse_to_tuple(features)
# 对称标准化邻接矩阵，即计算拉普拉斯矩阵 L_sys
def normalize_adj(adj):
adj = sp.coo_matrix(adj)
rowsum = np.array(adj.sum(1))
d_inv_sqrt = np.power(rowsum, -0.5).flatten()
d_inv_sqrt[np.isinf(d_inv_sqrt)] = 0.
d_mat_inv_sqrt = sp.diags(d_inv_sqrt)
return adj.dot(d_mat_inv_sqrt).transpose().dot(d_mat_inv_sqrt).tocoo()
def preprocess_adj(adj):
adj_normalized = normalize_adj(adj + sp.eye(adj.shape[0]))
return sparse_to_tuple(adj_normalized)
因为图的矩阵常是稀疏矩阵，所以需要考虑稀疏矩阵的运算。先定义乘法：
def _dot(x, y, sparse=False):
if sparse:
return tf.sparse_tensor_dense_matmul(x, y)
return tf.matmul(x, y)
然后可以着手定义图卷积层：
class GraphConvLayer:
def __init__(self, input_dim, output_dim,
name, act=tf.nn.relu, bias=False):
self.input_dim = input_dim
self.output_dim = output_dim
self.act = act
self.bias = bias
# 实验表明xavier初始化比较能保证训练稳定
with tf.variable_scope(name):
with tf.name_scope('weights'):
self.w = tf.get_variable(
name='w',
shape=(self.input_dim, self.output_dim),
initializer=tf.contrib.layers.xavier_initializer())
if self.bias:
with tf.name_scope('biases'):
self.b = tf.get_variable(
name='b',
initializer=tf.constant(0.1, shape=(self.output_dim,)))
def call(self, adj_norm, x, sparse=False):
hw = _dot(x=x, y=self.w, sparse=sparse)
ahw = _dot(x=adj_norm, y=hw, sparse=True)
if not self.bias:
return self.act(ahw)
return self.act(tf.add(ahw, self.bias))
def __call__(self, *args, **kwargs):
return self.call(*args, **kwargs)
3层ReLU图卷积的网络就可以如下实现：
# 因为是稀疏矩阵，所以要用tf.sparse_placeholder
ph = {
'adj_norm': tf.sparse_placeholder(tf.float32, name="adj_mat"),
'x': tf.sparse_placeholder(tf.float32, name="x")}
l_sizes = [4, 4, 2]
o_fc1 = lg.GraphConvLayer(input_dim=feat_x.shape[-1],
output_dim=l_sizes[0],
name='fc1',
act=tf.nn.relu)(adj_norm=ph['adj_norm'],
x=ph['x'], sparse=True)
o_fc2 = lg.GraphConvLayer(input_dim=l_sizes[0],
output_dim=l_sizes[1],
name='fc2',
act=tf.nn.relu)(adj_norm=ph['adj_norm'], x=o_fc1)
o_fc3 = lg.GraphConvLayer(input_dim=l_sizes[1],
output_dim=l_sizes[2],
name='fc3',
act=tf.nn.relu)(adj_norm=ph['adj_norm'], x=o_fc2)
体会
GCN和CNN本质上并没有不同，都是在给定结构下，对结构内的元素进行加权平均的过程，只不过后者的结构会缩小，前者不变。假设将GCN用到GAN中，图的拓扑结构也是贯穿始终的“容器”，而生成的内容只不过是各个节点中的特征而已。在某些领域，比如机构学，拓扑结构才是王道。显然，无法对拓扑结构进行改变的GCN是无法应用在这种类型的场景中的。
参考文献
GCN半监督学习对图的顶点进行分类：https://github.com/tkipf/gcn （没有可视化的代码）
GCN无监督/半监督图顶点聚类教程：https://github.com/dbusbridge/gcn_tutorial （依赖包nomkl已不可用，代码没法跑）
（知乎superbrother的回答）如何理解图卷积：https://www.zhihu.com/question/54504471