{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,14]],"date-time":"2026-03-14T17:59:49Z","timestamp":1773511189227,"version":"3.50.1"},"reference-count":38,"publisher":"Association for Computing Machinery (ACM)","issue":"5","license":[{"start":{"date-parts":[[2022,3,9]],"date-time":"2022-03-09T00:00:00Z","timestamp":1646784000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"JSPS KAKENHI","award":["20H04244 and 21J22490"],"award-info":[{"award-number":["20H04244 and 21J22490"]}]},{"name":"JST PRESTO program","award":["JPMJPR165A"],"award-info":[{"award-number":["JPMJPR165A"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Knowl. Discov. Data"],"published-print":{"date-parts":[[2022,10,31]]},"abstract":"<jats:p>The recent advancements in graph neural networks (GNNs) have led to state-of-the-art performances in various applications, including chemo-informatics, question-answering systems, and recommender systems. However, scaling up these methods to huge graphs, such as social networks and Web graphs, remains a challenge. In particular, the existing methods for accelerating GNNs either are not theoretically guaranteed in terms of the approximation error or incurred at least a linear time computation cost. In this study, we reveal the query complexity of the uniform node sampling scheme for Message Passing Neural Networks, including GraphSAGE, graph attention networks (GATs), and graph convolutional networks (GCNs). Surprisingly, our analysis reveals that the complexity of the node sampling method is completely independent of the number of the nodes, edges, and neighbors of the input and depends only on the error tolerance and confidence probability while providing a theoretical guarantee for the approximation error. To the best of our knowledge, this is the first article to provide a theoretical guarantee of approximation for GNNs within constant time. Through experiments with synthetic and real-world datasets, we investigated the speed and precision of the node sampling scheme and validated our theoretical results.<\/jats:p>","DOI":"10.1145\/3502733","type":"journal-article","created":{"date-parts":[[2022,3,10]],"date-time":"2022-03-10T14:03:20Z","timestamp":1646921000000},"page":"1-31","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["Constant Time Graph Neural Networks"],"prefix":"10.1145","volume":"16","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-6912-4464","authenticated-orcid":false,"given":"Ryoma","family":"Sato","sequence":"first","affiliation":[{"name":"Kyoto University, RIKEN AIP, Sakyo-ku, Kyoto, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Makoto","family":"Yamada","sequence":"additional","affiliation":[{"name":"Kyoto University, RIKEN AIP, Sakyo-ku, Kyoto, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hisashi","family":"Kashima","sequence":"additional","affiliation":[{"name":"Kyoto University, RIKEN AIP, Sakyo-ku, Kyoto, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2022,3,9]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"publisher","DOI":"10.1126\/science.286.5439.509"},{"key":"e_1_3_2_3_2","doi-asserted-by":"publisher","DOI":"10.1021\/ci940128y"},{"key":"e_1_3_2_4_2","volume-title":"Proceedings of the 2nd International Conference on Learning Representations","author":"Bruna Joan","year":"2014","unstructured":"Joan Bruna, Wojciech Zaremba, Arthur Szlam, and Yann LeCun. 2014. Spectral networks and locally connected networks on graphs. In Proceedings of the 2nd International Conference on Learning Representations."},{"key":"e_1_3_2_5_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539702403244"},{"key":"e_1_3_2_6_2","volume-title":"Proceedings of the 6th International Conference on Learning Representations","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 Proceedings of the 6th International Conference on Learning Representations."},{"key":"e_1_3_2_7_2","first-page":"941","volume-title":"Proceedings of the 35th 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 Proceedings of the 35th International Conference on Machine Learning. 941\u2013949."},{"key":"e_1_3_2_8_2","doi-asserted-by":"publisher","DOI":"10.1145\/3292500.3330925"},{"key":"e_1_3_2_9_2","doi-asserted-by":"publisher","DOI":"10.1145\/1007352.1007386"},{"key":"e_1_3_2_10_2","first-page":"3837","volume-title":"Proceedings of the 29th Advances in Neural Information Processing Systems, NeurIPS","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. In Proceedings of the 29th Advances in Neural Information Processing Systems, NeurIPS. 3837\u20133845."},{"key":"e_1_3_2_11_2","doi-asserted-by":"crossref","first-page":"290","DOI":"10.5486\/PMD.1959.6.3-4.12","article-title":"On random graphs I","volume":"6","author":"Erd\u0151s Paul","year":"1959","unstructured":"Paul Erd\u0151s and Alfr\u00e9d R\u00e9nyi. 1959. On random graphs I. Publicationes Mathematicae 6 (1959), 290\u2013297.","journal-title":"Publicationes Mathematicae"},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.1145\/3308558.3313488"},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.5555\/3305381.3305512"},{"key":"e_1_3_2_14_2","first-page":"249","volume-title":"Proceedings of the 13th International Conference on Artificial Intelligence and Statistics","author":"Glorot Xavier","year":"2010","unstructured":"Xavier Glorot and Yoshua Bengio. 2010. Understanding the difficulty of training deep feedforward neural networks. In Proceedings of the 13th International Conference on Artificial Intelligence and Statistics. PMLR, 249\u2013256."},{"key":"e_1_3_2_15_2","doi-asserted-by":"publisher","DOI":"10.1109\/IJCNN.2005.1555942"},{"key":"e_1_3_2_16_2","first-page":"1025","volume-title":"Proceedings of the 30st Advances in Neural Information Processing Systems, NeurIPS","author":"Hamilton William L.","year":"2017","unstructured":"William L. Hamilton, Zhitao Ying, and Jure Leskovec. 2017. Inductive representation learning on large graphs. In Proceedings of the 30st Advances in Neural Information Processing Systems, NeurIPS. 1025\u20131035."},{"key":"e_1_3_2_17_2","first-page":"2217","volume-title":"Proceedings of the 29th Advances in Neural Information Processing Systems, NeurIPS","author":"Hayashi Kohei","year":"2016","unstructured":"Kohei Hayashi and Yuichi Yoshida. 2016. Minimizing quadratic functions in constant time. In Proceedings of the 29th Advances in Neural Information Processing Systems, NeurIPS. 2217\u20132225."},{"key":"e_1_3_2_18_2","first-page":"2470","volume-title":"Proceedings of the Advances in Neural Information Processing Systems 30, NeurIPS","author":"Hayashi Kohei","year":"2017","unstructured":"Kohei Hayashi and Yuichi Yoshida. 2017. Fitting low-rank tensors in constant time. In Proceedings of the Advances in Neural Information Processing Systems 30, NeurIPS. 2470\u20132478."},{"key":"e_1_3_2_19_2","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.1963.10500830"},{"key":"e_1_3_2_20_2","volume-title":"Proceedings of the 31st Advances in Neural Information Processing Systems, NeurIPS","author":"Huang Wen-bing","year":"2018","unstructured":"Wen-bing Huang, Tong Zhang, Yu Rong, and Junzhou Huang. 2018. Adaptive sampling towards fast graph representation learning. In Proceedings of the 31st Advances in Neural Information Processing Systems, NeurIPS."},{"key":"e_1_3_2_21_2","doi-asserted-by":"publisher","DOI":"10.5555\/795665.796533"},{"key":"e_1_3_2_22_2","volume-title":"Proceedings of the 5th 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. In Proceedings of the 5th International Conference on Learning Representations."},{"key":"e_1_3_2_23_2","first-page":"439","volume-title":"Proceedings of the 12th Annual Symposium on Discrete Algorithms","author":"Mishra Nina","year":"2001","unstructured":"Nina Mishra, Daniel Oblinger, and Leonard Pitt. 2001. Sublinear time approximate clustering. In Proceedings of the 12th Annual Symposium on Discrete Algorithms. SIAM, 439\u2013447."},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2008.81"},{"key":"e_1_3_2_25_2","doi-asserted-by":"publisher","DOI":"10.1145\/3292500.3330855"},{"key":"e_1_3_2_26_2","doi-asserted-by":"publisher","DOI":"10.5555\/1280283.1280327"},{"key":"e_1_3_2_27_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793255151"},{"key":"e_1_3_2_28_2","doi-asserted-by":"publisher","DOI":"10.1109\/TNN.2008.2005605"},{"key":"e_1_3_2_29_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-93417-4_38"},{"key":"e_1_3_2_30_2","doi-asserted-by":"publisher","DOI":"10.1109\/72.572108"},{"key":"e_1_3_2_31_2","first-page":"5998","volume-title":"Proceedings of the 30th Advances in Neural Information Processing Systems : Annual Conference on Neural Information Processing Systems 2017, NeurIPS","author":"Vaswani Ashish","year":"2017","unstructured":"Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. 2017. Attention is all you need. In Proceedings of the 30th Advances in Neural Information Processing Systems : Annual Conference on Neural Information Processing Systems 2017, NeurIPS. 5998\u20136008."},{"key":"e_1_3_2_32_2","volume-title":"Proceedings of the 6th International Conference on Learning Representations","author":"Veli\u010dkovi\u0107 Petar","year":"2018","unstructured":"Petar Veli\u010dkovi\u0107, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Li\u00f2, and Yoshua Bengio. 2018. Graph attention networks. In Proceedings of the 6th International Conference on Learning Representations."},{"key":"e_1_3_2_33_2","doi-asserted-by":"publisher","DOI":"10.1145\/3308558.3313417"},{"key":"e_1_3_2_34_2","doi-asserted-by":"publisher","DOI":"10.1145\/3292500.3330989"},{"key":"e_1_3_2_35_2","doi-asserted-by":"publisher","DOI":"10.1145\/3219819.3219890"},{"key":"e_1_3_2_36_2","doi-asserted-by":"publisher","DOI":"10.1145\/1536414.1536447"},{"key":"e_1_3_2_37_2","first-page":"3391","volume-title":"Proceedings of the 30th Advances in Neural Information Processing Systems, NeurIPS","author":"Zaheer Manzil","year":"2017","unstructured":"Manzil Zaheer, Satwik Kottur, Siamak Ravanbakhsh, Barnab\u00e1s P\u00f3czos, Ruslan Salakhutdinov, and Alexander J. Smola. 2017. Deep sets. In Proceedings of the 30th Advances in Neural Information Processing Systems, NeurIPS. 3391\u20133401."},{"key":"e_1_3_2_38_2","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v32i1.11782"},{"key":"e_1_3_2_39_2","first-page":"11247","volume-title":"Proceedings of the 32nd Advances in Neural Information Processing Systems, NeurIPS","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 Proceedings of the 32nd Advances in Neural Information Processing Systems, NeurIPS. 11247\u201311256."}],"container-title":["ACM Transactions on Knowledge Discovery from Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3502733","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3502733","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T18:09:47Z","timestamp":1750183787000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3502733"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,3,9]]},"references-count":38,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2022,10,31]]}},"alternative-id":["10.1145\/3502733"],"URL":"https:\/\/doi.org\/10.1145\/3502733","relation":{},"ISSN":["1556-4681","1556-472X"],"issn-type":[{"value":"1556-4681","type":"print"},{"value":"1556-472X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,3,9]]},"assertion":[{"value":"2021-03-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-11-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-03-09","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}