具有理论保证的基于结构扰动的黑盒攻击图神经网络的赌博算法

versarial attacks [10, 37, 31, 38, 26, 32, 25, 20]. That is, anattacker can easily fool a GNN model by slightly perturb-ing the graph structure (e.g., injecting new fake edges intothe graph or deleting the existing edges from the graph) orperturbing the node features. Most of the existing attacksto GNNs essentially rely on white-box or gray-box threatmodel [10, 37, 31, 38, 26, 32, 25]. An attacker can not onlyobtain the predictions generated by the targeted GNN model,but also know the whole (i.e., in white-box) or partial (i.e.,in gray-box) GNNs’ inner parameters and network struc-ture. These threat models enable the attacker to derive thetrue gradients that can be used to construct an (almost) op-timal edge/feature perturbation via first-order optimizationapproaches, e.g., projected gradient descent (PDG).In practice, however, an attacker often has limited knowl-edge about the GNN model. For instance, many models aredeployed as an API due to the commercial value. In thesepractical scenarios, an attacker can only obtain the model pre-dictions by querying the API, while not knowing the model’sother information. An attack based on such a realistic threatmodel is called a black-box attack, which significantly raisesthe bar for the attacker as he cannot obtain the gradient in-formation. A recent work [20] performs black-box attacksagainst GNNs. However, this work has two key drawbacks.First, it assumes that the attacker can only perturb the (con-tinuous) node features. Existing works (e.g., [37]) haveshown that feature perturbation-based attacks to GNNs aresignificantly less effective than structure perturbation-basedattacks. Second, the attack is implemented via a heuristicgreedy algorithm, which has no theoretically guaranteed at-tack performance. Note that black-box attacks are classifiedas soft-label black-box attacks [14, 18] and hard-label [8]black-box attacks. The former means an attacker knows theconfidence scores when querying a target model, while thelatter means an attacker only knows the predicted label.In this paper, we consider soft-label black-box attacks toGNNs with structure perturbation. However, such a newattack setting is much more challenging, as finding the opti-mal structure perturbation is essentially an NP-hard problem133790具有理论保证的基于结构扰动的黑盒攻击图神经网络的赌博算法0Binghui Wang *，Youqi Li†和Pan Zhou‡0* 伊利诺伊理工学院计算机科学系，† 北京理工大学网络空间科学与技术学院和计算机科学学院，‡华中科技大学网络科学与工程学院大数据安全湖北省工程研究中心，电子邮件：* bwang70@iit.edu，†liyouqi@bit.edu.cn，‡ panzhou@hust.edu.cn0摘要0图神经网络（GNNs）在许多基于图的任务中，如节点分类和图分类，取得了最先进的性能。然而，许多最近的研究表明，攻击者可以通过轻微扰动图结构来误导GNN模型。现有的对GNNs的攻击要么是在攻击者可以访问GNN模型参数的较不实际的威胁模型下进行的，要么是在实际的黑盒威胁模型下进行的，但是考虑到对节点特征的扰动并不足够有效。在本文中，我们旨在弥合这一差距，考虑带有结构扰动的GNNs的黑盒攻击以及具有理论保证。我们提出通过赌博技术来解决这个挑战。具体而言，我们将我们的攻击问题形式化为带有赌博反馈的在线优化问题。由于扰动图结构是一个二进制优化问题，这个原始问题本质上是NP困难的。然后，我们提出了一种基于赌博优化的在线攻击，该攻击在查询次数T上被证明是次线性的，即O(√T)。0NT3/4)其中N是图中节点的数量。最后，我们通过在多个数据集和GNN模型上进行实验来评估我们提出的攻击。各种引文图和图像图的实验结果表明，我们的攻击既有效又高效。01. 引言0图神经网络（GNNs）已成为学习图的最重要的方法，如社交网络、化学网络、超像素图等。GNNs还推动了许多与图相关的应用，包括但不限于药物发现[24]、社交媒体上的假新闻检测[21]、交通预测[34]和超像素图分类[11]。然而，最近的研究表明，GNNs容易受到对抗性攻击[10, 37, 31, 38, 26, 32, 25,20]。也就是说，攻击者可以通过轻微扰动图结构（例如，向图中注入新的虚假边缘或删除现有的边缘）或扰动节点特征来轻易欺骗GNN模型。大多数现有的对GNNs的攻击基本上依赖于白盒或灰盒威胁模型[10, 37, 31, 38, 26, 32,25]。攻击者不仅可以获得目标GNN模型生成的预测，还可以了解整个（即白盒）或部分（即灰盒）GNNs的内部参数和网络结构。这些威胁模型使攻击者能够推导出可以用于构建（几乎）最优边缘/特征扰动的真实梯度，例如，投影梯度下降（PDG）。然而，在实践中，攻击者对GNN模型的了解往往有限。例如，许多模型由于商业价值而部署为API。在这些实际情况下，攻击者只能通过查询API来获取模型的预测，而不知道模型的其他信息。基于这样一个现实的威胁模型的攻击被称为黑盒攻击，这显著提高了攻击者的门槛，因为他无法获得梯度信息。最近的一项工作[20]对GNNs进行了黑盒攻击。然而，这项工作有两个关键缺点。首先，它假设攻击者只能扰动（连续的）节点特征。现有的工作（例如[37]）表明，与结构扰动攻击相比，基于特征扰动的攻击对GNNs的影响显著较小。其次，该攻击是通过一种启发式的贪婪算法实现的，没有理论上的攻击性能保证。需要注意的是，黑盒攻击被分为软标签黑盒攻击[14,18]和硬标签黑盒攻击[8]。前者表示攻击者在查询目标模型时知道置信度分数，而后者表示攻击者只知道预测的标签。在本文中，我们考虑带有结构扰动的GNNs的软标签黑盒攻击。然而，这种新的攻击设置更具挑战性，因为找到最优的结构扰动本质上是一个NP困难问题。0‡ 通讯作者。Θ∗ = arg minΘ −133800（即，一个二进制优化问题），攻击者只能通过查询模型来获取预测结果。我们首次解决了具有理论保证的基于结构扰动的黑盒攻击GNN的问题。具体来说，我们首先将我们的攻击重新定义为一个赌博优化（即，带有赌博反馈的在线优化）问题，它描述了攻击者在黑盒GNN模型上的查询过程，并捕捉了未知的梯度。然后，我们处理离散结构扰动的二进制约束，并将其整合到我们的基于赌博的攻击目标中。接下来，我们设计了一种高效有效的GNN在线攻击。最后，我们从理论上分析了我们的攻击。我们的主要贡献总结如下：•我们设计了第一个具有理论保证的基于结构扰动的黑盒攻击GNN的赌博优化算法。0•我们证明了我们的基于赌博的攻击算法在理论上具有次线性的0在T个查询中，对具有N个节点的图进行攻击，攻击者可以在NT3/4次查询内完成。0•我们进行了大量实验证明我们的攻击在多个图数据集和GNN模型上的有效性和效率。02.初步和问题描述02.1.图神经网络0设G = (V, E, X)为一个图，其中u ∈ V是一个节点，(u, v) ∈E是u和v之间的边，X = [x1; x2; ...; xN] ∈RN×d是节点特征矩阵。我们将av = [av1; av2; ...; avN] ∈{0, 1}^N表示节点v的邻接向量。N = |V|和M =|E|分别是节点和边的数量。我们将du和N(u)分别表示u的节点度和邻居集合。本文中，我们考虑用于节点分类的GNN。在这个背景下，每个节点u ∈ V都有一个来自标签集Y = {1,2, ..., LC}的标签yu。给定一个训练集V_L �V，其中包含标记节点{(xu, yu)}u ∈V_L，GNN用于节点分类是为了学习一个节点分类器，将每个未标记节点u ∈ V \ V_L映射到类别y ∈Y，基于图G。一般来说，GNN包含两个主要步骤：邻居聚合和节点表示更新。假设一个GNN有K层。我们将第k层中v的表示表示为h(k)v，其中h(0)v =xv。在邻居聚合中，GNN通过聚合(v −1)层中v的邻居的表示来获得表示l(k)v = AGG(h(k − 1)u: u∈N(v))。在节点表示更新中，GNN通过将v的上一层表示h(k−1)v与聚合邻居的表示l(k)v相结合来更新v在第k层的表示h(k)v = UPDATE(h(k − 1)v, l(k)v)。01我们的攻击可以自然地推广到用于图分类的GNN。我们在第3.1节中讨论了这一点。0不同的GNN使用不同的AGG和UPDATE函数。例如，在图卷积网络（GCN）[16]中，AGG是逐元素的均值池化函数，UPDATE是ReLU激活函数。具体来说，它具有以下形式：h(k)v = ReLU(W(k))0u ∈ N(v)d−1/2u d−1/2v0其中 W(k) 是第k层的参数。节点v的最终表示h(K)v ∈R|Y|可以捕捉到v的K-hop邻居中所有节点的结构信息。此外，训练节点的最终节点表示被用来训练节点分类器。具体来说，令Θ = {W(1), ..., W(K)}为模型参数，v的输出为fΘ(av)= softmax(h(K)v) ∈R|Y|，其中fΘ(av)y表示节点v属于类别y的概率。然后，通过最小化训练节点V_L的输出的交叉熵损失来学习Θ。0v ∈V L ln  f Θ ( a v ) y . (1)0通过学习到的 Θ � ，我们可以预测每个未标记节点 u ∈ V \ VL 的标签，即 ˆ y u = arg max y  f Θ � ( a u ) y 。02.2. 威胁模型0攻击者的知识。本文考虑的黑盒攻击设置意味着攻击者不知道目标GNN模型的内部配置（即学习的参数）。对于目标节点 v ∈V，攻击者所知道的关于GNN模型的唯一信息是通过查询GNN模型 f Θ � 获得的预测值 f Θ � ( a v)（即输出logits）。此外，我们还合理地假设攻击者知道她的邻居，即邻接向量 a v3。在实践中，攻击者自然知道他所控制节点的邻居。以社交网络为例，攻击者控制一个恶意用户，这个恶意用户肯定知道他在社交网络中的（非）邻居。请注意，比较的黑盒RL-S2V攻击[10]也要求攻击者的目标节点知道他的邻居。攻击者的能力。我们认为攻击者可以修改目标节点 v与图中其他节点之间的连接状态（例如，注入新的虚假边缘或删除现有的边缘）。在实践中，操纵不同边缘对于攻击者来说也会产生不同的成本。攻击者操纵边缘的预算通常是有限的，我们用 C表示成本预算。我们还限制要操纵的边缘数量不超过B。攻击者的目标。基于攻击者的知识和能力，攻击者的目标是欺骗目标GNN，即通过扰动她的邻接向量 a v并在成本预算 C 和允许的扰动边缘数 B 的情况下使目标节点v 的预测标签与真实标签 y v 不同。02 注意，预测还取决于 v 的节点特征 x v 和整个图G。为了简化表示，我们省略了 x v 和 G。3对于图分类，我们假设攻击者知道输入图。̸133810我们的威胁模型要求攻击者知道置信度分数（与许多现有的对DNN模型的攻击一样）。虽然这比攻击者只需要知道硬标签的威胁模型更强，但我们也强调这是针对离散图结构扰动的第一个基于优化的攻击，这个问题本身就非常具有挑战性。我们将在未来的工作中解决使用硬标签作为查询反馈的攻击问题。02.3. 问题建模0给定目标节点 v，标签 y v 和邻接向量 av，攻击者的目标是修改与目标节点 v相关的连接状态，使得目标GNN对 v 进行错误分类。令 s v∈ { 0 ,  1 } N 为对 v 的敌对结构扰动，其中 s vu = 1表示节点 v 和 u 之间的连接状态发生了变化，s vu = 0表示没有变化。然后，我们将 v 的扰动邻接向量定义为 a v⊕ s v，其中 ⊕是两个二进制向量之间的异或运算符。此外，我们用 c v ∈R N 表示与 v 相关的成本向量，即 c vu 是修改节点 v 和 u之间连接状态的成本。在关注的黑盒设置中，我们考虑非目标攻击。令 L ( a v ) 为没有攻击的目标节点 v的损失函数。通过敌对扰动 s v，我们得到攻击损失 L ( a v⊕ s v )。在本文中，我们使用 CW 攻击损失函数[3]和 κ攻击置信度。具体来说，它定义如下：0L ( x ) = max { f Θ � ( x ) y  −  max ˆ y � = y { f Θ � ( x )ˆ y } ,  − κ } . (2)0最后，我们的基于结构扰动的黑盒攻击问题可以被定义为0最小化 s v L ( a v  ⊕  s v ) ，s.t.，1 T  s v  ≤  B，c T  s v  ≤  C，s v  ∈ {0 ,  1 } N，(3)0其中第一个约束条件表示要扰动的边的数量不超过B，第二个约束条件表示扰动的总成本不超过C。引理1.我们在公式（3）中的问题是NP难的。证明.我们在公式（3）中的问题是一个组合优化问题，实际上是一种背包问题，这是一个经典的NP难问题。0引理1表明，在大型图中（即sv具有大的维度）下，计算最优扰动向量s�v是困难的。为此，我们的目标是设计一个近似算法来得到次优解。一种算法是将组合二进制约束sv ∈ {0,1}N放松为凸包sv ∈ [0,1]N，并得到一个连续优化问题。设ˆsv为连续优化问题的解。我们可以通过将ˆsv舍入到组合空间{0, 1}N中来得到原始问题的次优解，即公式（3）中的问题。0使用类似伯努利采样[32]的随机采样。然后，我们有以下引理来描述sv和ˆsv之间的关系：0引理2. 当使用来自放松向量ˆsv ∈ [0,1]N的概率在伯努利分布中逐元素对sv进行采样时，sv的期望值是ˆsv，即条件E[sv] = ˆsv成立。0证明. 由于随机变量X服从支持集为{0,1}的伯努利分布，它的概率等于期望值，即E[X] =P[X]。应用这个事实到sv的元素上，我们可以证明这个引理。0传统上，为了解决我们的放松连续优化问题，我们可以通过在几个步骤内运行梯度更新并将其投影到可行域上来应用PGD方法。然而，PGD需要可用的梯度信息。在我们的黑盒攻击设置中，只有预测结果可用（通过查询GNN），而不是精确的梯度。因此，攻击问题变成了如何估计梯度，以便仍然可以应用PGD方法。已经证明，零阶优化（简称ZOO）可以用于估计梯度[6, 15,19]。然而，由于必须在每一轮中探索所有边缘以估计梯度，ZOO的收敛速度较低且查询开销较高。我们的目标是通过使用赌博方法来控制探索-利用的平衡来估计未知的梯度。强化学习（RL）也可以控制探索-利用的平衡。然而，基于RL的攻击，即RL-S2V[10]，是自然启发式的。我们的攻击可以解决ZOO和基于RL的攻击的两个问题。具体来说，我们的攻击具有理论保证，并且比基于ZOO和基于RL的攻击具有更好的攻击性能（见第6节）。接下来，我们将我们的攻击问题重新定义为一个赌博优化问题，然后提出一个解决方案。02.4. 将我们的攻击问题重新定义为一个赌博问题0当攻击者选择一个扰动向量sv，并使用扰动的邻接向量av ⊕sv来查询GNN时，GNN返回预测值fΘ�(av ⊕sv)。因此，基于公式（2），目标函数L(av ⊕sv)可以被揭示出来，这可以被看作是对所选择的扰动向量sv（即一只手臂）的赌博反馈（即奖励）。在赌博反馈下，攻击者希望最大化累积奖励。需要注意的是，由于攻击者在每一轮中不知道最优手臂s�v，它会产生遗憾，即在事后最优手臂s�v下的最大奖励与攻击者的攻击算法的奖励之间的差异。然后，攻击者的目标是最小化累积遗憾。设Reg(T)为T轮中的累积遗憾，stv为第t轮选择的扰动向量，则累积遗憾Reg(T)可以计算为04注意，在我们的设置中，ZOO是一个完美的基准。首先，只有ZOO通过查询直接逼近梯度。其次，ZOO是唯一一个也具有遗憾界限的方法。因此，我们可以从理论结果和实证攻击性能两方面与ZOO进行比较。133820Reg ( T ) = E [ � T t =1 L ( s t v )] - TL ( s � v ) . 在赌徒优化中，设计具有次线性遗憾（即Reg ( T ) = o ( T ) ）的臂选择算法非常重要。这是因为当 T 足够大时，第 T 轮选择的臂 sv 渐进地最优（即 lim T →∞ Reg ( T ) ）0T = 0 ).03. 基于结构扰动的黑盒攻击GNNs通过赌徒算法0在这里，我们设计了一种基于赌徒优化的在线攻击GNN，并在下一节展示了其次线性遗憾。首先，我们将二进制扰动向量 s v ∈ { 0, 1 } N 松弛为连续凸包 ˆ s v ∈ [0, 1] N。在这种情况下，我们可以定义臂集合 W 如下：W = { ˆ s v ∈ [0, 1] N | 1 T ˆ s v ≤ B, cT ˆ s v ≤ C }，其中 W是凸的。注意，我们的黑盒赌徒设置与传统的多臂赌徒（MAB）不同，因为臂集合 W包含无限的扰动向量。因此，上置信界（UCB）[2]和汤普森抽样（ThompsonSampling）[22]等MAB的方法无法解决我们的问题。此外，使用组合赌徒[7,29]来推导最优扰动是不可能的，因为它们必须收集足够的历史样本来计算每个扰动边的均值。特别地，在利用阶段，它们的行为类似于ZOO [6]，并使用 N + 1个查询来估计梯度。在探索阶段，它们需要一个近似算法来推导具有UCB值的次优扰动。然而，据我们所知，在结构扰动攻击的背景下，没有这样一个具有理论保证的高效近似算法。接下来，我们需要解决如何高效地决定下一个臂（即 ˆ s t +1 v ）在第 t轮结束时，以使遗憾最小化。我们利用在线凸优化（OCO）技术来推导下一个臂 ˆ s t +1 v在第 t + 1 轮。我们注意到损失函数 L ( ∙ )通常是非凸的。然而，我们强调OCO中使用的梯度下降仍然是有用的，因为对于非凸函数来说，很难推导出闭式解。OCO方法需要在选择的臂上的梯度信息来进行梯度下降。在我们的黑盒攻击设置中，攻击者只接收到选择的臂 ˆ s t v的赌徒反馈。为了估计黑盒攻击在选择的臂 ˆ s t v处的梯度，攻击者只能查询GNN来计算梯度。我们使用一点梯度估计（OPGE）[13]技术来估计梯度，因为它简单而有效。OPGE的思想是从单位球 S = { u ∈ R N | || u || 2 = 1 }中均匀采样一个单位向量，使其方向与梯度的交角较小（即 u是梯度的良好近似）。为此，我们从 S中均匀采样一个单位向量，并在以下引理中推导出一个近似梯度。引理3. 对于从单位球 S中均匀采样的单位向量 u 和足够小的 δ > 0 ，我们可以估计梯度为 � ˆ L ( ˆ s v ) = E u ∈S[ N0δ L ( ˆ s v + δ u ) u ] .0算法1 GNN的黑盒攻击用于节点分类通过OCO和赌徒 输入：目标GNN模型 f �Θ，目标节点 v，最大扰动边数 B，成本预算 C，PGD步长 η，δ > 0，α ∈[0, 1]，查询次数 T0输出: 扰动向量 s v 1: 初始化: v 1 = 0 ∈ W = { ˆ s v ∈ [0, 1] N | 1 T ˆ s v ≤B, c T ˆ s v ≤ C }02: 对于 t = 1 到 T 做 3: 攻击者随机选择一个单位向量 u t 从单位球 S 中。04: 攻击者确定扰动ˆstv=vt+δut。05: 攻击者通过将ˆstv中的前B个值设置为1，其余值设置为0，将其转换为二进制stv。06:07: 攻击者进行PGD更新：vt+1=projW(vt−δL(stv)ut)。0ηˆg)，ˆg=N0δL(stv)ut。08: 结束循环 9:返回sTv0我们的攻击算法的详细信息如算法1所示。我们算法的输入包括目标GNN模型f�Θ，目标节点v，最大扰动边数B，成本预算C，PGD步长η，一个小的δ>0，投影比例α∈[0,1]和查询次数T。输出是目标节点v经过T轮后的扰动向量sTv。在第1行，我们将0设置为初始先验向量v1。在第2-8行，我们根据OCO和赌博反馈计算一个次优的扰动向量来攻击目标GNN。在第t轮，我们在第3行随机选择一个单位向量ut作为随机梯度。在第4行，我们根据选择的随机梯度ut更新先验向量vt，得到一个松弛的扰动向量ˆstv。在第5行，我们通过将ˆstv的前B个非零值（对应于ˆstv中B个最大非零概率的条目）设置为1（从而最多扰动B条边），其余值设置为0，将其转换为二进制stv。在第6行，我们使用stv查询GNN模型f�Θ，并获得损失反馈L(stv)。在第7行，我们对臂集合W进行PGD更新，得到第t+1轮的vt+1。最后，在进行T次查询后，我们得到目标节点v的扰动向量sTv。03.1.扩展我们的图分类攻击我们提出的节点分类攻击可以自然地扩展到对图分类的GNN模型的攻击，只需稍作修改。在图分类模型中，其输入是一个图的邻接矩阵，输出是图的标签。在节点分类中，我们的目标是扰动目标节点的邻接向量，而在图分类中，我们扰动邻接矩阵。设A∈{0,1}N×N是一个图的邻接矩阵。此外，设S∈{0,1}N×N是一个扰动矩阵，其中Sij=1表示边(i,j)之间的连接状态被修改，Sij=0表示未修改。为了对图分类模型进行攻击，我们只需要将矩阵S展平为向量s，并将其作为输入提供给我们的攻击算法。在获得扰动后的s之后，我们可以将其重新整形为扰动后的邻接矩阵。E[T�t=1L(ˆstv)] − TL(ˆs∗v) ≤ CLR√T,(6)minw(1α)L(w) − TL(ˆs∗v) ≤ 2αT.(7)1338304. 主要结果0在本节中，我们分析了攻击算法的遗憾界限，其中我们假设损失函数是凸函数。我们注意到将我们的分析推广到非凸损失函数是一个有趣的未来工作。我们首先提出以下假设和引理。0假设1.存在一个Lipschitz常数CL，使得对于任意的u和v，以下不等式成立：0|L(u)−L(v)|≤CL||u−v||2。（4）0引理4.对于连续的界，如下所示：0E[|L(sv)−L(ˆstv)|]≤CLN3/4δ01+η0δ。（5）0算法1中的第7行可以看作是对L(ˆsv+δu)进行随机梯度下降。因此，我们有以下引理来描述其遗憾界限。0引理5（[12]）。假设臂集合W满足W�RB，其中R>0，B是单位球，即B={u∈RN:||u||2≤1}。当损失函数L(∙)是凸函数时，对于松弛连续变量的累积遗憾有以下界限：0其中  ˆ s t v 是第 t 轮的连续变量， ˆ s � v是我们放松的优化问题的最优连续解。需要注意的是，引理5只捕捉了整个臂集合 W上的遗憾。然而，算法1中的第7行通过将臂 ˆ s t v投影到集合 (1  −  α ) W 上来更新臂 ˆ s t v ，其中 0  < α<  1 。通过进行 (1  −  α )-投影所产生的遗憾由以下引理捕捉。0引理6. 对于时间长度为 T ，由于 (1  −  α )-投影而产生的遗憾界限如下所示：0基于上述假设和引理，我们对我们的攻击的遗憾界限有以下定理：0定理1. 在 T 轮攻击中，我们提出的攻击算法产生的遗憾 Reg( T ) 上界为  O ( √0NT 3 / 4 )  ，需要 T 个查询来对GNN进行攻击。0备注.定理1不仅证明了我们的攻击实现了次线性的遗憾，还表明0N ) .这意味着我们的攻击可以扩展到大规模图。需要注意的是，无梯度的ZOO [ 6 ] 的查询复杂度为 O ( N )。从遗憾界限可以看出，我们的攻击比ZOO [ 19]具有更好的收敛速度 O (1 /T 3 / 4 ) ，而ZOO的收敛速度为 O(1 /T 1 / 2 ) 。此外，Ilyas等人[ 15 ]提出了一个0基于赌博机的黑盒攻击图像分类器，可以用来解决我们的问题。然而，他们的方法 1)在遗憾界限方面没有提供理论结果；2)在效率上不如我们的方法，因为每次迭代需要多次梯度估计。计算复杂度。我们的攻击每轮需要1个查询，每个查询的时间复杂度为 O ( N ) 。ZOO每轮需要 2 N个查询，每个查询的时间复杂度为 O ( N )，其每轮的时间复杂度为 O ( N 2 )。RL-S2V需要训练一个额外的 Q-网络，用于执行攻击。在攻击过程中，它的时间复杂度与我们的攻击相同：每轮1个查询，每轮的时间复杂度为 O ( N )。这些分析表明我们的攻击比RL-S2V和ZOO更高效。05. 相关工作0最近对GNN的攻击主要集中在白盒/灰盒设置上[ 37 ,  10 ,5 ,  38 ,  32 ,  27 ,  25 ,  4 ,  36 ,  20 ]。例如，Zugner [ 37]提出了第一个攻击方法，称为Nettack，用于通过扰动图结构或/和节点特征来攻击GCN进行节点分类。具体来说，Nettack通过定义一个保持图结构的扰动来学习GCN的替代线性模型，该扰动限制了攻击前后图的节点度分布之间的差异。Xu等人[ 32]利用模型梯度来生成对图拓扑的扰动。我们研究的是梯度信息对攻击者是未知的黑盒设置。最近的一项工作[ 20]对GNN进行了黑盒攻击。然而，该工作侧重于扰动连续的节点特征，这与我们的问题不符，并且比离散结构扰动方法效果更差。此外，该攻击是通过一种启发式贪婪算法实现的，没有理论上的性能保证。此外，[ 37]已经表明，基于特征扰动的攻击对GNN的效果明显不如基于结构扰动的攻击（例如，攻击者需要扰动平均100个节点特征，才能达到仅扰动5条边的攻击的性能）。因此，我们在本文中侧重于图结构扰动。Zang等人[ 35]研究了图的通用对抗攻击，其中识别了一组锚节点，并翻转它们与目标节点的连接。然而，如何选择最优的锚节点尚未研究。其他一些工作[ 28 ,  17]侧重于攻击社区检测，它们是启发式的，并且与我们的工作无关。已经提出了几种针对非图分类模型的黑盒攻击[ 14 ,15 ,  9]。然而，这些方法无法解决我们的问题，因为它们的攻击问题本质上是连续优化问题。需要注意的是，[ 15]还使用了赌博机来形式化黑盒攻击问题。然而，他们的工作没有理论上的遗憾界限，并且由于每次迭代中使用了多次梯度估计，效率较低。Cora12,7085,4297(1)Citeseer13,3274,7326(1)Pubmed119,71744,3383(1)MNIST70K70.57564.5310(2)CIFAR10 60K117.63941.0710(2)1338406. 实验06.1. 实验设置0数据集描述和GNN模型。在节点分类实验中，我们使用三个基准引文图，即Cora、Citeseer和Pubmed[23]。在这些图中，每个节点表示一个文档，每条边表示两个文档之间的引用。每个文档将词袋特征视为节点特征向量，并具有一个标签。我们采用代表性的GCN [16]和SGC[30]进行节点分类，并针对这两个模型评估我们的攻击。在图分类中，我们使用两个基准超像素图，即MNIST和CIFAR10[11]，在计算机视觉中。MNIST和CIFAR10是经典的图像分类数据集。在我们的实验中，它们被转换为使用SLIC超像素[1]的图。每个节点具有超像素坐标作为特征，每个超像素图具有一个标签。我们采用代表性的GIN[33]进行图分类，并针对GIN评估我们的攻击。表1总结了这些数据集的基本统计信息。训练节点/图和目标节点/图。我们使用训练节点/图来训练GNN模型，并使用目标节点/图来评估我们对训练模型的攻击。按照现有的工作[16, 37,11]，在引文图中，我们随机从每个类别中抽取20个节点作为训练节点；从每个GNN模型正确分类的节点中抽取100个节点作为目标节点。在图像图中，我们分别使用55,000个图和45,000个图在MNIST和CIFAR10上进行训练，并随机选择100个被GIN模型正确分类的图作为目标图。基线。我们将我们的攻击与两种最新技术进行比较：基于RL的攻击[10]和ZOO攻击[6]。请注意，对于基于RL的攻击，我们使用与我们的攻击相同的CW攻击损失进行调整，因此与我们的攻击进行了公平比较。我们还选择随机攻击进行比较，其中我们通过随机更改节点对之间的连接状态来生成结构扰动。成本模拟。我们为每对节点的修改连接状态的成本进行了指定。请注意，成本可能依赖于应用程序。我们假设不同节点对的成本在某个区间内均匀分布（例如，在我们的实验中为[1,5]）。请注意，相等的成本可以看作是均匀成本的特例。参数设置。我们将攻击算法中的超参数设置如下：η =10^(-4)，δ = 10^(-6)，α =0.7，用于攻击节点分类方法；η = 10^(-1)，δ =10^(-3)，α =0.6，用于攻击图分类方法。考虑到不同的图大小，我们在三个引文图上将默认最大扰动边数B设置为5，两个图像图上设置为15；默认总成本C在引文图上限制为25，在图像图上限制为75。此外，查询的总数T = 50。0数据集 #图 #平均节点数 #平均边数 #类别 任务0(1)  节点分类，(2)  图分类。0默认设置。我们还研究了这些参数在我们的实验中的影响。我们使用Python实现了我们的算法，并使用公共源代码进行实验。所有实验在一台计算机上运行，该计算机配备有Intel(R) Core(TM) i7-6700 CPU @3.4Hz处理器，4核，32GBRAM，1TB磁盘空间和6GGPU。我们运行所有实验30次，并报告平均结果。评估指标。我们采用攻击成功率作为评估指标，即在我们的攻击之后被错误分类的目标节点/图的总数（即100）的比例，来衡量我们攻击的效果。我们还使用查询次数（T）来衡量我们攻击的效率。具体而言，我们将我们算法1中的每个PGD迭代视为一个查询。06.2. 实验结果0在本节中，我们对GNN的黑盒攻击进行了全面评估，包括节点分类和图分类。我们旨在从效果和效率两个方面研究我们的攻击。我们的攻击算法有三个关键因素：扰动边数B、总成本C和查询数量T。我们将逐个研究这些参数的影响。扰动边数的影响。在这个实验中，我们分别将有界总成本C固定为25和75，并将查询数量T设置为50，用于攻击节点分类模型和图分类模型。攻击这些模型的结果分别显示在图1、图2和图3中。我们有以下观察结果：首先，当最大扰动边数B增加时，所有攻击方法的攻击成功率都会增加。这是因为较大的B允许对手具有更好的攻击能力。其次，在所有GNN模型和图数据集中，我们的攻击明显比其他攻击方法实现了更高的攻击成功率。例如，当攻击GCN和SGC进行节点分类时，我们的攻击的攻击成功率大于80%（甚至达到90%），而第二好的强化学习攻击在三个引文图中的攻击成功率最多只有80%。当攻击GIN进行图分类时，我们的攻击实现了60%的攻击成功率，而强化学习攻击在两个图像图中的攻击成功率不到53%。所有这些结果验证了我们算法中黑盒强化学习反馈的实用性，可以指导选择最佳的扰动边。相比之下，启发式强化学习攻击很难做到这一点。15.3.4.5.6.7(a) Cora.15.6.7.8.9.0(b) Citeseer.15.4.5.6.7.8(c) Pubmed.15.4.5.6.7.8(a) Cora.15.5.6.7.8.9(b) Citeseer.15.2.4.6.8.0(c) Pubmed.3691215#Perturbed edges B.2.3.4.5.6Our attackRandom attackZoo attackRL attack(a) MNIST.3691215#Perturbed edges B.2.3.4.5.6Our attackRandom attackZoo attackRL attack(b) CIFAR10.20406080100#Queries T.1.2.3.4.5Our attackRandom attackZoo attackRL attack(a) MNIST.20406080100#Queries T.1.2.3.4.5Our attackRandom attackZoo attackRL attack(b) CIFAR10.133850扰动边数B0攻击成功率0我们的攻击随机攻击动物园攻击强化学习攻击0扰动边数B0攻击成功率0我们的攻击随机攻击动物园攻击强化学习攻击0扰动边数B0攻击成功率0我们的攻击随机攻击动物园攻击强化学习攻击0图1. GCN进行节点分类时攻击成功率与扰动边数B的关系。0扰动边数B0攻击成功率0我们的攻击 随机攻击动物园攻击强化学习攻击0扰动边数B0攻击成功率0我们的攻击 随机攻击动物园攻击强化学习攻击0扰动边数B0攻击成功率0我们的攻击 随机攻击动物园攻击强化学习攻击0图2. SGC进行节点分类时攻击成功率与扰动边数B的关系。0攻击成功率0攻击成功率0图3. GIN进行图分类时攻击成功率与扰动边数B的关系。0攻击成功率0攻击成功率0图4. GIN进行图分类时攻击成功率与查询数量T的关系。0查询数量的影响。在这个实验中，我们分别将有界总成本C固定为25和75，将最大扰动边数B分别固定为2和5，用于攻击节点分类模型和图分类模型。攻击GIN进