Bipartite Graph Network with Adaptive Message Passing for Unbiased Scene Graph Generation

In plain words

A scene graph describes a photo as a set of objects and the relations between pairs of them: subject, relation, object. Building one is hard because the relations are very unevenly spread. A few common relations appear constantly, and many rarer ones appear only a handful of times. A model trained on the raw data learns the common ones well and mostly guesses the common ones for everything else.

The paper's approach has two parts. The first treats objects and relations as two kinds of nodes in a graph and lets them exchange information back and forth. Each relation candidate also gets a confidence score, and that score decides how much its message counts, so guesses that look like noise pass little information. The second part changes how training data is drawn: rarer relations are shown more often, and the most common ones are thinned out inside each image so the balance shifts. Together these aim to improve the rare relations without giving up too much on the common ones.

TL;DR

• Scene graph generation is trained on a long-tailed set of relation labels, so rare relations are weak.
• BGNN runs gated message passing between entity and relation proposals on a bipartite graph, with the gate set by a learned relation confidence.
• Training adds bi-level resampling: image-level repeat sampling plus instance-level drop-out.
• Author-reported gains on Visual Genome and Open Images. The gains are largest on mean recall (balanced over predicates), and the paper does not claim a win on plain recall.
• Code for the authors' method is in the PySGG framework, and its BGNN settings differ from the paper in several places (see Paper vs code).

Problem

Scene graph generation (SGG) needs a model to find objects and then classify the relation between each ordered pair. The authors name two causes of biased prediction. The first is the intrinsic long-tail of relation labels: head classes dominate and tail classes get few examples §1. The second is large intra-class variation for non-head predicates, which the authors describe as verbs such as "play" or "look" that take many visual forms §1. Prior context models often connect all pairs of entities, so most links carry noise §1. An empirical study in the paper removes the negative predicate-to-entity links in a baseline (MSDN) during message passing, and the gain in tail classes suggests that noise in context modelling is a bottleneck §1 fig. 1. The paper's supplement reports that this removal gives the baseline a large gain, especially on tail categories app. C.

Standard re-balancing (image-level repeat factor sampling, LVIS-style) does not fit SGG well, because a single image carries many relation instances with different frequencies. The authors combine image-level over-sampling with instance-level under-sampling §3.3 fig. 4.

Method

Overview. The model is hypothesize-and-classify. A detector proposes entities. Every ordered pair of entities becomes a relation proposal §3.2.1. A bipartite graph neural network (BGNN) refines entity and predicate features by message passing. Two linear classifiers then label each entity and each predicate §3.2. fig. 2 shows the pipeline.

Proposal features §3.2.1. Entity features combine visual, geometric and word-embedding features eq. 1. A relation feature combines a union-box feature with the two entity features eq. 2. The code builds its initial features differently, see Paper vs code.

\mathbf{e}_i = f_e(\mathbf{v}_i \oplus \mathbf{g}_i \oplus \mathbf{w}_i) eq. 1

\mathbf{r}_{i\to j} = f_u(\mathbf{u}^p_{i,j}) + f_p(\mathbf{e}_i \oplus \mathbf{e}_j) eq. 2

Bipartite graph §3.2.2. Entity nodes and predicate nodes are connected by two sets of directed edges, one from entities to predicates and one back §3.2.2. The network runs several stages. Each stage has a relation confidence estimation (RCE) module and a confidence-aware message propagation step §3.2.2.

RCE §3.2.2. For each predicate proposal, the RCE module predicts one score per predicate class from the predicate feature and the detector's class probabilities for its two entities eq. 3. A sigmoid over a weighted sum of those scores gives one confidence per proposal eq. 4.

\mathbf{s}^m_{i\to j} = g_x(\mathbf{r}_{i\to j} \oplus \mathbf{p}_i \oplus \mathbf{p}_j) \in \mathbb{R}^{|\mathcal{C}_p|} eq. 3

s^b_{i\to j} = \sigma(\mathbf{w}_b^\top \mathbf{s}^m_{i\to j}) eq. 4

Confidence gate §3.2.2. The confidence passes through a clamped linear gate with two learnable thresholds, alpha and beta. Low confidence gives zero, high confidence gives one, and values in between scale linearly eq. 7. The paper describes this as hard control at the extremes and soft control in between.

\gamma_{i\to j} = \mathcal{T}(s^b_{i\to j}), \quad \mathcal{T}(x) = \begin{cases} 0 & x \le \beta \\ \alpha x - \alpha\beta & \beta < x < 1/\alpha + \beta \\ 1 & x \ge 1/\alpha + \beta \end{cases} eq. 7

Message propagation §3.2.2. Each predicate reads its two entities through learned affinity terms, and its state is updated with a residual step eq. 5 eq. 6. Each entity then reads its neighbouring predicates. A neighbour's message is scaled by its gate. Messages from predicates where the entity is the subject are averaged separately from messages where it is the object, and the two averages are added eq. 8 eq. 9. The paper writes both updates with a generic activation phi.

\mathbf{r}^{(l+1)}_{i\to j} = \mathbf{r}^{(l)}_{i\to j} + \phi\big(d_s \mathbf{W}_r^\top \mathbf{e}^{(l)}_i + d_o \mathbf{W}_r^\top \mathbf{e}^{(l)}_j\big) eq. 5

d_s = \sigma(\mathbf{w}_s^\top[\mathbf{r}^{(l)}_{i\to j} \oplus \mathbf{e}^{(l)}_i]), \quad d_o = \sigma(\mathbf{w}_o^\top[\mathbf{r}^{(l)}_{i\to j} \oplus \mathbf{e}^{(l)}_j]) eq. 6

\mathbf{e}^{(l+1)}_i = \mathbf{e}^{(l)}_i + \phi\Big( \frac{1}{|\mathcal{B}_s(i)|}\sum_{k\in\mathcal{B}_s(i)} \gamma_k d_s \mathbf{W}_e^\top \mathbf{r}^{(l)}_k + \frac{1}{|\mathcal{B}_o(i)|}\sum_{k\in\mathcal{B}_o(i)} \gamma_k d_o \mathbf{W}_e^\top \mathbf{r}^{(l)}_k \Big) eq. 8 eq. 9

The paper runs N_i propagation steps per stage §3.2.2. The ablation found N_i = 3 best for a single stage, and N_t = 3 stages best overall tab. 4.

Scene graph prediction §3.2.3. Each predicate's final logit is a linear map of its refined feature plus a log frequency prior of its (subject, object) pair eq. 10. Each entity is classified from a fusion of its refined feature and its initial visual feature, with a weight rho eq. 11. The paper gives rho = -5 in the implementation details and also says it lies in [0, 1] §4.1 §3.2.3.

\mathbf{p}_{\mathbf{r}_{i\to j}} = \mathrm{softmax}\big(\mathbf{W}_{rel}^\top \hat{\mathbf{r}}_{i\to j} + \log \hat{\mathbf{p}}_{\mathbf{r}_{i\to j}}\big) \in \mathbb{R}^{|\mathcal{C}_p|} eq. 10

\mathbf{p}_{\mathbf{e}_i} = \mathrm{softmax}\big(\mathbf{W}_{ent}^\top(\rho\,\hat{\mathbf{e}}_i + (1-\rho)\,\mathbf{v}_i)\big) \in \mathbb{R}^{|\mathcal{C}_e|} eq. 11

The forward pass for one refinement stage is sketched below. The paper gives the steps, and the code confirms the stage structure. Items marked code-only come from the code and are not in the paper's text.

# BGNN: N_t stages, each with N_i message-passing steps  [§3.2.2] [tab. 4]
# Input:  entities (N, d), predicates (M, d), pairs (M, 2) = (subj, obj)
# Output: refined entities (N, d), refined predicates (M, d)

def bgnn(entities, predicates, pairs):
    for stage in range(N_t):  # N_t = 3  [tab. 4]
        # 1. Confidence of each predicate proposal  [§3.2.2] [eq. 3-4]
        conf_logits, conf = rce[stage](predicates, entities, pairs)
        # 2. Keep the most confident pairs as senders  (code-only: 128)
        senders = top_k(conf, k=128)
        # 3. Recalibrate confidence with the gate  [§3.2.2] [eq. 7]
        gate = clamp(alpha * conf - alpha * beta, 0.0, 1.0)
        senders = senders[gate[senders] > 1e-4]  # (code-only)
        for step in range(N_i):  # N_i = 3  [tab. 4]
            old_entities = entities
            # 4. Predicates -> entities: gated messages, averaged per
            #    role (subject, object), added  [§3.2.2] [eq. 8-9]
            to_subj = gated_mean(gate, predicates, "subject")
            to_obj = gated_mean(gate, predicates, "object")
            entities = entities + fuse(to_subj + to_obj, entities)
            # 5. Entities -> predicates, read from the pre-update
            #    entities  [§3.2.2] [eq. 5-6]  (code-only ordering)
            from_subj = learned_mean(predicates, old_entities, pairs, 0)
            from_obj = learned_mean(predicates, old_entities, pairs, 1)
            predicates = predicates + fuse(from_subj + from_obj, predicates)
    return entities, predicates

Bi-level resampling §3.3. Images are repeated by a class-based factor. Each predicate class c gets r^c = max(1, sqrt(t / f^c)), where f^c is its frequency over the training set and t is a threshold §3.3. An image takes the largest r^c over its labelled classes §3.3. Then, inside each image, an instance of class c is dropped from the loss with probability (r_i - r^c) / r_i * gamma_d, where gamma_d is a hyper-parameter §3.3. A dropped instance keeps its place but is ignored in the loss §3.3 fig. 4.

# Bi-level resampling of images and instances  [§3.3] [fig. 4]
# Input: class frequencies f[c], threshold t, drop factor gamma_d

def image_repeat(image_classes, f, t):
    # Class repeat factor r^c = max(1, sqrt(t / f^c))  [§3.3]
    r_c = [max(1.0, sqrt(t / f[c])) for c in image_classes]
    # Image repeat factor: the largest over its labelled classes  [§3.3]
    return max(r_c)


def drop_instances(relations, r_image, r_class, gamma_d):
    # Drop probability (r_i - r^c) / r_i * gamma_d  [§3.3]
    # The paper prints max(..., 1.0); the code clips to [0, 1]  (code-only)
    for rel in relations:
        p_drop = clip((r_image - r_class[rel.c]) / r_image * gamma_d, 0, 1)
        if random() < p_drop:
            rel.label = IGNORE  # no loss on this instance  [§3.3]
    return relations

Losses §3.3 app. A. The total loss is the predicate classification loss, plus a weighted RCE loss, plus an entity classification loss eq. 12. The paper gives no values for the weights. The RCE loss combines a class-specific term and a binary term, each a focal loss app. A. The paper gives the focal form and the normalisation over the M proposals, but not the values of its alpha and gamma.

\mathcal{L}_{total} = \mathcal{L}_{p} + \lambda_{rce}\mathcal{L}_{rce} + \lambda_{e}\mathcal{L}_{e} eq. 12

Here L_rce = L_m + lambda * L_b, with lambda not stated §3.3. Each term is the focal loss of its prediction, averaged over the M proposals app. A.

Hyperparameters

Values are from the paper's text unless the Where column names code. Code values are from the PySGG config used by the authors' VG run.

Results

Author-reported throughout. Setup: Visual Genome split with 150 objects and 50 predicates, ResNeXt-101-FPN backbone, frozen Faster R-CNN detector. The baselines are the paper's reproductions, marked with a dagger, and the published numbers of other papers §4.1 tab. 1.

Visual Genome, headline comparison (mean recall mR@50 / mR@100, recall R@50 / R@100) tab. 1:

The paper says BGNN beats Unbiased on PredCls mR by 5.0 and 4.2 points §4.1. On the VGG16 backbone the text claims comparable PredCls and SGCls results with PCPL and a large gain on SGGen §4.1, but the VGG16 block of tab. 1 has no BGNN row (see Pitfalls).

Ablation of the model structure on SGGen tab. 2. B is plain bipartite message passing, C the confidence-aware propagation, M the multi-stage refinement:

Resampling on SGGen tab. 3. RFS is the LVIS-style repeat-factor sampling, BLS is the bi-level method:

Stages and iterations on SGGen tab. 4:

In the appendix, the BLS sampler added to other models gives: GPS-Net with BLS 11.4 / 34.3 mR@100 / R@100, MSDN with BLS 11.8 / 34.4, and BGNN with BLS 12.6 / 35.8 app. B. The RCE module's AUC on VG validation is 0.839, against 0.629 for the detector's entity score and 0.671 for a Graph-RCNN-style relation proposal network app. A.

Open Images, mR@50, R@50, weighted mAP for relations and phrases, and the weighted score (score = 0.2 R@50 + 0.4 wmAP_rel + 0.4 wmAP_phr §4.2) tab. 5:

On OI V4 the paper's score is below the cited GPS-Net score, so the claim there is "competitive" §4.2. On OI V6 the mean recall is the highest among the compared methods §4.2. In tab. 5, * marks resampling and † a reproduction with the authors' code.

Paper vs code

The code is in the PySGG framework at github.com/SHTUPLUS/PySGG, commit a63942a076932b3756a477cf8919c3b74cd36207. Paths below are relative to that repository. The title page links a different repository, github.com/Scarecrow0/BGNN-SGG p. 1. That repository holds only a README, and the README says the code is released in PySGG [README of BGNN-SGG]. I did not check the SHTUPLUS organisation's ties to the authors beyond that README. Its LICENSE file says MIT, but adds an author note that they do not know which licence should apply. Only path and line citations are used here, with no verbatim code.

Several discrepancies between paper and code were found. The paper's values are listed first, then the code's:

• Gate thresholds. The paper gives alpha and beta initial values 2.2 and 0.025, and says both are learnable §4.1 §3.2.2. The VG config sets (3.12, 0.06) and freezes beta e2e_relBGNN_vg.yaml model_bgnn.py.
• rho and the entity fusion. The paper's entity classifier fuses the refined entity feature with the initial visual feature using rho = -5 §4.1 eq. 11. The code feeds the refined entity feature straight to the classifier, and the skip-connection flag is set but never read [code: pysgg/modeling/roi_heads/relation_head/model_bgnn.py#L450-L452] roi_relation_predictors.py.
• Repeat factor. The paper uses t = 0.07 §4.1. The code uses REPEAT_FACTOR = 0.1 in the repeat-factor computation [code: pysgg/data/datasets/bi_lvl_rsmp.py#L32] e2e_relBGNN_vg.yaml. The 0.07 value sits in TAIL_REPEAT_FACTOR, which no code reads [code: configs/e2e_relBGNN_vg.yaml#L301] defaults.py. The code also rounds each class factor to an integer at random [code: pysgg/data/datasets/bi_lvl_rsmp.py#L68-L72]. The paper does not say how this rounding works.
• Drop factor. The paper uses gamma_d = 0.7 §4.1. The VG config uses 0.9 and the OI configs 0.85 e2e_relBGNN_vg.yaml e2e_relBGNN_oiv6.yaml. The paper prints the drop formula with max(..., 1.0), which would always give 1; the code clips the probability to [0, 1] bi_lvl_rsmp.py.
• Propagation order. The paper lists entity-to-predicate messages first §3.2.2. The code updates entities from predicates first, then updates predicates from the pre-update entities [code: pysgg/modeling/roi_heads/relation_head/model_bgnn.py#L901-L991].
• Message fusion. The paper applies one activation phi to the summed messages eq. 5 eq. 8 eq. 9. The code averages the subject and object messages, then adds a residual with two linear maps, each applied after a ReLU model_bgnn.py model_bgnn.py.
• Gate function. The paper's affinity d is one linear layer with a sigmoid eq. 6. The code's gate is a LayerNorm, ReLU and linear map to 128 units, each with a sigmoid, averaged over the units [code: pysgg/modeling/roi_heads/relation_head/model_bgnn.py#L49-L108]. The code then multiplies the message by the recalibrated confidence [code: pysgg/modeling/roi_heads/relation_head/model_bgnn.py#L104].
• Senders and filtering. The paper gives no cap on messaging pairs. The code keeps the top 128 pairs model_bgnn.py and drops pairs gated to zero model_bgnn.py. It also excludes entities with detection score at or below 0.03 from messaging model_bgnn.py. The paper's commented-out text mentions 3,000 relation proposals, which is not in the active text.
• RCE inputs. The paper's RCE uses the predicate feature and the detector's class probability vectors eq. 3. The code uses a detached visual feature, box encodings and GloVe embeddings weighted by the softmax of the predicted class logits models.py. The visual feature is detached, so the RCE loss does not reach the feature extractor models.py. In the hybrid head, the binary confidence is a linear layer with a bias on the class logits, then a sigmoid models.py models.py. The paper's eq. 4 has no bias.
• RCE loss. The paper normalises the focal loss over M proposals app. A. The code divides by the number of positive labels plus one [code: pysgg/modeling/roi_heads/relation_head/rel_proposal_network/loss.py#L63-L69]. The code combines the binary and class terms as 0.8 and 0.2 [code: pysgg/modeling/roi_heads/relation_head/rel_proposal_network/loss.py#L133]. One RCE loss is added per refinement stage, without a weight [code: pysgg/modeling/roi_heads/relation_head/roi_relation_predictors.py#L668-L676].
• Frequency bias. The paper's logit adds log p̂ eq. 10. The code adds a frequency term scaled by freq_lambda = 1, indexed by predicted object labels in sgcls and sgdet modes, and by ground-truth labels in predcls [code: pysgg/modeling/roi_heads/relation_head/roi_relation_predictors.py#L650-L661].
• Initial features. The paper's entity feature includes a geometric term g_i eq. 1. The code's initial feature extractor is documented as following the Motifs pipeline, with GloVe embeddings of the predicted labels [code: pysgg/modeling/roi_heads/relation_head/model_msg_passing.py#L110-L170]. I did not trace its geometry features.
• Backbone. The paper uses ResNeXt-101-FPN §4.1. The VG config names R-101-FPN as the conv body, with ImageNet weights for X-101-32x8d [code: configs/e2e_relBGNN_vg.yaml#L41] e2e_relBGNN_vg.yaml. The released detector checkpoint is not in the repository, so the backbone actually used cannot be confirmed.
• Pre-training and freezing. The paper does not state a schedule. The VG config pre-trains the RCE for 2,000 iterations with message passing off [code: configs/e2e_relBGNN_vg.yaml#L237] relation_train_net.py. Then it sets the graph on relation_train_net.py. The freeze at iteration 3,000 targets the module list for "rel_pn" or "pre_clser" methods only [code: tools/relation_train_net.py#L212-L218] relation_train_net.py. The VG config uses RelAwareRelFeature, so the freeze is a no-op.
• Optimizer and schedule. The paper states none of these. The code uses SGD build.py with the values in Hyperparameters.
• Numbers in the authors' README. The BGNN-SGG README reports VG SGGen mR@100 13.55 and OI V6 score 42.47, against 12.6 and 42.06 in the paper. I did not reproduce either number.

Pitfalls

• Gate saturation and gradients. With the code's values, the gate reaches one for confidence at or above 1/alpha + beta, about 0.38. With the paper's 2.2 and 0.025 it is about 0.48 eq. 7. The clamp passes no gradient outside [0, 1], so gated-off pairs give no gradient to alpha or to the RCE model_bgnn.py.
• Hidden selection. The top-128 cap, the 1e-4 gate cut and the 0.03 detection cut decide which proposals send messages. None is in the paper's text, so a reimplementation that follows the paper will pass a different set.
• Random drops. Drops and repeat rounding are redrawn with numpy on each access, so runs without a fixed seed differ [code: pysgg/data/datasets/bi_lvl_rsmp.py#L146].
• Ignored instances. A dropped instance is labelled -1, so the loss skips it bi_lvl_rsmp.py. The paper says the same §3.3.
• VGG16 claims. The text makes claims for a VGG16 BGNN §4.1, but the VGG16 block of tab. 1 has no BGNN row, so those claims cannot be checked against a number.
• Inconsistent baseline. The same baseline has R@100 34.1 in tab. 2 and 36.1 in tab. 3, with mR@100 9.7 in both.
• Dependencies. Both model_bgnn.py and loss.py import ipdb at the top model_bgnn.py loss.py. Install it or remove the import before running.
• Cost. Each stage runs N_i message passes over up to 128 senders, with 512-dimensional features e2e_relBGNN_vg.yaml. The paper gives no timing, memory or parameter counts.
• Comparisons. All numbers are author-reported. Some baselines are the authors' reproductions, and some are the numbers from the original papers. Compare within one table only.

Lineage

• Builds on: the message-passing context models for scene graphs that connect entities and predicates, such as MSDN and Graph-RCNN §2, and the LVIS-style repeat-factor sampling §3.3. The instance-level replay of Hu et al. (2020) gives the under-sampling idea §3.3.
• Uses the backbone and the frozen detector of Tang et al. (2020) §4.1.
• Compared against: GPS-Net (Lin et al., 2020), Unbiased (Tang et al., 2020), PCPL (Yan et al., 2020), RelDN (Zhang et al., 2019), MSDN (Li et al., 2017), G-RCNN, VCTree, Motifs tab. 1 tab. 5.
• Superseded by: not known from the content of this wiki.