ROS: A GNN-based Relax-Optimize-and-Sample Framework for Max-$k$-Cut Problems

Claims And Evidence

Response to C1: Theorem 3.2 requires a global optimum, which is why we introduce Theorem 3.3. It theoretically establishes the expected equivalence between relaxed and integer solutions for all feasible points, not just the global optimum. Our sampling algorithm and experiments rely on Theorem 3.3, ensuring practical relevance. Moreover, to stress your concern, we add one row for the continuous objective function in Tables 10 and 12 in the ablation study (updated in Tables 1 and 2 in anonymous link), explicitly comparing the continuous objcetive values and their integer counterparts.

Methods And Evaluation Criteria

Response to M1: See "Response to Q1" for Reviewer zJRf.

Experimental Designs Or Analyses

Response to E1: Since ROS is unsupervised, we only generate graphs, not ground truth. As stated in Section 4.1, the training dataset consists of 500 regular graphs, which can be generated within 1 second. The pre-training process runs for only one epoch, requiring just 8.75 seconds in total in our device. In contrast, other L2O baselines, such as ECO-DQN and ANYCSP, demand significantly longer training times, ranging from several hours to multiple days. This highlights the efficiency of ROS in both dataset preparation and model training.

Response to E2: We evaluate ROS for larger $k$ (specifically, $k=10$) in our experiments on the real-world Bitcoin-OTC dataset. The corresponding results are provided in Table 1 in "Response to R1" for Reviewer bfPu.

Response to E3: We selected the [0.9, 1.1] perturbation range to highlight that ANYCSP struggles even with minimal weight variations, while ROS remains robust across different weight settings in the Max-$k$-Cut problem. To further address your concern, we conduct additional experiments with larger perturbation scales ([0,10] and [0,100]) on the weighted Gset benchmark. The results in Tables 3–6 in anonymous link show that:

• ROS consistently achieves the best performance in terms of both solution quality and computational efficiency.
• Even under extreme perturbations, ROS maintains its advantage over baselines, demonstrating its robustness in handling arbitrary edge weights.

Relation To Broader Scientific Literature and Essential References Not Discussed

While [1] also derives relaxation-based approaches and sampling methods on discrete Bayesian optimization, our sampling step is theoretically derived rather than borrowed directly from prior work. Theorem 3.2 establishes the relationship between continuous and discrete solutions at global optimal, which leads to our sampling strategy designing and analysis: each feasible continuous solution defines a categorical distribution over discrete assignments, and sampling from it preserves the expected objective value (Theorem 3.3). This makes relaxation and sampling inherently connected rather than an arbitrary choice. We acknowledge similar ideas in other fields and will expand the discussion in our paper.

Weakness

As shown in Table 3 of the manuscript and Tables 3–6 in anonymous link, ROS consistently produces the highest-quality solutions while maintaining the fastest computational time in the weighted experiments. Additionally, results on the real-world Bitcoin-OTC dataset (Table 1, response to Reviewer bfPu) demonstrate that ROS effectively handles practical problems, confirming its applicability on weighted Max-$k$-Cut beyond synthetic benchmarks.

Other Comments Or Suggestions

Response to C1: We clarify that the correct selection criterion is to choose the solution with the lowest objective value of $f(X)$, as defined in Problem $(P)$ (right column in Line 131), where $f(X)=Tr(XWX^T)$. This corresponds to the highest objective value of the original optimization problem in Equation (1) due to a constant shift and sign inversion. We will revise the manuscript to explicitly state this selection criterion to avoid confusion.

Response to C2: We will replace the order of two literatures.

Questions for Authors

• We have added extensive experiments, including tests on real-world weighted Max-$k$-Cut instances and perturbation studies across different ranges. These results, detailed in Table 1 in response to Reviewer bfPu and Tables 3–6 (anonymous link), further highlight the importance of ROS.
• Regarding the theoretical contribution, ROS is not a direct adaptation from other fields; its components are tightly integrated. The relaxation and sampling steps ensure consistency between the relaxed and discrete solutions, while the powerful GNN effectively bridges the optimization gap. This demonstrates a strong alignment between theory and practical performance.

Reference

[1] Michael R, et al. A Continuous Relaxation for Discrete Bayesian Optimization[J].

Claims And Evidence

Response to C1: Please refer to "Response to W2" for Reviewer bfPu.

Methods And Evaluation Criteria

Response to M1:

• NeuroCUT [1] is a reinforcement learning-based partitioning method, while DGCLUSTER [2] and DMoN [3] employ graph neural networks to optimize clustering objectives. However, these methods are designed for graph clustering, which aims to minimize inter-cluster connections, whereas Max-$k$-Cut seeks to maximize inter-partition connections. As a result, they are not directly applicable to our problem. Additionally, while NeuroCUT claims to support arbitrary objective functions, its node selection heuristics are only tailored for graph clustering, making it unsuitable for Max-$k$-Cut.
• Despite these differences, we evaluated NeuroCUT as a representative baseline of graph clustering. We trained it on 500 3-regular graphs as ROS and tested it on Bitcoin-OTC, a real-world signed network with 5,881 nodes and 35,592 weighted edges (ranging from -10 to 10), which captures trust relationships among Bitcoin traders. The results is shown in "Response to R1" for Reviewer bfPu, ROS significantly outperforms NeuroCUT and other baselines, further demonstrating its effectiveness for Max-$k$-Cut.

Response to M2: We include a real-world dataset, Bitcoin-OTC, in our evaluation, which contains 5,881 nodes and 35,592 weighted edges. The comparison results with baselines on this dataset are presented in "Response to R1" for Reviewer bfPu.

Response to M3: Please refer to the "response to W1" of reviewer bfPu for details regarding the generalizability of our method to unseen $k$.

Experimental Designs Or Analysis:

Figure 2 represents the fine-tuning time for ROS. ROS does not require ground-truth generation, unlike supervised methods. Pre-training for a specific $k$ is lightweight—training on 500 regular graphs for one epoch takes only 8.75 seconds, whereas L2O baselines like ECO-DQN and ANYCSP require hours or even days. The scalability of fine-tuning (inference) time is detailed in Table 1 of the manuscript, and ROS efficiently scales to instances of large $N$.

Essential References Not Discussed

Please see the response to M1.

Weakness

Response to W1: Please see "Response to W2" for Reviewer bfPu.

Response to W2: As stated in Section 4.1, the training dataset consists of 500 regular graphs, and the pre-training process runs for only one epoch, requiring just 8.75 seconds in total. In contrast, L2O baselines like ECO-DQN and ANYCSP require significantly longer training times, ranging from several hours to multiple days. This highlights the efficiency of ROS. The fine-tuning (inference) time is already reported in Section 4.

Response to W3: Please refer to the "response to W1" for reviewer bfPu regarding the generalizability of our method to unseen $k$.

Response to W4: Please see Response to M2.

Response to W5: Please see Response to M1.

Response to W6: We upload our code in https://anonymous.4open.science/r/ROS_anonymous-1C88/.

Other Comments Or Suggestions

Since fine-tuning directly solves test instances, we cannot remove this stage. However, to enhance readability, we now include results for ROS-vanilla (i.e., ROS without pre-training). The updated tables explicitly present ROS-vanilla results, improving clarity. Below are the updated rows in Tables 1, 2, and 3 of the manuscript (Tables 4 and 5 already included ROS-vanilla results):

Updated Row in Table 1 in manuscripts

Updated Row in Table 2 in manuscripts

Updated Row in Table 3 in manuscripts

Questions For Authors

Response to Q1: Please refer to the "response to W1" for reviewer bfPu.

Response to Q2: Please see Response to M1.

Response to Q3: Please see Response to M2.

Reference

[1] Rishi Rajesh Shah et al., NeuroCut: A Neural Approach for Robust Graph Partitioning, in KDD. [2] Anton Tsitsulin et al., Graph clustering with graph neural networks. In JMLR. [3] Aritra Bhowmick et al, DGCLUSTER: A Neural Framework for Attributed Graph Clustering via Modularity Maximization. In AAAI.

Essential Reference Not Discussed

Response to R1:

• NeuroCUT [1] is a reinforcement learning-based partitioning method designed for graph clustering, which aims to minimize inter-cluster connections, whereas Max-$k$-Cut seeks to maximize inter-partition connections. Additionally, while NeuroCUT claims to support arbitrary objective functions, its node selection heuristics are specifically tailored for graph clustering. Due to this fundamental difference, NeuroCUT is not directly applicable to our problem.
• Despite these differences, we compared our methods with NeuroCUT. We trained NeuroCUT on 500 3-regular graphs as ROS and tested it on Bitcoin-OTC [2], a real-world signed network with 5,881 nodes and 35,592 weighted edges (ranging from -10 to 10), which captures trust relationships among Bitcoin traders. As shown in Table 1, ROS significantly outperforms NeuroCUT and other baselines, further demonstrating its effectiveness for Max-$k$-Cut.

Table 1: Evaluation results on Bitcoin-OTC Datasets.

Weakness

Response to W1:

• ROS-vanilla (without pre-training) can directly generalize to any value of $k$ since the absence of pre-training.

• ROS (with pre-training and fine-tuning) improves efficiency but does not generalize directly to unseen $k$ due to the fixed output layer during pre-training. However, this limitation can be addressed through ROS-partial, a simple modification that enables adaptation to different $k$.

• ROS-partial works by pre-training the model on $k=2$ while saving all parameters except the last layer. Before fine-tuning, the pre-trained parameters are loaded, and the last layer is randomly initialized to accommodate the new $k$. This approach serves as a middle ground between ROS (fully pre-trained) and ROS-Vanilla (no pre-training).

• We evaluate ROS-partial, ROS, and ROS-vanilla on the Bitcoin-OTC dataset. The results in Table 2 show that ROS-partial effectively generalizes to different $k$ while maintaining strong performance.

Table 2: Comparison between pre-training ways on Bitcoin-OTC Datasets.

Response to W2:

• The pre-training and fine-tuning phases of ROS correspond to the training and inference phases of other L2O baselines. Specifically, ROS is pre-trained on a collected dataset, similar to how L2O baselines are trained. During fine-tuning, ROS further optimizes based on test instances, whereas standard L2O inference keeps parameters fixed. To ensure fairness, we include the full fine-tuning time in our reported results. Thus, the datasets used for pre-training (training) and fine-tuning (testing) in ROS align with those in other L2O methods.
• To further address the concern, we also conduct experiments where we introduce fine-tuning to existing L2O baselines. After training, these models are further fine-tuned on test instances, and we plot the cut value against fine-tuning iterations in the anonymous link. The results confirm that even with fine-tuning, other baselines do not surpass ROS in solution quality.

Response to W3: We upload our code in https://anonymous.4open.science/r/ROS_anonymous-1C88/.

Reference

[1] Rishi Rajesh Shah, Krishnanshu Jain, Sahil Manchanda, Sourav Medya and Sayan Ranu, "NeuroCut: A Neural Approach for Robust Graph Partitioning", in KDD, 2024.

[2] S. Kumar, F. Spezzano, V.S. Subrahmanian, C. Faloutsos. Edge Weight Prediction in Weighted Signed Networks. IEEE International Conference on Data Mining (ICDM), 2016.

Methods And Evaluation Criteria

Response to M1: Please see "Response to W2" for Reviewer bfPu.

Weakness

Response to W1: The Max-$k$-Cut problem is a fundamental NP-complete problem with applications in physics [1], power networks [2], and data clustering [3]. While ROS is tailored for Max-$k$-Cut, its core Relax-Optimize-and-Sample framework is generalizable to other combinatorial optimization problems by adjusting the objective functions. Investigating such extensions, particularly their theoretical guarantees, is a promising direction for future work.

Response to W2: The core novelty of our work lies in the Relax-Optimize-and-Sample (ROS) framework, where the "pre-train + fine-tune" approach is used solely for efficiency. The key contributions of ROS are:

• The probability simplex relaxation ensures that the optimal values of the relaxed and original Max-$k$-Cut problems are equivalent (Theorem 3.2).
• A GNN parametrizes the decision variable, enhancing both representation power and computational efficiency.
• The proposed sampling procedure maps the relaxed solution to a discrete Max-$k$-Cut solution while preserving the objective value (Theorem 3.3).

Response to W3: Please see "Response to W2" for Reviewer bfPu.

Response to W4: We will refine and reorganize the experimental section to improve clarity and readability. Specifically, we will integrate Tables 2 and 3 in anonymous link into the manuscript to provide a clearer presentation of dataset statistics and enhance the overall structure of the experimental setup.

Response to W5: We will add a Related Work section to provide context. This will cover approximation algorithms (e.g., Goemans-Williamson (GW) [4], Frieze et al. [5]), non-convex relaxations (Rank-2 [6], QUBO [7]), and Lovász extensions [8]. We will clarify how ROS differs by ensuring objective value consistency and leveraging GNN-based optimization for high-quality solutions. We will also add Table 1 in anonymous link to further clarify the distinctions between these methods.

Other Comments and Suggestions:

Response to C1 and C2: We will revise Fig. 1 to correct the typo and ensure that all notations are used consistently throughout the manuscript.

Response to C3: The statistics of the training and testing datasets are summarized in Tables 2 and 3 in anonymous link, which we will add to the manuscript for clarity.

Response to C4: The training dataset consists of 500 3-regular graphs for $k=2$ and 500 5-regular graphs for $k=3$. The fine-tuning (testing) datasets correspond to different graph types: (a) random regular graphs, (b) Gset, and (c) weighted Gset, as detailed in Section 4.1 (Line 272, right column, Page 5).

Questions For Authors

Response to Q1:

• The random initialization does not introduce instability, as shown by the low standard deviation in Table 1 in manuscripts, where the relative error across runs remains around 1%.
• Additionally, the node features and the adjacency information can be incorporated as initialization in ROS when it is available. For example, on the Cora dataset [9], we interpolated both node features as well as the adjacency matrix to match the input dimension. Results in Table 4 in the anonymous link show that when all other model parameters remain the same, the model yields identical outputs across different initialization methods, confirming the adequacy of random initialization.
• Furthermore, random initialization facilitates distributed deployment where each node is employed on a different device, avoiding global operations required for feature interpolation.

Reference

See anonymous link.