8 月 19 日至 23 日，數據挖掘頂會 KDD 2018 在英國倫敦舉行，昨日大會公布了最佳論文等獎項。最佳論文來自慕尼黑工業大學的研究者，他們提出了針對圖深度學習模型的對抗攻擊方法，是首個在屬性圖上的對抗攻擊研究。研究者還提出了一種利用增量計算的高效算法 Nettack。此外，實驗證明該攻擊方法是可以遷移的。

圖數據是很多高影響力應用的核心，比如社交和評級網絡分析（Facebook、Amazon）、基因相互作用網絡（BioGRID），以及互連文檔集合（PubMed、Arxiv）。基于圖數據的一個最常應用任務是節點分類：給出一個大的（屬性）圖和一些節點的類別標簽，來預測其余節點的類別標簽。例如，你可能想對生物相互作用圖（biological interaction graph）中的蛋白質進行分類、預測電子商務網絡中用戶的類型 [13]，或者把引文網絡中的科研論文按主題分類 [20]。

盡管過去已經出現很多解決節點分類問題的經典方法 [8, 22]，但是近年來人們對基于圖的深度學習方法產生了極大興趣 [5, 7, 26]。具體來說，圖卷積網絡 [20, 29] 方法在很多圖學習任務（包括節點分類）上達到了優秀性能。

這些方法的能力超出了其非線性、層級本質，依賴于利用圖關系信息來執行分類任務：它們不僅僅獨立地考慮實例（節點及其特征），還利用實例之間的關系（邊緣）。換言之，實例不是被分別處理的，這些方法處理的是某種形式的非獨立同分布（i.i.d.）數據，在處理過程中利用所謂的網絡效應（如同質性（homophily）[22]）來支持分類。

但是，這些方法存在一個大問題：人們都知道用于分類學習任務的深度學習架構很容易被欺騙／攻擊 [15, 31]。即使是添加輕微擾動因素的實例（即對抗擾動／樣本）也可能導致結果不直觀、不可信，也給想要利用這些缺陷的攻擊者開了方便之門。目前基于圖的深度學習方法的對抗擾動問題并未得到解決。這非常重要，尤其是對于使用基于圖的學習的領域（如 web），對抗非常常見，虛假數據很容易侵入：比如垃圾郵件制造者向社交網絡添加錯誤的信息；犯罪分子頻繁操控在線評論和產品網站 [19]。

該論文試圖解決這一問題，作者研究了此類操控是否可能。用于屬性圖的深度學習模型真的很容易被欺騙嗎？其結果可信程度如何？

答案難以預料：一方面，關系效應（relational effect）可能改善魯棒性，因為預測并未基于單獨的實例，而是聯合地基于不同的實例。另一方面，信息傳播可能帶來級聯效應（cascading effect），即操縱一個實例會影響到其他實例。與現有的對抗攻擊研究相比，本論文在很多方面都大不相同。

圖 1：對圖結構和節點特征的極小擾動導致目標誤分類。

該論文提出一個對屬性圖進行對抗擾動的原則，旨在欺騙當前最優的圖深度學習模型。具體來說，該研究主要針對基于圖卷積網絡（如 GCN [20] 和 Column Network（CLN）[29]）的半監督分類模型，但提出的方法也有可能適用于無監督模型 DeepWalk [28]。研究者默認假設攻擊者具備全部數據的知識，但只能操縱其中的一部分。該假設確保最糟糕情況下的可靠脆弱性分析。但是，即使僅了解部分數據，實驗證明本研究中的攻擊仍然有效。該論文的貢獻如下：

模型：該研究針對節點分類提出一個基于屬性圖的對抗攻擊模型，引入了新的攻擊類型，可明確區分攻擊者和目標節點。這些攻擊可以操縱圖結構和節點特征，同時通過保持重要的數據特征（如度分布、特征共現）來確保改變不被發現。

算法：該研究開發了一種高效算法 Nettack，基于線性化思路計算這些攻擊。該方法實現了增量計算，并利用圖的稀疏性進行快速執行。

實驗：實驗證明該研究提出的模型僅對圖進行稍微改動，即可惡化目標節點的分類結果。研究者進一步證明這些結果可遷移至其他模型、不同數據集，甚至在僅可以觀察到部分數據時仍然有效。整體而言，這強調了應對圖數據攻擊的必要性。

論文：Adversarial Attacks on Neural Networks for Graph Data

論文鏈接：https://arxiv.org/pdf/1805.07984.pdf

摘要：應用到圖的深度學習模型已經在節點分類任務上實現了強大的性能。盡管此類模型數量激增，但目前仍未有研究涉及它們在對抗攻擊下的魯棒性。而在它們可能被應用的領域（例如網頁），對抗攻擊是很常見的。圖深度學習模型會輕易地被欺騙嗎？在這篇論文中，我們介紹了首個在屬性圖上的對抗攻擊研究，具體而言，我們聚焦于圖卷積模型。除了測試時的攻擊以外，我們還解決了更具挑戰性的投毒/誘發型（poisoning/causative）攻擊，其中我們聚焦于機器學習模型的訓練階段。

我們生成了針對節點特征和圖結構的對抗擾動，因此考慮了實例之間的依賴關系。此外，我們通過保留重要的數據特征來確保擾動不易被察覺。為了應對潛在的離散領域，我們提出了一種利用增量計算的高效算法 Nettack。我們的實驗研究表明即使僅添加了很少的擾動，節點分類的準確率也會顯著下降。另外，我們的攻擊方法是可遷移的：學習到的攻擊可以泛化到其它當前最佳的節點分類模型和無監督方法上，并且類似地，即使僅給定了關于圖的有限知識，該方法也能成功實現攻擊。

圖 2：隨著擾動數量的增長，平均代理損失（surrogate loss）的變化曲線。由我們模型的不同變體在 Cora 數據集上得到，數值越大越好。

圖 3 展示了在有或沒有我們的約束下，得到的圖的檢驗統計量 Λ。如圖可知，我們強加的約束會對攻擊產生影響；假如沒有強加約束，損壞的圖的冪律分布將變得和原始圖更加不相似。類似地，表 2 展示了特征擾動的結果。

圖 3（左）：檢驗統計量 Λ 的變化（度分布）。圖 4（右）梯度 vs. 實際損失。

表 2：Cora 上每個類別中的特征擾動 top-10。

圖 6a 評估了兩個攻擊類型的 Nettack 性能：逃逸攻擊（evasion attack），基于原始圖的模型參數（這里用的是 GCN [20]）保持不變；投毒攻擊（poisoning attack），模型在攻擊之后進行重新訓練（平均 10 次運行）。

圖 6b 和 6c 顯示，Nettack 產生的性能惡化效果可遷移至不同（半監督）圖卷積方法：GCN [20] and CLN [29]。最明顯的是，即使是無監督模型 DeepWalk [28] 也受到我們的擾動的極大影響（圖 6d）。

圖 6：使用不同攻擊算法在 Cora 數據上的結果。Clean 表示原始數據。分值越低表示結果越好。

圖 7 分析了攻擊僅具備有限知識時的結果：給出目標節點 v_0，我們僅為模型提供相比 Cora 圖其尺寸更大的圖的子圖。

圖 7：具備有限數據知識的攻擊。

表 3 總結了該方法在不同數據集和分類模型上的結果。這里，我們報告了被正確分類的部分目標節點。我們對代理模型（surrogate model）的對抗擾動可在我們評估的這些數據集上遷移至這三種模型。毫不奇怪，influencer 攻擊比直接攻擊導致的性能下降更加明顯。

表 3：結果一覽。數值越小表示結果越好。