Sage Journals: Discover world-class research

Abstract

Because of their proficiency in capturing the category characteristics of graphs, graph neural networks have shown remarkable advantages for graph-level classification tasks, that is, rumor detection and anomaly detection. Due to the manipulation of special means (e.g. bots) on online media, rumors may spread across the whole network at an overwhelming speed. Compared with normal information, popular rumors usually have a special propagation structure, especially in the early stage of information dissemination. More specifically, the special propagation structure determines whether rumors can be spread successfully. Namely, online users and their interaction that constitute the special propagation structure play a key role in the spread of rumors. Therefore, the problem of rumor detection can be transformed into detecting the existence of a special propagation structure. Inspired by backdoor attacks, we propose an interpretable rumor detection algorithm based on backdoor. Firstly, based on causal analysis, the causal sub-graph that determines the category of the graph (rumor vs. normal information) is obtained, that is, the critical online users in the rumor spreading effect are found, and then the specific propagation structure is explored. Finally, the special propagation structure is planted into the rumor detection model as a trigger. Experimental results and performance analysis on three real-world datasets demonstrate the effectiveness of our proposed algorithm in the special propagation structure detection of rumors. Compared with two baselines, Lurker achieves up to 33.1% and 61.8% performance improvement in terms of attack success rate and clean accuracy drop.

Keywords

Rumor detection Graph classification Graph neural networks backdoor attack

Introduction

Social media serves as a platform for people to share their opinions and experiences with each other. While its convenience and efficiency facilitate the rapid dissemination of information, it also opens the door for malicious users to spread rumors. The widespread spread of rumors may disturb the thoughts of the public, affect the credibility of the government, and even cause social panic. Therefore, rumor detection on social media platforms is critical to maintaining a trustworthy and secure cyberspace.

The goal of rumor detection on social media is to verify the authenticity of messages and identify rumors on social platforms, so as to prevent the spread of false information in time. An effective rumor detection method can avoid the negative impact of rumors on the public. Classical rumor detection methods primarily focus on analyzing content, semantics, sentiment, and other aspects of the information itself using natural language processing techniques.^1,2 For example, Shu et al.³ developed a fake news detection method to capture explainable top-k check-worthy sentences and user comments by exploiting both news contents and user comments. Wu et al.⁴ analyzed articles and related content to find supporting evidence. These methods can improve the efficiency of rumor detection, but they mainly rely on textual analysis, which can be inadequate for identifying well-crafted rumors.

Since it is difficult to accurately identify rumors through content analysis, researchers turned to the propagation structure of rumors to identify rumors. Vosoughi et al.⁵ analyzed the propagation paths of news on Twitter and discovered that false information spreads significantly farther, faster, deeper, and wider across all domains compared to real information. It suggests that there is a distinct difference between rumors and true information in terms of their propagation patterns. In other words, it is feasible to detect rumors by the propagation structure they form in social networks. Therefore, propagation pattern-based methods have become a feasible solution to rumor detection. Given the different propagation structures of rumors and real information, Liu et al.⁶ modeled information propagation as a multivariate time series. Bian et al.⁷ designed a bi-directional propagation tree based on the Bi-GCN model to detect rumors. These methods exploit the features of the propagation graph, such as the number of retweets and temporal characteristics, to achieve rumor detection effectively and efficiently. However, these methods rely on feature construction to learn the characteristics of rumor propagation, ignoring the structural properties of propagation paths.

Generally, malicious users can use some means such as bots to enable rapid and extensive propagation across the network once rumors have been posted. Such rapid spread of rumors on social platforms means that they may have a special propagation structure, especially in the early stages of dissemination. Previous work^5–8 has shown that rumors spread in a significantly different pattern compared to real information, which demonstrated the existence of this substructure. The substructure provides a new solution to our rumor detection problem. However, how to bridge the structure of the propagation path to rumor detection is our first challenge. The propagation graphs of these information are massive in number and variable in structure. In addition, rumors typically involve a large number of users during their propagation, resulting in propagation graphs with numerous nodes and edges. Furthermore, given the complexity of the graph’s connectivity, identifying whether a specific subgraph is an NP-hard problem.^9,10

Rumor detection on social media is essentially a graph neural network (GNN)-based classifier. Ideally, we expect that the rumor detection model we develop can detect all rumors and keep real information intact at the same time. Although it has been confirmed that the rumor propagation graph contains a special substructure, it remains unclear how the special substructure is used to perform the rumor detection. Therefore, how to make the rumor detection model learn the correlation between the special substructure and rumors is our second challenge. Fortunately, backdoor attack can implant the specific information into a model. Backdoor attacks were first presented in image classification.¹¹ Zhang et al.¹² introduced the first backdoor attack on GNNs using well-designed subgraph as trigger, revealing the vulnerability of GNNs. According to the relation between triggers and samples, backdoor attacks can be divided into sample-agnostic and sample-specific attacks. The former uses a fixed trigger for all graphs,^13,14 while the latter generates a tailored trigger for each graph.^15,16 Xu et al.¹⁷ proposed a clean-label backdoor attack, where the labels of the poisoned graphs are unchanged in poisoning phase and the graphs containing the trigger are identified as the target label in the inference phase. The recent advances of interpretable GNNs^18–20 make it possible to design rumor detection models from the perspective of interpretability.

To address these two challenges, inspired by Zhang et al.¹²and Ying et al.,¹⁸ we propose a novel backdoor planted-based interpretable rumor detection model, Lurker, on online media. We first find the key nodes in the information propagation graph based on information theory, then explore the key substructure that determines the classification of the rumor propagation graph, and finally use the substructure as a trigger to train a rumor detection model. By using the specific substructure derived from the rumor propagation pattern, we successfully establish strong associations of the target label with the special substructure, enabling the model to predict subgraphs with similar organization to the specific substructure as rumors and for non-target label samples as their true labels.

Our contribution can be summarized as follows:

We propose an interpretable rumor detection framework for online media based on the specific patterns of information propagation.

With the clean-label poisoning strategy, we implant the specific substructure into the rumor detection model. The proposed model, Lurker, establishes a correlation between the specific substructure and rumors, ensuring that samples with the substructure are detected as rumors while minimizing the impact on non-target label samples.

We evaluate the performance of Lurker using three public real-world datasets. Compared with two baselines, Lurker achieves up to 33.1% and 61.8% performance improvement in terms of attack success rate (ASR) and clean accuracy drop (CAD).

Related work

Rumor detection on social media

Early rumor detection methods focused on the analysis of rumor texts because rumors are generally false information with malicious intent. Zhao et al.²¹ combined keyword detection with K-means clustering to detect rumors. Huang et al.²² proposed a heterogeneous graph attention network to capture the global semantics of text. Although these proposed methods have achieved good performance, it is difficult to fully learn rumor features only through text analysis. Thanks to the superiority of deep learning, deep learning-based rumor detection methods have emerged. Ma et al.²³ made the first attempt to utilize recurrent neural networks (RNNs) to learn textual and temporal features. To fully capture the characteristics of rumors, a series of methods explored supplementary information beyond text to detect rumors. Wang et al.²⁴ designed a multimodal graph convolutional network that effectively incorporated features derived from text content, images, and knowledge graphs to improve the detection performance of fake news. Zheng et al.²⁵ developed a multimodal feature-enhanced attention network, MFAN, that combined text, images, and user behaviors to achieve better rumor detection performance. Currently, the researchers have also explored the feasibility of using the rumor propagation pattern to detect rumors. Ma et al.²⁶ constructed a tree based on the hierarchical relationship between responses and comments to represent the rumor propagation graph on social networks and utilize RNNs to capture text semantics and propagation patterns. Bian et al.⁷ introduced a bidirectional information propagation mechanism to model the rumor propagation structure to learn the forward and reverse path characteristics of information propagation. Zhang et al.¹² applied backdoor attack to rumor detection for the first time and designed a subgraph-based backdoor attack model. In addition, Pattanaik et al.²⁷ systematically evaluated the state-of-the-art deep learning models for rumor detection on social media and summarized the key issues and challenges currently faced in this field. Cesarini et al.²⁸ provided a review of interpretable AI methods in text classification, offering an important theoretical foundation for the application of interpretable methods in rumor detection. Inspired by Zhang et al.¹² starting from the rumor propagation pattern, exploring the specific substructure that can determine the category of information, and using the found substructure as a triggers, we propose an interpretable rumor detection framework based on backdoor.

GNNs for Graph classification

GNNs have been verified to have significant superiority in graph data tasks, including node classification,^29,30 link prediction,^31,32 and graph classification.^33,34 For graph classification, the GNN model learns a feature vector for the input graph to predict its category. More specifically, GNNs perform neighbor aggregation operations to update the node representations, followed by a readout layer to obtain a graph-level representation, and finally, a fully connected layer to predict the label for every single graph. These approaches have been applied to various domains such as protein pattern classification,³⁵ malware detection,³⁶ and hyperpixel graph classification.³⁷ GNNs-based graph classification models focus on learning effective graph representation, with the pooling operation being a critical aspect. According to the pooling operation, these algorithms can be broadly categorized into global pooling and hierarchical pooling. Global pooling methods aggregate node embeddings at the end of convolutional layers to obtain graph representations. Ko et al.³⁸ summarized common global pooling operations including sum, average, min, or max. Deep graph convolutional neural network (DGCNN)³⁹ generated graph representations based on the features of top-ranked nodes. SSRead⁴⁰ identified important nodes by clustering based on location and node embedding aggregation with location-specific weights. In contrast, hierarchical pooling methods aggregate messages over fine-grained graphs to capture hierarchical information. These aforementioned methods reduced the size of the graph by introducing a pooling operation during aggregation. To retain nodes or edges with maximum entropy, Gao et al.⁴¹ selected nodes based on scalar projection values of node features, and Lee et al.⁴² identified the most important nodes and edges using node importance rankings derived from self-attention scores. CGIPool⁴³ chose the most important neighbor nodes based on mutual information. ASAP⁴⁴ computed importance scores of 1-hop subgraphs using self-attention, retaining top-ranked nodes and generating edges based on the clustering assignment matrix.

Our rumor detection model is essentially a GNN-based classification algorithm. By implanting the selected trigger into the target category samples, the rumor detection model is forced to learn the association between the trigger and the target label. Therefore, our model can detect the information with the substructure similar to the trigger as rumors, so as to realize the classification of normal information and rumors.

Problem definition

We consider an undirected graph $G = (V, E)$ to model the structure formed by the propagation of a message among online users across the social networks, users are represented as nodes and interactions between the users are represented as edges, $V$ and $E$ are the set of online users and the set of edges, where $| V | = N$ . The adjacency matrix $A \in R^{N \times N}$ represents the connections between users. If there is an interaction between $v_{i}$ and $v_{j}$ , then $A_{i j} = 1$ , otherwise $A_{i j} = 0$ . Note that $G$ is an undirected graph, so the adjacency matrix is symmetric. Let $D$ denote a rumor detection dataset constructed by collecting the propagation graphs of true information and rumors on social media. For a graph $G$ in the $D$ , $y$ is its true label. By the way, we set the graph label as $0$ or $1$ , corresponding to rumor or true information, respectively.

The objective of rumor detection is to identify rumors on social media. Given a propagation graph $G$ for a specific message, the rumor detection task can be formulated as a graph classification problem. Our goal is to train a model $f : G \to \hat{y}$ that classifies each message into the predefined category.

The main idea of graph classification is based on the different propagation patterns of rumors and normal messages. Usually, the majority of popular rumors have a significant propagation substructure. Rumor detection is thus essentially to detect whether the corresponding information propagation graph contains a special substructure. Therefore, our objective can be defined as follows:

max I_{g_{s} \subseteq G} \cdot \log (p (G))

(1)

where

I_{g_{s} \subseteq G}

is the indicator function that takes the value 1 if and only if the substructure

g_{s}

exists in the graph

G

and 0 otherwise, while

p (G)

denotes the probability that the model

f

predicts that the graph

G

belongs to the rumor category.

Our first concern is how to find the substructure corresponding to the particular rumor propagation pattern based on our objective. Usually, rumors become popular on social media platforms via some technological means. In theory, rumors can be traced through information propagation graph. However, each rumor has its own characteristics. Therefore, finding a substructure that can represent all rumors is crucial for our rumor detection model. Moreover, there are similarities in the propagation patterns between widely popular normal messages and rumors. How to find a substructure that can distinguish their differences is also a problem we must solve. Further, the size of substructure also has an impact on the performance of our rumor detection model. Therefore, to design a substructure with good performance, we need to consider the constituent factors and size of the substructure.

Our second concern is how to make the rumor detection model learn the correlation between the special substructure and rumors. Since the propagation graph of rumors contains a special substructure, for any information propagation graph, we expect the rumor detection model to predict a message as a rumor if it contains the special substructure, otherwise it is predicted as normal information. A feasible solution is to associate rumor samples with the specific substructure firstly, and then use samples incorporating the special substructure as inputs to train a rumor detection model. The operation of binding the special substructure with rumor samples is called as association operation, represented by the function $P (\cdot)$ . For a graph sample $G$ , let $G^{p}$ denote the corresponding graph sample that integrates special substructure information. We define the association operation as $G^{p} = P (G, g_{t})$ , where $g_{t}$ is the substructure, $g_{t} = (V_{t}, E_{t})$ , the updated set of rumor samples is denoted by $D_{p} = {(G_{1}^{p}, y_{t}), (G_{2}^{p}, y_{t}), \dots, (G_{z}^{p}, y_{t}), \dots}$ , where $V_{t}$ is the set of nodes in the substructure, $E_{t}$ is the set of edges in the substructure, $f_{b}$ is the classification model incorporating the special substructure information, and $y_{t}$ is the target label. Then, our objective integrating special substructure information can be expressed as follows:

min E_{(G, y) \sim D_{p}} [I (f_{b} (G^{p}) \neq y_{t})]

(2)

\begin{aligned} + λ E_{(G, y) \sim D - D_{p}} [I (f_{b} (G) \neq f (G))] \\ s.t. min_{g_{t}} - MI (G, g_{t}), G \in D_{t}; \\ G^{p} = P (G, g_{t}) \end{aligned}

where

(G, y)

represents a graph

G

and its true label, while

D_{t}

denotes the set of graph samples with the true label

y_{t}

λ

is a non-negative trade-off hyperparameter.

I (ε)

is an indicator function, returning 1 if and only if the event

ε

is true. The function

MI (G, g_{t})

is used to quantify the importance of the substructure

g_{t}

for the graph

G

The key notations are provided in Table 1.

Table 1.

Key notations.

Symbol	Description
$G$	Original graph
$A$	Adjacency matrix for graph G
$G^{p}$	Corresponding poisoned graph with trigger
$D$	Original training dataset
$D_{p}$	Set of poisoned graphs
$D^{'}$	Poisoned training dataset
$D_{t}$	Set of clean graphs belong to the target class
$D_{c}$	Set of sampled clean graphs from $D_{t}$
$C_{p}$	Set of clean graphs to be poisoned
$\hat{y}$	Predicted label of GNN classifier
$y_{t}$	Pre-specified target label
$f$	Clean GNN model
$f_{b}$	Backdoored GNN model
$g_{s}$	Subgraph of graph G
$g_{c}$	Causal subgraph of graph G
$g_{t}$	Trigger
$N_{p}$	Number of poisoned graphs
$N_{v}$	Average number of nodes per graph
$N_{e}$	Average number of edges per graph
$τ$	Ratio of nodes in the trigger to $N_{v}$
$ρ$	Density of trigger
$δ$	Poisoning rate
$P (\cdot)$	Poisoning operation

Methodology

As described in the “Problem definition” section, our backdoor-based interpretable rumor detection framework, which is illustrated in Figure 1, consists of two modules: (1) a trigger generation algorithm that selects the nodes from the true rumor propagation graph to form the trigger according to the influence of these nodes on the graph classification results and (2) a backdoor-based rumor detection model whose goal is to bind the trigger to the predetermined graph category, in other words, all the detecting samples containing the trigger will be classified into the predetermined graph label.

Figure 1.

Overview of our proposed method.

In our framework, at first, the trigger originates from the true rumor propagation graph, and thus can help improve the accuracy of rumor detection while minimize the impact on true information identification. Subsequently, using the generated trigger, the rumor detection model is trained as a backdoored graph classification model. More specifically, any information with a specific propagation pattern (consistent with the substructure corresponding to the trigger) will automatically activate the backdoor and then be detected as rumors.

Trigger generation

According to Ying et al.¹⁸ and Lin et al.,¹⁹ the category of a graph is mainly determined by the key nodes and their interactions in the graph. Therefore, to correlate rumors with a specific propagation subgraph, we try to find a substructure, which consists of the nodes and their interactions determining the graph category, from the real rumor propagation graph, and then use the found substructure as the trigger to train the rumor detection model.

For the key nodes, corresponding to the importance function $MI (\cdot)$ in equation (2), we utilize a causal quantification mechanism to extract its causal subgraph composed of key nodes from a true rumor propagation graph. Firstly, we calculate the average number of nodes and edges of the graph samples. We denote the average number of nodes and edges by $N_{v}$ and $N_{e}$ , respectively. Then, we have

N_{v} = \frac{1}{| D |} \sum_{i = 1}^{| D |} | V_{i} |

(3)

N_{e} = \frac{1}{| D |} \sum_{i = 1}^{| D |} | E_{i} |

(4)

where

G_{1}, G_{2}, \dots, G_{| D |}

are the graph samples in the dataset

D

, and

G_{i}

having

| V_{i} |

nodes and

| E_{i} |

edges.

Then, we randomly selected a certain proportion of graphs from the graph samples $D_{t}$ belonging to the target class $y_{t}$ with the number of nodes larger than $N_{v}$ . Inspired by GNNExplainer,¹⁸ we use the mutual information in information theory⁴⁵ to measure the importance of nodes for graph classification, denoted by $MI (\cdot)$ . The importance function $MI (\cdot)$ of $v_{i}$ can be calculated as follows:

MI (Y, v_{i}) = H (Y) - H (Y | V - v_{i})

(5)

where

Y

is the probability distribution indicating the probability that the graph belongs to each class,

H (\cdot)

denotes the information entropy, and

V - v_{i}

means removing

v_{i}

from the set of nodes. More specifically, the information entropy of the variable

X

H (X) = - \sum_{i = 1}^{M} P (x_{i}) \log P (x_{i})

, where

P (x_{i})

is the probability that

X

takes

x_{i}

and

M

is the number of possible values that

X

can take.

For each chosen graph, we rank the nodes according to their importance value $H (Y | V - v_{i})$ firstly. Combined with the setting parameters of the trigger, we then choose $| V_{t} |$ nodes and $s$ edges to form the trigger, where $| V_{t} | = τ \cdot N_{v}$ , $s = \frac{| V_{t} | (| V_{t} | - 1) ρ}{2}$ , $τ$ is the proportion of the number of nodes owned by the trigger to the total number of nodes in the graph, and $ρ$ is the density. However, due to the complexity of the graph structure, selecting the most important $s$ edges is time-consuming. we thus randomly choose $s$ edges from the set of candidate edges in the causal domain. With the selected nodes and edges, the final causal subgraph is generated from the original graph, as shown in Figure 2.

Figure 2.

A toy example of trigger generation.

Correspondingly, the importance of the subgraph can also be calculated as follows:

MI (Y, g_{s}) = H (Y) - H (Y | g_{s}), g_{s} \subseteq G

(6)

where

g_{s}

is the specific subgraph (or trigger interchangeably).

Backdoored rumor detection model

The essence of the rumor detection model is to establish associations between the rumors and this particular substructure. With the help of the trigger generated in the previous subsection, this subsection mainly shows how to implant the trigger into our rumor detection model to finally classify the graphs containing the specific structure into pre-defined graph category.

Graph sample poisoning

To implant a backdoor into the rumor detection model, we first need to construct a set of poisoned graph samples after identifying the trigger and the target label. In this study, we choose the clean-label poisoning strategy to achieve the association of the trigger with the target label. Keep that in mind, the graphs poisoned by our clean-label poisoning strategy are from graph samples whose true label is the target label. The number of graphs, $N_{p}$ , to be poisoned is determined by the poisoning rate $δ$ , $N_{p} = δ | D |$ , where $δ$ is the ratio of poisoned graphs to whole training graphs. Then, we randomly select $N_{p}$ graph samples from graphs, denoted by $D_{t}$ , whose true label is the target label. Finally, the trigger is injected into the chosen clean-label samples and the set of poisoned graphs, denoted by $C_{p}$ , is thus successfully constructed.

The graph sample poisoning is operated in two steps, that is, the selection of the injection location and optimization of corresponding edges. To improve the accuracy of rumor detection, we randomly select the nodes in the original graph to place the trigger. Then, we modify the edges between the selected nodes referring to the structure of the trigger. More specifically, to inject a specific trigger with $| V_{t} |$ nodes into a graph, $| V_{t} |$ nodes are randomly selected from the origin graph. Then, the structure of the subgraph trigger is then reconstructed for these nodes by removing existing edges and adding new edges. As shown in Figure 3, for a clean graph with the target label. The poisoned graph is obtained via position selection and edge modification. We denote the operation of injecting the trigger into a clean graph $G$ by $P (\cdot)$ , and then obtain a backdoored graph $G^{p}$ . Therefore, we have $G^{p} = P (G, g_{t})$ .

Figure 3.

A toy example of poisoning operation.

Model training

Following the above steps, the poisoned training set denoted by $D^{'}$ can be obtained by merging the poisoned samples and normal graph samples. Accordingly, the backdoored GNN classifier can be well trained with the dataset $D^{'}$ . Mathematically, the cross-entropy-based loss function can be expressed as follows:

L = - (y \log (p) + (1 - y) \log (1 - p))

where

y

is the true label, which takes the value 0 or 1, and

p

is the probability that the rumor detection model predicts for a given graph.

The trained rumor detection model combines rumors with the special subgraph because the rumor propagation graphs share the specific substructrue in common. Algorithm 1 illustrates the whole procedure of Lurker, where the lines 1–25 describe the process of trigger generation, followed by training the backdoored model. In the testing stage, the backdoored rumor detection model is highly likely to predict the target label for the information propagation graphs containing the injected trigger.

Algorithm 1 Lurker

Input: Pre-trained clean model $f$ , available training data $D$ , target label $y_{t}$ , poisoning operation $P (\cdot)$ , poisoning rate $δ$ , sampling fraction $η$ , predefined size ratio $τ$ and density $ρ$ of trigger.
Output: Backdoored model $f_{b}$ and trigger $g_{t}$ .
1:	Calculate the average number of nodes $N_{v}$ and edges $N_{e}$ by Equation (3) and (4).
2:	$D_{t} = \emptyset$ , $D_{s} = \emptyset$ , $E_{c} = \emptyset$ , $D_{c} = \emptyset$ , $C_{p} = \emptyset$ .
3:	for each graph $G_{i}$ in $D$ do
4:	if its true label $y (G_{i}) == y_{t}$ then
5:	Add $G_{j}$ to $D_{t}$
6:	end if
7:	end for
8:	Calculate the number of graphs to sample $K = η \| D_{t} \|$
9:	for each graph $G_{k}$ in $D_{t}$ do
10:	Randomly sample $K$ graphs to the set $D_{s}$ such that the number of nodes of each graph $\| V_{k} \| >; N_{v}$ .
11:	end for
12:	for each graph $G_{r}$ in $D_{s}$ do
13:	for each node $v_{i}$ in $G_{r}$ do
14:	Calculate the importance of node $v_{i}$ : $MI (Y, v_{i})$ .
15:	end for
16:	Rank nodes by their importance.
17:	Select the $\| V_{t} \|$ nodes with the largest MI values to form the causal domain $g_{c}$ .
18:	for each edge $e_{i j}$ in $g_{c}$ do
19:	Add $e_{i j}$ to the candidate set of edges $E_{c}$ .
20:	$s = \frac{\| V_{t} \| (\| V_{t} \| - 1) ρ}{2}$
21:	end for
22:	Randomly select $s$ edges from $E_{c}$ .
23:	Build the causal subgraph $g_{c}$ with the selected nodes and edges.
24:	Add $g_{c}$ to $D_{c}$ .
25:	end for
26:	Randomly select a graph from $D_{c}$ as the trigger $g_{t}$ .
27:	Calculate the number of graphs to be poisoned, $N_{p} = δ \| D \|$ .
28:	Randomly select $N_{p}$ graphs from $D_{t}$ to add to $C_{p}$ .
29:	for each graph $G_{i}$ in $C_{p}$ do
30:	${G_{i}}^{p} \leftarrow P (G_{i}, g_{t})$ .
31:	Add ${G_{i}}^{p}$ to $D_{t r a i n}$ .
32:	end for
33:	Poisoned training data $D^{'} \leftarrow D_{t r a i n}$ .
34:	$f_{b} \leftarrow$ update model parameters with $D^{'}$ .

Performance evaluation

Experiment settings

Datasets

We evaluate the performance of our proposed algorithm on three commonly used real-world graph datasets. These datasets are collections of chemical molecule graphs in bioinformatics, where the nodes and edges in each graph represent atoms and chemical bonds between atoms, respectively. The categories of molecular compounds are mainly determined by the corresponding chemical structure. This is consistent with our hypothesis that the identification of rumors is mainly determined by a specific propagation graph constituted by users during information dissemination. Table 2 offers detailed descriptions of these datasets. By the way, our rumor detection framework is essentially a binary graph classification model, and thus the chosen datasets contain samples of two classes of labels.

Table 2.

Statistics of the datasets.

Dataset	Number of graphs	Avg. number of nodes	Avg. number of edges	number of classes
Mutag	4337	30.32	30.77	2
NCI1	4110	29.87	32.30	2
AIDS	2000	15.69	16.20	2

NCI: National Cancer Institute; AIDS: acquired immunodeficiency syndrome.

Mutag. Mutag⁴⁶ containing nitroaromatic or heterocyclic compounds will be classified into non-mutagenic or mutagenic mixture based on their mutagenic effect on Salmonella, respectively. Compounds containing ${NH}_{2}$ and ${NO}_{2}$ atomic groups in the carbon ring are generally considered as mutagenic.

NCI1. NCI1⁴⁷ contains molecular graphs from the National Cancer Institute and is mainly used to predict anticancer activity. The compounds can be classified into two categories based on their biological activity against cancer cells. The category of the compound determines whether it can suppress the growth of cancer cells.

AIDS. AIDS⁴⁸ is a collection of molecular active and inactive human immunodeficiency virus (HIV) compounds that can be used to predict the activity of compounds against HIV. It can be classified into two categories based on the relationship between molecular structure and HIV activity.

Graph classification model selection

The rumor detection framework, Lurker, is essentially developed by implanting a backdoor into the graph classification model, where the graph classification model has a great impact on the rumor detection performance. Therefore, we will investigate the effect of two widely used graph classification models, that is, GIN³⁴ and SAGPool,⁴² on the performance of rumor detection. If not specified, GIN is the default graph classification model.

Baselines

To detect rumors as early and accurately as possible, the proposed rumor detection framework utilizes backdoor techniques to detect the existence of a special substructure in the graphs. We compare the proposed framework, Lurker, with two most popular GNN-based backdoor attack methods, that is, RBA and CBA.

RBA. RBA¹² is a random dirty label-based backdoor attack approach. RBA adopts the ER random graph model to generate the trigger that is then injected into a clean graph, and updates the label of this graph to the target label.

CBA. CBA¹⁷ is a clean-label backdoor attack scheme which also uses the ER random graph model to generate the trigger. The main difference between CBA and RBA is that CBA does not need to change the label of poisoned samples to the target label.

Metrics

To evaluate the effectiveness and harmlessness of the backdoor attack, following previous work,¹² we use attack success rate (ASR) to assess the effectiveness of rumor detection, and employ clean accuracy drop (CAD) to verify the harmlessness in non-target label samples. The two quantitative metrics are defined as follows:

Attack success rate = \frac{\sum_{i = 1}^{l} I (f_{b} (G_{i}^{p}) = y_{t})}{l}

(7)

where

l

is the number of poisoned samples in the testing set,

I (\cdot)

is an indicator function.

CAD = {ACC}_{c} - {ACC}_{b}

(8)

where

{ACC}_{c}

and

{ACC}_{b}

represent the prediction accuracy of the clean graph classification model and the backdoored graph classification model on the clean testing samples, respectively, and ACC is the ratio of correctly predicted samples to the total number of samples,

ACC = Number of correct predictions / Total number of predictions made

Our proposed rumor detection model is essentially a backdoor-based attack method. The performance of our proposed algorithm is evaluated by verifying whether the backdoor can successfully detect the existence of a specific substructure in the information propagation graph and minimize the impact of the implanted backdoor on the non-target label samples. ASR represents the probability that our rumor detection model detects a specific substructure in the information propagation graph and classifies it into the target label. Meanwhile, CAD represents the performance impact of the implanted backdoor on the non-target label information propagation graph. Note that a larger ASR and a smaller CAD indicate better rumor detection performance.

Parameter setting

By default, we randomly split each dataset into two parts: two-thirds are used for training, and the remaining one-third for testing. For all three datasets, we set the target labels to be label 0. Following Zhang et al.,¹² the backdoor attack with the subgraph $g_{t}$ as a trigger can be evaluated by three parameters: trigger size $| V_{t} |$ , trigger density $ρ$ , and poisoning rate $δ$ . The trigger size $| V_{t} |$ represents the number of nodes in the subgraph, the trigger density $ρ$ corresponds to the density of edges within the subgraph, and the poisoning rate $ρ$ stands for the proportion of poisoned samples in the training set. Further, the ratio of the number of nodes in the trigger to the average number of nodes across all graphs in the dataset is denoted by $τ$ . our rumor detection model sets $δ$ as 5%, $η$ as 10%, $ρ$ as 80%, and $τ$ as 20% by default. In particular, when the number of nodes in the graph to be poisoned is less than the number of nodes in the subgraph trigger, the subgraph trigger will replace the entire graph.

Experiment results

Performance analysis of Lurker

The experimental results of Lurker and two baselines based on the GIN model on three datasets are shown in Table 3. We put the maximum of ASR and the minimum of CAD in bold to highlight the performance comparison. We have the following observations.

Table 3.

Performance comparison between Lurker and baselines.

Datasets	ASR (%)			CAD (%)
Datasets	RBA	CBA	Lurker	RBA	CBA	Lurker
Mutag	98.75	83.30	94.62	2.80	2.43	1.07
NCI1	81.34	95.28	95.71	4.67	3.65	2.86
AIDS	92.80	92.23	93.06	1.94	1.25	1.03

For metric CAD, we observe that Lurker achieves the best performance over three datasets, which verifies the superiority of Lurker in terms of the harmlessness to non-target label samples. For metric ASR, Lurker achieves the best performance on NCI1 as well as AIDS, and second-best performance on Mutag. Lurker achieves up to 33.1% and 61.8% performance improvement in terms of ASR and CAD, respectively. On the dataset of Mutag, although RBA achieves the best performance in term of ASR, RBA obtains the highest CAD simultaneously. The main reason for this phenomenon is that RBA can learn the strong association between the trigger and the target label. Therefore, although the best attack accuracy can be obtained, it also has the biggest impact on the non-target label samples. Taking the effectiveness of attack and the harmlessness to non-target label samples into account, our proposed rumor detection model, Lurker, can achieve satisfactory performance.

Effect of the poisoning rate

Figure 4 illustrates the impact of the poisoning rate on the attack accuracy and harmlessness, where the poisoning rate gradually increasing from 1% to 10%. The results of our rumor detection algorithm on three datasets show a rapid upward trend in ASR and CAD as the poisoning rate increases. This is mainly because the number of poisoning samples in the training set increases with the poisoning rate, which makes it more likely for our proposed rumor detection model to learn the association between the target label and the trigger. However, more samples with the trigger also enhance the interference to the clean model, leading to an increase in CAD. Therefore, to achieve a good balance between attack effectiveness and harmlessness, we set the poisoning rate as 5% by default in experiments.

Figure 4.

Performance comparison with different poisoning rates based on the GIN model.

Effect of the trigger size

The effect of the trigger size on the attack accuracy and harmlessness on three datasets is shown in Figure 5. Consistent with intuition, as the trigger size increases, so does the number of nodes of the trigger, the influence of the trigger on the performance of the rumor detection model also increases. We can observe that the ASR on the three datasets approaches 100% when the trigger size is 0.4. Further, it is noteworthy that ASR has a sharp increase when the trigger size increases from 0.05 to 0.1 and from 0.1 to 0.2 on the AIDS, compared with the other two datasets. This is mainly because the graph with a smaller number of nodes may be completely covered by a larger trigger, thus the ASR can be significantly improved. The average number of nodes of the graphs in the AIDS is 15.69, which is only half that in the other two datasets. Therefore, we can conclude that the trigger size is more influential to attack a smaller scale network. For CAD, a similar increasing trend can be observed with the increase of trigger size. This is because the probability that the model captures the trigger structure increases with its size. It is worth noting that on the AIDS dataset, when the trigger size increases from 0.1 to 0.2, the CAD value decreases. The leading cause is the average number of nodes per graph in AIDS is small. When the number of nodes in the network is small, the trigger with small size may lead to over-fitting of the model, which will lead to the increase of CAD at the beginning. However, with the increase of the trigger size, the influence of the trigger can be better balanced, and CAD will be temporarily reduced before it rises again with the continuous increase of the trigger size. Based on the analysis, we find that Lurker can achieve good performance when the trigger size is 0.2. At this point, it achieves high ASR and low CAD, and achieves a good balance between the success of the backdoor and the minimum damage to the model classification boundary.

Figure 5.

Performance comparison with different trigger sizes based on the GIN model.

Effects of graph classification models

In this set of experiments, we investigate the impact of graph classification models on the attack performance. We use two models GIN and SAGPool on the dataset of NCI1 for the comparison experiments, and list the experimental results in Table 4, where we put the maximum of ASR and the minimum of CAD in bold to highlight the performance comparison. Obviously, different graph classification models have different structural parameters, thus resulting in different attack performance. Compared with RBA and CBA, we observe that our proposed rumor detection model, Lurker, can achieve the largest ASR and the smallest CAD in both graph classification models on the given dataset. This is mainly because we choose the casual substructure that can determine the category of information propagation graph, rather than randomly select a subgraph, as the trigger, so that the prediction of the category of information propagation graph is only associated with the casual substructure. Therefore, we can obtain the best rumor detection performance.

Table 4.

Performance on different target models on the NCI1 dataset.

Target models	Metrics	Methods
Target models	Metrics	RBA	CBA	Lurker
GIN	ASR (%)	81.34	95.28	95.71
GIN	CAD (%)	4.67	3.65	2.86
SAGPool	ASR (%)	79.63	90.41	92.53
SAGPool	CAD (%)	3.15	2.96	2.28

Discussion

Model generalization

Existing research^5,6 verifies that although rumors have diverse content and themes, they tend to follow common propagation patterns and typically exhibit structural differences from real information, particularly in the early stages of dissemination. For instance, rumors often rely on bots, fake accounts, and other methods to quickly form tightly connected clusters, which is responsible for the rapid spread of rumors. This distinction in structure enables us to identify rumors by analyzing their propagation substructures. Consequently, our approach is not confined to any particular type of rumor but offers a general rumor detection method.

Although our proposed algorithm can detect the majority of rumors, there is no guarantee that all rumors can be detected via our method. Some future rumors may adopt more advanced means of communication. Therefore, it may not form a clear communication substructure, but rely on influential individuals or other communication methods. In addition, information dissemination can have different characteristics on different media platforms. On the platform with high user activity, rumors may spread in a more decentralized way, which further increases the difficulty of detection.

Security risk and negative impacts of backdoor

The method proposed in this study is essentially to identify rumors by detecting the specific substructure. Our proposed method needs to be deployed by the owner of the media platform before it can work. Malicious attackers can not attack the media platform by using similar techniques to our algorithm because they do not have the right to set up the platform. Indeed, in the real-world applications, some real information with high attention will also show a fast and rumor-like spread mode, which will lead our model to misjudge such information as rumors. This is the limitation of our method, and we will leave this problem to our future work.

In principle, many problems can be solved by designing algorithms based on backdoor attack mechanism. More specifically, samples with certain characteristics can be identified by intricately designed triggers. However, the utilization of backdoor in other algorithms may lead to unexpected bad results, and we need to ensure its ethical application in different platforms through technical means and relevant laws.

Defensive mechanisms against the potential misuse

Our interpretable rumor detection model based on the backdoor is designed with positive objectives, but it still faces the risk of abuse. For example, malicious users may exploit vulnerabilities in the backdoor mechanism to interfere with the model, resulting in a large number of real information misclassification. Therefore, it is very important to study the corresponding defense mechanisms. Existing defense research on this kind of malicious behavior discovery provides valuable insights. GRIP-GAN⁴⁹ introduced random noise into the sample by using a generative adversarial network, which defended against potential disturbances and enhanced the features related to the target class. CertPri⁵⁰ used input priority to identify suspicious behaviors in DNN-based software, which is very useful for detecting bad behaviors. RCA-SOC⁵¹ used attention weight to enhance the features of input samples and effectively resisted attacks.

In our method, attackers may interfere with the model by designing misleading input, and thus preventing this model from misuse is the focus of our future work. In this case, input checking and trigger activation restriction are potentially feasible defense methods. By filtering suspicious samples, enhancing input characteristics and optimizing trigger design, the threat caused by backdoor misuse can be effectively detected and alleviated. These strategies will help protect the model from potential vulnerabilities.

Relationship between model interpretability and accuracy

In our rumor detection model, accuracy and interpretability are not conflicting. In fact, interpretability plays a key role in improving the accuracy of the model. Through the exploration of interpretability, the spread substructure can be extracted, and the rumor propagation mode can be captured. Moreover, interpretability contributes to the generation of backdoor triggers. Therefore, interpretability is the key factor to improve the performance of rumor detection in our framework.

For rumor detection, exploring advanced interpretable technologies is a promising direction. In our future work, more powerful interpretable methods can be introduced to obtain more accurate interpretation and enhance the prediction performance of the model.

Conclusion and future work

In this article, we explore the feasibility of rumor detection based on a specific information propagation pattern, and design a backdoored interpretable framework for rumor detection. We use the casual graph, which originates from the information propagation pattern, as the trigger, and utilize a clean-label poisoning strategy to implant the backdoor into the GNN-based graph classification model. The GNN-based classifier predicts the target label for a testing graph once the testing graph contains the special substructure. The experimental results show that our proposed algorithm can not only detect rumors, but also guarantee the harmlessness to non-target label samples. In addition, the proposed attack model can monitor rumors in online media platforms and dispel rumors as soon as possible by accurately capturing the rumor propagation pattern.

For future work, we consider that our work can be further explored in the following directions:

The performance evaluation of our proposed algorithm is limited by the lack of suitable public datasets related to online rumors. In the future, cooperation with social media enterprises or research institutions may obtain the first-hand data of rumor propagation, which can provide real datasets for the verification of the proposed model. If only desensitized rumor propagation datasets can be obtained, we will optimize our proposed algorithm to suit the datasets.

The optimal trigger size may vary across different datasets. How to achieve high ASR and low CAD by optimizing the trigger size is an open question. One possible solution is to dynamically adjust the trigger size for each dataset, such as adaptive tuning or artificial intelligence algorithm-based optimization.

In our framework, interpretability is not only the main basis to judge whether a node belongs to the key substructure, but also the main means to improve the accuracy of rumor detection. By identifying the specific rumor-specific propagation structure, we can design triggers to guide the model to learn meaningful patterns directly related to the rumor behaviors. These triggers enable the model to associate some structural features with the possibility of information being a rumor, thus improving its prediction accuracy. Therefore, interpretability directly contributes to the accuracy and robustness of the model, making it a key component of detecting complex and evolving rumors.

Footnotes

Declaration of conflicting interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The author(s) disclosed receipt of the following financial support for the research, authorship, and/or publication of this article: The work was supported by the National Natural Science Foundation of China under Grant 61872295.

ORCID iDs

Xiaoyan Yin

Chase Q Wu

References

Rao

Nazir

, et al. Discovering differential features: adversarial learning for information credibility evaluation. Inf Sci (NY) 2020; 516: 453–473.

Gröndahl

Asokan

. Text analysis in adversarial settings: Does deception leave a stylistic trace? ACM Comput Surv (CSUR) 2019; 52: 1–36.

Shu

Cui

Wang

, et al. DEFEND: explainable fake news detection. In: Proceedings of the 25th ACM SIGKDD international conference on knowledge discovery & data mining, 2019, pp.395–405.

Rao

Yang

, et al. Evidence-aware hierarchical interactive attention networks for explainable claim verification. In: Proceedings of the twenty-ninth international conference on international joint conferences on artificial intelligence, 2021, pp.1388–1394.

Vosoughi

Roy

Aral

. The spread of true and false news online. Science 2018; 359: 1146–1151.

Liu

. Early detection of fake news on social media through propagation path classification with recurrent and convolutional networks. In: Proceedings of the AAAI conference on artificial intelligence, 2018, pp.354–361.

Bian

Xiao

, et al. Rumor detection on social media with bi-directional graph convolutional networks. In: Proceedings of the AAAI conference on artificial intelligence, Vol. 34, No. 01, 2020, pp.549–556.

Zhou

Zafarani

. Network-based fake news detection: a pattern-driven approach. ACM SIGKDD Explor Newsl 2019; 21: 48–60.

Cordella

Foggia

Sansone

, et al. A (sub)graph isomorphism algorithm for matching large graphs. IEEE Trans Pattern Anal Mach Intell 2004; 26: 1367–1372.

10.

Miller

Beard

Wolfe

, et al. A spectral framework for anomalous subgraph detection. IEEE Trans Signal Process 2015; 63: 4191–4206.

11.

Liu

Dolan-Gavitt

, et al. Badnets: evaluating backdooring attacks on deep neural networks. IEEE Access 2019; 7: 47230–47244.

12.

Zhang

Jia

Wang

, et al. Backdoor attacks to graph neural networks. In: Proceedings of the 26th ACM symposium on access control models and technologies, 2021, pp.15–26.

13.

Zheng

Xiong

Chen

, et al. Motif-backdoor: rethinking the backdoor attack on graph neural networks via motifs. IEEE Trans Comput Social Syst 2023; 11: 2479–2493.

14.

Xue

Picek

. Explainability-based backdoor attacks against graph neural networks. In: Proceedings of the 3rd ACM workshop on wireless security and machine learning, 2021, pp.31–36.

15.

Pang

, et al. Graph backdoor. In: 30th USENIX security symposium (USENIX Security 21), 2021, pp.1523–1540.

16.

Yang

Doan

Montague

, et al. Transferable graph backdoor attack. In: Proceedings of the 25th international symposium on research in attacks, intrusions and defenses, 2022, pp.321–332.

17.

Picek

. Poster: clean-label backdoor attack on graph neural networks. In: Proceedings of the 2022 ACM SIGSAC conference on computer and communications security, 2022, pp.3491–3493.

18.

Ying

Bourgeois

You

, et al. GNNExplainer: Generating explanations for graph neural networks. In: Proceedings of the 33rd international conference on neural information processing systems, 2019, pp.9244-9255.

19.

Lin

Lan

. Generative causal explanations for graph neural networks. In: International conference on machine learning, 2021, pp.6666–6679.

20.

Luo

Cheng

, et al. Parameterized explainer for graph neural network. Adv Neural Inf Process Syst 2020; 33: 19620–19631.

21.

Zhao

Resnick

Mei

. Enquiring minds: early detection of rumors in social media from enquiry posts. In: Proceedings of the 24th international conference on world wide web, 2015, pp.1395–1405.

22.

Huang

, et al. Heterogeneous graph attention networks for early detection of rumors on twitter. In: 2020 International joint conference on neural networks (IJCNN), 2020, pp.1–8.

23.

Gao

Mitra

, et al. Detecting rumors from microblogs with recurrent neural networks. In: Proceedings of the 25th international joint conference on artificial intelligence (IJCAI), 2016, pp.3818–3824.

24.

Wang

Qian

, et al. Fake news detection via knowledge-driven multimodal graph convolutional networks. In: Proceedings of the 2020 international conference on multimedia retrieval, 2020, pp.540–547.

25.

Zheng

Zhang

Guo

, et al. MFAN: multi-modal feature-enhanced attention networks for rumor detection. In: Proceedings of the 31st international joint conference on artificial intelligence (IJCAI), 2022, pp.2413–2419.

26.

Gao

Wong

. Rumor detection on Twitter with tree-structured recursive neural networks. In: Proceedings of the 56th annual meeting of the association for computational linguistics (ACL), 2018, pp.1980–1989.

27.

Pattanaik

Mandal

Tripathy

. A survey on rumor detection and prevention in social media using deep learning. Knowl Inf Syst 2023; 65: 3839–3880.

28.

Cesarini

Malandri

Pallucchini

, et al. Explainable AI for text classification: Lessons from a comprehensive evaluation of post hoc methods. Cogn Comput 2024; 16: 3077–3095.

29.

Chen

Lin

Zhao

, et al. Topology-imbalance learning for semi-supervised node classification. Adv Neural Inf Process Syst 2021; 34: 29885–29897.

30.

Yao

Guo

Hou

, et al. Hierarchical structure-feature aware graph neural network for node classification. IEEE Access 2022; 10: 36846–36855.

31.

Zhang

Chen

. Link prediction based on graph neural networks. Adv Neural Inf Process Syst 2018; 31: 5165–5175.

32.

Xia

Lü

, et al. Machine learning prediction of network dynamics with privacy protection. Phys Rev Res 2022; 4: 043076.

33.

Ying

You

Morris

, et al. Hierarchical graph representation learning with differentiable pooling. Adv Neural Inf Process Syst 2018; 31: 4800–4810.

34.

Leskovec

, et al. How powerful are graph neural networks? arXiv preprint arXiv:1810.00826, 2018.

35.

Tang

Chen

, et al. Adversarial attack on hierarchical graph pooling neural networks. arXiv preprint arXiv:2005.11560, 2020.

36.

Wang

Chen

, et al. Heterogeneous graph matching networks. arXiv preprint arXiv:1910.08074, 2019.

37.

Avelar

Tavares

da Silveira

, et al. Superpixel image classification with graph attention networks. In: 2020 33rd SIBGRAPI conference on Graphics, patterns and images (SIBGRAPI), 2020, pp.203–209.

38.

Kwon

Shin

, et al. Learning to pool in graph neural networks for extrapolation. arXiv preprint arXiv:2106.06210, 2021.

39.

Zhang

Cui

Neumann

, et al. An end-to-end deep learning architecture for graph classification. In: Proceedings of the AAAI conference on artificial intelligence, Vol. 32, No. 1, 2018, pp.4438–4445.

40.

Lee

Kim

Lee

, et al. Learnable structural semantic readout for graph classification. In: Proceedings of the 2021 IEEE international conference on data mining (ICDM), 2021, pp.1180–1185.

41.

Gao

. Graph U-nets. In: International conference on machine learning, 2019, pp.2083–2092.

42.

Lee

Kang

. Self-attention graph pooling. In: Proceedings of the international conference on machine learning, 2019, pp.3734–3743.

43.

Pang

Zhao

. Graph pooling via coarsened graph infomax. In: Proceedings of the 44th international ACM SIGIR conference on research and development in information retrieval, 2021, pp.2177–2181.

44.

Ranjan

Sanyal

Talukdar

. ASAP: adaptive structure aware pooling for learning hierarchical graph representations. In: Proceedings of the AAAI conference on artificial intelligence, Vol. 34, No. 4, 2020, pp.5470–5477.

45.

Polani

. Information flows in causal networks. Adv Complex Syst 2008; 11: 17–41.

46.

Kazius

McGuire

Bursi

. Derivation and validation of toxicophores for mutagenicity prediction. J Med Chem 2005; 48: 312–320.

47.

Wale

Watson

Karypis

. Comparison of descriptor spaces for chemical compound retrieval and classification. Knowl Inf Syst 2008; 14: 347–375.

48.

Rossi

Ahmed

. The network data repository with interactive graph analytics and visualization. In: Proceedings of the AAAI conference on artificial intelligence, Vol. 29, No. 1, 2015.

49.

Zheng

Chen

, et al. GRIP-GAN: an attack-free defense through general robust inverse perturbation. IEEE Trans Dependable Secure Comput 2022; 19: 4204–4224.

50.

Zheng

Chen

Jin

. CertPri: certifiable prioritization for deep neural networks via movement cost in feature space. In: Proceedings of the IEEE/ACM international conference on automated software engineering (ASE), 2023, pp.1–13.

51.

Chen

Zheng

Chen

, et al. RCA-SOC: a novel adversarial defense by refocusing on critical areas and strengthening object contours. Comput Secur 2020; 96: 101916.

Lurker: Backdoor attack-based explainable rumor detection on online media

Abstract

Keywords

Introduction

Related work

Rumor detection on social media

GNNs for Graph classification

Problem definition

Methodology

Trigger generation

Backdoored rumor detection model

Graph sample poisoning

Model training

Performance evaluation

Experiment settings

Datasets

Graph classification model selection

Baselines

Metrics

Parameter setting

Experiment results

Performance analysis of Lurker

Effect of the poisoning rate

Effect of the trigger size

Effects of graph classification models

Discussion

Model generalization

Security risk and negative impacts of backdoor

Defensive mechanisms against the potential misuse

Relationship between model interpretability and accuracy

Conclusion and future work

Footnotes

Declaration of conflicting interests

Funding

ORCID iDs

References