{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,7]],"date-time":"2026-08-07T16:39:23Z","timestamp":1786120763692,"version":"build-2736575974"},"publisher-location":"New York, NY, USA","reference-count":37,"publisher":"ACM","license":[{"start":{"date-parts":[[2026,8,8]],"date-time":"2026-08-08T00:00:00Z","timestamp":1786147200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/legalcode"}],"funder":[{"name":"National Natural Science Foundation of China","award":["62172107"],"award-info":[{"award-number":["62172107"]}]},{"name":"National Key Research and Development Program of China","award":["2018YFB0505000"],"award-info":[{"award-number":["2018YFB0505000"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2026,8,9]]},"DOI":"10.1145\/3770855.3818103","type":"proceedings-article","created":{"date-parts":[[2026,8,6]],"date-time":"2026-08-06T17:15:47Z","timestamp":1786036547000},"page":"2122-2131","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["RIDGECUT: Learning Graph Partitioning with Rings and Wedges"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1636-8825","authenticated-orcid":false,"given":"Qize","family":"Jiang","sequence":"first","affiliation":[{"name":"College of Computer Science and Artificial Intelligence, Shanghai Key Laboratory of Data Science, Fudan University, Shanghai, China and Shanghai Institute of Intelligent Electronics & Systems, Shanghai, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0002-1865-7337","authenticated-orcid":false,"given":"Angelo","family":"Zangari","sequence":"additional","affiliation":[{"name":"University of Illinois Chicago, Chicago, Illinois, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4784-9795","authenticated-orcid":false,"given":"Linsey","family":"Pang","sequence":"additional","affiliation":[{"name":"PayPal Inc., San Jose, California, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5692-3996","authenticated-orcid":false,"given":"Alice","family":"Gatti","sequence":"additional","affiliation":[{"name":"Center for AI Safety, San Francisco, California, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3552-9233","authenticated-orcid":false,"given":"Mahima","family":"Aggarwal","sequence":"additional","affiliation":[{"name":"Qatar Computing Research Institute, Hamad Bin Khalifa University, Doha, Qatar"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0000-0406-3525","authenticated-orcid":false,"given":"Giovanna","family":"Vantini","sequence":"additional","affiliation":[{"name":"Qatar Computing Research Institute, Hamad Bin Khalifa University, Doha, Qatar"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1261-2496","authenticated-orcid":false,"given":"Xiaosong","family":"Ma","sequence":"additional","affiliation":[{"name":"Computing and Mathematical Sciences (CMS) Division, Mohamed bin Zayed University of Artificial Intelligence (MBZUAI), Abu Dhabi, United Arab Emirates"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9483-4599","authenticated-orcid":false,"given":"Weiwei","family":"Sun","sequence":"additional","affiliation":[{"name":"College of Computer Science and Artificial Intelligence, Shanghai Key Laboratory of Data Science, Fudan University, Shanghai, China and Shanghai Institute of Intelligent Electronics & Systems, Shanghai, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0996-2807","authenticated-orcid":false,"given":"Sourav","family":"Medya","sequence":"additional","affiliation":[{"name":"University of Illinois Chicago, Chicago, Illinois, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8102-2572","authenticated-orcid":false,"given":"Sanjay","family":"Chawla","sequence":"additional","affiliation":[{"name":"Qatar Computing Research Institute, Hamad Bin Khalifa University, Doha, Qatar"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2026,8,8]]},"reference":[{"key":"e_1_3_2_1_1_1","volume-title":"The Tenth International Conference on Learning Representations, ICLR","author":"Brody Shaked","year":"2022","unstructured":"Shaked Brody, Uri Alon, and Eran Yahav. 2022. How Attentive are Graph Attention Networks?. In The Tenth International Conference on Learning Representations, ICLR 2022. OpenReview.net."},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-49487-6_4"},{"key":"e_1_3_2_1_3_1","volume-title":"CBMS Regional Conference Series in Mathematics.","author":"Chung Fan R. K.","year":"1997","unstructured":"Fan R. K. Chung. 1997. Spectral Graph Theory. Vol. V92. CBMS Regional Conference Series in Mathematics."},{"key":"e_1_3_2_1_4_1","volume-title":"V26, 12","author":"Diekmann Ralf","year":"2000","unstructured":"Ralf Diekmann, Robert Preis, Frank Schlimbach, and Chris Walshaw. 2000. Shape-Optimized Mesh Partitioning and Load Balancing for Parallel Adaptive FEM. Parallel Comput., V26, 12 (2000), 1555-1581."},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","unstructured":"W. E. Donath and A. J. Hoffman. 1973. Lower Bounds for the Partitioning of Graphs. IBM Journal of Research and Development V17 5 (1973) 420-425. doi:10.1147\/rd.175.0420","DOI":"10.1147\/rd.175.0420"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-981-15-4095-0"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01581107"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"crossref","unstructured":"Alice Gatti Zhixiong Hu Tess Smidt Esmond G. Ng and Pieter Ghysels. 2022a. Deep Learning and Spectral Embedding for Graph Partitioning. 25-36.","DOI":"10.1137\/1.9781611977141.3"},{"key":"e_1_3_2_1_9_1","first-page":"1","article-title":"Graph Partitioning and Sparse Matrix Ordering using Reinforcement Learning and Graph Neural Networks","volume":"23","author":"Gatti Alice","year":"2022","unstructured":"Alice Gatti, Zhixiong Hu, Tess Smidt, Esmond G. Ng, and Pieter Ghysels. 2022b. Graph Partitioning and Sparse Matrix Ordering using Reinforcement Learning and Graph Neural Networks. Journal of Machine Learning Research, V23, 303 (2022), 1-28.","journal-title":"Journal of Machine Learning Research"},{"key":"e_1_3_2_1_10_1","volume-title":"Liu","author":"George Alan","year":"1981","unstructured":"Alan George and Joseph W. Liu. 1981. Computer Solution of Large Sparse Positive Definite. Prentice Hall Professional Technical Reference."},{"key":"e_1_3_2_1_11_1","unstructured":"Nathan Grinsztajn. 2023. Reinforcement learning for combinatorial optimization: leveraging uncertainty structure and priors. Ph.D. Dissertation. Universit\u00e9 de Lille."},{"key":"e_1_3_2_1_12_1","volume-title":"First conference on language modeling.","author":"Gu Albert","year":"2024","unstructured":"Albert Gu and Tri Dao. 2024. Mamba: Linear-time sequence modeling with selective state spaces. In First conference on language modeling."},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-011-0503-x"},{"key":"e_1_3_2_1_14_1","volume-title":"Rivest","author":"Hyafil Laurent","year":"1973","unstructured":"Laurent Hyafil and Ronald L. Rivest. 1973. Graph Partitioning and Constructing Optimal Decision Trees are Polynomial Complete Problems. Technical Report Rapport de Recherche no. 33. IRIA - Laboratoire de Recherche en Informatique et Automatique."},{"key":"e_1_3_2_1_15_1","volume-title":"Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020","author":"Karalias Nikolaos","year":"2020","unstructured":"Nikolaos Karalias and Andreas Loukas. 2020. Erdos Goes Neural: an Unsupervised Learning Framework for Combinatorial Optimization on Graphs. In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020."},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/266021.266273"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/92.748202"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/369028.369103"},{"key":"e_1_3_2_1_19_1","volume-title":"METIS: A software package for partitioning unstructured graphs, partitioning meshes, and computing fill-reducing orderings of sparse matrices","author":"Karypis George","year":"1997","unstructured":"George Karypis and Vipin Kumar. 1997. METIS: A software package for partitioning unstructured graphs, partitioning meshes, and computing fill-reducing orderings of sparse matrices. University of Minnesota, Department of Computer Science and Engineering, Army HPC Research Center, Minneapolis, MN (1997)."},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1137\/S1064827595287997"},{"key":"e_1_3_2_1_21_1","volume-title":"METIS: Family of Graph and Hypergraph Partitioning Software","author":"Karypis George","year":"2023","unstructured":"George Karypis and Vipin Kumar. 2023. METIS: Family of Graph and Hypergraph Partitioning Software. http:\/\/glaros.dtc.umn.edu\/gkhome\/views\/metis. Accessed: 2023-01-30."},{"key":"e_1_3_2_1_22_1","volume-title":"ParMETIS: Parallel Graph Partitioning and Fill-reducing Matrix Ordering","author":"Karypis George","unstructured":"George Karypis, Kirk Schloegel, and Vipin Kumar. 2023. ParMETIS: Parallel Graph Partitioning and Fill-reducing Matrix Ordering. http:\/\/glaros.dtc.umn.edu\/gkhome\/metis\/parmetis\/overview. Accessed: 2023-01-30."},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1002\/j.1538-7305.1970.tb01770.x"},{"key":"e_1_3_2_1_24_1","volume-title":"Semi-Supervised Classification with Graph Convolutional Networks. In 5th International Conference on Learning Representations, ICLR","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, ICLR 2017. OpenReview.net."},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICTAI.2019.00125"},{"key":"e_1_3_2_1_26_1","volume-title":"V134","author":"Mazyavkina Nina","year":"2021","unstructured":"Nina Mazyavkina, Sergey Sviridov, Sergei Ivanov, and Evgeny Burnaev. 2021. Reinforcement learning for combinatorial optimization: A survey. Computers & Operations Research, V134 (2021), 105400."},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2009.04.005"},{"key":"e_1_3_2_1_28_1","first-page":"849","volume-title":"NIPS","author":"Ng Andrew Y.","year":"2001","unstructured":"Andrew Y. Ng, Michael I. Jordan, and Yair Weiss. 2001. On Spectral Clustering: Analysis and an algorithm. In Advances in Neural Information Processing Systems 14 [Neural Information Processing Systems: Natural and Synthetic, NIPS 2001, Thomas G. Dietterich, Suzanna Becker, and Zoubin Ghahramani (Eds.). MIT Press, 849-856."},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-74466-5_22"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-61142-8_588"},{"key":"e_1_3_2_1_31_1","first-page":"4731","volume-title":"The Thirty-Third AAAI Conference on Artificial Intelligence, AAAI","author":"Prates Marcelo O. R.","year":"2019","unstructured":"Marcelo O. R. Prates, Pedro H. C. Avelar, Henrique Lemos, Lu\u00eds C. Lamb, and Moshe Y. Vardi. 2019. Learning to Solve NP-Complete Problems: A Graph Neural Network for Decision TSP. In The Thirty-Third AAAI Conference on Artificial Intelligence, AAAI 2019. AAAI Press, 4731-4738."},{"key":"e_1_3_2_1_32_1","first-page":"469","volume-title":"Saarbr\u00fccken","author":"Sanders Peter","year":"2011","unstructured":"Peter Sanders and Christian Schulz. 2011. Engineering multilevel graph partitioning algorithms. In Algorithms-ESA 2011: 19th Annual European Symposium, Saarbr\u00fccken, Germany, September 5-9, 2011. Proceedings 19. Springer, 469-480."},{"key":"e_1_3_2_1_33_1","volume-title":"Proximal policy optimization algorithms. arXiv preprint arXiv:1707.06347","author":"Schulman John","year":"2017","unstructured":"John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. 2017. Proximal policy optimization algorithms. arXiv preprint arXiv:1707.06347 (2017)."},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/3637528.3671815"},{"key":"e_1_3_2_1_35_1","volume-title":"Graph Attention Networks. In 6th International Conference on Learning Representations, ICLR","author":"Velickovic Petar","year":"2018","unstructured":"Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Li\u00f2, and Yoshua Bengio. 2018. Graph Attention Networks. In 6th International Conference on Learning Representations, ICLR 2018. OpenReview.net."},{"key":"e_1_3_2_1_36_1","volume-title":"V233","author":"Wang Qi","year":"2021","unstructured":"Qi Wang and Chunlei Tang. 2021. Deep reinforcement learning for transportation network combinatorial optimization: A survey. Knowledge-Based Systems, V233 (2021), 107526."},{"key":"e_1_3_2_1_37_1","volume-title":"V32","author":"Wilder Bryan","year":"2019","unstructured":"Bryan Wilder, Eric Ewing, Bistra Dilkina, and Milind Tambe. 2019. End to end learning and optimization on graphs. Advances in Neural Information Processing Systems, V32 (2019). new"}],"event":{"name":"KDD '26: The 32nd ACM SIGKDD Conference on Knowledge Discovery and Data Mining","location":"Jeju Island Republic of Korea","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 32nd ACM SIGKDD Conference on Knowledge Discovery and Data Mining V.2"],"original-title":[],"deposited":{"date-parts":[[2026,8,7]],"date-time":"2026-08-07T01:30:43Z","timestamp":1786066243000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3770855.3818103"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,8,8]]},"references-count":37,"alternative-id":["10.1145\/3770855.3818103","10.1145\/3770855"],"URL":"https:\/\/doi.org\/10.1145\/3770855.3818103","relation":{},"subject":[],"published":{"date-parts":[[2026,8,8]]},"assertion":[{"value":"2026-08-08","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}