Efficient and Effective Spam Filtering and Re-ranking for Large Web Datasets

Gordon V. Cormack; Mark D. Smucker; Charles L. A. Clarke

Source-linked AI summary

Efficient and Effective Spam Filtering and Re-ranking for Large Web Datasets

Gordon V. Cormack, Mark D. Smucker, Charles L. A. Clarke

arXiv:1004.5168v1Apr 29, 2010cs.IR

TL;DR

The paper asks how spam affects retrieval effectiveness in the large ClueWeb09 collection and how filtering can mitigate that impact. It develops and evaluates a simple labeling and filtering approach, finding substantial improvements across TREC 2009 web ad hoc and relevance feedback runs, while noting uncertainty about whether the filter captures spamminess alone.

Problem
The paper addresses limited quantitative evidence about spam’s impact on retrieval effectiveness and methods for mitigating it in large web collections.
Method
The paper develops a practical spam-labeling process and evaluates its percentile scores for filtering and reranking TREC 2009 retrieval runs.
Results
A simple on-line logistic regression filter dramatically improves the effectiveness of systems in the TREC 2009 web ad hoc and relevance feedback tasks.
Takeaways & Limitations
Spam filtering substantially improves retrieval effectiveness, providing a baseline for comparing labels and ways of using them in information retrieval.
Takeaways & Limitations
The authors note that improvements may reflect learning some aspect of page quality apart from spamminess, and incomplete relevance assessment may produce outliers.

Abstract

from arXiv · show

The TREC 2009 web ad hoc and relevance feedback tasks used a new document collection, the ClueWeb09 dataset, which was crawled from the general Web in early 2009. This dataset contains 1 billion web pages, a substantial fraction of which are spam --- pages designed to deceive search engines so as to deliver an unwanted payload. We examine the effect of spam on the results of the TREC 2009 web ad hoc and relevance feedback tasks, which used the ClueWeb09 dataset. We show that a simple content-based classifier with minimal training is efficient enough to rank the "spamminess" of every page in the dataset using a standard personal computer in 48 hours, and effective enough to yield significant and substantive improvements in the fixed-cutoff precision (estP10) as well as rank measures (estR-Precision, StatMAP, MAP) of nearly all submitted runs. Moreover, using a set of "honeypot" queries the labeling of training data may be reduced to an entirely automatic process. The results of classical information retrieval methods are particularly enhanced by filtering --- from among the worst to among the best.

1 Introduction

The paper studies how spam affects retrieval effectiveness in the large ClueWeb09 collection and develops practical ways to label and mitigate it. Its measurements show positive effects from filtering and reranking TREC Web Track results.

Dataset and problem: ClueWeb09 contains roughly 1 billion web pages, with TREC tasks using its English subset of about 500 million pages and some Category B runs using about 50 million.The collection was crawled from the general Web in early 2009.
Dataset and problem: The study addresses the lack of quantitative evidence about spam’s impact on retrieval effectiveness and evaluates the TREC 2009 web ad hoc and relevance feedback tasks.Its objectives were to label every ClueWeb09 page and quantify labeling quality through effects on contemporary IR methods.
Labeling approach: The paper provides downloadable percentile spam labels that support threshold-based classification or ranking pages by spamminess.The labels are part of a general labeling process requiring minimal computation and training.
Labeling approach: The labeling process includes variants using automatically labeled training examples, older dissimilar data, 2.5 hours of human adjudication, and a combined meta-ranking.These variants reduce or remove manual labeling requirements while offering alternative training strategies.
Results: The measurements show significant and substantive positive effects on fixed-cutoff precision and rank-based measures when spam labels filter or reorder submitted runs.The evaluation includes 50-fold cross-validation and examines all officially submitted TREC Web ad hoc and relevance feedback runs.

2 Context

ClueWeb09 exposed substantial spam-related problems in TREC 2009 retrieval, especially for Category A. The study therefore measured spam prevalence and evaluated filtering and reranking as possible remedies.

2 Context: Category A submitted runs had P@10 mean 0.25, standard deviation 0.11, and maximum 0.41, contrary to expectations for a large collection.Category B runs performed better, with P@10 mean 0.38, standard deviation 0.07, and maximum 0.56.
2 Context: Table 2 reports highly prevalent spam in top-ranked documents for both categories, with prevalence higher in Category A.The estimates came from independent Group X and Group Y assessments.
2 Context: Group X achieved P@10=0.38 on Category A ad hoc, while Group Y achieved P@10=0.16 despite using the same search engine and parameters as in Category B.The collection difference was Category A versus Category B.
2 Context: The authors attribute these contrasting outcomes plausibly to spam, hypothesizing a higher spam proportion in Category A than Category B.They sought to quantify spam in top-ranked pages and evaluate automatic mitigation.
2 Context: Group X adjudicated 756 pages and Group Y adjudicated 461 pages sampled from top-ten results using a web-based spamminess evaluation interface.The efforts took 2 hours 20 minutes and 1 hour 20 minutes, respectively.

3 Evaluation Measures

The evaluation framework combines classifier-oriented AUC with estimated precision and rank-based measures because TREC 2009 relevance assessments are sparse. It uses independent examples for training and evaluation while accounting for unknown relevance counts.

3 Evaluation Measures: Group X examples are used for training and tuning, while independent Group Y examples are reserved for evaluation.The groups used different topics, retrieval methods, and assessors, and Group X was independent of TREC.
3 Evaluation Measures: AUC evaluates how well filters identify spam and nonrelevant documents, while retrieval improvements are assessed with estimated precision at multiple cutoff values.AUC is threshold-independent; sparse assessments constrain the retrieval-effectiveness measures.
3 Evaluation Measures: Filtering requires estimating P@10 because unassessed lower-ranked documents rise into the top ten after spam removal.The Category B baseline also requires estimation because only a sample of submitted documents was assessed.
3 Evaluation Measures: The four candidate P@10 estimators are unjudged-nrel, unjudged-elided, statPC10, and estP10, each with distinct bias or stability concerns.Unjudged-nrel underestimates P@10; unjudged-elided can under- or overestimate it; statPC10 can underestimate or exceed 1.
3 Evaluation Measures: estP10 is more stable than statPC10 and equals P@10 when the top ten documents are fully adjudicated.It estimates relevant and non-relevant documents from sampled judgments and is nearly symmetric.
3 Evaluation Measures: The study reports estP10 as its primary measure and compares it with estR-Precision, StatMAP, MAP with unjudged nonrelevant documents, and MAP with unjudged elided.The other three measures produced similar results and the same conclusions.
3 Evaluation Measures: Because R and most rel(k) values are unknown, AP estimation is unreliable for TREC 2009, motivating R-precision and estimated rank measures.R-precision depends on R, but estimation errors have much lower impact because R is not a direct factor in its formula.

4 Spam Filter Design

The paper uses a fast content-based linear classifier to score spamminess across ClueWeb09, training filters from several example sources and combining their scores. Pages are represented with hashed binary byte 4-grams, and percentile scores support filtering or ranking.

Training filters: Three filters used UK2006, automatically generated Britney, and Group X training examples; a naive Bayes fusion combined their scores.The fusion interpreted the component scores as log-odds estimates and averaged them.
Classifier: Online gradient-descent logistic regression trained a linear classifier in one pass, then assigned each English page a spamminess score.The score can be interpreted as a log-odds estimate, although training–test mismatch may bias it.
Filtering operation: Percentile scores rank pages by spamminess and define thresholds in which the spammiest t% of the corpus is filtered.A threshold of t = 0 filters nothing, whereas t = 100 filters everything.
Feature representation: Pages were treated as flat text and represented by binary overlapping byte 4-grams, with hashing reducing the feature space from 4 × 10^9 to 10^6 dimensions.Pages longer than 35,000 bytes were truncated, and term and document frequencies were not used.

5 Filter Results

The filters strongly identified spam and nonrelevant pages and substantially improved retrieval effectiveness across TREC 2009 web ad hoc and relevance-feedback runs. The fusion filter performed best overall, with optimal thresholds differing between Category A and Category B.

Spam identification: 0.94 for Category A and 0.90 for Category B were the UK2006 filter’s spam-identification AUC results.These results were comparable to the best reported for the 2007 AIRWeb Challenge, and the fusion filter performed better still.
Relevance impact: Spam-filter AUC scores for nonrelevant-document identification were only slightly lower than those for spam identification.The evaluation used official TREC relevance assessments on the same documents labeled by Group Y.
Average effectiveness: p ≪0.001 supported the superiority of the non-control filters in average estP10 effectiveness.All filters except the random control rose substantially before falling off as more of the corpus was labeled spam.
Threshold behavior: The fusion filter peaked at t = 70 for Category A and t = 50 for Category B, while other filters continued improving for Category A and plateaued for Category B beyond t = 50.These thresholds were used to illustrate effects on individual submissions.
Run-level consequences: Filtering substantially improved relevance-feedback runs and improved a simple query-likelihood method from the worst unfiltered Category A result to better than the best unfiltered result.The relevance-feedback baselines were stronger but still improved substantially.

6 Reranking Method

The paper replaces hard spam filtering with supervised reranking that uses spam scores alongside the original search ranking. Applied to TREC Category A submissions, this approach substantially improves effectiveness across nearly all runs and multiple rank measures.

Reranking versus filtering: Spam scores are used to reorder search results rather than eliminate high-scoring documents outright.Documents with higher spam scores are moved lower in the ranking.
Learning the reranking function: Supervised learning computes a new ranking from the original ranking and spam percentile scores.The method uses the original ranking and spam scores as inputs to learn how documents should be reordered.
Learning the reranking function: 50-fold cross-validation evaluates one TREC topic at a time while treating the other 49 topics as historical training examples.This substitutes for historical query results, which were unavailable for the experiments.
Learning the reranking function: Exhaustive threshold enumeration and greedy list construction produce the reranked list for each submission.For every k, the method finds the threshold optimizing estP_k, then greedily builds the new ranking.
Effectiveness: All reported measures show substantial improvement for nearly all Category A runs after reranking.The evaluation includes estP30, estP300, estRP, StatMAP, and MAP; watwp is a notable exception because it consists entirely of Wikipedia documents.

7 Discussion

The discussion frames spam as a previously unquantified threat to retrieval effectiveness and reports that simple content-based filtering substantially improves TREC results. It also identifies incomplete relevance assessment and the future availability of graph-based metrics as important boundaries on interpretation and extension.

Motivation: The paper addresses a gap in quantitative evidence about how Web spam affects retrieval effectiveness and how filtering mitigates that impact.Earlier work measured spam prevalence or detection but had not reported relevance-based quantitative impact.
Main findings: A simple online logistic regression filter dramatically improves TREC 2009 web ad hoc and relevance feedback results, including submissions from major Web search providers.The authors interpret the improvement as evidence that spam’s retrieval impact is substantial, while noting that filters might also learn other page-quality signals.
Interpretation: The interpretation remains compatible with filters learning static relevance in addition to spamminess, although the authors find that explanation unlikely based on AUC scores.The authors state that the distinction is practically moot if filtering improves retrieval effectiveness either way.
Scope and future comparison: Graph-based quality and spam metrics for ClueWeb09 were unavailable at writing, limiting direct comparison with that major methodological alternative.The authors suggest later comparison or combination could produce a meta-filter.
Robustness across systems: Reranking improves already filtered submissions, including yhooumd00BGM from P@10 0.4040 to 0.4724 and uvamrftop from 0.4100 to 0.4855.The paper also reports twJ48rsU improving from 0.2380 to 0.2801.
Reproducibility: The four sets of percentile scores are available for download, at about 350MB compressed and 16GB uncompressed each.The release supports experimentation with the filtering and reranking approaches.