ICML 2023 | 通过图模型窃取图数据？图重建攻击与防御的系统研究

图神经网络（Graph Neural Network, GNN）促进了许多现实世界的应用，如药物发现，推荐系统与社交网络[1,2,3]。然而，GNN的潜在隐私泄漏风险仍未被系统地定义与研究。GNN的训练图数据中，图邻接矩阵往往包含大量的隐私信息，如社交媒体上的朋友关系。前人工作中，已证实了重建攻击窃取视觉模型CNN训练数据的可行性 [4,5,6]，但目前暂无工作从GNN的视角系统性地研究图模型的重建攻击问题。为了填补这一空白，我们首次对图重建攻击（Graph Reconstruction Attack, GRA）进行了系统且深入的研究。

论文标题： On Strengthening and Defending Graph Reconstruction Attack with Markov Chain Approximation. 论文链接： https://arxiv.org/abs/2306.09104 代码链接： https://github.com/tmlr-group/MC-GRA

我们正式地定义了图重建攻击问题，并提出链式建模：将GNN的前向推理流程建模为一个马尔可夫链（Markov Chain），其中间状态对应GNN在该层的表征。基于此建模和信息论的指导，我们提出了攻击方法Markov Chain-based Graph Reconstruction Attack（MC-GRA）与防御方法Markov Chain-based Graph Privacy Bottleneck（MC-GPB）。其攻&防效果如图1所示：MC-GRA能通过GNN还原邻接关系（中图），而MC-GPB能有效帮助GNN抵御攻击（右图）。

图1. Cora 数据集上恢复的邻接关系。绿点为正确预测的边，红点则表示错误预测。

简言之，在本项工作中：

• 
  

  我们首次对GRA展开系统研究，并揭示了几个重要的现象：原始GNN对应的马尔科夫链中的单一变量可以在一定程度上恢复原始邻接关系，然而多个变量的线性组合只能略微增加重建精度。此外，GNN模型在训练中，会首先记住邻接关系并逐步遗忘；这些发现指导了我们设计相应的攻防方法。

  
  

• 
  

  我们基于链式建模和信息论理论，提出了图与防御图重建攻击的机制：为了更精确地重建图，攻击者必须从预训练的GNN和先验知识中提取出更多的隐私信息（MC-GRA）；而为了更安全地训练，防御者必须在训练GNN时丢弃更多敏感的链接信息，并避免模型性能崩溃（MC-GPB）。

  
  

• 
  

  实验方面，在三种常见图模型和六个常用数据集上，MC-GRA均取得了最优的图重建效果，MC-GPB则在略微损失精度的情况下，大幅削弱了所有的重建攻击的能力。

  
  

接下来，将简要地分享我们发表在 ICML 2023 上关于图重建攻击的研究结果。

一、问题定义：图重建攻击

我们首先通过一个简单例子，来理解图重建攻击。如图2所示，其中

• 
  

  GNN的前向推理（蓝色箭头）：通过角色本身属性以及角色之间的亲缘关系，推断各个角色所属的家族，如推断Daenerys为Targaryen家族，Arya为Stark家族。GNN 通过输入的图节点特征 以及图邻接矩阵 ，预测图节点标签 ；

  
  

• 
  

  图重建攻击则是一个逆向的过程（红色箭头）：通过角色所属家族，推断角色之间的亲缘关系，如Sansa与Arya同为Stark家族，那么她们很有可能存在亲缘关系。此处，图重建攻击旨在通过 及 ，重建原始邻接矩阵 。

  
  

图2. 图重建攻击示意图。

正式地，我们给出了图重建攻击的定义：给定一个先验知识集合 ，一个预训练GNN ， 图重建攻击旨在重建图邻接矩阵 ，来逼近训练图 的原始邻接矩阵 ，即

其中， 表示生成 的攻击方法，而 可以是集合 的任意子集，在此 代表节点表征， 为模型分类输出。

为了更好地研究GNN是如何产生隐私泄漏的，我们将GNN的推理流程建模为马尔可夫链，如图3所示。

这里，GNN的前向推理可以看作是离散的、不可逆转的、成对无关的马尔科夫链，即当前状态 的概率只取决于前一个状态 ，其中转移核由 和 决定。 该链式建模带来了三方面的优势：

• 
  

  能够自适应地利用任何一组先验知识以达成白盒攻击，如节点特征 与标签 等；

  
  

• 
  

  有助于推导出基于链式攻击和防御的优化目标；

  
  

• 
  

  能够从信息论的角度进行理论分析。

  
  

图3. 将GRA问题建模为用攻击链逼近原始马尔可夫链。

其中，原始链（ORI-chain）和攻击链（GRA-chain）的详细展开如下：

二、 先导实验：GNN推理过程中的隐私泄漏

对于节点分类任务，GNN的推理流程可简化为一个马尔可夫链 ，其中

• 
  

  邻接矩阵 与节点特征矩阵 作为模型输入生成节点表征 ；

  
  

• 
  

  通过线性层转换为分类输出 来预测节点标签 。

  
  

由于部分转移核由 决定，原始链（ORI-Chain）中的变量 可能包含原始邻接矩阵 的信息。为了量化 与 的直接相关性，即 与 的互信息 ，我们通过点乘法将 转换成计算 与 的AUC指标，其中 为激活函数，结果如下。

表1. A与Z互信息的量化结果，其中以AUC作为量化指标。

表1的量化数据表明，预训练GNN所包含的信息与原始邻接矩阵存在大量重合，并有如下两个新发现：

• 原始链中的单一变量可以在一定程度上恢复原始邻接关系；

• 
  

  先验知识的线性组合只能略微增加重建精度。

  
  

接下来，为了进一步理解原始链的学习和记忆机制，并为设计相应的防御方法提供灵感。我们提出图信息平面[7,8]（graph information plane），通过隐私度 和准确度 来跟踪训练过程，并把训练阶段的 被投 射到二维平面 上。

如图4所示，GNN训练可分成两个主要阶段，拟合和压缩：

• 
  

  在第一个较短的阶段，，GNN表征包含更多的隐私信息；

  
  

• 
  

  而在第二个较长的阶段，，GNN表征会逐渐丢失隐私信息。

  
  

图4. 图信息平面：可视化GNN训练过程隐私信息变化趋势。

三、攻防方法：基于马尔可夫链的图重建攻击与防御

图5. MC-GRA算法框架（左），MC-GPB算法框架（右）。

基于以上发现，我们提出了基于马尔可夫链的图重建攻击（MC-GRA）与防御（MC-GPB）方法。

• 
  

  MC-GRA：在模型前向推理过程，我们从一个参数化的分布 中采样出重建的邻接矩阵 并注入噪声。注入的噪声将有利于移除 , 和 之间潜在的虚假相关性。

  
  

• 
  

  MC-GPB：通过在GNN训练过程中约束节点表征，使得GNN遗忘 中的隐私信息。我们同时向 注入随机噪声来促进此遗忘过程。

  
  

接下来，我们将详细地阐述我们提出的攻击与防御算法。

Markov Chain-based Graph Reconstruction Attack (MC-GRA):为了更充分地利用原始链所包含的隐私信息，我们利用攻击链（GRA-Chain）去自适应地逼近原始链的变量，以获得原始邻接矩阵 的最优近似矩阵 。

MC-GRA是一个maximin博弈：它最大化了两个马尔可夫链的前向过程的近似值，同时最小化了每个转移的复杂度，并限制复杂度以避免平凡解。MC-GRA的自适应能力来自于它对任何先验知识集的利用，即公式（3）中的 和 ，一旦获得便能立即生效。因此，它可以作用于任意的先验知识组合，具体算法如下。

图6. MC-GRA 算法。

Markov Chain-based Graph Privacy Bottleneck (MC-GPB):为了防御图重建攻击，我们基于信息瓶颈理论提出了MR-GPB，其优化目标为：

MC-GPB也是一个maximin博弈，旨在促进 与 之间的相关性最大化的同时，最小化其与 之间的相关性。公式（4）的目标是通过平衡预测准确性 和隐私性 来最小化条件互信息 。

为了进一步的促进GNN对 的遗忘，我们在训练过程中对 注入随机噪声，迫使GNN辨识必要的拓扑信息 ，而不是完全捕获 和 之间的关联，以期保护隐私的同时保证准确性，具体算法如下。

图7. MC-GPB 算法。

四、理论分析：从信息论角度理解攻与防

图8. 训练、攻击和防御过程的信息属性。

接下来，我们通过图8与数条定理，从信息论的角度分析MC-GRA与MC-GPB可行性：

• 
  

  定理1:GNN的层级变换 是不可逆的，这里 ，其中 表示图卷积核。此种性质会使得两条马尔可夫链之间的互信息愈来愈低。

  
  

• 
  

  定理2:（保真度下界）攻击保真度满足

其中 为近似误差概率， 为二元熵。

上述定理表明，在执行最大化互信息项的GRA时， 可以作为有价值的参考（见图 8（b））。此外，定理2还表明，较高的近似值 和较低的误差 可以带来较高的 ，即攻击保真度较高。

• 定理3:（最优保真度）重建保真度满足

定理3表明，MC-GRA 能够达到最佳重建保真度。需要注意的是， 中余下的信息，即 部分，是无法从 中观测到的（除非提供额外信息），如图 8（b）中 与 的非重叠区域。

• 定理4:（最大邻接信息） 和 之间的互信息满 足

定理4表明，图表征可能会保留 的最大隐私信息，即 ，其中存储了过多的邻接信息 ，如图8（a）所示。

• 定理5:（最小邻接信息）对于任务 和邻接矩阵 的充分图表征 ，满足 如果 ，则可实现最小互信息 。

定理5表明，求解MC-GPB可以得到最佳表示的近似值，如图8（c） 所示，它满足充分性（准确性保证）和最小邻接性（隐私性保证）。

四、实验与讨论

我们提供了多维度的实验结果，以理解我们提出的方法性能及底层机理。

主要性能对比：我们针对标准的两层GCN模型在6个常见的数据集上评估MC-GRA。如表3所示，在不同的可用先验知识场景下，MC-GRA相较于简单的线性组合GRA有较大的提升。

表3. MC-GRA的攻击表现。我们根据原文表2的数据，计算相对提升(以%表示)。

同时，我们借助两种不同的GRA算法，以及我们提出的MC-GPB，评估防御算法MC-GPB的性能，如表4与5所示。可以看到，经由MC-GPB训练的GNN大幅减少了隐私信息的泄漏，同时最大程度地保留预测准确度。

表4. MC-GPB对不同攻击方法的防御表现。我们根据表1的数据，计算相对提升（以%表示）。

多方面的消融实验及深入讨论：我们进一步进行了诸多消融实验，深入探讨了所提方法在不同设定下的性能表现。

表6. MC-GRA在不同GNN架构的攻击表现（Cora 数据集）。

如表6，7所示，MC-GRA与MC-GPB可以推广到不同层数、不同类型的GNN：

• 一般而言，更深的模型（更大的层数 ）可以更好地保护隐私（更低的 ）。然而，由于GNN在信息传播中的过度平滑效应，增加层数会使模型准确率的急剧降低；

• 
  

  此外，一个表达能力更强大、精度更高的模型通常更容易受到GRA的影响，这在实际应用中会带来更高的隐私泄露风险。

  
  

结果可视化：我们提供了不同算法重建的邻接矩阵的可视化结果，如图9所示。可以看到，我们的MC-GRA精确恢复了近乎所有的原始边（a），且MC-GPB也能够充分地防御攻击算法，使得其预测出错（b）。

图9. (a):不同GRA从常规训练的GNN恢复的邻接关系; (b):不同GRA从MC-PGB训练的GNN恢复的邻接关系，以Cora与Brazil为例。

此外，我们还提供了以及经由MC-GPB训练的图信息平面，如图10所示，MC-GPB在保留原有精度的前提下，大大降低了隐私泄漏的风险。

图10. 经由MC-GPB训练的GNN在Cora数据集上的图信息平面

五、总结

本文中，我们对增强和防御图重建攻击进行了全面研究。基于链式建模，我们将问题转化为用攻击链逼近原始链。

技术上，我们推导出了（1）基于链的自适应攻击方法，可提取更多隐私信息，以及（2）基于链的防御方法，可在保证预测准确性的前提大幅降低攻击准确度。

实验上，我们所提出的方法在六个数据集和三个图模型上取得了最佳效果。

六、展望

增强GRA的一个大方向是从更多信息源中提取邻接信息，例如，利用目标图的部分边或辅助数据集进行转移攻击。GRA可以在更多的GNN架构上进行，并与生成模型（如图自动编码器或扩散模型）相结合。

此外，对图属性（如密度、聚类、motif数量）进行更精细的研究也很有意义，在多大程度上可以恢复上述属性将有助于深入了解GRA的能力和GNN的记忆效应。

最后，将GRA应用于更现实的场景也很有价值，例如Inductive GNN或是攻击者只能获取模型输出的黑盒场景。

参考文献

[1] Fan, W., Ma, Y., Li, Q., He, Y., Zhao, E., Tang, J., and Yin, D. Graph neural networks for social recommendation. In TheWebConf, 2019.

[2] Wu, S., Sun, F., Zhang, W., Xie, X., and Cui, B. Graph neural networks in recommender systems: a survey. ACM Computing Surveys, 2020a.

[3] Ioannidis, V. N., Zheng, D., and Karypis, G. Few-shot link prediction via graph neural networks for covid-19 drug- repurposing. arXiv preprint arXiv:2007.10261, 2020.

[4] Fredrikson, M., Jha, S., and Ristenpart, T. Model inver- sion attacks that exploit confidence information and basic countermeasures. In CCS, 2015.

[5] Zhang, Y., Jia, R., Pei, H., Wang, W., Li, B., and Song, D. The secret revealer: Generative model-inversion attacks against deep neural networks. In CVPR, 2020.

[6] Struppek, L., Hintersdorf, D., Correia, A. D. A., Adler, A., and Kersting, K. Plug and play attacks: Towards robust and flexible model inversion attacks. In ICML, 2022.

[7] Tishby, N. and Zaslavsky, N. Deep learning and the information bottleneck principle. In IEEE information theory workshop.

[8] Shwartz-Ziv, R. and Tishby, N. Opening the black box of deep neural networks via information. In arXiv.

课题组介绍

香港浸会大学可信机器学习和推理课题组（TMLR Group）由多名青年教授、博士后研究员、博士生、访问博士生和研究助理共同组成，课题组隶属于理学院计算机系。课题组专攻可信表征学习、基于因果推理的可信学习、可信基础模型等相关的算法，理论和系统设计以及在自然科学上的应用，具体研究方向和相关成果详见本组Github（ https://github.com/tmlr-group）。 课题组由政府科研基金以及工业界科研基金资助，如香港研究资助局杰出青年学者计划，国家自然科学基金面上项目和青年项目，以及微软、英伟达、百度、阿里、腾讯等企业的科研基金。青年教授和资深研究员手把手带，GPU计算资源充足，长期招收多名博士后研究员、博士生、研究助理和研究实习生。此外，本组也欢迎自费的访问博士后研究员、博士生和研究助理申请，访问至少3-6个月，支持远程访问。有兴趣的同学请发送个人简历和初步研究计划到邮箱（ bhanml@comp.hkbu.edu.hk）

Illustration From IconScout By Delesign Graphics

-The End-

扫码观看！

本周上新！

“AI技术流”原创投稿计划

TechBeat是由将门创投建立的AI学习社区（www.techbeat.net）。社区上线500+期talk视频，3000+篇技术干货文章，方向覆盖CV/NLP/ML/Robotis等；每月定期举办顶会及其他线上交流活动，不定期举办技术人线下聚会交流活动。我们正在努力成为AI人才喜爱的高质量、知识型交流平台，希望为AI人才打造更专业的服务和体验，加速并陪伴其成长。

投稿内容

// 最新技术解读/系统性知识分享 //

// 前沿资讯解说/心得经历讲述 //

投稿须知

稿件需要为原创文章，并标明作者信息。

我们会选择部分在深度技术解析及科研心得方向，对用户启发更大的文章，做原创性内容奖励

投稿方式

发送邮件到

chenhongyuan@thejiangmen.com

或添加工作人员微信（chemn493）投稿，沟通投稿详情；还可以关注“将门创投”公众号，后台回复“投稿”二字，获得投稿说明。

关于我“门”

将门是一家以专注于数智核心科技领域的新型创投机构，也是北京市标杆型孵化器。 公司致力于通过连接技术与商业，发掘和培育具有全球影响力的科技创新企业，推动企业创新发展与产业升级。

将门成立于2015年底，创始团队由微软创投在中国的创始团队原班人马构建而成，曾为微软优选和深度孵化了126家创新的技术型创业公司。

如果您是技术领域的初创企业，不仅想获得投资，还希望获得一系列持续性、有价值的投后服务，欢迎发送或者推荐项目给我“门”:

bp@thejiangmen.com

点击右上角，把文章分享到朋友圈