#paper reading#Semi-supervised Learning on Graphs with Generative Adversarial Nets

????https://dl.acm.org/doi/10.1145/3269206.3271768
文章提出了图的半监督学习的一种新方法GraphSGAN。

摘要

我们研究了生成对抗网（generative attersarial nets，GANs）如何帮助图的半监督学习。我们首先介绍了图的对抗学习的工作原理，然后提出了图的半监督学习的一种新方法GraphSGAN。在GraphSGAN中，生成器和分类器网络进行了一种新颖的竞争博弈。在平衡状态下，生成器在子图之间的低密度区域生成假样本。为了区分真假样本，分类器隐式地考虑了子图的密度特性。提出了一种有效的对抗学习算法，在理论上保证了对传统规范化图拉普拉斯正则化的改进。在几种不同类型的数据集上的实验结果表明，所提出的GraphSGAN明显优于几种最新的方法。GraphSGAN还可以使用小批量进行训练，因此具有可伸缩性优势。

1简介

图的半监督学习在理论和实践中都引起了极大的关注。它的基本设置是给我们一个由一小组有标记的节点和一组大的未标记节点组成的图，目标是学习一个能够预测未标记节点的标记的模型。
关于图的半监督学习有很多工作要做。研究的一个重要范畴是基于图的拉普拉斯正则化框架。例如，朱等。[41]提出了一种称为标签传播（Label Propagation）的方法来学习图上有标记和未标记的数据，后来Lu和Getoor在bootstrap迭代框架下对该方法进行了改进。Blum和Chawla[4]还将图学习问题归结为求图的最小割。朱等。[42]提出了一种基于高斯随机场和形式化图-拉普拉斯正则化框架的算法。Belkin等人。[2] 提出了一种利用边缘分布几何进行半监督学习的正则化方法ManiReg。第二类研究是将半监督学习与图嵌入相结合。Weston等人。[37]首先将深度神经网络纳入图拉普拉斯正则化框架，用于半监督学习和嵌入。Yang等人。[38]提出了联合学习图嵌入和预测节点标记的Planetoid模型。最近，Defferrard等人。[9] 利用局部谱切比雪夫滤波器对图进行卷积以完成机器学习任务。图卷积网络（GCN）[17]及其基于注意技术的扩展[34]展示了强大的能力，并在这个问题上取得了最先进的性能。本文研究了生成对抗网（GANs）在图的半监督学习中的潜力。GANs[13]最初是为生成图像而设计的，通过训练两个神经网络来进行最小-最大博弈：鉴别器D试图区分真样本和假样本，而生成器G试图生成“真实”样本来愚弄鉴别器。据我们所知，利用GANs在图上进行半监督学习的研究还很少。本文提出了一种新的图的半监督学习方法GraphSGAN。GraphSGAN将图拓扑映射到特征空间，并联合训练生成网络和分类器网络。以前的研究[8,18]试图解释半监督甘斯的工作原理，但只发现在互补区域生成适度的假样本有利于分类和在强假设下进行分析。本文从博弈论的角度解释了该模型的工作原理。我们有一个有趣的观察，在子图之间的低密度区域中的假样本可以减少附近样本的影响，从而有助于提高分类精度。在这个观察的指导下，设计了一个新颖的类似GAN的游戏。精密损耗保证了发生器在这些低密度区域产生的样品处于平衡状态。另外，结合观察，图拉普拉斯正则化框架（方程（9））可以利用聚类特性取得稳定的进展。理论上可以证明，这种对抗学习技术可以在生成样本丰富但有限的图上获得理想的半监督学习分类。提出的GraphSGAN评估了几种不同类型的数据集。实验结果表明，graphsgans明显优于几种最新的方法。GraphSGAN还可以使用小批量进行训练，因此具有可扩展性优势。
我们的贡献如下：
•我们引入了GANs作为解决半监督环境下图的分类问题的工具。GraphSGAN在图的低密度区域生成假样本，并利用聚类特性帮助分类。
•我们为GraphSGAN设计了一个新颖的发电机鉴别器之间的竞争博弈，深入分析了训练过程中的动力学、平衡和工作原理。此外，我们还对传统算法进行了改进。理论证明和实验验证都表明了该方法的有效性。
•我们在多个不同比例的数据集上评估我们的模型。GraphSGAN的性能明显优于以前的工作，并且展示了出色的可伸缩性。
论文的其余部分安排如下。在第二节中，我们介绍了必要的定义和定义。在第三节中，我们展示了图形，并详细讨论了为什么以及如何设计模型。第四节对GraphSGAN的工作原理进行了理论分析。我们在第5节概述了我们的实验，并展示了我们的模型的优越性。最后，我们总结了第6节中的相关工作和我们的结论。

2准备工作

2.1问题定义

定义1. 图的半监督学习。给定一个部分标记的图G=（VL∪VU，E），这里的目标是使用与每个节点和图形结构相关联的特征w来学习函数f，以便预测图中未标记节点的标签。请注意，在半监督学习中，训练和预测通常是同时进行的。在这种情况下，学习同时考虑了有标记的节点和未标记的节点，以及整个图的结构。在本文中，我们主要考虑的是传导式学习设置，虽然所提出的模型也可以应用到其他机器学习环境中。此外，我们只考虑无向图，但是对有向图的扩展是直接的。

图1:GraphSGAN工作原理的定性说明。两个标记节点分别为蓝色和橙色，其他节点均为未标记节点。左图是香草标签传播算法的一个坏例子。在这种情况下，nodev3被分配了一个错误的标签，因为它直接链接到节点v+。右图说明了GraphSGAN是如何工作的。它在密度间隙中生成假节点（黑色），从而减少了穿过密度间隙的节点的影响。

GAN[13]是一种通过对抗过程估计生成模型的新框架，其中生成模型G被训练成最适合原始训练数据，而判别模型D被训练来区分真实样本和模型G生成的样本。该过程可以形式化为一个介于D和D之间的最小-最大博弈，具有以下损耗（值）函数：
其中pds是来自训练数据的数据分布，pz（z）是输入噪声变量的先验值。

3模型框架

3.1动机

我们现在介绍如何利用GANs的能力进行图的半监督学习。直接将GAN应用于图学习是不可行的，因为它没有考虑图的结构。为了说明GANs如何帮助图的半监督学习，我们从一个例子开始。图1中的左图显示了基于图的半监督学习的一个典型示例。两个标记节点分别为蓝色和橙色。传统的方法如标签传播[41]没有考虑图的拓扑结构，因此无法区分从节点v+到节点v1、v2和v3的传播。仔细看一下图的结构，我们可以看到有两个子图。我们把这两个子图之间的面积称为密度差。我们的想法是使用GAN来估计密度子图，然后在密度空白区域生成样本。然后我们要求分类器先对假样本进行识别，然后再将其分类。这样，将假样本与真样本区分开来，会导致学习到的分类函数在密度间隙附近具有更高的曲率，从而削弱了穿过密度间隙传播的效果（如右图所示图1）。同时，在每个子图内部，由于有监督的降损技术和一般的平滑技术，例如随机层，对正确标签的置信度将逐渐提高。更详细的分析将在§5.2中报告。

3.2架构

基于GAN的模型不能直接应用于图形数据。为此，GraphSGAN首先使用网络嵌入方法（例如，DeaveWalk（23），线[29 ]，或NetMF[24 ]）学习潜在的分布式表示QiOver每个节点，然后将潜在分布Quig与原始特征向量CeWTWI连接，即席=（Wi，QI）。最后，xiis作为我们方法的输入。图2显示了GraphSGAN的体系结构。GraphSGAN中的分类器D和生成器G都是多层感知器。更具体地，发生器以高斯噪声Z作为输入，并输出具有与席I形状相似的伪样本。在生成器中，使用批处理规范化[15]。生成器的输出层受权重规范化技巧的约束[27]，该技巧具有可训练的权重刻度。GANs中的鉴别器由分类器代替，在输入后加入随机层（加性高斯噪声）和全连通层以达到平滑的目的。在预测模式下去除噪声。全连通层中的参数通过正则化的权重归一化来约束。分类器h（n）（x）中最后一个隐藏层的输出是通过非线性变换从输入x中提取的特征，这对于训练生成器时的特征匹配至关重要[26]。分类器以（M+1）单元输出层和softmax**结束。单元0到单元M−1的输出可以解释为不同类别的概率，单元M的输出表示伪概率。在实践中，我们只考虑前M个单元，并假设假类pmi的输出总是在softmax之前为0，因为从softmax之前的所有单元中减去一个相同的数字不会改变softmax的结果。

图2：我们的模型的概述。伪输入由生成器生成，真实输入通过连接原始特征WI和学习的嵌入qi获得。生成器生成的真实输入和假样本都被输入到分类器中。

3.3学习算法

3.3.1博弈与均衡

Gan试图生成与训练数据相似的样本，但我们希望在密度差距中生成假样本。因此，在提出的GraphSGAN模型中，优化目标必须与原GANs不同。为了更好的解释，我们从博弈论的更一般的角度重新审视了GANs。在一个普通的两人博弈中，G和D有各自的损失函数，并试图使其最小化。他们的损失是相互依存的。我们表示了损耗函数LG（G，D）和LD（G，D）。效用函数VG（G，D）和vd（G，D）是负损失函数。GANs定义了一个零和博弈，其中LG（G，D）=−LD（G，D）。在这种情况下，唯一的纳什均衡可以通过极大极小策略来达到[35]。找到平衡点相当于求解优化：
古德费罗等人。[13] 证明了如果VD（G，D）定义为式1中G在平衡点生成服从数据分布的样本。生成样本pg（x）的分布是真实数据pd（x）分布的近似值。但我们希望在密度间隙中生成样本，而不是仅仅模仿真实数据。所以，原来的甘斯不能解决这个问题。在所提出的GraphSGAN中，我们修改了LD（G，D）和LG（G，D）来设计一个新的博弈，在这个博弈中，G将在平衡点的密度间隙中生成样本。更准确地说，我们希望真假样本在其最终代表层（n）（x）中如图3所示进行映射。

图3:h（n）（x）中预期平衡的图示。不同的训练点是不同的训练点。未标记的样本（白点）映射到特定的簇中。不同的密度间隙出现在中心，其中是生成的样本（黑点）。

因为“密度间隙”的概念在代表层中比在图中更直接，我们定义当且仅当节点位于h（n）（x）层中的密度隙时，节点处于密度间隙中。第3.2节解释了如何将节点映射到代表层。设计背后的直觉是基于著名的“维度诅咒”[10]。在像h（n）（x）这样的高维空间中，中心区域远比外部区域窄。中心区域的培训数据很容易成为中心[25]。中心点经常出现在其他类样本的最近邻上，这可能会严重影响半监督学习，成为一个主要的难点。因此，我们希望中心区域成为一个密度间隙而不是一个团簇。我们将LD（G，D）和LG（G，D）定义如下，以保证预期的平衡。

接下来，我们用LD（G，D）和LG（G，D）解释这些损失项，并详细说明它们是如何生效的。

3.3.2鉴别损失

在均衡状态下，没有一个球员可以改变他们的策略来单方面减少他的损失。假设G在中心区域生成均衡样本，我们提出了D在h（n）（x）中达到预期均衡的四个条件：（1）不同类别的节点应映射到不同的簇中。（2） 标记和未标记的节点都不应/。。。；映射到中心区域，以使其成为一个密度间隙。（3） 每个未标记的节点都应该映射到一个表示特定标签的集群中。（4） 不同的集群应该足够远。满足条件（1）的最自然的方法是监督损失损失。lossupis定义为M个类上的预测分布与一个实数标签的热表示之间的交叉熵。

其中xl是带标签的nodesVL的输入集。条件（2）相当于原GAN中D的目的，因为g在中心密度隙中产生假样本。因此，我们仍然使用方程式1中的损耗，称之为损耗。当真的或假的错误分类发生时，分类器D会产生损失。

其中XUis对未标记的NoDeVu的预处理输入集；G（z）是生成样本的分布；而p（m席席）表示XI的预测伪概率。条件（3）请求SD为每个未标记的节点分配一个明确的标签。我们通过增加一个熵正则化项lossent来解决这个问题，即M个标签上的分布熵。熵是概率分布不确定性的度量。长期以来，它已成为半监督学习中的一个正则化术语[14]，并在[28]中首次与GANs结合。减少熵可以鼓励分类器为每个节点确定一个明确的标签。

条件（4）扩大了密度差距，有助于分类。我们利用“拉离期损失”来满足这一要求。losspt为最初设计用于在普通干草中产生不同的样本。它是批处理中向量之间的平均余弦距离。它使h（n）（x）层中的表示尽可能远离其他层。因此，它也鼓励集群远离其他集群。

其中Xi、Xj在同一批中，M是批量大小。

3.3.3发电损耗

同样，假设D满足上述四个条件，我们也有两个条件可以保证G在h（n）（x）中达到预期平衡：（1）G生成映射到中心区域的样本。（2） 生成的样本不应在唯一的中心点过度拟合。对于条件（1），我们使用特征匹配损失进行训练[26]。它使生成样本与真实样本的中心点之间的距离最小化。实际上，在训练过程中，中心点被一个真实的批处理所取代，这有助于满足条件（2）。这些距离最初是用L2范数测量的。（但是，在实践中，我们发现L1-norm也能很好地工作，性能甚至稍好一些。）
条件（2）要求生成的样本覆盖尽可能多的中心区域。我们还使用一个拉脱损失项（方程式6）来保证这个条件的满足，因为它鼓励G生成不同的样本。在中心性和分集性之间需要权衡，因此我们使用一个超参数λ2来平衡lossfm和losspt。D中的随机层给假输入增加了噪声，这不仅提高了鲁棒性，而且防止了假样本的过拟合。

3.3.4 training

GANs通过迭代最小化D和G的损失来训练D和G。在博弈论中，它被称为近视最佳反应[1]，一种寻找平衡点的有效启发式方法。格拉夫斯甘也是这样训练的。训练的第一部分是将图中的节点转换为特征空间中的向量。我们使用[29]行对q进行预处理，它在我们的数据集上执行快速而稳定的操作。我们还测试了其他的网络嵌入算法，发现在分类方面有相似的性能。为了加快收敛速度，采用邻域融合技术重新计算节点的特征w。设N e（vi）是vi的邻域集，nodevi的权重由
决定。邻域融合的思想类似于使用注意机制的预处理技巧[34]。在主训练循环中，我们迭代地训练D和g。为了计算LD，我们需要三批标记的、未标记的和生成的样本分别是损失标记数据.lossunis基于未标记和生成的数据计算。理论上，lossun还应该考虑标记数据，以确保它们被归类为真实数据。但是，lossuphas将标签数据正确地分类为其真实标签，因此不必考虑lossun中的标签数据。lossent只考虑未标记的数据，而losspts应同时“拉走”已标记和未标记的数据。通常需要三个超参数来平衡四个损失的规模。我们在GraphSGAN中只使用了两个参数λ0和λ1，因为在半监督设置下，由于标记样本较少，损失很快就会优化到接近0。训练G需要实批数据和生成批数据。lossf M比较h（n）（x）中的实数据和生成数据的批处理中心，LOSSPT测量生成数据的多样性。我们总是希望G在中心区域生成样本，这是在讨论LDin第3.3.2节时的一个假设。因此，在每次训练D之后，我们训练G几个步骤来收敛。

4理论基础

我们从理论上分析了为什么GANs可以帮助图的半监督学习。在第3.1节中，我们声称其工作原理是减少穿过密度间隙的标记节点的影响。针对深层神经网络训练中直接分析动力学的困难，本文基于图-拉普拉斯正则化框架进行分析。
图拉普拉斯正则化框架的损失函数如下
其中y′i表示节点vi的预测标签。损失（·，·）函数测量实际和预测标签之间的监督损失。neq（·，·）是表示不相等的0或1函数。
式中，A和~A是相邻矩阵和负规范化图拉普拉斯矩阵，deg（i）表示vi的阶数。需要注意的是，我们的方程与[40]略有不同，因为我们只考虑显式的预测标签，而不是标签分布。归一化是降低边缘节点影响的核心。我们的方法很简单：生成假节点，将它们链接到最近的实节点，然后求解图的拉普拉斯正则化。假标签不允许分配给未标记的节点，损失计算只考虑真实节点之间的边。生成前后的唯一区别是边缘节点的度发生了变化。然后正则化参数αij发生变化。

4.1证明

我们分析生成的假样本如何帮助获得正确的分类。

由于αij减小，推论1很容易推导出来。随着新的假样本的产生，基本真相的损失继续减少。这表明基本事实更有可能被获取。然而，可能存在其他分类解决方案，其损失减少得更多。因此，我们将进一步证明，我们可以在合理的假设下，以足够的生成样本进行完美的分类。
定义3。局部图。我们定义了由所有标记为c（aka）的节点诱导的子图。以及它们的其他邻居Nec作为部分图Gc。
假设2。连通性。每个类中所有内部节点所诱导的子图是连通的。此外，每个边缘节点至少连接到同一类中的一个内部节点。
大多数现实世界中的网络都很密集，足够大，足以满足假设2。这实际上意味着另一个弱假设，即每个类至少存在一个标记节点。这通常由半监督学习的设置来保证。设mc是Gc中边缘节点之间的边数。此外，我们将degc定义为节点的最大度数，而loss是误分类标记节点的监督损失。

假设Cmin给vi∈M∩Vc，vj∈I和（vi，vj）∈E，让vi赋c′。如果我们将vi的标签改为c，那么vi与其内部邻居之间的αij将被排除在损失函数之外。但是，在损失函数中，可能会加入一些其他边的权重。让λ∆表示损失的变化。下面的等式将表明损耗的减少会导致矛盾。
假设Cmin避免了上面讨论的所有情况，而vi∈M∩vc仍然被赋予c′。在假设2下，存在一个连接vi的内部节点vj。正如我们所讨论的，vj在Cmin中必须被赋值为c，这导致了矛盾。因此，C′是Gc最佳二元分类的唯一选择。这意味着c类中的所有节点都被正确分类。但是如果在Gc中，Nec中的所有节点都被标记为c′？实际上，不管分配了哪些标签，Vc中的所有节点都是正确分类的。如果N个节点除c和c′外都指定了标签，则证明几乎相同，c′仍然是最优的。如果Nec中的任何节点被错误地分配了标签c，唯一的结果就是鼓励节点被正确地分类为c。
最后，分析对所有类都是正确的，因此所有节点都将被正确分类。

5实验

我们在两个引文网络和一个实体抽取数据集上进行了实验。表1总结了三个数据集的统计数据。为了避免过度调整网络架构和超参数，在我们所有的实验中，我们都使用默认的训练和测试设置。具体地说，该分类器有5个隐藏层（500500250250250）单元。随机层为零中心高斯噪声，输入标准差为0.05，隐层输出为0.5。生成器有两个500个单元的隐藏层，每个隐藏层后面都有一个批处理规范化层。指数线性单元（ELU）[6]用于提高学习精度，但G的输出层使用tanh来生成从-1到1的样本。算法1中的权衡因子为λ0=2，λ1=1，λ2=0.3。模型由Adam[16]优化，其中β1=0.5，β2=0.999。所有参数都是用Xavier[12]初始化器初始化的。

5.1Results on Citation Networks

两个引文网络包含论文和论文之间的引文链接。每一篇论文都有以单词包表示的特征，并且基于主题属于特定的类，例如“数据库”或“机器学习”。目的是把所有的论文分类成正确的类别。为了公平比较，我们严格遵循[38]中的实验设置，每堂课选择20个随机实例（论文）作为标记数据，1000个实例作为测试数据。报告的性能是10个随机拆分的平均值。在这两个数据集中，我们将我们提出的方法与三类方法进行了比较：

•基于正则化的方法，包括LP[41]、ICA[20]和ManiReg[2]；基于嵌入的方法，包括DeepWalk[23]、sememb[37]和Planetoid[38]；以及基于卷积的方法，包括Chebyshev[9]、GCN[17]和GAT[34]。我们使用early stop对模型进行训练，500个节点进行验证（Cora上平均20个时代，citeeser上平均35个时代）。每个epoch包含100个批，批大小为64。表2显示了所有比较方法的结果。我们的方法明显优于所有基于正则化和嵌入的方法，性能也比Chebyshev和图卷积网络（GCN）好得多，同时也略优于带注意的GCN（GAT）。与基于卷积的方法相比，GraphSGAN对标记数据更为敏感，因此可以观察到更大的方差。差异较大的原因可能是甘肃训练的不稳定性。例如，模式崩溃现象[33]将阻碍GraphSGAN在密度间隙中均匀地生成假节点。这些不稳定性是目前遗传算法研究中的主要问题。更先进的稳定GraphSGAN的技术将留待将来的工作。

5.2验证

我们通过实验验证对GraphSGAN有更多的了解。有两个验证实验：一个是关于期望平衡，另一个是验证GraphSGAN的工作原理。5.2.1平衡验证。第一个实验是关于GraphSGAN是否在§3.3.2中描述的平衡点收敛。在图4（a）中，我们使用t-SNE算法将citeser实验中的训练过程可视化（有关详细的实验设置，请参阅第5节）。一开始，G生成的样本与实际样本有很大的不同，聚类的边界是模糊的。在训练过程中，分类器D逐渐学习非线性变换inh（n）（x），将真假样本映射成不同的聚类，而G则试图在真实样本的中心区域生成样本。小批量训练、lossptin-lga和高斯噪声可以防止G在唯一的中心点上过度拟合。对抗训练最终达到了预期的平衡点，假样本在20个时代之后被真实样本群包围在中心区域。

5.2.2工作原理验证

第二个实验是验证所提出的工作原理。我们在§4理论上证明了减少边缘节点的影响有助于分类。但是我们还需要进一步验证生成的样本是否减少了边缘节点的影响。一方面，在h（n）（x）中，节点被映射成不同的、远的簇。另一方面，“影响”与“平滑度”有关。例如在图-拉普拉斯正则化框架中，为了保证光滑性，相邻节点的标签之间的差异显式最小化。因此，我们检验了分类器函数在密度间隙附近的平滑度。用每一类的最大概率梯度的范数来测量夏尔的光滑度。

5.3实体提取结果

DIEL数据集[3]是用于信息提取的数据集。它包含文本中提到的每个实体的预先提取的特征，以及一个将实体提到的实体连接到相应的坐标项列表的图形。其目的是从给定的特征向量、图拓扑和一些已知的医学实体中提取医学实体。同样，为了进行比较，我们采用了与原始论文[3]相同的设置，包括数据分割和不同运行的平均值。由于特征是非常高维的稀疏向量，我们采用截断SVD算法将其维数降到128。我们在α=0的项串节点上使用邻居融合，因为只有实体提及节点具有特征。我们将一个模型给出的前k（k=24万）个实体视为正，并比较不同方法对前k名结果的召回率。请注意，由于基本事实中的许多项没有出现在文本中，因此在这个数据集中召回的上限是0.617。我们还将其与不同类型的方法进行了比较。表3报告了平均值召回@k所有比较方法的10次标准数据分割。DIEL代表了文献[3]中的方法，它利用多类标签传播的输出来训练分类器。行星的结果是归纳结果，在三个版本中表现最好。由于DIEL数据集有数百万个节点和边，这使得全批训练（例如GCN）不可行（使用稀疏存储，内存需求>200GB），我们不在这里报告GCN和GAT。从表3可以看出，我们的方法GraphSGAN实现了最佳性能，显著优于所有比较方法（p−value≪0.01，t−test）。

5.4空间效率

由于GCN不能处理大规模的网络，我们在实践中考察了GraphSGAN的内存消耗。GPU已经成为深度学习算法的标准平台。与主存储器相比，GPU上的内存通常非常有限。我们比较了图5中不同类别的四种代表性算法的GPU内存消耗。标签传播不需要GPU，我们将其结果显示在CPU上以便于比较。对于小型数据集，GraphSGAN结构最复杂，占用空间最大。但是对于大型数据集，GraphSGAN使用的GPU内存最少。线性规划通常通过求解方程来实现，其空间复杂度为O（N2）。这里我们使用“传播实现”来节省空间。GCN需要完整的批处理训练，不能处理数百万个节点的图。采用小批量的方法训练小行星和图形，使空间消耗与节点数无关。DIEL数据集中的高维特征也具有挑战性。Planetoid使用稀疏存储来处理稀疏特征，GraphSGAN使用截断SVD来降低维数。5.5对抗性标签传播对抗性学习是否有助于传统的半监督学习算法？是的，我们已经从理论上证明了减少边缘节点的影响有助于§4中的分类。因此，为了验证我们的证明（参见§4），我们进一步提出了一个带有生成样本的图拉普拉斯正则化的对抗性改进。我们通过在标签传播框架[40]中加入对抗性学习来进行实验，看看性能是否能得到改善。为了合并节点的特征，我们在特征空间x中通过将节点链接到其k个最近邻来重构图。我们在本实验中使用citeser网络，其设置如§5.1 meanwhilek=10所述。生成足够的损坏数据是时间消耗，因此我们直接确定边缘节点BYPF（席）> TAV（TAU是一个阈值），因为
其中pf（x）是x是假的概率。然后，我们增加边缘节点的度来减少它们的影响。图6显示了结果。较小的pf意味着更多的边缘节点。曲线表明，τ=0.1是区分边缘节点和内部节点的良好阈值。r越大，性能越好，这就鼓励我们在密度差距中生成尽可能多的假节点。通过增加边缘节点的度，LP的性能得到了改善，但仍低于GraphSGAN。我们认为，主要原因是GraphSGAN使用神经网络来捕捉特征之间的高阶相互关系。因此，我们也尝试使用有监督的多层感知器的第一层输出重构图，并进一步观察到性能的改善，突出了神经网络在这个问题上的能力。

6相关工作

主要分为三类：图的半监督学习算法、半监督学习的GAN和基于GAN的图上应用。我们对它们进行了讨论，并总结出我们提出的模型与这些工作的主要区别如下：

6.1图的半监督学习

如§1所述的图的半监督学习，以往的研究方法可分为三类。标签传播[41]是图-拉普拉斯框架下的第一个工作。标记的节点继续将其标签传播到相邻节点，直到收敛。在揭示了LP与图的拉普拉斯正则化之间的关系之后，该方法通过复杂的平滑正则化[2,42]和bootstrap方法[20]加以改进。这种方法主要关注图的局部光滑性，而忽略了图1的聚类特性，使得图1这样的情况变得很困难。Deepwalk[23]是图嵌入的第一个工作。DeepWalk作为一种无监督的节点潜在表示学习方法，与SVM分类器相结合，可以很容易地转化为半监督的基线模型。因为标签帮助学习嵌入，然后帮助分类，Planetoid[38]联合学习图嵌入和预测节点标签。图嵌入成为GraphSGAN的一个步骤，为了获得更好的性能，我们加入了GANs。GCN[17]是第一个用于图的半监督学习的图卷积模型。GCN中的每一个滤波器都学习每个特征在谱域上的线性变换，并将它们组合起来。更复杂的图卷积方法[9，34]显示出更好的性能。图卷积的一个明显的缺点是占用大量空间，GraphSGAN克服了这个缺点。

6.2GANs for Semi-supervised Learning

用于半监督学习的半监督GANs（SGAN）是在计算机视觉领域首次提出的[22]。SGAN只是用一个分类器代替了GANs中的判别器，与最先进的半监督图像分类模型相比，它更具竞争力。为了防止发电机过度训练，首次提出了特征匹配损失[26]。人们发现这种技术有助于半监督学习，而工作原理尚未探索[26]。文献[8]分析了半监督分类性能与发电机质量的权衡关系。Kumar等人。[18] 通过估计数据流形的切线空间来寻找一种平滑方法。此外，各种辅助结构与半监督GANs相结合，可以更准确地对图像进行分类[5,11,21]。所有这些工作都集中在图像数据和利用CNN架构上。GraphSGAN将这种思想引入到图形数据中，并首次设计了一个新的类似GAN的游戏，其工作原理清晰、令人信服。

6.3基于图的GAN应用

尽管我们首先将GAN引入到基于图的半监督学习问题中，但GAN在许多其它的图上机器学习问题上取得了成功。一类是关于图形生成的。刘等。[19] 提出了一种由多个GANs组成的层次结构来生成图形。该模型保持了训练图的拓扑特征。Tavakoli等人。[32]将GANs应用于社交网络中的链接形成。生成的网络保留了链接的分布，并将隐私泄露的风险降到最低。另一类是关于图嵌入的。在图[36]中，生成器学习节点的嵌入并由鉴别器求解基于嵌入的链路预测任务。在平衡点得到了面向分类的嵌入。Dai等人。[7] 利用对抗性学习来规范图形表示的训练。Generator将传统算法中的嵌入转化为新的嵌入，既保留了结构信息，又模拟了先验分布。

7结论和未来的工作

我们提出了GraphSGAN，一种利用GANs在图上进行半监督学习的新方法。我们设计了一种新的发生器和分类器之间的竞争博弈，在均衡状态下发生器在密度间隙中生成样本。几个复杂的损失条件共同保证了预期的均衡。在三个基准数据集上的实验证明了该方法的有效性。我们还提供了一个深入的工作原理背后提出的模型GraphSGAN。生成的样本减少了密度间隙中邻近节点的影响，使决策边界更加清晰。这些原理可以在理论保证和实验验证的基础上，对传统的基于图拉普拉斯正则化的算法进行改进。GraphSGAN是可伸缩的。在DIEL数据集上的实验表明，我们的模型在大型图上也表现出了良好的性能。作为今后的工作，一个潜在的方向是研究更理想的平衡点，进一步稳定训练，加快训练速度，强化该方法的理论基础，并将该方法推广到其他图数据任务，如[30]。致谢这项工作得到了（2015AA124102）、国家自然科学基金（616310136156130160）和英国皇家学会牛顿高级奖学金的资助。