Fast Spammer Detection Using Structural Rank

Seungyeon Kim, Haesun Park, Guy LebanonarXiv 2014 · OpenReview

Abstract

Comments for a product or a news article are rapidly growing and became a medium of measuring quality products or services. Consequently, spammers have been emerged in this area to bias them toward their favor. In this paper, we propose an efficient spammer detection method using structural rank of author specific term-document matrices. The use of structural rank was found effective and far faster than similar methods.

Introduction

Web comments on news articles, products, and sports games are valuable sources of public sentiment, but they are frequently plagued by spammers. These bad actors use automated programs to flood platforms with repetitive propaganda, links, or gibberish. A common way to detect these spammers is by measuring the content similarity across all posts made by a single author; normal users post diverse thoughts, while spammers repeat themselves. However, traditional methods for measuring multi-document similarity—such as computing the average of all pairwise cosine similarities—are computationally expensive. Given the massive scale of modern social media, platforms need a way to measure this repetition that is both accurate and extremely fast.

Proposed Method

We model an author's comment history as a term-document matrix, where rows represent unique words and columns represent individual comments. If an author repeats the same content, the columns become linearly dependent, resulting in a lower mathematical rank for the matrix.

Instead of computing the true numerical rank using Singular Value Decomposition (SVD)—which is mathematically heavy—we utilize structural rank. Structural rank only looks at the pattern of non-zero entries in the matrix. Because short comments create extremely sparse matrices, structural rank can be computed using highly efficient bipartite graph traversal algorithms. The time complexity drops to practically $O(\tau + n)$, where $\tau$ is the number of non-zero entries.

We define a SpammerScore as: 1 - (Structural Rank / Number of Comments) * A score near 0 means the author uses diverse vocabulary (normal user). * A score near 1 means the author constantly reuses the exact same words (spammer).

Experimental Evaluation

The method was evaluated using the NBA dataset from the XDATA 2014 challenge, containing 352,936 comments from 42,382 unique authors across Yahoo Sports and ESPN. Standard NLP preprocessing (tokenization, stemming, and stop-word removal) was applied. The dataset analysis revealed that a very small number of authors (about 1,237) were responsible for 28% of all comments, highlighting the need for automated detection.

Key Results

Massive Computational Speedup

The structural rank method is orders of magnitude faster than traditional approaches. As shown in the table below, our proposed method processed the dataset in approximately 1.5 seconds, while the traditional average cosine similarity method took over 21,000 seconds—a speedup of over 14,000x.

Table 1: Computational time comparison between structural rank and traditional similarity methods.

Qualitative Effectiveness

The SpammerScore successfully stratified users. The distribution of scores shows that the majority of authors have low scores, indicating diverse, legitimate participation. Authors with high scores (0.8 - 1.0) were found to be posting literal copy-pasted spam, repetitive links, or identical strings of gibberish.

Figure 1: Distribution of SpammerScore across authors in the NBA dataset.

Conclusion

Structural rank provides a highly efficient and scalable proxy for detecting "copy-paste" spam behavior by exploiting the sparsity of web comment data. While the SpammerScore is a powerful standalone feature, it is best utilized as part of a broader machine learning classifier that incorporates other signals like posting frequency and user profile data.

Summary updated

Abstract

Comments for a product or a news article are rapidly growing and became a medium of measuring quality products or services. Consequently, spammers have been emerged in this area to bias them toward their favor. In this paper, we propose an efficient spammer detection method using structural rank of author specific term-document matrices. The use of structural rank was found effective and far faster than similar methods.
BibTeX
@misc{kim2014fast,
  author = {Seungyeon Kim and Haesun Park and Guy Lebanon},
  title = {{Fast Spammer Detection Using Structural Rank}},
  year = {2014},
  eprint = {1407.7072},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1407.7072},
}
Figure