Width-Budgeted Constraint Networks for Annotation-Free Part Labeling

Unsupervised part discovery methods split an image of a bird, car or dog into parts without anyone drawing part masks. They routinely produce labelings that no real object could have. Two patches both get called "left wing". A head is labeled even though it is occluded. A leg ends up on the wrong side of the torso. These errors come from labeling each patch, or each part, more or less independently, using soft attention or clustering. The usual remedy is human part annotation, which is the cost the field is trying to avoid (How Do You Tell a Blackbird from a Crow?; Guest Editorial: Introduction to the Special Section on Fine-Grained Visual Categorization). This proposal takes a different route. For each object category, learn from unlabeled images a small constraint network: a set of rules that each tie together two or three parts. A rule might say "the beak lies on the far side of the head from the tail" or "the left and right wings are distinct patches on opposite sides of the body axis." Then find the single most consistent labeling of every image exactly, rather than approximately.

Rules over three parts at once are what make this both useful and dangerous. They can express relative orientation, which pairwise rules cannot. But exact inference over arbitrary three-way rules is intractable in general. The theory of constraint satisfaction problems (CSPs: find values for variables that satisfy every rule) gives a precise escape hatch. If the hypergraph of rules has bounded fractional hypertree width, exact inference costs polynomial time with the width in the exponent (Constraint Solving via Fractional Edge Covers). A hypergraph here is a graph whose "edges" can join three or more nodes. Fractional hypertree width measures how close that hypergraph is to a tree. We therefore learn the rule structure under an explicit width budget. Exact width checkers act as the gatekeeper on which rules are allowed in. The exact labelings are then used as pseudo-labels that retrain the part discoverer. The measurable question is how much part annotation this saves.

Core Claim

Per-category constraint networks over discovered parts, made of pairwise and three-way geometric rules and learned under a hypertree-width budget of 2 or 3, can be solved exactly over all candidate patches. A "null" value in each part's domain handles occluded parts. We claim three things. First, exact solutions remove physically impossible labelings that attention-based matchers produce. Second, used as pseudo-labels, they improve unsupervised part segmentation on CUB-200-2011 and PartImageNet. Third, they reduce the fraction of PartImageNet part masks needed to approach supervised accuracy.

What would be new is not "use a CSP for vision"; On the Minimality and Decomposability of Constraint Networks already cast scene labeling as a CSP, for binary constraints on toy rectilinear scenes. What is new is treating the structure of the rule set as something learned from data under a certified width bound, with higher-order rules, and closing the loop back into an unsupervised part learner.

The width-recognition literature plays a specific, modest role here. Deciding whether fractional hypertree width is at most 2 is NP-complete in general (A More General Theory of Static Approximations for Conjunctive Queries; Complexity Analysis of Generalized and Fractional Hypertree Decompositions). But our hypergraphs only contain edges of size two or three, so any two edges share at most two vertices. That places them in the bounded-intersection class, where Complexity Analysis of Generalized and Fractional Hypertree Decompositions shows the fractional check is polynomial for fixed $k$. It is also the $(2,d)$ setting, with $d=2$, of FPT Approximation of Generalised Hypertree Width for Bounded Intersection Hypergraphs. The hardness results therefore do not block us. What we need is a fast, exact, certified checker that can be called thousands of times inside a structure-learning loop.

Research Program

Part proposals and domains. We start from an existing unsupervised part discoverer. The primary choice is MPAE from Unsupervised Part Discovery via Descriptor-Based Masked Image Restoration with Optimized Constraints, which reconstructs masked images from learned part descriptors and already allows parts to be absent. We use it with a fixed number of parts $K$ (16 on CUB, 50 on PartImageNet, matching that paper). Each part is a CSP variable. Its domain is the top-$m$ candidate patch locations by descriptor similarity, plus a null value meaning "not visible". The null value is how we address the presence problem noted in Gap 3 of the file. Width theory assumes a fixed, well-formed hypergraph. So we keep the hypergraph fixed per category and let domains absorb occlusion, rather than deleting vertices image by image.

Rule families. Rules come in two forms. Pairwise rules are soft costs on relative displacement between two parts. Three-way rules are soft costs on the signed angle that one part makes with the line through two others. This orientation term is what distinguishes left from right and resolves the duplicate-wing error. Rule parameters are fitted by maximum likelihood on high-confidence MPAE outputs, with no annotations.

Width-budgeted structure learning. Candidate three-way rules are ranked by how much they reduce held-out negative log-likelihood. They are added greedily, and each addition is accepted only if a width checker certifies that the resulting hypergraph stays within the budget $k$. The checker we deploy is the SAT/SMT solver of Computing Optimal Hypertree Decompositions with SAT. It computes exact hypertree width, which upper-bounds the fractional width, so passing it is a valid certificate. It also returns a decomposition we use directly for inference.

Two diagnostics run alongside. We compute the fractional width of the final decomposition by linear programming to quantify slack. We also run an unbudgeted greedy pass to measure how wide "natural" part rule networks are per PartImageNet super-category. That pass is a cheap empirical test of a van Beek-style conjecture: that vision constraint networks are structurally benign.

Exact inference. Inference is dynamic programming over the decomposition. Each bag joins candidate tables, and by the Shearer-lemma bound in Constraint Solving via Fractional Edge Covers, bag tables have at most $(m+1)^{\text{fhw}}$ rows. That bound is why the budget matters most when $m$ and $K$ grow. The output is the minimum-cost labeling, including nulls, for each image.

Self-training. The exact labelings become pixel pseudo-labels, through patch-to-part assignment, and are used to fine-tune the part discoverer. We alternate rule fitting and retraining for a small fixed number of rounds.

Baselines

The naive reference point is MPAE itself, with its own argmax part labeling and no further processing. It is also the strongest existing unsupervised method in the file. On PartImageNet out-of-distribution evaluation with $K=50$, Unsupervised Part Discovery via Descriptor-Based Masked Image Restoration with Optimized Constraints reports NMI 53.65% and ARI 74.22%. NMI and ARI are clustering-agreement scores that compare discovered parts with ground-truth part masks. On CUB it reports only relative gains over PDiscoFormer: 10.45% in normalized mean error and 19.22% in ARI at $K=16$. We found no absolute CUB number for MPAE on Lacuna. The older contrastive method of Unsupervised Part Discovery from Contrastive Reconstruction reports CUB NMI 46.0, and we include it as a second reference.

We rerun MPAE from the released recipe on our splits rather than copying numbers. Our method then gets exactly the same backbone, $K$, training images and total GPU-hours, with the self-training rounds counted against that budget. Beating it means a statistically reliable gain in NMI and ARI across three seeds on both datasets. It also means a large drop in our invalid-labeling rate, defined in the experiments.

A second baseline is one-to-one assignment with pairwise costs only. Each part is matched to at most one patch by Hungarian assignment with a null option, and the pairwise displacement costs are made submodular where possible so that the exact min-cut method of A Maximal Tractable Class of Soft Constraints applies. This is the strongest competitor that needs no width theory at all. It isolates whether three-way rules are needed.

A third baseline keeps our full three-way rule set but replaces exact inference with approximate inference: loopy max-product message passing, plus an off-the-shelf integer-programming solver given the same wall-clock limit. This isolates the value of exact, decomposition-based inference.

A fourth is a star-shaped model of the kind used in Neural Activation Constellations: Unsupervised Part Model Discovery with Convolutional Networks, where every part relates only to an object center, so the width is 1.

The key ablation sweeps the width budget $k \in \{1,2,3,\text{unbounded}\}$ while holding the rule-scoring procedure fixed. This shows whether accuracy saturates at small width and how inference time scales.

For annotation dependency, the ceiling reference is supervised SegFormer on PartImageNet at 65.27% mIoU (PartImageNet: A Large, High-Quality Dataset of Parts).

Why not just…?

Why not just use one-to-one optimal transport or Hungarian matching, which already forbids two parts landing on the same patch? This is the most serious threat, and we take it seriously. Uniqueness constraints fix duplicate assignments. They cannot fix swaps: a left wing labeled as right, or a head and tail exchanged under out-of-plane rotation. Fixing swaps needs an orientation rule over three parts, and binary costs cannot express that. A Maximal Tractable Class of Soft Constraints also shows that exact pairwise optimization stays tractable only within the submodular class. The pairwise-plus-assignment baseline settles the question directly. If it matches our method on NMI, ARI and swap rate, then three-way rules and everything downstream of them are unnecessary. We would report that result and drop the width machinery.

Why not keep the three-way rules but use loopy message passing or a generic integer-programming solver? With top-$m$ pruning at small $m$ and $K=16$, a generic solver may well solve each image exactly and quickly, so on CUB this alternative may tie. Our claim is narrower. As $K$ reaches 50 on PartImageNet and $m$ grows to keep recall under occlusion, unbudgeted rule sets become wide. Generic solvers then time out, and loopy inference returns inconsistent labels. The width budget instead gives a known polynomial bound. We will plot solve time and solution quality against $K$ and $m$ for all three. If the generic solver keeps pace at $K=50$, $m=64$, we will report that the value lies in the learned three-way rules, not the decomposition.

Why not restrict to a tree, as pictorial-structure and constellation models do? A width-1 model is the $k=1$ point of our sweep, so this question is answered by data rather than argument. The constellation model reached 81.01% classification accuracy on CUB-200-2011 (Neural Activation Constellations: Unsupervised Part Model Discovery with Convolutional Networks). But a tree over parts cannot encode the cyclic left/right/axis relations that articulated quadrupeds and bipeds in PartImageNet require. We expect the gap between $k=1$ and $k=2$ to be largest on those super-categories and small on rigid ones such as Bottle. If it is small everywhere, trees suffice.

Why not simply self-train MPAE longer on its own pseudo-labels? The self-training rounds may help by themselves, whatever the constraints contribute. A control runs identical rounds using MPAE's unconstrained labels as pseudo-labels, so any gain we attribute to the constraint network must exceed this.

Proposed Experiments

The first, cheapest experiment is descriptive and needs no training. On PartImageNet validation, we fit rule sets without a budget and report, per super-category, the exact hypertree width from the SAT solver alongside the LP-computed fractional width. The headline output is the width distribution per super-category and the fraction of held-out likelihood captured at $k=2$. If natural rule networks already sit at width 2 or below, the budget is nearly free. If they sit far above, the budget is doing real pruning, and the accuracy trade-off becomes the central result.

The main experiment trains on CUB-200-2011 ($K=16$) and PartImageNet ($K=50$, including the out-of-distribution split) and reports NMI and ARI against all baselines.

We add an invalid-labeling rate, computed with ground-truth part masks only at evaluation. It is the fraction of images where a discovered part's majority ground-truth label conflicts with its discovered identity in a left/right or front/back swap, or where two discovered parts map to the same ground-truth instance. We measure it on clean images and under synthetic occlusion at 25% and 50% of the object box, which tests the null-value mechanism.

The annotation-dependency experiment fine-tunes a SegFormer part segmenter on PartImageNet with 0%, 1%, 5% and 10% of part masks. The rest of the training signal comes either from our pseudo-labels or from MPAE pseudo-labels. We report mIoU relative to the fully supervised 65.27%. The decisive result is the mask fraction at which each pseudo-label source reaches 90% of the supervised mIoU.

As a downstream check, we feed constraint-refined parts into a part matcher in the style of Fine-grained Few-Shot Classification with Part Matching on Hotels-8k 1-shot. That paper reports a 13% improvement over prior methods, but we found no absolute Hotels-8k accuracy on Lacuna. So we rerun its released pipeline and compare our parts against its Grounded-SAM segments under identical matching code.

The decisive checks are threefold. First, the full method must beat the pairwise one-to-one baseline on swap rate under occlusion; otherwise three-way rules are not earning their cost. Second, at $K=50$ it must match or beat the generic-solver baseline in quality while staying within its time budget; otherwise the width budget is ornamental. Third, it must lower the mask fraction needed on PartImageNet relative to the MPAE self-training control; otherwise the annotation claim fails. We will report each outcome whichever way it falls.