【随记】Adversarial Attacks on Neural Networks for Graph Data
目录
1、简介（含背景知识）
0、先验知识
0.1、针对于图神经网络的分类问题主要有两种，即图分类、节点分类。具体如下：
0.2、攻击方式分类
0.3、机器学习类别
2、正文
一、Introduction
二、Preliminary
三、Related work
四、attack method
4.0 问题定义
4.1 unnoticebale perturbation
五、产生对抗图
六、实验部分
3、参考
1、简介（含背景知识）
0、先验知识
0.1、针对于图神经网络的分类问题主要有两种，即图分类、节点分类。具体如下：
1、图分类(Graph classification)： 图分类是一种数据处理方式，指通过节点和边的结构对图数据进行分类。具体应用场景包括分析化学分子是否具备特定功能，评估某些物质是否具有抗癌活性，判断某些蛋白质是否为酶这类问题。其中，化学分子分类涉及分子性质分析，物质分类关注其生物活性评估，蛋白质分类则聚焦于功能特性的识别。
**2、节点分类(Node classification)：**指的是在给定的图网络当中(节点关系已知，各点特征已知)，在一些节点的标签一致的情况下，对其余未知标签节点的标签进行预测分类。举一个具体的例子，比如要通过人物之间的关系网来预测一个人的政治立场。人物关系构成用下面的图结构描述：
每个节点(个人)都具有若干属性，例如，在分析政治立场的案例中，每个人的一些因素会影响其政治立场，包括政治学习、母校、邮政编码以及家庭成员等。实际上，到此为止，每个人的一些信息可能已经足以对所属类别进行大致判断，但通过图的结构，预测的准确性和力度将得到显著提升。
节点分类的目标是，基于现有标记节点的信息，借助图架构完成对未标注节点的分类预测。通过图卷积神经网络(GCN)实现节点分类任务，各层之间遵循特定的传播机制。
类比于卷积神经网络（CNN），这里的W，也就是对节点特征H进行线性变换的W，可以看作是CNN中的卷积核，可以看作是GCN中的可学习参数。回想一下，每一个CNN中的卷积核，实际上是针对一个特定区域进行的线性操作，这个过程可以看作是CNN中的卷积操作，这个过程可以看作是CNN中的卷积操作，这个过程可以看作是CNN中的卷积操作。
0.2、攻击方式分类
逃逸攻击（Evasion Attacks）是指攻击者通过构造特定输入样本，无需对目标机器学习系统进行任何改动的情况下，达到欺骗目标系统的目的。
在训练过程中，攻击者通过输入恶意样本来造成模型训练效果的下降，进而影响其正常功能。这些恶意样本通常被设计为具有特定的特征，能够在模型训练过程中引入干扰，从而降低模型的性能和准确性。
0.3、机器学习类别
机器学习按照学习数据经验的不同，即训练数据的标签信息的差异，可以分为：
监督型学习（Supervised Learning）、非监督型学习（Unsupervised Learning）、半监督型学习（Semi-Supervised Learning）、强化型学习（Reinforcement Learning），具体说明如下：
1、监督学习： 监督学习是基于有标签的数据样本（x,y），学习如何将输入特征x映射到输出标签y。在监督学习框架下，模型通过已知条件下（特征x）参考答案（标签y）进行学习，并通过标签y的监督纠正自身参数，以达到学习目的。监督学习的主要任务包括分类和回归，其中分类模型处理预测结果y的取值范围有限的分类任务，例如通过日照、湿度、温度等多因素判断是否下雨；而回归模型则处理预测结果y的取值范围无限的回归任务，例如通过温度、风力等多因素预测具体温度值。监督学习的常见模型包括线性回归、朴素贝叶斯、k近邻算法、逻辑回归、支持向量机、神经网络、决策树以及集成学习等。根据模型的任务特性，监督学习可以进一步划分为分类和回归两大类。
非监督学习：
- step1：从数据集中随机选取k个样本，作为初始簇类中心（这些中心点的选取可基于先验知识或通过验证方法确定k的值）。
- step2：对于数据集中的每一个样本，计算其到各个簇类中心的距离，并将其归入距离最近的簇类中心所属的类别。
- step3：重新计算每个簇类的中心位置。
- step4：依次重复step2和step3，直至满足终止条件，如达到预设的迭代次数或簇类中心位置不再变化。
3、半监督学习：
该算法基于图的半监督学习框架，旨在通过图网络结构实现节点标签的传播与预测。其基本思路是通过从已标记节点的标签推导出未标记节点的标签，从而实现对图网络中所有节点的分类任务。
- step1：首先，基于样本间的关联性构建完全图模型，其中关联性可基于样本的固有属性或通过相似度函数计算得出。
- step2：将预设的标签信息注入图中，以指导后续的分类过程。
- step3：在迭代过程中，每个节点将其标签设为其邻居节点中标签出现频率最高的类别（物以类聚、人以群分），直至收敛。
How to understand semi-supervised learning?
这个需要在学习了图结构以及图神经网络的定义之后才能理解。推理预测的测试点，经历了训练过程，并在最后一层获取最终的预测结果。半监督的感觉上就是将模型对测试集的预测结果用于训练。
这个地方我暂时的理解是，网络参数的调整依赖于损失函数的计算。关键在于，损失是如何被计算的，我认为它是基于具有标签的节点进行计算的。对于网络参数的可训练性有指导作用的是通过具有标签节点计算得到的损失。半监督学习是指在训练整个网络的过程中，既利用了带标签的数据，也采用了无标签的数据。带标签的数据即为计算损失的节点，无标签数据虽然缺乏标签信息，但在Message Passing过程中，它们的信息也被纳入计算，从而间接影响了带标签节点的特征更新。
强化学习作为一种有延迟反馈的监督学习方法，其核心机制是智能体Agent在环境中采取行为action，环境将其转换为回报reward和状态state，随后向智能体反馈。
inductive learning和transductive learning的区别：
question：
What is node embeddings?
三、其他
节点分类任务的定义如下：
生成对抗样本的本质是：
图神经网络在节点分类任务中的对抗样本研究，与以往对抗样本研究的假设差异主要体现在对任务本质的理解和应用场景的聚焦程度上。
数据是独立和连续的假设不再成立。
2、正文
一、Introduction
图中节点分类的主要目标是：基于图结构分析，结合节点属性信息以及少量节点的标签信息，以推断未标注节点的标签。
归因于未单独关注每个节点的信息，而是综合了各节点间的信息关联。
研究图神经网络是否容易受到攻击的不可预见性，其主要的两个原因在于，这一发现的焦点在于图网络的结果是会提升还是降低网络的鲁棒性，这一发现具有重要的理论和实践意义。
the relational effect：不仅依赖于单一节点，而是由多个节点协同作用的结果，这可能有助于提高鲁棒性。
在图中，节点信息具有传播性，因此，一个节点的扰动可能对后续结果产生显著影响。
因为上述两点效应，给我们对图的攻击提出了机遇和挑战：
opportunities：有机会攻击估计成功。
在节点分类攻击的过程中，我们能够控制的节点被称为attacker node。我们希望通过攻击改变分类结果的节点被称为target node。
（1）与图像数据的连续性特征不同，图结构数据和节点特征是离散的，因此基于梯度的方法无法有效生成对抗样本。（2）在图像领域中，unnoticeable changes概念可以用最大扰动的概念来度量，那么在图结构中如何度量unnoticeable changes这一概念呢？这部分内容将在后续的论文讨论中详细解释，具体内容见4.1节。（3）在半监督学习框架下，统一训练图像和图数据时，基于固定模型参数寻找对抗样本的方法同样不可行。
本文的处理对象：
以图卷积技术为基础的GCN框架，结合Column Network (CLN)技术的半监督分类模型；无监督学习的Deepwalk模型。
本文假设前提：
攻击者掌握完整图的节点信息和图结构信息，但仅能操控其中一部分节点。即便仅掌握部分信息，该攻击方法在实验中仍表现出色。攻击者无法完全控制整个图的所有节点，但通过部分信息仍能成功实施攻击。即便仅掌握部分信息，该攻击方法在实验中仍表现出色。
二、Preliminary
图神经网络各层间的传递函数的一般型式下图片描述的很清楚了：
下面建立一个具体的GCN模型，相关定义如下：
注意，所有用于计算损失的样本都属于训练集合，并且这些样本具有明确的标签信息，这是计算交叉熵损失函数的前提。
三、Related work
请看原论文。
四、attack method
4.0 问题定义
先说明一下用到的符号定义与一些名词定义：
攻击目的：
target node：我们希望攻击的点，攻击成功的标志是该节点被分错类。
attacker node： 通常情况下，我们无法直接修改目标节点（target node），而是通过调整一些可修改的其他节点，以实现对目标节点分类的间接影响。
特征扰动和结构扰动的数学描述：
直接攻击和间接攻击：
攻击程度的约束表述（限制扰动的大小）：
可见约束体现在两方面：对特征的修改、对图结构的修改。
定义一个满足上述（4）、（5）的所有图的集合。
那攻击问题可以描述为：
注意上式中：
我们的目标是确定一个图，该图在target node上的最大分类概率与原图的分类概率之间的差值最大化，其中所有候选图都必须满足扰动限制的约束条件。
4.1 unnoticebale perturbation
图结构、数据的unnoticebale perturbation不好定义的原因：
图结构具有离散特征，具体而言，与图片数据不同，在梯度作为扰动的情况下，可以调整幅度为0.01、0.1或1等数值。然而，图结构不同，例如调整节点之间的连接关系时，无法像处理小数那样进行微调，而是只能通过将节点间连接关系从0调整为1，或从1调整为0来实现。
将图的结构进行可视化呈现，在较大的图中，节点之间会形成众多连接线，这些线相互交织。复杂结构难以被人类直观识别，这种混乱的线条配置使得其不适合作为观察依据。
改写说明
在规模较大的图中，若将所有的扰动预算集中分配给少数节点，则会出现不切实际的情况。例如，一个节点原本可能与众多节点相连，若突然全部被移除，尽管仍满足约束条件，这种现象同样显得不真实。
由于扰动从两个方面引入，导致节点连接的改变（涉及图结构的扰动）以及节点特征的改变（涉及特征数据的扰动）。分别从这两个方面进行定义，通过学习下一节内容，需明确如何定义两个图的结构以及两个图的特征不可分割性。
1、图结构扰动：
关于power-law distributions幂律分布：
图结构的扰动不可分割地定义为：在扰动前后，图节点度遵循同一分布规律。在现实生活中，一个图的幂律分布参数通常可以通过以下公式进行近似计算：
在这一阶段，通过上述公式计算得到的参数，可以用来衡量两个图是否具有相同的分布特征。接下来，我们定义了log-likelihood分数。只有当图结构扰动满足特定条件时，这种扰动才被认为是可行的。
当满足上述条件时，我们认为图的度分布的改变是不可分辨的。
2、特征扰动
对于节点特征而言，如果两个特征从未同时出现过，而扰动导致这两个特征开始同时出现，那么对于我们来说，这种变化是比较容易察觉的；反之，如果两个特征通常会同时出现，但在某个节点特征中它们并未共同出现，而扰动后它们开始同时出现，那么对于我们来说，这种变化则是不容易被察觉的。举个例子，一篇关于深度学习的文章很可能同时包含“深度学习”和“神经网络”这两个关键词，但如果某个深度学习文章中这两个词并未共同出现，我们只需进行轻微的修改，就可以使它们开始同时出现，而且这种修改不会对文章的整体内容造成显著影响；相反，如果我们试图加入像“氢氧化钠”这样不相关的词汇，将会使文章显得突兀而不自然。
度量特征间的共生特征，要考虑一个问题：
不同特征同时出现是正常的，不易被察觉；而突然同时出现则不正常且容易被发现。关键在于如何将某个节点特征从0修改为1，使得它们同时出现却不易被察觉。如果将一个节点特征由0修改为1，应满足以下条件。
综上，将特征扰动限制在：
在此基础上，从结构和特征两方面对扰动施加不可分辨的限制后，攻击的问题就转化为：
也就是加了限定条件之后，搜索的子图空间变小了。
五、产生对抗图
代理模型surrogate model：
为了优化目标，我们在满足特定条件的子图集合中进行搜索，以使模型对target node的识别结果与正确识别结果之间的差异最大化（无需考虑softmax操作，因为其对结果无影响）
受限于离散域的限制，上述损失函数的优化过程难以在离散域内实现。为此，作者提出了一个替代方案。通过该替代方法，可以对公式（14）的损失进行近似评估。
恰当的分数函数的结构和特征，以及对符合条件的解进行判别，都是十分重要的。接下来，具体阐述这两个分数的计算方式。
XW保持不变，其背后的原因是基于训练完成的GCN模型，因此，可训练参数W保持不变。同时，由于当前研究关注的是图结构扰动，输入特征X保持不变。对于同一节点而言，其输出自然形成一个1×k的行向量。g(v0)记录了目标节点与其他节点的连接关系。
该研究团队开发了一种高效计算方法，用于在结构变换过程中处理邻接矩阵。由于计算量过大，无法在每次结构变换后重新计算邻接矩阵，这种方法的实现依赖于预处理和优化策略。
计算特征扰动分数：
总的扰动算法：
还需验证改动后的图形是否与原图保持相同的分布特征，原因已经述述，作者仍提供了一种快速计算的方法。
证明过程见原文。
六、实验部分
所用的数据集：
实验过程以及结果分析原文写的很清楚，请见原文第6章节。
3、参考
(Adversarial Attacks on Neural Networks for Graph Data, presented at KDD 2018) (https://zhuanlan.zhihu.com/p/426911359 "Adversarial Attacks on Neural Networks for Graph DataKDD 2018")