Complement-Normalized Edge Budgets for Scene Graph Pruning

Scene graph models first detect objects in an image and then decide which pairs of objects are actually related ("man riding horse"). Because almost every pair is unrelated, the strongest systems throw most pairs away before doing any relational reasoning. They do this with a fixed budget, such as the top fixed percentage of pairs, the top few neighbors per object, or a few hundred edges per image. This proposal asks whether that budget can be set per image from a quantity that does not depend on scene size. Graph theory's Nordhaus-Gaddum inequalities supply such a quantity. They are sharp bounds on how a graph property, summed over a graph and its complement (the graph made of exactly the missing edges), can vary for a fixed number of nodes. Where a scene's true relation graph falls inside that sharp interval gives a size-free "how pruned should this be" coordinate. The idea is to predict that coordinate from the image and prune until the kept graph reaches it.

Put in two sentences: pruning a candidate relation graph is the same act as growing its complement, so a property measured on the pair (graph, complement) has known worst and best values for $n$ objects. We test whether the position between those values is more stable across scenes, and easier to predict, than raw edge counts, and whether it makes a better per-image stopping rule than a fixed budget. The result could be negative, and the design is built so that a negative result is informative.

Core Claim

The fixed-budget problem is documented in the pruning literature. Devil's on the Edges: Selective Quad Attention for Scene Graph Generation (SQUAT) scores all pairs with a small network and keeps the top $\rho\%$ before attention-based reasoning. It shows that hard pruning matters: removing its edge selection costs nearly 9% mR@100. IS-GGT samples edges autoregressively and finds that performance peaks at 200–250 edges. It also reports a ceiling of about 30.7% constrained accuracy at that budget. Spatial-Aware Graph Relation Network keeps the top $t$ links per region. All three motivate this proposal, because each picks one number for an empty room and a crowded street alike. None of them looks at the structure of what was discarded.

Our claim concerns the degree-function index from Extremal Graphs to Vertex Degree Function Index for Convex Functions. That index is $H_f(G)=\sum_v f(d(v))$ for a convex $f$, where $d(v)$ is the number of edges at node $v$. The relevant sum is then

$$ S_f(G) = H_f(G) + H_f(\bar G) = \sum_{v} \big[f(d(v)) + f(n-1-d(v))\big], $$

where $\bar G$ is the complement and $n$ the number of detected objects. He et al. prove sharp lower and upper bounds $L_f(n) \le S_f(G) \le U_f(n)$ for general, not necessarily connected, graphs. We define the complement-normalized coordinate

$$ z(G) = \frac{S_f(G) - L_f(n)}{U_f(n) - L_f(n)} \in [0,1]. $$

Two properties make $z$ useful rather than decorative. First, in the sparse regime of scene graphs every degree is below $(n-1)/2$. There, removing an edge pushes both endpoint degrees toward the extreme, so $S_f$ increases monotonically as we prune. A target value of $z$ is therefore a well-defined stopping point for greedy pruning in score order.

Second, a convex $f$ makes $z$ sensitive to how concentrated the degrees are, not only to how many edges there are. A scene where one person relates to eight objects gets a different $z$ than one with eight scattered pairs. Fixed top-$K$ ignores this distinction. Per-node top-$t$ actively destroys it.

The claim is falsifiable. If $z$ carries no information beyond the edge count normalized by $n$, the method collapses to a learned edge-count predictor, and we will report that.

We use the degree-function index rather than the Steiner or total-proper-connection results (Nordhaus-Gaddum-type results for the Steiner Wiener index of graphs, Nordhaus–Gaddum-Type Theorem for Total-Proper Connection Number of Graphs). Those results constrain the design by excluding themselves: their sharp bounds assume both the graph and its complement are connected. Scene graphs are routinely disconnected, and the disconnected case is listed as open. Their invariants are also costly to compute inside a training loop.

The symmetric division deg index from Sharp bounds on the symmetric division deg index of graphs and line graphs serves as a second, edge-level invariant. It measures degree imbalance across edges and is cheap to evaluate. It is a secondary probe, not the core mechanism.

Research Program

Measurement study. On Visual Genome ground-truth relation graphs (Visual Genome, using the standard 150-object, 50-predicate split), we compute $z$ for several convex $f$ (squares, $x\log x$). We also compute edge density $m/\binom{n}{2}$ and per-node mean degree. The question is which of these is flatter as $n$ grows, and which is better predicted from pooled image features by a small regressor. We measure predictability as held-out $R^2$ and as rank correlation with the budget that would maximize per-image recall.

A small theory deliverable. The generic He et al. interval spans from star-like to path-like extremes. At scene-graph densities that interval may be so wide that $z$ crowds near 1. We will derive the sharp interval for the restricted class of graphs on $n$ vertices with maximum degree at most $\Delta$, allowing disconnection. This partially addresses the disconnected-case gap noted for Direction 1. We will use whichever interval spreads real scenes more evenly.

Stopping rule. We attach a head that predicts $\hat z$ from image and detection features, trained on ground-truth $z$. At inference, edges are removed in ascending order of an existing edge scorer until $z(G)\ge \hat z$. This happens before any relational reasoning layers, so the rest of the network is unchanged. Because the pruning order still comes from the learned scorer, the only thing that changes is how many edges, and in which degree pattern, survive.

Baselines

The naive reference point is no pruning. It reuses SQUAT's ablated configuration with edge selection removed, which the paper reports costs nearly 9% mR@100. The point of this baseline is to confirm that our reimplementation reproduces the gap pruning provides.

The strongest existing method on the shared benchmark is SQUAT's fixed top-$\rho\%$ rule. SQUAT reports 16.5 mR@100 on Visual Genome scene graph detection and a weighted score of 43.5 on Open Images v6. IS-GGT reports 20.7% mR@100 averaged across the three Visual Genome protocols. That figure is not directly comparable to a single-protocol number, so we cite it only as context. We will retrain SQUAT with the same detector, schedule and seeds, and tune $\rho$ on the validation split with the same number of trials our method receives for its single hyperparameter. Our method then differs from SQUAT only in its stopping rule. Beating SQUAT means a statistically reliable mR@100 gain across three seeds at equal or lower average kept-edge count.

Two further fixed rules complete the fixed-budget picture. One keeps a fixed 200–250 edges, as IS-GGT does. The other keeps the top $t$ per node, as SGRN does. Both are tuned under the same budget.

The decisive ablation keeps everything identical but replaces the $\hat z$ head with a head that predicts the normalized edge count $\hat m / n$ from the same features. Pruning then stops at that count. This isolates the one ingredient the proposal adds: degree-concentration awareness under complement normalization.

A second ablation drops normalization by the sharp interval and predicts raw $S_f$. This tests whether the Nordhaus-Gaddum interval contributes anything beyond the convex-degree statistic itself.

Why not just…?

Why not just use soft attention and skip pruning? SQUAT's ablation directly measures this: soft weights over thousands of background pairs add up to noise, and removing hard selection costs nearly 9% mR@100. We still run the no-pruning baseline, so the claim is checked in our own setup rather than assumed.

Why not just prune by box overlap or distance? Human-object Behavior Analysis Based on Interaction Feature Generation Algorithm shows that geometric pruning works for human-object interaction, reaching 27.89% on HICO-DET. Scene graphs, however, contain non-touching relations such as "looking at", and a pure geometric filter cannot keep those. We include an overlap-plus-distance filter as an additional pruning-stage baseline. We report its ground-truth edge recall at matched kept-edge counts so the trade-off is visible.

Why not just predict how many edges to keep, or threshold calibrated per-pair probabilities? This is the real threat. A per-image count predictor, or a sigmoid threshold in the style of On Class Imbalance and Background Filtering in Visual Relationship Detection, already adapts to scene complexity. The latter raised Neural Motifs mPCR from 15.06 to 29.03. We do not argue around this. The count-predictor ablation and a tuned sigmoid-threshold baseline are both run under identical budgets. If either matches the $z$ rule, the conclusion is that degree concentration adds nothing and that complement normalization is unnecessary for this task. That would be a clean negative result about whether Nordhaus-Gaddum structure is relevant to learned pruning.

Proposed Experiments

The first decisive check happens before any training. On Visual Genome ground truth, $z$ must show lower variance across object-count bins, and higher held-out predictability from image features, than normalized edge count. If it does not, the program stops at the measurement study.

The second check is at the pruning stage. At matched average kept-edge counts, the $z$ rule should retain a larger share of ground-truth edges than fixed top-$\rho\%$. It should retain an even larger share for rare predicates, measured as per-predicate edge recall, because hub objects tend to carry many rare relations. If the gain appears, it should also show up as headroom against the IS-GGT-style ceiling, computed as the oracle best accuracy given the kept edges.

The third check is end to end. We measure mR@50 and mR@100, together with R@K, for predicate classification, scene graph classification and scene graph detection on Visual Genome, and the weighted score on Open Images v6. Here the method must beat both the retuned SQUAT and the count-predictor ablation.

We will also report the gain split by object count. The method's premise predicts that the advantage should grow in crowded scenes and vanish in sparse ones. Seeing that pattern is as important as the headline number.