【论文解读】GCN论文阅读总结

本次要总结的论文是 Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering，论文链接GCN^[1]，参考的代码实现GCN-code^[2]。

不得不说，读懂这篇论文难度较大，因为里面有许多数学推导，要了解较多的数学知识。本人数学一般，因此在读本论文的同时参考了网上部分较优秀的讲解，这里会结合我对论文的理解，对本论文下总结，文末会详细列出我参考的讲解链接。

「建议在非深色主题下阅读本文，pc端阅读点击文末左下角“原文链接”，体验更佳」

• 回顾卷积定义与CNN

• 传统傅里叶变换与卷积

• 拉普拉斯算子与拉普拉斯矩阵

• GCN模型

• 切比雪夫多项式及其捕捉局部特征

• Graph Coarsening（图粗化）

• 文本分类实验(Text Categorization on 20NEWS)

• 数据预处理步骤

• 模型部分

• 实验结果

• 个人总结

• 参考文献

回顾卷积定义与CNN

我们知道卷积神经网络(cnn)在图像、视频、语音识别等领域取得了巨大的成功。cnn的一个核心内容就是卷积操作。

卷积核：上图中的feature map 参数共享机制：假设每个神经元连接数据窗口的权重是固定的

❝

对于input layer中，不同的数据区域，卷积核参数是共享的，但是不同的输入通道卷积核参数可以不同

❞

这种参数共享机制有如下两个优点

• 大大减少了模型需要学习的参数
• 可以将卷积操作理解为 平移不变的滤波器，这意味着它们能够独立于其空间位置识别相同的特征。

在维基百科里，可以得到卷积操作的定义： 为 的卷积

• 连续形式

• 离散形式

❝

更深入的理解可参考知乎这个回答：如何通俗易懂地解释卷积？^[3]

❞

那么对于「不规则或非欧几里德域上」的结构数据，例如社交网络用户数据、生物调控网络上的基因数据、电信网络上的日志数据或单词嵌入的文本文档数据等，可以用图形（graph）来构造，cnn上的卷积操作想直接推广到graph上并不是简单可行的，「因为卷积核池化操作只能作用在规则的网格中。」

由上面一张社交网络图可以看出，每个顶点的邻居顶点数量可能都不一致，无法直接使用卷积核池化操作进行特征提取。

为此还需要了解傅里叶变换以及拉普拉斯算子。

传统傅里叶变换与卷积

傅里叶变换的核心是「从时域到频域的变换，而这种变换是通过一组特殊的正交基来实现的。即把任意一个函数表示成了若干个正交函数（由sin,cos 构成）的线性组合。」

• Fourier变换

❝

 为傅里叶变换基函数，且为拉普拉斯算子的特征函数

❞

• Fourier逆变换

定义 是 和 的卷积，则有代入 最后对等式的两边同时作用 ，得到也即是：「即对于函数 与 两者的卷积是其函数傅立叶变换乘积的逆变换」

即可以通过傅里叶变换得到函数卷积结果。

那么问题来了，如何类比到graph上的傅里叶变换呢？

拉普拉斯算子与拉普拉斯矩阵

这里只说几点重要的结论

• 拉普拉斯算子计算了周围点与中心点的梯度差。当 受到扰动之后，其可能变为相邻的 之一，「拉普拉斯算子得到的是对该点进行微小扰动后可能获得的总增益」 （或者说是总变化）。
• 「拉普拉斯矩阵就是图上的拉普拉斯算子，或者说是离散的拉普拉斯算子」；拉普拉斯矩阵中的第 行实际上反应了第 个节点在对其他所有节点产生扰动时所产生的增益累积。直观上来讲，图拉普拉斯反映了当我们在节点 上施加一个势，这个势以哪个方向能够多顺畅的流向其他节点。「谱聚类中的拉普拉斯矩阵可以理解为是对图的一种矩阵表示形式。」

❝

拉普拉斯矩阵实际上是对图的一种矩阵表示形式，这句话太重要了 更深入的证明请查看拉普拉斯矩阵与拉普拉斯算子的关系^[4]

❞

上面讲到传统的傅里叶变换：

其中 为拉普拉斯算子的特征函数：

类比到图上，拉普拉斯算子可以由拉普拉斯矩阵 代替。而由于 为半正定对称矩阵，有如下三个性质：

• 实对称矩阵一定n个线性无关的特征向量 ，且
• 半正定矩阵的特征值一定非负
• 实对阵矩阵的特征向量总是可以化成两两相互正交的正交矩阵

其中 为特征向量， 为特征值构成的对角矩阵。

那么 在图上的傅里叶变换可以表示如下：

其中 表示第 个特征， 表示graph上顶点个数。

❝

可以看出等式左边是以特征值为自变量，等式右边以顶点为自变量，同样可以类别理解为从一个域转换到另外一个域

❞

表示图 上的顶点数量， 可理解为输入 可理解为作用在顶点 上的函数， 故 为长度为 的向量

其中 个特征向量组成的矩阵如下：

其中 为 特征值为 对应的特征向量， 类似

则 「在图上的傅里叶变换」的矩阵形式如下：

即：

同理可以推导 在图上的逆傅里叶变换：

GCN模型

上面已经得出：类比得到图上卷积：

其中 :

其中 为 的参数。

则可得：

=

由此可得：

其中 为激活函数， 就是「卷积核」，注意 为特征值组成的对角矩阵，所以 也是对角的，可以将卷积核记为如下形式

❝

这里面的 就是我们要定义的卷积核具体形式

❞

这里面的参数 即为模型需要学习的卷积核参数。

论文中将 ，也即

❝

为 个shape相同的矩阵相加，结果还是矩阵形式 注意上式中不同的特征值共享相同的参数 ，做到了参数共享

❞

继续推导可得：

❝

注意得到的还是 个矩阵相加形式

❞

可得：

好了，直观上看这样做有以下几个优点：

• 卷积核只有 个参数，一般 远小于 ，参数的复杂度被大大降低了。
• 矩阵变换后，直接用拉普拉斯矩阵 替换，计算 时间复杂度还是

切比雪夫多项式及其捕捉局部特征

可以利用切比雪夫多项式来逼近卷积核函数：

其中 表示切比雪夫多项式， 表示模型需要学习的参数， 表示re-scaled的特征值对角矩阵，进行这个shift变换的原因是Chebyshev多项式的输入要在 之间，因此

由 可得：

其中

在实际运算过程中，可以利用Chebyshev多项式的性质，进行「递推」：

那么这种切比雪夫展开式如何体现其"localize" 呢？可以看看下面这个简单例子

可以由上面这个简单的graph得到图的拉普拉斯矩阵

• 当 时，卷积核为 ：

❝

显然K=0时，卷积核只能关注到每个节点本身

❞

• 当 时，卷积核为 ：

❝

K=1时，卷积核能关注到每个节点本身与其一阶相邻的节点

❞

• 当 时，卷积核为 ，其中 :

❝

K=2时，卷积核能关注到每个节点本身与其一阶相邻和二阶相邻的节点

❞

显然由上面推导可知：「切比雪夫多项式的项数，就是图卷积的感受野 」参数共享机制：「同阶共享相同参数，不同阶的参数不一样」。

Graph Coarsening（图粗化）

图的粗化可以理解为cnn中的pooling操作，这里面将相似的顶点合并成一个超级顶点。

论文中采用一种贪心(Graclus)算法来计算给定图的粗化结果，在每个coarsening level（可能存在多次粗化），使用一个unmarked的顶点 ，将这些顶点 与unmarked的邻居 相互匹配，找到

这两个匹配上的顶点然后mark一下，使用他们的权重的和 来作为粗化后的权重。一直重复这个过程，知道所有的点都被marked。

❝

这里面相当于pool_size=2

❞

• 中两两类似的顶点合并，[0,1]，[4,5], [8,9]，6, 10合并重排成 中的0, 2, 4, 3, 5顶点
• 中的0, [2, 3],  [4, 5] 顶点 合并重排成 中的 0, 1, 2顶点
• 为了能在1D数据上能方便的进行池化，需要给每个顶点配备两个子节点，如果该顶点有两个顶点则无需配备，否则需要配备一个或2个 。由 可知， 需要补充1 个 ， 需要补充4 个 ，例如上图的右半部分图。
• 有12顶点后，可以在1D上很方便的pooling。
• 在 处，当使用 的时候， 初始化为0。这些 并不相连，故初值并不影响卷积操作结果，但是这些 确实增加了计算消耗，但是实践发现，Graclus算法里面的singletons很少。

❝

图粗化的目的就是找到合适的填充fake node方式，方便后面在1D数据上pooling

❞

文本分类实验(Text Categorization on 20NEWS)

上面大概的把gcn的数学原理总结了一遍，来看看代码中 gcn是如何应用在文本分类这个task上的。

• 18846个text document【11314训练，7532测试】
• 20个类别
• 选取出现频次最高的1000个token作为词袋，每个document 用这个bag of words表示

数据预处理步骤

1. 选取出现频次最高的1000个token作为词袋，每个文档用这个bag of words来表示
2. gensim.models.Word2Vec学习词的embeding矩阵，embed_size=100
3. 计算词袋内两两词之间相似度，相似度矩阵shape=[1000, 1000]
4. 相似度矩阵每行相当于一个顶点，将每行相似度最小的16个对应位置设置为0，剩余位置随机填1，由此构成邻接矩阵
5. 对上面得到的邻接矩阵进行多层粗化，倒推每个coarsen_level应该填充多少个fake node
6. 对train_data,test_data中每个样本填充相应数量的fake node，「其实就是对每个样本添加额外的零特征」

❝

代码中顶点数量M_0 = |V| = 1000 nodes (0 fake node added)，边数量|E| = 11390 edges 其实就是以词袋内每个token作为图上的顶点，以token之间相似度来随机构造边

❞

模型部分

表示一个batch的样本，论文代码中

这里以以下参数为例

  name = 'cgconv_fc_softmax'
    params = common.copy()
    params['dir_name'] += name
    params['regularization'] = 0
    params['dropout']        = 1
    params['learning_rate']  = 0.1
    params['decay_rate']     = 0.999
    params['momentum']       = 0
    params['F']              = [5] 
    params['K']              = [15]
    params['p']              = [1]
    params['M']              = [100, C]
    model_perf.test(models.cgcnn(L, **params), name, params,
                    train_data, train_labels, val_data, val_labels, test_data, test_labels)

• params['F'] ：表示卷积核的输出维度
• params['K']：切比雪夫多项式数
• params['p'] ：每层池化的pool_size
• params['M'] = [100, C]: 表示先过100个神经元的fc，再在C=20个类别上做softmax

def _inference(self, x, dropout):
        # Graph convolutional layers.
        x = tf.expand_dims(x, 2)  # N x M x F=1
        for i in range(len(self.p)):
            with tf.variable_scope('conv{}'.format(i+1)):
                with tf.name_scope('filter'):
                ## filter表示切比雪夫的卷积过程
                # self.L[i]表示当前level邻接矩阵的拉普拉斯矩阵
                # self.F[i] 当前level卷积操作的输出维度
                # self.K[i] 当前level卷积切比雪夫展开项数
                    x = self.filter(x, self.L[i], self.F[i], self.K[i])
                with tf.name_scope('bias_relu'):
                    x = self.brelu(x)
                with tf.name_scope('pooling'):
                    x = self.pool(x, self.p[i])
        
        # Fully connected hidden layers.
        N, M, F = x.get_shape()
        x = tf.reshape(x, [int(N), int(M*F)])  # N x M
        for i,M in enumerate(self.M[:-1]):
            with tf.variable_scope('fc{}'.format(i+1)):
                x = self.fc(x, M)
                x = tf.nn.dropout(x, dropout)
        
        # Logits linear layer, i.e. softmax without normalization.
        with tf.variable_scope('logits'):
            x = self.fc(x, self.M[-1], relu=False)
        return x

切比雪夫过程

def chebyshev5(self, x, L, Fout, K):
        N, M, Fin = x.get_shape()
        N, M, Fin = int(N), int(M), int(Fin)
        # Rescale Laplacian and store as a TF sparse tensor. Copy to not modify the shared L.
        L = scipy.sparse.csr_matrix(L)
        L = graph.rescale_L(L, lmax=2)
        L = L.tocoo()
        indices = np.column_stack((L.row, L.col))
        L = tf.SparseTensor(indices, L.data, L.shape)
        L = tf.sparse_reorder(L)
        # Transform to Chebyshev basis
        x0 = tf.transpose(x, perm=[1, 2, 0])  # M x Fin x N
        x0 = tf.reshape(x0, [M, Fin*N])  # M x Fin*N
        x = tf.expand_dims(x0, 0)  # 1 x M x Fin*N
        def concat(x, x_):
            x_ = tf.expand_dims(x_, 0)  # 1 x M x Fin*N
            return tf.concat([x, x_], axis=0)  # K x M x Fin*N
        if K > 1:
            x1 = tf.sparse_tensor_dense_matmul(L, x0)
            x = concat(x, x1)
        for k in range(2, K):
            x2 = 2 * tf.sparse_tensor_dense_matmul(L, x1) - x0  # M x Fin*N
            x = concat(x, x2)
            x0, x1 = x1, x2
        x = tf.reshape(x, [K, M, Fin, N])  # K x M x Fin x N
        x = tf.transpose(x, perm=[3,1,2,0])  # N x M x Fin x K
        x = tf.reshape(x, [N*M, Fin*K])  # N*M x Fin*K
        # Filter: Fin*Fout filters of order K, i.e. one filterbank per feature pair.
        W = self._weight_variable([Fin*K, Fout], regularization=False)
        x = tf.matmul(x, W)  # N*M x Fout
        return tf.reshape(x, [N, M, Fout])  # N x M x Fout

pool过程：

def mpool1(self, x, p):
        """Max pooling of size p. Should be a power of 2."""
        if p > 1:
            x = tf.expand_dims(x, 3)  # N x M x F x 1
            x = tf.nn.max_pool(x, ksize=[1,p,1,1], strides=[1,p,1,1], padding='SAME')
            #tf.maximum
            return tf.squeeze(x, [3])  # N x M/p x F
        else:
            return x

可以看出加了fake node后，可以直接在输入矩阵上做pool

实验结果

个人总结

• 本论文旨在将图像上的卷积操作类比到graph上的卷积，做到了 「参数共享，局部特征」 cnn的两大核心特性，做法比较巧妙。

参考文献

• http://papers.nips.cc/paper/6081-convolutional-neural-networks-on-graphs-with-fast-localized-spectral-filtering.pdf
• https://github.com/mdeff/cnn_graph
• http:/www.youtube.com/watch%3Fv%3Dc0MR-vWiUPU
• https://www.zhihu.com/question/54504471/answer/332657604
• https://zhuanlan.zhihu.com/p/54505069
• https://www.zhihu.com/column/c_1131513793020334080（强烈推荐）

Reference