Left–Right Part Swaps as an Expressivity Floor

Methods that discover object parts without labels, such as wings, eyes and legs, repeatedly make one embarrassing mistake: they give the left wing and the right wing the same label, or swap them between images. The papers that report this treat it as an unsolved nuisance. This note argues that it is not an optimization failure. It is a counting fact about what the part-labeling network can see. A labeler that decides each pixel's part from a bounded local window cannot tell "left wing" from "right wing" whenever both look the same inside that window. Which side is which depends on the whole bird's pose. No loss function can repair that without widening what the labeler sees.

The argument borrows a tool from logic. In descriptive complexity, the study of which logical languages can express which computations, the standard way to prove a model cannot compute something is to show two inputs it provably cannot tell apart. The resulting indistinguishability classes set a hard error floor for any model in that family. We transfer this tool from graphs to pixels. We measure the floor on real part-discovery networks, test whether it predicts their swap rates, and use it to choose the cheapest fix that actually removes swaps without any part annotation at training time.

Core Claim

Let $\phi_r(p)$ denote the representation a part-labeling head uses at pixel $p$, computed from a window of radius $r$. Group evaluation pixels that fall on a paired part (left or right eye, wing, leg) into classes $C$ of near-identical $\phi_r$. Let $w_C$ be the share of paired-part pixels in class $C$, and $q_C$ the fraction of those that are truly "left". Any labeler that is a function of $\phi_r$ alone then has a swap rate of at least

$$\text{floor}(r) = \sum_C w_C \,\min(q_C,\,1-q_C).$$

This is simply the Bayes error of predicting side from $\phi_r$. It is the pixel analogue of the argument that a message-passing network cannot separate nodes that color refinement leaves identical.

We make three claims. First, this floor, estimated from trained networks, predicts the observed left–right swap rates of existing unsupervised part methods. Second, the floor falls only when the labeler gets a reference to the object's global frame, meaning facing direction and visible side. Third, the prediction that separates this account from its rivals: symmetry-breaking by random features, which suffices for expressiveness in the graph setting, will not help here. Random features break ties inconsistently across images, while part discovery needs the same tie broken the same way on every bird.

Grounding in Prior Work

The problem itself comes from the vision literature. SCOPS discovers parts with concentration, equivariance and semantic-consistency losses on pretrained features. It reports that the model sometimes labels both wings of a bird with the same index. Unsupervised Part Segmentation Through Disentangling Appearance and Shape separates shape from appearance with a bottleneck and reports occasional left/right flips on near-symmetric objects. Both papers motivate this proposal. Neither explains why the flips happen or when they are unavoidable.

The method comes from logic. The Descriptive Complexity of Graph Neural Networks shows that bounded-depth message-passing networks are exactly as expressive as guarded first-order logic with counting. It also shows that random initialization together with a global readout lifts them to the circuit class $TC^0$. We reuse the indistinguishability style of argument. Unlike Grohe, we do not assume a given graph; the "neighborhood" is the receptive field over pixels. We also treat his random-feature result as a hypothesis to falsify in a setting that requires consistency across images.

The team-semantics literature, surveyed in Dagstuhl 24111 and Dagstuhl 19031, reasons about properties of sets of assignments rather than single ones. That fits here because "consistent side labeling" is a property of a batch of images, not of one image. We use it only as the evaluation vocabulary. Building a differentiable team-logic loss is exactly the unsolved quantifier problem flagged in Logic and Learning, and we deliberately avoid it.

The interdisciplinary-silo framing in the TAMC preface and in 19361 enters as a concrete deliverable. We will release a working diagnostic, taken from finite model theory, inside a standard vision pipeline, so that the transfer is more than a conceptual one. Part annotations, which the FGVC special section editorial calls unsustainable at scale, are used here only to score results.

Research Program

The work has three stages.

The first stage is a diagnostic. For a trained part network, we extract $\phi_r$ at several effective radii by probing the head's inputs at increasing layers and window crops. We cluster these features with a fixed quantization and estimate $\text{floor}(r)$ on held-out images, using the paired left/right part locations as ground truth. We report the floor with bootstrap intervals and check that it is insensitive to how many clusters the quantization uses.

The second stage is a controlled intervention. We add to a SCOPS-style labeler one of three inputs. The first is a global frame vector: a pooled whole-object descriptor, trained only through the existing self-supervised losses plus a flip-consistency term, in which a horizontally flipped image must receive labels permuted by a learned involution over part indices. The second is per-image random features, which match the capacity of the first option but give no shared frame. The third is a wider local receptive field with no global pooling. All three are trained with no part labels.

The third stage tests the theory. We ask whether the ranking of these variants by measured floor matches their ranking by swap rate, and whether the floor bounds swap rate from below in every variant.

Baselines

The naive reference point is SCOPS trained exactly as published, with its saliency input. It is the method whose authors first documented the swap problem. On unaligned CelebA it reports a 15.01% landmark error rate, according to SCOPS.

The strongest existing competitor is the squeeze-and-expand disentangling model of Liu et al.. It reports a CelebA landmark regression error of 15.39 with $K=4$ parts, without saliency maps. In its own evaluation it lists SCOPS at 21.76, so the two papers' protocols differ. We will re-run both under a single protocol rather than mixing reported figures. For left–right swap rate on CUB-200-2011 or CelebA, no reported result was found on Lacuna for any method, so we establish these numbers ourselves.

All variants share the same backbone, the same number of parts $K$, the same training images, and the same GPU-hour budget. Each gets the same hyperparameter search budget. Our variant counts as beating a baseline if it roughly halves the swap rate, falls within its measured floor, and does not increase landmark error beyond the confidence interval.

The ablation that isolates the key ingredient is the random-feature variant. It adds the same number of parameters and the same symmetry-breaking capacity as the global-frame variant, but no shared reference frame.

Why not just…?

Why not just add a flip-equivariance loss? This is the most serious threat. If flip consistency alone removes swaps, the theory adds little. Our account predicts that the loss only helps when the head can see enough to obey it: with a local head, the floor stays put regardless of the training signal. The experiment settles this directly by crossing loss (on/off) with head type (local, wide, global). If flip loss on a local head drives swaps below $\text{floor}(r)$, our claim is refuted.

Why not just use a GNN over discovered patches? Grohe's result is exactly what warns against this. A message-passing network over parts inherits color-refinement blindness to mirror-symmetric configurations unless it is given symmetry-breaking or a global readout, per Grohe. A GNN over patches is therefore one more instance of our "local" condition, and we include it as such.

Why not just add a sequence model or diversity loss over parts? The bi-directional LSTM in the complementary parts model and the orthogonal loss in Du et al. raise classification accuracy, to 90.3% and 89.1% on CUB respectively. Both, however, encourage parts to differ from each other. Neither establishes which side a part belongs to consistently across images. We will report swap rates for an orthogonal-loss variant to confirm that diversity does not buy side consistency.

Proposed Experiments

The data are CUB-200-2011 (Wah et al.), using its paired left/right part locations for evaluation only, and CelebA, using its eye and mouth-corner landmarks. The metrics are swap rate on paired parts, the SCOPS landmark-error protocol, and $\text{floor}(r)$.

There are three decisive checks. The first is a correlation test: across all trained variants and radii, the floor should predict swap rate with a rank correlation well above that of the plain receptive-field size. The second is a bound test: no variant should fall significantly below its own floor. The third is the random-feature test: random features should not reduce swaps compared with the unmodified network, while the global frame should.

If the global frame fails to lower both the floor and the swap rate, the thesis is wrong. In that case swaps come from optimization, and the loss-engineering alternatives deserve the credit.