{"id":"1c1e80ed-b67f-456d-809e-bf85d555a55a","arxiv_id":"2412.09860","paper_version":1,"verdict":"REJECT","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":5,"one_line_summary":"Chaotic graph backpropagation adds a chaotic loss to GNN training and improves solution quality for large-scale combinatorial optimization problems.","lead":"This paper adds a chaotic loss term to graph neural network training, turning backpropagation into a chaotic dynamical system that anneals into gradient descent, and applies it to maximum independent set, max cut, and graph coloring problems. The authors report that this 'chaotic graph backpropagation' improves solution quality of physics-inspired GNN solvers and, on several benchmarks, matches or beats state-of-the-art combinatorial optimization heuristics.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The paper's core inference—Marotto chaos gives ergodic exploration of the loss landscape—does not establish global optimization of the Hamiltonian, and Table 1 already contradicts the 'outperform SOTA' abstract claim.","rationale":"The reader's rejection is justified, and the weakest assumption identified is the same as the one I consider load-bearing: the paper moves from 'the weight dynamics are chaotic and hence ergodic on an attractor' to 'CGBP learns the optimal GNN globally.' That inference fails for two independent reasons. First, ergodicity on an attractor is not equivalent to uniform coverage of weight space, let alone coverage of the sublevel sets of the Hamiltonian loss; the chaotic attractor is generated by the total loss, including the artificial chaotic loss, so it need not align with the COP objective. Second, the annealing schedule in Eq. (11) makes the actual training process non-autonomous, so the invariant measure used to define ergodicity does not exist for the system that is actually run. The paper does not supply a transient-analysis theorem that would replace this missing step. The empirical record also undercuts the headline: Table 1 shows CGBP below classical SOTA methods on three of five Gset instances, so the abstract's 'outperform not only existing GNN algorithms but also SOTA methods' is contradicted by the paper's own data. I therefore see no reason to alter the reader's reject verdict; the method may still be a useful heuristic, but the central global-optimality claim is not supported.","tokens_in":15154,"tokens_out":6774,"duration_ms":79711,"concrete_test":"Run CGBP on the 3-node toy graph of Fig. 2 with a Hamiltonian/MSE loss engineered to have a known, unique global minimum and a disjoint local minimum; from 100 random initializations, record whether the chaotic phase (epochs 0–1000, before z anneals to ~0) visits the global minimizer's basin and whether the final trajectory converges there. If, in any run, the orbit stays outside the global basin for the entire chaotic phase and later converges to the local minimum, the claim that ergodicity of the chaotic weight dynamics guarantees global optimization is refuted.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Section 4 claims that CGBP's strong performance is due to 'theoretically guaranteed global ergodicity and pseudo-randomness' of chaotic dynamics, and the Abstract concludes this 'enable[s] CGBP to learn each optimal GNN effectively and globally.' The gap is that ergodicity is a property of the invariant measure on the strange attractor of the weight map F in Eq. (10), not a guarantee about the Hamiltonian loss_H that defines the COP. The attractor is shaped by the total loss (loss_H + loss_C), and the map from weights to node probabilities p(θ) to H can be highly non-injective; an ergodic orbit in weight space need not visit, or spend time near, the preimage of the global minimum of H. Moreover, the actual algorithm anneals z to zero via Eq. (11), so the training system is non-autonomous and has no invariant measure; 'global ergodicity' in the strict sense does not apply to the transient process. The paper cites Marotto chaos from the authors' separate MLP work and verifies positive Lyapunov exponents only on the 3-node toy model; no theorem is given for the shared-weight GCN/GraphSAGE updates in Eqs. (8)-(9). Finally, the paper's own Table 1 contradicts 'outperform SOTA': CGBP reaches 3035/3016/13318 on G14/G15/G22, below BLS and KHLWG (3064/3050/13359), and the text itself downgrades to 'comparable.' Thus the central global-optimality claim is asserted rather than established.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"This paper proposes CGBP (chaotic graph backpropagation), a training algorithm that adds a 'chaotic loss' term to the GNN objective so that the weight-update dynamics become chaotic. The authors claim that the global ergodicity and pseudo-randomness of these chaotic dynamics let the GNN escape local minima and find globally optimal solutions, and they apply CGBP to PI-GNN-based solvers for maximum independent set, maximum cut, and graph coloring. They report improvements over standard backpropagation on synthetic 3-regular graphs, compare against established solvers on Gset, Queen, and Citation benchmarks, and claim linear time complexity and plug-in usability for any GNN-based method.","tokens_in":15500,"tokens_out":5313,"duration_ms":52640,"significance":"If the central claims held, the paper would make a useful contribution by showing that a chaotic training rule can improve unsupervised GNN solvers for large combinatorial optimization problems while preserving linear scaling. The paper has several positive features: public code is available, the empirical study uses public benchmarks, and the scaling experiment on 3-regular graphs up to 10^5 nodes is informative. However, the main theoretical claim connecting chaos to global optimality is not established, the empirical protocol is asymmetric, and the headline 'outperforms SOTA' statement is contradicted by the authors' own Table 1 on three of five Gset instances. As presented, the contribution is a heuristic training rule with partial empirical evidence rather than the theoretically grounded global optimization algorithm the paper claims.","major_comments":[{"comment":"The central theoretical claim is not established. The abstract and Section 4 assert that the 'global ergodicity and pseudo-randomness' of the chaotic dynamics 'enable CGBP to learn each optimal GNN effectively and globally.' However, the paper does not prove a theorem connecting Marotto chaos of the weight map F in Eq. (10) to global optimality of the Hamiltonian loss loss_H in Eq. (4). Ergodicity on a strange attractor of the weight dynamics does not imply that the trajectory reaches the preimage of the global minimum of H, because the map from weights to node probabilities and then to loss_H is non-injective and the attractor is shaped by the combined loss. Moreover, the annealing schedule in Eq. (11) makes the system non-autonomous, so no invariant measure exists and strict ergodicity does not apply to the training process. The Discussion's own caveat that 'the obtained solution may not [be] optimal' contradicts the global-optimality claim. The authors should either supply a proof for the actual GCN/GraphSAGE updates or substantially weaken the claim to 'chaotic exploration may improve solution quality.'","section":"Abstract; Section 4"},{"comment":"The claimed 'outperform existing SOTA methods' is contradicted by the paper's own Table 1. On G14, G15, and G22, the best CGBP results are 3035, 3016, and 13318, respectively, whereas BLS and KHLWG reach 3064, 3050, and 13359. The text in Section 3.3 correctly downgrades this to 'comparable,' but the abstract and introduction continue to claim outperformance. This overstatement directly affects the paper's central empirical contribution and must be corrected, with conclusions limited to the instances where CGBP actually matches or exceeds SOTA.","section":"Table 1; Abstract"},{"comment":"The empirical protocol is asymmetric and does not support the claim that CGBP outperforms existing GNN algorithms. Section 5.3 states that hyperopt is used 'to fully unleash the performance of CGBP' with up to 300 hyperparameter samples, while the baseline PI-GCN and PI-SAGE results appear to be taken from the original publications with their default settings. Under this protocol, the comparison conflates algorithmic improvement with hyperparameter tuning. A fair comparison requires tuning the baselines under the same search budget, or at least reporting baseline results with the same optimizer and search strategy.","section":"Section 5.3; Tables 1-3"},{"comment":"The proof of Marotto chaos is not transferred to the GNN setting. The text asserts in Section 2.4 that when z is sufficiently large, Eq. (9) exhibits Marotto chaos, citing the authors' prior MLP work (ref. 37). But Eq. (9) now contains node selection d and shared weights across all nodes in the GCN/GraphSAGE update; the earlier proof does not automatically apply. The only numerical evidence of positive Lyapunov exponents is on the 3-node toy model in Fig. 2, not on the shared-weight GNN used in the benchmark experiments. The authors should either provide a theorem for the GCN update or state the chaotic behavior as a numerical observation.","section":"Section 2.4; Eq. (9)"},{"comment":"The experiments do not isolate the effect of chaos. In addition to the chaotic loss, CGBP introduces a stochastic node-selection scheme (CGBP-R in Fig. 2) and an annealing schedule, Eq. (11). The comparison of CGBP against BP therefore changes multiple factors simultaneously, so the observed improvements cannot be attributed specifically to chaotic dynamics. An ablation that replaces the chaotic term with a non-chaotic random perturbation of the same magnitude, or that keeps the same stochastic selection and annealing without the chaotic loss, is needed to support the mechanistic claim in Section 4.","section":"Figs. 3-4; Section 3.2"}],"minor_comments":[{"comment":"The text mentions 'the hyperparameters z and β introduced in CSBP'; this should be 'CGBP'.","section":"Section 5.3"},{"comment":"The mathematical notation in Eq. (7) and the surrounding derivation appears garbled in the rendered manuscript; please ensure all formulas are typeset correctly.","section":"Eq. (7), Eq. (8)"},{"comment":"The phrase 'outperforming not only the existing GNN learning algorithms but also SOTA methods' should be aligned with the more cautious 'comparable' language used in Section 3.3.","section":"Introduction"},{"comment":"The claim that CGBP is a universal plug-in for 'any existing method' is not supported by experiments, which only consider PI-GNN; please temper the claim or add evidence with a different base method.","section":"Abstract; Section 4"},{"comment":"Figure 4a reports an approximation ratio 'around 0.95' but does not specify whether this is the median, mean, or best over the 100 runs; please clarify in the caption or text.","section":"Fig. 4"}],"recommendation":"reject","confidential_remarks":"The paper relies heavily on the authors' prior theorems (refs. 15, 18, 19, 37) without re-deriving them for the shared-weight GNN case, and the empirical comparison is not designed to isolate the chaotic mechanism. The code availability and reproducible scaffolding are positive, but the central claims as written are not supported by the evidence presented. I recommend rejection."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The honest version of this paper is a good one. Adding the chaotic loss term to PI-GNN training improves solution quality on MIS, MC, and graph coloring across several benchmarks, with code and consistent 100-seed results on 3-regular graphs. That is a real, if modest, contribution. The advertised version—global ergodicity through Marotto chaos guarantees optimal GNNs, and CGBP outperforms SOTA—does not hold up.\n\nWhat is new is the GNN-specific adaptation of the authors' chaotic backpropagation: a node-averaged chaotic loss that handles weight sharing. The experiments on 3-regular graphs are the best part: across SGD, SGDM, and Adam, CGBP beats BP-based PI-GNN on both loss and solution size, with clear boxplots. The robustness to z and beta shown in Fig. 4c-d is also convincing. These are controlled comparisons with the same architecture and protocol.\n\nThe soft spots are where the claims outrun the evidence. First, the theoretical bridge from Marotto chaos in weight dynamics to global optimization of the Hamiltonian is not derived. Ergodicity on a strange attractor in weight space does not imply the trajectory spends time near the preimage of the Hamiltonian's global minimum. The map from weights to outputs to loss is non-injective, and the annealing schedule (Eq. 11) makes the system non-autonomous, so there is no invariant measure to be ergodic over. The Lyapunov-exponent evidence is limited to the single-neuron toy model. I don't see a way to rescue the \"global\" language without a new theorem or a much weaker statement.\n\nSecond, the benchmark comparison is not fair as reported. CGBP gets hyperopt tuning and best-of-seed selection; the baselines appear to use their original published settings. And Table 1 itself contradicts the abstract: CGBP is below BLS and KHLWG on G14, G15, and G22. The text quietly says \"comparable.\" On G49 and G50 CGBP ties the SOTA value, which is good, but that is not \"outperform SOTA.\" Third, the universal-plug-in claim is tested on only two GNN architectures and three COPs.\n\nThe paper also does some things well: it states its own limitations in the Discussion, the data and code are available, and the core empirical effect is reproducible in principle. The paper is a legitimate incremental advance in neural combinatorial optimization, not a breakthrough. A serious referee should see it, because the empirical trick may be useful to the community even if the theory is not there yet.\n\nMy recommendation: send it to peer review, but require the authors to either prove a weaker convergence statement or drop the global-optimality framing, and to run the baselines with the same tuning protocol or explicitly report their settings. I would not cite it for the chaos theory, but I might cite it for the training trick.","headline":"A useful empirical training trick for GNN solvers, wrapped in an unsupported global-optimality narrative and a SOTA claim its own Table 1 contradicts.","tokens_in":16034,"tokens_out":3468,"would_cite":false,"duration_ms":36380,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper claims that adding a chaotic local loss term to GNN training, then annealing its strength, lets the network escape local minima and solve large-scale combinatorial optimization problems at least as well as specialized…","keywords":["combinatorial optimization","graph neural networks","chaotic backpropagation","chaotic simulated annealing","maximum cut","graph coloring","maximum independent set","Marotto chaos"],"falsifier":"Use a small max-cut or independent-set instance with a known optimum and compare, over many random seeds, the same GNN trained with the chaotic term $z>0$ against the identical network with $z=0$. If the chaotic runs never reach the known optimum while multi-start backpropagation does, or if runs with positive Lyapunov exponents systematically end at higher loss than $z=0$ runs, the central claim that chaos enables global optimization fails. A best-of-100 comparison on a fixed 3-regular graph with $n=100$ would be decisive, since the paper's own results show seed-dependent overlap between BP and CGBP on such instances.","tokens_in":14923,"feed_emoji":"🧠","tokens_out":6915,"duration_ms":68043,"temperature":0.7,"pith_summary":"The paper introduces chaotic graph backpropagation (CGBP), a training rule for graph neural networks that adds a local \"chaotic loss\" to the physics-inspired Hamiltonian loss used for combinatorial optimization. The claim is that when the chaotic strength is large, the weight updates become genuinely chaotic (Marotto chaos, high-dimensional topological chaos), and the resulting global ergodicity and pseudo-randomness let the network explore the loss landscape and escape local minima that trap ordinary backpropagation. Annealing the chaotic strength down to zero then lets the dynamics settle into a good solution. On maximum independent set, maximum cut, and graph coloring benchmarks, CGBP-trained GNNs outperform standard GNN training and, on several instances, match or beat classical solvers. Because the extra loss is a plug-in term, the paper argues CGBP can improve any GNN training method rather than only this particular solver.","feed_headline":"Chaotic training helps graph neural nets beat top optimizers","feed_subtitle":"Adding a chaotic loss term and annealing it solves max-cut, independent set, and coloring at scale.","key_machinery":"The load-bearing object is the chaotic loss term $\\mathcal{L}_C = -z \\sum_{l,j} [I_0 \\ln o^{(l)}_{dj} + (1-I_0)\\ln(1-o^{(l)}_{dj})]$, added to the Hamiltonian loss $\\mathcal{L}_H$. Its gradient with respect to a weight is proportional to $-z(I_0 - o^{(l)}_{dj}) h^{(l)}_i c_{kj}$, so the term acts as local negative feedback and, for large chaotic strength $z$, makes the discrete weight-update map $W(t+1)=F(W(t))$ a snap-back repeller system exhibiting Marotto chaos. Annealing $z$ by the rule $z\\leftarrow \\beta z$ with $\\beta<1$ implements chaotic simulated annealing: the trajectory is globally exploratory early and reduces to gradient dynamics late.","core_discovery":"The central discovery is that chaos in weight space, induced deliberately through a cross-entropy-like local loss whose gradient acts as negative feedback on each weight, is not a nuisance but a global search mechanism. For sufficiently large chaotic strength $z$, the update map $W(t+1)=F(W(t))$ is shown to exhibit Marotto chaos; with $z$ annealed by $z\\leftarrow \\beta z$, training starts in a chaotic regime, passes through bifurcations, and ends in gradient descent. The paper reports that this schedule consistently lowers the Hamiltonian loss and raises solution quality relative to backpropagation on 3-regular graphs, and that on the Gset max-cut instances and the Queen and Citation coloring instances, the CGBP versions reach or exceed the best known results of classical state-of-the-art methods, including optimal cuts on G49 and G50.","pith_inferences":["If chaos is the operative mechanism, the same chaotic-loss recipe should transfer to non-graph neural architectures and even to classical local-search heuristics; the paper tests only GCN and GraphSAGE, so a direct test on MLPs, Transformers, or tabu search would clarify the mechanism.","The paper links global ergodicity to global optimization, but ergodicity on a strange attractor in weight space does not by itself guarantee convergence to the global minimum of the loss; a proof would need to show the chaotic invariant measure concentrates on low-loss regions.","Because the chaotic loss is evaluated at intermediate neuron outputs, its benefit may come from local credit assignment rather than chaos per se; comparing against a non-chaotic local loss with the same annealing schedule would separate the two.","A robustness check beyond the reported hyperparameter grid would be to vary $z$ and $\\beta$ jointly over a wider range and verify that the best-of-many-seeds solution quality remains stable; the paper reports medians over 100 runs for fixed pairs only."],"forward_implications":["Any existing GNN-based combinatorial optimization solver can be upgraded by adding the chaotic loss term, without changing the problem encoding or network architecture.","The linear time complexity of the GNN solver is preserved, so the improvement applies to graphs with up to millions of nodes, although optimality is not guaranteed at that scale.","The benefit is robust across optimizers: CGBP lifts SGD, SGDM, and Adam to similar quality, removing a major source of variance in unsupervised GNN solvers.","On max-cut instances G49 and G50, CGBP attains the known optimal cut value, and on graph-coloring benchmarks it reduces conflicting edges far below the backpropagation-trained baselines, for example to 2 on Pubmed."],"supporting_citations":[{"why":"Supplies the physics-inspired GNN framework and Hamiltonian losses that CGBP is applied to and compared against.","marker":"[12]"},{"why":"The prior chaotic backpropagation algorithm for MLPs whose local chaotic loss CGBP adapts to graph networks.","marker":"[37]"},{"why":"Defines Marotto chaos via snap-back repellers, the topological-chaos criterion used to show CGBP's weight dynamics are chaotic for large z.","marker":"[31]"},{"why":"Provides the chaotic simulated annealing schedule that CGBP uses to transition from global exploration to convergence.","marker":"[18]"},{"why":"Theoretical basis for attributing global search ability to ergodicity and pseudo-randomness of chaotic neural dynamics.","marker":"[15]"},{"why":"Analyzes chaos and asymptotic stability in discrete-time neural networks, grounding the stability side of CGBP's convergence.","marker":"[19]"},{"why":"Extends the physics-inspired GNN encoding to the Potts model for the graph-coloring benchmarks CGBP is tested on.","marker":"[48]"}],"fun_headline_variants":["Chaotic training lifts GNN optimizers to SOTA on graph COPs","Chaotic annealing in GNN training beats top solvers on max-cut, coloring","Chaotic backprop: a plug-in that improves any GNN optimizer","Global search via chaotic dynamics lifts GNN to best graph solutions","Chaos in GNN training outperforms classical solvers on large COPs"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that chaos in the weight updates—the property that the training trajectory wanders ergodically over a strange attractor—by itself means the trajectory will find the global minimum of the loss function; the paper gives numerical evidence but no proof that ergodicity in weight space implies reaching the loss minimum.","fun_headline_variants_meta":{"raw":{"variants":["Chaotic training lifts GNN optimizers to SOTA on graph COPs","Chaotic annealing in GNN training beats top solvers on max-cut, coloring","Chaotic backprop: a plug-in that improves any GNN optimizer","Global search via chaotic dynamics lifts GNN to best graph solutions","Chaos in GNN training outperforms classical solvers on large COPs"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000964,"raw_usage":{"total_tokens":4118,"prompt_tokens":973,"completion_tokens":3145,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":589,"completion_tokens_details":{"reasoning_tokens":3047}},"tokens_in":589,"tokens_out":3145,"duration_ms":24063,"temperature":1.0,"reasoning_tokens":3047,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T16:39:16.227735+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Use a small max-cut or independent-set instance with a known optimum and compare, over many random seeds, the same GNN trained with the chaotic term $z>0$ against the identical network with $z=0$. If the chaotic runs never reach the known optimum while multi-start backpropagation does, or if runs with positive Lyapunov exponents systematically end at higher loss than $z=0$ runs, the central claim that chaos enables global optimization fails. A best-of-100 comparison on a fixed 3-regular graph with $n=100$ would be decisive, since the paper's own results show seed-dependent overlap between BP and CGBP on such instances.","supporting_citations":[{"cited_title":"Combinatorial optimization with physics-inspired graph neural networks","cited_arxiv_id":null,"evidence_quote":"Supplies the physics-inspired GNN framework and Hamiltonian losses that CGBP is applied to and compared against."},{"cited_title":"Brain-in spired chaotic backpropagation for MLP","cited_arxiv_id":null,"evidence_quote":"The prior chaotic backpropagation algorithm for MLPs whose local chaotic loss CGBP adapts to graph networks."},{"cited_title":"On redefining a snap-back repeller","cited_arxiv_id":null,"evidence_quote":"Defines Marotto chaos via snap-back repellers, the topological-chaos criterion used to show CGBP's weight dynamics are chaotic for large z."},{"cited_title":"Chaotic simula ted annealing by a neural network model with transient chaos","cited_arxiv_id":null,"evidence_quote":"Provides the chaotic simulated annealing schedule that CGBP uses to transition from global exploration to convergence."},{"cited_title":"Global searching ability of chaotic neural networks","cited_arxiv_id":null,"evidence_quote":"Theoretical basis for attributing global search ability to ergodicity and pseudo-randomness of chaotic neural dynamics."},{"cited_title":"Chaos and asymptot ical stability in discrete-time neural networks","cited_arxiv_id":null,"evidence_quote":"Analyzes chaos and asymptotic stability in discrete-time neural networks, grounding the stability side of CGBP's convergence."},{"cited_title":"Graph coloring with physics-inspired graph neural networks","cited_arxiv_id":null,"evidence_quote":"Extends the physics-inspired GNN encoding to the Potts model for the graph-coloring benchmarks CGBP is tested on."}],"review_version":1}