课程主页：CS224W | Home
课程视频链接：斯坦福CS224W《图机器学习》课程(2021) by Jure Leskovec

1  前言

上一篇笔记介绍了节点嵌入的目的和一些节点嵌入的方法，着重介绍了通过随机游走的方式进行嵌入。上一篇中介绍的方法是单个节点的嵌入过程，在本文中，我们将着重学习如何嵌入一个子图或者一个完整的图。

我们还将用这个完整的图嵌入来完成以下任务：

• 分类有毒/无毒的分子
• 识别异常图

2  嵌入整个图的方法

2.1  方法一

最简单（但有效）的方法：使用标准的节点嵌入方法得到嵌入后，再对所有的节点嵌入求和或求平均。如以下式子：

一个利用该式子进行分子分类的例子：Convolutional Networks on Graphs for Learning Molecular Fingerprints

2.2  方法二

引入一个虚拟节点代表整个图然后执行一个标准的节点嵌入，将求得的虚拟节点嵌入作为整个图的嵌入。（这个方法是在Gated Graph Sequence Neural Networks中提出的一种通用的子图嵌入技术）

2.3  方法三：匿名随机游走

2.3.1  匿名随机游走方法介绍

核心思想：匿名游走中的节点状态对应于我们在随机漫步中第一次访问该节点时的索引。

该方法来自于Anonymous Walk Embeddings, ICML 2018

解释：在这种方法中，我们用第一次访问某节点时的索引顺序来表示游走路径，如上图中的Random Walk 1和Random Walk 2都可以用同一个Anonymous Walk1来表示，这种做法会使具体哪些节点被游走到这件事不可知，因此叫做匿名随机游走。

由此，我们可以得到，当一个匿名随机游走的游走长度为3时，会出现5种随机游走的方式：

经统计发现，匿名随机游走的个数随游走的路径长度呈指数级增长： 

2.3.2  匿名随机游走的简单使用

总的来说分为两步：

1. 模拟游走长度为的匿名游走并进行记录游走的数量；
2. 用这些游走的概率分布代表整个图。

举例：

• 若设置随机游走的路径长度为；
• 由上文可知，最多会出现5种随机游走的方式，因此可以得到一个5维的向量；
• 即表示匿名游走在整个图G的匿名游走过程中出现的概率。

当匿名游走的长度增加时，匿名游走的数量成倍增加，选取游走方式来嵌入显然不可取。
那么这种情况下我们应该采样多少个匿名游走来嵌入得到图的概率分布呢？

设我们需要独立地生成个随机游走集合，那么可以根据以下公式来得到：

 在这个公式中，我们通过两个参数和来量化准确性，表示游走长度为时的游走总数量，如：当时，设置参数和后可以得到。（此公式的由来Jure并没有介绍）

2.3.3  新思路：学习匿名游走的嵌入

与其简单地按照每次步行发生的时间来表示每次步行，我们还可以学习匿名游走的嵌入

在学习所有匿名游走的嵌入的同时，我们也可以学习到整个图的嵌入，表示采样后的匿名游走个数。

关键思想：嵌入一个游走使得它能预测到与它邻近的游走。

具体做法：

1. 从节点开始进行T次长度为的随机游走得到：（注：此时的不再是一组节点，而是一组匿名游走）
2. 学习预测在大小的窗口中同时出现的游走；如：给出和，且，则要能预测出
3. 通过以下目标函数学习匿名游走的嵌入：

   

 其中，是所有可能出现的游走嵌入的数目。具体参考Anonymous Walk Embeddings, ICML 2018

2.3.4  匿名随机游走的两种思路小结

• 思路一：对一定数量的匿名游走进行抽样，并用每一个匿名游走发生次数的比例来表示这个图
• 思路二：嵌入每一个匿名行走，连接它们的嵌入来得到整个图的嵌入

3  总结

在第三篇笔记3.1和3.2中，我们讨论了学习节点和图的嵌入以执行下游任务的方法——图表示学习，并以此来取代人工特征工程。

编码器和解码器框架：
编码器：简单的编码器仅仅是一个查找；
解码器：基于节点嵌入和原始图节点相似度之间的匹配度预测分数；

基于随机游走的方式定义节点相似度：
讨论了DeepWalk和Node2vec两种方法，都采用了相同的优化学习方式，用到了负采样的方法。

扩展到整个图的嵌入：（3.2学习内容）
可以进行简单的求和或归并，也可以采用匿名随机游走，按照第一次访问给定节点的时间或索引来表示一个游走。

4  参考资料

• 03-nodeemb.pdf (stanford.edu)
• 图神经网络（CS224w）学习笔记3 Node Embeddings_白衣少年不留白的博客-CSDN博客