Abstract—With millions of users, Wikipedia is now the largest collaborative encyclopedia in the world. However, there is a growing problem of vandalism edit. Several previous works have developed either hand-designed or automated techniques to detect those vandalism edits. In this paper, we proposed a novel vandalism detection technique by combining spectral features of the nodes and the nodes’ neighborhood information with deep autoencoder’s representation learning. Our experimental testing has shown that our proposed method outperforms other standard learning algorithms such as k-nearest neighbors, support vector machine, and softmax classifier.

Keywords—machine learning; security; data mining; signed network; wikipedia; vandalism detection; autoencoder; deep learning.

I. Introduction

Launched in 2001, Wikipedia has grown to be the largest collaborative encyclopedia in the world. The English Wikipedia (2016) currently has around 5 million articles, 40 million pages, 29 million users, 128 thousands active users, and 865 million edits [3]. In addition, according to Alexa.com (2016), Wikipedia is ranked as the 5th top sites in the global internet traffic [4].

Wikipedia Statistics

Most of the edits in Wikipedia are constructive edits. However, as mentioned in Potthast (2010) [6], around 7% of them are bad edits which is roughly 60 million edits. Several related works that will be discussed in the next section have developed various detection techniques to address this problem. However, most of them only leverage the users’ editing contents and behaviors.

The contribution of this paper can be described as follows:

  • To the best of our knowledge, this paper is the first attempt at combining spectral features of the nodes and nodes neighborhood with deep autoencoder to get better performance at vandalism detection in Wikipedia.
  • As our proposed method has been shown to be working well, it might also be used in other kind of social network platform.

The remainder of this paper is organized as follows. Section II describes our goal and accomplishment. Section III describes background and reviews related work. Section IV describes our design and implementation. Section V discusses evaluation results. Section VI concludes the paper.

II. Background and Related Work

Wikipedia (2016) itself defines vandalism as “the act of editing the project in a malicious manner that is intentionally disruptive. It includes the addition, removal, or other modification of the text or other material that is either humorous, nonsensical, a hoax, or that is of an offensive, humiliating, or otherwise degrading nature.” [5]

Potthast et al. (2008) [10] is among the first to introduce machine learning method using logistic regression to automate vandalism detection. While also being faster at the same time, their attempt increased the F-measure performance by 49% compared to the rule-based method that was applied in Wikipedia at the time. Velasco (2010) [9] has developed an extended version of this method by extracting vandalism indicating features and showed LogitBoost and Random Forest as two best performing classifiers. This work won the first place in the PAN’10 Wikipedia vandalism detection task.

Along that line, Smets et al. (2008) [11] have demonstrated that using machine learning algorithms can improve the detection rate of current detection bot which can only detect 30% of the vandalism edits at the time.

Harpalani et al. (2011) [7] showed using statistical models that writing style of those vandals are unique. They further showed that deep syntactic patterns based on probabilistic context free grammars (PCFG) discriminate vandalism more effectively than shallow lexicosyntactic patterns based on n-grams which was proposed by Wang and Mckeown (2010) [12].

West et al. (2010-2014) [13-15] has developed a metric by leveraging spatio-temporal analysis of Wikipedia’s revision metadata to help with vandalism detection which is called stiki-score. Along that line, Adler et al. (2011) [8] proposed a new approach by combining stiki-score, a reputation based system (WikiTrust), and natural language processing features. Kumar et al. (2015) [1] have developed an improved vandalism detection method which is shown to be better than stiki-score and cluebot-ng by leveraging users’ editing behavior features.

Shrivastava (2008) [17] has shown that collaborative attack in a social network can be detected by looking at neighborhood information of a node in the network. Along that line, Ying (2011) [16] has shown an improved version of collaborative attack detection by leveraging spectral features of each node and each node’s neighborhood information.

Figure 1: Deep Autoencoder Architecture

Hinton and Salakhutdinov (2006) [18] proposed a novel method for dimensionality reduction which is superior than principal component analysis by using neural networks with a small center layer as shown in Figure 1. Further described by Ng (2011) [19] and Le (2014) [20-21], this novel method is called an autoencoder. This method works by compressing the feature representation of the input to the small center layer. Based on this compressed feature representation, it will try to reconstruct the input at the output layer by minimizing the difference between the values at the input layer and the output layer. This will force the small center layer to learn compressed representation of the input.

Furthermore, Liu et al. (2015) [22] has shown that using an abstract features derived by autoencoder as input to a supervised learning method works better than hand-designed features.

To summarize, the quality of vandalism detection method in Wikipedia still need to be improved to minimize the burden of human administrators to revert vandalism editing. Furthermore, this paper will aim to investigate the possibility of combining spectral features of nodes and nodes’ neighborhood information with deep autoencoder to further improve state of the art in Wikipedia’s vandalism detection.

III. Design and Implementation

This section describes the design and implementation of the experiments to test our proposed method.

A. Dataset

The original source of the dataset is from the KDD-2015 paper “VEWS: A Wikipedia Vandal Early Warning System”. It contains 33K Wikipedia users with 770K edits. We composed a signed network from that dataset based on the co-editing relationship between the users. This signed network contains 21,535 users with 348,255 links. It is less than the original dataset since some of the pages do not have co-editing relationship between users. This signed network will then be represented as a signed adjacency matrix as shown in Figure 3 with three possible values: 0 for no between the two nodes, +1 for positive link, and -1 for negative link respectively.

A user is considered making a good edit on a particular page if the edit is not reverted later. Otherwise, if the edit is later reverted, it is considered as bad edit.

Figure 2: Constructing the Signed Graph

Furthermore, as can be seen in Figure 2, if two users with good edits or two users with bad edits co-edit a page, a positive link (+) is added to these two users. If a user with good edit and a user with bad edit co-edit a page, a negative link (-) is added to these two users. If two same users co-edit multiple pages, we focus on the first page that they co-edit. If a user edits a particular page multiple times, some of them reverted, some of them are not reverted, we decide if it is bad edit or good edit by taking the majority of them being reverted or not.

Figure 3: An Example of n x n Signed Adjacency Matrix

B. Our Proposed Method

We proposed a novel technique that will leverage the combination of each nodes’ spectral features and each nodes’ neighborhood information with deep autoencoder.

Following are the design of our spectral features for each node and each node’s neighborhood information in the network. We will try several eigen-pair sizes to see whether bigger eigen-pair will help the accuracy. We will also try different combination of node’s neighborhood information addition to see which will do better.

  1. 50 eigen-pairs was extracted from the signed network’s adjacency matrix to construct this feature:
    1. Features 101_50: 50 eigen-vectors, 50 mean of neighbors’ eigen-vectors, 1 degree
  2. 25 eigen-pairs was extracted from the dataset’s adjacency matrix to construct this feature:
    1. Features 103: 25 eigen-vectors, 25 mean of neighbors’ eigen-vectors, 25 mean of neighbors’ eigen-vectors which are attackers, 25 mean of neighbors’ eigen-vectors which are regulars, 1 degree, 1 attackers degree, 1 regulars degree;
  3. 100 eigen-pairs was extracted from the dataset’s adjacency matrix to construct these features:
    1. Features 101: 100 eigen-vectors, 1 degree; Features 201: 100 eigen-vectors, 100 mean of neighbors’ eigen-vectors, 1 degree;
    2. Features 403: 100 eigen-vectors, 100 mean of neighbors’ eigen-vectors, 100 mean of neighbors’ eigen-vectors which are attackers, 100 mean of neighbors’ eigen-vectors which are regulars, 1 degree, 1 attackers degree, 1 regulars degree;
    3. Features 300: 100 eigen-vectors, 100 mean of neighbors’ eigen-vectors with positive edges, 100 mean of neighbors’ eigen-vectors with negative edges
    4. Features 303: 100 eigen-vectors, 100 mean of neighbors’ eigen-vectors with positive edges, 100 mean of neighbors’ eigen-vectors with negative edges, 1 degree, 1 positive edges degree, 1 negative edges degree

Those features will then be combined with a Deep Learning model as follows:

2 Auto encoder layers with topology 200->20 and Softmax classifier at the output layer. The autoencoder layers in this deep learning architecture has been tuned by trying various sizes of hidden units and different decoder transfer function. Then, the best performance setting is used throughout all experiments.

C. Learning Methods

Five repetitions of randomly selected samples with various sizes of training data. Training data sizes used are 5%, 10%, 15%, 25%, 30%. We test each training size with five different random index and report the average performance.

We use Matlab built-in packages for the learning algorithms. Matlab codes are written to automate all the processing.

We compare with following algorithms to measure the performance of the deep learning model that we propose:

  1. K Nearest Neighbors, with k = 1.
  2. Support Vector Machine with default Matlab setting.
  3. Softmax classifier with default Matlab setting.

Workflow

IV. Challenges and Solution

Calculating mean of neighbor’s eigen vectors:

  • Naïve solution: O (n^2), runs okay (several minutes) on 10^3 nodes, unresponsive on 10^5 nodes
  • With indexing, one for-loop, runs in 10 minutes on 10^5 nodes
  • No for loop, using Matlab’s aggregate function, runs in 2 seconds

Organizing the code:

  • A lot of loop indexing, easy to mess up the index
  • Keeping it small, under 50 LOC per file, ~ 180 files
  • Variable naming and comment; Consistency; Pipelining the Workflow

Running the experiments:

  • 5 repetitions * 6 training sizes * 7 features variations * 4 learning algorithms = 840 experiment runs
  • SVM took the longest time, 2 hours on all features variations, one training size, 5 repetitions
  • Other algorithms took around half an hour

V. Evaluation

This section explores the performance of each learning algorithms tested.

A. Accuracy

As can be seen in Figure 4 and Table I  the accuracy of our deep learning model clearly outperforms other learning algorithms in most of the various features inputs. The best performance is highlighted in red in the table.

As expected, most of the time, the performance of each algorithm is increasing on bigger training size.

Figure 4: Accuracy Across Algorithms and Features on 25% Training Size

Table I. Accuracy across algorithms and features

B. F1-Score

As can be seen in Figure 5 and Table II the F1-Score of our deep learning model clearly outperforms other learning algorithms in most of the various features inputs. The best performance is highlighted in red.

As expected, most of the time, the performance of each algorithm is increasing on bigger training size.

Figure 5: F1-score Across Algorithms and Features on 25% Training Size

Table II. F1-score across algorithms and features

VI. Summary and Future Work

In summary, we have shown that our deep learning method works well and outperforms other learning algorithms. Furthermore, we can get better accuracy by using more eigen-pairs. We can also get better accuracy by leveraging more neighborhood information from the nodes.

One possible future work is to further tune the deep learning model by tuning the parameters and using more hidden layers and hidden units. We can then also compare the performance of our work with several previous works.

Another possible future work is to test our method on other social network dataset such as the Web Spam Challenge dataset which contains 114K nodes and 1.8M links. We can then validate if our proposed method will work to detect  various types of Random Link Attack injections on this dataset.

References

  • Kumar, F. Spezzano, and V. S. Subrahmanian, “VEWS: A Wikipedia Vandal Early Warning System,” Proc. 21th ACM SIGKDD Int. Conf. Knowl. Discov. Data Min., pp. 607–616, 2015.
  • Matlab Autoencoder, http://www.mathworks.com/help/nnet/ref/trainautoencoder.html
  • Wikipedia Statistics, https://en.wikipedia.org/wiki/Wikipedia:Statistics
  • Alexa Top Sites, http://www.alexa.com/topsites
  • Vandalism on Wikipedia, https://en.wikipedia.org/wiki/Vandalism_on_Wikipedia
  • Martin Potthast. 2010. Crowdsourcing a wikipedia vandalism corpus. In SIGIR’10 , pages 789–790.
  • Harpalani, M. Hart, S. Singh, R. Johnson, and Y. Choi, “Language of vandalism: Improving Wikipedia vandalism detection via stylometric analysis,” ACL-HLT 2011 – Proc. 49th Annu. Meet. Assoc. Comput. Linguist. Hum. Lang. Technol., vol. 2, pp. 83–88, 2011.
  • T. Adler, L. De Alfaro, S. M. Mola-Velasco, P. Rosso, and A. G. West, “Wikipedia vandalism detection: Combining natural language, metadata, and reputation features,” Lect. Notes Comput. Sci. (including Subser. Lect. Notes Artif. Intell. Lect. Notes Bioinformatics), vol. 6609 LNCS, no. PART 2, pp. 277–288, 2011.
  • M. Mola Velasco, “Wikipedia vandalism detection through machine learning: Feature review and new proposals: Lab report for PAN at CLEF 2010,” CEUR Workshop Proc., vol. 1176, 2010.
  • Potthast, B. Stein, and R. Gerling, “Automatic vandalism detection in Wikipedia,” Lect. Notes Comput. Sci. (including Subser. Lect. Notes Artif. Intell. Lect. Notes Bioinformatics), vol. 4956 LNCS, pp. 663–668, 2008.
  • Smets, B. Goethals, and B. Verdonk, “Automatic Vandalism Detection in Wikipedia : Towards a Machine Learning Approach,” Proc. AAAI 2008 Work. Wikipedia Artif. Intell. An Evol. Synerg. WikiAI08, pp. 43–48, 2008.
  • Y. Wang and K. R. Mckeown, “Got You!: Automatic Vandalism Detection in Wikipedia with Web-based Shallow Syntactic-Semantic Modeling,” in Proceedings of the 23rd International Conference on Computational Linguistics (Coling 2010), 2010, no. August, pp. 1146–1154.
  • West, S. Kannan, and I. Lee, “Detecting wikipedia vandalism via spatio-temporal analysis of revision metadata?,” … Third Eur. Work. Syst. …, vol. 1752050, pp. 22–28, 2010.
  • G. West, “Damage detection and mitigation in open collaboration applications.,” Diss. Abstr. Int. Sect. B Sci. Eng., vol. 75, no. 1–B(E), p. No-Specified, 2014.
  • G. West, S. Kannan, and I. Lee, “STiki: An Anti-vandalism Tool for Wikipedia Using Spatio-temporal Analysis of Revision Metadata,” Proc. 6th Int. Symp. Wikis Open Collab. – WikiSym ’10, p. 1, 2010.
  • Ying, X. Wu, D. Barbara, and D. Barbar, “Spectrum based fraud detection in social networks,” 2011 IEEE 27th Int. Conf. Data Eng., pp. 912–923, 2011.
  • Shrivastava, A. Majumder, and R. Rastogi, “Mining (social) network graphs to detect random link attacks,” Proc. – Int. Conf. Data Eng., vol. 0, pp. 486–495, 2008.
  • E. Hinton and R. R. Salakhutdinov, “Reducing the Dimensionality of Data with Neural Networks,” Science, vol. 313, no. July, pp. 504–507, 2006.
  • Ng, “CS294A Lecture Notes Sparse Autoencoder,” Cs294a, pp. 1–19, 2011.
  • V Le, “A Tutorial on Deep Learning Part 1: Nonlinear Classifiers and The Backpropagation Algorithm,” Tutorial, pp. 1–18, 2014.
  • V Le, “A Tutorial on Deep Learning Part 2: Autoencoders, Convolutional Neural Networks and Recurrent Neural Networks,” Tutorial, pp. 1–20, 2015.
  • Liu, I. S. I. Usc, A. Jaiswal, K. Yao, I. S. I. Usc, and C. S. Raghavendra, “Autoencoder-derived Features as Inputs to Classification Algorithms for Predicting Well Failures,” Society of Petroleum Engineers Western Regional Meeting, 2015.