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

Boris Knyazev, Harm de Vries, Catalina Cangea, Graham W. Taylor, Aaron C. Courville, Eugene Belilovsky

Introduction

Scene Graph Generation (SGG) is a fundamental computer vision task that involves parsing an image into a structured representation. In a scene graph, nodes represent objects (e.g., "man", "surfboard"), and edges represent the relationships between them (e.g., "on", "in"). A significant hurdle in this field is compositional generalization: the ability of a model to recognize novel (zero-shot) or rare (few-shot) combinations of concepts. For instance, a model might easily identify a "man in a shirt" because it is a frequent triplet, but struggle with a "cup on a surfboard," a combination it may never have seen during training.

Conceptual diagram of a scene graph highlighting the difference between frequent and zero-shot triplets.

The Challenges of Generalization

The authors identify two primary obstacles preventing current SGG models from generalizing effectively:

  1. The Math of Neglect: In an image containing $N$ objects, the model evaluates $N^2$ potential edges. In complex scenes with many objects, the vast majority of these edges represent "background" (no relationship). Standard loss functions average error across all $N^2$ edges. As $N$ increases, the signal from actual relationships (foreground) is mathematically overwhelmed by the background noise. Consequently, models tend to ignore the rich information present in complex, dense images.
  2. Frequency Bias: Datasets like Visual Genome are highly imbalanced. Models often learn to rely on statistical priors—guessing "on" whenever they see a "cup" and a "table"—rather than extracting features from the visual evidence. This "lazy" behavior is often rewarded by standard evaluation metrics but fails catastrophically on novel compositions.

Proposed Methodology: Density-Normalized Edge Loss

To address the "neglect" of complex scenes, the researchers propose a Density-Normalized Edge Loss. Unlike the standard approach that treats all $N^2$ edges equally, this new loss decouples the calculation into Foreground (FG) and Background (BG) terms. The loss is then normalized by the graph's density—the ratio of actual relationships to total possible edges.

This simple, hyperparameter-free modification ensures that foreground edges in large, sparse graphs generate gradients strong enough to drive learning. It forces the model to attend to the diverse examples often found in complex scenes.

Furthermore, the authors introduce Weighted Triplet Recall (wRtr@K). This metric evaluates accuracy at the individual triplet level and applies an inverse weight based on training frequency. This prevents models from achieving high scores simply by exploiting frequency biases.

Experimental Results

The proposed density-normalized loss was evaluated on standard datasets like Visual Genome and GQA. The results demonstrate significant improvements across the board, particularly in zero-shot scenarios.

Comparison of baseline performance vs. the proposed density-normalized loss, showing substantial gains.

Key findings include:

  • Zero-Shot Performance: Applying the loss to a Message Passing (MP) baseline resulted in a 22% relative improvement in zero-shot recall ($R_{ZS}@100$) on Visual Genome. For the Neural Motifs (NM) baseline, the improvement reached 50%.
  • Debiasing Effects: Removing the frequency prior from the Neural Motifs model caused zero-shot predicate classification ($R_{ZS}@50$) to jump from 11.1% to 26.6%, highlighting how much statistical bias hinders true visual understanding.
  • Efficiency: Since the method only modifies the loss function, these performance gains are achieved with zero additional computational overhead during training or inference.

Conclusion and Future Directions

By acknowledging that graph density dictates learning, this work provides a simple yet powerful tool for improving compositional generalization in SGG. While the density-normalized loss significantly aids learning from large graphs, the authors note that performance still dips for extremely complex scenes (>40 nodes), likely due to "oversmoothing" in Graph Neural Networks. Future research may explore edge-specific attention mechanisms to further enhance the model's ability to parse the most intricate visual environments.

Summary updated

Abstract

Scene graph generation (SGG) aims to predict graph-structured descriptions of input images, in the form of objects and relationships between them. This task is becoming increasingly useful for progress at the interface of vision and language. Here, it is important - yet challenging - to perform well on novel (zero-shot) or rare (few-shot) compositions of objects and relationships. In this paper, we identify two key issues that limit such generalization. Firstly, we show that the standard loss used in this task is unintentionally a function of scene graph density. This leads to the neglect of individual edges in large sparse graphs during training, even though these contain diverse few-shot examples that are important for generalization. Secondly, the frequency of relationships can create a strong bias in this task, such that a blind model predicting the most frequent relationship achieves good performance. Consequently, some state-of-the-art models exploit this bias to improve results. We show that such models can suffer the most in their ability to generalize to rare compositions, evaluating two different models on the Visual Genome dataset and its more recent, improved version, GQA. To address these issues, we introduce a density-normalized edge loss, which provides more than a two-fold improvement in certain generalization metrics. Compared to other works in this direction, our enhancements require only a few lines of code and no added computational cost. We also highlight the difficulty of accurately evaluating models using existing metrics, especially on zero/few shots, and introduce a novel weighted metric.
BibTeX
@inproceedings{knyazev2020graph,
  author = {Boris Knyazev and Harm de Vries and Catalina Cangea and Graham W. Taylor and Aaron C. Courville and Eugene Belilovsky},
  title = {{Graph Density-Aware Losses for Novel Compositions in Scene Graph Generation}},
  booktitle = {BMVC},
  year = {2020},
  url = {https://openreview.net/forum?id=wEa6nIU-pex},
}
Figure