基于圖卷積網絡的社交網絡Spammer檢測技術

曲強，于洪濤，黃瑞陽

（國家數字交換系統工程技術研究中心，河南 鄭州 450002）

1 引言

隨著移動互聯網技術的廣泛應用，在線社交網絡由于具有便捷、靈活、內涵豐富的特性而快速成為人們生活重要的組成部分，如Facebook、Twitter、Google、新浪微博、微信等流行社交網絡。目前，在線社交網絡的用戶數量呈指數級別增長，據統計，2018年春節期間微信和 WeChat的合并月活躍賬戶數超過10億[1]。由于社交網絡蘊含的巨大用戶隱私信息及其廣闊的商業價值，社交網絡成為不法分子圖謀不軌的目標，其中，異常用戶是不法分子攻擊社交網絡的主要手段之一，異常用戶的類型由于社交網絡類型不同也呈現出多種形態，如表1所示。Spammer作為一類重要異常用戶，它是指未經接收者允許，大量地發送對接受者無關的廣告信息的用戶。根據 2013年的社交網絡垃圾信息統計報告[2]，2013年 1月～6月，社交垃圾信息數量增長了355%，每200條社交信息中有1條是垃圾信息，它們對5%的社交應用App造成了一定程度的威脅。通過收集用戶的個人信息，Spammer向用戶發送特定的垃圾信息以達到誘導用戶進入惡意網站或者購買劣質產品的目的[3～5]，進而對社交網絡的可用性以及安全性造成影響。

表1 在線社交網絡的異常用戶種類

針對社交網絡 Spammer的廣泛存在與潛在危害特性，國內網學者對社交網絡Spammer的檢測進行了大量的研究，研究人員主要采用監督算法、無監督算法以及圖算法來檢測社交網絡Spammer。Benevenuto等[6]利用支持向量機檢測Twitter中的Spammer，通過向支持向量機中引入參數J給出Spammer占比的先驗分布，調節J來平衡準確率或者召回率的提升，并且通過gain與卡方檢驗選出幾種比較具有區分性的特征。Gao等[7]根據文本的MD5相似性以及URL指向目標的相同性聚類構建相似的群組，再通過Spammer的分布覆蓋以及時間爆發判定每個群組是否為Spammer群組。Hu等[8,9]將內容矩陣和構造的隨機游走網絡矩陣結合，利用譜分解方式求解最佳權重，識別 Twitter中 Spammer。后來，Hu[10]又將情感信息矩陣融入內容矩陣和鄰接矩陣中，優化目標函數求得最佳權重。上述3種方法各有利弊：監督算法需要具有區分度的特征指標，無監督算法需要合理的相似性指標，這2種指標是研究人員根據經驗設定的指標，屬于可認知的淺層特征，Spammer利用根據淺層特征容易逃過檢測，但方法的效率很高。盡管圖算法能夠獲取深層特征，但是由于圖數據量級太大和稀疏性導致計算復雜度過高，效率低。

針對上述監督算法與無監督算法提取的淺層特征和圖算法的計算復雜度過高問題，本文提出了基于GCN的Spammer檢測技術，主要內容如下。

1) 本文基于網絡結構信息，通過引入網絡表示學習算法提取網絡局部結構特征，結合重正則化技術條件下的 GCN算法[11]獲取網絡全局結構特征，提出基于GCN的Spammer檢測技術，有效利用了網絡結構的局部特征與全局特征，淺層特征與深層特征。

2) 本文從直交多項式的角度推導出重正則化技術條件下的 GCN算法，有效降低了圖算法的高計算復雜度。

3) 本文基于 Tagged社交網絡數據進行了大量實驗，實驗表明，該方法具有通用性、高準確與高效率等特點。

2 相關工作

2.1 網絡表示學習

網絡表示學習是指從網絡數據中學習到每個節點的向量表示，并將向量表示作為節點的特征應用于后續的網絡應用任務[12,13]。一般的網絡表示學習算法可以分成兩類：基于網絡結構的網絡表示學習；帶有信息的網絡結構的網絡表示學習。由于文中數據未包含節點標簽屬性信息，因此此處僅對基于網絡結構的網絡表示學習進行闡述。

在基于網絡結構的網絡表示學習算法中，DeepWalk[14]、Node2vec[15]、Struc2vec[16]以及LINE[17]是該領域主流的網絡表示學習算法，它們在鏈路預測、引文文本分類等領域廣泛應用。但是，上述網絡表示學習算法僅考慮局部游走，即網絡局部結構信息。

2.2 圖卷積網絡

2010年以來，神經網絡由于具有從大規模數據中提取高維深度特征的性質，受到學術界以及工業界的青睞，尤其是提取以圖像視頻為代表的低維規則網格的深度特征，進一步識別圖像、視頻或文檔的種類等[18,19]，隨后研究人員又提出循環神經網絡[20]、帶門控機制的神經網絡[21]等。然而，這些神經網絡無法適用高維不規則網格，如社交網絡、腦部連接網絡、計算機網絡等。因此，Kipf等[11]利用信號處理技術中小波變換[22]以及數值計算中的多項式逼近理論[23]，提出了圖卷積網絡，用于圖像檢測[24]以及引文網絡節點分類[11]。但是，GCN網絡算法需要大量特征字段，在現實情況下很難滿足。

下面簡要介紹經過卷積變換與多項式逼近后的GCN算法表達形式以及目標函數形式，如式(1)和式(2)所示。

其中，x表示節點的特征向量。L為圖G的經過標準化的 Laplacian矩陣：L=IN-gθ為頻譜卷積變換的操作符，其中，θ ∈ RN表示傅里葉變換系數。θk∈RK表示多項式的權重系數。 Tk(?)表示k階極小化極大多項式，K表示逼近多項式局部階數。z表示經GCN算法預測的樣本標簽。

其中，Lγ表示擁有標簽的樣本集合，F表示類別數目，Y表示樣本實際標簽集合，Z表示經GCN算法預測的樣本標簽集合，其中，l表示樣本的標號，f表示類別的標號。

3 基于圖卷積網絡的Spammer檢測技術

基于GCN的社交網絡Spammer檢測技術的流程如圖1所示，其中，矩形表示不同結構的數據，帶箭頭的矩形表示不同處理方式，虛線表示不同處理模塊。根據圖1，基于GCN的社交網絡Spammer檢測技術分為3個模塊：數據處理模塊、特征學習模塊、Spammer檢測模塊。數據處理模塊將在4.1節進行介紹。本節主要介紹后面2個模塊，其中，3.1節介紹特征學習模塊，即不同的網絡表示學習算法；3.2節介紹Spammer檢測模塊，即重正則化技術條件下的GCN算法。

3.1 網絡表示學習

面對僅含網絡結構的社交數據，本文方法利用網絡表示學習提取局部網絡結構信息的特征向量，主要使用了下面3種網絡表示學習算法。

圖1 基于GCN的社交網絡Spammer檢測技術流程

1) DeepWalk[14]：第一次將深度學習中的技術引入網絡表示學習領域，該方法利用網絡結構中隨機游走序列的信息獲取節點的特征表示向量。該方法只考慮了網絡局部結構的同質性。

2) Node2vec[15]：通過改變隨機游走序列生成的方式進一步擴展DeepWalk 算法，DeepWalk選取隨機游走序列中下一個節點的方式是均勻隨機分布的，而Node2vec通過引入2個參數p和q，將寬度優先搜索和深度優先搜索引入隨機游走序列的生成過程。該方法只考慮了網絡局部結構的同質性與同構性。

3) Struc2vec[16]：通過嚴格定義節點的結構同構性，Struc2vec利用M層結構同質性的圖重構節點相似性的多層混合圖，然后利用隨機游走與語言模型獲取節點的特征向量表示。該方法只考慮了網絡全局結構的同構性。

3.2 重正則化技術條件下的GCN

在使用重正則化技術的條件下，研究人員[11]發現使用Chebyshev-I多項式的GCN算法具有較高的正確率與較小的時間消耗，優于高階多項式的實驗效果。由于 Chebyshev-I多項式是典型的直交多項式，因此本文試圖從直交多項式角度推導出使用重正則化技術條件下的GCN，并利用該形式GCN開展社交網絡的Spammer檢測工作。

根據算法 1，需要選取極小化極大多項式，并且這種多項式是存在且唯一。然而，根據文獻[23]以及Lagrange多項式插值逼近原理，極小化極大多項式可以用以 Chebyshev-I多項式為代表的直交多項式進行逼近，其誤差與使用極小化極大多項式進行估計幾乎一致，但是降低了由構造極小化極大多項式所帶來的計算復雜度。本文給出直交多項式的定義以及構造方法。

定義1 設 pj(x)是j次實系數多項式，若多項式系中任意2個多項式在區間[a, b]上關于權函數W( x)都直交，即滿足條件

則稱為區間[a, b]關于權函數W( x)的直交多項式，并稱為區間[a, b]關于權函數的n次直交多項式。

定理1 對給定的權函數W( x)，在區間[a, b]上關于權函數W( x)的k次首一直交多項式 pk(x)（k為任意的一個自然數或0）存在，唯一，且滿足遞推關系式

由于典型直交多項式的逼近性質好于其他多項式，因此本文選取5種典型的直交多項式逼近頻譜卷積操作符，表達形式如表2所示，從直交多項式的角度推導重正則化技術條件下的 GCN算法。

表2 典型直交多項式

本文選取 5種直交多項式中最復雜的Languerre多項式來推導重正則化技術條件下的GCN算法，推導如下。

同理，其余幾種直交多項式可以得到同樣的表達形式，因此，在重正則化技術的條件下，單層 GCN表達形式為，其中，。本文最終使用兩層GCN 網絡結構，即其中，，F是類別數目。

4 實驗

4.1 實驗設置

1) 數據處理

本文使用的數據來自Tagged.com社交平臺，Tagged社交平臺使用不同的方法檢測Spammer。例如，它利用傳統的內容和注冊信息建立過濾器檢測Spammer；同時，Tagged采用舉報系統與管理安全系統檢測 Spammer。因此，本文 Tagged數據集是已經通過 Tagged.com傳統過濾器檢測的數據集，數據集中包含的Spammer需要安全團隊的人工檢驗。

Tagged數據集包含 2個數據文件：userdata.csv和relations.csv。用戶數據集包含5 607 447用戶信息，分為5個字段：userID、sex、timePassedValidations、ageGroup和label。關系數據集包含858 247 099條網絡鏈接信息，分為5個字段：day、time_ms、src、dst和 relation，字段具體含義如表3所示。

本文方法使用用戶數據集的userID與label；通過在時間序列上的采樣，本文方法使用第三天23～24 h的關系數據集的src與dst，數據處理流程如圖2的數據處理模塊所示。

2) 實驗環境

在數據處理模塊，使用的實驗環境是Ubuntu14.04的系統， 32個CPU處理器以及125.8 GB內存，編程語言為Python2.7；而在特征提取模塊與 Spammer檢測模塊，使用的實驗環境為Ubuntu16.04系統，8個CPU處理器以及23.5 GB內存，編程語言為Python3.6。

4.2 實驗結果

實驗中提取不同種類的網絡結構特征向量的網絡表示學習算法的默認設置為：特征向量維度64，隨機游走數量10，隨機游走長度40，skip-gram的序列窗口大小5，工作CPU核數4。Node2vec的隨機游走概率參數 p=1，q=2。在方法訓練過程中，訓練集與測試集比例為7：3，GCN方法訓練200輪。如果沒有特殊說明，方法默認設置不變。實驗中特征學習模塊采用3種網絡表示學習算法（DeepWalk、Node2vec、Struc2vec），Spammer檢測模塊選取了 3種典型的監督算法（感知機、邏輯回歸、隨機森林）和文中提出的重正則化技術條件下的GCN（簡記為GCN）。

實驗1 不同算法對社交網絡Spammer檢測方法準確率的影響

表3 Tagged數據集

表4展示了不同的社交網絡Spammer檢測方法的準確率。首先，在特征學習模塊中，采用不同網絡表示學習算法的Spammer檢測方法準確率相對于基準正確率一般為 DeepWalk＞ Node2vec＞Struc2vec，這也證明了網絡局部結構的同質性對Spammer檢測的貢獻程度大于網絡局部結構同構性與網絡全局結構的同構性。

其次，在Spammer檢測模塊中，3種監督算法中邏輯回歸算法的準確率大于感知機和隨機森林，但是邏輯回歸算法的準確率低于 GCN算法（DeepWalk+邏輯回歸

表4 社交網絡Spammer檢測方法準確率

實驗 2 特征向量維度對社交網絡 Spammer檢測方法準確率的影響

圖 2展示了特征向量維度對 4種社交網絡Spammer檢測方法準確率的影響，其中，橫軸表示特征向量維度，縱軸表示準確率。根據圖3，隨著特征向量維度的增長，DeepWalk與Node2vec方法準確率在特征向量維度為16時達到最大，隨后下降；而 DeepWalk+GCN與Node2vec+GCN方法準確率在特征向量維度為64時達到最大，隨后下降。整體上，當特征向量維度大于32時，DeepWalk+GCN方法準確率最高，其次為 Node2vec+GCN方法，好于DeepWalk與Node2vec方法的準確率。

圖2 特征向量維度對社交網絡Spammer檢測方法準確率的影響

實驗 3 訓練集特征向量所占百分比對社交網絡Spammer檢測方法效率的影響

圖3展示了訓練集特征向量占總數據集的特征向量的百分比對于4種社交網絡Spammer檢測方法準確率的影響，其中，橫軸表示訓練集特征向量所占百分比（或者說含有標簽的數據占總數據集的百分比），縱軸表示準確率。根據圖4，隨著總數據集中含標簽樣本百分比的增長，DeepWalk+GCN與Node2vec+GCN方法準確率不斷增長，而DeepWalk與Node2vec方法準確率相對穩定。總體上，當含標簽樣本百分比大于50%時，DeepWalk+GCN方法準確率最高，其次為Nodezvec+GCN方法，好于DeepWalk與Node2vec方法準確率。即使在含標簽樣本百分比為10%時，DeepWalk+GCN方法準確率好于任何含標簽樣本百分比下的DeepWalk與Node2vec方法，因此該方法可以通過訓練較少的樣本形成模型，實現大規模數據集Spammer檢測的目的。

實驗4 數據規模對于社交網絡Spammer檢測方法效率的影響

圖 4展示了數據規模對于社交網絡Spammer檢測方法效率的影響，橫軸表示網絡邊的數據量，縱軸表示 200輪訓練所需時間。根據圖4，隨著邊的數量規模增長，DeepWalk+GCN與Node2vec+GCN方法時間不斷增長，呈現亞線性的關系。即使在100 000條邊的情況下，本文方法需要大約5 min，遠遠低于普通的圖算法，檢測效率大大提升，適用于大規模數據Spammer檢測。

圖3 訓練集特征向量所占百分比對社交網絡Spammer檢測方法準確率的影響

圖4 數據規模對社交網絡Spammer檢測方法效率的影響

5 結束語

針對現有社交網絡 Spammer檢測方法提取淺層特征與計算復雜度高的問題，本文提出了一種基于圖卷積網絡的社交網絡 Spammer檢測技術。該方法基于網絡結構信息，通過引入網絡表示學習算法提取網絡局部結構特征，結合重正則化技術條件下的 GCN算法獲取網絡全局結構特征去檢測Spammer。本文在Tagged.com社交網絡數據上進行實驗，發現本文方法的具有高準確與高效率，并且對于網絡圖數據結構具有普遍的適用性。

參考文獻：

[1]MA HUATENG. Normal and reasonable competition is good for business[C]//World Fortune Forum. 2017.

[2]HAROLD NGUYEN. 2013 state of social media spam. Technical report[R]. 2013

[3]STRINGHINI G, KRUEGEL C, VIGNA G. Detecting Spammers on social networks[C]//The 26th Annual Computer Security Applications Conference. 2010： 1-9.

[4]RAYANA S, AKOGLU L. Collective opinion spam detection：bridging review networks and metadata[C]//The 21th ACM Sigkdd International Conference On Knowledge Discovery And Data Mining. 2015： 985-994.

[5]LIM E P, NGUYEN V A, JINDAL N, et al. Detecting product review Spammers using rating behaviors[C]//The 19th ACM International Conference On Information and Knowledge Management.2010： 939-948.

[6]BENEVENUTO F, MAGNO G, RODRIGUES T, et al. Detecting Spammers on twitter[C]//Collaboration, Electronic Messaging, Anti-Abuse And Spam Conference (CEAS 2010). 2010： 12.

[7]GAO H, HU J, WILSON C, et al. Detecting and characterizing social spam campaigns[C]//The 10th ACM SIGCOMM Conference on Internet Measurement. 2010： 35-47.

[8]HU X, TANG J, ZHANG Y, et al. Social Spammer detection in microblogging[C]//(IJCAI 2013). 2013： 2633-2639.

[9]HU X, TANG J, LIU H. Online social Spammer detection[C]//AAAI. 2014： 59-65.

[10]HU X, TANG J, GAO H, et al. Social Spammer detection with sentiment information[C]//2014 IEEE International Conference on Data Mining (ICDM). 2014： 180-189.

[11]KIPF T N, WELLING M. Semi-supervised classification with graph convolutional networks[C]// ICLR. 2017.

[12]涂存超, 楊成, 劉知遠, 等. 網絡表示學習綜述[J]. 科學通報,1998, 43： 1681.TU C C, YANG C, LIU Z Y, et al. Network representation learning：an overview [J]. Chinese Science Bulletin, 1998, 43： 1681.

[13]CUI P, WANG X, PEI J, et al. A survey on network embedding[J].Social and Information Networks(Cornell University Library),2017.

[14]PEROZZI B, AL-RFOU R, SKIENA S. DeepWalk： online learning of social representations[C]//The 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM,2014： 701-710.

[15]GROVER A, LESKOVEC J. Node2vec： scalable feature learning for networks[C]//The 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 2016：855-864.

[16]RIBEIRO L F R, SAVERESE P H P, FIGUEIREDO D R.Struc2vec： learning node representations from structural identity[C]//The 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 2017： 385-394.

[17]TANG J, QU M, WANG M, ET AL. Line： large-scale information network embedding[C]//The 24th International Conference on World Wide Web. 2015： 1067-1077.

[18]HENAFF M, BRUNA J, LECUN Y. Deep convolutional networks on graph-structured data[J]. Computer Science, 2015.

[19]HE K, ZHANG X, REN S, ET Al. Deep residual learning for image recognition[C]//IEEE Conference on Computer Vision and Pattern Recognition. 2016： 770-778.

[20]JAIN A, ZAMIR A R, SAVARESE S, et al. Structural-RNN： deep learning on spatio-temporal graphs[C]//IEEE Conference on Computer Vision and Pattern Recognition. 2016： 5308-5317.

[21]LI Y, TARLOW D, BROCKSCHMIDT M, ET AL. Gated graph sequence neural networks[J]. Computer Science, 2015.

[22]SHUMAN D I, NARANG S K, FROSSARD P, et al. The emerging field of signal processing on graphs： extending high-dimensional data analysis to networks and other irregular domains[J]. IEEE Signal Processing Magazine, 2013, 30(3)： 83-98.

[23]HAMMOND D K, VANDERGHEYNST P, GRIBONVAL R.Wavelets on graphs via spectral graph theory[J]. Applied and Computational Harmonic Analysis, 2011, 30(2)： 129-150.

[24]DEFFERRARD M, BRESSON X, VANDERGHEYNST P. Convolutional neural networks on graphs with fast localized spectral filtering[C]//Advances in Neural Information Processing Systems.2016： 3844-3852.

[25]CHUNG F R K. Spectral graph theory[C]// CBMS Regional Conference Series in Mathematics. 1996.