图卷积网络

这里的图是指Graph，一种数据结构。
图卷积网络关键问题在于如何定义在图上的卷积操作。目前有两种方法：

谱方法
空间方法

已经证明，谱方法是空间方法的一种特例。本文将简要介绍目前关于图卷积操作的基本方法，以其基于paddlepaddle平台实现了其中一种称为GCN的图卷积网络。由于图像可以视为一种特殊的Graph。因此图卷积网络也可以处理图像的数据。将实现后的网络用于MNIST数据集做图的分类，实验结果表明，图卷积网络具有很强的表达能力。

谱方法

对于一个图 $G = (V, E, W)$ ，如果结点个数 $n = ∣ V ∣$ ，那么邻接矩阵 $W\in \mathbb R^{n\times n}$ 。令 $X\in \mathbb R^{n \times d}$ ,其中每一列代表图上的一个信号，共d个信号。

假设 $L$ 是 $W$ 的规一化后的拉普拉斯矩阵，且其正交特征向量矩阵为 $U$ 。则图上信号 $x$ 的傅立叶变换和逆变换定义如下：
$\hat x = U^{\top}x \\ 傅立叶逆变换：x =U\hat x$
根据卷积定理可以定义卷积操作如下。其中 $U^\top y = (\theta_1, \theta_2,...,\theta_n)^\top, \theta_g=diag(\theta_1,\theta_2,...,\theta_n)$ 。
$\begin{aligned} x *_G y &= U(U^\top x \ \odot \ U^\top y) \\ &= U\theta_gU^\top x \end{aligned}$
那么GCN可表示如下。
$x_{t,j}=h(\sum_{i=1}^{d} U\theta_gU^\top x_{t-1,i} )$
其中 $x_{t,j}$ 表示第 $t$ 层第 $j$ 个信号。 $d$ 表示第 $t ? 1$ 层的信号个数。 $h$ 是一个非线性函数。上面公式的含义是：后一层中的某一个信号等于前一层所有d个信号卷积后相加，再过一个非线性变换。

以上的每一次卷积复杂度都是 $O(n^2)$ 。下面使用 $g_{\beta}$ 对 $g_{\theta}$ 做近似，令 $g_\beta=\sum_{i=1}^{K}\beta_k\Lambda ^k$ 。其中 $\Lambda^k$ 是对角矩阵, 根据Chebyshev 多项计算。 $\Lambda^k =2\Lambda \cdot \Lambda^{k-1} + \Lambda^{k-2}$ 。 $\Lambda^0 = 0,\Lambda^1 = \Lambda$ 。 $\Lambda$ 表示矩阵L的特征值矩阵。根据稀疏矩阵乘法则复杂度可降为O(|E|)
$U\theta_\beta U^\top x = \sum_{i=1}^{K}\beta_kL^kx$

空间方法

空间方法的基本思想是：

Aggregate the information of neighboring nodes to update the representation of center node。
即通过聚合邻居结点的信息来更新中心结点的表示

分为两个步骤：

从邻居采样
把采样结果做一个聚合（加权平均,最大值,…）

GCN

即 Graph Convolution Network。对于两层的图卷积网络定义如下。
$softmax(\hat A \ \mathbf{RELU}(\hat AXW^{(0)})W^{(1)})$
其中 $\hat A=\tilde D^{-\frac{1}{2}} \tilde A \tilde D^{-\frac{1}{2}}$ 表示从邻居采样然后聚合。 $\tilde A=I_N-A, \tilde D_{ii} = \sum_j \tilde A_{ij}$ 。 $\in \mathbb R^{n \times n}$ 表示图的邻接矩阵， $I_N$ 是单位矩阵。 $\in \mathbb R^{n \times d}$ 是图上的信号。 $W^{(0)} \in \mathbb R^{d \times c_0}, W^{(1)} \in \mathbb R^{c_0 \times c_1}$ 都是卷积的参数。 $c_0,c_1$ 表示卷积之后的信号个数。

请添加图片描述
图在做完卷积操作后，图的结构并没有改变。即结点个数不变，连接权重也不改变。唯一改变的是图上的信号和信号的个数。如上图所示，输入层3个信号经过两层卷积后变成了5个信号。

GAT

即Graph Attention Network。该方法使用Attention来聚合邻居信号。
$\alpha_{ij}=\frac{\exp(LeakyRelu(\vec{a}^\top[W\vec{h_i} ||W\vec{h_j}]))}{ \sum_{k\in N_i} \exp(LeakyRelu(\vec{a}^\top[W\vec{h_i} ||W\vec{h_k}]))}$
其中 $N_i$ 表示结点 $i$ 的所有邻居。 $\vec{h_i}$ 表示结点 $i$ 的信号向量。|| 表示拼接操作。 $\vec a$ 是注意力机制的参数， $W$ 是特征提取的参数。

请添加图片描述

MoNet

根据MoNet（论文中描述了一种一般化的空间方法）描述。卷积过程可形式化表述如下：
$D_j(x)f=\sum_{y \in N(x)} w_j(\mathbf u(x,y))f(y), j=1,...,J$

$\sum_{j=1}^{J}g_jD_j(x) f$

其中 $x$ ， $y$ 都表示图中的结点。

$f (y)$ 则表示结点 $y$ 上的信号值。

$u (x, y)$ 表示结点 $x$ 和结点 $y$ 的一个 $d$ 维向量

$w_j(\cdot)$ 表示一个把 $d$ 维向量转换成权重的函数。

$N (x)$ 表示结点 $x$ 的邻居结点。

$D_j(x)f$ 表示结点 $x$ 从邻居那里聚合一次得到的值。

$(f ? g) (x)$ 表示结点 $x$ 从邻居那里聚合得到的 $J$ 个值，作加权平均。也就相当于卷积操作。 $g_i$ 表示卷积核。

图池化

对图是否需要池化，仍有较大争议。现有如下方法：

图粗糙：把几个结点集合成大结点。
结点选择：自动学习一个量化结点重要性的函数。根据重要性选择结点。

表达能力

图卷积网络的基本任务有两个：

结点分类：每个结点都有一个标签
图分类：整个图有一个标签

单层GCN不能很好的区分结点。提高层数GCN能提高表达能力，但是表达能力有上限。GNN本质是一个 $G\rightarrow R^d$ 的映射。其表达能力意味着能够区分图的能力. GIN（Graph isomorphism network）是一种比表达能力更加的强的图神经网络，它克服了GCN表达能力上限的问题。

代码实现

这部分实现了GCN。因为比较简单，而且效果好。
首先利用paddle的提供的功能，自定义一个卷积层。代码如下。

import paddle
import paddle.fluid as fluid
from paddle.autograd import PyLayer
import numpy as np


# GCN单层结构
class GCNLayer(fluid.dygraph.Layer):

    def __init__(self, A_hat, num_signals = 1, num_filters = 1):
        """
        A_hat - 由图的邻接矩阵计算而来的一个矩阵。维度为 (N, N)。N表示图中结点个数
        num_signals - 输入的信号个数
        num_filters - 卷积核个数,即输出信号个数
        """
        super(GCNLayer, self).__init__()
        self.A_hat = A_hat
        self.named_buffers = num_filters
        self.W = self.create_parameter(shape=[num_signals, num_filters], dtype='float64')

    def forward(self, X):
        """
        前向传播计算
        X - 图上的信号。维度为(N, C)
        输出 Y = relu(AXW) 
        """
        #print("X.shape", X.shape)
        x = fluid.layers.matmul(self.A_hat.astype("float64"),X.astype("float64"))
        x = fluid.layers.matmul(x, self.W)
        x = fluid.layers.soft_relu(x)
        return x

实验结果

本次实验使用GCN对MINST数据集进行网络模型优化和评估。该数据集训练集中包含了6万多张手写数字图片，以及对应的标签（即数字0~9）。我们使用上面定义的图卷积层(GCNLayer)结合全连接层(Linear)简单地组建了一个图像分类网络。结构如下。

# Layer类继承方式组网
class GCN(fluid.dygraph.Layer):

    def __init__(self,  A, num_signals):
        """
        A - 图的邻接矩阵。维度为(N, N)。N表示图结点的个数
        num_signals - 图上信号的个数
        """
        super(GCN, self).__init__()
        N = A.shape[1]
        I = np.eye(N, dtype="float64")
        A_tilde = A + I
        D_tilde = np.sum(A_tilde, axis=0)
        D_inv = D_tilde**-0.5
        D_inv = np.diag(D_inv)
        A_hat = D_inv.dot(A_tilde).dot(D_inv)
        A_hat = paddle.to_tensor(A_hat)

        self.layer_1 = GCNLayer(A_hat, num_signals=num_signals, num_filters=16)
        self.layer_2 = GCNLayer(A_hat, num_signals=16, num_filters=8)
        self.layer_3 = GCNLayer(A_hat, num_signals=8, num_filters=4)
        self.layer_4 = GCNLayer(A_hat, num_signals=4, num_filters=2)
        self.layer_5 = GCNLayer(A_hat, num_signals=2, num_filters=1)
        self.sofxmax = fluid.layers.softmax
        self.flatten = paddle.nn.Flatten(start_axis=0, stop_axis=1)
        self.linear = paddle.nn.Linear(N * 1, 10)

    def forward(self, x):
        """
        前向传播计算
        X - 图上的信号。维度为(N, C)
        输出 Y = GCN(X) 
        """
        x = self.layer_1(x)
        x = self.layer_2(x)
        x = self.layer_3(x)
        x = self.layer_4(x)
        x = self.layer_5(x)
        x = self.flatten(x.astype("float32"))
        x = self.linear(x)
        x = self.sofxmax(x, axis=0)
        return x

然后导入数据，开始训练的参数自动优化。

# 加载数据集
from paddle.vision.transforms import ToTensor
train_dataset = paddle.vision.datasets.MNIST(mode='train', transform=ToTensor())
test_dataset = paddle.vision.datasets.MNIST(mode='test', transform=ToTensor())
train_dataset = list( map(lambda x: (paddle.reshape(x[0], [-1, 1]), x[1]), train_dataset) )
test_dataset = list( map(lambda x: (paddle.reshape(x[0], [-1, 1]), x[1]), test_dataset) )

#模型优化和评估
width = 28
height = 28
n_nodes = width * height
A = np.zeros((n_nodes, n_nodes), dtype="float64")
"""
因为图像也是一种特殊的Graph，因此在这里构造它的邻接矩阵。每个像素都是一个结点，并且它的邻居结点即上下左右相邻的四个像素。
"""
for i in range(width):
    for j in range(height):
        if(i - 1 >= 0):
            A[i * width + j, (i - 1) * width + j] = A[(i - 1) * width + j, i * width + j] = 1;
        if(i + 1 < width):
            A[i * width + j, (i + 1) * width + j] = A[(i + 1) * width + j, i * width + j] = 1;
        if(j - 1 >= 0):
            A[i * width + j, i * width + (j - 1)] = A[i * width + (j - 1), i * width + j] = 1;
        if(j + 1 < height):
            A[i * width + j, i * width + (j + 1)] = A[i * width + (j + 1), i * width + j] = 1;

print(A)
net = GCN(A, 1)
print(paddle.summary(net, input_size=(n_nodes , 1)))
model = paddle.Model(net) 
optim = paddle.optimizer.SGD(learning_rate=0.1, parameters=model.parameters())
model.prepare(optim, paddle.nn.CrossEntropyLoss(), paddle.metric.Accuracy())
model.fit(train_dataset)
model.evaluate(test_dataset)