Gravity-Inspired Graph Autoencoders for Directed Link Prediction 针对链路预测的重力启发式图自编码器-程序员宅基地

技术标签: 图神经网络  机器学习  深度学习  神经网络  

Gravity-Inspired Graph Autoencoders for Directed Link Prediction

针对链路预测的重力启发式图自编码器

**作者:Guillaume Salha, Stratis Limnios, Romain Hennequin, Viet Anh Tran, Michalis Vazirgiannis. **

摘要

图自动编码器(AE)和变分自动编码器(VAE)最近作为强大的节点嵌入方法出现了。 特别是,图AE和VAE被成功地利用来解决具有挑战性的链接预测问题,旨在弄清楚图中的某些节点对是否通过未观察到的边连接。 但是,这些模型专注于无向图,因此忽略了链接的潜在方向,这限制了许多实际应用。 在本文中,我们扩展了图AE和VAE框架,以解决有向图中的链接预测。 我们提出了一种新的重力启发式解码器方案,该方案可以从节点嵌入中有效地重构有向图。 我们对三种不同的有向链接预测任务进行经验评估,这些任务的标准图AE和VAE效果较差。 我们在三个真实世界的图表上取得了竞争性结果,超过了一些流行的基准。

CCS CONCEPTS

• Information systems → Social networks;
• Mathematics of computing → Graph algorithms;
• Computing methodologies → Learning latent representations.

关键字

有向图,自动编码器,变分自动编码器,图表示学习,节点嵌入,链接预测

1. 介绍

图形是有用的数据结构,可以有效地表示项目之间的关系。 由于图形数据的激增[54,56],各种各样的特定问题引发了机器学习社区的重大研究工作,旨在从此类结构中提取相关信息。 这包括节点聚类[33],影响最大化[21],图生成[45]和链接预测,这是我们在本文中关注的重点。

链接预测关键在于根据可观察的链接及其属性[29,52]推断实体对(节点)之间是否存在新的关系或仍未观察到的交互(即,图中的新边)。 这一具有挑战性的任务已得到广泛研究,并成功应用于多个领域。 在生物网络中,利用链接预测模型来预测蛋白质之间的新相互作用[26]。 它也存在于我们的日常生活中,暗示我们的社交网络中可能认识的人,但我们仍然没有联系[18、29、52]。 此外,链接预测与众多推荐任务密切相关[4、28、58]。

链接预测在历史上已通过图挖掘启发式法,通过在节点之间构建相似性索引来解决,从而捕获了它们在图中的连接可能性。反映邻域结构和节点接近度的Adamic-Adar和Katz索引[29]是此类相似性索引的臭名昭著的例子。最近,随着将深度学习方法扩展到图结构[6、43、54]的努力越来越多,这些方法已被节点嵌入范式[16、46、56]超越。概括地说,该策略是训练图神经网络将节点表示为低维向量空间(即嵌入空间)中的向量。理想情况下,在此类空间中,图中的结构接近的节点应彼此靠近。因此,人们可以求助于诸如矢量表示之间的内积之类的接近性度量,以预测基础图中的新未观察到的链接。在这个方向上,自动编码器(AE)[1,40]和变分自动编码器(VAE)[23,48]的图形扩展最近在许多实验分析中作为最新的链接预测方法出现[25,38] ,41,47,51]。

但是,这些模型专注于无向图,因此忽略了链接的潜在方向。如第2节所述,预测节点i连接到节点j的图形自动编码器也将以相同的概率预测节点j连接到节点i。由于有向图无处不在,因此这限制了许多实际应用。例如,网络图由有向超链接组成。在诸如Twitter之类的社交网络中,舆论领袖通常被许多用户关注,但是这些联系中只有单项 很少的是互惠的。此外,有向图是在许多没有将数据显式构造为图的领域中的有效抽象。例如,在音乐流媒体平台上,提供有关歌手的信息的页面通常将显示k个最相似的歌手。艺术家的相似性可以在一个图中表示,其中的节点是艺术家,与他们的k个最相似的邻居相连。这样的图绝对是有针对性的:的确,尽管鲍勃·马利可能是一个新的未知雷鬼乐队中最相似的艺术家之一,但该乐队不太可能出现在鲍勃·马利页面上的顶级相似艺术家中。

定向链接预测已通过图挖掘非对称度量得到解决[13、44、55],最近,有人提出了在创建节点嵌入时捕获非对称接近度的一些尝试[34、36、59]。 但是,如何从向量空间表示中重建有向图以有效执行有向链接预测的问题仍然广泛存在。 特别是,尚不清楚如何将图AE和图VAE扩展到有向图,以及在有向链接预测任务上还可以在何种程度上实现这些模型在无向图上的有前途的性能。 我们建议解决这些问题
在本文中,做出了以下贡献:

• 我们提出了一种新模型,可以使用图AE和VAE框架从有向图中有效地学习节点嵌入。 我们从牛顿的万有引力理论中汲取灵感,介绍了一种新的解码器方案,该方案能够从矢量空间节点嵌入中重建不对称关系。

• 我们对三种不同的有向链接预测任务进行经验评估,这些任务的标准图AE和VAE效果较差。 我们在三个现实世界的数据集上取得了竞争性结果,超过了流行基准。 据我们所知,这是有向图上的第一个图AE / VAE实验。

• 我们为这些实验公开发布了code1,以提高可重复性并简化将来的使用。

本文的组织如下。 在第2节中,我们回顾了与图AE和VAE相关的关键概念,并解释了为什么这些模型不适合定向链接预测。 在第3节中,我们介绍了重力启发方法,以使用图AE或VAE重建有向图,并有效执行有向链接预测。 我们在第4节中介绍和讨论我们的实验分析,在第5节中总结。

准备工作/前情回顾

在本节中,我们概述了图AE,VAE及其在链接预测中的主要应用。 在下面,我们考虑具有| V |的无自环图G =(V,E)。 = n个节点,| E | =可以定向的m条边。 我们用A表示G的邻接矩阵,该矩阵是二进制的或加权的。 此外,节点可能具有大小为f的特征向量,并聚集在n×f矩阵X中。否则,X为n×n恒等式 I

2.1 图自编码器 GAE

图自动编码器[25,51]是将自动编码器[1,40]扩展到图结构的一系列无监督模型。 他们的目标是学习节点嵌入,即节点的低维向量空间表示。 图AE由两个堆叠模型组成:

• 首先,编码器模型为图中的每个节点i分配大小为d且大小的潜矢量zi。 所有潜在向量zi的n×d矩阵Z通常是图神经网络(GNN)的输出,该图神经网络适用于A,并在适当时应用于X,即Z = GNN(A,X)。

• 然后,解码器模型旨在使用另一个GNN或更简单的替代方法从Z重建邻接矩阵A。 例如,在[25]及其模型的[38,41]的几个扩展中,解码是通过潜在矢量之间的内积以及S型激活σ(x)= 1 /(1 + e-x)获得的。 或者,如果对A加权,则进行一些更复杂的阈值处理。 换句话说,内积zTizj越大,根据模型在图中连接的节点i和j的可能性就越大。 从解码器表示Aˆ A的重建,我们有Aˆ =σ(ZZT)。

自动编码器背后的直觉如下:如果从潜矢量开始,解码器能够重建与原始矢量接近的邻接矩阵Aˆ,则这意味着这些表示保留了图结构的某些重要特征。 通过最小化图结构的重建损失∥A-Aˆ∥F [51],用F·Robinius矩阵范数∥·∥F,或者通过梯度下降[15],加权交叉熵损失[25]来训练图AE。 。

2.2 图卷积神经网络 GCN

在整个论文中,作为[25]和大多数后续工作[10、17、38、41],我们假设GNN编码器是图卷积网络(GCN)[24]。 在GCN中有L层,L≥2且Z = H(L),我们有:

Structure

在上述等式中,A〜表示A的某些归一化形式。由于在现有模型中考虑了无向图,因此通常的选择是对称归一化A〜= D -1/2(A + I)D -1/2,其中 D是A + I的对角度矩阵。 简而言之,对于每个layerl,我们对给定节点的邻居的H(l-1)的特征向量,其自身的特征信息(因此为I)和ReLU激活进行平均:ReLU(x)= max(x,0)。 权重矩阵W(l)通过随机梯度下降训练

我们依赖GCN编码器的原因主要有以下三个:1)与以前在图AE方面所做的努力保持一致; 2)在基于GCN的图AE之前获得成功的情况下采用大写形式(请参阅第2.4小节),最后但并非最不重要的是3)提高了计算效率。 实际上,评估GCN的每一层都具有线性复杂度w.r.t。 边数m [24]。 还提出了提高GCN训练速度的策略[8,53]。 尽管如此,我们指出,本文中介绍的方法不限于GCN,对于任何其他编码器(例如, 对于更复杂的编码器,例如ChebNet [9],有时在经验上优于GCN编码器[41]。
G

2.3 图变分自编码器 VGAE

[25]引入了变图自动编码器,表示为VGAE,是VAE的图形扩展[23]。 在共享自动编码器名称的同时,VAE实际上是基于完全不同的数学基础。具体而言,[25]假设图上的概率模型涉及每个节点i∈V的长度为d≪ n的潜在变量zi。 这样的向量是低维嵌入空间Z中的节点表示。作者用Z表示所有潜在向量的n×d矩阵,作者将推理模型定义如下:

Structure

潜矢量zi本身是从学习到的分布中提取的随机样本,该推断步骤称为图形VAE的编码部分。 使用两个GCN来学习高斯分布的参数。 换句话说,平均矢量矩阵μi的定义为μ=GCNμ(A,X)。 同样,logσ=GCNσ(A,X)。

然后,一个生成模型尝试使用潜在变量之间的内积来重建A,例如图AE:

Structure 如前所述,σ(·)是S型激活函数。 这是模型的解码部分。 [25]通过最大化模型可能性的可预测变化下界(ELBO)来优化GCN权重: Structure

高斯先验p(Z)=Îp(zi)=ÎN(zi | 0,I),使用整批梯度下降并利用重新参数化技巧[23]。 DK L(·,·)是Kullback-Leibler散度[27]。

2.4 对于无向链接得GAE和VAE

在过去的三年中,图AE / VAE及其扩展已经成功地用于解决一些挑战性任务,例如节点聚类[38、41、50],二部图的推荐[4、10]和图生成,尤其是生物学上 从图VAE的生成模型中得出合理的分子生成[19,30,31,42,45]。 我们参考前面提到的参考资料,对这些应用程序进行更广泛的概述,并在本节的其余部分重点介绍链接预测任务。

在[25]的开创性工作和众多扩展[17,38,41,47]中,链接预测一直是图AE和VAE的主要评估任务。简而言之,作者使用节点的潜在空间表示,评估了其模型的整体能力,以预测无向图中的几对节点是否通过未观察到的边连接。更正式地说,在这种设置中,通常会在图形的不完整版本上训练自动编码器,在该版本中,会随机删除一部分边缘(例如10%)。然后,创建一个测试集,收集这些缺失的边缘和相同数量的随机选择的未连接节点对。作者评估模型通过使用潜在向量Aˆi,j =σ(zTizj)的解码来区分真实边缘(即完整邻接矩阵中的Aij = 1)与假边缘(Aij = 0)的能力。预测当Aˆi,jis大于某个阈值时节点已连接。这是一个二进制分类任务,通常使用接收器工作特征(ROC)曲线下的面积(AUC)或平均精度(AP)分数进行评估。对于此类任务,经验证明AE和VAE图表具有竞争力,并且通常比W.r.t.一些流行的节点嵌入基准,特别是Laplacian特征图[3]和类似于word2vec的模型,例如DeepWalk [39],LINE [46]和node2vec [16]。

我们指出,这些实验大多数都集中在具有多达数千个节点和边的中等大小的图上,这主要是由于内积解码器的O(dn2)二次时间复杂度有限所致,其中涉及到密集矩阵Z和ZT然而,[41]最近绕过了这个可伸缩性问题,并利用图简并性概念[32]引入了用于可伸缩性图AE和VAE的通用框架。他们基于对多达数百万个节点和边的无向图的实验,证实了图AE和VAE在大规模链接预测方面的竞争性能。

2.5 为什么这些模型在有向图得表现不好?

在此阶段,我们记得前面提到的所有工作都明确或隐含地假定输入图是无向的。 通过设计,图AE和VAE不适合有向图,因为它们在从嵌入中重建邻接矩阵时会忽略方向。 实际上,由于内积解码器的对称性,我们具有:

Structure

换句话说,如果我们预测从节点i到节点j的边缘(i,j)的存在,那么我们也必须以相同的概率预测反向边缘(j,i)的存在。 结果,正如我们在第4节中的经验所示,标准图AE和VAE在有向图中的链接预测任务上表现明显不佳,这些关系之间的关系并不总是互惠的。

将内积解码器替换为嵌入中的Lp距离(例如,如果p = 2,则为欧几里德距离)或使用现有的更精细的解码器方案[17]会得出相同的结论,因为它们也是对称的。 最近,[57]提出了D-VAE,一种用于小型有向无环图(DAG)的变体自动编码器,例如神经网络体系结构或贝叶斯网络,其重点是神经体系结构搜索和结构学习。 但是,如何将图AE和VAE扩展到一般有向图,例如在有向链接预测很有挑战的引文网络或Web超链接网络中,仍然存在问题

2.6 关于源/目标向量范式

3 一个针对有向图得重力启发式GAE & VAE

在本节中,我们将介绍一个新模型,以使用AE和VAE框架从有向图中学习节点嵌入,并解决有向链接预测问题。 主要挑战如下:如何从编码表示形式(内积和标准距离对称的节点嵌入中)中的(唯一)潜矢量有效地重构非对称关系?

为了克服这一挑战,我们诉诸于经典力学,尤其是牛顿的万有引力理论。 我们提出了一个嵌入中的潜在节点表示与空间中的天体之间的类比。 具体而言,即使地月距离是对称的,由于重力,月球向地球的加速度也比地向月球的加速度大。 如下所述,这是因为地球更大。 在本节的其余部分中,我们将质量和加速度的这些概念转换为节点嵌入,以构建我们的非对称图解码方案。

3.1 牛顿的万有引力理论

3.2 从物理到节点

让我们回到在空间中的天体与节点嵌入之间的最初类比。 在本小节中,让我们假设,除了维数为d≪的潜矢量zi之外,我们还有一个模型可以为每个节点i∈V学习新的质量参数mi∈R +。 这样的参数将捕获i的倾向,以便吸引该图中其他节点的其他节点,即使其通过有向边指向i。 从这种扩充模型中,我们可以在生成的嵌入中应用牛顿方程。 具体来说,我们可以将节点i由于嵌入中的重力而朝向节点j的加速度 a i → j = G m j / r 2 ai→j = Gmj/r^{2} aij=Gmj/r2作有向图中i与j连接的可能性的指标,其中
r 2 = ∥ z i − z j ∥ 2 2 r^{2} = \parallel zi-zj\parallel ^{2}_{2} r2=zizj22 简而言之

  • 分子捕捉到以下事实:某些节点比图中的其他节点更有影响力。 例如,在科学出版物的引文网络中,开创性的开篇文章更具影响力,应予以更多引用。 在此,mj越大,我越有可能通过(i,j)有向边连接到j。

  • 分母突出显示,如果模型有效地设法将这些节点彼此靠近地嵌入潜在空间表示中,则图中具有结构邻近性的节点(通常具有公共邻域)更可能被连接。 例如,在科学出版物引文网络中,如果文章i来自类似的研究领域,则文章i更可能引用文章j。

3.3 重力启发式GAE

出于教学目的,我们在3.2小节中假设拥有一个能够学习所有i∈V的质量参数mi的模型。让我们详细了解如何使用图自动编码器框架实际推导此类参数。

3.3.1编码器 对于模型的编码器部分,我们求助于图卷积网络处理A,并可能使节点具有矩阵X。此类GCN将大小为(d + 1)的向量分配给图的每个节点,而不是d为 在标准图形自动编码器中。 前d维对应于节点的潜矢量表示,即zi,其中d≪n是节点嵌入的维。 输出向量的最后一个值是模型的估计值 m ~ i = log ⁡ G m i \tilde{m}_i = \log Gm_{i} m~i=logGmi。 综上所述,我们有:

( Z , M ~ ) = G C N ( A , X ) (Z,\tilde M) = GCN(A,X) (Z,M~)=GCN(A,X)

其中Z是所有潜向量zi的n×d矩阵,M是所有 m i m_{i} mi值的n维向量,(Z,M〜)是n×(d +1)个矩阵行连接Z和 M〜。 我们注意到,学习m〜i等同于学习mi,是由于我们得到
去除了重力常数G和对数

在此GCN编码器中,当我们处理有向图时,我们将A的常规对称归一化(即 D − 1 / 2 ( A + I ) D − 1 / 2 D^{-1/2}(A+I)D^{-1/2} D1/2(A+I)D1/2
)替换为向外度归一化 D o u t − 1 ( A + I ) D^{-1}_{out}(A+I) Dout1(A+I)。 在此,Dout表示A + I的对角度矩阵,即Dout的元素(i,i)对应于从节点i出来的边数(可能加权),加一。 因此,在GCN的每一层,节点的特征向量是它所指向的邻居的上一层的特征向量的平均值,以及它自己的特征向量和ReLU激活。

3.3.2解码器 我们利用先前定义的加速度的对数形式以及S型激活,从Z和M〜重建邻接矩阵A。 Aˆ表示 A的重建,我们有:

A ~ i j = σ ( m ~ j − log ⁡ ∥ z i − z j ∥ 2 2 ) \tilde{A}_{ij} = \sigma(\tilde{m}_{j} - \log{\parallel zi-zj\parallel ^{2}_{2}}) A~ij=σ(m~jlogzizj22)

与内部乘积解码器相反,我们通常使用Aˆij,Aˆji。 因此,该方法与有向图重构更相关。 模型训练类似于标准图AE,即我们的目标是通过随机梯度下降使矩阵A的重建损失最小化,该损失由公式[25]表示为加权交叉熵损失。

3.4 重力启发式GVAE

我们还提出了将受重力启发的方法扩展到图变分自动编码器框架。

3.4.1编码器 我们扩展[25]以建立(Z,M〜)的推理模型。 换句话说,与每个节点i相关联的(d + 1)维潜向量是(zi,m〜i),将f维向量zi和标量m〜i连接在一起。 我们有:

q ( ( Z , M ~ ) ∣ A , X ) = ∏ i = 1 n q ( ( z i , m ~ i ) ∣ A , X ) q((Z,\tilde{M})|A,X) = \prod_{i=1}^{n} q((z_i,\tilde{m}_i)|A,X) q((Z,M~)A,X)=i=1nq((zi,m~i)A,X)

根据高斯假说【25】:
q ( ( Z , M ~ ) ∣ A , X ) = N ( ( x i , m ~ i ) ∣ μ ) i , d i a g ( σ i 2 ) ) q((Z,\tilde{M})|A,X) = N((x_i,\tilde{m}_i)|\mu_)i,diag(\sigma^2_i)) q((Z,M~)A,X)=N((xi,m~i)μ)i,diag(σi2))

高斯分布的参数是使用两个GCN来学习的,它们的相似度归一化为w.r.t。 第3.3小节:

µ = G C N µ ( A , X ) a n d l o g σ = G C N σ ( A , X ) . µ = GCNµ (A,X) and log σ = GCNσ (A,X). µ=GCNµ(A,X)andlogσ=GCNσ(A,X).

3.4.2解码器 然后,根据这些分布的样本矢量(zi,m〜i),将我们的重力启发式解码方案合并到生成模型中,尝试重建A:
q ( ( A ∣ Z , M ~ ) ) = ∏ i = 1 n ∏ j = 1 n P ( A i j ∣ z i , z j , m ~ i ) q((A|Z,\tilde{M})) = \prod_{i=1}^{n}\prod_{j=1}^{n} P(A_{ij}|z_i,z_j,\tilde{m}_i) q((AZ,M~))=i=1nj=1nP(Aijzi,zj,m~i)

where

p ( A i j = 1 ∣ z i , z j , m ~ j ) = σ ( m ~ j − log ⁡ ∥ z i − z j ∥ 2 2 ) p(A_{ij} = 1|z_i,z_j,\tilde{m}_{j}) = \sigma(\tilde{m}_{j} - \log{\parallel zi-zj\parallel ^{2}_{2}}) p(Aij=1zi,zj,m~j)=σ(m~jlogzizj22)

根据[25],我们通过使用全梯度梯度下降最大化模型似然性的ELBO来训练模型,并根据高斯先验, p ( ( Z , M 〜 ) ) = ∏ i p ( z i , m i ) = ∏ i N ( ( z i , m i ) ∣ 0 , I ) p((Z,M〜))= \prod_{i}p(z_i,m_i)= \prod_{i}N((z_i,m_i)| 0,I) p((ZM))=ip(zimi)=iN((zimi0I)。 我们将在本文的实验部分讨论这些高斯假设。

3.5 解码方案的推广

我们指出,通过引入附加参数 λ ∈ R + λ∈R+ λR+并按以下方式重构Aˆij,可以在AE和VAE设置中提高解码方案的灵活性:

A ~ i j = σ ( m ~ j − λ log ⁡ ∥ z i − z j ∥ 2 2 ) \tilde{A}_{ij} = \sigma(\tilde{m}_{j} - \lambda \log{\parallel zi-zj\parallel ^{2}_{2}}) A~ij=σ(m~jλlogzizj22)

3.3和3.4节中的解码器是λ= 1的特殊情况。可以通过对链接预测任务进行交叉验证来调整此参数(请参阅第4节)。 这种参数的解释是双重的。 首先,它构成了一个简单的工具,可以在嵌入重构时平衡节点距离的相对重要性。 质量吸引参数。 然后,从物理角度来看,这等效于用牛顿公式中的平方距离替换为2λ次方的距离。 在我们对链接预测的实验分析中,我们提供了有关何时以及为何偏离牛顿的实际理论(即λ= 1)相关的见解。

3.6 复杂性和可扩展性

假设无特征节点,具有m个非零条目的邻接矩阵A的稀疏表示,并且考虑到我们的模型返回密集的n×(d + 1)嵌入矩阵Z,则我们方法的空间复杂度为O(m + n (d + 1)),都适用于AE和VAE框架。 如果节点也具有在n×f矩阵X中堆叠的特征,则空间复杂度变为O(m + n(f + d + 1)),实际上是d≪ n和f≪ n。 因此,作为标准图AE和VAE模型[25],空间复杂度会随着w.r.t线性增加图的大小。

此外,由于在重力启发式解码方案中涉及的所有d维矢量zi和zj之间的L2距离的成对计算,我们的模型具有二次时间复杂度O(dn2)w.r.t。 图形中的节点数,以标准图形AE和VAE为例。 因此,在我们的实验分析中,我们专注于中等大小的数据集,即具有数千个节点和边的图形。 尽管如此,我们仍然指出,可以通过将[41]中提出的简并框架应用于图自动编码器规模化,或将它们的方法引入有向图简并性概念[ 14]。 未来的工作将对这些可扩展性问题进行更深入的研究.

4 实验分析

在本节中,我们将对三个真实世界的数据集以及定向链接预测问题的三个变体进行经验评估和讨论模型的性能。

4.1 三个有向链接预测

我们为实验考虑以下三个学习任务。

4.1.1任务1:通用定向链路预测。 第一项任务称为一般定向链接预测。 如以前的工作[17,24,38,41],我们在不完整版本的图上训练模型,其中不完整的15%的边被随机删除。 我们在屏蔽过程中会考虑方向性。 换句话说,如果节点i和j之间的链接是对等的,我们可能可以删除(i,j)边,但仍可以在训练不完整图中观察到反向(j,i)边。 然后,我们从删除的边缘和相同数量的未连接节点的随机采样对中创建验证和测试集。 我们在二元分类任务中评估模型的性能,该任务包括区分实际的伪造边缘和伪造的伪造边,并使用AUC和AP得分比较结果。 在下文中,验证集包含5%的边,而测试集包含10%的边。 验证集仅用于超参数调整。

此设置对应于链接预测的最一般形式。 但是,由于大多数现实世界图中的大量未连接节点对,我们预计方向性对性能的影响会受到限制。 确实,对于图中的每个实际单向边(i,j),不太可能在测试集中的负样本中检索到反向(未连接)对(j,i)。 因此,专注于图接近度而忽略链接方向的模型(例如标准图AE和VAE)可能仍然可以很好地执行此类任务。 因此,在本小节的以下部分中,我们还提出了两个额外的学习任务,旨在增强方向性学习的重要性。

4.1.2任务2:偏差负样本(B.N.S.)链接预测。 对于第二项任务,我们还将在不完整版本的图上训练模型,该图的不完整版本中删除了15%的边:验证集为5%,测试集为10%。 但是,删除的边都是单向的,即存在(i,j)但不存在(j,i)。 在此设置中,反向节点对包括在验证和测试集中,并构成阴性样本。 换句话说,来自验证和测试集的所有节点对都包含在两个方向中。 对于一般的有向链接预测任务,我们评估模型在二元分类任务上的性能,该模型将实际边缘与假边缘区分开,因此评估模型正确同时重构Aij = 1和Aji = 0的能力。

这项工作已在[59]中以偏向负样本链接预测的名义提出。 w.r.t.更具挑战性 一般链接方向,因为重建非对称关系的能力更为关键。 因此,在这种设置下,忽略方向性并且仅从对称图邻近学习的模型(例如标准图AE和VAE)将失败。

4.1.3任务3:双向性预测。第三项任务是评估模型区分双向边缘(即相互连接)与单向边缘的能力。具体来说,我们通过随机删除所有双向边缘的两个方向之一来创建不完整的训练图。因此,训练图仅具有单向连接。然后,再次设计一个二元分类问题,目的是在测试集中检索双向边缘,该测试集中包含双向方向的移除方向和相同数量的反向方向(因此是伪边缘)。换句话说,对于测试集中的每对结点i,j,我们在不完整的训练图中观察到j与i的联系,但是只有一半是对等的。第三项评估任务在本文中称为双向预测,也强烈依赖于方向性学习。结果,对于任务2,预计标准图形AE和VAE的性能较差。

4.2 实验设置

4.2.1数据集 我们提供了三个可公开获得的现实世界有向图的实验,其统计数据在表1中给出。Cora2和Citeseer2数据集是引文图,由相互引用的科学出版物组成。 Google3数据集是一个网络图,其节点是网页,有向边表示它们之间的超链接。 Google图比Cora和Citeseer更为密集,并且双向边缘的比例更高。 图是未加权的且无特征。

4.2.2标准和重力自动编码器 我们为每张图训练重力启发式AE和VAE模型。 为了进行比较,我们还从[25]中训练了标准图AE和VAE。 这四个模型中的每个模型都包括一个两层GCN编码器,该编码器具有64暗的隐藏层,并且具有第3.3.1节中定义的A的向外度左归一化。 所有模型都经过200个纪元的训练,并返回32维潜在矢量节点表示。 我们使用Adam优化器[22],对Cora和Citeseer应用0.1的学习率,对Google应用0.2的学习率,训练没有辍学的模型,执行批量梯度下降,对可变自动编码器使用重新参数化技巧[23]。 同样,对于任务1和3,我们为Cora和Citeseer(分别为Google)选择λ= 1(分别为λ= 10); 对于任务2,我们为所有三个图形选择了λ= 0.05,我们将在下一部分中对其进行解释。 所有超参数均根据任务1的AUC分数进行了调整,即针对通用定向链接预测任务进行了调整

4.2.3基线 除了标准AE和VAE模型外,我们还比较了我们的方法的性能 第2.6小节介绍的替代图形嵌入方法:

  • 我们的源/目标图AE和VAE,将源目标矢量范式扩展到AE和VAE的图,并使用类似的设置进行了训练。 标准和重力模型。
  • HOPE [36],设置β= 0.01,并且源向量和目标向量的尺寸为16,以学习32维节点表示。
  • APP [59],通过[59]的实现中的标准设置,训练了100次迭代的模型,以学习16维的源向量和目标向量,即32维的节点表示。
  • 为了进行比较,在我们的实验中,我们还训练了node2vec模型[16],该模型在处理随机游走的方向性时,每个节点仅返回一个32维嵌入矢量。 我们依靠具有S型激活的对称内积来进行链路预测,因此我们希望node2vec的性能不如w.r.t. APP。 我们训练了10个随机游动模型,每个节点的长度为80,p = q = 1,窗口大小为5。

4.3 实验结果

在任务1中,标准图AE和VAE尽管忽略了图重建的方向性,但仍然表现良好(例如,Cora上标准图VAE的AUC为82.79%)。 这强调了方向性对此类任务的绩效的有限影响,这在第4.1.1节中已计划。 尽管如此,我们的重力启发模型明显优于标准模型(例如Cora上重力启发图VAE的91.92%AUC),这证实了捕获通用方向链接预测的接近度和方向性的相关性。 此外,我们的模型具有竞争力 专为有向图设计的基线。 其中,APP是我们三个数据集中最好的,另外Google图中的源/目标图AE也是如此。

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/leo_queef/article/details/108925294

智能推荐

C#:实现SM2加密算法​(附完整源码)_c# sm2 算法源码-程序员宅基地

文章浏览阅读988次。C#:实现SM2加密算法​(附完整源码)_c# sm2 算法源码

Android RecyclerView左滑侧滑显示删除按钮_android studio 自定义recyclerview 左滑显示按钮 万用适配器-程序员宅基地

文章浏览阅读1.9k次。创建一个Recyclerview列表item布局,自定义容器:SlidButtonView.javapublic class SlidButtonView extends HorizontalScrollView { private static final String TAG = "SlidButtonView"; private TextView lTextView_..._android studio 自定义recyclerview 左滑显示按钮 万用适配器

Linux Bash 基础和启动过程 (一)_程序启动bash-程序员宅基地

文章浏览阅读606次。业精于勤,荒于嬉,行成于思,毁于随 Linux常用的有Bash,Csh,Tcsh等系统每个用户再登录时就为其 启动一个shell 作为工作环境,默认为/etc/passwd文件内的shellshell基本功能环境控制,命令解释,启动程序,数据流重定向,管道功能,通配符,变量维护个shell编程等shell 通配符*匹配多个字符?匹配任意一个字符[list]匹配list中任意单一..._程序启动bash

jQuery 实现点击div以外其他地方隐藏div_jquery点击除div以外的地方-程序员宅基地

文章浏览阅读835次。<p><a href="javascript:void(0)" class="a">按钮</a></p><div class="menu"> <p>显示弹窗</p></div>$(".a").on("click", function(e){ if($(".menu").is(":hidden")){ $(".menu").show(); }else{ $(".._jquery点击除div以外的地方

Linux运维笔记----日志管理_chmod 2755 /var/log/journal-程序员宅基地

文章浏览阅读5.3k次。日志管理1.日志系统功能日志系统将我们系统运行的每一个状况信息都使用文字记录下来,这些信息有助我们观察系统运行过程中正常状态和系统运行错误时快速定位错误位置的途径等操作系统在运行中会产生非常多的日志信息,如果我们将这些信息都记录下来的话,那我们的磁盘I/O一定很繁忙,这对系统的性能有很大的影响,这就有违了我们的初衷,所以我们根据产生日志的来源和日志信息的重要性,将系统运行中所产生的日志进行分类2_chmod 2755 /var/log/journal

C# WinForm 添加等待界面 利用Gif图片实现-程序员宅基地

文章浏览阅读952次。首先 创建 等待窗体 WatingForm:其次 在WatingForm窗体下编写代码:View Code using System;using System.Collections.Generic;using System.ComponentModel;using System.Data;using System.Drawing;using System.Lin..._winform等待图片gif

随便推点

循环单链表-JAVA语言实现_java语言循环单链表怎么插入运算-程序员宅基地

文章浏览阅读732次。定义循环单链表类,用来实现循环单链表public class CycleNode { //节点内容 int data; //在循环链表中,只有一个节点的循环链表的下一个节点指向其自身 CycleNode next = this; //构造函数 public CycleNode(int data) { this.data = data; } //获取下一个节点..._java语言循环单链表怎么插入运算

Photon通信过程解析《一》(用户登录)[unity3d-->ugui-->playmaker-->pun-->Photon3Unity3d.dll-->photon master serve-程序员宅基地

文章浏览阅读1.7k次。Photon通信过程解析《一》(用户登录)路线节点:[unity3d-->ugui-->playmaker-->pun-->Photon3Unity3d.dll-->photon master server-->mysql]步骤:1、【客户端】用户输入用户名、密码。设置PhotonNetwork.AuthValues。 -->AccountLogin.cs_photon master

Scala - Collections-程序员宅基地

文章浏览阅读82次。what will be covered in this post include the following. Sequence Lists Arrays List Buffers (the builder of List) ArrayB..._scala collections

OneFlow登上“2021世界人工智能大会SAIL奖Top 30”榜单_ai框架 排名 -baijiahao-程序员宅基地

文章浏览阅读1k次。近日,OneFlow新一代开源深度学习框架入选“2021世界人工智能大会SAIL奖TOP 30”榜单。_ai框架 排名 -baijiahao

如何使用OmniGraffle创建横向的画布_omnigraffle画布大小-程序员宅基地

文章浏览阅读962次。OmniGraffle(http://www.omnigraffle.cc/) 是一款绘图软件,它具有采用拖放的所见即所得界面。所谓的"Stencils"—一组用于拖放的形状—可以作为OmniGraffle的插件使用,用户也可以创建自定义的Stencils。有些用户吐槽OmniGraffle只有纵向的画布,今天就来教大家如何使用OmniGraffle创建横向画布。首先我们在中文网上下载正版Omn..._omnigraffle画布大小

FFmpeg源代码简单分析:avformat_open_input()_avformat_open_input 非阻塞-程序员宅基地

文章浏览阅读664次。登录 | 注册收藏成功确定收藏失败,请重新收藏确定标题标题不能为空网址标签 摘要公开取消收藏 查看所有私信查看所有通知_avformat_open_input 非阻塞