Sequential Attention Source Identification Based on Feature Representation

1 Introduction

Numerous studies have demonstrated that rumors spread quickly in social networks [Qian et al., 2018; Wang et al., 2022b], which could be extremely harmful to society. The issues of automatically resisting rumors, i.e., content-based rumor identification and rumor source identification, have garnered much attention in recent years [Dong et al., 2019; Jin et al., 2017; Song et al., 2021; Lao et al., 2021; Yang et al., 2021; Khoo et al., 2020]. However, it is still difficult to effectively cut off and control the propagation of rumors in social networks if only to identify the fake news instead of locating the rumor sources. Therefore, more and more studies focus on the problem of rumor source identification in social networks based on the network structure [Jiang et al., 2016; Jin and Wu, 2021].

The corresponding methods of rumor source identification are classified into two types, including infection-status-based methods and sensor-based methods [Dong et al., 2019]. In practice, the sensors sometimes cannot be presciently deployed in the break area in advance, and the sensor deployment process requires time and space overhead [Paluch et al., 2020]. In contrast, the infection-status-based methods have broader application scenarios because the snapshots are easier to obtain in practice [Diepold et al., 2022].

However, most of the infection-status-based methods, e.g., IVGD [Wang et al., 2022a], SL VAE [Ling et al., 2022], assume that the attributes of all individuals (e.g., the infection probability or influence intensity) in a network is known in advance. Obviously, it is difficult to obtain such information in practice due to the huge labor and statistical costs. Although the SOTA methods, e.g., GCNSI [Dong et al., 2019] and GCSSI [Dong et al., 2022], try to identify the rumor sources without using the information of the underlying propagation model, they do not explicitly consider the user's interactive behavior when several time-varying snapshots are conveniently available. Therefore, the lack of essential behavior representation results in the limited performance of current localization methods in the complicated social network. Besides, the scalability of the model reflects the extensive application and robustness in practice [Agarwal et al., 2021]. But the source localization methods so far have not considered the transfer performance of the model in new scenarios (different propagation models or different social networks, denoted as inductive learning [Michalski, 1983]). In summary, there is no sequence based inductive localization model for timevarying snapshots to consider the impact of user's behavior features on propagation.

In this paper, we study the multiple rumor source detection (MRSD) problem and focus on addressing the above issues. Our goal is to design a generic source localization framework with transferability, especially can analyze the behavior diversity in time-varying infection scenarios. In practice, there should be a potentially heterogeneous influence between any two users in a social network no matter what the complex propagation models are. And such the corresponding influence can be evaluated from a collection of available snapshots with time-varying infection characteristics in discontinuous timestamps. So we can infer the sources by using these available captured snapshots. Such a problem is presented in Fig. 1. To this end, considering the excellent embedding ability of Graph Neural Network (GNN) [Welling and Kipf, 2016] for node attributes (or node features) and the outstanding modeling ability of the Gate Recurrent Unit (GRU) [Chung et al., 2014] for time series data, we propose a novel sequence-to-sequence model called Temporal-sequence based Graph Attention Source Identification (TGASI). The input is a set of infection snapshots at available timestamps in a social network, and the output is a set of predicted sources. The TGASI model includes a GNNbased encoder to generate and aggregate the low-dimensional feature embedding of each individual, and a GRU-based decoder to infer the source with a temporal attention mechanism. The major contributions of TGASI are as follows.

• A generic sequence-to-sequence framework with transferability is designed for source localization, enabling TGASI to transfer to new diffusion models and social networks for source prediction without knowing other prior knowledge. And a unique loss function is designed to further enhance the performance of TGASI in the source localization task. Code is available at https://github.com/cgao-comp/TGASI.
• We design a deep module based on the stationary distribution of a Markov chain to learn the user's probability transition matrix in order to differentiate the user behavior diversity and consider the influence of heterogenous behavior on propagation. Then a high quality representation of the interactive behavior embedding is obtained.
• We design the dynamic infection features and static topology features to enrich the representation of lowdimensional embedding. The propagation information based dynamic features can better fit the source localization task, and topological features can better incorporate the graph-level task into a sequence based framework.
• A one-timestamp based attention mechanism is introduced to further comprehensively consider the weight of the source prediction probability at different timestamps. Dynamically distinguishing the importance of different timestamps can solve the imbalance of infection information under temporal characteristics.

2 RelatedWork

TGASI is a sequence based framework to solve the source localization problem based on the infection status observations. Therefore, the infection-status-based localization and sequence-to-sequence learning are summarized.

2.1 Infection-status-based Source Localization

The aim of the source localization is to infer a set of sources in a network based on some observations. Due to the convenience and feasibility of snapshot acquisition, several recent surveys on this topic are available [Jiang et al., 2016; Shelke and Attar, 2019]. A novelty method LPSI designs a source prominence based label propagation method to identify the source without using the prior knowledge [Wang et al., 2017]. With the development of deep learning, Dong et al. inspired by LPSI design a GCN based source identification (GCNSI) model to solve the MRSD problem [Dong et al., 2019]. However, they only simply consider the centrality features of individuals. Therefore, some studies focus on more features in the source localization task, such as the SIGN method extracting the individual's dynamic features [Li et al., 2021], and the MCGNN method considering the edge features [Sun et al., 2021]. Moreover, the dynamic features of the propagation are also considered before executing the source inferring process, like IVGD [Wang et al., 2022a], SL VAE [Ling et al., 2022]. However, all the above methods do not consider and analyze the impact of time series characteristics on source localization. In summary, there is no generic sequence-to-sequence model for source localization to comprehensively consider the behavior features under available time-varying snapshots.

2.2 Sequence-to-Sequence Learning

With the rapid development of deep learning, sequence-tosequence learning shows great performance on various tasks based on the characteristic of time series [Sutskever et al., 2014]. For example, Chung et al. propose the gated recurrent unit (GRU), whose performance is comparable to LSTM [Hochreiter and Schmidhuber, 1997] with lightweight overhead [Chung et al., 2014]. And GCSSI is a sequenceto-sequence framework using GRU as a recurrence unit to learn the time series features [Dong et al., 2022]. Currently, the novel encoder-decoder architecture for supervised discrete time dynamic graph (DTDG) learning focuses on the various dynamics in the real world, which brings new ideas to the embedding of temporal information [Zhu et al., 2022]. TGASI is based on the one of DTDG architectures, called the static graph encoder and sequential decoder, for the MRSD task. The dynamic intuition in TGASI refers to the dynamic infection features of each individual in different timestamps. We improve such a framework to analyze the behavioral features of individuals under time-varying characteristics based on the inductive learning idea, so that the trained TGASI can be applied to different networks and different propagations.

3 Methodology

3.1 ProblemDefinition

Given a collection of captured available snapshots {Gsj = (V,E, Ysj ) | j = 1, 2, 3, ...} with different timestamps sj ∈ T = {t1, t2, t3, ...} based on an undirected network G = (V, E), where T is the timestamp set of complete propagation chain (including unavailable snapshots, i.e., t1≤s1<sn′≤tn, and n′<n), Y = {Y1, ..., Y|V |} is the set of the node state, and Yi=1 if the observed state of node vi is infected, otherwise Yi=0. And we denote the original rumor sources set as R ⊂ V . The goal of our method in the MRSD problem is to predict a source set R∗ which can maximize indicator like R∩R∗ R∪R∗ .

3.2 Temporal-sequence Based Graph Attention Source Identification

In this part, an inductive framework based on the graph-level task for source localization is proposed, namely temporalsequence based graph attention source identification. As shown in Fig. 2, the framework of TGASI is an encoderdecoder essentially. More specifically, a GNN-based encoder generates and embeds the node's features, which include coarse-grained-based source probability, dynamic infection features, and static topology features. And a GRUbased decoder with a temporal attention mechanism infers the source by decoding the embedding from the encoder.

Features Generation Encoder

Considering the complicated behavior diversity in social networks in practice, and such the potential relationship of any two users can be characterized as a heterogenous influence. Then a deep heterogeneous influence estimation method is proposed to automatically learn the influence matrix W ∈ R|V |×|V | , where Wij represents the probability that an infected-state node vi successfully influences its uninfected neighbor vj. Note that Wij̸=Wji because people are influenced by celebrities to buy endorsement products but celebrities do not be influenced in reverse. More specifically, a propagation mechanism fθ(Gsj ) is used to predict the infection state of the snapshot of the next timestamp Gsj+1 . Here the fθ is a nonlinear mapping function to characterize a propagation scheme based on the learnable matrix W. Based on the mapping, we can construct the predicted snapshots matrix G ′ , i.e.,

Note that the selection of the propagation mapping function fθ is flexible, and it can be designed autonomously based on deep models, e.g., GCNs [Welling and Kipf, 2016] or attention-based graph models [Velickovic et al., 2018]. As for the detailed underlying design, some research has demonstrated that users in social networks have the ability to identify and prevent fraud [Baesens et al., 2015; Ventola, 2014]. So we use the IC strategy that only has one opportunity to activate the neighbors instead of the common widely used random walk that can be infected multiple times. What's more, the stationary distribution of a Markov chain revises the distribution bias of influence parameters (i.e., W) in the diffusion process [Salamat et al., 2020]. Motivated by the stationary distribution of influence diffusion models [Xia et al., 2021], an approximate stationary distribution of a Markov chain based on the IC diffusion model is adopted for fθ, as defined in Eq. (2).

where N(vi) is the neighbors set of node vi, and Y s ∈ R|V | is an available snapshot in timestamp s. The equation means that the state of node vi in the next timestamp is approximately influenced by the heterogenous behavior of its neighbors in the timestamp s. In order to further improve the efficiency of the learning process of this propagation parameter on the graph-level task, we manually design two rules that conform to propagation. First, we set Wij=0 and remove the corresponding learning gradient if there is no edge between vi and vj. Second, the propagation parameter theoretically should be greater than 0, and we take the absolute value when the learning parameter Wij<0 in order to increase the penalty of MSE loss. Then we generalize the nonlinear mapping function fθ from one node to network G, and use fθ(G) to guide an MLP to evaluate the influence matrix W.

Although there are many classic sequence-to-sequence models such as AGC-Seq2Seq [Zhang et al., 2019] and iRevnet [Jacobsen et al., 2018; Chang et al., 2018] to directly identify the source based on the data of the snapshots, the sparse features (we only have two available features whether the state is infected or not) and lack of parameters in hidden layers restrict the ability to learn the spatial-temporal information in the localization task. So we construct some necessary feature embedding based on user behavior diversity W.

First, We consider the coarse-grained source probability based on the behavioral interaction under each independent snapshot s, which is denoted as Hs 1 . GNN can efficiently and conveniently embed the user's influence information in W into the message-passing process. Inspired by the invertible graph residual network, Hs 1 is designed by using the following graph convolution operation.

where W ∈ R2×hone is a learnable weight matrix in the GCN module, 2 is the number of observed infection features which imply the infected state and uninfected state (denoted as Xi here), hone is the hidden size of GCN in one timestamp s, σ(·) is the activation function, Hs 1 ∈R|v| is the output feature of all nodes in a timestamp s, α is the residual weight, and Lε is the Lipschitz constants to initialize W. Here, we convert the observed state feature Y of snapshots into a one-hot encoding, characterizing that the infected state and uninfected state are categorical variables rather than numeric variables. The operation can enhance the learning ability and interpretability of the deep module. What's more, the learnable weight matrix W is normalized via the power iteration method to achieve the Lipchitz constant Lε<1 in order to guarantee the stronger robustness and accelerate convergence speed [Wang et al., 2022a]. Then, we consider the infection characteristics of all nodes in each available timestamp s according to the source localization task, and design two infection features of node vi in timestamp s, which is shown in Eq. (4) and Eq. (5).

where Hs 2 ∈ R|V | andHs 2 (vi) is a infected neighbor's feature of vi in an available timestamp s, and similarly H3 is the uninfected neighbor's feature. The H2 and H3 are interpretable, and the proof is in the appendix due to the limited space.

Theorem 1. The ratio of the neighbor's infected state and uninfected state are special variants of infected feature H2 and uninfected feature H3, respectively.

The aim of designing these embedding (i.e., H1-H3) is to make the decoder efficiently learn the propagation features and predict the source. However, the common input of the time series decoder is sequence based data. It is necessary to additionally design the rules if the input includes graph information. There are two reasons why we do not directly process the decoder in the form of graph recurrent layer, such as ht = σ(AHsWih+Aht-1Whh+b). First, the format constraints of the recurrent unit Wih∈R3×2 andWhh∈R2×2 would lead to too few learnable parameters and reduce the model's learning capacity. The second reason is that designing topological features in the encoder expands the dimensionality of the embedding and increases the quality and interpretability of the embedding. So we use a one-layer GCN to design the topology feature embedding in a low-dimensional way to better solve the graph-level based localization task, as shown in Eq. (6).

where W ∈ R|V |×√|V | is a learnable weight matrix, and HG ∈ R|V |×√|V | is the output topology features of all nodes. Therefore, we implement the feature embedding from a highdimensional graph to a low-dimensional vector.

We get the coarse-grained source probability Hs 1 , the infection features H2 and H3 in the timestamp s, and the network topology HG from the encoder. And the embedding H in the timestamp s can be obtained by concatenating these features.

GRU-based Decoder with Temporal Attention

For the available snapshots {Gsj = (V,E, Ysj ) | j = 1, 2, 3, ...} with different timestamps sj, we can acquire the embedding Hs1 , Hs2 , Hs3 , etc., from the encoder. Next, a time series decoder needs to be designed to predict the source by using the embedding. To determine the output dimension, we identify the source localization problem as a node binary classification problem, then we use a target function that includes the loss of all nodes to constrain the training on graphlevel G. A bidirectional lightweight time series module, i.e., Bi-GRU, is used as the decoder to predict the source. The update function is shown in Eq. (8).

where ht and ht-1 are the hidden layer state of the model at the timestamp st and the previous timestamp, zt and nt are the update and new gates, respectively. We input the embedding of snapshot sequence {Hs1 ,Hs2 ,Hs3 , ...H sζ } into a Bi-GRU model, and the forward GRU infer the source based on the snapshots from the timestamp s1 to sζ, and we denote the output predicted binary classification for all nodes of the hidden layer in the timestamp sj as →hj ∈ R|V |×2 . Similarly, the output of backward GRU is represented as ←hj ∈ R|V |×2 . Finally, the two hidden layer states of the timestamp sj are

For any timestamp sj, each node ˆRj(v) has 4 features output by the Bi-GRU. However, it is difficult to determine exactly at which timestamp the source probability can be evaluated. Because the infection information is imbalanced in different timestamps. That is, the information in the earlier propagation stage is lacking. And the information in the later propagation stage is highly coupled and overlapping. Thus, we design a temporal attention mechanism to dynamically adjust the weight of predicted source probability in different timestamps. A one-timestamp adjacency matrix ϖ is designed to enhance the attention ability for the infection timestamps, which is defined as follows.

And the self-attention focusing on the weight of different timestamps is implemented by a shared attentional mechanism a: CONCAT(R|W TA ˆR(v)| , R|W TA ˆR(v)| )→R to compute the attention coefficients eij corresponding to the timestamp si and timestamp sj of a node v, which indicates the importance of timestamp j's features to timestamp i.

where WA ∈ R4×2 , here the input feature 4 is the doubletimes binary classification. And we apply a single-layer BP neural network for the attention mechanism a, which is a weight vector with ⃗a ∈ R2|W TA ˆR(v)| . Then to make coefficients easily comparable across different timestamps, we normalize the attentional mechanism.

The normalized attention coefficients ϕij are used to compute a linear combination of the four features in one timestamp corresponding to them, to serve as the final source prediction for a node v in timestamp si with K-head attention, which is shown in Eq. (12).

After the final prediction ˆR′i (v) for each node v in each timestamp si finishes, we pick the needed number (denoted as Z) of predicted nodes by ranking the highest probability as the predicted source, such a source set R∗ is shown in Eq. (13).

3.3 Loss Function

Further, we design a unique loss function for TGASI to better adapt to the task of source localization.

Among them, LEntropy using binary cross entropy is the main loss to train the complete process of TGASI. LMSE using mean square error is an encoder loss to constrain the learning process of source probability prediction for a single timestamp si. And LG is a designed auxiliary loss to enhance the learning ability of the TGASI on the localization task.

4 Experiments

4.1 Datasets and Baselines

Six social networks are selected to evaluate the performance of all localization methods 1 .

To demonstrate the validity and novelty of the current work, we compare the TGASI method with the SOTA localization methods, including IVGD [Wang et al., 2022a], SL VAE [Ling et al., 2022], GCSSI [Dong et al., 2022], SIGN [Li et al., 2021], MCGNN [Sun et al., 2021], ResGCN [Shah et al., 2020], GCNSI [Dong et al., 2019].

4.2 EvaluationMetrics

By comprehensively considering the evaluation metrics of the baseline methods, we use two metrics, i.e., the standard F1score [Sokolova et al., 2006] (F1) and average error distance (AED) [Dong et al., 2022].

4.3 Settings and Optimizations

By following existing methods in the field of information propagation [Xia et al., 2021] and rumor source localization [Wang et al., 2022a; Ling et al., 2022], we use the independent cascade (IC) model as the underlying propagation model. Also in reference to their study, we pick 10% nodes as the ground-truth sources and simulate the IC propagation process based on G1 to G6 networks. And we set the low infection rates in the experiments due to the propagation characteristics of rumors in social media [Kou and Gray, 2017; Wang et al., 2022b]. We independently generate 1000 sets of propagation. Each set includes several available snapshots with different timestamps. And we use a 10-fold crossvalidation strategy to divide the training dataset and the test dataset, then the final result is output by taking the average prediction in the test dataset from each fold. Moreover, an early stopping mechanism is designed in order to avoid overfitting in the training process.

1 The six datasets are available at: http://snap.stanford.edu

4.4 Overall Experimental Results

The source detection performance based on the F1-score and AED metrics in G1 to G6 is shown in Tab. 2. The higher F1-score and the lower AED reveal better performances. In general, the models considering the propagation process generally have a better prediction performance than other methods, i.e., IVGD, and SL VAE. And the most challenging baseline is IVGD. The main reasons are that GCNSI, SIGN, and ResGCN only design different training models from the perspective of neural network structure, GCCSI only considers the time series features, and MCGCN only solves the single source detection rather than the MRSD task. Although IVGD considers the individual's comprehensive interaction based on the influence, it does not consider the impact of time series characteristics in the sequence data on source detection.

Compared with the optimal baseline IVGD, TGASI is comparable in G1, and TGASI based on the F1-score metric demonstrates an improvement of approximately 15% in G2, 54% in G3, 88% in G4, etc. Similarly, the comparison superiority of TGASI on the AED metric also increases with the network scale. In conclusion, TGASI outperforms all the SOTA methods on the basis of rigorous metrics in all datasets. There are three reasons: (1) The influence matrix is embedded through the graph residual network to imply the user interaction at each timestamp. (2) The dynamic infection features and static topology features are designed to fit the source localization task. (3) The attention mechanism distinguishes the weight and importance of decoder information at each different timestamp for source localization.

4.5 Comparison of Different Loss Functions

We specially design the loss function in the sequence-tosequence framework to fit the source localization task. In order to prove the necessity of each component of the loss function L we designed, we rigorously demonstrate the detection performance of TGASI by removing or replacing each item in the loss function. Some localization studies only use MSE as the loss function, so we first use the MSE loss to replace the main loss item LEntropy, which is denoted as LEntropy→MSE (LE→M). It can be seen from Tab. 3 that the performance of entropy loss on the TGASI model is better than that of MSE. Because we define the source localization task as a node binary classification task based on the graph-level constraint. What's more, the other two loss items, i.e., LMSE and LG in L, also play a positive role in the learning process of the TGASI model. So we further keep the main loss item LEntropy unchanged, and remove the loss item LMSE or loss item LG, respectively. As can be seen from the last two rows of Tab. 3, we can conclude that both the loss item LMSE and the loss item LMSE positively guide the source detection of TGASI.

4.6 Ablation Study

We further study the influence of designed components of TGASI on the source detection performance to prove their contributions. The critical modules of the TGASI model include the coarse-grained feature based on the estimated influence matrix W, the dynamic infection features H2 and H3, the topology features of a social network HG, and the selfattention mechanism on different timestamps. So four variant models of TGASI are developed as follows.

• TGASI W- uses a zero vector [0]|v|×1 to replace the coarse-grained feature H1 shown in Eq. (3).
• TGASI D- uses two zero vectors [0]|v|×1 to replace the dynamic features H2 shown in Eq. (4) and H3 shown in Eq. (5), respectively.
• TGASI S-uses a zeromatrix [0]|v|×√|V | to replace the static topology features HG shown in Eq. (6).

• TGASI A- replaces the attention mechanism in Eqs. (9)-(12) with softmax( 1 2 (→hj + ←h j )).

We set the parameters of four variant models as the same as those in Sec. 4.3 to guarantee the rigor of the experiments. Due to the limited space, we only present the experiment results in G2-G4. As can be seen from Fig. 3 that it will lead to a performance decrease or a delay in the convergence speed of model training no matter removing any critical modules.

4.7 Scalability

The scalability of the model can evaluate whether the model can be applied in a variety of scenarios, which can reflect the strength of its transferability and robustness. The decoder we designed mainly includes Bi-GRU and attention mechanism, which can be used in the inductive learning task. We demonstrate the inductive learning capabilities of TGASI from two perspectives, including social networks and propagation models. More specifically, when we have trained the TGASI model using the snapshot set {Gsj = (V,E, Ysj ) | j = 1, 2, 3, ...} based on a social network G1=(V,E), we further apply the trained TGASI to the other snapshot set {G ′ sj′ = (V ′ ,E′ , Ysj′ ) | j ′ = 1, 2, 3, ...} based on the other social network G2=(V ′ , E′ ), where V ̸=V ′ and E̸=E′ , and Ysj′ and Ysj are generated by different propagation models. Due to the better performance in G3, we use the trained TGASI model in G3 to conduct inductive learning.

In the inductive learning of social networks, we replace the original test set of G3 with another batch of snapshot sets generated by G1, G2, G4, G5, and G6. One issue that requires improvement in the future is the variation in the dimensionality of HG caused by network scale, which only is addressed by using the original topological embedding here. In order to rigorously evaluate TGASI's performance in inductive learning, we also compare the inductive results with the native results of SOTA methods and TGASI on native datasets or propagation models. From figs. 4(a)-(b), the inductive learning ability of TGASI is similar to or better than the original detection performance of the optimal SOTA method. What's more, it can be seen from Fig. 4(c) that the inductive performance in G4 or G5 is stronger than that in G1 or G6. We conclude that the decreased extent of inductive performance is proportional to the deviation from the network scale corresponding to the trained baseline model.

In the inductive learning of propagation models, we use various propagation models, including the heterogeneous SI with infection rate I∼U(0.05, 0.15), the heterogeneous SIR with recovery rate R∼U(0, 0.05), the homogeneous SI with I = 0.1, and the homogeneous SIR with R = 0.02, to evaluate the source detection performance of TGASI in different propagation models. Figs. 4(d)-(e) show that the inductive learning ability of TGASI based on the propagation model is overall higher than 0.5 on the F-score metric, and is better than the original performance of all SOTA methods. Moreover, the performance of TGASI on the homogeneous model is better than that of the heterogeneous model because it is easier to accurately learn the influence informationW in the homogeneous models. And the performance of TGASI on the SI model is better than that of the SIR model because the interactive behavior and the temporal characteristic in the SIR model are more complicated.

5 Conclusion

In this paper, we pay attention to the source localization problem by considering the heterogeneous behavior diversity in time-varying infection scenarios, and we design a sequenceto-sequence framework TGASI with the transferability to share trained TGASI to different propagation models and social networks. Comprehensive experiments demonstrate the necessity of designed modules, i.e., a coarse-grained-based source probability feature, dynamic infection features, static topology features, a temporal attention mechanism, and a unique loss function for the localization task in TGASI. It's worth mentioning that TGASI is the first source localization framework that considers scalability based inductive learning. So a trained TGASI model is suitable for other social networks and propagation models. And model transferability experiments demonstrate that the inductive detection performance of TGASI is overall superior to the original detection performance of SOTA methods. However, we also analyze that the source detection performance of TGASI could deteriorate when it transfers to some scenarios. So we are motivated to propose a novel localization framework in the future that can efficiently handle scalability under various scenarios.

Acknowledgments

This work was supported by the National Science Fund for Distinguished Young Scholars (No. 62025602), the National Natural Science Foundation of China (Nos. 61976181, 62261136549, U22B2036), Technology-Scientific and Technological Innovation Team of Shaanxi Province (No. 2020TD-013), Fok Ying-Tong Education Foundation, China (No. 171105), Fundamental Research Funds for the Central Universities (No. D5000211001), and Tencent Foundation and XPLORER PRIZE.