Rumor Detection on Social Media with Graph Structured Adversarial Learning

1 Introduction

With the rapid growth of social media such as Twitter and Weibo, information campaigns are frequently carried out by misinformation producers with various commercial and political purposes. Consequently, large amounts of fake or unverified information have emerged and spread to affect online social network users, which also leads to tremendous effects on the offline society. For example, the wide spread of fake news on social media has influenced the 2016 US presidential election [Allcott and Gentzkow, 2017]. Thus, identifying rumors automatically is beneficial for providing early precautions to minimize its negative influence.

Traditional rumor detection methods such as [Yang et al., 2012; Ma et al., 2015; Kwon et al., 2017] mainly focused on extracting hand-crafted features from post contents, user profiles, and diffusion patterns as inputs for supervised learning algorithms. Recently, powerful deep learning models without heavy feature engineering have been applied in this task. RNN-, CNN-, and autoencoder-based methods have achieved significant improvements over traditional methods. However, existing methods mostly treat the detection of each piece of information independently, ignoring their correlations. On social networks, there are rich structure correlations among different pieces of information. For instance, multiple posts can be connected if they are posted or retweeted by the same user. Such correlations enable sharing knowledge between connected instances, assisting each other's detection to improve the performance. Recent efforts on utilizing structure information for rumor and fake news detection have shown promising performance. In [Yuan et al., 2019], based on a heterogeneous graph constructed from posts, comments, and the related users on social networks, structure semantics are captured by graph attention network[Veliˇckovi´c et al., 2018]. In [Zhang et al., 2018], a deep diffusive network model is built to learn the representations of news articles, creators, and subjects simultaneously.

∗Corresponding author

Despite the success of deep graph neural networks, the lack of interpretability and robustness would make it risky for rumor detection. A fundamental assumption of these models is that a piece of information connecting with high-credit users would also have high credit, but the credit can be manipulated by rumor producers. A rumor could try to disguising itself by posting with hijacked or traded accounts from honest users. For example, in 2013, Associated Press's Twitter account was hijacked and the rumor of explosion at White House was posted, causing the stock market to briefly plunge. Other cheaper and more common camouflage strategies include connecting the posting user with high-credit users, removing opposing comments, and creating fake supporting comments. Figure 1 shows four types of camouflages on the social graph. Such attacks would make the rumor evade graph-based models by intentionally modifying the graph structures. However, little attention has been paid to this severe issue.

We argue that considering camouflages are necessary to complement prior work on rumor detection. We focus on the attack type that fools the graph neural network-based detection model by manipulating the graph structure. In this regard, RL-based and gradient-based adversarial attack methods on graph-structured data have been proposed in [Dai et al., 2018], but the target graph they consider is homogeneous and the structure can be modified arbitrarily. In contrast, the graph constructed for rumor detection is heterogeneous and involves domain constraints. For example, a post cannot be connected with another post directly.

In this paper, we investigate: (i) how to simulate various camouflage methods on social networks to evade the rumor detector (ii) how to make the detector reveal camouflages as much as possible. To address these two issues, we rigorously define the possible camouflage, i.e., attack types in consideration of domain constraints. We then propose a novel graph adversarial learning framework that enables such attacks to fool the detector by dynamically adding intentional perturbations. Meanwhile, the detector would be enhanced to learn more distinctive structural features to resist such perturbations. The attacker and detector would strengthen each other iteratively, making our model produce robust detection results.

The main contributions of this paper can be summarized as follows:

• We study a novel problem of rumor detection on social media in the face of camouflage.
• We propose an end-to-end framework that jointly exploits text and structure information for detection.
• We develop a graph adversarial learning method that encourages the model to provide robust predictions under the perturbed graph structure.
• We conduct extensive experiments on real-world datasets to demonstrate the effectiveness of our model.

2 RelatedWork

Compared to the traditional machine learning models such as [Zhao et al., 2015; Ma et al., 2017; Castillo et al., 2011], deep learning models have achieved state-of-the-art performance for rumor detection. Most of these models adopt the text information for detection. [Ma et al., 2018] uses recursive neural networks with a bottom-up structure and a top-down tree structure to extract text features. [Khattar et al., 2019] uses a variational autoencoder to obtain features of texts and pictures to determine whether the post is a rumor. [Liu and Wu,

2018] models the propagation path of a tweet as a multivariate time series, and uses RNN and CNN to capture the global and local variations of user characteristics along propagation paths. The common limitation of these studies is that they don't fully utilize the social network structure information. In contrast, [Yuan et al., 2019] not only uses text features but also extracts network structure features through the Graph Attention Network [Veliˇckovi´c et al., 2018], which shows good performance. However, it doesn't consider the camouflage behaviors in the social network, and thus may fail to detect the camouflaged rumors.

[Wang et al., 2018] obtains non-event-specific features from texts and pictures with the idea of the generative adversarial network (GAN) [Goodfellow et al., 2014] for detection. [Ma et al., 2019] uses GAN to generate uncertain or conflicting voices to learn more effective features. Different from these GAN-based works that manipulate the texts, we perturb the network structure to learn stronger structure features. Although there are some recent studies on graph adversarial attacks [Xu et al., 2019; Wu et al., 2019; Dai et al., 2019], they perform general attacks without considering the heterogeneity and domain constraints that exist in real-world applications such as rumor detection.

3 ProblemDefinition

Let P = {p1, p2, ..., p|P|} be a set of posts on social media, R(pi) = {r1, r2, ..., r|R|} be a set of comments of pi, U = {u1, u2, ..., u|U|} be a set of users who deliver one or more posts or comments.

To exploit the posting and retweeting behaviours on the social network for classification, we construct the heterogeneous graph G = (V, E, A), where V is the set of nodes, E is the set of edges and A ∈ {0, 1}|V |×|V | is the adjacency matrix. There are three types of nodes, users, social posts, and user comments. To construct the graph, there would be an edge between a user and her post. The user and her comment would also be connected. Users are connected according to the follower/followee relationships. Moreover, there would be an edge between two comments if one is the comment for the other. For simplicity, we don't consider the directions on the edges and thus treat G as an undirected graph.

We take the rumor detection task as a binary classification problem. c ∈ {0, 1} denotes the class labels where c = 1 represents the rumor and the other represents the non-rumor. Our goal is to train a model f(·) to predict the label of a given post where f(pi) = 1 denotes pi as a rumor and f(pi) = 0 denotes pi as a non-rumor

4 Methodology

4.1 Model Overview

The proposed rumor detection model consists of three main components, encoding camouflaged graph, encoding text contents, and classification with adversarial learning. Figure 2 shows the architecture of the proposed model.

We define several widely used camouflage strategies, and automatically learn to generate camouflages on the graph. We then extract the structure representations from camouflaged graphs for each post. Besides structure information, we also exploit the post contents to extract the text representations for each post and fuse text and structure representations to make a classification. This classification loss with camouflaged structure features would be combined with another standard classification loss with non-camouflaged structure features. To optimize the sum of these two losses, we train the model end-to-end with an adversarial learning method.

4.2 Encoding Camouflaged Graph

Generating Camouflages on Graph

To simulate the camouflage strategies of a rumor spreader, we divide users into two categories: bad user and good user. Bad users refer to those who deliver or forward at least one piece of rumor and the others are good users. We support the following four types of camouflages as shown in Figure 1:

(a) a bad user node links to good user nodes which represents the bad user disguises himself by buying some fans or following some good users.

(b) a bad user node links to non-rumor post nodes, indicating a rumor spreader carries out normal social activities.

(c) a rumor spreader node deletes the edges between the rumor post node and the opposing comment nodes, avoiding being caught.

(d) a good user node links to rumor post nodes, indicating a good user account was hacked or bought to forward a rumor.

To formally describe the camouflage strategies, we define a camouflage compatibility matrix in Table 1 which corresponds to Figure 1 exactly. The entry values "0" and "1" denote it does and doesn't allow a camouflage between the corresponding two types of nodes respectively. We then define an action mask matrix M ∈ {0, 1}|V |×|V | , where Mij = 1 if it allows a camouflage between node types of ni and nj ({ni, nj} ∈ V ) in Table 1. Otherwise, Mij = 0. For example, if ni is a rumor post and nj is a comment, in this case, Mij = 1 because a camouflaged modification between a rumor and a comment is allowed in Table 1.

Apart from the action mask matrix M, we also define an action matrix S ∈ {0, 1}|V |×|V | to specify the camouflage actions that are actually taken. Specifically, Sij = 1 means a camouflage action is performed between ni and nj. Otherwise, Sij = 0 indicates no action is performed. For example, given Aij = 1 (resp. Aij = 0), Sij = 1 would lead to the deletion (resp. addition) of the edge between ni and nj as a camouflage. The adjacency matrix is thus modified and we obtain Aij = 0 (resp. Aij = 1) accordingly. To connect the modification of Aij with the action Sij, we further introduce an assistant matrix C ∈ {0, 1, -1}|V |×|V | . C = ¯ A-A, where ¯ A = 11T - I -A. I is the identity matrix and (11T - I) represents the fully-connected graph. Since C = ¯ A-A, directly apply C to A would make all the entries (except the diagonal ones ) in A are modified from 1 to 0 or from 0 to 1, indicating performing camouflages on all the pairs of nodes. Actually, whether it is allowed to perform a specific camouflage between a pair of nodes is determined byM, and even if it is allowed, whether it is performed is determined by S. Thus, the final camouflaged adjacency matrix A′ is obtained by jointly involving these matrices, that is,

where ◦ represents element-wise product.

Note that A, M, and C are predetermined according to the dataset. Sij is updated in the training process. For ease of optimization, we relax Sij ∈ {0, 1} to its convex hull Sij ∈ [0, 1]. To enable this learning, we use the attention mechanism to derive the elements of S.

For example, suppose ni is a rumor node and nj is a good user node. In this work, representations of all kinds of nodes have the same dimension of d. {vi, vj} ∈ Rd represent the node vectors of ni and nj respectively. Considering the heterogeneity of the graph, we first transform vi and vj to the same feature space through Wpvi and Wuvj where Wp ∈ Rd′×d and Wu ∈ Rd′×d are two parameterized weight matrices for posts and users respectively. Similarly, there is also Wr ∈ Rd′×d for comments. In this way, we transform the d-dimensional vi to the d′ -dimensional vector. Then the attention coefficient is obtained through a singlelayer neural network g : Rd′ ×Rd′ →R

where σ is an activation function such as ReLU. a1 ∈ Rd′ and a2 ∈ Rd′ are parameters in the attention corresponding to posts and users respectively. There is also a3 ∈ Rd′ corresponding to comments. eij indicates the importance of nj to ni. We denote Ni as a set of nodes that could have camouflaged actions with ni. Then softmax is applied to normalize each attention coefficient by

The more important nj is to ni, the greater value αij has. In our application, there is Sij = αij, indicating the extent of camouflage action between nj and ni. In this way, we parameterize A′ . With the camouflaged graph, we then discuss how to extract the graph structure features.

Encoding Structures

Graph neural networks (GNNs) have shown superior capability in capturing the graph structures. GCN [Kipf and Welling, 2017] and GAT [Veliˇckovi´c et al., 2018] are two widely-used models. We chose GCN in this work.

First, the camouflaged adjacency matrix is added with the self-connections, that is

Then the propagation step from the l-th layer to the (l+1)- th layer is

where σ is the ReLU activation function. H(l) ∈ R|V |×d is the matrix of activations in the l-th layer. H(0) is the node embedding matrix B ∈ R|V |×d . The element of ˜D is ˜Dii = ∑j ˜ Aij. W (l) is a trainable weight matrix. We use a twolayer GCN to extract structure features. It is calculated as

where ˆ A = ˜D- 1 2 ˜ A ˜D- 12 and W (0) ∈ Rd×d′ is the inputto-hidden weight matrix. W (1) ∈ Rd′×d′ is the hidden-tooutput weight matrix. f(B,A) ∈ R|V |×d′ is the updated node embedding matrix. We denote h′i ∈ Rd′ as the i-th node embedding in f(B,A) which represents the structure feature of pi.

Besides extracting the structure representation h′i from the camouflaged graph A′ , we also extract the structure representation of pi from the original graph A, denoted as hi. Both hi ′ and hi would be concatenated with the text representation (described in the next subsection) for classification.

4.3 Encoding Text Contents

To obtain the text representation for each post, we adopt the multi-head self-attention and CNN with pooling.

For preprocessing, we truncate the text if its length is larger than L and pad zero if the length is smaller than L. Let xij ∈ Rd represent the word embedding of the j-th word in the text of post pi. The text representation of pi is thus represented as

where Xi1:L ∈ RL×d .

Then, we refine word embeddings using the multi-head self-attention [Vaswani et al., 2017] to capture dependencies between words. Each of the heads captures a hidden relationship from a specific aspect. Considering a self-attention with h heads. There are three input matrices for the j-th head which are the query matrix Qj ∈ RL× dh , the key matrix Kj ∈ RL× dh and the value matrix Vj ∈ RL× dh . Take Xi1:L ∈ RL×d as an example. For simplicity, we denote Xi1:L as X. There are Kj = XW K j , Qj = XW Q j and Vj = XW V j with {W Q j ,W K j ,W V j } ∈ Rd× dh . Besides, we denote the output of the self-attention with h heads as Z = [Z1;Z2; ...;Zh]. The output of the j-th head is calculated as

with Zj ∈ RL× dh . Then Z is calculated as

We then capture the semantic representation of a post with CNN. Xie:e+k-1 is convolved with a filter W ∈ Rk×d where k is the size of the receptive field. The feature tj is generated from a window of word embeddings Xie:e+k-1

where ∗ is the convolution operation and b ∈ R is the bias term. σ is an activation function such as tanh. The filter W is applied to each possible window of word embeddings in Xi1:L to produce a feature map t for pi

where t ∈ RL-k+1 . Then a max pooling with a stride of L - k + 1 is applied over the feature map:

We use d/3 filters with varying receptive filed k ∈ {5, 6, 7} to obtain the semantics from different granularities. Each of the receptive fileds corresponds to a feature vector of length d/3. Next, we concatenate all feature vectors to form mi ∈ Rd , which is the final text representation of post pi.

4.4 Classification with Adversarial Learning

Here we describe how to combine the structure and text representations for classification.

Objective of Optimization

For post pi, we have obtained its structure features h′i and hi from the camouflaged graph and the non-camouflaged graph respectively, as well as its text representationmi.

Then we concatenate them to form two feature vectors of pi, which are P ′ i = [h′i ;mi] and Pi = [hi;mi]. Next, we feed P ′ i and Pi into the fully-connected layers respectively and obtain

where {W1,W2} ∈ R(d+d′ )×|c| are the weight parameters and {b1, b2} ∈ R|c| are the bias terms. ˆ y′i and ˆ yi are the predicted probability distributions of pi over two classes.

Then we use the cross-entropy loss as the optimization objective which consists of two parts. One is the standard loss L1 based on the original adjacency matrix A. The other loss L2 is based on the camouflaged adjacency matrix A′ . Therefore, the overall loss L is

where yi is [1, 0] when pi is a rumor post and [0, 1] when it is a non-rumor post. N is the number of training data. θs denotes parameters in the camouflaged adjacency matrix A′ except the node embedding matrix B. The remaining parameters are denoted as θd. β is a hyperparameter to control the scale of L2.

Adversarial Learning

Given the optimization object L in Eq. 15, we adopt an adversarial learning method to infer the parameters. It can be viewed as playing a minimax game as follows

The overall training process is shown in Algorithm 1. In each iteration, we first optimize the parameters θs in Eq. 2 to generate a camouflaged graph A′ that can cause the largest classification loss L (Lines 7-9). We then optimize the other parameters θd to minimize L (Lines 10-12), encouraging the model to make the correct classification.

5 Experiments

5.1 Datasets

We evaluate our model on two real-word datasets: Weibo [Song et al., 2018] and Twitter [Zubiaga et al., 2016], which were collected from the most influential social media in China

Algorithm 1 Model training with a minimax game

Input: Graph G = (V, E, A), a set of post contents T , learn-

ing rate ϵ

Parameter: θs and θd

• 1: for epoch from 1 to maxEpoch do
• 2: for G = (V, E, A) and a batch of T do
• 3: Compute the camouflage adjacency matrix A′ using Eq. 1;
• 4: Extract structure features using Eq. 6;
• 5: Generate text representations using Eq. 12;
• 6: Compute CrossEntropy loss L using Eq. 15;
• 7: /* Maximize L w.r.t.θs */

8: Compute gradient ∇(θs);

• 9: Update: θs ← θs + ϵ∇(θs);
• 10: /* Minimize L w.r.t. θd */
• 11: Compute gradient ∇(θd);
• 12: Update: θd ← θd - ϵ∇(θd);
• 13: end for
• 14: end for

and the U.S respectively. For a specific post, both of the datasets contain two labels, i.e., rumor (R) or non-rumor (N), and also contain rich information such as post texts, comments, and user profiles. Table 2 shows the statistics of the datasets.

5.2 Baselines

We compare the following baseline models with our model:

HAN [Yang et al., 2016] applies a hierarchical attention network to the post contents at the word-level and sentence-level.

Text-CNN [Kim, 2014] uses convolutional neural networks to capture text semantics for classification tasks.

GRU [Ma et al., 2016] adopts recurrent neural networks for learning hidden representations to capture the variation of contextual information of relevant posts over time.

RvNN [Ma et al., 2018] adopts two recursive neural models based on a bottom-up and a top-down tree-structured neural networks, which are denoted as RvNNBU and RvNNTD.

EANN [Wang et al., 2018] is a GAN-based model that can extract event-invariant features and thus benefit the detection of newly arrived events. Note that different from the original EANN, we don't consider pictures as input due to the lack of pictures in our dataset.

GAN-GRU [Ma et al., 2019] is a GAN-based model where a generator will produce conflicting voices to force the discriminator to learn stronger rumor indicative representations.

GLAN [Yuan et al., 2019] adopts a global-local attention network for rumor detection, which jointly encodes the local semantic and the global structural information.

CGAT is our proposed model, which is short for simulating Camouflages on Graph with Adversarial Training

Among the above baselines, Text-CNN, GRU, HAN, and RvNN are deep learning methods. EANN and GAN-GRU deal with rumor contents based on the idea of the generative adversarial network. GLAN combines text contents with social network structures to detect rumors.

We split the datasets for training, developing, and testing with a ratio of 7:1:2. We adopt the accuracy, precision, recall, and F1 score as the evaluation metrics. We use the Adam algorithm [Kingma and Ba, 2015] to optimize our objective function with β1 = 0.9 and β2 = 0.999. The learning rate used in the training process is 0.002.

5.3 Results and Discussion

Table 3 shows the performance of the comparison methods. It can be observed that CGAT significantly outperforms all the baselines which confirms that considering the camouflages on the graph would benefit the rumor detection task.

Most baseline models cannot perform well on both of the two datasets. The possible reason is these models are based on text representations, and it is hard to design a good text model that can capture the semantics across two very different languages. On the contrary, GLAN and CGAT also consider social structures which are independent of languages, and thus achieve consistent performance improvements.

Besides our model and GLAN, GAN-GRU and RvNNBU perform better than the other baselines on Weibo dataset. The reason is that, in addition to post contents, they also involve the user comments for detection. However, they perform not very well on Twitter dataset. The possible reason is that according to Table 2, the number of comments on Twitter is less than that inWeibo, limiting the benefits of the comments.

5.4 Performance of the Variations

To show the effectiveness of different components in CGAT, we compare it with the following variations:

CGAT-TEXT only uses rumor texts. As all the other variations utilize texts, we omit it in the remaining for simplicity.

CGAT-ADJ only uses the structure features from the original graph, without involving the camouflaged graph.

CGAT-GP uses another graph adversarial attack method [Bojchevski and G¨unnemann, 2019] to perturb the graph structure A, and the resulting graph takes the role of A′ in CGAT.

CGAT-M doesn't use the action mask matrix M and thus enables edges are added or removed between any two nodes.

The comparison results are shown in Table 4. It can be observed that: (i) all the other methods outperform CGATTEXT, indicating the structure features are important for rumor detection; (ii) models with the perturbed graph structure outperform CGAT-ADJ, which shows the benefits of the adversarial attacks on the graph; (iii) CGAT-M and CGAT-GP are only a little better than CGAT-ADJ, but much worse than CGAT, indicating that attacking the graph structures without domain constraints would introduce unnecessary noises in the model and thus limit the performance improvements.

6 Conclusion

In this paper, we propose a graph-based rumor detection method which takes into account the camouflages of rumors from an adversarial perspective. By dynamically generating the perturbations on the heterogeneous social graph with domain constrains, we learn to extract more distinctive structure features, which cooperates with text representations to improve the performance of the model. Evaluations with both English and Chinese rumor datasets demonstrate our model can outperform the state-of-the-art baselines.

Acknowledgments

This work was supported by the National Key Research and Development Program of China (No.2017YFB0803301) and Natural Science Foundation of China (No.61976026, No.U1836215) and 111 Project (B18008).