{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T02:01:41Z","timestamp":1740103301166,"version":"3.37.3"},"publisher-location":"New York, NY, USA","reference-count":51,"publisher":"ACM","funder":[{"name":"National Key Research and Development Program of China","award":["2022YFB3904201"]},{"name":"National Natural Science Foundation of China","award":["No.62106143"]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2024,10,21]]},"DOI":"10.1145\/3627673.3679866","type":"proceedings-article","created":{"date-parts":[[2024,10,20]],"date-time":"2024-10-20T19:34:21Z","timestamp":1729452861000},"page":"2138-2147","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Breaking the Bottleneck on Graphs with Structured State Spaces"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0009-0008-5856-8949","authenticated-orcid":false,"given":"Yunchong","family":"Song","sequence":"first","affiliation":[{"name":"Shanghai Jiao Tong University, Shanghai, China"}]},{"ORCID":"https:\/\/orcid.org\/0009-0005-7963-6590","authenticated-orcid":false,"given":"Siyuan","family":"Huang","sequence":"additional","affiliation":[{"name":"Shanghai Jiao Tong University, Shanghai, China"}]},{"ORCID":"https:\/\/orcid.org\/0009-0004-1304-5651","authenticated-orcid":false,"given":"Jiacheng","family":"Cai","sequence":"additional","affiliation":[{"name":"Shanghai Jiao Tong University, Shanghai, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0357-8356","authenticated-orcid":false,"given":"Xinbing","family":"Wang","sequence":"additional","affiliation":[{"name":"Shanghai Jiao Tong University, Shanghai, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3331-2302","authenticated-orcid":false,"given":"Chenghu","family":"Zhou","sequence":"additional","affiliation":[{"name":"Chinese Academy of Sciences, Shanghai, China"}]},{"ORCID":"https:\/\/orcid.org\/0009-0009-7204-0689","authenticated-orcid":false,"given":"Zhouhan","family":"Lin","sequence":"additional","affiliation":[{"name":"Shanghai Jiao Tong University, Shanghai, China"}]}],"member":"320","published-online":{"date-parts":[[2024,10,21]]},"reference":[{"key":"e_1_3_2_1_1_1","volume-title":"Shortest Path Networks for Graph Property Prediction. Learning on Graphs Conference","author":"Abboud Ralph","year":"2022","unstructured":"Ralph Abboud, Radoslav Dimitrov, and. Ismail. Ilkan Ceylan. 2022. Shortest Path Networks for Graph Property Prediction. Learning on Graphs Conference (2022)."},{"key":"e_1_3_2_1_2_1","volume-title":"international conference on machine learning. PMLR, 21--29","author":"Abu-El-Haija Sami","year":"2019","unstructured":"Sami Abu-El-Haija, Bryan Perozzi, Amol Kapoor, Nazanin Alipourfard, Kristina Lerman, Hrayr Harutyunyan, Greg Ver Steeg, and Aram Galstyan. 2019. Mixhop: Higher-order graph convolutional architectures via sparsified neighborhood mixing. In international conference on machine learning. PMLR, 21--29."},{"key":"e_1_3_2_1_3_1","volume-title":"International Conference on Learning Representations.","author":"Alon Uri","year":"2021","unstructured":"Uri Alon and Eran Yahav. 2021. On the Bottleneck of Graph Neural Networks and its Practical Implications. In International Conference on Learning Representations."},{"key":"e_1_3_2_1_4_1","volume-title":"Learning on Graphs Conference","author":"Arnaiz-Rodr\u00edguez Adri\u00e1n","year":"2022","unstructured":"Adri\u00e1n Arnaiz-Rodr\u00edguez, Ahmed Begga, Francisco Escolano, and Nuria Oliver. 2022. DiffWire: Inductive Graph Rewiring via the Lov\u00e1sz Bound. Learning on Graphs Conference (2022)."},{"key":"e_1_3_2_1_5_1","volume-title":"Residual gated graph ConvNets. arXiv preprint arXiv:1711.07553","author":"Bresson Xavier","year":"2017","unstructured":"Xavier Bresson and Thomas Laurent. 2017. Residual gated graph ConvNets. arXiv preprint arXiv:1711.07553 (2017)."},{"key":"e_1_3_2_1_6_1","volume-title":"Spectral networks and locally connected networks on graphs. arXiv preprint arXiv:1312.6203","author":"Bruna Joan","year":"2013","unstructured":"Joan Bruna, Wojciech Zaremba, Arthur Szlam, and Yann LeCun. 2013. Spectral networks and locally connected networks on graphs. arXiv preprint arXiv:1312.6203 (2013)."},{"key":"e_1_3_2_1_7_1","volume-title":"NAGphormer: A Tokenized Graph Transformer for Node Classification in Large Graphs. In The Eleventh International Conference on Learning Representations.","author":"Chen Jinsong","year":"2023","unstructured":"Jinsong Chen, Kaiyuan Gao, Gaichao Li, and Kun He. 2023. NAGphormer: A Tokenized Graph Transformer for Node Classification in Large Graphs. In The Eleventh International Conference on Learning Representations."},{"key":"e_1_3_2_1_8_1","volume-title":"Simple and Deep Graph Convolutional Networks. In International Conference on Machine Learning.","author":"Chen Ming","year":"2020","unstructured":"Ming Chen, Zhewei Wei, Zengfeng Huang, Bolin Ding, and Yaliang Li. 2020. Simple and Deep Graph Convolutional Networks. In International Conference on Machine Learning."},{"key":"e_1_3_2_1_9_1","volume-title":"Hungry Hungry Hippos: Towards Language Modeling with State Space Models. In International Conference on Learning Representations.","author":"Dao Tri","year":"2022","unstructured":"Tri Dao, Daniel Y. Fu, Khaled Kamal Saab, A. Thomas, A. Rudra, and Christopher R\u00e9. 2022. Hungry Hungry Hippos: Towards Language Modeling with State Space Models. In International Conference on Learning Representations."},{"key":"e_1_3_2_1_10_1","volume-title":"Convolutional neural networks on graphs with fast localized spectral filtering. Advances in neural information processing systems","author":"Defferrard Micha\u00ebl","year":"2016","unstructured":"Micha\u00ebl Defferrard, Xavier Bresson, and Pierre Vandergheynst. 2016. Convolutional neural networks on graphs with fast localized spectral filtering. Advances in neural information processing systems, Vol. 29 (2016)."},{"key":"e_1_3_2_1_11_1","volume-title":"International Conference on Machine Learning. PMLR, 7865--7885","author":"Giovanni Francesco Di","year":"2023","unstructured":"Francesco Di Giovanni, Lorenzo Giusti, Federico Barbero, Giulia Luise, Pietro Lio, and Michael M Bronstein. 2023. On over-squashing in message passing neural networks: The impact of width, depth, and topology. In International Conference on Machine Learning. PMLR, 7865--7885."},{"key":"e_1_3_2_1_12_1","volume-title":"A generalization of transformer networks to graphs. arXiv:2012.09699","author":"Dwivedi Vijay Prakash","year":"2020","unstructured":"Vijay Prakash Dwivedi and Xavier Bresson. 2020. A generalization of transformer networks to graphs. arXiv:2012.09699 (2020)."},{"key":"e_1_3_2_1_13_1","volume-title":"Benchmarking graph neural networks. arXiv:2003.00982","author":"Dwivedi Vijay Prakash","year":"2020","unstructured":"Vijay Prakash Dwivedi, Chaitanya K Joshi, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. 2020. Benchmarking graph neural networks. arXiv:2003.00982 (2020)."},{"key":"e_1_3_2_1_14_1","volume-title":"Graph Neural Networks with Learnable Structural and Positional Representations. In International Conference on Learning Representations.","author":"Dwivedi Vijay Prakash","year":"2022","unstructured":"Vijay Prakash Dwivedi, Anh Tuan Luu, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. 2022. Graph Neural Networks with Learnable Structural and Positional Representations. In International Conference on Learning Representations."},{"key":"e_1_3_2_1_15_1","first-page":"22326","article-title":"Long range graph benchmark","volume":"35","author":"Dwivedi Vijay Prakash","year":"2022","unstructured":"Vijay Prakash Dwivedi, Ladislav Ramp\u00e1vsek, Michael Galkin, Ali Parviz, Guy Wolf, Anh Tuan Luu, and Dominique Beaini. 2022. Long range graph benchmark. Advances in Neural Information Processing Systems, Vol. 35 (2022), 22326--22340.","journal-title":"Advances in Neural Information Processing Systems"},{"key":"e_1_3_2_1_16_1","unstructured":"Jiarui Feng Yixin Chen Fuhai Li Anindya Sarkar and Muhan Zhang. 2022. How Powerful are K-hop Message Passing Graph Neural Networks. In Advances in Neural Information Processing Systems."},{"key":"e_1_3_2_1_17_1","volume-title":"International conference on machine learning. PMLR, 1263--1272","author":"Gilmer Justin","year":"2017","unstructured":"Justin Gilmer, Samuel S Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl. 2017. Neural message passing for quantum chemistry. In International conference on machine learning. PMLR, 1263--1272."},{"key":"e_1_3_2_1_18_1","unstructured":"Francesco Di Giovanni T. Konstantin Rusch Michael M. Bronstein Andreea Deac M. Lackenby Siddhartha Mishra and Petar Velivckovi'c. 2023. How does over-squashing affect the power of GNNs?. In arXiv.org."},{"key":"e_1_3_2_1_19_1","volume-title":"International Conference on Machine Learning.","author":"Goel Karan","year":"2022","unstructured":"Karan Goel, Albert Gu, Chris Donahue, and Christopher R'e. 2022. It's Raw! Audio Generation with State-Space Models. In International Conference on Machine Learning."},{"key":"e_1_3_2_1_20_1","volume-title":"Mamba: Linear-Time Sequence Modeling with Selective State Spaces. In arXiv.","author":"Gu Albert","year":"2023","unstructured":"Albert Gu and Tri Dao. 2023. Mamba: Linear-Time Sequence Modeling with Selective State Spaces. In arXiv."},{"key":"e_1_3_2_1_21_1","volume-title":"Hippo: Recurrent memory with optimal polynomial projections. Advances in neural information processing systems","author":"Gu Albert","year":"2020","unstructured":"Albert Gu, Tri Dao, Stefano Ermon, Atri Rudra, and Christopher R\u00e9. 2020. Hippo: Recurrent memory with optimal polynomial projections. Advances in neural information processing systems, Vol. 33 (2020), 1474--1487."},{"key":"e_1_3_2_1_22_1","volume-title":"Efficiently Modeling Long Sequences with Structured State Spaces. In International Conference on Learning Representations.","author":"Gu Albert","year":"2022","unstructured":"Albert Gu, Karan Goel, and Christopher Re. 2022. Efficiently Modeling Long Sequences with Structured State Spaces. In International Conference on Learning Representations."},{"key":"e_1_3_2_1_23_1","unstructured":"Albert Gu Isys Johnson Karan Goel Khaled Saab Tri Dao Atri Rudra and Christopher R\u00e9. 2021. Combining recurrent convolutional and continuous-time models with the structured learnable linear state space layer. In Advances in Neural Information Processing Systems."},{"key":"e_1_3_2_1_24_1","volume-title":"DRew: Dynamically Rewired Message Passing with Delay. In International Conference on Machine Learning. PMLR, 12252--12267","author":"Gutteridge Benjamin","year":"2023","unstructured":"Benjamin Gutteridge, Xiaowen Dong, Michael M Bronstein, and Francesco Di Giovanni. 2023. DRew: Dynamically Rewired Message Passing with Delay. In International Conference on Machine Learning. PMLR, 12252--12267."},{"key":"e_1_3_2_1_25_1","volume-title":"Inductive representation learning on large graphs. Advances in neural information processing systems","author":"Hamilton Will","year":"2017","unstructured":"Will Hamilton, Zhitao Ying, and Jure Leskovec. 2017. Inductive representation learning on large graphs. Advances in neural information processing systems, Vol. 30 (2017)."},{"key":"e_1_3_2_1_26_1","volume-title":"A New Approach to Linear Filtering and Prediction Problems. Journal of Basic Engineering","author":"Kalman R. E.","year":"1960","unstructured":"R. E. Kalman. 1960. A New Approach to Linear Filtering and Prediction Problems. Journal of Basic Engineering (1960)."},{"key":"e_1_3_2_1_27_1","volume-title":"International Conference on Learning Representations.","author":"Karhadkar Kedar","year":"2023","unstructured":"Kedar Karhadkar, P. Banerjee, and Guido Mont\u00fafar. 2023. FoSR: First-order spectral rewiring for addressing oversquashing in GNNs. In International Conference on Learning Representations."},{"volume-title":"The Lipschitz Constant of Self-Attention. In International Conference on Machine Learning.","author":"Kim Hyunjik","key":"e_1_3_2_1_28_1","unstructured":"Hyunjik Kim, G. Papamakarios, and A. Mnih. 2021. The Lipschitz Constant of Self-Attention. In International Conference on Machine Learning."},{"key":"e_1_3_2_1_29_1","volume-title":"International Conference on Learning Representations","author":"Kipf Thomas N","year":"2017","unstructured":"Thomas N Kipf and Max Welling. 2017. Semi-supervised classification with graph convolutional networks. International Conference on Learning Representations (2017)."},{"key":"e_1_3_2_1_30_1","unstructured":"Johannes Klicpera Stefan Weissenberger and Stephan G\u00fcnnemann. 2019. Diffusion Improves Graph Learning. In Advances in Neural Information Processing Systems. Article 1197 13 pages."},{"key":"e_1_3_2_1_31_1","unstructured":"Devin Kreuzer Dominique Beaini William L. Hamilton Vincent L\u00e9tourneau and Prudencio Tossou. 2021. Rethinking Graph Transformers with Spectral Attention. In Advances in Neural Information Processing Systems."},{"key":"e_1_3_2_1_32_1","first-page":"4465","article-title":"Distance encoding: Design provably more powerful neural networks for graph representation learning","volume":"33","author":"Li Pan","year":"2020","unstructured":"Pan Li, Yanbang Wang, Hongwei Wang, and Jure Leskovec. 2020. Distance encoding: Design provably more powerful neural networks for graph representation learning. Advances in Neural Information Processing Systems, Vol. 33 (2020), 4465--4478.","journal-title":"Advances in Neural Information Processing Systems"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v32i1.11604"},{"key":"e_1_3_2_1_34_1","volume-title":"Gated graph sequence neural networks. arXiv preprint arXiv:1511.05493","author":"Li Yujia","year":"2015","unstructured":"Yujia Li, Daniel Tarlow, Marc Brockschmidt, and Richard Zemel. 2015. Gated graph sequence neural networks. arXiv preprint arXiv:1511.05493 (2015)."},{"key":"e_1_3_2_1_35_1","volume-title":"Towards Deeper Graph Neural Networks. In ACM SIGKDD Conference on Knowledge Discovery and Data Mining.","author":"Liu Meng","year":"2020","unstructured":"Meng Liu, Hongyang Gao, and Shuiwang Ji. 2020. Towards Deeper Graph Neural Networks. In ACM SIGKDD Conference on Knowledge Discovery and Data Mining."},{"key":"e_1_3_2_1_36_1","volume-title":"Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networks. In AAAI Conference on Artificial Intelligence.","author":"Morris Christopher","year":"2019","unstructured":"Christopher Morris, Martin Ritzert, Matthias Fey, William L. Hamilton, J. E. Lenssen, Gaurav Rattan, and Martin Grohe. 2019. Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networks. In AAAI Conference on Artificial Intelligence."},{"key":"e_1_3_2_1_37_1","unstructured":"Eric Nguyen Karan Goel Albert Gu G. Downs Preey Shah Tri Dao S. Baccus and C. R\u00e9. 2022. S4ND: Modeling Images and Videos as Multidimensional Signals with State Spaces. In Advances in Neural Information Processing Systems."},{"key":"e_1_3_2_1_38_1","volume-title":"Graph Neural Networks Exponentially Lose Expressive Power for Node Classification. In International Conference on Learning Representations.","author":"Oono Kenta","year":"2020","unstructured":"Kenta Oono and Taiji Suzuki. 2020. Graph Neural Networks Exponentially Lose Expressive Power for Node Classification. In International Conference on Learning Representations."},{"key":"e_1_3_2_1_39_1","volume-title":"Anh Tuan Luu, Guy Wolf, and Dominique Beaini.","author":"Ramp\u00e1vsek Ladislav","year":"2022","unstructured":"Ladislav Ramp\u00e1vsek, Mikhail Galkin, Vijay Prakash Dwivedi, Anh Tuan Luu, Guy Wolf, and Dominique Beaini. 2022. Recipe for a General, Powerful, Scalable Graph Transformer. Advances in Neural Information Processing Systems, Vol. 35 (2022)."},{"key":"e_1_3_2_1_40_1","volume-title":"Markus Hagenbuchner, and Gabriele Monfardini.","author":"Scarselli Franco","year":"2008","unstructured":"Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. 2008. The graph neural network model. IEEE transactions on neural networks, Vol. 20, 1 (2008), 61--80."},{"key":"e_1_3_2_1_41_1","volume-title":"International conference on machine learning","author":"Shirzad Hamed","year":"2023","unstructured":"Hamed Shirzad, Ameya Velingker, Balaji Venkatachalam, Danica J Sutherland, and Ali Kemal Sinop. 2023. Exphormer: Sparse transformers for graphs. International conference on machine learning (2023)."},{"key":"e_1_3_2_1_42_1","volume-title":"The Eleventh International Conference on Learning Representations.","author":"Song Yunchong","year":"2023","unstructured":"Yunchong Song, Chenghu Zhou, Xinbing Wang, and Zhouhan Lin. 2023. Ordered GNN: Ordering Message Passing to Deal with Heterophily and Over-smoothing. In The Eleventh International Conference on Learning Representations."},{"volume-title":"International Conference on Learning Representations.","author":"Topping Jake","key":"e_1_3_2_1_43_1","unstructured":"Jake Topping, Francesco Di Giovanni, Benjamin Paul Chamberlain, Xiaowen Dong, and Michael M. Bronstein. 2022. Understanding over-squashing and bottlenecks on graphs via curvature. In International Conference on Learning Representations."},{"key":"e_1_3_2_1_44_1","volume-title":"Advances in Neural Information Processing Systems","volume":"30","author":"Vaswani Ashish","year":"2017","unstructured":"Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, \u0141ukasz Kaiser, and Illia Polosukhin. 2017. Attention is all you need. Advances in Neural Information Processing Systems, Vol. 30 (2017)."},{"key":"e_1_3_2_1_45_1","volume-title":"International Conference on Learning Representations","author":"Velivckovi\u0107 Petar","year":"2018","unstructured":"Petar Velivckovi\u0107, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. 2018. Graph attention networks. International Conference on Learning Representations (2018)."},{"volume-title":"Simplifying Graph Convolutional Networks. In International Conference on Machine Learning.","author":"Wu Felix","key":"e_1_3_2_1_46_1","unstructured":"Felix Wu, Tianyi Zhang, A. Souza, Christopher Fifty, Tao Yu, and Kilian Q. Weinberger. 2019. Simplifying Graph Convolutional Networks. In International Conference on Machine Learning."},{"key":"e_1_3_2_1_47_1","volume-title":"International Conference on Learning Representations","author":"Xu Keyulu","year":"2019","unstructured":"Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. 2019. How powerful are graph neural networks? International Conference on Learning Representations (2019)."},{"key":"e_1_3_2_1_48_1","volume-title":"International conference on machine learning. PMLR, 5453--5462","author":"Xu Keyulu","year":"2018","unstructured":"Keyulu Xu, Chengtao Li, Yonglong Tian, Tomohiro Sonobe, Ken-ichi Kawarabayashi, and Stefanie Jegelka. 2018. Representation learning on graphs with jumping knowledge networks. In International conference on machine learning. PMLR, 5453--5462."},{"key":"e_1_3_2_1_49_1","unstructured":"Chengxuan Ying Tianle Cai Shengjie Luo Shuxin Zheng Guolin Ke Di He Yanming Shen and Tie-Yan Liu. 2021. Do Transformers Really Perform Badly for Graph Representation?. In Advances in Neural Information Processing Systems."},{"key":"e_1_3_2_1_50_1","first-page":"15734","article-title":"Nested graph neural networks","volume":"34","author":"Zhang Muhan","year":"2021","unstructured":"Muhan Zhang and Pan Li. 2021. Nested graph neural networks. Advances in Neural Information Processing Systems, Vol. 34 (2021), 15734--15747.","journal-title":"Advances in Neural Information Processing Systems"},{"key":"e_1_3_2_1_51_1","volume-title":"Effectively Modeling Time Series with Simple Discrete State Spaces. In International Conference on Learning Representations.","author":"Zhang Michael","year":"2023","unstructured":"Michael Zhang, Khaled Kamal Saab, Michael Poli, Tri Dao, Karan Goel, and Christopher R\u00e9. 2023. Effectively Modeling Time Series with Simple Discrete State Spaces. In International Conference on Learning Representations."}],"event":{"name":"CIKM '24: The 33rd ACM International Conference on Information and Knowledge Management","sponsor":["SIGIR ACM Special Interest Group on Information Retrieval"],"location":"Boise ID USA","acronym":"CIKM '24"},"container-title":["Proceedings of the 33rd ACM International Conference on Information and Knowledge Management"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3627673.3679866","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,21]],"date-time":"2024-10-21T15:38:43Z","timestamp":1729525123000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3627673.3679866"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,10,21]]},"references-count":51,"alternative-id":["10.1145\/3627673.3679866","10.1145\/3627673"],"URL":"https:\/\/doi.org\/10.1145\/3627673.3679866","relation":{},"subject":[],"published":{"date-parts":[[2024,10,21]]},"assertion":[{"value":"2024-10-21","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}