Graph Density-Aware Losses for Novel Compositions in Scene Graph Generation

Introduction

In recent years, there has been growing interest to connect successes in visual perception with language and reasoning . This requires us to design systems that can not only recognize objects, but understand and reason about the relationships between them. This is essential for such tasks as visual question answering (VQA) or caption generation . However, predicting a high-level semantic output (e.g. answer) from a low-level visual signal (e.g. image) is challenging due to a vast gap between the modalities. To bridge this gap, it would be useful to have some intermediate representation that can be relatively easily generated by the low-level module and, at the same time, can be effectively used by the high-level reasoning module. We want this representation to semantically describe the visual scene in terms of objects and relationships between them, which leads us to a structured image representation, the scene graph (SG) . A scene graph is a collection of visual relationship triplets: (e.g. ). Each node in the graph corresponds to a subject or object (with a specific image location) and edges to predicates (Figure 1). Besides bridging the gap, SGs can be used to verify how well the model has understood the visual world, as opposed to just exploiting one of the biases in a dataset . Alternative directions to SGs include, for example, attention and neural-symbolic models .

Scene graph generation (SGG) is the task of predicting a SG given an input image. The inferred SG can be used directly for downstream tasks such as VQA , image captioning or retrieval . A model which performs well on SGG should demonstrate the ability to ground visual concepts to images and generalize to compositions of objects and predicates in new contexts. In real world images, some compositions (e.g. ) appear more frequently than others (e.g. or ), which creates a strong frequency bias. This makes it particularly challenging for models to generalize to novel (zero-shot) and rare (few-shot) compositions, even though each of the subjects, objects and predicates have been observed at training time. The problem is exacerbated by the test set and evaluation metrics, which do not penalize models that blindly rely on such bias. Indeed, Zellers et al. has pointed out that SGG models largely exploit simple co-occurrence information. In fact, the performance of models predicting solely based on frequency (i.e. a cup is most likely to be on a table) is not far from the state-of-the-art using common metrics (see Freq in Table 1).

In this work, we reveal that (a) the frequency bias exploited by certain models leads to poor generalization on few-shot and zero-shot compositions; (b) existing models disproportionately penalize large graphs, even if these often contain many of the infrequent visual relationships, which leads to performance degradation on few and zero-shot cases (Figure 2). We address these challenges and show that our suggested improvements can provide benefits for two strong baseline models . Overall, we make the following four contributions:

Improved loss: we introduce a density-normalized edge loss, which improves results on all metrics, especially for few and zero-shots (Section 3.2);

Novel weighted metric: we illustrate several issues in the evaluation of few and zero-shots, proposing a novel weighted metric which can better track the performance of this critical desiderata (Section 3.3);

Frequency bias: we demonstrate a negative effect of the frequency bias, proposed in Neural Motifs , on few and zero-shot performance (Section 4);

Scaling to GQA: in addition to evaluating on Visual Genome (VG) , we confirm the usefulness of our loss and metrics on GQA – an improved version of VG. GQA has not been used to evaluate SGG models before and is interesting to study, because compared to VG its scene graphs are cleaner, larger, more dense and contain a larger variety of objects and predicates (Section 4).

Related Work

Zero-shot learning. In vision tasks, such as image classification, zero-shot learning has been extensively studied, and the main approaches are based on attributes and semantic embeddings . The first approach is related to the zero-shot problem we address in this work: it assumes that all individual attributes of objects (color, shape, etc.) are observed during training, such that novel classes can be detected at test time based on compositions of their attributes. Zero-shot learning in scene graphs is similar: all individual subjects, objects and predicates are observed during training, but most of their compositions are not. This task was first evaluated in on the VRD dataset using a joint vision-language model. Several follow-up works attempted to improve upon it: by learning a translation operator in the embedding space , clustering in a weakly-supervised fashion , using conditional random fields or optimizing a cycle-consistency loss to learn object-agnostic features . Augmentation using generative networks to generate more examples of rare cases is another promising approach ; but, it was only evaluated in the predicate classification task. In our work, we also consider subject/object classification to enable the classification of the whole triplets, making the “image to scene graph” pipeline complete. Most recently, Tang et al. proposed learning causal graphs and showed strong performance in zero-shot cases.

While these works improve generalization, none of them has identified the challenges and importance of learning from large graphs for generalization. By concentrating the model’s capacity on smaller graphs and neglecting larger graphs, baseline models limit the variability of training data, useful for stronger generalization . Our loss enables this learning, increasing the effective data variability. Moreover, previous gains typically incur a large computational cost, while our loss has negligible cost and can be easily added to other models.

Few-shot predicates. Several recent works have addressed the problem of imbalanced and few-shot predicate classes . However, compared to our work, these works have not considered the imbalance between foreground and background edges, which is more severe than other predicate classes (Figure 3) and is important to be fixed as we show in this work. Moreover, we argue that the compositional generalization, not addressed in those works, can be more difficult than generalization to rare predicates. For example, the triplet is challenging to be predicted correctly as a whole; even though ‘on’ can be the most frequent predicate, it has never been observed together with ‘cup’ and ‘surfboard’. Experimental results in previous work highlight this difficulty. Throughout this work, by “few-shot” we assume triplets, not predicates.

“Unbiasing” methods. Our idea is similar to the Focal loss , which addresses the imbalance between foreground and background objects in the object detection task. However, directly applying the focal loss to Visual Genome is challenging, due to the large amount of missing and mislabeled examples in the dataset. In this case, concentrating the model’s capacity on “hard” examples can be equivalent to putting more weight on noise, which can hurt performance. Tang et al. compared the focal loss and other unbiasing methods, such as upsampling and upweighting, and did not report significantly better results.

Methods

In this section, we will review a standard loss used to train scene graph generation models (Section 3.1) and describe our improved loss (Section 3.2). We will then discuss issues with evaluating rarer combinations and propose a new weighted metric (Section 3.3).

In scene graph generation, given an image $I$, we aim to output a scene graph ${\cal G}=(O,R)$ consisting of a set of subjects and objects ($O$) as nodes and a set of relationships or predicates ($R$) between them as edges (Figure 1). So the task is to maximize the probability $P({\cal G}|I)$, which can be expressed as $P(O,R|I)=P(O|I)\ P(R|I,O)$. Except for works that directly learn from pixels , the task is commonly reformulated by first detecting bounding boxes $B$ and extracting corresponding object and edge features, $V=f(I,B)$ and $E=g(I,B)$ respectively, using some functions $f,g$ (e.g. a ConvNet followed by ROI Align ):

The advantage of this approach is that solving $P(O,R|V,E,I)$ is easier than solving $P(O,R|I)$. At the same time, to compute $P(V,E|I)$ we can use pretrained object detectors . Therefore, we follow and use this approach to scene graph generation.

In practice, we can assume that the pretrained object detector is fixed or that ground truth bounding boxes $B$ are available, so we can assume $P(V,E|I)$ is constant. In addition, following , we can assume conditional independence of variables $O$ and $R$: $P(O,R|V,E,I)=P(O|V,E,I)P(R|V,E,I)$. We thus obtain the scene graph generation loss:

Some models do not assume the conditional independence of $O$ and $R$, making predicates explicitly depend on subject and object labels: $P(O,R|V,E,I)=P(O|V,E,I)P(R|O,V,E,I)$. However, such a model must be carefully regularized, since it can start to ignore $(V,E,I)$ and mainly rely on the frequency distribution $P(R|O)$ as a stronger signal. For example, the model can learn that between ‘cup’ and ‘table’ the relationship is most likely to be ‘on’, regardless the visual signal. As we show, this can hurt generalization.

Eq. (2) is commonly handled as a multitask classification problem, where each task is optimized by the cross-entropy loss ${\cal L}$. In particular, given a batch of scene graphs with $N$ nodes and $M$ edges in total, the loss is the following:

Node and edge features $(V,E)$ output by the detector form a complete graph without self-loops (Figure 1). So, conventionally , the loss is applied to all edges: $M\approx N^{2}$. These edges can be divided into foreground (FG), corresponding to annotated edges, and background (BG), corresponding to not annotated edges: $M=M_{FG}+M_{BG}$. The BG edge type is similar to a “negative” class in the object detection task and has a similar purpose. Without training on BG edges, at test time the model would label all pairs of nodes as “positive”, i.e. having some relationship, when often it is not the case (at least, given the vocabulary in the datasets). Therefore, not using the BG type can hurt the quality of predicted scene graphs and can lower recall.

2 Hyperparameter-free Normalization of the Edge Loss

Baseline loss as a function of graph density. In scene graph datasets such as Visual Genome, the number of BG edges is greater than FG ones (Figure 3), yet the baseline loss (3) does not explicitly differentiate between BG and other edges. If we assume a fixed probability for two objects to have a relationship, then as the number of nodes grows we can expect fewer of them to have a relationship. Thus the graph density can vary based on the number of nodes (Figure 4), a fact not taken into account in Eq. (3). To avoid this, we start by decoupling the edge term of (3) into the foreground (FG) and background (BG) terms:

where ${\cal E}$ is a set of FG edges, $M_{FG}$ is the number of FG edges ($|{\cal E}|$) and $M_{BG}$ is the number of BG edges. Next, we denote FG and BG edge losses averaged per batch as ${\cal L}_{FG}=1/M_{FG}\sum_{ij\in\cal E}^{M_{FG}}{\cal L}_{rel,ij}$ and ${\cal L}_{BG}=1/M_{BG}\sum_{ij\notin\cal E}^{M_{BG}}{\cal L}_{rel,ij}$, respectively. Then, using the definition of graph density as a proportion of FG edges to all edges, $d=M_{FG}/(M_{BG}+M_{FG})$, we can express the total baseline loss equivalent to Eq. (3) as a function of graph density:

Density-normalized edge loss. Eq. (5) and Figure 4 allow us to notice two issues:

Discrepancy of the loss between graphs of different sizes. Since $d$ exponentially decreases with graph size (Fig. 4, left), FG edges of larger graphs are weighted less than edges of smaller graphs in the loss (Fig. 4, middle), making the model neglect larger graphs.

Discrepancy between object and edge losses. Due to $d$ tending to be small on average, $L_{edge}$ is much smaller than $L_{node}$, so the model might focus mainly on $L_{node}$ (Fig. 4, right).

Both issues can be addressed by normalizing FG and BG terms by graph density $d$:

where $\gamma=1$ in our default hyperparameter-free variant and $\gamma\neq 1$ only to empirically analyze the loss (Table 4). Even though the BG term still depends on graph density, we found it to be less sensitive to variations in $d$, since the BG loss quickly converges to some stable value, performing a role of regularization (Figure 4, right). We examine this in detail in Section 4.

3 Weighted Triplet Recall

The common evaluation metric for scene graph prediction is image-level Recall@K or R@K . To compute it, we first need to extract the top-$K$ triplets, $\text{Top}_{K}$, from the entire image based on ranked predictions of a model . Given a set of ground truth triplets, GT, the image-level R@K is computed as (see Figure 5 for a visualization):

There are four issues with this metric (we discuss additional details in Appendix):

The frequency bias of triplets means more frequent triplets will dominate the metric.

The denominator in (7) creates discrepancies between images with different $|\text{GT}|$ (the number of ground truth triplets in an image), especially pronounced in few/zero shots.

Evaluation of zero ($n=0$) and different few-shot cases $n=1,5,10,...$ leads to many R@K results . This complicates the analysis. Instead, we want a single metric for all $n$.

Two ways of computing the image-level recall , graph constrained and unconstrained, lead to very different results and complicate the comparison (Figure 5).

To address issue (a), the predicate-normalized metric, mean recall (mR@K) and weighted mR@K were introduced . These metrics, however, only address the imbalance of predicate classes, not whole triplets. Early work used triplet-level Recall@K (or Rtr@K) for some tasks (e.g. predicate detection), which is based on ranking predicted triplets for each ground truth subject-object pair independently; the pairs without relationships are not evaluated. Hence, Rtr@K is similar to top-$K$ accuracy. This metric avoids issues (b) and (d), but the issues of the frequency bias (a) and unseen/rare cases (c) still remain. To alleviate these, we adapt this metric to better track unseen and rare cases. We call our novel metric Weighted Triplet Recall wRtr@K, which computes a recall at each triplet and reweights the average result based on the frequency of the GT triplet in the training set:

where $T$ is the number of all test triplets, $[\cdot]$ is the Iverson bracket, $w_{t}=\frac{1}{(n_{t}+1)\sum_{t}1/(n_{t}+1)}\in$ and $n_{t}$ is the number of occurrences of triplet $t$ in the training set; $n_{t}+1$ is used to handle zero-shot triplets; $\sum_{t}w_{t}=1$. Since wRtr@K is still a triplet-level metric, we avoid issues (b) and (d). Our metric is also robust to the frequency-bias (a), since frequent triplets (with high $n_{t}$) are downweighted proportionally, which we confirm by evaluating the Freq model from . Finally, a single wRtr@K value shows zero and few-shot performance linearly aggregated for all $n\geq 0$, solving issue (c).

Experiments

Datasets. We evaluate our loss and metric on Visual Genome . Since it is a noisy dataset, several “clean” variants were introduced. We mainly experiment with the most common variant (VG) , which consists of the 150 most frequent object and 50 predicates classes. An alternative variant (VTE) has been often used for zero-shot evaluation. Surprisingly, we found that the VG split is better suited for this task, given a larger variability of zero-shot triplets in the test set (see Table 7 in Appendix). Recently, GQA was introduced, where scene graphs were cleaned to automatically construct question answer pairs. GQA has more object and predicate classes, so that zero and few-shot triplets are more likely to occur at test time. To the best of our knowledge, scene graph generation (SGG) results have not been reported on GQA before, even though some VQA models have relied on SGG .

Training and evaluation details. We experiment with two models: Message Passing (MP) and Neural Motifs (NM) . We use publicly available implementations of MP and NMhttps://github.com/rowanz/neural-motifs, with all architecture details and hyperparameters kept the same (except for the small changes outlined in Table 8 in Appendix). To be consistent with baseline models, for Visual Genome we use Faster R-CNN with VGG16 as a backbone to extract node and edge features. For GQA we choose a more recent Mask R-CNN with ResNet-50-FPN as a backbone pretrained on COCO. We also use this detector on the VTE split. We perform more experiments with Message Passing, since our experiments revealed that it better generalizes to zero and few-shot cases, while performing only slightly worse on other metrics. In addition, it is a relatively simple model, which makes the analysis of its performance easier. We evaluate models on three tasks, according to : 1) predicate classification (PredCls), in which the model only needs to label a predicate given ground truth object labels and bounding boxes, i.e. $P(R|I,B,O)$; 2) scene graph classification (SGCls), in which the model must also label objects, i.e. $P(O,R|I,B)$; 3) scene graph generation SGGen (sometimes denoted as SGDet), $P({\cal G}|I)$, which includes detecting bounding boxes first (reported separately in Tables 5, 6).

Table 1 shows our main results, where for each task we report five metrics: image-level recall on all triplets (R@K) and zero-shot triplets (RZS@K), triplet-level recall (Rtr@K) and our weighted triplet recall (wRtr@K), and mean recall (mR@K). We compute recalls without the graph constraint since, as we discuss in Appendix, this is a more accurate metric. We denote graph-constrained results as PredCls-GC, SGCls-GC, SGGen-GC and report them only in Tables 4, 4 and Table 5.

We can observe that both Message Passing (MP) and Neural Motifs (NM) greatly benefit from our density-normalized loss on all reported metrics. Larger gaps are achieved on metrics evaluating zero and few-shots. For example, in PredCls on Visual Genome, MP with our loss is 22% better (in relative terms) on zero-shots, while NM with our loss is 50% better. The gains arising from other zero-shot and weighted metrics are also significant.

GQA results.

On GQA, our loss also consistently improves results, especially in PredCls. However, the gap is lower compared to VG. There are two reasons for this: 1) scene graphs in GQA are much denser (see Appendix), i.e. the imbalance between FG and BG edges is less pronounced, which means that in the baseline loss the edge term is not diminished to the extent it is in VG; and 2) the training set of GQA is more diverse than VG (with 15 times more labeled triplets), which makes the baseline model generalize well on zero and few-shots. We confirm these arguments by training and evaluating on our version of GQA: GQA-nLR with left and right predicate classes excluded making scene graph properties, in particular sparsity, more similar to those of VG.

Effect of the Frequency Bias (Freq) on Zero and Few-Shot Performance.

The Freq model simply predicts the most frequent predicate between a subject and an object, $P(R|O)$. Its effect on few-shot generalization has not been empirically studied before. We study this by adding/ablating Freq from baseline MP and NM on Visual Genome (Figure 6). Our results indicate that Freq only marginally improves results on unweighted metrics. At the same time, perhaps unsurprisingly, it leads to severe drops in zero-shot and weighted metrics, especially in NM. For example, by ablating Freq from NM, we improve PredCls-RZS@50 from 11% to 25%. This also highlights that the existing recall metrics are a poor choice to understand the effectiveness of a model.

Why does loss normalization help more on few and zero-shots?

The baseline loss effectively ignores edge labels of large graphs, because it is scaled by a small $d$ in those cases (Figure 4). To validate that, we split the training set of Visual Genome in two subsets, with a comparable number of images in each: with relatively small and large graphs evaluating on the original test set in both cases. We observe that the baseline model does not learn well from large graphs, while our loss enables this learning (Figure 7). Moreover, when trained on small graphs only, the baseline is even better in PredCls than when trained on all graphs. This is because in the latter case, large graphs, when present in a batch, make the whole batch more sparse, downweighting the edge loss of small graphs as well. At the same time, larger graphs predictably contain more labels, including many few-shot labels (Figure 2). Together, these two factors make the baseline ignore many few-shot triplets pertaining to larger graphs at training time, so the model cannot generalize to them at test time. Since the baseline essentially observes less variability during training, it leads to poor generalization on zero-shots as well. This argument aligns well to the works from other domains , showing that generalization strongly depends on the diversity of samples during training. Our loss fixes the issue of learning from larger graphs, which, given the reasons above, directly affects the ability to generalize.

Alternative approaches.

We compare our loss to ones with tuned hyperparameters $\alpha,\beta,\lambda$ (Table 4):

Our main finding is that, while these losses can give similar or better results in some cases, the parameters $\alpha$, $\beta$ and $\lambda$ do not generally transfer across datasets and must be tuned every time, which can be problematic at larger scale . In contrast, our loss does not require tuning and achieves comparable performance.

To study the effect of density normalization separately from upweighting the edge loss (which is a side effect of our normalization), we also consider downweighting our edge term (6) by some $\gamma<1$ to cancel out this upweighting effect. This ensures a similar range for the losses in our comparison. We found (Table 4) that the results are still significantly better than the baseline and, in some cases, even better than our hyperparameter-free loss. This further confirms that normalization of the graph density is important on its own. When carefully fine-tuned, the effects of normalization and upweighting are complimentary (e.g. when $\alpha,\beta$ or $\gamma$ are fine-tuned, the results tend to be better).

Comparison to other zero-shot works.

We also compare to previous works studying zero-shot generalization (Tables 4 and 4). For comprehensive evaluation, we test on both VTE and VG splits. We achieve superior results on VTE, even by just using the baseline MP, because, as shown in our main results, it generalizes well. On the VG split, we obtain results that compete with a more recent Total Direct Effect (TDE) method , even though the latter uses a more advanced detector and feature extractor. In all cases, our loss improves baseline results and, except for RZS@100 in SGCls, leads to state-of-the-art generalization. Our loss and TDE can be applied to a wide range of models, beyond MP and NM, to potentially have a complementary effect on generalization, which is interesting to study in future work.

Comparison on SGGen, P​(𝒢|I)𝑃conditional𝒢𝐼P({\cal G}|I).

In SGCls and PredCls, we relied on ground truth bounding boxes $B_{gt}$, while in SGGen the bounding boxes $B_{pred}$ predicted by a detector should be used to enable a complete image-to-scene graph pipeline. Here, even small differences between $B_{gt}$ and $B_{pred}$ can create large distribution shifts between corresponding extracted features $(V,E)$ (see Section 3.1), on which SGCls models are trained. Therefore, it is important to refine the SGCls model on $(V,E)$ extracted based on predicted $B_{pred}$, according to previous work . In our experience, this refinement can boost the R@100 result by around 3% for Message Passing and up to 8% for Neural Motifs (in absolute terms). In Table 5, we report results after the refinement completed both for the baseline loss and our loss in the same way. Similarly to the SGCls and PredCls results, our loss consistently improves baseline results in SGGen. It also allows Neural Motifs (NM) to significantly outperform KERN on zero-shots (RZS@100), while being only slightly worse in one of the mR@100 results. The main drawback of KERN is its slow training, which prevented us to explore this model together with our loss. Following our experiments in Table 1 and Figure 6, we also confirm the positive effect of removing Freq from NM. A more recent work of Tang et al. shows better results on zero-shots and mean recall, however, we note their more advanced feature extractor, therefore it is difficult to compare our results to theirs in a fair fashion. But, since they also use the baseline loss (3), our loss (6) can potentially improve their model, which we leave for future work.

Finally, we evaluate SGGen on GQA using Message Passing (Table 6), where we also obtain improvements with our loss. GQA has 1703 object classes compared to 150 in VG making object detection harder. When evaluating SGGen, the predicted triplet is matched to ground truth (GT) if predicted and GT bounding boxes have an intersection over union (IoU) of $\geq$50%, so more misdetections lead to a larger gap between SGCls and SGGen results.

Conclusions

Scene graphs are a useful semantic representation of images, accelerating research in many applications including visual question answering. It is vital for the SGG model to perform well on unseen or rare compositions of objects and predicates, which are inevitable due to an extremely long tail of the distribution over triplets. We show that strong baseline models do not effectively learn from all labels, leading to poor generalization on few/zero shots. Moreover, current evaluation metrics do not reflect this problem, exacerbating it instead. We also show that learning well from larger graphs is essential to enable stronger generalization. To this end, we modify the loss commonly used in SGG and achieve significant improvements and, in certain cases, state-of-the-art results, on both the existing and our novel weighted metric.

Acknowledgments

BK is funded by the Mila internship, the Vector Institute and the University of Guelph. CC is funded by DREAM CDT. EB is funded by IVADO. This research was developed with funding from DARPA. The views, opinions and/or findings expressed are those of the authors and should not be interpreted as representing the official views or policies of the Department of Defense or the U.S. Government. The authors also acknowledge support from the Canadian Institute for Advanced Research and the Canada Foundation for Innovation. We are also thankful to Brendan Duke for the help with setting up the compute environment. Resources used in preparing this research were provided, in part, by the Province of Ontario, the Government of Canada through CIFAR, and companies sponsoring the Vector Institute: http://www.vectorinstitute.ai/#partners.

References

Appendix

2 Evaluation

Evaluation of zero/few shot cases. To evaluate $n$-shots using image-level recall, we need to keep in the test images only those triplets that have occurred no more than $n$ times and remove images without such triplets. This results in computing recall for very sparse annotations, so the image-level metric can be noisy and create discrepancies between simple images with a few triplets and complex images with hundreds of triplets. For example, for an image with only two ground truth triplets, R@100 of 50% can be a quite bad result, while for an image with hundreds of triplets, this can be an excellent result. Our Weighted Triplet Recall is computed for all test triplets joined into a single set, so it resolves this discrepancy.

Constrained vs unconstrained metrics. In the graph constrained case , only the top-1 predicted predicate is considered when triplets are ranked, and follow-up works improved results by removing this constraint. This unconstrained metric more reliably evaluates models, since it does not require a perfect triplet match to be the top-1 prediction, which is an unreasonable expectation given plenty of synonyms and mislabeled annotations in scene graph datasets. For example, ‘man wearing shirt’ and ‘man in shirt’ are similar predictions, however, only the unconstrained metric allows for both to be included in ranking. The SGDet+ metric has a similar motivation as removing the graph constraint, but it does not address the other issues of image-level metrics.