{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,7]],"date-time":"2026-04-07T16:11:23Z","timestamp":1775578283039,"version":"3.50.1"},"publisher-location":"New York, NY, USA","reference-count":49,"publisher":"ACM","license":[{"start":{"date-parts":[[2025,7,20]],"date-time":"2025-07-20T00:00:00Z","timestamp":1752969600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2025,7,20]]},"DOI":"10.1145\/3690624.3709301","type":"proceedings-article","created":{"date-parts":[[2025,4,4]],"date-time":"2025-04-04T18:42:22Z","timestamp":1743792142000},"page":"49-60","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Fast and Effective GNN Training through Sequences of Random Path Graphs"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-9464-8315","authenticated-orcid":false,"given":"Francesco","family":"Bonchi","sequence":"first","affiliation":[{"name":"CENTAI Institute, Turin, Italy and Eurecat, Barcelona, Spain"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1551-2167","authenticated-orcid":false,"given":"Claudio","family":"Gentile","sequence":"additional","affiliation":[{"name":"Google Research, New York, NY, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0000-2936-1297","authenticated-orcid":false,"given":"Francesco Paolo","family":"Nerini","sequence":"additional","affiliation":[{"name":"Sapienza University, Rome, Italy and CENTAI Institute, Turin, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3336-0374","authenticated-orcid":false,"given":"Andr\u00e9","family":"Panisson","sequence":"additional","affiliation":[{"name":"CENTAI Institute, Turin, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0000-7398-9436","authenticated-orcid":false,"given":"Fabio","family":"Vitale","sequence":"additional","affiliation":[{"name":"CENTAI Institute, Turin, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2025,7,20]]},"reference":[{"key":"e_1_3_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.neucom.2020.10.096"},{"key":"e_1_3_2_2_2_1","volume-title":"9th 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 9th International Conference on Learning Representations (Virtual Event, Austria) (ICLR 2021)."},{"key":"e_1_3_2_2_3_1","volume-title":"Intl. Conf. on Machine Learning (ICML","volume":"2547","author":"Black Mitchell","year":"2023","unstructured":"Mitchell Black, Zhengchao Wan, Amir Nayyeri, and Yusu Wang. 2023. Understanding Oversquashing in GNNs through the Lens of Effective Resistance. In Intl. Conf. on Machine Learning (ICML 2023, Vol. 202). PMLR, 2528--2547."},{"key":"e_1_3_2_2_4_1","volume-title":"Adv. Neural Inf. Process. Syst.","volume":"32","author":"Hermsdorff Gecia Bravo","year":"2019","unstructured":"Gecia Bravo Hermsdorff and Lee Gunderson. 2019. A unifying framework for spectrum-preserving graph sparsification and coarsening. In Adv. Neural Inf. Process. Syst., Vol. 32."},{"key":"e_1_3_2_2_5_1","volume-title":"The 22nd Annual Conf. on Learning Theory","author":"Cesa-Bianchi Nicol\u00f2","year":"2009","unstructured":"Nicol\u00f2 Cesa-Bianchi, Claudio Gentile, and Fabio Vitale. 2009. Fast and optimal prediction on a labeled tree. In The 22nd Annual Conf. on Learning Theory (Montr\u00e9al, Canada) (COLT 2009). Omnipress, 145--156."},{"key":"e_1_3_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.5555\/2567709.2502620"},{"key":"e_1_3_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v34i04.5747"},{"key":"e_1_3_2_2_8_1","volume-title":"6th International Conference on Learning Representations (ICLR","author":"Chen Jie","year":"2018","unstructured":"Jie Chen, Tengfei Ma, and Cao Xiao. 2018. FastGCN: Fast Learning with Graph Convolutional Networks via Importance Sampling. In 6th International Conference on Learning Representations (ICLR 2018)."},{"key":"e_1_3_2_2_9_1","volume-title":"Proceedings of the 35th International Conference on Machine Learning (ICML","volume":"949","author":"Chen Jianfei","year":"2018","unstructured":"Jianfei Chen, Jun Zhu, and Le Song. 2018. Stochastic Training of Graph Convolutional Networks with Variance Reduction. In Proceedings of the 35th International Conference on Machine Learning (ICML 2018, Vol. 80). PMLR, 941--949."},{"key":"e_1_3_2_2_10_1","first-page":"14556","article-title":"Scalable graph neural networks via bidirectional propagation","volume":"33","author":"Chen Ming","year":"2020","unstructured":"Ming Chen, Zhewei Wei, Bolin Ding, Yaliang Li, Ye Yuan, Xiaoyong Du, and Ji-RongWen. 2020. Scalable graph neural networks via bidirectional propagation. In Adv. Neural Inf. Process. Syst., Vol. 33. 14556--14566.","journal-title":"Adv. Neural Inf. Process. Syst."},{"key":"e_1_3_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/3292500.3330925"},{"key":"e_1_3_2_2_12_1","volume-title":"Spectral graph theory","author":"Chung Fan RK","unstructured":"Fan RK Chung. 1997. Spectral graph theory. Vol. 92. American Mathematical Soc."},{"key":"e_1_3_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/3394486.3403192"},{"key":"e_1_3_2_2_14_1","volume-title":"GraphZoom: A Multi-level Spectral Approach for Accurate and Scalable Graph Embedding. In 8th International Conference on Learning Representations (Addis Ababa, Ethiopia,) (ICLR","author":"Deng Chenhui","year":"2020","unstructured":"Chenhui Deng, Zhiqiang Zhao, Yongyu Wang, Zhiru Zhang, and Zhuo Feng. 2020. GraphZoom: A Multi-level Spectral Approach for Accurate and Scalable Graph Embedding. In 8th International Conference on Learning Representations (Addis Ababa, Ethiopia,) (ICLR 2020)."},{"key":"e_1_3_2_2_15_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_2_16_1","volume-title":"Adv. Neural Inf. Process. Syst.","volume":"35","author":"Ding Mucong","year":"2022","unstructured":"Mucong Ding, Tahseen Rabbani, Bang An, Evan Wang, and Furong Huang. 2022. Sketch-GNN: Scalable Graph Neural Networks with Sublinear Training Complexity. In Adv. Neural Inf. Process. Syst., Vol. 35."},{"key":"e_1_3_2_2_17_1","volume-title":"Fast graph representation learning with PyTorch Geometric. arXiv preprint arXiv:1903.02428","author":"Fey Matthias","year":"2019","unstructured":"Matthias Fey and Jan Eric Lenssen. 2019. Fast graph representation learning with PyTorch Geometric. arXiv preprint arXiv:1903.02428 (2019)."},{"key":"e_1_3_2_2_18_1","volume-title":"International conference on machine learning. PMLR, 3294--3304","author":"Fey Matthias","year":"2021","unstructured":"Matthias Fey, Jan E Lenssen, Frank Weichert, and Jure Leskovec. 2021. Gnnautoscale: Scalable and expressive graph neural networks via historical embeddings. In International conference on machine learning. PMLR, 3294--3304."},{"key":"e_1_3_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-09037-0_54"},{"key":"e_1_3_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/3583780.3614997"},{"key":"e_1_3_2_2_21_1","unstructured":"Will Hamilton Zhitao Ying and Jure Leskovec. 2017. Inductive Representation Learning on Large Graphs. In Adv. Neural Inf. Process. Syst."},{"key":"e_1_3_2_2_22_1","volume-title":"Adv. Neural Inf. Process. Syst.","volume":"19","author":"Herbster Mark","year":"2006","unstructured":"Mark Herbster and Massimiliano Pontil. 2006. Prediction on a graph with a perceptron. In Adv. Neural Inf. Process. Syst., Vol. 19."},{"key":"e_1_3_2_2_23_1","volume-title":"Tsourakakis","author":"Hoskins Jeremy G.","year":"2018","unstructured":"Jeremy G. Hoskins, Cameron Musco, Christopher Musco, and Charalampos E. Tsourakakis. 2018. Inferring networks from random walk-based node similarities. In Adv. Neural Inf. Process. Syst. 3708--3719."},{"key":"e_1_3_2_2_24_1","volume-title":"Adv. Neural Inf. Process. Syst.","volume":"33","author":"Hu Weihua","year":"2020","unstructured":"Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. 2020. Open graph benchmark: Datasets for machine learning on graphs. In Adv. Neural Inf. Process. Syst., Vol. 33."},{"key":"e_1_3_2_2_25_1","volume-title":"Adv. Neural Inf. Process. Syst.","volume":"31","author":"Huang Wenbing","year":"2018","unstructured":"Wenbing Huang, Tong Zhang, Yu Rong, and Junzhou Huang. 2018. Adaptive sampling towards fast graph representation learning. In Adv. Neural Inf. Process. Syst., Vol. 31."},{"key":"e_1_3_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/3447548.3467256"},{"key":"e_1_3_2_2_27_1","volume-title":"Graph Condensation for Graph Neural Networks. In The Tenth International Conference on Learning Representations (Virtual Event) (ICLR","author":"Jin Wei","year":"2022","unstructured":"Wei Jin, Lingxiao Zhao, Shichang Zhang, Yozen Liu, Jiliang Tang, and Neil Shah. 2022. Graph Condensation for Graph Neural Networks. In The Tenth International Conference on Learning Representations (Virtual Event) (ICLR 2022)."},{"key":"e_1_3_2_2_28_1","volume-title":"Adam: A Method for Stochastic Optimization. In 3rd International Conference on Learning Representations","author":"Diederik","year":"2015","unstructured":"Diederik P. Kingma and Jimmy Ba. 2015. Adam: A Method for Stochastic Optimization. In 3rd International Conference on Learning Representations (San Diego, CA, USA) (ICLR 2015)."},{"key":"e_1_3_2_2_29_1","volume-title":"Semi-Supervised Classification with Graph Convolutional Networks. In 5th International Conference on Learning Representations","author":"Thomas","year":"2017","unstructured":"Thomas N. Kipf and Max Welling. 2017. Semi-Supervised Classification with Graph Convolutional Networks. In 5th International Conference on Learning Representations (Toulon, France) (ICLR 2017)."},{"key":"e_1_3_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.3113\/JSOA.2018.0261"},{"key":"e_1_3_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.24963\/ijcai.2022\/772"},{"key":"e_1_3_2_2_32_1","first-page":"1","article-title":"Graph Reduction with Spectral and Cut Guarantees","volume":"20","author":"Loukas Andreas","year":"2019","unstructured":"Andreas Loukas. 2019. Graph Reduction with Spectral and Cut Guarantees. J. Mach. Learn. Res. 20, 116 (2019), 1--42.","journal-title":"J. Mach. Learn. Res."},{"key":"e_1_3_2_2_33_1","volume-title":"International Conference on Machine Learning. PMLR, 3237--3246","author":"Loukas Andreas","year":"2018","unstructured":"Andreas Loukas and Pierre Vandergheynst. 2018. Spectrally approximating large graphs with smaller graphs. In International Conference on Machine Learning. PMLR, 3237--3246."},{"key":"e_1_3_2_2_34_1","volume-title":"Probability on trees and networks","author":"Lyons Russell","unstructured":"Russell Lyons and Yuval Peres. 2017. Probability on trees and networks. Vol. 42. Cambridge University Press."},{"key":"e_1_3_2_2_35_1","volume-title":"Adv. Neural Inf. Process. Syst.","volume":"32","author":"Paszke Adam","year":"2019","unstructured":"Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. 2019. Pytorch: An imperative style, high-performance deep learning library. In Adv. Neural Inf. Process. Syst., Vol. 32."},{"key":"e_1_3_2_2_36_1","volume-title":"A Survey on Oversmoothing in Graph Neural Networks. arXiv preprint arXiv:2303.10993","author":"Rusch T. Konstantin","year":"2023","unstructured":"T. Konstantin Rusch, Michael M. Bronstein, and Siddhartha Mishra. 2023. A Survey on Oversmoothing in Graph Neural Networks. arXiv preprint arXiv:2303.10993 (2023)."},{"key":"e_1_3_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2024.3397692"},{"key":"e_1_3_2_2_38_1","volume-title":"The Eleventh International Conference on Learning Representations (Kigali, Rwanda) (ICLR","author":"Shi Zhihao","year":"2023","unstructured":"Zhihao Shi, Xize Liang, and Jie Wang. 2023. LMC: Fast training of GNNs via subgraph sampling with provable convergence. In The Eleventh International Conference on Learning Representations (Kigali, Rwanda) (ICLR 2023)."},{"key":"e_1_3_2_2_39_1","volume-title":"Super-convergence: Very fast training of neural networks using large learning rates. In Artificial intelligence and machine learning for multi-domain operations applications","author":"Smith Leslie N","year":"2019","unstructured":"Leslie N Smith and Nicholay Topin. 2019. Super-convergence: Very fast training of neural networks using large learning rates. In Artificial intelligence and machine learning for multi-domain operations applications, Vol. 11006. SPIE, 369--386."},{"key":"e_1_3_2_2_40_1","unstructured":"Rakshith S Srinivasa Cao Xiao Lucas Glass Justin Romberg and Jimeng Sun. 2020. Fast graph attention networks using effective resistance based graph sparsification. (2020). arXiv:arXiv preprint arXiv:2006.08796"},{"key":"e_1_3_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/1401890.1402008"},{"key":"e_1_3_2_2_42_1","volume-title":"The Tenth International Conference on Learning Representations (Virtual Event) (ICLR","author":"Topping Jake","year":"2022","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 The Tenth International Conference on Learning Representations (Virtual Event) (ICLR 2022)."},{"key":"e_1_3_2_2_43_1","volume-title":"6th International Conference on Learning Representations","author":"Velickovic Petar","year":"2018","unstructured":"Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, Yoshua Bengio, et al. 2018. Graph attention networks. In 6th International Conference on Learning Representations (Vancouver, BC, Canada) (ICLR 2018)."},{"key":"e_1_3_2_2_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/237814.237880"},{"key":"e_1_3_2_2_45_1","unstructured":"Xinyi Wu Amir Ajorlou Zihui Wu and Ali Jadbabaie. 2023. Demystifying Oversmoothing in Attention-Based Graph Neural Networks. In Adv. Neural Inf. Process. Syst."},{"key":"e_1_3_2_2_46_1","volume-title":"International conference on machine learning. PMLR, 40--48","author":"Yang Zhilin","year":"2016","unstructured":"Zhilin Yang, William Cohen, and Ruslan Salakhudinov. 2016. Revisiting semisupervised learning with graph embeddings. In International conference on machine learning. PMLR, 40--48."},{"key":"e_1_3_2_2_47_1","volume-title":"GraphSAINT: Graph Sampling Based Inductive Learning Method. In 8th International Conference on Learning Representations (ICLR","author":"Zeng Hanqing","year":"2020","unstructured":"Hanqing Zeng, Hongkuan Zhou, Ajitesh Srivastava, Rajgopal Kannan, and Viktor K. Prasanna. 2020. GraphSAINT: Graph Sampling Based Inductive Learning Method. In 8th International Conference on Learning Representations (ICLR 2020)."},{"key":"e_1_3_2_2_48_1","unstructured":"Shichang Zhang Atefeh Sohrabizadeh ChengWan Zijie Huang Ziniu Hu Yewen Wang Jason Cong Yizhou Sun et al. 2023. A Survey on Graph Neural Network Acceleration: Algorithms Systems and Customized Hardware. arXiv preprint arXiv:2306.14052 (2023)."},{"key":"e_1_3_2_2_49_1","volume-title":"Adv. Neural Inf. Process. Syst.","volume":"32","author":"Zou Difan","year":"2019","unstructured":"Difan Zou, Ziniu Hu, Yewen Wang, Song Jiang, Yizhou Sun, and Quanquan Gu. 2019. Layer-dependent importance sampling for training deep and large graph convolutional networks. In Adv. Neural Inf. Process. Syst., Vol. 32."}],"event":{"name":"KDD '25: The 31st ACM SIGKDD Conference on Knowledge Discovery and Data Mining","location":"Toronto ON Canada","acronym":"KDD '25","sponsor":["SIGMOD ACM Special Interest Group on Management of Data","SIGKDD ACM Special Interest Group on Knowledge Discovery in Data"]},"container-title":["Proceedings of the 31st ACM SIGKDD Conference on Knowledge Discovery and Data Mining V.1"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3690624.3709301","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3690624.3709301","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,16]],"date-time":"2025-08-16T15:35:55Z","timestamp":1755358555000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3690624.3709301"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,7,20]]},"references-count":49,"alternative-id":["10.1145\/3690624.3709301","10.1145\/3690624"],"URL":"https:\/\/doi.org\/10.1145\/3690624.3709301","relation":{},"subject":[],"published":{"date-parts":[[2025,7,20]]},"assertion":[{"value":"2025-07-20","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}