DG-Mamba: Robust and Efficient Dynamic Graph Structure Learning with Selective State Space Models
Haonan Yuan, Qingyun Sun, Zhaonan Wang, Xingcheng Fu, Cheng Ji, Yongjian Wang, Bo Jin, Jianxin Li · 2024
Read DG-Mamba: Robust and Efficient Dynamic Graph Structure Learning with Selective State Space Models by Haonan Yuan, Qingyun Sun, Zhaonan Wang, Xingcheng Fu, Cheng Ji, Yongjian Wang, Bo Jin, Jianxin Li (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-08160.txt.
Introduction
Haonan Yuan and co-authors present DG-Mamba, a method for learning from graphs that change over time, in a 2024 paper. Real networks shift by the hour, and their records are gappy and noisy, which weakens graph neural networks. Cleaning the graph structure as it evolves can help, but older cleaning methods are slow and lean on hand set rules.
Their design cuts the cost from quadratic to linear with a kernel based message step. A state space model then treats the whole graph history as one system, scanning across snapshots to catch long range links. A self taught rule keeps the most useful, least repeated information. Tests beat rivals on strength and speed, even under attack.
Catalog record
| CREATOR | Haonan Yuan, Qingyun Sun, Zhaonan Wang, Xingcheng Fu, Cheng Ji, Yongjian Wang, Bo Jin, Jianxin Li |
|---|---|
| YEAR | 2024 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 106 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2412-08160
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
DG-Mamba: Robust and Efficient Dynamic Graph Structure Learning with Selective State Space Models Haonan Yuan, Qingyun Sun, Zhaonan Wang, Xingcheng Fu, Cheng Ji, Yongjian Wang, Bo Jin, Jianxin Li Abstract Dynamic graphs exhibit intertwined spatio-temporal evolutionary patterns, widely existing in the real world. Nevertheless, the structure incompleteness, noise, and redundancy result in poor robustness for Dynamic Graph Neural Networks (DGNNs). Dynamic Graph Structure Learning (DGSL) offers a promising way to optimize graph structures. However, aside from encountering unacceptable quadratic complexity, it overly relies on heuristic priors, making it hard to discover underlying predictive patterns. How to efficiently refine the dynamic structures, capture intrinsic dependencies, and learn robust representations, remains under-explored. In this work, we propose the novel DG-Mamba , a robust and efficient D ynamic G raph structure learning framework with the Selective State Space Models ( Mamba ). To accelerate the spatio-temporal structure learning, we propose a kernelized dynamic message-passing operator that reduces the quadratic time complexity to linear. To capture global intrinsic dynamics, we establish the dynamic graph as a self-contained system with State Space Model. By discretizing the system states with the cross-snapshot graph adjacency, we enable the long-distance dependencies capturing with the selective snapshot scan. To endow learned dynamic structures more expressive with informativeness, we propose the self-supervised Principle of Relevant Information for DGSL to regularize the most relevant yet least redundant information, enhancing global robustness. Extensive experiments demonstrate the superiority of the robustness and efficiency of our DG-Mamba compared with the state-of-the-art baselines against adversarial attacks. 1 SKLCCSE, School of Computer Science and Engineering, Beihang University, China 2 National Superior College for Engineers, Beihang University, China 3 Key Lab of Education Blockchain and Intelligent Technology, Ministry of Education, Guangxi Normal University, China 4 The Third Research Institute of Ministry of Public Security, China {yuanhn, sunqy, wangzn, jicheng, lijx}@buaa.edu.cn, [email protected], [email protected], [email protected] 1 Introduction Dynamic graphs are ubiquitous in real world, spanning domains such as social media ( Sun et al. 2022a ) , traffic networks ( Guo et al. 2021 ) , financial transactions ( Pareja et al. 2020 ) , and human mobility ( Zhou et al. 2023 ) , etc. Their complex spatial and temporal correlation patterns present significant challenges across various downstream deployments. Leveraging exceptional expressive capabilities, Dynamic Graph Neural Networks (DGNNs) intrinsically excel at dynamic graph representation learning by modeling both spatial and temporal predictive patterns, which enjoy the combined merits of both GNNs and sequential models. \hat{\mathcal{G}}^{1:T} \mathcal{G}^{1:T} \mathcal{L}_{\text{task}} \mathcal{L}_{\text{reg}} \mathcal{G}^{T+1} Figure 1: A general paradigm of DGSL. Recently, there has been a growing research trend on enhancing the efficacy of DGNNs ( Zhang et al. 2022 ; Zhu et al. 2023 ; Yuan et al. 2024 ) . This includes a specific focus on improving their ability to capture the intricate spatio-temporal correlations that surpass the first-order Weisfeiler-Leman (1-WL) graph isomorphism test ( Xu et al. 2019b ) . Most of the DGNNs perform spatio-temporal message-passing over potentially flawed graph structures, assuming the observed graph structures can reflect the ground-truth relationships between nodes. However, this fundamental assumption often leads to suboptimal robustness and generalization performance due to the inherent incompleteness, noise, and redundancy in graph structures, which also make the learned representations susceptible to noise and intended adversarial attacks ( Zügner, Akbarnejad, and Günnemann 2018 ) . Graph Structure Learning (GSL) has emerged as a crucial graph learning paradigm for iteratively optimizing structures and representations ( Sun et al. 2022b ; Sun et al. 2022c ; Wei et al. 2024 ; Fu et al. 2023 ) . Similarly, the GSL for dynamic graphs (DGSL) aims to refine spatial- and temporal-wise structures (Figure 1 ). Despite its potential, DGSL faces several challenges. On one hand, the intricate coupling of spatial and temporal dimensions makes it particularly vulnerable to noise and adversarial attacks in open data environments, which significantly hampers its performance and robustness. Moreover, the predictive patterns indicate the causal behind real-world decision-making. However, current approaches often emphasize the optimization of local structures, overlooking latent long-range dependencies. This oversight results in a notable decline in performance on long-sequence dynamic graph prediction tasks as the sequence length increases. On the other hand, DGSL demonstrates vast complexity challenges. In addition to the overwhelming quadratic complexity within individual graphs caused by node-pair probabilistic measuring ( Wu et al. 2022 ) , attention-based sequential models ( e.g. , Transformer ( Vaswani et al. 2017 ) ) also encounter quadratic complexity when computing step-pair attentions ( Shen et al. 2021 ) . As the scale of nodes and sequence length grow explosively, this complexity bottleneck severely hinders the advancement of existing DGSL frameworks. Several works have attempted to address the complexity problems from spatial and temporal perspectives ( Wu et al. 2022 ; Gu and Dao 2023 ) . However, dynamic graphs function as a system with intricate spatio-temporal couplings, necessitating a holistic framework for complexity reduction across both dimensions. Notably, the complexities of both dimensions are not orthogonal but interdependent. Attempting to isolate and reduce spatial complexity without considering temporal complexity, or vice versa, is insufficient. Their interdependence significantly amplifies the overall computational burden. This multifaceted framework is essential for achieving efficient and robust dynamic graph learning, ensuring it can not only handle quadratic complexity but also capture insightful correlations. Research Question: How to capture long-range intrinsic dependency of underlying predictive patterns to derive robust representations against adversarial attacks over the denoised structures while simultaneously reduce both spatial and temporal time complexity from quadratic to linear? Present Work. In this work, we introduce DG-Mamba , a robust and efficient D ynamic G raph structure learning framework with the selective state space models ( Mamba ). We propose a kernelized dynamic message-passing operator that reduces the quadratic time complexity to linear to accelerate the spatio-temporal structure learning. To break the local Markovian dependence assumption limitations and capture global intrinsic dynamics, we model the dynamic graph with the State Space Model as a system, and discretize the system states with the cross-snapshot graph adjacency. To endow the learned dynamic structures with informative expressiveness, we propose the self-supervised Principle of Relevant Information for DGSL to regularize the most relevant yet least redundant information, enhancing global robustness for downstream tasks. Our contributions are: • We propose a robust and efficient dynamic graph structure learning framework DG-Mamba with linear time invariance property for robust representations against adversarial attacks. To the best of our knowledge, this is the first trial in which the spatio-temporal computational complexity of DGSL has been simultaneously reduced to linear. • The kernelized dynamic graph message-passing operator behaves efficient DGSL with the help of state-discretized SSM. The structural information between the original and the learned is regularized with the proposed PRI for DGSL to enhance the robustness of the global representation. • Experiments on real-world and synthetic dynamic graphs validate the effectiveness, robustness, and efficiency of the proposed DG-Mamba, demonstrating its superiority over 12 state-of-the-art baselines against adversarial attacks. 2 Related Work 2.1 Robust Dynamic Graph Learning Dynamic Graph Neural Networks (DGNNs) are prevalent in learning representations by inherently modeling both spatial and temporal features ( Han et al. 2021 ) . However, dynamic graphs naturally contain noise and redundant features irrelevant to the target, which