ORFEL: Efficient detection of defamation or illegitimate promotion in online recommendation

Abstract

What if a successful company starts to receive a torrent of low-valued (one or two stars) recommendations in its mobile apps from multiple users within a short (say one month) period of time? Is it legitimate evidence that the apps have lost in quality, or an intentional plan (via lockstep behavior) to steal market share through defamation? In the case of a systematic attack to one’s reputation, it might not be possible to manually discern between legitimate and fraudulent interaction within the huge universe of possibilities of user-product recommendation. Previous works have focused on this issue, but none of them took into account the context, modeling, and scale that we consider in this paper. Here, we propose the novel method Online-Recommendation Fraud ExcLuder (ORFEL) to detect defamation and/or illegitimate promotion of online products by using vertex-centric asynchronous parallel processing of bipartite (users-products) graphs. With an innovative algorithm, our results demonstrate both efficacy and efficiency – over 95% of potential attacks were detected, and ORFEL was at least two orders of magnitude faster than the state-of-the-art. Over a novel methodology, our main contributions are: (1) a new algorithmic solution; (2) one scalable approach; and (3) a novel context and modeling of the problem, which now addresses both defamation and illegitimate promotion. Our work deals with relevant issues of the Web 2.0, potentially augmenting the credibility of online recommendation to prevent losses to both customers and vendors.

Introduction

In the Web 2.0, it is up to the users to provide content, like photos, text, recommendations and many other types of user-generated information. The more interaction, e.g., likes, recommendation, comments, etc., a product page (or a user profile) gets, the better are the potential profits that a company (or an individual) may achieve with automatic recommendation, advertisement, and/or priority in automatic search engines. In Google Play, for example, mobile apps heavily depend on high-valued (4 or 5 stars) recommendations to get more important and to expand their pool of customers; on Amazon, users are offered the most recommended products, that is, those that were better rated; and in TripAdvisor, users rely on other’s feedback to pick their next travels. The same holds for defamation, which is the act of lowering the rank of a product by creating artificial, low-valued recommendations. Sadly, fraudulent interaction has come up in the Web 2.0 – fraudulent likes, recommendations, and evaluations define artificial interests that may illegitimately induce the importance of online competitors.

Attackers create illegitimate interaction by means of fake users, malware credential stealing, Web robots, and/or social engineering. The identification of such behavior has great importance to companies, not only because of the potential losses due to fraud, but also because their customers tend to consider the reliability of a given website as an indicator of trustfulness and quality. According to Facebook [11], fraudulent interaction is harmful to all users and to the Internet as a whole, so it is important that users have a true engagement around brands and content.

However, catching up with such attacks is a challenging task, especially when there are millions of users and millions of products being evaluated in a system that deals with billions of interactions per day. In such attacks, multiple fake users interact with multiple products at random moments [1] in a way that their behavior is camouflaged among millions of legitimate interactions per second. The core of the problem is: how to track the temporal evolution of fraudulent user-product activity since the number of possible interactions is factorial?

We want to identify the so-called lockstep behavior, i.e., groups of users acting together, generally interacting with the same products at around the same time. As an example, imagine that an attacker creates a set of fake users to artificially promote his e-commerce website; then, he would like to comment and/or recommend his own Web pages, posts, or advertisements to gain publicity that, fairly, should come from real customers. Here, an attacker may refer to employees related to a given company, professionals (spammers) hired for this specific kind of job, Web robots, or even anonymous users. The weak point in all these possibilities is that the attacker must substantially interact with the attacked system within limited time windows; also, the attacker must optimize his efforts by using each fake user account to interact with multiple products. This behavior agrees with the lockstep definition. Note that this pattern is well-defined in online recommendation and in many other domains, such as academic co-citation, social network interaction, and search-engine optimization. Provided that this is not a new problem, we use in this paper the definition of lockstep behavior given by Beutel et al. [4]. See the upcoming Section 3.3 for details.

The task of identifying locksteps is commonly modeled as a graph problem – nodes are either users or products; weighted edges represent recommendations – in which we want to detect near-bipartite cores considering a given time constraint. The bipartite cores correspond to groups of users that interacted with groups of products within limited time intervals. One lockstep may be defamation, when the interactions are negative (low-valued) recommendations; or illegitimate promotion, when the recommendations are positive. Therefore, the problem generalizes to finding near-bipartite cores with edges whose weights correspond to the rank of the recommendations. Note that we want to tackle the problem without any previous knowledge about suspicious users, products, nor the moments when frauds occurred in the past.

This work extends the state-of-the-art solutions for the problem of lockstep identification. Our main contributions are threefold:

• Novel algorithmic paradigm: We introduce the first vertex-centric algorithm able to spot lockstep behavior in Web-scale graphs using asynchronous parallel processing; vertex-centric processing is a promising paradigm that still lacks algorithms specifically tailored to its modus operandi;

• Scalability and accuracy: We tackle the problem for billion-scale graphs in one single commodity machine, achieving efficiency that is comparable to that achieved by state-of-the-art works on large clusters of computers, whilst obtaining the same efficacy;

• Generality of scope: We tackle the problem for real weighted graphs ranging from social networks to e-commerce recommendation, expanding the state-of-the-art of lockstep semantics to discriminate defamation and illegitimate promotion.

This paper follows a traditional organization. Section 2 presents background concepts, while Section 3 reviews the related works. Our proposal is described in Section 4. In Section 5, we report experimental results, including real data analyses. Finally, Section 6 concludes the paper and presents ideas for future work.