双图卷积网络的图半监督分类方法

4990基于图的半监督分类的双图卷积网络0Chenyi Zhuang，Qiang Ma京都大学信息学部，日本京都，zhuang@db.soc.i.kyoto-u.ac.jp，qiang@i.kyoto-u.ac.jp0摘要0通过图分析提取有意义的数据的问题涵盖了互联网、社交网络、生物网络等多个领域。随着越来越多的结构化数据的可用性，能够有效地从这些数据中挖掘和学习的重要性不断增长。在本文中，我们提出了一种简单且可扩展的半监督学习方法，用于仅有很少一部分训练数据标记的图结构化数据。为了充分嵌入图知识，我们的方法从原始数据的不同视图进行图卷积。具体而言，我们设计了一种双图卷积神经网络方法，共同考虑了半监督学习的两个基本假设：（1）局部一致性和（2）全局一致性。因此，我们设计了两个卷积神经网络来嵌入基于局部一致性和全局一致性的知识。鉴于两个网络的不同数据转换，我们引入了一个无监督的时间损失函数进行集成。在使用无监督和有监督损失函数的实验中，我们的方法在不同的数据集上优于现有技术。0关键词0图卷积网络，半监督学习，图扩散，邻接矩阵，点间互信息0ACM参考格式：Chenyi Zhuang，QiangMa。2018。基于图的半监督分类的双图卷积网络。在WWW2018：2018年网络会议上，2018年4月23日至27日，法国里昂。ACM，纽约，美国，10页。https://doi.org/10.1145/3178876.318611601 引言0结构化和半结构化数据（例如来自互联网、社会科学、物理学、生物学和计算机科学的数据）的可用性爆炸导致了对图分析的大量研究。此外，现代公司通常希望以企业知识图的形式存储信息，并应用各种机器学习和数据挖掘技术（例如图挖掘[8]、关系学习[19]、安全[25]、知识嵌入[27]）进行不同的应用。0本文根据知识共享署名4.0国际（CC BY4.0）许可发布。作者保留在个人和公司网站上传播作品的权利，并附上适当的归属。WWW 2018，2018年4月23日至27日，法国里昂 © 2018IW3C2（国际万维网会议委员会），根据知识共享CC BY 4.0许可发布。ACM ISBN978-1-4503-5639-8/18/04。https://doi.org/10.1145/3178876.31861160一个非常有趣的问题是如何仅利用少量标记的训练数据和图结构对图节点进行分类。在机器学习的背景下，基于图的半监督学习是一种旨在利用图结构在只有有限标记数据可用时提高模型准确性的技术。因此，在本文中，我们提出了一种新的通用半监督学习算法，可以应用于不同类型的图，如社交网络、知识图谱、引用网络、万维网等。传统上，基于图的半监督学习可以通过以下损失函数来定义：0L = L0 + λLreд，（1）0其中，L0表示对标记数据的监督损失，Lreд表示对图结构的正则化项。（注意，在公式（1），（2）和（3）中，为简单起见，我们省略了模型自身参数的正则化项。）使用显式的基于图的正则化项Lreд，公式（1）的表达式将L0中的标签信息在整个图上平滑。例如，图拉普拉斯正则化项通常用于Lreд[3][5][33]，它依赖于连接的节点在图中可能共享相同标签的先验假设。然而，这种假设可能限制建模能力，因为图边不一定编码节点相似性，而可能包含其他信息。为了避免这种限制，最近的研究尝试以卷积方式同时考虑标签和图结构信息[2][9][15]。在公式（2）中，我们不再在损失函数中使用显式的基于图的正则化项，而是直接推导出一个卷积函数Conv来编码图结构。0L = L0(Conv)。0在近似的条件下，结构编码Conv可以在两个领域中进行：（1）图顶点领域[2][32]；（2）图谱领域[9][15]。在[24]中，作者讨论了这两个领域之间的关系。然而，通过使用公式（1）和（2），大部分相关工作只考虑了图的局部一致性以进行知识嵌入。为了充分嵌入图的知识，我们发现图的全局一致性尚未得到很好的研究。因此，在本文中，我们提出了一种双图卷积神经网络方法来同时考虑这两个领域。所提出策略中的损失函数的形式为0L = L0(Conv A) + λ(t)L reд(Conv A, Conv P)。0我们方法的思想很简单。首先，在卷积过程中，样本输入数据（例如节点的特征向量）通过两种卷积网络：Conv A和Conv P。0Track：社交网络分析和Web上的图算法WWW 2018，2018年4月23日至27日，法国里昂Lreд =kbi,jxj,(5)Track: Social Network Analysis and Graph Algorithms for the WebWWW 2018, April 23-27, 2018, Lyon, France5000使用图邻接矩阵和正点互信息矩阵，两个卷积网络编码了局部和全局结构信息。与半监督学习中的两个基本假设相对应[32]，ConvA嵌入了基于局部一致性的知识（即附近的数据点很可能具有相同的标签），而ConvP嵌入了基于全局一致性的知识（即在相似上下文中出现的数据点往往具有相同的标签）。在训练过程中，样本通过两个卷积网络和随机逐层丢弃[26]进行多次传递。因此，获得了样本的不同变换。然后，Conv A或Conv P的输出用于监督学习，例如L0(ConvA)。然而，为了提供更好的预测，针对这些变换的面向集成的正则化器L reд(Conv A, ConvP)被导出。通过最小化输入样本的不同变换之间的预测差异，该正则化器结合了Conv A和Conv P的意见。因此，L reд(Conv A, ConvP)是一种无监督的损失函数。总体而言，本文的主要贡献可以总结如下：0（1）除了基于图邻接矩阵的卷积ConvA之外，我们提出了一种依赖于正点互信息（PPMI）矩阵的新型卷积神经网络Conv P。与Conv A不同，ConvP利用随机游走构建PPMI矩阵，进一步嵌入语义信息，即全局一致性的知识。（2）除了对少量标记训练数据进行监督学习（即公式（3）中的L0），我们提出了一种无监督损失函数（即公式（3）中的Lreд）作为一种正则化器，将不同卷积数据变换的输出组合起来。在考虑Conv A和ConvP的一系列实验中，我们的方法显示出比单个卷积网络更好的预测能力。02基于图的半监督学习背景0半监督学习考虑了从有标签和无标签数据中学习的一般问题。给定一组数据点X = {x1，...，xl，xl + 1，...，xn}和一组标签C ={1，...，c}，前l个点具有标签{y1，...，yl}∈C，其余点没有标签。目标是预测无标签点的标签。除了有标签和无标签点，基于图的半监督学习还涉及给定的图，表示为n×n矩阵A。每个条目ai，j∈A表示数据点x i和xj之间的相似性。相似性可以通过计算数据点之间的距离来得到[33]，也可以由结构化数据明确给出，例如知识图[29]，引文图[14]，文档之间的超链接[20]等。因此，基于图的半监督学习的关键问题是如何嵌入图的附加信息以获得更好的标签预测。在近似的条件下，我们将不同的图知识嵌入分类为两组，即显式和隐式的基于图的半监督学习。02.1 显式图半监督学习0显式图半监督学习使用基于图的正则化器（即方程（1）中的Lreд）来合并图中的信息。传统上，图拉普拉斯正则化器被定义为在预测具有不同标签f（xi）和f（xj）的相似数据点xi和xj时产生大的惩罚。0i，j ai，j || f（xi） - f（xj）|| 2 = f T∆f . (4)0方程（4）给出了图拉普拉斯正则化器的一个实例，其中f（∙）是标签预测函数（例如，神经网络）。非归一化图拉普拉斯矩阵定义为∆ =A - D，其中A是邻接矩阵，D是一个对角矩阵，每个条目定义为di，i=∑jai，j。已经提出了许多与方程（4）的变体相关的方法。例如，在[33]中，作者提出了一种基于高斯随机场的标签传播算法。在[32]中，提出了一种类似PageRank的算法，用于考虑图中的局部和全局一致性。最近，在[30]中，作者提出了一种基于采样的方法。他们不使用图拉普拉斯矩阵∆，而是推导出一种基于随机游走的采样算法，以获取每个数据点的正负上下文。然后使用前馈神经网络方法进行知识嵌入。02.2 隐式图半监督学习0如第1节所述，隐式图半监督学习的卷积过程可以在图节点域或图谱域中进行。我们现在介绍与每种情况相关的一些工作。在节点域中进行卷积。为了在节点域中应用卷积，数据点xi通常会以扩散的方式进行转换。一个k-hop局部化线性变换的简单示例是0Conv（xi）= bi，ixi + �0其中{bi，j}是一些用于过滤的权重，N（i，k）表示通过k个或更少的边连接到xi的邻居的集合。这样的卷积建立在扩散核的思想上，可以看作是图中任意两个节点之间连接程度的度量。例如，通过引入阻尼比，较长的路径将比较短的路径更多地打折。最近的一篇综述论文[10]比较了几种图上的扩散核。最近，有几种方法使用基于扩散的卷积。例如，在[2]中，作者提出了一种扩散卷积神经网络。在他们的方法中，k-hop扩散卷积结果（即一个大的张量）直接用作神经网络的输入。因此，需要大量的内存来记录输入。在[15]中，作者提出了一种可扩展的方法，该方法在神经网络的每一层上进行1-hop扩散。这种方法在半监督分类中获得了最先进的性能。谱域中的卷积。我们首先考虑标量xi的最简单情况。在这种情况下，输入X ∈Conv X = дθX = UдθU X,(6)Conv(i)A (X) = Z(i) = σ( ˜D− 12 ˜A ˜D− 12 Z(i−1)W (i)).(7)5010R n ×1被视为在具有n个节点的图上定义的信号。如方程（6）所示，图上的谱卷积可以定义为信号X与由θ ∈ R n参数化的滤波器дθ =diaд（θ）的乘积在图傅里叶域中。0其中U是归一化拉普拉斯矩阵∆ = In - D - 1的特征向量矩阵02，它起到傅里叶变换的作用。当xi具有多个特征时，我们可以将X视为具有多个输入通道的信号。然后将变换U应用于每个通道[13]。在[24]中，作者讨论了定义图谱域的不同方法，并详细解释了图傅里叶变换。由于方程（6）在大型图上的计算代价高昂，最近的研究[9][12][15]已经尝试降低计算复杂性。例如，在[12]中，作者使用切比雪夫多项式的截断展开来近似дθ。两个域之间的关系。在[24]中，作者确定了顶点域和谱域中的卷积之间的关系。也就是说，当将滤波函数дθ近似为一个k阶多项式时，谱卷积可以解释为k-hop扩散卷积。这个结论后来得到了验证[15]。因此，通过将дθ近似为一个一阶切比雪夫多项式，在一些推导之后，它等效于一次跳扩散。我们的工作主要受到[15]的启发。除了基于邻接矩阵的卷积之外，我们还进一步计算了一个PPMI矩阵，用于在卷积过程中编码语义信息。此外，我们提出了一种新的正则化器，将不同的卷积结果组合起来以获得更好的标签预测。03 双图卷积网络 3.1 问题定义和示例0按照第1节和第2节的符号表示，我们模型的输入包括一组数据点X ={x1, ..., xl, xl + 1, ..., xn}，前l个点的标签{y1, ...,yl}和图结构。假设每个点最多有k个特征，数据集表示为矩阵X ∈Rn×k。如前期研究[2] [9] [15] [32]所述，图结构由邻接矩阵A ∈Rn×n表示。给定输入X，{y1, ...,yl}和A，我们的模型旨在预测未标记点的标签。如图1a所示，我们以Karate俱乐部网络[31]为例，可视化一些中间结果。在这个例子中，数据点（即图节点）没有任何特征，我们将X初始化为单位矩阵。也就是说，每个节点由长度为34的不同的one-hot向量描述。我们的目标是正确地将所有节点分类为两个组（标记为红色和绿色）。在本节的剩余部分，我们将分三步介绍我们的方法。首先，为了实现局部一致性，我们引入了使用图邻接矩阵A的卷积方法。然后，我们提出了一种基于随机游走的卷积方法，用于编码全局一致性的语义信息。最后，我们引入了一个集成的正则化器。01如果边有属性，我们可以添加额外的边节点进行编码。有关详细的预处理，请参考我们实验中的NELL数据集。03.2 局部一致性卷积：Conv A通过直接利用[15]中提出的最先进的方法，我们将基于图结构的卷积Conv A形式化为一种前馈神经网络。给定输入特征矩阵X和邻接矩阵A，网络的第i个隐藏层的输出Z(i)定义为：0˜ A  =  A + I n ，其中I n ∈ R n × n是单位矩阵，是带自环的邻接矩阵，˜ D i , i  = � j ˜ A i , j。相应地，˜ D −  10是归一化的邻接矩阵。Z(i−1)是第(i−1)层的输出，Z(0) =X。W(i)是网络的可训练参数，σ(∙)表示激活函数（例如ReLU，Sigmoid）。在[15]中，作者从[9][12]中的频谱域卷积推导出了公式（7），即公式（6）。在这个背景下，公式（7）中的参数W(i)对应于滤波函数дθ的参数θ。详细的解释请参见[15]。˜ D −  102  Z ( i − 1)在公式（7）中的作用是在每一层中精确地进行1跳扩散过程。也就是说，节点的特征向量通过线性加法丰富了其所有邻居的特征向量。这一发现启发了所提出的概念。也就是说，这种方法可以通过减少半监督学习中的局部一致性例外来进一步改进：附近的点很可能具有相同的标签。例如，从图1a可以看出，直接连接的数据点x8和x30具有不同的标签，它们的卷积特征向量不应该相似。然而，公式（7）无法有效处理这种例外情况。为了验证我们的想法，我们使用t-随机邻居嵌入（SNEs）[17]可视化Karate俱乐部网络的卷积结果，即ConvA的输出。给定X（单位矩阵）和归一化的˜A（见图1b），构建一个具有两个隐藏层的神经网络，所有参数，即W(1)和W(2)，都是随机初始化的。不进行训练。从图1d的可视化结果中，如预期的那样，x8和x30靠得很近。然而，它们属于不同的组。为了验证所提出的概念，我们手动删除x8和x30之间的边，即设置A[8, 30] = A[30, 8] =0。结果，图1e呈现了所有34个数据点的新t-SNE分布，其中x8和x30相距很远。因此，问题在于如何自动减少这类例外的数量。在下一小节中，我们介绍了一种基于PPMI的卷积方法。通过编码语义信息，该方法允许为每个数据点学习不同的潜在表示。通过设计一个集成，我们自动减少了例外的数量，同时避免引入额外的噪声。03.3 全局一致性卷积：Conv P除了由邻接矩阵A定义的图结构信息外，我们还进一步应用PPMI来编码语义信息，即一个矩阵P∈Rn×n。我们首先使用随机游走计算频率矩阵F。然后，基于F计算P，并解释为什么它利用了从频率到语义的知识。最后，我们定义基于P的卷积函数Conv P。0Track: Social Network Analysis and Graph Algorithms for the Web WWW 2018, April 23-27, 2018, Lyon, France0123456789101112131415161718192021222324252627282930313233051015202530051015202530051015202530051015202530−100−75−50−250255075100−200−1000100200081416301−60−40−20020406080−100−75−50−250255075100081416301−300−200−1000100200−150−100−50050100081416301(9)5020(a) Karate俱乐部网络0(b) 归一化邻接矩阵的热图0(c) 归一化PPMI矩阵的热图0(d) Conv A的t-SNE分布0(e) 当设置A[30, 8] = A[8, 30] = 0时0(f) Conv P的t-SNE分布0图1：我们提出的方法的示意图。 (a) 显示了Karate俱乐部网络[31]； (b) 和 (c) 分别显示了归一化邻接矩阵˜A和PPMI矩阵P的热图；(d)、(e)和(f)分别显示了通过Conv A和Conv P获得的不同卷积结果的t-SNE分布。请注意，没有进行训练。0算法1 计算频率矩阵F01: 输入：邻接矩阵A，路径长度q，窗口大小w，每个节点的游走次数γ02: 输出：频率矩阵F∈Rn×n03: 用零初始化F04:05: 将xi设置为路径的根节点06: 对于i从0到γ进行循环07: S = 使用公式(8)进行随机游走获取路径S08: 在S中均匀采样所有的(xn, xm)对，其中w是窗口大小09: 对于每对(xn, xm)进行循环010: F[n, m] += 1.0; F[m, n] += 1.0011: 结束循环012: 结束循环013: 结束循环0计算频率矩阵F。描述随机游走者访问的节点序列的马尔可夫链称为随机游走。如果随机游走者在时间t处于节点xi上，则将状态定义为s(t) =xi。从当前节点xi跳转到其邻居节点xj的转移概率记为p(s(t+1)=xj|s(t)=xi)。在我们的问题设置中，给定邻接矩阵A，我们分配：0p(s(t+1)=xj|s(t)=xi) = Ai,j /计算公式0j A[i, j]. (8)0算法1描述了使用随机游走计算F的过程。时间复杂度为O(nγq^2)；由于参数γ和q是小整数，可以快速计算F。此外，该算法可以通过在图的不同部分同时进行多个随机游走来并行化。随机游走已被用作推荐系统[11]、图分类[1]和半监督学习[30]等问题的相似度度量。在我们的方法中，我们使用随机游走来计算节点之间的语义相似度。计算PPMI。在计算频率矩阵F之后，F的第i行是行向量Fi,:，F的第j列是列向量F:,j。Fi,:对应节点xi，F:,j对应上下文cj。根据算法1，上下文被定义为X中的所有节点。条目Fi,j的值是xi在上下文cj中出现的次数。基于F，我们计算PPMI矩阵P∈Rn×n，计算公式如下：0pi, j = Fi, j /计算公0p i , �  =0计算公式0p � , j  =计算公式0Pi，j = max{pmi i，j =log(pi，j/pi，�p�，j)，0}。0pi，�p�，j)，0}。0Track：社交网络分析和Web的图算法WWW 2018年4月23日至27日，法国里昂Yl,iln ˆZAl,i,(11)∥ ˆZ Pi,: − ˆZAi,: ∥2 .(12)5030应用公式（9）对P进行编码，将语义信息编码到P中。也就是说，pi，j是节点xi出现在上下文cj中的估计概率；pi，�是节点xi的估计概率；p�，j是上下文cj的估计概率。根据统计独立性的定义，如果xi和cj是独立的（即xi在cj中纯粹是随机发生的），那么pi，j = pi，�p�，j，因此pmii，j =0。因此，如果xi和cj之间存在语义关系，则pi，j预计大于xi和cj独立时的概率。因此，当pi，j > pi，�p�，j时，pmii，j应该是正的。如果节点xi与上下文cj无关，则pmii，j可能为负。由于我们关注具有语义关系的（xi，cj）对，我们的方法使用非负的pmi。PPMI已经在自然语言处理（NLP）方面进行了广泛的研究。事实上，PPMI度量在语义相似性任务上表现良好。然而，据我们所知，我们是第一个将PPMI引入基于图的半监督学习领域的人。此外，使用一种新颖的基于PPMI的卷积，我们的方法应用了全局一致性的概念：出现在相似上下文中的图节点倾向于具有相同的标签。图1c可视化了Karate俱乐部网络的归一化PPMI矩阵P。与该网络的邻接矩阵（图1b中显示）相比，至少有两个明显的区别：（1）P减少了中心节点（例如x0和x33）的影响；（2）P在不同数据点之间引发了更多的潜在关系，这不能由邻接矩阵A来描述。基于PPMI的卷积。除了基于邻接矩阵A定义的相似性的卷积ConvA之外，还有一个基于PPMI矩阵P定义的相似性的前馈神经网络ConvP。该卷积神经网络由以下公式给出：0Conv(i)P(X) = Z(i) = σ(D-102 PD-102 Z(i-1)W(i))，(10)0其中P是PPMI矩阵，Di，i =∑jPi，j进行归一化。显然，基于这样的节点上下文矩阵P应用扩散可以确保全局一致性。此外，通过使用与ConvA相同的神经网络结构，两者可以非常简洁地结合在一起。图1f展示了应用于Karate俱乐部网络的ConvP输出的t-SNE分布。我们发现x8和x30现在稍微远离彼此。更令人鼓舞的是，与图1d和图1e中显示的结果相比，ConvP已经正确分类了数据点x0和x14。然而，ConvP没有为x16分配理想的潜在表示。因此，在下一小节中，我们引入了一种新的集成方法来共同考虑局部和全局的一致性。03.4局部和全局一致性的集成0为了共同考虑半监督学习的局部一致性和全局一致性，我们必须克服训练数据标记很少的挑战。也就是说，由于训练数据有限，不能使用一般的集成方法（例如通过连接Conv A和ConvP的输出）。在附录A中，我们详细讨论了这个问题。训练数据的缺乏导致附录A中介绍的集成方法的性能比非集成方法差。因此，除了0为了使用训练数据进行半监督学习，我们进一步推导出一个无监督的正则化项用于集成。图2展示了我们的双图卷积网络方法的架构。除了使用标记数据（即L0(Conv A)在公式（3）中）训练ConvA之外，还引入了一个无监督的正则化项（即Lreд(Conv A, ConvP)在公式（3）中）来训练ConvP，该正则化项针对先前训练模型的后验概率，即训练的L0(ConvA)。为了解释这种自我集成方法，本节的其余部分依次描述了计算L0(Conv A)和Lreд(Conv A, Conv P)以及引入学习算法。计算L0(ConvA)。假设有c个不同的标签用于预测，对Conv A给出的输出Z A ∈ Rn × c逐行应用softmax激活函数。softmax层的输出记为ˆZ A ∈ R n× c。计算L0(Conv A)，即计算所有标记数据点上的交叉熵误差：0L 0 ( Conv A ) =  −10| Y L |0个0l ∈Y L0c个0其中 Y L 是观察到标签的数据索引集合，Y ∈ R n × c是真实标签。计算 L reд ( Conv A , Conv P ) 。L reд 的计算如下：0L reд ( Conv A , Conv P )= 10n0n个0类似于 Conv A ，在应用 softmax 激活函数后，Conv P 的输出表示为 ˆ Z P ∈ R n ×c 。对于所有的 n 个数据点，我们引入一个无监督损失函数，最小化 ˆ Z P 和 ˆ Z A之间的均方差差异。从公式（12）的形式可以看出，我们可以将无监督损失函数视为对Conv P 进行 Conv A 的训练。也就是说，在基于 L 0 的训练之后（即公式（11）），ˆZ A 中的 softmax 分数被解释为对 c个标签的后验分布。通过最小化公式（12）中的损失函数，尽管 Conv A 、Conv P和随机的逐层丢弃进行了不同的转换，每个模型给出的最终预测应该是相同的。如图2所示，我们模型的关键是共享模型参数（即 Eqs. (7) 和 (10) 中的神经网络权重 W ）在Conv A 和 Conv P 中。通过这样做，我们的模型可以共同考虑 Conv A 和 Conv P的观点。尽管共享相同的参数 W ，不同的扩散（即 A 和 P ）和随机丢弃可能导致Conv A 和 Conv P 的预测（即 ˆ Z A 和 ˆ Z P ）不同。0使 ˆ Z A 和 ˆ Z P )不同。然而，我们知道每个数据点只分配给一个类别。因此，模型（由参数 W 表示）预期从 Conv A 和 Conv P给出相同的预测，即最小化公式（12）。因此，训练后的参数 W考虑了 Conv A 和 Conv P中的观点。我们知道最近提出的一种基于类似原理的转换/稳定性损失[23]。通过在数据转换阶段明确地结合先验知识（即我们方法中的扩散矩阵 A 和 P ），我们的集成方法可以被视为进一步的扩展。0Track: Social Network Analysis and Graph Algorithms for the Web WWW 2018, April 23-27, 2018, Lyon, France5040Conv A0Conv P0X0Y0SoftmaxSoft0L 00L reg0Z A0Z P ˆ Z P0ˆ Z A0损失0λ ( t )0L 0 +0λ ( t ) L reg0˜ A0P0共享神经网络的参数0图2：我们方法的架构。输入为：X ∈ R n × k，掩码的 Y ∈ R n × c，˜ A ∈ R n × n，P ∈ R n × n 和时间 t。0他们的方法是通过使用多个神经网络，在数据转换阶段嵌入不同的先验知识。最终模型。算法2描述了我们的双图卷积网络方法的训练过程。损失函数定义为 L 0 ( Conv A ) 和 L reд ( Conv A , Conv P )的加权和。我们设计了一个动态权重函数来实现上述思想。也就是说，在训练过程开始时（即小的 t 值），损失函数主要由监督项 L 0主导。在使用 Conv A 获得标签的后验分布后，增加 λ ( t )强制我们的模型同时考虑 Conv P中编码的知识。由于我们的方法由两个简单的前馈神经网络组成，可以应用传统的参数更新策略。我们的实现使用批量梯度下降（BGD）而不是随机梯度下降（SGD），在每次训练迭代中使用完整的训练数据集。尽管BGD相对较慢，但对于凸误差曲面可以收敛到全局最小值，对于非凸曲面可以收敛到局部最小值。对于无法完全加载到内存的非常大的训练数据集，SGD或小批量梯度下降是内存高效的扩展。最近的一项调查[22]详细讨论了不同的梯度下降方法。04 实验0在本节中，我们通过几个实验结果来验证我们的方法在基于图的半监督学习任务中的性能。首先介绍实验中使用的五个数据集，然后列出比较方法及其实现细节。最后，我们呈现实验结果，并讨论我们的方法的优点和局限性。此外，在附录1中，我们提供和讨论了一些我们方法的变体供参考。04.1 数据集0为了比较，我们使用了之前研究中使用的相同数据集[15][30]。具体来说，有三个引文网络数据集（即Citeseer，Cora和Pubmed）和一个知识图谱数据集（即NELL）。此外，我们构建了一个简化版的NELL数据集进行进一步验证。表1给出了五个数据集的概览；下面给出了详细描述。0算法2 双图卷积网络01：要求：02：X ∈ R n × k：数据特征矩阵03：Y ∈ R n × c：掩码的真实值05：˜ A和P ∈ R n × n：两个扩散矩阵06：λ ( t )：动态权重函数07：h：隐藏卷积层数09：训练好的模型，即参数W ( 1 ) ，...，W ( h ) 。010：随机初始化W ( 1 ) ，...，W ( h ) �  构建网络011：对于t在[0，num _ of  _ epochs]范围内012：ˆ Z A ←  sof tmax ( Conv A ( X )) �  方程(7)013：ˆ Z P ←  sof tmax ( Conv P  ( X )) �  方程(10)014：损失  ← L 0 ( ˆ Z A )  +  λ ( t )L reд ( ˆ Z A , ˆ Z P ) �015：使用∂损失更新W0∂ W ( 1 )0∂ W ( h ) 16：如果收敛则017：跳出循环018：结束如果019：结束循环0表1：五个数据集的概览0数据集 #节点 #特征 #边 #类别0Citeseer 3,327 3,703 4,732 6 Cora 2,708 1,433 5,429 7Pubmed 19,717 500 44,338 3 NELL 65,755 61,278266,144 210 简化版NELL 9,891 5,414 13,142 2100Citeseer。Citeseer数据集包含3,327篇科学出版物，分为六类。引文网络包含4,732个链接。该数据集中的每个出版物由一个0/1值的词向量描述，指示字典中3,703个唯一单词的存在/缺失。仅有3.6%的节点用于训练。Cora。与Citeseer数据集类似，Cora包含2,708篇科学出版物，分为七类。引文0Track: 社交网络分析和Web上的图算法 WWW 2018年4月23日至27日，法国里昂2https://github.com/ZhuangCY/Coding-NN3https://github.com/tkipf/gcn4https://github.com/kimiyoung/planetoid5https://github.com/phanein/deepwalk5050表2：我们DGCN中超参数的值0数据集 W ( 1 ) W ( 2 ) Dropout rate w η0Citeseer，Cora，Pubmed 32 6, 7, 3 10% 2 0.050NELL 64 210 10% 2 0.002 简化版NELL 96 210 30% 2 0.0010网络包含5,429个链接。每个节点由一个1,433维的0/1值向量描述。仅有5.2%的节点用于训练。Pubmed。Pubmed数据集包含19,717篇科学出版物，分为三类。引文网络包含44,338个链接。每个出版物由一个从包含500个术语的字典中提取的词频-逆文档频率（TF-IDF）向量描述。仅有0.3%的节点用于训练。NELL。NELL数据集是从Never Ending LanguageLearning（NELL）知识图谱[6]中提取的。通过将选定的NELL实体（总共9,891个）与ClueWeb09[7]中的文本描述链接起来，NELL中的每个关系都被描述为一个三元组（e h，r，e t）。e h和et分别是头实体和尾实体向量，r表示它们之间的关系。通过将每个（eh，r，e t）拆分为两个边（e h，r 1）和（r 2，et），我们得到一个包含65,755个节点（即实体和关系节点的总数）和266,144个边的图。通过为每个关系节点分配一个不同的独热向量，每个特征向量的长度为5,414 + 55,864 =61,278。每个类别只有一个标记的数据点用于训练。简化版NELL。在简化版NELL中，关系信息（即r）已被删除，并直接添加了实体之间的边。通过计算所有三元组中每个（e h，et）对的共现次数，构建了一个加权邻接矩阵A。在删除小权重边之后，我们得到一个包含9,891个节点（即所有实体的数量）和13,142个边的图。简化版NELL数据集旨在进一步验证我们的双卷积网络方法比基线更稳健（见第4.3节）。04.2 比较方法0我们需要几个先进的基线方法进行比较。由于大多数基线方法都有几个需要精细调整的超参数，我们选择了具有公共源代码的基线方法。由于不同的基线方法使用不同的策略来嵌入图知识，我们确保我们的基线集具有足够的多样性。因此，选择了以下方法。• DGCN.这是我们提出的方法，如算法2中所述。在我们的双图卷积网络（DGCN）实现中，ConvA和ConvP都有两个隐藏层。即，有两个单独的W向量W（1）和W（2）需要在算法2中进行训练。表2详细介绍了我们方法在每个数据集上的实现信息，包括（1）隐藏层的大小；（2）逐层丢失率；（3）算法1中的窗口大小w；和（4）学习率η。关于算法2中的时间正则化权重λ（t）的详细讨论在第4.4节中给出。我们的源代码可供参考。• GCN.图卷积网络（GCN）方法[15]是一种先进的技术，在基线方法中取得了最高的性能。它源自在谱域中进行图卷积的相关工作（即Eq.（6））[9][12]。我们的DGCN方法受到GCN的启发。显然，如果我们设置λ（t）= 0，DGCN将坍缩为GCN。GCN的源代码公开可用。•PLANETOID. 受NLP中的Skipgram模型[18]的启发，PLANETOID[30]使用正负采样来嵌入图信息。在采样过程中，同时考虑标签信息和图结构。由于PLANETOID可以以归纳和传导的方式进行，我们报告更好的结果。PLANETOID的源代码公开可用。•DeepWalk.通过在图上进行随机游走，生成不同的路径。通过将路径视为“句子”，DeepWalk[21]将语言建模技术从单词序列推广到图中的路径。由于我们的方法也使用随机游走来计算PPMI矩阵，因此该方法代表了一个重要的比较。DeepWalk的源代码公开可用。0表3：所有方法的验证准确率：DGCN，GCN，PLANETOID和DeepWalk0方法 Citeseer Cora Pubmed NELL0DeepWalk [21] 43.2% 67.2% 65.3% 58.1% PLANETOID [30]64.7% 75.7% 77.2% 61.9% GCN [15] 70.3% 81.5% 79.0%66.0% DGCN（我们的方法）72.6% 83.5% 80.0% 74.2%0正则化权重λ（t）的详细讨论在第4.4节中给出。我们的源代码可供参考。• GCN.图卷积网络（GCN）方法[15]是一种先进的技术，在基线方法中取得了最高的性能。它源自在谱域中进行图卷积的相关工作（即Eq.（6））[9][12]。我们的DGCN方法受到GCN的启发。显然，如果我们设置λ（t）=0，DGCN将坍缩为GCN。GCN的源代码公开可用。•PLANETOID.受NLP中的Skipgram模型[18]的启发，PLANETOID[30]使用正负采样来嵌入图信息。在采样过程中，同时考虑标签信息和图结构。由于PLANETOID可以以归纳和传导的方式进行，我们报告更好的结果。PLANETOID的源代码公开可用。•DeepWalk.通过在图上进行随机游走，生成不同的路径。通过将路径视为“句子”，DeepWalk[21]将语言建模技术从单词序列推广到图中的路径。由于我们的方法也使用随机游走来计算PPMI矩阵，因此该方法代表了一个重要的比较。DeepWalk的源代码公开可用。0除了上述先进的基线方法，我们还比较了我们提出的方法的一些变体。为简洁起见，这些自我比较在附录A中给出。04.3 结果0类似于描述基线的研究[15][21][30]，我们的比较使用分类准确率指标进行定量评估。表3总结了在三个引文网络数据集（Citeseer、Cora和Pubmed）和知识图谱数据集（NELL）上的实验结果以及使用公共源代码的比较方法的分类结果。我们直接执行了它们的程序，并获得了表中报告的分类结果。根据表3，结果是令人鼓舞的。也就是说，在所有四个数据集上，我们的DGCN方法优于所有基线方法。具体而言，基于随机游走的方法（即DeepWalk）在平均度较低的图上表现不佳。例如，在Citeseer数据集（平均度为2.84）上，DeepWalk的分类准确率较低。0会议: Social Network Analysis and Graph Algorithms for the Web WWW 2018, 2018年4月23日至27日, 法国里昂02550751001251501752000.00.10.20.30.40.50.60.70.8Weight Function Valuef1f2f3f4f50255075100125150175200Epoch0.620.640.660.680.700.720.74f1f2f3f4f5Figure 4: Classification accuracy using different weight func-tions for training. Dataset: Citeseer.5060表4：DGCN和GCN在简化NELL上的比较0%已标记 1% 5% 10% 15% 20% 25%0DGCN 26.0% 62.6% 70.4% 70.6