Tangle-Restricted Reasoning over Noisy Scene Graphs

Visual question answering systems often answer from context instead of evidence. A model asked about a dog may use the park around it; a model asked about a banana's color may say "yellow" without looking. One clean way to force a model to look is to reason over a scene graph, where detected objects are nodes and predicted relationships are edges, and to run explicit reasoning steps on that graph. This works perfectly on synthetic scenes and poorly on real photos. Explainable and Explicit Visual Reasoning Over Scene Graphs reaches 100% on CLEVR with ground-truth graphs but 67.5% on VQAv2.0 with predicted ones. Part of that gap is that real parsers produce dense, noisy webs of background relations. When reasoning passes messages along these edges, background co-occurrence leaks into the answer.

We propose to cut the graph where it is only weakly attached before reasoning, using a notion of "cluster" from structural graph theory that is designed to survive messy, overlapping cut boundaries. A tangle of order $k$ is a consistent rule that, for every way of splitting the graph by removing fewer than $k$ vertices (a separation), says which side is the "big" side. Tangles and Connectivity in Graphs develops this "compass over cuts" view, and Quasi-4-Connected Components gives a canonical, cubic-time decomposition into pieces that correspond to order-4 tangles. The core idea fits in two sentences. Decompose each predicted scene graph into its tangle regions, and let reasoning steps pass information only inside the region that contains the objects the question mentions. Evidence reached only by crossing a small separator is then treated as suspect context rather than proof.

Core Claim

We make one testable claim. On real scene graphs, a meaningful share of shortcut behavior comes from reasoning paths that cross separators of order at most 3 into a different tangle. Restricting reasoning to the question's tangle should reduce reliance on those shortcuts more than simpler locality restrictions do. The reason is stability under parser noise. Adding or deleting one edge raises or lowers the order of any separation by at most one. So an order-$k$ tangle in the true graph still induces an order-$(k-1)$ tangle in the perturbed graph. Minimum cuts, hop balls and community partitions carry no comparable guarantee. The decomposition is also canonical, meaning it does not depend on node order. Crossing separators do not destroy it; that problem was the reason tangles were invented. Our claim is the empirical counterpart: this stability should show up as robustness when scene-graph noise and background correlation shift together.

This differs from the closest existing work in a specific way. XNM's Transfer module propagates attention along all predicted edges with no structural gating. Don't Just Assume; Look and Answer (GVQA) separates concept recognition from answer prediction with a handcrafted three-module split, and it does not reason about the relational structure among objects. BARE diagnoses "over-entangled" representations and fixes them with learned gates and prototypes, with no model of which cuts separate evidence from context. TangleScore borrows the word "tangle" for a hidden-state shift ratio in LLM editing and uses none of the graph theory. We use the formal object itself, applied to the explicit graph a reasoning model already consumes.

Research Program

The pipeline has three stages. First, we build the scene graph. We use the same detector and relation parser as the XNM real-image setting, then sparsify the graph by keeping each node's top-$d$ relation edges by confidence. Sparsifying matters because a near-complete graph is a single tangle, so decomposition would be vacuous. We treat $d$ as a swept hyperparameter and report how often the decomposition becomes trivial.

Second, we decompose. We compute Grohe's adhesion-3 tree decomposition into quasi-4-connected torsos and small cliques. With $n \le 100$ detected objects, the $O(n^2(n+m))$ cost from Quasi-4-Connected Components takes milliseconds. We deliberately avoid general order-$k$ tangle computation because of the $n^{O(k)}$ cost in Computing with Tangles and Grohe's stated doubt that quasi-5-connectivity is well behaved. Order 4 is the highest order where the theory gives a clean canonical object, and we stay there.

Third, we reason under restriction. The question's anchor nodes come from XNM's initial AttendNode step. We locate the torso or torsos containing most of the anchors' attention mass. Transfer steps are then masked to edges inside those torsos plus their adhesion sets, the at most 3 vertices a torso shares with its neighbors. We also run a soft variant that down-weights edges by how many decomposition-tree edges they cross, in place of the hard mask.

We add a diagnostic called crossing exposure. For each question it measures the fraction of the unrestricted model's final attention mass reached only through a path that crosses an adhesion set. The mechanism predicts that items with high crossing exposure are where the unrestricted model fails under distribution shift, and where restriction helps.

We accept one known cost in advance. The literature shows that forcing models away from shortcuts can lower in-distribution accuracy: about 1% in SOrT-ing VQA Models, and some drop for GVQA. Restriction may lose questions whose true answer really does need background context ("what is the weather"). We will report accuracy by question type rather than hide this.

Baselines

The naive reference point is unrestricted XNM on the same predicted graphs. The file reports 67.5% on VQAv2.0 for XNM (Explainable and Explicit Visual Reasoning Over Scene Graphs). We will rerun it with our detector, parser and sparsification so every method sees identical graphs. Beating it means higher accuracy on the prior-shifted and background-shifted splits with an in-distribution loss no larger than the roughly 1% that SOrT accepted.

The strongest existing prior-robust method in the file is GVQA. Don't Just Assume; Look and Answer reports 39.23% on VQA-CP v1 against 26.88% for SAN. We found no reported result on Lacuna for GVQA on VQA-CP v2. We will reproduce GVQA on both VQA-CP splits under the same training-data budget, and report our method with and without the published visual features. DeVLBert (71.1% VQAv2.0 test-dev) is a pretrained causal-deconfounding model and not comparable in capacity. We cite it as the upper reference for large-model deconfounding, not as a head-to-head target.

Three ablations isolate the key ingredient, which is the tangle structure rather than locality alone. The first is a hop-ball mask: restrict Transfer to the $r$-hop neighborhood of the anchors, with $r$ tuned on validation and the retained edge count matched to our method. The second is a community mask: the same restriction using the Louvain or spectral cluster that contains the anchors. The third is a low-order mask: restriction to the anchors' triconnected component, which is the order-3 decomposition. This ablation tests whether order 4 matters, given the hexagonal-grid failure of order 3 described in Tangles and Connectivity in Graphs. All masks get the same hyperparameter search budget. Our method beats them only if it wins on the shifted splits and on the noise-robustness curve below, by more than seed variance across five seeds.

Why not just…?

Why not just restrict reasoning to a k-hop neighborhood of the question's objects? This is the most serious threat, since most of any gain might come from locality alone. A hop ball has no stability guarantee: one spurious edge from a parser can pull a whole background cluster within $r$ hops. A tangle region needs more than one edge to change. Our edge-noise experiment compares the two directly. If the hop-ball mask matches our method across noise levels, we will report that tangle structure adds nothing over locality, and recast the work as a study of locality restriction.

Why not just use standard community detection? Communities are optimized for density, not for small separators. They are also not canonical, since results vary with random seed and node order. Nothing in the file says community detection fails here, so the community-mask ablation settles the question empirically, measured by accuracy and by partition agreement between clean and perturbed graphs.

Why not just augment with counterfactual images? COCO-Counterfactuals breaks background correlations in the data and gains an average of 5 points on Flickr30k zero-shot retrieval. Its generation, however, is limited to nouns and misses relations, spatial layout and counting, and humans agreed with its counterfactual captions only 73% of the time. Relational shortcuts are the case our method targets. Augmentation and restriction also combine naturally, and we will test the combination.

Why not just gate features as BARE does? BARE is strong in-distribution (91.6% RefCOCO testA for BARE-B), yet falls to 71.69% on RefCOCOg Hard relational queries (BARE). That is the multi-object relational regime where explicit structure should help. We do not claim to beat BARE on grounding. We report its numbers as context for where learned gating stops helping.

Proposed Experiments

The first experiment is a controlled test we call CLEVR-Spurious. We start from CLEVR and CLEVR-CoGenT ground-truth scene graphs, where XNM is at 100%. We inject background clusters of distractor objects whose attributes correlate with answers in training and anti-correlate at test. Each cluster attaches to the foreground through fewer than 4 vertices. We also add random relation edges at rates from 0% to 30% to imitate parser noise. The deciding measurement is an accuracy-versus-noise curve for our method against the hop-ball and community masks. The stability argument predicts that our method's advantage grows with noise until the injected edges start merging tangles. The mechanism fails if the curves coincide.

The second experiment uses real prior shift. We train on VQA-CP v2 and on VQAv2.0 with predicted graphs, then report accuracy overall, by question type, and binned by crossing exposure. The central prediction is that the gain over unrestricted XNM concentrates in the high-exposure bins. If it spreads evenly across bins, the gain is not coming from separator crossing, whatever the overall number shows.

The third experiment checks triviality and cost. For each sparsification level $d$, we report the fraction of real scene graphs whose decomposition has a single torso, along with the decomposition time. If most real graphs are one torso at useful $d$, the method is not applicable to real scenes. We will state that plainly, since it would be informative about why the perception bottleneck resists structural fixes.