深度归纳网络表示学习

9530深度归纳网络表示学习0Ryan A. RossiAdobe Researchrrossi@adobe.com0Rong Zhou Googlerongzhou@google.com0Nesreen K. Ahmed IntelLabsnesreen.k.ahmed@intel.com0摘要0本文介绍了一种称为DeepGL的通用归纳图表示学习框架，用于学习在网络间泛化的深度节点和边特征。具体而言，DeepGL从图中推导出一组基本特征（例如图元特征），并自动学习多层次的分层图表示，其中每个连续层利用前一层的输出来学习更高阶的特征。与以往的工作相反，DeepGL学习了自然泛化到网络间的关系函数（每个函数表示一个特征），因此对于基于图的迁移学习任务非常有用。此外，DeepGL自然支持属性图，学习可解释的归纳图表示，并且通过学习稀疏特征向量而具有空间效率。此外，DeepGL具有表达能力强、灵活性高、组件可互换、时间复杂度为O（| E|）的高效并行实现，可扩展到大型网络。与最近的方法相比，DeepGL在跨网络迁移学习任务和大型（属性）图上具有以下优势：（1）有效性，（2）空间效率，需要的内存减少了6倍，（3）速度快，运行时间性能提高了182倍，（4）准确性，在许多学习任务和各种网络上的AUC平均改进了20％或更多。0关键词0归纳网络表示学习，归纳学习，迁移学习，网络嵌入，表示学习，属性网络，函数学习，网络模式，深度学习0ACM参考格式：Ryan A. Rossi，Rong Zhou和Nesreen K.Ahmed。2018年。深度归纳网络表示学习。在WWW '18Companion：2018年Web会议伴侣，2018年4月23日至27日，法国里昂。ACM，纽约，纽约，美国，8页。https://doi.org/10.1145/3184558.319152401 引言0学习有用的图表示是许多机器学习任务的核心和成功因素，例如节点和链接分类[20,34]，异常检测[5]，链接预测[6]，动态网络分析[21]，社区检测[25]，角色发现[27]，01 本文最初于2017年4月作为R. Rossi等人的“Deep Feature Learning for Graphs”[30]发表。0本文发表在知识共享署名-非商业性使用-禁止演绎 4.0国际许可下。作者保留在个人和公司网站上传播作品的权利，并附上适当的归属。WWW'18 Companion，2018年4月23日至27日，法国里昂，© 2018IW3C2（国际万维网会议委员会），根据知识共享CC BY-NC-ND 4.0许可发布。ACMISBN 978-1-4503-5640-4/18/04。https://doi.org/10.1145/3184558.31915240可视化和感知[24]，网络对齐[16]等。事实上，机器学习方法的成功在很大程度上取决于数据表示[12,28]。能够学习这种表示的方法在成本和工作量方面具有许多优势。有关关系表示学习的调查和分类，请参阅[28]。最近的工作主要基于流行的skip-gram模型[18]，该模型最初用于学习自然语言处理（NLP）领域中单词的向量表示。特别是，DeepWalk[23]将成功的word2vec框架[19]（称为word2vec）应用于嵌入节点，以便保留短随机游走中成对出现频率。更近期的node2vec[13]引入了调整随机游走深度和广度的超参数。这些方法非常成功，并且已经在节点分类等任务上表现出优于许多现有方法的能力。然而，过去的工作仅关注于学习特定图的节点特征[13, 23,32]。这些方法的特征不能推广到其他网络，因此无法用于跨网络迁移学习任务。相比之下，DeepGL学习了泛化到任意图上计算的关系函数，因此自然支持跨网络迁移学习任务，例如跨网络链接分类，网络对齐，图相似性等。现有方法在节点特征向量完全稠密的情况下也不具备空间效率。对于大型图，存储这些密集特征所需的空间可能会超出内存容量。这些特征也难以解释和解释，这在实践中变得越来越重要[9,33]。此外，现有的嵌入方法也无法捕捉更高阶的子图结构，也无法从这些更高阶结构中学习分层图表示。最后，这些方法的运行时间效率也低于本文中介绍的算法（如后面的第3节所示）。下面讨论了其他关键差异和局限性。在这项工作中，我们提出了一种通用的、表达能力强的、灵活的深度图表示学习框架DeepGL，克服了上述许多限制。直观地说，DeepGL通过使用图结构和任何属性（如果有）推导出一组基本特征。基本特征使用一组学习的关系特征运算符进行迭代组合，这些运算符在图元的（距离-ℓ）邻居的特征值上操作。02 迁移学习和归纳学习这两个术语可以互换使用。3请注意，根据Bengio等人的定义，深度学习方法是指通过更深的计算组合来学习多层表示，其中更高层次通过更深的计算组合来捕捉更抽象的概念。此定义包括基于神经网络的方法以及DeepGL和许多其他深度学习范例。0论文集：第三届大型网络学习表示国际研讨会（BigNet 2018）WWW 2018，2018年4月23日至27日，法国里昂9540（节点，边；见表1）从低阶特征中推导出高阶特征，形成分层图表示，其中每个层由越来越高阶的特征组成。在每个特征层中，DeepGL在关系特征运算符的组合中定义了一组关系函数空间，这些运算符应用于前一层输出的每个特征。如果特征（或关系函数）是新颖的，并且因此添加了重要信息，而其他特征集合没有捕捉到这些信息，则保留这些特征。请参阅下面关于DeepGL优势和特性的总结。01.1 贡献总结0提出的DeepGL方法为从属性图中学习深度图表示提供了一个通用的强大框架，该框架在跨网络学习任务中具有自然归纳的特性。DeepGL克服了现有工作的许多局限性，并具有以下关键特性：•新颖的框架：本文提出了一个称为DeepGL的深层分层归纳图表示学习框架，用于大型（属性）网络的发现节点和边特征。DeepGL搜索一个关系函数空间（表示特征），这些函数由应用于一组基本特征的关系特征运算符的组合表示。该框架具有灵活的可互换组件，表达能力强，并且在各种应用中已被证明是有效的。•归纳表示学习：与现有的节点嵌入方法相反，DeepGL通过学习适用于任意图的关系函数来自然地进行归纳，并且因此支持跨网络的迁移学习任务。•空间效率：大多数现有方法学习密集的高维特征向量，这对于大型图来说通常是不实际的（例如，太大而无法放入内存中），DeepGL通过学习稀疏图表示来实现空间效率，其所需空间比现有工作少多达6倍。•快速、并行和可扩展：它的运行时间与边的数量成线性关系。通过简单高效的并行化，它可以扩展到大型图。值得注意的是，在第3节中观察到了强大的扩展结果。•分层图表示：DeepGL学习具有多个层的分层图表示，其中每个连续层使用前一层的输出作为输入，以推导出更高阶的特征。•可解释和可解释性：与现有的嵌入方法不同，DeepGL学习可解释和可解释的特征。02 框架0本节介绍DeepGL框架。由于该框架自然地推广到学习节点和边的表示，因此它通常描述为一组图元素（例如节点或边）。0为方便起见，DeepGL-edge和DeepGL-node有时用于分别指代DeepGL的边和节点表示学习变体。0表1：符号总结。矩阵用粗体正体罗马字母表示；向量用粗体小写字母表示。0G（无）定向（属性）图G=（V，E）的稀疏邻接矩阵N，M图中节点和边的数量F，L学习特征和层数G图元素集合{д1，д2，∙∙∙}（节点，边）d + v，d-v，d v出度，入度，顶点v的度数Γ+（дi），Γ-（дi）图元素дi的外/内邻居Γ（дi）дi的邻居（相邻图元素）Γℓ（дi）ℓ-邻域Γ（дi）= {дj∈G |dist（дi，дj）≤ℓ}dist（дi，дj）дi和дj之间的最短距离S与дi相关的图元素集合，例如，S = Γ（дi）X特征矩阵x N或M维特征向量xi x的第i个元素，用于图元素дi | X|矩阵X中的非零元素数F特征定义/函数集合来自DeepGL Fkk-th特征层（其中k是深度）fi x i的关系函数（定义）Φ关系运算符集Φ ={Φ1，∙∙∙，ΦK}K（∙）特征得分函数λ容差/特征相似性阈值α变换超参数（例如，对数分箱中的bin大小0≤α≤1）x' = Φi�x�应用于每个图元素的关系运算符02.1基本图特征0DeepGL的第一步（算法1）是使用图的拓扑结构和属性（如果有）推导出一组基本图特征5。最初，特征矩阵X仅包含用户输入的属性。如果没有提供属性，则X将仅包含下面推导出的基本特征。注意，DeepGL可以使用任意一组基本特征，因此不限于下面讨论的基本特征。给定图G =(V，E)，我们首先使用局部图元分解方法[3]将G分解为其较小的子图组件，称为图元（网络模式），并将基于图元计数的特征向量连接到特征矩阵X。本研究通过计算具有最多4个和/或5个顶点的所有节点或边的轨道（图元自同构）来推导此类特征。根据是否需要基于节点或边的特征表示（因为我们的方法自然地推广到两者），对图中的每个节点或边计算轨道数。注意，具有2-4个节点的轨道有15个节点和12个边，具有2-5个节点的轨道有73个节点和68个边。我们还为G中的每个图元（节点、边）推导出简单的基本特征，例如入度/出度/总度数和k核数。对于每个边（v，u）∈E和每个◦∈{+，×}，我们为边特征学习推导出边度特征，如下所示：�d + v ◦ d + u，d−v ◦d−u，d−v ◦ d + u，d + v ◦ d−u，dv ◦ du�（1）0其中dv = d + v ◦ d − v，并从表1中回忆dv +v，d−v和dv分别表示v的出度/入度/总度数。此外，还使用了Egonet特征[4]。给定一个节点v和一个整数ℓ，v的ℓ-Egonet被定义为距离vℓ跳（即距离最多为ℓ）的图元素集合，以及该集合之间的所有边和节点。为节点提供外部和内部Egonet特征。05术语“图特征”指的是边缘或节点特征。0Track:第三届大型网络学习表示国际研讨会（BigNet 2018）WWW 2018，2018年4月23日至27日，法国里昂!inputx2"x1"ℱ1xi"ℱ2ℱ3xj xk"wjkℱ/wij…"⋯"⋯"⋯"⋯"⋯"⋯"⋯"X,"ℱ!⋯"⋯"⋯"⋯"9550自我中心）0内部-ego）0外部自我中心）0（a）外部Egonet特征0（b）内部Egonet特征0图1：Egonet特征。基本（ℓ =1跳）Egonet图特征集合。（a）外部Egonet特征；（b）内部Egonet特征。请参见图例，了解顶点类型：自我中心（•），内部Egonet顶点（•），外部Egonet顶点（◦）。0如图1所示，并在DeepGL-node中作为基本特征使用。对于上述所有基本特征，我们还根据方向（入度/出度/双向）和权重（加权/非加权）推导出变体。观察到DeepGL自然支持许多其他图属性，包括高效/线性时间属性，如PageRank。此外，还可以使用具有可证明边界的快速近似方法推导出诸如每个图元（节点、边）邻域中的局部着色数和最大团等特征。DeepGL的一个关键优势在于其自然处理属性图的能力。特别是，任何作为输入给定的初始属性集合可以简单地与X连接起来，并且与初始基本特征一样处理。0图2：DeepGL架构的图表示学习概述。令W =[wij]为特征权重矩阵，其中wij（或Wij）是特征向量xi和xj之间的权重。注意，W有一个约束条件，即i < j  λ (2)0表2：一些关系特征运算符的定义。回顾表1中的符号表示。为了通用性，S在表1中被定义为与дi的相关图元素（节点、边）的集合，因此sj ∈ S可以是一个边sj = ej或一个节点sj = vj；在这项工作中，S ∈{Γℓ(дi), Γ+ℓ(дi),Γ-ℓ(дi)}。关系运算符推广到ℓ距离邻域（例如，Γℓ(дi)，其中ℓ是距离）。注意x = [x1 x2 ... xi ...] ∈RM，其中xi是x的第i个元素，对应于дi。0Hadamard Φ�S, x� = ∏0sj ∈ S x j0mean Φ�S, x� = 1/|S| ∑0sj ∈ S x j0sum Φ�S, x� = ∑0sj ∈ S x j0maximum Φ�S, x� = max sj ∈ S xj0权重。LpΦ�S, x� = ∑0||x i - x j||p0RBF Φ�S, x� = exp(-1/σ^2)0s j ∈S0||xi - xj||^20算法1：DeepGL：深度归纳图表示学习框架0要求：一个（无）定向图G = (V, E)；一组关系特征运算符Φ = {Φ1, ...,ΦK}，以及一个特征相似性阈值λ。01:  如果没有作为输入给出，则初始化  F 1  为  �02:  给定  G ，构建基础特征(详见正文以获取更多细节)，并将特征向量连接到  X ，将函数定义添加到 F 1 ；并设置  F ← F 1 .03:  转换基础特征向量 ; 设置  τ  ←  204:  重复 � 特征层  F τ  ，对于  τ  =  2 , ...,  T05: 搜索由应用关系特征运算符  Φ  =  { Φ 1 ,  ∙ ∙ ∙  ,  Φ K  }  到特征 � ∙ ∙ ∙ x i x i+ 1 ∙ ∙ ∙ � 定义的特征空间0以前一层输出的特征层  F τ  − 1  为输入 (通过 Alg.  2)。将特征向量添加到  X ，将函数/定义添加到  F τ  .06: 通过特征扩散过程 (Eq.  3 ) 扩散新的特征向量07: 转换特征层  F τ  的特征向量08: 使用准则  K 对特征层  F τ  中的特征 (函数)进行评估，以得到特征对的分数，并使用特征选择方法选择子集 (Alg.  3 ).09: 从  X  中丢弃被修剪的特征 (不在  F τ  中) 并设置  F ← F ∪ F τ010: 设置  τ  ←  τ  +  1 并初始化  F τ  为  �  以供下一特征层使用011:  直到没有新的特征出现或达到最大层数012:  返回  X  和关系函数集合 (定义)  F0结果是一个加权特征依赖图  G F  。现在，  G F  被用于从层  τ中选择一组重要特征。特征的选择如下：首先，特征图  G F被划分为特征组  {C 1 ,  C 2 , . . . } ，其中每个集合  C k  ∈ C表示相关的特征 (尽管不一定是成对相关的)。为了划分特征图  G F，Alg.  3使用连通分量，但也可以使用其他方法，例如聚类或社区检测方法。接下来，从每个相关特征组 (簇)中选择一个或多个代表性特征。或者，还可以从相关特征组中派生一个新特征，例如找到这些特征的低维嵌入或取主特征向量。在 Alg.  3中，选择每个连通分量  C k  =  { ...,  f i , ...,  f j , ... } ∈ C中最早的特征，并删除其他特征。修剪特征层  F τ  后，从  X中删除被丢弃的特征，并通过设置  F ← F ∪ F τ  (Alg.  1 : Line  9 )更新到目前为止学到的特征集合。接下来，Line  10 增加  τ  并设置F τ  ←  � 。最后，检查是否收敛，如果停止准则不满足，则  DeepGL学习一个额外的特征层 (Line  4 - 11 )。与仅输出节点特征矩阵  X的节点嵌入方法不同，  DeepGL  还输出与学到的特征对应的 (分层)关系函数  F。保持关系函数的重要性在于将特征转移到其他任意感兴趣的图中，同时也有助于解释这些特征。此外，  DeepGL是一种归纳表示学习方法0Track: 第三届大型网络学习表示国际研讨会 (BigNet 2018) WWW 2018, 2018年4月23日至27日, 法国里昂9570Algorithm 2  使用前一层的特征和关系特征运算符集合  Φ  =  { Φ 1 ,  ∙ ∙ ∙  ,Φ K  }  派生一个特征层01  procedure  FeatureLayer( G ,  X ,  Φ ,  F ,  F τ  ,  λ ) 2并行对于每个图元素  д i  ∈ G  do 3 设置  t  ← |F| 4对于每个特征  x k  s.t.  f k  ∈ F τ  − 1  按顺序执行  do 5对于每个 S  ∈ � Γ + ℓ ( д i ) ,  Γ − ℓ ( д i ) ,  Γ ℓ ( д i ) � do6 对于每个关系运算符  Φ  ∈  Φ  do 7 X it  =  Φ ( S ,  x k )  and  t  ←  t  +  108 将特征定义添加到  F τ 9 返回特征矩阵  X  和  F τ0算法 3 评估特征层01 过程 评估特征层( G , X , F , F τ )2 令 G F = ( V F , EF , W )03 并行对于每个特征 f i ∈ F τ ，执行以下操作：41 )05 如果 K � x i , x j � > λ，则执行以下操作：6 E F = E F ∪ {(i , j )} 7 W ij = K � x i , x j �08 使用连通分量将 G F 进行分割，得到 C = {C 1 , C 2 , ...}09 并行对于每个 C k ∈ C ，执行以下操作：� 移除特征10 找到 f i ，使得 � f j ∈ C k ：i < j 。11 从 F τ 中移除 C k ，并设置 F τ ← F τ ∪ { f i }0因为关系函数可以用来推导新节点甚至图的嵌入。02.4 特征扩散0我们引入特征扩散的概念，其中每一层的特征矩阵可以使用任意的特征扩散过程进行平滑。例如，假设 X 是第 τ层的结果特征矩阵，那么我们可以设置 ¯ X ( 0 ) ← X 并求解：0¯ X ( t ) = D − 1 A ¯ X ( t − 1 ) (3)0其中 D 是对角度矩阵，A 是 G的邻接矩阵。上述扩散过程在固定的迭代次数 t = 1, 2, ..., T或收敛之前重复进行；而 ¯ X ( t ) = D − 1 A ¯ X ( t − 1 )对应于简单的特征传播。DeepGL中还可以使用更复杂的特征扩散过程，例如归一化拉普拉斯特征扩散，定义如下：0¯ X ( t ) = ( 1 − θ ) L ¯ X ( t − 1 ) + θ X ，对于 t = 1, 2,0其中 L 是归一化的拉普拉斯矩阵：0得到的扩散特征向量 ¯ X = � ¯ x 1 ¯ x 2 ∙ ∙ ∙ �0通过相关的图元素（节点/边）的特征进行平滑处理。请注意，在算法 1 的第 5 行或第 9行之后，输出的特征向量可以进行扩散处理。注意，¯ X可以以多种方式利用：X ← ¯ X（替换之前的特征）或通过 X ← � X ¯X �进行连接。特征扩散可以看作是一种图正则化的形式，因为它可以提高使用图嵌入学习的模型的泛化能力。02.5 计算复杂度0回顾一下，M 是边的数量，N 是节点的数量，F 是特征的数量。02.5.1 学习。DeepGL框架中边表示学习的总计算复杂度为：0O � F ( M + MF ) � (6)0对于节点表示学习，Deep0O � F ( M + NF ) � (7)0因此，在这两种情况下，DeepGL中表示学习的运行时间与边的数量成线性关系。另外，初始的图元特征是使用快速准确的估计方法计算得出的，详见Ahmed等人[3]。02.5.2归纳关系函数。我们现在给出直接计算在另一个任意图上学习到的归纳关系函数（特征定义）集合的计算复杂度。在归纳跨网络学习任务中，计算在另一个任意图上的学习到的关系函数 F是很重要的。给定学习到的关系函数集合 F ，DeepGL中边的关系函数的总计算复杂度为：O � FM�。同样，节点的关系函数的时间复杂度也是 O � FM �。因此，DeepGL中推导边和节点的关系函数的运行时间与边的数量成线性关系。在另一个任意图上计算归纳关系函数集合的工作量显然比学习实际的归纳关系函数集合（第 2.5.1节）要少。关键区别在于，在直接推导关系函数时不需要评估特征。相反，在 DeepGL 中的表示学习会对每一层的特征进行评估。03实验0本节展示了所提出框架的有效性。03.1实验设置0在这些实验中，我们使用以下实例化的DeepGL：使用对数分箱转换特征，并使用简单的一致性评分函数进行评估，其中K（xi，xj）=图元素的比例一致。更正式地，一致性评分定义为：0K（xi，xj）=0| xik，xjk |，�k = 1，...，N | xik = xjk0N（9）0其中xik和xjk分别是xi和xj的第k个特征值的N维向量。除非另有说明，我们设置α =0.5（对数分箱的bin大小），并在λ∈{0.01，0.05，0.1，0.2，0.3}和Φ∈{Φ mean，Φ sum，Φ prod，{Φ mean，Φ sum}，{Φprod，Φ sum}，{Φ prod，Φmean}}上进行网格搜索。参见表2。请注意，Φprod是在表2中正式定义的Hadamard关系运算符。顺便说一句，DeepGL的超参数比节点2vec、DeepWalk和LINE少。通过对10%的标记数据进行10折交叉验证选择上述DeepGL的具体模型。0Track:第三届大型网络学习表示国际研讨会（BigNet 2018）WWW 2018年4月23日至27日，法国里昂00.10.20.30.40.50.60.70.80.919580实验重复进行了10次随机种子初始化。所有结果在p值<0.01的情况下具有统计学意义。我们将所提出的框架与节点2vec [13]、DeepWalk [23]和LINE[32]进行了评估。对于节点2vec，我们使用超参数和p，q∈{0.25，0.50，1，2，4}进行网格搜索，如[13]中所述。DeepWalk和LINE使用[13]中提到的实验设置。除非另有说明，我们使用带有L2惩罚项和一对多的逻辑回归进行多类问题。数据已在NetworkRepository [26]上提供。80表3：网络内链接分类的AUC得分0escorts yahoo - msg0| xi 0DeepGL 0.6891 0.9410 平均节点2vec 0.6426 0.9397DeepWalk 0.6308 0.9317 LINE 0.6550 0.79670DeepGL 0.6339 0.9324 乘积节点2vec 0.5445 0.8633DeepWalk 0.5366 0.8522 LINE 0.5735 0.73840DeepGL 0.6857 0.9247 加权L1节点2vec 0.5050 0.7644DeepWalk 0.5040 0.7609 LINE 0.6443 0.74920DeepGL 0.6817 0.9160 加权L2节点2vec 0.4950 0.7623DeepWalk 0.4936 0.7529 LINE 0.6466 0.534603.2网络内链接分类0我们首先评估DeepGL在链接分类中的有效性。为了能够将DeepGL与节点2vec和其他方法进行比较，在本节中我们专注于网络内链接分类。为了比较，我们使用相同的二元运算符集合通过学习到的节点表示间接构建边特征：给定节点i和j的特征向量xi和xj，(xi + xj) /2是均值；xi ⊙ xj是（Hadamard）乘积；| xi − xj |是绝对值差。0而 ( xi − xj ) ◦ 2是加权L1和加权L2二元运算符，分别。9请注意，这些二元运算符（用于创建边特征）与表2中定义的关系特征运算符不同。从表3中我们可以看到，在所有图和二元运算符中，DeepGL在节点2vec、DeepWalk和LINE之上的平均增益在18.09%到20.80%之间。请注意，节点2vec、DeepWalk和LINE都要求训练图中的每个节点之间至少有一条边。然而，DeepGL克服了这个基本限制，实际上可以预测训练图中不存在的边的类标签，以及完全不同网络中的边的类标签。03.3 空间效率分析0对于存储甚至适度数量的稠密特征来说是不切实际的（特别是在内存中存储）。尽管学习稀疏高效的表示的重要性，但现有的工作仅限于发现完全稠密的（节点）特征[13, 23, 32]。0参见http://networkrepository.com/以获取数据描述和统计信息9注意x ◦2是逐元素Hadamard幂运算；x i ⊙ x j是逐元素乘积。0fb-MIT yahoo-msg enron fb-PU DD210嵌入密度0DeepGL-edgeDeepGL-nodenode2vec0图3：DeepGL所需的空间比node2vec和其他学习密集嵌入的方法少多达6倍。0对于学习稀疏的空间高效图表示的重要性，现有的工作只限于发现完全稠密（节点）特征[13, 23,32]。为了了解DeepGL用于学习稀疏图表示的有效性，我们测量了从DeepGL学习到的每个表示的密度，并将其与最先进的方法[13,23]进行比较。我们首先关注节点表示，因为现有方法仅限于节点特征。结果如图3所示。在所有情况下，DeepGL学习到的节点表示非常稀疏，比node2vec[13]更节省空间，如图3所示。DeepWalk和LINE与node2vec几乎使用相同的空间，因此为了简洁起见，省略了它们。令人惊讶的是，DeepGL仅使用现有方法所需空间的一小部分（图3）。此外，DeepGL的节点和边表示的密度分别为0.162、0.334（节点）和0.164、0.318（边），比现有方法节省多达6倍的空间。值得注意的是，最近的节点嵌入方法不仅输出密集的节点特征，而且通常是实值和负值（例如[13, 23,32]）。因此，它们每个特征值需要8个字节，而DeepGL仅需要2个字节，如果需要可以通过调整α（即对数分箱转换的箱子大小）进一步减少到1个字节。为了理解这一影响，假设这两种方法都学习了一个具有128个维度（特征）的节点表示，用于具有10000000个节点的图。在这种情况下，node2vec、DeepWalk和LINE需要10.2GB的空间，而DeepGL仅使用0.768GB的空间（假设密度为0.3）-空间减少了13倍。03.4 运行时间和可扩展性0为了评估所提出框架的性能和可扩展性，我们学习了Erdös-Rényi图的节点表示，图的大小逐渐增加（从100到10000000个节点），使得每个图的平均度为10。我们将DeepGL的性能与专门用于大型图可扩展性的node2vec[13]进行比较，并且已经证明node2vec比DeepWalk和LINE更快。每种方法都使用默认参数。在图4中，我们观察到DeepGL比node2vec快得多，且可扩展性更好。特别地，node2vec对于1000万个节点需要1.8天（45.3小时），而DeepGL仅需15分钟；参见图4。令人惊讶的是，这比node2vec快182倍。0Track: 第三届大型网络学习表示国际研讨会（BigNet 2018）WWW 2018，2018年4月23日至27日，法国里昂10-210-11001011021031041050246810129590表4：节点分类的AUC分数0图|C| DeepGL node2vec0DD242 20 0.730 0.673 DD497 20 0.6960.660 DD68 20 0.730 0.713 ENZYMES118 20.779 0.610 ENZYMES295 2 0.872 0.588ENZYMES296 2 0.823 0.61003.5 并行扩展性0本节研究了DeepGL的并行性能。为了评估并行算法的有效性，我们使用加速比来衡量，定义为Sp = T10T p 其中 T 1 和 T p 分别是顺序算法（使用 p个处理单元）和并行算法的执行时间。从图5中，我们可以观察到所有DeepGL变体都具有强大的并行扩展性，其中边表示学习变体的性能略优于节点表示学习方法。结果是在具有4个Intel Xeon E5-4627v2 3.3GHzCPU的机器上对soc-gowalla进行的。其他图和机器给出了类似的结果。03.6 节点分类0对于节点分类，我们使用rsm的i.i.d.变体[29]，因为它能够直接处理多类问题（而不是间接处理，例如one-vs-rest），并且始终优于其他间接方法，如LR和SVM。特别地，rsm将测试向量xi分配给与训练向量（即已知标签节点的特征向量）最相似的类别；详见[29]以获取更多细节。相似性使用RBF核来衡量，RBF的超参数σ使用网格搜索和交叉验证来设置，σ∈{0.001, 0.01, 0.1,1}。结果如表4所示。在所有情况下，我们观察到DeepGL在所有图和节点分类问题上明显优于node2vec，包括二分类和多分类问题。此外，DeepGL在ENZYMES295的AUC上取得了48%的最佳改进。顺便提一下，为了简洁起见，删除了DeepWalk和LINE的结果，因为在所有情况下node2vec的表现优于它们。010 1 10 2 10 3 10 4 10 5 10 6 10 7 10 8节点0时间（秒）0DeepGLnode2vec0图4：在平均度为10的Erdös-Rényi图上的运行时间比较。所提出的方法比node2vec[13]快几个数量级。01 4 8 12 16 处理单元数量0加速比0DeepGL-NodeDeepGL-Node+AttrDeepGL-EdgeDeepGL-Edge+Attr0图5：DeepGL框架不同变体的并行加速比。详见正文讨论。04 相关工作0相关研究按以下方式分类。0节点嵌入方法：最近对于从大规模网络中自动学习一组有用的节点特征引起了很大的兴趣[13, 22, 23,32]。特别是，最近的方法将流行的word2vec框架应用于学习节点嵌入[13, 23,32]。DeepGL框架与这些方法在六个基本方面有所不同：(1)DeepGL学习能够泛化到跨网络迁移学习的复杂关系函数。从一个图中学习的DeepGL特征可以从另一个图中提取出来，用于网络对齐、图相似性、角色发现、时态图建模等迁移学习任务。(2)DeepGL学习稀疏特征，因此对于大型网络来说非常节省空间。(3)DeepGL学习重要且有用的边和节点表示，而现有的工作仅限于节点特征[13, 23, 32]。(4) DeepGL自然地支持属性图。(5)DeepGL运行速度快且高效，运行时间与边的数量成线性关系。(6)DeepGL完全并行，并在第3节中展示了强大的扩展性。还有另一个相关的工作集中在属性图上。最近，Huang等人提出了一种用于属性网络的标签信息嵌入