Does the graph neural network beat greedy?

“…the graph neural network optimizer performs on par or outperforms existing solvers, with the ability to scale beyond the state of the art to problems with millions of variables.” Schuetz, Brubaker & Katzgraber, Nature Machine Intelligence 4, 367 (2022)

“…a simple greedy algorithm, running in almost linear time, can find solutions for the MIS problem of much better quality than the GNN. The greedy algorithm is faster by a factor of 10⁴…” Angelini & Ricci-Tersenghi, arXiv:2206.13211 (abstract); published as Nature Machine Intelligence 5, 29 (2023), whose own abstract words this differently

The measured object is the validity of a published sentence against an exact objective, not which model is better. That sentence contains two claims, and they are scored separately because they can have different answers.

Uniform random d-regular graphs. Quality is the approximation ratio against McKay's upper bound — the same metric the critique used, so these numbers sit directly beside the published ones. Every set below was verified independent and maximal by a separate checker.

“As published” and “published configuration” on this page mean the authors’ released example implementation’s setting, which uses an embedding of int(sqrt(n)) at every n and a patience of 100; the paper’s text uses int(cbrt(n)) below n = 10⁵ (10 rather than 31 at n = 1000) and a patience of 10³. A pre-registered re-run at that smaller embedding (D39) reproduces the ceiling — 0/15 non-empty raw outputs at d = 8, 12, 20, while d = 3 and 5 still escape in 10/10 runs. Every other result on this page uses the released setting.

The replication holds: at d = 3, n = 10,000 (5 seeds each) the greedy lands at AR 0.9502 against the critique's published ≈0.95, and PI-GNN at 0.9138 against their ≈0.92. Both sides of their figure reproduce on independently written code.

None of the five documents in the exchange — the original paper, two Comments and two Replies — separates what the network contributes from what the post-processing contributes. Both are needed to produce a reported score, and only one of them is the thing under test.

The separation is available from data already collected: compare the raw thresholded output against the score after repair and maximalization.

Above degree seven the network's raw output — before any post-processing — is all zeros. My first explanation was wrong, and the way it was wrong is the finding.

I thought the culprit was the diagonal. The published loss is L(p) = pᵀQp with Qᵢᵢ = −1, a pure quadratic form with no linear term, so ∇L(0) = 0 exactly: the empty set is a critical point at every degree. Fixing that should rescue it. It does not. Changing the diagonal to −Σpᵢ removes the critical point, and d = 20 still returns nothing.

The real mechanism is visible when you compare the final training loss against the exact uniform optimum of the modified, linear-diagonal objective (a post-hoc change, not the published loss) — the value a network that learned nothing at all would reach:

A caution this page’s first draft got wrong: matching L* does not by itself prove the configuration is uniform. The loss is second-order blind to zero-mean scatter around the stationary point, and two of the three seeds land slightly below L*, which no uniform configuration can do. The trapped-at-the-saddle claim therefore rests on measuring the output vector directly (mean p = 0.0261, standard deviation 27–29% of p*, maximum 0.074 — recorded in results/pstats.jsonl), not on the loss agreement alone.

For the published quadratic diagonal, that uniform solution happens to be p = 0. So “collapses to the empty set” and “stuck at the mean field” are the same event — the formulation simply makes the symmetric solution be nothing, and the fixed 0.5 threshold then reports it as nothing. This also explains why the rescue attempts tried here failed: learning rate, patience and a larger embedding (256) do not cause symmetry breaking. Neither does a smaller one: at the paper’s int(∛n) = 10 the raw output is empty in 15/15 runs at d = 8, 12, 20 (D39).

A tuning budget was fixed in writing before any sweep ran — four learning rates × two penalty values × three seeds, at d = 3, 5 and 20 — followed by a separately-labelled post-hoc round with a bigger embedding, longer patience and the repaired objective.

That budget was aimed at the wrong target, and this page previously said otherwise. It was designed against the assumption that the Replies argue the network was under-tuned. Reading the Reply to Angelini (arXiv:2302.03602) shows the defence is two specific changes: “by simply setting P = 10 we find even further consistent improvements. Specifically, for d = 3 at P = 10 GraphSAGE achieves approximation ratios of AR ~ 0.947, on par with the DGA-based results…” — a different architecture and a penalty five times the published one (P = 10 against 2), well above the pre-registered grid, which stopped at P = 3 and never implemented GraphSAGE. The claim that the objection had been “answered on its own terms” is withdrawn.

On the same seeds 0–2 (every column above), the pre-registered grid buys at most 0.5 percentage points of AR, and the post-hoc round at most 1.1 — its best arms are the modified objective, a change to the loss rather than a tuned setting — and neither approaches the greedy. (The d = 20 column reports densities, as no published bound is adopted there.) At d = 20 every one of the 24 pre-registered runs and every one of the 21 post-hoc runs had an empty raw output: 0 non-empty results out of 45.

The Reply’s own configuration, run as described

GraphSAGE with a mean aggregator was implemented here (the Reply gives no code for it) and crossed with the penalty, giving the four arms below at n = 1000, seeds 0–2, with DGA on the same seeds.

At d = 3, P = 10 moves the GCN slightly in the direction the Reply claims (0.9223 to 0.9289) and still falls short of greedy’s 0.9479 on the same seeds. At d = 5 it makes matters markedly worse (0.8818 to 0.8073, with a non-empty raw output in only 1/3 runs), which the Reply does not mention. These arms were run at d = 3, 5 and 20 only.

One result here is a failure to reproduce, and is reported as nothing more. The Reply states GraphSAGE at P = 10 reaches AR ~ 0.947 for d = 3. This implementation reaches 0.8777 — below its own GCN. The likeliest explanation is that this GraphSAGE is not equivalent to theirs: the Reply gives no architecture detail and no code for it. That is a gap in what can be checked from the published record, not evidence against their number.

The Reply also answers the high-degree benchmark on relevance rather than capability: it calls the d > 16 instances “an interesting academic exercise” but is “not convinced about its practical usefulness”, because real problems are not random regular graphs. That is a different objection from the one measured here. This page concerns random d-regular graphs only, where the ceiling sits at d ≈ 7 (raw output empty in every run from d = 8), below the regime the Reply calls academic; it says nothing about structured real-world graphs.

The published 10⁴ figure was never a controlled measurement. The critique timed its greedy on the authors' own laptop and read the network's times off Figure 5 of the paper it was criticising — different hardware, different conditions. Everything below is one machine, one job at a time, nothing concurrent.

The reference implementation builds a dense torch.zeros(n, n) QUBO matrix. At n = 1,000,000 that is 1.0e+12 float32 entries — 3.6 TiB. The full paper never describes the QUBO construction used at that scale — the word “dense” does not appear in it — so this is a property of the released example implementation, not of a published method description. The sparse reformulation used here is mathematically identical and is what makes any test at this scale possible — a deliberate improvement in the claim’s favour.

The approximation ratios above are measured against McKay's upper bound, which is not tight. To check the scale is sane I solved small instances to proven optimality with an integer program.

Proven optima sit at 0.96–0.98 of the bound at these sizes, consistent with the 1RSB asymptotic value of 0.990. Runs that hit the time limit are reported as lower bounds, not optima.

Stated plainly, because a verdict that cannot be attacked is not worth much:

• The port. The original code is DGL 0.5.3 / torch 1.7.1 and will not run on current hardware, so I ported it to plain PyTorch. The repository’s test checks the port’s forward math against the reference’s, re-derived inline — the loss to machine precision against the true asymmetric Q, the convolution to float32 epsilon — and an adversarial audit found it kills the natural mutations of that math except a row-normalisation mutant, because its normalisation check is vacuous on d-regular graphs (D26), and the GraphSAGE layer is untested, because no reference implementation of it exists. The training loop is outside that proof: its fidelity rests on line-by-line replication of the reference’s bookkeeping and on six fresh reruns that matched the recorded results (D26); training is not bit-deterministic, so re-executing a seeded cell can shift its final loss and epoch count slightly (D38). One reporting deviation exists and favours the network: the port keeps the larger of the best and final bitstrings, where the reference keeps best only.
• The threshold’s location is measured, not derived. The mean-field analysis says where a non-breaking network lands; it does not say why symmetry breaking fails only above d ≈ 6–7 — the uniform point is a strict saddle at every degree.
• Charity where it counts. Every difference from the reference favours the network: a sparse loss it does not have, and a repair-and-maximalize step it does not perform. The greedy gets none of that. One protocol choice cuts slightly the other way: in the device benchmark at n = 10⁵ the GPU (MPS) was 7% faster than the CPU at d = 3 and 1% slower at d = 5, and every GNN run used the CPU (D14); the check was never repeated at n = 10⁶, an unexecuted protocol step.
• The mean-field result is a closed form, checked against measurement, not a fit. −12.500 is L* = −n/(2Pd) under the modified objective, derived after that arm had run (D17) and compared with the measured −12.499. Nothing in it is fitted to the data, which makes it the easiest claim here to check.
• Cells deliberately not run. PI-GNN at d = 5 and d = 20 for n = 10⁵, and at d = 5 for n = 10⁶, were cut on wall-clock grounds after the smaller sizes had already settled those cases — 2.4 hours of machine time for results predictable to three digits, or for a collapse already 10/10 consistent with a closed-form explanation. Their baselines were measured. Saying so beats leaving the gap implicit.
• Prior art. Much of this is anticipated. The null-control idea is Böther et al., ICLR 2022 (arXiv:2201.10494), for a different method; both failure modes are named by Ichikawa, NeurIPS 2024 (arXiv:2309.16965); the density transition is Krutský et al., ECAI 2025 (arXiv:2507.13703). Their MIS tables put the baseline at zero at d = 10, as here (0/10 non-empty); an earlier version of this repository claimed a disagreement at d = 10 by comparing with their MaxCut result, and that claim is withdrawn (D38). What this study adds on that axis is resolution: its degree grid places the MIS transition at d ≈ 6–7, between their grid points 5 and 10.
• What I did not test. MaxCut — Boettcher's concurrent critique targets that, and this study is MIS only. Nor does any of this show that graph neural networks cannot do combinatorial optimisation. It shows that this relaxation, with this projection, does not.

559 measurement records on one Apple M1 Pro (10 core, 32 GB). Greedy baselines are C with a bucket queue, so the timing comparison is not distorted by a slow baseline. Instances are uniform random d-regular graphs, verified simple and exactly regular at generation. Seeds control the graph, the network initialisation and the tie-break together.

# Python 3.12
pip install -r requirements.txt
cc -O3 -march=native -o code/greedy code/greedy.c     # drop -march=native if your compiler rejects it
cc -O3 -march=native -o code/repair code/repair.c
python code/test_port.py            # run first — forward-math port-equivalence check; needs nothing else
python code/analyze.py              # summary tables from the committed results
python code/build_report.py && python code/make_site.py      # regenerate report.html and site/
python code/fetch_refs.py           # optional: the papers + the reference implementation into refs/
# To re-measure rather than re-read, write to a NEW file — drivers skip cells already in --out:
python code/runner.py --out results/rerun_phase1.jsonl --d 3 5 20 --n 1000 10000 --seeds 0 1 2 3 4
# collapse_sweep.py, escape_prob.py, escape_d10plus.py and reply_defence.py take no --out: each
# appends to a fixed file in results/ and skips cells already there, so move that file aside first.
# mv -n never overwrites an earlier move-aside; the published files are tracked by git, so
# `git checkout -- results/` restores them.
mkdir -p results.published
mv -n results/collapse.jsonl results/escape.jsonl results.published/
python code/collapse_sweep.py && python code/escape_prob.py && python code/escape_d10plus.py   # escape table: 121 of its 127 runs (the other 6 are phase-1 runs, re-measured by runner.py above)
mv -n results/reply_defence.jsonl results.published/ && python code/reply_defence.py             # the Reply’s defence, GraphSAGE + P=10 (D37)

Code, the raw results/*.jsonl and the decision log are at github.com/ryanonline1234/gnn-vs-greedy; its README carries the same commands.