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

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

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

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

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

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

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

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

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

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

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

實(shí)驗(yàn)：實(shí)驗(yàn)證明該研究提出的模型僅對(duì)圖進(jìn)行稍微改動(dòng)，即可惡化目標(biāo)節(jié)點(diǎn)的分類結(jié)果。研究者進(jìn)一步證明這些結(jié)果可遷移至其他模型、不同數(shù)據(jù)集，甚至在僅可以觀察到部分?jǐn)?shù)據(jù)時(shí)仍然有效。整體而言，這強(qiáng)調(diào)了應(yīng)對(duì)圖數(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ù)上實(shí)現(xiàn)了強(qiáng)大的性能。盡管此類模型數(shù)量激增，但目前仍未有研究涉及它們?cè)趯?duì)抗攻擊下的魯棒性。而在它們可能被應(yīng)用的領(lǐng)域（例如網(wǎng)頁），對(duì)抗攻擊是很常見的。圖深度學(xué)習(xí)模型會(huì)輕易地被欺騙嗎？在這篇論文中，我們介紹了首個(gè)在屬性圖上的對(duì)抗攻擊研究，具體而言，我們聚焦于圖卷積模型。除了測(cè)試時(shí)的攻擊以外，我們還解決了更具挑戰(zhàn)性的投毒/誘發(fā)型（poisoning/causative）攻擊，其中我們聚焦于機(jī)器學(xué)習(xí)模型的訓(xùn)練階段。

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

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

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

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

表 2：Cora 上每個(gè)類別中的特征擾動(dòng) top-10。

圖 6a 評(píng)估了兩個(gè)攻擊類型的 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] 也受到我們的擾動(dòng)的極大影響（圖 6d）。

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

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

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

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

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