KDD 2022 | 中科院计算所提出无监督高鲁棒性图结构学习框架—STABLE

©作者 | 社媒派SMP

单位 | 中科院计算所

来源 | 中科院计算所MLDM组

图神经网络在诸多基于图数据的下游任务中表现出色，但近年来研究发现图神经网络面对恶意的结构扰动非常脆弱。一种直观的增强鲁棒性的方法是图结构学习，通过优化被篡改的图结构缓解攻击带来的负面影响。已有方法大多基于原始特征或者监督信号来进行图结构学习。但这两种方法都存在一定的局限，前者缺乏对结构信息的利用，而后者因为分类器受到攻击，表征质量也随之下降。

鉴于此，我们提出了一个基于对比学习的无监督框架来获取鲁棒的高质量表征，以此来进行结构优化。另一方面，我们还发现 GCN 的重参数化 trick 会使得模型更加脆弱，因此我们简单地修改了 GCN，获得了更鲁棒的下游分类器。

论文标题：

Reliable Representations Make A Stronger Defender: Unsupervised Structure Refinement for Robust GNN

论文链接：

https://arxiv.org/abs/2207.00012

研究动机

近年来，得益于消息传递机制，图神经网络（GNN）在大量基于图数据的任务上取得了卓越成效，尤其是半监督节点分类任务 [1, 2]。然而，最新的研究表明，GNN 在攻击面前极为脆弱，尤其是结构扰动型攻击。攻击者只需要对图结构进行微小的篡改就能使模型性能大幅下降 [3, 4, 5]。

模型的对抗鲁棒性（Adversarial Robustness）在一些 security-critical 任务中至关重要，例如欺诈交易检测，欺诈者可以在金融交易图中，通过故意和普通用户建立交易关系，来隐藏自己的欺诈意图。

最直观的提高 GNN 鲁棒性的方法是对干扰连边进行侦测，找出潜在的扰动并将其删除或者降低对模型的影响。其中一种代表性方法是基于一个 pair-wise function   计算任意两个节点 i, j 之间的权值，进而给邻接矩阵计算出一个权重矩阵（weights matrix），最终基于这个权重矩阵决定一条边在图中的去留，达到优化图结构的目的 [6]。

先前的方法更多的关注如何设计一个巧妙的 function 来得到一个更准确地 weights matrix，总体上可以分为两类：

1. Feature-based：这类方法用节点的原始特征去计算  ，代表方法有 GCN-Jaccard [7]，GNNGuard [8] 等；

2. Representation-based：这类方法用基于监督信号获取的表征去计算  ，代表方法有 GRCN [9] 等。

但这两类方法均有一定的局限。下面是在 Cora 数据集上用 MetaAttack 在不同扰动率下进行攻击的结果。从结果可以看出，feature-based 的方法在扰动率较低的时候，表现甚至不如 Vanilla GCN，表现出了明显的 performance 和 robustness 的 trade-off。

这是由于基于特征优化图结构丢失了图中的拓扑信息，在扰动率较低的时候，删除的正常连边的负面影响大于了删除干扰边的正面影响，从而出现了 trade-off；另一方面，基于监督信号获取 representation 的方法在扰动率较高的时候性能下降明显，这是因为分类器受到了攻击算法影响，可以认为基于下游任务学到的 representation 的质量和下游任务的表现强相关，在扰动较高的时候质量较低，用低质量的表征优化结构自然很难得到高质量的图结构。

基于以上分析，我们认为设计对抗结构扰动攻击的方法关键在于得到一个在对抗攻击场景下可靠的表征，再利用它优化图结构。我们认为可靠的表征应有以下特点：1）携带特征信息的同时，包含尽可能多的正确的结构信息；2）与下游任务无关，并对结构扰动不敏感。

基于此思路，我们提出了一套无监督的 pipeline 方法 STABLE，用于图结构优化。

方法

2.1 Representation Learning

前文提到解决该问题的关键是得到可靠的表征，我们采用了对比学习作为这部分的 backbone。一方面，对比学习在图的无监督表示学习上的高效性已经得到了充分验证；另一方面，对比学习中的 augmentation 策略和 graph attack 有天然联系。

例如，一种常用的生成 augmentation views 的方法就是对图结构进行随机扰动，而这也可以看作是在对图做随机攻击（Random Attack）。基于此特性，我们可以设计一些更贴近攻防场景的数据增强策略。 

我们设计了两种适用于图对抗鲁棒性场景的改进策略，训练前的 preprocess 和生成 augmentation views 的 recovery。在图上进行对比学习训练之前，preprocess 首先基于简单的相似度策略进行粗略剪枝：

该函数计算任意两个相连节点的相似度，剪去低于一定阈值的连边。这一步可以对图进行粗略的净化，删除那些容易被侦测出来的干扰边。

第二步生成多个 views，将第一步 preprocess 中删除的边，进行小部分随机恢复来得到一个 view。同时，对比学习训练中需要有负样本来构成负样本对，我们沿用 DGI [10] 中随机扰动特征矩阵的方法来获取负样本，训练的目标函数是：

我们采用了全局局部的对比模式 [10]，而没有用常见的局部对比 [11, 12]。因为攻击者在对图结构进行扰动时需要保持 unnoticeable，即全局不显明性，这也就决定了攻击对某些节点的局部可能修改很大，但对全局的影响却是比较小的。因此，采用 global-local 的对比范式，也是在用受影响较小的全局表征对局部表征进行校准。

为什么 preprocess 和 recover 这两个操作可以得到满足我们要求的表征呢？回想一下第一个要求，我们希望学习到的表征中包含特征信息以及尽可能多的正确的结构信息，而基于特征相似性的 preprocess 步骤进行的粗剪枝和对比学习在图表示学习上的高效性满足了这个要求。

第二个要求，我们希望表征对结构扰动不敏感，而 recovery 这个操作本质上可以看作是在对预处理后的图进行微小的攻击，因为 preprocess 删除的大部分是易察觉的干扰边，那么恢复的也大概率是干扰边。因此，recovery 可以看作是在以攻击方式生成 augmentation views。

对比学习训练的目标会使得各个 view 和经 preprocess 步骤后得到的图  的表征接近，也就是对每个 view 包含的微小攻击不敏感，从而满足了可靠表征的第二个要求。

2.2 Graph Refining

当得到了高质量表征之后，优化结构就非常简单了，只需要基于简单的相似度度量对图进行加减边，剪去相似度低于阈值的边，并为每个节点连上 k 个与其最相似的节点，如下图。

2.3 Classifier

当图结构优化优化完成了，理论上可以衔接任意的分类器进行下游任务，以往的方法有许多采用了 Vanilla GCN，例如 SimpGCN [13]、GCN-Jaccard，我们发现，GCN 的 renormalization trick 会加重 GCN 的脆弱性。 

以往的研究发现，攻击算法更倾向于攻击低度节点，但这只关注了干扰边一侧的特点，缺忽视了什么样的节点会被用作 fake neighbor，我们定义边的度为两个相连节点的度之和，并将图中干扰边和普通边的度分布展示如下图：

可以发现干扰边度都较低，换言之攻击算法会给低度节点连上一个低度的邻居，回顾一下 GCN 的 renormalization trick：

可以看出，GCN 会给低度的邻居分配更高权重，低度节点的邻居较少，加之 fake neighbor 的负面影响，分配低度邻居更高的权重进一步扩大了负面影响。我们的解决方法也非常直观，反其道而行，给高度节点和节点自身特征赋更高的权重：

对比发现，这个微小改动能显著增强 GCN 的鲁棒性，如下图。

实验结果

我们在四个 benchmark 数据集上验证了 STABLE 的鲁棒性，对比了与其他 7 种 Robust GNN 在 3 种攻击算法下的性能表现。

可以看出 STABLE 在不同数据集、不同攻击算法和各种扰动率下的性能具有一致的优越性。

上图是将三种算法总体剪边数量调整到 1000 左右时统计的删除干扰连边占比情况，可以看出 STABLE 删掉的干扰边最多，具有更准确的结构学习能力。

上图为参数敏感性实验以及在不同扰动率下取得最佳表现的具体参数值。其中k为添加的邻居数量，  为分类器为邻居节点分配权重的幂值，越高代表给高度节点越高的权重，可以看出随着扰动率的上升，应该给节点增加更多相似邻居，同时应该更多在消息传递过程中采用高度邻居的信息。

上图为 ablation study，几种变体含义分别为：

• STABLE-P：没有 preprocess

• STABLE-A：没有 augmentation 策略

• STABLE-Ran：采用随机扰动生成 views

• STABLE-K：没有 top-k 加邻居策略

• STABLE-GCN：下游分类器采用普通 GCN

值得注意的是 STABLE-A 和 STABLE-Ran 的线条几乎重合，说明随机的增强策略和无增强效果接近，间接表明 recovery 的策略切实有效。

结论

文章提出了 STABLE，一种无监督的图结构学习框架。其重点是我们认为计算边的权重矩阵的关键在于学习到可靠的表征，基于此思路，设计了面向对抗鲁棒性的对比学习模型来获取高质量的节点表征，该方法在多个数据集上抵御多种攻击算法的鲁棒性均显著超过了以往的方法。

参考文献

[1] William L Hamilton, Rex Ying, and Jure Leskovec. 2017. Inductive Representation Learning on Large Graphs. In NeruIPS. 1025–1035.

[2] Thomas N. Kipf and Max Welling. 2017. Semi-Supervised Classification with Graph Convolutional Networks. In ICLR.

[3] Hanjun Dai, Hui Li, Tian Tian, Xin Huang, LinWang, Jun Zhu, and Le Song. 2018. Adversarial Attack on Graph Structured Data. In ICML. 1115–1124.

[4] Daniel Zügner, Amir Akbarnejad, and Stephan Günnemann. 2018. Adversarial Attacks on Neural Networks for Graph Data. In KDD. 2847–2856.

[5] Daniel Zügner and Stephan Günnemann. 2019. Adversarial Attacks on Graph Neural Networks via Meta Learning. In ICLR.

[6] Yanqiao Zhu, Weizhi Xu, Jinghao Zhang, Qiang Liu, Shu Wu, and Liang Wang. 2021. Deep Graph Structure Learning for Robust Representations: A Survey. arXiv preprint arXiv:2103.03036.

[7] HuijunWu, ChenWang, Yuriy Tyshetskiy, Andrew Docherty, Kai Lu, and Liming Zhu. 2019. Adversarial Examples on Graph Data: Deep Insights Into Attack and Defense. In IJCAI. 4816-4823.

[8] Xiang Zhang and Marinka Zitnik. 2020. GNNGuard: Defending Graph Neural Networks Against Adversarial Attacks. In NeurIPS. 33, 9263-9275.

[9] Donghan Yu, Ruohong Zhang, Zhengbao Jiang, Yuexin Wu, and Yiming Yang. 2020. Graph-revised Convolutional Network. In ECML. Springer, 378–393.

[10] Petar Veličković, William Fedus, William L Hamilton, Pietro Liò, Yoshua Bengio, and R Devon Hjelm. 2019. Deep Graph Infomax. In ICLR.

[11] Kaveh Hassani and Amir Hosein Khasahmadi. 2020. Contrastive Multi-view Representation Learning on Graphs. In ICML. PMLR, 4116–4126.

[12] Yanqiao Zhu, Yichen Xu, Feng Yu, Qiang Liu, Shu Wu, and Liang Wang. 2020. Deep Graph Contrastive Representation Learning. In ICML Workshop on Graph Representation Learning and Beyond.

[13] Wei Jin, Tyler Derr, Yiqi Wang, Yao Ma, Zitao Liu, and Jiliang Tang. 2021. Node Similarity Preserving Graph Convolutional Networks. In WSDM. 148–156.

更多阅读

#投 稿 通 道#

 让你的文字被更多人看到 

如何才能让更多的优质内容以更短路径到达读者群体，缩短读者寻找优质内容的成本呢？答案就是：你不认识的人。

总有一些你不认识的人，知道你想知道的东西。PaperWeekly 或许可以成为一座桥梁，促使不同背景、不同方向的学者和学术灵感相互碰撞，迸发出更多的可能性。 

PaperWeekly 鼓励高校实验室或个人，在我们的平台上分享各类优质内容，可以是最新论文解读，也可以是学术热点剖析、科研心得或竞赛经验讲解等。我们的目的只有一个，让知识真正流动起来。

📝 稿件基本要求：

• 文章确系个人原创作品，未曾在公开渠道发表，如为其他平台已发表或待发表的文章，请明确标注 

• 稿件建议以 markdown 格式撰写，文中配图以附件形式发送，要求图片清晰，无版权问题

• PaperWeekly 尊重原作者署名权，并将为每篇被采纳的原创首发稿件，提供业内具有竞争力稿酬，具体依据文章阅读量和文章质量阶梯制结算

📬 投稿通道：

• 投稿邮箱：[e-mail] 

• 来稿请备注即时联系方式（微信），以便我们在稿件选用的第一时间联系作者

• 您也可以直接添加小编微信（pwbot02）快速投稿，备注：姓名-投稿

△长按添加PaperWeekly小编

🔍

现在，在「知乎」也能找到我们了

进入知乎首页搜索「PaperWeekly」

点击「关注」订阅我们的专栏吧

·