基于子圖采樣的大規模圖對抗性攻擊方法

高昕 安冬冬 章曉峰

摘??要：?為提高對抗性攻擊在大規模圖上的攻擊效率，提出了基于子圖采樣的對抗樣本生成方法. 該方法通過引入PageRank、余弦相似度及K跳子圖等技術，提取與目標節點高度相關的子圖，在大規模圖上緩解了計算梯度效率較低的問題，在降低被攻擊模型準確性的同時提升了攻擊的隱蔽性. 實驗結果表明：?所提出的對抗性攻擊方法與基于梯度攻擊的GradArgmax算法相比，在Cora數據集上提升了30.7%的攻擊性能，且在Reddit大規模數據上能夠計算GradArgmax算法無法計算的攻擊擾動.

關鍵詞：?圖神經網絡；?對抗性攻擊；?子圖提取算法

中圖分類號：?TP 181 ???文獻標志碼：?A ???文章編號：?1000-5137（2024）02-0167-05

Subgraph sampling-based adversarial attack method for large-scale graphs

GAO Xin¹，?AN Dongdong^1?，?ZHANG Xiaofeng²

（1.College of Information，?Mechanical and Electrical Engineering，?Shanghai Normal University，Shanghai 201418，?China；?2.Shanghai Newtouch Software Co.，?Ltd.，?Shanghai 200120，?China）

Abstract：?A subgraph sampling-based adversarial example generation method was proposed to enhance the efficiency of adversarial attacks on large-scale graphs. PageRank，?cosine similarity，?and K-hop subgraphs were employed to extract subgraphs highly relevant to the target node in this method，?alleviating the issue of low gradient computation efficiency in large-scale graphs. The stealthiness of the attack was also increased while reducing the accuracy of the attacked model. Experimental results showed that attack performance was improved by 30.7% on the Cora dataset by this adversarial attack method compared to the GradArgmax algorithm，?and attack perturbations on large-scale like Reddit dataset could be computed which the GradArgmax algorithm could not achieve.

Key words：?graph neural network；?adversarial attack；?subgraph extraction algorithm

隨著圖神經網絡在商品推薦^［1-3］、信用評估^［4］等現實領域的廣泛應用，其安全性問題已經成為一個重要的關注點. 在這個背景下，對抗性攻擊作為一種攻擊手段，研究如何生成對抗性樣例，以評估和提高模型的安全性變得至關重要. 圖神經網絡強大的圖數據分析能力來源于其消息傳遞機制，這也為惡意攻擊者提供了機會.攻擊者可以通過構建微小的擾動至原圖，導致模型輸出錯誤的結果.

目前已有的研究中，DAI等^［5］提出GradArgmax方法，通過訓練代理模型提取梯度信息，生成對抗擾動疊加至原圖，從而實現攻擊效果；XU等^［6］提出了project gradient descent（PGD）結構攻擊，從一階優化的角度進行梯度攻擊；ZUGNER等^［7］提出Nettack方法，通過修改圖結構或特征，最大化代理模型的損失函數.但是隨著數據規模的不斷增長，由于大多數攻擊算法需要存儲不必要的圖信息，時間和內存成本上升較多，難以實現對更大規模的圖進行攻擊^［8］.

本文作者針對上述問題，提出了基于大規模圖節點分類的對抗性攻擊方法. 首先通過提取目標節點的K跳內節點，并利用PageRank、余弦相似度等方法提取其余高關聯節點采樣子圖，減少攻擊方法所存儲的不必要的圖信息；同時，利用線性圖卷積網絡（GCN）訓練代理模型，提高梯度計算效率. 實驗結果表明，該方法能夠在降低時間和空間成本的同時，有效施加攻擊，從而降低原模型的準確性.

1 ?模型定義和問題描述

定義待攻擊圖，其中，表示結構矩陣表示特征矩陣，每個節點擁有一個標簽.對于半監督節點分類任務，利用所有已有標簽節點信息，最小化模型損失函數以學習模型構建節點到標簽的映射：

， （1）

其中，為圖的節點集合；（·）為交叉熵損失函數；為分類器在節點上的預測分類；為實際節點分類.

對于攻擊者，通過在滿足攻擊約束的條件下，設計結構攻擊及特征攻擊疊加至原圖，得到攻擊后的圖，最大化分類錯誤

（2）

其中，.本研究以攻擊預算為約束條件，即攻擊者僅能修改特定次數的結構矩陣或特征矩陣.

2 ?算法實現

2.1 訓練代理模型

構建代理模型用于后續梯度計算. 多種圖神經網絡模型都可被用作代理模型，如GCN、圖注意力（GAT）網絡. 但是，傳統的GCN模型通常由于效率較低，難以用于對大規模圖神經網絡的訓練. 因此，使用線性神經網絡模型（SGC）作為代理模型. SGC使用線性變換，不使用ReLU函數作為激活函數，一個2層SGC可以被表示為

， （3）

其中，表示壓縮后的權重矩陣.通過訓練參數構建代理模型，用于后續的攻擊.

2.2 子圖提取

采用子圖提取技術來降低計算成本. 設計若干提取器，提取關聯性較高的節點，得到最終的子圖.對于子圖的計算，在減少計算規模的同時，減少了攻擊算法存儲的不必要的參數，以提升攻擊效率.

2.2.1 K跳子圖提取器

淺層鄰域對于圖神經網絡來說足以學習到有效的節點表示，通過提取一個K跳子圖來避免過度的計算量.K跳子圖定義如下：

（4）

其中，表示節點到節點的最短距離；表示K跳子圖的跳數；表示與節點距離小于的所有節點集合；表示與節點距離小于的所有節點的連邊集合，最終得到K跳子圖.

2.2.2 Personalized PageRank提取器

節點通常與之高度相關的節點相連，與相關性較低的節點的連接往往不隱蔽. 因此，為了增強隱蔽性，有必要將攻擊限制在高度相關的節點上. PageRank算法通常用于計算節點之間的重要性，通過使用改進的Personalized PageRank算法，計算特定節點到其余節點的相關性. Personalized PageRank 可被描述為：

（5）

其中，是重啟概率，控制隨機游走的每一步中選擇回到初始節點的概率為單位矩陣；為節點數量；為歸一化矩陣.

2.2.3 余弦相似度提取器

在多數場景中，若兩個節點的特征高度相似，則可被看作高度相關的節點，通過計算余弦相似度來表示兩個節點的相似性：

. （6）

2.2.4 目標節點相關分數

首先計算各個節點與目標節點的相關分數

， （7）

其中，，表示提取器類型c表示提取器的權重；表示節點在提取器下的分數，得到：

（8）

設置超參數作為子圖提取的閾值，若，?則將節點添加至子圖：

. （9）

將上述子圖與K跳子圖進行合并：

，（10）

2.3 梯度計算

通過提取子圖和訓練代理模型，可以計算梯度，選擇擾動進行攻擊. 計算目標節點在子圖上的損失函數梯度

（11）

其中，表示損失函數相對于鄰接矩陣的偏導數表示最終提取的子圖的梯度.

為了保證擾動的隱蔽性，需要避免攻擊效果作用于低相關性的節點，首先對相關分數進行歸一化，作為梯度的系數：

（12）

其中，表示各個節點與目標節點的相關分數.

最后，通過選擇最大梯度，遵照以下規則進行擾動：

（13）

3 ?實驗及結果分析

3.1 實驗設置

在4個開源數據集上評估方法的性能：Citeseer，Cora，Pubmed以及Reddit. 前三個數據集為文獻引用數據集，節點為文獻，連邊表示節點間存在引用；Reddit為社區論壇數據集，節點表示不同實體，如用戶、帖子等，連邊為用戶間的交互、帖子與用戶的關系等. 其中，Citeseer和Cora作為小規模數據集，用于評估方法的可行性；Pubmed和Reddit作為大規模數據集，用于評估方法在大規模數據集上的效率. 數據隨機選擇30%的節點作為訓練集，70%作為測試集.

使用常見的GCN^［9］，GAT^［10］，GraphSage^［11］作為實驗的目標模型，通過評估攻擊算法在目標模型上的攻擊前、攻擊后的準確率，驗證攻擊算法的有效性.

將方法與以下2種方法進行比對：

隨機攻擊（RA）：隨機地添加或刪除連邊；

GradArgmax：通過代理模型提取梯度信息，在所有已存在的邊中，刪除梯度最大的邊.

對于節點分類任務，在受到攻擊后，目標模型會降低分類的準確率. 因此，使用分類準確性來評估模型攻擊的有效性.

3.2 模型性能分析

表1為各對抗性攻擊算法作用于目標模型后，模型在小規模數據集上的分類準確率. 可以看出，在小規模數據集上，相較隨機攻擊算法和GradArgmax算法，本方法表現更好，說明通過子圖采樣后，算法能夠更有效地選擇攻擊對象，使目標模型更容易產生誤分類的情況. 圖1展示了各攻擊方法在Citeseer和Cora數據集上的攻擊有效性，可以發現本方法的攻擊有效性優于其余兩種攻擊方法.

表2為各對抗性攻擊算法作用于目標模型后，模型在大規模數據集上的分類準確率. 可以看出，本方法能有效地施加攻擊. 同時，在Reddit數據集上，本方法在實現攻擊的同時，能夠大幅降低目標模型的準確率.

4 ?結語

本文作者提出了大規模圖節點分類任務上的對抗性攻擊算法. 該算法在使用梯度攻擊的基礎上，引入了子圖采樣的方法，通過提取與目標節點高度相關的節點，在降低算法計算規模的同時，能夠更有效地施加擾動. 實驗表明，所提出的算法能夠對大規模圖進行高效的攻擊.

參考文獻：

［1］ YIN H Z，?SUN Y Z，?XU G D，?et al. Trustworthy recommendation and search：?introduction to the special issue part 1 ［J］. ACM Transactions on Information Systems，?2023，41（3）：51.

［2］ NIU X C，?LI B F，?LI C L，?et al. A dual heterogeneous graph attention network to improve long-tail performance for shop search in e-commerce ［C］// The 26th ACM SIGKDD Conference on Knowledge Discovery and Data Mining. Virtual Event：?ACM，?2020：3405-3415.

［3］ ZHAO K，?ZHENG Y K，?ZHUANG T，?et al. Joint learning of e-commerce search and recommendation with a unified graph neural network ［C］// The Fifteenth ACM International Conference on Web Search and Data Mining. Virtual Event：?ACM，?2022：1461-1469.

［4］ LIU Z Q，?CHEN C C，?YANG X X，?et al. Heterogeneous graph neural networks for malicious account detection ［C］// The 27th ACM International Conference on Information and Knowledge Management. Torino：?ACM，?2018：2077-2085.

［5］ DAI H J，?LI H，?TIAN T，?et al. Adversarial attack on graph structured data ［C］// Proceedings of the 35th International Conference on Machine Learning. Stockholm：?ACM，?2018：1123-1132.

［6］ XU K D，?CHEN H G，?LIU S J，?et al. Topology attack and defense for graph neural networks：?an optimization perspective ［C］// Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence. Macao：?ACM，?2019：3961-3967.

［7］ Z?GNER D，?AKBARNEJAD A，?G?NNEMANN S. Adversarial attacks on neural networks for graph data ［C］//Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence. Macao：?ACM，?2019：6246-6250.

［8］ LI J T，?XIE T，?CHEN L，?et al. Adversarial attack on large scale graph ［J］. IEEE Transactions Knowledge Data Engineering，?2023，35（1）：82-95.

［9］ KIPF T N，?WELLING M. Semi-supervised classification with graph convolutional networks ［J/OL］. arXiv，2016 ［2023-10-10］. https：// arxiv.org/abs/1609.02907.

［10］ VELICKOVIC P，?CUCURULL G，?CASANOVA A，?et al. Graph attention networks ［C］// 6th International Conference on Learning Representations.Vancouver：ICLR，?2018：1-12.

［11］ HAMILTON W L，?YING R，?LESKOVEC J. Inductive representation learning on large graphs ［C］// Proceedings of the 31st International Conference on Neural Information Processing Systems. Long Beach：?ACM，?2017：1025-1035.

（責任編輯：包震宇，顧浩然）

DOI：?10.3969/J.ISSN.1000-5137.2024.02.004

收稿日期：?2023-12-15

基金項目：?國家自然科學基金青年基金（62302308），上海市青年科技英才揚帆計劃（21YF1432900）

作者簡介：?高昕（1998—），?男，?碩士研究生，?主要從事對抗圖網絡方面的研究. E-mail：?1000513347@smail.shnu.edu.cn

* 通信作者：?安冬冬（1990—），?女，?講師，?主要從事形式化驗證方面的研究. E-mail：andongdong@shnu.edu.cn

引用格式：?高昕，?安冬冬，?章曉峰. 基于子圖采樣的大規模圖對抗性攻擊方法?［J］. 上海師范大學學報?（自然科學版中英文），?2024，53（2）：167?171.

Citation format：?GAO X，?AN D D，?ZHANG X F. Subgraph sampling-based adversarial attack method for large-scale graphs ［J］. Journal of Shanghai Normal University （Natural Sciences），?2024，53（2）：167?171.