Question

1. 图机器学习的核心问题是：找到一种将图结构信息结合到机器学习模型中的方法。例如：

   • 在社交网络的链接预测任务中，可能需要对节点之间的成对属性进行编码，如关系强度 relationship strength 或者共同好友数量。
   • 在节点分类任务中，可能需要包含节点在图中全局位置相关的信息，或者节点局部邻域结构相关的信息。

   从机器学习角度来看，面临的挑战是：没有直接的方法可以将有关图结构的高维非欧信息编码为特征向量。为了从图上提取图结构信息，传统的机器学习方法通常依赖于图的统计信息（如 degree 等）、核函数、或者精心设计的用于衡量图局部邻域结构的特征。但是，这些方法都有局限性：

   • 这些人工设计的特征不灵活，无法在学习过程中自适应地调整。
   • 人工设计特征可能是一个耗时耗力的过程。

   最近涌现出很多方法来寻求学习图的有效representation 从而能够编码有关图结构信息，这些方法背后的思想是：学习一个映射，该映射将节点或者子图或者整个图映射到低维向量空间${\mathbb{R}}^d$$ \mathbb R^d $ ，其中$d$$ d $ 为低维向量空间的维度。在映射过程中，保持 emebdding 空间中的几何关系能够反映原始图结构。一旦得到这样的映射，就可以将学到的 embedding 用作下游机器学习任务的特征输入。

   表示学习representation learning 方法和之前工作的主要区别在于如何处理图结构表示的问题。

   • 之前工作将该问题视为预处理步骤，通过人工设计的统计信息来提取图结构信息。
   • representation learning 将该问题视为机器学习任务本身，使用数据驱动的方法来学习对图结构进行编码的 emebdding 。

2. 假设representation learning 的输入为无向图$\mathcal{G}=(\mathcal{V},\mathcal{E})$$ \mathcal G = (\mathcal V, \mathcal E) $ ，其邻接矩阵为$\mathbf{A}$$ \mathbf A $ 。每个节点$v_i\in \mathcal{V}$$ v_i\in \mathcal V $ 对应一个节点属性向量${\overrightarrow{\mathbf{x}}}_i\in {\mathbb{R}}^m$$ \mathbf{\vec x}_i\in \mathbb R^m $ ，所有节点的属性向量构成节点属性矩阵$\mathbf{X}\in {\mathbb{R}}^{m\times |\mathcal{V}|}$$ \mathbf X\in \mathbb R^{m\times |\mathcal V|} $ ，其中$m$$ m $ 为属性向量维度。

   representation learning 的目标是利用$\mathbf{A}$$ \mathbf A $ 和$\mathbf{X}$$ \mathbf X $ 包含的信息将每个节点或子图或全图映射到一个向量$\overrightarrow{\mathbf{z}}\in {\mathbb{R}}^d$$ \mathbf{\vec z}\in \mathbb R^d $ ，其中$d\ll |\mathcal{V}|$$ d\ll |\mathcal V| $ 。

   大多数方法仅使用$\mathbf{A}$$ \mathbf A $ 和$\mathbf{X}$$ \mathbf X $ 中的信息从而以无监督方式来学习这个映射，无需了解特定的下游机器学习任务。也有一些方法以监督学习的方式利用下游任务的监督信息来学习该映射，这些监督信息可能与单个节点或者子图或者全图相关。

   论文 《Representation Learning on Graphs: Methods and Applications》 以综述的形式总结了这些 representation learning 方法。

3.1 节点 embedding

1. 我们首先讨论节点 embedding，其目的是将节点编码为低维向量，从而包含节点在图中的位置信息以及节点的局部邻域结构。这些低维 embedding 可以看作是将节点投影到低维潜在空间中，其中潜在空间中节点之间的几何关系对应于原始空间中节点之间的交互（如是否存在边）。

   下图给出了著名的 Zachary Karate Club 社交网络的节点 embedding，这些二维的节点 embedding 捕获了社交网络中隐式的社区结构 community structure 。下图中，如果两个用户是好友关系，则他们之间存在边。节点根据不同社区community 进行着色。

   

3.1.1 Encoder-Decoder 视角

1. 在讨论各种节点 embedding 技术之前，我们首先提出一个统一的 encoder-decoder 框架，在该框架中统一了各种各样的节点 embedding 方法。

   在encoder-decoder 框架中，我们围绕两个关键的映射函数来组织各种方法：

   • 一个编码器 encoder：它将每个节点映射到一个低维向量。
   • 一个解码器 decoder：它从学到的 embedding 中解码有关图结构的信息。

   encoder-decoder 思想背后的直觉如下：如果我们可以从encoder 的低维的 embedding 中解码高维的图信息（如，节点在图中的全局位置或节点的局部邻域结构），则原则上这些 embedding 包含了下游机器学习任务所需的所有信息。

   • encoder 是一个函数：$\text{ENC}:\mathcal{V}\to {\mathbb{R}}^d$$ \text{ENC}: \mathcal V \rightarrow \mathbb R^d $ 。它将节点$v_i\in \mathcal{V}$$ v_i\in \mathcal V $ 映射到 embedding 向量${\overrightarrow{\mathbf{z}}}_i\in {\mathbb{R}}^d$$ \mathbf{\vec z}_i\in \mathbb R^d $ ，其中$d$$ d $ 为 embedding 向量维度。

   • decoder 也是一个函数，它接收一组节点 embedding，并从这些 embedding 中解码人工指定的图统计信息。如，decoder可能会根据给定节点的 embedding 预测节点之间的边，或者预测节点所属的社区。

     原则上 decoder 可以有很多选择，但是绝大多数方法都是采用基础的 pairwise decoder ：

     $$\text{DEC}:{\mathbb{R}}^d\times {\mathbb{R}}^d\to {\mathbb{R}}^{+}$$

     它将一对节点的 embedding 映射到一个实数值的节点相似度，从而刻画原始图中两个节点的相似性。

2. encoder-decoder 框架整体架构如下图所示。

   • 首先 encoder 根据节点在图中的位置、节点局部邻域结构信息、节点属性信息，从而将节点$v_i$$ v_i $ 映射到低维向量${\overrightarrow{\mathbf{z}}}_i$$ \mathbf{\vec z}_i $ 。
   • 然后 decoder 从低维向量${\overrightarrow{\mathbf{z}}}_i$$ \mathbf{\vec z}_i $ 中提取人工指定的信息，这可能是有关$v_i$$ v_i $ 局部邻域的信息（如，直接相连的边），或者$v_i$$ v_i $ 关联的类别标签信息（如社区标签）。

   通过联合优化 encoder 和 decoder，系统学会了将图结构有关的信息压缩到低维 embedding 空间中。

   

3. 我们将 pairwide decodr 应用到一对 embedding$({\overrightarrow{\mathbf{z}}}_i,{\overrightarrow{\mathbf{z}}}_j)$$ (\mathbf{\vec z}_i,\mathbf{\vec z}_j) $ 时，我们得到原始$v_i,v_j$$ v_i,v_j $ 之间相似性的重构。我们的目标是优化 encoder, decoder，从而最大程度地减少重构误差，使得：

   $$\text{DEC}(\text{ENC}(v_i),\text{ENC}(v_j))=\text{DEC}({\overrightarrow{\mathbf{z}}}_i,{\overrightarrow{\mathbf{z}}}_j)\simeq s_{\mathcal{G}}(v_i,v_j)$$

   即，我们要优化 encoder-decoder 模型，以便可以从节点的低维 embedding${\overrightarrow{\mathbf{z}}}_i$$ \mathbf{\vec z}_i $ 和${\overrightarrow{\mathbf{z}}}_j$$ \mathbf{\vec z}_j $ 解码原始图的成对节点相似性$s_{\mathcal{G}}(v_i,v_j)$$ s_{\mathcal G}(v_i,v_j) $ 。

   其中$s_{\mathcal{G}}$$ s_{\mathcal G} $ 是在图$\mathcal{G}$$ \mathcal G $ 上定义的、节点之间的相似性函数。例如：

   • 可以定义$s_{\mathcal{G}}(v_i,v_j)=A_{i,j}$$ s_{\mathcal G}(v_i,v_j) = A_{i,j} $ ，即节点之间的相似性为它们之间的边的权重。
   • 也可以根据图$\mathcal{G}$$ \mathcal G $ 上固定长度随机游走序列上$v_i,v_j$$ v_i,v_j $ 共现的概率来定义$s_{\mathcal{G}}(v_i,v_j)$$ s_{\mathcal G}(v_i,v_j) $ 。

   在实践中，大多数方法通过最小化经验损失$\mathcal{L}$$ \mathcal L $ 来最优化重建过程：

   $$\mathcal{L}=\sum _{(v_i,v_j)\in \mathcal{D}}\mathcal{l}(\text{DEC}({\overrightarrow{\mathbf{z}}}_i,{\overrightarrow{\mathbf{z}}}_j),s_{\mathcal{G}}(v_i,v_j))$$

   其中：

   • $\mathcal{D}$$ \mathcal D $ 为训练集，它由成对的节点 pair 对组成。
   • $\mathcal{l}:\mathbb{R}\times \mathbb{R}\to \mathbb{R}$$ \mathcal l:\mathbb R\times \mathbb R \rightarrow \mathbb R $ 是一个人工定义的损失函数，它衡量了预估的相似度$\text{DEC}({\overrightarrow{\mathbf{z}}}_i,{\overrightarrow{\mathbf{z}}}_j)$$ \text{DEC}\left(\mathbf{\vec z}_i, \mathbf{\vec z}_j\right) $ 和真实相似度$s_{\mathcal{G}}(v_i,v_j)$$ s_{\mathcal G} (v_i,v_j) $ 之间的差异。

4. 一旦我们优化了 encoder-decoder ，就可以使用训练好的 encdoer 为节点生成 embedding，然后将其作为下游机器学习任务的特征输入。例如，可以将学到的 embedding 作为逻辑回归分类器的输入，从而预测节点所属的社区。

5. 通过这种 encoder-decoder 视角，我们沿着以下四个部分对各种节点 embedding 方法进行讨论：

   • 成对节点相似性函数pairwise similarity function$s_{\mathcal{G}}:\mathcal{V}\times \mathcal{V}\to {\mathbb{R}}^{+}$$ s_{\mathcal G}:\mathcal V\times \mathcal V \rightarrow \mathbb R^+ $ ：在图$\mathcal{G}$$ \mathcal G $ 上定义，用于衡量两个节点之间相似性。
   • encoder 函数 ENC：用于生成节点 embedding。该函数包含大量可训练的参数，这些参数在训练期间进行优化。
   • decoder 函数 DEC：用于从生成的节点 embedding 中重建 pairwise 节点相似性。该函数通常不包含可训练的参数。
   • 损失函数$\mathcal{l}$$ \mathcal l $ ：用于评估相似性重建的质量，即如何比较$\text{DEC}({\overrightarrow{\mathbf{z}}}_i,{\overrightarrow{\mathbf{z}}}_j)$$ \text{DEC}\left(\mathbf{\vec z}_i, \mathbf{\vec z}_j\right) $ 和真实相似度$s_{\mathcal{G}}(v_i,v_j)$$ s_{\mathcal G} (v_i,v_j) $ 的差异。

   正如我们即将讨论的，各种节点 embedding 方法之间的主要区别在于如何定义这四个部分。

6. 我们讨论的所有方法都涉及通过最小化损失函数来优化 encoder 的参数。大多数情况下我们使用随机梯度下降算法来优化，尽管某些算法确实允许通过矩阵分解来获得闭式解。

   注意，这里我们关注的重点并不是优化算法，而是不同 embedding 方法之间的更高层次的差异，而与底层优化方法的细节无关。

3.1.2 浅层 embedding

1. 大多数节点 embedding 方法都依赖于我们所说的浅层嵌入 shallow embedding 。对于这些浅层 embedding 方法，将节点映射到 embedding 向量的 encoder 函数仅仅是一个 embedding lookup：

   $$\text{ENC}(v_i)=\mathbf{Z}{\overrightarrow{\mathbf{v}}}_i$$

   其中：

   • $\mathbf{Z}\in {\mathbb{R}}^{d\times |\mathcal{V}|}$$ \mathbf Z\in \mathbb R^{d\times |\mathcal V|} $ 是包含所有节点 embedding 向量的 embedding 矩阵，第$i$$ i $ 列对应于节点$v_i$$ v_i $ 的 embedding 向量。
   • ${\overrightarrow{\mathbf{v}}}_i\in {\mathbb{R}}^{|\mathcal{V}|}$$ \mathbf{\vec v}_i\in \mathbb R^{|\mathcal V|} $ 为节点$v_i$$ v_i $ 的 one-hot 向量。

   浅层 embedding 方法的可训练参数仅仅是$\mathbf{Z}$$ \mathbf Z $ ，即直接优化 embedding 矩阵$\mathbf{Z}$$ \mathbf Z $ 。

2. 浅层 embedding 方法在很大程度上受到降维dimensionality reduction和多维缩放multi-dimensional scaling 中的经典矩阵分解技术的启发。但是，我们在 encoder-decoder 框架中重新解释了它们。

   下表总结了 encoder-decoder 框架中的一些著名的浅层 embedding 方法，我们根据几个方面来区分它们：decoder 函数、图相似性度量、损失函数。

   总体而言它们分为基于矩阵分解的方法Matrix Factorization、基于随机游走的方法Random Walk 。注意，在基于随机游走的方法中，decoder 和 similarity 函数都是非对称的，其中相似度函数$p_{\mathcal{G}}(v_j\mid v_i)$$ p_{\mathcal G}(v_j\mid v_i) $ 对应于从$v_i$$ v_i $ 开始的固定长度的随机游走序列中访问节点$v_j$$ v_j $ 的概率。

   注意，相似度函数$p_{\mathcal{G}}(v_j\mid v_i)$$ p_{\mathcal G}(v_j\mid v_i) $ 就是$s_{\mathcal{G}}(v_i,v_j)$$ s_\mathcal G(v_i,v_j) $ 。在不同的模型中，$s_{\mathcal{G}}(v_i,v_j)$$ s_\mathcal G(v_i,v_j) $ 有不同的表现形式。而在基于随机游走的方法中，其表现形式就是$p_{\mathcal{G}}(v_j\mid v_i)$$ p_{\mathcal G}(v_j\mid v_i) $ 。

   

a. Matrix Factorization

1. 早期的节点 embedding 方法主要集中于矩阵分解上，这直接受到经典的降维技术的启发。

2. 拉普拉斯特征图Laplacian Eigenmaps：最早的、最著名的基于矩阵分解的方法是拉普拉斯特征图Laplacian Eigenmaps:LE 方法。我们可以将拉普拉斯特征图视为一种 encoder-decoder 框架内的浅层 embedding 方法，其中 decoder 定义为：

   $$\text{DEC}({\overrightarrow{\mathbf{z}}}_i,{\overrightarrow{\mathbf{z}}}_j)=||{\overrightarrow{\mathbf{z}}}_i-{\overrightarrow{\mathbf{z}}}_j|{|}_2^2$$

   损失函数根据节点pair 对的相似性进行加权：

   $$\mathcal{L}=\sum _{(v_i,v_j)\in \mathcal{D}}\text{DEC}({\overrightarrow{\mathbf{z}}}_i,{\overrightarrow{\mathbf{z}}}_j)\times s_{\mathcal{G}}(v_i,v_j)$$

3. 内积方法Inner-product method：在拉普拉斯特征图之后，有大量基于 pairwise 的、内积式 decoder 的 embedding 方法，其中 decoder 定义为：

   $$\text{DEC}({\overrightarrow{\mathbf{z}}}_i,{\overrightarrow{\mathbf{z}}}_j)={\overrightarrow{\mathbf{z}}}_i^{\mathrm{\top }}{\overrightarrow{\mathbf{z}}}_j$$

   即两个节点之间关系的强度strength 和它们 embedding 的内积成正比。

   图因子分解 Graph Factorization:GF、GraRep、HOPE 都完全属于此类。这三种方法都使用内积式 decoder，都采用均方误差 mean squared error:MSE 损失函数：

   $$\mathcal{L}=\sum _{(v_i,v_j)\in \mathcal{D}}||\text{DEC}({\overrightarrow{\mathbf{z}}}_i,{\overrightarrow{\mathbf{z}}}_j)-s_{\mathcal{G}}(v_i,v_j)|{|}_2^2$$

   它们之间的主要区别在于采用的节点相似性函数不同，即如何定义$s_{\mathcal{G}}(v_i,v_j)$$ s_{\mathcal G}(v_i,v_j) $ 。

   • GF 算法直接基于邻接矩阵来定义节点相似度，即$s_{\mathcal{G}}(v_i,v_j)=A_{i,j}$$ s_{\mathcal G}(v_i,v_j) = A_{i,j} $ 。
   • GraRep 算法考虑邻接矩阵的各种幂次从而捕获高阶节点相似性，如$s_{\mathcal{G}}(v_i,v_j)=({\mathbf{A}}^2{)}_{i,j}$$ s_{\mathcal G}(v_i,v_j) = (\mathbf A^2)_{i,j} $ 。
   • HOPE 算法支持通用的相似性度量，如基于 Jaccard 指标的邻域交集。

   这些不同的相似性函数在建模一阶邻近性（如$s_{\mathcal{G}}(v_i,v_j)=A_{i,j}$$ s_{\mathcal G}(v_i,v_j) = A_{i,j} $ ）和建模高阶邻近性（$s_{\mathcal{G}}(v_i,v_j)=({\mathbf{A}}^2{)}_{i,j}$$ s_{\mathcal G}(v_i,v_j) = (\mathbf A^2)_{i,j} $ ）之间进行权衡。

4. 本节中我们将这些方法统称为基于矩阵分解的方法，因为大致上它们优化了以下形式的损失函数：

   $$\mathcal{L}\simeq ||{\mathbf{Z}}^{\mathrm{\top }}\mathbf{Z}-\mathbf{S}|{|}_2^2$$

   其中：

   • $\mathbf{S}$$ \mathbf S $ 为节点相似度矩阵，$S_{i,j}=s_{\mathcal{G}}(v_i,v_j)$$ S_{i,j} = s_{\mathcal G}(v_i,v_j) $ 。
   • $\mathbf{Z}$$ \mathbf Z $ 为节点的 embedding 矩阵。

   直观上讲，这些方法的目标是为每个节点学习 embedding，使得学到的 embedding 向量之间的内积近似于某个给定的节点相似性度量。

b. Random Walk

1. 最近一些比较成功的浅层 embedding 方法都是基于随机游走统计信息来学习节点 embedding。它们的关键创新在于：优化节点 embedding，使得随机游走序列上共现的节点具有相似的 embedding，如下图所示。

   因此，这些随机游走方法并没有像基于矩阵分解方法那样使用确定性的节点相似性度量，而是采用一种灵活的、随机的节点相似性度量，从而在很多场景下都具有出色的性能。

   基于随机游走的方法从每个节点$v_i$$ v_i $ 开始采样大量固定长度的随机游走序列，并计算从$v_i$$ v_i $ 开始的固定长度随机游走序列上访问到节点$v_j$$ v_j $ 的概率$p_{\mathcal{G}}(v_j\mid v_i),\mathrm{\forall }{v}_j\in \mathcal{V},v_j\ne v_i$$ p_\mathcal G(v_j\mid v_i), \forall v_j\in \mathcal V , v_j\ne v_i $ 。然后优化 embedding 向量，使得两个 embedding 向量${\overrightarrow{\mathbf{z}}}_i$$ \mathbf{\vec z}_i $ 和${\overrightarrow{\mathbf{z}}}_j$$ \mathbf{\vec z}_j $ 之间的点积或角度与$p_{\mathcal{G}}(v_j\mid v_i)$$ p_\mathcal G(v_j\mid v_i) $ 成正比。

   

2. DeepWalk & node2vec：与上述矩阵分解方法一样，DeepWalk 和 node2vec 依赖浅层 embedding 并使用内积式 decoder 。但是，这些方法不是对确定性的节点相似性度量进行解码，而是优化 embedding 从而对随机游走的统计信息进行编码。

   这些方法背后的基本思想是学习 embedding，使得：

   $$\text{DEC}({\overrightarrow{\mathbf{z}}}_i,{\overrightarrow{\mathbf{z}}}_j)=\frac{\exp \left({\overrightarrow{\mathbf{z}}}_i^{\mathrm{\top }}{\overrightarrow{\mathbf{z}}}_j\right)}{\sum _{v_k\in \mathcal{V}}\exp \left({\overrightarrow{\mathbf{z}}}_i^{\mathrm{\top }}{\overrightarrow{\mathbf{z}}}_k\right)}\simeq p_{\mathcal{G},T}(v_j\mid v_i)$$

   其中：$p_{\mathcal{G},T}(v_j\mid v_i)$$ p_{\mathcal G,T}(v_j\mid v_i) $ 是在以$v_i$$ v_i $ 为节点的、长度为$T$$ T $ 的随机游走序列上访问节点$v_j$$ v_j $ 的概率，通常$2\le T\le 10$$ 2\le T\le 10 $ 。

   注意：不像基于矩阵分解方法那样使用确定性的、对称的节点相似性度量（如边的强度$A_{i,j}$$ A_{i,j} $ ），这里使用的$p_{\mathcal{G},T}(v_j\mid v_i)$$ p_{\mathcal G,T}(v_j\mid v_i) $ 是随机的、非对称的。

   进一步地，DeepWalk 和 node2vec 最小化以下交叉熵损失函数：

   $$\mathcal{L}=\sum _{(v_i,v_j)\in \mathcal{D}}-\log \left(\text{DEC}({\overrightarrow{\mathbf{z}}}_i,{\overrightarrow{\mathbf{z}}}_j)\right)$$

   其中训练集$\mathcal{D}$$ \mathcal D $ 是从每个节点开始的随机游走序列中采样得到。

   由于计算$\text{DEC}({\overrightarrow{\mathbf{z}}}_i,{\overrightarrow{\mathbf{z}}}_j)$$ \text{DEC}(\mathbf{\vec z}_i, \mathbf{\vec z}_j ) $ 的分母的时间复杂度为$O(|\mathcal{V}|)$$ O(|\mathcal V|) $ ，因此计算$\mathcal{L}$$ \mathcal L $ 的时间复杂度为$O(|\mathcal{D}|\times |\mathcal{V}|)$$ O(|\mathcal D|\times |\mathcal V|) $ 太高。因此，DeepWalk 和 node2vec 使用不同的优化和近似来计算$\mathcal{L}$$ \mathcal L $ ，例如层次 Softmax 和负采样技术。

   node2vec 和 DeepWalk 之间的关键区别在于：node2vec 允许定义灵活的随机游走策略，而 DeepWalk 只能使用简单的无偏随机游走。具体而言， node2vec 引入两个随机游走超参数$p$$ p $ 和$q$$ q $ ，从而在随机游走中引入 bias 。假设随机游走当前节点为$v$$ v $ ，上一步节点为$t$$ t $ ：

   • 返回参数 Return Parameter$p$$ p $ ：参数$p$$ p $ 控制了重新访问上一步已访问节点的概率。

     • 一个较大的值$p>max(q,1)$$ p\gt \max(q,1) $ 将使得接下来访问的节点$x$$ x $ 不大可能是上一步已访问的节点$t$$ t $ （除非节点$v$$ v $ 除了$t$$ t $ 之外再也没有其它邻居）。

       这种策略鼓励适当的进行探索新结点，并避免采样过程中的冗余2-hop （即：经过两步转移又回到了结点本身）。

     • 一个较小的值$p<max(q,1)$$ p\lt \max(q,1) $ 将使得接下来访问的节点$x$$ x $ 很可能是上一步已访问的节点$t$$ t $ 。

       这种策略使得随机游走序列尽可能地留在源点$u$$ u $ 的局部区域。

   • 内外参数 In-out parameter$q$$ q $ ：参数$q$$ q $ 控制了探索的方向是向内搜索还是向外搜索。

     • 如果$q>1$$ q\gt1 $ 则$x$$ x $ 倾向于向$t$$ t $ 靠拢。这种策略将采样局限在一个很小的范围，从而获得网络的一个局部视图，类似于 BFS 的行为。
     • 如果$q<1$$ q\lt 1 $ 则$x$$ x $ 倾向于远离$t$$ t $ 。这种策略将鼓励采样向外拓展，从而获得网络的一个宏观视图，类似于 DFS 的行为。

     

   通过引入这些超参数，node2vec 可以在广度优先搜索和深度优先搜索之间折衷。实验发现：调整这些超参数可以使得模型在学习社区结构 community structure 和局部结构角色 local structrual role 之间折衷，如下图所示。下图表示从《悲惨世界》小说中得到的人物与人物互动图的两个不同的视角，如果相应的人物有互动则两个节点就会连接起来。

   • 左图：不同的颜色代表节点在图中全局位置的不同：如果节点在全局层面上属于同一个社区，那么它们的颜色就相同。
   • 右图：不同的颜色代表节点之间的结构等价性structural equivalence，或者说两个节点在其局部邻域中扮演类似的角色（例如，bridging node 为蓝色）。

   

   下图说明了 node2vec 如何通过$p$$ p $ 和$q$$ q $ 来引入有偏的随机游走。

   • 图 A：假设随机游走刚从节点$v_s$$ v_s $ 游走到节点$v_{\ast }$$ v_* $ ，$\alpha$$ \alpha $ 表示游走到下一个节点的概率。

   • 图 B：广度优先搜索 BFS 和深度优先搜索 DFS 的随机游走之间的差异。

     • 类似 BFS 的随机游走主要探索节点的 1-hop 邻域，因此在捕获局部结构角色方面更为有效。
     • 类似 DFS 的随机游走主要探索得更远，对于捕获社区结构方面更为有效。

   

3. LINE：LINE 是另一种非常成功的浅层 embedding 方法，它不是基于随机游走，而基于共现。

   LINE 经常与 DeepWalk 和 node2vec 进行比较，它结合了两个 encoder-decoder 目标，分别优化了一阶节点相似性和二阶节点相似性。

   • 一阶节点相似性为$s_{\mathcal{G}}(v_i,v_j)=A_{i,j}$$ s_{\mathcal G}(v_i,v_j) = A_{i,j} $ ，一阶 decoder 为：

     $$\text{DEC}({\overrightarrow{\mathbf{z}}}_i,{\overrightarrow{\mathbf{z}}}_j)=\frac{1}{1+\exp (-{\overrightarrow{\mathbf{z}}}_i^{\mathrm{\top }}{\overrightarrow{\mathbf{z}}}_j)}$$

   • 二阶节点相似性为$p_{\mathcal{G},T}(v_j\mid v_i)$$ p_{\mathcal G,T}(v_j\mid v_i) $ ，二阶 decoder 为：

     $$\text{DEC}({\overrightarrow{\mathbf{z}}}_i,{\overrightarrow{\mathbf{z}}}_j)=\frac{\exp \left({\overrightarrow{\mathbf{z}}}_i^{\mathrm{\top }}{\overrightarrow{\mathbf{z}}}_j\right)}{\sum _{v_k\in \mathcal{V}}\exp \left({\overrightarrow{\mathbf{z}}}_i^{\mathrm{\top }}{\overrightarrow{\mathbf{z}}}_k\right)}\simeq p_{\mathcal{G},T}(v_j\mid v_i)$$

   一阶目标和二阶目标都是基于 KL 距离的损失函数。因此， LINE 在概念上和 node2vec, DeepWalk 有关，因为LINE 使用了概率性的 decoder 和损失函数。但是，LINE 明确地分解了一阶相似度和二阶相似度，而不是采用固定长度的随机游走序列。

4. HARP：HARP （《Harp: Hierarchical representation learning for networks》）是一种元数据策略，通过图预处理步骤来改善各种随机游走方法。

   HARP 使用图粗化 coarsening 过程将$\mathcal{G}$$ \mathcal G $ 中的相关节点折叠在一起，称作 “超级节点”，然后在这个粗化图上运行 DeepWalk, node2vec, LINE 等。在得到$\mathcal{G}$$ \mathcal G $ 粗化版的 embedding 之后，每个超级节点学到的 emebdding 将作为超级节点中每个组成节点的初始 embedding，然后执行更细粒度的 embedding 学习。

   这种方式在不同粒度上以层次方式反复执行，每次都能得到更细粒度的 emebdding 。实践表明HARP 可以持续改善 DeepWalk, node2vec, LINE 等方法的性能。

3.1.3 通用 encoder-decoder

1. 目前为止我们研究过的所有节点 embedding 方法都是浅层 embedding 方法，其中 encoder 只是一个简单的 embedding lookup。这种方式有很多缺点：

   • 浅层embedding的encoder 中节点之间没有共享任何参数，即 encoder 只是基于节点 ID 的 embedding lookup。

     • 由于参数共享可以充当一种强大的正则化，因此浅层 embedding 方法的泛化能力较差。
     • 浅层 embedding 方法中参数数量为$O(|\mathcal{V}|)$$ O(|\mathcal V|) $ ，因此在计算效率、存储效率上也很低效。

   • 浅层 embedding 的 encoder 无法利用节点属性。在很多大型图中，节点有丰富的属性信息（如社交网络的用户画像），这些属性信息对于节点在图中的位置和角色具有很高的信息价值。

   • 浅层 embedding 方法本质是 transductive 的，它们只能为训练阶段存在的节点生成 embeddign，无法为从未见过的节点生成 embedding。因此无法应用到不断演变的图、需要泛化到新的图等场景。

   最近已经提出很多方法来解决这些问题。这些方法仍然使用 encoder-decoder 框架，但是和浅层 embedding 不同之处在于：它们使用更复杂的 encoder （通常基于深度神经网络），并且更依赖于图的结构和节点属性。

a. 邻域自编码器

1. Deep Neural Graph Representations: DNGR 和 Structural Deep Network Embeddings: SDNE 解决了上面的第一个问题。和浅层 embedding 方法不同，它们使用深度神经网络将图结构直接融合到 encoder 算法中。

   它们背后的基本思想是：使用自编码器来压缩有关邻域的信息（如下图所示）。另外，不同于之前的方法，DNGR, SDNE 的 decoder 只有一个节点而不是一对节点。

   在这两个方法中，令$\mathbf{S}$$ \mathbf S $ 是节点相似度矩阵，$S_{i,j}=s_{\mathcal{G}}(v_i,v_j)$$ S_{i,j} = s_{\mathcal G}(v_i,v_j) $ 。则每个节点$v_i$$ v_i $ 关联一个邻域向量${\overrightarrow{\mathbf{s}}}_i\in {\mathbb{R}}^{|\mathcal{V}|}$$ \mathbf{\vec s}_i\in \mathbb R^{|\mathcal V|} $ ，它是$\mathbf{S}$$ \mathbf S $ 中$v_i$$ v_i $ 对应的行，刻画了节点$v_i$$ v_i $ 和其它所有节点的相似性，并作为$v_i$$ v_i $ 全局邻域的高维表示。DNGR 和 SDNE 自编码器的目标是基于邻域向量${\overrightarrow{\mathbf{s}}}_i$$ \mathbf{\vec s}_i $ 来嵌入节点$v_i$$ v_i $ ，以便可以从 embedding 向量中重建${\overrightarrow{\mathbf{s}}}_i$$ \mathbf{\vec s}_i $ ：

   $$\text{DEC}\left(\text{ENC}\left({\overrightarrow{\mathbf{s}}}_i\right)\right)=\text{DEC}\left({\overrightarrow{\mathbf{z}}}_i\right)\simeq {\overrightarrow{\mathbf{s}}}_i$$

   因此这些方法的损失函数为：

   $$\mathcal{L}=\sum _{v_i\in \mathcal{V}}{\Vert \text{DEC}({\overrightarrow{\mathbf{z}}}_i)-{\overrightarrow{\mathbf{s}}}_i\Vert }_2^2$$

   和 pairwise decoder 一样，我们选择 embedding${\overrightarrow{\mathbf{z}}}_i$$ \mathbf{\vec z}_i $ 的维度远远小于$|\mathcal{V}|$$ |\mathcal V| $ （${\overrightarrow{\mathbf{s}}}_i$$ \mathbf{\vec s}_i $ 的维度），所以DNGR,SDNE 将节点的邻域信息压缩为低维向量。

   对于 SDNE,DNGR， encoder 和 decoder 函数均由多个堆叠的神经网络层组成，encoder 的每一层都降低了其输入的维度，decoder 的每一层都增加了其输入的维度。

   

2. SDNE 和 DNGR 在相似度函数（用于构造邻域向量${\overrightarrow{\mathbf{s}}}_i$$ \mathbf{\vec s}_i $ ）以及自编码器优化细节上有所不同。

   • DNGR 根据随机游走序列中两个节点共现的 pointwise mutual information:PMI 来定义${\overrightarrow{\mathbf{s}}}_i$$ \mathbf{\vec s}_i $ ，类似于 DeepWalk 和 node2vec 。

   • SDNE 简单地定义${\overrightarrow{\mathbf{s}}}_i=(A_{i,1},A_{i,2},\cdots ,A_{i,|\mathcal{V}|}{)}^{\mathrm{\top }}$$ \mathbf{\vec s}_i = (A_{i,1},A_{i,2},\cdots,A_{i,|\mathcal V|})^\top $ ，即等于节点$v_i$$ v_i $ 的邻接向量。

     SDNE 还结合了自编码器的损失函数和拉普拉斯特征图的损失函数：

     $$\mathcal{L}=\sum _{v_i\in \mathcal{V}}{\Vert \text{DEC}({\overrightarrow{\mathbf{z}}}_i)-{\overrightarrow{\mathbf{s}}}_i\Vert }_2^2+\beta (\sum _{(v_i,v_j)\in \mathcal{D}}\text{DEC}({\overrightarrow{\mathbf{z}}}_i,{\overrightarrow{\mathbf{z}}}_j)\times s_{\mathcal{G}}(v_i,v_j))$$

3. 注意：公式$\text{DEC}\left(\text{ENC}\left({\overrightarrow{\mathbf{s}}}_i\right)\right)=\text{DEC}\left({\overrightarrow{\mathbf{z}}}_i\right)\simeq {\overrightarrow{\mathbf{s}}}_i$$ \text{DEC}\left(\text{ENC}\left(\mathbf{\vec s}_i\right)\right)=\text{DEC}\left(\mathbf{\vec z}_i\right)\simeq \mathbf{\vec s}_i $ 取决于输入向量${\overrightarrow{\mathbf{s}}}_i$$ \mathbf{\vec s}_i $ ，该项包含有关$v_i$$ v_i $ 全局邻域的信息。这使得 SDNE, DNGR 可以将有关节点全局邻域的结构信息以正则化的形式直接合并到 encoder 中。

   这对于浅层 embedding 方法是不可能的，因为浅层 embedding 方法的 encoder 取决于节点 ID，而不是节点全局邻域结构。

4. 尽管SDNE, DNGR 在 encoder 中编码了有关节点全局邻域的结构信息，但是它们仍然存在一些严重的局限性。

   • 最突出的局限性是：自编码器的输入维度固定为$|\mathcal{V}|$$ |\mathcal V| $ ，对于具有数百万甚至更多节点的图，其代价非常大甚至难于处理。
   • 另外，自编码器的结构和大小也是固定的，因此 SDNE,DNGR 也是 transductive 的，无法处理不断演变的图，也无法跨图进行泛化。

b. 邻域聚合卷积 encoder

1. 最近许多节点 embedding 方法旨在通过设计依赖于局部邻域（而不是全局邻域）的 encoder 来解决浅层 embedding 方法和自编码器方法的缺陷。这些方法背后的直觉是：通过聚合来自局部邻域的信息来为节点生成 embedding ，如下图所示。

   为了生成节点 A 的 embedding，模型聚合了来自 A 的局部邻域（节点 B,C,D ）的消息。然后，这些邻域节点又基于它们各自邻域来聚合消息，依次类推。下图给出了一个迭代深度为 2 的版本，它聚合了节点 A 的 2-hop 邻域消息，原则上可以为任意深度。

   

2. 和之前讨论的方法不同，这些邻域聚合算法依赖于节点属性${\overrightarrow{\mathbf{x}}}_i\in {\mathbb{R}}^m$$ \mathbf{\vec x}_i\in \mathbb R^m $ 来生成 embedding 。在没有属性信息的情况下，也可以使用简单的图统计信息（如节点 degree）作为节点属性；或者也可以为每个节点分配一个 one-hot indicator 作为属性。

   这些邻域聚合方法通常称作卷积，因为它们将节点embedding 表示为周围邻域的函数，这和计算机视觉中的卷积算子很类似。

3. 在编码阶段，邻域聚合方法以迭代或递归的方式构建节点的 embedding 。

   • 首先，节点 embedding 初始化为节点属性向量。
   • 然后，在encoder 算法的每次迭代过程中，节点使用一种聚合算法来聚合邻域的 embedding。
   • 接着，在聚合之后每个节点被分配一个新的 embedding，它结合了邻域聚合 embedding 以及该节点上一轮迭代的 embedding。
   • 最后，这个新的 embedding 被馈入一个 dense 层从而得到本轮迭代的 embedding 。

   以上过程不断重复进行，使得节点 embedding 聚合了图中距离该节点越来越远的信息。但是 embedding 维度仍然保持不变并限制在低维，迫使 encoder 不断将越来越大范围的邻域的信息压缩到低维向量。

   经过$K$$ K $ 轮迭代之后，最终 emebdding 向量作为节点的输出 representation。

   整体算法如下所示：

   邻域聚合 encoder 算法：

   • 输入：

     • 图$\mathcal{G}(\mathcal{V},\mathcal{E})$$ \mathcal G(\mathcal V, \mathcal E) $
     • 节点特征向量集合$\{{\overrightarrow{\mathbf{x}}}_v,\mathrm{\forall }v\in \mathcal{V}\}$$ \{\mathbf{\vec x}_v,\forall v\in \mathcal V\} $
     • 深度$K$$ K $
     • 每层的权重矩阵$\{{\mathbf{W}}^{(k)},1\le k\le K\}$$ \left\{\mathbf W^{(k)},1\le k\le K\right\} $
     • 非线性激活函数$\sigma (\cdot )$$ \sigma(\cdot) $
     • 每层可微的聚合函数$\{{\text{Agg}}_k(\cdot ),1\le k\le K\}$$ \{\text{Agg}_k(\cdot), 1\le k\le K\} $
     • 邻域函数$\mathcal{N}(\cdot )$$ \mathcal N(\cdot) $

   • 输出：节点的 representation$\{{\overrightarrow{\mathbf{z}}}_v,\mathrm{\forall }v\in \mathcal{V}\}$$ \{\mathbf{\vec z}_v,\forall v\in \mathcal V\} $

   • 算法步骤：

     • 初始化：${\overrightarrow{\mathbf{h}}}_v^{(0)}={\overrightarrow{\mathbf{x}}}_v,\mathrm{\forall }v\in \mathcal{V}$$ \mathbf{\vec h}_v^{(0)} = \mathbf{\vec x}_v, \forall v\in \mathcal V $

     • 迭代，$k=1,2,\cdots ,K$$ k=1,2,\cdots,K $ ，迭代过程为：

       对于每个节点$v\in \mathcal{V}$$ v\in \mathcal V $ ，计算：

       $$\begin{array}{c}{\overrightarrow{\mathbf{h}}}_{\mathcal{N}(v)}^{(k)}\leftarrow {\text{Agg}}_k\left(\{{\overrightarrow{\mathbf{h}}}_u^{(k-1)},\mathrm{\forall }u\in \mathcal{N}(v)\}\right)\\ {\overrightarrow{\mathbf{h}}}_v^{(k)}=\sigma \left({\mathbf{W}}^{(k)}\text{COMBINE}({\overrightarrow{\mathbf{h}}}_v^{(k-1)},{\overrightarrow{\mathbf{h}}}_{\mathcal{N}(v)}^{(k)})\right)\end{array}$$

       执行归一化：${\overrightarrow{\mathbf{h}}}_v^{(k)}\leftarrow \text{NORMALIZE}\left({\overrightarrow{\mathbf{h}}}_v^{(k)}\right),\mathrm{\forall }v\in \mathcal{V}$$ \mathbf{\vec h}_v^{(k)} \leftarrow \text{NORMALIZE}\left(\mathbf{\vec h}_v^{(k)}\right),\forall v\in \mathcal V $ 。

     • 返回${\overrightarrow{\mathbf{z}}}_v\leftarrow {\overrightarrow{\mathbf{h}}}_v^{(K)},\mathrm{\forall }v\in \mathcal{V}$$ \mathbf{\vec z}_v\leftarrow \mathbf{\vec h}_v^{(K)},\forall v\in \mathcal V $ 。

4. 有很多遵循上述算法的最新方法，包括 GCN、Column Network、GraphSAGE 等。这些算法中的可训练参数包括一组权重矩阵$\{{\mathbf{W}}^{(k)},\mathrm{\forall }1\le k\le K\}$$ \left\{\mathbf W^{(k)},\forall 1\le k\le K\right\} $ ，它们指定如何从节点的局部邻域聚合信息。和浅层 embedding 方法不同，这些参数在所有节点之间共享。

   对每个节点都相同的聚合函数和权重矩阵为所有节点生成 embedding，在这个过程中仅输入节点属性和邻域结构在不同节点之间发生变化。这种参数共享提高了效率（即参数规模和图的大小无关），也提供了正则化，还允许为训练期间从未见过的节点生成 embedding （即 inductive learning ）。

5. GraphSAGE, Column Network 以及各种 GCN 方法都遵循以上算法，但是区别在于执行聚合（Agg 函数）、向量组合（COMBINE 函数）的方式不同。

   • GraphSAGE 使用向量拼接作为 COMBINE 函数，并允许使用通用聚合函数作为 Agg 函数，如均值池化、最大池化、LSTM。他们发现更复杂的聚合器，尤其是最大池化，获得了明显的收益。

   • GCN 和 Column Network 使用加权和的方式作为 COMBINE 函数，并使用均值聚合（加权或者不加权）作为 Agg 函数。

   • Column Network 使用一个额外的插值项，即在 Normalize 之前：

     $$\begin{array}{c}{\overrightarrow{\mathbf{h}}}_v^k\leftarrow \alpha {\overrightarrow{\mathbf{h}}}_v^k+(1-\alpha ){\overrightarrow{\mathbf{h}}}_v^{k-1}\\ {\overrightarrow{\mathbf{h}}}_v^{(k)}\leftarrow \text{NORMALIZE}\left({\overrightarrow{\mathbf{h}}}_v^{(k)}\right)\end{array}$$

     其中$\alpha$$ \alpha $ 是插值系数，它是通过对${\overrightarrow{\mathbf{h}}}_v^{k-1}$$ \mathbf{\vec h}_v^{k-1} $ 和${\overrightarrow{\mathbf{h}}}_{\mathcal{N}(v)}^{k-1}$$ \mathbf{\vec h}_{\mathcal N(v)}^{k-1} $ 的一个非线性函数计算得到。

     这个插值项允许模型在迭代过程中保留局部信息。由于随着$k$$ k $ 的增加模型会整合来自图中更远范围的信息，这个插值项保留更近的信息从而保留局部信息。

6. 原则上可以将 GraphSAGE, Column Network, GCN 的 encoder 和前面讨论的任何一种 decoder 以及损失函数一起使用，并使用 SGD 来优化。

   在节点分类、链接预测的 benchmark 上，实验发现这些方法相对浅层 embedding 的 encoder 提供了一致的增益。

   从 high level 上讲，这些方法解决了浅层 embedding 的四个主要限制：

   • 它们将图结构合并到 encoder 中。
   • 它们利用了节点属性信息。
   • 它们的参数规模可以为$|\mathcal{V}|$$ |\mathcal V| $ 的sub-linear ，即低于$O(|\mathcal{V}|)$$ O(|\mathcal V|) $ 。
   • 它们可以为训练期间未见过的节点生成 embedding，即 inductive learning 。

3.1.4 task-specific 监督信息

1. 目前为止 encoder-decoder 架构默认都是无监督的。即，模型在一组节点上进行优化，优化目标是重构依赖于图$\mathcal{G}$$ \mathcal G $ 的成对相似度$s_{\mathcal{G}}(v_i,v_j)$$ s_{\mathcal G}(v_i,v_j) $ 。

   但是，很多 embedding 算法（尤其是邻域聚合方法）也可以包含 task-specific 监督信息，尤其是通常会结合节点分类任务中的监督信息来学习节点 embedding 。

2. 为简单起见，我们讨论节点具有二元类别标签的情形，但是我们的讨论很容易扩展到更复杂的多类分类问题。

   假设每个节点$v_i$$ v_i $ 关联一个类别标签$y_i\in \{0,1\}$$ y_i\in \{0,1\} $ 。为了学习节点到类别标签的映射，我们可以使用一个 sigmoid 函数，函数的输入为节点 embedding ：

   $${\hat{y}}_i=\sigma \left({\overrightarrow{\mathbf{z}}}_i^{\mathrm{\top }}\overrightarrow{\theta }\right)$$

   其中$\overrightarrow{\theta }$$ \mathbf{\vec\theta} $ 为可训练的参数向量。

   然后我们计算预测标签和真实标签之间的交叉熵作为损失函数：

   $$\mathcal{L}=\sum _{v_i\in \mathcal{V}}{y}_i\log \left(\sigma (\text{ENC}(v_i{)}^{\mathrm{\top }}\overrightarrow{\theta })\right)+(1-y_i)\log (1-\sigma (\text{ENC}(v_i{)}^{\mathrm{\top }}\overrightarrow{\theta }))$$

   最后我们通过 SGD 来优化模型的参数。

   这种 task-specific 监督信息可以完全替代掉 decoder 中的重建损失，也可以和 decoder 重建损失一起使用（即同时包含监督损失和无监督损失）。

3.1.5 多模态

1. 前面讨论的都是简单的无向图，而现实世界中很多图具有复杂的多模态 multi-modal、多层级（如异质节点、异质边） 的结构。已有很多工作引入了不同的方法来处理这种异质性。

2. 很多图包含不同类型的节点和边。如，推荐系统中包含两种类型的节点：用户节点、item 节点。解决该问题的通用策略是：

   • 对不同类型的节点使用不同的 encoder 。

   • 使用 type-specific 参数扩展 pairwise decoder 。例如，在具有不同类型边的图中，可以将标准的内积式 edge decoder （即${\overrightarrow{\mathbf{z}}}_i^{\mathrm{\top }}{\overrightarrow{\mathbf{z}}}_j\simeq A_{i,j}$$ \mathbf{\vec z}_i^\top \mathbf{\vec z}_j \simeq A_{i,j} $ ） 替换为一个双线性 bilinear 形式：

     $${\text{DEC}}_{\tau }({\overrightarrow{\mathbf{z}}}_i,{\overrightarrow{\mathbf{z}}}_j)={\overrightarrow{\mathbf{z}}}_i^{\mathrm{\top }}{\mathbf{W}}_{\tau }{\overrightarrow{\mathbf{z}}}_j$$

     其中$\tau$$ \tau $ 表示边的类型，${\mathbf{W}}_{\tau }$$ \mathbf W_\tau $ 表示针对边类型为$\tau$$ \tau $ 的可学习的参数矩阵。

     ${\mathbf{W}}_{\tau }$$ \mathbf W_{\tau} $ 可以通过各种方式进行正则化，如约束它为对角矩阵。当存在大量的边类型时（如在知识图谱中），这种方式特别有用。

   • 最近人们提出了一种从异质图中采样随机游走序列的策略，其中随机游走仅限于特定类型节点之间。这种方法允许我们将基于随机游走的浅层 embedding 方法应用于异质图。

3. 某些场景下图有很多层，其中不同层包含相同的节点，即多层图 multi-layer graph 。注意，这里不是神经网络的层数，而是图数据的层数。此时跨层的信息共享是有益的，因为节点在其中一层的 embedding 可以接收节点在其他层的 embedding 信息。

   OhmNet 结合了带正则化项的 node2vec 从而跨层绑定 embedding。具体而言，假设节点$v_i$$ v_i $ 同时属于层${\mathcal{G}}_1,{\mathcal{G}}_2$$ \mathcal G_1, \mathcal G_2 $ ，我们可以可以改进标准的损失函数为：

   $$\mathcal{L}(v_i{)}^{\prime }=\mathcal{L}(v_i)+\lambda {\Vert {\overrightarrow{\mathbf{z}}}_i^{{\mathcal{G}}_1}-{\overrightarrow{\mathbf{z}}}_i^{{\mathcal{G}}_2}\Vert }_2^2$$

   其中：

   • $\mathcal{L}$$ \mathcal L $ 表示节点的常规损失函数。
   • $\lambda$$ \lambda $ 为正则化系数，${\overrightarrow{\mathbf{z}}}_i^{{\mathcal{G}}_1},{\overrightarrow{\mathbf{z}}}_i^{{\mathcal{G}}_2}$$ \mathbf{\vec z}_i^{\mathcal G_1},\mathbf{\vec z}_i^{\mathcal G_2} $ 表示节点$v_i$$ v_i $ 在不同层的 embedding 。

   OhmNt 通过使用 hierarchy 来扩展这个思想，从而可以学习不同graph layer 上的 embedding，而正则化项可以在 graph layer 的 parent-child 关系之间依次使用。

   如下图所示：

   • A：一个包含四层的图，其中相同节点出现在不同的层。这种多层结构可以通过正则化来学习，使得相同节点在不同层之间的 emebdding 彼此相似。

   • B：通过层次结构来展示多层图，其中 non-root 层包含所有子层的所有节点和所有边。

     这种结构可以学习不同层级结构的 embedding，并在 parent-child 层级关系之间应用正则化，使得相同节点在 parent 和 child 层级之间的 embedding 相似。

   • C-E ：大脑组织中不同的 “蛋白质-蛋白质”作用图protein-protein interaction graph 对应的multi-layer graph embedding 。embedding 是通过 OhmNet 方法得到并通过 t-SNE 可视化。

     • C：不同组织区域中的层级结构。
     • D：脑干brainstem 层得到的蛋白质 embedding 的可视化。
     • E：全脑whole-brain 层得到的蛋白质 embedding 的可视化。

   

3.1.6 结构角色

1. 目前为止我们研究的所有方法都优化节点 embedding，使得图中距离相近的节点具有相似的 embedding。但是在很多任务中，更重要的是学习和节点结构角色structural roles 相对应的表示形式，而与它们在图中的全局位置无关。

   • node2vec 为这个问题提供了一种解决方案，它采用有偏的随机游走从而更好地捕获结构角色。
   • 近期 struc2vec 和 graphwave 提出了专门用于捕获结构角色的节点 embedding 方法。

2. struc2vec 涉及一系列从原始图$\mathcal{G}$$ \mathcal G $ 生成的加权辅助图$\{{\mathcal{G}}_k^{\prime }{\}}_{k=1,2,\cdots }$$ \{\mathcal G_k^\prime\}_{k=1,2,\cdots} $ ，其中辅助图${\mathcal{G}}_k^{\prime }$$ \mathcal G_k^\prime $ 捕获了节点和 k-hop 邻居之间的结构相似性。

   具体而言，令${\mathcal{D}}_k(i)$$ \mathcal D_k(i) $ 表示和$v_i$$ v_i $ 距离刚好为 k-hop 的节点集合，$R_k(v_i)$$ R_k(v_i) $ 表示${\mathcal{D}}_k(i)$$ \mathcal D_k(i) $ 中节点 degree 的有序序列。在辅助图${\mathcal{G}}_k^{\prime }$$ \mathcal G_k^\prime $ 中，边的权重$w_k(v_i,v_j)$$ w_k(v_i,v_j) $ 递归地定义为：

   $$w_k(v_i,v_j)=w_{k-1}(v_i,v_j)+d(R_k(v_i),R_k(v_j))$$

   其中：

   • $w_0(v_i,v_j)=0$$ w_0(v_i,v_j) = 0 $ 。

   • $d(R_k(v_i),R_k(v_j))$$ d(R_k(v_i),R_k(v_j)) $ 刻画了有序 degree 序列$R_k(v_i),R_k(v_j)$$ R_k(v_i),R_k(v_j) $ 之间的距离，例如通过 dynamic time wariping:DTW 来计算这两个序列之间的距离。

     通过$R_k(v_i)$$ R_k(v_i) $ 来刻画节点$v_i$$ v_i $ 的$k$$ k $ 阶邻域，通过$d(\cdot ,\cdot )$$ d(\cdot,\cdot) $ 来计算节点$v_i$$ v_i $ 和节点$v_j$$ v_j $ 之间$k$$ k $ 阶邻域的差异。$w_k(v_i,v_j)$$ w_k(v_i,v_j) $ 越小则说明节点$v_i$$ v_i $ 和$v_j$$ v_j $ 之间越相似。

   在计算得到这些加权辅助图之后，struc2vec 对它们执行有偏的随机游走，并将这些随机游走作为 node2vec 优化算法的输入。

3. graphwave 采用另一种非常不同的方法来捕获结构角色，它依赖于谱图小波 spectral graph wavelet 以及 heat kernel 技术。

   简而言之，令$\mathbf{L}=\mathbf{D}-\mathbf{A}$$ \mathbf L = \mathbf D - \mathbf A $ 为图拉普拉斯矩阵，$\mathbf{D}$$ \mathbf D $ 为图的 degree 矩阵，$\mathbf{A}$$ \mathbf A $ 为图的邻接矩阵。令$\mathbf{U}$$ \mathbf U $ 为$\mathbf{L}$$ \mathbf L $ 的特征向量eigenvector组成的矩阵 eigenvector matrix，对应的特征值eigenvalues 为$\{{\lambda }_1,\cdots ,{\lambda }_{|\mathcal{V}|}\}$$ \{\lambda_1,\cdots,\lambda_{|\mathcal V|}\} $ 。

   定义 heat kernel 为$g(\lambda )=\exp (-s\lambda )$$ g(\lambda) = \exp(-s\lambda) $ ，其中$s$$ s $ 为预定义的 scale 超参数。

   对于每个节点$v_i$$ v_i $ ，graphwave 使用$\mathbf{U}$$ \mathbf U $ 和$g(\lambda )$$ g(\lambda) $ 计算一个向量${\overrightarrow{\psi }}_{v_i}$$ \vec\psi_{v_i} $ 来代表节点$v_i$$ v_i $ 的结构角色：

   $${\overrightarrow{\psi }}_{v_i}=\mathbf{U}\mathbf{G}{\mathbf{U}}^{\mathrm{\top }}{\overrightarrow{\mathbf{v}}}_i$$

   其中：

   • $\mathbf{G}=\text{diag}(g({\lambda }_1),\cdots ,g({\lambda }_{|\mathcal{V}|}))$$ \mathbf G = \text{diag}\left(g(\lambda_1),\cdots,g(\lambda_{|\mathcal V|})\right) $ 为$g(\lambda )$$ g(\lambda) $ 组成的对角矩阵。
   • ${\overrightarrow{\mathbf{v}}}_i$$ \mathbf{\vec v}_i $ 为 one-hot indicator 向量，表示$v_i$$ v_i $ 对应于拉普拉斯矩阵$\mathbf{L}$$ \mathbf L $ 中的哪一行。

   graphwave 表明这些${\overrightarrow{\psi }}_{v_i}$$ \vec \psi_{v_i} $ 隐式地和拓扑统计量相关，如$v_i$$ v_i $ 的 degree 。选择一个合适的 scale$s$$ s $ ，graphwave 能够有效地捕获有关图中节点角色的结构信息。

   graphwave 的一个典型示例如下图所示：

   • A：一个人工合成的杠铃图，其中节点根据其结构角色着色。

   • B-D ：杠铃图上不同结构角色检测算法输出的节点emedding ，通过 PCA 降维来可视化。

     • B：RoIX 算法，它采用人工设计的特征，是 baseline 方法。
     • C：struc2vec 算法。
     • D：graphwave 算法。

     所有方法都可以正确区分杠铃末端和杠铃其它部分，只有 graphwave 方法能够正确区分所有结构角色。

     另外，D 的节点看起来比 A 中原始图节点少得多，因为 graphwave 将颜色相同（即结构角色相同）的节点映射到 embedding 空间中几乎相同的位置。

   

3.1.7 应用

1. 节点 embedding 最常见的应用是可视化 visualization、聚类 clustering、节点分类 node classification、链接预测 link prediction。

   • 可视化和模式挖掘：节点 embedding 为可视化提供了强大的新的范式paradigm。因为节点被映射到实值向量，因此研究人员可以轻松地利用现有的通用技术对高维数据集进行可视化。

     例如，可以将节点 embedding 和 t-SNE, PCA 之类的通用技术结合，从而得到图的二维可视化。这对于发现社区以及其它隐藏结构非常有用。

   • 聚类和社区检测：和可视化类似，节点 embedding 也是对相关节点进行聚类的强大工具。同样地，由于每个节点都和实值向量相关联，因此可以将通用聚类算法应用到节点embedding 上，如k-means, DB-scan 等。

     这为传统的社区检测技术提供了开放的、更强大的替代方案，并且还开辟了新的天地，因为节点 embedding 不仅可以捕获社区结构，还可以捕获不同节点扮演的结构角色。

   • 节点分类和半监督学习：节点分类可能是评估节点 embedding 的最常见 baseline 任务。大多数情况下，节点分类任务是半监督学习的一种形式，其中仅一小部分节点的标签可用，目标是仅基于这一小部分标记节点来标记整个图。

   • 链接预测：节点 embedding 作为链接预测的特征也非常有用，其目标是预测缺失的边或将来可能形成的边。

     链接预测是推荐系统的核心，其中节点 embedding 反映了节点之间的深度交互。典型的场景包括预测社交网络中缺失的好友链接，电影推荐中预测用户和电影之间的亲和力 affinity 。

3.2 子图 embedding

1. 现在我们考虑子图或者全图的 embedding，其目标是将子图或者整个图编码为低维 embedding 。

   正式地讲，我们需要学习一个诱导子图induced subgraph${\mathcal{G}}_{\mathcal{S}}$$ \mathcal G_{\mathcal S} $ 的向量表示${\overrightarrow{\mathbf{z}}}_{\mathcal{S}}\in {\mathbb{R}}^d$$ \mathbf{\vec z}_{\mathcal S}\in \mathbb R^d $ ，其中$\mathcal{S}\subseteq \mathcal{V}$$ \mathcal S \sube \mathcal V $ 。如果$\mathcal{S}=\mathcal{V}$$ \mathcal S = \mathcal V $ ，则为整个图的 embedding 。然后${\overrightarrow{\mathbf{z}}}_{\mathcal{S}}$$ \mathbf{\vec z}_{\mathcal S} $ 可以用于预测子图或整个图的标签，如预测化合物分子的某些属性。

2. 子图的 representation learning 和graph kernel 密切相关。graph kernel 定义了子图之间的距离度量，但是这里我们不会对 graph kernel 进行仔细讨论，因为这是一个庞大、丰富的研究领域。我们讨论的方法和传统的 graph kernel 不同，我们寻求从数据中学习有用的 representation，而不是通过 graph kernel 函数得到预先指定的feature representation。

   有很多方法都是基于前面介绍的单个节点 embedding 的技术。但是，和节点 embedding 不同，大多数子图 emebdding 方法都是基于完全监督的 fully-supervised 。因此，这里我们假设子图 embedding 都是采用交叉熵损失函数。

3.2.1 sets of node embedding

1. 有几种子图 emebdding 技术可以看作是基于卷积的节点 embedding 算法的直接扩展。这些方法背后的基本直觉是：它们将子图等价于节点 embedding 的集合。它们使用卷积的邻域聚合思想为节点生成 embedding，然后使用额外的模块来聚合子图对应的节点 embedding 集合。

   这里不同方法之间的主要区别在于：如何聚合子图对应的节点 embedding 集合。

2. sum-based 方法：

   • 《convolutional molecular fingerprints》 通过对子图中所有节点 embedding 进行求和，从而得到子图的 embedding ：

     $${\overrightarrow{\mathbf{z}}}_{\mathcal{S}}=\sum _{v_i\in \mathcal{S}}{\overrightarrow{\mathbf{z}}}_i$$

     其中$\{{\overrightarrow{\mathbf{z}}}_i,v_i\in \mathcal{S}\}$$ \{\mathbf{\vec z}_i,v_i\in \mathcal S\} $ 是通过邻域聚合卷积 encoder 算法的变体来生成的。

   • 《Discriminative embeddings of latent variable models for structured data》 采用类似于 sum-based 方法，但是概念上它和 mean-field inference 相关：如果图中的节点视为潜在变量，则邻域聚合卷积 encoder 算法可以视为一种 mean-field inference 的形式，其中消息传递操作被可微的神经网络替代。因此，该论文提出了基于 Loopy Belief Propagation 的 encoder，基本思想是为每条边$(i,j)\in \mathcal{E}$$ (i,j)\in \mathcal E $ 构建一个临时的embedding${\overrightarrow{\eta }}_{i,j}$$ \vec\eta_{i,j} $ ：

     $${\overrightarrow{\eta }}_{i,j}^{(k)}=\sigma \left({\mathbf{W}}_{\mathcal{E}}^{(k)}\text{COMBINE}({\overrightarrow{\mathbf{x}}}_i,\text{AGG}({\overrightarrow{\eta }}_{l,i}^{(k-1)},\mathrm{\forall }{v}_l\in \mathcal{N}(v_i),v_l\ne v_j))\right)$$

     然后根据这些临时 embedding 聚合得到节点 embedding ：

     $${\overrightarrow{\mathbf{z}}}_i=\sigma \left({\mathbf{W}}_{\mathcal{V}}^{(k)}\text{COMBIME}({\overrightarrow{\mathbf{x}}}_i,\text{AGG}({\overrightarrow{\eta }}_{i,l}^{(k)},\mathrm{\forall }{v}_l\in \mathcal{N}(v_i)))\right)$$

     一旦得到节点 embedding，论文使用子图中所有节点 embedding 的简单求和从而得到子图的 embedding 。

3. graph-coarsening 方法： 《Spectral networks and locally connected networks on graphs》 也采用了卷积方法，但是它并未对子图的节点 embedding 求和，而是堆叠了卷积层以及图粗化 graph coarsening 层（类似于 HARP 方法）。

   在图粗化层中，节点被聚类在一起（可以使用任何图聚类算法），并且聚类之后使用一个簇节点来代表簇内所有节点。这个簇节点的 embedding 为簇内所有节点 embedding 的最大池化。然后，新的、更粗粒度的图再次通过卷积 encoder，并不断重复该过程。

3.2.2 GNN 方法

1. 从概念上讲，GNN 和邻域聚合卷积 encoder 算法密切相关。但是GNN 的直觉是：将图视为节点之间消息传递的框架，而不是从邻域那里收集信息。

2. 在原始 GNN 框架中，每个节点以一个随机的 embedding${\overrightarrow{\mathbf{h}}}_i^{(0)}$$ \mathbf{\vec h}_i^{(0)} $ 进行初始化。然后在 GNN 算法每轮迭代过程中，节点根据其邻域消息更新 embedding 为：

   $${\overrightarrow{\mathbf{h}}}_i^{(k)}=\sum _{v_j\in \mathcal{N}(v_i)}f({\overrightarrow{\mathbf{h}}}_j^{(k-1)},{\overrightarrow{\mathbf{x}}}_i,{\overrightarrow{\mathbf{x}}}_j)$$

   其中：$f(\cdot )$$ f(\cdot) $ 是任意一个可微函数$f:{\mathbb{R}}^d\times {\mathbb{R}}^m\times {\mathbb{R}}^m\to {\mathbb{R}}^d$$ f:\mathbb R^d\times \mathbb R^m\times \mathbb R^m\rightarrow \mathbb R^d $ ，$m$$ m $ 为特征向量维度，$d$$ d $ 为 embedding 向量维度。

   上述公式以递归的方式重复迭代直到 embedding 收敛为止，其中必须确保$f(\cdot )$$ f(\cdot) $ 是收敛映射。

   一旦经过$K$$ K $ 次迭代收敛，最终输出 embedding 为${\overrightarrow{\mathbf{z}}}_i=g\left({\overrightarrow{\mathbf{h}}}_i^{(K)}\right)$$ \mathbf{\vec z}_i = g\left(\mathbf{\vec h}_i^{(K)}\right) $ ，其中$g(\cdot )$$ g(\cdot) $ 为任意一个可微函数$g:{\mathbb{R}}^d\to {\mathbb{R}}^d$$ g:\mathbb R^d\rightarrow \mathbb R^d $ 。

3. 《Gated Graph Sequence Neural Networks》 使用 GRU 扩展和修改了 GNN 框架，它使用节点属性来初始化${\overrightarrow{\mathbf{h}}}_i^{(0)}$$ \mathbf{\vec h}_i^{(0)} $ ，并更新${\overrightarrow{\mathbf{h}}}_i^{(k)}$$ \mathbf{\vec h}_i^{(k)} $ 为：

   $${\overrightarrow{\mathbf{h}}}_i^{(k)}=\text{GRU}({\overrightarrow{\mathbf{h}}}_i^{(k-1)},\sum _{v_j\in \mathcal{N}(v_i)}\mathbf{W}{\overrightarrow{\mathbf{h}}}_j^{(k-1)})$$

   其中$\mathbf{W}\in {\mathbb{R}}^{d\times d}$$ \mathbf W\in \mathbb R^{d\times d} $ 为一个可训练的权重矩阵。

4. 《Neural Message Passing for Quantum Chemistry》 考虑 GNN 的另一种迭代方式：

   $${\overrightarrow{\mathbf{h}}}_i^{(k)}=U({\overrightarrow{\mathbf{h}}}_i^{(k-1)},\sum _{v_j\in \mathcal{N}(v_i)}q({\overrightarrow{\mathbf{h}}}_i^{(k-1)},{\overrightarrow{\mathbf{h}}}_j^{(k-1)}))$$

   其中：

   • $q:{\mathbb{R}}^d\times {\mathbb{R}}^d\to {\mathbb{R}}^{d^{\prime }}$$ q:\mathbb R^d\times \mathbb R^d\rightarrow \mathbb R^{d^\prime} $ 为一个可微函数，用于计算从邻域传入的消息。
   • $U:{\mathbb{R}}^d\times {\mathbb{R}}^{d^{\prime }}\to {\mathbb{R}}^d$$ U:\mathbb R^d\times \mathbb R^{d^\prime}\rightarrow \mathbb R^d $ 是一个可微的更新函数。

   这个称为消息传递神经网络 Message Passing Neural Networks:MPNNs，它可以概括很多图神经网络方法。

5. 所有这些图神经网络方法原则上可以用于 node-level 的 embedding，尽管它们更经常用于 subgraph-level 的 embedding 。

   为了计算子图embedding，可以采用任何聚合过程。也可以引入一个“虚拟”的超级节点来完成聚合，该超级节点连接到目标子图中的所有节点。

3.2.3 应用

1. 子图 embedding 主要用于子图分类。例如对不同分子对应的图的属性进行分类，包括分子药物的治疗效果、分子材料的功能等。也可以将子图 embedding 用于图像分类（将图像转换为 graph 之后）、预测计算机程序是否满足某种形式的属性、以及执行逻辑推理任务。

3.3 未来方向

1. 目前graph representation领域还有很多悬而未决的问题：

   • 可扩展性scalability：尽管大多数方法理论上都有很高的可扩展性（时间复杂度$O(|\mathcal{E}|)$$ O(|\mathcal E|) $ ），但是如果需要应用到超大规模数据集（例如数十亿节点和边），仍有大量工作要做。例如，大多数方法依赖于对每个节点训练和存储一个 embedding，并且假设用于训练和测试的所有节点的属性、embedding、以及 edge list 都可以放在内存中，这在现实中与实际情况不符。

   • 解码高阶主题 motifs：近年来很多工作都致力于改善生成节点 embedding 的 encoder，但是 decoder 还是最基础的 pairwise decoder。这种 decoder 可以预测节点之间的成对关系，并忽略涉及两个以上节点的高阶图结构。

     众所周知，高阶结构主题对于复杂网络的结构和功能是必不可少的，设计能够解码复杂主题的 decoder 算法是未来工作的重要方向。

   • 动态图：很多领域都涉及高度动态的图，但是目前我们缺乏建模动态图 embedding 的方法。

   • 大量候选子图的 inference：当前子图 embedding 方法的主要技术限制在于它们要求在学习过程之前预先指定目标子图。我们需要改善子图 embedding 方法，使得该方法能够有效地自动推断大量的候选子图，无需人工指定。

   • 可解释性：representation learning 缓解了人工设计特征的负担，但是代价是可解释性较差。除了可视化和 benchmark 评估之外，还必须开发新技术以提高学到的 embedding 的可解释性。我们需要确保这些 embedding 方法真正学到图相关的信息，而不仅仅是利用 benchmark 的一些统计趋势。