Pith. sign in

REVIEW 3 major objections 4 minor 19 references

Reinforcement learning for graph theory, Parallelizing Wagner's approach

T0 review · 3 major / 4 minor · reviewed 2026-08-05 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read A parallelized reinforcement-learning search over graphs finds more counterexamples to conjectured Laplacian spectral radius bounds, including three previously open cases, while running faster than the baseline.

desk verdict Three plausible new counterexamples to 2006 Laplacian-radius conjectures, but the paper makes you fetch a calculator to believe them. read the letter →

arxiv 2509.01607 v1 pith:3J3QZHXL submitted 2025-09-01 math.CO cs.LG

Alix Bouffard , Jane Breen This is my paper · ORCID
classification math.COcs.LG MSC 05C5068T0590C59
keywords reinforcementlearningcross-entropymethodLaplacianspectralradiusgraphtheorycounterexamplesparallelsearchactionspacebounds
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper tries to show that a parallelized reinforcement-learning search, based on the cross-entropy method, can find counterexamples to conjectured upper bounds on the largest eigenvalue of a graph's Laplacian matrix more efficiently and more successfully than earlier code. It reports four small graphs that falsify many of the 68 open bounds in a known automated-conjecture catalogue, including three bounds that had no previously known counterexample. The engine of the method is a policy network that learns to edit graphs with a bit-flip action space, seeded from the previous best graph, while multiple independent models explore different regions of graph space. If the reported counterexamples hold up, the paper both closes three concrete conjectures and demonstrates a reusable recipe for AI-assisted conjecture falsification in extremal graph theory.

What carries the argument

The central mechanism is the cross-entropy method: a policy network proposes graphs, the top 10% by reward update the network, and the top 5% are carried into the next generation. The reward is the graph's Laplacian spectral radius minus the conjectured bound, so ordinary graphs get negative rewards and a counterexample yields a positive one. Two modifications carry the argument: (1) multiple policy networks train in parallel on disjoint batches, and (2) the action is a bit-wise exclusive-or against the observation, so a portion of each batch starts at the previous generation's best graph and mutates it instead of constructing from the zero matrix. This second change is congruent to the old

What would settle it

Compute the largest Laplacian eigenvalue of each of the four adjacency matrices in Appendix A and evaluate the corresponding conjecture formula on that graph; if any graph's spectral radius does not strictly exceed its stated bound, the central claim fails. For the performance claim, re-run the comparison on multiple conjectures with fixed random seeds and measure wall-clock time and number of counterexamples found per run.

Watch

Extended reading notes

Core claim

The paper claims that running several cross-entropy reinforcement-learning agents in parallel, with an action space redefined so an agent can mutate the previous best graph rather than build from zero, outperforms the prior single-agent implementation: it finds more counterexamples to conjectured upper bounds on the Laplacian spectral radius in less wall-clock time. It reports four graphs that falsify many of the 68 open bounds from an earlier automated-conjecture catalogue, including three bounds (conjectures 2, 32, 61) for which no counterexamples had been previously published. The decentralization is meant to escape the cross-entropy method's tendency to stall at local optima.

Load-bearing premise

The load-bearing premise is that the four Appendix A graphs genuinely violate the listed conjectures and that the reported speedups are not artifacts of the threading-related random-number-seed behaviour the paper itself flags; an error in the eigenvalue computation, in transcribing the conjecture formulas, or in the RNG handling would collapse the central claims.

Editorial extensions

If this is right

  • Three previously open conjectured upper bounds (numbers 2, 32, 61) from the cited catalogue are false, witnessed by graphs on 12 and 20 vertices; any repair of these bounds must accommodate these graphs.
  • The parallel, local-optimum-initialized cross-entropy method is faster and finds more counterexamples than the single-model baseline, making it a practical template for automated conjecture falsification in spectral graph theory.
  • The four reported graphs each serve as counterexamples to many distinct conjectures, showing that a single extremal graph can witness a cluster of similar bounds.
  • The redefined action space reduces to the original when starting from the zero matrix, so the observed gains come from parallel decentralization and seeding with the previous top graph rather than from the XOR formulation alone.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • If independently verified, the three new counterexamples stand as a mathematical result independent of the reinforcement-learning framing; the method acts as a discovery tool rather than a proof generator.
  • The same parallel search could be pointed at other eigenvalue-based conjectures (adjacency spectral radius, normalized Laplacian, distance matrices) as long as a reward function can be defined, though the paper does not report such experiments.
  • The paper itself flags a possible random-number-seed artifact from threading; an ablation with fixed seeds across model counts would clarify whether the speedups are genuinely due to parallelism or to implementation details.
  • A controlled comparison with zero seeding of the top graph would isolate whether the quarter-of-batch seeding is the main driver of the performance gain, since the reported experiments do not vary that factor alone.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 4 minor

Summary. The paper presents a parallelized, reinforcement-learning implementation (based on a cross-entropy method) for searching for counterexamples to 68 conjectured upper bounds on the Laplacian spectral radius of a graph, originally generated by Brankov et al. The authors reimplement Stevanovic et al.'s code, introduce a redefined action space that toggles bits of the current observation matrix, and run multiple models in parallel. The main claims are (i) the new implementation outperforms the original in both time per generation and in the number of counterexamples found, and (ii) the search discovers three new counterexamples, to Conjectures 2, 32, and 61, using four graphs listed in Appendix A. The paper includes adjacency matrices and conjecture formulas for these graphs but does not report any computed Laplacian spectral radius or bound values.

Significance. If the three claimed counterexamples are correct, the paper would make a modest but real contribution to extremal spectral graph theory: it would close three open conjectures from Brankov et al.'s list and demonstrate that a simple decentralized cross-entropy method can find graphs that standard local search misses. The code is publicly available, which is a strength for reproducibility. However, the verification of the counterexamples is entirely external to the text: the appendix asserts the inequalities but provides no numerical evidence. Since the search reward is defined as the spectral radius minus the conjectured bound, the discovery procedure is coherent and not circular, but an implementation error in either the spectral radius computation or the conjecture formula transcription would invalidate the central claim. The time-complexity comparison also lacks statistical detail. The paper's significance therefore hinges on an independent verification that is neither provided nor pointed to in the repository in enough detail.

major comments (3)
  1. [Section 3, Appendix A] The central novelty is the three circled entries in the table: Conjectures 2, 32, and 61 are marked with '◦', which the text defines as 'new counter-examples'. Appendix A provides adjacency matrices and expressions for the conjectured bounds, but it never gives the computed Laplacian spectral radius µ(G) for any of the four graphs, nor the numerical value of the conjectured bound. The appendix only states that 'the spectral radius of the Laplacian matrix of the graph is larger than the stated conjecture'. This is a load-bearing verification gap: the conjecture formulas are intricate maxima over degree and average-neighbor-degree terms (e.g., Conjectures 52/53 contain nested radicals), and the reward computation in the code uses the same formulas, so a bug in formula transcription or spectral radius evaluation would silently produce false positives. The paper even flags a possible RNG-see
  2. [Section 3, Figure 10] The performance comparison rests on 'the average of 15 runs of 400 generations', but no error bars, standard deviations, or significance tests are reported. The figure also appears to compare different numbers of parallel models with different per-model batch sizes (200 vs. 500), and the text says the 5-model version initially underperforms for that reason. The paper's concluding sentence claims superiority in 'time-complexity', but the runtime comparisons are described only qualitatively ('reduced the time to process a generation by up to a third') with no hardware or timing methodology. Moreover, the text acknowledges a possible bug in the randomization function's RNG seed handling, which could affect both the reward trajectories and the discovered graphs. This makes the performance claim hard to evaluate. Please provide per-run data, error bars, and a clear specification of what is be
  3. [Section 2.1, Section 2.3] The paper's second stated contribution is the 'novel redefining of the action space' to XOR the model's action with the observation matrix. However, the experimental section does not isolate the effect of this change: the comparisons vary the number of parallel models and the initialization insertion percentage simultaneously. It is therefore unclear whether the observed improvements come from the parallelization, the new action space, the GELU activation, or the initialization strategy. In addition, Section 2.3 says the default hidden sizes are 72 and 12, while Figure 9's caption says 24 and 12; please reconcile this inconsistency. An ablation study (original action space vs. new action space, with parallelization held fixed) would strengthen the attribution of the claimed improvement.
minor comments (4)
  1. [Abstract/Introduction] Typographical errors: 'Wagnar's approach' in the abstract and 'Stevonovic's' in the contributions section. The abstract also uses 'Wagnar' inconsistently with the title's 'Wagner'.
  2. [Section 3, Table] The table legend should be expanded. It is unclear what 'previously closed' means: presumably closed by Stevanovic et al., but the text should say so explicitly and cite the corresponding results. The symbol placement in the table is also hard to read; a clearer table with explicit columns for each graph would help.
  3. [Appendix A] The conjecture formulas are typeset without the inequality that defines them as upper bounds. For example, Conjecture 2 is simply listed as 'max 2m_v^2/d_v' with no '≤ µ(G)' or 'µ(G) ≤ ...'. Adding the full inequality would remove ambiguity and make the counterexample check transparent.
  4. [Section 2.2] The claim that parallelization 'reduced the time to process a generation by up to a third' is not accompanied by any measurement details. Please specify the hardware, the timing methodology, and whether the comparison used identical hyperparameters.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the RL reward is the target inequality, and counterexamples are external search outputs, not fitted predictions.

full rationale

The paper's method defines the reward as the spectral radius minus the conjectured upper bound (Section 2), so maximizing the reward is exactly the search for a counterexample. This is a legitimate optimization target rather than a self-referential derivation: the discovered graphs are not parameters fitted to the conjectures, and the claim that they violate the conjectures is a separate computational assertion (Appendix A) that could in principle be checked independently by diagonalizing the Laplacian. There are no load-bearing self-citations, no imported uniqueness theorems, and no ansatz hidden in a citation. The implementation caveat in Section 3 regarding RNG seeds and the absence of tabulated spectral radii in Appendix A are correctness/verification risks, not circularity. Hence the derivation chain is self-contained and no step reduces to its own input.

Assumptions & free parameters 5 free parameters · 3 assumptions · 0 invented entities

The mathematical results (counterexamples) depend only on standard graph theory and the correctness of the conjecture formulas. The RL method introduces several hand-chosen hyperparameters that affect the search process and the performance comparison, but not the external verifiability of the counterexamples. No new entities are postulated.

free parameters (5)
  • Learning rate (ADAM optimizer) = 0.002
    Chosen hyperparameter for the policy network update; affects search behavior but not the mathematical validity of any counterexample.
  • Hidden layer sizes = 72 and 12 nodes
    Network architecture chosen by hand; affects the representational capacity of the policy.
  • Top-k selection percentages = top 10% for learning, top 5% duplicated
    Chosen for the cross-entropy update; affects which graphs guide the next generation.
  • Randomization rate = 0.05% to 1% in experiments
    Fraction of random graphs per batch; the paper reports that increasing to 1% decreased performance.
  • Initialization insertion percent = quarter of the batch (not precisely specified)
    Portion of each generation initialized from the previous top observation; admitted to lead to local optima.
assumptions (3)
  • standard math Standard spectral graph theory: the Laplacian matrix is positive semidefinite, and its largest eigenvalue can be computed from the adjacency matrix.
    Used throughout the methodology and appendix to define the spectral radius and conjectures.
  • domain assumption The conjecture bounds from Brankov et al. (2006) are correctly transcribed into the formulas in Appendix A.
    The counterexample determination depends on comparing the Laplacian spectral radius to the stated algebraic expression; any transcription error invalidates the result.
  • domain assumption The cross-entropy method with the given policy network and reward converges to high-reward graphs in practice.
    The method's ability to find counterexamples relies on this empirical convergence, which the paper does not rigorously justify.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Reinforcement learning for graph theory, Parallelizing Wagner's approach." pith.science (2026). https://pith.science/paper/3J3QZHXL

@misc{pith2026250901607,
  author       = {Pith},
  title        = {Pith review of: Reinforcement learning for graph theory, Parallelizing Wagner's approach},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/3J3QZHXL}},
  note         = {Machine review of arXiv:2509.01607}
}
read the original abstract

Our work applies reinforcement learning to construct counterexamples concerning conjectured bounds on the spectral radius of the Laplacian matrix of a graph. We expand upon the re-implementation of Wagner's approach by Stevanovic et al. with the ability to train numerous unique models simultaneously and a novel redefining of the action space to adjust the influence of the current local optimum on the learning process.

Figures

Figures reproduced from arXiv: 2509.01607 by the authors.

Figure 1
Figure 1. A four vertex graph and its adjacency matrix [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 2
Figure 2. The Laplacian matrix is displayed in the lower left [PITH_FULL_IMAGE:figures/full_fig_p002_2.png] view at source ↗
Figure 3
Figure 3. A graph on 19 vertices satisfying λ1 + µ < √ n − 1 + 1 For the conjectures on transmission regularity and the sum of eigenvalue and matching number, the algorithm directly produced valid counterexamples. Although the model did not yield a direct counterexample to the proximity conjecture, the graphs that achieved the maximum reward gave a clear indication on the probable structure that a counterexample might take. W… view at source ↗
Figures from the paper (7 more)
Figure 4
Figure 4. Figure 4: Counter-example for the conjecture: π + δ⌊ 2D 3 ⌋ > 0 [PITH_FULL_IMAGE:figures/full_fig_p003_4.png]
Figure 5
Figure 5. Figure 5: A reinforcement learning algorithm en￾acts a policy on an environment, makes obser￾vations, and optimizes itself according to a re￾ward.10 Cross-entropy is a basic evolutionary algorithm, where populations are generated, evaluated, and iterated upon.11 Populations are …
Figure 7
Figure 7. Figure 7: Left: A graph and its adjacency matrix. The sec [PITH_FULL_IMAGE:figures/full_fig_p005_7.png]
Figure 8
Figure 8. Figure 8: Left: Centralized and De-centralized models. [PITH_FULL_IMAGE:figures/full_fig_p006_8.png]
Figure 9
Figure 9. Figure 9: Example network for a 4-node graph. 12 node observation/input layer. 24 and 12 node hidden layers. 2 node [PITH_FULL_IMAGE:figures/full_fig_p006_9.png]
Figure 10
Figure 10. Figure 10: Comparison of various implementation performances on conjecture 3 [PITH_FULL_IMAGE:figures/full_fig_p007_10.png]
Figure 11
Figure 11. Figure 11: Comparison of the impact of randomness on performances on conjecture 3 [PITH_FULL_IMAGE:figures/full_fig_p008_11.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

19 extracted references · 13 canonical work pages

  1. [1]

    Constructions in combinatorics via neural networks,

    Wagner, A. Z., “Constructions in combinatorics via neural networks,” arXiv preprint arXiv:2104.14516 (2021)

    arXiv 2021

  2. [2]

    Reinforcement learning for graph theory, i. reimplementation of wagner’s approach,

    Ghebleh, M., Al-Yakoob, S., Kanso, A., and Stevanovic, D., “Reinforcement learning for graph theory, i. reimplementation of wagner’s approach,” arXiv preprint arXiv:2403.18429(2024)

    arXiv 2024

  3. [3]

    Variable neighborhood search for extremal vertices: The autographix-iii system,

    Caporossi, G., “Variable neighborhood search for extremal vertices: The autographix-iii system,” Computers & Operations Research78, 431–438 (2017)

    work page 2017

  4. [4]

    Automated conjectures on upper bounds for the largest laplacian eigenvalue of graphs,

    Brankov, V., Hansen, P., and Stevanovi´ c, D., “Automated conjectures on upper bounds for the largest laplacian eigenvalue of graphs,” Linear algebra and its applications414(2-3), 407–424 (2006)

    work page 2006

  5. [5]

    A nordhaus-gaddum type problem for the normalized laplacian spectrum and graph cheeger constant,

    Faught, J. N., Kempton, M., and Knudson, A., “A nordhaus-gaddum type problem for the normalized laplacian spectrum and graph cheeger constant,”Applied Mathematics and Computation480, 128920 (2024)

    work page 2024

  6. [6]

    A survey of automated conjectures in spectral graph theory,

    Aouchiche, M. and Hansen, P., “A survey of automated conjectures in spectral graph theory,” Linear algebra and its applications432(9), 2293–2322 (2010)

    work page 2010

  7. [7]

    Artificial intelligence and machine learning generated conjectures with TxGraffiti

    Davila, R., “Artificial intelligence and machine learning generated conjectures with txgraffiti,”arXiv preprint arXiv:2407.02731 (2024)

    work page Pith review arXiv 2024

  8. [8]

    Reinforcement learning for graph theory, II. Small Ramsey numbers

    Ghebleh, M., Al-Yakoob, S., Kanso, A., and Stevanovi´ c, D., “Reinforcement learning for graph theory, ii. small ramsey numbers,” arXiv preprint arXiv:2403.20055(2024)

    work page Pith review arXiv 2024

Show all 19 references
  1. [9]

    Graph6java: A researcher–friendly java framework for testing conjectures in chemical graph theory,

    Ghebleh, M., Kanso, A., and Stevanovic, D., “Graph6java: A researcher–friendly java framework for testing conjectures in chemical graph theory,” MATCH Commun. Math. Comput. Chem81, 737–770 (2019)

    2019

  2. [10]

    Tempestas ex machina: A review of machine learning methods for wavefront control,

    Fowler, J. and Landman, R., “Tempestas ex machina: A review of machine learning methods for wavefront control,” (09 2023)

    2023

  3. [11]

    A tutorial on the cross-entropy method,

    De Boer, P.-T., Kroese, D. P., Mannor, S., and Rubinstein, R. Y., “A tutorial on the cross-entropy method,” Annals of operations research134, 19–67 (2005)

    2005

  4. [12]

    A simple decentralized cross-entropy method,

    Zhang, Z., Jin, J., Jagersand, M., Luo, J., and Schuurmans, D., “A simple decentralized cross-entropy method,” Advances in Neural Information Processing Systems35, 36495–36506 (2022)

    2022

  5. [13]

    Adam: A method for stochastic optimization,

    Kingma, D. P. and Ba, J., “Adam: A method for stochastic optimization,” arXiv preprint arXiv:1412.6980 (2014)

    2014 arXiv

  6. [14]

    Gaussian error linear units (gelus),

    Hendrycks, D. and Gimpel, K., “Gaussian error linear units (gelus),” arXiv preprint arXiv:1606.08415 (2016)

    2016 arXiv

  7. [15]

    Annealing adaptive search, cross-entropy, and stochastic approximation in global optimization,

    Hu, J. and Hu, P., “Annealing adaptive search, cross-entropy, and stochastic approximation in global optimization,” Naval Research Logistics (NRL)58(5), 457–477 (2011)

    2011

  8. [16]

    Patternboost: Constructions in mathe- matics with a little help from ai,

    Charton, F., Ellenberg, J. S., Wagner, A. Z., and Williamson, G., “Patternboost: Constructions in mathe- matics with a little help from ai,” arXiv preprint arXiv:2411.00566(2024)

    2024 arXiv

  9. [17]

    Small ramsey numbers,

    Radziszowski, S., “Small ramsey numbers,” The electronic journal of combinatorics, DS1–Jan (2012)

    2012

  10. [18]

    Action space shaping in deep reinforcement learning,

    Kanervisto, A., Scheller, C., and Hautam¨ aki, V., “Action space shaping in deep reinforcement learning,” in [2020 IEEE conference on games (CoG)], 479–486, IEEE (2020)

    2020

  11. [19]

    Population based training of neural networks,

    Jaderberg, M., Dalibard, V., Osindero, S., Czarnecki, W. M., Donahue, J., Razavi, A., Vinyals, O., Green, T., Dunning, I., Simonyan, K., et al., “Population based training of neural networks,” arXiv preprint arXiv:1711.09846 (2017). APPENDIX A. COUNTER-EXAMPLES Following the d...

    2017 arXiv

Pith tools

Reviewed August 5, 2026 · model on record in the stance chip above.