Most systems that turn an image into a scene graph (a list of objects plus labeled relations such as "man holding bat") work in two stages. A detector first decides which boxes are objects. A relation model then labels pairs of those boxes. The handoff between the stages is a hard filter: the detector's duplicate-removal step, non-maximum suppression (NMS), keeps the highest-scoring box and deletes any box that overlaps it too much. A confidence threshold then removes weak boxes. Anything deleted at this point is gone for good. The relation model never sees it, however strongly the rest of the scene implies it exists. Several papers document this ceiling: CURVE states outright that its relation-level robustness cannot recover an object its Mask R-CNN detector missed. The proposal here is to move the deletion decision after relation evidence is available. Detection and relation selection become one global energy minimization over binary keep/drop variables. A weak, half-occluded person box can then survive because a confidently detected bat needs a holder, while a true duplicate still dies because it brings no new relational support.
The second half of the proposal treats the solver as an object of study. Variational quantum algorithms, in which a shallow quantum circuit is tuned by a classical optimizer in a closed loop, are reported to "absorb" systematic errors. In Barkoutsos et al., the classical loop compensated for a coarse single-step approximation, and in Qi Yin it compensated for hardware miscalibration. We argue that this absorption cannot fix noise in the cost itself: optimizing harder only finds the minimum of the wrong energy. Absorption can, however, be recreated one level up. If the weights that build the energy from detector outputs are learned with the approximate solver inside the training loop, the learned weights can compensate for that solver's characteristic mistakes. This gives a concrete, testable bridge between the two literatures, and it does not depend on any claim that quantum hardware is faster or better.
Core Claim
We make two claims, and both are solver-agnostic by design. First, a joint box-and-relation energy recovers ground-truth objects that standard NMS plus thresholding discards, and the gain should be concentrated in crowded, heavily occluded regions. That is exactly where box-only global suppression, QSQS, lost to plain NMS on the CityPersons "Heavy Occlusion" subset. Our explanation for that failure is that box-only pairwise penalties see only overlap. Two people standing close together and two boxes on one person look identical to such a penalty. Relational terms break the tie, because two distinct people participate in different relations. Second, when the energy weights are trained with an approximate solver in the loop, deployment accuracy with that solver approaches deployment accuracy with an exact solver. When they are trained with an exact solver and deployed with an approximate one, it does not. The approximate solvers are shallow QAOA (the Quantum Approximate Optimization Algorithm), a variational circuit for binary optimization, and simulated annealing. We expect this "in-loop absorption" effect to hold for classical heuristics too. The quantum question is narrower: at the cluster sizes that matter in crowded scenes, does a variational solver behave differently from classical heuristics?
Research Program
The energy is defined over a local cluster of candidate boxes taken from a standard detector with a deliberately permissive score floor. Let $x_i \in \{0,1\}$ mark whether box $i$ is kept, let $y_{ij} \in \{0,1\}$ mark whether the top-scoring relation between boxes $i$ and $j$ is asserted, let $s_i$ be the detector score, let $o_{ij}$ be box overlap, and let $r_{ij}$ be the relation classifier's score. Then
$$ E(x,y) = -\sum_i a_i s_i x_i + \sum_{i<j} b_{ij}\, o_{ij}\, x_i x_j - \sum_{(i,j)} c_{ij}\, r_{ij}\, y_{ij} + \lambda \sum_{(i,j)} \left(2y_{ij} - y_{ij}x_i - y_{ij}x_j\right). $$
The last term is zero when a relation is asserted only between kept boxes and positive otherwise. The whole energy is therefore quadratic in binary variables, the same problem form (a QUBO) that QSQS sent to a D-Wave annealer. The coefficients $a, b, c$ are outputs of small networks that read box features, class labels, and pair geometry. The constraint weight $\lambda$ is fixed large. The key structural difference from QSQS is the edge variables and the reward they carry. Through them, relation evidence can pay for keeping a box that the overlap penalty would otherwise remove.
Scenes are split into clusters of mutually overlapping or relation-linked boxes. Most clusters are trivially small and are solved exactly. Dense clusters are capped at roughly 20 to 30 binary variables. We keep only one predicate per pair and only pairs with nonzero relation prior. At this size the exact optimum is cheap to compute classically, which gives a ground-truth solver for every comparison. The cap is also the size at which Schwägerl et al. found variational circuits starting to beat random sampling (around 30 variables) and holding their largest lead over greedy search (around $N=31$). That paper's numbers come from Max-Cut on 3-regular graphs, not from vision energies like ours. They motivate the size cap but do not predict our results, and the same work warns that small instances trap variational circuits in poor minima. That warning is why the exact solver is in the comparison.
The coefficient networks are trained on Visual Genome with a structured hinge loss. The solver's output on a loss-augmented energy serves as the "most violating" configuration, so any black-box solver can sit inside training without needing gradients through it. Four solvers are interchangeable at both training and test time. The first is exact enumeration or branch-and-bound. The second is greedy local search. The third is simulated annealing. The fourth is depth-$p$ QAOA with a CVaR objective, which scores the circuit by its best sampled outcomes, matching the setup of Schwägerl et al., run on a statevector simulator. A small number of runs on physical hardware are added only to check that simulator conclusions survive real gate noise. Following VQNHE, which used a classical network to post-correct a shallow circuit's output, we also test a cheap classical repair step: one pass of local search started from the circuit's best sample. This tells us whether any quantum benefit comes from the circuit or from the repair.
Downstream, the kept boxes and asserted edges replace the Faster R-CNN plus NMS output that feeds a Neural Motifs relation model. Neural Motifs is the setup whose output, according to Zhong et al., caps caption quality. Everything else is held fixed, so any downstream change is attributable to the selection step.
Baselines
The naive reference point is the standard cascade: a Faster R-CNN detector, greedy NMS, a fixed score threshold, and the Neural Motifs relation model on top. Its role is to measure the omission ceiling we claim to lift. Run on our own detector, it supplies the "rescued recall" denominator: ground-truth objects that had a matching candidate box before suppression and lost it afterwards.
The strongest box-level competitor is QSQS, which solves a box-only QUBO with overlap penalties and soft rescoring. It reports 75.11% mAP on PASCAL VOC 2007 against 74.20% for NMS. It reports no exact numbers for CityPersons or COCO, only that NMS beat it in heavy occlusion. We reimplement it as our energy with the edge variables removed. That reimplementation is solved by the same four solvers, uses the same detector and candidate pool, and gets the same tuning budget for its coefficients. First we must reproduce roughly its VOC gain over NMS. Beating it then means a clear advantage on CityPersons heavy occlusion, where it lost, without giving back its VOC gain. This box-only variant is also the main ablation, because it isolates the contribution of the relational terms.
The strongest scene-graph competitor without a detector stage is Pixels to Graphs by Associative Embedding. It predicts objects and relation midpoints directly from pixels and reports Visual Genome scene graph generation (SGGen) Recall@100 of 11.3%, against a prior 4.2%. We compare against this reported figure and against our own retrained cascade baseline at matched backbone and training compute. Neural Motifs reports only relative gains (7.1% over its frequency baseline), so we rerun it rather than quote an absolute number. Beating these baselines means higher SGGen Recall@100 and higher mean per-predicate recall than our retrained Motifs cascade, with the difference coming from recovered objects rather than better relation labels on objects both systems already kept.
The solver ablation compares exact, greedy, annealing, and QAOA solvers under a matched budget of energy evaluations, following Schwägerl et al. A cross-training ablation compares weights trained with solver A and tested with solver B, for every pair. This ablation isolates the in-loop absorption claim.
Why not just…?
Why not just lower the NMS threshold, or use Soft-NMS, and let the relation model sort out duplicates? This is the most serious threat to the first claim, because the relation model would then see the occluded box. The trouble is that Neural Motifs-style models reason over whatever boxes they receive. The Neural Motifs analysis shows how heavily their predictions lean on label co-occurrence, so extra duplicates should produce duplicated, plausible-looking relations rather than being filtered out. We test this directly. We sweep the NMS and Soft-NMS thresholds and the score floor feeding a retrained Motifs model, and plot SGGen precision against recall. If some point on that curve matches our method's recall at equal precision, the joint energy adds nothing, and we will report that.
Why not just solve the same energy with a classical solver? For clusters of 20 to 30 variables, an exact classical solver is fast. We expect it to match or beat QAOA on solution quality, and the QSQS latency result (1.44 times slower than NMS end to end) argues against any deployment case for quantum hardware. We concede this point in advance. Both main claims are stated so that they hold for classical solvers. The quantum component is evaluated as a scientific question: where on the cluster-size axis does a variational solver, trained in the loop, sit relative to annealing and greedy search? If QAOA is dominated everywhere, that is a useful negative result on a non-synthetic problem distribution. That kind of distribution is missing from the Max-Cut benchmarks.
Why not just train an end-to-end pixel-to-graph model and drop the detector? Newell and Deng did this. They report output-slot collisions on a fixed 64x64 grid in crowded scenes and near-zero recall on rare predicates. Crowded scenes are exactly where the omission problem lives. We compare on their reported Recall@100 and also break results down by scene crowding. Their reported failure mode predicts that the gap in our favor should grow with crowding. If it does not, the end-to-end route is the better answer.
Why not just rely on uncertainty-guided pruning as in CURVE? CURVE estimates per-edge uncertainty and prunes unreliable relations, which improves robustness to out-of-distribution shifts (DeepAccident MCC of 35.07 against 12.91 for RS2G). It only removes structure, though; it cannot add a node, and its authors note that it can over-prune rare events. The two methods are complementary, not competing. Our energy decides which nodes exist, and CURVE could run afterwards on the result.
Proposed Experiments
The first decisive check is rescued recall on Visual Genome. On held-out images, we count ground-truth objects that had a matching candidate box before NMS and were lost by the standard cascade. We then measure the fraction our energy keeps, together with the duplicate rate this introduces. We report the result in bins of occlusion and crowding, and alongside SGGen Recall@50/100 and mean per-predicate recall. The first claim holds if rescued recall rises substantially in the most crowded bin, the duplicate rate stays at most at the Soft-NMS sweep's matched-recall level, and the gain disappears when the edge variables are removed.
The second check transfers the method to CityPersons heavy occlusion. CityPersons has no relation labels, so the relation term uses a Visual Genome-trained person-to-person and person-to-object relation scorer, frozen. Missing-rate curves are compared against NMS, Soft-NMS, and the reimplemented QSQS. Lacuna lists no reported CityPersons numbers for QSQS, so all three baselines are rerun here. Showing that relational terms reverse QSQS's heavy-occlusion loss would directly support our explanation of why that method failed.
The third check is the solver cross-training grid on dense clusters, swept by cluster size from about 8 to 30 variables. Each cell reports downstream SGGen recall and the energy gap to the exact optimum. The in-loop absorption claim holds if matched train-and-test pairings with an approximate solver close most of the gap to exact deployment, while mismatched pairings do not. The quantum-specific result is where QAOA, with and without local-search repair, falls relative to annealing and greedy search at matched evaluation budgets. Schwägerl et al.'s Max-Cut results suggest any QAOA advantage would appear only near the top of this size range. A small set of hardware runs at the largest feasible cluster size checks whether simulator conclusions survive real gate noise. Finally, a caption-level check passes the recovered graphs to the Zhong et al. captioner. It asks whether lifting the detection ceiling actually reaches the task that the ceiling was shown to limit.
References
- CURVE: Learning Causality-Inspired Invariant Representations for Robust Scene Understanding via Uncertainty-Guided Regularization
- Quantum algorithms for electronic structure calculations: Particle-hole Hamiltonian and optimized wave-function expansions
- Realization of a quantum autoencoder for lossless compression of quantum data
- Quantum-Soft QUBO Suppression for Accurate Object Detection
- Benchmarking variational quantum algorithms for combinatorial optimization in practice
- Variational Quantum-Neural Hybrid Eigensolver
- Neural Motifs: Scene Graph Parsing With Global Context
- Comprehensive Image Captioning via Scene Graph Decomposition
- Pixels to Graphs by Associative Embedding