Proceedings

Mamba-Based Graph Convolutional Networks: Tackling Over-smoothing with Selective State Space

Download BibTeX Cite

Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence. Main Track. Pages 5345-5353.

https://doi.org/10.24963/ijcai.2025/595

Abstract

Graph Neural Networks (GNNs) have shown great success in various graph-based learning tasks. However, it often faces the issue of over-smoothing as the model depth increases, which causes all node representations to converge to a single value and become indistinguishable. This issue stems from the inherent limitations of GNNs, which struggle to distinguish the importance of information from different neighborhoods. In this paper, we introduce MbaGCN, a novel graph convolutional architecture that draws inspiration from the Mamba paradigm—originally designed for sequence modeling. MbaGCN presents a new backbone for GNNs, consisting of three key components: the Message Aggregation Layer, the Selective State Space Transition Layer, and the Node State Prediction Layer. These components work in tandem to adaptively aggregate neighborhood information, providing greater flexibility and scalability for deep GNN models. While MbaGCN may not consistently outperform all existing methods on each dataset, it provides a foundational framework that demonstrates the effective integration of the Mamba paradigm into graph representation learning. Through extensive experiments on benchmark datasets, we demonstrate that MbaGCN paves the way for future advancements in graph neural network research. Our code is in https://github.com/hexin5515/MbaGCN.

  1. [Behrouz and Hashemi, 2024] Ali Behrouz and Farnoosh Hashemi. Graph mamba: Towards learning on graphs with state space models. In Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 119-130, 2024.
  2. [Chen et al., 2020] Ming Chen, Zhewei Wei, Zengfeng Huang, Bolin Ding, and Yaliang Li. Simple and deep graph convolutional networks. In International conference on machine learning, pages 1725-1735. PMLR, 2020.
  3. [Chien et al., 2020] Eli Chien, Jianhao Peng, Pan Li, and Ol- gica Milenkovic. Adaptive universal generalized pagerank graph neural network. arXiv preprint arXiv:2006.07988, 2020.
  4. [Dao and Gu, 2024] Tri Dao and Albert Gu. Transformers are ssms: Generalized models and efficient algorithms through structured state space duality. arXiv preprint arXiv:2405.21060, 2024.
  5. [Ding et al., 2024] Yuhui Ding, Antonio Orvieto, Bobby He, and Thomas Hofmann. Recurrent distance filtering for graph representation learning. In Forty-first International Conference on Machine Learning, 2024.
  6. [Gasteiger et al., 2018] Johannes Gasteiger, Aleksandar Bo- jchevski, and Stephan Günnemann. Predict then propa- gate: Graph neural networks meet personalized pagerank. arXiv preprint arXiv:1810.05997, 2018.
  7. [Grazzi et al., 2024] Riccardo Grazzi, Julien Siems, Si- mon Schrodi, Thomas Brox, and Frank Hutter. Is mamba capable of in-context learning? arXiv preprint arXiv:2402.03170, 2024.
  8. [Gu and Dao, 2023] Albert Gu and Tri Dao. Mamba: Linear- time sequence modeling with selective state spaces. arXiv preprint arXiv:2312.00752, 2023.
  9. [Gu et al., 2020] Albert Gu, Tri Dao, Stefano Ermon, Atri Rudra, and Christopher Ré. Hippo: Recurrent memory with optimal polynomial projections. Advances in neural information processing systems, 33:1474-1487, 2020.
  10. [Gu et al., 2021] Albert Gu, Karan Goel, and Christopher Ré. Efficiently modeling long sequences with structured state spaces. arXiv preprint arXiv:2111.00396, 2021.
  11. [He et al., 2021] Mingguo He, Zhewei Wei, Hongteng Xu, et al. Bernnet: Learning arbitrary graph spectral filters via bernstein approximation. Advances in Neural Information Processing Systems, 34:14239-14251, 2021.
  12. [Hu et al., 2025] Vincent Tao Hu, Stefan Andreas Baumann, Ming Gui, Olga Grebenkova, Pingchuan Ma, Johannes Fischer, and Björn Ommer. Zigma: A dit-style zigzag mamba diffusion model. In European Conference on Com- puter Vision, pages 148-166. Springer, 2025.
  13. [Jin et al., 2021] Wei Jin, Tyler Derr, Yiqi Wang, Yao Ma, Zitao Liu, and Jiliang Tang. Node similarity preserving graph convolutional networks. In Proceedings of the 14th ACM international conference on web search and data mining, pages 148-156, 2021.
  14. [Kipf and Welling, 2016] Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. arXiv preprint arXiv:1609.02907, 2016.
  15. [Li et al., 2018] Qimai Li, Zhichao Han, and Xiao-Ming Wu. Deeper insights into graph convolutional networks for semi-supervised learning. In Proceedings of the AAAI con- ference on artificial intelligence, volume 32, 2018.
  16. [Li et al., 2021] Ruifan Li, Hao Chen, Fangxiang Feng, Zhanyu Ma, Xiaojie Wang, and Eduard Hovy. Dual graph convolutional networks for aspect-based sentiment analy- sis. In Proceedings of the 59th Annual Meeting of the Asso- ciation for Computational Linguistics and the 11th Inter- national Joint Conference on Natural Language Process- ing (Volume 1: Long Papers), pages 6319-6329, 2021.
  17. [Lieber et al., 2024] Opher Lieber, Barak Lenz, Hofit Bata, Gal Cohen, Jhonathan Osin, Itay Dalmedigos, Erez Safahi, Shaked Meirom, Yonatan Belinkov, Shai Shalev-Shwartz, et al. Jamba: A hybrid transformer-mamba language model. arXiv preprint arXiv:2403.19887, 2024.
  18. [Miao et al., 2024] Rui Miao, Kaixiong Zhou, Yili Wang, Ninghao Liu, Ying Wang, and Xin Wang. Rethinking in- dependent cross-entropy loss for graph-structured data. In Proceedings of the 41st International Conference on Ma- chine Learning, pages 35570-35589, 2024.
  19. [Qin et al., 2024] Yifang Qin, Wei Ju, Hongjun Wu, Xiao Luo, and Ming Zhang. Learning graph ode for continuous- time sequential recommendation. IEEE Transactions on Knowledge and Data Engineering, 2024.
  20. [Rusch et al., 2023] T Konstantin Rusch, Michael M Bron- stein, and Siddhartha Mishra. A survey on over- smoothing in graph neural networks. arXiv preprint arXiv:2303.10993, 2023.
  21. [Shen et al., 2024a] Xu Shen, Pietro Lio, Lintao Yang, Ru Yuan, Yuyang Zhang, and Chengbin Peng. Graph rewiring and preprocessing for graph neural networks based on effective resistance. IEEE Transactions on Knowledge and Data Engineering, 2024.
  22. [Shen et al., 2024b] Xu Shen, Yili Wang, Kaixiong Zhou, Shirui Pan, and Xin Wang. Optimizing ood detection in molecular graphs: A novel approach with diffusion mod- els. In Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 2640- 2650, 2024.
  23. [Shen et al., 2025] Xu Shen, Yixin Liu, Yili Wang, Rui Miao, Yiwei Dai, Shirui Pan, and Xin Wang. Raising the bar in graph ood generalization: Invariant learning beyond explicit environment modeling. arXiv preprint arXiv:2502.10706, 2025.
  24. [Tang et al., 2023] Siyi Tang, Jared A Dunnmon, Qu Liangqiong, Khaled K Saab, Tina Baykaner, Christopher Lee-Messer, and Daniel L Rubin. Mod- eling multivariate biosignals with graph neural networks and structured state space models. In Conference on Health, Inference, and Learning, pages 50-71. PMLR, 2023.
  25. [Veličković et al., 2017] Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. arXiv preprint arXiv:1710.10903, 2017.
  26. [Wan et al., 2021] Sheng Wan, Shirui Pan, Jian Yang, and Chen Gong. Contrastive and generative graph convolu- tional networks for graph-based semi-supervised learning. In Proceedings of the AAAI conference on artificial intel- ligence, volume 35, pages 10049-10057, 2021.
  27. [Wang et al., 2021] Bo Wang, Tao Shen, Guodong Long, Tianyi Zhou, Ying Wang, and Yi Chang. Structure- augmented text representation learning for efficient knowl- edge graph completion. In Proceedings of the Web Con- ference 2021, pages 1737-1748, 2021.
  28. [Wang et al., 2022] Yili Wang, Kaixiong Zhou, Rui Miao, Ninghao Liu, and Xin Wang. Adagcl: Adaptive subgraph contrastive learning to generalize large-scale graph train- ing. In Proceedings of the 31st ACM international con- ference on information & knowledge management, pages 2046-2055, 2022.
  29. [Wang et al., 2024a] Chloe Wang, Oleksii Tsepa, Jun Ma, and Bo Wang. Graph-mamba: Towards long-range graph sequence modeling with selective state spaces. arXiv preprint arXiv:2402.00789, 2024.
  30. [Wang et al., 2024b] Yili Wang, Yixin Liu, Xu Shen, Chenyu Li, Kaize Ding, Rui Miao, Ying Wang, Shirui Pan, and Xin Wang. Unifying unsupervised graph-level anomaly detection and out-of-distribution detection: A benchmark. arXiv preprint arXiv:2406.15523, 2024.
  31. [Wang et al., 2024c] Yili Wang, Kaixiong Zhou, Ninghao Liu, Ying Wang, and Xin Wang. Efficient sharpness-aware minimization for molecular graph transformer models. In The Twelfth International Conference on Learning Repre- sentations, ICLR 2024, Vienna, Austria, May 7-11, 2024. OpenReview.net, 2024.
  32. [Wang et al., 2025] Zihan Wang, Fanheng Kong, Shi Feng, Ming Wang, Xiaocui Yang, Han Zhao, Daling Wang, and Yifei Zhang. Is mamba effective for time series forecast- ing? Neurocomputing, 619:129178, 2025.
  33. [Wu et al., 2019] Felix Wu, Amauri Souza, Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Weinberger. Simpli- fying graph convolutional networks. In International con- ference on machine learning, pages 6861-6871. PMLR, 2019.
  34. [Wu et al., 2024] Xinyi Wu, Amir Ajorlou, Zihui Wu, and Ali Jadbabaie. Demystifying oversmoothing in attention- based graph neural networks. Advances in Neural Infor- mation Processing Systems, 36, 2024.
  35. [Xu et al., 2021] Minghao Xu, Hang Wang, Bingbing Ni, Hongyu Guo, and Jian Tang. Self-supervised graph-level representation learning with local and global structure. In International Conference on Machine Learning, pages 11548-11558. PMLR, 2021.
  36. [Yan et al., 2022] Yujun Yan, Milad Hashemi, Kevin Swer- sky, Yaoqing Yang, and Danai Koutra. Two sides of the same coin: Heterophily and oversmoothing in graph con- volutional neural networks. In 2022 IEEE International Conference on Data Mining (ICDM), pages 1287-1292. IEEE, 2022.
  37. [Yang et al., 2024] Chenhongyi Yang, Zehui Chen, Miguel Espinosa, Linus Ericsson, Zhenyu Wang, Jiaming Liu, and Elliot J Crowley. Plainmamba: Improving non- hierarchical mamba in visual recognition. arXiv preprint arXiv:2403.17695, 2024.
  38. [Yu et al., 2022] Pengyang Yu, Chaofan Fu, Yanwei Yu, Chao Huang, Zhongying Zhao, and Junyu Dong. Multi- plex heterogeneous graph convolutional network. In Pro- ceedings of the 28th ACM SIGKDD Conference on Knowl- edge Discovery and Data Mining, pages 2377-2387, 2022.
  39. [Yuan et al., 2024] Xiaosong Yuan, Chen Shen, Shaotian Yan, Xiaofeng Zhang, Liang Xie, Wenxiao Wang, Renchu Guan, Ying Wang, and Jieping Ye. Instance-adaptive zero-shot chain-of-thought prompting. arXiv preprint arXiv:2409.20441, 2024.
  40. [Zhai et al., 2024] Jiayu Zhai, Lequan Lin, Dai Shi, and Jun- bin Gao. Bregman graph neural network. In ICASSP 2024- 2024 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 6250-6254. IEEE, 2024.
  41. [Zhang and Li, 2021] Muhan Zhang and Pan Li. Nested graph neural networks. Advances in Neural Information Processing Systems, 34:15734-15747, 2021.
  42. [Zhang et al., 2021] Wentao Zhang, Mingyu Yang, Zeang Sheng, Yang Li, Wen Ouyang, Yangyu Tao, Zhi Yang, and Bin Cui. Node dependent local smoothing for scalable graph learning. Advances in Neural Information Process- ing Systems, 34:20321-20332, 2021.
  43. [Zhu and Koniusz, 2021] Hao Zhu and Piotr Koniusz. Sim- ple spectral graph convolution. In International conference on learning representations, 2021.
  44. [Zhu et al., 2024] Lianghui Zhu, Bencheng Liao, Qian Zhang, Xinlong Wang, Wenyu Liu, and Xinggang Wang. Vision mamba: Efficient visual representation learning with bidirectional state space model. arXiv preprint arXiv:2401.09417, 2024.

References were extracted automatically from the PDF and may contain errors.

Welcome Future Conferences AI Journal Division IJCAI Proceedings About IJCAI IJCAI Awards