SimGuard 阅读笔记：Over-Similarity Perspective

论文Boosting Graph Robustness Against Backdoor Attacks: An Over-Similarity Perspective关键词Graph Backdoor Defense、Over-Similarity、Trigger Detection、Contrastive Learning、DRR1. 核心问题现有图后门攻击中的触发器是真的具有样本特异性还是表现出固有的相似性作者发现这些生成的触发器存在过度相似性表现为高度的特征相似性和结构相似性。这种过度相似性使其更容易与干净节点区分开来原因很可能是触发器生成过程缺乏足够约束。2. 核心方法SimGuard 的目标是精准识别触发器并有效消除其影响。整体方法包括将整体异常检测与密度聚类方法结合识别潜在触发器通过灵活边界区分触发器与干净节点提高检测精度引入基于对比学习的触发器检测模块通过对比损失函数让触发器嵌入与干净节点嵌入有效分离。2. Preliminaries2.1 Backdoor and Problem Definition2.1.1 图的基本定义作者定义带属性图为$$G(V,E,X)$$其中$$V\{v_1,\dots,v_N\}$$$$E \subseteq V \times V$$$$X\{x_1,\dots,x_N\}$$这里$V$节点集合$E$边集合$X$节点特征集合。2.1.2 Inductive Setting作者强调训练图和测试图不是同一个图。训练阶段有$$G_T(V_T,E_T,X_T)$$推理阶段有一个未见过的新图$$G_U(V_U,E_U,X_U)$$并且训练图和测试图节点不重叠$$V_U \cap V_T \emptyset$$这个设定很关键。因为如果只是 transductive setting防御方法可能只需要在一个固定图上删除触发器但 inductive setting 要求方法能够迁移到新图上。所以 SimGuard 后面不仅要在训练阶段找 trigger还要训练一个trigger detector使其在推理阶段也能检测新图中的触发器。2.1.3 干净节点与后门节点训练图中有干净节点集合$$V_C \subseteq V_T$$也有后门节点集合$$V_B \subseteq V_T$$干净节点 $v_i \in V_C$ 的标签是真实标签$$y_i$$后门节点 $v_j \in V_B$ 会被攻击者赋成目标类别$$y_t$$也就是说攻击者会把一部分节点污染掉给它们加 trigger并把它们标成攻击目标类别。2.1.4 Trigger 与目标节点之间的边图后门攻击一般不是像图像后门那样贴一个小图案而是在目标节点附近注入节点或子图。作者用$$E_B \subseteq E_T$$表示后门节点和 trigger 之间的连接边。也就是说目标节点本身不一定改变但是它的邻域里多了触发器节点或触发器子图。随后通过 GNN 的 message passingtrigger 信息会传到目标节点上。2.1.5 推理阶段测试图里面也分干净节点和后门节点$$V_U V_U^C \cup V_U^B$$测试阶段后门节点和 trigger 的连接边写成$$E_U^B \subseteq E_U$$这说明攻击不只发生在训练图推理阶段也可能给新节点挂 trigger。2.1.6 攻击者目标攻击者希望训练出一个后门模型使其同时满足两个条件第一带 trigger 的节点被预测成目标类$$f(v_j)y_t$$第二不带 trigger 的干净节点保持正常分类。因此后门攻击的危险在于干净准确率看起来正常但只要触发条件出现模型就会稳定误判。2.1.7 防御者知识防御者不知道$$V_B$$也就是不知道哪些节点被攻击。防御者也不知道$$y_t$$也就是不知道攻击目标类是什么。防御者只能拿到一个可能已经被污染的训练图然后训练防御模型。推理阶段还要面对一个可能也被污染的新图。2.1.8 图后门防御目标作者把防御目标写成$$\min_f \sum_{v_i\in V_C} l(f(v_i),y_i) \sum_{v_j\in V_B} l(f(v_j),y_j)$$第一项表示干净节点要分类正确$$\sum_{v_i\in V_C} l(f(v_i),y_i)$$第二项表示后门节点也应该恢复到正确状态$$\sum_{v_j\in V_B} l(f(v_j),y_j)$$这和很多旧防御不同。旧防御往往只要求$$g(v_t)\neq y_t$$也就是被攻击节点不要再预测成攻击目标类。但 SimGuard 要求更高$$g(v_t)y_o$$其中 $y_o$ 表示攻击前的原始预测结果或者原本应该属于的语义类别。核心思想不预测成目标类不代表恢复到了正确类别。2.1.9 Proposition 2.1Proposition 2.1 想表达鲁棒训练方法可以让目标节点不再预测成攻击目标类但不能保证它恢复到原始类别。鲁棒训练目标大致为$$\min_f L_f \sum_{v_i\in V_D} \log f(v_i)_{y_t} \sum_{v_j\in V_T\setminus V_D} L(f(v_j),y_j)$$其中$V_D$检测出的疑似 trigger 或后门相关节点$y_t$攻击目标类别$g(v_i)$节点 $v_i$ 的预测类别。鲁棒训练最多能做到$$g(v_t)\neq y_t$$但不能保证$$g(v_t)y_o$$原因是防御者不知道这个节点攻击前到底应该是什么类别。所以它可以把节点从目标类拉走但不知道该把它拉回哪里。2.2 Contrastive Learning Preliminaries对比学习的核心思想是相似样本拉近不相似样本推远。正样本对$$(z_i,z_j)$$负样本对$$(z_i,z_k)$$InfoNCE 损失为$$L_{\text{contrastive}} -\frac{1}{N} \sum_{i1}^{N} \log \frac{ e^{\operatorname{sim}(z_i,z_j)/\tau} }{ \sum_{k1}^{N} e^{\operatorname{sim}(z_i,z_k)/\tau} }$$其中$$e^{\operatorname{sim}(z_i,z_j)/\tau}$$表示正样本对的相似度项。如果正样本越相似$$\operatorname{sim}(z_i,z_j) \uparrow$$则分子越大loss 越小。分母为$$\sum_{k1}^{N} e^{\operatorname{sim}(z_i,z_k)/\tau}$$它包含很多样本包括负样本。如果 $z_i$ 和负样本也很像分母就会变大loss 也会变大。所以模型为了让 loss 变小会学到$$\operatorname{sim}(z_i,z_j) \uparrow$$同时$$\operatorname{sim}(z_i,z_k) \downarrow$$3. Over-Similarity Phenomenon第三章的核心问题是现有图后门攻击生成的 trigger 到底是不是真的 sample-specific还是说它们其实有共同模式可以被检测出来作者的结论是它们并不够 sample-specific反而具有明显的 over-similarity。3.1 Over-Similarity in Features3.1.1 Trigger-Bridge Node作者没有直接分析整个 trigger 子图而是先定义了一个更关键的节点Trigger-Bridge Nodes简称 TBN。它指的是直接连接到目标节点的 trigger node。原因是在 GNN 里信息通过 message passing 传播。真正把 trigger 影响传给目标节点的就是这些和目标节点直接相连的 trigger node。攻击链路可以理解为trigger node → target node → GNN message passing → target prediction 被劫持3.1.2 特征相似度计算作者计算 TBN 之间的 pairwise cosine similarity$$C_k \frac{1}{n-1} \sum_{j1, j\neq i}^{n} \frac{v_i \cdot v_j}{\|v_i\|\|v_j\|}$$其中$v_i, v_j$两个 trigger node 的特征向量$n$trigger-bridge nodes 的总数$C_k$某个 trigger node 和其他 trigger nodes 的平均相似度。如果 $C_k$ 很高说明 trigger nodes 彼此非常相似。3.1.3 主要观察作者在 GTA、UGBA、DPGBA 上进行分析发现trigger 之间的相似度明显高于 clean nodes 之间的相似度GTA 和 DPGBA 中trigger 几乎 collapse 到同一种特征上UGBA 没有完全 feature collapse但仍存在全局异常相似。可以概括为GTA / DPGBAtrigger 特征几乎坍缩 UGBA没有完全坍缩但仍存在全局异常相似SimGuard 的逻辑链为trigger features over-similar → trigger 在特征空间形成异常高密度区域 → 可以用相似性 / 密度聚类 / 异常分数检测 trigger3.2 Over-Similarity in Structure3.2 关注 trigger 的结构相似性尤其是 trigger 的 degree 分布。作者计算每个 trigger 的度数然后统计均值和方差$$\text{Mean}$$$$\text{Var}$$如果所有 trigger node 的 degree 都一样那么$$\text{Var}0$$这说明 trigger 在结构上高度一致。Table 1 的主要结果GTA: Cora: Mean 1.0, Var 0.0 CiteSeer: Mean 1.0, Var 0.0 PubMed: Mean 1.0, Var 0.0 ​ DPGBA: Cora: Mean 3.0, Var 0.0 CiteSeer: Mean 3.0, Var 0.0 PubMed: Mean 3.0, Var 0.0 ​ UGBA: Cora: Mean 2.7, Var 0.45 CiteSeer: Mean 3.0, Var 0.0 PubMed: Mean 1.0, Var 0.0结论现有 graph backdoor attacks 不仅在特征上过相似在结构上也过相似。4. Defense MethodSimGuard 的基本策略是在消息传播前识别 trigger ↓ 删除 trigger ↓ 训练 trigger detector ↓ 推理阶段遇到新图也能检测并删除 trigger4.1 Identify Triggers检测要在 message passing 之前做。原因是一旦开始 GNN 聚合trigger 特征会和目标节点、邻居节点特征混在一起。4.1.1 DBSCAN 聚类$$C \operatorname{DBSCAN}(F,\epsilon,\operatorname{minPts})$$其中$F$节点原始特征$\epsilon$DBSCAN 的邻域半径$\operatorname{minPts}$形成一个簇所需要的最小点数。DBSCAN 得到多个簇$$C\{C_1,C_2,\dots,C_K\}$$4.1.2 结构方差辅助判断对每个 cluster 计算节点度数均值和方差$$\mu(C_i)\frac{1}{|C_i|}\sum_{u\in C_i}d(u)$$$$\sigma^2(C_i)\frac{1}{|C_i|}\sum_{u\in C_i}(d(u)-\mu(C_i))^2$$如果一个簇里所有节点度数几乎一样$$\sigma^2(C_i) \approx 0$$则这个簇可能是 trigger cluster$$\{C_i \mid \sigma^2(C_i)\delta\}$$其中 $\delta$ 是一个很小的阈值例如$$\delta0.001$$4.1.3 Global Anomaly ScoreUGBA 没有完全 feature collapse因此作者设计了 global anomaly score$$G(x) \frac{1}{m} \sum_{i1}^{m} \frac{\|x-y_i\|_1}{\|x\|_1\|y_i\|_1}$$其中$x$待检测节点$y_i$选出来的 clean nodes$m$clean nodes 的数量$G(x)$节点 $x$ 的 global anomaly score。然后将所有节点的 $G(x)$ 从大到小排序得到$$G_{\operatorname{sorted}}$$找排序后相邻分数差距最大的地方$$k\arg\max_j \left( G_{\operatorname{sorted}}(j) - G_{\operatorname{sorted}}(j1) \right)$$最后取前面异常分数最高的一批节点作为 trigger$$S\{\pi(i)\mid 0\leq i\leq k\}$$其中 $\pi(i)$ 表示排序后索引映射回原始节点索引。这个过程可以理解为异常分数排序 ↓ 找最大断崖 ↓ 断崖之前的节点认为是 trigger4.2 Training a Trigger Detector Based on Contrastive Learning4.1 是训练阶段检测 trigger但推理阶段会遇到新的 unseen graph$$G_U$$所以 SimGuard 需要训练一个 trigger detector使其能泛化到新图。4.2.1 Proposition 4.1如果 trigger generation 足够强攻击者总能通过加边或加 trigger让目标节点预测成攻击目标类$$f_u(G)y_t$$这说明推理阶段也必须防御不能只清理训练图。4.2.1 Subset of Normal Nodes训练 trigger detector 需要两类样本trigger nodes clean nodestrigger nodes 可以通过 4.1 的检测方法找出来。clean nodes 则通过 autoencoder 的重构误差选出。Autoencoder 重构损失为$$L_{\operatorname{recon}}(v_i) \left\| X_i - f_{\operatorname{decoder}} \left( f_{\operatorname{encoder}}(X_i) \right) \right\|_1$$选择高置信 clean nodes$$O\{v_i\mid L_{\operatorname{recon}}(v_i)\delta\}$$4.2.2 Train a Trigger Detection作者使用对比学习训练 trigger detector。目标是clean nodes 彼此靠近 trigger nodes 彼此靠近 clean nodes 和 trigger nodes 彼此远离每轮训练采样 $m$ 个 clean nodes其中 $m$ 等于检测出来的 trigger 数量。clean-clean 相似项$$u_i \frac{1}{m-1} \sum_{j1,j\neq i}^{m} e^{z_i^\cdot z_j^/\tau}$$trigger-trigger 相似项$$v_i \frac{1}{m-1} \sum_{j1,j\neq i}^{m} e^{z_i^-\cdot z_j^-/\tau}$$clean-trigger 相似项$$q_i \frac{1}{m} \sum_{j1}^{m} e^{z_i^\cdot z_j^-/\tau}$$其中$z_i^$clean node 的归一化表示$z_i^-$trigger node 的归一化表示$\tau$temperature parameter。整体 contrastive loss 为$$L -\frac{1}{m} \left( \sum_{i1}^{m} \log\frac{u_i}{q_i} \sum_{i1}^{m} \log\frac{v_i}{q_i} \right)$$最终效果clean nodes 聚成一类 trigger nodes 聚成一类 两类之间拉开距离