1 Introduction
Social media commonly uses the notion of aliases to preserve the privacy of users, creating a separation between their ‘real world’ and ‘online’ personae. An ‘alias’ is a moniker that is (often self-) assigned to a user, identifying that user without revealing their true, ‘real world’ identity. A commonly used alias is for e-mail accounts; while some corporate e-mail address policies specify the incorporation of a real name, such as firstname.lastname@company.com, many ‘web mail’ providers allow users to select their own e-mail address, resulting in aliases such as hunter2@email.com.
With the rise of social media, the use of aliases has increased dramatically. While some sites (such as Facebook) request that real names be used, there is typically little or no verification of such identities during registration. As a result, one person can register for these services under different names or different aliases.
While the use of aliases can have legitimate purposes, some user classes (including trolls and cyberbullies) use them to evade responsibility for their online activities (Stabek, Watters and Layton Reference Stabek, Watters and Layton2010). Aliasing can defeat some access controls, such as banning malicious users, since they can simply re-register under a new alias and continue posting. By removing the link between actual and online identity, civil and criminal investigations can be impeded, because the true author of a defamatory post, for instance, may not be readily identified from their alias.
Thus, there is a need (in some circumstances) for reliable alias matching to be performed. Being able to match aliases and ultimately link them to a known identity would enable attribution, and would likely reduce the incidence of some forms of cybercrime that rely upon anonymisation (Layton and Watters, Reference Layton and Watters2009). This approach is consistent with the situational crime prevention principle of increasing the risk by reducing anonymity (Clarke, Reference Clarke1997).
This desire to enhance law enforcement capability needs to be balanced against legitimate desires for privacy and anonymity, allowing citizens to speak freely on the Internet against tyranny or oppression (Ureche, Layton and Watters Reference Layton, McCombie and Watters2012), particularly in repressive states or those which restrict Internet usage. As noted in Narayanan et al. (Reference Narayanan, Paskov, Gong and Bethencourt2012, p. 1), ‘a right to anonymity is meaningless if an anonymous author’s identity can be unmasked by adversaries’.
Network-based methods also exist that are capable of identifying a user responsible for a posting on the Internet – which we refer to as direct methods – by tracing the source of the network packets to its origin. Countermeasures, such as The Onion Router (TOR), can be readily used to mask the provenance of communication on the Internet. For the purposes of this research, we assume that such direct methods of linking aliases are generally infeasible, and therefore, indirect methods are required (Watters et al. Reference Watters and Patel2012). This assumption is a realistic one, due to the continuous improvement of both sides of attribution and anonymisation technology – engaged, in a sense, in a war of attrition.
In this paper, we refer to the original creator of a document, regardless of the alias used, as the author. The pseudonym that the document is noted as being created by is the alias. When we split an author’s documents into groups under the guise of being by two aliases, we refer to these as sub-aliases, to emphasise that these are created within the methodology through differentiation, and not an actual alias chosen by the author.
1.1 Research objective
Research into the alias matching problem often requires generating data, as real-world datasets containing authors attempting to hide behind multiple aliases are difficult to find and/or reliably generate. Previous research has generated multiple sub-aliases for an author by taking all documents under a single alias, and randomly relabelling them. We refer to this process as generating ‘random sub-aliases’. Research using this approach has often generated very impressive results, typically with accuracy levels above 90% (Novak, Raghavan and Tomkins Reference Novak, Raghavan and Tomkins2004) and exceeding 60% in difficult scenarios (Layton, McCombie and Watters Reference Layton, McCombie and Watters2012).
Unfortunately, this solution does not sufficiently model the real-world problem. If an author is hiding behind multiple aliases, it is likely that they are discussing different topics, deliberately choosing which alias to use (and not choosing randomly which alias to use). This distinction is shown in Figure 1. This means that sub-aliases are likely to be very different to each other with regard to topic.
Comparison between (a) the real-world problem, (b) the idealised problem using random sub-aliases, and (c) the idealised problem using topic-based aliases.
In this paper, we investigate whether this is a major problem in terms of accuracy and applicability, and whether topic-based sub-aliases differ significantly from random sub-alias generation.
1.2 Contributions
In research on alias matching, we aim to create techniques to identify when postings made under multiple aliases are written by the same author. There has been previous research on this application, however, we show that previously used methods drastically reduce in accuracy when sub-aliases are created based on topic (and not randomly). We believe that this is a major limitation to the applicability of existing techniques to real-world problems, and thus, we present a methodology for generating sub-aliases by topic, even if the topics are not known for the datasets. The proposed methodology uses a word-based document clustering technique to split the documents into two, approximating multiple topics. We also present a semantically aware version of the methodology for validation. We finally perform an experimental comparison using a number of datasets from online social media.
This paper makes three major contributions. Firstly, we support our assertion that random sub-aliases generation increases performance over topic-based sub-aliases, by using a topic controlled dataset. This experiment shows that randomly generated sub-aliases are much easier to classify than topic-based sub-aliases. In a real-world application, we could expect significant variance by topic, which should be replicated in experiments in this area. Secondly, we show that generating topic-based aliases using a topic clustering methodology is effective at generating difficult to match aliases, modelling the use case of topic controlled datasets, even when the original dataset does not contain topic information. This allows for the more thorough testing of methods for this application, bridging the gap between the idealised and application scenarios. Thirdly, we test a large number of authorship models using this methodology and show that local n-gram (LNG) models perform better than feature-based approaches for this type of application. The reduction in performance was less significant for LNG methods and the overall accuracy was much higher, suggesting that LNG methods are more robust than other types tested.
2 Literature review
Alias matching is a relatively new field of research, but draws heavily upon methods from authorship analysis. Novak et al. first investigated the problem of identifying when multiple online aliases belonged to the same author using authorship analysis of the text within their messages (Novak et al., Reference Novak, Raghavan and Tomkins2004). They used several types of features, including word distributions, misspellings, punctuation characters, emoticons and function words. Using these features to form vector space representations of the documents written under each alias, the Kullback–Leibler (KL) divergence was then used to determine how similar two aliases were. For their experiments, one hundred aliases were used, after which the documents were split into two sub-aliases. The testing corpora were collected from an online forum, composed of approximately 3,000 words per alias. Each sub-alias was then compared against the other 199 sub-aliases. The most similar sub-alias was predicted as the match. This methodology was able to achieve over 90% accuracy in some of the experiments.
There has been other research on linking aliases using methods other than authorship analysis. Anti-aliasing was performed by analysing e-mail address usage by authors across different websites (Holzer, Malin and Sweeney, Reference Holzer, Malin and Sweeney2005). Overall, these methods of linking aliases are highly relevant to the practical problem. In this research, we consider these techniques to be complimentary to an investigator interested in matching aliases. However, the experiments in this research will assume that the only information that can be used is the posts themselves, and confine the research to using authorship analysis methods.
Other research, such as that by Schein et al. (Reference Schein, Caver, Honaker and Martell2010), has investigated the use of topic to inform authorship attribution accuracy. The separated topics when performing cross-validation, allow for the evaluation of authorship methods to be compared based on unseen topics. This approach has some overlap with the goals of this research; however, we focus on the problem of alias matching instead of authorship attribution, and specifically address the instances when topic information is not available.
2.1 Authorship analysis
The problem of anti-aliasing using authorship analysis can be seen as an abstraction of the problem of authorship attribution. Authorship attribution is the supervised learning problem of attributing a single document of unknown authorship to one of a set of candidate authors. There is a wide range of research into this problem, and the techniques can be separated into two major categories: vector space models and LNGs.
Vector space models use an ordered set of features F of size d to create a representation 
$x \in \mathbb {R}^{d}$ of each document in the testing corpora. This representation can then be used as input to a supervised classification algorithm such as Support Vector Machines (SVM) or used with a distance metric to determine the distance between different documents (under the assumption that a lower distance gives a higher likelihood of co-authorship). The initial choice of features is determined by the investigator and includes features such as the frequency of certain function words, the mean length of sentences or the occurrence of a signature in an e-mail.Footnote 1 There are a significant number of features, with Rudman now famously declaring in 1998 that nearly 1,000 features had been used in the authorship analysis literature (Rudman, Reference Rudman1998). Since then, many more features have been used. One of the most thorough descriptions of the most commonly used features is given in Zheng et al. (Reference Zheng, Li, Chen and Huang2005). The previously mentioned research of Novak et al. (Reference Novak, Raghavan and Tomkins2004) used a vector space model for representing the documents, as have many other papers in the field (Solorio et al., Reference Solorio, Pillay, Raghavan and Gómez2011).
LNG models instead aim to determine an author profile for writing habits, using the distribution of character n-grams in the author’s messages. For a document of unknown authorship, a similar document profile is created, and then the profiles are compared. The first technique of this type utilised was the Common n-grams (CNG) methodology (Kešelj et al., Reference Kešelj, Peng, Cercone and Thomas2003), which profiled an author or document using the top L most frequently occurring n-grams (L is usually in the thousands while n is usually between two and five inclusive). The distance between two profiles, P 1 and P 2, is given in (1).
\begin{equation}
K(P_1, P_2) = \displaystyle \sum _{x \in X_{P_1} \cup X_{P_2}} \Biggl (\frac{2\cdot (P_1(x) - P_2(x))}{P_1(x) + P_2(x)}\Biggr )^2
\end{equation}
Since then, several variations on this scheme have been released. The Source Code Author Profile (SCAP) methodology used the same profile method as CNG, but the similarity between profiles was computed as the size of the intersection (i.e. n-grams appearing in both profiles) (Frantzeskou et al., Reference Frantzeskou, Stamatatos, Gritzalis, Chaski and Howald2007; Layton, Watters and Dazeley, Reference Layton, Watters and Dazeley2011b). Recentred Local Profiles (RLP) used a language default profile to recentre the values within each profile, and used the top L most distinctive n-grams, where distinctive was the absolute distance between the frequency of the n-gram in normal usage, compared to that author or document (Layton, Watters and Dazeley Reference Layton, Watters and Dazeley2011c). Stamatatos’ d1 and d2 measures are improvements designed to work with unbalanced datasets (Stamatatos, Reference Stamatatos2007). CNG-WPI (Weighted Profile Intersection) is an improvement to SCAP which weights the n-grams based on the number of documents they appear in (inferring the likelihood of the n-gram to appear in both profiles) (Escalante, Montes-y Gómez and Solorio, Reference Escalante, Montes-y Gómez and Solorio2011). LNG methods have also been used for unsupervised methodologies, outperforming feature-based models (Layton, Watters and Dazeley Reference Layton, Watters and Dazeley2011a).
Luyckx and Daelemans (Reference Luyckx and Daelemans2011) investigated the impact of several components of the authorship attribution problem. The effect of the number of candidate authors and the amount of training data available was tested, finding that more data and fewer candidate authors give better results. While unsurprising at a high level, this was the first time such effects have been quantified, and also highlighted the fact that topic variation in texts appears to play a substantial role. While not solidly determined, this topic effect was discovered by examining whether a dataset with fewer topics and less data often had higher accuracies than a dataset with more topics and more data.
2.2 Topic modelling
In this section, we will briefly overview methods for modelling the topic of documents. As this research will investigate the impact of creating sub-aliases based on topic difference, it is necessary to understand how topic is modelled. The aim is not to be exhaustive; for in-depth coverage, we recommend Sebastiani’s (Reference Sebastiani2002) review, and the more recent work by Aggarwal and Zhai (Reference Aggarwal and Zhai2012).
Topic modellingFootnote 2 is the task of creating a representation of documents to build a classifier or clusterer based on their topic or category. While recent advances have improved the accuracy of such systems, many older methods still provide sufficient accuracy for many applications. A prime example of this is the bag-of-words model. In the bag-of-words model, a matrix X is created such that X i, j is the frequency of word i in document j. In this method, the position, relationship and interaction between words is ignored. While simplistic, this model has been shown to perform quite well, and is often used as a baseline for testing other approaches (Aggarwal and Zhai, Reference Aggarwal and Zhai2012).
One method for improving the weighting of a bag-of-words model is to use the tf-idf weighting scheme. In tf-idf, the weight of a frequency is proportional not only to the number of times it appears in a given document, but also the number of documents in the corpus it appears in Salton and Buckley (Reference Salton and Buckley1988). For a given term ti appearing in document Dj ∈ D, the tf-idf weighting is given as
\begin{equation}
tfidf(t_i, D_j) = count(t_i, D_j) \cdot log \frac{|D|}{|\lbrace k:t_i \in D_k\rbrace |}
\end{equation}
This is the dot product of the term frequency (tf) and the inverse document frequency (idf), giving the name of the method. The term frequency, count(ti, Dj), is the number of times the term ti appears in document Dj. The inverse document frequency, 
$log \frac{|D|}{|\lbrace k:t_i \in D_k|\rbrace}$, is the log of the inverse of the proportion of documents in the corpus containing the term. The resulting weights are used to update the matrix X given by the bag-of-words model.
The final step of the topic modelling process is to determine the distance between two vectors in X, giving the distance between the corresponding documents in terms of their topic. One such commonly used method is the cosine distance (Salton and McGill, Reference Salton and McGill1986). While many other metrics exist, the cosine distance is often used for calculating the distance between documents in topic modelling applications (Aggarwal and Zhai, Reference Aggarwal and Zhai2012).
3 Problem observation
In this section, we use a topic controlled authorship corpus to highlight the issues with alias matching and randomly separate aliases. We performed an experiment that compared the accuracy of randomly chosen sub-aliases compared to topic-separated sub-aliases using a topic controlled corpus. The corpus selected for this research was the AAAC ‘A’ corpus (Juola, Reference Juola2004), in which thirteen students were asked to write essays on four topics. Each student has one essay on each topic, with one exception, giving fifty-one total documents with a mean document length of 4,541 characters and standard deviation of 1,070 characters. We chose two of these topics, and performed the experiment detailed below. We then repeated the experiment with combination of two topics, giving a total of six different subsets.
Each document was split into sub-documents of length 500 characters. This gave a larger corpus to draw sub-aliases from. Sub-aliases were then created either by sampling from the two topics at random (‘random’ sub-aliases) or splitting based on the topic of the documents (‘topic’ sub-aliases). We then used a large number of models to perform alias matching, using the procedure outlined in more detail below. For the random sub-aliases, we repeated the experiment for each model one hundred times, re-sampling to create new sub-aliases at each iteration. The expected result for this experiment was that the topic-based sub-aliases would produce significantly lower accuracies for alias matching than the random sub-aliases.
3.1 Results
We now present the results comparing random- and topic-based sub-aliases. As there was no variance in topic-based sub-aliases, only one iteration was performed. For random sub-aliases, one hundred iterations with re-sampled sub-aliases were chosen. However, for all tests, including the topic-based sub-aliases, ten-fold cross validation was performed and the mean results are taken as the quality of the algorithm.
The results from this experiment show a significant difference between the alias generation methods. Figure 2 highlights this result, with a drastic difference between the accuracy of random sub-aliases, which is very high, compared to topic-based sub-aliases, which is quite low. Models in this figure were ranked by their accuracy on random sub-aliases, highlighting the very large gap by the most accurate methods. Only in the worst performing 10% of methods did we find topic-based sub-alias accuracy was within the 95th percentile for the random sub-aliases. The topic-based sub-aliases results were similar to what many methods obtain on this dataset for classification accuracy (Layton et al., Reference Layton, Watters and Dazeley2011c). We tested all topic combinations for this dataset and found that all repeated this combination. The mean accuracy values overall were over 0.75 for the random sub-aliases and under 0.14 for the topic sub-aliases. In all cases, the two tailed p-value for a t-test was less than e −170, indicating that the two distributions are highly unlikely to have been generated by the same distribution.
Comparison between random sub-aliases and topic sub-aliases over all authorship models from this paper, for the AAAC A dataset. Shaded area is the 95th percentile for randomly chosen sub-aliases.
3.2 Effect of topic
To further show the effect of topic on sub-alias creation and subsequent alias matching, we repeated the experiment, but using sub-aliases with a mixture of sampling between topic and random. This mixture sub-alias was selected by choosing sub-documents from the above process with p% of sub-documents from the same topic and (100 − p)% from the opposite topic. When p = 50, we expected this procedure to have the same results as random sub-aliases. When p = 100 or when p = 0Footnote 3, we expected the same results as for the topic-based aliases above.
Figure 3 shows that this is indeed the case. When the probability is 50%, the prediction accuracy is at its highest and decreases when p both increases or decreases. As before, this same pattern was observed in all other topic combinations. A Pearson correlation of the relationship between the absolute distance to p = 0.5 and the accuracy was − 0.956, (p < 1e −27).
Comparison between random sub-aliases and topic sub-aliases over many authorship models for AAAC A datasets. The randomisation parameter determines whether a document is selected from the same topic or the opposite topic, with 50% being completely randomly selected.
4 Methodology
First, LNG methods such as CNG are compared against the feature-based and bag-of-words approaches performed in previous research. In this experiment, a writer’s documents are randomly split to form two sub-aliases. The algorithm then chooses the best matching sub-alias, aiming to discover the one originally belonging to the same author. We show that the LNG approaches generally outperform these previously tested methods. In the second experiment, each writer’s documents are clustered into two sub-aliases using document topic clustering. The aim is to analyse the effect that topic has on the accuracy of the results. Previous research has suggested, without evidence, that character n-gram-based approaches are more susceptible to topic and context biases than other approaches to authorship analysis (Narayanan et al., Reference Narayanan, Paskov, Gong and Bethencourt2012). We show that this is not true and that other methods are actually more susceptible than character-based approaches.
In this section, we first outline the datasets and algorithms used in both experiments. We then outline more fully how each of these experiments is performed and the method for analysing the results.
4.1 Datasets
Three datasets involving online communication were used in this research, since they are representative of real-world case studies for aliasing. The first two were taken from Twitter, an online micro-blogging website limiting posts to just 140 characters. The two datasets, Twitter Large and Twitter Small, were samples from the data collected in Layton, Watters and Dazeley (Reference Layton, Watters and Dazeley2010). Twitter Large is the full set of posts from one hundred authors taken at random. Twitter Small is the first fifty postings by a separate set of one hundred randomly selected authors. In both cases, only aliases with at least ten documents were considered. The third dataset was taken from a dataset of blog postings from the online forum ‘Chronicle of Higher Education’ (Pillay and Solorio, Reference Pillay and Solorio2010). While not limited in length, the blog postings are often small with around 400 to 600 characters per post. Only aliases with at least twenty postings were considered and of those aliases one hundred were chosen at random. A maximum of forty postings from each alias were taken.
Several preprocessing steps were undertaken for each dataset. For the Twitter-based datasets, we uniformly removed any tokens beginning with @ and #, as these represent mentions of other users and topics, respectively. Both of these are out of the control of the authorFootnote 4 and therefore removed. The forum data is considerably noisier than the Twitter data, including tags for formatting etc. In collecting the data, Pillay and Solorio removed such tags and mentions of the author/alias (Pillay and Solorio, Reference Pillay and Solorio2010).
4.2 Tested authorship methods
There were two types of authorship analysis methods noted in Section 2: vector space and profile-based. Each was used in this experimentation with a number of parameters.
For vector space methods, we used each of the datasets identified by Narayanan et al. (Reference Narayanan, Paskov, Gong and Bethencourt2012): character, function words, syntactic and ‘other’. While Narayanan et al. (Reference Narayanan, Paskov, Gong and Bethencourt2012) found that including all features provided the best accuracy in their tests, we considered all combinations of these datasets. We also tested the word features used by Novak et al. (Reference Novak, Raghavan and Tomkins2004), which were found to be most effective in their previous anti-aliasing experiments. For each sub-alias, the documents belonging to that sub-alias were represented in vector space form, then the vectors were averaged to form a centroid. The centroids were then compared using each of the Euclidean, cosine and correlation distance metrics. The sub-alias with the lowest distance to the candidate was chosen as the most likely match.
For profile-based methods, we considered all profile methods listed in Section 2: CNG, SCAP, RLP, d1, d2 and CNG-WPI. The parameters used for each of these methods were each combination of n ∈ {2, 3, 4, 5} and L ∈ {100, 500, 1,000, 2,000, 5,000}. This range provided a representative coverage of the parameters used for these methods in previous research.
The KL divergence-based bag-of-words model employed by Novak et al. (Reference Novak, Raghavan and Tomkins2004) was also included in the tests. This model has two parameters; the number of words to include in the model (L) and the mixing parameter for including the corpus wide frequencies for smoothing α. We chose the same range for L as for the n-gram-based models. Values for α range from 0 to 1 inclusive, in steps of 0.2. All combinations of L and α were tested.
4.3 Experiment 1: Randomly generated sub-aliases
In the first experiment, we evaluated different authorship analysis methods on their ability to correctly identify matching aliases for authors. This is performed for each of the datasets from Section 4.1 and the results analysed both on a overall-average scale and per-dataset.
For a given dataset, the documents from each of the authors were split into two sub-aliases. This was performed randomly, with the only constraint that each sub-alias had the same number of documents. Each model described in Section 4.2 was then evaluated using ten-fold cross validation (using the same sub-aliases for each fold). This procedure was run thirty times, each time generating new sub-aliases for all authors.
4.4 Experiment 2: Topic-based sub-aliases
The second experiment aimed to evaluate the effect of topic on the results. To do this, we repeated experiment 1 with sub-aliases chosen using topic clustering, rather than randomly. The documents were first stemmed, normalising word types. Any function words were discarded and then a bag-of-words model was applied to vectorise the documents. The documents for each author were clustered to create two evenly sized clusters with a high divergence by topic. In all other respects, this experiment was performed exactly as experiment 1. The expected result of this experiment was that the authorship methods would perform less effectively if they were susceptible to modelling topic and not authorship.
The first step of the process involved removing function words, which are often considered to include authorship information and are often discarded for the topic-based classification (Sebastiani, Reference Sebastiani2002). Secondly, the bag-of-words model was employed, collecting the frequency of all words appearing in at least 50% of all documents in each corpus. The most frequent 10,000 words fulfilling these criteria were kept for each corpus. As a third step, tf-idf weighting was applied. The above steps gave a matrix X such that X i, j was the tf-idf weighting of word i in document j. This methodology was performed using the topic modelling modules contained within scikits.learn version 0.11 (Pedregosa et al., Reference Pedregosa, Varoquaux, Gramfort, Michel, Thirion, Grisel, Blondel, Prettenhofer, Weiss, Dubourg, Vanderplas, Passos, Cournapeau, Brucher, Perrot and Duchesnay2011).
Finally, the documents from each author were clustered into two distinct clusters. A matrix D was created for each author, such that D m, n was the distance between documents m and n, with distance calculated using the cosine distance. The two documents with the highest distance were selected as exemplars. Each of the other documents was then ranked according to its minimum distance to one of the exemplars. Starting with the documents with the smallest distance, each was assigned to their nearest exemplar. This process continued until the number of documents assigned to either exemplar was more than 50% of the total number of documents. At this point, the rest of the documents were assigned to the other exemplar, resulting in two distinct clusters that are approximately the same size. We used this method rather than an algorithm such as k-means used in other studies such as Layton et al. (Reference Layton, Watters and Dazeley2011a), to give evenly sized clusters. The k-means algorithm (and most other clustering algorithms) chooses clusters based on other criteria, often minimising some evaluation function that is not dependent on the size of the clusters.
As a further exercise, we replicated this second experiment leaving topic hashtags in the tweets for the topic clustering step and then removing them for the de-aliasing. We found only a small difference of generally less than 1% in accuracy for most methods and no discernible pattern to the results (i.e. one algorithm was not generally better performing than the other). For this reason, we conclude that the results were indicative of both including and excluding topic tags for the topic-based sub-alias creation.
As a final note, the documents were reverted to their original state for the authorship attribution. We did this to remove the effect of topic on the clusters, which may have led to overfitting. An example of this problem may be if an author pens a document in a topic not included in the training set, an overfitted model with topic features may incorrectly attribute this author due to the change in topic.
4.5 Experiment 3: Semantic topic-based sub-aliases
The bag-of-words model used in experiment 2 for sub-alias creation has the potential to positively affect character n-gram models. While word features are an obvious candidate for improvement based on the previous sub-alias creation, characters are closely linked to words and may also be affected positively. This may provide a positive benefit to those models that use character- or word-based features. To overcome this, we performed a final experiment that also incorporated semantic information. This experiment was performed exactly as experiment 2, with the exception that the semantic weighting described below was used, rather than the tf-idfweighting used in the previous experiments.
We employed the method used by Jing et al. (Reference Jing, Zhou, Ng and Huang2006) that uses Wordnet to find semantically related terms. Wordnet has been used in a number of document (topic-based) clustering and classification (Watters and Patel, Reference Watters and Patel1998; Hotho, Staab and Stumme, Reference Hotho, Staab and Stumme2003; Sedding and Kazakov, Reference Sedding and Kazakov2004; Choudhury, Kimtani and Chakrabarty, Reference Choudhury, Kimtani and Chakrabarty2012). The model used takes the input bag-of-words matrix, without the tf-idf weighting, and updates it based on the semantic relationship between words using the following equation:
\begin{equation}
\bar{x}_{j,i} = x_{j,i} + \sum _{k, i \ne k}^{m} \delta _{i, k}x_{j, k}
\end{equation}
Where x j, i is the value of the ith term in the jth document and δi, k is the semantic distance between the ith and kth terms (a value between 0 and 1 with higher values indicating a higher semantic similarity). All rows in the matrix (i.e. the sum of weights for each document) were normalised to equal 1.0 for all documents.
The net effect of this update in weighting is that semantically related terms are increased in weight, even if they do not directly appear in the document. In an example given in Jing et al. (Reference Jing, Zhou, Ng and Huang2006), a document with the words ‘ball’ five times and ‘basketball’ three times results in a net value of 6.4 for the word ‘football’, even though it does not appear in the document at all. By using this semantic information, we drastically reduce the impact of characters on the bag-of-words representation, instead using word sense rather than word form.
5 Results and discussion
The results for the four experiments are given in this section. A large number of tests were performed over a large parameter range. In the interests of clarity and space considerations, some of the results have been summarised, but are available from the authors. The abbreviations used in the results table are shown in Table 1. For each experiment, we present two tables of results. The first table shows the top ten performing model/parameter combinations. As this list is usually dominated by the same form of model, we give a second table of each of the different types of model tested. In all cases, the best parameter combination is shown in this second table, for each of the model types. This gives a view of the comparative strength of each form of model, without listing each of the thousands of parameter combinations tested.
Abbreviations used in results tables
5.1 Experiment 1
The top results for experiment 1 were dominated by LNG methods, with CNG performing best overall and for each dataset. SCAP and RLP also performed favourably, which was expected since the methods are heavily related. Table 2 shows the top ten models (including parameters) and their performance on each corpus. Overall, there was no significant difference between relative corpora results, although it can be clearly seen that more data produces more accurate models. Including all tweets in the Large Twitter dataset performed better than the Small Twitter dataset, which in turn did better than the (generally) smaller Forum dataset, a pattern found in most authorship analysis studies.
Top ten models when sorted by mean accuracy for anti-aliasing for random sub-aliases. The maximum recorded score for each corpus is represented on this list. Model abbreviations are listed in Table 1
Top recorded accuracy for each model type (as well as variants for some models), for anti-aliasing for random sub-aliases (experiment 1). Model abbreviations are listed in Table 1
Top ten models when sorted by mean accuracy for anti-aliasing for the topic-separated sub-aliases (experiment 2). The maximum recorded score for each corpus is represented on this list. Model abbreviations are listed in Table 1
Top recorded accuracy for each model type (as well as variants for some models), for anti-aliasing for the topic-separated sub-aliases (experiment 2). Model abbreviations are listed in Table 1
In comparing the results of LNG-based models with other models, two aspects are clear. Firstly, there was a significant degradation in the results as less data appears, with accuracies for the large Twitter corpus being generally high, but the Forum corpus showing results barely above the chance rate of 0.05 for many model types. Secondly, KL-BOW performed comparably on the Twitter datasets to the better LNG methods, but scored quite poorly on the Forum dataset. One potential cause for this may be the less formal language in forums compared to tweets, resulting in fewer ‘proper’ words.
5.2 Experiment 2
Experiment 2, using topic-separated anti-aliasing experiment showed similar final results to experiment 1. LNG methods represented all of the top results, with CNG again performing best. The most significant result shown through this experiment was that all methods performed less for the topic-separated sub-aliases, compared to the randomly chosen sub-aliases. This difference was universal, but was more pronounced in some methods than others. Presented again are the top ten performing models, as well as the best performing of each model type.
5.3 Comparative results
Overall, the relative results between the two lists were similar. SCAP dropped significantly more than CNG or RLP, but still performed well compared to other methods. The feature-based approaches were again the worst performing methods, highlighting that these techniques are not suited to this application, at least for shorter documents tested here. The Spearman’s rank coefficient between the two sets of results was 0.9883 with a given p-value of 0. The Pearson’s correlation was similar at 0.9804 with a p-value of 0. The mean difference for all methods between the random and topic-based sub-aliases was 0.0868 and the mean difference as a percentage was 39.19%. For LNG-based methods, the difference was 35.15% (CNG = 30.16%, RLP = 32.15%, SCAP = 47.09%, d1 = 47.41%, d2 = 18.94%). For KL-BOW, the difference was 38.92%, while for the feature-based methods it was 55.31%.
Table 6 shows the percentage change between methods from experiment 1 to experiment 2. In all cases, the best (i.e. least drop in accuracy) was reported for each model type. While the vast majority of model/data pairs reported a drop in accuracy between experiment 1 and experiment 2, there were a few cases in which the accuracy improved. However, in all cases, the original models were poorly performing and this happened rarely enough to consider them to be chance events unlikely to consistently be repeated in real-world applications.
Percentage change between the results of experiment 1 and experiment 2. The best (least drop) of each model are listed and the median result is over all sub-results (not just summaries). Model abbreviations are listed in Table 1
One significant result from the second experiment was that LNG methods tended to perform better comparatively and relatively, compared to non-LNG methods. Furthermore, the drop in accuracy was also less, as a proportion of accuracy in experiment 1. This is shown in Table 6, where LNG methods are near the top of the table for percentage of accuracy degradation. All changes in this table were statistically significant, as was the overall change in accuracy (p < 1e 20 in all cases).
5.4 Experiment 3
The results from experiment 3, in which sub-aliases are created using a semantically aware topic modelling function, are given in Table 7 and show a similar pattern to experiment 2. The results showed a greater degradation, however, the overall rankings were relatively similar, especially to experiment 2. Furthermore, the per-model results shown in Table 8 show that there was little variation, despite the significant difference in the calculation of the profiles.
Top ten models when sorted by mean accuracy for anti-aliasing for semantically aware topic-separated sub-aliases (experiment 3). The maximum recorded score for each corpus is represented on this list. Model abbreviations are listed in Table 1
Top recorded accuracy for each model type (as well as variants for some models), for anti-aliasing for semantically aware topic-separated sub-aliases (experiment 3). Model abbreviations are listed in Table 1
Finally, in Table 9, we compare the results of experiment 3 to experiment 1. Most notably, the word-based authorship did not reduce performance as before, since words were not directly used for the sub-alias creation. A number of parameter sets had negligible results (fifteen from 256 combinations), with lower alpha values having less degradation in results. The LNG methods performed worse than previously, with the best LNG method still having a 25% degradation in results. The best Narayanan feature-based set had a loss of 40%. Surprisingly, the RLP method scored the ‘worst best result’ of 42.5% degradation, significantly worse than the previous comparison between experiment 1 and experiment 2. The overall degradation, excluding RLP, was comparable to the previous comparison of results.
Percentage change between the results of experiment 1 and experiment 3. The best (least drop) of each model are listed and the median result is over all sub-results (not just summaries). Model abbreviations are listed in Table 1
6 Conclusions
In this paper, we highlighted that randomly chosen sub-aliases do not adequately represent the real-world problem of alias matching. In the theoretical sense, if an author is aiming to hide their identity by using multiple aliases, it is unlikely that the author will randomly choose an alias when posting a message. Instead, it is more likely that they would choose one alias for one purpose and another alias for a different one. In the practical sense, Section 3 showed that for a topic controlled dataset, using topic-based separation results in drastically reduced accuracy compared to random separation. Furthermore, we showed a correlation between the mixture of topic versus random and the final accuracy of the method. This correlation occurred across all methods we tested.
We then showed that using a topic-based clustering repeats this behaviour and can be used in datasets without topic identifiers. Thus, the methodology can be used in a wide variety of applications for alias matching. The use of topic-based sub-aliases allows for better evaluations of authorship methods for this task.
Furthermore, this method allowed us to test the efficacy of authorship methods, especially with respect to their overfitting of topic. If a model performed well with randomly chosen sub-aliases and poorly with topic-based sub-aliases, we suspect that the method is overfitting on topic more than author traits. In contrast, those that are high for both types of sub-aliases are better at modelling authorship. Our results for LNG methods are very high, with 99% accuracy achieved on the Large Twitter dataset for randomly selected sub-aliases. The accuracy does drop off with less data; the Small Twitter dataset recorded a high 84.5% and Forum just over 41%. Compared to the other results tested, LNG methods are highly effective both relatively and comparatively. This shows that the topic-based sub-aliases are more difficult to match than those randomly generated. Furthermore, it shows that LNG-based models are more robust to this degradation. An exception to this was RLP when using a semantically aware topic-based method.
This research also adds to the body of work that shows that LNG-based methods outperform feature-based approaches for authorship analysis applications. While it appears that current feature approaches are somewhat accurate in many settings, there is an ongoing trend that LNG-based methods perform better. With this research, the fears that character n-gram-based methods are topic-dependent appear to be unfounded. Further work on this result is needed to more accurately determine this conclusion across a larger range of authorship analysis applications.
Koppel, Schler and Argamon (Reference Koppel, Schler and Argamon2010) showed that by randomly selecting subsets of features for multiple classifiers and then ensembling the results, the accuracy of a character n-gram-based model (not an LNG method) can be drastically improved. As far as the authors are aware, this concept has not been tested in LNG models, although Layton et al. (Reference Layton, Watters and Dazeley2011a) did use an ensemble-based method with different n and L values. It would be worth investigating if this type of technique can be used to improve the performance of LNG methods for anti-aliasing, improving on results mentioned in this paper. Given that LNG methods appear to be more robust to topic-based sub-aliases, the ensemble decision of them may further improve robustness again. We also consider an application in non-language-based applications, such as the authorship analysis of compiled malware, using low-level features like API calls (Alazab et al., Reference Alazab, Layton, Venkataraman and Watters2010).
Acknowledgment
This research was conducted at the Internet Commerce Security Laboratory and was funded by the State Government of Victoria, IBM, Westpac, the Australian Federal Police and the University of Ballarat. More information can be found at http://www.icsl.com.au.
