3.1 Burst Detection

We first introduce review burst detection. As mentioned already, this step detects bursts in reviews, allowing the second step to model the reviewers appearing within these bursts. As the modeling is based on several important assumptions regarding the properties of bursts, detecting real bursts is crucial to the performance of the spammer detection algorithm. However, since it is a step independent of the real spammer detection and is thus beyond the scope of this chapter, we will only briefly introduce one method, which is based on kernel density estimation [23]. Kernel density estimation is a nonparametric way to estimate the probability density of a random variable on the basis of a finite data sample. Given a sample S = {x_i}_i=1…N from an unknown distribution, its density function f(x) can be estimated with Eq. (9.1):

$\begin{array}{l}\hfill \widehat{f}(x)=\frac{1}{N}\sum _{i=1}^N{K}_h(x-x_i),\end{array}$

where K_h is called the scaled kernel with a bandwidth (scale) h such that K_h(t) = hK(t/h). K is called the kernel, which should satisfy K(u) ≥ 0 and $\int K(u)du=1$. One can think of Eq. (9.1) as estimating the probability distribution function by averaging the effect of a set of kernel functions centered at each data point. In kernel density estimation a range of kernel functions are commonly used. In this method, a Gaussian kernel is used.

Assume we have a product p that has a set of m reviews {p₁, …, p_m}, and each review is associated with a review date {t₁, …, t_m}. The method first chooses a bin size that is equal to a time period (eg, 2 weeks). Then the reviews are separated into subintervals on the basis of their time stamps to generate a histogram of review counts. The last step is to fit the histograms via kernel density estimation and select bursts by the setting of proper burst thresholds.

3.2 Spammer Detection Under Review Bursts

Now we introduce the algorithm for detecting spammers within bursts. The algorithm uses several important assumptions about review bursts and models the co-occurrence of reviewers using a probabilistic graphical model called MRFs. We start by introducing MRFs.

4.1 Campaign Promoter Modeling Using Typed Markov Random Fields

In contrast to a classic MRF, a T-MRF defines a graph with typed nodes T = {t₁, t₂…, t_n}. Each t_i is an element of a finite set of types H; that is, t_i ∈ H. For example, we use three node types in this work; that is, H ={user, URL, burst}. Each type of node represents a type of entity of interest (eg, user, URL, or burst in our case), and the edges between nodes represent their dependency relationships. For example, there will be a user-URL edge if a user’s tweet contains a certain URL. Again, two kinds of potential functions are defined on the T-MRF: the prior potential ϕ_i(σ_i|t_i) and the compatibility potential ψ_{i, j}(σ_i, σ_j|t_i, t_j). The compatibility potential gives the probability of a node v_j of type t_j being in the state σ_j given its neighboring node v_i of type t_i being in state σ_i. Now we introduce how prior potentials and compatibility potentials are set.

4.2 Inference

Similarly to the inference algorithm in the first algorithm, LBP is used to approximate the posterior probability over the states/labels of each node. In the T-MRF the message passing assignment of LBP is as shown in Eq. (9.9):

$\begin{array}{l}\hfill m_{i,j}({\sigma }_j|t_j)=Z_1\sum _{{\sigma }_i\in S}{\psi }_{i,j}({\sigma }_i,{\sigma }_j|t_i,t_j){\varphi }_i({\sigma }_i|t_i)\prod _{k\in N(i)\setminus j}{m}_{k,i}({\sigma }_i|t_i).\end{array}$

Eq. (9.10) shows the final belief b_i(σ_i|t_i) of a node i of type t_i, which is a vector of the same dimension as the message that measures the probability of node i of type t_i being in state σ_i:

$\begin{array}{l}\hfill b_i({\sigma }_i|t_i)=Z_2{\varphi }_i({\sigma }_i|t_i)\prod _{k\in N(i)}{m}_{k,i}({\sigma }_i|t_i).\end{array}$

4.3 Opinion Spam Evaluation

One of the major obstacles toward review spammer detection is the evaluation because ground truth data are hard to obtain for comparison with the model output. Here we introduce two approaches to opinion spam/spammer evaluation:

• Supervised text classification: Supervised text classification can be considered as complementary to human evaluation. In spam review detection, we can treat the spam reviews as belonging to the positive class and nonspam reviews as belonging to the negative class. A classifier can then be built to separate the two classes of reviews. This evaluation can be applied only when an underlying assumption holds. It assumes that a set of features different from the text features are used in the spam detection step. In the review classification, we use purely linguistic features. If the classification shows good accuracy, we know that the reviews written by reviewers labeled as spammers and nonspammers on the basis of their behaviors are also separable on the basis of their review text. The mixed class is not used in this evaluation because it contains a mixture of spam and nonspam reviews, which are harder to separate.

5.1 Problem Definition

Dianping’s filtering system has a very high precision, but unknown recall. This means almost all fake reviews detected are certainly fake but the remaining ones may not all be genuine. As reviews passed by its system may still contain many fake reviews, it is more appropriate to treat negative examples as an unlabeled set. In this section we will first introduce some notation and concepts and then define the CPU learning problem in a heterogeneous network.

A heterogeneous network is defined as $\mathcal{G}=(V,T,E)$, where V = {v₁, v₂, …, v_|V|} is a set of nodes representing the entities of different types and E is the set of edges incident on V. e_{i, j} ∈ E if v_i has a link to v_j. In Dianping’s problem, the heterogeneous network is defined as an undirected graph; that is, if e_{i, j} ∈ E, then e_{j, i} ∈ E. T = {t₁, t₂, …, t_|V|} is the set of corresponding entity types of nodes. Each t_i is an element of a finite set of types Γ (ie, t_i ∈ Γ). For example, in the defined heterogeneous network, there are three types of nodes; users, reviews, and IP addresses. That is, Γ = {user, review, IP address}. The edges between nodes represent their dependency relationships. Fig. 9.1 schematically shows three types of nodes and some edges between them.

Each node v_i is associated with a class label y_i, which is an element of a set of states $S_{t_i}$ that the node belongs to with respect to its entity type t_i. Thus we have $y_i\in S_{t_i}$. In the PU learning setting, a review has three states; fake (positive class), truthful (negative class), and a special state called unlabeled. A user has two states: spammer and nonspammer. An IP address can be either suspicious or organic.

5.2 Collective Classification

CPU learning uses an iterative classification algorithm (ICA) [31] as its underlying relational classifier. While a conventional classifier is a function f that maps the observed feature matrix $\mathcal{X}$ onto the class label space $\mathcal{Y}$, the ICA breaks the independence assumption. Consider a node v_i whose class label $y_i\in \mathcal{Y}$ needs to be determined and suppose a neighborhood function ${\mathcal{N}}_i=\{j|e_{i,j}\in E\}$ returns the indices of its neighbors. ${\mathcal{M}}_i=\{\widehat{y_j}|j\in {\mathcal{N}}_i,\widehat{y_j}\in \widehat{\mathcal{Y}}\}$ is the class label vector of the neighbors of node i that is derived from ${\mathcal{N}}_i$ and the estimated class labels matrix $\widehat{\mathcal{Y}}$. The ICA trains a local classifier f, whose input is the observed features x_i of v_i as well as the estimated labels from its neighbors ${\mathcal{M}}_i$. Because many labels of nodes are unknown, this process has to be executed iteratively, and in each iteration the label y_i of each node is assigned the current best estimates from the local classifier $y_i=f(x_i,{\mathcal{M}}_i)$. The base learner used by the ICA can be any conventional classifier that gives probabilistic outputs such as logistic regression or support vector machines.

As the network is heterogeneous, Li et al. [30] divide the network into multiple networks, each of which is homogeneous. Nodes in the resulting networks are connected if they share common neighbors in the original network. Unlike the ICA, CPU learning allows initial labels to be violated if the current probability estimate strongly indicates the opposite prediction. This is especially useful for the mining of fake reviews that are identified by the collective classifier but not identified by Dianping’s filter [32]. During each iteration, the model produces new estimates of nodes for all three types. For each type of node, the probability is assumed to be a normal distribution such that a set of reliable positive and reliable negative data instances can be extracted. Once a reliable positive data instance is identified, its label is changed from unlabeled to positive. However, relying on the fact that Dianping’s filter has a very high precision, the label of a reliable negative is updated only if its label was previously unlabeled. Algorithm 9.1 outlines the CPU learning model.

5.3 Model Evaluation

The effectiveness of the CPU learning model was evaluated on gold standard data from Dianping’s system.¹ Tenfold cross validation was performed for each model. F₁, precision, recall, and accuracy are reported in Table 9.3. Compared with the other collective classification models ICA and MHCC [33], the CPU learning model achieves much better classification results (F₁ scores, precision, and accuracy) than nonrelational classifiers, which classify each instance independently. Nonrelational PU learning models (PU-LEA [34], Spy-EM [35], Spy-SVM [35]) have higher recall than the traditional supervised classifier logistic regression (LR) despite some loss in precision. This is because Dianping’s unlabeled reviews contain hidden positives that provide purer positive and negative instances for training.

5.4 Trends and Directions

Although many algorithms have been proposed to detect fake reviews, there is still a long way to go before we can weed out opinion spamming activities. There are also many interesting research directions that have not been or have barely been explored. Here we describe several such directions based on [36]:

• Multiple site comparisons: Spammers who promote or demote some target products may write fake reviews on multiple sites to achieve the maximum effect as many websites may sell the products or host reviews about the products. It is interesting to compare reviews of the same product across these sites to discover abnormalities; for example, similar reviews (contents or ratings) that are written at about the same time, similar user ids, and the same or a similar IP address. It is quite unlikely for a genuine reviewer to be bothered to post a positive review for a product on multiple sites.

• Language inconsistency: To suit different products and to stress personal experiences, fake reviewers may write something that is inconsistent or against social norms in different reviews. For example, to promote a woman’s watch, a spam reviewer may write “I bought this watch for my wife and she simply loved it.” Later, to promote a man’s shirt, the same reviewer may write “I bought this shirt for my husband yesterday.” The two sentences indicate gender inconsistency. There are many other possible inconsistencies that can be detected (eg, age, with/without children, ethnicity).

• Nature of business: In many cases the nature of the product or business can help to detect fake reviewing activities. For example, if all positive reviews of a hotel come from people living in the area near the hotel (on the basis of their IP addresses), these positive reviews are clearly suspicious because few people would stay in a hotel if they have homes nearby. However, there are so many types of businesses, and manually compiling such normal and abnormal behavior patterns is very difficult. The challenge is how we can design an algorithm to automatically discover such abnormal behavioral patterns for each domain.

• Web use abnormality: Web servers record almost everything that a person does on a website, which is valuable for detecting fake reviews. For example, using the IP address information and click behaviors, we may find that all positive reviews for a product are from the same or a similar IP address, or many reviewers who have never visited the website suddenly came to a product page directly and wrote positive reviews. In the first case, all the reviews might have come from the same person, and in the second case, the seller of the product might have paid people to write reviews for the product and also provided a link to the product page. The fake reviewers simply clicked on the link and posted fake reviews. Again, there are a large number of abnormal web use behavior patterns, and the challenge is how to automatically mine such patterns.

• Early detection: Most existing algorithms rely on patterns detected from review contents and reviewers’ behaviors. It takes some time for most types of patterns to form. However, when the patterns finally show themselves, some major damage might already have been done. Thus it is important to design algorithms that can detect fake reviews as soon as possible, ideally immediately after they have been posted.