本文为转载，原文链接：https://wmathor.com/index.php/archives/1531/
Introduction
既然你点进了这篇博客，我就默认你了解图的最基本概念，包括但不限于有向图、无向图的定义，这里我不再多做赘述，下面我只阐述一些比较重要的部分
图神经网络是一种直接对图结构进行操作的神经网络。GNN 的一个典型应用是节点分类。本质上，图中的每一个节点都与一个标签相关联。如下图所示，a节点的向量表示为[0.3, 0.02, 7, 4, ...]，将该向量送入下游继续做分类即可得到a节点的类别。
a 节点的向量表示究竟是如何得到的，等会儿我会详细阐述，不过在这我们可以简单的思考一下，a 节点的向量表示一定应该与其相邻节点和**相邻边有关系，假设每个节点的one-hot向量表示为
，则
其中表示与
相连边的one-hot表示，
表示与v相邻节点的embedding，
表示与
相邻节点的one-hot表示。最终再将
向量和真实标签计算loss，不过也有的地方是将
向量和
经过一轮融合之后再计算loss，例如
上述公式以及符号可能不好理解，这里其实可以类比 Word2Vec。在 Word2Vec 中，输入的是每个词对应的 one-hot，即
。输出的是这个词对应的 embedding，即
作为一个典型的非欧式数据，对于图数据的分析主要集中在节点分类，链接预测和聚类等。对于图数据而言，图嵌入（Graph / Network Embedding）和图神经网络（Graph Neural Networks, GNN）是两个类似的研究领域。图嵌入旨在将图的节点表示成一个低维向量空间，同时保留网络的拓扑结构和节点信息，以便在后续的图分析任务中可以直接使用现有的机器学习算法。一些基于深度学习的图嵌入同时也属于图神经网络，例如一些基于图自编码器和利用无监督学习的图卷积神经网络等。下图描述了图嵌入和图神经网络之间的差异：
DeepWalk：第一个无监督学习节点嵌入的算法
DeepWalk 用一句话概述就是：随机生成图节点序列，然后对该序列进行 Word2Vec
具体来说，给定一个图，我们随机选择一个节点作为起始，然后随机 "步行" 到邻居节点，直到节点序列的长度达到给定的最大值。例如下图，分别选择 d,e,f 作为起点进行游走，得到三条节点序列
在这种情况下，我们可以将节点和节点序列分别看作是“单词”和“句子”，然后利用skip-gram或者cbow算法训练得到每个节点的embedding。
DeepWalk算法主要包含两个部分：一个随机游走序列生成器和一个更新过程。
随机游走序列生成器首先在图中随机抽样一个随机游走
的根节点
，接着从根节点的邻居中均匀地随机抽样一个节点直到达到设定的最大长度
。对于一个生成的以
为中心左右窗口为
的随机游走序列
，DeepWalk利用SkipGram算法通过最大化以
为中心，左右
为窗口的同其他节点共现概率来优化模型：
DeepWalk和Word2Vec的类比如下表所示：
node2vec: bias random walk
一般的随机游走公式
其中，表示
节点的邻居节点数量，
表示当前节点，
表示下一个选择的节点
一般的随机游走存在以下几个问题：
- 如果是带权图，没考虑边权值的影响
- 太过于随机，不能由模型自行学习以何种方式游走更好
实际上图的游走分为两大类：DFS和BFS
为了引入边的权重，以及依概率选择DFS或BFS，我们首先要将一般的随机游走公式进行修改：
其中，在值上与
是相等的，
可以理解为归一化的缩放因子
假设当前随机游走经过边到达顶点
，节点
和
之间的边权为
，则可以将
改写为
其中，表示当前节点
的一节邻居节点到节点
的最短距离
- p: 控制随机游走以多大的概率“回头”
- q: 控制随机游走偏向DFS还是BFS
- q较大时(q>1)，倾向于BFS
- q较小时(q<1)，倾向于DFS
- p=1=1时，
到此为止，GNN 中节点 Embedding 算法我就不再多叙述，其实还有很多更好的算法，例如 LINE，Struct2vec 等，不过我个人感觉这些 embedding 算法并不重要，或者说它们并不是 GNN 的核心部分，只要当作工具来用就行了，类比 Transformer 中 Word Embedding 的地位
References
- An introduction to Graph Neural Networks
- Random Walk in Node Embeddings (DeepWalk, node2vec, LINE, and GraphSAGE)
- How to do Deep Learning on Graphs with Graph Convolutional Networks
- A Gentle Introduction to Graph Neural Networks (Basics, DeepWalk, and GraphSage)
- Hands-on Graph Neural Networks with PyTorch & PyTorch Geometric
- PGL 全球冠军团队带你攻破图神经网络
- 台大李宏毅助教讲解 GNN 图神经网络
- 图神经网络详解
- 图嵌入 (Graph Embedding) 和图神经网络 (Graph Neural Network)
网友评论