PolaritySpam: Propagating Content-based Information Through a Web-Graph to Detect Web Spam

POLARITYSPAM: PROPAGATING CONTENT-BASED INFORMATION THROUGH A WEB-GRAPH TO DETECT WEB-SPAM F. Javier Ortega, Jose´ A. Troyano, Ferm´ın L. Cruz and Carlos G. Vallejo Department of Languages and Computer Systems University of Seville Avda. Reina Mercedes, s/n, 41012, Seville, Spain { javierortega; troyano; fcruz; vallejo }@us.es Abstract. Spam web pages have become a problem for Information Retrieval systems due to the negative effects that this phenomenon can cause in their results. In this work we tackle the problem of detecting these pages with a propagation algorithm that, taking as input a web graph, chooses a set of spam and not-spam web pages in order to spread their spam likelihood over the rest of the network. Thus we take advantage of the links between pages to obtain a ranking of pages according to their relevance and their spam likelihood. Our intuition consists in giving a high reputation to those pages related to relevant ones, and giving a high spam likelihood to the pages linked to spam web pages. We introduce the novelty of including the content of the web pages in the computation of an a priori estimation of the spam likelihood of the pages, and propagate this information. Our graph-based algorithm computes two scores for each node in the graph. Intuitively, these values represent how bad or good (spam-like or not) is a web page, according to its textual content and its relations in the graph. The experimental results show that our method outperforms other techniques for spam detection. Keywords: Information retrieval, Web spam detection, Graph algorithms, PageRank, Web search 1. Introduction. Together with the appearance of the first web search engines intended to provide the users with a set of relevant web pages given a user information need or query, many companies came up for the purpose of offering the clients not only the creation of a web site, but also the maximum visibility for them. It was usually done by taking advantage of the mechanisms of the web search engines to rank the web pages according to their relevance in addition to their similarity to the user query. The first approaches to achieve this goal used keyword stuffing methods, based on the inclusion of some frequent words in order to get a web page to be highly ranked. Web Spam was firstly known in the literature as search engine persuasion [18], due to its goal of making a web page more visible by taking advantage of the search engines. Later, it took the name of spam from the similar method that was being used for the massive sending of advertisements and fraudulent or simply annoying messages in newsgroups and e-mails. Web spam mechanisms have evolved from those first attempts becoming more sophisticated, in parallel to search engines counter-measures. Basically, web spam is a phenomenon where web pages are manipulated for the purpose of obtaining some kind of benefits by illicitly gaining web traffic. Nowadays, spammers use a wide variety of methods intended to make a search engine deliver undesirable results and rank these web pages higher than they would otherwise [21]. There are two basic forms of web spam: Self and Mutual promotion [5]. Self promotion tries to create a web page that gains high relevance for a search engine, mainly based on its content. It can be achieved through many techniques, such as the above mentioned keyword stuffing, in which visible or invisible keywords are inserted in the page, in order to improve its rank for the most common queries. Mutual promotion is based on the cooperation of various sites in order to benefit each other. It usually implies the creation of a wide number of web pages that form a link-farm, which is a large number of pages pointing one to another, in order to improve their scores by increasing the number of in-links to them. This method is effective against search engines that employ co-citations between pages as features (e.g., PageRank [23]). There are several approaches intended to deal with the problem of web spam using different information sources to decide whether a web page is spam or not. Some techniques are based on document classification approaches and try to identify the spam web pages according to some features. Other techniques are focused on the computation of a ranking of web pages, trying to demote the spam web pages in the last positions of the ranking. The intuition behind these methods is that a user who uses a web search engine will take mainly the top ranked documents retrieved by the system, so the goal is to avoid the appearance of spam web pages in those first positions. In this work, we introduce a novel method that computes a ranking of web pages according to their spam likelihood. It is based on a propagation algorithm that spreads over the graph the information about the spam or not-spam likelihood of the web pages. This information is computed regarding the textual content of the pages. Unlike other web spam detection systems, our method does not need any human intervention in the process. In spite of this, it achieves very good results in the task. The organization of the rest of the paper is as follows. In the next section, we discuss other works that tackle the problem of web spam detection from different points of view. In Section 3, we introduce the intuition behind our approach, and explain the components of our method: the set of content-based metrics, and the way in which these heuristics are used in the creation of the graph model. The experimental design and results are shown in Section 4. Finally, we remark on our conclusions concerning the present work, and talk about some ideas for future works. 2. Related Work. As mentioned above, one of the most common methods for web spam detection are content-based techniques. These methods are focused on determining whether a page is spam or not according to its textual content. Mishne et al. [19] propose the comparison of language models to classify texts as spam or non-spam. In [15], Kolari et al. present a machine learning technique based on SVM, taking as features different heuristics such as the anchor text of the links in a web page, the tokenized URL of the page, or the meta-tag text. In [22], several spam detection metrics are proposed. They compare the values of these content-based metrics for spam and not-spam web pages, and discuss the discrimination ability of each metric to detect spam. Some of the proposed heuristics are the number of words in the title of a web page, the average length of words, the amount of invisible content, the compression rate of the web pages, the fraction of anchor text with respect to the total amount of text in a page, etc. Other works focus their attention in the selection of features that optimize the performance of the spam detection systems [17]. On the other hand, link-based techniques focus on the structure of the graph made up of the web pages and the hyperlinks among them. These methods study the relations of the pages in the web graph, aiming to detect the link-farms of spam web pages (see Figure 1). The basic assumption to deal with link-farms is that similar objects are related to similar objects in the web graph [13]. In the context of web spam, it means that non-spam web pages are frequently related to other non-spam web pages, and vice versa. Link-based methods are intended to deal with the mutual promotion mechanisms. Figure 1. Graphical representation of a link-farm of web pages: a set of web pages with a high number of links between them The key assumption in [2] is that supporters of a non-spam page should not be overly dependent on one another. In other words, if the supporters of a web page have a large numbers of links between them, they likely form a link-farm and could be spam web pages. An example of suspicion is the case of a page that receives its PageRank from a large number of very low ranked pages. The proposed algorithm obtains the supporters of each page, then studies the distribution of their PageRank scores in order to compute a PageRank biased according to a vector of penalizations. Truncated PageRank [1] tackles also the problem of the link-farms. It penalizes pages that obtain a large share of their PageRank from the nearest neighbors, avoiding the effect of the supporters that are topologically very close to a given node. TrustRank [9] is based on the idea that a high PageRank score held on a huge amount of links from pages with low PageRank, is suspicious of being spam. It means that a node with high PageRank and no relations with others pages with high PageRank is likely to be a spam web page. They obtain an estimator for this metric by calculating the estimated non-spam mass, that is the amount of PageRank received from a set of (hand-picked) trusted pages. TrustRank takes as input the web graph, and a set of hand-picked nonspam web pages. In contrast, [16] proposes an algorithm with the same idea, but taking as input a set of spam web pages. This technique, called Anti-TrustRank, computes the estimated spam mass for each node. Both methods need some human intervention in order to choose the set of sources for the ranking algorithms. This fact limits the number of sources that can be taken into account by both methods. In [25], Wu et al. propose an approach based on trust and distrust propagation. This work consists in an algorithm that computes two scores for each node in the graph, indicating the levels of trust and distrust of a page. The process starts from two source sets, trustworthy and spam pages, respectively. A system that combines content-based and link-based features is proposed in [4]. They discuss three methods to include features related to the web graph topology into a classifier. Some well-known algorithms are used in this work, such us PageRank or the above mentioned TrustRank and Truncated PageRank. Similar ideas has been applied to enhance the performance of other information retrieval systems [10, 24]. The impact of spam in information retrieval systems, and the effects of some anti-spam filters are studied in [5]. They use three filters in this work, and a naive Bayes classifier to combine all of them. The first filter is a classifier built from a labeled corpus with spam and non-spam pages. The second one consists of a set of documents retrieved by some of the most popular queries to a web search engine. And finally a set of documents extracted from the Open Directory Project1. They show the improvements achieved in some of the systems participants in TREC 20092applying a spam detection technique. 3. PolaritySpam. Both link-based and content-based techniques have been shown to be reliable methods for web spam detection, although they present some vulnerabilities that can be easily exploited by spammers. In this section we present PolaritySpam as our proposal for web spam detection. It is a method that includes concepts from link-based and content-based techniques, combining the strongest points of them. PolaritySpam is based on similar ideas as PolarityRank [7], a ranking algorithm over graphs with positive and negative weights in its edges. This algorithm propagates the information of a set of positive and negative seeds through the graph, obtaining the polarity of the rest of nodes. The intuition behind PolaritySpam is the propagation of spam and not-spam likelihood of web pages over the web graph. It relies on the assumption that similar objects are related to similar objects in the web graph [13]. So every web page related to a spam-like web page must be considered as spam, and vice versa. In other words, each page propagates its spam likelihood to their neighbors, so every web page will receive good or bad reputation regarding to the pages that are pointing to them. PolaritySpam consists in a propagation algorithm that computes two scores for each node: a positive score representing the authority of a web page, and a negative score which represents the spam likelihood of a page. The difference between both scores is taken into account in order to build a ranking of web pages. Intuitively, this value represents the overall relevance of a web page. In this way, web pages with high negative scores are demoted in the final ranking, because they are likely to be spam. Following this reasoning, we need some kind of a priori knowledge about the web pages in order to determine their spam likelihood before starting the propagation. At this point, we propose the use of some heuristics to extract this information from the textual content of the pages. These metrics are the basis of an automatic process intended to obtain an a priori score for each page, weighting their spam likelihood. Then, we compute aspam-biased random-walk algorithm to propagate this a priori information through the web graph. We take advantage of the links in the graph to spread the contentbased information over the network. In this way, we can promote those pages related to relevant web pages, because they will receive high positive scores. On the contrary, those web pages related to spam-like pages are demoted in the ranking because they will receive high negative scores. In Figure 2, we show the general schema of our system. It consists of three components: the A-priori Information Extractor that processes the textual content of the web pages in order to obtain a score representing their spam likelihood; the Selector of Sources that automatically selects two sets of spam and not-spam like web pages, respectively, regarding the a priori information previously computed; and the Propagation Algorithm that processes the web graph, propagating the a priori information of the sources according to the links between the web pages. In this work, we propose three variations for our system. Each method automatically selects a number of pages (namely sources) to spread their positive or negative influence to the rest of the network. Then, they specify the weight of each source to be propagated. Since we compute two scores for each page, we need two sets of sources, each of them 1http://www.dmoz.org 2http://trec.nist.gov Figure 2. Structure of our spam detection system intended to reinforce the positive or negative relevance of each type of web pages in the graph. Thus, the first set of sources must contain a group of non-spam pages, and the second one consists in a group of spam pages. Isolated pages, i.e., pages without any in-links or out-links are also a problem for random-walk algorithms. Indeed, despite not being able to obtain any feedback from their neighbors, the textual content itself provides useful information to obtain a spam likelihood score for these pages. In the remainder of this section, we discuss the content-based metrics and their role in our system (Section 3.1), the automatic methods to obtain the sets of sources (Section 3.2), and finally the algorithm proposed to propagate the content-based information of the web pages over the network (Section 3.3). 3.1. Extracting a priori information. The intuition behind the use of the contentbased metrics in conjunction with a random-walk algorithm lies on the propagation of the spam likelihood of the web pages over the graph. We propose the use of the information provided by the textual content of the web pages as spam likelihood indicators. In this way, we provide some a priori information to our system in order to begin the propagation graph-based algorithm. The aim behind this idea is to increase the ranking of the good web pages and penalize the bad ones, regarding the content of the pages in addition to the link structure of the graph. The content-based metrics that we use in the experiments of this work have been chosen according to their discrimination capacity, distinguishing between spam and not-spam web pages, as identified by [22]. Another important factor to select these metrics is their computational complexity. Following these criteria, we have implemented two heuristics: •Compressibility: is defined as the fraction of the sizes of a web page, x, before and after being compressed. Compressibility(vj) = GZIPSize(vj) TotalSize(vj) A web page with a very high compressibility value, is likely to be a spam. This heuristic is intended to detect repeated content or words in a web, because more redundant content leads to a higher compression ratio. •Average length of words: non-spam web pages have a bell-shaped distribution of average word lengths, while malicious pages have much higher values of this metric. Hence, this heuristic penalizes the use of word stuffing mechanisms. In the next section, we explain the different ways of including these heuristics into our system. 3.2. Selection of sources. PolaritySpam uses the content-based heuristics to automatically assign a priori scores to some specific pages (henceforth called sources), regarding their spam or not-spam likelihood. A given page will be demoted or promoted in the final ranking according to its relations with these sources. We use sources sets to ensure that negative scores of negative pages will be propagated over the graph, and analogous for the positive sources. The sources sets are represented in our approach by two spam-biased vectors, e+and e−. The vectors contain the spam and non-spam likelihoods of the web pages taken as sources in our algorithm, giving higher positive or negative scores to those nodes that have higher e+or e−(see Equations (4) and (5)). In this section, we introduce three different ways to characterize the spam-biased vectors, given the heuristics of each web page. 3.2.1. Most spamy/not-spamy sources (S-NS). This first method chooses the Nmost spam-like and not-spam like pages in the graph as sources, according to their metrics. Formally, given a page vj, let M(vj) be a vector with the content-based metrics for vj. The spam likelihood of vjwill be determined by the norm of M(vj), as shown in Equation (1): Spaminess(A) = √∑ h∈M(vj) h2(1) where Ais a web page, and hrepresents the heuristics which M(vj) contains. In this way, we take the Nnodes with highest Spaminess as negative sources, and the Nnodes with lowest Spaminess as positive sources. The spam-biased vectors can be defined as follows: e+ i={1/N if i∈S+ 0 otherwise (2) where Nis a parameter that specifies the number of sources that will be taken. S+is the set of the Nnodes with lowest Spaminess in the graph. The formula is analogous for vector e−. 3.2.2. Content-based weighted spamy/not-spamy sources (CS-NS). Following the previous schema, we can take advantage of the content-based metrics by including the actual scores directly in the computation of the weights of the sources, as shown in Equation (3): e+ i={Spaminess(i) ∑j∈S+Spaminess(j)if i∈S+ 0 otherwise e− i={Spaminess(i) ∑j∈S−Spaminess(j)if i∈S− 0 otherwise (3) where Spaminess(i) is the norm of the vector built from the metrics of the page i(see Equation (1)). 3.2.3. Content-based graph sources (C-GS). The last method consists in applying the previous formula to every nodes in the graph. We can rely on the thresholds proposed in the study in [22], and use them to determine whether a page must be a negative or a positive source. The thresholds for the metrics considered in the present work are shown in Table 1. Given a page, if one of its metrics is above the corresponding threshold, we include the page in the set of negative sources, and in other case it will be taken as a positive source. Once the sets of nodes have been defined, we apply the same formulas shown in Equation (3). Table 1. Thresholds for the content-based metrics Heuristics Threshold Compressibility 6.0 Average length of words 9.0 3.3. Propagation algorithm. As mentioned above, we propose a propagation algorithm in order to spread over the graph the information extracted by the content-based metrics, and to compute a ranking of the web pages according to their relevance. This algorithm is intended to demote the spam web pages in the overall ranking by computing two scores for each page, PR+and PR−. Given a page A, it is desirable that its positive score, PR+, depends on the good pages pointing to A, and analogous for the negative score, PR−. In other words, we want the spam web pages to propagate their negative scores to their neighbors, and the positive pages do the same with their positive scores. With this aim, two vectors, e+and e−, are built based on a set of content-based metrics from each page. These spam-biased vectors are used in the computation of our random-walk algorithm, representing the non-spam and the spam likelihoods of a page, respectively. They can be thought of a reinforcement for the positive and negative scores of each page. Having said that, the proposed scores are obtained as shown in Equations (4) and (5) below: PR+(vi) = (1 −d)e+ i+d∑ j∈In(vi) PR+(vj) |Out(vj)|(4) PR−(vi) = (1 −d)e− i+d∑ j∈In(vi) PR−(vj) |Out(vj)|(5) where viis a node of the graph (a web page), In(vj) is the set of nodes pointing to vj, and Out(vj) is the set of nodes which vjpoints to. Both scores, PR+and PR−, are obtained with a PageRank-like algorithm. The algorithm iterates over the nodes in the graph, applying Equations (4) and (5). This process is performed until the maximum difference between the scores in one iteration and the previous one, is lower than a given threshold. This algorithm has the same time complexity as the original one. Once the propagation algorithm is finished, a ranking of web pages is built regarding the difference between PR+and PR−for each node, as shown in Equation (6). score(vi) = PR+(vi)−PR−(vi) (6) 4. Experiments. In this section, we show the experimental design defined to show the performance of PolaritySpam, as well as the dataset used and the results obtained. We also detail the values of the parameters for each set of experiments, and the different variants proposed in this work. The aim of the experiments is to show the performance of PolaritySpam in terms of the demotion of spam web pages in the resulting ranking, in order to asses its usefulness in the web spam detection task. The results of PolaritySpam are compared to a state-of-art web spam detection technique, TrustRank [9], which achieves very good results in this task. Since PolaritySpam does not classify the web pages between spam or non-spam, it does not make sense to perform an evaluation in terms of classification accuracy. On the other hand, we use in our experiments the same evaluation method followed in other works on the application of graph-based algorithms to the spam detection task [2, 9]. This kind of spam detection techniques are based on the fact that a user usually looks only at the top ranked documents of a result set, ignoring the rest of lower-ranked documents. So the goal of ranking algorithms in the web spam detection task is to demote the spam web pages in such way that they became less visible to the users due to their low rankings. Therefore, the evaluation methods applied in this work take into account the positions obtained by the spam web pages in the rankings computed by the implemented techniques, in order to measure their performance. The organization of the rest of this section is as follows. The dataset used in the experiments is presented in Section 4.1. The evaluation methods are explained in Sections 4.2 and 4.3. In Section 4.4, we present the TrustRank algorithm, taken as baseline in the evaluation. Finally, we show the experimental results for all the techniques in Section 4.5, comparing the results of the techniques to the TrustRank algorithm using some useful evaluation metrics. 4.1. Dataset. The corpus used in the experiments is the WEBSPAM-UK2006 Dataset [3], a huge collection of web pages specifically crawled for researching on spam detection. It contains more than 98 million pages. The collection is based on a crawl of the .uk domain performed in May 2006. It was collected by the Laboratory of Web Algorithmics, Universit`a degli Studi di Milano, with the support of the DELIS EU-FET research project. The collection was labeled by a group of volunteers and/or by domain-specific patterns such as .gov.uk or .ac.uk. Of the 11,402 hosts in UK2006 dataset, 7,423 are labeled as spam or non-spam. For the evaluation purposes, we have considered as spam any web page that belongs to a host labeled as spam. There are about 10 million spam web pages in the collection. 4.2. Evaluation with PR-buckets. Since the position of spam web pages in the ranking of documents is the key of our spam detection technique, we focus on this feature in order to evaluate the performance of our approaches. In this section, we explain the PR-buckets method, introduced in [9] to evaluate their proposal. The aim of this method is to easily get a qualitative evaluation by determining the number of spam web pages detected mainly in the highest positions of the ranking of web pages, that are the most pernicious for the performance of a web search engine. This evaluation method is implemented as follows. First, a list of pages is generated in decreasing order of their PageRank score. This list is segmented into 20 buckets, in such way that each of the buckets contains a different number of sites, with scores summing up to 5% of the total PageRank score. The sizes of these PR-buckets are taken to build a similar set of buckets using the rankings computed by each web spam detection method. In this way, given N1, the size of the first PR-bucket, we take the N1top ranked web pages for each technique in order to build the first bucket corresponding to each result set, and so forth. The number of spam web pages per bucket is our evaluation metric. It is obtained by counting the number of pages in each bucket that are labeled as “spam” in the dataset. The aim of a spam detection technique is to avoid spam web pages into the first buckets (top positions of the ranking), demoting these pages in order to put them into the last buckets. 4.3. Evaluation with nDCG. Another method intended to evaluate the results of ranking algorithms is the Normalized Discounted Cumulative Gain [20] (nDCG), a well-known metric widely used in Information Retrieval for the evaluation of a set of retrieved documents given a query. This metric measures the quality of a ranking of documents, penalizing the appearance of top-ranked irrelevant documents in the results. It is based on the Discounted Cumulative Gain (DCG), computed as follows: DCG =Relevance1+ N ∑ i=2 Relevancei log i where Nis the total number of documents in the collection, and Relevancei= 1 if document in the i-th position is relevant (in our case, a relevant document is a not spam web page), and zero in other case. As we can see, the higher are the positions of irrelevant documents in the ranking, the lower is the DCG score of the ranking. nDCG is obtained by normalizing the previous score using the IDCG, that is the best DCG that can be achieved with the given dataset: IDCG = |Relevance| ∑ i=1 1 log i The normalized score is obtained as follows: nDCG =DCG IDCG where 0 ≤nDCG ≤1, corresponding nDCG = 1 to the perfect system that gets all the irrelevant documents ranked in the last positions of the ranking. So, with nDCG we can evaluate the performance of each technique in terms of the demotion of spam web pages in the ranking. 4.4. Baseline: TrustRank. TrustRank algorithm [9] is a link-based algorithm that takes as input the web graph and a set of non-spam web pages, chosen in a semi-supervised way, that are the sources for the algorithm. The output is a ranking of web pages according to their relevance, in which the spam web pages are demoted. TrustRank computes a score for each web page, similarly to PageRank, using the source set to include a bias in the random-walk algorithm. In order to build the source set, they propose an inverse PageRank algorithm, that computes a ranking of web pages, but taking into account the outlinks of the web pages instead of their inlinks. Once the inverse ranking has been built, they choose by hand the Ntop-ranked non-spam web pages from that ranking. In this way, they try to take as sources the Ngood pages that reach as many nodes as possible, trying to maximize the propagation of the information from these sources. The disadvantage of this method is that human intervention is required, so it is expensive to consider a high number of web pages as sources due to the manual effort needed. We test this technique with the UK2006 dataset, and it achieves very good results. The results shown in Figure 3 have been obtained by performing 20 iterations of the algorithm