Question

1. 传统的图分析任务经常受到计算复杂度、空间复杂度的困扰，而一种新的、称之为 graph embedding:GE 的范式为解决这类问题提供了一条有效途径。具体而言，GE 将图数据转换为低维空间，从而可以最大程度地保留图的拓扑结构和内容信息。之后，生成的 embedding 将作为特征输入到下游机器学习任务中。

   此外，通过结合深度学习技术，人们提出了 图神经网络 Graph Neural Network:GNN 。CNN 使用共享权重以及多层架构来提升模型的学习能力。图是典型的局部链接结构，共享权重可以显著降低计算代价，而多层架构是捕获各种尺寸特征的同时处理层次模式hierarchical pattern 的关键。因此，GNN 是 CNN 在图上的推广。

   目前已有很多 GE 和 GNN 算法，但是它们主要集中在简单的图数据上。现实世界商业场景相关的绝大多数图数据具有四个属性：大规模large-scale、异质性heterogeneous、带属性attributed、动态性dynamic 。例如，当今的电商网络通常包含数十亿个具有各种类型和丰富属性的节点、边，并且随着时间的推移而迅速演变。

   这些特性带来了巨大挑战：

   • 如何提高大规模图上 GNN 的时间和空间效率？
   • 如何优雅地将异质信息整合为统一的 embedding 结果？
   • 如何统一定义要保留的拓扑结构信息和属性信息（它们位于不同的空间）？
   • 如何在动态图上设计有效的增量 GNN 方法？

   为应对上述挑战，已有大量的工作来设计效率高、效果好的 GNN 方法。下表给出了流行的 GE 和 GNN 模型的分类，其中包括阿里巴巴内部开发的模型（黄色阴影表示）。如图所示，大多数现有方法同时集中于一个或者两个特点。但是现实世界中的商业数据通常面临更多挑战。为了缓解这种情况，阿里巴巴的一篇论文《AliGraph: A Comprehensive Graph Neural Network Platform》提出了一种针对 GNN 的全面而系统的解决方案。论文设计并实现了一个叫做 AliGraph 的平台，该平台提供了系统和算法来解决实际的问题（即前面提出的四个问题）从而很好地支持了各种 GNN 方法和应用。

   

2. AliGraph 的主要贡献：

   • 系统：在 AliGraph 的基础组件中，我们构建了一个支持 GNN 算法和应用application 的系统。该系统架构是从通用 GNN 方法抽象而来的，由存储层 storage layer、采样层sampling layer、算子层 operator layer 组成。

     具体而言：

     • 存储层应用了三种新的技术来存储大规模的原始数据，从而满足 high-level 操作和算法对数据的快速访问要求。这三种技术为：结构化structural 和属性特定attributed specific 的存储、图分区、缓存某些重要节点的邻居。
     • 采样层优化了 GNN 方法中的关键采样操作。我们将采样方法分为遍历 TRAVERSE 、邻居NEIGHBORHOOD、负采样NEGATIVE 三种采样，并提出了无锁方法在分布式环境中执行采样操作。
     • 算子层在 GNN 算法中提供了两个常用的算子的优化实现，即 AGGREGATE、COMBINE 。

     我们使用一种缓存策略来存储一些中间结果以加快计算过程。这些组件经过共同设计和共同优化，从而使得整个系统有效且可扩展。

   • 算法：该系统提供了灵活的接口来设计 GNN 算法。我们表明：所有现有的GNN 方法都可以在我们的系统上轻松实现。

     此外，我们还针对实际需求内部开发了几种新的 GNN，并在这里详细介绍了其中的六种（上表中的黄色阴影表示的），每种方法在处理实际问题时都更加灵活实用。

   • 评估：我们的 AliGraph 平台实际上已经部署在阿里巴巴公司中，从而支持各种业务场景，包括阿里巴巴电商平台的商品推荐、个性化搜索。

     通过对具有 4.92 亿节点、68.2 亿条边以及丰富属性的真实世界数据集进行广泛的实验，AliGraph 在图构建方面的执行速度提高了一个量级（5 分钟 vs SOTA 的 PowerGraph 平台的数小时）。

     在训练方面，AliGraph 使用新颖的缓存策略可以将运行速度提高 40%~50%，并通过改进的 runtime 达到大约 12 倍的加速比。

     我们在 AliGraph 平台上内部开发的 GNN 模型将归一化的评估指标提升了 4.12% ~ 17.19%（如下图所示）。这些数据是从阿里巴巴电商平台淘宝收集而言，我们将数据集贡献给社区从而促进社区进一步的发展。

     因此实验结果从系统和算法两个层面都验证了 AliGraph 的效率和效果。

     

3. 相关工作：

   • 同质图 homogeneous graph：

     • DeepWalk 首先通过随机行走在图上生成一个语料库，然后在语料库上训练一个 skip-gram 模型。
     • LINE通过同时保留一阶邻近性和二阶接近性来学习 node presentation。
     • NetMF 是一个统一的矩阵分解框架 unified matrix factorization framework ，用于从理论上理解和改进 DeepWalk和 LINE。
     • Node2Vec 增加了两个超参数来控制随机游走过程。
     • SDNE提出了一种结构保留的emebdding 方法。
     • GCN 使用卷积运算来融合了邻居的 feature representation。
     • GraphSAGE 提供了一种归纳式方法 inductive approach ，将结构信息与节点特征相结合。

   • 异质图 heterogeneous graph：

     • 对于具有多种类型节点和/或边的图，PMNE 提出了三种方法将 multiplex network 投影到连续向量空间。
     • MVE 使用注意力机制将具有多个视图的网络嵌入到一个 collaborated embedding 中。
     • MNE 为每个节点使用一个 common embedding 和几个附加 embedding （每个边类型对应一个附加的 emebdding ），这些embedding 是由一个统一的 network embedding 模型共同学习的。
     • Mvn2Vec通过同时建模 preservation 和 collaboration 来探索 embedding result。
     • HNE 联合考虑内容和拓扑结构是 unified vector representation 。
     • PTE 从标签信息中构建大规模异质文本网络，然后将其嵌入到低维空间。
     • Metapath2Vec 和 HERec 形式化了 meta-path based 的随机行走从而构建节点的异质邻域，然后利用 skip-gram 模型来进行 node embedding 。

   • 属性图attributed graph：attributed network embedding的目的是寻求低维vector representation 从而同时保留拓扑和属性信息。

     • TADW通过矩阵分解将节点的文本特征纳入 network representation learning。
     • LANE 顺利地将标签信息纳入attributed network embedding ，同时保留了它们的相关性。
     • AANE 使联合学习过程以分布式方式完成，以加速 attributed network embedding 。
     • SNE提出了一个通用框架，通过捕获结构邻近性和属性邻近性来嵌入社交网络。
     • DANE 可以捕获高非线性，并同时保留拓扑结构和节点属性的各种邻近性。
     • ANRL 使用邻域增强自编码器对节点属性信息进行建模，并使用skip-gram 模型来捕获网络结构。

   • 动态图 dynamic graph：

     • 实际上，一些静态方法也可以基于static embedding 来更新 new node 从而处理动态网络。
     • 考虑到新节点对原始网络的影响，《Dynamic network embedding: An extended approach for skip-gram based network embedding》扩展了 skip-gram 方法来更新原始节点的 embedding 。
     • 《Dynamic network embedding by modeling triadic closure process》专注于捕获 triadic structure property 从而用于学习 network embedding 。
     • 同时考虑到网络结构和节点属性，《Attributed network embedding for learning in a dynamic environment》 侧重于更新 streaming network 的top 特征向量 eigen-vector 和特征值 eigen-value。

7.1 基本概念

1. 给定图$\mathcal{G}=(\mathcal{V},\mathcal{E},\mathbf{A})$$ \mathcal G=(\mathcal V,\mathcal E, \mathbf A) $ ，其中$\mathcal{V}$$ \mathcal V $ 为所有节点的集合，$\mathcal{E}$$ \mathcal E $ 为所有边的集合，$\mathbf{A}$$ \mathbf A $ 为邻接矩阵。如果节点$u,v$$ u,v $ 之间存在连接，则$A_{u,v}>0$$ A_{u,v} \gt0 $ 表示连接的权重；否则$A_{u,v}=0$$ A_{u,v} = 0 $ 。注意，这里$\mathcal{G}$$ \mathcal G $ 可以为有向图也可以为无向图。如果是有向图，那么$A_{u,v}\ne A_{v,u}$$ A_{u,v}\ne A_{v,u} $ ；如果是无向图，那么有$A_{u,v}=A_{v,u}$$ A_{u,v} = A_{v,u} $ 。

   对于每个节点$u$$ u $ ，定义其邻居集合为${\mathcal{N}}_u$$ \mathcal N_u $ 。对于有向图，进一步地我们将入边in-edge 邻居集合记作${\mathcal{N}}_u^{+}$$ \mathcal N_u^+ $ 、出边out-edge邻居集合记作${\mathcal{N}}_u^{-}$$ \mathcal N_u^- $ 。

   令$n=|\mathcal{V}|$$ n=|\mathcal V| $ 为所有节点的数量，$m=|\mathcal{E}|$$ m=|\mathcal E| $ 为所有边的数量。

2. 为全面描述现实世界中的商业数据，实际的图中通常包含丰富的内容信息，例如多种类型的节点、多种类型的边、节点属性、边属性等。因此我们定义了属性异质图Attributed Heterogeneous Graph:AHG$\mathcal{G}=(\mathcal{V},\mathcal{E},\mathbf{A},{\mathcal{T}}_{\mathcal{V}},{\mathcal{T}}_{\mathcal{E}},{\mathcal{A}}_{\mathcal{V}},{\mathcal{A}}_{\mathcal{E}})$$ \mathcal G = (\mathcal V,\mathcal E, \mathbf A, \mathcal T_\mathcal V,\mathcal T_\mathcal E, \mathcal A_\mathcal V, \mathcal A_\mathcal E) $ ，其中：

   • $\mathcal{V}$$ \mathcal V $ 为节点集合，$\mathcal{E}$$ \mathcal E $ 为边集合，$\mathbf{A}$$ \mathbf A $ 为节点的邻接矩阵。

   • ${\mathcal{T}}_{\mathcal{V}}:\mathcal{V}\to {\mathcal{F}}_{\mathcal{V}}$$ \mathcal T_\mathcal V: \mathcal V\rightarrow \mathcal F_\mathcal V $ 为节点的类型映射函数，${\mathcal{T}}_{\mathcal{E}}:\mathcal{E}\to {\mathcal{F}}_{\mathcal{E}}$$ \mathcal T_\mathcal E:\mathcal E\rightarrow \mathcal F_\mathcal E $ 为边的类型映射函数。其中${\mathcal{F}}_{\mathcal{V}}$$ \mathcal F_\mathcal V $ 为节点类型集合，${\mathcal{F}}_{\mathcal{E}}$$ \mathcal F_\mathcal E $ 为边类型集合。

     为了确保异质性，我们要求$|{\mathcal{F}}_{\mathcal{V}}|\ge 2$$ |\mathcal F_\mathcal V|\ge 2 $ 或/和$|{\mathcal{F}}_{\mathcal{E}}|\ge 2$$ |\mathcal F_\mathcal E| \ge 2 $ 。

   • ${\mathcal{A}}_{\mathcal{V}}$$ \mathcal A_ \mathcal V $ 为节点属性的映射函数，它将每个节点映射到节点属性向量（可能有多个向量组成）；${\mathcal{A}}_{\mathcal{E}}$$ \mathcal A_\mathcal E $ 为边属性的映射函数，它将每条边映射到边属性向量（可能有多个向量组成）。

     对于节点$v\in \mathcal{V}$$ v\in \mathcal V $ ，我们假设它的第$i$$ i $ 个属性向量为${\overrightarrow{\mathbf{x}}}_{v,i}$$ \mathbf{\vec x}_{v,i} $ ；对于边$e\in \mathcal{E}$$ e\in \mathcal E $ ，我们假设它的第$i$$ i $ 个属性向量为${\overrightarrow{\mathbf{w}}}_{e,i}$$ \mathbf{\vec w}_{e,i} $ 。

   一个典型的属性异质图如下图所示，其中包含两种类型的节点（user 节点和 item 节点）、四种类型的边。

   

3. 现实世界的图通常随时间动态演化。给定一个时间区间 [1, T]，动态图Dynamic Graph是一个图序列$\{{\mathcal{G}}^{(1)},{\mathcal{G}}^{(2)},\cdots ,{\mathcal{G}}^{(T)}\}$$ \left\{\mathcal G^{(1)},\mathcal G^{(2)},\cdots,\mathcal G^{(T)}\right\} $ 。 对于每个$1\le t\le T$$ 1\le t\le T $ ，${\mathcal{G}}^{(t)}$$ \mathcal G^{(t)} $ 为一个简单的图或者一个属性异质图。

   为了便于说明，我们采用上标$(t)$$ (t) $ 表示对象在时刻$t$$ t $ 的状态。如${\mathcal{V}}^{(t)}$$ \mathcal V^{(t)} $ 为时刻$t$$ t $ 的图${\mathcal{G}}^{(t)}$$ \mathcal G^{(t)} $ 的节点集合、${\mathcal{E}}^{(t)}$$ \mathcal E^{(t)} $ 为时刻$t$$ t $ 的图${\mathcal{G}}^{(t)}$$ \mathcal G^{(t)} $ 的边集合。

4. 给定输入图$\mathcal{G}$$ \mathcal G $ （它是简单图或属性异质图），embedding 问题是将图$\mathcal{G}$$ \mathcal G $ 转换为$d$$ d $ 维空间，使得图属性尽可能地被保留。其中$d$$ d $ 为预先给定的维度，$d\ll |\mathcal{V}|$$ d\ll |\mathcal V| $ 。

   GNN 是一种特殊的 graph embedding 方法，它通过在图上应用神经网络来学习 embedding 结果。

   注意，本文中我们专注于 node-level 的 embedding 。即对于每个节点$v\in \mathcal{V}$$ v\in \mathcal V $ ，我们输出一个$d$$ d $ 维的 embedding 向量${\overrightarrow{\mathbf{h}}}_v\in {\mathbb{R}}^d$$ \mathbf{\vec h}_v\in \mathbb R^d $ 。这里暂时不考虑边的 emebdding 、子图的 embedding、甚至整个图的 embedding 。

7.2 系统

1. 在我们的 AliGraph 平台中，我们设计并实现了一个底层系统（蓝色实线的方框标记）从而很好地支持高级 GNN 算法和应用程序。接下来我们详细介绍该系统。

   

7.2.1 GNN 算法框架

1. 这里我们为 GNN 算法抽象出一个通用的框架。一系列经典的 GNN 算法，如 Structure2Vec, GCN, FastGCN, AS-GCN, GraphSAGE 可以通过对这个框架的算子进行实例化来实现。

2. GNN 框架算法：

   • 输入：图$\mathcal{G}$$ \mathcal G $ ，embedding 维度$d\in \mathbb{N}$$ d\in \mathbb N $ ，每个节点$v\in \mathcal{V}$$ v\in \mathcal V $ 的属性向量${\overrightarrow{\mathbf{x}}}_v$$ \mathbf{\vec x}_v $ ，最大hop 邻域$k_{max}\in \mathbb{N}$$ k_\max\in \mathbb N $

   • 输出：每个节点$v\in \mathcal{V}$$ v\in \mathcal V $ 的 embedding 向量${\overrightarrow{\mathbf{h}}}_v\in {\mathbb{R}}^d$$ \mathbf{\vec h}_v\in \mathbb R^d $

   • 算法步骤：

     • 对每个节点$v\in \mathcal{V}$$ v\in \mathcal V $ ，初始化${\overrightarrow{\mathbf{h}}}_v^{(0)}={\overrightarrow{\mathbf{x}}}_v$$ \mathbf{\vec h}_v ^{(0)}=\mathbf{\vec x}_v $ 。

     • 迭代$k=1,2,\cdots ,k_{max}$$ k=1,2,\cdots,k_{\max} $ ，迭代步骤为：

       • 对每个节点$v\in \mathcal{V}$$ v\in \mathcal V $ ，执行：

         • 对节点$v$$ v $ 的邻域进行采样：${\mathcal{S}}_v\leftarrow \text{SAMPLE}({\mathcal{N}}_v)$$ \mathcal S_v\leftarrow \text{SAMPLE}(\mathcal N_v) $
         • 聚合节点$v$$ v $ 的采样邻域：${\overrightarrow{\mathbf{h}}}_{{\mathcal{N}}_v}^{\prime }\leftarrow \text{AGGREGATE}({\overrightarrow{\mathbf{h}}}_u^{(k-1)},\mathrm{\forall }u\in \mathcal{S})$$ \mathbf{\vec h}_{\mathcal N_v}^\prime\leftarrow \text{AGGREGATE}\left(\mathbf{\vec h}_u^{(k-1)},\forall u\in \mathcal S\right) $
         • 生成节点$v$$ v $ 的新的embedding ：${\overrightarrow{\mathbf{h}}}_v^{(k)}\leftarrow \text{COMBINE}({\overrightarrow{\mathbf{h}}}_v^{(k-1)},{\overrightarrow{\mathbf{h}}}_{{\mathcal{N}}_v}^{\prime })$$ \mathbf{\vec h}_v^{(k)}\leftarrow \text{COMBINE}\left(\mathbf{\vec h}_v^{(k-1)},\mathbf{\vec h}_{\mathcal N_v}^\prime\right) $

       • 归一化所有节点$v\in \mathcal{V}$$ v\in \mathcal V $ 的 embedding 向量${\overrightarrow{\mathbf{h}}}_v^{(k)}$$ \mathbf{\vec h}_v^{(k)} $ 。

     • 对所有节点$v\in \mathcal{V}$$ v\in \mathcal V $ ，返回${\overrightarrow{\mathbf{h}}}_v={\overrightarrow{\mathbf{h}}}_v^{(k_{max})}$$ \mathbf{\vec h}_v = \mathbf{\vec h}_v^{(k_\max)} $ 作为节点$v$$ v $ 的 final embedding 。

3. GNN 框架的输入包括图$\mathcal{G}$$ \mathcal G $ 、embedding 维度$d\in \mathbb{N}$$ d\in \mathbb N $ 、每个节点$v\in \mathcal{V}$$ v\in \mathcal V $ 的属性向量${\overrightarrow{\mathbf{x}}}_v$$ \mathbf{\vec x}_v $ 、最大hop 邻域$k_{max}\in \mathbb{N}$$ k_\max\in \mathbb N $ 。GNN 框架的输出为每个节点$v\in \mathcal{V}$$ v\in \mathcal V $ 的 embedding 向量${\overrightarrow{\mathbf{h}}}_v\in {\mathbb{R}}^d$$ \mathbf{\vec h}_v\in \mathbb R^d $ ，然后将 embedding 馈入到下游机器学习任务，如节点分类、链接预测任务等。

   GNN 框架首先将节点$v$$ v $ 的节点 embedding${\overrightarrow{\mathbf{h}}}_v^{(0)}$$ \mathbf{\vec h}_v ^{(0)} $ 初始化为输入的属性向量${\overrightarrow{\mathbf{x}}}_v$$ \mathbf{\vec x}_v $ 。然后在第$k$$ k $ 轮迭代时，每个节点$v$$ v $ 聚合邻域的 embedding 来更新自己的 embedding。

   具体而言：

   • 首先使用 SAMPLE 函数来对节点$v$$ v $ 的邻域${\mathcal{N}}_v$$ \mathcal N_v $ 采样从而获得邻域子集$\mathcal{S}$$ \mathcal S $ 。
   • 然后通过 AGGREGATE 函数来聚合$\mathcal{S}$$ \mathcal S $ 中所有节点的 embedding 来获得邻域 embedding${\overrightarrow{\mathbf{h}}}_{{\mathcal{N}}_v}^{\prime }$$ \mathbf{\vec h}_{\mathcal N_v}^\prime $ 。
   • 然后使用 COMBINE 函数来拼接${\overrightarrow{\mathbf{h}}}_{{\mathcal{N}}_v}^{\prime }$$ \mathbf{\vec h}_{\mathcal N_v}^\prime $ 和${\overrightarrow{\mathbf{h}}}_v^{(k-1)}$$ \mathbf{\vec h}_v^{(k-1)} $ 来生成${\overrightarrow{\mathbf{h}}}_v^{(k)}$$ \mathbf{\vec h}_v^{(k)} $ 。
   • 处理完所有节点之后，将 embedding 向量归一化normalized 。
   • 最后，经过$k_{max}$$ k_\max $ 步之后，返回${\overrightarrow{\mathbf{h}}}_v^{(k_{max})}$$ \mathbf{\vec h}_v^{(k_\max)} $ 作为节点$v$$ v $ 的 final embedding${\overrightarrow{\mathbf{h}}}_v$$ \mathbf{\vec h}_v $ 。

4. 基于上述 GNN 算法框架，我们自然地构建了 AliGraph 平台的系统架构。该平台整体上由五层组成，其中底部三层用于支撑顶部的算法层algorithm layer 和应用层 application layer 。

   • 存储层storage layer 可以组织和存储各种原始数据，从而满足high-level 操作和算法对快速访问数据的要求。
   • 在此基础上，结合 GNN 算法框架，我们发现 SAMPLE, AGGREGATE, COMBINE 这三个主要的算子operator 在各种 GNN 算法中起着重要作用。其中 SAMPLE 算子为 AGGREGATE, COMBINE 奠定基础，因为它直接控制了后者需要处理的信息的范围。因此我们设计了 sampling layer 来访问存储，从而快速、正确地生成训练样本。
   • 在采样层的上方， operator layer 专门优化了 AGGREGATE 和COMBINE 函数。
   • 在系统顶部，可以在algorithm layer 构建 GNN 算法，并在 application layer 服务于实际任务。

7.2.2 存储层

1. 这里我们讨论如何存储和组织原始数据。注意，存储真实世界的图的空间成本非常大。常见的电商网络可能包含数百亿节点和数千亿边，其存储成本很容易超过 10TB。大规模的图为有效的图访问带来了巨大的挑战，尤其是在集群的分布式环境中。

   为了很好地支持high-level 算子和算法，我们在 AliGraph 的存储层应用了以下三种策略：图分区 graph partition、属性的分离存储separate storage of attributes 、重要节点的邻居缓存caching neighbors of important vertices。

a. 图分区

1. AliGraph 平台建立在分布式环境上，因此整个图被划分并分别存储在不同的 worker 中。图分区的目标是最小化交叉边crossing edge 的数量。其中交叉边指的是：一条边的两个节点位于不同的 worker 上。

   已有一些文献提出了一系列算法。这里我们实现了四种内置的图分区算法，这四种算法适用于不同的情况。

   • MEIS 算法：适用于稀疏图。
   • 节点cut 和边 cut 分区算法：适用于稠密图。
   • 2-D 分区算法：适用于 worker 数量固定的场景。
   • 流式streaming-style分区策略：适用于边频繁更新的场景。

   用户可以根据自己的需求选择最佳的分区策略。此外，用户还可以将其它的图分区算法实现为系统中的插件。

2. MEIS 算法背后的基本思想非常简单：

   • 粗化阶段coarsening phase：将图$\mathcal{G}$$ \mathcal G $ 粗化coarsen 为一个很小的子图。在这个阶段，图的规模不断缩减。
   • 初始划分阶段initial partitioning phase：对这个子图一分为二bisection。
   • 逆粗化阶段uncoarsening phase：把这个子图的划分不断映射回原始的大图，映射过程中不断微调refine划分边界。

   这个过程如下图所示。

   

3. 节点cut 和边 cut 分区算法：

   • edge-cuts：已有一些方法的目标是将节点均匀分配给worker 从而使得 cut edges （跨机器的边）数量最小化。但是这种方式对于幂律分布的图low graph 效果非常差。因此 edge-cuts 使用随机的节点划分。

     定理：如果节点被随机分配到$p$$ p $ 个机器上，则期望的跨机器的边的比例为：

     $$\mathbb{E}\left[\frac{|\text{cut edges}|}{|\mathcal{E}|}\right]=1-\frac{1}{p}$$

     进一步地，如果节点 degree 分布服从指数为$\alpha$$ \alpha $ 的幂律分布，则每个节点的期望的跨机器的边的比例为：

     $$\mathbb{E}\left[\frac{|\text{cut edges}|}{|\mathcal{V}|}\right]=(1-\frac{1}{p})\mathbb{E}[D_v]=(1-\frac{1}{p})\frac{\mathbf{h}(\alpha -1)}{\mathbf{h}(\alpha )}$$

     其中：$D_v$$ D_v $ 为节点$v$$ v $ 的 degree ；$\mathbf{h}(\alpha )=\sum _{d=1}^{|\mathcal{V}|-1}{d}^{-\alpha }$$ \mathbf h(\alpha)=\sum_{d=1}^{|\mathcal V|-1}d^{-\alpha} $ 为幂律分布的归一化常数。

   • vertex-cut：我们既可以按照节点来划分graph，也可以按照边来划分 graph。节点的 degree 的分布是高度倾斜的，但是每条边相邻的节点数量的分布是恒定的（如每条边仅与两个节点相连）。因此 vertex-cut 具有更好的潜力。

     在 vertex-cut 中，每条边都分配给单个机器，并且在所有机器之间cut 节点。如果相邻的两条边位于不同的机器，则相邻边的共同节点在这两台机器之间拷贝。

     如下图所示分别为 edge-cut（按节点划分并切割边）、vertex-cut（按边划分并切割节点）。虚线节点表示被拷贝的 ghost 节点，1,2,3 表示三台机器。

     

     定理：如果边被随机分配到$p$$ p $ 个机器上，则期望的被切割节点比例为：

     $$\mathbb{E}\left[\frac{|\text{cut vertex}|}{|\mathcal{V}|}\right]=\frac{p}{|\mathcal{V}|}\sum _{v\in \mathcal{V}}(1-{(1-\frac{1}{p})}^{D_v})$$

     其中$D_v$$ D_v $ 为节点$v$$ v $ 的 degree 。

     进一步地，如果节点 degree 分布服从指数为$\alpha$$ \alpha $ 的幂律分布，则期望的被切割节点比例为：

     $$\mathbb{E}\left[\frac{|\text{cut vertex}|}{|\mathcal{V}|}\right]=p-\frac{p}{\mathbf{h}(\alpha )}\sum _{d=1}^{|\mathcal{V}|-1}{\left(\frac{p-1}{p}\right)}^d{d}^{-\alpha }$$

     其中$\mathbf{h}(\alpha )=\sum _{d=1}^{|\mathcal{V}|-1}{d}^{-\alpha }$$ \mathbf h(\alpha)=\sum_{d=1}^{|\mathcal V|-1}d^{-\alpha} $ 为幂律分布的归一化常数。

   随机的vertex-cut 实现了很好的预期的性能，在机器之间获得了几乎完美的平衡。$\alpha$$ \alpha $ 越大则拷贝节点的比例越大（replication factor ），但是随机的vertex-cut 也获得了更好的收益。

4. 2D 划分算法：从原理上将，2D 划分算法将图的邻接矩阵划分为$\sqrt{k}\times \sqrt{k}$$ \sqrt k\times \sqrt k $ （行 x 列）一共$k$$ k $ 个分块，并将$k$$ k $ 个分块分配到$p$$ p $ 台机器。其中要求少数分块具有大量的非零元素、大部分分块具有少量的非零元素。

   如下图所示为 2D 划分到 6 台机器上的情况，每种颜色代表一台机器。对角线的 block 包含大量的非零元素，非对角线的 block 包含少量的非零元素。

   

5. 流式分区：在流式分区中，我们将以 edge stream 的形式将节点分发到各个 worker。当节点到达时，一个 partitioner 决定将节点放置在哪个 worker 上。节点一旦放置则永不移动。

   • edge stream 的顺序可以是随机的、广度优先搜索、深度优先搜索。
   • 边可以是有向的或者无向的。如果是无向图，则每条边在流中出现两次。
   • 我们运行分区算法访问已经落地的节点定义的整个子图，或者仅仅是有关这个子图的局部信息（直接邻域）。

   流式分区理论上可以处理非常大的图（只要集群资源足够），并且只需要加载一次图，并且只需要很少的通信成本。

6. Partition and Caching 算法：

   • 输入：图$\mathcal{G}$$ \mathcal G $ ，分区数量$p$$ p $ ，cache 深度$h$$ h $ ，阈值${\tau }_1,\cdots ,{\tau }_h$$ \tau_1,\cdots,\tau_h $ （用于指定$h$$ h $ 层的重要的节点）

   • 输出：$p$$ p $ 个子图

   • 算法步骤：

     • 初始化$p$$ p $ 个 graph server

     • 分区：对于每条边$e=(u,v)\in \mathcal{E}$$ e=(u,v)\in \mathcal E $ 执行：

       • $j=\text{ASSIGN}(u)$$ j=\text{ASSIGN}(u) $ 。其中 ASSIGN(.) 为图分区函数，它根据边$e$$ e $ 来对节点分区。
       • 将边$e$$ e $ 发送到第$j$$ j $ 个 partition 。

     • 缓存：对每个节点$v\in \mathcal{V}$$ v\in \mathcal V $ 执行：

       • $\text{for}k\leftarrow 1\text{to}h$$ \text{for } k\leftarrow 1 \text{ to } h $ ：

         • 计算$D_i^{(k)}(v)$$ D_i^{(k)}(v) $ 和$D_o^{(k)}(v)$$ D_o^{(k)}(v) $
         • 如果$\frac{D_i^{(k)}(v)}{D_o^{(k)}(v)}\ge {\tau }_k$$ \frac{D_i^{(k)}(v)}{D_o^{(k)}(v)}\ge \tau_k $ ，则在$v$$ v $ 的分区上缓存节点$v$$ v $ 的、从 hop 1 到 hop k 的出边邻居。

b. 属性的分离存储

1. 对于异质图，我们需要在每个 worker 进行中存储分区图的结构和属性。

   • 图的结构信息可以通过邻接表简单地存储。即，对于每个节点$v$$ v $ ，我们存储其邻域集合${\mathcal{N}}_v$$ \mathcal N_v $ 。

   • 对于节点和边上的属性，不宜将它们一起存储在邻接表中。有两个原因：

     • 属性通常占用更多的空间。例如存储节点 ID 的空间成本最多为 8 个字节，但是存储节点上的属性的空间成本可能从 0.1KB 到 1KB。
     • 不同节点或边之间的属性有很大的重叠。例如，很多节点可能具有表示性别的标签 man。

     因此，单独存储属性更为合理。

2. 在 AliGraph 中，我们通过构建两个索引集合${\mathcal{I}}_{\mathcal{V}},{\mathcal{I}}_{\mathcal{E}}$$ \mathcal I_\mathcal V,\mathcal I_\mathcal E $ 来存储节点和边上的属性。

   • ${\mathcal{I}}_{\mathcal{V}}$$ \mathcal I_\mathcal V $ 中的每一项关联节点上的一个unique 属性。
   • ${\mathcal{I}}_{\mathcal{E}}$$ \mathcal I_\mathcal E $ 中的每一项关联边上的一个 unique 属性。

   如下图所示，在邻接表中：

   • 对于每个节点$u$$ u $ ，我们存储属性${\mathcal{A}}_{\mathcal{V}}(u)$$ \mathcal A_\mathcal V(u) $ 在${\mathcal{I}}_{\mathcal{V}}$$ \mathcal I_\mathcal V $ 中的索引。
   • 对于每条边$(u,v)$$ (u,v) $ ，我们存储属性${\mathcal{A}}_{\mathcal{E}}(u,v)$$ \mathcal A_\mathcal E(u,v) $ 在${\mathcal{I}}_{\mathcal{E}}$$ \mathcal I_\mathcal E $ 中的索引。

   令$N_D$$ N_D $ 和$N_L$$ N_L $ 分别为平均邻居数量、平均属性长度。令$N_A$$ N_A $ 为节点和边上的 distinct 属性的数量。显然，我们的属性分离存储策略将空间成本从$O(n{N}_D{N}_L)$$ O(nN_DN_L) $ 下降到$O(n{N}_D+N_A{N}_L)$$ O(nN_D + N_AN_L) $ 。

   

3. 毫无疑问，属性的分离存储将增加检索属性的访问时间。平均而言，每个节点需要访问索引${\mathcal{I}}_{\mathcal{E}}$$ \mathcal I_\mathcal E $ 最多$N_D$$ N_D $ 次就可以收集它的所有邻居的属性。

   为缓解这个问题，我们添加了两个缓存组件cache components ，分别将${\mathcal{I}}_{\mathcal{V}}$$ \mathcal I_\mathcal V $ 和${\mathcal{I}}_{\mathcal{E}}$$ \mathcal I_\mathcal E $ 中频繁访问的项缓驻留在cache 中。我们对每个 cache 采用least recently used:LRU 策略来更新cache 内容。

c. 重要节点的邻居缓存

1. 在每个 worker 中，我们进一步提出了一种在局部cache 某些重要节点的邻居的方法从而降低通信成本。

   直观的想法是：如果节点$v$$ v $ 经常被访问，我们可以将$v$$ v $ 的出边邻居out-neighbors存储在它出现的每个分区中。这样就可以大大降低访问$v$$ v $ 邻居的成本。

   但是，如果$v$$ v $ 的邻居数量很大，则存储$v$$ v $ 邻居的多个副本将导致巨大的存储成本。为了更好地平衡trade-off，我们定义了一个指标来评估每个节点的重要性，这个指标决定了是否值得缓存一个节点。

   • 定义$D_i^{(k)}(v)$$ D_i^{(k)}(v) $ 为节点$v$$ v $ 的 k-hop 入边邻居 in-neighbors ，它衡量了缓存节点$v$$ v $ 邻居的收益。

     因为$v$$ v $ 入边邻居越多，则缓存邻居之后可以从高速缓存中获取邻居节点和边的特征，而不需要从索引集合中遍历地检索。

   • 定义$D_o^{(k)}(v)$$ D_o^{(k)}(v) $ 为节点$v$$ v $ 的 k-hop 出边邻居 out-neighbors。它衡量了缓存节点$v$$ v $ 邻居的成本。

     因为邻居节点也需要以该邻居节点为 key 来缓存当前节点（作为该邻居的邻居），因此$v$$ v $ 出边越多则需要缓存的节点数量越多。

   因此，定义节点$v$$ v $ 的 k-th 重要性为：

   $${\text{Imp}}^{(k)}(v)=\frac{D_i^{(k)}(v)}{D_o^{(k)}(v)}$$

   仅当节点$v$$ v $ 的重要性${\text{Imp}}^{(k)}(v)$$ \text{Imp}^{(k)}(v) $ 足够大时，才会缓存节点$v$$ v $ 的出边邻居。

   注意：这里考虑的是有向图。对于无向图，入边邻居等于出边邻居，则${\text{Imp}}^{(k)}(v)=1$$ \text{Imp}^{(k)}(v) = 1 $ 恒成立。

2. Partition and Caching 算法给出了缓存重要节点的出边邻居的过程。$h$$ h $ 为我们考虑的邻居的最大深度，${\tau }_k$$ \tau_k $ 为用户指定的、 k-hop 邻居的阈值。如果${\text{Imp}}^{(k)}(v)\ge {\tau }_k$$ \text{Imp}^{(k)}(v) \ge \tau_k $ ，则我们缓存节点$v$$ v $ 的从 1...k-hop 出边邻居。

   • 注意，将$h$$ h $ 设置为一个比较小的数字（通常为 2）就足以支持一系列实际中的 GNN 算法。
   • 实际上我们发现${\tau }_k$$ \tau_k $ 不是敏感参数。通过实验评估，将${\tau }_k$$ \tau_k $ 设置为 0.2 左右的较小的值可以在缓存成本和收益之间取得最佳平衡。

3. 有趣的是，我们发现要缓存的节点只是整个图的很小一部分。现实世界中节点的、直接相连的 in-degree$D_i^{(1)}(v)$$ D_i^{(1)}(v) $ 和 out-degree$D_o^{(1)}(v)$$ D_o^{(1)}(v) $ 通常服从幂律分布 power-law distribution 。即，图中的极少数节点具有较大的 in-degree 和 out-degree。

   有鉴于此，我们得出两个定理：

   • 定理一：如果 in-degree 和 out-degree 服从幂律分布，则对于任意$k\ge 1$$ k\ge 1 $ ，图中节点的 k-hop 的 in-degree 和 out-degree 也服从幂律分布。

     该定理可以通过数学归纳法证明，具体过程参考原始论文。

   • 定理二：如果图的in-degree 和 out-degree 服从幂律分布，则图中节点的 importance 取值也服从幂律分布。

     该定理可以直接证明，具体过程参考原始论文。

   定理二表明：图中的极少数节点具有较大的 importance 。这意味着我们只需要缓存少量的、重要的节点即可显著降低图遍历的成本。

   虽然要缓存的节点比较少，但是这些节点覆盖的邻居节点集合比较大，整体空间占用也比较高。

7.2.3 采样层

1. GNN 算法需要聚合邻域信息来生成每个节点的 embedding。但是，现实世界的 degree 分布通常会倾斜，这使得卷积运算难以执行。为解决这个问题，现有的 GNN 通常采用各种采样策略来采样邻域的子集。由于采样的重要性，在我们的系统中我们抽象出了一个采样层来优化采样策略。

2. 正式地，采样函数接受一个节点集合${\mathcal{V}}_T$$ \mathcal V_T $ 作为输入，并返回一个更小的节点集合${\mathcal{V}}_S\subseteq {\mathcal{V}}_T$$ \mathcal V_S\sube\mathcal V_T $ 作为输出，其中$|{\mathcal{V}}_S|\ll |{\mathcal{V}}_T|$$ |\mathcal V_S|\ll |\mathcal V_T| $ 。通过全面了解当前的 GNN 模型，我们抽象出三种不同的采样器，即：

   • TRAVERSE：用于从整个分区的子图中采样一个 batch 的节点或者边。
   • NEIGHBORHOOD：用于从节点的邻域中采样节点作为上下文。邻域可以是直接邻域或者 k-hop 邻域。
   • NEGATIVE：用于生成负样本从而加快训练过程的收敛速度。

3. 在之前的工作中，采样方法在提高 GNN 算法的效率和准确性方面起着重要作用。在我们的系统中，我们将所有采样器都视为插件，它们每个都可以独立地实现。上述三种类型的采样器可以实现如下：

   • TRAVERSE：可以从局部子图获取数据。

   • NEIGHBORHOOD：可以从局部存储获取1-hop 邻域，也可以从局部cache 获取k-hop 邻域。如果节点的邻居没有被缓存，则需要调用远程的 graph server 。

     当获取一个 batch 节点的邻域时，我们首先将这些节点划分为多个 sub-batch，然后每个 sub-batch 节点的邻域从相应的 graph server 返回，然后将返回结果组合在一起。

   • NEGATIVE：通常从局部 graph server 获得负采样。对于某些特殊情况，可能需要从其它graph server 进行负采样。

     负采样在算法上很灵活，我们不需要在一个 batch 中调用所有的 graph server。

   总之，下述代码给出了一个典型的采样阶段：

   
   xxxxxxxxxx
   # Define a TRAVERSE sampler as s1
   # Define a NEIGHBORHOOD sampler as s2
   # Define a NEGATIVE sampler as s3
   # ...
   def sampling(s1, s2, s3, batch_size):
       vertex = s1.sample(edge_type, batch_size)
       # hop_nums contains neighbor count at each hop
       context = s2.sample(edge_type, vertex, hop_nums)
       neg = s3.sample(edge_type, vertex, neg_num)
       return vertex, context, neg

4. 通过使用带动态权重的几种有效的采样策略，我们可以加快训练速度。我们在采样器的反向传播阶段实现了权重更新操作，类似于算子的梯度反向传播。因此，当需要权重更新时，我们应该做的是为采样器注册一个梯度函数。权重更新的模式（同步的或者异步的）取决于模型训练算法。

5. 目前为止，读取和更新都将在内存中的 graph storage 上进行，这可能会导致性能下降。根据邻域要求，图将按照源节点进行划分。基于此，我们将graph server 上的节点分为几组。每一组都与一个 request-flow bucket 相关联。在这个request-flow bucket 中，包括读取、更新在内的所有操作都将与该组中的节点相关。bucket 是无锁的队列。

   如下图所示，我们将每个bucket 绑定到一个 CPU core，然后bucket 中的每个操作都将被顺序处理而不会加锁。这将进一步提高系统效率。

   

7.2.4 算子层

1. 经过采样之后，得到的输出将被对齐aligned，然后我们可以轻松地对采样后的集合进行处理。

   我们需要一些 GNN-like 算子来处理这些采样后的结果。在我们的系统中，我们抽象了两种算子，即 AGGREGATE 和 COMBINE：

   • AGGREGATE：收集每个节点的邻域信息从而产生单个结果。例如， AGGREGATE 将一系列向量${\overrightarrow{\mathbf{h}}}_u\in {\mathbb{R}}^d$$ \mathbf{\vec h}_u\in \mathbb R^d $ 映射到单个向量${\overrightarrow{\mathbf{h}}}_{{\mathcal{N}}_v}^{\prime }\in {\mathbb{R}}^d$$ \mathbf{\vec h}_{\mathcal N_v}^\prime\in \mathbb R^d $ ，其中$u$$ u $ 属于节点$v$$ v $ 采样后的邻域集合。${\overrightarrow{\mathbf{h}}}_{{\mathcal{N}}_v}^{\prime }$$ \mathbf{\vec h}_{\mathcal N_v}^\prime $ 为中间结果，用于进一步生成${\overrightarrow{\mathbf{h}}}_v$$ \mathbf{\vec h}_v $ 。

     AGGREGATE 函数充当卷积算子的作用，因为它从周围邻域收集信息。在不同的 GNN 方法中采用了不同的聚合函数，如均值池化、最大池化、LSTM 等。

   • COMBINE：它给出如何使用邻域信息来更新节点的 embedding。例如，COMBINE 函数将两个向量${\overrightarrow{\mathbf{h}}}_v^{(k-1)}\in {\mathbb{R}}^d,{\overrightarrow{\mathbf{h}}}_{{\mathcal{N}}_v}^{\prime }\in {\mathbb{R}}^d$$ \mathbf{\vec h}_v^{(k-1)}\in \mathbb R^d,\mathbf{\vec h}_{\mathcal N_v}^\prime\in \mathbb R^d $ 映射到单个向量${\overrightarrow{\mathbf{h}}}_v^{(k)}\in {\mathbb{R}}^d$$ \mathbf{\vec h}_v^{(k )}\in \mathbb R^d $ 。

     COMBINE 函数可以将前一层的信息以及邻域信息整合到一个统一的空间中。通常在现有的 GNN 方法中，将${\overrightarrow{\mathbf{h}}}_v^{(k-1)}$$ \mathbf{\vec h}_v^{(k-1)} $ 和${\overrightarrow{\mathbf{h}}}_{{\mathcal{N}}_v}^{\prime }$$ \mathbf{\vec h}_{\mathcal N_v}^\prime $ 相加（或拼接），然后馈入到一个深度神经网络中。

2. 典型的算子由前向计算和反向计算组成。采样器和 GNN-like 算子不仅执行前向计算，而且在需要时会反向计算从而更新参数。这样我们可以将整个模型作为一个网络从而进行端到端的训练。

   和SAMPLE 类似，AGGREGATE, COMBINE 也是 AliGraph 的插件，可以独立地实现。基于算子，用户可以快速搭建 GNN 模型。

3. 考虑到图数据的特点，可以使用大量优化从而获得更好的性能。

   为了进一步加速这两个算子的计算，我们通过具体化materialization${\overrightarrow{\mathbf{h}}}_v^{(k)}$$ \mathbf{\vec h}_v^{(k)} $ 的中间向量的策略来实现。注意到在训练过程中的每个 mini-batch，我们可以为mini-batch 中的所有节点共享一组采样的邻居。同样地，我们可以为同一个 mini-batch 中的所有节点之间共享向量${\overrightarrow{\mathbf{h}}}_v^{(k)},1\le k\le k_{max}$$ \mathbf{\vec h}_v^{(k)},1\le k\le k_\max $ 。为此：

   • 我们对 mini-batch 中的所有节点存储$k_{max}$$ k_\max $ 个向量${\widehat{\overrightarrow{\mathbf{h}}}}_v^{(1)},\cdots ,{\widehat{\overrightarrow{\mathbf{h}}}}_v^{(k_{max})}$$ \hat{\mathbf{\vec h}}_v^{(1)},\cdots,\hat{\mathbf{\vec h}}_v^{(k_\max)} $ ，并将其视为新的向量。
   • 然后在 AGGREGATE 函数中，我们通过${\widehat{\overrightarrow{\mathbf{h}}}}_v^{(1)},\cdots ,{\widehat{\overrightarrow{\mathbf{h}}}}_v^{(k_{max})}$$ \hat{\mathbf{\vec h}}_v^{(1)},\cdots,\hat{\mathbf{\vec h}}_v^{(k_\max)} $ 来获取${\widehat{\overrightarrow{\mathbf{h}}}}_{{\mathcal{N}}_v}^{\prime }$$ \hat{\mathbf{\vec h}}_{\mathcal N_v}^\prime $ 。
   • 最后，我们在 COMBINE 函数中通过${\widehat{\overrightarrow{\mathbf{h}}}}_{{\mathcal{N}}_v}^{\prime }$$ \hat{\mathbf{\vec h}}_{\mathcal N_v}^\prime $ 和${\overrightarrow{\mathbf{h}}}_v^{(k-1)}$$ {\mathbf{\vec h}}_v^{(k-1)} $ 来计算${\widehat{\overrightarrow{\mathbf{h}}}}_v^{(k)}$$ \hat{\mathbf{\vec h}}_v^{(k)} $ 。

   通过这种策略，可以大大降低算子上的计算成本。这本质上是空间换时间的策略。

   这种方式避免了针对 mini-batch 中的每个子图来进行独立地计算，因为独立地计算每个子图可能会导致重复计算。

7.3 GNN 方法

1. 这里我们讨论GNN 算法的设计。我们表明：现有的 GNN 可以轻松地在 AliGraph 上构建。此外，我们还提出了一系列新的 GNN 算法，从而解决前面概述的、在 embedding 真实世界图数据的四个挑战。所有这些都是 AliGraph 平台的算法层的插件。

2. 由于我们的 AliGraph 平台时从通用 GNN 算法中抽象出来的，因此可以在该平台上轻松实现所有的 GNN。这里以 GraphSAGE 为例，其它 GNN 可以用类似的方式实现，由于篇幅所限我们这里省略。

   • 注意到， GraphSAGE 采用了简单的node-wise 采样，从而在每个节点的邻域集合中采样一个小的子集。显然，使用我们的 SAMPLING 算子可以轻松实现其采样策略。
   • 然后，我们需要实现 AGGREGATE 和 COMBINE 函数。GraphSAGE 可以通过加权平均的方式实现 AGGREGATE 函数。也可以使用更复杂的函数，如最大池化、LSTM 等。

   对于其它的 GNN 方法（如 GCN, FastGCN, AS-GCN ）中，我们可以对 SAMPLING, AGGREGATE, COMBINE 采用不同的策略。

3. 除了已有的 GNN 算法之外，我们还开发了一些内部的 GNN 。我们内部开发的 GNN 专注于各个不同方面，如采样（AHEP）、多重性（GATNE）、多模态（Mixture GNN）、层次性（Hierarchical GNN）、动态性（Evolving GNN）、多源信息（Bayesian GNN）。

7.3.1 AHEP

1. HEP: Heterogeneous Embedding Propagation 尝试通过聚合每种类型的邻居来重构节点embedding 。

   对于每个节点$v\in \mathcal{V}$$ v\in \mathcal V $ ，定义其类型为$c$$ c $ 的邻域为${\mathcal{N}}_v^{(c)}\subset {\mathcal{N}}_v$$ \mathcal N_v^{(c)}\sub \mathcal N_v $ 。对于每种类型的邻域我们聚合邻域的embedding 为：

   $${\widetilde{\overrightarrow{\mathbf{g}}}}_v^{(c)}=\sum _{u\in {\mathcal{N}}_v^{(c)}}\frac{s_{v,u}}{\sum _{u^{\prime }\in {\mathcal{N}}_v^{(c)}}{s}_{v,u^{\prime }}}{\overrightarrow{\mathbf{h}}}_u$$

   其中$s_{v,u}$$ s_{v,u} $ 为邻域节点$u$$ u $ 的权重，它根据$(v,u)$$ (v,u) $ 边的特征来计算。计算方式为：

   $$s_{v,u}=\sigma ({\overrightarrow{\lambda }}_{\phi (v,u)}\cdot {\overrightarrow{\mathbf{f}}}_{(v,u)}+{\overrightarrow{\mathbf{b}}}_{\phi (v,u)})$$

   其中：

   • $\sigma (\cdot )$$ \sigma(\cdot) $ 为非线性激活函数。
   • ${\overrightarrow{\mathbf{f}}}_{(v,u)}$$ \mathbf{\vec f}_{(v,u)} $ 为边$(v,u)$$ (v,u) $ 的特征向量。
   • ${\overrightarrow{\lambda }}_{\phi (v,u)}$$ \vec\lambda_{\varphi(v,u)} $ 为对应于边类型$\phi (v,u)$$ \varphi(v,u) $ 的权重参数，它在相同类型的边上共享。
   • ${\overrightarrow{\mathbf{b}}}_{\phi (v,u)}$$ \mathbf{\vec b}_{\varphi(v,u)} $ 对应于边类型$\phi (v,u)$$ \varphi(v,u) $ 的bias 参数，它在相同类型的边上共享。

   注意：$s_{v,u}$$ s_{v,u} $ 只能在节点$v$$ v $ 的相同类型的邻域上进行比较，无法跨邻域比较。

   然后我们将所有类型的邻域的 embedding 向量进行拼接，从而得到总的邻域 embedding 向量：

   $${\widetilde{\overrightarrow{\mathbf{g}}}}_v=\text{CONCAT}({\widetilde{\overrightarrow{\mathbf{g}}}}_v^{(c_1)},\cdots ,{\widetilde{\overrightarrow{\mathbf{g}}}}_v^{(c_K)})$$

   最后我们根据总的邻域 embedding 向量来重构节点$v$$ v $ 的 embedding${\widetilde{\overrightarrow{\mathbf{h}}}}_v$$ \tilde{\mathbf{\vec h}}_v $ ：

   $${\widetilde{\overrightarrow{\mathbf{h}}}}_v=\sigma ({\mathbf{W}}_{\varphi (v)}^{\prime }{\widetilde{\overrightarrow{\mathbf{g}}}}_v+{\overrightarrow{\mathbf{b}}}_{\varphi (v)}^{\prime })$$

   其中：

   • ${\mathbf{W}}_{\varphi (v)}^{\prime }$$ \mathbf W^\prime_{\phi(v)} $ 是对应于节点类型$\varphi (v)$$ \phi(v) $ 的权重矩阵，它在相同的节点类型上共享。
   • ${\overrightarrow{\mathbf{b}}}_{\varphi (v)}^{\prime }$$ \mathbf{\vec b}^\prime_{\phi(v)} $ 为对应于节点类型$\varphi (v)$$ \phi(v) $ 的bias 向量，它在相同的节点类型上共享。

   我们的重构损失为 hinge loss ：

   $$\mathcal{l}(v,u)=[\gamma +\pi ({\widetilde{\overrightarrow{\mathbf{h}}}}_v,{\overrightarrow{\mathbf{h}}}_v)-\pi ({\widetilde{\overrightarrow{\mathbf{h}}}}_v,{\overrightarrow{\mathbf{h}}}_u)]$$

   其中：

   • $\pi ({\widetilde{\overrightarrow{\mathbf{h}}}}_v,{\overrightarrow{\mathbf{h}}}_v)=\frac{1}{2}{\Vert {\widetilde{\overrightarrow{\mathbf{h}}}}_v-{\overrightarrow{\mathbf{h}}}_v\Vert }_2^2$$ \pi\left(\tilde{\mathbf{\vec h}}_v,\mathbf{\vec h}_v\right)=\frac 12 \left\|\tilde{\mathbf{\vec h}}_v- {\mathbf{\vec h}}_v\right\|_2^2 $ 为重构距离。
   • $u$$ u $ 为负采样的节点，$\gamma >0$$ \gamma\gt 0 $ 为松弛参数。

   物理意义为：节点$v$$ v $ 重构之后的 embedding和节点$v$$ v $ 原始 embedding 之间的距离，要小于节点$v$$ v $ 重构之后的 embedding 和随机选择的节点$u$$ u $ 原始 embedding 之间的距离。

2. 除了重构损失之外，如果有监督信息则 HEP 还会考虑监督损失。则总的损失为：

   $$\mathcal{L}={\mathcal{L}}_1+\alpha \times {\mathcal{L}}_2+\beta \times \mathrm{\Omega }(\mathrm{\Theta })$$

   其中：

   • ${\mathcal{L}}_1$$ \mathcal L_1 $ 为监督损失，${\mathcal{L}}_2$$ \mathcal L_2 $ 为无监督的重构损失，$\mathrm{\Omega }(\mathrm{\Theta })$$ \Omega(\Theta) $ 为正则化项。
   • $\alpha ,\beta$$ \alpha,\beta $ 为trade-off 系数。

3. AHEP 算法（HEP with adaptive sampling ）旨在缓解异质图上传统的 embedding 传播 embedding propagation:EP 算法（HEP）沉重的计算和存储成本。

   在 AHEP中，我们对重要邻居进行采样，而不是考虑整个邻域。在这个过程中：

   • 我们通过节点的结构信息和特征信息设计了一个指标，从而评估了邻居的重要性。

   • 然后，不同类别邻居根据各自的概率分布独立地进行采样。

     我们精心设计了概率分布，从而最大程度地减少采样方差。

   实验分析表明：AHEP 运行速度要比 HEP 快得多，同时具有相当的准确率。

7.3.2 GATNE

1. General Attributed Multiplex HeTerogeneous Network Embedding:GATNE 旨在处理节点、边上具有异质信息和属性信息的图。在 GATNE 中，每个节点的最终 embedding 由三部分组成：

   • 通用 embedding：每个节点$v_i$$ v_i $ 有一个 base embedding${\overrightarrow{\mathbf{b}}}_i\in {\mathbb{R}}^d$$ \mathbf{\vec b}_i\in \mathbb R^d $ ，它在所有子视图（每种类型的边构成一个子视图）上都相同。

   • specific emebdding（即子视图的 embedding）：边类型为$r$$ r $ 的节点和边构成了一个子视图${\mathcal{G}}_r$$ \mathcal G_r $ 。节点$v_i$$ v_i $ 在${\mathcal{G}}_r$$ \mathcal G_r $ 上第$k$$ k $ 层（$k=1,2,\cdots ,K$$ k=1,2,\cdots,K $ ）的 embedding 的迭代方程为：

     $${\overrightarrow{\mathbf{u}}}_{i,r}^{(k)}=\text{agg}\left(\{{\overrightarrow{\mathbf{u}}}_{j,r}^{(k-1)}\mid v_j\in {\mathcal{N}}_{i,r}\}\right)$$

     其中：

     • ${\mathcal{N}}_{i,r}$$ \mathcal N_{i,r} $ 为节点$v_i$$ v_i $ 在视图${\mathcal{G}}_r$$ \mathcal G_r $ 上的邻居节点集合。
     • agg(.) 为聚合函数，它可以为均值聚合，也可以为池化聚合。

     则节点$v_i$$ v_i $ 在子视图${\mathcal{G}}_r$$ \mathcal G_r $ 中的 emebdding 为${\overrightarrow{\mathbf{u}}}_{i,r}={\overrightarrow{\mathbf{u}}}_{i,r}^{(K)}\in {\mathbb{R}}^s$$ \mathbf{\vec u}_{i,r} = \mathbf{\vec u}_{i,r}^{(K)}\in \mathbb R^s $ ，$s$$ s $ 为edge embedding 维度。

     所有子视图 embedding 通过 self-attention 机制来加权聚合。假设边的类型取值为$\mathcal{R}$$ \mathcal R $ ，则我们拼接节点$v_i$$ v_i $ 的所有类型的 embedding 得到节点$v_i$$ v_i $ 的 embedding 矩阵：

     $${\mathbf{U}}_i=({\overrightarrow{\mathbf{u}}}_{i,1},\cdots ,{\overrightarrow{\mathbf{u}}}_{i,|\mathcal{R}|})\in {\mathbb{R}}^{s\times |\mathbb{R}|}$$

     我们使用 self-attention 机制来计算每个子视图的加权系数${\overrightarrow{\mathbf{a}}}_{i,r}$$ \mathbf{\vec a}_{i,r} $ ，从而线性组合$\{{\overrightarrow{\mathbf{u}}}_{i,1},\cdots ,{\overrightarrow{\mathbf{u}}}_{i,|\mathcal{R}|}\}$$ \left\{\mathbf{\vec u}_{i,1},\cdots,\mathbf{\vec u}_{i,|\mathcal R|}\right\} $ ，得到节点$v_i$$ v_i $ 的 edge embedding ：

     $$\begin{array}{c}{\overrightarrow{\mathbf{a}}}_{i,r}=\text{softmax}({\overrightarrow{\mathbf{w}}}_r^{\mathrm{\top }}\tanh \left({\mathbf{W}}_r{\mathbf{U}}_i\right))\in {\mathbb{R}}^{|\mathcal{R}|}\\ {\widehat{\overrightarrow{\mathbf{u}}}}_{i,r}={\mathbf{U}}_i{\overrightarrow{\mathbf{a}}}_{i,r}\end{array}$$

   • 属性 embedding：每个节点$v_i$$ v_i $ 都带有特征向量${\overrightarrow{\mathbf{x}}}_i$$ \mathbf{\vec x}_i $ 。

   final embedding 由通用 embedding、specific embedding、属性 embedding 组成。它们分别刻画了结构信息、异质信息、属性信息。节点类型为$z$$ z $ 的节点$v_i$$ v_i $ 在子视图${\mathcal{G}}_r$$ \mathcal G_r $ 中的 final embedding 为：

   $${\overrightarrow{\mathbf{v}}}_{i,r}={\overrightarrow{\mathbf{b}}}_i+{\alpha }_r{\mathbf{M}}_r^{\mathrm{\top }}{\mathbf{U}}_i{\overrightarrow{\mathbf{a}}}_{i,r}+{\beta }_r{\mathbf{D}}_z^{\mathrm{\top }}{\overrightarrow{\mathbf{x}}}_i$$

   其中${\alpha }_r,{\beta }_r$$ \alpha_r,\beta_r $ 为 trade-off 系数，${\mathbf{M}}_r,{\mathbf{D}}_z$$ \mathbf M_r,\mathbf D_z $ 为可训练的映射矩阵。

   这里三种类型的 embedding 在 final 时候才进行交互。实际上如果在一开始的时候就交互，可能会得到更好的 embedding 。这就是特征交互的 pre-fuse 和 post-fuse 之间的重要区别。

7.3.3 Mixture GNN

1. Mixture GNN 用于处理具有多模态的异质图。在该模型中，我们扩展了同质图上的 skip-gram 模型来适配异质图上的多义性场景polysemous situation

   • 在传统的 skip-gram 模型中，我们尝试通过最大化似然来找到参数为$\theta$$ \theta $ 的 graph embedding：

     $${\mathcal{L}}_{\theta }=\log {\text{Pr}}_{\theta }({\mathcal{N}}_v\mid v)=\sum _{u\in {\mathcal{N}}_v}\log {\text{Pr}}_{\theta }(u\mid v)$$

     其中${\mathcal{N}}_v$$ \mathcal N_v $ 为节点$v$$ v $ 的邻域，${\text{Pr}}_{\theta }(u\mid v)$$ \text{Pr}_\theta(u\mid v) $ 为 softmax 函数。

   • 在我们的异质图中，每个节点属于多个意义sense。为区分它们，令$P$$ P $ 为节点意义的已知分布，则目标函数为：

     $${\mathcal{L}}_{\text{ploy},\theta }=\log {\text{Pr}}_{P,\theta }({\mathcal{N}}_v\mid v)=\sum _{u\in {\mathcal{N}}_v}\log {\text{Pr}}_{P,\theta }(u,v)$$

     注意：这个分布$P$$ P $ 是待求的、未知的。

     此时，很难结合负采样方法来直接优化上述公式。一种可选的方法是推导出上式的一个新的下界${\mathcal{L}}_{\text{low}}$$ \mathcal L_{\text{low}} $ ，然后尝试优化${\mathcal{L}}_{\text{low}}$$ \mathcal L_{\text{low}} $ 。我们发现下界${\mathcal{L}}_{\text{low}}$$ \mathcal L_{\text{low}} $ 的项可以通过负采样近似。这就是 EM 算法的思想。

     结果，可以通过稍微修改现有的工作（如 Deepwalk, node2vec ）中的采样过程，可以轻松实现训练过程。

7.3.4 Hierarchical GNN

1. 当前 GNN 方法本质上是平的flat，并且无法学习图的 hierarchical representation。这种限制在显式研究各种类型的用户行为的相似性时尤为突出。Hierarchical GNN 结合了层次结构以增强GNN 的表达能力。

   令${\mathbf{H}}^{(k)}\in {\mathbb{R}}^{|\mathcal{V}|\times d}$$ \mathbf H^{(k)}\in \mathbb R^{|\mathcal V|\times d} $ 表示GNN 经过$k$$ k $ 步之后的节点 embedding 矩阵，$\mathbf{A}$$ \mathbf A $ 为图$\mathcal{G}$$ \mathcal G $ 的邻接矩阵。传统的 GNN 迭代式地通过结合${\mathbf{H}}^{(k-1)}$$ \mathbf H^{(k-1)} $ 、$\mathbf{A}$$ \mathbf A $ 、可训练的参数${\theta }^{(k)}$$ \theta^{(k)} $ 来学习${\mathbf{H}}^{(k)}$$ \mathbf H^{(k)} $ 。其中${\mathbf{H}}^{(0)}$$ \mathbf H^{(0)} $ 初始化为$\mathbf{X}$$ \mathbf X $ ，其中$\mathbf{X}$$ \mathbf X $ 为节点特征矩阵。

   在我们的 Hierarchical GNN 中，我们以 layer-to-layer 的方式来学习节点 embedding 。具体而言：

   • 令${\mathbf{A}}^{(l)}$$ \mathbf A^{(l)} $ 和${\mathbf{X}}^{(l)}$$ \mathbf X^{(l)} $ 为第$l$$ l $ 层的邻接矩阵和节点特征矩阵。令节点 embedding 矩阵${\mathbf{Z}}^{(l)}$$ \mathbf Z^{(l)} $ 为通过单层 GNN 以及输入${\mathbf{A}}^{(l)},{\mathbf{X}}^{(l)}$$ \mathbf A^{(l)},\mathbf X^{(l)} $ 学到的。

   • 我们对图的节点聚类，从而得到邻接矩阵${\mathbf{A}}^{(l+1)}$$ \mathbf A^{(l+1)} $ 。为学到这样的聚类，我们定义${\mathbf{S}}^{(l)}$$ \mathbf S^{(l)} $ 为第$l$$ l $ 层待学习的分配矩阵 assignment matrix。

     ${\mathbf{S}}^{(l)}$$ \mathbf S^{(l)} $ 中的元素$S_{i,j}^{(l)}$$ S^{(l)}_{i,j} $ 表示第$l$$ l $ 层的“节点”$i$$ i $ （它实际上是一个粗化的节点，即一个簇）被分配到第$l+1$$ l+1 $ 层的“节点”$j$$ j $ （它也是一个粗化的节点，即一个簇）。

     ${\mathbf{S}}^{(l)}$$ \mathbf S^{(l)} $ 可以通过在另一个 pooling GNN 以及输入${\mathbf{A}}^{(l)},{\mathbf{X}}^{(l)}$$ \mathbf A^{(l)},\mathbf X^{(l)} $ 上应用 softmax 函数来获得。

   • 当有了${\mathbf{Z}}^{(l)},{\mathbf{S}}^{(l)}$$ \mathbf Z^{(l)},\mathbf S^{(l)} $ 之后，我们可以得到新的、粗化的邻接矩阵${\mathbf{A}}^{(l+1)}={\mathbf{S}}^{(l{)}^{\mathrm{\top }}}{\mathbf{A}}^{(l)}{\mathbf{S}}^{(l)}$$ \mathbf A^{(l+1)} = \mathbf S^{(l)^\top}\mathbf A^{(l)}\mathbf S^{(l)} $ ，以及新的特征矩阵${\mathbf{X}}^{(l+1)}={\mathbf{S}}^{(l)}{\mathbf{Z}}^{(l)}$$ \mathbf X^{(l+1)} = \mathbf S^{(l)}\mathbf Z^{(l)} $ 。

   如实验所验证的，多层 Hierarchical GNN 比单层的传统 GNN 效果更好。

   这就是 DiffPool 的核心思想。

7.3.5 Evolving GNN

1. Evolving GNN 用于对动态网络的节点进行 embedding ，即学习图序列$\{{\mathcal{G}}^{(1)},{\mathcal{G}}^{(2)},\cdots ,{\mathcal{G}}^{(T)}\}$$ \left\{\mathcal G^{(1)},\mathcal G^{(2)},\cdots,\mathcal G^{(T)}\right\} $ 中的节点 embedding。

   为了捕获动态图的演变性质evolving nature，我们将演变的链接划分为两种类型：

   • 代表大多数边的合理变化的正常演变normal evolution 。
   • 代表罕见的、异常的演变边evolving edge 的突然burst连接。

   基于这两种类型的边，动态图中所有节点的 embedding 以交错的方式interleave manner 学习。具体而言，在时间戳$t$$ t $ ：

   • 图${\mathcal{G}}^{(t)}$$ \mathcal G^{(t)} $ 上的正常链接和burst 链接通过 GraphSAGE 集成在一起，从而得到${\mathcal{G}}^{(t)}$$ \mathcal G^{(t)} $ 中每个节点$v$$ v $ 的 embedding${\overrightarrow{\mathbf{h}}}_v$$ \mathbf{\vec h}_v $ 。
   • 然后，我们通过使用变分自编码器Variational Autoencoder:VAE 以及 RNN 模型来预测${\mathcal{G}}^{(t+1)}$$ \mathcal G^{(t+1)} $ 中的 normal 链接和 burst 链接。

   该过程以迭代方式进行，从而在每个时间戳$t$$ t $ 输出每个节点$v$$ v $ 的 embedding 结果。

7.3.6 Bayessian GNN

1. Bayessian GNN 模型通过贝叶斯框架集成了两种信息源：知识图 embedding （如 symbolic）、行为图 embedding（如 relation）。具体而言，它模仿了认知科学中的人类理解过程。在该过程中，每种认知都是通过调整特定任务下的先验知识来驱动的。

   • 给定知识图$\mathcal{G}$$ \mathcal G $ 和$\mathcal{G}$$ \mathcal G $ 中的实体（节点）$v$$ v $ ， 仅考虑$\mathcal{G}$$ \mathcal G $ 本身就可以学到basic embedding${\overrightarrow{\mathbf{h}}}_v$$ \mathbf{\vec h}_v $ ，它表征了$\mathcal{G}$$ \mathcal G $ 中的先验知识。

   • 然后，根据${\overrightarrow{\mathbf{h}}}_v$$ \mathbf{\vec h}_v $ 和针对任务的矫正项${\overrightarrow{\delta }}_v$$ \vec \delta_v $ 来得到 task-specific embedding${\overrightarrow{\mathbf{z}}}_v$$ \mathbf{\vec z}_v $ 。即：

     $${\overrightarrow{\mathbf{z}}}_v\simeq f({\overrightarrow{\mathbf{h}}}_v+{\overrightarrow{\delta }}_v)$$

     其中$f(\cdot )$$ f(\cdot) $ 是一个非线性函数。

   注意，学到精确的${\overrightarrow{\delta }}_v$$ \vec \delta_v $ 和$f(\cdot )$$ f(\cdot) $ 似乎是不可行的，因为每个实体$v$$ v $ 具有不同的${\overrightarrow{\delta }}_v$$ \vec \delta_v $ 并且$f(\cdot )$$ f(\cdot) $ 函数非常复杂。为解决该问题，我们通过考虑二阶信息从而应用一个从${\overrightarrow{\mathbf{h}}}_v$$ \mathbf{\vec h}_v $ 到${\overrightarrow{\mathbf{z}}}_v$$ \mathbf{\vec z}_v $ 的生成模型。具体而言：

   • 对于每个实体$v$$ v $ ，我们从高斯分布$\mathcal{N}(\overrightarrow{\mathbf{0}},s_v^2)$$ \mathcal N\left(\mathbf{\vec 0},s_v^2\right) $ 中采样它的矫正项${\overrightarrow{\delta }}_v$$ \vec \delta_v $ ，其中$s_v$$ s_v $ 由${\overrightarrow{\mathbf{h}}}_v$$ \mathbf{\vec h}_v $ 决定。

   • 然后，对于每对实体 pair 对$(v_1,v_2)$$ (v_1,v_2) $ ，我们根据另一个高斯分布来采样$({\overrightarrow{\mathbf{z}}}_{v_1}-{\overrightarrow{\mathbf{z}}}_{v_2})$$ \left(\mathbf{\vec z}_{v_1}- \mathbf{\vec z}_{v_2}\right) $ ：

     $$\mathcal{N}(f_{\varphi }({\overrightarrow{\mathbf{h}}}_{v_1}+{\overrightarrow{\delta }}_{v_1})-f_{\varphi }({\overrightarrow{\mathbf{h}}}_{v_2}+{\overrightarrow{\delta }}_{v_2}),\text{diag}({\sigma }_{v_1}^2+{\sigma }_{v_2}^2))$$

     其中$\varphi$$ \phi $ 为$f(\cdot )$$ f(\cdot) $ 函数的可训练参数。

   • 令${\overrightarrow{\delta }}_v$$ \vec \delta_v $ 的后验均值为$\widehat{{\overrightarrow{\mu }}_v}$$ \hat{\vec\mu_v} $ ，$\hat{\varphi }$$ \hat\phi $ 为结果参数，则最终我们将${\overrightarrow{\mathbf{h}}}_v+\widehat{{\overrightarrow{\mu }}_v}$$ \mathbf{\vec h}_v+\hat{\vec\mu_v} $ 作为知识图的矫正的 embedding ，$f_{\hat{\varphi }}({\overrightarrow{\mathbf{h}}}_v+\widehat{{\overrightarrow{\mu }}_v})$$ f_{\hat\phi}\left(\mathbf{\vec h}_v+\hat{\vec\mu_v}\right) $ 为 task-specific 的矫正的 embedding 。

7.4 实验

7.4.1 平台能力评估

1. 这里我们将从storage（图构建和邻居缓存）、sampling、operator 等角度评估 AliGraph 平台中底层系统的性能。所有实验都在下表中描述的Taobao-small 和Taobao-large上进行，后者的存储规模是前者的六倍。它们都是从淘宝电商平台获取的、代表用户和 item 的子图。

   

2. 图构建：图构建的性能在图计算平台中起着核心作用。AliGraph 支持来自不同文件系统的各种原始数据。下图给出了两个数据集上图构建的时间成本和 worker 数量的关系。

   可以看到：

   • 随着 worker 数量的增加，图构建的时间明显降低。
   • AliGraph 可以在几分钟内构建大图，如Taobao-large 五分钟构建完成。

   这比大多数SOTA 的实现要快很多（例如 PowerGraph 需要几个小时）。

   

3. 缓存邻居的效果：我们研究了缓存重要节点的 k-hop 邻居的影响。在我们的缓存算法中，我们需要通过分析$D_i^{(k)}$$ D_i^{(k)} $ 和$D_o^{(k)}$$ D_o^{(k)} $ 来设置$\text{Imp}(v)$$ \text{Imp}(v) $ 的阈值。

   在实验中，我们在本地缓存所有节点的 1-hop 邻居（直接邻居），并且调整阈值从而控制2-hop 邻域的缓存。我们将阈值逐渐从 0.05 增加到 0.45 从而测试其敏感性sensitivity 和有效性effectiveness 。

   下图给出了被缓存的节点数量的百分比和阈值之间的关系。我们注意到：随着阈值的增加，被缓存的节点数量百分比在下降。当阈值小于 0.2 时，百分比下降速度较快；当阈值大于等于0.2 时，百分比相对稳定。这是因为如定理中所证明的那样，节点的 importance 服从幂律分布。

   

   为了在缓存成本和收益之间取得平衡，我们将阈值设置为 0.2，此时只需要缓存大约 20% 的额外节点。

   我们还比较了基于 importance 的缓存策略以及另外两种策略：随机策略（它随机选择一部分比例节点，然后缓存这些节点的邻域）、LRU 策略。下图说明了时间成本和缓存节点比例之间的关系。

   我们发现我们的方法相对于随机策略节省了大约 40%~50% 的时间、相对于LRU 策略节省了大约50%~60% 的时间。原因很简单：

   • 随机选择的节点不太可能被访问。
   • 由于 LRU 策略经常替换缓存的节点，因此会产生额外的成本。
   • 基于重要性的缓存节点更可能被其它节点访问到。

   

4. 采样的效果：我们以 512 的 batch size 和 20% 的cache rate 来测试采样策略的影响。下表给出了三种采样策略的时间成本。我们发现：

   • 采样方法非常有效，它们可以在几毫秒到不超过 60 毫秒内完成。
   • 采样时间随着图的大小缓慢增长。尽管 Taobao-large 是 Taobao-small 的六倍，但是这两个数据集的采样时间却非常接近。

   这些观察结果证明了我们对采样方法的实现是有效且可扩展的。

   

5. Operators 的效果：我们进一步检查了我们的 AGGREGATE 和 COMBINE 算子的影响。下表给出了这两个算子的时间成本，以及我们提出的实现方案可以加速一个量级。

   这仅仅是因为我们通过缓存策略来消除中间 embedding 向量的冗余计算。这再次证明了我们 AliGraph 平台的优越性。

   W/O Our Implementation 表示不采用我们方法的实现方式。

   

7.4.2 算法效果评估

1. 数据集：我们使用两个数据集，包括来自 Amazon 的公开数据集，以及 Taobao-small 数据集。我们没有考虑 Taobao-large 是因为考虑到一些baseline 模型的可扩展性问题。

   下表给出了数据集的统计信息。这些数据集都是属性异质图。

   • 亚马逊公共数据集包含亚马逊公司电子产品类目下的产品元数据。在图中，每个节点代表了带属性的商品，并且每条边代表同一个用户的共同查看co-view或者共同购买 co-buy 行为。
   • Taobao-small 具有两种类型的节点，即用户和商品，以及用户和商品之间的四种类型的边：点击click、添加收藏add-to-preference 、添加购物车add-to-cart 、购买buy。

   

2. baseline 方法：

   • 同质的 graph embedding 方法：DeepWalk, LINE, Node2Vec 。这些方法仅用于同质图，并且仅使用结构信息。

   • 带属性的 graph embedding 方法： ANRL。它可以通过同时捕获结构信息和属性信息来生成 embedding 。

   • 异质的 graph embedding 方法：Metapath2Vec, PMNE, MVE, MNE 。

     Metapath2Vec 只能处理具有多种节点类型的图，而其它三种方法只能处理具有多种类型边的图。PMNE 涉及三种不同的方法来扩展 Node2Vec 方法，分别表示为 PMNE-n, PMNE-r, PMNE-c。

   • GNN-based 方法：Structure2Vec, GCN, Fast-GCN, AS-GCN, GraphSAGE, HEP 。

   为公平起见，所有算法都是通过在系统上应用优化的算子来实现的。如果模型无法处理属性以及多种类型的节点，则在 embedding 中我们忽略这些信息。对于同质的、基于 GNN 的模型，我们为具有相同边类型的每个子图生成 embedding，然后将它们拼接在一起成为最终结果。

   注意，在我们的实验中，我们并未针对所有baseline 来比较我们提出的每一种 GNN 算法。这是因为每种算法的设计重点不同。

3. 评估指标：我们评估了所提出方法的效率和效果。

   • 可以通过算法的执行时间简单地评估效率。
   • 为了评估效果，我们将算法应用于链接预测任务。我们随机抽取一部分数据作为训练集，将剩余部分作为测试集。为了衡量效果，我们使用了四个常用指标，即 ROC-AUC、PR-AUC、F1-score、hit recall rate:HR Rate 。

   值得注意的是：每个指标是在不同类型的边之间取平均的。

   这里的评估结果仅供参考，因为不同实验中的指标未能统一，此外也没有进行科学的超参数调优、n-fold 交叉验证。

4. 超参数：对于所有算法，我们选择 embedding 向量的维度为 200 。

5. AHEP 算法：AHEP 算法的目标是在不牺牲太多准确率的情况下快速获得 embedding 结果。

   在下表中，我们给出了在 Taobao-small 数据集上 AHEP 和它的竞争对手的比较结果。N.A. 表示算法无法合理的时间内结束；O.O.M. 表示算法由于内存溢出而终止。

   

   在下图中，我们说明了不同算法的时间和空间成本。x 表示算法无法合理的时间内结束。显然，我们观察到：

   • 在 Taobao-small 数据集上，HEP 和 AHEP 是仅有的两种可以在合理时间和空间限制下产生结果的算法。但是，AHEP 比 HEP 要快 2~3 倍，并且比 HEP 使用更少的内存。

     从下图指标来看，AHEP 的时间与 HEP 相差无几？

   • 就结果质量而言，AHEP 的 ROC-AUC 和 F1-score 和 HEP 可比。

   

   这些实验结果说明 AHEP 可以使用更少的时间和空间来产生可比于 HEP 的结果。

6. GATNE 算法：GATNE 的目标旨在处理节点和边上都有异质信息和属性信息的图。我们在下表给出了 GATNE 和它的竞争对手的结果。显然，我们发现 GATNE 在所有指标上都优于所有现有方法。

   例如，在 Taobao-small 数据集上，GATNE 的 ROC-AUC 提升 4.6%、PR-AUC 提升 1.84%、F1-score 提升 5.08%。这仅仅是因为 GATNE 同时捕获了节点和边的异质信息和属性信息。同时，我们发现 GATNE 的训练时间随着 worker 数量增加而几乎线性减少。

   GATNE 模型在 150 个 worker 下，不到2 个小时就可以收敛。这验证了 GATNE 方法的高效性和可扩展性。

   

7. Mixture GNN：我们将 Mixture GNN 方法和 DAE、${\beta }^{\ast }\text{-VAE}$$ \beta^*\text{-VAE} $ 方法在 Taobao-small 数据集上进行对比。下表给出了将 embedding 结果应用于推荐任务的点击召回率 hit recall rate。可以看到 Mixture GNN 的 hit recall rate 提升大约2% 。

   

8. Hierarchical GNN：我们将 Hierarchical GNN 方法和 GraphSAGE 在 Taobao-small 数据集上进行比较。结果见下表所示。可以看到 F1-score 提升大约 7.5%。这表明 Hierarchical GNN 可以产生效果更好的 embedding 。

   

9. Evolving GNN：我们将 Evolving GNN 方法和其它方法在 multi-class 链接预测任务上进行比较。对比的方法包括：DeepWalk,DANE,DNE,TNE,GraphSAGE 等。这些竞争对手无法处理动态图，因此我们在动态图的每个快照上运行算法，并报告所有时间戳的平均性能。

   下表给出了 Taobao-small 数据集的比较结果。我们很容易发现在所有指标上，Evolving GNN 优于所有其它方法。

   

10. Bayesian GNN：该模型的目标是将贝叶斯方法和传统 GNN 模型相结合。我们对比了 GraphSAGE 模型。下表给出了在 Taobao-small 数据集上推荐结果的 hit recall rate。注意，我们同时考虑了商品品牌粒度以及类目粒度。显然，使用Bayesian GNN 时，hit recall rate 分别提高了 1% 到 3% 。