{"id":"0511a8c1-c703-4cf0-a8fc-3cc9cc375fc4","arxiv_id":"2412.05146","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":6,"one_line_summary":"ROS relaxes Max-k-Cut to continuous simplex, optimizes via GNN, and samples back, achieving fast large-scale solving with expectation-preserving mapping.","lead":"ROS is a graph neural network framework that solves large Max-k-Cut problems by first relaxing the discrete partition to continuous probabilities, optimizing that relaxation, then sampling back to a discrete cut. It combines a pre-train and fine-tune strategy with a theoretical guarantee that the expected objective value of the sampled cut matches the continuous solution.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Abstract's unqualified 'outperforming state-of-the-art' claim is contradicted by the paper's own Gset tables, where MOH and LPI beat ROS on essentially every unweighted instance.","rationale":"Good-faith reading: the framework is a plausible engineering contribution, and the theoretical statements are correct but modest. The multi-affine structure makes Theorem 3.2 a flatness statement only around global optima of the relaxation, and Theorem 3.3 is an exact expectation identity for categorical sampling; neither theorem says anything about the quality of the GNN's solution. The paper therefore leans on empirical evidence for its main 'outperforming SOTA' claim, and that evidence is internally inconsistent on the standard unweighted Gset benchmark: classical heuristics MOH and LPI beat ROS on nearly every instance, and ANYCSP also beats ROS on random regular graphs. The reader's weakest assumption—that the GNN must reach near-global optima—is real, but the more decisive, directly checkable problem is the unqualified superiority claim in the abstract. A conditional verdict asking for honest, benchmark-specific claims (e.g., restricting SOTA claims to weighted large instances or reporting gaps against MOH/LPI) is appropriate. I do not see grounds to move beyond the reader's conditional verdict, nor grounds for rejection: the method does offer genuine speed advantages and competitive performance on weighted large graphs, and the tables provide enough data for a corrected, more accurate presentation.","tokens_in":30288,"tokens_out":7763,"duration_ms":90234,"concrete_test":"Re-analyze Tables 6 and 7 as-is: for every Gset instance, compute the relative gap (ROS - best_baseline)/best_baseline using MOH, LPI, and ANYCSP as baselines, and report the mean and median gap separately for k=2 and k=3. If the mean/median gap is negative, the abstract's unqualified 'outperforming state-of-the-art' claim should be formally revised to a runtime-and-weighted-instances claim. This requires no new experiments, only a transparent aggregate of the data already in the paper.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central practical claim is that ROS outperforms state-of-the-art algorithms. The paper's own experiments contradict this on the standard unweighted Gset benchmark. In Table 6 (k=2), MOH and LPI achieve higher cut values than ROS on essentially every instance, e.g., G1: MOH/LPI 11624 vs ROS 11395; G22: 13359 vs 13007; G70: 9544/9594 vs 8916. In Table 7 (k=3), MOH again dominates, e.g., G1: 15165 vs ROS 14961; G6: 2632 vs 2361. ROS is competitive mainly on weighted Gset perturbations and on runtime, not on solution quality. The theoretical results do not bridge this gap: Theorem 3.3 only states E[f(hatX)] = f(X) for whatever continuous X is produced, and Theorem 3.2 requires a global optimum of a non-convex, NP-hard relaxation. The GNN optimizer is trained locally with no guarantee of reaching such a global optimum. Consequently, the 'superior performance' half of the central claim rests entirely on empirical evidence that the paper's own tables undermine in the most standard benchmark.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces ROS, a three-stage heuristic for weighted Max-k-Cut: relax the one-hot assignment to a product of probability simplices, optimize the resulting non-convex objective Tr(XWX^T) with a GNN using a pre-train-plus-fine-tune protocol, and finally map the continuous solution to a discrete cut by independent categorical sampling per node, repeated T times. The theoretical component consists of Theorem 3.2, which states that a global optimum of the relaxation is flat on its support face, so that all integer points in that face have the same objective value, and Theorem 3.3, which states that the random sampling map preserves the objective value in expectation. Experiments are reported on random regular graphs, the Gset benchmark, COLOR graphs, and Bitcoin-OTC, with runtimes of a few seconds for instances up to 20,000 nodes. The abstract and introduction claim that ROS outperforms state-of-the-art algorithms.","tokens_in":30454,"tokens_out":5011,"duration_ms":57698,"significance":"If the efficiency claims hold, ROS is a useful scalable heuristic for weighted Max-k-Cut, and the two theorems give a clean consistency statement for the relaxation-sampling pair: Theorem 3.2 is a correct multi-affine support-containment argument, and Theorem 3.3 is a direct expectation calculation. The paper ships a code link, reports ablations for sampling trials and pre-training, and covers a broad set of benchmarks. However, the headline 'outperforming state-of-the-art' claim is contradicted by the paper's own unweighted Gset tables, and the theoretical guarantees require a global optimum of an NP-hard non-convex problem that the GNN optimizer is not guaranteed to deliver. These issues make the contribution sound in its narrow theoretical statements but over-claimed in its central practical message.","major_comments":[{"comment":"The claim that ROS 'outperforms state-of-the-art algorithms' is contradicted by the paper's own experiments on the standard unweighted Gset benchmark. In Table 6, MOH and LPI achieve higher cut values than ROS on essentially every instance, for example G1 (MOH/LPI 11624 vs. ROS 11395), G22 (13359 vs. 13007), and G70 (9544/9594 vs. 8916). In Table 7 for k=3, MOH again dominates, for example G1 (15165 vs. 14961) and G6 (2632 vs. 2361). The legitimate claim from these tables is that ROS is much faster than MOH and LPI, not that it obtains better solutions. The abstract and Section 1's 'Superior Performance' bullet should be revised to state the actual trade-off, for example 'competitive quality at a fraction of the runtime' or 'outperforming state-of-the-art algorithms on weighted instances while being orders of magnitude faster on unweighted instances.' As written, the central claim of the paper is not supported by its own evidence.","section":"Abstract; §4.2.2; Appendix D, Tables 6 and 7"},{"comment":"The theoretical guarantee in Theorem 3.2 applies only to a globally optimal solution X* of the relaxed problem P, which the paper itself notes is NP-hard to solve (Q1). The actual pipeline replaces global optimization with Adam-based training of a GNN, and Section 3.3 provides no convergence guarantee, no approximation guarantee, and no bound on the distance between the GNN output and a global optimum. Consequently, the consistency results do not apply to the solution produced by the method, and Theorem 3.3 only states that sampling preserves the objective value of whatever continuous point the GNN found. To make the practical claim load-bearing, the authors should provide evidence that the GNN solutions are close to global optima of P, for example by comparing f(H_Phi^(L); W) against exact or SDP-based bounds on small instances, or against the values obtained by running a global/local optimizer from many restarts. Without this, the framework's practical effectiveness rests on an unverified assumption.","section":"Theorem 3.2 and Section 3.3 (Q1)"},{"comment":"The comparison framework mixes solution quality and runtime without a clear quality-time trade-off analysis. Tables 6 and 7 show that MOH and LPI are allowed thousands of seconds on large instances, while ANYCSP is capped at its default 180-second limit; ROS runs in seconds. A reader cannot tell from the current tables whether ROS would remain competitive if the baselines were given the same short time budget, or whether the 'outperforming' claim is purely a runtime claim. The authors should either report time-limited comparisons (e.g., best solution within 5, 30, and 180 seconds) or a Pareto plot of cut value versus time. This is especially important because the paper's own ROS-vanilla variant beats the pretrained ROS on most random-regular and weighted-Gset instances in Tables 2 and 3, so the reported quality of ROS is not even the best obtainable within the proposed family.","section":"§4.2.2 and §4.3"}],"minor_comments":[{"comment":"The same label P is used for both the discrete problem and the relaxed problem; please use distinct labels such as P_discrete and P_relaxed to avoid confusion in the statement of Theorem 3.2 and the surrounding discussion.","section":"§3.1"},{"comment":"The expression '/BD (X~·i = X~·j)' appears to be a rendering artifact for an indicator function; please replace it with the standard indicator notation.","section":"Appendix C, Eq. (6)"},{"comment":"Several entries in Table 5 contain the string '/enc-37' (and '/enc-33'), which appears to be a PDF encoding artifact; the table should be regenerated with correct symbols.","section":"Table 5"},{"comment":"Figure 2 contains label typos: 'Gene(i' in panel (a), 'ROS- anilla' in panel (b), and 'Ti e (s)' in panel (c). These should be corrected.","section":"Figure 2"},{"comment":"The COLOR dataset reference is listed as 'Micheal, T.'; the correct spelling is 'Michael'. Also, the Gset reference is formatted as 'Y e, Y .' with stray spacing and should be 'Ye, Y.'","section":"References"},{"comment":"The sentence 'The ROS model is pre-training using Adam' should be 'The ROS model is pre-trained using Adam'.","section":"§4.1"}],"recommendation":"major_revision","confidential_remarks":"The two theorems are correct as stated and are not circular, but the paper's advertised practical claim is not supported by its own benchmark tables. I would advise the editor that the revision must either substantially soften the 'outperforms state-of-the-art' language or add a time-limited comparison that substantiates a specific quality-time claim. The theoretical section could also be strengthened by explicitly stating that Theorem 3.2 is a property of global optima and does not apply to the GNN's output."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Quick take: this is a legitimate learning-to-optimize contribution for Max-k-Cut, with two correct theorems and real speed gains on large weighted instances. The abstract's claim that ROS 'outperforms state-of-the-art algorithms' is not supported by the paper's own Gset tables; the strongest baselines beat it on cut value there. The paper deserves a serious referee, but the main claim needs to be rewritten.\n\nWhat's genuinely new: the Relax-Optimize-and-Sample pipeline—probability simplex relaxation, GNN trained unsupervised, pre-train/fine-tune to warm-start, and categorical sampling with T trials—is a coherent engineering package. PI-GNN, ANYCSP and related work all use pieces of this, but the transfer-learning scheme and the explicit sampling-theoretic analysis together are not in prior work as far as I can tell. The theorems are real: Theorem 3.2 correctly shows that a global optimum of the non-convex simplex relaxation has a flat neighborhood (extending Carlson–Nemhauser), and Theorem 3.3 is a clean expectation identity. Both proofs in the appendix check out. The empirical speed is impressive: 10k–20k node instances in seconds, roughly 1–2 orders of magnitude faster than MD or PI-GNN. The framework handles arbitrary signed weights, which many baselines cannot.\n\nNow the soft spot, in proportion: it's the performance claim, not the machinery. On unweighted Gset (Tables 6 and 7), MOH and LPI achieve higher cut values than ROS on essentially every instance—G70 k=2: 9544/9594 vs. 8916, G81 k=3: 16321 vs. 14464. On weighted perturbed Gset and random regular graphs, ROS is competitive or better, especially versus L2O baselines, but on the standard benchmark it clearly loses in solution quality. The paper's own ablation adds another wrinkle: ROS-vanilla (no pre-training) often gives higher cut values than ROS, so pre-training buys speed, not quality.\n\nThe theory doesn't rescue the performance claim. Theorem 3.2 needs a global optimum of the NP-hard relaxation; the GNN is a heuristic, so the flatness result has no direct leverage on the actual solutions. Theorem 3.3 is an expectation equality, not a high-probability guarantee, and with T=100 samples it's a heuristic rounding step. The paper acknowledges Q1's NP-hardness, so this isn't hidden—it's just that the abstract oversells.\n\nWho should read this: people working on GNN-based combinatorial optimization or fast large-scale Max-k-Cut heuristics will find the speed results and the transfer scheme useful, and the theorems are a nice sanity check. It deserves peer review: the engineering is reproducible (code is public), the experiments are documented honestly in tables, and a referee could ask for a claim-rewrite plus a clearer separation of speed vs. quality. I'd send it out.","headline":"A solid engineering paper with correct but modest theory, undermined by an abstract overclaim that its own tables contradict.","tokens_in":31061,"tokens_out":2779,"would_cite":false,"duration_ms":27307,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C27","90C35","68T07","90C26"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper proposes the ROS framework, which solves weighted Max-k-Cut by relaxing one-hot labels to a probability simplex, optimizing with a GNN, and sampling back under an expectation-preservation guarantee.","keywords":["Max-k-Cut","probability simplex relaxation","graph neural networks","random sampling","combinatorial optimization","signed edge weights","transfer learning","large-scale optimization"],"falsifier":"On small graphs (a few dozen nodes) with arbitrary signed edge weights, compute the true maximum cut value by exhaustive enumeration and also compute the global optimum of the relaxed simplex problem with a dense global solver; then run ROS from several random initializations. If the fine-tuned GNN's relaxed objective value is ever strictly below that global optimum, or if the best sampled cut fails to reach the true integer optimum on an instance where the relaxation optimum equals it, the chain of consistency guarantees would not apply to the solutions ROS actually produces.","tokens_in":29997,"feed_emoji":"✂️","tokens_out":11880,"duration_ms":112749,"temperature":0.7,"pith_summary":"Max-k-Cut asks to split a graph's vertices into k parts so that the total weight of edges crossing different parts is as large as possible; with arbitrary signed weights it generalizes Max-Cut and is NP-complete. This paper proposes the Relax-Optimize-and-Sample (ROS) framework, which replaces each node's one-hot choice with a probability distribution over the k labels, trains a graph neural network on the resulting continuous objective, and then samples each node's label from its learned distribution, keeping the best cut found. The authors try to establish that this continuous-to-discrete mapping is faithful: at a global optimum of the relaxed problem the objective is constant across an entire induced neighborhood, and the sampling step is unbiased in expectation, so solving the relaxation does not silently change the cut value. They report that the resulting solver handles weighted instances with up to 20,000 nodes in a few seconds and generalizes across graph types, which would make it a practical alternative to semidefinite-programming, heuristic, and earlier learning-based methods.","feed_headline":"GNN solves 20,000-node Max-k-Cut in seconds","feed_subtitle":"A simplex relaxation plus unbiased sampling preserves cut quality while shrinking solve time from minutes to seconds","key_machinery":"The load-bearing object is the induced neighborhood $N(X)$ of a matrix $X$ in the probability simplex: the set of all feasible matrices whose non-zero support is contained in that of $X$. Theorem 3.2 establishes that at a global optimum $X^{*}$ of the relaxed problem, the objective is flat on $N(X^{*})$, which is what makes a fractional optimum convertible to an integer cut without objective loss. The companion random sampling algorithm draws each column independently from the categorical distribution given by the relaxed matrix; Theorem 3.3 proves this step is unbiased. The practical engine is a two-layer GNN with edge-weight-aware aggregation, trained with a pretrain-plus-finetune scheme that warm-starts each instance from a model pretrained on small random regular graphs and transfers across graph sizes and types.","core_discovery":"The paper's central discovery is a consistency theorem for a naive-looking relaxation. Writing the Max-k-Cut objective as $f(X;W) = \\mathrm{Tr}(XWX^{\\top})$ over matrices whose columns are one-hot vectors, the authors relax the feasible set to the Cartesian product of k-dimensional probability simplices and study the induced neighborhood $N(X^{*})$ of a global optimum $X^{*}$: all matrices that keep the same zero-pattern of non-zero entries. Theorem 3.2 shows the relaxed objective is constant on $N(X^{*})$, so a fractional global optimum contains integer solutions with exactly the same objective value; Theorem 3.3 shows that independently sampling each column of any $X$ from its categorical distribution gives $E_{\\hat X}[f(\\hat X;W)] = f(X;W)$. Together these results say the relaxation and the sampling step do not introduce a gap in objective value, provided the relaxed problem is solved to global optimality. The paper pairs this with a GNN parametrization and a pretrain-plus-finetune strategy, and reports cut values and runtimes showing that this recipe scales to 20,000-node graphs in seconds across random regular graphs, Gset, COLOR, and Bitcoin-OTC instances.","pith_inferences":["Editorial inference: Because Theorem 3.3 only fixes the mean of the sampled cut value, variance-reduction schemes—such as sampling labels in a graph-aware order or conditioning on previously sampled nodes—should improve the best-of-T cut without changing the expectation; the paper does not test this.","Editorial inference: The real bottleneck is the GNN's ability to solve the non-convex relaxation, not the relaxation or sampling step itself; a stronger classical optimizer on the same simplex would reveal how much of ROS's reported advantage comes from the GNN rather than from the relaxation.","Editorial inference: If flat-basin behavior extends to near-global optima or to other objectives, the relax-optimize-sample recipe could carry over to related graph partitioning problems such as Min-k-Cut or balanced partitioning; the paper only gestures at this as future work."],"forward_implications":["Weighted Max-k-Cut instances with up to 20,000 nodes can be solved in seconds on a single GPU, roughly ten times faster than the mirror-descent baseline and about one hundredth of PI-GNN's reported time on the same cases.","Because the relaxation lives on a probability simplex, the same pipeline handles any number of partitions k and arbitrary signed edge weights, which QUBO-based methods (k=2 only) and the unweighted-only ANYCSP baseline cannot do.","Pre-training on small random regular graphs transfers to larger and structurally different graph families, cutting fine-tuning time by roughly 40% on the Gset instances while keeping cut values close to those of the no-pretraining variant.","The sampling step is cheap and stable: cut values stabilize after about five sampling rounds and remain essentially unchanged through the 100 trials used in the experiments, so best-of-T sampling adds only milliseconds even at 20,000 nodes."],"supporting_citations":[{"why":"Supplies the classical result that a global optimum of the relaxed problem has an integer counterpart, which Theorem 3.2 extends to the induced neighborhood.","marker":"Carlson & Nemhauser (1966)"},{"why":"Provides the SDP relaxation and rounding baseline for Max-Cut that ROS's simplex relaxation and sampling approach is compared against.","marker":"Goemans & Williamson (1995)"},{"why":"Extends the SDP rounding approach to Max-k-Cut; the paper argues this baseline becomes impractical at large scale.","marker":"Frieze & Jerrum (1997)"},{"why":"Provides the graph neural network architecture used to parametrize and optimize the relaxed objective.","marker":"Morris et al. (2019)"},{"why":"Defines the Lovász-extension relaxation used as a theoretical contrast; the paper argues it does not give the same consistency guarantees for arbitrary k and signed weights.","marker":"Bach (2013)"},{"why":"Supplies the PI-GNN QUBO baseline, the main learning-based comparison for weighted Max-Cut, as well as the random regular graph test instances.","marker":"Schuetz et al. (2022)"},{"why":"Supplies the ANYCSP baseline, the strongest large-scale comparison on unweighted instances, and the paper notes it cannot handle weighted edges.","marker":"Tönshoff et al. (2023)"},{"why":"Represents the prior probabilistic-penalty learning approach whose sampling step ROS distinguishes from its own unbiased sampling.","marker":"Karalias & Loukas (2020)"},{"why":"Supplies the Gset benchmark graphs used to test scalability, weighted variants, and generalization.","marker":"Y e (2003)"},{"why":"Supplies the Bitcoin-OTC signed network dataset used to demonstrate performance with arbitrary signed edge weights.","marker":"Kumar et al. (2016)"}],"fun_headline_variants":["GNN relax-optimize-sample: 20k-node Max-k-Cut in seconds","No-gap GNN relaxation for Max-k-Cut scales to 20k nodes","Max-k-Cut: GNN finds high-quality cuts in seconds on 20k nodes","ROS: GNN with provable consistency for large Max-k-Cut"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The practical claims stand on the unproven assumption that the GNN optimizer, after pretraining and fine-tuning, finds a relaxed solution close enough to a global optimum of the non-convex simplex problem that the flat-basin and unbiased-sampling theorems still deliver competitive cuts.","fun_headline_variants_meta":{"raw":{"variants":["GNN relax-optimize-sample: 20k-node Max-k-Cut in seconds","No-gap GNN relaxation for Max-k-Cut scales to 20k nodes","Max-k-Cut: GNN finds high-quality cuts in seconds on 20k nodes","ROS: GNN with provable consistency for large Max-k-Cut"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000332,"raw_usage":{"total_tokens":1882,"prompt_tokens":1013,"completion_tokens":869,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":629,"completion_tokens_details":{"reasoning_tokens":779}},"tokens_in":629,"tokens_out":869,"duration_ms":8878,"temperature":1.0,"reasoning_tokens":779,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T20:52:34.405489+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"On small graphs (a few dozen nodes) with arbitrary signed edge weights, compute the true maximum cut value by exhaustive enumeration and also compute the global optimum of the relaxed simplex problem with a dense global solver; then run ROS from several random initializations. If the fine-tuned GNN's relaxed objective value is ever strictly below that global optimum, or if the best sampled cut fails to reach the true integer optimum on an instance where the relaxation optimum equals it, the chain of consistency guarantees would not apply to the solutions ROS actually produces.","supporting_citations":[{"cited_title":"However, t heir reliance on large-scale semidefinite programming limi ts practical scalability and makes them less effective on mode rn large-scale instances","cited_arxiv_id":null,"evidence_quote":"Extends the SDP rounding approach to Max-k-Cut; the paper argues this baseline becomes impractical at large scale."},{"cited_title":"Seminal SDP-based methods, such as Goemans-Williamson (Goemans & Williamson,","cited_arxiv_id":null,"evidence_quote":"Defines the Lovász-extension relaxation used as a theoretical contrast; the paper argues it does not give the same consistency guarantees for arbitrary k and signed weights."},{"cited_title":"S., and Falout- sos, C","cited_arxiv_id":null,"evidence_quote":"Supplies the Bitcoin-OTC signed network dataset used to demonstrate performance with arbitrary signed edge weights."}],"review_version":1}