Online Reputation Fraud Campaign Detection in User Ratings

1 Introduction

Crowdsourced online ratings have been an informative source for users to assess the quality of various items, such as product ratings on Amazon and Page Likes on Facebook. As being more influential, these ratings are capable of affecting the profitability of items being evaluated [Forman et al., 2008]. While positive ratings could boost item reputation and bring increase in sales, negative commentary could damage public image and lead to business failure. This, however, has spurred the rise of an underground business, where fake ratings are crafted by spammers to either promote or degrade item reputation [Jindal and Liu, 2008; De Cristofaro et al., 2014]. To stay ahead of defensive systems, spammers are constantly evolving. They are found recently to rely on astroturfing [Xu et al., 2015; Wang et al., 2014] to commit large-scale fraud practices. With popular crowdsourcing services, spammers now can easily orchestrate reputation fraud campaigns (RFCs) that take advantage of the efforts of multiple users [Fayazi et al., 2015]. Figure 1 shows a real RFC found in a crowdsourcing platform, which is described as a crowdsourcing task instructing each spammer to leave a positive rating (with monetary rewards) for a targeted item during a specific time period.

when seeking for online solutions. First, many existing features for RFC detection are not suitable for online scenarios; they are designed to capture occurred campaigns, but cannot effectively handle emerging campaigns due to the lack of collectible evidence when the campaigns are still in progress. Second, the rating data collected in online settings are incomplete and sparse, which could in turn cause the sparsity of the features and deteriorate the models built on the features.

In this paper, to overcome the above issues, we propose a novel and unified framework, FRAUDSCAN, to conduct RFC detection online. In this framework, instead of directly comparing RFCs with normal activities, internal interactions between campaign members are exploited. Such interactions are presumably more indicative of emerging campaigns, since they become observable once the campaigns have begun. In addition, to effectively model the sparse rating behaviors, FRAUDSCAN takes an embedding-based approach to compactly encode user-rating-item relations with dense embeddings. A novel campaign-aware optimization scheme is also proposed for efficient online update. Results of extensive experiments on two real datasets show the superiority of the proposed framework over state-of-the-art methods in both detection accuracy and efficiency.

2 ProblemFormulation and Challenges

We introduce the notations and definitions related to the studied problem. To adapt built detection model to constantly changing campaign strategies, we formulate the task of online reputation fraud campaign detection and identify the challenges of fulfilling this task.

Assume that there is a set of n items V = {vj}nj=1 receiving ratings from a set of m users U = {ui}mi=1 . A typical item rating consists of four fundamental elements: a user id specifying the subject giving the rating, an item id referring to the rated item, a numerical star instantiating the rating, and a timestamp recording the time of the rating. We use a 4tuple rij =< ui, eij, vj, tij > to represent an item rating rij generated by user ui for item vj with star eij at time tij.

Definition 1 Along the time dimension, we can observe a rating sequence comprised of an unbounded series of incoming ratings in temporal order {rt}, with timestamp t = {1, 2, 3, ...}. Denote U t and V t as the sets of users and items up to time t respectively, and a rating matrix Rt ∈ R|U t |×|V t | as all the ratings from U t to V t .

Definition 2 A reputation fraud campaign (RFC) consists of a group of campaigned spammers who are asked to conduct reputation fraud on a set of targeted items. A RFC can be denoted by a 3-tuple < Uc, Rc, Vc > with Vc the set of targeted items, Rc the set of created ratings, and Uc the set of involved campaigned spammers.

Definition 3 To quantify the tendency of a user to participate in RFCs, a real-valued spamicity score stu ∈ R+ is assigned to each user u ∈ U t at time t. A ranked list of κ users with the largest spamicities Stκ will be produced as the detection result at time t.

Given the definitions above, we formulate the task of online reputation fraud campaign detection as below: Given the old rating matrix Rt-1 at time t - 1, the model Mt-1 learned from Rt-1 , and the detection result St-1 κ , upon a new rating comes in at time t, the goal is to efficiently update the new model Mt for reputation fraud campaign detection on the current rating matrix Rt , and output the up-to-date detection result Stκ .

The fulfillment of the above task, however, requires two challenges to be addressed. The first is concerned with effective emerging campaign characterization. Various features have been proposed to characterize occurred campaigns on different dimensions. For example, deviationbased features [Lim et al., 2010; Mukherjee et al., 2012; 2013] are commonly used to capture the differences between the ratings given by spammers and the remaining users. However, when dealing with emerging campaigns, if an item has not yet received sufficient ratings to form a general "groundtruth" rating at the beginning, the deviation of any incoming rating at this point would be no longer statistically significant to indicate manipulation. Another example is the profilebased features that focus on the external properties of campaigns, such as Group Size and Group Support Count used in [Mukherjee et al., 2012]. These features may fail to accurately reflect the traits of emerging campaigns, since the size of a campaign is yet undetermined before the campaign ends.

The second challenge is about effective user rating behavior modeling. In online environments, the rating matrix R is inherently incomplete and sparse, which would cause many existing features to also be very sparse, and further hurt the performance of models built on those features. More robust representations are thus needed to encode user rating behaviors so as to effectively differentiate between campaigned spammers and normal users.

3 The Proposed Framework

To overcome the above challenges, we propose a novel framework, FRAUDSCAN, for online reputation fraud campaign detection. In light of the first challenge, we introduce the notion of campaign context to capture the interactions between campaigned spammers. Such interactions are driven by ongoing collaborations between spammers from the same campaigns, as they are instructed to target the same items and give ratings with the same polarity during the campaign period (as illustrated in Figure 1). By monitoring such interactions across time, it is possible to spot emerging campaigns once they have launched. Second, to model the sparse rating behaviors, we take an embedding-based approach [Hofmann, 1999] where each user or item is mapped to a dense embedding formed by considering all user-rating-item relations in the data. A novel regularized matrix factorization model is proposed to substantiate the campaign embedding in the campaign context, and a campaign-aware online update scheme to further efficiently adapt the built detection model to new ratings.

3.1 Campaign ActivityMonitoring

In this section, we introduce the campaign context built to monitor emerging campaign activities. Different from batch solutions, the campaign context is maintained incrementally upon the arrival of new ratings.

Target conformity

The first type of campaign context is focused on the items targeted by campaigned spammers. Due to the involvement in the same campaigns, spammers would naturally co-rate the same items, and are tied by such co-rating actions. We model such co-rating behaviors as a matrix Ct ∈ R|U t |×|U t | , where each entry cti,i′ is the normalized number of common items rated by both user ui and ui′ up to time t. The update rule for Ct is as follows: upon the arrival of a new rating rij from user ui to item vj, we update cti,i′ as,

where c∗i,i′ is a helper variable for counting; V t i and V t i′ are the items rated by ui and ui′ up to time t respectively.

Agreement intensity

The ratings given by campaigned spammers should also agree on the co-rated items, as they are instructed to post either positive ratings for promotion or negative ratings for demotion. Thus, the differences between their ratings given to the corated items should be small. We use a matrix Gt ∈ R|U t |×|U t | to capture the intensity of spammers' agreements. Each entry gt i,i′ keeps the up-to-date average rating difference between ui and ui′ , and is updated as follows,

where g∗ i,i′ is the helper variable, and RBF (radial basis function) kernel is used to compute the rating deviation.

Operational constraint

RFCs are often associated with time schedules specifying for how long the campaigns would last. In order to achieve the desired fraud effects, spammers are required to finish their jobs in time, such that their utilities can be aggregated. Such a constraint, however, would necessarily lead to small gaps between the timings of fraud activities. To account for this intuition, a matrix Ot ∈ R|U t |×|U t | is used for tracking the proximity of users in time, with each entry oti,i′ recording the average time interval between ratings given by ui and ui′ on the co-rated items so far, and being updated as below,

where o∗i,i′ is the helper variable, and tij(ti′ j) is the timestamp of ui(ui′ )'s rating for vj .

3.2 Fraud Campaign Embedding

As discussed, to address the sparsity of incoming rating data, we take an embedding-based approach for robust user rating behavior modeling, and propose a regularized matrix factorization model for RFC embedding. Concretely, we map each entity (a user or an item) in the data to a real-valued, dense vector in a low-dimensional space by taking all user-ratingitem relations into account. This can be achieved by factorizing the original rating matrix Rt into two matrices, i.e., user matrix Ut ∈ Rk×m and item matrix Vt ∈ Rk×n , where k ≪ min(m, n) is the rank of the embedded space, which is commonly set to be low (e.g., within [10, 50]). Each column uti of Ut (or vtj of Vt ) corresponds to the current embedding of user ui (or item vj). Meanwhile, to effectively capture campaign activities, we regularize such factorization in a proper way so that users who have stronger interactions in the campaign context are mapped to closer regions in the embedded space. As such, spammers from the same campaigns can be clustered together due to their strong connections in the campaign context, while normal users on the other hand would be dispersed randomly in the embedded space. Formally, we model the task of online RFC detection as a regularized embedding problem:

where Iij is the indicator function that equals to 1 if ui rated vj, and 0 otherwise. ∥ · ∥F is Frobenius Norm. αc, αg, αo, λu, λv are non-negative regularization parameters. The term ∑mi=1 ∑nj=1 Iij(rij - uti T vtj )2 is the objective function that factorizes the input rating matrix Rt into user and item matrices Ut and Vt . The terms ∑mi=1 ∑mi′=1 (∗)ti,i′ ∥uti - uti′∥2F are inspired by fused lasso [Tibshirani et al., 2005], and used to constrain the former objective function, so as to bridge the campaign context and the embedded space. More specifically, they are designed to penalize large differences between the embeddings of two users if they are strongly correlated in the campaign context (i.e., with large cti,i′ , gt i,i′ , oti,i′ ). As such, campaigned spammers will obtain similar embeddings (in the sense of small Frobenius distance) due to their strong connections in the campaign context. The last two terms ∥Ut∥2F and ∥Vt ∥2F are regularizers for avoiding overfitting.

To solve this optimization problem, stochastic gradient descent (SGD) is commonly used in the literature. In our case, for each rating rij ∈ Rt , the following updating equations are used to learn the detection model Mt = {Ut , Vt}:

where βu and βv are the learning rates.

Once SGD converged, for each user pair (ui, ui′ ), we compute the (inverted) Frobenius distance sti,i′ = 1 1+∥uti -uti′ ∥2F to measure the degree of their closeness in the embedded space. Then, the spamicity of a user ui is derived as the highest closeness she has with any other user so far, i.e., sti = max({sti,i′ |ui′ ∈ U t}). To generate the detection result Stκ , we rank the users by their current spamicities, and obtain the list of κ users with the largest values.

3.3 Online Campaign Detection

The above optimization procedure, however, is not sufficient for efficient and effective online RFC detection. First, the update scheme is in batch-mode; the model is not updated across time. Second, it implicitly assumes that the users are independent, and does not utilize the fact that campaigned spammers are correlated in the campaign context. Here, we propose a campaign-aware online optimization scheme to update the built detection model. The key observation is that, whenever a new rating arrives, it is not necessary to make updates for all users and items in the data. Instead, only the parts of the model that are related to the incoming rating should be affected. More specifically, let rij be the current rating from a user ui to an item vj, and U t j the set of users who had rated vj up to time t. Then, the arrival of rij would only change the relations between ui and those in U t j in the campaign context (see Eq. (1-3)). Moreover, as rating data increase, the impact of each rating to the embedding model decreases, and new ratings would not significantly change the entire embedded space. Thus, to obtain the current user matrix Ut and item matrix Vt , it is sufficient to only update the columns of Ut-1 that correspond to ui and the users in U t-1 j , and the column of Vt-1 that corresponds to vj. In other words, to obtain the current detection model Mt = {Ut ,Vt }, we approximate Ut and Vt by updating the embeddings of ui, U t-1 j , and vj that undergo changes in the campaign context, and keep the remaining part fixed as Mt-1 . This leads to Algorithm 1 for incremental RFC detection model update.

Input: Ct , Gt , Ot , Ut-1 , Vt-1 , St-1 κ , Rt-1 ∪ {rij} Output: Ut , Vt , Stκ // (1) Initialization 1 if ui is new then 2 Append a new column to the rightmost of Ut-1 ; 3 Initialize ui, i.e., the ui's column in Ut-1 ; 4 if vj is new then 5 Append a new column to the rightmost of Vt-1 ; 6 Initialize vj, i.e., the vj's column in Vt-1 ; // (2) Update user and item matrix 7 Initialize ui; 8 repeat 9 foreach ri∗ ∈ Rt-1 i ∪ {rij} do 10 Update ui and v∗ according to Eq. (5); 11 foreach ui′ ∈ U t j do 12 Update ui′ according to Eq. (5); 13 until Convergent or maximum iteration reached; // (3) Update detection report 14 foreach (ui, ui′) do 15 sti,i′ = 1 1+∥uti -uti′ ∥2F ; 16 sti = max({sti,i′ |ui′ ∈ U t }); 17 Insert {sti , ui} into St-1 κ ; 18 returnUt , Vt , Stκ

The algorithmic flow consists of three stages. First, we initialize the embeddings of ui and vj if either of them is new

(line 1-6). Then, the campaign embedding is updated (line 7-13). In this stage, we re-train the embedding of ui by first initializing ui and then updating the embedding according to her up-to-date rating profile Rti = Rt-1 i ∪ {rij} (line 9-10). Then, we update the embeddings of users in U t j who are related to the current rating in the campaign context (line 1112). Finally, we generate the detection report (line 14-17). For efficient update, the report Sκ is implemented as a maxheap that stores the largest κ spamicities and the corresponding users, which supports O(logκ) insertion. Through only updating the entities undergoing changes in campaign context, the complexity of online RFC detection has been considerably reduced. The time complexity of Algorithm 1 is O((|Rti | + |U t j |)×k×Iter) for campaign embedding update and O(|U t j | logκ) for result reporting. Note that Rti and U t j are only the ith and jth columns of rating matrix Rt , which are typically small in real applications (e.g., power-law distributed).

4 Experimental Analysis

We validate the proposed FRAUDSCAN for online reputation fraud campaign detection based on extensive experiments on real-world datasets. The evaluation is focused on the effectiveness of the proposed framework in RFC detection, and the efficiency of the proposed incremental scheme for detection model update.

4.1 Datasets

Our experiments are conducted on two real-world datasets.

Restaurant Reviews on Yelp (YelpZip): This dataset was used in [Rayana and Akoglu, 2015], which contains reviews about restaurants on Yelp.com. These reviews were collected through restaurant searching on Yelp via zipcode. The annotation is based on Yelp's own mechanism that classifies reviews as recommended or filtered. Users who authored filtered reviews are considered as the golden standard of spammers. However, there is no annotation for campaigned spammers in the dataset. We then follow the procedure in [Mukherjee et al., 2012] to extract user groups who have coratings, and regard groups whose members are all spammers as fraud campaigns.

Product Reviews on Amazon (AmazonCn): This dataset was created by [Xu et al., 2013]. It contains consumer reviews on amazon.cn. It already has the gold standard of campaigned spammers, which was obtained in a similar way by first locating users whose reviews were filtered by Amazon, and then grouping those exhibiting co-rating behaviors.

Table 1 shows the statistics of the two datasets.

4.2 Evaluation Protocol

For effectiveness comparison, as FRAUDSCAN outputs a ranked list of users with numerical spamicity scores, we adopt two well-known metrics - Average Precision (AP) and Area Under ROC Curve (AUC) - for ranking performance evaluation. Average Precision is essentially the area under precision-recall curve, and AUC is commonly used to validate binary classification systems by varying the discrimination threshold. For efficiency evaluation, runtime of the detection algorithm is used as the performance metric.

4.3 Performance Evaluation

In this section, we evaluate the effectiveness of FRAUDSCAN for reputation fraud campaign detection.

Qualitative analysis

We first conduct qualitative analysis. The success of FRAUDSCAN lies in the regularized campaign embedding that maps spammers from the same campaigns to close regions in the embedded space. Figure 2 shows the user projections in the embedded space on the two datasets. We can see that on both datasets, the campaigned spammers are effectively clustered together as expected, while the normal users are more scattered over the space, which validates the efficacy of the proposed embedding model. In addition, this also shows that our method can be used for visualization, which is lacking in other unsupervised methods that yield spamicity scores only.

Comparison analysis

Next, we compare FRAUDSCAN with state-of-the-art approaches, with the following baselines used:

• GSRank [Mukherjee et al., 2012]: a power iterationbased approach for spotting campaigned spammers based on the causal relations between users, reviews, and items. A set of Group Spam Behavior Indicators are proposed to capture suspicious collective behaviors of campaigned spammers.
• LCM [Xu and Zhang, 2015]: a statistical framework to model the collective behaviors of campaigned spammers for campaign inference and prediction.

In addition, two variants of FRAUDSCAN (FS) are also used:

• FS B: this is a batch variant of the proposed framework. In this variant, only the matrix factorization objective is optimized, without the use of campaign context-based regularization.
• FS BC: this is a batch variant of the proposed framework, with campaign context-based regularization used.

We empirically set optimal parameters for the hyperparameters (e.g., learning rate) of each method using a grid search in {0.001, 0.01, 0.1, 0.5, 1}. For FRAUDSCAN and its variants, four parameters α1, α2, α3, and k need to be tuned. We will show later the sensitivity analysis conducted on these parameters. Here, the optimal settings (α1, α2, α3, k) are used, i.e., (0.1, 0.1, 0.01, 20) for AmazonCn and (0.01, 0.1, 0.01, 30) for YelpZip. Figure 3 shows the performance comparison on the two datasets. In the figure, each result is the average over 10 runs of the corresponding experiment. All the improvements in the results are significant at p < .05 with paired ttest. The following observations are made based on the result comparison.

First, we can see that our proposed methods FS BC and FRAUDSCAN achieve better results than other baselines on both datasets. In particular, by comparing FS BC with the two start-of-the-art methods GSRank and LCM, the performance is improved by a margin of [2.4%, 3.2%] in AP and [1.5%, 14.5%] in AUC on AmazonCn, and [3.2%, 33.4%] in AP and [3.8%, 11.5%] in AUC on YelpZip. This might be ascribed to the embedding-based approach used in FRAUDSCAN for user rating behavior modeling, which compactly encodes rich user-rating-item relationships in the sparse original rating matrix in a more robust way.

Second, by comparing different variants of FRAUDSCAN, we observe that FS B performs worse than the other two on both datasets, suggesting that the factorization of the input rating matrix alone is not sufficient for campaign activity characterization. By further utilizing the campaign context proposed for capturing interactions between campaigned spammers, the performance of FS BC is largely improved. This shows that the incorporation of campaign-level information is crucial for collusive behavior modeling. Finally, FS BC and FRAUDSCAN achieve comparable results on both datasets, suggesting that the approximation adopted in the proposed online detection approach does not harm the embedded model building and the detection performance.

4.4 Earliness of Detection

One important objective of online detection is to spot emerging campaign activities as early as possible, so as to limit the caused damage in time. To this regard, we run the compared methods across time, with a one-day interval, and measure the earliness of detection by computing the lag between the time when a spammer appeared for the first time in the system and the time when (s)he was first detected. Ideally, the lag should be zero for all spammers.

Figure 4: Histograms of detection time lags for spammers caught by the compared methods. The histograms are truncated at 90-day lag due to the long-tail shape.

Figure 4 shows the results on AmazonCn 1 , by drawing histograms of detection time lags (in days) for caught spammers (true positives) 2 . We find that all the evaluated methods can discover more than half of the caught spammers in less than 10 days after their first ratings. In particular, FRAUDSCAN achieves better results than others by catching more spammers with less delay. Surprisingly, 921 spammers are caught by FRAUDSCAN right after they have posted the first ratings (zero delay), which is 34.4% more than LCM and 45.9% more than GSRank. This shows that compared to other methods, FRAUDSCAN is more effective in quickly responding to emerging reputation fraud campaigns.

4.5 Sensitivity Analysis

In this section, we evaluate the influences of model parameters on the detection performance. They are α1, α2, α3, and k in our framework controlling the importances of the three types of campaign context and the rank of the embedded space. For each α parameter, an independent experiment is conducted by setting other parameters to zero. The results on AmazonCn are shown in Figure 5.

We can see that all the results show similar patterns. The detection performance first rises as the parameter values increase. It then reaches the peak at particular settings and decreases afterwards. This is because when the parameters are

1 We omit the results on YelpZip due to less significant improvements being observed. The main reason is that the activeness of campaigns on YelpZip is relatively low, resulting in inherently large time lags between consecutive ratings.

2 We regard the users ranked at the top 2000 as positives, since there are 1,937 annotated campaigned spammers in the dataset.

set too small, the campaign context cannot be fully exploited to improve detection performance. However, the overuse of the campaign context can hurt the detection performance, since each type of the campaign context is just a necessary condition for characterizing RFCs. It can be seen that as long as the parameters are set within a medium range, the detection performance can always be improved compared to that without the campaign context. We can also observe that the rank of the embedded space should be set sufficiently large to achieve an optimal representation capacity.

4.6 Efficiency Analysis

Finally, we evaluate the runtime performance of our framework to validate its efficiency in RFC detection. In particular, the performance of the batch model FS BC and that of the online learning model FRAUDSCAN are compared. The experiments are conducted on a machine with a single-CPU, 3.20Ghz and 16G memory. Figure 6 shows the results on AmazonCn due to its larger size. We vary the size of training data, and record the execution time of each baseline. It can be observed that FRAUDSCAN requires less execution time than the batch version FS BC on datasets with different sizes. This shows that our online learning method is more efficient than the batch counterpart in detection. Moreover, as the size of training data increases, the differences in efficiency between the two approaches become more significant. Specifically, when the full dataset is used, the proposed online learning approach achieves around 4.1x speedup in detection.

5 Conclusion and FutureWork

In this paper, we study the problem of reputation fraud campaign detection in user ratings, and propose a principled optimization framework for emerging campaign detection. The new framework is based on the online learning scheme, and operates by monitoring campaign activities across time. The notion of campaign context is introduced to capture emerging campaigns via monitoring interactions among spammers. Moreover, to accurately model users' sparse rating behavior, an embedding approach is adopted to compactly map users and items into low-dimensional space. In the approach, the campaign context serves as model regularizers which can project campaigned spammers onto close regions in the embedded space. A campaign-aware online learning scheme is finally developed for efficient model update. The experiments show that our method achieves superior detection accuracy and efficiency over batch-based competitors. As future work, a potential extension of our approach is to analyze and incorporate other useful side information such as review text to improve model building.

Acknowledgments

We thank the anonymous reviewers for their valuable comments. This work was supported by the MOE AcRF Tier 2 Grant M4020110.020 awarded to Dr. Jie Zhang.