图神经网络1-介绍

2020-04-20

科研

字数统计: 1.8k字 | 阅读时长≈ 6分钟

1. 图神经网络GNN

¶1.1 基础知识-图*

图神经网络中的图是指数据结构中的图的样子，图由顶点(Vertex)和边(Edge)构成G=(V,E)，顶点连接的边的数量叫做顶点的度(Degree)。

Walk：一个walk是一个确定的序列，表示在图中沿着边走的路径。

Trail：Trail是没有重复边的Walk。图1

Path：Path是没有重复点的Walk。图2

Cycle：构成环的Path。图3

Circuit：构成环的Trail。图4

特殊的图：

每个点有相同的度的图叫做Regular graph。图1

图中任意两个点都有连线的图叫Complete graph。图2

常用矩阵：

顶点和边之间的关系使用邻接矩阵A (Adjacency matrix)表示，A可以是0-1矩阵，也可以是带权重的矩阵。

度矩阵D (Degree matrix)的对角线为对应顶点的度，其余元素为0。

拉普拉斯矩阵L (Laplacian matrix)，L=D-A。它定义了图上的导数，刻画了信号在图上的平滑程度。

对称归一化的拉普拉斯矩阵：$L=D^{-\frac{1}{2}} L D^{-\frac{1}{2}}=I-D^{-\frac{1}{2}} A D^{-\frac{1}{2}}$，

¶1.2 图卷积网络*

图神经网络可以用在知识图谱、社交网络、城市路网流量等多个领域。可以处理的任务可以分为节点预测任务（如节点分类）、链路预测任务、以及子图预测任务（如子图匹配）。

图神经网络GNN和图卷积网络GCN的关系就好比深度神经网络DNN和卷积神经网络CNN的关系。

For these models, the goal is then to learn a function of signals/features on a graph G=(V,E) which takes as input:

A feature description $x_i$ for every node $i$ ; summarized in a N×D feature matrix X (N: number of nodes, D: number of input features)
A representative description of the graph structure in matrix form; typically in the form of an adjacency matrix A (or some function thereof)

and produces a node-level output Z (an N×F feature matrix, where F is the number of output features per node). Graph-level outputs can be modeled by introducing some form of pooling operation.

图卷积网络最大的问题是如何在图上定义卷积和池化操作。在Graph中，因为节点的度差异很大，所以很难找到以一个节点为中心的模板，对于每个节点都适用。这使得参数共享难以实现。

¶图卷积

GCN分为谱域GCN (Spectral)和空域GCN (Spatial)。谱域GCN是空域GCN的特例。

谱域GCN：在谱域中定义卷积。将图上的信号变换到谱域，在谱域实现卷积，然后再变回空间域。具体来说，假设图上的每个节点都有一个取值（一个feature值），图上共有n个节点，图上的信号就是一个n维向量，我们要将这个n维向量变换到一个新的域中，这就需要一组基，这个基就是拉普拉斯矩阵的n个特征向量。变换公式为 $\widehat={U}^{T}{x}$，逆变换公式为 $x=U \hat{x}$，$x$为原始空间的信息，$\hat x$为新的空间下的信息。其中U为特征向量$U=[u_1,…,u_n]$。根据卷积定理，两个信号的卷积等于傅里叶变换后的点积，因此信号$x$和卷积核$y$的图卷积$*G$可以写为：

$$ x *_{G} y=U\left(\left(\boldsymbol{U}^{T} \boldsymbol{x}\right) \odot\left(\boldsymbol{U}^{T} y\right)\right) $$ 使用$g_{\theta}$对上式做一个等式变换：

由上图可以看出谱域GCN计算卷积时的三步：首先对输入x变换到谱域得到 $\widehat{{x}}={U}^{T}{x}$，然后对$\hat x$进行卷积（即用$g_\theta$对$\hat x$做加权），然后做逆变换得到空间域的卷积结果。

上面解释中举的例子输入是一个一维向量，当输入是多维时同理。这是Y.LeCun组在ICLR2014中提出的，它是谱域GCN的基础，但是由于计算拉普拉斯矩阵的特征向量耗时、特征向量（稠密向量）与x相乘耗时、该计算方法中结果不是局部的而是和所有的节点都有关系，这三个问题使得该方法无法使用。

在NIPS2016论文ChebyNet中，通过将$g_\theta$换为 $g_{\beta}(\Lambda)=\sum_{k=0}^{K-1} \beta_{k} \Lambda^{k} \quad$，其中$\Lambda=\operatorname{diag}\left(\lambda_{1}, \lambda_{2}, \cdots, \lambda_{n}\right)$为拉普拉斯矩阵的特征值，即由特征值的多项式代替特征向量，使得图卷积不再显式依赖特征向量，参数由n降为K，卷积是局部的半径为K（例如，K为距中心节点的跳数），解决了上述问题。使得谱域图卷积可以使用。之后，还有一些方法做了各种改进。

空域GCN：仍然在节点域直接定义卷积。

ICML, 2016. 标准的CNN中的卷积拆开来看其实是三步：1. 选定一个节点后确定它的邻域 2. 给它的邻域编个号定个序 3. 参数共享。因此类比到GCN，对于每个节点，1. 选择固定个数的邻居节点（根据自己定义的邻近度度量），2. 给邻居节点定序，比如最近的排第一，第二近的排第二… 3. 参数共享

NIPS, 2017 GraphSAGE. 通过以本节点为中心随机游走选取固定个数的邻居，然后聚合邻居节点的信息来更新中心节点。

ICLR, 2017 GCN. 将节点的一阶邻居的特征经过变换后加权平均，权重由拉普拉斯矩阵得到。

NIPS, 2018 GAT. 认为GCN中根本没有实现卷积，它没有参数共享，权重靠的是拉普拉斯矩阵。参数共享只是用在特征变换中。因此它在聚合邻居变换后的特征时，不使用拉普拉斯矩阵，而是使用可以学习的参数$\overrightarrow{\mathbf{a}}$ ，这才是真正参数共享的卷积核。

CVPR, 2017 MoNet. 更一般的空间方法是这样的，空间方法需要多个图上的核函数，每一个核函数定义了一种度量图上任意两个节点相似度的方式，所谓卷积就是对这些不同相似度定义方式的加权平均，卷积核的参数就是核函数的权重，核函数才是我们需要定义的基础。核函数在谱方法里就是核变换的基；在空间方法里就是我们要选择哪些邻居，它们的相似度怎么样。

谱方法是空间方法的特例意思就是，谱方法具体的知道我们把节点投影到了哪个空间，而空间方法不需要知道投影到了哪，只需要知道一个核矩阵。

¶图池化

图粗化：对节点聚类，每一类变成一个超级节点。聚类方法可以是事先规定的，也可以是学习来的。