{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T05:05:34Z","timestamp":1750309534269,"version":"3.41.0"},"reference-count":31,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2025,3,21]],"date-time":"2025-03-21T00:00:00Z","timestamp":1742515200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"Schweitzer Engineering Laboratories and by the National Science Foundation","award":["2126449"],"award-info":[{"award-number":["2126449"]}]},{"name":"U.S. Department of Energy through the Exascale Computing","award":["17-SC-20-SC"],"award-info":[{"award-number":["17-SC-20-SC"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Archit. Code Optim."],"published-print":{"date-parts":[[2025,3,31]]},"abstract":"<jats:p>\n            The\n            <jats:italic>k<\/jats:italic>\n            -dimensional Weisfeiler-Lehman (\n            <jats:italic>k<\/jats:italic>\n            -WL) algorithm\u2014developed as an efficient heuristic for testing if two graphs are isomorphic\u2014is a fundamental kernel for node embedding in the emerging field of graph neural networks. Unfortunately, the\n            <jats:italic>k<\/jats:italic>\n            -WL algorithm has exponential storage requirements, limiting the size of graphs that can be handled. This work presents a novel\n            <jats:italic>k<\/jats:italic>\n            -WL scheme with a storage requirement orders of magnitude lower while maintaining the same accuracy as the original\n            <jats:italic>k<\/jats:italic>\n            -WL algorithm. Due to the reduced storage requirement, our scheme allows for processing much bigger graphs than previously possible on a single compute node. For even bigger graphs, we provide the first distributed-memory implementation. Our\n            <jats:italic>k<\/jats:italic>\n            -WL scheme also has significantly reduced communication volume and offers high scalability. Our experimental results demonstrate that our approach is significantly faster and has superior scalability compared to five other implementations employing state-of-the-art techniques.\n          <\/jats:p>","DOI":"10.1145\/3715124","type":"journal-article","created":{"date-parts":[[2025,2,10]],"date-time":"2025-02-10T16:09:29Z","timestamp":1739203769000},"page":"1-25","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["ScaWL: Scaling k-WL (Weisfeiler-Lehman) Algorithms in Memory and Performance on Shared and Distributed-Memory Systems"],"prefix":"10.1145","volume":"22","author":[{"ORCID":"https:\/\/orcid.org\/0009-0007-7206-0976","authenticated-orcid":false,"given":"Coby","family":"Soss","sequence":"first","affiliation":[{"name":"Washington State University, Pullman, United States and Schweitzer Engineering Laboratories Inc, Pullman, United States"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4062-0293","authenticated-orcid":false,"given":"Aravind","family":"Sukumaran Rajam","sequence":"additional","affiliation":[{"name":"Meta, Menlo Park, United States"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9533-5599","authenticated-orcid":false,"given":"Janet","family":"Layne","sequence":"additional","affiliation":[{"name":"Boise State University, Boise, United States"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0689-5063","authenticated-orcid":false,"given":"Edoardo","family":"Serra","sequence":"additional","affiliation":[{"name":"Boise State University, Boise, United States"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2323-4753","authenticated-orcid":false,"given":"Mahantesh","family":"Halappanavar","sequence":"additional","affiliation":[{"name":"Data Sciences and Machine Intelligence, Pacific Northwest National Laboratory, Richland, United States"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5383-8032","authenticated-orcid":false,"given":"Assefaw H.","family":"Gebremedhin","sequence":"additional","affiliation":[{"name":"Washington State University, Pullman, United States"}]}],"member":"320","published-online":{"date-parts":[[2025,3,21]]},"reference":[{"key":"e_1_3_1_2_2","volume-title":"Data-centric Machine Learning Research (DMLR) Workshop at ICML 2023, Honolulu, Hawaii","author":"Akbiyik Eren","year":"2023","unstructured":"Eren Akbiyik, Florian Gr\u00f6tschla, B\u00e9ni Egressy, and Roger Wattenhofer. 2023. Graphtester: Exploring theoretical boundaries of GNNs on graph datasets. In Data-centric Machine Learning Research (DMLR) Workshop at ICML 2023, Honolulu, Hawaii."},{"doi-asserted-by":"publisher","key":"e_1_3_1_3_2","DOI":"10.1017\/S0962492914000038"},{"key":"e_1_3_1_4_2","article-title":"Weisfeiler and Lehman go topological: Message passing simplicial networks","volume":"2103","author":"Bodnar Cristian","year":"2021","unstructured":"Cristian Bodnar, Fabrizio Frasca, Yu Guang Wang, Nina Otter, Guido Mont\u00fafar, Pietro Li\u00f2, and Michael M. Bronstein. 2021. Weisfeiler and Lehman go topological: Message passing simplicial networks. CoRR abs\/2103.03212 (2021). arXiv:2103.03212https:\/\/arxiv.org\/abs\/2103.03212","journal-title":"CoRR"},{"doi-asserted-by":"publisher","unstructured":"Gian Maria Campedelli Janet Layne Jack Herzoff and Edoardo Serra. 2021. The geometrical shapes of violence: Predicting and explaining terrorist operations through graph embeddings. 10 (Mar.2021). DOI:10.1093\/comnet\/cnac008","key":"e_1_3_1_5_2","DOI":"10.1093\/comnet\/cnac008"},{"key":"e_1_3_1_6_2","article-title":"A novel higher-order Weisfeiler-Lehman graph convolution","volume":"2007","author":"Damke Clemens","year":"2020","unstructured":"Clemens Damke, Vitalik Melnikov, and Eyke H\u00fcllermeier. 2020. A novel higher-order Weisfeiler-Lehman graph convolution. CoRR abs\/2007.00346 (2020). arXiv:2007.00346https:\/\/arxiv.org\/abs\/2007.00346","journal-title":"CoRR"},{"doi-asserted-by":"publisher","key":"e_1_3_1_7_2","DOI":"10.1145\/2049662.2049663"},{"doi-asserted-by":"publisher","key":"e_1_3_1_8_2","DOI":"10.1109\/IPDPS.2008.4536305"},{"key":"e_1_3_1_9_2","doi-asserted-by":"crossref","first-page":"322","DOI":"10.1007\/3-540-48224-5_27","volume-title":"Automata, Languages and Programming","author":"F\u00fcrer Martin","year":"2001","unstructured":"Martin F\u00fcrer. 2001. Weisfeiler-Lehman refinement requires at least a linear number of iterations. In Automata, Languages and Programming, Fernando Orejas, Paul G. Spirakis, and Jan van Leeuwen (Eds.). Springer Berlin, Berlin, 322\u2013333."},{"doi-asserted-by":"publisher","key":"e_1_3_1_10_2","DOI":"10.1145\/3372123"},{"unstructured":"William L. Hamilton Rex Ying and Jure Leskovec. 2017. Representation learning on graphs: Methods and applications. http:\/\/arxiv.org\/abs\/1709.05584","key":"e_1_3_1_11_2"},{"doi-asserted-by":"publisher","key":"e_1_3_1_12_2","DOI":"10.1145\/800076.802486"},{"doi-asserted-by":"publisher","key":"e_1_3_1_13_2","DOI":"10.1145\/3450315"},{"doi-asserted-by":"publisher","key":"e_1_3_1_14_2","DOI":"10.1007\/s10618-022-00880-x"},{"key":"e_1_3_1_15_2","article-title":"Paper Implementations","author":"Junior Tiago Toledo","year":"2022","unstructured":"Tiago Toledo Junior. 2022. Paper Implementations. https:\/\/github.com\/TNanukem\/paper_implementations","journal-title":"https:\/\/github.com\/TNanukem\/paper_implementations"},{"key":"e_1_3_1_16_2","article-title":"Walk refinement, walk logic, and the iteration number of the Weisfeiler-Leman algorithm","volume":"1905","author":"Lichter Moritz","year":"2019","unstructured":"Moritz Lichter, Ilia Ponomarenko, and Pascal Schweitzer. 2019. Walk refinement, walk logic, and the iteration number of the Weisfeiler-Leman algorithm. CoRR abs\/1905.03008 (2019). arXiv:1905.03008http:\/\/arxiv.org\/abs\/1905.03008","journal-title":"CoRR"},{"key":"e_1_3_1_17_2","article-title":"Provably powerful graph networks","volume":"1905","author":"Maron Haggai","year":"2019","unstructured":"Haggai Maron, Heli Ben-Hamu, Hadar Serviansky, and Yaron Lipman. 2019. Provably powerful graph networks. CoRR abs\/1905.11136 (2019). arXiv:1905.11136http:\/\/arxiv.org\/abs\/1905.11136","journal-title":"CoRR"},{"key":"e_1_3_1_18_2","article-title":"The power of the Weisfeiler-Leman algorithm for machine learning with graphs","volume":"2105","author":"Morris Christopher","year":"2021","unstructured":"Christopher Morris, Matthias Fey, and Nils M. Kriege. 2021. The power of the Weisfeiler-Leman algorithm for machine learning with graphs. CoRR abs\/2105.05911 (2021). arXiv:2105.05911https:\/\/arxiv.org\/abs\/2105.05911","journal-title":"CoRR"},{"key":"e_1_3_1_19_2","volume-title":"IEEE International Conference on Data Mining (ICDM), 2017","author":"Morris Christopher","year":"2017","unstructured":"Christopher Morris, Kristian Kersting, and Petra Mutzel. 2017. Glocalized Weisfeiler-Lehman graph kernels: Global-local feature maps of graphs. In IEEE International Conference on Data Mining (ICDM), 2017."},{"unstructured":"Christopher Morris Gaurav Rattan and Petra Mutzel. 2020. Weisfeiler and Leman go sparse: Towards scalable higher-order graph embeddings. arxiv:1904.01543 [cs.DS] https:\/\/arxiv.org\/abs\/1904.01543","key":"e_1_3_1_20_2"},{"key":"e_1_3_1_21_2","article-title":"Weisfeiler and Leman go neural: Higher-order graph neural networks","volume":"1810","author":"Morris Christopher","year":"2018","unstructured":"Christopher Morris, Martin Ritzert, Matthias Fey, William L. Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe. 2018. Weisfeiler and Leman go neural: Higher-order graph neural networks. CoRR abs\/1810.02244 (2018). arXiv:1810.02244http:\/\/arxiv.org\/abs\/1810.02244","journal-title":"CoRR"},{"key":"e_1_3_1_22_2","article-title":"A survey on the expressive power of graph neural networks","volume":"2003","author":"Sato Ryoma","year":"2020","unstructured":"Ryoma Sato. 2020. A survey on the expressive power of graph neural networks. CoRR abs\/2003.04078 (2020). arXiv:2003.04078https:\/\/arxiv.org\/abs\/2003.04078","journal-title":"CoRR"},{"doi-asserted-by":"publisher","key":"e_1_3_1_23_2","DOI":"10.1137\/1.9781611976700.38"},{"key":"e_1_3_1_24_2","article-title":"K-FWL","author":"Serra Edoardo","year":"2024","unstructured":"Edoardo Serra. 2024. K-FWL. https:\/\/github.com\/edoardoserra\/K--F-WL-","journal-title":"https:\/\/github.com\/edoardoserra\/K--F-WL-"},{"doi-asserted-by":"publisher","key":"e_1_3_1_25_2","DOI":"10.1109\/BigData50022.2020.9377854"},{"issue":"77","key":"e_1_3_1_26_2","first-page":"2539","article-title":"Weisfeiler-Lehman graph kernels","volume":"12","author":"Shervashidze Nino","year":"2011","unstructured":"Nino Shervashidze, Pascal Schweitzer, Erik Jan van Leeuwen, Kurt Mehlhorn, and Karsten M. Borgwardt. 2011. Weisfeiler-Lehman graph kernels. Journal of Machine Learning Research 12, 77 (2011), 2539\u20132561. http:\/\/jmlr.org\/papers\/v12\/shervashidze11a.html","journal-title":"Journal of Machine Learning Research"},{"issue":"77","key":"e_1_3_1_27_2","first-page":"2539","article-title":"Weisfeiler-Lehman graph kernels","volume":"12","author":"Shervashidze Nino","year":"2011","unstructured":"Nino Shervashidze, Pascal Schweitzer, Erik Jan van Leeuwen, Kurt Mehlhorn, and Karsten M. Borgwardt. 2011. Weisfeiler-Lehman graph kernels. Journal of Machine Learning Research 12, 77 (2011), 2539\u20132561. http:\/\/jmlr.org\/papers\/v12\/shervashidze11a.html","journal-title":"Journal of Machine Learning Research"},{"issue":"9","key":"e_1_3_1_28_2","first-page":"12","article-title":"The reduction of a graph to canonical form and the algebra which appears therein","volume":"2","author":"Weisfeiler B.","year":"1968","unstructured":"B. Weisfeiler and A. A. Lehman. 1968. The reduction of a graph to canonical form and the algebra which appears therein. Nauchno-Technicheskaya Informatsia 2, 9 (1968), 12\u201316.","journal-title":"Nauchno-Technicheskaya Informatsia"},{"key":"e_1_3_1_29_2","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?. In International Conference on Learning Representations. https:\/\/openreview.net\/forum?id=ryGs6iA5Km"},{"unstructured":"Zuoyu Yan Tengfei Ma Liangcai Gao Zhi Tang Chao Chen and Yusu Wang. 2023. Cycle invariant positional encoding for graph representation learning. arxiv:2311.14333 [cs.LG] https:\/\/arxiv.org\/abs\/2311.14333","key":"e_1_3_1_30_2"},{"key":"e_1_3_1_31_2","article-title":"The expressive power of graph neural networks: A survey","volume":"2308","author":"Zhang Bingxue","year":"2023","unstructured":"Bingxue Zhang, Changjun Fan, Shixuan Liu, Kuihua Huang, Xiang Zhao, Jin-Yu Huang, and Zhong Liu. 2023. The expressive power of graph neural networks: A survey. ArXiv abs\/2308.08235 (2023). https:\/\/api.semanticscholar.org\/CorpusID:260925813","journal-title":"ArXiv"},{"unstructured":"Bohang Zhang Jingchu Gai Yiheng Du Qiwei Ye Di He and Liwei Wang. 2024. Beyond Weisfeiler-Lehman: A quantitative framework for GNN expressiveness. arxiv:2401.08514 [cs.LG] https:\/\/arxiv.org\/abs\/2401.08514","key":"e_1_3_1_32_2"}],"container-title":["ACM Transactions on Architecture and Code Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3715124","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3715124","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T01:18:18Z","timestamp":1750295898000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3715124"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,3,21]]},"references-count":31,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2025,3,31]]}},"alternative-id":["10.1145\/3715124"],"URL":"https:\/\/doi.org\/10.1145\/3715124","relation":{},"ISSN":["1544-3566","1544-3973"],"issn-type":[{"type":"print","value":"1544-3566"},{"type":"electronic","value":"1544-3973"}],"subject":[],"published":{"date-parts":[[2025,3,21]]},"assertion":[{"value":"2024-05-25","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-12-29","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-03-21","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}