【CS224W课程笔记】Graph Representation Learning

Feature Learning in Graphs

Goal: 基于图为机器学习进行高效的、任务独立的特征工程。

Task: 将图中的每个节点映射到一个低维空间，即d维的向量。这是一种节点的分布式表示，节点之间嵌入后的相似性表明了对应网络的相似性，继而实现编码网络信息、生成节点表示的目的。

Challenge: 现代深度学习大多是为一些简单的序列或网格而设计的，而网络相较而言要复杂得多，它具有复杂的拓扑结构、没有固定的节点顺序或参考点、通常是动态的且具有多模态特征。

Embedding Nodes

Setup: 设 $V$ 表示节点集合， $A$ 表示01邻接矩阵。
Goal: 对节点进行编码，使得其在嵌入空间的相似度（可以通过点乘计算）接近于原始网络中的相似度。
${similarity(u, v)} \approx {\mathbf{z}_v^{\top} \mathbf{z}_u}$

Learning:

定义encoder，即节点和嵌入式表示之间的映射关系；
$ENC(v) = \mathbf{z}_v$
定义节点相似度计算公式，即原始网络中相似度的衡量方式，需要明确向量空间中的关系是如何映射到原始网络中的关系的；
优化encoder中的参数使得Goal中的相似度近似公式成立。

Encoder:
最简单的编码方式：encoder is just an embedding-lookup，即： $ENC(v) = \mathbf{Z}\mathbf{v}$ ，其中 $\mathbf{Z} \in \mathbb{R}^{d \times |\mathcal{v}|}$ 是一个矩阵，每一列为一个node embedding，也是我们所要学习的， $\mathbf{v} \in \mathbb{I}^{|\mathcal{v}|}$ 是一个指示向量，除了表示节点 $\mathbf{v}$ 的一列为1之外，其它列均为0。

Node Embedding

Node Similarity:
定义节点相似性的方式有很多，如：

基于邻接的，即相连的节点即为相似节点
根据节点之间的跳数定义相似性
random walk方法（接下来介绍的）

不同的节点相似性定义方案适用于不同的应用场景，如node2vec算法在节点分类任务上具有较好的性能，而基于跳数的方法在关系检测的任务上表现较好。而Random walk方法通常更有效。
总而言之，必须选择与应用相匹配的节点相似性定义。

Random Walk Approaches to Node Embedding

Material based on:
Perozzi et al. 2014. DeepWalk: Online Learning of Social Representations. KDD.
Grover et al. 2016. Node2vec: Scalable Feature Learning for Networks. KDD.

Random Walk:
给定一个图和一个起点，随机选择它的一个邻居并移动到该邻居；然后再随机选择一个当前位置的邻居继续移动，以此类推。以这种方式选择的点的随机序列就是当前图的一个Random walk。

Random-walk Embeddings:
定义 $\mathbf{z}_u^{\top} \mathbf{z}_v \approx$ $u$ 和 $v$ 在当前网络的一个random walk中同时出现的概率。

Process:

使用某些random walk策略 $R$ 估计从节点 $u$ 开始的一个random walk序列中经过节点 $v$ 的概率 $P_R(v|u)$
优化节点的嵌入式表示以对这些random walk统计信息进行编码

Why Random Walks？

Expressivity: 对节点相似性的定义灵活且随机，结合了本地及高阶的邻居信息；
Efficiency: 训练时无需考虑所有节点对，仅需考虑random walks中同时出现的节点对。

Feature Learning as Optimation:
给定图 $G=(V, E)$ ，期望可以学到一种映射 $z:u \rightarrow \mathbb{R}^d$ ，其目标可以一个对数似然函数表示（其中 $N_R(u)$ 表示根据策略R得到的节点 $u$ 的邻居）：
$max_z \sum_{u \in V} log P(N_R(u)|z_u)$
即给定节点 $u$ ，我们期望学到可以预测其邻域 $N_R(u)$ 节点的特征表示。

Random Walk Optimization:

使用某种策略 $R$ （random walk的次数、长度等等）从图中的每一个节点开始进行短的定长的random walks；
对于每个节点 $u$ ，收集其邻域 $N_R(u)$ ，注意其邻域是可包含重复节点的，因为在random walks中可能重复访问某一节点多次；
优化目标是给定节点 $u$ ，预测其邻域 $N_R(u)$ ，即上述对数似然函数，根据次目标优化节点的嵌入表示。

由上述最大化优化目标，可以得到以下损失函数，即优化random walk embeddings $\approx$ 寻找embeddings $\mathbf{z}_u$ 使得损失 $\mathcal{L}$ 最小：
$\mathcal{L} = \sum_{u \in V} \sum_{v \in N_R(u)} -log(P(v|\mathbf{z}_u)) \\ P(v|\mathbf{z}_u) = \frac{exp(\mathbf{z}_u^{\top} \mathbf{z}_v)}{\sum_{n \in V} exp(\mathbf{z}_u^{\top} \mathbf{z}_n)}$

Why Softmax: 期望 $\sum_i exp(x_i) \approx max_i exp(x_i)$ ，使起始节点和其邻域中的节点相似度相较于其它节点尽可能得高

对该损失函数的详细解释如下图所示：
[图片上传失败...(image-11090d-1590747776172)]

对损失计算的时间复杂度的优化：
但关于该损失函数的计算需要 $O(|V|^2)$ 的时间复杂度，这主要来源于softmax的操作，可对其进行近似计算，解决方法是Negative Sampling：
$log(\frac{exp(\mathbf{z}_u^{\top} \mathbf{z}_v)}{\sum_{n \in V} exp(\mathbf{z}_u^{\top} \mathbf{z}_n)}) \approx log(\sigma (\mathbf{z}_u^{\top} \mathbf{z}_v)) - \sum_{i=1}^k log(\sigma (\mathbf{z}_u^{\top} \mathbf{z}_{n_i})), n_i \sim P_V$

在该方案中，并非对所有节点执行归一化操作，而是随机选择 $k$ 个负样本进行归一化，且用到了sigmoid。其中 $P_V$ 是所有节点的随机分布；关于负样本的个数 $k$ 的说明如下：

$k$ 越大，估计就越可靠；
$k$ 越大，关于负例的bias就越高；
通常 $k$ 取5到20。

Random Walk的策略R：
最简单的想法是：只需从每个节点开始进行固定长度的、无偏的random walk。
该想法的问题在于相似性的概念过于受限，对于那些距离较远但是相似的节点则无法检测到。

Node2Vec

Key observation：扩展节点 $u$ 的邻域概念可以带来node embeddings的更丰富的信息，因此开发额外的第二种顺序的random walk策略 $R$ 来生成节点 $u$ 的邻域 $N_R(u)$ 。

Biased Walks
idea：使用灵活的、有偏的（biased）random walk可以实现关于网络本地视图及全局视图的权衡，如通过BFS获取局部微观视图（Local microscopic view），通过DFS获取全局宏观视图（Global macroscopic view）

这样的策略需要指定两个参数，同时记录到达当前结点的上一节点：

返回参数 $p$ ：返回上一个节点的概率
In-out参数 $q$ ：指明是DFS（outwards）还是BFS（inwards），可以理解为BFS和DFS的比例。例如：若节点进行BFS的概率为1，返回上一节点的概率为1/p，则进行DFS的概率为1/q（这里的概率是指未做归一化的概率）。这样的策略称为Biased Random Walks。

Node2Vec Algorithm:

计算random walk的概率；
模拟random walk的过程；
使用随机梯度下降优化node2vec的目标。

How to use Embedding $z_i$ ？

聚类检测
节点分类：基于 $z_i$ 预测节点 $i$ 的类别 $f(z_i)$
关系预测：基于 $f(z_i,z_j)$ 预测边 $(i, j)$ ，其中 $f(z_i,z_j)$ 可针对两个向量的连接、平均、乘积、或差别进行计算。

Embedding Entire Graphs

对图中的节点进行embedding，然后求和或取平均得到图的嵌入式表示。Duvenaud et al., 2016使用了该方案基于分子的图结构对其进行分类。
$z_G = \sum_{v \in G} z_v$
引入一个虚拟节点来表示（子）图，图中的其它节点均与该节点相连，然后在其上执行标准的图嵌入算法。由Li et al., 2016提出作为一种子图嵌入式表示的通用方法。
Anonymous Walk Embeddings