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
Venue: ICML 2025 poster (2025)
Keywords: Max-k-Cut
Learning to Optimize
Graph Neural Networks
Pre-train and Fine-tune
Sampling
Primary area: optimization

Abstract: The Max-$k$-Cut problem is a fundamental combinatorial optimization challenge that generalizes the classic $\mathcal{NP}$-complete Max-Cut problem. While relaxation techniques are commonly employed to tackle Max-$k$-Cut, they often lack guarantees of equivalence between the solutions of the original problem and its relaxation. To address this issue, we introduce the Relax-Optimize-and-Sample (ROS) framework. In particular, we begin by relaxing the discrete constraints to the continuous probability simplex form. Next, we pre-train and fine-tune a graph neural network model to efficiently optimize the relaxed problem. Subsequently, we propose a sampling-based construction algorithm to map the continuous solution back to a high-quality Max-$k$-Cut solution. By integrating geometric landscape analysis with statistical theory, we establish the consistency of function values between the continuous solution and its mapped counterpart. Extensive experimental results on random regular graphs and the Gset benchmark 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.

ROS: A GNN-basee Relax-Optimie--nd--Sama Framework for Max-k-Cut Problems
Yeqing Qiu 12
Ye Xue
Akang Wang 12 Yiheng Wang 12 Qingjiang Shi Zhi-Quan Luo
Abstract
total weight of edges between vertices in different sub- sets is maximized. This problem represents significant challenge in combinatorial optimization and finds applica- tions across various fields, including telecommunication networks (Eisenblätter 2002 Gui et al. 2019), data cluster- ing (Poland & Zeugmann 20066] Ly et al. 2023), and theo-
The Max-k-Cut problem is a fundamental com- binatorial optimization challenge that general- izes the classic -CP-copleete Max-Cut problem. While relaxation techniques are commonly em- ployed to tackle Max-k--Ctt, they often lack guar- antees of equivalence between the solutions of the original problem and its relaxation. To address this issue, we introduce the Relax-Optimize-ande Sample (ROS) framework. In particular, we begin by relaxing the discrete constraints to the continu- ous probability simplex form. Next, we pre-train and fine-tune graph neural network model efficiently optimize the relaxed problem. Subse- quently, we propose a sampling- based construc- tion algorithm to map the continuous solution back to a high-quality Max-k-Cut solution. By in- tegrating geometric landscape analysis with statis- tical theory, we establish the consistency of func- tion values between the continuous solution and its mapped counterpart. Extensive experimental results on random regular graphs, the Gset bench- mark, 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-ar al- gorithms. Furthermore, ROS exhibits strong gen- eralization capabilities across both in-distribution and -uito--distribution instances, underscoring its effectiveness for large-scale optimization tasks.
retical physics (Cook et al. 2019 Coja-Oghlan et al. 2022). The Max-k-Cut problem is known to be -'P-complete, it generalizes the well-known Max-Cit problem, which is one of the 21 classic N -Cm-copeee problems identified by Karp (1922).
Significant efforts have been made to develop methods for solving Max-k- k-Cut problems (Nath Kuhnle 2024). )024). [hadd] dar et al. (2011) introduced an exact branch-and-cut algo- rithm based semi-definite programming, capable of han- dling graphs with up to 100 vertices. For larger instances, various polynomial-tine -imeel approximation algorithms have been proposed. Goemman & Williamson (1995) addressed the Max-Cut problem by first solving a semi-definite re- laxation to obtain a fractional solution, then applying a randomization technique convert it into a feasible solu- tion, resulting in 1.878-approximation algorithm. Building this, Frieze & Jerrum (997) extended the approach to Max-k-Cun Cut, offering feasible solutions with approximation guarantees. de Klerk et al. (2004) further improved these guarantees, while Shinde et al. (2021) optimized memory usage. Despite their strong theoretical performance, these approximation algorithms involve solving computationally intensive semi-definite programs, rendering them impracti- cal for large-scale Max-k-Cut problems. A variety of heuris- tic methods have been developed to tackle the scalaby scalability challenge. For the Max-Cut problem, Burer et al. (2002) proposed rank-two relaxation- bbaed heuristics, and Goudet ct al. 2024) introduced a meta-heurise evolutionary algorithms. For Max-k- -C-Ct, heuristics such as genetic algorithms (Li & Wang 2016). greedy search Gui
1. Introduction
approach using
The Max-k-Cut k-C problem involves partitioning the vertices of a graph into l: disjoint subsets in such a way that the
et al. 2019), multiple operator heuristics (Ma & Hao 2017) and local search (Garvardt et al. 2023) have been proposed.
'Shenzhen Research Institute of Big Data, Shenzhen, China. "The Chinese University of Hong Kong. Shenzhen, China. 'Tongii University, Shanghai, China. Correspondence to: Ye Xue <xu- eye@ www.k.cw...........
While these heuristics can handle much larger Max-k-Cul instances, they often struggle to balance efficiency and solu- tion quality.
Proceedings of the 42nd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).
Recently, machine learning techniques have gained atten- tion for enhancing optimization algorithms (Bengio et al.

---

ROS: A GNN-based Relax-Opiimizz-ad--Saa Framework for Max-k-Cut Problems
2022 Chen al. 2024). Several studies, including Khalil et al. 2017 Barrett al. 2020); Chen et al. 2020); Barrett et al. (2022), framed the Max-Cut problem as a sequential decision decision-making process, using reinforcement learning to train policy networks for gen- erating feasible solutions. However, RL-based methods often suffer from extensive sampling efforts and increased complexity in action space when extended to Max-k-Cut, and hence entails significantly longer training and testing time. Karalias & Loukas (200)) focuses subset selection, including Max-Cur as special case. It trains graph neu- ral network (GNN) to produce a distribution over subsets of nodes of an input graph by minimizing a probabilistic penalty loss function. After the network has been trained, a randomized algorithm is employed to sequentially decode valid Max-Cut solution from the learned distribution. A notable advancement by |Schuetz et al. (2022) reformulated Max-Cut as quadratic unconstrained binary optimization (QUBO), removing binarity constraints to create a differ- entiable loss function. This loss function was used to train a GNN, followed by a simple projection onto integer vari- ables after unsupervised training. The key feature of this approach is solving the Max-Cut problem during the train- ing phase, eliminating the need for a separate testing stage. Although this method can produce high-quality solutions for Max- Cut instances with millions of nodes, the computa- tional time remains significant due to the need to optimize a parameterized GNN from scratch. The work of Tönshoff eet al. (2023) first formulated the Max-Cur problem as a Constraint Satisfaction Problem (CSP) and then proposed novel GNN-based reinforcement learning approach. This method outperforms prior neural combinatorial optimization techniques and conventional search heuristics. However, to the best of our knowledge, it is limited to unweighted Max- k-Cut problems. NeuroCUT (Shah et al., 2024) is a parti- tioning method based on reinforcement learning, whereas DGCLUSTER (Bhowmick et al.) 2024) and DMoN (Tsit:
2021
Gasse et al.
timize the relaxed formulation by training parameterized GNNs in an unsupervised manner. To further improve ef- ficiency, we apply transfer learning, utilizing pre-trained GNNs to warm-start the training process. Finally, we refine the continuous solution using a random sampling algorithm, resulting in high-quality Max-k-Cus solutions.
The key contributions of our work are summarized as fol- lows:
Novel Framework. We propose scalable ROS frame- work tailored to the weighted Max-k-Cut problem with arbitrary signs, built on solving continuous relaxations using efficient sarming-based techniques.
Theoretical Foundations. We conduct a rigorous the- oretical analysis of both the relaxation and sampling steps. By integrating geometric landscape analysis with statistical theory, we demonstrate the consistency of function values between the continuous solution and its sampled discrete counterpart.
Superior Performance. Comprehensive experiments on public benchmark datasets show that our frame- work produces high-quality solutions for Max-k-Cut instances with up to 20, 000 nodes in just few seconds. Our approach significantly outperforms state-of-the-at algorithms, while also demonstrating strong general- ization across various instance types.
2. Preliminaries
2.1. Max-k- Problems
Let g E) represent an undirected graph with vertex set V and edge set E. Each edge (i.5) E E is assigned an arbitrary weight Way E R, which can have any sign. A cut in 9 refers to a partition of its vertex set. The M-x- problem involves finding a k-partition (V,..., Vi) of the vertex set such that the sum of the weights of the edges between different partitions is maximized.
sulin al. 2023) utilize GNNs to optimize clustering objec- tives. However, these methods are specifically designed for graph clustering, which focuses on minimizing inter-cluster connections-cootrall to Max-k-Cut, where the goal is to maximize inter-partition connections. Consequently, they are not directly applicable to our problem. Although Neu- roCUT claims support for arbitrary objective functions, its node selection heuristics are tailored exclusively for graph clustering, rendering it unsuitable for Max-k-Cur
To represent this partitioning, we employ a k-dimensional one-hot encoding scheme. Specifically, we define k N matrix X E R where each column represents one-hot vector. The Max-k-Cut problem can be formulated as:
1 N
ΣΣ W (1- (1-X...)) X,)
max XER 2
(1)
In this work, we propose a GNN-based Relax- Optinnzzeniiz-- Sample (ROS) framework for efficiently solving the Max-k- Cut problem with arbitrary edge weights. The framework depicted in Figure Initially, the Max-k-Cut problem is formulated as a discrete optimization task. To handle this, we introduce probability simplex relaxations, transforming the discrete problem into continuous one. We then op-
t. (e,, e...., ex)
Vj
where X., denotes the jth column of X, W is symmetric matrix with zero diagonal entries, and e E R* is a oot-hot vector with the hh entry set to 1. This formulation aims to maximize the total weight of edges between different partitions, ensuring that each node is assigned to exactly one
2

---

ROS: A GNN-based Cellax-Opimizz-aan--Sanaee Framework for Max-k-Cut Problems
Probability Simplex Relaxation
GNN Parametrization-basee Optimization
Discrete Problem min fX; W)
Initialization h
GNNs
Prediction
Loss Function
Pre-train
103
min f (# ( .
Continuous Relaxation
Fine-tune
R
min fX; W) xEa
4
f4
Random Sampling
x 1
X 22
2
5
5
H
(L)
0
0.6
1
0
X 3g
0
0
0
Discrete Solutions
Continuous Solution
Figure 1: The Sllax-Opimize-and-Samaay framework.
partition, represented by the one-hot encoded vectors. We remark that weighted Max-k-Cut problems with arbitrary signs is generalization of classic Max-Cut problems and arise in many interesting applications (De Simone et al. 1995
3. A Relax--ptimixx-and--Sajp Framework
In this work, we leverage continuous optimization tech- niques to tackle Max-k-Cut problems, introducing a novel ROS framework. Acknowledging the inherent challenges of discrete optimization, we begin by relaxing the problem to probability simplices and concentrate on optimizing this relaxed version. To achieve this, propose machine learning-based approach. Specifically, model the relaxed problem using GNNs, pre-training the GNN on a curated graph dataset before fine-tuning it on the specific target in- stance. After obtaining high-quality solutions to the relaxed continuous problem, we employ a random sampling proce- dure to derive a discrete solution that preserves the same objective value.
Poland & Zeugmann
2006
Hojny et al. 2021).
2.2. Graph Neural Networks
GNNs powerful tools for learning representations from graph-structured data. GNNs operate by iteratively aggre- gating information from a node's neighbors, enabling each node to capture increasingly larger sub-graph structures as more layers are stacked. This process allows GNNs to learn complex patterns and relationships between nodes, based on their local connectivity.
At the initial layer (1 = 0), each node E V is assigned feature vector h which typically originates from node features labels. The representation of node i is then recur- sively updated each subsequent layer through parametric aggregation function fa defined as:
3.1. Probability Simplex Relaxations
To simplify the formulation of the problem T remove constant terms and negate the objective function, yielding equivalent formulation expressed follows:
min Xex
f(X:W) = TXxXXX
P
1/ f400 (n! (111) (h :(EN())) (2)
where X' := (X E R X., E (ei, e2, ej)
It is important to that the matrix W is indefinite due its diagonal entries being set zero.
where ((() represents the trainable parameters at layer (i) denotes the set of neighbors of node i, and h is the node's embedding at layer for E 21,2,--. -.. L}. This iterative process enables the GNN to propagate informa- tion throughout the graph, capturing both local and global structural properties.
Given the challenges associated with solving the discrete problem P. we adopt a naive relaxation approach, obtain- ing the convex hull of X' as the Cartesian product of N k-dimensional probability simplices, denoted by AN Con- sequently, the discrete problem is relaxed into the follow-
3

---

ROS: A GNN-based Relax-Opimizzeand-Saa Framework for Max-k-Cut Problems
ing continuous optimization form:
where p E [0, 1]. From the neighborhood ((X)), we can identify the following integer solutions that maintain the same objective value.
min XEA
W(
P
xi - (101 1 100000003
0 1 X - 1 00)
Before optimizing problem P, we will characterize its ge- ometric landscape. To facilitate this, we introduce the fol- lowing definition.
Given that P is a non-convex program, identifying its global minimum is challenging. Consequently, the following two critical questions arise.
Definition 3.1. Let denote a point in A We define the neighborhood induced by X follows:
((X) = X XEA
Σ
Xi 11, AjEV
Q1. Since solving P to global optimality is P-r-hadd, how to efficiently optimize for high-quality solutions?
iEX(X 1)
where K(XX;)) = li (1, ... 1) by 0}.
Q2. Given X E A \ X' as high-quality solution to P, can we construct feasible solution X E X to P such that f(x; W) f(x; W)
The set ((X) represents neighborhood around X, where each point in N (X) can be derived by allowing each non- zero entry of the matrix X to vary freely, while the other entries are set to zero. Utilizing this definition, we can establish the following theorem.
We provide positive answer to Q2 in Section 3.2 while our approach to addressing Q1 deferred to Section 3.3
Theorem 3.2. Let X* denote globally optimal solution to P, and let ((*)) be its induced neighborhood. Then
3.2. Random Sampling
Let X E A X' be a feasible solution to the relaxation P. Our goal is construct a feasible solution X E X for the original problem P, ensuring that the corresponding objective values are equal. Inspired by Theorem 3.2 we propose a random sampling procedure, outlined in Algo- rithm 1 In this approach, we sample each column X.; of the matrix X from a categorical distribution characterized by the event probabilities X.; , (denoted as Cat(æ; p = x.,) in Step of Algorithm IT. This randomized approach yields feasible solution X for P. However, since Algorithm | in- corporates randomness in generating X from X, the value of f(X; ; W) becomes random as well, This raises the criti- cal question: is this value greater or lesser than f f(X; W)? We address this question in Theorem 3.3
J(x; W ((X;;W), VX EN(X))
Theorem 3.2
states that for globally optimal solution X", every point within its neighborhood (X*) shares the same objective value as X", thus forming basin in the geomet- ric landscape of f(X; W). If X E X' (i.e., an integer solution), then (XX) reduces to the singleton set {X*). Conversely, if X & X, there exist ILy IK(X:)) unique integer solutions within N(X*) that maintain the same ob- jective value as X This indicates that once globally optimal solution to the relaxed problem P is identified, it becomes straightforward to construct an optimal solution for the original problem P that preserves the same objective value.
Algorithm 1 Random Sampling
According to Carlson Nemhauser (1966), among all glob- ally optimal solutions the relaxed problem P. the integer solution always exists. Theorem 3. exteeds this result, indi- cating that if the globally optimal solution is fractional, we can provide straightforward method to derive its integer counterpart. We remark that is highly non-trivial to guar- antee that the feasible Max-k-Cuu solution obtained from the relaxation one has the same quality.
I: Input: X E A
2: for i = 1 N do
3: X,, ~ Cat(<; = X.))
end for
Output: X x
Theorem 3.3. Let X and X denote the input and output of
Algorithm respectively. Then, we have E. Ex IX(; W))
Example. Consider a Max-Cur problem (k 2) associated with the weight matrix W. We optimize its relaxation and obtain the optimal solution X
f(x: W..
Theorem 3.3 states that S(X; W) is equal to ʃ(X; W) in expectation. This implics that the random sampling pro- cedure operates on a fractional solution, yielding Max-k- Cut feasible solutions with the same objective values in probabilistic sense. While the Lovász-extensionn-aae
0
1
W= =
0 1
X*
=
p
1 0
9)
0
1 0
4

---

ROS: A GNN-based Relax-Opimizze-nd--Saa Framework for Max-k-Cut Problems
method (Bach 2013) also offers framework for contin- uous relaxation, achieving similar theoretical results for arbitrary k and edge weights Wij E IR is not always guar- anteed. In practice, we execute Algorithm| T times and select the solution with the lowest objective value of f as our best result. We remark that the theoretical interpretation in Theorem 3.3 distinguishes our sampling algorithm from the existing ones in the literature (Karalias & Loukas 2020 Tönshoff et al. 2021
optimizer with random initialization, targeting the objective
M
min +
Spre-training training (+))
I1) J(
(m) train )
M 11
where D= = (W train...... train represents the pre-
training dataset. In the fine-tuning phase, for a problem
instance Wiss, the Adam optimizer seeks to solve
Michael al. 2024).
min 4
Liineturing tuniny (+) ((H Wis),
3.3. GNN Parametrization-Be
Optimization
To solve the problem P. we propose an efficient learning-to- optimize (I.20) method based on GNN parametrization. This approach reduces the laborious iterations typically required by classical optimization methods (e.g., mirror descent). Additionally, we introduce a "pre-train + fine- tune" strategy, where the model is endowed with prior graph knowledge during the pre-training phase, significantly de- creasing the computational time required to optimize P.
initialized with the pre-trained parameters.
Moreover, to enable the GNN model to fully adapt to spe- cific problem instances, the pre-training phase can be omit- ted, enabling the model to be directly trained and tested on the same instance. While this direct approach may necessi- tate more computational time, it often results in improved performance regarding the objective function. Consequently, users can choose to include a pre-training phase based on the specific requirements of their application scenarios.
GNN Parametrization. The Max-k- -utt problem can be framed as node classification task, allowing us to leverage GNNs to aggregate node features, and obtain high-quality solutions. Initially, we assign a random embedding (0) to each node i in the graph G. We adopt the GNN architecture proposed by Morris et al. (2019), utilizing L-layer GNN with updates at layer given by:
4. Experiments
4.1. Experimental Settings
We compare the performance of ROS against traditional methods as well as L20 algorithms for solving the Max-k- Cut problem. Additionally, we assess the impact of the "Pre- train" stage in the GNN paramettizaaiion-aased optimization. com/
h
(111
(1)
Σ
W
The source code is available at Net SysOpt/ROSSSSS
JEN(1)
Baseline Algorithms. We denote our proposed algorithms by ROS and compare them against both traditional algo- rithms and L20 methods. When the pre-training step is skipped, we refer to our algorithm as ROS-van l1a. The following traditional Max-k-Cut algorithms are considered as baselines: (i) GW (Goemans & Williamson 1995]: an method with a 0.878-aprroiimation guarantee based on semi-definite relaxation; (ii) BQP (Gui et al., 2019): a
where (-) is an activation function, and Φ and ,0 are the trainable parameters at layer 1. This formulation facili- tates efficient learning of node representations by leveraging both node features and the underlying graph structure. Af- ter processing through L layers of GNN, we obtain the final output ( = [n[ (L) hxx ( E TRXN
soft- max activation function is applied in the last layer to ensure H E N making the final output feasible for P.
local search method designed for binary quadratic pro- grams; (ii) Genetic (Li & Wang 2016): a genetic al- gorithm specifically for Max-k-Cut problems; (iv) MD: a mirror descent algorithm that addresses the relaxed prob- lem with a convergence tolerance at 10-8 and adopts the same random sampling procedure; (v) LPI (Goudet et al., 2024): an evolutionary algorithm featuring a large pop- ulation organized across different islands; (vi) MOH (Mal & Hao 2017): heuristic algorithm based multiple operator heuristics, employing various distinct search op- erators within the search phase. For the L20 method, we primarily examine the state-of-the-art baseline algo- rithms: (vii) PI-GNN (Schuetz et al.) 2022): an unsuper- vised method for QUBO problems, which can model the
"Pre-train + Fine-tune" Optimization. We propose a "pre-train + fine-tune" framework for learning the train- able weights of GNNs. Initially, the model is trained on collection of pre-collected datasets to produce pre-trained model. Subsequently, we fine-tune this pre-trdined model for each specific testing instance. This approach equips the model with prior knowledge of graph structures during the pre-training phase, significantly reducing the overall solving time. Furthermore, it allows for out-of-distribution generalization due to the fine-tuning step.
In the pre-training phase, the trainable parameters + :=
{ (1) + (1)
$ (L) $ (1)) are optimized using the Adam
5

---

ROS: A GNN-based Saapppimizz-add-aaaaaaa Framework for Max-k-Cut Problems
weighted Max-Cut problem, delivering commendable per-
CW DON-
formance. (viii) ECO-DQN (Barrett al., 2020): rein-
PQP
AMrcs
Gondlic Ro5-von
forcement L2O method introducing test-time exploratory
HD RDS
10a
refinement for Max-Cut problems. (ix) ANYCSP (Tönshoff
NJA
et al. 2:23): an unsupervised GNN-based search heuristic for CSPs, which can model the unweighted Max-k-Cut prob- lem, leveraging a compact graph representation and global search action with the default time limit of 180 seconds.
Time [s)
101
104
104
Datasets. We conduct experiments the following datasets.
10
100 k-3
N=1,000 k=2
N=1,000
N-10,000
N000,000
k-2
km3
k-2
k-3
r-Random regular graphs (Schuetz et al. 2022): Each node has the same degree Edge weights are either 0 or 1.
(a) Random regular graph
ROS-vanilla
FI-GNN ANYCSP
ROS
Gset Ye 2003): A well-known Max-k-Cur benchmark comprising toroidal, planar, and random graphs with 800 ~ 20, 000 nodes and edge densities between 2% and 6%. Edge weights are either or =1.
Time
1oa
COLOR (Micheal, 2002): A collection of dense graphs derived from literary texts, where nodes rep- resent characters and edges indicate co-occurrence. These graphs have large chromatic numbers (x x 10), making them suitable for Max- Edge weights are either or 1.
G70 k=2
G70
G72
G72
G77
G77
G81
G81 k=3
k=2
k=3
k=2
k=
k=2
(b) Weighted Gset with perturbation ratio [0, 10]
MD ANYCSP
ROS-vanilla
BiCc (Kumar et al. 2016): A real-world signed network with 5, 881 nodes and 35, 592 edges, weighted from -00 to 10, capturing trust relationships among Bitcoin users.
100
Time
The construction of the training and testing datasets is sum- marized in Table [ 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 & 2, k = 3, and k = 10 respectively. The test set of ran- dom regular graphs includes 20 3-regular and 20 5-regular graphs for each & E (2, 3), with node counts of 100, 1 1,000, and 10,000. For the Gset benchmark, we evaluate both un- weighted and weighted variants. The unweighted test set includes all Gset instances, with results reported in Tables 6 and and7in in Appendix [ For the weighted variant, we generate perturbations of the four largest Gset graphs (G70, G72 G77, G81) by multiplying each edge weight by a 2(1 w). creating 10 perturbed instances per graph. We examine three distinct perturbation regimes: (i) mild perturbations (0.9, 1.1)), (ii) moderate variations ((0, 10), and (iii) ex- treme modifications (00, 100]). The moderate perturbation results (0, 10)) presented in Table with the remaining cases available in Appendix E Additionally, we evaluate performance on three COLOR benchmark instances: anna, david, and huck.
CONOX
CD0
(c) COLOR datasets and Bitcoin-OTC datascts
Figure 2: The computational time comparison of Max-k- Cut problems.
the issue of gradient vanishing, we apply graph normaliza- tion as proposed Caa et al.] (202T). The ROS model is pre-training using Adam with a learning rate of 10 for one epoch. During fine-tuning, the model is further optimized using the same Adam optimizer and learning rate, apply- ing early stopping with 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 for 7 = 100 trials and return the best solution.
Model Settings. ROS is designed as a two-layer GNN, with both the input and hidden dimensions set to 100. To address
Evaluation Configuration. All our experiments were con- ducted on an NVIDIA RTX 3090 GPU, using PyTorch 2.2.0.
6

---

ROS: A GNN-based Aelaxx-Opimizzeand--Saa Framework for Max-k-Cut Problems
Table I: Statistics of the training and testing datasets.
Dataset
Graph Type
N
# Graphs
Weight Type
Train
Random Regular Graph
regular
100
500
unweighted
Random Regular Graph
regular
100, 1,000, 10,000
60
unweighted unweighted, weighted unweighted
Gset
random, planar, toroidal
800 ~ 20,000
71
Test
COLOR
real-world
74, 87, 138
Bitcoin-OTC
real-world
5,881
weighted
Table 2: Cut value comparison of Max-k-Cut problems random regular graphs.
N=100
N=1, 000
N=10, 000
Methods
==
k=
==
2
3
GW
130.2022.79
N/A
N/A
BQP
131.55
239.70+1.82
1324.4526.34
2419.15_a.78
N/A
N/A
Genetic
127.55 235.50+3.15
1136..5521..57
2130.30=8.i
N/A
N/A
MD
127.20+2.16 235.50+3.29
1250.35+11.21
2344.85-9
12428.85, 2
23341
23341.20 30
PI-GNN
122.95
1210.45
1210.45
12655.00 454.4.25
ECO-DQN
135.60
1366.20 26.
N/A
ANYCSP
131.6
247.9010.69
1366.0515..
2494.50_2.90
13692.35 111
24929.80
ROS-vanilla
132. 80 243. 243.20 20
66.
44.1
39239.80+14
24413.30
ROS
128.20g2... 240.30+2.00
1283.75+6.s0
2405.75=0.72
12856.854288
24085.95421.0
4.2. Performance Comparison against Baselines
each iteration. Notably, MD is the only traditional method capable of solving large instances within reasonable time frame; however, when N reaches 10, 000, the computational time for MD approaches 15 times that of ROS. Regarding L,20 methods, PI-GNN necessitates retraining and predic- tion for each instance, with test times exceeding dozens of seconds even for N 100. ECO-DQN relies on expen- sive GNNs at each decision step and can scale to large problem sizes of N 10, 000. ANYCSP needs hundreds of seconds even for N = 100 due to the global search opera- tion and long sampling trajectory. In contrast, ROS solves these large instances in merely a few seconds throughout the experiments, requiring only 10% of the computational time utilized by other I.20 baselines. Figure 26 and Fig- ure 2c illustrate the results for the weighted Gset benchmark and real-world datasets, respectively, where ROS efficiently solves the largest instances in just few seconds, while other methods take tens to hundreds of seconds for equiva- lent tasks. Remarkably, ROS utilizes only about 1% of the computational time required by PI-GNN.
4.2.1. COMPUTATIONAL TIME
We evaluated ROS against seven baseline algorithms: GW, BOP, Genetic, MD, PI-GNN, ECO-DQN, and ANYCSP on random regular graphs, comparing computational time for both Max-Cut and Max-3-Cut tasks. Experiments covered three problem scales: N = 100, N = 1,000, and N = 10,000, with results shown in Figure 2a For larger instances, Figure 26 compares the scalable meth- ods (MD, ANYCSP, and PI GNN) on weighted Gset graphs (N > 10,000) with edge weight perturbations in [0, 10). Figure 2c extends this comparison real-world networks (COLOR and Bitcoin-OTC graphs). Instances marked "N/A" indicate timeout failures (30-minute limit). Com- plete results for unweighted Gset benchmarks, including comparisons with state-of-the-ae methods LPI and MOH, are provided in Tables and 7 (Appendix DD).
The results depicted in Figure 2a indicate that ROS effi- ciently solves all problem instances within seconds, even for large problem sizes of N 10, 000. In terms of base- line performance, the approximation algorithm GW performs efficiently on instances with = 100, but struggles with larger sizes due to the substantial computational burden associated with solving the underlying semiidefinite pro- gramming problem. Heuristic methods such as BQP and ienetic manage cases up to N 1, 000 in few hundred seconds, yet they fail to solve larger instances with N = 10, 000 because of the high computational cost of
4.2.2. CUT VALUE
We evaluate ROS's performance on random regular graphs, the Gset benchmark, and real-world datasets, measuring solution quality for Problem ( Results appear in Tables (random graphs), (weighted Gset), and And (real-world data), where "_" denotes methods incompatible with Max-k-Cut problems.

---

ROS: A GNN-based Relax--ptimizzeand--Saa Framework for Max-k-Cut Problems
Table 3: Cut value comparison of Max-k-Cut problems on weighted Gset instances, where the noise factor o [0, 10].
G70 (N=10, (00)
G72 (N=1C, 000)
G77 (N=14, 4, 000)
GB1 (N=20,000)
Methods
k 2
h =
k: = 2
h = 3
k = 2
k = 3
k = 2
k =
GW
N/A
N/A
N/A
N/A
BQP
N/A
N/A
N/A
N/A
N/A
N/A
N/A
N/A
Genetic
N/A
N/A
N/A
N/A
N/A
N/A
N/A
N/A
MD
45490.21 21
49615.85
33449.49
38798.78
47671.94
55147.26
67403.00
78065.07
P1-GNN
44275.72
31469.65
44359.72
62439.97
ECO-DQN
N/A
N/A
N/A
N/A
ANYOSP
46420.48
48831.32
280.74
208.00
845.72
988.96
13.52
271.01
ROS-vanilla
47140.07
49826.90 49813.45
36697.11
42067.80 80
52226.53
59636.36 58253.31
7405142
84498.44
ROS
46707.60
35733.11
40987.92
50790.44
72057.24
82450.68
Table 4: Cut value comparison of Max-k-Cut problems COLOR datasets and Bitcoin-OTCC Datasets.
COLOR anna
COLOR david
COLOR huck
Bitcoin-OTC
Methods
k 2
k
k k=
2
==3
k 2
k == 2
k 3
k 10
MD
339
421
259
329
184
242
39076
47595
53563
PI-GNN
279
228
166
37216
ANYCSP
330
423
263
328
166
139
10431
14265
19372
ROS-vanilla ROS
351
429
266
336
191
246
40576
48214
53758
351
423
266
324
191
242
39850
48980
53778
The results demonstrate that ROS consistently produces high-quality solutions for both k = 2 and k = 3 across all scales. While GW performs well for Max-Cut (A: 2) at N = 100, it fails to generalize to arbitrary k. Traditional methods like BQP and Genet ic support = 3 but often converge to suboptimal solutions. Although MD handles gen- eral k, consistently underperforms ROS. Among learning- based methods, PI-GNN proves unsuitable for to QUBO incompatibility and unreliable heuristic round- ing, while ECO-DQN lacks k: = 3 support entirely. While ANYCSP achieves strong results on unweighted graphs, it cannot process weighted instances. These experiments col- lectively show that ROS offers superior generalizability and robustness for weighted Max-k-Cut tasks, outperforming both traditional and learning-based approaches in solution quality and flexibility.
4.3. Effect of the "Pre-train" Stage in ROS
To evaluate the impact of the pre-training stage in ROS, compared it with ROS-vani 1 11a, which omits pre-training (see Section 3.3) We assessed both methods based on cut values and computational time. Figure 3 Billustrates the ratios of these metrics between ROS-vani 1la a and ROS. In this figure, the horizontal axis represents the problem instances, while the left vertical axis (green bars) displays the ratio of objective function values, and the right vertical axis (red curve) indicates the ratio of computational times.
due
As shown in Figure 3a ROS-vani 1 la achieves higher ob- jective function values in most settings on the random regu- lar graphs; however, its computational time is approximately 1.5 times greater than that of ROS. Thus, ROS demonstrates faster solving speed compared to ROS-vani i ala. Sim- ilarly, in experiments conducted on the Gset benchmark (Figure Bb), ROS reduces computational time by around 40% while maintaining performance comparable to that of ROS vanilla. Notably, in the Max-3-Cut problem for the largest instance, G81, ROS effectively halves the solv- ing time, showcasing the significant acceleration effect of pre-training. It is worth mentioning that the ROS model was pre-trained on random regular graphs with N 100 and generalized well to regular graphs with N 1,000 and N 10,000, as well as to Gset problem instances of varying sizes and types. This illustrates ROS's 's capability to
To further assess ROS's 's scalability, we conduct comprehen- sive benchmarking against scalable baselines using challeng- ing real-world datasets, including the COLOR and Bitcoin- OTC networks. The results demonstatet that both ROS and its simplified variant ROS-vani consistently outperform competing methods across most experimental settings. This performance advantage is particularly pro- nounced for the weighted Bitcoin-OTC instances, where our approach achieves superior solution quality while maintain- ing computational efficiency.
8

---

ROS: A GNN-based Relax- Shaax-Opimizz--nd--Saaaa Framework for Max-k-Cut Problems
2.0
20
laxed problem, we present a novel random sampling algo- rithm that maps the continuous solution back to discrete form. By integrating geometric landscape analysis with statistical theory, we establish the consistency of function values between the continuous and discrete solutions. Ex- periments conducted on random regular graphs, the Gset benchmark, and real-world datasets demonstrate that our method is highly efficient for solving large-scale Max-k-Cut problems, requiring only few seconds, even for instances with tens of thousands of variables. Furthermore, it exhibits robust generalization capabilittes across both in-distribution and out-of -iistiiibbttnn instances, highlighting its effective- ness for large-scale optimization tasks. Exploring other sampling algorithms to further boost ROS performance future research direction. Moreover, the ROS framework with theoretical insights could be potentially extended to other graph-related combinatorial problems, and this direc- tion is also worth investigating future work.
Roll Olighhe
0.8
N- 100
N=100
N=1,000
N=1,000
N-10,000 k-2
N=10,000
k=2
k
k=2
K-3
k-3
(a) Random regular graph
2.2
2.0
1.6
1.4
1,2
1.0
G77
Impact Statement
km3
km2
Km3
km2
km3
km3
(b) Gset
This paper presents work whose goal is to advance the field of Machine Learning. There many potential societal consequences of our work, none of which we feel must be specifically highlighted here.
Figure 3: The ratio of computational time and cut value comparison between ROS vani 1la and ROS.
A Acknowledgement
generalize and accelerate the solving of large-scale problems across diverse graph types and sizes, emphasizing the strong out-of-distribution generalization afforded by pre-training.
This work was supported by the National Key R&D Pro- gram of China under grant 3022YFA1003900 Ye Xue acknowledges support from the National Natural Science Foundation of China (Grant No. 62301334), the Guangdong Major Project of Basic and Applied Basic Research (No. 2023B0303000001,, Akang Wang also acknowledges sup- port from the National Natural Science Foundation of China (Grant No. 12301416), the Guangdong Basic and Applied Basic Research Foundation (Grant No. 2024A1515010306)
In summary, while ROS-vanill 1la achieves slightly higher objective function values on individual instances, it requires longer solving times and struggles to generalize to other problem instances. This observation highlights the trade-off between model's ability to generalize and its capacity to fit specific instances. Specifically, a model that fits individual instances exceptionally well may fail to generalize to new data, resulting in longer solving times. Conversely, a model that generalizes effectively may exhibit slightly weaker per- formance on specific instances, leading to a marginal de- crease in objective function values. Therefore, the choice between these two training modes should be guided by the specific requirements of the application.
References
Andrade, C. E., Pessoa, L. S., and Stawiarski, The phys- ical cell identity assignment problem: practical opti- mization approach. JEEE Transactions on Evolutionary Computation, 28(2):282-29) 2024.
5. Conclusions
Bach, F. Learning with Submodular Functions: A Convex Optimization Perspective. Now Publishers Inc., Hanover, MA, USA, 2013. ISBN 1601987560.
In this paper, we propose ROS, an efficient method for addressing the Max-k-Cut problem with arbitrary edge weights. Our approach begins by relaxing the constraints of the original discrete problem to probabilistic simplices. To effectively solve this relaxed problem, we propose an opti- mization algorithm based on GNN parametrization and in- corporate transfer learning by leveraging pre-trained GNNs to warm-start the training process. After resolving the re-
Barrett, T., Clements, W., Foerster, J., and Lvovsky, A. Ex- ploratory combinatorial optimization with reinforcement learning. Proceedings of the AAAI Conference on Artifi- cial Intelligence, 34(04):3243-3250 2020.
Barrett, T. D., Parsonson, C. W., and Laterre, A. Learning

---

ROS: A GNN-based Relax-Opiiiizz-an--Saa Framework for Max-k-Cut Problems
to solve combinatorial graph partitioning problems via efficient exploration. arXiv preprint 2xxi::2055.14003 2022.
algorithm. Journal of Statistical Physics, 80:487-496. 1995.
Eisenblätter A. The semidefinite relaxation of the k- partition polytope is strong. In Integer Programming and Combinatorial Optimization, pp. 273-290, Berlin, Heidelberg, 2002. Springer Berlin Heidelberg.
Bengio, Y., Lodi, A., and Prouvost, A. Machine learning for combinatorial optimization: methodological tour d'horizon. European Journal of Operational Research, 290(2):405-421, 2021. ISSN 0377-2217.
Frieze, A. and Jerrum, M. Improved approximation algo- rithms for max k-cut and max bisection. Algorithmica, 18(1):67-81, 1997.
Bhowmick, A., Kosan, M., Huang, Z., Singh, A., and Me- dya, S. Dgcluster: neural framework for attributed graph clustering via modularity maximization. Proceed- ings of the AAAI Conference on Artificial Intelligence, 38 (10): 1069-11077, 2024.
Garvardt, J., Grüttemeier, N., Komusiewicz, C., and Moraw- ietz, N. Parameterized local search for max C-cut. In Elkind, E. (ed.), Proceedings of the Thirty-Second In- ternational Joint Conference on Artificial Intelligence, IJCAI-23, pp. 5586-5594, International Joint Confer- ences Artificial Intelligence Organization, 2023.
Burer, S., Monteiro, R. D. C., and Zhang, Y. Rank-two re- laxation heuristics for max-cut and other binary quadratic programs. SIAM Journal on Optimization, 12(2):503- 521, 2002.
Main Track.
Cai, T., Luo, S., Xu, K., He, D., Liu, T.-Y., and Wang, L. Graphnorm: A principled approach to accelerating graph neural network training. In Proceedings of the 38th International Conference Machine Learning, volume 139 of Proceedings of Machine Learning Research, pp. 1204-1215. PMLR, 18-24 Jul 2021.
Gasse, M., Bowly, S., Cappart, Q. Charfreitag, J., Charlin, L., Chételat, D., Chmiela, A., Dumouchelle, J., Gleixner, A., Kazachkov, A. M., et al. The machine learning for combinatorial optimization competition (ml4co): Results and insights. In NeurlPS 2021 competitions and demon- strations track, pp. 220-231. PMLR, 2022.
Carlson, R. and Nemhauser, G. L. Scheduling to mini- mize interaction cost. Operations Research, 14(1):52-58, 1966.
Ghaddar, B., Anjos, M. F., and Liers, F. A branch-and- cut algorithm based on semidefinite programming for the minimum k-partition problem. Annals of Operations Research, 188(1):155-174, 2011.
Chen, M., Chen, Y.. Du, Y., Wei, L., and Chen, Y. Heuris- tic algorithms based deep reinforcement learning for quadratic unconstrained binary optimization. Knowledge- Based Systems, 007:1063666 2020. ISSN 0950-7051.
Goemans, M. X. and Williamson, D. P. Improved approx- imation algorithms for maximum cut and satisfiability problems using semidefinite programming. Journal of the ACM (JACM), 42()):11155) 1995.
Chen, X., Liu, J., and Yin, W. Learning to optimize: A tutorial for continuous and mixed-integer optimization. Science China Mathematics, pp. 1-72, 2024.
Goudet, O., Goëffon, A., and Hao, J.-K. A large pop- ulation island framework for the unconstrained binary quadratic problem. Computers Operations Research, 168:106684, 2024. ISSN 0305-0548.
Coja-Oghlan A., Loick, P., Mezei, B. F., and Sorkin, G. B. The ising antiferromagnet and max cut on random regular graphs. SIAM Journal on Discrete Mathematics, 36(2): 1306-1342, 2022.
Gui, J., Jiang, Z., and Gao, Pci planning based on bi- nary quadratic programming in Ite/lte-a networks. IEEE Access, 7:203 214, 2019.
Cook, C., Zhao, H., Sato, T., Hiromoto, M., and Tan, S. X.-D. Gpu-based ising computing for solving max-cut combinatorial optimization problems. Integration, 69: 335-344, 2019. ISSN 0167-9260.
Hojny, C., Joormann, I., Lüthen, H., and Schmidt, M. Mixed- integer programming techniques for the connected max-k- cut problem. Mathematical Programming Computation, 13(1):75- 132, 2021.
de Klerk, E., Pasechnik, D. V., and Warners, P. On approx- imate graph colouring and max-k-eut algorithms based on the f-function. Journal of Combinatorial Optimization, 8:267-294, 2004.
Karalias, N. and Loukas, A. Erdos goes neural: unsuper- vised learning framework for combinatorial optimization on graphs. In Advances Neural Information Processing Systems, volume 33, pp. 6659-6672. Curran Associates, Inc., 2020.
De Simone, C., Diehl, M., Jünger, M., Mutzel, P., Reinelt, G., and Rinaldi, G. Exact ground states of ising spin glasses: New experimental results with a branch-and-cut
10

---

ROS: A GNN-based Relax- Relax-Opiimize-nn---a Framework for Max-k-Cut Problems
Karp, R. M. Reducibility among Combinatorial Problems, pp. 85-103. Springer US, Boston, MA, 1972. ISBN
Shah, R., Jain, K., Manchanda, S., Medya, S., and Ranu, S. Neurocut: A neural approach for robust graph partition- ing. In Proceedings of the 30th ACM SIGKDD Confer- ence on Knowledge Discovery and Data Mining, KDD 224, pp. 2584-2595, New York, NY, USA, 2024. Associa- tion for Computing Machinery. ISBN 9798400704901.
Khalil, E., Dai, H., Zhang, Y., Dilkina, B., and Song, L. Learning combinatorial optimization algorithms over graphs. In Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017.
Shinde, N., Narayanan, V., and Saunderson, J. Memory- efficient approximation algorithms for max-k-cut and cor- relation clustering. In Advances in Neural Information Processing Systems, volume 34, pp. 2269-8281. 1. Curran Associates, Inc., 2021.
Kumar, S., Spezzano, F., Subrahmanian, V. S., and Falout- sos, C. Edge weight prediction in weighted signed net- works. In 2016 IEEE 16th International Conference Data Mining (ICDM), pp. 221-230, 2016.
Tönshoff, J., Ritzert, M., Wolf, H., and Grohe, M. Graph neural networks for maximum constraint satisfaction. Frontiers in artificial intelligence, 3:580607, 2021.
Li, P. and Wang, J. Pci planning method based on genetic algorithm Ite network. Telecommunications Science, 32(3))201602,, 2016.
Tönshoff, J., Kisin, B., Lindner, J., and Grohe, M. One model, any esp: Graph neural networks as fast global search heuristics for constraint satisfaction. In Proceed- ings of the Thirty-Second International Joint Conference on Artificial Intelligence, IJCAI-23, pp. 4280-428855 In- ternational Joint Conferences on Artificial Intelligence Organization, 8 2023. Main Track.
Ly. A., Sawhney, R., and Chugunova, M. Data cluster- ing and visualization with recursive wwillasn maxcut algorithm. In 2023 International Conference on Computational Science and Computational Intelligence (CSCI), pp. 496-500, IEEE, 2023.
Ma, F. and Hao, J.-K. A multiple search operator heuris- tic for the max-k-cut problem. Annals of Operations Research, 248:365-403, 2017.
Tsitsulin, A., Palowitch, J., Perozzi, B., and Müller, Graph clustering with graph neural networks. Journal of Machine Learning Research, 24(127): 2023.
Michael, R., Bartels, S., González-Duque, M., Zainchkovskyy, Y., Frellsen, J., Hauberg, S., and Boomsma, W. continuous relaxation for discrete bayesian optimization. arXiv preprint 17455 2024.
Ye, Y. The gset dataset. https://wel: stanfsttaoooo edu/-vyye/yyye/Cstt 2003.
Micheal, T. The color datasets.
cmu edw/coLoR02/ 2002.
Morris, C., Ritzert, M.. Fey, M.. Hamilton, W. L., Lenssen, J. E., Rattan, G., and Grohe, M. Weisfeiler and leman go neural: Higher-order graph neural networks. Proceedings of the AAAI Conference on Artificial Intelligence, 33(01): 4602 4609, Jul. 2019.
Nath, A. and Kuhnle, A. A benchmark for maximum cut: Towards standardization of the evaluation of learned heuristics for combinatorial optimization. arXiv preprint arXiv:2406. / 1897, 2024.
Poland, J. and Zeugmann, T. Clustering pairwise distances with missing data: Maximum cuts versus normalized cuts. In International Conference Discovery Science, pp. 197-208. Springer, 2006.
Schuetz, M. J., Brubaker, J. K., and Katzgraber, H. G. Com- binatorial optimization with physics-inspired graph neu- ral networks. Nature Machine Intelligence, 4(4):367-377, 2022.

---

ROS: A GNN-based Relax-Opiimizx-and-Smaa -ample Framework for Max-k-Cut Problems
A. Related Works
Relaxation-basee methods have been central to the algorithmic design for Max-Cut and generalizations. Table S we compare our proposed probability simplex relaxation with several representative approaches along key dimensions: variable complexity (# Var.), applicability to general Max-k-Cut, polynomial time solvability, objective value consistency with the original problem, and scalability to large instances.
Table 5: Comparison between Different Relaxations
Relaxation
Var.
Max-k-Cut
Polynomial Solvable?
Obj. Value Consistency?
Scalable?
Lovasz Extension Bach
2013
O(N)
x
SDP Relaxation Goemans & Williamson
1995
O(N2)
X
AYXAA XXW
Relaxation (Fiize Jemrum
1997
O(N x k)
x
Rank-2 Relaxation Burer et al. 2002
O(N)
X
X
QURO Relaxation Andrade et al. 2024
((N)
X
X
Probability Simplex Relaxation (ours)
O(N
V
The Lovász extension Bach 2013)
originally designed for submodular optimization, admits scalable convex formula- tions but does not extend naturally to general Max-k-Cut problems. Seminal SDP-based methods, such as Goemans- Williamson (Goemans& & Williamson 1995) for Max-Cut and its k-way extension (Frieze & Jerrum 1997). offer polynomial- time approximation guarantees. However, their reliance on large-scale semidefinite programming limits practical scalability and makes them less effective on modern large-scale instances. Non-convex formulations, including the rank-2 relax- ation (Burer al. 2002) and QUBO-based relaxation (Andrade al. 2024), provide scalable alternatives for Max-Cl -ax-Cut but lack theoretical guarantees for Max-k-Cut and are typically solved locally. These methods often exhibit poor objective consistency and limited generalization.
In contrast, our probability simplex relaxation introduces non-convex yet tractable formulation for Max-k-Cut with O(N x k) variables. While it is not globally solvable in polynomial time, its optimal value aligns exactly with that of the original Max-k-Cut problem. Empirically, our GNN-based solver produces high-quality fractional solutions, which serve as effective initializations for randomized sampling. Overall, the proposed relaxation strikes favorable balance between expressiveness, consistency, and scalability, offering a practical and theoretically grounded solution framework for large-scale Max-k-Cun Cut problems.
B. Proof of Theorem 3.2
Proof. Before proceeding with the proof of Theorem 3.2 we first define the neighborhood a vector ă E Ag, and establish results of Lemma B.2 and Lemma 3.3
Definition B.1. Let æ- (#1, @s) denote a point in Ag. We define the neighborhood induced by æ as follows:
N(#) = (3) (0)..... (x)))..,,x))
{
xxx) E D
Σ xj =1
jEK(Z)
where K(@) (j (1.... 1 > 0}.
Lemma B.2. Given X.; E (X)),, it follows that
K(X.) C ((X)).
Proof. Suppose there exists j K(X.;) such that j $ K(X)), implying X,x and X3, 0.
We then have
Σ
X
X5+
S
X 1
LEK(X;))
1=1
12

---

ROS: A GNN-based Relax-Opimizze-nd--Sma Framework for Max-k-Cut Problems
which leads
E
Xu S1 X3+ <1,
(EX(X;))
contradicting with the fact that X.; (N()))
Lemma B.3. Let X be globally optimal solution to P. then
f(x: f(x': :W):
where X has only the ith column X, (X(:), and other columns are identical to those of X'. Moreover, X is also a globally optimal solution to P.
Proof. The fact that X is a globally optimal solution to P follows directly from the equality f(X; W) f(X+; W). Thus, it suffices to prove this equality. Consider that X and X differ only in the 7th column, and X, E ((x)), We can rewrite the objective value function as
f(x; W) = 9(X xi) + +
where X. represents all column vectors of X except the ith column. The functions g and h are defined as follows:
N
g(x. X
W
x
X
5=1
h(X
Σ
ΣEW
W
To establish that f(x: W) = f(x
W), it suffices to show that
as X X Rewriting g( .x; X i), we obtain
g(X X i))
W ij X I X,j
Σ
Wj:X.xx
N
= 2
W x X
1=1
N Σ W
=
j=1,jşi
2X.TT.Y..
where Y. >N ii= X.
If [K(X)) 1, then there is only one non-zero element in x; equal to one. Therefore, (X.;:.-i)) = x(_.;;X..))
since X,, = X
For the case where [K(X)) > 1, we consider any indices j, E K((:)) such that X; X E (0. Then, there exists 0 such that we construct a point क E A where the jth element set to Xj, - e, the 4th element is set to X + e, and all other elements remain the same as in X Since X is a globally optimum of the function f(;; W), it follows that X is also global optimum for the function X;; X. x)). Thus, we have
X 1) (6;
x Y. < क T
Ya
= x: Y.: cY,: + cY..
13

---

ROS: A GNN-based Relax-Opüiizze-nn--SSene Framework for Max-k-Cut Problems
which leads to the inequality
Ys S Yis
(3)
Next, we can similarly construct another point ø E A with its jth element equal to X;; + e, the hthh element equal to X c, and all other elements remain the same in x Subsequently, we can also derive that
g(X
)) S g(0; x.- x Y. + + - cYy..
which leads to another inequality
Y: S Yj:
(4)
Consequently, combined inequalities and
we have
Ys Yi:.
for j.l E (((X)).
From this, can deduce that
Yns = Ysi -... Y (IR(X:11
where "", S1x(X111 E KC(;)) Next, we find that
g X X.) x.-x))--xXX3 =2x;" Y::
k =2 Σ XjAY
j=l
22 Σ
X;,Y;;
j=1jjE((x))
N
21
Σ
Xj.
}=1jE(((;))
2t.
Similarly, we have
9(X,;; X () 2X.YY. Y.:
=2 > Xj
/=1
=2 Σ
XjiY,
j=1JEK((X))
Lemma B.J 2t
Σ
(=1jEX((..)
= 2/
Accordingly, we conclude that
0(.4; = g(X;; X..)).
which leads us to the result
s(x: W) = ((X::W),
where X., x
x,, X
14

---

ROS: A GNN-based Sawp---ppmizzann----aaaaa Framework for Max-k-Cut Problems
Accordingly, for any X (X*), iteratively apply Lemma B.3 to each column of X while holding the other columns fixed, thereby proving Theorem 3.2
C. Proof of Theorem 3.3
Proof. Based on X, we can construct the random variable X, where X, Cat(x:: X.). function is given by
The probability mass
P(X.; ee) X
(5)
where & 1, k.
Next, we have
N N
Exlf(X; = XXXXXXXXXX = Ex
W x ,
N N
WidEx,X, X.
WiJEx, 11(x; 1 X.,)
WipP(X, =X,)
N
Σ Σ WoP((, =X,). E
(6)
Since X,; and X, are independent for i + j. we have
P P X
P(X.; = xX,;= = =
P(X:; =e;, x, es)
t=1
P P(X.; et) ((), = ce)
Σ XAXi
1=1
= =,,,,''
(7)
Substitute 7 into 6
we obtain
N N
ExI((X: W)) = Σ Σ
W
((:
(8)
D. The Results on Unweighted Gset Instances
15

---

ROS: A GNN-based Cellx--piimize-and-See -na-aa Framework for Max-k-Cut Problems
Time 63
1.3
1.8
1.0
211
17
17
18
19
18
14
1.5
18
13
15
13
18
16
27
24
19
35
19
19
29
17
17
ROS
7
11595
1467
1550
11459
11408
1907
1801
1775
1876
1755
494
494
524
2953
2916
2014
905
772
788
868
1.0001
12936
12933
12843
12444
2971
2923
3088
3025
1236
1
1220
60
2.6
2.6
26
26
255
28
26
2.6
19
1.9
1.5
177
19
21
2.1
2.6
19
26
2.9
22
233
11425
11462
11116
11505
1994
1576
1559
1811
498
518
2992
2920
2917
2002
903
843
858
13228
13035
1300
13054
2993
2985
3056
5004
1240
1224
1226
63)
13
23
119
104
32
413
254
258
291
197
203
410
350
349
302
1070
11624
1200
11016
11631
2178
2005
2005
2054
2000
556
582
3064
3050
3052
3047
992
908
961
951
13399
1333
13340
13328
3396
2465
2413
1410
1382
1384
1.5
4.6
1.0
30
32
68
0.9
2513
93.7
129.5
112.7
43.7
1553
3524
7779
442.5
535
707-2
5552
330.
65.
508.1
84.2
11624
166
11546
16671
2178
2005
2054
2006
556
582
3064
3052
3517
992
941
931
13359
13327
1:540
1,322
3298
3405
3413
1430
530
1304
Table 6: Complete results on Gset instances for Max- Max-Cut Cut.
61) L
90
800
180
800
180
180
180
180
180
180
180
180
180
180
1804
180.
100
180
1
1000
1800
180.
100
180
180
100
T
11574
1159
1159
15575
21300
1972
1974
2006
1953
548
542
568
3036
3018
3027
996
925
925
13200
13234
18279
13255
5305
3346
3365
1360
1342
1350
(4)
23
25.2
06
26.8
24.
23.5
23.5
268
27.1
25.6
22.2
26.9
23.4
26.8
25.8
25.6
28.
25.2
198.
509
202.5
2014
201 1
204.3
200
198
194.5
198.
T
11422
11516
11522
11-85
3055
1957
1955
2044
19300
541
565
2807
2757
2754
925
897
864
13169
19995
131 3145
13126
3160
2312
3247
2215
1549
1530
1520
(6)
113
11.7
11.2
11.0
11.4
111
145
10.9
110
10.
11.1
143
12.1
112
119
16.1
95.6
93.0
1026
96.9
96.3
96.4
99.3
02.7
89.5
95.0
1140K
11:26
14006
1991
1760
1758
1845
1816
534
580
2965
2056
2987
2067
922
860
857
1303
13002
12008
12406
2003
2014
3074
1338
130
1314
597 4
588 3
536
580.5
598 2
581
591
552.3
589.
514
5300
564
5413
558
567.0
568
572.2
N/A
N/A
N/A
N/A
N/
N/A
N/A
N/A
N/A
N/A
M/A
10020
109225
10945
10369
1435
1241
1345
1313
398
426
2555
2848
2830
613
633
630
A/A
NAA
NA
AA
NA
NA
NA
NA
CO
214.5
212.7
216.0
214
214.4
215
211.2
212.7
215.
214.2
211.5
212.
186.7
212.9
213
289.3
212.9
2145
214.3
217.2
2163
214
216.5
214.3
214
2134
2124
185.
PE-GRR
10600
10533
10805
10417
1748
1588
1545
1415
470
480
2484
2604
2455
763
240
240
12283
11608
12233
12141
2563
2378
2559
1106
1068
110
05)
5
5.3
4.8
3.7
6.9
6.1
80
7.3
24
3.0
3.1
38
3.3
3.7
33
3.0
12.2
10.0
11.7
10.8
11.2
12.3
11.7
11.5
6.8
6.6
5.8
11 300
155
1200
11280
1156
1755
1651
1720
1700
498
2030
2433
2037
2022
825
207
784
1277
12221
1223
12723
2782
2736
2774
1136
1106
1
1225
12178
125 8
16 6
1235
12150
2223
NA
NTA
17166
N/A
1
571.3
10156
1350.
M/A
NAA
AAA
A/A
NA
AAA
ASA
N/A
NA
NWA
NAA
NA
7799
1299
1139
12007
12556
1776
1676
1675
NA
NA
2842
NA
2516
83
763
781
831
MA
NAA
MA
MOA
N/A
NAA
MA
NAA
MA
MA
19/76
19176
19:76
19/76
19776
19176
19176
19776
19276
19176
1800
4004
4672
4067
1081
4822
4067
19990
1999
1999
19990
1999
19990
19990
4000
2000
2000
11778
IM
800
800
800
800
800
800
800
800
800
800
800
800
800
800
800
800
800
800
800
800
800
300
200
200
200
200
2000
2000
2000
2000
2000
GL
G2
G4
63
06
69
C10
Q12
G13
014
G16
G17
018
620
G21
622
624
625
626
622
629
630
632
G33
16

---

ROS: A GNN-based Selxx-Opimmize-an--aee -ample Framework for Max-k-Cut Problems
Time (3)
1.5
1.5
17
25
23
17
17
17
18
21
22
19
17
16
16
13
25
23
3
23
33
34
39
8.1
7107
7141
2168
2128
2138
2255
6-71
6-72
6400
6299
6400
5498
5452
5582
3677
3641
3038
3642
3675
3078
17514
13602
5011
45M
7057
45335
5500
8916
6102
9740
Time (3)
2.4
1.7
25
277
166
22
27
2.5
24
25
25
32
31
32
15
13
1.5
16
21
1.3
23
19
2
388
358
17
23
4.4
55
49
6.2
9
7235
7164
2107
2207
2120
2200
66988
6528
6608
5640
5500
50%
3629
3536
3633
3633
244
3140
17632
13433
5055
425
7508
4678
5570
600
9004
6056
8675
Teae
5740
4062
347
314
286
19
20
19
94
93
90
119
182
49143
3634
65731
44822
74577
2655
49138
21735
34002
28830
42542
66063
7680
7691
2400
2405
2461
6600
6630
6654
662
6657
6000
600
5000
3851
2000
3852
4017
3894
1924
1419
5798
4072
8752
5502
6354
0504
7004
9926
Time: (43
66
652
787
4725
377.4
12
53
6.9
0.0
0.0
200
2093
9904
1528
1222
2963
6605.3
55686
401
1111
4700
6061
55324
6885
986366
760
769
2408
2400
2405
2481
0690
6650
6654
6629
6657
6000
6000
5000
3851
2000
3802
4016
2094
1928
1450
5798
4806
3747
550
6300
9564
6995
9924
Time (0)
180
180
180
180
180
180.1
180.
1881
1882
1802
1886
1882
1900
1802
1800
1880
1802
1801
1804
180.
1596
180
1802
180.
7
7655
761
2354
2530
2346
2416
663
0532
6612
A63
0655
5962
5936
5330
382
3836
5007
3220
10215
301
3404
19152
14096
5710
4732
A514
5392
6172
9300
0825
9994
Time (5)
ECO-EOR
1051
204
198.
1998
203.7
42.2
41.3
2W1.2
871.
41.
38.
44.6
3/4
NA
NA
NA
NA
NA
N44
N/1
NA
W44
N/4
N/A
NA
N4
N/A
Table 6: Continued.
6922
6555
6655
1904
2171
1925
2152
6585
6577
658
6570
6575
5679
5879
5007
3409
3435
N1
N/A
N/A
NA
N44
NAA
N/A
NA
NAA
M/A
N/
N/A
N/A
N/A
Time (3)
05.
95.4
97.3
1058
180
185
22.4
3004
3050
2098
173
18.
180
IN.
11476
1120
11766
NA
NA
ASA
NA
AA
AVA
N/
NA
NA
7400
7498
2196
2108
21
2255
699
646
6400
6485
669
6000
600
5800
3759
3771
3752
3751
3710
3510
18813
NOA
ADA
NA
AWA
ADA
NA
N/A
NVA
NA
Time (1)
Canotic
NAA
N/A
N/A
N/A
NAA
9143
9215
9124
A/A
AVA
ASA
AR79
2052
8728
8001
NA
AUA
ASA
AGA
NA
AVA
ASA
N/X
AVA
AVA
N/A
AGA
NOA
N/A
N/A
N/A
N/A
NA
6009
6036
5978
NSA
N/4
NA
3575
2565
3528
400
NW
NM
A64
AWA
AIA
NA
N/A
ADA
NA
N/A
AUA
NIA
NA
Tiae: (41
3163
1853
2155
216.0
2186
1869
1908
1896
191.4
192.
1885
1858
1366
180.
201
2850
2023
210
2139
210
2129
2204
2231
2175
217
2010
22-308
6424
6024
1855
1898
6099
0091
55M
4058
4938
4948
3185
3029
3201
2939
26500
17115
11430
4225
3720
6616
4200
4816
8604
5396
7552
Time (V)
00
8.3
922
9.
81
50
5.0
49
47
106
10.1
47
4.5
4,4
23.8
17.3
29.2
316
24.
36.3
26.1
437
32.5
37.3
563
412
660
7555
2400
1971
1969
2075
6380
6527
6129
630
636
5005
5066
513
3695
3670
3682
0462
5203
2770
1845
1309
4592
3922
7283
4520
5100
8851
5538
7934
Time (6)
NAA
N/
N/
NA
NA
1784
1488
1522.
N/A
N/A
A/A
N/4
NR
AA
N/
NA
A/4
N/1
N/A
A44
2/4
N/1
N/A
A44
N/1
N/K
NAA
NA
N/A
N/A
NA
M/A
N/A
NA
6340
6351
6353
6357
NA
NA
N7A
NA
N/
NAA
N/A
NA
NI
N/A
N/A
N7A
NA
NA
N/A
NA
NA
MA
NA
NA
MA
NAA
MA
17706
11785
11788
11766
11285
1779
0920
9900
0990
9200
6000
600
600
5916
5914
5916
12688
1030
20510
1714H
1714
1500
41550
1600
1800
9909
2000
2000
4000
2000
2000
2000
2000
2000
2000
1000
1000
2000
3000
3000
1000
1001
8000
5001
500
7000
700
RUM
7000
5000
5000
10000
10000
1000
G35
637
639
640
G41
G44
G45
648
C32
026
657
890
E61
664
555
620
G72
17

---

ROS: A GNN-based Relax-Optimzze-ndd -ample Framework for Max-k-Cut Problems
1.9
2.3
1.9
2.9
18
2.4
2.1
2.2
2.3
1.4
1.5
2.1
2
1.6
1.6
1.7
1.7
1.8
1.5
2.2
3
1.8
2.1
3.4
2.5
1,7
1.7
1,7
Time
ROS
Obj
14961
14932
14961
14962
2361
2188
2171
2185
2181
591
582
624
3892
3838
3852
1062
967
993
975
16601
16702
16754
16673
16665
3532
3414
3596
3654
3525
1482
1454
1435
9536
ROS R0S-vamm -aa--aannll 1oss-annlll 1.s
Time (5)
2.8
2.8
3.3
3.2
2.8
2.1
2.8
2.8
2.9
288
1.9
2.3
2.4
2.2
2.1
2.2
2.2
3.3
3.6
2.1
1.7
3
34
3.1
3
255
2.5
2.4
2
Obj 1
14949
15033
14984
15006
2188
2237
2246
2201
616
604
3914
5817
3841
1094
972
1006
1011
16790
16819
16801
16795
3517
3507
3656
3596
1488
1449
1418
9225
Time 4
557.3
333.3
300
98.2
381.0
456.5
282.0
509.
143.8
100.7
88.2
80.3
1.3
7.8
0.3
0.2
133
55.8
28.5
45.1
16.3
64.8
53.2
38.9
68.2
15004
124.7
160
62.6
88.9
66.2
Table 7: Complete results on Gset instances for Max 33 C.Cu..
Obg.
15165
15172
15184
15193
2632
2409
2428
2/78
2407
609
660
4012
3984
3991
3983
1207
1081
1122
1109
17167
17168
17162
17163
4020
3973
11
4003
1653
1625
1607
10046
Time (>)
180.1
180
180.
180.1
180
180.
180.
180
180
180
180.
180
180
180
180.1
180.
180
180.
180.
180.1
180
180
180.
180.1
180
180
180.
180.1
180
180
180
AAYCSB
Obj.
15115
15088
15155
15092
1164
932
1007
1164
919
650
633
3073
3975
3945
3955
999
915
861
895
17098
17049
17042
17085
2846
2778
3035
3032
2881
1.90
1550
1525
9968
Time (8)
16.5
17.0
17.1
17.3
25.0
16.6
19.3
16.5
18.2
1644
17.
16.9
17.3
20.2
18.7
17.0
17.0
17.5
135.5
135.6
137.7
141.8
134.3
1364
136.2
133.6
131.0
129,3
126.2
126.0
138.1
DDP
Obi
148880
14845
14886
14847
23002
2081
2096
2099
2055
624
608
3000
3885
3886
1083
977
984
16599
16626
1659)
16861
3475
3433
3578
3439
1545
1517
1459
9816
Time (x)
595.5
595
588
588.7
591.9
604
589
589.7
6044
593.3
554.5
543.6
571.1
567.6
558.7
584.0
576.8
576.3
N/A
NIA
N/A
N/A
N/A
NGA
NIA
N/A
NGA
N/A
N/A
N/A
N/A
N/A
Genet.ic
Olgi
14075
14035
14055
14104
1260
1252
1326
1266
414
388
425
3679
3625
3640
704
595
589
612
N/A
N/A
N/A
N/A
N/
N/A
NIA
NA
NIA
NAA
N/A
NIA
NIA
NIA
Time +
9.6
8-4
6.9
8.1
8.9
7.7
822
7.5
4.0
444
5.0
488
5.3
4.5
45
49
15.2
15.0
16.1
16.2
16.4
16.1
16.0
16.2
17.0
11.1
10.7
10.9
14.2
MD
14735
14787
14716
14681
2161
2017
1938
2031
1961
553
530
558
3844
3815
3825
3815
992
860
928
976
16402
16422
16452
16407
3250
3198
3524
3320
3243
1342
1284
1292
96-44
Obj.
|1|
19176
19176
19176
19176
19176
19176
19176
19176
1600
1600
1600
4694
4661
4667
4694
4661
4672
4667
19990
19990
19990
19990
19990
19990
19990
19990
4000
4000
4000
11778
M
800
800
800
800
800
800
800
800
800
800
800
800
800
800
800
800
800
2000
2000
2000
2000
2000
2000
2000
2000
2000
2000
2000
2000
2000
G1
G2
G4
65
G7
G8
G10
G11
G12
614
G15
G16
G17
618
G19
G20
621
G22
G23
G24
G25
G26
G27
G28
G29
G30
631
G32
G33
G34
G35
18

---

ROS: A GNN-based Selxx-Opiiiize-an---aa -ample
Framework for Max-k-Cut Problems
2.3
1.5
1.5
2.2
24
2.5
2.2
2.3
1.7
1.8
1.7
2.2
2
1.8
1.8
1.7
1.9
1.6
14
2.6
2.1
2.8
1.9
3.5
2.3
3.6
2.7
1.9
2.5
2.6
3.9
4.1
2.5
3.5
8.5
9.7
ROS
9422
9370
2557
2584
2613
K349
K311
8339
8357
5912
5918
4820
4866
4808
11965
4037
3595
23274
6448
16398
5861
5086
9171
5775
6610
7250
9971
7297
10329
14466
Time (6) 2
ROS -oos-vonnii 1.0-vvani.1. 1.1
1.4
2.5
23
3.2
2.7
2.6
2.6
29
266
26
28
2.8
2.9
2.4
1.9
2.6
2.2
2.1
3.3
3.3
2.1
1.7
2.6
2.5
3.4
28
3.5
54
3.5
4.2
5.1
8.6
20.2
Ob)
9372
8893
9489
2621
252
2638
8414
8369
8397
8409
8386
5954
59.8
48
4796
4846
12010
4085
3597
6133
16467
5881
4983
32468
8911
5735
6501
9982
7210
10191
14418
Time (6)
3.4
116.6
90
82.8
87.7
2.5
380.3
616.8
215.3
239.4
04
119.2
47.9
0.7
223.9
383,
569.2
535.6
576.0
27.5
683.0
503.1
242.4
186.9
324,
542.5
756.7
7.8
271.2
154.9
331.2
OPty 1
10039
10052
10040
2903
2870
2887
2980
8573
R571
8568
8572
6000
6000
5037
5040
5039
12429
4752
4083
7262
17076
6853
5688
10443
6490
7416
8086
9999
8192
11578
16321
Time (6) 2
180.
180.
180.
180.1
8.6
8.4
32.8
180.1
180.
180.
180.
180.2
180.2
180.2
180.2
180.2
180.2
180.2
180.2
180.2
180.2
180.2
180.2
180.2
180.2
180.2
180.4
180.1
159.6
146.5
180.2
160.2
180.2
180.2
ANYCSE
Obj-
9972
9983
9980
2497
2416
2685
8531
8515
8501
8513
5985
5989
4990
5002
5000
12355
4408
3913
23025
6178
16974
6426
5444
35070
8557
6232
7129
7827
9848
7893
11128
15658
Table 7: Continued.
Time (5)
139.2
142.3
1328
131.
129.9
129.2
29.9
27.7
34.2
27.8
27.3
394.8
427
28.6
27.8
27.6
1506.0
1341.5
1317.2
1468.3
1377.1
N/
N/A
N/A
N/
NA
NAA
N/A
NA
NA
N/A
N/A
PQP
Obj f
9786
9821
9775
2600
2606
2682
8329
8326
8312
8322
5998
6000
4922
4910
4920
4921
12042
420S
3817
6631
NA
N/A
MA
NAA
NA
N/A
NA
NA
NA
N/A
N/A
Time (8)
N/A
N'A
N/
N/A
N/A
NA
NA
926.7
919.0
926.7
918.7
928.0
N/A
N/A
NA
889.5
908.
898
N'
MA
N/A
N/A
NA
NA
N/A
N/A
NA
NA
NA
N/A
N/A
NA
NA
N/A
N/A
Cenetic ic
Obj
N/A
NIA
NA
N/
N/
NIA
NA
7624
7617
7635
7619
NA
N/A
NIA
4582
4571
4568
4562
NIA
NA
NA
N/A
NIA
NA
N/A
NA
N/A
NIA
NA
NIA
N/A
NIA
NA
N/
NA
Time (8)
14.9
14,0
13.4
13.3
12.7
13.1
8.1
7.0
7.7
7.5
7.2
14,7
14.4
14.5
6.6
6.4
68
6.4
37.9
38.5
33.0
47.1
46.3
58.5
57.7
49.7
73.4
73.4
59.6
69.0
79.0
74.8
79.2
142.3
241.1
KD
Obj.
9600
9632
9629
2368
2315
2386
2490
8214
8187
$229
8211
5906
5794
5823
4805
4849
4845
4836
11612
3716
3246
24099
6057
15993
5374
4497
8773
5212
5948
6545
9718
6612
9294
13098
|11
11785
11779
11778
17766
11785
11779
9990
9990
9990
9990
9990
6000
6000
6000
5909
5916
5914
12498
12498
10000
29570
29570
17148
17148
140000
41459
41459
16000
18000
20000
9999
20000
28000
4000N0
M
2000
2000
2000
2000
2000
1000
1000
1000
1000
1000
3000
3000
1000
1000
1000
XX00
5000
5000
5000
5000
7000
7000
7000
7000
8000
9000
10000
10000
10000
14000
20000
G36
G37
G38
G39
G40
G41
642
G43
G44
G45
G46
G47
G48
G49
G50
G51
G52
G53
G54
G55
G56
G57
G58
G59
G60
G61
G62
G63
G64
G65
G66
G67
G70
G72
G77
G81
19

---

ROS: A GNN-based Relax-Opiimizzendd-Smaea Framework for Max-k-Cut Problems
MD ANYCSP
ROS-vanila
ND ANYCSP
ROS-vanile
10P
10
Time (s)
Time (s)
10
10a
10
G70
G70
G72
G72
G77
G77
G81
G81
G70
G70
G72
G72
G77
G77
G81
G81
k=2
k=3
k=2
k=2
k=3
k=2
k=3
k-2
k=3
k=2
k=3
k=2
k=3
k=2
k=3
(a) Weighted Gset with perturbation ratio [0.9, 1.1]
(b) Weighted Gset with perturbation ratio [o, 100]
Figure 4: The computational time comparison of Max-k- k-ttt problems.
Table 8: Cut value comparison of Max-k-Cut problems weighted Gset instances with perturbation ratio [0.9, 1.1].
G70 (N=10, 000)
G72
(N=10,000)
G77 (N=14, 000)
G81
(N=20, 000)
Methods
k = =
= 2
=
h = 2
k
k: = 3
8594.38
9709.56
5647.25
6585.04
8051.81
9337.31
11326.30
13179.33
PI-GNN
8422.79
5309.65
7470.89
10416.44
ANYCSP
5198.87
5375.92
15.57
25.33
81.76
114.36
33.49
4.225
ROS-vanilla
9177.21
9991.95
6542.78
7733.87
9265.65
10944.35
13132.52
15456.28
ROS
8941.80
9970.72
6165.62
7366.54
8737.59
10359.25
12325.85
14570.04
E. The Results on Weighted Gset Instances
The computational time on weighted Gset with perturbation ratio of [0.9, 1.1] and [0, 100] are shown in Fig. respectively. The cut values are shown in Table and Table respectively.
4a and Fig. 4b
F. Ablation Study
F.1. Model Ablation
We conducted additional ablation studies to clarify the contributions of different modules.
We consider two cases: (i) replace GNNs by multi-layer perceptrons (denoted by ROS-MI.P) in our ROS framework and (ii) solve the relaxation via mirror descent (denoted by MD), Experiments on the Gset dataset show that ROS consistently outperforms ROS-MLP and MD, highlighting the benefits of using GNNs for the relaxation step.
Effeet of Neural Networks:
Effeet of Random Sampling: We compared ROS with PI-GNN, which employs heuristie rounding instead our random sampling algorithm. Results indicate that ROS generally outperforms PI-GNN, demonstrating the importance of the sampling procedure.
These comparisons, detailed in Tables 10 and 11 confirm that both the GNN-based optimization and the random sampling algorithm contribute significantly to the overall performance.
F.2. Sample Effect Ablation
We investigated the effect of the number of sampling iterations and report the results in Tables 12
13 14 and
15
The cut values stabilize after approximately 5 sampling iterations, demonstrating strong performance without requiring extensive sampling.
Cut Value (Table 12 Table 14):
Sampling Time (Table
13 Table 15
The time spent on sampling remains negligible compared to the total computational
20

---

ROS: A GNN-based Relax-Opiimize-nd---ae -aaaaa Framework for Max-k-Cut Problems
Table 9: Cut value comparison of Max-k-Cut problems on weighted Gset instances with perturbation ratio [0, 100].
G70
(N-10, 000)
G72
(N-10,
000)
G77
(N-14, 00C)
G81
(N-20, 000)
Methods
==
3
k:
==3
2
k 3
==3 3
MD
456581.30
497167.48
338533.0 07
392908.80
482413.19
558264.21
682809.47
790089.41
PT-GNN
442650.59
312802.48
442354.44
623256.74 74
ANYCSP
467696.98
491654.75
11903.50
-2498.86
9712.13
10130.89
2842.64
2845.46
472067.14
498273.60 60
367795.62
421189.97
524010.92
597597.50 700
742432.4 41
846395.85
ROS
470268.97
498269.90
362910.89
415905.88
515991.31
590312.40
731468.67
835424.19
Table 10: Cut values returned by each method on Gset.
G70
G72
G77
GB1
Methods
==
==
k 3
k
k
2
1: 3
ROS-MIA
8867
9943
6052
6854
8287
9302
12238
12298
PI-GNN
8956
4544
6406
8970
MD
8551
9728
5638
6612
7934
9294
1 11226
13098
ROS
8916
9971
6102
7297
8740
10329
12332
14464
time, with increased number of samples.
These results highlight the efficiency of our sampling method, achieving stable and robust performance with little computa- tional cost.
21

---

ROS: A GNN-based Relax-Opiimizzeand-SSmaa Framework for Max-k-Cut Problems
Table 11: Computational time for each method on Gset.
G70
G72
G77
GB1
Methods
k = 2
k
3
k
k
k =
2
k
h 2
k: = 3
ROS-MLP
3.49
3.71
3.93
4.06
8.39
9.29
11.98
16.97
PI-GNN
34.50
253.00
349.40
557.70
MD
54.30
74.80
44.20
79.20
66.00
142.30
130.80
241.10
ROS
3.40
2.50
3.90
3.50
8.10
8.50
9.30
9.70
Table 12: Cut value results corresponding to the times of sample T on Gset.
G70
G72
G77
G8
T
h ==
k =
==
==
k: k=
k
0
8912.62
9968.11 11
6099.88
7304.45
8736.58
10323.61
12328.83
14458.09
8911
9968
6100
7305
8736
10321
12328
14460
8915
9969
6102
7304
8740
10326
12332
14462
10
8915
9971
6102
7305
8740
10324
12332
14459
25
8915
9971
6102
7307
8740
10326
12332
14460
50
8915
9971
6102
7307
8740
10327
12332
14461
100
8916
9971
6102
7308
8740
10327
12332
14462
Table 13: Sampling time results corresponding to the times of sample T on Gset.
G70
G72
G77
G81
T
k:
k ==3 3
k = 2
1: 2
h: = 3
k 2
0.0011
0.0006
0.0011
0.0006
0.0020
0.0010
0.0039
0.0020
0.0030
0.0029
0.0029
0.0030
0.0053
0.0053
0.0099
0.0098
10
0.0058
0.0059
0.0058
0.0058
0.0104
0.0104
0.0196
0.0196
25
0.0144
0.0145
0.0145
0.0145
0.0259
0.0260
0.0489
0.0489
50
0.0289
0.0289
0.0288
0.0289
0.0517
0.0518
0.0975
0.0977
100
0.0577
0.0577
0.0576
0.0578
0.1033
0.
0.1949
0.1953
Table 14:
Cut value results corresponding to the times of sample on random regular graphs.
n
100
1, 000
n 10, 000
k
2
h: = 3
k = 3
h: = 2
k: = 3
126.71
244.77
1291.86
2408.71
12856.53
24102.22
127
245
1293
2408
12856
24103
127
245
1293
2410
12863
24103
10
127
245
1293
2410
12862
24103
25
127
245
1293
2410
12864
24103
50
127
245
1293
2410
12864
24103
100
127
245
1293
2410
12864
24103
22

---

ROS: A GNN-based Relax- Shlax--pimize-an--Saaaa Framework for Max-k-Cut Problems
Table 15: Sampling time results corresponding to the times of sample T on random regular graphs.
100
1, 1,000
10, 000
T
k
2
k
h: 2
0.0001
0.0001
0.0001
0.0001
0.0006
0.0006
5
0.0006
0.0006
0.0007
0.0007
0.0030
0.0030
10
0.0011
0.0011
0.0014
0.0013
0.0059
0.0059
25
0.0026
0.0026
0.0033
0.0031
0.0145
0.0145
0.0052
0.0052
0.0065
0.0060
0.0289
0.0289
100
0.0103
0.0103
0.0128
0.0122
0.0577
0,0578
23


Reviews:
[{"review_id": "vHyuAUTkN3", "reviewer": "Reviewer_zJRf", "summary": "The paper proposes a GNN-based solver for the mak-k-cut problem.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "## Methods And Evaluation Criteria\n**Response to M1:** Please see \"Response to W2\" for Reviewer bfPu.\n\n## Weakness\n**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.\n\n**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:\n- The probability simplex relaxation ensures that the optimal values of the relaxed and original Max-$k$-Cut problems are equivalent (Theorem 3.2).\n- A GNN parametrizes the decision variable, enhancing both representation power and computational efficiency.\n- The proposed sampling procedure maps the relaxed solution to a discrete Max-$k$-Cut solution while preserving the objective value (Theorem 3.3).\n\n**Response to W3:** Please see \"Response to W2\" for Reviewer bfPu.\n\n**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](https://anonymous.4open.science/r/Tables_and_Reference_For_zJRF-9D0B) into the manuscript to provide a clearer presentation of dataset statistics and enhance the overall structure of the experimental setup.\n\n**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](https://anonymous.4open.science/r/Tables_and_Reference_For_zJRF-9D0B) to further clarify the distinctions between these methods.\n\n## Other Comments and Suggestions: \n**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. \n\n**Response to C3:** The statistics of the training and testing datasets are summarized in Tables 2 and 3 in [anonymous link](https://anonymous.4open.science/r/Tables_and_Reference_For_zJRF-9D0B), which we will add to the manuscript for clarity.\n\n**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).\n\n## Questions For Authors\n**Response to Q1:** \n- 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%. \n- 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](https://anonymous.4open.science/r/Tables_and_Reference_For_zJRF-9D0B) 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.\n- Furthermore, random initialization facilitates distributed deployment where each node is employed on a different device, avoiding global operations required for feature interpolation.\n\n## Reference \n\nSee [anonymous link](https://anonymous.4open.science/r/Tables_and_Reference_For_zJRF-9D0B).", "claims_and_evidence": "Yes. But I do have many questions.", "methods_and_evaluation_criteria": "Some points may not be clear enough. For example,\n\n- Does other baselines use the same training data as the training+finetuning datasets of ROS? If not, can other methods be fit under the pretrain-finetune framework?", "theoretical_claims": "I did not check them very carefully.", "experimental_designs_or_analyses": "See comments.", "relation_to_broader_scientific_literature": "The work contributes to the combinatorial optimization community.", "essential_references_not_discussed": "n/a", "other_strengths_and_weaknesses": "Strengths\n\n- The max k cut problem, as a generalization of the max cut problem, holds significant research value.\n\nWeaknesses\n\n- The scope of the paper is relatively narrow. The proposed framework is only applicable to the max k cut problem. It would be more meaningful if the framework could be more widely applied to other combinatorial optimization problems.\n\n- The method appears to lack novelty. The pretrain-finetune framework employed is not new and has been widely used in other contexts.\n\n- The comparison with baseline methods may not be entirely fair. I question whether the training data used are consistent with those used in ROS. Given that ROS involves a two-stage process of pretraining and finetuning, whereas other methods only include a single training step, this discrepancy could affect the validity of the comparisons.\n\n- I find the experimental section somewhat challenging to follow. The descriptions of the experimental settings are somewhat disorganized and could benefit from clearer and more structured presentation.\n\n- The absence of a related works section is notable. While it is true that research on the max k cut problem may be relatively sparse, it is still unusual to omit this section entirely. Including a discussion of related works would provide valuable context and help situate the current research within the broader field.", "other_comments_or_suggestions": "- Fig. 1 has two h6 in the initialization step of the grey box\n\n- Notations are sometimes abused. For example, \\overline{X} shows up three times with different meanings. In Def 3.1, it is a point. In Theorem 3.2, it is the globally optimal solution. In Q2, it is a high quality solution. They make me confused.\n\n- Statistics of the datasets are not given. For example, how many graphs are in the different datasets?\n\n- In the results of figure 2, which part of the datasets are used for training, which part are for finetuning, and which part are for testing? It seems that Sec. 4.1 does not figure it out.", "questions_for_authors": "- Noticing that the initial embeddings h0 are assigned by random values. I have doubt on the correctness of doing so.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "LFD7AAeVoC", "reviewer": "Reviewer_bfPu", "summary": "This paper introduces ROS, a GNN-based framework for Max-k-Cut. The authors propose a solution that relaxes the problem to a continuous space, optimizes it with a neural network, and samples a discrete solution. They compare with existing neural and non neural baselines and show they are better in terms of quality and running time.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "## Essential Reference Not Discussed\n\n**Response to R1:** \n- 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.\n- 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.\n\n**Table 1: Evaluation results on Bitcoin-OTC Datasets.**\n| Model    | Value ($k=2$) | Time (s) ($k=2$) | Value ($k=3$) | Time (s) ($k=3$) | Value ($k=10$) | Time (s) ($k=10$) |\n| - | - | - | - | - | - | - |\n| NeuroCut |1424|239.46| 1667| 242.65| 13235| 250.90|\n| PIGNN| 14587| 62.31| -| -| -| -|\n| MD| 14989| 37.15| 18448| 50.40| 21182| 105.92|\n| ANYCSP| 10678| 180.20| 14319| 180.16| 19359|180.24|\n| ROS| **15384**| **2.94**| **18585**| **2.44**| **21251**| **2.04**|\n\n## Weakness\n\n**Response to W1:**\n\n- **ROS-vanilla** (without pre-training) can directly generalize to any value of $k$ since the absence of pre-training. \n\n- **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$.\n\n- **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).\n\n- 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.\n\n**Table 2: Comparison between pre-training ways on Bitcoin-OTC Datasets.**\n| Model    | Value ($k=2$) | Time (s) ($k=2$) | Value ($k=3$) | Time (s) ($k=3$) | Value ($k=10$) | Time (s) ($k=10$) |\n| - | - | - | - | - | - | - |\n| ROS| 15384| **2.94**| 18585| **2.44**| 21251| **2.04**|\n| ROS-vanilla| **15661**| 5.24| **18977**| 4.77| **21365**| 4.43|\n| ROS-partial| 15102| 4.24| 18732| 3.93| 21308| 2.92|\n\n\n\n**Response to W2:** \n- 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. \n- 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](https://anonymous.4open.science/r/Figures_for_bfPu-9473). The results confirm that even with fine-tuning, other baselines do not surpass ROS in solution quality.\n\n**Response to W3:** We upload our code in https://anonymous.4open.science/r/ROS_anonymous-1C88/.\n\n## Reference\n[1] Rishi Rajesh Shah, Krishnanshu Jain, Sahil Manchanda, Sourav Medya and Sayan Ranu, \"NeuroCut: A Neural Approach for Robust Graph Partitioning\", in KDD, 2024.\n\n[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.", "claims_and_evidence": "1. ROS has better quality . Supported by evaluation on diverse dataset and values of k.\n2. Better running time. supported by running time plots.", "methods_and_evaluation_criteria": "Yes", "theoretical_claims": "Did not check proofs in details.", "experimental_designs_or_analyses": "Mostly it is clear. Only thing that is not clear whether baselines were fine-tuned?", "relation_to_broader_scientific_literature": "1. Proposed method does not require any ground truth.\n2. Framework uses relaxation approach, which is effective in this setup.", "essential_references_not_discussed": "[A] NeuroCUT: A Neural Approach for Robust Graph Partitioning\nRishi Shah, Krishnanshu Jain, Sahil Manchanda, Sourav Medya, Sayan Ranu\nKDD Knowledge Discovery and Data Mining(KDD), 2024\n\n[A] solves graph partitoning problem for arbitrary partitoning objectives. The approach is inductive to number of partitioing.", "other_strengths_and_weaknesses": "Weakness:\n1. Kindly clarify if model can do inference on unseen k(number of partitions). Can the model be fine-tuned to different k? If yes, how?\nFrom line 233 it seems output layer is fixed to k. \n\n2. Were the neural baselines also fine-tuned? Kindly clarify.\n\n3. Code is not shared.", "other_comments_or_suggestions": "None", "questions_for_authors": "Check weakness", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "vPlvZMdyb7", "reviewer": "Reviewer_rFKE", "summary": "The paper introduces, a GNN-based framework for solving the Max-k-Cut problem by relaxing the discrete optimization problem into a continuous optimization task. A Graph Neural Network (GNN) optimizes the relaxed problem, followed by a sampling-based algorithm to obtain a discrete solution. The authors integrate geometric landscape analysis with statistical theory to establish the consistency of function values between the continuous solution and its mapped discrete counterpart.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "## Claims And Evidence\n**Response to C1:** Please refer to \"Response to W2\" for Reviewer bfPu.\n\n## Methods And Evaluation Criteria\n**Response to M1:** \n- 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**. \n- 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.\n\n**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.\n\n**Response to M3:** Please refer to the \"response to W1\" of reviewer bfPu for details regarding the generalizability of our method to unseen $k$.\n\n## Experimental Designs Or Analysis: \nFigure 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$.\n\n\n\n## Essential References Not Discussed\nPlease see the response to M1.\n\n## Weakness\n**Response to W1:** Please see \"Response to W2\" for Reviewer bfPu.\n\n**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.\n\n**Response to W3:** Please refer to the \"response to W1\" for reviewer bfPu regarding the generalizability of our method to unseen $k$.\n\n**Response to W4:** Please see Response to M2.\n\n**Response to W5:** Please see Response to M1.\n\n**Response to W6:** We upload our code in https://anonymous.4open.science/r/ROS_anonymous-1C88/.\n\n\n## Other Comments Or Suggestions\nSince 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):\n\n**Updated Row in Table 1 in manuscripts**\n| Model| $N=100, k=2$| $N=100, k=3$| $N=1000, k=2$| $N=1000, k=3$| $N=10000, k=2$| $N=10000, k=3$      |\n| - | - | - | - | - | - | - |\n| ROS-vanilla | $132.00\\pm 1.89$ | $243.75\\pm 2.00$ | $1322.95\\pm 6.57$ | $2440.55\\pm 4.97$ | $13191.25\\pm 20.73$ | $24317.40\\pm 21.36$ |\n\n**Updated Row in Table 2 in manuscripts**\n| Model| G70 ($k=2$) | G70 ($k=3$) | G72 ($k=2$) | G72 ($k=3$) | G77 ($k=2$) | G77 ($k=3$) | G81 ($k=2$) | G81 ($k=3$) |\n| - | - | - | - | - | - | - | - | - |\n| ROS-vanilla | 9004| 9982| 6066| 7210| 8678        | 10191| 12260| 14418|\n\n**Updated Row in Table 3 in manuscripts**\n| Model| G70 ($k=2$) | G70 ($k=3$) | G72 ($k=2$) | G72 ($k=3$) | G77 ($k=2$) | G77 ($k=3$) | G81 ($k=2$) | G81 ($k=3$) |\n| - | - | - | - | - | - | - | - | - |\n| ROS-vanilla | 8989.38| 9973.75| 6140.50| 7207.13| 8744.47| 10190.37| 12278.70| 14341.25|\n\n## Questions For Authors\n**Response to Q1:** Please refer to the \"response to W1\" for reviewer bfPu.\n\n**Response to Q2:** Please see Response to M1.\n\n**Response to Q3:** Please see Response to M2.\n\n## Reference\n[1] Rishi Rajesh Shah et al., NeuroCut: A Neural Approach for Robust Graph Partitioning, in KDD.\n[2] Anton Tsitsulin et al., Graph clustering with graph neural networks. In JMLR.\n[3] Aritra Bhowmick et al, DGCLUSTER: A Neural Framework for Attributed Graph Clustering via Modularity Maximization. In AAAI.", "claims_and_evidence": "Authors show the superiority of their algorithms but it is not clear if baselines involving learning base techniques also used the pretraining and finetuning phase or not. \n\nIn addition, some direct baselines have neither been cited nor compared with.", "methods_and_evaluation_criteria": "- **Baselines:** It appears [1][2] and [3] are related and potential baselines, by suitably changing the loss/reward function. [1], in particular, does not even need the optimization function to be differentiable. Why are they not discussed and compared with?\n\n[1] Rishi Rajesh Shah, Krishnanshu Jain, Sahil Manchanda, Sourav Medya and Sayan Ranu, \"NeuroCut: A Neural Approach for Robust Graph Partitioning\", in KDD, 2024.\n\n[2] Anton Tsitsulin, John Palowitch, Bryan Perozzi, and Emmanuel Müller. 2023. Graph clustering with graph neural networks. Journal of Machine Learning Research 24, 127 (2023), 1–21.\n\n[3] Aritra Bhowmick, Mert Kosan, Zexi Huang, Ambuj Singh, and Sourav Medya. 2024. DGCLUSTER: A Neural Framework for Attributed Graph Clustering via Modularity Maximization. In Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 38. 11069–11077.\n\n- **Datasets:** None of the datasets are real. Please include real world datasets containing atleast few thousands of nodes (See [1] for example)\n\n- **Generalizability to $k$:** It appears that the method needs to know the number of partitions ($k$) before inference. Specifically, it needs to train for each specific value of $k$ since it does not generalize to unseen $k$ at inference time. This is evident from line 232 where the output embedding is $\\mathbb{R}^{k\\times N}$.", "theoretical_claims": "Seems intuitively correct but did not go through deeply.", "experimental_designs_or_analyses": "- Could you please clarify whether Fig. 2 represents the training time or inference time. Could you please demonstrate scalability with respect to ground-truth generation, training time and inference time explicitly and compare with non-neural approaches. Non-neural approaches generalize to any value of $k$. Hence, it is important to look at the scalability of all three dimensions to evaluate the practical value of this work.", "relation_to_broader_scientific_literature": "Earlier works try to solve maximum-k-cut problems using graph learning approaches but they seem limited to the unweighted setting while the proposed approach deals with solving weighted maximum-k-cut problems using GNN.", "essential_references_not_discussed": "As mentioned above, important related works have not been disucussed and compared to.\n\n[1] Rishi Rajesh Shah, Krishnanshu Jain, Sahil Manchanda, Sourav Medya and Sayan Ranu, \"NeuroCut: A Neural Approach for Robust Graph Partitioning\", in KDD, 2024.\n\n[2] Anton Tsitsulin, John Palowitch, Bryan Perozzi, and Emmanuel Müller. 2023. Graph clustering with graph neural networks. Journal of Machine Learning Research 24, 127 (2023), 1–21.\n\n[3] Aritra Bhowmick, Mert Kosan, Zexi Huang, Ambuj Singh, and Sourav Medya. 2024. DGCLUSTER: A Neural Framework for Attributed Graph Clustering via Modularity Maximization. In Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 38. 11069–11077.", "other_strengths_and_weaknesses": "**Strengths:** \n\n- The paper presents a GNN-based framework for solving the weighted Max-k-Cut problem, converting a discrete optimization task into a continuous one for easier processing, which is interesting and novel\n\n- Compared to the baselines, the results look good both in efficiency and quality.\n\n**Weakness:**\n\n- The authors have not mentioned if leaning-based baselines are used pertaining and fine-tuning steps separately or not.\n- Figure 2 appears to be inference time. Please report time for pre-training, training/fine-tuning, etc.\n- The method does not generalize to unseen $k$. This appears to be a serious limitation.\n- The benchmark datasets do not include any real-world dataset\n- Important works have not been discussed and compared to.\n- Code base is not shared and hence reproducibility is hampered.", "other_comments_or_suggestions": "In Tables 2,3, and 4, you can directly put ROS without finetuning results. It will enhance readability.", "questions_for_authors": "The key reasons for my current rating are below. I would be happy to revisit the rating if the questions raised below are satisfactorily addressed.\n\n1Justify why the inability to generalize to unseen $k$ during inference is not a severe limitation.\n2. Please discuss (and compare with unless there are obvious reasons not to) the missing baselines discussed above.\n3. Include real world datasets.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "WnFVtXUiOQ", "reviewer": "Reviewer_cFx5", "summary": "This paper proposes ROS, a GNN-based L2O method, to obtain high-quality max-$k$-cut solutions. The one-hot encoding of each node is relaxed to continuous variables, a GNN is used to do node classification task, i.e., assigning nodes into $k$ partitions, and the continuous output from GNN is then used to construct a feasible solution by a random sampling step. Theoretical result guarantees the existence of feasible max-$k$-cut solution when a globally optimal continuous solution is found. Numerical results on various benchmarks show that ROS can indeed provide high-quality solutions in an efficient way.\n\n## update after rebuttal\n\nMy concerns are resolved by those extra experimental results and clarifications. A revised version with those details is acceptable.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "## Claims And Evidence\n**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](https://anonymous.4open.science/r/Tables_For_cFx5-357C/)), explicitly comparing the continuous objcetive values and their integer counterparts. \n\n## Methods And Evaluation Criteria\n**Response to M1:** See \"Response to Q1\" for Reviewer zJRf.\n\n## Experimental Designs Or Analyses\n**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.\n\n**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.\n\n**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](https://anonymous.4open.science/r/Tables_For_cFx5-357C/) show that:\n- ROS consistently achieves the best performance in terms of both solution quality and computational efficiency.\n- Even under extreme perturbations, ROS maintains its advantage over baselines, demonstrating its robustness in handling arbitrary edge weights.\n\n## Relation To Broader Scientific Literature and Essential References Not Discussed\nWhile [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.\n\n## Weakness\nAs shown in Table 3 of the manuscript and Tables 3–6 in [anonymous link](https://anonymous.4open.science/r/Tables_For_cFx5-357C/), 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.\n\n## Other Comments Or Suggestions\n**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.\n\n**Response to C2:** We will replace the order of two literatures.\n\n## Questions for Authors\n- 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.\n- 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.\n\n## Reference \n[1] Michael R, et al. A Continuous Relaxation for Discrete Bayesian Optimization[J].", "claims_and_evidence": "Claim 1 [the consistency of function values between continuous solution and its mapped counterpart]: theoretically supported in Theorem 3.2, but lack of empirical evidence. The reason is that Theorem 3.2 requires a global optimum for the relaxation, which is practically learned by a GNN. It will be more convincing if the authors could show the difference between objective values of continuous solutions and their integer counterparts.\n\nClaim 2 [ROS can efficiently scale to large instances]: supported in Section 4.\n\nClaim 3 [ROS exhibits strong generalization capabilities]: supported in Section 4.", "methods_and_evaluation_criteria": "The overall idea of ROS makes sense to me. My only question is about the initial node embeddings. Random embeddings seem to be quite casual and make random seed affect both the training and evaluation. Is it more reasonable to use more meaningful embeddings, e.g., including some neighborhood information?", "theoretical_claims": "I roughly checked all proofs and they look correct.", "experimental_designs_or_analyses": "I have several concerns about the experiments.\n\n- The extra cost of preparing training dataset is important to evaluate the effectiveness of a L2O method, which is missing in the paper.\n\n- The experiments only test $k=2,3$, making it unclear if ROS could be applied for larger $k$.\n\n- For the weighted benchmark, the edge weights are constrained to $\\pm 1$ with 10\\% perturbations. Are there any reasons for choosing such specific settiing? Especially observing that ROS achieves the best performance on this setting compared to other methods.", "relation_to_broader_scientific_literature": "ROS follows a standard GNN-based L2O setting. The idea of solving relaxation and then retrieving an integer solution nearby is commonly used in integer programming. The random sampling step as shown in Algorithm 1 is already in the literature, e.g., see https://arxiv.org/pdf/2404.17452.", "essential_references_not_discussed": "The discussion about max-$k$-cut is quite sufficient. But the discussion about the idea of relax-optimize-and-sample in other fields is missing.", "other_strengths_and_weaknesses": "**Strengths**\n\n- The paper is well-written and easy to follow.\n\n- Theoretical results are solid.\n\n- Simple setting results in good performance over various scenarios.\n\n**Weaknesses**\n\nI already stated most concerns in above. Additionally, the experimental results are unable to show that ROS could generate better solutions compared to other methods except for faster computational time. The word \"high-quality\" is quite vague. Intuitively, when the objective value of one solution is approaching to the global optimum, it is much harder to further improve it. It is unclear if ROS already gives meaningful or useful solutions to any practical problems.", "other_comments_or_suggestions": "- In lines 197-199, after executing Algorithm 1 T times, should one choose the solution with the hightest objective value? if the objective is still defined as Eq. (1).\n\n- The order of references in second column of lines 201-202.", "questions_for_authors": "I already asked all questions in previous sections. They are majorly about clarifications of experiments for better evaluation the importance of ROS, and how well the theoretical contribution is aligned in practice.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This submission proposes the Relax-Optimize-and-Sample (ROS) framework to solve the Max-k-Cut problem. Unlike relaxation techniques that do not guarantee equivalence between relaxation solutions and solutions of the original problem, ROS involves a sampling-based construction algorithm to map the relaxed solution (produced using a GNN) back to a high-quality solution in the original problem space. The authors provide theoretical guarantees on consistency. Experiments in settings of up to 20K nodes show fast computational time, and reasonable performance (while ROS does not "dominate" with respect to every experiment, its benefits are demonstrated with respect to generalizability across instances). 

Reviewers initially raised concerns about the experimental setups (lack of real-world experiments) and fairness of baseline comparisons, but these concerns were mitigated during author-reviewer discussion, notably via the addition of a real-world Bitcoin-OTC dataset (with $k=10$). They also expressed some concerns about the clarity of the experiments section (which should be addressed in the revised version). However, overall, reviewers were convinced of the relevance and significance of the contribution.
Decision: Accept (poster)