neural-mis

Neural Maximum Independent Set

A 4-layer graph convolutional network (GCNConv, residual connections, LayerNorm, hidden dim 32) trained entirely on free synthetic Erdos-Renyi graphs, evaluated against QOBLIB's Maximum Independent Set benchmark — a suite built by IBM Quantum, ZIB, and Purdue to benchmark quantum optimization methods. This model uses classical deep learning on the same problem instead.

Code, full evaluation, and the two documented negative findings along the way: github.com/Bauxitiego/neural-mis.

Result, stated plainly

Beats a classical greedy baseline on 23 of 50 QOBLIB instances, ties on 22, loses on 5 — concentrated, not evenly spread. Wins land where greedy was weakest (frb/BHOSLIB: 5 wins, 0 losses; C-family: 3/3 wins). One family, keller, fails badly (0.29-0.36 drop in solution quality relative to greedy) despite two independent, documented attempts to fix it. Full per-family table in the repo's notes/GATE1.md.

This is not "the GCN beats greedy." That framing is true on the pooled number and false in spirit — see the repo's README for why the per-family breakdown is the actual result.

What this proves, and what it doesn't

GNN-guided construction heuristics for Maximum Independent Set are established technique (Li, Chen & Koltun 2018). This isn't a new method. What's here is an honest, reproducible evaluation on a specific, credible, quantum-optimization-relevant benchmark, validated against QOBLIB's own exact ground truth (38 of 50 instances have proven-optimal solutions).

Usage

Requires the model architecture from the repo (src/model.py), since this checkpoint is state_dict-only, not a full serialized module.

import torch
from model import MISNet  # from github.com/Bauxitiego/neural-mis, src/model.py

model = MISNet(hidden_dim=32, n_layers=4)
model.load_state_dict(torch.load("gcn.pt", map_location="cpu"))
model.eval()

Then use gcn_infer.iterative_decode(model, graph) from the same repo — the static, one-shot decode fails badly (see notes/GATE2.md), the iterative one (re-running inference on the residual graph after every pick) is what produces the result above.

Training data

500 synthetic Erdos-Renyi graphs (20-2000 nodes, density 0.05-0.5), each labelled via randomized-greedy-plus-local-search with 20 restarts per graph. Never touches QOBLIB's evaluation instances. Regenerable from the repo, not separately hosted here.

License

Apache 2.0 (code and model weights). QOBLIB data used for evaluation is CC BY 4.0, attribution in the repo's data/qoblib-07-independentset/PROVENANCE.md.