浅读各类图神经网络
现在需要对非欧氏结构的数据进行建模，听说最近图神经网络这块火得很，所以找了各类不同的图神经网络进行对比和分析。
图神经网络的核心在于将图结构转化为向量，这个过程被称为嵌入(Embedding)，这是借鉴于自然语言处理中的Word2Vec，所以首先要对Word2Vec有初步的了解。
Efficient Estimation of Word Representations in Vector Space
Word2vec是Google开源推出的用于获取词向量的算法。词向量主要用于语言翻译任务。该文首次提出利用Embedding算法获取词向量，通过大规模的单词训练（1.6billion）得到高质量词向量。算法设计类似于神经网络模型，但没有隐藏层。获取词向量的方式主要有两种，通过已知的上下文词向量推断未知的词向量（CBOW模型），或是通过已知词向量推断未知的上下文词向量（Skip-Gram模型）。Word2Vec的主要工作就是将文本中的每个词映射到一个低维向量中。
DeepWalk: Online learning of social representations
DeepWalk受Word2Vec的启发，将节点类比成词，则算法游走的节点序列可类比成句子。首先针对每个节点运行游走算法，获取节点序列（游走长度是超参，长度是10时对梯度影响最佳）。然后运算Word2Vec得到各节点的向量。作者表示算法在博客和Youtube的社交用户分类任务中表现优异。
Network representation learning with rich text information
本文首先证明了DeepWalk的学习过程类似于传统的矩阵分解，将邻接矩阵分解为节点的向量矩阵和上下文相关的向量矩阵。而本文提出的TADW算法（Text-associated DeepWalk）则将邻接矩阵分解成节点矩阵、上下文相关矩阵和文本特征矩阵（text feature matrix）——包含相邻节点结构信息的矩阵。从而使学到的相邻包含更多信息。
LINE: Large-scale information network embedding
提出可处理大规模网络结构（数百万个顶点和数十亿条边）的embedding算法，模型主要分为一阶相似度模型和二阶相似度模型两部分。 1. 一阶相似度模型：若两个节点相邻，且相接边上的权重值较大，则这两个节点的一阶相似度较大；若两个节点间没有变相邻，则两个节点间的一阶相似度为0。在建立模型中，一阶相似度会通过计算概率得出，且该模型仅适用于无向图。 2. 二阶相似度模型：若两个节点非直接相邻，但是共享的相邻节点较多，则认为这两个节点二阶相似。该模型适用于有向图和无向图。 3. 对比DeepWalk算法，该算法效果优异。
Node2vec: Scalable feature learning for networks
Node2Vec是DeepWalk和LINE的改进算法。DeepWalk是设计了随机游走算法，这是一个类似于DFS搜索节点的算法，有利于算法寻找距离较远但结构相似的节点；LINE则是仅仅则是类似于一个BFS搜素节点的算法，有利于寻找距离较近（NLP中则是上下文相关)但结构不相似的节点。Node2Vec的改进之处就是设置一个分段函数，使游走时可以调整算法选择BFS或是DFS搜索。
REVISED NOTE on LEARNING QUADRATIC ASSIGNMENT with GRAPH NEURAL NETWORKS
给定GNN模型如下所示，其中$\hat{A}={1,D,A,A_1,…,A_J,U}$，$D$是度矩阵，$AJ=min(1,(A^2)^J)$。该模型的特点是为目标节点添加了$2^J$阶邻点的影响。节点向量$x$公式如下： $$ x^{k+1}=\rho(\sum{B\in \hat{A}}Bx^k\theta^k_B)$$ 其中$\theta$为神经网络的训练参数
Dynamic Graph CNN for Learning on Point Clouds
通过邻接结点坐标来计算边向量，通过聚合边向量更新embedding，在处理动态变化的图时，只需要重新计算变化节点的邻接节点向量即可。
Laplacian eigenmaps and spectral techniques for embedding and clustering
拉氏变化实际上是一个降维算法，主要思想是希望结构中有联系的结点（图中相连的结点）在降维后的空间中尽可能接近。在图中，根据邻接矩阵求得拉氏矩阵，根据拉氏矩阵求得顶点在降维后空间的向量，拉氏矩阵便是拉氏变化中的权重矩阵。
Distributed Large-scale Natural Graph Factorization * Shravan Narayanamurthy
Graph Factorization算法（GF），该算法适用于大规模社交网络（无向图），结点规模在$10^8$左右，边的规模在$10^{10}$左右。降维后向量与邻接矩阵的关系如下所示，要求出降维后向量需要对公式进行求导。$\lambda$是正则向系数，是类似于学习速率的超参，$\phi$是损失函数。
$$ \phi(Y,\lambda)=\frac{1}{2}\sum{(i,j)\in E}(W{ij}-
GraRep: Learning graph representations with global structural information
主要适用于社交网络任务（无向图），创新点是设计了一个常量k，计算k阶邻点对目标节点的影响。降维向量公式如下所示，其中A是度矩阵的逆乘以邻接矩阵，β是偏置参数。 $$ Y^k_{i,j}=W^k_i\bullet C^kj=log(\frac{A^k{i,j}}{\sumtA^k{t,j}}-log(\beta))$$
Asymmetric transitivity preserving graph embedding
HOPE算法，主要适用于有向图，提出应该计算输出向量（从目标节点出发可以到达的节点对目标节点的影响）和输入向量（可以到达目标节点之结点对目标节点的影响）。其损失函数$L$为: $$L=||S-Y_sY_t^T||^2_F$$ 其中$S$为相似度矩阵
Graph Embedding Techniques, Applications, and Performance: A Survey
综述性文章，基本总结了已有的embedding算法
参考网站1
