1. 章节前言

1. 图表示学习graph representation learning：学习到图数据用于机器学习的、与下游任务无关的特征，我们希望这个向量能够抓住数据的结构信息。

这个数据被称作特征表示feature representation或嵌入embedding。

2. Why embedding?

任务：将节点映射到embedding space

• embedding的相似性可以反映原节点在网络中的相似性，比如定义有边连接的点对为相似的点，则这样的点的embedding应该离得更近
• embedding编码网络信息
• embedding可用于下游预测任务

3. node embedding举例：Zachary’s Karate Club network1 的二维节点嵌入可视化（将不同类的节点很好地分开了）

图源：Perozzi et al. DeepWalk: Online Learning of Social Representations. KDD 2014

2. Node Embeddings: Encoder and Decoder

1. 图 G ，节点集合 V ，邻接矩阵 A （二元的）（简化起见：不考虑节点的特征或其他信息）

2. 节点嵌入：目标是将节点编码encode为embedding space中的向量embedding，使embedding的相似度（如点积2）近似于图中节点的相似度（需要被定义）

3. Encoder：将节点映射为embedding

定义一个衡量节点相似度的函数（如衡量在原网络中的节点相似度）

Decoder DEC 将embedding对映射为相似度得分

4. two key components

d一般是64-1000维

5. “shallow” encoding

Z每列是一个节点所对应的embedding向量。v是一个其他元素都为0，对应节点位置的元素为1的向量。通过矩阵乘法的方式得到结果。

这种方式就是将每个节点直接映射为一个embedding向量，我们的学习任务就是直接优化这些embedding。

缺点：参数多，很难scale up3到大型图上。

优点：如果获得了Z，各节点就能很快得到embedding。

有很多种方法：如DeepWalk，node2vec等

6. Encoder + Decoder Framework Summary

• Shallow encoder: embedding lookup
• 优化参数：Z（包含每个节点对应的node embedding）
• 在Lecture 6将介绍deep encoders（已完成对应章节的笔记，见cs224w（图机器学习）2021冬季课程学习笔记7 Graph Neural Networks 1: GNN Model）
• Decoder: based on node similarity
• 目标：对于相似点对 (u,v)，最大化其embedding点积

7. 节点相似的不同定义

• 有边
• 共享邻居
• 有相似的structural roles
• 本节课：随机游走random walk定义的节点相似度

8. Note on Node Embeddings

• 无监督/自监督unsupervised/self-supervised：不用节点的标签和特征，直接估算得到节点的一系列坐标（如embedding），这一系列坐标在某种程度上可以保留网络结构（由DEC捕获）
• task independent

3. Random Walk Approaches for Node Embeddings

1. 统一符号表示notation

2. random walk：从某一节点开始，每一步按照概率选一个邻居，走过去，重复。停止时得到一系列节点

3. random walk embeddings

4. Why random walks?

• Expressivity: Flexible stochastic definition of node similarity that incorporates both local and higher-order neighborhood information

Idea: if random walk starting from node 𝒖 visits 𝒗 with high probability, 𝒖 and 𝒗 are similar (high-order multi-hop information)

• Efficiency: Do not need to consider all node pairs when training; only need to consider pairs that co-occur on random walks

5. unsupervised feature learning

6. feature learning as optimization

7. random walk optimization

把最大似然估计翻过来，拆开，就成了需被最小化的损失函数L：

我们发现问题就在于用于softmax归一化的这个分母：

8. 为了解决这个分母，我们使用negative sampling6的方法：简单来说就是原本我们是用所有节点作为归一化的负样本，现在我们只抽出一部分节点作为负样本，通过公式近似减少计算

这个随机分布不是uniform random，而是random in a biased way：概率与其度数成比例。

负样本个数k的考虑因素：

• 更高的k会使估计结果更鲁棒robust（我的理解是方差↓）
• 更高的k会使负样本上的偏差bias更高（其实我没搞懂这是为什么）
• 实践上的k常用值：5-20

9. 优化目标函数（最小化损失函数）的方法：随机梯度下降SGD

10. random walks: summary

11. random walk策略

• Simplest idea: Just run fixed-length, unbiased random walks starting from each node

举例：DeepWalk7

问题：相似度概念受限

• node2vec8

• 其他随机游走方法：

12. Summary so far

• 节点嵌入：使embedding的向量距离能够反应原网络中的节点相似度
• 衡量节点相似度的指标

Naive: 节点间有边

Neighborhood overlap （在Lecture 212 讲过）

random walk approaches（本节课所讲）

• 需要根据具体情况来选择算法。node2vec在节点分类任务上表现更好，不同的方法在不同数据的链接预测任务上表现不同13。random walk approaches整体上更有效。

4. Embedding Entire Graphs

任务示例：

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

也可以视为对节点的一个子集的嵌入

1. 方法1：聚合（加总或求平均）节点的嵌入

示例：Duvenaud D, Maclaurin D, Aguilera-Iparraguirre J, et al. Convolutional networks on graphs for learning molecular fingerprints[J]. arXiv preprint arXiv:1509.09292, 2015. 用图结构对分子进行分类。虽然方法很简单但是表现挺好。

2. 方法2：创造一个假节点（virtual node），用这个节点嵌入来作为图嵌入

这个virtual node和它想嵌入的节点子集（比如全图）相连

示例：Li Y, Tarlow D, Brockschmidt M, et al. Gated graph sequence neural networks[J]. arXiv preprint arXiv:1511.05493, 2015.

3. 方法3：anonymous walk embeddings14（以节点第一次出现的序号（是第几个出现的节点）作为索引）

这种做法会使具体哪些节点被游走到这件事不可知（因此匿名）

• anonymous walks的个数随walk长度指数级增长：

• anonymous walks的应用1：模拟图上长为 l ll 的匿名随机游走，将图表示为walks的概率分布向量（我感觉有点bag-of-anonymous walks、有点像GDV那些东西，总之都是向量每个元素代表其对应object的出现概率/次数）

• sampling anonymous walks（图中这个m我还不知道是从哪来的）

• anonymous walks的应用2：walk embeddings

• Summary

• Lecture 8中会讲到Hierarchical Embeddings方法，分层级聚合图中节点获得全图嵌入向量

5. 本章总结

1. 如何使用节点嵌入：聚类、社区发现，节点分类，链接预测（通过concatenate、哈达玛积、取平均、求和、计算距离来得到链接嵌入）图分类（聚合节点嵌入或使用匿名随机游走获得图嵌入）

哈达玛积、sum/avg、L2距离在无向图上表现好，因为它们是commulative的（就是交换参数对结果没有影响）；如果是有向图的话concatenate就会好

2. Summary