{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,26]],"date-time":"2026-06-26T13:47:34Z","timestamp":1782481654065,"version":"3.54.5"},"reference-count":65,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2026,6,26]],"date-time":"2026-06-26T00:00:00Z","timestamp":1782432000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/legalcode"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"crossref","award":["U24A20234"],"award-info":[{"award-number":["U24A20234"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Ant Group through CCF-Ant Research Fund","award":["CCF-AFSGRF20240205"],"award-info":[{"award-number":["CCF-AFSGRF20240205"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Archit. Code Optim."],"published-print":{"date-parts":[[2026,6,30]]},"abstract":"<jats:p>Graph sampling plays a critical role in graph learning applications, notably within Graph Neural Networks (GNNs). Typically, the performance of GPU-based graph sampling is determined by the efficiency of sampling kernels. Different sampling methods excel under different conditions, and no single method consistently outperforms others in all scenarios. As sampling applications become increasingly complex, graph-related sparse operations can dominate the computational workload, with performance heavily influenced by storage formats. In this article, we propose DGS, a GPU-based graph sampling framework that can detach the kernel implementation from computation logic. In addition to sampling kernels, DGS jointly optimizes sparse graph kernels. It can adaptively switch between different execution strategies based on various inputs. Experiments show that DGS outperforms current state-of-the-art GPU sampling frameworks, achieving speedups ranging from 1.1\u00d7 to 92.0\u00d7. This adaptability and performance improvement establish DGS as a highly effective and efficient solution for diverse graph sampling scenarios.<\/jats:p>","DOI":"10.1145\/3817060","type":"journal-article","created":{"date-parts":[[2026,5,20]],"date-time":"2026-05-20T11:24:59Z","timestamp":1779276299000},"page":"1-26","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["DGS: A GPU-based Adaptive Graph Sampling Framework"],"prefix":"10.1145","volume":"23","author":[{"ORCID":"https:\/\/orcid.org\/0009-0008-1956-1242","authenticated-orcid":false,"given":"Junyi","family":"Mei","sequence":"first","affiliation":[{"name":"Shanghai Jiao Tong University","place":["Shanghai, China"]}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4060-9438","authenticated-orcid":false,"given":"Shixuan","family":"Sun","sequence":"additional","affiliation":[{"name":"Shanghai Jiao Tong University","place":["Shanghai, China"]}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6218-4659","authenticated-orcid":false,"given":"Chao","family":"Li","sequence":"additional","affiliation":[{"name":"Shanghai Jiao Tong University","place":["Shanghai, China"]}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3764-8065","authenticated-orcid":false,"given":"Xinkai","family":"Wang","sequence":"additional","affiliation":[{"name":"Shanghai Jiao Tong University","place":["Shanghai, China"]}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7260-0521","authenticated-orcid":false,"given":"Jing","family":"Wang","sequence":"additional","affiliation":[{"name":"Shanghai Jiao Tong University","place":["Shanghai, China"]}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4372-7851","authenticated-orcid":false,"given":"Xiaofeng","family":"Hou","sequence":"additional","affiliation":[{"name":"Shanghai Jiao Tong University","place":["Shanghai, China"]}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0034-2302","authenticated-orcid":false,"given":"Minyi","family":"Guo","sequence":"additional","affiliation":[{"name":"Computer Science, Shanghai Jiao Tong University","place":["Shanghai, China"]}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3440-9675","authenticated-orcid":false,"given":"Yongchao","family":"Liu","sequence":"additional","affiliation":[{"name":"Ant Group CO Ltd","place":["Hangzhou, China"]}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0009-3472-6102","authenticated-orcid":false,"given":"Chuntao","family":"Hong","sequence":"additional","affiliation":[{"name":"Ant Group Co Ltd","place":["Hangzhou, China"]}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2026,6,26]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"publisher","DOI":"10.1145\/1963405.1963488"},{"key":"e_1_3_2_3_2","doi-asserted-by":"publisher","DOI":"10.1145\/988672.988752"},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.1109\/CGO51591.2021.9370321"},{"key":"e_1_3_2_5_2","doi-asserted-by":"publisher","DOI":"10.1093\/biomet\/69.3.653"},{"key":"e_1_3_2_6_2","volume-title":"International Conference on Learning Representations","author":"Chen Jie","year":"2018","unstructured":"Jie Chen, Tengfei Ma, and Cao Xiao. 2018. FastGCN: Fast learning with graph convolu-tional networks via importance sampling. In International Conference on Learning Representations. International Conference on Learning Representations, ICLR."},{"key":"e_1_3_2_7_2","first-page":"942","volume-title":"International Conference on Machine Learning","author":"Chen Jianfei","year":"2018","unstructured":"Jianfei Chen, Jun Zhu, and Le Song. 2018. Stochastic training of graph convolutional networks with variance reduction. In International Conference on Machine Learning. PMLR, 942\u2013950."},{"key":"e_1_3_2_8_2","doi-asserted-by":"publisher","DOI":"10.1145\/3545008.3545056"},{"key":"e_1_3_2_9_2","unstructured":"Xinhao Cheng Zhihao Zhang Yu Zhou Jianan Ji Jinchen Jiang Zepeng Zhao Ziruo Xiao Zihao Ye Yingyi Huang Ruihang Lai et\u00a0al. 2025. Mirage persistent kernel: A compiler and runtime for mega-kernelizing tensor programs. arXiv:2512.22219. Retrieved from https:\/\/arxiv.org\/abs\/2512.22219"},{"key":"e_1_3_2_10_2","doi-asserted-by":"publisher","DOI":"10.1145\/3102254.3102279"},{"key":"e_1_3_2_11_2","volume-title":"ICLR Workshop on Representation Learning on Graphs and Manifolds","author":"Fey Matthias","year":"2019","unstructured":"Matthias Fey and Jan E. Lenssen. 2019. Fast graph representation learning with PyTorch geometric. In ICLR Workshop on Representation Learning on Graphs and Manifolds."},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.1080\/15427951.2005.10129104"},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.5555\/3433701.3433723"},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.1145\/3600006.3613168"},{"key":"e_1_3_2_15_2","doi-asserted-by":"publisher","DOI":"10.1145\/2939672.2939754"},{"key":"e_1_3_2_16_2","article-title":"Inductive representation learning on large graphs","volume":"30","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 30 (2017).","journal-title":"Advances in Neural Information Processing Systems"},{"key":"e_1_3_2_17_2","first-page":"22118","volume-title":"Proceedings of the 34th International Conference on Neural Information Processing Systems","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 Proceedings of the 34th International Conference on Neural Information Processing Systems. 22118\u201322133."},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.1109\/SC41405.2020.00076"},{"key":"e_1_3_2_19_2","doi-asserted-by":"publisher","DOI":"10.1145\/3447786.3456244"},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","DOI":"10.1145\/3559009.3569686"},{"key":"e_1_3_2_21_2","doi-asserted-by":"publisher","DOI":"10.1145\/3184558.3186929"},{"key":"e_1_3_2_22_2","doi-asserted-by":"publisher","DOI":"10.5555\/3433701.3433816"},{"key":"e_1_3_2_23_2","doi-asserted-by":"publisher","DOI":"10.1145\/2507157.2507173"},{"key":"e_1_3_2_24_2","first-page":"31","volume-title":"10th USENIX Symposium on Operating Systems Design and Implementation, OSDI 2012, Hollywood, CA, USA, October 8-10, 2012","author":"Kyrola Aapo","year":"2012","unstructured":"Aapo Kyrola, Guy E. Blelloch, and Carlos Guestrin. 2012. GraphChi: Large-scale graph computation on just a PC. In 10th USENIX Symposium on Operating Systems Design and Implementation, OSDI 2012, Hollywood, CA, USA, October 8-10, 2012. 31\u201346. Retrieved from https:\/\/www.usenix.org\/conference\/osdi12\/technical-sessions\/presentation\/kyrola"},{"key":"e_1_3_2_25_2","article-title":"SNAP Datasets: Stanford Large Network Dataset Collection","author":"Leskovec Jure","year":"2014","unstructured":"Jure Leskovec and Andrej Krevl. 2014. SNAP Datasets: Stanford Large Network Dataset Collection. Retrieved from http:\/\/snap.stanford.edu\/data","journal-title":"http:\/\/snap.stanford.edu\/data"},{"key":"e_1_3_2_26_2","doi-asserted-by":"publisher","DOI":"10.1145\/3581784.3607038"},{"key":"e_1_3_2_27_2","doi-asserted-by":"publisher","DOI":"10.18653\/v1\/D19-1334"},{"key":"e_1_3_2_28_2","unstructured":"Costas Mavromatis and George Karypis. 2024. Gnn-rag: Graph neural retrieval for large language model reasoning. arXiv:2405.20139. Retrieved from https:\/\/arxiv.org\/abs\/2405.20139"},{"key":"e_1_3_2_29_2","doi-asserted-by":"publisher","DOI":"10.14778\/3659437.3659438"},{"key":"e_1_3_2_30_2","doi-asserted-by":"publisher","DOI":"10.1145\/3293883.3295716"},{"key":"e_1_3_2_31_2","unstructured":"Tomas Mikolov Kai Chen Greg Corrado and Jeffrey Dean. 2013. Efficient estimation of word representations in vector space. arXiv:1301.3781. Retrieved from https:\/\/arxiv.org\/abs\/1301.3781"},{"key":"e_1_3_2_32_2","article-title":"Fast inverse transform sampling in one and two dimensions","author":"Olver S.","year":"2013","unstructured":"S. Olver and A. Townsend. 2013. Fast inverse transform sampling in one and two dimensions. arXiv: Numerical Analysis (2013).","journal-title":"arXiv: Numerical Analysis"},{"key":"e_1_3_2_33_2","unstructured":"Lawrence Page Sergey Brin Rajeev Motwani and Terry Winograd. 1998. The PageRank Citation Ranking: Bringing Order to the Web. Stanford Digital Library Technologies Project. Retrieved from http:\/\/citeseerx.ist.psu.edu\/viewdoc\/summary?doi=10.1.1.31.1768"},{"key":"e_1_3_2_34_2","doi-asserted-by":"publisher","DOI":"10.1109\/SC41405.2020.00060"},{"key":"e_1_3_2_35_2","doi-asserted-by":"publisher","DOI":"10.1145\/2623330.2623732"},{"key":"e_1_3_2_36_2","article-title":"PyTorch","year":"2025","unstructured":"PyTorch. 2025. PyTorch. Retrieved from https:\/\/pytorch.org\/. Last accessed on 2025-05-13.","journal-title":"https:\/\/pytorch.org\/"},{"key":"e_1_3_2_37_2","article-title":"torch.fx","year":"2025","unstructured":"PyTorch. 2025. torch.fx. Retrieved from https:\/\/docs.pytorch.org\/docs\/stable\/fx.html. Last accessed on 2025-05-13.","journal-title":"https:\/\/docs.pytorch.org\/docs\/stable\/fx.html"},{"key":"e_1_3_2_38_2","doi-asserted-by":"publisher","DOI":"10.1145\/3649329.3656504"},{"key":"e_1_3_2_39_2","doi-asserted-by":"publisher","DOI":"10.1145\/2499370.2462176"},{"key":"e_1_3_2_40_2","volume-title":"Springer Science & Business Media","author":"Robert Christian","year":"2013","unstructured":"Christian Robert and George Casella. 2013. Monte carlo statistical methods. In Springer Science & Business Media."},{"key":"e_1_3_2_41_2","doi-asserted-by":"publisher","DOI":"10.1145\/3710848.3710858"},{"key":"e_1_3_2_42_2","doi-asserted-by":"publisher","DOI":"10.14778\/3476249.3476257"},{"key":"e_1_3_2_43_2","doi-asserted-by":"publisher","DOI":"10.1145\/2481244.2481248"},{"key":"e_1_3_2_44_2","doi-asserted-by":"publisher","DOI":"10.1109\/CGO57630.2024.10444812"},{"key":"e_1_3_2_45_2","doi-asserted-by":"publisher","DOI":"10.1145\/3588944"},{"key":"e_1_3_2_46_2","doi-asserted-by":"publisher","DOI":"10.1145\/3147.3165"},{"key":"e_1_3_2_47_2","doi-asserted-by":"publisher","DOI":"10.1145\/355744.355749"},{"key":"e_1_3_2_48_2","doi-asserted-by":"publisher","DOI":"10.1145\/3219819.3219869"},{"key":"e_1_3_2_49_2","unstructured":"Minjie Wang Lingfan Yu Da Zheng Quan Gan Yu Gai Zihao Ye Mufei Li Jinjing Zhou Qi Huang Chao Ma et\u00a0al. 2019. Deep graph library: Towards efficient and scalable deep learning on graphs. arXiv:1909.01315. Retrieved from https:\/\/arxiv.org\/abs\/1909.01315"},{"key":"e_1_3_2_50_2","doi-asserted-by":"publisher","DOI":"10.1109\/PACT52795.2021.00029"},{"key":"e_1_3_2_51_2","article-title":"Optimizing GPU-based graph sampling and random walk for efficiency and scalability","author":"Wang Pengyu","year":"2023","unstructured":"Pengyu Wang, Cheng Xu, Chao Li, Jing Wang, Taolei Wang, Lu Zhang, Xiaofeng Hou, and Minyi Guo. 2023. Optimizing GPU-based graph sampling and random walk for efficiency and scalability. IEEE Trans. Comput. (2023).","journal-title":"IEEE Trans. Comput."},{"key":"e_1_3_2_52_2","first-page":"559","volume-title":"2020 USENIX Annual Technical Conference (USENIX ATC 20)","author":"Wang Rui","year":"2020","unstructured":"Rui Wang, Yongkun Li, Hong Xie, Yinlong Xu, and John C. S. Lui. 2020. \\(\\lbrace\\) GraphWalker \\(\\rbrace\\) : An \\(\\lbrace\\) I\/O-efficient \\(\\rbrace\\) and \\(\\lbrace\\) resource-friendly \\(\\rbrace\\) graph analytic system for fast and scalable random walks. In 2020 USENIX Annual Technical Conference (USENIX ATC 20). 559\u2013571."},{"key":"e_1_3_2_53_2","doi-asserted-by":"publisher","DOI":"10.1145\/3582016.3582025"},{"key":"e_1_3_2_54_2","doi-asserted-by":"publisher","DOI":"10.1145\/2851141.2851145"},{"key":"e_1_3_2_55_2","first-page":"149","volume-title":"2023 USENIX Annual Technical Conference (USENIX ATC 23)","author":"Wang Yuke","year":"2023","unstructured":"Yuke Wang, Boyuan Feng, Zheng Wang, Guyue Huang, and Yufei Ding. 2023. \\(\\lbrace\\) TC-GNN \\(\\rbrace\\) : Bridging sparse \\(\\lbrace\\) GNN \\(\\rbrace\\) computation and dense tensor cores on \\(\\lbrace\\) GPUs \\(\\rbrace\\) . In 2023 USENIX Annual Technical Conference (USENIX ATC 23). 149\u2013164."},{"key":"e_1_3_2_56_2","doi-asserted-by":"publisher","DOI":"10.1145\/3447786.3456247"},{"key":"e_1_3_2_57_2","series-title":"SC\u201922","volume-title":"Proceedings of the International Conference on High Performance Computing, Networking, Storage and Analysis","author":"Yang Dongxu","year":"2022","unstructured":"Dongxu Yang, Junhong Liu, Jiaxing Qi, and Junjie Lai. 2022. WholeGraph: A fast graph neural network training framework with multi-GPU distributed shared memory architecture. In Proceedings of the International Conference on High Performance Computing, Networking, Storage and Analysis (Dallas, Texas) (SC\u201922). IEEE Press, Article 54, 14 pages."},{"key":"e_1_3_2_58_2","doi-asserted-by":"publisher","DOI":"10.1145\/3341301.3359634"},{"key":"e_1_3_2_59_2","doi-asserted-by":"publisher","DOI":"10.1145\/3572848.3577506"},{"key":"e_1_3_2_60_2","unstructured":"Hanqing Zeng Hongkuan Zhou Ajitesh Srivastava Rajgopal Kannan and Viktor Prasanna. 2019. Graphsaint: Graph sampling based inductive learning method. arXiv:1907.04931. Retrieved from https:\/\/arxiv.org\/abs\/1907.04931"},{"key":"e_1_3_2_61_2","doi-asserted-by":"publisher","DOI":"10.1145\/3368826.3377909"},{"key":"e_1_3_2_62_2","doi-asserted-by":"publisher","DOI":"10.1145\/3276491"},{"key":"e_1_3_2_63_2","doi-asserted-by":"publisher","DOI":"10.1145\/3575693.3575723"},{"key":"e_1_3_2_64_2","doi-asserted-by":"publisher","DOI":"10.1145\/3587135.3592199"},{"key":"e_1_3_2_65_2","article-title":"FastGL: A GPU-efficient framework for accelerating sampling-based GNN training at large scale","author":"Zhu Zeyu","year":"2024","unstructured":"Zeyu Zhu, Peisong Wang, Qinghao Hu, Gang Li, Xiaoyao Liang, and Jian Cheng. 2024. FastGL: A GPU-efficient framework for accelerating sampling-based GNN training at large scale. arXiv preprint arXiv:2409.14939 (2024).","journal-title":"arXiv preprint"},{"key":"e_1_3_2_66_2","volume-title":"Layer-Dependent Importance Sampling for Training Deep and Large Graph Convolutional Networks","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. Curran Associates Inc., Red Hook, NY, USA."}],"container-title":["ACM Transactions on Architecture and Code Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3817060","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,6,26]],"date-time":"2026-06-26T12:57:42Z","timestamp":1782478662000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3817060"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,6,26]]},"references-count":65,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2026,6,30]]}},"alternative-id":["10.1145\/3817060"],"URL":"https:\/\/doi.org\/10.1145\/3817060","relation":{},"ISSN":["1544-3566","1544-3973"],"issn-type":[{"value":"1544-3566","type":"print"},{"value":"1544-3973","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,6,26]]},"assertion":[{"value":"2025-11-15","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2026-05-01","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2026-06-26","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}