参考链接：https://blog.csdn.net/weixin_43269174/article/details/98492487
一、引言
近几年来，伴随着计算机算力的急剧提升，神经网络从历史的尘埃中走出，横扫各大领域，完成一次次颠覆性的创新。依托高度弹性的参数结构，线性与非线性的矩阵变换，神经网络能适用于各式各样的数学场景，在各个类别的应用上我们都能看到神经网络的影子。其中著名的应用方向，包括自然语言处理、计算机视觉、机器学习、生物医疗、推荐系统、自动驾驶等等。图神经网络，广泛应用于社交关系、知识图谱、推荐系统、蛋白质分子建模，同样源自于对传统领域的创新，它的前身是图嵌入算法；而图嵌入算法又以图数据作为载体。这一关系，将贯穿本文始末，成为我们的展开线索。
二、图
在进入图嵌入算法前，本节将详细介绍该领域下的基础知识，包括各类图的概念以及路径相关算法。希望直入主题的读者可直接跳到下一节。
相关概念
> 图 (Graph) 是最基础的几种计算机 数据结构 之一，由若干个 节点 (Node, or Vertex) 构成；节点与节点相连，构成 边 (Edge)，代表了两者之间的依赖关系。根据图中边的方向，概念上可将图分为两种：有向图 (Directed Graph, or Digraph) 和 无向图 (Undirected Graph, or Undigraph)，如下所示，左侧为无向图，右侧为有向图：
当边被赋予权重，则图可称为 权重图 (Weighted Graph)：
一个形象的例子是城市地图，每一个交叉路口是一个节点，道路是一条边，而权重指的则是道路的长度。但如果我们希望用权重大小代表拥挤程度，在地图上看到每条道路的拥堵情况，那么一条边显然不足以满足我们的要求。这时就引申出了 多重图 (Multigraph)：
概念上，多重图必然是有向图和权重图；但需要注意的是，多重图中两个节点之间的边，既可以单向，也可以双向，i.e. 节点 AAA 和 BBB 之间可以有两条或以上 A→BA\rightarrow BA→B 的边；两条或两条以上的单向边成为 平行边 (Parallel Edges)，而平行边的数量称为 重数 (Multiplicity)。
此外，还有一些其他类型图的定义，包括 混合图 (Mixed Graph)，指的是既包含无向边也包含有向边的图；连通图 (Connected Graph)，指的是任意两个节点都有路径 (一个或多个边相连) 相连的无向图；强连通图 (Strongly-connected Graph)，指的是任意两个节点都有路径相连的有向图；循环图 (Cyclic Graph)，指的是存在首尾相连的路径，可以串起所有节点的图；以及最后的 完全图 (Complete Graph)，指的是所有节点之间都有边相连的无向图。
清楚这些图的概念，是我们理解算法、熟悉算法应用场景的前提。
路径相关算法
伴随着图一起诞生的，是与路径相关的算法，其中部分算法可以帮助我们从图中提取更多的特征信息融入到节点中，从而丰富图的架构，在图嵌入或图神经网络算法中达到更好的效果。
- 拓扑排序 (Topological Sorting)：
应用于有向非循环图，是对图中的所有节点 ViV_iV
i
(i=1,…,n)(i=1,…,n)(i=1,…,n) 进行统一排序，使得对于任意边 (Va→Vb)(V_a\rightarrow V_b)(V
a
→V
b
)，满足 a<ba<ba<b。经过拓扑排序的图，能加速目标检索的效率，同时能够快速获取两个节点间的上下游位置，应用场景包括学位课程之间的先修关系、面对对象程序类之间的继承，以及工程项目之间的调度等。需要注意的是，一个有向非循环图可能存在不止一种拓扑排序的结果。算法原理在于通过迭代，将无入度的节点从原图中抽出放入排序序列中，直至所有节点全部抽出。
- 深度优先搜索 (DFS, abbr. Depth-First Searching)：
通过遍历检测两个节点是否连通，或检测一个图是否为连通图。其过程类似于牵着绳子走入迷宫，每一个拐角是一个节点，当走到死角时，记录来过这里，沿着绳子的路线返回寻找下一个拐角；这将用到两个栈，分别记录走访过的节点，以及绳子沿路的拐角。实际应用中，全程只用一根绳子无疑是低效的，因此常常引入递归的思想，每到一个拐点切出多个绳头分头搜索。
- 广度优先搜索 (BFS, abbr. Breadth-First Searching)：
依据从源点出发，路径上的节点数量，将全图分为不同的层级，逐层向下检查。相对于深度优先搜索，广度优先搜索能够保证在边的数量上两个节点间检索到的路径最短。
Dijkstra 算法：
算法思想在于从源点出发，构建一个逐步扩张的“云”，每次迭代将云外离源点最近的节点拉入到云内来，使云逐渐遍布全图，从而检索到两个节点间的最短路径。时间复杂度为 O(n2)O(n^2)O(n
2
)，是贪心算法应用在路径问题上的绝佳案例。Floyd-Warshall 算法：
假如我们不希望每次检索两个节点是否连通，或计算最短路径时，都从头开始遍历，可以使用该算法生成 传递闭包 (Transitive Closure)，以加速后续检索，一劳永逸。该算法的原理在于每次迭代时，将所有满足连通要求的 Vk−1→Vk→Vk+1V_{k-1}\rightarrow V_k\rightarrow V_{k+1}V
k−1
→V
k
→V
k+1
的 Vk−1V_{k-1}V
k−1
和 Vk+1V_{k+1}V
k+1
单独建立联系，构建新的边 Vk−1→Vk+1V_{k-1}\rightarrow V_{k+1}V
k−1
→V
k+1
。如此一来，多次迭代过后，所有可连通的节点对 (VaV_aV
a
,VbV_bV
b
) 都将拥有直接关系。需要注意的是，该算法的时间复杂度为 O(kn3)O(kn^3)O(kn
3
)，kkk 为迭代次数，为保证所有可达节点配对存在直接相连的边，算法的运算消耗最高可接近 O(n4)O(n^4)O(n
4
)。显而易见，当节点的数量 nnn 逐渐增加时，算法运行的时间消耗将呈灾难性地增加。
- Prim-Jarnik 算法：
归属于 最小生成树 (MST, abbr. Minimum-Spanning-Tree) 一类的算法，旨在求解连通所有节点的最短路径。由 Dijkstra 算法调整而来，以所有零入度节点作为云的初始状态，不断找寻离云内节点最近的邻点拉入到云内来，以此迭代，直至所有节点访问完毕。如果不存在零入度点，则随机挑选一个加入到云中。
三、图嵌入算法
abbr. Graph Embedding Algorithms，目的在于学习图的结构或节点之间的邻接关系，对节点进行编码 (或对固有特征进行降维)，将所有节点映射为等维度的向量，使其能够方便地应用于下游的聚类、分类、关联分析或可视化任务。因此，在实际应用中，图嵌入属于预处理工作，绝大多数图嵌入算法皆为无监督学习算法。
常见概念
- 图 (Graph)：$G(V,E)$
节点 (Node, or Vertex)：$V={v1,…,vn}$，包含全部节点
度 (Degree)：D={deg1,…,degn}，包含每个节点的入度数量
边 (Edge)：$E=\{e_{ij}\}_{i,j=1}^n$，包含所有的边；如果边是双向的，则分别表达为两条，e.g. $v_i\leftrightarrow v_j$关系将对应$e_{ij}$与$e_{ji}$ ；如果边$v_i\rightarrow v_j$不存在，则不会出现在 EEE 里面
邻点 (Neighbors)：N(vi)\mathcal{N}(v_i)N(v
i)，包含节点 viv_iv
i的所有邻点
邻接矩阵 (Adjacency Matrix)：A={wij∣wij≥0}ni,j=1∈Rn×nA=\{w_{ij}|w_{ij}\ge 0\}_{i,j=1}^n\in\mathbb{R}^{n\times n}A={w
ij∣w
ij≥0}
i,j=1
n∈R
n×n
，记录图中边的权重信息；对于无向图，wij=wjiw_{ij}=w_{ji}w
ij=w
ji；要求所有的边权重不得小于 0；对于不相邻的节点，wij=wji=0w_{ij}=w_{ji}=0w
ij=w
ji=0
一阶相似度 (First-order Proximity)：边的权重 wijw_{ij}w
ij，代表两个节点的直接依赖关系
二阶相似度 (Second-order Proximity)：对于节点 viv_iv
i和 vjv_jv
j，从邻接矩阵分别获取相应的一阶相似性 wi=[wi1,…,win]\mathrm{w_i}=[w_{i1},…,w_{in}]w
i=[w
i1,…,w
in]，sj=[wj1,…,wjn]\mathrm{s_j}=[w_{j1},…,w_{jn}]s
j=[w
j1,…,w
jn]；wi\mathrm{w_i}w
i与 wj\mathrm{w_j}w
j的相似度即为二阶相似度，代表两个节点的邻居相似性
- 图嵌入 (Graph Embedding)：映射关系$ f:vi→zi∈R^d,∀i∈[1,n]$, $d$ 为超参数，决定最终的编码长度
- 特征表示 (Feature Representation)：$Xi∈R^{d0}$ ，对节点 $v_i$ 的固有特征 (不包含边及其他节点信息) 进行简单编码后形成的向量，因此又称为特征向量。
演变历程
图嵌入算法初步诞生于 21 世纪初，彼时的模型将更多的焦点放在降维上，嵌入的同时使得相邻的节点在最终的向量空间上更为接近，代表性的包括 Locally Linear Embedding (2000) 和 Laplacian Eigenmaps (2001) ，这一类算法充分利用所有的样本间权重，时间复杂度通常较高，最高可达 O(n2)O(n^2)O(n
2
)，因此并不适合大规模图数据。2010 年以后，新诞生的图嵌入算法逐渐在时间复杂度上得到优化，转而应对现实生活中广泛存在的特征稀疏性问题，这其中的翘楚便是 Graph Factorization (2013)，该算法旨在于邻接矩阵以及正则项之间寻求一个平衡点，使得生成的向量保留邻接矩阵的绝大多数信息；LINE (2015) 将该思想延续下去，并努力在嵌入向量中维持节点的一阶和二阶相似度；HOPE (2016) 更是引入了更高阶的相似度矩阵，通过广义奇异值分解保留高阶相似性。以上所有算法皆可归类于矩阵分解，又称为因子分解，其中心思想在于生成相似度矩阵，通过数学方法将矩阵中包含的邻接信息融入节点向量中。
另一个知名的流派是基于随机游走，以 DeepWalk (2014) 和 node2vec (2016) 作为代表。前者在节点的上下游随机走动，生成长度为 2k+12k+12k+1 的等长序列，作为节点的邻接特征导入 skip-gram 模型训练；后者在前者的基础上对随机游走在 DFS 和 BFS 的方向上施加权重，使生成的序列更为真实地体现节点的结构信息。
在这之后，图嵌入算法逐渐过渡到神经网络时代，涌现出一大批优质的图神经网络模型，包括 SDNE (2016) 与 GraphSAGE (2017) 等等，在工业界大放异彩。从此，基于神经网络的图嵌入算法不再仅仅局限于节点的邻接信息，而开始将节点本身的特征纳入模型考量，并逐渐从静态的直推式 (transductive) 学习向动态的归纳式 (inductive) 学习演变，无论是拟合能力还是泛化能力，都大大提升；部分图神经网络直接针对下游任务进行建模，已不再属于图嵌入的范畴。依据 Wu et. al (2019) 的定义，图神经网络可分为五大类：
图卷积网络 (Graph Convolution Networks)：简称为 GCN，是目前最主流的图神经网络算法，其余四种图神经网络皆由 GCN 演化而来。依据建模过程中是否应用到傅里叶变换，可将其分为基于谱 (Spectral-based) 和基于空间 (Spatial-based) 两个流派。
图注意力网络 (Graph Attention Networks)：引入注意力机制，将图网络整合为端到端的模型；具体的做法，是在 GCN 的聚合函数中加入可训练的权重参数，使得训练后的模型将更多的重心放在关键的邻点上。
图自编码器 (Graph Auto-encoders)：由一个编码器 (encoder) 和一个解码器 (decorder) 构成；在应对无固有特征的图时，编码器对邻接矩阵进行一定的预处理，包括融入更丰富的邻接信息 (e.g. 高阶相似度) 或是将邻接矩阵输入一套神经网络；在应对包含固有特征的图时，则直接使用 GCN 作为编码器对邻接矩阵进行编码；解码器对编码结果进行后续处理获得一阶及二阶相似度，通过计算损失函数对模型参数进行更新。
图生成网络 (Graph Generative Networks)：2018 年以后出现的新的研究方向，目的是在图的节点和边经验分布的基础上，生成新的图，进行对抗式训练。
图时空网络 (Graph Spatial-Temporal Network)：旨在于时空图中学习模式 (pattern)，应用在分类或是对未来特征的预测。
GNNPapers 详细列示了图神经网络诞生以来里程碑式的优秀模型，以及其在具体场景中的应用。
四、图卷积网络
abbr. Graph Convolution Networks。在节点嵌入这一下游任务上，基于空间的 GCNs 从彼时大热的卷积神经网络中汲取思想，直接在原图的拓扑序列上进行卷积操作；而考虑到图结构的不稳定性，基于谱的 GCNs 则将所有节点映射到傅里叶域后进行卷积乘积，再经由傅里叶逆变换得到空间域下的嵌入向量。以下是 Wu et. al (2019) 对近年来图卷积网络的总结：
GNN: The Graph Neural Network Model (2009)
这篇论文首次提出图神经网络 (Graph Neural Network) 的概念，并将模型设计为有目的的监督学习模型，分为 转换 (Transition) 和 输出 (Output) 两个部分。转换部分为每一个节点提取邻点信息，生成向量表示的 状态 (state)；输出则将该状态映射至等维的向量表示，通过 softmax 归一化进行多分类预测。相关公式如下：
其中 $f$ 和 $g$ 皆为可训练的全连接层，$l_n$为节点的标签 (可以理解为特征)，$l_{co}$ 为与节点相接的边的标签 (即我们常谈的权重)，$x_{ne}$ 代表邻点转换过后的状态 (向量)，$l_{ne}$为邻点的标签 (特征)。由于转换部分的输入 $x_n$包含了该部分邻点的输出，因而需要通过交互性的多轮迭代实现训练和推理，论文中将其称呼为 扩散机制 (Diffusion Mechanism)：
相关的数学定理 Banach’s Theorm 证实，经过扩散机制后，对于满足$∣∣f w(x,l)−f w(y,l)∣∣≤μ∣∣x−y∣∣,0≤μ<1$ 的 $w$，有仅有唯一的解。因而在训练完成后，我们可以提取 $f_w(x,l)$ 作为节点的嵌入表示。
该模型除了可用于节点级别的分类，同样可用于图的级别，只需要为每张输入的图添加一个代表全局的特殊节点即可。由于模型应用到了在节点级别进行邻点采样作为输入的思想，与后来的图卷积神经网络不谋而合，论文作者虽没有自行提出卷积的概念，但本篇论文后来被认为是第一个图卷积网络的提出者。模型采用顺时针的方式为每个节点提取固定长度的邻点列表，对相对位置上空缺的邻点采取统一的无意义填充策略；这样的做法将算法的应用场景限制在了 2D 空间，且需要使用者进行更为繁琐的数据预处理，因而成为饱受诟病的之处，也为后续优化指引了方向。
GraphSAGE: Inductive Representation Learning on Large Graphs (2017)
初代 GNN 中邻点采样的思想一直保留了下来，但 GraphSAGE 并不将采样信息局限在节点的拓扑结构里，而是使用节点的固有特征取而代之，对造成庞大参数量的扩散机制也选择了摒弃处理。根据下游任务的不同，GraphSAGE 采用不同的训练策略：应用于图嵌入时，使用负采样技术计算二阶相似度实现参数收敛；应用于分类任务时，使用 softmax 进行有监督学习。其中，无监督学习的表达式如下：
$\mathcal{J}_{\mathcal{G}}(z_u)=-\log \big(\sigma(z_u^Tz_v)\big)-Q\cdot \mathbb{E}_{v_n\sim P_n(v)}\log\big(\sigma(-z_u^Tz_{v_n})\big)$
模型的特别之处，在于每一次迭代时，都重新对邻点进行采样，前馈公式如下：
$h_v^k=\sigma\big(W^k\cdot \text{Concat}(h_v^{k-1},h_{\mathcal{N}(v)}^k)\big) $
$h_{\mathcal{N}(v)}^k=\text{Aggregate}(\{h_u^{k-1},\forall u\in\mathcal{N}(v) \})$
其中$k=1,…,K$ 为迭代次数；$h_v^kh$ 为前馈层输出的隐藏向量，无监督学习使用最后一层计算损失函数。
