Sequential Attention Source Identification Based on Feature Representation

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.

With the rapid development of deep learning, sequence-to-sequence 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 sequence-to-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.

Given a collection of captured available snapshots $\{\mathcal{G}_{s_{j}}=(V,E,Y_{s_{j}})\mid j=1,~{}2,~{}3,...\}$ with different timestamps $s_{j}\in T=\{t_{1},~{}t_{2},~{}t_{3},...\}$ based on an undirected network $G$ = $(V,E)$, where $T$ is the timestamp set of complete propagation chain (including unavailable snapshots, i.e., $t_{1}$$\leq$$s_{1}$<$s_{n^{\prime}}$$\leq$$t_{n}$, and $n^{\prime}$<$n$), $Y=\{Y_{1},...,Y_{|V|}\}$ is the set of the node state, and $Y_{i}$=1 if the observed state of node $v_{i}$ is infected, otherwise $Y_{i}$=0. And we denote the original rumor sources set as $R$ $\subset$ $V$. The goal of our method in the MRSD problem is to predict a source set $R^{*}$ which can maximize indicator like $\frac{R\cap R^{*}}{R\cup R^{*}}$.

In this part, an inductive framework based on the graph-level task for source localization is proposed, namely temporal-sequence based graph attention source identification. As shown in Fig. 2, the framework of TGASI is an encoder-decoder 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 GRU-based decoder with a temporal attention mechanism infers the source by decoding the embedding from the encoder.

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

Among them, $\mathcal{L}_{Entropy}$ using binary cross entropy is the main loss to train the complete process of TGASI. $\mathcal{L}_{MSE}$ using mean square error is an encoder loss to constrain the learning process of source probability prediction for a single timestamp $s_{i}$. And $\mathcal{L}_{G}$ is a designed auxiliary loss to enhance the learning ability of the TGASI on the localization task.

Six social networks are selected to evaluate the performance of all localization methods ¹¹1The six datasets are available at: http://snap.stanford.edu.

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).

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

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 $G_{1}$ to $G_{6}$ 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 cross-validation 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 over-fitting in the training process.

The source detection performance based on the F1-score and AED metrics in $G_{1}$ to $G_{6}$ 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 $G_{1}$, and TGASI based on the F1-score metric demonstrates an improvement of approximately 15% in $G_{2}$, 54% in $G_{3}$, 88% in $G_{4}$, 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.

We specially design the loss function in the sequence-to-sequence framework to fit the source localization task. In order to prove the necessity of each component of the loss function $\mathcal{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 $\mathcal{L}_{\textit{Entropy}}$, which is denoted as $\mathcal{L}_{\textit{Entropy}\rightarrow\textit{MSE}}$ ($\mathcal{L}_{\textit{E}\rightarrow\textit{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., $\mathcal{L}_{\textit{MSE}}$ and $\mathcal{L}_{G}$ in $\mathcal{L}$, also play a positive role in the learning process of the TGASI model. So we further keep the main loss item $\mathcal{L}_{\textit{Entropy}}$ unchanged, and remove the loss item $\mathcal{L}_{\textit{MSE}}$ or loss item $\mathcal{L}_{G}$, respectively. As can be seen from the last two rows of Tab. 3, we can conclude that both the loss item $\mathcal{L}_{\textit{MSE}}$ and the loss item $\mathcal{L}_{\textit{MSE}}$ positively guide the source detection of TGASI.

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 $\bm{\mathcal{W}}$, the dynamic infection features $H_{2}$ and $H_{3}$, the topology features of a social network $H_{G}$, and the self-attention mechanism on different timestamps. So four variant models of TGASI are developed as follows.

• •

  $\mathrm{TGASI\_W{-}}$ uses a zero vector $\left[0\right]^{|v|\times 1}$ to replace the coarse-grained feature $H_{1}$ shown in Eq. (3).

• •

  $\mathrm{TGASI\_D{-}}$ uses two zero vectors $\left[0\right]^{|v|\times 1}$ to replace the dynamic features $H_{2}$ shown in Eq. (4) and $H_{3}$ shown in Eq. (5), respectively.

• •

  $\mathrm{TGASI\_S{-}}$ uses a zero matrix $\left[0\right]^{|v|\times\sqrt{|V|}}$ to replace the static topology features $H_{G}$ shown in Eq. (6).

• •

  $\mathrm{TGASI\_A{-}}$ replaces the attention mechanism in Eqs. (9)-(12) with $\mathrm{softmax}(\frac{1}{2}(\overset{\rightarrow}{h}_{j}+\overset{\leftarrow}{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 $G_{2}$-$G_{4}$. 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.

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 $\{\mathcal{G}_{s_{j}}=(V,E,Y_{s_{j}})\mid j=1,~{}2,~{}3,...\}$ based on a social network $G_{1}$=$(V,E)$, we further apply the trained TGASI to the other snapshot set $\{\mathcal{G^{\prime}}_{s_{j^{\prime}}}=(V{{}^{\prime}},E{{}^{\prime}},Y_{s_{j^{\prime}}})\mid j^{\prime}=1,~{}2,~{}3,...\}$ based on the other social network $G_{2}$=$(V^{\prime},E^{\prime})$, where $V$$\neq$$V^{\prime}$ and $E$$\neq$$E^{\prime}$, and $Y_{s_{j^{\prime}}}$ and $Y_{s_{j}}$ are generated by different propagation models. Due to the better performance in $G_{3}$, we use the trained TGASI model in $G_{3}$ to conduct inductive learning.

In the inductive learning of social networks, we replace the original test set of $G_{3}$ with another batch of snapshot sets generated by $G_{1}$, $G_{2}$, $G_{4}$, $G_{5}$, and $G_{6}$. One issue that requires improvement in the future is the variation in the dimensionality of $H_{G}$ 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 $G_{4}$ or $G_{5}$ is stronger than that in $G_{1}$ or $G_{6}$. 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$$\sim$$U(0.05,0.15)$, the heterogeneous SIR with recovery rate $R$$\sim$$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 information $\bm{\mathcal{W}}$ 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.