GNN

摘要 大规模图网络的节点嵌入对很多任务有很重要的作用，比如在推荐系统领域、蛋白质网络研究领域等。然而，目前大多数节点嵌入方法要求所有节点都在训练集中，且难以泛化到未见过的新节点上，这些方法称为直推式（transductive）方法。本文提出了一个归纳式（inductive）的节点嵌入方法GraphSAGE，它利用节点属性生成未见过节点的embedding。GraphSAGE并不直接训练节点embedding本身，而是训练生成embedding的函数，这个函数通过采样并聚合节点邻居的特征来生成自身节点的embedding。在三个数据集上的实验结果表明，GraphSAGE的性能显著强于其他方法。 简介 Graph embedding很重要，然而大多数工作只能在一个固定的图上学习节点embedding，无法泛化到训练期间未见过的节点上，是直推式（transductive）方法。 但是，现实世界中的图网络往往是动态变化的，比如社交网络、用户和商品的交互网络、蛋白质相互作用网络等。归纳式（inductive）的方法训练完之后，可以泛化到未见过的节点上，甚至泛化到未见过的图上，比如在蛋白质相互作用研究中，使用某个器官的蛋白质网络训练的模型，可以泛化到另一个器官的蛋白质网络中，只要这两个网络中的蛋白质的属性有相同的格式。 本文的GraphSAGE就是一种归纳式（inductive）的方法，它的特点如下： 利用节点的属性特征（node features）生成节点的embedding，所以学习的是embedding生成函数，而不是embedding本身 因此，只要未见过节点的属性值域与训练集中的属性值域相同，就可以将embedding生成函数泛化到未见过的节点上，从而生成未见过节点的embedding GraphSAGE在生成embedding时，聚合了邻居的属性信息，所以既学到了邻居的拓扑结构，又学到了邻居的属性分布，一举两得 虽然GraphSAGE主要针对属性图，但由于它仍然利用了结构信息，所以也适用于无属性的图 GraphSAGE既可以用在有监督任务中，也可以用在无监督任务中 方法 GraphSAGE的全称是Graph SAmple and aggreGatE，所以其核心步骤就两步，采样（sample）与聚合（aggregate）。 如下图Fig1所示，先形象地理解一下GraphSAGE的过程。例如为了得到图中红色节点（目标节点target node）的embedding，第1步采样时，k=1采样的是其1-hop邻居；第2步采样时，k=2采样的是其2-hop的邻居。采样的过程是从由内到外进行的。 采样完成之后，开始聚合，聚合的过程是从外到内聚合的，即先聚合2-hop邻居到1-hop邻居上，再聚合1-hop邻居到目标节点上。由此我们得到的目标节点的embedding。 最后参数优化与损失函数有关，利用节点embedding，可以构造有监督或者无监督的loss，然后梯度下降进行优化。 接下来我们来详细看一下其伪代码，正文Algorithm 1给出了所有节点的前向过程，但是当图很大的时候，往往采用mini-batch的方式，我们直接看mini-batch的前向算法吧，如上图Algorithm 2所示。 大的流程仍然是采样与聚合，其中第1~7行为采样过程，第8~16行为聚合过程。 采样 以下图为例，假设网络层数\(K=3\)，当前batch中只有红色节点。初始的时候令\(B^3\)只包含红色节点；采样的时候是从\(B^3\)到\(B^0\)进行的。\(B^2\)采样的是\(B^3\)的1-hop邻居，同时加上\(B^3\)本身，所以\(B^2\)包括图中的绿色+红色节点。类似的，\(B^1\)采样的是\(B^2\)的1-hop邻居，同时加上\(B^2\)本身，所以\(B^1\)包括图中的蓝色+绿色+红色节点。类似的，\(B^0\)包括图中的黄色+蓝色+绿色+红色节点。 其实在采样的时候，每个节点都只采样它自己的1-hop邻居，但是由于存在第5行求并集的操作，所以对于初始的红色节点来说，最终采样到的\(B^0\)包含了其最多\(K=3\)-hop的邻居。 另外一个值得提醒的是，采样的过程是从\(B^3\)到\(B^0\)降序进行的，主要是为方便后续聚合的时候从从\(B^0\)到\(B^3\)进行。 采样的目的有两个： 不同节点的邻居数目相差很大，如果不进行采样的话，热门节点的数目会非常多，导致训练有偏，而且不同batch的样本量大小也相差很大，不方便预估每个batch的训练时间 采样之后，每个batch训练时只跟当前采样的\(B^0\)里面的节点有关，网络参数更新时也只需要更新与\(B^0\)相关的参数，而不需要更新所有参数，可以大幅缩减训练时间 聚合 聚合操作就是聚合邻居的embedding，来更新自身的embedding。聚合与采样类似，也是分层进行的，只不过方向和采样相反。比如\(K=3\)时，需要聚合3层，每层又需要聚合多次。下图展示了\(k=1,2,3\)时的聚合情况。 以\(k=1\)为例，此时，所有在\(B^1\)里的节点都是目标节点，都需要聚合邻居的信息，包括如下聚合过程： 黄色节点→蓝色节点 蓝色节点→绿色节点 绿色节点→红色节点 上面→表示聚合方向。注意所有→左边的embedding都是\(h^{k-1=0}\)的embedding，即上一个循环时的embedding。比如第2步用的蓝色节点并不是第1步聚合得到的蓝色节点，而是上一个循环得到的蓝色节点（上一个循环为初始\(h^0\)）。所以，上述三次聚合互不影响，可以并行进行。 当所有节点聚合完成之后，→右边的embedding变成了\(h^{k=1}\)的embedding，作为下一层\(k=2\)时的左边embedding。 如上图所示，当\(k=2\)时，最外层的黄色节点已经不参与计算了，此时包括如下聚合过程： 蓝色节点→绿色节点 绿色节点→红色节点 虽然绿色节点还是只聚合其直接邻居蓝色节点，但是由于蓝色节点在上一轮中聚合了黄色节点，所以绿色节点在这一轮中能够通过蓝色节点间接聚合到黄色节点，即绿色节点聚合到了其2-hop邻居。类似的，红色节点也聚合到了其2-hop邻居即蓝色节点。 当\(k=3\)时，蓝色节点也已经不参与计算了，此时包括如下聚合过程： 绿色节点→红色节点 根据上面的分析，红色节点能间接聚合到其3-hop邻居，即最远聚合到黄色节点的信息。 三层聚合结束之后，最终我们得到了红色节点的embedding。可以看到，为了得到红色这一个节点的embedding，如果网络层数为3的话，其最终聚合了三层节点的信息。在GraphSAGE中需要设置采样参数，例如fanouts=[20,10,5]，就表示第一层每个节点采样20个邻居，第二层每个节点采样10个邻居，第三层每个节点采样5个邻居。这样每个节点最终聚合了20*10*5=1000个邻居节点的信息。可见，邻居聚合的威力很大，只需要少数几层就可以聚合大量邻居节点。GraphSAGE文中说只需要两层，fanouts=[25,10]就取得了很好的效果。 聚合函数 上述操作只是把红色节点的邻居聚合到一起了，相当于收集到了红色节点的邻居，怎样根据邻居embedding来生成自身节点的embedding呢，这就需要聚合函数来完成了。 有关聚合函数的描述，我觉得原文有点描述不清楚，我这里总结一下，可分为四种聚合函数，如下图所示： 所有聚合函数都有两步，第一步是聚合邻居信息，第二步是进行非线性激活，差别在于邻居的定义，以及聚合操作。 Mean aggregator是最简单的聚合操作，即把邻居（不包含v本身）求均值，然后和自身concat起来，最后非线性激活。 GCN aggregator和mean aggregator非常像，它们的区别是，GCN aggregator在聚合邻居的时候，也聚合了它本身，即GCN认为v也是v的邻居之一（相当于有自回路）。但是它在非线性激活的时候，没有和自身上一个状态concat，而这个caoncat操作类似ResNet中的短路原则，可以避免长距离信息丢失的问题。因此，GCN aggregator的网络不能太深，而且往往效果不如Mean aggregator。 Pooling aggregator对所有邻居先过一个MLP（公式中的\(W_{pool}\)和\(b_{pool}\)），然后进行element-wise的max pooling，接着把pooling结果和自身concat，最后非线性激活。作者测试发现这里使用max pooling和mean pooling的效果相当。 ...

前言 这节课主要介绍传统的图机器学习方法。传统方法主要分为两步，第一步人工设计特征，第二步使用各种机器学习方法进行预测。因此，特征工程在传统图机器学习方法中有很重要的地位。本节课主要介绍图上的特征工程方法，分别介绍针对节点（node-level）、边（link-level）和图（graph-level）的特征工程方法。 针对节点的特征工程方法 节点水平的特征主要有四类，下面分别介绍。 节点的度（node degree） 节点的中心性（node centrality） 节点的集聚系数（clustering coefficient） 非同构子图（graphlets） 节点的度 节点的度，这个最好理解了，即该节点的所连边的数目，或者说该节点的直接邻居数目。如果是有向图，还分为出度和入度。 节点的度的不足是，没有考虑到不同邻居的重要性不同，只要有一个邻居，度就加1，即认为所有邻居的重要性是相同的。 节点的中心性 节点的中心性这个特征考虑了节点的重要性，有多个中心性指标，如下： 特征向量中心性（Engienvector centrality） 中介中心性（Betweenness centrality） 接近中心性（Closeness centrality） 特征向量中心性的定义是：节点v的重要性=v的邻居的重要性的和，除以λ进行归一化。 根据定义可知，特征向量中心性是递归定义的，写成矩阵形式就是Ac=λc，特征向量c的每个维度就是每个顶点的特征向量中心性的值。 忘记了怎么求特征值和特征向量的同学可以复习一下：https://blog.csdn.net/Junerror/article/details/80222540。 算出最大特征值λ_max对应的特征向量c_max之后，节点v的特征向量中心性就是向量c_max的第v个分量。具体看维基百科：https://zh.wikipedia.org/zh-cn/%E7%89%B9%E5%BE%81%E5%90%91%E9%87%8F%E4%B8%AD%E5%BF%83%E6%80%A7。 如果说特征向量中心性有点难以理解和计算的话，接下来介绍的中介中心性和接近中心性就很好理解了。 中介中心性，顾名思义，就是节点作为中介（枢纽）的重要性。计算方法是，所有节点对(s,t)的最短路径穿过节点v的比例。(s,t)的最短路径可以认为是(s,t)之间的交通要道，如果这条路径穿过节点v的话，说明v在交通要道上，所以v是很重要的中介枢纽。具体计算方法见下图，即v在所有(s,t)的最短路径中出现的比例。 接近中心性也很好理解，就是节点v与图中其他节点的接近程度。计算方法是：v到其他节点的最短路径之和的倒数。如果一个节点越中心，则它到其他节点的最短路径越短，则接近中心性越大。比如下图的D就比A更中心，所以D的接近中心性更大。 节点的集聚系数 集聚系数是个很有意思的指标，它描述的不是节点本身，而是节点的邻居的集聚程度。其计算公式如下图所示，分子是v的邻居形成的边的数目，分母是v的邻居理论上能形成最多的边的数目，分母用来归一化的。 集聚系数=1表示v的邻居都两两认识，=0表示v的邻居两两都不认识。集聚系数越大，表示邻居聚集程度越高，越有可能是一个紧密的团体。 非同构子图 非同构子图的英文定义是：rooted connected non-isomorphic subgraphs，很准确啊，有根的连通的非同构子图。比如下图中3个节点的graphlets有3个，G1中目标节点（根节点）在1和2形成的子图是不一样的（不同构），而在G2中3个点的位置是等价的，所以G2只有1个graphlet，加起来就是3个graphelts。从2个节点到5个节点，能形成的graphlets总数是73个。 Graphlet Degree Vector（GDV）是基于graphlets的特征，它计算以目标节点v为根，能形成的不同graphlets的数目向量，相当于描述了v周围不同子结构的子图个数。如下子图3所示，红色节点v的2-3个节点的GDV向量是[2,1,0,2]。如果统计节点v周围的2~5个节点（包含v自己）形成的graphlets的数目，则会得到一个维度为73的GDV向量，相当于节点v的一个特征向量。这个73维度的特征向量是节点v周围四跳（4-hop）的结构信息。 小结一下节点的特征大概可以分成两类，一类是基于重要性的特征，例如节点的度、节点的中心性；另一类是基于结构的特征，例如节点的度、集聚系数、非同构子图个数向量。基于重要性的特征可用于预测网络中的重要节点，例如社交网络中的名人节点；基于结构的特征可用于预测网络中不同节点的不同功能，例如蛋白质相互作用网络中不同蛋白质的功能，因为不同的局部子结构往往蕴含了不同的功能。 针对边的特征工程方法 针对边<A,B>的特征工程方法，固然可以把节点A和B的节点特征concat起来作为边<A,B>的特征，但是丢失了很多边特有的信息，效果不一定好。专门针对边设计的特征工程方法有三个，下面分别介绍： 基于距离的特征（Distance-based feature） 局部邻居重叠比例（Local neighborhood overlap） 全局邻居重叠比例（Global neighborhood overlap） 基于距离的特征 两点之间的最短路径长度，这个最好理解了，可以用Dijkstra算法和Floyd算法求解。然而最短路径无法捕捉两个节点的共同邻居数目，比如下图中BH和BE的最短路径都是2，但BH有两个共同邻居CD，而BE只有一个共同邻居D，如果只用最短路径这个特征，则无法区分BH和BE这两对节点。 局部邻居重叠比例 局部邻居重叠比例衡量两个节点的邻居重叠程度，比如简单的Common neighbors直接计算两个节点的共同邻居数目；Jaccard’s coefficient用邻居交集数目除以并集数目做了归一化。 Adamic-Adar index的计算方法是所有共同邻居的度的对数分之一加和。它的直观含义是，如果共同邻居的度越小，则说明两个节点的关系越紧密。比如下图中，A和B的共同邻居是C，C的度是4，说明C除了连接了A和B，还连了另外2个节点。如果C的度越大，则说明A和B占C的邻居的重要性越低；反之，如果C只连了A和B，则说明A和B通过C这个枢纽连接的关系很重要。举个简单的例子，比如两个人都喜欢一个很小众的电影，则他们的兴趣可能会很接近，但如果都喜欢一个大众电影，则他们的关系可能没那么强烈。 局部邻居重叠比例的问题是：只考虑了一跳直接相连的邻居，没有考虑间接相连的邻居（潜在关系），后面介绍的全局邻居重叠比例可以解决这个问题。 全局邻居重叠比例 Katz index统计的是任意两个节点之间任意长度的路径的个数。在计算Katz index的时候，需要计算两个节点uv之间长度为l的路径个数。计算方法是邻接矩阵的l次方。 ...

摘要 GCN模型是不是越复杂越好呢？这篇文章分析发现，GCN中常用的矩阵变换（feature transformation）和非线性激活函数（nonlinear activation）没有作用，甚至有反作用，据此作者提出了一个非常简单的GCN模型LightGCN，模型参数只有节点的embedding。这么简单的模型在推荐任务上，比大多数复杂模型的性能都要好，而且作者从理论分析了如此设计存在的若干好处。 简介 作者所在团队在2019年发表了一个NGCF的模型，该模型基于user和item的交互关系网络，使用GCN训练得到user和item的embedding，然后使用embedding相似度进行推荐。 简单来说，第k+1层的user和item的embedding使用如下公式计算。其中的W1是直接对embedding进行变换的矩阵，W2是对user和item点乘之后进行变换的矩阵；而σ是非线性激活函数。 以user为例，右边有两项，第一项是对user在第k层的embedding进行矩阵变换；第二项是邻居聚合。其中邻居聚合又有两项，第一项是对item的embedding进行矩阵变换；第二项是对user和item点乘之后进行矩阵变换。 作者发现，对于协同过滤任务来说，由于user和item都只有ID本身，没有很多的属性，所以并不需要复杂的矩阵变换和非线性激活函数。言下之意是，如果节点有丰富的属性信息的话，非线性变换和激活有用？感觉可以这么理解：有些属性重要，有些属性不重要，所以需要非线性激活函数进行识别？如果只有节点ID的话，ID的embedding的所有维度都是重要的，不需要非线性激活，直接线性加权聚合就行了。 然后作者对NGCF模型进行了简单的消融实验，如下表所示，NGCF就是原始的NGCF，NGCF-f、-n、-fn分别表示去掉矩阵变换W1和W2、去掉非线性激活函数σ、同时去掉W1、W2和σ。很意外的是，-f、-n、-fn居然都比原始的NGCF效果好，而且-fn效果最好。说明对于只有user和item顶点，没有属性的网络来说，不用过于复杂的矩阵变换和非线性激活，效果反而更好。 按道理NGCF的参数空间比NGCF-f大，且前者能覆盖后者（只需要把W1和W2设置成单位矩阵），为什么前者的效果反而比后者差呢？作者进一步分析了两者训练时的loss和recall曲线，发现NGCF的参数空间虽然比NGCF-f大，但其收敛后的loss更大，recall更小。也就是说训练效果反而不如NGCF-f。作者认为，加入过多的矩阵变换和非线性变换，导致模型过于复杂，难以训练到较好的效果。据此，作者提出了一个更简单的模型LightGCN，具体看下一节介绍。 方法 既然前面分析说矩阵变换和非线性激活函数会起副作用，LightGCN的方法非常简单，就是把这两个操作去掉。如公式3所示，每个节点的embedding表示直接等于其邻居的embedding的线性加权求和，既没有矩阵变换，也没有非线性激活函数，如此的简单。而且，对比公式3和公式1可知，LightGCN没有显式使用自回路，即计算某个节点的embedding的时候，只用了其邻居的embedding，没有用自己的embedding；而NGCF在公式1中使用了自回路。 其网络结构图如下： 最后，节点的最终embedding等于其各层embedding的加权求和。如公式4所示，权重系数α可以手工指定，也可以使用注意力网络来自动学习。为简便起见，本文直接设置为等权重，所有系数都等于1/(K+1)，相当于所有层embedding求平均。 节点最终embedding等于各层embedding的加权求和有如下三个好处： GNN存在over-smoothing的问题，即随着网络层数越深，深层网络的输出结果趋向于相同。即所有节点的最后一层的输出有可能很接近。而如果把所有层加起来的话，能一定程度上缓解这个问题 GNN不同层捕获的语义信息不一样，使用所有层输出能增强表达能力，这个和CNN的道理是类似的。 所有层embedding求和可以捕获自回路的信息。也就是说虽然公式3没有显式使用自回路，但计算顶点最终embedding时（公式4）可以隐含自回路的信息，这个后面会给出证明。 除此之外，由于LightGCN很简单，所以也很好训练，更容易收敛，收敛效果更好。总之，虽然LightGCN很简单，但它很强大，而且有很多好处。 模型分析 接下来，作者分析了为什么LightGCN可以学习到自回路，其证明思路是这样的。另一篇工作SGCN和这篇工作很像，也做了很多简化，且显式添加了自回路。作者通过分析发现LightGCN可以表达SGCN的形式，间接说明LightGCN隐含可以考虑自回路。下面是具体的证明过程。 首先定义user和item的交互矩阵\(\mathbf{R}\in \mathbb{R}^{M\times N}\)，其中M和N分别表示user和item的个数。\(\mathbf{R}_{ui}\)为1表示u和i有交互，等于0表示没有交互。则全图的邻接矩阵可以表示为公式6： 公式3的矩阵形式可以表示成公式7，其中矩阵D为度矩阵。对照下原始的GCN公式，其实就是把原始GCN的变换矩阵W和非线性激活函数σ去掉了。 由于LightGCN是将多层embedding加权求和，所以最终结果是公式8： 然后作者对SGCN的公式进行了简单的变换，发现形式上和公式8是一致的，所以LightGCN也能隐含学习到自回路特征。 此外，作者还分析了另一个模型APPNP，APPNP借鉴pagerank的思想，可以缓解GNN过深带来的over-smoothing问题。然后作者如法炮制，对APPNP的公式进行变换，发现也和公式8等价，所以LightGCN也能缓解GNN的over-smoothing问题。其实这个从LightGCN不只使用最后一层，而是使用所有层embedding就能得到这个结论，不需要这么大费周章证明。 实验 最后是实验环节。作者将LightGCN和本文开头提到的NGCF进行了对比，实验结果表明，LightGCN的性能相比NGCF有显著提升，而且比NGCF-fn也高。作者提到，虽然NGCF-fn已经去掉了矩阵变换和非线性激活函数，但NGCF-fn仍然还有自回路、user和item的点积、dropout等等，还是比较复杂，不好训练。而LightGCN非常简单，只有embedding和邻居的线性加权，所以LightGCN还是比NGCF-fn好。真的很神奇啊，照这个说法，难道连dropout也会起副作用？ 此外，在消融实验中，作者还对比了LightGCN和LightGCN-single，LightGCN-single是只用LightGCN的最后一层作为节点的embedding。作者发现，当网络层数增大到4层时，LightGCN-single性能显著下降，出现了over-smoothing的问题。而LightGCN由于多层组合的操作，不会有over-smoothing的问题。考虑到性能和收益，LightGCN使用了3层神经网络。 评价 结果有些意外，LightGCN这么简单的模型，效果居然比复杂模型还要好？感觉即使是NGCF，模型也不复杂啊，和CV、NLP那些大模型相比简单多了，怎么就训练不好了呢？难道是GNN特有的现象？ 感觉和数据有关，本文测试的数据是只包含user和item顶点，顶点没有属性。如果是属性图的话，也许结论会有变化。 不过至少提供了调参的思路：去掉矩阵变换、去掉非线性激活函数、甚至是去掉dropout。。。另外重要的一点是，不要只用最后一层的embedding，而是组合所有层的embedding进行加权求和。 另外，本文开篇提到的NGCF和本文是同一批作者，自己批判自己一年前发表的工作，不免让人担心这篇工作的可靠性。。。以及当时的NGCF难道没有做本文开篇的消融实验吗？难道不应该吗？

前言 工业界的图规模都非常大，少说也是上千万的顶点+上亿的边，单机训练不现实，必须借助多机分布式训练。然而目前主流的图训练框架PyG、DGL对图的多机分布式训练支持都不太好。工业界好像阿里的Euler、百度的PGL可以支持分布式训练。今天介绍一下亚马逊DGL针对分布式训练所做的优化。 摘要 GNN广泛应用在推荐、搜索、风控等领域，在这些领域，图的规模往往非常大，有数以亿计的顶点和万亿的边。为支持大规模图的分布式训练，本文提出了DistDGL，它能以mini-batch的方式在多机上进行分布式训练。DistDGL基于DGL框架，它将图数据分布在多台机器上，并基于数据分布，将计算也分布在多台机器上（owner-compute rule）。DistDGL以同步更新的方式进行训练。为了减小分布式训练的通信开销，DistDGL使用一个高效、轻量的图分割算法对图进行分割，在分割时设计了多个负载均衡约束，使得每个分割的子图达到较好的负载均衡。此外，为了减小跨机器的通信，DistDGL在每个子图中保留了halo nodes（正文会介绍到），并且使用了稀疏embedding更新策略。这些优化策略使得DistDGL在分布式训练时能达到较好的高并行效率和内存可扩展性。实验结果表明，在分布式训练时，随着计算资源的增大，DistDGL的训练速度可以线性增长。在16台机器组成的分布式环境中，DistDGL仅用13秒就可以完成1亿节点+30亿边的一个epoch的训练。DistDGL是DGL的一部分，已开源在：https://github.com/dmlc/dgl/tree/master/python/dgl/distributed。 简介 GNN很有用，但是现实世界中的网络都很大，比如Facebook的社交网络、Amazon的用户商品关系网络等。 GNN分布式训练的难点： GNN中每个训练样本（顶点）不是独立的，是相互依赖的，比如为了训练顶点A，必须采样A的邻居，随着GNN层数的增大，采样的邻居数目呈指数上升。而CV、NLP中每条样本是相互独立的。 GNN的多机分布式训练的通信数据主要是图数据（顶点和边，及其属性），而CV、NLP的分布式训练的通信数据主要是网络参数、梯度等，需要通信的数据类型不同，导致CV、NLP的分布式训练优化技术无法直接迁移到GNN的分布式训练中。 此外，神经网络大多采用同步更新的分布式训练策略（难道不是异步？），因此需要尽量做到不同机器或者worker的负载均衡。由于图的特殊结构，不同顶点的度差异很大，即不同子图的负载差异很大，所以如何实现GNN训练时的负载均衡，也是一个难点。 背景介绍 GNN 以消息传递的方式来解读GNN，每一层GNN可以用下面的公式来概括。\(\mathbf{h}_v^{(l+1)}\)和\(\mathbf{h}_v^{l}\)分别表示节点\(v\)在第\(l+1\)层和第\(l\)层的向量表示。\(f\)表示节点\(v\)和每个邻居\(u\)计算消息；\(\oplus\)表示邻居聚合函数；\(g\)用来更新节点表示。 作者将GNN的参数分为两部分，一部分是网络参数，即上面的\(f\)、\(\oplus\)和\(g\)。另一部分是节点本身的embedding参数，对于transductive模型来说，节点本身有embedding，故有这部分参数；但对于inductive模型，节点本身没有embedding参数，节点的embedding表示是通过网络参数生成的。 为了区分这两部分参数，作者将网络参数称为稠密参数dense parameters，所有dense参数在每个mini-batch都需要被全部更新。作者将顶点本身的embedding参数称为稀疏参数sparse parameters，每个mini-batch只需要更新该batch涉及到的顶点的稀疏参数即可。 Mini-batch training GNN进行mini-batch训练时的基本流程如下： 从训练集中随机采样N个顶点，这部分顶点称为target vertices 对每个target vertex随机采样最多K个邻居顶点 对每个target vertex，通过聚合其邻居的信息得到target vertex的表示 上述流程是一层GNN的训练过程，如果GNN有多层，则邻居采样的过程会递归进行下去。 方法 DistDGL分布式训练框架 DistDGL的核心可以用上面的图来表示。DistDGL包含三个组件： Trainer，即图中的GNN Training Component，其中放大的GNN Training Component只是右边3个之一的放大图而已。Trainer主要是用来训练的，即进行前向传播和反向传播的。 Sampler，即图中的Sampling Component，用来采样邻居的。 KVStore，即图中的KVStore Component，用来存储顶点和边的特征，以及相应的embedding。 对照背景介绍中的mini-batch training过程，DistDGL的训练过程如下： Trainer随机采样N个顶点作为target vertices Trainer向Sampler请求采样target vertices的邻居 Trainer向KVStore请求target vertices及其邻居的属性信息 Trainer开始分布式训练，并使用AllReduce方式同步更新dense参数（网络参数）；并将sparse参数（embedding）存储到KVStore中 主要优化点 图分割及负载均衡 这是DistDGL最核心的优化点。为了实现高效的分布式训练，DistDGL首先使用METIS图分割算法把图分割成多个子图，不同子图分布式存储在不同机器上；然后把不同子图的计算也分配到存储数据的机器上。做到数据在哪里，计算就在哪里（owner-compute rule），最大程度利用数据和计算的局部性，减小网络通信。 如下图所示，METIS算法以最小割的方式分割图网络，即如果每条边都有不同的权重的话，METIS希望分割的时候切割的边的权重之和最小，由此可以尽量把有密切连接的节点分割到同一个子图中。 我没仔细研究METIS算法，我理解METIS还需要一个约束，即需要分割成多少个子图，或者每个子图最多有多少个顶点之类的。要不然什么都不分割，直接输出全图，则割最小是0。 如果某一条边被分割了，其所连的两个顶点被分割到两个不同的子图中了，称这样的顶点为HALO vertices（通俗理解就是边缘点）。如果需要采样HALO顶点的邻居，则需要跨子图进行采样，涉及到网络通信。为了避免网络通信成为瓶颈，DistDGL会在两个子图中都保留HALO顶点的另一端顶点。在这种情况下，如果只涉及到HALO顶点的一跳采样的话，不需要跨子图通信。DistDGL通过冗余存储HALO顶点，以减小网络通信。由于GNN网络的邻居采样一般只会有2-3跳，所以这种策略应该能避免大部分跨子图通信。 由于同一批数据只需要在开始训练时做一次分割，相对于漫长的N个epoch训练时间来说，分割图的时间开销被分摊了，可以忽略不计。 分割完图之后，DistDGL把不同子图分配到不同机器上。在训练的时候，由于trainer、sampler和KVStore需要互相交换数据，为了提高数据交换效率，DistDGL把属于同一个子图的trainer、sampler和KVStore分配到了同一台机器上，则三者之间的通信可以直接通过共享内存的方式进行内存拷贝，大幅减小了网络通信带来的延时。 如下图所示，同一台机器上的Trainer、Sampler和KVStore是共享内存的。 文中还提到在METIS分割图的时候，增加了很多约束条件，以达到负载均衡的目的。我理解默认METIS在进行分割的时候，可能只保证不同子图的顶点数大致相同，在这个约束下去最小化割。然而子图的顶点数相同，并不代表子图的负载也相同，还涉及到子图中边的数目，不同类型顶点的数目分布等等。因此DistDGL在METIS子图分割时还增加了很多约束条件，使得分割的子图在训练的时候尽量达到负载均衡。 分布式KVStore DistDGL把顶点和边的属性特征及embedding存储在分布式KVStore中，DistDGL开发了自己的分布式KVStore，而不是使用现成的比如Reddis，原因是更方便自定义功能，比如把属于同一个子图的顶点、边、特征存储到同一个机器上，优化了网络传输，实现稀疏embedding的异步更新等。 分布式Sampler Trainer训练和Sampler采样是并行进行的，简单理解就是，Trainer在训练当前Epoch数据的时候，Sampler就已经在异步采样下一个Epoch的数据了，充分利用计算资源，实现流水线作业。类似的，局部采样和远程网络RPC通信也可以overlap“同步”进行，使得局部采样感受不到远程通信的等待时间。 ...

前言 最近的工作涉及到图神经网络，打算系统学习下这方面的内容。首先搜集了相关的教材，发现市面上的教材大多数是罗列论文的形式，不太适合初学者入门。后来找到了斯坦福CS224W这门公开课，打算入坑，一是之前学习过斯坦福CS224N，感觉不错；二是CS224W这门课的老师是GraphSAGE的作者Jure Leskovec，有大佬背书错不了。 CS224W主页：http://web.stanford.edu/class/cs224w/ Winter 2021版主页：http://snap.stanford.edu/class/cs224w-2020/ Winter 2021版视频：https://www.youtube.com/playlist?list=PLoROMvodv4rPLKxIpqhjhPgdQy7imNkDn，Jure Leskovec是斯洛文尼亚人，英语不是很标准，建议打开YouTube的字幕。 背景介绍 图（Graph）是描述实体（entity）和关系（relation）的一种通用语言形式，它由节点（vertex或node）和连接节点的边组成，很多数据类型都可以用图的形式来描述。 图1 图及其应用实例 目前常见的图有两类： 第一类是网络（network），也称为自然图，例如： 社交网络，全球70亿人形成一个大网络 通信网络，例如通过电话、邮件、交易等形成的网络 生物医药网络，例如基因、蛋白质之间形成的网络 大脑中的成千上万的神经元形成的网络 第二类是通过抽象表示形成的图，例如 人工组织形成的信息网络、知识网络 软件中的代码调用形成的网络 分子网络、场景图、基于粒子的物理模拟等 现有的机器学习工具箱主要针对图像、文本和语音，对图的机器学习处理工具相对较少，因为图是不规则的数据，难以处理。对图的处理主要有以下难点： 图不是欧几里得数据结构，没有固定的大小和拓扑结构 图上的节点没有固定的顺序，也没有参考点，是去中心化的 图会随着时间动态变化，并且图中常常会融合多模态信息 本课程的两个重点： Deep learning in graphs，即图上的深度学习算法 Representation learning，即图表示学习，将图中的节点嵌入到一个低维稠密向量中，使得网络中相似节点的embedding距离接近 本课程的主要内容包括： 传统方法：Graphlets，Graph Kernels 节点嵌入方法：DeepWalk，Node2Vec 图神经网络：GCN，GraphSAGE，GAT，Theory of GNNs 知识图谱：TransE，BetaE 图上的深度生成网络 图在生物医药，科学和工业上的应用 图机器学习应用 图可以有很多应用场景，这些应用可以分为节点水平的（nodel level）、边水平的（edge level）、子图水平的（subgraph level）和图水平的（graph level）。下面逐一举例： Node-level：节点分类（node classification），例如预测节点的属性。节点回归？例如AlphaFolde使用GNN预测每个氨基酸在三维空间中的位置坐标，从而预测蛋白质的结构。感觉和GNN关系不太大吧？具体得看论文了。 Edge-level：链接预测（link prediction），预测两个节点之间是否存在边。例如在推荐系统中，预测user是否会购买item等。另外还可以用于预测药物的副作用，例如任意两种药组合吃，是否会产生副作用，产生哪种副作用，都是针对边的任务。 Sub-graph level：地图导航，预测预期到达时间（ETA）。DeepMind和Google Maps合作的一个工作，很有意思：https://www.deepmind.com/blog/traffic-prediction-with-advanced-graph-neural-networks。简单来说，把每条路分段（supersegment），每段表示成一个点，一条路的相邻段（点）连边，交叉路口的段（点）连边。通过GNN的消息传递，一条路的拥堵信息，可以传递到相邻的路。很自然的想法，也符合实际情况，比如在这条路拥堵了，司机可能就会走相邻的路，进而会影响相邻的路的ETA。问题是，GNN对图很敏感，不同地区、地段的路网图差异很大，有的路网小，有的路网大，因此不同training run之间的方差很大。一开始想到用lr decay来缓解。后来使用MetaGradients让模型自动调整学习率。使用多个loss，多目标学习防止过拟合。 Graph-level：例如新药发现：节点是原子、边是各种键，生成一个graph，就是一种新的复合物。物理模拟：动态图，节点表示粒子，有属性比如速度、动量，然后下一个时刻有新的位置，不断进化变化，类似RNN，可以模拟出粒子的动态变化过程。 图2 图机器学习应用场景 图的表示方法 构成图的基本要素包括顶点集合N和边集合E，可以用\(G(N,E)\)来表示一张图。 根据边是否有方向，可以将图分为无向图和有向图，无向图即图中的边没有方向，有向图即图中的边有方向。 对于无向图G，每个顶点的度就是该顶点所连边的数目，由于一条边连接了两个顶点，贡献了2个度，所以所有顶点的平均度数=2E/N。 对于有向图，顶点的度可分为入度和出度，如图3所示，顶点C的入度为2，出度为1。所有顶点的平均入度=平均出度=E/N。如果某个顶点的入度为0，则称该顶点为源点，例如顶点G；如果某个顶点的出度为0，则称该顶点为槽点（sink），就像水槽一样，只进不出；如果某个顶点的入度和出度都为0，则称该顶点为孤立点。 图3 图的表示方法和顶点的度 ...