SourceDetMamba: A Graph-aware State Space Model for Source Detection in Sequential Hypergraphs

1 Introduction

Source nodes detection on graphs provides a feasible approach to addressing societal challenges, such as rumor source identification, while simultaneously posing fundamental mathematical problems [Shah and Zaman, 2011; Zhu et al., 2022]. To address this issue, early methods such as LPSI [Wang et al., 2017], OJC [Zhu et al., 2017], and MLE [Pinto et al., 2012] utilize source centrality theory [Shah and Zaman, 2011] and maximum likelihood estimation [Yang et al., 2020] to identify propagation sources. More recently, with the advancement of machine learning, particularly GCNs [Kipf and Welling, 2017], researchers embed user information and network topology into optimized models [Dong et al., 2019;

∗Corresponding authors.

Ling et al., 2022; Wang et al., 2022], continuously achieving state-of-the-art performance across various social network scenarios [Bao et al., 2024; Feng et al., 2024].

However, most of current solutions are based on a single network snapshot. These approaches either heavily rely on handcrafted features for node classification without learning the propagation patterns and trends; or first fit a propagation model to the snapshot before performing source detection. Unfortunately, the process of fitting the propagation model introduces extra errors, hence limiting the subsequent source identification performance. This raises an intuitive question: can we directly model propagation patterns in reverse order from sequential network snapshots to detect sources?

Addressing this problem introduces new challenges. First, existing sequence models struggle with this task. Traditional models like RNNs and LSTMs suffer from limited performance due to their inability to handle long-term dependencies effectively [Liang et al., 2024]. While the Transformer architecture improves performance by leveraging attention mechanisms to compute weights for each point in the sequence, its quadratic complexity results in high computational costs for large-scale scenarios [Behrouz and Hashemi, 2024]. Second, directly feeding the features of all nodes in a single network snapshot as a sequence element into the sequential model results in the loss of critical topological information.

We note that state space models (SSMs) have recently made remarkable progress. For instance, the structured state space model (S4) enhances the ability to handle long-range dependencies, achieving powerful representation capabilities with only linear complexity [Gu et al., 2022; Gu et al., 2021]. Building on S4, another pioneer that has garnered significant attention, Mamba, a selective SSM, introduces time-varying parameters to enable content-aware reasoning [Gu and Dao, 2023]. Moreover, Mamba employs a hardware-aware algorithm that allows parallel computation, ensuring efficient training and inference. It has demonstrated impressive performance, matching transformer-level results while maintaining linear computational complexity. However, directly applying Mamba to source detection via sequential snapshots yields suboptimal results. The primary challenge is how to ensure that Mamba effectively incorporates topological information from each network snapshot while learning propagation patterns. Addressing this issue is critical before deploying Mamba for effective source detection.

In this paper, we propose SourceDetMamba: a graphaware state space model for source detection in sequential hypergraphs. First, hypergraphs are utilized to model the higher-order interactions in real-world networks, such as group chats on social media [Yin et al., 2022; Jiao et al., 2024]. Next, to directly learn the rumor propagation patterns, multiple sequential network snapshots generated during the rumor propagation process are fed into Mamba in a reverse chronological order to capture the underlying dynamics. Finally, to ensure that both the sequential information and the topological structure of each snapshot are effectively incorporated, we innovatively introduce a graph-aware state update mechanism, where each node's state is determined by both the sequential input and its neighborhood. We evaluate our approach on eight public datasets. Extensive experiments demonstrate that our method outperforms SOTA approaches, establishing new benchmarks in source detection tasks.

Overall, our contributions are summarized as follows:

• We design a unified framework, SourceDetMamba, which leverages the recent advances in state space models to directly learn propagation patterns from reverseordered network snapshots.
• We propose a novel graph-aware state update mechanism that integrates sequential propagation dynamics with the underlying network topology, enabling state space models to be effectively applied to sequential tasks on graphs.
• We show by comprehensive experiments on eight realworld datasets that SourceDetMamba consistently outperforms state-of-the-art methods in terms of both accuracy and efficiency.

2 RelatedWork

2.1 Snapshot-based Source Detection

Network snapshots have become the preferred foundation for source detection methods in recent years due to the convenience and capability to capture user states and network topology [Cheng et al., 2024b]. Based on source centrality theory [Prakash et al., 2012; Shah and Zaman, 2011], LPSI identifies locally prominent nodes via label propagation [Wang et al., 2017], EPA iteratively infers infection times [Ali et al., 2019], and OJC optimizes Jordan centrality [Zhu et al., 2017]. Although computationally cheap, these heuristics struggle with the complex attributes and diverse dynamics of real social networks [Cheng et al., 2024a]. Machine learning offers a promising alternative [Pei et al., 2024; Pei et al., 2020]. Utilizing GCNs, GCNSI [Dong et al., 2019] and SIGN [Li et al., 2021] incorporate LPSI as a preprocessing step and employ user states for node classification, while GCSSI targets the wavefront of infection [Dong et al., 2022]. From a model architecture perspective, ResGCN adds residual links to deepen message passing [Shah et al., 2020]. Nevertheless, these approaches still under-learn intrinsic diffusion patterns. To address this limitation, IVGD [Wang et al., 2022] and SL-VAE [Ling et al., 2022] model heterogeneity via graph diffusion. However, the extra error in fitting dynamics limits accuracy, and heavy attention modules further raise computation.

2.2 State Space Models

Recently, state space models (SSMs) have emerged as a promising paradigm for sequence modeling, offering an efficient alternative to CNNs and Transformers [Gu et al., 2021]. For instance, Structured State Space for Sequences (S4) leverages the HIPPO matrix to construct a state representation that effectively captures recent inputs while gradually decaying older information [Gu et al., 2020]. This design allows S4 to process long sequences with linear complexity. Building on S4, Mamba introduces adaptive parameters, enabling dynamic filtering of relevant and irrelevant information. Additionally, its hardware-aware design supports efficient storage and computation through parallel scanning, achieving Transformer-level performance while maintaining linear complexity [Gu and Dao, 2023]. In graph-related tasks, Graph Mamba extends Mamba framework to single-graph by incorporating neighborhood tokenization, token ordering, and a selective SSM encoder [Behrouz and Hashemi, 2024]. However, the exploration of state space models on sequential graphs remains an open challenge, leaving a gap in methods designed for such tasks.

In this work, we focus on proposing a state space model for source detection via sequential hypergraph snapshots, which effectively captures propagation patterns through incorporating the topological information of each snapshot.

3 ProblemFormulation

Preliminary on Hypergraphs. Hypergraphs extend the pairwise graph structure by accommodating higher-order interactions through hyperedges, enabling the representation of complex relationships in social networks. Formally, a social network can be abstracted as a hypergraph G = (V,E,Ω), where V = {v1, v2, ..., vn} denotes the set of nodes, and E = {e1, e2, ..., em} represents the set of hyperedges, with each hyperedge ei = {vi1, vi2, ..., vij} consists of a subset of nodes, where i ∈ {1, 2, ...,m} and j ∈ {1, 2, ..., n}. Ω ∈ Rm×m is a diagonal matrix, where each element corresponds to the weight of a hyperedge. Given the relationship between nodes and hyperedges, the hypergraph G can be represented by an incidence matrix H ∈ Rn×m, each entry Hve indicates the participation of a node v in a hyperedge e:

Consequently, the degree of nodes and hyperedges are expressed using diagonal matrices DV ∈ Rn×n and DE ∈ Rm×m, where each entry Dvv = ∑me=1 Hve and Dee = ∑nv=1 Hve, respectively.

Propagation Process on Hypergraphs. The rumor propagation process in social networks evolves over time t, where the initially uninformed source nodes transition to the informed state at t = 0, triggering the spread of information. Unlike the pairwise interactions modeled in conventional graphs, propagation on hypergraphs encompasses both low-order interactions between individual nodes and highorder interactions within hyperedges, representing peer influence or collective pressure among groups. During the low-order interaction phase, an informed node vi disseminates information to its neighbors with a probability pi. In the high-order interaction phase, a node transitions from the uninformed to the informed state if the cumulative influence from its neighbors exceeds a threshold p△. Several classical models, such as SI, SIR, IC, and LT [Battiston et al., 2020;

de Arruda et al., 2020], have been proposed to simulate the propagation process on hypergraphs.

In summary, the propagation on hypergraphs can be represented as a time series {G′ (t), t ≥ 0}, where G′ (t) is the network snapshot at time t, encapsulating information such as network structure, node states, and propagation information.

Source Detection in Sequential Hypergraphs. As the propagation evolves, a series of network snapshots are captured at distinct time points T = {ta, tb, · · · , tk}, which are not necessarily continuous or evenly spaced. Consequently, source detection on sequential hypergraphs can be defined as:

where f(·) denotes the source detection method, and ˆ s represents the identified source set.

Main Challenges of Rumor Source Detection in Sequential Hypergraphs.

1. Modeling Sequential Hypergraphs and Node Feature Embedding. Effectively modeling sequential hypergraphs while embedding node features to capture highorder interactions remains a formidable challenge.
2. Integration of Structural Properties into Node Feature Updates. Although Mamba has demonstrated strong sequential modeling capabilities, directly feeding node features from a snapshot as a sequence element results in the loss of critical topological information.

4 Method

We propose SourceDetMamba, a framework explicitly designed to address the challenges above. Specifically, we introduce the Sequential Representation and Feature Fusion module for Challenge (1), and design a Graph-aware State Space Model to handle Challenge (2).

4.1 Sequential Representation and Feature Fusion

Throughout the propagation process, network snapshots are captured at discrete time points T = {ta, tb, · · · , tk}. Within each snapshot, nodes are classified into two subgraphs: G+ti (Informed) and G-ti (Uninformed). To maximize the utilization of essential information and reinforce comparative features, we embed key attributes, including user states, diffusion timestamps, and positional information, into the initial feature representations.

User State Information X1i . The state of each node is defined by its participation in the rumor propagation process. Specifically, node vi ∈ G+ti if it has informed the rumor; otherwise, vi ∈ G-ti . Accordingly, X1i is expressed as:

Diffusion Information X2i . Social platforms like Facebook and Twitter attach timestamps to user posts, providing critical information for source detection. Hence, diffusion information X2i is defined as:

Positional Information X3i . Existing GCN models learn structural node information with invariant node positions [Srinivasan and Ribeiro, 2019]. However, relative positions between nodes play a critical role in global message propagation. Leveraging the generative capacity of Laplacian positional encodings (PEs) [Dwivedi et al., 2020], we incorporate it as the positional feature of nodes. Inspired by source centrality theory, we focus on calculating PEs for the infected subgraph G+ti rather than the entire graph, highlighting the positional significance of sources. The symmetric normalized Laplacian matrix for G+ti is defined as:

where I denotes the identity matrix, H+ is the incidence matrix of the subgraph G+ti , DV + and DE+ represent the degree matrices of nodes and hyperedges, respectively. The Laplacian matrix Lsym + can further be decomposed as:

where Γ consists of eigenvectors and Λ is the diagonal matrix of eigenvalues. The eigenvectors associated with the smallest non-zero eigenvalues provide the positional encodings, which we adopt as the node-level positional feature X3i :

Finally, the initial feature of node vi is obtained by concatenating the individual components:

Sequential Feature Preprocessing. For the derived sequential hypergraph features {X(ti)}ti∈T . Unlike the feature aggregation process in pairwise graphs, hypergraphs require a unique approach due to the role of hyperedges as mediums for interactions among multiple nodes. To address this, we employ the Hypergraph Neural Network (HGNN) [Feng et al., 2019; Gao et al., 2022; Bai et al., 2021] that aggregates features in two stages: node-to-hyperedge and hyperedge-tonode. The process is formulated as:

where X(l) represents the node features at layer l, H is the incidence matrix, DV and DE are the diagonal degree matrices of nodes and hyperedges, respectively. Ω denotes the hyperedge weight matrix, and W(l) is the trainable parameters. The activation function σ(·) introduces non-linearity, enabling the model to capture the intricate high-order interactions effectively. Through Eq. (9), the initial feature sequence {X(ti)n×x }ti∈T is projected into {X′ (ti)n×x′ }ti∈T , serving as the foundation for downstream tasks.

4.2 Graph-aware State Space Model

State Space Model. By capturing sequential dynamics through explicitly maintaining a latent state that evolves over time, State Space Models (SSMs) map an input sequence xt ∈ R to a latent state representation ht ∈ RN , and subsequently derive a predicted output sequence yt ∈ R. While continuous SSMs provide a mathematically elegant framework, finding an analytical solution for the state representation ht remains a significant challenge. Moreover, the majority of practical sequences, such as textual data, are inherently discrete. Consequently, discrete SSMs are adopted with four parameters (∆, A, B, C), the sequence-to-sequence transformation can be expressed as:

where C and D represent projection parameters mapping the latent state and input to the output space. A and B are derived through the zero-order hold (ZOH) discretization method with a sampling step size ∆. Specifically:

This discretization strategy ensures both numerical stability and computational efficiency. However, the parameters A, B, C, ∆ are fixed across all time steps, adhering to the Linear Time Invariant (LTI) property, which restricts the model's ability to accommodate dynamic variations in input sequences. To address this limitation, Mamba introduces a content-aware reasoning framework by modeling B, C, ∆ as functions of the input. This transformation results in a selective SSM capable of adapting to input-dependent variations.

We feed the sequence of hypergraph features {X′ (ti)} into several Mamba blocks in reverse temporal order to capture the underlying propagation dynamics. Moreover, by utilizing convolution kernel K = (CB, CAB, ..., CAk B, ...), we achieve the sequence-to-sequence transformation through y = X′ ∗ K with linear time complexity.

Graph-aware State Update Mechanism. While Mamba enables input-dependent learning with linear time complexity, directly feeding hypergraph snapshots as individual sequence elements into the model risks losing essential topological information. To address this, we propose a graphaware state update mechanism allows for the update of node features by enabling node communication, where the state of each node is determined collaboratively by both the sequence input and the states of its neighbors, as expressed by:

Similar to the convolutional process on hypergraphs, the neighbor state hN is updated in two steps: node-to-hyperedge and hyperedge-to-node.

1. Node-to-Hyperedge Acting as mediators between nodes, hyperedges first collect the averaged state information from its connected nodes:

(2) Hyperedge-to-Node In this process, the state information is aggregated back to the nodes from the hyperedges:

Through aggregating the state information of neighboring nodes, the SSM acquires the capability to perceive the underlying graph structure. However, in the context of rumor propagation, distinct groups of nodes contribute differently to the spread of information. Therefore, hyperedges should be weighted based on their respective states. Given that attention mechanisms introduce additional computational complexity, we utilize a MLP block with an activation function and sigmoid to learn the weights of each hyperedge:

Consequently, the state update process is summarized as:

The proposed graph-aware state update mechanism ensures that the node feature updates are informed by both the sequential data and the structural context of the hypergraph. Moreover, the adoption of hyperedge weights enables the model to dynamically adjust the influence of different hyperedges based on the propagation dynamics, providing a more adaptive and context-sensitive approach to learning rumor propagation patterns.

4.3 Optimization and Training

For the output sequence y, we focus on the last element, i.e., y1, for source detection task. To alleviate the class imbalance resulting from the substantial disparity between the sample numbers of source and non-source nodes, we introduce a parameter ξ to mitigate the prediction bias:

where n denotes the number of nodes, and |s| represents the number of sources. This harmonic parameter equalizes the contribution of all samples. Consequently, the optimization objective is to minimize the discrepancy between the predicted set of sources and the actual sources, formalized as:

where L denotes the cross-entropy loss, and for a sample x with corresponding label z, L(x, z) = - log(x)×z. The final term represents the L2 regularization of the weight vector W, with λ controlling the regularization strength.

5 Experiments

5.1 Experimental Settings

Datasets. Eight datasets with varying scales and characteristics are used to evaluate the performance of our SourceDetMamba. Considered datasets includes Zoo [Asuncion et al., 2007], House [Chodrow et al., 2021], NTU2012 [Chen et al., 2003], Mushroom [Asuncion et al., 2007], ModelNet40 [Wu et al., 2015], 20News [Asuncion et al., 2007], PubMed [Yadati et al., 2019] and Walmart [Amburg et al., 2020].

Baselines. Different categories of methods are selected as baselines, including source centrality-based methods such as LPSI [Wang et al., 2017] and EPA [Ali et al., 2019], user state-based methods like GCNSI [Dong et al., 2019], SIGN [Li et al., 2021], GCSSI [Dong et al., 2022] and ResGCN [Shah et al., 2020], and propagation information-integrated methods such as IVGD [Wang et al., 2022], SL-VAE [Ling et al., 2022], and GIN-SD [Cheng et al., 2024b].

Implementation. Given the independence of users on social platforms and the short-term nature of rumor propagation, we simulate the rumor spread using a heterogeneous independent cascade model. The propagation process is triggered by randomly selecting 5% of the nodes as sources. For low-order interactions, the propagation rate pi of each node follows a uniform distribution U(0, 0.5). In the high-order interaction phase, the state transition probability p∆ for each node in a hyperedge is proportional to the number of informed nodes, formulated as p∆ = 0.3 · (|e ∩ v+|/|e|), v+ ∈ G+ti . The sequential snapshots are captured when 10%, 20%, and 30% of the nodes in the network are informed, with the resulting dataset is split into training and testing sets in an 8: 2 ratio. For the training process, the model's learning rate and weight decay are set to 10-3 and 10-5 , respectively. In the state space model, each input in the sequence undergoes a state update via a two-layer stack, with state size equals to 128. Hyperedge weights are calculated through two linear layers, each followed by an activation function, and the state is mapped to a single scalar value using a sigmoid function. The hypergraph snapshots are first subjected to clique expansion before being applied to the baseline methods. All experiments are conducted on a workstation equipped with four NVIDIA RTX 3090Ti GPUs.

Metrics. ACC (Accuracy), F-Score, and AUC (Area Under the Curve) are selected as evaluation metrics to assess the performance of different methods. ACC measures the proportion of correctly classified samples. F-Score comprises Precision and Recall, where Precision = |ˆ s ∩ s|/|ˆ s| represents the proportion of true sources in the detected source set, and Recall = |ˆ s∩s|/|s| indicates the proportion of true sources detected. The AUC evaluates the model's ability to differentiate between source and non-source nodes across varying thresholds. These metrics provide a comprehensive evaluation of the performance and robustness of source detection methods.

5.2 Performance Analysis

Comparison with State-of-the-art Methods. Table 1 presents the comparative results of our proposed SourceDetMamba against baseline methods, revealing several key insights. First, all methods achieve higher ACC than F-Score, primarily due to the imbalance between the large number of non-source nodes and the relatively small number of source nodes. As ACC measures the overall proportion of correctly classified samples, this disparity highlights the impact of class imbalance, particularly for methods such as LPSI and EPA based on source centrality, and machine learning approaches like GCNSI, SIGN, and GCSSI. Second, methods relying solely on source centrality demonstrate lower F-Score due to the inherent randomness of the propagation process, which limits the effectiveness of topology-only approaches. Machine learning-based methods that incorporate user features perform better, and methods that model the propagation process, such as IVGD and SL-VAE, or integrate propagation features directly, like GIN-SD, achieve even greater performance improvements. Notably, SourceDetMamba outperforms all baselines, delivering 10%-23% higher accuracy than propagation-aware methods, 25%-35% higher than user state-based methods, and even doubling the performance of source centrality-based approaches. These significant improvements stem from SourceDetMamba's ability to directly learn propagation dynamics through Mamba blocks and its graph-aware state update mechanism, which seamlessly incorporates hypergraph topology into the learning process.

Visualization. To provide an intuitive illustration of the source detection results, we visualize the outputs of SourceDetMamba alongside those of representative methods on the NTU2012 dataset [Chen et al., 2003] in Fig. 3. As compared to baselines, our approach demonstrates better performance in identifying the sources.

Computational Efficiency. To evaluate computational efficiency, we compare the runtime and accuracy of the proposed method against baseline approaches, as shown in Fig. 4. The results reveal that methods not considering propagation dynamics achieve faster runtime but suffer from lower F-scores, indicating limited accuracy. Conversely, methods incorporating propagation dynamics demonstrate improved accuracy at the expense of significantly higher computational complexity. In contrast, our proposed method achieves a better balance, excelling in both accuracy and runtime efficiency. These findings validate the effectiveness of SourceDetMamba in delivering SOTA performance with computational efficiency.

5.3 Ablation Study and Other Analyses

Effects of Sequential Snapshots and Positional Encoding. We first remove the sequential snapshots, retaining only the earliest one. The results in Table 2 show a noticeable performance decline compared to the complete model, highlighting the importance of utilizing multiple snapshots to capture propagation patterns. Next, we exclude the positional encodings in w/o PEs, the observed performance degradation highlights the critical role that PEs play in capturing the structural context and enhancing the model's robustness.

Effects of Exiting Sequential Models. We employ transformation and attention mechanisms to facilitate reverse learning of propagation patterns in w/ Attention, the results demonstrate a noticeable decline compared to SourceDetMamba. When sequential features are directly fed into an LSTM, the performance is similar to that of the attentionbased model. In the w/ Att & LSTM, we first apply attention fusion to the features and then input them into the LSTM. However, the results reveal a decrease in performance compared to using attention or LSTM individually. The performance is mainly attributed to the challenge of existing sequential models in effectively learning input dependencies.

Effects of the Graph-aware State Update Mechanism. By removing node communication from Mamba and relying solely on the temporal states of individual nodes for prediction, we observe a significant performance drop. This highlights the critical role of the graph-aware state update mechanism in sequential graph tasks. Additionally, when hyperedge weight computation is omitted, performance improves compared to the model without the graph-aware mechanism, yet it still falls short of SourceDetMamba. These results confirm the effectiveness and validity of integrating topological structure and differentiating hyperedges in our proposed model.

Impact of Information Diffusion Models. To address diverse scenarios, we employ various information diffusion models and summarize the performance of SourceDetMamba in Table 3. The results demonstrate that SourceDetMamba consistently performs well across all tested models. A slight decline is observed for the SIS and SIR models due to the possibility of sources recovery, which introduces ambiguity into the detection process. Nonetheless, the strong overall performance underscores the robustness and adaptability of SourceDetMamba, reinforcing its effectiveness across a range of information propagation dynamics.

Impact of Propagation Scale and Snapshot Intervals. We set the initial snapshot sizes to 10%, 20%, and 30%, and vary the interval between subsequent snapshots from 5% to 25% with an increment of 5%. The results of SourceDetMamba are shown in Fig. 5. Firstly, across all datasets, the F-Score decreases as the propagation scale increases. This is primarily due to the necessity of identifying a larger number of samples, which leads to increased errors. Secondly, varying the snapshot intervals highlights that overly close snapshots may fail to capture sufficient propagation dynamics, while excessively distant snapshots may over-represent the influence of non-source nodes. Therefore, an appropriate snapshot interval is beneficial for effective source detection.

6 Conclusion

This paper presents a new perspective on rumor source detection by focusing on effective learning in sequential hypergraphs. The key idea involves reverse-order input of hypergraph snapshots into the Mamba state space model to learn propagation patterns, followed by the proposal of a graphaware state update mechanism, which integrates topological information with temporal dependencies. Extensive experiments demonstrate that this approach significantly outperforms existing methods in sequential snapshot-based rumor source detection, providing a robust solution for sequential network learning. We hope that this work will inspire further research into topological-aware models in this field.

Acknowledgements

This work was supported in part by the National Natural Science Foundation of China (Grant Nos. U22B2036, 62025602, 62471403, 62073263, 62472117), the Fundamental Research Funds for the Central Universities (Grant Nos. G2024WD0151, D5000240309), the Technological InnovationTeam of Shaanxi Province (Grant No. 2025RS-CXTD009), the International Cooperation Project of Shaanxi Province (Grant No. 2025GH-YBXM-017), the Guangdong Basic and Applied Basic Research Foundation (Grant No. 2025A1515010157), the Science and Technology Projects in Guangzhou (Grant No. 2025A03J0137), the National Foreign Experts Program (Grant No. G2023183019), and the Tencent Foundation and XPLORER PRIZE.