{"id":"1749d667-8a70-4030-887b-f7ab02197800","arxiv_id":"1908.05767","paper_version":1,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":5,"one_line_summary":"Unsupervised graph neural networks match the cut quality of the Goemans-Williamson SDP on random regular graphs, while extremal optimization achieves the best cuts.","lead":"Graph neural networks trained without labels produce max-cut solutions on random regular graphs that are close in quality to the classical Goemans-Williamson SDP, while a physics-inspired local search called extremal optimization performs best. The paper is a benchmark that shows unsupervised neural networks can hold their own on hard combinatorial problems, even when there is no planted structure to learn.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The claim that 'GNNs are comparable to SDP' is not consistently supported by the reported point estimates: at n=500,d=20 the better GNN trails SDP by ~0.05 in P, and no error bars or seed variance are reported.","rationale":"The reader's weakest assumption is the finite-n validity of the Dembo et al. asymptotic formula used to define P. That is a legitimate concern for the 'closer to asymptotic optimum' language, but it is not the main threat to the method-versus-method comparison, because every table row fixes n and d; ranking by P is then identical to ranking by cut size. The more load-bearing issue is that the reported evidence is a set of unquantified point estimates and that the two GNN variants behave very differently. For example, Table 1 at n=500,d=20 gives SDP 0.6742 versus GNN relaxation 0.6136 and policy gradient 0.6259, a gap of roughly 0.05-0.06 P; at d=15 the relaxation gap is 0.071. If the standard error over 1000 graphs is small, these are substantive gaps, and 'comparable' would require a defined threshold. If the GNN was trained only once per configuration, seed variability could be comparable to the gap. The policy-gradient variant also trails SDP by 0.083 at d=10, so the broad phrase 'GNNs attain comparable performance' is at best regime-dependent and variant-dependent. These issues are addressable by rerunning with multiple seeds, reporting confidence intervals, and stating train/test disjointness. The CONDITIONAL verdict therefore remains appropriate, but the condition should focus on statistical support for the relative comparison rather than mainly on the asymptotic P* yardstick. I see no evidence of internal inconsistency in the algorithms themselves, and the released code is a positive factor, but the headline comparison is not yet quantified enough to be taken as established across the full tested range.","tokens_in":9959,"tokens_out":12318,"duration_ms":133266,"concrete_test":"Re-run the GNN pipeline for n=500 at d=20,15,10,5,3 with 10 independent training seeds and fresh 5000-graph training sets per seed, then evaluate on a fresh held-out set of 1000 graphs per (n,d), reporting P for both variants as mean +/- 2SE. Also verify in the released code that the evaluation graphs are disjoint from the training graphs. If the SDP-GNN gap at d=20 and d=15 remains above 0.02 for both variants with non-overlapping intervals, the abstract should be revised to claim comparability only in sparse regimes; if the gap collapses, the dense-regime claim was an artifact of a single run.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim is that Graph Neural Networks attain performance comparable to the Goemans-Williamson SDP, but the only evidence is Tables 1-3, which list single point estimates of P. The paper reports no standard deviations, confidence intervals, or number of independent GNN training runs, and it never states whether the 1000 evaluation graphs are disjoint from the 5000 training graphs. More importantly, the point estimates themselves do not support a broad 'comparable' reading. For n=500, the better GNN variant trails SDP by 0.049 P at d=20 and by 0.071 P at d=15, while at d<=5 it slightly leads SDP; the policy-gradient variant trails SDP by 0.083 P at d=10 (Table 1 and Table 3). Thus 'GNNs' denotes two variants whose performances differ by up to roughly 0.07 P, and the SDP-minus-GNN gap changes sign with d. Without a stated threshold for 'comparable,' an explicit aggregation rule over the two variants, and a statistical uncertainty statement, the abstract's headline comparison is not established. The reader's finite-n Dembo/yardstick concern is real for the 'closer to asymptotic optimum' statements, but it does not drive the method-vs-method ranking, because P is a monotone transformation of cut size at fixed (n,d). The load-bearing gap is therefore the missing uncertainty quantification and the over-broad aggregation of two distinct GNN variants.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper experimentally compares three methods for max-cut on random d-regular graphs: a line-graph neural network (GNN) trained with two unsupervised losses (a relaxation loss and a policy-gradient loss), the Goemans–Williamson semidefinite programming (SDP) relaxation with random rounding, and extremal optimization (EO). Performance is measured through the normalized statistic P defined in Eq. (9), which compares the cut value to the Dembo et al. asymptotic constant P*. The authors report that GNNs attain performance comparable to the SDP, that EO consistently outperforms both, and that all methods produce cuts closer to the asymptotic optimum when graphs are sparser and larger. The paper includes a derivation of the two GNN losses and points to publicly available code.","tokens_in":10248,"tokens_out":6412,"duration_ms":54652,"significance":"If the headline claims were backed by adequate statistical evidence, this would be a useful experimental contribution on the applicability of unsupervised GNNs to NP-hard optimization on random instances, complementing existing supervised GNN results on the stochastic block model. The derivation of the two unsupervised losses is correct, and the use of a known asymptotic benchmark to evaluate heuristics is an appropriate strategy. The authors also make their code publicly available, which aids reproducibility. However, the reported tables contain single point estimates without error bars, confidence intervals, or variance over training runs, so the comparative claims are difficult to assess; the evidence as it stands does not establish the abstract's strongest statements.","major_comments":[{"comment":"The central claim that GNNs attain 'comparable' performance to SDP is not supported by the reported point estimates alone. Tables 1–3 give a single P value per method per (n,d) with no standard deviations, confidence intervals, or number of independent GNN training runs, and the two GNN variants (relaxation and policy gradient) differ by up to about 0.07 P (e.g., at n=500, d=5 in Table 1, relaxation gives 0.7014 while policy gradient gives 0.6682). The SDP-minus-GNN gap changes sign with d (e.g., at n=500, d=20 the policy-gradient GNN trails SDP by about 0.048, while at d=5 the relaxation GNN leads SDP by about 0.012), so without a pre-specified 'comparable' threshold and an explicit aggregation rule over the two variants, the abstract's headline is not established.","section":"§3.1, Tables 1–3; abstract"},{"comment":"The text states that 'in both cases, the computed P for all three methods increase as the node size n increases,' but Tables 2 and 3 contradict this. For d=3, SDP P drops from 0.7091 at n=200 to 0.7015 at n=500, and the policy-gradient GNN drops from 0.7010 at n=200 to 0.6928 at n=500. For d=10, SDP P drops from 0.6919 at n=200 to 0.6820 at n=500, and the policy-gradient GNN drops from 0.6598 at n=200 to 0.5989 at n=500. The claim in the abstract that all methods improve with larger n is therefore contradicted by the reported data.","section":"§3.1, Tables 2 and 3"},{"comment":"The conclusion that 'extremal optimization is the most computationally efficient' is unsupported by any runtime data in the paper. The only complexity statement is a citation of Boettcher and Percus's O(N) claim, but the experimental section fixes EO's iteration budget at tmax = 10^4 n and does not report wall-clock times, iteration counts to convergence, or comparable measurements for SDP and the GNN. A claim about computational efficiency requires at least a runtime comparison.","section":"§4"},{"comment":"The manuscript does not state whether the 5000 training graphs are disjoint from the 1000 evaluation graphs, nor the number of GNN training runs, epochs, or random initializations. Without this information, the reader cannot assess whether the reported GNN numbers are representative or whether they are selected from multiple runs. This is particularly important because the two GNN variants are stochastic and the evaluation set is fixed.","section":"§3"}],"minor_comments":[{"comment":"Several typos appear throughout, such as 't echniques' in the abstract, 'they where first proposed' in the Introduction, and 'of and edges connecting' in §2.2; a full proofreading pass is recommended.","section":"Abstract and Introduction"},{"comment":"The use of the asymptotic constant P* from Dembo et al. as a finite-n yardstick is reasonable for ranking methods at fixed (n,d) because P is a monotone transformation of cut size, but the statement that a value P closer to P* implies the cut is 'among the best possible' should be qualified, since finite-size corrections may differ across degrees.","section":"Eq. (9) and surrounding text"},{"comment":"The definitions of 'good' and 'bad' edges are counterintuitive: the text first calls edges within the same set 'good' in the context of maximizing cut, then uses them to derive a loss to be minimized; please clarify the sign convention or use neutral terminology.","section":"§2.2"},{"comment":"The claim that the SDP's fractional solution has P = 1 in the limit and 'is not an improvement over a simple spectral method' is stated without a derivation or explicit citation; please add a reference or a one-line argument to support this observation.","section":"§3, SDP fractional solution"},{"comment":"The equality in Eq. (8) is correct only as an unbiased estimator of the gradient of the expected return; the sampled objective is not the same as the expected return, so the presentation should emphasize that the empirical gradient is a stochastic estimate, not an exact equality.","section":"§2.3.2, Eq. (8)"}],"recommendation":"major_revision","confidential_remarks":"The manuscript is a concise note that presents an interesting experimental study. My main concern is that the abstract and conclusion claim comparative performance that the point estimates alone do not support, particularly without any uncertainty quantification. I recommend major revision rather than rejection: the core experimental setup is sound and the code availability is a strength, but the authors need to add variance information and either define a threshold for 'comparable' or soften the claims. I see no evidence of circularity or data fabrication."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Quick take: this is a legitimate experimental note, not a breakthrough. What's new is that they take Chen, Li, Bruna's line graph network and use it for unsupervised max-cut with two losses (relaxation and policy gradient), then compare against SDP and EO on random regular graphs. The loss derivations (Eqs. 5-8) check out; the policy-gradient step is the standard REINFORCE trick, and the relaxation is a clean continuous substitute. They evaluate against an external asymptotic constant and against fixed baseline algorithms, so there is no circularity. Code is public.\n\nCredit where due: the authors are careful to note that SDP's fractional solution isn't the right asymptotic benchmark, and they report all three methods across a reasonable sweep of n and d. The observation that EO wins consistently in these ranges is consistent with earlier physics literature and useful as a sanity check for anyone working on learned heuristics.\n\nThe soft spots are real but concentrated. The abstract says GNNs are 'comparable' to SDP, but the point estimates tell a more qualified story: at n=500, d=20 the better GNN trails SDP by about 0.049 P, and at d=15 by 0.071 P; at d<=5 it slightly beats SDP; the policy-gradient variant is worse. No error bars, no number of independent GNN training runs, no confidence intervals. The tables also do not say whether the 1000 test graphs are disjoint from the 5000 training graphs. So the paper does not currently establish the headline claim, and 'GNNs' is ambiguous because the two variants differ by as much as 0.07 P. That is a load-bearing omission, and it should be fixed with standard errors and per-variant reporting.\n\nThe reader's worry about the Dembo et al. yardstick at finite n is less concerning than it looks. Since P is a monotone transformation of cut size at fixed (n,d), method-by-method rankings are unaffected by whether P* is exact for finite n. The 'closer to asymptotic optimum' language does depend on P*, but the main comparisons stand or fall on the missing UQ, not on finite-size corrections.\n\nWho's this for? Anyone working on GNNs for combinatorial optimization will want it on the radar. It's a small result, and I wouldn't cite it as evidence that learned heuristics are competitive with SDP. A serious referee should engage with it, because the experiment is reproducible and the question is worth asking; but it needs a revised version with uncertainty quantification and a more precise claim.","headline":"A small, honest benchmark applying an existing LGNN architecture to unsupervised max-cut; the math is right and the code is public, but the 'comparable to SDP' claim is not actually established without error bars and a clear aggregation rule.","tokens_in":10821,"tokens_out":2916,"would_cite":false,"duration_ms":28174,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C80","68T07","90C22","90C27","68R10"],"pacs":[],"model":"deepseek-v4-flash","headline":"Unsupervised graph neural networks match the Goemans-Williamson SDP on random max-cut instances.","keywords":["max-cut","random regular graphs","graph neural networks","semidefinite programming","extremal optimization","unsupervised learning","policy gradient","asymptotic optimality"],"falsifier":"Solve small random d-regular graphs exactly (for example all $n \\le 30$ with $d = 3$ and $10$) and compare the three methods' $P$ values against the true maximum cut; if the methods' ranking by $P$ disagrees with their ranking by true cut size, the asymptotic yardstick is not a valid finite-$n$ comparator.","tokens_in":9730,"feed_emoji":"✂️","tokens_out":7283,"duration_ms":63186,"temperature":0.7,"pith_summary":"This note asks whether graph neural networks can be taught, without labels, to find good max-cut solutions on random regular graphs. It reports that they can: an unsupervised line-graph neural network trained to maximize the cut directly produces cuts comparable to those from the standard semidefinite-programming relaxation of max-cut, while the physics-inspired extremal optimization heuristic consistently finds better cuts than both. Because random regular graphs have no planted ground truth, the paper scores every candidate solution against the known asymptotic value of the optimal max-cut, giving the comparison an absolute yardstick. A reader should care because the result suggests unsupervised learning can serve as a practical heuristic for NP-hard combinatorial optimization on random inputs, even though it does not beat a well-tuned local search.","feed_headline":"GNNs match Goemans-Williamson SDP on random max-cut","feed_subtitle":"Unsupervised graph networks find cuts as good as a classic SDP; extremal optimization still wins.","key_machinery":"The load-bearing object is the Line Graph Neural Network (LGNN): a neural network that propagates signals on the original graph and on its line graph using the degree, adjacency, power-graph, and non-backtracking operators, then merges node and edge features through indicator matrices. For max-cut it is trained without labels by maximizing a differentiable proxy for the cut value: either the relaxed quadratic form $(2p-1)^T L_G (2p-1)/4$, where $p$ is the probability that a vertex is assigned to side 1, or a policy-gradient estimator that samples assignments and updates through the score function $\\nabla \\log \\pi$. The two baselines are the semidefinite relaxation with random rounding and extremal optimization, which repeatedly flips the variable with the worst normalized fitness under a power-law selection rule. The evaluation yardstick is the asymptotic max-cut formula that supplies $P^* \\approx 0.7632$, used to normalize every reported cut value.","core_discovery":"The paper's central claim is that, for max-cut on random d-regular graphs with $n = 50$ to $500$ vertices and degrees $d = 3$ to $20$, an unsupervised graph neural network trained with either a continuous relaxation or a policy-gradient estimator of the cut objective attains performance comparable to the semidefinite-programming relaxation, and that extremal optimization outperforms both. Each cut is converted to the standardized score $P = (z/n - d/4)/\\sqrt{d/4}$, whose known asymptotic optimum is $P^* \\approx 0.7632$; across all reported tables, $P$ increases as graphs become sparser and larger, so all three methods approach the asymptotic optimum in those regimes. The paper frames this as experimental evidence that unsupervised machine learning can be successfully adapted to hard optimization problems on random inputs, with the GNN result being the least anticipated of the three.","pith_inferences":["The paper trains a fresh network for each $(n,d)$ pair; an untested consequence is whether one network transfers across sizes or degrees, which would tell whether the GNN has learned a general algorithm or fit each regime separately.","If finite-size corrections to the asymptotic max-cut formula are method-dependent, rankings by $P$ could differ from rankings by true cut quality; a small-$n$ exact benchmark would settle this.","The two training variants perform inconsistently relative to each other across tables, suggesting that a variance-reduced policy-gradient estimator or a hybrid loss could close part of the gap to extremal optimization.","Because similarly scored cuts can be structurally different, solution diversity, not just cut value, may matter for applications that need multiple candidate partitions."],"forward_implications":["If the finding holds, unsupervised graph neural networks are a viable heuristic for max-cut on random regular graphs at moderate sizes, requiring no labels and no planted signal.","Extremal optimization, not the neural method, is the strongest of the three, so further theoretical study of that heuristic is the more direct route to provable guarantees.","The monotone approach toward $P^*$ as graphs grow sparser and larger indicates that finite-size effects, rather than algorithmic failure, account for most of the observed gap to the asymptotic optimum.","Because the GNN and the SDP land in the same performance band, the two approaches are comparable alternatives in this regime rather than one dominating the other."],"supporting_citations":[{"why":"Supplies the asymptotic max-cut formula and the constant $P^*$ used to normalize all reported cut values.","marker":"Dembo et al. (2017)"},{"why":"Defines the semidefinite relaxation and rounding baseline against which the GNN is compared.","marker":"Goemans and Williamson (1995)"},{"why":"Provides the extremal optimization algorithm, its fitness ranking, and the parameter guidance adopted here.","marker":"Boettcher and Percus (2001)"},{"why":"Defines the Line Graph Neural Network architecture that the paper adapts to unsupervised max-cut.","marker":"Chen et al. (2017)"},{"why":"Establishes that the SDP relaxation is not asymptotically tight, motivating the finite-size comparison.","marker":"Montanari and Sen (2016)"},{"why":"Gives the policy-gradient estimator used for one of the unsupervised training losses.","marker":"Sutton et al. (1999)"},{"why":"Provides the SDP solver used to compute the semidefinite-programming baseline.","marker":"Yang et al. (2015)"}],"fun_headline_variants":["GNNs match Goemans-Williamson on random max-cut","Graph nets tie classic SDP for max-cut","Max-cut: GNNs match SDP, but extremal optimization wins","Neural nets rival SDP on random max-cut","On random max-cut, GNNs match SDP, heuristic wins"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The comparison assumes the known asymptotic formula for the optimal max-cut is an accurate yardstick at the finite sizes tested, so that a higher $P$ always indicates a better cut relative to the true optimum.","fun_headline_variants_meta":{"raw":{"variants":["GNNs match Goemans-Williamson on random max-cut","Graph nets tie classic SDP for max-cut","Max-cut: GNNs match SDP, but extremal optimization wins","Neural nets rival SDP on random max-cut","On random max-cut, GNNs match SDP, heuristic wins"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001116,"raw_usage":{"total_tokens":4656,"prompt_tokens":963,"completion_tokens":3693,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":579,"completion_tokens_details":{"reasoning_tokens":3605}},"tokens_in":579,"tokens_out":3693,"duration_ms":26394,"temperature":1.0,"reasoning_tokens":3605,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T13:04:58.541298+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Solve small random d-regular graphs exactly (for example all $n \\le 30$ with $d = 3$ and $10$) and compare the three methods' $P$ values against the true maximum cut; if the methods' ranking by $P$ disagrees with their ranking by true cut size, the asymptotic yardstick is not a valid finite-$n$ comparator.","supporting_citations":[{"cited_title":"Semidefinite programs on sparse random graphs and their application to community detection","cited_arxiv_id":null,"evidence_quote":"Establishes that the SDP relaxation is not asymptotically tight, motivating the finite-size comparison."},{"cited_title":"SDPNAL +: a majorized semismooth newton-cg augmented lagrangian method for semidefinite programming with nonnegative constraints","cited_arxiv_id":null,"evidence_quote":"Provides the SDP solver used to compute the semidefinite-programming baseline."}],"review_version":1}