做设计找参考的设计网站有那些,wordpress建立网盘,简约网站模板,wordpress天气接口图神经网络 (GNN) 主要是利用神经网络处理复杂的图数据#xff0c;它将图数据转换到低维空间#xff0c;同时最大限度保留结构和属性信息#xff0c;并构造一个用于训练和推理的神经网络。在实际应用中#xff0c;为了加速 GNN 训练和新算法的快速迭代#xff0c;设计一套…图神经网络 (GNN) 主要是利用神经网络处理复杂的图数据它将图数据转换到低维空间同时最大限度保留结构和属性信息并构造一个用于训练和推理的神经网络。在实际应用中为了加速 GNN 训练和新算法的快速迭代设计一套统一的图计算框架面临着巨大的挑战。近日阿里巴巴在阿里云峰会北京站上重磅推出了大规模图神经网络平台 AliGraph本文是 AI 前线第 74 篇论文导读我们将深入了解阿里图神经网络库 AliGraph 背后的系统架构细节和内部自研的 GNN 算法原理。介绍图作为一种复杂的模型已广泛应用于各种现实应用中的建模和管理数据。典型的例子包括社交网络、物理系统、生物网络和知识图谱等。图分析探索隐藏在图数据中的潜在洞察在过去的十年引起了人们极大的关注。它们在许多领域发挥了重要的作用如节点分类、链接预测、图聚类和推荐系统等。由于传统的图分析任务经常面临着高额的计算和空间成本一种称为图嵌入(GE)的新范式为解决此类问题提供了一种高效的方法。具体地说图嵌入(GE)是将图数据转换为低维空间以最大程度保留图中结构和内容信息。之后生成的嵌入作为特征输入到下游机器学习任务中。此外结合深度学习技术通过将图嵌入(GE)与卷积神经网络(CNN)相结合提出了图神经网络(GNN)。在 CNN 中采用共享权重和多层结构来增强其学习能力。图是最典型的局部连接结构共享权值以降低计算成本多层结构是处理层次模式的关键同时可以捕获各种变化尺寸的特征。GNN 是 CNN 在图上的一种推广。因此GNN 不但拥有图嵌入(GE)的灵活性而且在有效性和鲁棒性两个方面展示了其优越性。GNN 面临的挑战当前已有大量论文贡献了大量精力在开发图嵌入(GE)和 GNN 算法方面上这些工作主要集中在没有或者有少量辅助信息的简单图上。然而大数据和复杂系统的兴起揭示了图数据上的新洞察。这是一种共识绝大多数与现实商业场景相关的图数据表现出四个特点即大规模、异构、属性化和动态。例如现在的电商的图通常包含数十亿个顶点和边这些顶点和边具有各种类型和丰富的属性并且会随着时间的推移快速演变。这些特性为嵌入和表征图数据带来了巨大的挑战如下所示GNN 的核心步骤特别针对网格结构(grid structures)进行了优化但不适用于不规则欧几里得空间中的图。因此现有的 GNN 方法无法在具有极大尺寸的真实图上进行缩放。第一个问题是如何提高大规模图上 GNN 的时间和空间效率不同类型的对象从不同的视角描述数据。它们提供了丰富的信息但是增加了将图信息映射到单个空间的难度。因此第二个问题是如何将异构信息优雅地集成到一个统一的嵌入结果中属性信息可以进一步增强嵌入结果的能力并且使图嵌入规约成为可能。在不考虑属性信息的情况下这些算法只能直推学习而忽略了预测未知实例的必要性。然而拓扑结构信息和非结构属性信息通常呈现在两个不同的空间中。因此第三个问题是如何统一保存和定义它们的信息由于 GNN 的效率较低从零开始更新结构和上下文信息然后重新计算图嵌入结果非常昂贵。因此第四个问题是如何设计动态的有效增量 GNN 方法论文贡献为了应对上述挑战大量的研究工作致力于设计高效并且有效的 GNN 方法。在表 1 中基于不同工作的关注点以及我们内部开发的模型(黄色阴影部分)我们对一系列流行的 GE 和 GNN 模型进行了分类。如图所示大多数现有方法同时集中在一个或两个属性上。然而现实世界中的商业数据通常面临更多的挑战。为了缓解这种情况在本文中我们提出了一个全面而系统的 GNN 解决方案。我们设计并实现了一个名为 AliGraph 的图神经网络平台它提供了一套对应的系统和算法来解决更实际的问题以更好地支持各种 GNN 方法和应用。AliGraph 的主要贡献包括系统在 Aligraph 的基础组件中我们构建了一个支持 GNN 算法和应用的系统。系统结构是从通用 GNN 方法中抽象出来的它由存储层、采样层和操作层组成。具体来说存储层应用了三种新技术即结构化和属性化的特定存储图划分和缓存一些重要顶点的领域来存储大规模的原始数据以满足高级操作和算法的快速数据访问要求。采样层优化了 GNN 方法中的关键采样操作。我们将抽样方法分为三类即横向抽样(TRAVERSE)、领域抽样(NEIGHBORHOOD)和反向抽样(NEGATIVE)并提出了在分布式环境下进行采样操作的无锁方法。操作层提供了 GNN 算法中两个常用的应用操作的优化实现即聚合(AGGREGATE)和组合 (COMBINE)。我们应用缓存策略来存储中间结果以加速计算过程。这些组件是共同设计和共同优化的以使整个系统有效和可扩展。算法系统提供了一个灵活的接口来设计 GNN 算法。我们的研究结果表明所有现有的 GNN 方法都可以很容易地在我们系统上实现。此外我们内部还为实际需求开发了几个新的 GNN 算法。如表 1 所示我们内部开发的方法用黄色阴影表示每种方法在处理实际问题时都更加灵活和实用。AliGraph 平台已经在阿里巴巴公司内部实际部署。实验结果从系统和算法两方面验证了其有效性和效率。如图 1 所示我们内部在 AliGraph 平台上开发的 GNN 模型将标准化评估指标提高了 4.12%-17.19%。其中数据来自阿里巴巴的电商平台淘宝我们会将此数据集(预计在 2019 年 5 月)贡献给社区以推动该领域进一步发展。预备知识在本节中表 2 总结了本文中常见的符号和标记。属性异构图为了全面描述现实世界中的商业数据实际图往往包含丰富的内容信息如顶点的多种类型、边的多种类型和属性等因此我们进一步定义属性异构图(AHG)。AHG 是一个元组 (V,ε,WTV,TE,AV,AE)其中 V,ε和 W 跟简单图具有相同的含义。T(V)V–F(V) 和 T(E)ε–F(E) 表示顶点类型和边类型的映射函数。为了确保异构性我们要求|FV|大于等于 2 和(或)|FE|大于等于 2。A(v) 和 A(E) 两个函数为每个顶点 v 和每个边 e 分配一些表征其属性的特征向量。我们将顶点 v 和边 e 的第 i 个特征向量分别表示为 x(v,i) 和 w(e,i)。AHG 的一个例子如图 2 所示它包含两种类型的顶点即 user 和 item以及连接它们的四种类型的边。动态图现实世界中图通常随着时间而演化。给定一个时间间隔 [1,T]动态图是一个系列的图 G(1),G(2),…,G(T)。对于每个 t 大于等于 1 并且小于等于 TG(T) 是一个简单图或者一个 AHG。为了便于记忆我们添加一个上标 t 来表示时间戳 t 处对象的对应状态。例如V(t) 和 E(t) 分别表示图 G(t) 的顶点集和边集合。问题定义给定一个输入图 G它是一个简单的图或者 AHG预先定义一个嵌入维度 d ∈ N其中 d |V|在尽可能保留图性质的前提下嵌入问题是将图 G 转换到 d 维空间。GNN 是一种特殊的图嵌入方法它将神经网络应用在图上学习嵌入结果。注意在本文中我们主要关注顶点级别的嵌入。也就是说对于每个顶点 v嵌入输出结果是一个 d 维度的向量h(v)。我们在第 7 节中讨论未来工作中我们还将考虑边的嵌入、子图嵌入甚至是整个图的嵌入。AliGraph 系统详解Aligraph 平台架构如图 3 所示我们设计并实现了一个底层系统(用浅蓝色方块标记)以更好地支持高级别的 GNN 算法和应用。本节将介绍该系统的详细信息在第 3.1 节中我们抽象了一个 GNN 的通用框架来解释为什么我们的系统是这样设计的第 3.2 至 3.5 介绍了系统中每个关键组件的设计和实现细节。3.1 GNN 算法框架在本小节中我们将为 GNN 算法抽象为一个通用框架。一系列经典的 GNN如 Structure2VecGCNFastGCNAS-GCN 和 GraphSAGE 可以通过在框架中实例化操作器来描述。GNN 框架的输入包含一个图 G嵌入维度 d ∈ N每个顶点 v ∈ V 的顶点特征 x(v)邻居的最大跳数 k(max)。对于每个顶点 v ∈ VGNN 的输出是一个嵌入向量h(v)将被送入下游机器学习任务如分类、链接预测等。算法 1 是对 GNN 框架的描述。在最开始顶点 v 的嵌入向量h(v)(0) 被初始化为等于输入属性向量x(v)。然后在每个 k 处每个顶点 v 聚合其邻居顶点的嵌入向量以更新自身的嵌入向量。具体地说我们应用样本函数在顶点 v 的领域集 Nb(v) 的基础上提取一个顶点的子集 S用聚合函数对所有顶点 u ∈ S 的嵌入进行聚合得到一个向量 h^(v)并将 h^(v) 与 h(v)(k-1) 通过组合函数生成嵌入向量h(v)(k) 。在处理完所有的顶点后嵌入向量被归一化。最后经过 k(max) 跳后h(v)(k(max)) 作为顶点 v 的嵌入结果 h(v) 返回。基于上面描述的 GNN 框架我们构建了 AliGraph 平台的系统架构如上一节图 3 所示。平台总体由五层组成其中三个底层构成了系统以支持算法层和应用层。在系统内部存储层对不同类型的原始数据进行组织和存储以满足高级操作和算法的快速数据访问要求。在此基础上通过算法 1我们发现三个主要的算子在各种 GNN 算法中起着重要的作用即采样、聚合和组合。其中采样操作为聚合和组合操作奠定了基础因为它直接控制了要处理的信息范围。因此我们设计了采样层来访问存储以便快速准确地生成训练样本。在此之上操作层专门优化聚合和组合函数。在系统的基础上可以在算法层构建 GNN 算法为应用层的实际任务提供服务。3.2 存储在本小节中我们将讨论如何存储和组织原始数据。存储现实世界的图的空间成本非常大常见的电子商务图可以包含数百亿个节点和数百亿个边存储成本很容易超过 10TB。图的大尺寸给有效访问带来了巨大的挑战特别是在集群的分布式环境中。为了更好地支持高级运算操作和算法我们在 AliGraph 的存储层中应用了以下三种策略。图分区Aligraph 平台建立在一个分布式环境中因此整个图被切分并分别存储在不同的 work 节点。图分区的目标是最小化交叉边(crossing edges)的数量其的端点(endpoints)分布在不同的 work 节点上。为此文献工作中提出一系列算法。我们实现了四个内置的图分区算法(1)METIS(2)顶点切割和边切割分区(3)2-D 分区(4)流式分区策略这四种算法适用于不同的环境。简而言之METIS 专门处理稀疏图顶点切割和边切割分区在稠密图上表现更好在 woker 数量固定时通常使用 2-D 分区而流式分区方法通常应用于边更新频繁的图上。用户可以根据自己的需要选择最佳的分区策略此外他们还可以将其他图分区算法实现为系统中的插件。在算法 2 中第 1-4 行给出了图分区的界面。对于每个边 e第 4 行中的通用 ASSIGN 函数将根据它的端点(endpoint)计算出 e 在哪个 woker 节点中。单独存储属性对于 AHG我们需要在每个 work 节点中存储分区图的结构和属性。图的结构信息可以简单地用邻接表存储。也就是说对于每个顶点 v我们存储它的邻居集 Nb(v)。然而对于两个顶点的属性和边不建议将它们存储在邻接表中。原因有两方面属性通常需要更多的空间。例如存储顶点 id 的空间成本最多为 8 字节而顶点上的属性可能在 0.1KB 到 1KB 之间。不同顶点和边之间的属性有很大的重叠。例如许多顶点可能具有相同的标记”man“表示其性别。因此单独存储属性更为合理。在我们的系统中我们通过构建两个索引 I(v) 和 I(e) 分别在顶点和边上存储属性。如图 4 所示在邻接表中对于每个顶点 u我们将属性 Av(u) 的索引存储在 I(v) 中。对于每个边(u,v)我们也将属性 Ae(u,v) 存储在 I(e) 中。假设 N(D) 和 N(L) 分别是邻居数量的平均值和属性长度的平均值。设 N(D) 为顶点和边上不同属性的数目。显然我们单独存储策略将空间成本从 O(n*ND*NL) 降低到 O(n*NDNA*NL)。缓存重要顶点的邻居在每个 work 节点我们进一步提出了一种局部缓存重要顶点的邻居的方法以降低通信成本。如果一个顶点 v 经常被其他顶点访问我们可以在它发生的每个分区中存储它的外部邻居。这样做可以大大降低其他顶点通过 v 访问相邻顶点的开销。但是如果 v 的邻居数目很大存储 v 的邻居的多个副本也会产生巨大的存储空间成本。为了更好地权衡我们定义了一个度量来评估每个顶点的重要性决定一个顶点是否值得缓存。假设 Di(v)(k) 和 Do(v)(k) 分别表示顶点 v 的 k-hop 入和出的邻居的数目。那么 Di(v)(k) 和 Do(v)(k) 就可以衡量缓存顶点 v 的外部邻居的收益和成本。因此顶点 v 第 k 重要性表示为 Imp(v)(k)定义如下在算法 2 中第 5-9 行给出了缓存重要顶点的邻居的过程。假设 h 表示邻居的最大深度。对于每个顶点 v我们缓存顶点 v 的 1 到 k-hop 的外部邻居顶点在 Imp(v)(k) 大于等于τk 的条件下。其中τk 是用户指定的阈值。注意将 h 设置为一个小数字(通常为 2)就足够支持一系列实际的 GNN 算法。实际上我们发现τk 不是一个敏感参数。通过实验评估将τk 设置为 0.2 左右可以在缓存成本和收益之间进行最佳的权衡。有趣的是我们发现要缓存的顶点只是整个图的一小部分。Di(v)(1) 和 Do(v)(1) 在实际图中经常服从幂律分布。也就是说在图中只有很少的顶点具有较大的出入度。基于此我们得到了以下两个定理。定理 2 表明图中只有极少数顶点是重要级别比较高的这意味着我们只需缓存少量重要顶点就可以显著降低图遍历的成本。3.3 采样回想一下GNN 算法依靠聚合邻居信息来生成每个顶点的嵌入。然而现实世界图的度的分布往往是偏度的这使得卷积运算难以操作。为了解决这个问题现有的 GNN 通常采用各种抽样策略来对大小一致的邻居子集进行抽样。由于它的重要性我们在 AliGraph 中抽象了一个特定的采样层来优化采样策略。概要形式上采样函数接受一个顶点子集 V(T) 的输入抽取一个小的子集 V(S)|V(S)|遍历(TRAVERSE)用于从整个分区图中采样一批顶点或边。邻域(NEIGHBORHOOD)将生成顶点的上下文。该顶点的上下文可以是一个或多个 hop 邻居用于对该顶点进行编码。负采样(NEGATIV)用于生成负样本以加速训练过程的收敛。实现在文献中抽样方法对提高 GNN 算法的效率和准确性起着重要的作用。在我们的系统中采样器都以插件的形式存在。这三种采样器可以实现如下对于遍历采样器他们从局部图中获取数据。对于领域采样器他们可以从本地存储获取一跳(one-hop)邻居也可以从本地缓存获取多跳(multi-hop)邻居。如果没有缓存顶点的邻居则需要从远程图服务器调用。当获取一批顶点的上下文时我们首先将顶点划分为子批并从相应的图服务器上获得返回结果后每个子批的上下文将被拼接在一起。负采样器通常从本地图服务器生成样本。对于某些特殊情况可能需要从其他图服务器进行负采样。负采样在算法上是灵活的我们不需要批量调用所有的图服务器。总之一个典型的采样阶段可以实现为如图 5 所示。我们可以通过采用动态权重的几种有效采样策略来加速训练。我们在采样器的反向计算中实现更新操作就像反向传播的运算一样。所以当需要更新时我们应该做的是为采样器注册一个梯度函数。更新模式是同步还是异步由训练算法决定。到目前为止读取和更新都将在内存中的图存储上进行这可能导致性能下降。根据邻居需要该图由源顶点分割。在此基础上我们将图服务器上的顶点分组。每个组都将与一个请求流桶相关其中的操作(包括读取和更新)都与该组中的顶点有关。桶是一个无锁队列如图 6 所示我们将每个 bucket 绑定到一个 CPU 内核然后桶中的每个操作都按顺序处理不加锁进一步提高了系统的效率。3.4 运算符概要采样后输出的数据被对齐处理起来就会容易很多。在采样器上我们需要一些类似 GNN 的运算符来使用它们。在我们的系统中我们抽象了两种运算符即聚合和组合。他们的作用如下聚合收集每个顶点的邻居信息以生成统一的结果。例如算法 1 中的聚合算法将一系列向量 h(u) 映射到单个向量 h^(v)其中 u 属于 v 的采样邻居节点。h^(v) 是一个中间结果为了进一步生成 h(k)(v)。聚合函数从周围邻居收集信息它可以用作卷积操作。各种聚合方法被应用在不同的 GNN 中例如元素平均值、最大池化神经网络和 LSTM。组合 负责如何使用顶点的邻居来描述顶点。在算法 1 中组合函数映射两个向量 h(v)(k-1) 和 h^(v) 为一个向量 h(v)(k)。组合函数可以将前一跳和领域的信息集成到一个统一的空间中。通常现有的 GNN 方法中h(v)(k-1) 和h^(u) 求和然后输入到神经网络中。实现采样器和类似 GNN 的运算符不仅可以前向运算还可以反向运算以便更新参数使整个模型成为端到端的训练网络。考虑到图数据的特点为了获得更好的性能可以考虑大量的优化。一个典型的运算符由前向和后向的运算组成以便参与到深层网络的训练中。用户可以在基于运算符的基础上快速构建 GNN 算法。为了进一步加速这两个算子的运算我们通过应用策略将中间结果向量h(v)(k) 缓存。在训练过程中的每个 mini-batch 中所有顶点我们可以共享采样邻居集合。同样在同一个 mini-batch 中对于所有的 k1 且 kk(max)我们也可以共享向量h(v)(k)。为此我们将 k(max) 个h^v(1)、h^v(2)、…h^v(kmax) 向量存储为 mini-batch 中所有顶点的最新向量。在聚合函数中我们利用向量h^v(1)、h^v(2)、…h^v(kmax) 来获取h^(v)。然后我们通过应用组合函数计算h^(v) 和h(v)(k-1) 来获得h^(v)(k)。最后存储的向量h^(k) 通过h^(v)(k) 更新。通过这种策略运算符的计算成本可以大大减小。方法论在系统的基础上我们来讨论算法的设计。我们的研究结果表明现有的 GNN 在 AliGraph 上非常容易创建。此外我们还提出了一系列新的 GNN 算法以解决第 1 节中总结的真实世界的图数据嵌入的四个新挑战。它们在 AliGraph 平台算法层以插件形式供用户使用。4.1 GNN 最佳实践由于 AliGraph 平台是基于通用 GNN 算法抽象出来的因此现有的 GNN 可以很容易地在这个平台上实现。具体来说表 1 中列出的 GNN 都可以按照算法 1 中的框架构建在 AliGraph 中。这里我们以 GraphSAGE 为例进行简要介绍其他 GNN 也可以用类似的方式实现。对于 GraphSAGE它应用简单的逐节点采样从每个顶点的相邻集中提取一个子集。显然这一采样策略通过我们的采样运算符很容易就能实现。然后我们需要在算法 1 中实例化聚合和组合函数。GraphSAGE 可以在第 4 行的聚合函数中应用加权元素平均。此外也可以使用其他更复杂的函数如 maxpooling 神经网络和 LSTM 神经网络。在其他的 GNN 方法中如 GCN、FastGCN 和 AS-GCN我们可以在抽样、聚合和组合上替换不同的策略。4.2 阿里内部开发的 GNNs我们内部开发的 GNN 专注于不同方面例如采样(AHEP)、复合边(GATNE)、多模态(Mixture GNN)、层次(Hierarchical GNN)、动态(Evolving GNN)和多源信息(Bayesian GNN)。AHEP 算法该算法是为了减轻传统嵌入传播(EP)算法在异构网络(HEP)上的繁重计算和存储成本而设计的。HEP 遵循 GNN 的总体框架对 AHG 进行了细微修改。在 HEP 中所有的顶点嵌入都是以迭代的方式生成的。在第 k 次 hop 中对于每个顶点 v 和每个节点类型 cc 中 v 的所有邻居 u传播其嵌入 h(u,c) 给 v 来重构一个 h^(v,c) 嵌入。然后跨所有节点类型连接 h^(v,c) 嵌入来更新 v 的嵌入。但是在 AHEP(HEP 用自适应抽样)中我们只对重要的邻居进行抽样而不考虑所有邻居。我们设计了一个度量通过结合每个顶点的结构信息和特征来评估其重要性。之后根据相应的概率分布分别对不同类型的所有邻居进行采样。我们仔细设计了概率分布以最小化抽样方差。在特定任务中为了优化 AHEP 算法损失函数一般可以描述为其中L(SL) 是批处理中监督学习的损失L(EP) 是批处理采样时的嵌入传播损失Ω(Θ) 是所有可训练参数的正则化α, β是两个超参数。根据第 5 节的实验结果验证AHEP 的运行速度比 HEP 快得多同时达到了相当的精度。GATNE 算法该算法用于处理顶点和边上具有异构和属性信息的图。为了解决上述问题我们提出了一种既能捕获丰富属性信息又能利用不同节点类型的多重拓扑结构新方法即通用的属性多重异构网络嵌入简称 GATNE。每个顶点的整体嵌入结果由三部分组成通用嵌入、特定嵌入和属性嵌入分别对应描述结构信息、异构信息和属性信息。对于每个顶点 v 和任何节点类型 c通用的嵌入 b(v) 和属性嵌入 f(v) 保持相同。设 t 为可调超参数当 1 ≤ t^ ≤ t 时 g(v,t^) 是元 - 特定嵌入。特定嵌入是通过连接所有的 g(v,t^) 得到。然后对于每种类型 c所有的 h(v,c) 嵌入如下其中α©和β©是反映特定嵌入和属性嵌入重要性的两个可调参数利用注意力机制计算系数矩阵 a©M© and D 是两个可训练的变化矩阵。最终嵌入结果 h(v) 可以通过连接所有的 h(v,c)。嵌入可以应用类似于随机游走的方法学习。具体来说在随机游走中给定 c 类型的顶点 v 和窗口大小 p设 v(-p),v(-p1),…v,v(1),…v§表示其上下文。我们需要最小化 negative log-likelihoodMixture GNN 算法该模型是一个混合的 GNN 模型用于处理多模态的异构图。在这个模型中我们扩展了异构图上的 skip-gram 模型以适应异构图上的多义场景。在传统的 skip-gram 模型中我们试图寻找参数为θ的图嵌入通过最大化似然函数其中Nb(v) 表示 v 的邻居Prθ(u|v) 表示 softmax 函数在我们对异构图上的设置中每个节点有多感知。为了区分它们假设 P 是节点感知的已知分布。我们将目标函数改写为此时很难结合负采样方法直接优化等式(6)。或者我们推导出一个新的方程(6)的下界 L(low)并尝试最大化 L(low)。我们发现下界 L(low) 可以用负采样近似。因此在现有的工作中如 Deepwalk 和 node2vec 中通过稍微修改采样过程可以很容易地实现训练过程。层次 GNN 算法当前的 GNN 方法本质上是扁平的并不学习图的层次表征。这个限制对于明确研究不同类型用户行为的相似性问题时尤其明显。层次 GNN 算法模型组合了层次结构增强了 GNN 的表达能力。假设 H(k) 表示在 GNN 的 k 步之后计算节点的嵌入矩阵。A 是图 G 的邻接矩阵在算法 1 中传统的 GNN 迭代学习 H(k) 通过组合 H(k-1)、A 和一些可训练的参数θ(k)。开始我们设置 H(0)X其中 X 表示节点特征的矩阵。在我们的层次 GNN 中我们以层级方式学习嵌入结果。具体来说让 A(l) 和 X(l) 分别表示第 l 层中的邻接矩阵和节点特征矩阵。通过输入 A(l) 和 X(l) 到单层 GNN 来学习第 l 层的节点嵌入向量结果矩阵 Z(l)。在此之后我们对图中的一些顶点进行聚类并将邻接矩阵 A(l) 更新为 A(l1)。设 S(l) 表示在第 l 层中的可学习的赋值矩阵。S(l) 中的每一行和每一列分别对应第 l 层和 (l1) 层中的一个聚类。S(l) 可以通过在另外一个 pooling GNN 的 A(l) 和 X(l) 上应用 softmax 函数获得。利用 Z(l) 和 S(l)我们可以为第 l1 层获得一个新的粗粒度邻接矩阵 A(l1)S(l)(T)*A(l)*S(l) 和一个新的特征矩阵 X(l1)S(l)(T)*Z(l)。如第 5 节所验证的多层的层次 GNN 比单层传统 GNN 更有效。动态演化的(Evolving)GNN 算法这个模型用于在动态网络设置中的顶点嵌入。我们的目标是学习图序列(G(1),G(2),G(3),…G(T))中顶点的表征。为了捕获动态图的演化性质我们将演化链接分为两种类型(1)正常演化代表边的大部分合理的变化(2)突发链接代表稀有和异常的边演化。在此基础上以交错方式学习动态图中的所有顶点的嵌入。在时间戳 t 处图 G(t) 上找到的正常和突发的链接与 GraphSAGE 模型集成以生成 G(t) 中每个顶点 v 的嵌入结果 h(v)。然后我们利用变分自动编码器和 RNN 模型对图 G(t1) 上的正常和突发信息进行预测。该过程在迭代中执行以在每个时间戳 t 输出每个顶点 v 的嵌入结果。贝叶斯 GNN 算法该模型通过贝叶斯框架集成了两种信息源即知识图谱嵌入或行为图嵌入。它模拟了认知科学中人类的理解过程在这个过程中每一种认知都是通过调整特定任务下的先验知识来驱动的。具体来说给定一个知识图 G 和 G 中的一个实体(顶点)v它的基础嵌入 h(v) 是通过纯粹考虑 G 本身来学习的它描述了 G 中的先验知识然后根据 hv 生成一个特定任务下的嵌入 z(v)并对该任务生成一个修正项δv也就是其中f 是一个非线性函数。注意学习精确的δv 和 f 似乎是不可行的因为实体 v 有不同的δvf 函数非常复杂。为了处理这个函数通过考虑二阶信息我们应用生成模型从 h(v) 到 z(v)。具体地说对于每个实体 v我们从一个高斯分布 N(0,s(v)(2)) 中采样出修正变量δv。其中s(v) 由 h(v) 的相关系数决定。然后对于每个 v1 和 v2 实体对我们从另外一个高斯分布中采样 z(v1)-z(v2)其中φ表示函数 f 可训练的参数。δv 的后验均值是 u^(v)φ^ 是结果参数。我们应用 h(v)u^(v) 作为修正的知识图谱的嵌入fφ(h(v)u^(v)) 作为修正的特定任务的嵌入。实验5.1 系统评估在本小节中我们从存储、采样、运算的角度评估 AliGraph 平台中底层系统的性能(图构建和缓存邻居节点)。所有实验都在两个数据集上进行的如表 3 所示Taobao-small 和 Taobao-large后者的存储容量是前者的六倍之大。它们都代表了淘宝电子商务平台中用户和物品的子图。图构建图构建的性能在图计算平台中起着核心作用。AliGraph 支持多种来自不同文件系统的各种原始数据无论是否分区。图 7 显示了在两个数据集上 worker 节点构建图所消耗的时间成本。我们观察到以下两个结果(1)随着 woker 节点数量增加构建图的时间明显缩短了(2)AliGraph 可以在几分钟内构建大型图如Taobao-large 花费 5 分钟。这比通常需要几个小时(比如PowerGraph)构建图的大多数技术高效得多。缓存邻居的有效性我们研究了缓存重要顶点的 k 跳(k-hop)邻居的效果。在我们的缓存算法中为了分析 Di(k) 和 Dv(k)我们为方程 1 中的 Imp(v) 设置阈值。在实验中我们局部缓存所有顶点的一跳(1-hop)邻居并改变控制缓存二跳(2-hop)邻居的阈值。我们逐渐将阈值从 0.05 增加到 0.45以测试其敏感性和有效性。图 8 说明了缓存顶点百分比和阈值的情况。当阈值小于 0.2 时缓存顶点百分比急剧下降之后变得相对稳定。这是因为顶点的重要性服从幂率分布正如我们定理 2 中证明那样。为了在缓存成本和收益之前进行良好的权衡我们根据图 9 将阈值设置为 0.2并且只需要缓存大约 20% 的额外顶点。我们还比较了基于重要性的缓存策略和另外两种策略即随机策略(缓存随机选择一小部分顶点的邻居)和 LRU 替换策略。图 9 说明了时间成本和缓存顶点百分比的关系。实验结果表明我们的随机策略方法节省了大约 40%-50% 的时间成本LRU 替换策略节省了大约 50%-60% 的时间成本。这仅仅是因为(1)随机选择的顶点不太可能被访问(2)LRU 策略由于经常替换缓存顶点而增加了额外的成本。然而我们基于重要性的缓存顶点更容易被其他顶点访问。抽样的影响我们测试了采样优化实现的影响。表 4 显示了三种抽样方法的时间成本其中批处理大小 512、缓存率为 20%。我们发现(1)采样方法非常有效完成时间在几毫秒到不到 60 毫秒之间(2)采样时间随着图大小缓慢增长虽然 Taobao-large 是 Taobao-small 的六倍但是两个数据集的采样时间却相当接近。这些观察结果验证了我们的采样方法的实现是有效且可扩展的。算子的影响我们进一步研究了我们在聚合、组合算子上实现的影响。表 5 显示了这两个运算符的时间成本在我们提出的实现中时间成本可以加快一个数量级。这是因为我们应用了缓存策略来消除中间嵌入向量的冗余计算这再次证明了 AliGraph 平台的优点。5.2 算法评估5.2.1 实验设置数据集我们在实验中使用了两个数据集包括一个来自 Amazon 和 Taobao-small 的公共数据集。数据集的统计数据汇总在表 6 中他们两个都是 AHG。Amazon 公共数据集是从亚马逊电子产品类别下的产品元数据抽取的。在这个图中每个顶点代表一个具有属性的产品每个边连接两个由同一个用户共同查看或者共同购买的产品。它有两个顶点即 user 和 item以及 user 和 item 之间的四种边类型即点击、添加到 preference、添加到购物车和购买行为。算法我们实现了所有在本文中提出的算法。为了进行比较我们还实现了一些不同类别的有代表性的图嵌入算法如下所示C1Homogeneous GE 方法。比较的方法包括DeepWalk、LINE 和 Node2Vec。这些方法只能应用于纯结构信息的普通图。C2带属性的 GE 方法。 比较方法包括 ANRL它可以生成嵌入捕获结构和属性信息。C3异构(Heterogeneous)的 GE 方法。比较方法包括 Methpath2Vec、PMNE、MVE 和 MNE。MethPath2Vec 只能处理具有多种类型顶点的图而其他三种方法只能处理具有多种类型边的图。PMNE 包括三种不同的方法来扩展 Node2Vec 方法分别表示为 PMNE-nPMNE-r 和 PMNE-c。C4基于 GNN 的方法。比较方法包括 Structural2Vec、GCN、Fast-GCN、AS-GCN、GraphSAGE 和 HEP。为了公平起见所有的算法都通过在我们的系统上应用优化的运算符来实现。如果一个方法不能处理属性或多个类型的顶点我们在嵌入过程中会忽略这些信息。我们为具有相同边类型的每个子图生成嵌入并将它们连接在一起作为基于异构的 GNN 的最终结果。请注意在我们的检查中我们不会比较我们提出的每个 GNN 算法。因为每个算法设计的侧重点不同。我们将详细介绍每个 GNN 算法的竞争对手报告其实验结果。指标我们评估了所提出方法的效率和有效性。该算法的执行时间可以用于简单地衡量效率。为了测量有效性我们将算法应用于广泛采用的链接预测任务在推荐等现实场景中发挥着重要作用。我们随机抽取一部分数据作为训练集其余部分作为测试集。为了测量结果的质量我们使用了四个常用的指标即 ROC 曲线下的面积(ROC-AUC)、PR 曲线(PR-AUC)、F1 分数和命中召回率(HR Rate)。值得注意的是每个度量在不同类型的边之间取平均值。参数对于所有的算法我们设置嵌入向量的维度 d 为 20。5.2.1 实验结果AHEP 算法AHEP 算法的目标是快速获得嵌入结果同时不会牺牲太多的精度。在表 7 中我们展示了在 Taobao-small 数据集上AHEP 算法和其他算法比较的结果。在图 10 中我们说明了不同算法的时间和空间成本。显然我们有以下观察(1)在 Taobao-small 数据集上HEP 和 AHEP 是唯一两种能够在合理的时间和空间限制下产生结果的算法。然而AHEP 比 HEP 快 2-3 倍而且比 HEP 占用的内存要小的多。(2)在结果质量方面AHEP 的 ROC-AUC 和 F1 评分与 HEP 相当。实验结果表明利用最短的时间和空间AHEP 可以产生与 HEP 相似的结果。GATNE 算法GATNE 的目标是处理具有顶点和边的异构和属性信息的图。我们将 GATNE 算法以及其竞争对手的比较结果显示在表 8 中。显然我们发现 GATNE 在所有度量指标方面都优于现有的方法。例如在 Taobao-small 数据集上GATNE 将 ROC-AUC、PR-AUC 和 F1 得分分别提高了 4.6%、1.84% 和 5.08%。这仅仅是因为 GATNE 同时捕获顶点和边的异构信息以及属性信息。同时我们发现 GATNE 的训练时间与 woker 节点数呈现线性关系。GATNE 模型收敛在不到两个小时内在 150 个节点的分布式环境下。验证了 GATNE 方法的高效性和可扩展性。Mixture GNN我们比较了 Mixture GNN、DAE 和β*-VAE 方法。将嵌入结果应用于推荐任务的命中率如表 9 所示。注意通过应用我们的模型命中率提高了 2% 左右。同样这种改进也在大型网络中有重要贡献。层次 GNN我们比较了层次 GNN 和 GraphSAGE。结果如表 10 所示。分数显著提高 7.5% 左右。这表明我们的层次 GNN 可以产生更具前景的嵌入结果。Evolving GNN我们比较了在多分类链接预测任务中 Evolving GNN 和其他方法。竞争对手包括具有代表性的 DeepWalk、DANE 、DNE 、TNE 和 GraphSAGE。这些竞争算法无法处理动态图因此我们在动态图的每个快照上运行该算法并报告所有时间戳的平均性能。Taobao-small 数据集的比较结果如表 11 所示。我们很容易发现在所有的度量上Evolving GNN 优于所有其他方法。例如在剧烈演变情况下Evolving GNN 将微观(micro)和宏观 (macro)F1 得分提高了 4.2% 和 3.6%。这仅仅是因为我们提出的方法能够更好地捕获真实网络的动态变化从而产生更具前景的结果。贝叶斯 GNN该模型的目标是将贝叶斯方法和传统 GNN 模型相结合。我们使用 GraphSAGE 作为基准线并将结果与包含和不包含贝叶斯模型的结果进行比较。表 12 中给出了推荐结果的命中率。注意我们同时考虑商品品牌和类别的粒度。显然在应用贝叶斯模型时命中召回率分别增加了 1% 到 3%。请注意这种改进可以为我们包含 900 万个 item 的网络带来显著的好处。相关工作在本节中我们简要回顾了 GE 和 GNN 方法的最佳性能。根据第 1 节总结的四个挑战我们将现有方法分类如下。同质性DeepWalk 首先通过随机游走在图上生成一个语料库然后在语料库上训练一个 skip-gram 模型。LINE 通过保留一阶和二阶近邻来学习节点的表征。NetMF 是一个统一的矩阵因式分解框架用于理论上理解和改进 DeepWalk 和 LINE。Node2Vec 增加了两个参数来控制随机游走过程而 SDNE 则提出了一种 structure-preserving 的嵌入方法。GCN 使用卷积运算合并邻居的特征表征。GraphSAGE 提供一种将结构特征信息与节点特征相结合的归纳方法。异构性对于具有多种顶点和(或)边的图PMNE 提出了三种方法将复合边网络投影到连续向量空间。MVE 使用注意力机制将具有多视图的网络嵌入到协同后的单个向量表征中。MNE 为每个节点使用一个通用嵌入和多个不同边类型的附加嵌入这些嵌入由统一的网络嵌入模型共同学习。Mvn2Vec 通过同时保存和协作建模来探索嵌入结果。HNE 将内容和拓扑结构共同考虑为统一的向量表征。PTE 利用标记信息构建大规模异构文本网络并将其嵌入低位空间。Metapath2Vec 和 HERec 将基于元路径的随机游走形式化以构造节点的异构领域然后利用 skip-gram 模型进行节点嵌入。属性属性网络嵌入的目的是寻找低维向量表征以 保留拓扑和属性信息。TADW 通过矩阵分解将顶点的文本特征融入到网络表征学习中。LANE 在保留相关性的同时平稳地将标签信息整合到属性网络潜入中。AANE 使联合学习过程能够以分布式方式完成从而加速属性网络嵌入。SNE 提出了一种通过捕获结构邻近度和属性邻近度来嵌入社交网络的通用框架。DANE 可以捕获高的非线性并在拓扑结构和节点属性中保留各种近似性。ANRL 使用邻居增强自编码器对节点属性信息进行建模并使用 skip-gram 模型捕获网络结构。动态的实际上一些静态方法也可以通过基于静态嵌入更新新的顶点来处理动态网络。考虑到新的顶点对原始网络的影响扩展了 skip-gram 方法来更新原始顶点的嵌入。“Dynamic network embedding by modeling triadic closure process”重点捕获学习网络嵌入的三元结构属性。考虑网络结构和节点属性“Attributed network embedding for learning in a dynamicenvironment”着重于更新 streaming 网络的特征向量和特征值。结论我们从目前实际的图数据问题中总结出了四个挑战即大规模、异构、属性和动态。基于这些挑战我们设计并实现了 AliGraph 平台它为解决更多实际问题提供了系统和算法。今后我们重点关注但不限于以下几个方面边级别和子图级别嵌入的 GNN更多的执行优化例如将计算变量与图数据在 GNN 中共同定位以减少跨网络流量引入新的梯度优化方法利用 GNN 的特点加速分布式训练而不造成精度损失在多 GPU 架构中更好地分配 work 节点Early-stop 机制有助于在没有预期结果的情况下提前终止训练任务Auto-ML有助于从各种 GNN 中选择最佳方法。论文原文链接https://arxiv.org/pdf/1902.08730.pdf公开数据集平台https://tianchi.aliyun.com/dataset/dataDetail?dataId9716
