基于图卷积网络的社交网络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.