Diego F. Martínez-Valencia
Machine learning applied to quantum computing.
A GCN beats greedy on 23 of 50 hard graphs, and loses badly on one family
Short version: a graph convolutional network trained entirely on free synthetic graphs, evaluated against QOBLIB's Maximum Independent Set benchmark, beats a classical greedy baseline on 23 of 50 instances, ties on 22, and loses on 5. The wins land exactly where greedy was weakest. One graph family, keller, it loses badly, and two separate attempts to fix that did not work. All of that is in the public repo, including the failures.
Why this benchmark
QOBLIB was built by IBM Quantum, ZIB and Purdue to benchmark quantum optimization methods against ten hard combinatorial problem classes. I used classical deep learning on one of them instead: Maximum Independent Set, given a graph, find the largest set of vertices with no edge between any two of them. NP-hard, simply stated, and QOBLIB hands you something most benchmarks don't: 38 of its 50 instances have a proven-optimal solution already, and the other 12 have a documented best-known value. There is no proxy metric to argue about. A proposed set is either as good as optimal or it isn't.
Several of the instances are the classic DIMACS/BHOSLIB graphs from the max-clique literature, deliberately inverted to independent-set form by QOBLIB so results are comparable to that literature. Graph neural networks for this exact problem go back to Li, Chen and Koltun's 2018 paper on GCNs with guided tree search. Nothing about the architecture here is new. What's mine is applying it honestly to a specific, credible, quantum-relevant benchmark, with training data that never touches the evaluation set.
A mistake I caught, not one I avoided
The original plan was to validate against Li et al.'s published table on the shared instances, the same way the decoder project validated against a known matching baseline before trusting anything downstream. I wrote that plan from memory. Partway through the build I actually read the paper, and their benchmarks are SATLIB, SAT Competition 2017, BUAA-MC, SNAP Social Networks and citation networks. None of them overlap with QOBLIB's DIMACS/BHOSLIB graphs. The comparison I'd planned doesn't exist.
I left the wrong claim in the spec with a dated correction next to it rather than quietly editing it away, because the honest version of this project includes getting things wrong before getting them right. The fix was straightforward once I stopped and thought about it properly: QOBLIB already provides something stronger than a matched external table, exact optimal ground truth on most of the instances. Validation became beating the classical greedy baseline by a real margin, measured against that ground truth directly.
The first model was worse than doing nothing clever
The first trained model, decoded by ranking every node once from the GCN's predicted probabilities and building a set greedily against that fixed order, lost to plain greedy on 36 of 50 held-out synthetic graphs. Not failed to beat it. Worse: mean set size 18.88 against greedy's 21.16.
The predictions themselves were fine. Checked directly: probability correlated with node degree at -0.68, the direction you want, low-degree nodes scoring highest. The problem was the decode, not the model. Classical greedy recomputes degree after every node it removes, so its notion of "best next choice" adapts as the graph shrinks. My decode computed one ranking from the original graph and never updated it. However good the initial ranking, a static order can't track how a node's neighbourhood changes as construction proceeds.
The fix was re-running the GCN's forward pass on the residual graph after every pick instead of committing to one pass. Same trained model, no retraining needed, since this was a decode-time problem. Held-out result went from 1 win, 0 ties, 49 losses to 29 wins, 17 ties, 4 losses. It's worth saying plainly that Li et al.'s own ablation table shows their raw GCN output alone, without tree search, solving only 18.8% of their test instances against 100% for the full pipeline. Static output being weak on its own isn't a surprise in this literature. It would have been a surprise if I'd shipped the static version without checking.
The result
Wins land exactly where greedy was weakest. keller is the one family where the GCN is worse than doing nothing clever at all.
| Family | Instances | Greedy mean | GCN mean | Wins / ties / losses |
|---|---|---|---|---|
| frb (BHOSLIB) | 5 | 0.817 | 0.872 | 4 / 1 / 0 |
| C (DIMACS random) | 3 | 0.867 | 0.933 | 3 / 0 / 0 |
| R (thesis-generated random) | 2 | 0.910 | 0.958 | 2 / 0 / 0 |
| johnson, insecta, c-fat, real-world | 14 | ~0.98-1.00 | same or better | mostly ties |
| keller | 2 | 0.907 | 0.581 | 0 / 0 / 2 |
Overall 21 wins, 25 ties, 4 losses out of 50 — that headline count is real, but it isn't the
finding. The finding is where. frb and C, the families greedy struggled hardest with
in the baseline, are exactly where the GCN closes the most ground. The families where greedy
was already near-optimal stayed near-optimal either way, because there wasn't room to move.
And keller dropped hard: keller4 from 1.000, greedy already optimal, to 0.636. keller6
from 0.814 to 0.525.
A pooled number like "wins more often than it loses" would be technically true and would hide the actual shape of the result. Every table in the repo is reported by family for this reason.
What I tried on keller, and what didn't work
Two things, both negative, both kept in the record rather than dropped.
First hypothesis: keller graphs are near-regular, so a model that leaned on "prefer low degree" as its main signal would have nothing to grab onto. Checked directly: keller4 and keller6's degree coefficient of variation, 0.12 and 0.09, isn't meaningfully different from brock200-1 at 0.04, which the model handles fine. Disproven by the data already on hand, without needing an experiment.
Second hypothesis: keller graphs have real excess clustering relative to a random graph at the same density, keller4 measured at 0.44 against an Erdos-Renyi-expected 0.35, and the training set was pure Erdos-Renyi, which has none of that structure by construction. Plausible enough to test. I added Watts-Strogatz small-world graphs to the training corpus, thirty percent of a fresh 500-graph set, and retrained from scratch.
keller4 came back at 0.636. keller6 came back at 0.525. Identical to three decimal places, despite a genuinely different training corpus and a full independent training run. That result is more informative than a small improvement would have been: it suggests degree dominates the decode so strongly on these specific graphs that changing the training distribution's clustering statistics didn't change which node gets picked first at each step. The excess-clustering explanation is now ruled out by experiment, not just weakly supported. Whatever keller actually needs, it's more specific than that, and I don't have it yet.
What this is and isn't
The method is not new. GCN-guided construction for Maximum Independent Set is Li, Chen and Koltun's approach from 2018, and I followed it closely rather than inventing an alternative. What's mine is the evaluation: a specific, credible, quantum-optimization-relevant benchmark, training data that's free and never touches it, ground truth that's exact rather than approximate on most instances, and a result reported by family because the pooled number would have said something true and misleading at the same time.
Two failed fixes for keller are also in the repo. Whatever it actually needs is more specific than either hypothesis I tried, and I still don't have it.
Code, every script, and the two negative results in full: github.com/Bauxitiego/neural-mis. Model: huggingface.co/Bauxitiego/neural-mis. Training data: huggingface.co/datasets/Bauxitiego/neural-mis-training-graphs.