|
由于数学功底不算强，故不从数学推导出发去学习GNN，主要学习GNN的结构，效果和用法。
之前的DL：针对欧式空间数据，对于图数据效果不好，故使用图神经网络直接处理图数据。
图嵌入
首先需要图嵌入，即高维图转变为低维向量表示，主要参考这篇文章https://zhuanlan.zhihu.com/p/62629465。
图嵌入的主要问题：属性选择，可扩展性，嵌入维数。
拉普拉斯矩阵
拉普拉斯矩阵是学习图神经网络绕不开的概念。首先复习一下相似矩阵，有可逆P，使得P^-1AP=B，则A和B是相似矩阵。在一组基（单位向量ij，任意x=ai+bj）下的变换x->y,使用一个矩阵A表示，A是该函数的线性变换。而对于另一组基下的相同变换，使用矩阵B表示，则A，B就是相似矩阵。P通过两组基的关系求出。
简单学习一下拉普拉斯矩阵。定义：拉普拉斯矩阵对应一个图，定义为L=D-A，D为图的度矩阵，A为邻接矩阵。正则化拉普拉斯矩阵Lsym=D(-1/2)LD(-1/2)。拉普拉斯矩阵和数理分析中拉普拉斯算子作用类似，拉普拉斯算子是用于求标量函数梯度场的散度，对于单变量函数就是求二阶导数。在图像处理中，其可以突出灰度值变化的位置从而锐化图像。
而为神马D-A这样一个东西在图问题中和拉普拉斯算子作用一样呢？首先图问题中对应的函数是节点v对于实数R的映射。参考https://zhuanlan.zhihu.com/p/67336297/中的社交网络为例，该图问题的函数就表示每个节点发消息的强度。那么在一条边上的梯度即用两节点函数值差除以边权值（代表距离），表示两人之间的信息流通。计算梯度即用边权值矩阵K（这里想不起来名字了，行是节点，列是边）乘以图函数组合成的向量f，即NablaF=K*f，这个很好理解。而节点的散度，即是从该节点射出去的梯度减去射入该节点的梯度（有点难理解）。这里不做数学推导，只是形象的理解一下，散度表示梯度的趋势，得到梯度差即为散度。而在梯度向量（上面得到的NablaF）左乘一个矩阵，射入置-1，射出置1，即可得到散度。该矩阵就是把K矩阵正的变1，负的变-1即可。这个矩阵和K相乘即得到计算散度的算子-拉普拉斯矩阵。计算后发现该矩阵为D-W，但D-W只是推导出该矩阵后，发现该矩阵具有的性质而方便计算，是现有矩阵后才知道其值等于D-W。
近似度
再说一下近似度的概念，一阶近似即权重，二阶近似描述该对节点领域结构的相似性，即比较两个节点的一阶近似向量。
三种图嵌入思想
简单了解一下三种方法的大致思想：
因子分解：通过最优化一个函数得到向量表示。如要保持权重高的节点之间离的近，则被分割远的节点会得到惩罚，最小化惩罚值函数：权值乘以距离。
随机游走：使用基于该点随机游走得到的序列作为该点的特征，用word embedding方法学习，用BFS策略倾向于反映了该点局部上下文信息，DFS倾向于反映图结构信息。Node2Vec综合两种策略。
深度学习方法：SDNE使用自动编码器嵌入，并基于拉普拉斯映射监督，来保持一阶和二阶近似。SDNE使用全局邻接矩阵作为输入，维度很高，故GCN提出在图上定义卷积，聚合节点的相邻嵌入，多轮迭代便可嵌入全局信息，这个很好理解。
学习图嵌入之后的一个想法：在GNN应用到软件分析中时，软件特征提取得到的图也可以先通过NLP的方法编码每个节点向量，再通过图嵌入去不断添加该结点周围结点的信息（边信息），结果发现门控神经网络就是采用这个思想。
图神经网络
图神经网络：首先参考这篇综述https://zhuanlan.zhihu.com/p/75307407?from_voters_page=true
GCN：上文介绍过大概思想，这里延伸一下。
图池化模块：全局池化，貌似是直接maxpooling？分层池化：每一层将节点映射到一组cluster，形成下一层的输入。分层池化的基本思想可以参考DIFFPOOL，这篇博客翻译了论文https://blog.csdn.net/yyl424525/article/details/103307795，这里先不详细看。
基于谱的GCN：涉及传统计算机图形学，数学信号处理的内容，这里不详细看了。且谱方法需要同构的图，泛化性太差，且需要load整个图结构，而且貌似本身效果也没有基于空间的方法好，就不相信看了，没意义。
基于空间：和传统图像卷积过程类似，将邻近节点作卷积。但一个图结点数目是不定的，那可以每次嵌入k个结点，分多轮迭代卷积。
GCN的数学推导过程，从傅立叶变换到拉普拉斯矩阵等等就先不看了，咱知道GCN大概思想和效果，然后先用起来再说。
GAT：如果单纯运用GCN，边的权值信息反映的还不够充分，只是通过卷积合并不同结点时的参数体现。故将注意力机制用于确定邻近节点的权重。
下面几种图神经网络感觉还不足以和上面两种并列，应该还有些网络类型没有列出，先不详细看了。
门控图神经网络：用LSTM，GRU的门控控制信息的传递，如GGNN将邻近结点的表征通过GRU更新到该结点，邻近结点相当于上一时刻信息。
GA：图自动编码器，运用在图嵌入上。这里以功能命名，其中包含多种网络结构。
GGN：图生成网络，参考GAN
GSTN(Graph spatial-temporal networks)：加入时间维度，预测未来节点值或标签
今天先看到这里，明天再看看综述，看完进行GCN实战
|