Multi-label recognition means naming every object in an image. Systems that do it often fix their mistakes with a table of which objects tend to appear together. A detector unsure whether a blurry shape is a fork is helped by seeing a plate and a dining table. Current systems spread this information densely. Every label nudges every other label in proportion to how often they co-occur, typically through a graph convolutional network, a neural layer that averages each node's features with those of its graph neighbors. This dense spreading has a documented failure. Classes that both co-occur often and look alike, such as dining table, chair and sofa, blur into one another, and some of them get worse (GAR).
We propose a sparser rule taken from metric graph theory. First take the few labels the recognizer is most confident about. Then let co-occurrence evidence reach only the labels that lie on a shortest path between two of those confident labels in the co-occurrence graph. Graph theorists call this set of in-between vertices the geodetic closure of the anchors, and they have studied it extensively as the "geodetic set" problem. Our bet is that the objects in a real scene sit "between" its most salient objects in the co-occurrence graph. If so, the geodetic closure is a small, targeted region that should receive context. Everything outside it should get no contextual boost, which blocks hallucinated out-of-context labels and stops the mutual averaging that washes out look-alike classes.
Core Claim
Let the label co-occurrence graph $G$ have one vertex per class and an edge between classes $i$ and $j$ when their pointwise mutual information in the training set exceeds a threshold $\tau$. Pointwise mutual information measures how much more often two labels appear together than chance would predict. For a test image, let $A$ be the $m$ labels with the highest first-stage scores, with $m$ small (2 to 4). The geodetic closure is
$$I[A] = \{\, v \in V(G) : v \text{ lies on some shortest path in } G \text{ between } x, y \in A \,\}.$$
Our method, geodesic context refinement, lets contextual messages reach only labels in $I[A]$. Labels outside $I[A]$ keep their raw first-stage score.
The claim has two parts, and each can fail on its own. The first is empirical. On standard benchmarks, $I[A]$ built from ground-truth-confident anchors should contain most of an image's true labels while being much smaller than the union of the anchors' one-hop neighborhoods. The second is methodological. Restricting refinement to $I[A]$ should match or beat dense co-occurrence refinement in mean average precision, and it should specifically recover the classes that dense refinement hurts. If only the first part holds, we still have a new descriptive fact about how scene labels are arranged in co-occurrence space. If the first part fails, the method has no reason to work, and we will report that.
Relation to Prior Work
The co-occurrence line supplies both our starting point and our target failure. GAR builds a graph of region proposals and scene nodes with co-occurrence edges and refines detection scores with a two-layer graph convolutional network. It reports the over-smoothing on visually similar, highly co-occurring classes that motivates us. Rawlekar et al. refine frozen CLIP logits with a graph convolutional network whose edges are empirical conditional probabilities $P(\text{class}_j \mid \text{class}_i)$. CLIP is a vision-language model that scores image regions against text prompts, and this paper's pipeline is the strongest direct competitor and the pipeline we modify. CooK (Kim et al.) injects conditional co-occurrence into one-hop message passing for scene graphs, and GRAN (Nie et al.) reasons jointly over visual and Wikipedia-derived semantic graphs for zero-shot detection. All four propagate over the full neighborhood structure. None asks which subset of the label graph should receive evidence given what the image has already confidently shown, and that selection is the whole of our change.
Barnea and Ben-Shahar constrain the design. They show that context separates correct classes from wrong classes or background at 70–80% accuracy but separates correct from slightly shifted boxes at only about 55%. Context therefore cannot fix localization. For that reason we evaluate mainly on multi-label recognition, where localization plays no role, and treat detection as secondary.
The geodetic line supplies definitions and a complexity lens, not a recognition method. Kellerhals et al. show that finding a minimum geodetic set is W[1]-hard even when feedback vertex number, pathwidth and solution size are all bounded. W[1]-hard means it is unlikely to become tractable just because those parameters are small. The same paper shows the problem is fixed-parameter tractable in feedback edge number, the number of edges that must be deleted to leave a forest. Chakraborty et al. give NP-hardness on interval graphs and partial grids, and a $2^{O(w)}n^{O(1)}$ algorithm on chordal graphs, where $w$ is the clique number. Dumas et al. show that graphs coverable by $k$ shortest paths have pathwidth bounded by a function of $k$.
Our per-image operation only computes the closure of a given small $A$. That needs one breadth-first search from each anchor and runs in polynomial time, so the hardness results do not block us. They do matter for our secondary question: the smallest set of anchor classes whose closure covers the whole label graph, a "monitoring vocabulary." For that question we measure the structural parameters of real co-occurrence graphs to see which of the known tractable regimes they fall into. No paper in the literature we found computes geodetic quantities on data-derived graphs. The theory papers explicitly leave empirical, noisy graphs aside.
Research Program
The first stage is diagnostic and needs no training. For each benchmark we build $G$ at several thresholds $\tau$, plus a weighted variant with edge length $-\log P(j \mid i)$. For every test image we take the anchors $A$, first as the $m$ ground-truth labels with the largest object area and then as the top-$m$ CLIP scores. We then measure two quantities. Closure recall is the fraction of true labels inside $I[A]$. Closure size is $|I[A]|$ divided by the size of the one-hop neighborhood union of $A$. The geodesic hypothesis predicts high recall at a closure size well below one. We also record where recall fails, for instance labels that co-occur with nothing in particular.
The second stage is the refinement model. We keep the Rawlekar et al. pipeline intact: frozen CLIP logits, a conditional-probability graph convolutional network, and their reweighted asymmetric loss. Before each propagation step we mask the adjacency matrix so that messages flow only into vertices of $I[A]$, and only along edges that lie on shortest paths between anchors. Because $I[A]$ depends on the first-stage scores, we compute it on the fly and add a soft version for robustness. In the soft version, anchor sets are sampled in proportion to confidence and the resulting masks are averaged.
The third stage is structural. On the empirical graphs we compute treewidth, feedback edge number and chordality, the geodetic number, and the minimum number of shortest paths needed to cover all vertices. The label graphs have only tens to about a hundred vertices, so we get exact answers through integer programming. We test whether a small monitoring vocabulary exists, and whether prompting only those classes and inferring the rest through closures loses much accuracy. This secondary result stands on its own as the first empirical look at geodetic structure in semantic graphs.
Baselines
The naive reference point is the frozen CLIP first stage with no context refinement, scored per class independently. Any context method must beat it, and the gap tells us how much context is worth on each dataset at all.
The strongest existing method is the conditional-probability graph refinement of Rawlekar et al.. It is the most direct competitor because it uses the same frozen backbone, the same co-occurrence statistic and the same datasets, differing from ours only in propagating densely. The file reports its advantage only in relative terms. It beats DualCoOp by 2.4 mAP on MS-COCO 2014-small, 0.4 on PASCAL VOC 2007, 3.9 on FoodSeg103 and 14.1 on UNIMIB 2016. We found no reported absolute mAP on Lacuna for this method, so we will re-run it from its described configuration and report our reproduced numbers next to those relative gaps as a sanity check. We use the same splits, the same backbone, an identical hyperparameter search budget for both models, and three seeds.
DualCoOp is a prompt-learning baseline without an explicit graph. It learns positive and negative CLIP prompts per class, and we include it to separate the value of any co-occurrence graph from the value of prompt tuning.
The key ablation replaces $I[A]$ with a mask of the same size drawn from the one-hop neighborhood union of the anchors, ranked by co-occurrence strength. It isolates whether "lying between anchors" matters beyond "being near an anchor." A second ablation uses random anchors to check that the anchors' confidence carries the signal.
Beating the strongest baseline means a mean mAP gain over three seeds that exceeds the seed spread on at least three of the four datasets, with no loss on the others. It also requires a per-class gain on the classes where dense refinement falls below the naive reference, which we identify in advance from the reproduced baseline.
Why not just…?
Why not just sparsify the graph by keeping each class's top-$k$ co-occurring neighbors? This also fights over-smoothing, but it is fixed per class and ignores the image. Dining table would still send messages to chair and sofa in every image. Our mask changes with which anchors each image shows. The size-matched ablation, run with top-$k$ sparsification added as a further baseline, tells us whether the image-conditioned selection matters.
Why not just re-score each label by its pointwise mutual information with the confident labels? This one-hop re-ranking is the most serious threat. It is simple, it is also anchor-conditioned, and it may capture most of the benefit. The difference is that geodetic closure also admits labels that are not adjacent to any single anchor but sit on paths between two of them. It also excludes labels adjacent to only one anchor in a direction away from the others. Stage one directly measures whether closures are smaller than one-hop unions at equal recall. If they are not, or if one-hop re-scoring matches our model in mAP, we will conclude that the geodetic ingredient is unnecessary and say so.
Why not just learn which edges to use with graph attention? Learned attention can in principle discover image-dependent masks. In the low-label settings these benchmarks target, however, such as the 5% COCO subset, it has little data to learn them from. We will include a graph-attention variant of the same refinement network. If it matches geodesic masking at full data but falls behind at small data, that locates the value of our rule as a prior. If it matches everywhere, the prior buys nothing.
Proposed Experiments
The multi-label experiments use MS-COCO 2014-small (4,014 training images, 80 classes), PASCAL VOC 2007, FoodSeg103 and UNIMIB 2016, following the protocol of Rawlekar et al.. We report mAP and per-class average precision, with emphasis on the pre-registered over-smoothed classes. As a secondary check we plug the geodesic mask into a GAR-style detection refinement on PASCAL VOC 2007 and MS COCO. The anchor points there are GAR's reported 76.1% mAP on VOC 2007 and 23.1% AP on COCO 2014 (GAR). Following Barnea and Ben-Shahar, we expect any detection gain to shrink as the overlap threshold for counting a detection correct tightens from 0.5 to 0.75, and we report both thresholds.
Three checks decide the proposal. The first is whether ground-truth-anchored closures reach high label recall at a closure size well below the one-hop union. Without this, the method has no basis. The second is whether geodesic refinement beats the size-matched one-hop mask and one-hop pointwise mutual information re-scoring, not just the naive reference. The third is whether it repairs the classes that dense refinement damages. For the structural study, success means reporting exact geodetic numbers and structural parameters for these graphs, and learning whether a monitoring vocabulary much smaller than the full label set keeps recognition within one mAP point of full prompting.
References
- GAR: Graph Assisted Reasoning for Object Detection
- Improving Multi-label Recognition using Class Co-Occurrence Probabilities
- Scene Graph Generation Strategy with Co-occurrence Knowledge and Learnable Term Frequency
- From Node to Graph: Joint Reasoning on Visual-Semantic Relational Graph for Zero-Shot Detection
- Exploring the Bounds of the Utility of Context for Object Detection
- Parameterized Complexity of Geodetic Set
- Algorithms and complexity for geodetic sets on planar and chordal graphs
- On Graphs Coverable byShortest Paths
- DualCoOp: Fast Adaptation to Multi-Label Recognition with Limited Annotations