解决问题：邻域聚合范式为试图提取敏感属性的节点级信息的攻击者暴露了额外漏洞

恶意攻击者在推断时，偷取敏感信息

传统GNN
任务训练 推断--> 节点攻击或邻接点攻击

图对抗神经网络
节点防御或邻接点防御 推断-->防御对抗攻击

如图所示：图对抗网络（GAL）通过任务解码器(蓝色)和模拟最差情况攻击者(黄色)在嵌入(下降)和属性(上升)上的最小-最大博弈来防御节点和邻域推断攻击。
恶意攻击者将很难在推理时从用我们的框架训练的GNN嵌入中提取敏感属性。

功能：
1.维护服务同时保护网络中用户敏感信息免受恶意推断攻击。
2.量化两个目标之间的权衡

分析对抗性攻击者的优势：
设D为样本空间X上的分布，对于事件E∈X，用D(E)表示表示D下E的概率。
给定特征变换函数g:X->Z
一个图实例，从输入空间X映射到特征空间Z
定义：

为g在D下的前推分布（一种类似向量映射的方式），对于任意事件：E'∈Z既是

对于同一样本空间上的D和D‘两个分布，设dTV(D,D')为TV（整体变量）两者间的距离：

显然，TV距离总是有界的：0≤dTV(D,D')≤1，事实上，它是概率分布空间上的一个距离度量，因此它满足三角形不等式。

图神经网络：首先介绍GNNs的符号和应用设置。
我们用G=(V, E)表示一个图，该图具有节点特征Xv∈R^d 其中v∈V，边特征Xc∈R^l
其中e∈E。
训练数据由一组图{G1,G2...GN}∈Gj和标签{y1...yn}∈y组成。
根据任务不同，每个yi可以是Gi对应的一组节点或边的一组标签，也可以是整个Gi图的单个标签。
我们的目标是学习为看不见的节点、边或图预测标签。
为此，我们用H表示假设集，该假设集以GNNs的节点特征作为输入并产生预测。

现代GNN遵循邻域聚合方案，通过聚合其邻居的表示，来递归地更新每个节点v(在第k层)的表示向量X(k)v。
然后可以使用节点向量X(k)v进行节点和关系预测。

GNN第k层：

其中X(k)v∈R^dk是节点y在第K次迭代时的特征向量，
用K表示层数。
我们初始化X(0)v=Xv, N(v)是节点v的邻域.

由一群大佬证明出，下式可以学习图上复杂的函数(多层感知机：处理非线性可分离的问题)

GNNs是下游任务（自然语言处理的内容，句子对分类任务，单句子分类任务，问答任务等）中学习节点和图表示的强大范式（科学史家库恩定义：范式包含两部分，某一科学团体在某一特定时期能够接受的一系列的理论假设，由上述假设解决的一系列问题。数学上范数表示这个变化过程的大小的一个度量。），但它也暴露了潜在恶意攻击者的巨大漏洞，这些攻击者的目标是从所学到的信息中推断单个节点的敏感属性。

如今，由于各种公开可用的结构化数据在真实场景中被使用和探索，例如社交网络、推荐系统和知识图，这一点尤为重要为此，我们用Av∈E{0,1}9表示节点v的敏感属性，如社交网络用户的年龄、性别、收入等。

攻击者A的目标是试图猜测或重构敏感属性Av，通过查看节点表示形式Xv(k)。注意，在这种情况下，仅仅从输入Xv中删除敏感属性Av是不够的，因为在实践中可能存在冗余编码问题（加入了大量的冗余信息，从而达到加密的目的），即Xv中的其他属性可以与Av高度相关，另一种潜在的防御技术是通过对学习到的表示Xv(k)进行同态加密(对数据进行处理，对经过同态加密的数据进行处理得到一个输出，将这一输出进行解密，其结果与用同一方法处理未加密的原始数据得到的输出结果是一样的。)，使加密后的数据可以安全地传输并用于下游任务。
然而，这往往涉及昂贵的计算，甚至在测试阶段，这限制了其应用在移动设置。
从信息论的角度探讨了上述方法的另一种选择,特别地，设

（节点特征Xv∈R^d）
为对抗攻击者的集合，以GNNs的最后一层特征作为输入输出，对敏感属性进行猜测。
设D为节点输入X、敏感属性A和目标变量y上的联合分布，我们将对抗性攻击者的优势定义为

注意：集合A的上确界记为Sup{A}(最小上界)，下确界记为Inf{A}(一个集合的最大下界)

其中Z是对x进行一系列GNN层变换表示节点特征的随机变量。
在上面的定义中，f可以理解为特定的攻击者，(3)中的上和对应于从FA类中寻找最强(最坏)的攻击者。
如果Advp (FA) = 1,那么存在攻击者通过观察节点功能几乎肯定能猜出敏感属性A。
为此,我们的目标是找到表示Z这样Advp (FA)很小,这意味着即使是最强的攻击者从FA总不能正确猜出敏感属性通过查看表示Z.
整个论文我们假设FA是对称的,即,如果f ∈FA,那么1-f ∈FA。

算法分析
在本节中，我们首先将上述对抗性攻击者的优势与一个自然数量联系起来，该数量通过查看节点特征Z=X(K)来衡量攻击者预测敏感属性A的能力。
受此关系启发，我们接着引入GNN特征编码器和最坏情况攻击者之间的极大极小博弈，讨论其中的潜在权衡，并分析这种防御的效果。

考虑一个对称的攻击者集合FA，那么很容易看出，1-Advp(FA)本质上对应于来自FA的任何攻击者希望达到的最佳i型和ii型推断错误之和，下式可知

因此为了最小化Advp (FA),一个自然的策略是学习GNN的参数,以便它过滤掉节点中的敏感信息输入,同时试图保存相关信息。
推断Y的目标任务明确地说,我们可以解决以下无约束最优化问题,权衡参数λ> 0

这里我们分别用εΥ(·)和εA(·)表示预测Y和A时的交叉熵误差(度量两个概率分布间的差异性信息。)，g对应GNN特征编码器(特征向量进行编码)。
显然,超参数λ控制精度和防御之间的平衡。
一方面，如果λ→0，我们几乎不关心A的防御，而是专注于最小化预测错误。
在另一个极端，如果λ→∞，我们只对防御潜在的攻击感兴趣。

请注意，上述公式不同于通常对图的中毒攻击，其目标是在数据中毒下学习健壮的节点分类器（投毒攻击：攻击者对算法的训练集进行投毒，从而影响训练好的算法在未被污染的测试集上面的表现）。

值得指出的优化式(5)承认一个有趣的博弈论的解释,两个特工f和g玩游戏的分数是由目标函数定义在(5)
直观地看,f是攻击者试图最小化的和i型和ii型错误
GNN g与f通过学习转换删除敏感信息属性A .
注意，在这个连续的游戏中，GNN g是第一个移动者，攻击者f是第二个。
因此，在没有显式约束的情况下，g具有先发优势，因此GNN g可以通过简单地将所有节点输入X映射到一个固定或均匀随机噪声来控制游戏。
为了避免上述情况
(5)的目标函数中的第一项作为激励，鼓励GNN保存与任务相关的信息。
但这种激励会损害A的信息吗?
作为一个极端的例子，如果目标变量Y和敏感属性A是完全相关的，那么很明显，在实现属性的准确性和防止信息泄露之间存在权衡。

在下文中，我们将对这种内在的权衡进行分析。

预测准确性与对抗优势的权衡
正如我们上面简要提到的，一般情况下，不可能同时达到防御和准确性最大化的目标。
但是，当精准度和防守度相互关联时，它们之间的平衡到底是什么呢?
下面的定理描述了目标预测器的交叉熵误差和对抗性攻击者的优势之间的权衡:

定理1：设Z为GNN产生的节点特征g, FA为所有二进制预测器(由上文可知FA是第k层节点到01的一个映射集合，既是攻击者的一个集合)的集合。（h以GNNs的节点特征作为输入并产生预测）

首先

表示给定A = a∈{0,1}时，预测Y的条件交叉熵误差。

因此，上述定理说明，在ðY|A给出确定的某一阈值(常数)之前，任何基于GNN g给出的特征的目标预测器必然会在至少一个敏感群上产生较大的误差。

此外，对手优势Advp(FA)越小，误差下界越大。

注意，定理1中的下界是与算法无关的，并且考虑了可能最强的对抗攻击者，因此它反映了错误最小化和对抗攻击防御之间的内在权衡。

值得指出的是，定理1中的结果并不依赖于敏感属性A的边际分布，结果中的所有项只依赖于给定A=0和A= 1的条件分布。

这通常比包含互信息的边界更可取，例如I(A,Y)，因为如果A的边缘分布高度不平衡，I(A, Y)接近0（互信息：它可以看成是一个随机变量中包含的关于另一个随机变量的信息量，或者说是一个随机变量由于已知另一个随机变量而减少的不肯定性）。

作为定理1的一个推论，总误差也确认一个下界:

补充设g#D，为D在GNN特征编码器g下的诱发(前推)分布。
为了简化表示法，我们也分别用Do和D1表示在A=0和A= 1条件下D的条件分布。
由于h: Z→{0,1}是任务预测器，故(hog)#Do和(hog)#D1在{0,1}上前推出两个分布。
回想一下drv(· ，·)是概率分布空间上的距离度量，通过一系列三角形不等式，我们有:

其中第2个方程fE(·)是事件E的特征函数，将上述两个不等式结合起来，有:

其中最后一个不等式是由于交叉熵损失是0-1二进制损失的上界。
为了完成证明，认识到对于二元预测问题，总变量项
drv(D(Y | A=0)，D(Y | A= 1)) 如下化简:

故而可以得出：

推论2：假设定理1中的条件成立，那么

上面的两个下界表示我们为了最小化对抗优势而必须在预测准确度方面付出的代价。
仔细看看下界中出现的常数项ðYIA，注意到这一点。
如果目标变量Y在统计上独立于敏感属性A，则ðY|A = 0，因此下界的第一项减少为0，这意味着即使我们完美地最小化了对手优势，也不会损失准确性。
如果目标变量Y是一个双射的敏感属性的编码A,
例如,Y = A or Y = 1-A,然后ðY|A =1因此第一项的下界达到最大值1,也就是说,在这种情况下,如果对手的优势Advp (FA)) = 0,那么无论我们使用什么预测器h(h以GNNs的节点特征作为输入并产生预测),它必须产生至少一个共同的错误.
min{PrD(A= 0),PrD(A= 1)}
请注意，这是我们通过使用固定的预测得到的错误率。

补充

保证对抗对手的攻击

在本节中，我们通过解决(5)对付最坏情况攻击者来分析这种防御的效果。

利用神经网络对一般非凸凹博弈中的(5)优化的分析仍然是一个活跃的研究领域
因此超出了本文的讨论范围。

相反，这里我们假设我们可以获得(5)的极大极小驻点解，并专注于理解(5)的解如何影响我们防御的有效性。

在接下来的内容中，我们分析了当任务分类器和对手都具有无限容量时，最坏情况下对手所产生的真实误差，即它们可以是Z到{0,1}之间的任意随机函数。

为了研究真实误差，我们在目标函数中使用总体损失而不是经验损失。

在这样的假设下，很容易看出，给定任意从GNN g中嵌入Z的节点，最坏的情况对手是条件分布:

表示在已知随机变量Z的条件下随机变量A的不确定性。（条件熵）

通过对称论证，我们也可以看到

因此我们可以进一步将优化公式(5)简化为如下形式，其中唯一的优化变量是嵌入g的GNN节点:

现在我们可以分析最坏情况下对手所产生的误差。

定理3：设Z为(7)的最优GNN（7）节点嵌入
定义H:= H(A|Z*)。
然后对任何对抗

定理3表明，在这种设置下，只要条件熵 H* = H(A | Z* )很大，那么任何(随机)对手产生的敏感属性的推理误差必须至少为Ω( H* / log(1/ I * ))。
条件熵进一步可以灵活调整优化权衡参数λ。

定理3还表明，GNN节点嵌入有助于防御，因为对于从输入X创建的任何GNN特征Z，我们总是有H(A| Z) ≥ H(A| X)。
最后需要注意的一点是，表示Z出现在上面的范围取决于图结构(像等式(1)和(2)证明)
在定理3和推理的错误表示Z(而不是原始输入X),这意味着防御可能适用于对邻近点的攻击。

补充
应用定理1中的下界完成证明。
以下关于逆二进制熵的引理将在定理3的证明中有用:

是s∈{0，1}的逆二元熵函数，

设Z为(7)的最优GNN节点嵌入
定义：H=H(A|Z*)
然后，对于一些攻击者：

为了展示方便，我们定义Z=Z*，为证明该定理，设E'为取值为1的二进制随机变量

现在考虑A，f(Z)和E的联合熵，一方面：

请注意，第二个方程成立，因为E'是A和f(Z)的确定性函数，也就是说，一旦，A和f(Z)已知，E也已知。因此H(E | A, f(Z)) = 0。另一方面，我们也可以将H(A,f(Z)， E)分解为:

将上述两个等式结合起来就产生了：

另一方面，我们也可以将H(E, A | f(Z))分解为

此外，由于条件作用不能增加熵，我们有H(E| f(Z)) < =H(E)，这进一步说明

现在考虑H(A | E, f(Z))由于A ∈{0,1}，根据条件熵的定义，有:

下界H(A I f(Z)）

由于f(Z)是Z的一个随机函数，使得a L f(Z) | Z，由于著名的数据处理不等式，我们有I(A;f (Z)) < I(A;Z),这意味着:

把上面的一切结合起来，我们有以下不等式链:

这意味着;

式中H2^(-1)(·)为二元熵H(t)的反函数:=-tlogt-(1-t) log(1-t)

当t ∈[0,1]最后

我们利用引理6进一步对逆二元熵函数下界进行了证明

邻域攻击和n-hop Genrealization

GAL有效保护敏感信息。两个面板显示了不同防御强度λ (0 vs. 1:3)下图特征表示的t-SNE图。节点颜色代表节点类。

最后，我们考虑攻击者试图从嵌入的邻居中提取节点级信息的场景。在GNNs中，这是一个特别严重的问题，因为消息传递层包含了社区级信息，因此会造成信息泄漏。
我们在图中的结果验证了，在没有任何形式的防御(λ = 0)的情况下，攻击者通过使用简单的2层chebcon - gnn访问Movielens-1M数据集上邻居的嵌入，确实实现了非同小可的性能。
我们进一步进行了综合实验，防御目标是邻居级嵌入，并且我们观察到攻击者的性能(在节点级和邻居级嵌入上)随着λ的增加而下降。
结果表明，在λ值较低的情况下，邻域级防御对邻域攻击者的影响大于节点攻击者，这表明节点级嵌入的防御效果较差。
然而，随着λ持续增加，节点攻击者的性能下降更加明显。
这种设置的一个扩展是将社区级攻击视为单跳攻击，我们可以自然地将n-hop定义为攻击者只访问距离目标节点n远的嵌入节点。
自从发现n-distant任意节点的邻居在一个大型图表动态计算效率低下在训练(的复杂性必然涉及jEj和合资j),我们建议蒙特卡罗算法概率发现这样的邻居在O (n^2)时间,也可以在附件中找到的细节。
我们在Movielens-1M上报告相同编码器-λ设置下不同跳数下的结果，如图3所示。一般来说，我们观察到随着跳数的增加，检索到的嵌入包含的关于目标节点的信息越来越少。
因此，对抗训练效应对目标任务退化的影响较小，RMSE的稳定下降证明了这一点。
节点级和邻域级攻击者趋势的波动是由于用于抽样邻居的蒙特卡罗算法的概率性质，它可能最终找到一个比预期更接近的邻居，破坏训练过程的稳定性。
由于训练时间有限，这是另一种折衷，但总的趋势仍然可见，证明了我们的假设。

总结：
在这篇论文中，我们讨论了具有GNNs的图的属性推理攻击问题。
我们提出的框架，称为GAL，引入了期望GNN编码器和最坏情况攻击者之间的极大极小博弈。由此产生的对抗性训练在误差率的可证明下限方面为推理创造了强大的防御，而在任务执行方面只遭受了边际损失。我们还展示了一个信息论的界限来描述准确度和防御之间的内在平衡。
在几个基准数据集上的实验表明，我们的方法可以很容易地补充部署在下游任务中的现有算法，以解决图结构数据上的信息安全问题。

参考：GRAPH ADVERSARIAL NETWORKS: PROTECTING INFORMATION AGAINST ADVERSARIAL ATTACKS

数学推导中有不懂的地方，可以学习了解下文：
信息熵及其相关概念