图网络空域卷积说明1:GNN

论文地址：A Generalization of Convolutional Neural Networks to Graph-Structured Data
GNN的做法是将一个图结构的数据强行变化为一个类似规则的数据，从而实现1维的卷积。

传统卷积：固定数量的邻域节点排序后，与相同数量的卷积核参数相乘后求和。

那么卷积就可以分为两步：
1.构建邻域(邻节点固定且有序)
2.对邻域的点和卷积核参数内积

但是对于图结构数据而言：邻域节点不固定，且图结构无序。因此需要找到一个解决构建邻域的方法。

解决思路：随机游走，根据被选中的概率期望和大小选择固定数量的邻居节点。

实现：
首先定义
$P$ 矩阵为图上的随机游走转移矩阵， $P_{ij}$ 为i节点到j节点的转移概率。
$S$ 矩阵为相似度矩阵，可以理解为邻接矩阵。
$D$ 矩阵为度矩阵， $D_{ii}=\sum_jS_{ij}$ 。
假设图结构已知，则 $S$ 和 $D$ 已知，则 $P$ 定义如下：
$P=D^{-1}S$

上式子相当于对S进行归一化，即使用归一化的邻接矩阵作为图转移矩阵。
多步转移矩阵定义为 $Q$ :
$Q^{(0)}=I,Q^{(1)}=I+P,\dots Q^{(k)}=\sum_{j=0}^kP^k$

其中 $k$ 为步数， $Q^{(k)}_{ij}$ 表示i节点进过k步达到j的期望访问次数，可视化如下图。

那么选择邻域的问题解决了，可以根据期望访问次数来选择需要的邻域节点， $\pi_i^{(k)}(c)$ 表示节点的序号，表示该节点是经过 $k$ 步内由 $i$ 节点出发的访问期望第 $c$ 大的节点，那么有节点期望访问大小排序:
$Q_{i\pi_i^{(k)}(1)}>Q_{i\pi_i^{(k)}(2)}>\dots>Q_{i\pi_i^{(k)}(N)}$
定义卷积：
每个点选取前 $p$ 个期望最大的作为邻域节点，且顺序由期望 $Q$ 决定。卷积核为 $W$ ，具有 $p$ 个参数。

举例：