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

圖數(shù)據(jù)是很多高影響力應(yīng)用的核心,，比如社交和評級網(wǎng)絡(luò)分析（Facebook、Amazon）,、基因相互作用網(wǎng)絡(luò)（BioGRID）,，以及互連文檔集合（PubMed、Arxiv）,?；趫D數(shù)據(jù)的一個最常應(yīng)用任務(wù)是節(jié)點(diǎn)分類：給出一個大的（屬性）圖和一些節(jié)點(diǎn)的類別標(biāo)簽，來預(yù)測其余節(jié)點(diǎn)的類別標(biāo)簽,。例如,，你可能想對生物相互作用圖（biological interaction graph）中的蛋白質(zhì)進(jìn)行分類、預(yù)測電子商務(wù)網(wǎng)絡(luò)中用戶的類型 [13],，或者把引文網(wǎng)絡(luò)中的科研論文按主題分類 [20],。

盡管過去已經(jīng)出現(xiàn)很多解決節(jié)點(diǎn)分類問題的經(jīng)典方法 [8, 22]，但是近年來人們對基于圖的深度學(xué)習(xí)方法產(chǎn)生了極大興趣 [5, 7, 26],。具體來說,，圖卷積網(wǎng)絡(luò) [20, 29] 方法在很多圖學(xué)習(xí)任務(wù)（包括節(jié)點(diǎn)分類）上達(dá)到了優(yōu)秀性能。

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

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

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

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

圖 1：對圖結(jié)構(gòu)和節(jié)點(diǎn)特征的極小擾動導(dǎo)致目標(biāo)誤分類,。

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

模型：該研究針對節(jié)點(diǎn)分類提出一個基于屬性圖的對抗攻擊模型,，引入了新的攻擊類型，可明確區(qū)分攻擊者和目標(biāo)節(jié)點(diǎn),。這些攻擊可以操縱圖結(jié)構(gòu)和節(jié)點(diǎn)特征,，同時通過保持重要的數(shù)據(jù)特征（如度分布、特征共現(xiàn)）來確保改變不被發(fā)現(xiàn),。

算法：該研究開發(fā)了一種高效算法 Nettack,，基于線性化思路計算這些攻擊。該方法實現(xiàn)了增量計算,，并利用圖的稀疏性進(jìn)行快速執(zhí)行,。

實驗：實驗證明該研究提出的模型僅對圖進(jìn)行稍微改動，即可惡化目標(biāo)節(jié)點(diǎn)的分類結(jié)果,。研究者進(jìn)一步證明這些結(jié)果可遷移至其他模型,、不同數(shù)據(jù)集，甚至在僅可以觀察到部分?jǐn)?shù)據(jù)時仍然有效,。整體而言,，這強(qiáng)調(diào)了應(yīng)對圖數(shù)據(jù)攻擊的必要性。

論文：Adversarial Attacks on Neural Networks for Graph Data

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

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

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

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

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

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

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

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

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

圖 6：使用不同攻擊算法在 Cora 數(shù)據(jù)上的結(jié)果,。Clean 表示原始數(shù)據(jù),。分值越低表示結(jié)果越好。

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

圖 7：具備有限數(shù)據(jù)知識的攻擊。

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

表 3：結(jié)果一覽。數(shù)值越小表示結(jié)果越好,。