ROS: A GNN-based Relax-Optimize-and-Sample Framework for Max-$k$-Cut Problems
Authors: Yeqing Qiu, Ye Xue, Akang Wang, Yiheng Wang, Qingjiang Shi, Zhi-Quan Luo
ICML 2025 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | Extensive experimental results on random regular graphs, the Gset benchmark, and the real-world datasets demonstrate that the proposed ROS framework effectively scales to large instances with up to 20, 000 nodes in just a few seconds, outperforming state-of-the-art algorithms. Furthermore, ROS exhibits strong generalization capabilities across both in-distribution and out-of-distribution instances, underscoring its effectiveness for large-scale optimization tasks. |
| Researcher Affiliation | Academia | 1 Shenzhen Research Institute of Big Data, Shenzhen, China. 2 The Chinese University of Hong Kong, Shenzhen, China. 3 Tongji University, Shanghai, China. Correspondence to: Ye Xue <EMAIL>. |
| Pseudocode | Yes | Algorithm 1 Random Sampling |
| Open Source Code | Yes | The source code is available at https://github.com/Net Sys Opt/ROS. |
| Open Datasets | Yes | Datasets. We conduct experiments on the following datasets. r-Random regular graphs (Schuetz et al., 2022): Each node has the same degree r. Edge weights are either 0 or 1. Gset (Ye, 2003): A well-known Max-k-Cut benchmark comprising toroidal, planar, and random graphs with 800 20,000 nodes and edge densities between 2% and 6%. Edge weights are either 0 or 1. COLOR (Micheal, 2002): A collection of dense graphs derived from literary texts, where nodes represent characters and edges indicate co-occurrence. These graphs have large chromatic numbers (χ 10), making them suitable for Max-k-Cut. Edge weights are either 0 or 1. Bitcoin-OTC (Kumar et al., 2016): A real-world signed network with 5, 881 nodes and 35, 592 edges, weighted from 10 to 10, capturing trust relationships among Bitcoin users. ... Micheal, T. The color datasets. https://mat.tepper.cmu.edu/COLOR02/, 2002. |
| Dataset Splits | Yes | The construction of the training and testing datasets is summarized in Table 1. The training set consists of 500 3-regular, 500 5-regular graphs, and 500 7-regular graphs with 100 nodes each, corresponding to the cases k = 2, k = 3, and k = 10 respectively. The test set of random regular graphs includes 20 3-regular and 20 5-regular graphs for each k {2, 3}, with node counts of 100, 1,000, and 10,000. |
| Hardware Specification | Yes | Evaluation Configuration. All our experiments were conducted on an NVIDIA RTX 3090 GPU, using PyTorch 2.2.0. |
| Software Dependencies | Yes | Evaluation Configuration. All our experiments were conducted on an NVIDIA RTX 3090 GPU, using PyTorch 2.2.0. |
| Experiment Setup | Yes | Model Settings. ROS is designed as a two-layer GNN, with both the input and hidden dimensions set to 100. To address the issue of gradient vanishing, we apply graph normalization as proposed by Cai et al. (2021). The ROS model is pre-training using Adam with a learning rate of 10 2 for one epoch. During fine-tuning, the model is further optimized using the same Adam optimizer and learning rate, applying early stopping with a tolerance of 10 2 and patience of 100 iterations. Training terminates if no improvement is observed. Finally, in the random sampling stage, we execute Algorithm 1 for T = 100 trials and return the best solution. |