核心思想：通过信息瓶颈实现链接预测的数据增强方法

《ACM Transactions on Knowledge Discovery from Data》：CORE: Data Augmentation for Link Prediction via Information Bottleneck

　　摘要
要查看此由AI生成的摘要，您必须具有高级访问权限。了解更多信息请登录。

链接预测（LP）是图表示学习中的基本任务，在多个领域中有广泛的应用。然而，由于图中的噪声或虚假信息以及图数据固有的不完整性，LP模型的泛化能力往往受到影响。为了解决这些挑战，我们借鉴了信息瓶颈原理，提出了一种新的数据增强方法——Complete and Reduce（CORE），以为LP模型学习紧凑且具有预测性的增强数据。具体来说，CORE旨在恢复图中的缺失边，同时去除图结构中的噪声，从而提高模型的鲁棒性和性能。在多个基准数据集上的广泛实验表明，CORE相对于现有方法的适用性和优越性，展示了其在图表示学习中作为强大LP方法的潜力。

AI摘要 AI生成的摘要（实验性）
此摘要是使用自动化工具生成的，并非由文章作者编写或审核。它旨在帮助发现、帮助读者评估相关性，并协助来自相关研究领域的读者理解该工作。它旨在补充作者提供的摘要，后者仍然是论文的正式摘要。完整文章是记录的权威版本。点击此处了解更多信息。点击此处对摘要的准确性、清晰度和实用性进行评价。这样做将有助于改进未来的生成版本。要查看此由AI生成的通俗语言摘要，您必须具有高级访问权限。

1 引言
图结构化数据在各种领域中无处不在，包括社交网络[36]、推荐系统[32]和蛋白质-蛋白质相互作用[56]。链接预测（LP），即预测图中缺失或未来的边，是图中的基本问题。多年来，已经提出了许多LP算法，从基于启发式的链接预测器[1, 28, 36, 80]到更复杂的基于图神经网络（GNN）的方法[30, 44, 72]。
LP中的一个主要挑战是图数据的质量、可靠性和真实性。在许多现实世界场景中，由于信息不完整、数据标注错误以及测量设备或人为错误引入的噪声等因素，数据收集可能会很困难[10, 81]。因此，基于收集的数据构建的图可能包含缺失或错误的边。这可能会影响LP模型的性能。此外，过度依赖噪声图会妨碍模型区分真实边和虚假边的能力，从而损害模型的泛化能力。因此，如何在噪声图上保持LP模型的鲁棒学习能力和泛化能力仍然是一个未解决的问题。
为了减轻模型在质量较差的噪声数据上的性能下降，数据增强（DA）作为一种强大的技术出现，通过人工扩展原始数据实例的转换版本来增加训练数据集，主要应用于计算机视觉领域[34, 50]。然而，在LP的背景下，很少有工作提出克服模型在噪声图上的限制[76]。例如，CFLP [77]通过将反事实链接补充到观察到的图中来采用因果推断。Edge Proposal [51]试图将高潜力的边注入图中作为信号增强预处理步骤。然而，这些工作没有考虑固有的噪声或由增强过程带来的噪声，隐含地假设观察到的图真正反映了潜在的关系。
在本文中，我们研究了如何增强图数据以完成两个主要目标：消除数据中固有的噪声并恢复图中的缺失信息。为了使用鲁棒、多样且无噪声的数据进行增强，我们采用了信息瓶颈（IB）原理[57, 58]。IB提供了一个框架，用于限制信息从输入到输出的流动，能够在保留其对当前任务预测相关性的同时实现最大程度的压缩表示[2]。IB施加的自适应正则化有助于仅保留数据的必要和有信息的部分，从而去除噪声。此外，由IB引导的适当扰动可以帮助恢复缺失信息，从而获得更完整和更鲁棒的表示。学习这种有效的表示特别有吸引力，因为它为我们提供了一个灵活的DA管道，我们可以在此管道中无缝集成其他DA技术，而不必担心它们可能引入的额外噪声。

2 初步介绍
在本节中，我们将介绍文章中使用的符号和概念。
图和LP。设G=(V,E,X)表示一个无向图，其中V是节点集，节点数量为n，索引为{i}i=1n。Nv 是节点v的邻域。E?V×V表示观察到的边集，Xi∈X表示节点i的特征。未观察到的边集，表示为Ec?V×V?E，包括缺失的边或预计在原始图G中形成的边。因此，对于那些边(i,j)∈E∪Ec，我们可以分配标签Y=1并将它们视为正样本，而对于其余的{(i,j)?V×V|(i,j)?E∪Ec}，我们分配标签Y=0作为负样本。根据给定的图G，LP任务的目标是计算节点相似性得分，以识别未观察到的边集Ec [37]。随着时间的推移，提出了许多用于LP任务的启发式模型，包括Common Neighbor（CN）[36]、Adamic–Adar Index（AA）[1]、Resource Allocation（RA）[80]和Katz指数[28]。虽然这些传统方法有效地利用了图的拓扑结构，但基于GNN的模型[30, 72]展示了利用图的结构和节点属性的更高级能力。
子图LP。尽管一些链接预测器（如Katz指数和PageRank [7]）需要整个图来计算目标链接的相似性得分，但许多其他模型仅依赖于目标链接周围的局部邻域进行计算。例如，CN预测器只需要目标链接的1跳邻域，通常，l层GNN需要目标链接的l跳邻域。此外，Zhang和Chen [72]已经证明局部信息足以用于LP任务。因此，特定目标链接的LP任务可以重新表述为基于目标链接局部邻域的图分类问题，以确定该链接是否存在[14]。正式地，给定由节点对(i,j)的l跳可达性诱导的子图G(i,j)l，子图LP是一个预测子图标签Y∈{0,1}的任务，其中Y=1表示目标链接存在，反之亦然。

3 提出的框架：CORE
在本节中，我们介绍了我们提出的用于LP的两阶段DA框架CORE。我们首先介绍Complete阶段，该阶段旨在恢复原始图中的缺失边。接下来，我们讨论Reduce阶段，这是我们提出方法中最关键的组成部分，旨在消除图中的噪声和虚假边。最后，我们概述了一个利用图信息瓶颈（GIB）[67]来修剪膨胀边的实际实现。该框架的概述如图1.3所示。

3.1 完成阶段：膨胀缺失连接
数据收集过程本质上容易出错，这可能导致原始图中的结构信息不完整或甚至错误。此外，LP任务的性质涉及识别缺失的或可能新形成的边，这隐含地假设图数据是不完整的。因此，减轻图结构的不完整性是有益的。在定理1中，我们还将看到膨胀缺失边如何帮助识别决定链接是否存在的关键组成部分。Complete阶段的整个过程在算法1中有详细说明。

实施。我们从Singh等人[51]介绍的简单直接的方法开始，用额外的边来膨胀原始图。尽管也可以将更复杂的图完成方法[63]插入Complete阶段，但我们发现使用一种简单且计算成本低的算法就足以有效增强图结构。
由于大多数现实世界图的稀疏性，潜在缺失边的数量与节点数量的平方成正比O(n^2)。对所有非连接的节点对进行评分在计算上可能是禁止性的。为了减少候选节点对的大小，我们只考虑那些至少有一个潜在添加到图中的CN的非连接对（算法1中的步骤1-6）。随后，我们可以使用任何LP方法来对这些候选节点对进行评分（算法1中的步骤7-11）。对于大规模的数据集，如OGB-Collab [24]，我们可以依赖于非参数启发式方法的更快计算。对于中等规模的图，可以选择任何启发式方法或基于GNN的方法，如图卷积网络（GCN）[31]和SAGE [20]。需要注意的是，只对具有公共邻居的节点对进行评分是一个实际的选择。大多数现实世界的图，受诸如同配SBM [22]或Watts–Strogatz模型[65]等流行模型的支配，显示出具有公共邻居的节点对有更高的连接可能性。因此，这种设计在计算效率和实证效果之间取得了平衡，我们认为这是一个微小但至关重要的权衡。实证调查可以在附录C.3中找到。在对所有候选节点对进行评分之后，我们根据它们的相似性评分对它们进行排序，并选择前k个节点对Eext添加到原始图中，其中k是一个超参数（算法1中的步骤12-14）。因此，图G变为G+=(V,E∪Eext,X)。需要注意的是，尽管我们将这些预测的链接添加到图中，但我们将其标记为膨胀边，以将其与原始图区分开来。这些膨胀边不会被用作后续阶段的训练信号，而只是作为图拓扑结构的补充。这种区分很重要，因为我们可以容忍输入空间中的噪声边，但不想在我们的DA过程中引入任何噪声到标签中。

3.2 缩减阶段：修剪噪声边
减少阶段是我们CORE DA框架的核心方面。受到GSAT [40]的启发，我们利用GIB [67]来参数化一个 reducer，它将图结构限制为一个最小但足够的图组件，以便进行LP。预期的结果图组件可以实现三个目标：（1）从数据中去除与任务无关的信息（方程式（6）中的正则化）；（2）修剪图结构，以便只有最具预测性的图组件保留下来用于推理（方程式（6）中的对数似然）；以及（3）为原始数据提供多样化的增强（边采样步骤）。我们首先介绍解耦每个链接的DA的必要性。然后，我们讨论GIB目标及其可行的变分界限。最后，我们介绍了我们在减少阶段DA的实现。

图数据的相互依赖性。在LP任务中，我们感兴趣的数据实例是图中的链接。然而，与图像不同，图中的链接是相关的；每个链接的存在和属性相互依赖。因此，当对特定链接应用DA时，它将不可避免地影响其他链接的环境，特别是那些附近的链接。这可能会导致次优结果，因为链接将相互竞争以获得最适合自己的增强。此外，当独立同分布（i.i.d）假设不成立时[67]，应用IB原则在计算上变得不可行。

为了解决这些问题，我们将LP重新表述为一个子图LP。子图LP允许解耦每个链接的重叠环境，从而可以为每个链接分别进行不同的DA。具体来说，对于每个节点对（i,j），我们从整个图G+中提取其l-hop包围子图G(i,j)+；l。为了简化表示，在没有歧义的情况下，我们可以省略跳数并将子图表示为G(i,j)+。值得注意的是，以前的工作也采用了类似的策略来处理图数据的非i.i.d性质[64, 78]，当扰动数据时。在第5.6节中，我们实证检验了为不同目标链接量身定制的最佳DA。值得注意的是，从单个边派生的DA可能会根据所考虑的目标链接而有所不同。

GIB。一般来说，IB旨在从输入X中学习一个简洁的表示Z，该表示也对输出y有很好的表达能力，通过潜在表示与输入/输出之间的互信息来衡量[2, 58]。因此，目标是：maxZI(Z,Y) s.t. I(X,Z)≤Ic, (1)，其中I(?,?)表示互信息，Ic是信息约束。在LP的背景下，我们可以将包围子图G(i,j)+视为输入X，包括节点属性和图结构。Y是在(i,j)处的链接的存在，Z是潜在表示。

虽然原始的GIB [67]限制了图的两个节点属性和图结构的信息流，但我们在LP任务的DA中提议只限制结构信息。与图中的节点属性相比，图结构对LP任务来说更为关键[37, 44]。此外，许多没有节点属性的图仍然需要LP。因此，我们定义我们的目标为：maxG(i,j)±∈Gsub(G(i,j)+)I(G(i,j)±,Y) s.t. I(G(i,j)±,G(i,j)+)≤Ic, (2)，其中G(i,j)±∈Gsub(G(i,j)+)是从膨胀图G(i,j)+中修剪出来的子图。换句话说，我们旨在找到一个对LP任务既最具预测性又最简洁的子图。我们假设这个图简化过程可以在保留有益的附加信息的同时，修剪掉前一个完整阶段引入的噪声边。我们的方法与GSAT [40]和IB-subgraph [71]有类似的精神，因为我们在探索找到对任务最必要的子图结构。

接下来，通过引入一个拉格朗日乘数β，我们得到了目标的无约束版本：minG(i,j)±∈Gsub(G(i,j)+)?I(G(i,j)±,Y)+βI(G(i,j)±,G(i,j)+)，(3)，其中β是一个超参数，用于平衡预测能力和压缩之间的权衡。

互信息项I(?,?)的计算通常在计算上是不可行的。为了解决这个问题，我们遵循Alemi等人[2]、Wu等人[67]和Miao等人[40]的工作，为方程式（3）推导出一个可行的变分上界。详细推导在附录D中提供。为了近似第一项I(G(i,j)±,Y)，我们推导出一个变分下界。下界可以表述为：I(G(i,j)±;Y)≥E[log?qθ(Y|G(i,j)±)]。(4)本质上，qθ是我们模型的预测器，它可以是一个参数化的GNN。

对于第二项I(G(i,j)±,G(i,j)+)，我们通过引入一个变分近似r(G(i,j)±)来为G(i,j)±的边际分布推导出一个上界：I(G(i,j)±,G(i,j)+)≤E[KL(p?(G(i,j)±|G(i,j)+)||r(G(i,j)±)], (5)，其中p?是用于修剪噪声边的 reducer。然后，我们可以将所有这些放在一起，得到要最小化的经验损失：L≈1|S|∑(i,j)?S∈V×V[?log?qθ(Y|G(i,j)±)+βKL(p?(G(i,j)±|G(i,j)+)||r(G(i,j)±)]。(6)接下来，我们讨论如何在减少阶段参数化预测器qθ和reducer p?，以及边际分布r(G(i,j)±的选择。

3.3 减少阶段的实现
减少阶段的整体架构如图2所示，算法详细说明在算法2中。需要注意的是，预测器qθ和reducer p?都使用GNN编码器来编码图表示，无论是用于预测还是图修剪。这两个组件可以使用相同的GNN编码器，因为整个减少阶段的训练是端到端的。这个共享的编码器允许更高效的学习，并减少了模型中所需的参数数量。

图2. 减少阶段从围绕目标链接(i,j)的膨胀子图G(i,j)+开始。我们首先应用GNN来编码节点表示，然后从节点编码中得到边表示。为了计算每条边的采样概率分数，我们使用一种注意力机制，将边表示与子图池化结合起来。由于子图池化包含了整个子图的信息，并且用于目标LP，因此生成的概率分数不仅反映了边的固有属性，还反映了它与目标链接(i,j)的关系。随后，我们根据概率使用伯努利分布对每条边进行采样，以获得修剪后的图。最后，修剪后的图G(i,j)±被反馈到模型中，作为增强图结构的输入。

子图编码。减少阶段从使用GNN编码膨胀图G(i,j)+开始。我们可以选择任何消息传递神经网络（MPNN）[19]作为GNN编码器的实现。MPNN可以描述如下：mv(l)=AGG({hu(l),hv(l),?u∈Nv}), (7) hv(l+1)=UPDATE({hv(l),mv(l)}), (8)，其中AGG(?)是T层GNN的第t层中采用的邻域聚合函数，UPDATE(?)是更新函数。因此，{hv(T)|v∈G(i,j)+}表示由GNN编码器学习的节点嵌入。

一个典型的LP方法，如GAE [30]或SEAL [72]，可以通过池化节点表示来进行预测，即hG(i,j)+=POOL(hv(T)|v∈G(i,j)+)，其中hG(i,j)+是节点对(i,j)的最终表示。然而，在我们的DA方法中，我们首先需要修剪噪声边，以获得更简洁的图结构。

通过边采样进行减少。在编码节点表示之后，我们继续修剪膨胀图中的噪声边。我们首先通过连接两个端节点的节点表示和一个可训练的嵌入来表示膨胀图G(i,j)+中的每条边(u,v)，以指示这条边是来自原始图G(i,j)还是来自完整阶段。具体来说，我们得到h(u,v)=[hu;hv;h~(u,v)]，其中[?;?]是连接操作。将h~(u,v)附加到边表示中，使模型能够知道边是否原本在图中，或者是由链接预测器在完整阶段引入的。

在这种设置中，边表示h(u,v)仅包含其在膨胀图中的结构角色信息。虽然结构相似的边可能会对不同的目标节点对产生不同的影响，但这种表示并不传达边(u,v)在局部子图G(i,j)+中如何影响目标节点对(i,j)预测的信息。为了使边表示直接与下游的LP任务交互，我们进一步应用了一种注意力机制[60, 61]，并将其与整个子图的总体表示相结合，以定义其对LP的重要性。我们按如下方式计算这一点：a(u,v)=Q?(hG(i,j)+)TK?(h(u,v))/F′′, (9)，其中Q?和K?是两个MLP，F′′是MLP的输出维度。

与GAT [61]不同，GAT直接在每一层中将注意力分数作为边权重应用，我们使用这些分数a(u,v)来采样边，以多样化图的视图。对于G(i,j)+中的每条边(u,v)，我们从伯努利分布ω(u,v)～Bern(sigmoid(a(u,v)))中采样一个边掩码，以掩盖图中不必要的边。为了确保梯度可以在这里的随机节点中流动，我们使用了Gumbel-Softmax技巧[26, 39]。这个程序通过变分分布p?(G(i,j)±|G(i,j)+来生成简化的子图G(i,j)±。

为了控制方程式（5）中的边际分布，我们遵循[40, 67]并应用一个非信息性先验r(G~(i,j))。换句话说，G~(i,j)是通过为G(i,j)+中的每个节点对(u,v)采样边连接性ω~(u,v)～Bern(γ)来获得的。γ是一个超参数。无论G(i,j)±的图结构如何，如果ω~(u,v)=1，我们就连接(u,v)，否则断开连接。这本质上是一个Erd?s–Rényi随机图[15]。关于边际分布的KL损失项的推导详细说明在附录B.1中。

基于修剪后的子图的预测。一旦我们获得了边掩码ω，我们就可以编码子图并进行LP。边掩码可以被视为膨胀图的边权重。这样，边权重就起到了修剪膨胀图中噪声边的消息传递限制器的作用，这修改了方程式（7）中的消息传递部分，如下所示：mv(l)=AGG({ω(u,v)?hu(l),hv(l),?u∈Nv}). (10)使用从简化后的子图G(i,j)±学到的表示，我们可以将它们输入到一个池化层和一个MLP中，以估计Y。这模型化了分布qθ(Y|G(i,j)±)。

训练预测器qθ和reducer p?的算法显示在算法3中。

3.4 理论分析
在本节中，我们为LP任务的DA方法中集成CORE阶段提供了理论基础。

定理1. 假设：(1) 链接(i,j)的存在Y完全由其局部邻域G(i,j)?决定，即p(Y)=f(G(i,j)?)，其中f是一个确定性的可逆函数；(2) 膨胀图包含足够的结构用于预测G(i,j)?∈Gsub(G(i,j)+。那么，G(i,j)±=G(i,j)?最小化了方程式（3）中的目标。

定理1中的第一个假设与图结构数据的广泛接受的局部依赖性假设[67, 72]是一致的。第二个假设强调了在执行reduce操作之前，在Complete阶段将足够的结构信息纳入图中的重要性。尽管我们假设链接存在Y是由G(i,j)?因果决定的，Y和G(i,j)+之间仍可能存在一些其他虚假的相关性。这些相关性可能由环境[3, 33, 66]引入，而在测试阶段这种相关性的变化可能导致LP模型的性能下降。定理1表明，在温和的假设下，优化方程(3)中的目标可以帮助我们揭示图中决定链接是否应该存在的最关键组成部分。因此，我们的方法能够消除噪声和虚假边缘，从而提高LP模型的泛化能力。证明可以在附录E.3中找到。

5.3 时间复杂度
我们的方法的时间复杂度主要与SEAL相似。然而，有两个额外的计算要求：(1)需要额外的节点表示编码用于边缘剪枝；(2)必须为每条边分配一个概率分数。因此，我们方法的总体计算复杂度为O(t(dl+1F′′+dl+1F′′2))，其中t表示目标链接的数量，d是最大节点度数，l对应于子图的跳数，F′′表示表示的维度。因此，CORE的总体时间复杂度与最先进的LP算法（如SEAL）是渐进可比的。

5.4 相关工作
LP作为图数据分析中的一个基本任务，已经从传统的基于启发式的方法发展到使用GNN的更高级方法。早期的努力集中在启发式方法上，如CN、Adamic–Adar Index (AA)、RA和经典度量标准，如Katz Index [28]、Jaccard Index [47]、PageRank [7]和Preferred Attachment [4]。随着基于GNN的方法的引入，发生了显著的变化。例如，Kipf和Welling [30]提出了Graph Auto-Encoder，它通过GNN学习节点表示来推断节点对的相似性。Cho [11]通过解耦余弦相似性和内积的范数进一步研究了Graph Auto-Encoder的局限性。SEAL [72]通过提取节点对周围的子图并纳入最短路径距离标签来提高性能。DEAL [21]处理LP任务，使得节点只有节点属性而没有图结构信息。在蛋白质-蛋白质相互作用图的背景下，Nasiri等人[42]引入了一种基于随机游走的属性图嵌入方法来学习更有效的表示。类似地，Nasiri等人[41]使用有偏随机游走来处理多路网络中的LP问题。此外，HSDAFS [49]作为一种特征选择方法被提出，它利用了超图拉普拉斯矩阵。

5.5 数据增强（DA）
数据增强（DA）策略在提高模型泛化能力方面的效果在各个领域都有很好的记录。传统的DA技术，如过采样、欠采样和插值方法[9]，已被证明对于缓解从不平衡数据集中学习的问题非常重要。近年来，DA在计算机视觉和自然语言处理中得到了广泛的应用。在计算机视觉领域，水平翻转、随机擦除[79]、Hide-and-Seek [52]和Cutout [13]等技术已经展示了它们提高模型性能的能力。相反，在自然语言处理中，DA通常通过词汇替换策略实现，其中单词被替换为其语义等价的词[75]。UDA [68]引入了一种新的方法，它利用TF-IDF度量为文档中的关键词特征进行增强。

5.6 图数据增强（Graph DA）
图结构数据具有异构的信息模式和复杂的属性，与传统图像或文本数据相比，为DA提供了更复杂的挑战。通常，图DA可以分为两种主要方法：图结构的扰动和节点属性的增强。
在半监督节点分类领域，已经提出了几种创新技术。例如，Drop Edge [46]引入了随机边删除来缓解GNN中普遍存在的过度平滑问题。同样，SDRF [59]利用图结构重连来解决GNN中的过度压缩问题。NodeAug [64]提出了一种更全面的方法，通过添加/删除边来增强图结构，同时通过特征替换来增强节点属性。GAugLLM [16]使用大型语言模型来扰动文本节点属性，生成图数据的多样化增强视图以进行对比学习。然而，它仅限于节点包含文本属性的图，这限制了其适用性。
对于图分类任务，AD-GCL [55]开创了一种对抗性增强技术来提升图对比学习的训练效果。同时，JOAO [70]和GraphAug [38]自动从预定义的池中选择增强方法，结合了边扰动和节点属性掩码。
然而，LP领域对DA的探索相对有限。值得注意的例外包括Distance Encoding [35]和Node labeling [73]，它们通过注入距离信息来增强GNN的表达能力。此外，Hwang等人[25]提出通过引入虚拟节点作为消息传递中心来提高模型表达能力和节点影响。AdaGCL [27]在推荐系统中应用适应性对比视图进行图对比学习。然而，它仅限于用户-项目二分图，这限制了其适用范围到更广泛的图数据类型。与现有的图DA方法不同，CORE可以在任何具有图结构的数据上操作，并执行适应性结构扰动以提高模型鲁棒性。

5.7 IB原则
IB原则越来越多地被纳入深度学习模型中以提高学习鲁棒性。例如，DeepVIB [2]首次在这个领域应用了IB原则。为了克服IB中的互信息项带来的难以处理的计算问题，DeepVIB设计了一种类似于变分自编码器[29]中使用的方法的变分近似。IB原则也被用于图表示学习领域。GIB [67]是最早将IB集成到图学习中的方法之一，旨在保护GNN免受对抗性攻击。VIB-GSL [54]在此基础上进一步发展，将IB原则应用于图结构学习，展示了其在图分类任务中的鲁棒性。GSAT [40]与我们的工作最相关，它使用IB从图中提取最有意义的组件以用于解释目的。同样，IB-subgraph [71]结合双级优化过程使用IB来识别最具代表性的子图组件。我们在附录A.5中提供了GSAT与我们工作的详细比较。

5.8 实验
在本节中，我们提出了我们提出的方法的实验结果。首先，我们评估了CORE与各种基线DA技术在LP任务上的性能。然后，我们展示了启发式链接预测器也可以从CORE增强的图结构中受益。此外，我们展示了其对对抗性边扰动的鲁棒性。实验的更多细节可以在附录B.5中找到。

5.8.1 实验设置
**基线方法**
我们选择了三种非GNN模型的启发式链接预测器：CN [43]、AA [1]和RA [80]。对于利用节点级表示的GNN模型，我们使用了两种最广泛使用的架构：GCN [31]和SAGE [20]。对于利用边级表示的LP，我们选择了SEAL [72]、ELPH [8]和NCNC [63]作为基线。
我们选择了Edge Proposal [51]和CFLP [77]，作为以GCN为架构的两种代表性DA基线。对于SEAL，我们评估了两种标准的图扰动技术[70]、Node Drop [45]和Edge Drop [46]。然后，我们展示了仅使用Complete、仅使用Reduce以及结合使用CORE的结果。这些基线模型的详细信息可以在附录C.1中找到。

**基准数据集**
我们选择了四个有属性和四个无属性的图作为基准。有属性的图包括三个合作网络CS、Physics [48]和Collab [67]，以及一个共购买的图Computers [48]。无属性的图包括USAir [5]、Yeast [62]、C.ele [65]和Router [53]。基准数据集的完整统计信息可以在表1中找到。

**评估协议**
我们遵循以前工作的评估设置[77]，将链接分为10%用于验证，20%用于测试。对于Collab [24]，我们使用官方的训练-测试分割。评估指标是Hits@50，这是评估LP任务广泛接受的指标[24]。结果报告了10次不同模型初始化下的运行结果。

5.9 结果
表2展示了所有方法的LP性能（Hits@50）。鉴于强大的基础模型SEAL，我们观察到我们提出的DA可以在各种数据集上进一步提高其性能。与没有DA技术的SEAL相比，CORE在Hits@50方面一致地将性能提高了1%到9%。更具体地说，仅使用Complete和仅使用Reduce都可以以不同的幅度提高模型能力。此外，通过结合这两个阶段，CORE几乎总是能够达到最佳性能，并显著优于基线。我们的结果还表明，当可用数据量有限时，CORE可以带来更大的性能提升。这一观察表明，模型可能在低数据情况下容易过拟合噪声。然而，CORE通过学习与图结构相关的（Bernoulli）分布有效地缓解了这个问题，防止模型过拟合于特定的结构扰动。

**表2. 各方法的LP性能（Hits@50）**
模型类型 | CN | USAir | Yeast | Router | CS | Physics | Computers | Collab |
|--------|------|--------|---------|---------|---------|---------|---------|
| Heuristics| 54.31 ± 0.00 | 57.34 ± 0.00 | 64.34 ± 0.00 | 57.34 ± 0.00 | 64.34 ± 0.00 | 64.34 ± 0.00 |
| Network Embedding| 50.82 ± 3.24 | 52.40 ± 2.02 | 52.40 ± 2.74 | 52.40 ± 2.74 | 52.40 ± 2.74 | 52.40 ± 2.74 |
| DA | 70.19 ± 2.95 | 74.36 ± 3.41 | 70.19 ± 2.95 | 74.36 ± 3.41 | 70.19 ± 2.95 | 70.19 ± 2.95 |
| GNNs | 57.32 ± 4.52 | 57.32 ± 4.52 | 57.32 ± 4.52 | 57.32 ± 4.52 | 57.32 ± 4.52 | 57.32 ± 4.52 |
| 边提案 | 68.76 ± 2.77 | 70.19 ± 2.95 | 72.10 ± 1.70 | 72.10 ± 1.70 | 72.10 ± 1.70 | 72.10 ± 1.70 |
| OOM | | | | | | | |

**备注**
- 最好的方法以粗体表示，第二好的性能以下划线表示。
- OOM表示内存不足。

5.10 可学习和可转移性
使用CORE的 reducer（一个具有通用逼近能力的神经网络[23]）的一个潜在担忧是，性能改进可能归因于模型的过参数化[6]，而不是我们增强图的质量。为了解决这个问题并验证CORE作为DA方法的有效性，我们将 reducer从模型中分离出来，并研究其提取图的可泛化视图的能力。我们将由 reducer 生成的增强图输入到三种启发式链接预测器：CN、AA 和 RA。这个实验的结果可以在图3中找到。我们的发现表明，由 CORE 精炼的图一致地提高了启发式链接预测器的性能。这一结果验证了 CORE 学习可转移和可泛化 DA 的能力。

5.11 增强鲁棒性
为了评估我们图 DA 方法的鲁棒性，我们进行了额外的实验，使用无监督图投毒攻击 CLGA [74] 以不同的攻击率对抗性地扰动图结构。这项分析的结果可以在表3和C1中找到。有趣的是，我们观察到像SEAL、ELPH和NCNC这样的高级LP模型对对抗性攻击的脆弱性比其他基线模型更高。这些表达能力强的模型能够捕捉复杂的结构关系，这使它们对结构变化更加敏感。然而，我们提出的方法CORE利用了IB [2, 67]中固有的鲁棒性，通过剪除虚假甚至有害的扰动来增强模型的抗冲击能力。这些发现表明，我们方法所提供的性能提升可能是由于它能够减轻模型对对抗性扰动的敏感性。

表3. 数据集与方法

No Adv 10% 30% 50%
c.eleGCN 57.32 ± 4.52 59.63 ± 3.41 54.97 ± 3.08 46.76 ± 3.90
SAGE 42.14 ± 5.62 31.98 ± 6.26 35.15 ± 3.38 28.32 ± 5.74
SEAL 67.32 ± 2.71 60.93 ± 2.23 58.55 ± 1.46 51.00 ± 2.32
ELPH 66.06 ± 3.00 62.28 ± 2.48 56.62 ± 2.48 50.40 ± 0.85
NCNC 60.42 ± 1.89 52.10 ± 1.29 53.40 ± 1.40 50.26 ± 0.93
Edge Proposal 70.19 ± 2.95 64.71 ± 1.86 58.60 ± 2.14 50.93 ± 2.00
CFLP 54.36 ± 3.41 51.75 ± 2.79 46.49 ± 3.30 42.83 ± 5.16
CORE 76.34 ± 1.65 72.03 ± 3.19 63.78 ± 2.24 58.16 ± 1.52
USAirGCN 82.14 ± 1.99 84.87 ± 1.22 83.06 ± 1.73 80.19 ± 0.77
SAGE 82.85 ± 4.01 78.21 ± 2.81 74.82 ± 3.28 73.88 ± 3.65
SEAL 91.76 ± 1.17 85.51 ± 1.70 84.80 ± 2.95 81.53 ± 3.95
ELPH 88.16 ± 1.21 86.71 ± 0.94 85.08 ± 0.96 84.54 ± 0.50
NCNC 83.22 ± 0.82 83.88 ± 0.78 83.44 ± 0.50 83.18 ± 0.53
Edge Proposal 86.35 ± 1.35 86.42 ± 1.34 84.95 ± 0.74 80.94 ± 1.66
CFLP 89.09 ± 1.12 86.53 ± 1.74 77.26 ± 4.24 80.32 ± 2.44

基于C.ele和USAir数据集的不同模型的对抗性鲁棒性结果

10%、30%和50%的攻击率分别代表CLGA [74]中受到对抗性翻转的边的比例。

5.5 拆除研究

我们使用图同构网络（GIN）作为主干模型，来检验CORE在不同的主干模型下是否仍然是一种有效的深度增强（DA）技术。结果表明，使用GIN作为主干模型时，CORE仍能在基础上提升LP性能，提高1%到10%。这表明CORE可以有效地与其他主干模型集成。

表4. 方法

C.ele USAir
Router Yeast
GIN作为主干模型
GIN 62.77 ± 2.33 87.22 ± 2.70 60.22 ± 2.09 75.38 ± 2.23
仅完成 71.03 ± 2.18 88.12 ± 1.47 60.22 ± 2.09 75.38 ± 2.23
仅减少 64.13 ± 2.84 88.71 ± 1.60 62.81 ± 2.46 78.40 ± 1.34
CORE 72.33 ± 2.62 88.71 ± 1.60 62.81 ± 2.46 78.40 ± 1.34
without sampling or info constraint
NoSample 75.20 ± 1.71 91.51 ± 1.65 64.35 ± 2.49 84.59 ± 1.16
β=0 74.02 ± 2.45 91.81 ± 1.53 63.90 ± 2.16 83.33 ± 2.05
NoSample-β=0 73.48 ± 2.52 91.45 ± 1.73 65.09 ± 1.41 84.47 ± 1.49
CORE 76.34 ± 1.65 92.69 ± 0.75 65.47 ± 2.44 84.22 ± 1.58

表格的上半部分展示了使用GIN作为主干模型的CORE的结果，而下半部分则研究了平衡超参数β和边缘采样对提出框架的影响。

GIN，图同构网络。

信息约束和随机采样。我们进一步研究了在目标函数中保留信息约束项以及在增强过程中使用随机采样组件的必要性。结果展示在表格的下半部分。通过设置β=0，我们方法的减少了阶段失去了从膨胀图中限制信息流的能力，这导致了性能的显著下降，表明正则化项有助于防止模型过拟合。此外，当移除随机采样组件并直接使用注意力得分作为边权重时，性能也会下降。这表明在DA中结合采样可能会使LP模型暴露于更广泛的增强数据变化中。

5.6 在LP任务中专门设计的三个组件的有效性。我们进一步对这三个组件进行了拆除研究，以提高我们提出方法的性能。结果显示，所有三个组件都能在不同程度上提升所提出DA方法的性能。例如，没有注意力的CORE将性能从0.6降低到2.5（基于 Hits@50）。没有边标签的CORE也将DA的有效性从0.5降低到3。偏差KL损失主要影响了CORE在USAir和Physics数据集上的性能，我们认为这两个数据集的度分布比其他数据集更偏斜。

表5. 模型

C.ele USAir Router Yeast CS Physics Computers Collaborab
No Attention (Equation (9)) 74.41 ± 1.75 92.38 ± 1.07 63.60 ± 2.92 82.81 ± 0.94 65.69 ± 2.38 73.10 ± 0.78 36.85 ± 1.17
No Edge Label (Appendix B.2) 74.27 ± 4.73 91.49 ± 0.81 63.07 ± 3.90 83.79 ± 2.01 65.84 ± 1.40 71.71 ± 2.72 36.79 ± 2.88 69.64 ± 1.32
Bias KL Loss 75.14 ± 2.18 90.66 ± 3.69 64.80 ± 2.25 81.91 ± 1.70 64.22 ± 3.38 69.32 ± 5.05 37.31 ± 2.47 69.61 ± 1.13

CORE使用GCN和SAGE作为主干模型的结果在表6中展示。结果表明，CORE可以与各种GNN作为主干模型一致地提升模型性能。

5.6 不同目标链接的不同DA

我们方法的一个独特设计是在各自独立的环境中增强每个目标链接。在这里，我们实证研究了隔离DA的必要性。我们收集了子图中每个边的边掩码ω，但这些边属于不同的目标链接。然后，对于同一边的这些边掩码，我们计算它们的标准差，以指示在学习不同目标链接时这些边掩码ω之间的一致性或差异。结果展示在图4中。

图4. 表示与不同目标链接相关联的子图中每个边的学习边掩码ω的标准差（std）的直方图。标准差较大的值频繁出现，表明在关注不同目标链接时，最优DA存在显著分歧。

如图所示，虽然一部分边可能有相似的增强（标准差小），但其中很大一部分边之间存在冲突（标准差大）。在C.ele和Router上，CORE对于几乎一半与不同目标链接相关的边会学习不同的DA。在Yeast上，大多数边的增强方式不同。这个结果表明，有必要隔离每个目标链接的DA效果。

5.7 参数敏感性

我们还进行了实验来检验CORE中超参数的敏感性。我们仅关注减少阶段，因为这是我们方法的核心组成部分。根据我们的超参数搜索程序，我们评估了β在[10,5,2,1,0.1,0.01]范围内和γ在[0.8,0.5,0.2]范围内的模型性能。结果显示，我们的方法在各种超参数设置下都能提升模型性能。然而，我们也注意到，如果增加图压缩项β或减少保留边的项γ，性能会下降。这是因为过度稀疏图会导致关键信息的丢失。因此，平衡β和γ对于核心性能的鲁棒性至关重要。

图5. CORE在不同超参数设置下可以通过 Hits@50 来提升LP性能。颜色越暖表示性能优于基线，颜色越冷则表示相反。

此外，参数γ作为调节机制，影响每条边的概率，使其趋向于随机图的行为。较低的γ倾向于抑制预测中的非必要边。根据我们的观察，[0.5,0.8]之间的值往往是最佳的。在我们的研究中，平衡因子β对模型性能的影响比γ更为显著。

5.8 通过AUCROC和AUCPR来衡量性能

我们还使用AUCROC和AUCPR来评估性能。如表7所示，我们的方法一致性地取得了比基线方法更好的显著结果，CS和Computers除外。在AUCPR方面，表8显示CORE在所有方法中表现最佳。然而，性能差距比其他指标小，可能是由于AUCPR分数的饱和效应。总体而言，这些结果支持了我们方法在不同评估指标上的有效性。

表7. 模型类型

Model Type C.ele USAir Router Yeast CS Physics Computers Collaborab
Heuristics CN 79.00 ± 0.00 91.22 ± 0.00 85.94 ± 0.00 54.24 ± 0.00 84.40 ± 0.00 92.32 ± 0.00 94.85 ± 0.00 82.79 ± 0.00
AA 80.80 ± 0.00 92.10 ± 0.00 85.99 ± 0.00 54.24 ± 0.00 84.42 ± 0.00 92.35 ± 0.00 95.30 ± 0.00 82.79 ± 0.00
RA 81.19 ± 0.00 92.41 ± 0.00 86.02 ± 0.00 54.24 ± 0.00 84.42 ± 0.00 92.34 ± 0.00 95.48 ± 0.00 82.79 ± 0.00
Network Embedding Node2Vec 80.99 ± 0.46 88.63 ± 0.42 91.25 ± 0.48 74.99 ± 0.45 85.09 ± 0.44 88.45 ± 0.41 81.03 ± 0.47 92.40 ± 0.43
DeepWalk 80.27 ± 0.47 88.52 ± 0.43 90.96 ± 0.44 74.81 ± 0.48 85.37 ± 0.41 88.40 ± 0.46 80.67 ± 0.43 92.97 ± 0.45
GNNs GCN 85.36 ± 0.87 90.62 ± 0.46 89.15 ± 0.19 80.86 ± 0.47 96.98 ± 0.27 98.66 ± 0.06 98.85 ± 0.04 90.85 ± 0.42
SAGE 82.95 ± 1.25 92.80 ± 0.60 93.46 ± 0.36 82.02 ± 0.58 94.75 ± 0.37 89.72 ± 14.75 96.95 ± 1.93 92.11 ± 0.43
SEAL 88.50 ± 0.73 95.80 ± 0.42 96.18 ± 0.42 91.28 ± 1.08 95.97 ± 0.41 98.76 ± 0.04 98.77 ± 0.02 95.21 ± 0.45
ELPH 85.98 ± 0.45 93.23 ± 0.47 90.20 ± 0.43 83.83 ± 0.48 86.57 ± 0.42 87.15 ± 0.46 75.35 ± 0.45 85.50 ± 0.44
NCNC 84.14 ± 0.48 91.61 ± 0.44 88.30 ± 0.47 83.06 ± 0.41 85.88 ± 0.46 88.22 ± 0.43 76.51 ± 0.44
Edge Proposal 87.77 ± 0.88 91.56 ± 0.69 89.35 ± 0.21 80.37 ± 1.08 97.10 ± 0.10 98.65 ± 0.07 98.86 ± 0.05 95.80 ± 0.44
CFLP 80.64 ± 1.21 93.15 ± 0.49 91.86 ± 0.34 82.22 ± 4.31
OOM OOM OOM OOM OOM
Node Drop 88.49 ± 0.57 96.11 ± 0.30 95.94 ± 0.56 84.57 ± 0.46 96.19 ± 0.21 96.90 ± 0.03 98.78 ± 0.02 94.97 ± 0.43
Edge Drop 88.43 ± 0.87 96.02 ± 0.29 91.18 ± 0.47 91.00 ± 1.14 86.38 ± 0.45 88.10 ± 0.46 98.78 ± 0.04 94.90 ± 0.45
Our Complete Only 88.98 ± 0.45 95.62 ± 0.28 96.12 ± 0.48 91.49 ± 0.97 95.83 ± 0.18 98.76 ± 0.04OOM 表示内存不足。表 8. 模型类型

| 模型类型 | C.ele | USAir | Yeast | Router | CSPhysics | Computers | Collab | Heuristics |
|-------------------|---------|--------|-------|---------|---------|---------|-----------|
| CN | 80.78 ± 0.009 | 3.17 ± 0.009 | 2.45 ± 0.007 | 3.69 ± 0.009 | 2.08 ± 0.009 | 6.09 ± 0.009 | 6.26 ± 0.009 |
| AA | 82.40 ± 0.009 | 4.02 ± 0.009 | 2.55 ± 0.007 | 3.79 ± 0.009 | 2.11 ± 0.009 | 6.12 ± 0.009 | 6.82 ± 0.009 |
| RA | 82.68 ± 0.009 | 4.14 ± 0.009 | 2.63 ± 0.007 | 3.79 ± 0.009 | 2.10 ± 0.009 | 6.11 ± 0.009 | 7.06 ± 0.009 |
| Network Embedding | Node2Vec | 85.20 ± 0.43 | 94.07 ± 0.38 | 95.05 ± 0.42 | 88.95 ± 0.47 | 92.74 ± 0.39 | 92.42 ± 0.37 | 97.35 ± 0.44 |
| | DeepWalk | 84.93 ± 0.45 | 94.03 ± 0.41 | 94.95 ± 0.38 | 88.88 ± 0.52 | 92.85 ± 0.40 | 92.40 ± 0.39 | 97.30 ± 0.41 |
| | LINE | 86.40 ± 0.48 | 94.16 ± 0.42 | 95.09 ± 0.40 | 89.18 ± 0.45 | 92.82 ± 0.37 | 92.57 ± 0.41 | 97.32 ± 0.38 |
| GNNs | GCN | 87.00 ± 0.44 | 95.06 ± 0.39 | 94.83 ± 0.41 | 89.28 ± 0.47 | 92.42 ± 0.43 | 93.46 ± 0.38 | 98.27 ± 0.42 |
| | SAGE | 85.14 ± 0.47 | 95.14 ± 0.42 | 94.59 ± 0.38 | 89.35 ± 0.49 | 88.82 ± 0.41 | 87.76 ± 0.44 | 96.74 ± 0.39 |
| | SEAL | 87.66 ± 0.77 | 95.81 ± 0.52 | 96.96 ± 0.25 | 91.27 ± 1.35 | 96.78 ± 0.30 | 98.98 ± 0.03 | 98.75 ± 0.02 |
| | ELPH | 88.08 ± 0.43 | 95.80 ± 0.39 | 94.66 ± 0.41 | 91.27 ± 0.47 | 93.30 ± 0.38 | 93.51 ± 0.42 | 98.36 ± 0.40 |
| | DNC | 87.38 ± 0.45 | 95.19 ± 0.40 | 93.95 ± 0.39 | 91.98 ± 0.46 | 93.04 ± 0.42 | 93.92 ± 0.38 | 98.52 ± 0.41 |
| | DAsEdge Proposal | 88.59 ± 0.46 | 95.57 ± 0.41 | 94.99 ± 0.38 | 89.40 ± 0.48 | 92.63 ± 0.40 | 93.60 ± 0.39 | 98.10 ± 0.42 |
| | CFLP | 81.02 ± 1.23 | 94.98 ± 0.35 | 94.15 ± 0.17 | 85.11 ± 2.63 | | | |
| Node Drop | 87.77 ± 0.70 | 95.98 ± 0.39 | 96.71 ± 0.48 | 91.55 ± 0.46 | 96.93 ± 0.20 | 99.08 ± 0.02 | 98.73 ± 0.04 |
| Edge Drop | 87.37 ± 0.92 | 95.86 ± 0.36 | 95.03 ± 0.48 | 91.16 ± 1.36 | 93.23 ± 0.42 | 93.87 ± 0.44 | 98.75 ± 0.05 |
| Our Complete Only | 88.25 ± 0.40 | 95.14 ± 0.39 | 96.86 ± 0.40 | 91.42 ± 0.82 | 96.64 ± 0.10 | 98.98 ± 0.03 | 98.75 ± 0.02 |
| Reduce Only | 88.25 ± 0.97 | 96.07 ± 0.47 | 97.22 ± 0.21 | 92.23 ± 0.67 | 97.07 ± 0.34 | 99.05 ± 0.03 | 98.74 ± 0.05 |
| CORE | 88.95 ± 0.52 | 95.34 ± 0.81 | 97.19 ± 0.15 | 92.02 ± 0.22 | 97.06 ± 0.14 | 99.05 ± 0.03 | 98.74 ± 0.05 |

p 值：0.11, 0.09, 0.00*, 0.0215**, 0.0164**, 0.2765, --, 0.0001**

**AUCPR 评估的 LP 性能**
表现最佳的方法以粗体显示，第二好的性能以下划线标示。OOM 表示内存不足。

**6 结论**
在本文中，我们介绍了 CORE，这是一种专为LP（线性规划）任务设计的新颖数据增强技术。通过利用IB（Iterator-Based）原理，CORE能够有效消除噪声和虚假边，并恢复图中缺失的边，从而提高LP模型的泛化能力。我们的方法生成的图结构揭示了图中固有的基本关系。在各种基准数据集上的广泛实验表明，CORE优于其他方法，显示出其在图表示学习中作为鲁棒LP方法的潜力。尽管CORE是为LP任务设计的，但其图增强策略也可以应用于其他图结构化数据任务，如节点分类和社区检测。

**致谢**
我们感谢匿名审稿人的富有洞察力的评论和有益的讨论。