Source-linked AI summary
Mapping Images to Scene Graphs with Permutation-Invariant Structured Prediction
Roei Herzig, Moshiko Raboh, Gal Chechik, Jonathan Berant, Amir Globerson
TL;DR
Scene-graph prediction involves interdependent labels, while general score-based inference can be computationally hard. The paper proposes permutation-invariant architectures for structured prediction and reports state-of-the-art Visual Genome results.
Problem
Scene-graph prediction must handle interdependent object and relation labels, while maximizing a general structured-prediction score can be computationally hard.
Source: §1 · pp. 1–2Method
The paper constrains deep structured-prediction architectures to produce outputs invariant to equivalent representations of pairwise terms.
Source: §6 · p. 9Results
The model achieves state-of-the-art results on Visual Genome, and synthetic experiments show permutation-respecting models need less training data at comparable model size.
Source: §1 · p. 2Takeaways & Limitations
Attention is a natural component of the GPI characterization and plays a key role in the scene-graph model.
Source: §3.1 · p. 6Architectures for geometric or feature-permutation invariances, and methods for discovering unknown invariant structure, are left for future work.
Source: §6 · p. 10
Abstract
from arXiv · showhide
Machine understanding of complex images is a key goal of artificial intelligence. One challenge underlying this task is that visual scenes contain multiple inter-related objects, and that global context plays an important role in interpreting the scene. A natural modeling framework for capturing such effects is structured prediction, which optimizes over complex labels, while modeling within-label interactions. However, it is unclear what principles should guide the design of a structured prediction model that utilizes the power of deep learning components. Here we propose a design principle for such architectures that follows from a natural requirement of permutation invariance. We prove a necessary and sufficient characterization for architectures that follow this invariance, and discuss its implication on model design. Finally, we show that the resulting model achieves new state of the art results on the Visual Genome scene graph labeling benchmark, outperforming all recent approaches.
1 Introduction
Scene-graph prediction must jointly infer interdependent objects and relations, motivating structured prediction; the paper proposes permutation invariance as a design principle for deep models and reports strong Visual Genome results.
1 Introduction
- Scene graphs represent image entities and their relations, whose interdependence motivates structured prediction.Source: §1 · p. 1
- Score-based structured prediction faces computationally hard inference because possible label assignments grow exponentially with input size.Source: §1 · p. 2
- The paper gives necessary and sufficient conditions for graph-permutation invariance and describes architectures satisfying them.Source: §1 · p. 2
- The proposed model achieves state-of-the-art results on Visual Genome, while synthetic experiments show that respecting permutation invariance reduces training-data needs at comparable model size.Source: §1 · p. 2
2 Structured Prediction
Structured prediction scores candidate label assignments and often decomposes those scores into simpler functions. Deep-learning work has incorporated neural scoring components, while this section motivates direct input-to-output models as an alternative.
2 Structured Prediction
- Structured prediction assigns compatibility scores to labels and can decompose them into simpler functions that support efficient local maximization.Source: §2 · p. 2
- Deep-learning approaches model local singleton and pairwise scores, progressing from independently learned local scores to end-to-end inference and global factors.Source: §2 · pp. 2–3
- Although score-based methods flexibly specify local dependencies, deep scoring removes convexity and general inference can be hard, motivating direct neural mapping from inputs to structured outputs.Source: §2 · p. 3
3 Permutation-Invariant Structured Prediction
The section characterizes graph-permutation-invariant labeling functions and shows how invariant aggregation can retain graph-wide information. It extends the characterization to incomplete graphs and draws implications for parallelizable, recurrent, and attention-based architectures.
3.1 Characterizing Permutation Invariance
- A graph labeling function is graph-permutation invariant if and only if it has the characterized form using functions φ, α, and ρ.The form aggregates features across the graph before producing each node's label.Source: §3.1 · p. 4
- The characterization applies to incomplete graphs by restricting aggregation to valid neighbors and requiring invariance only under graph automorphisms.For node i, the sum ranges over its neighbors N(i).Source: §3.1 · p. 5
- The φ and α aggregations can summarize the entire graph for downstream algorithms, unlike one round of message passing, though their dimensions may need to be large.The architecture itself can remain shallow.Source: §3.1 · p. 5
- All φ functions can be applied in parallel, unlike recurrent models that are harder to parallelize and slower in practice.Source: §3.1 · p. 6
- Attention fits the characterization by weighting neighboring features, while composing graph-permutation-invariant functions supports recurrent architectures.The paper uses both structures in its scene graph model.Source: §3.1 · p. 6
4 Related Work
The related work situates the paper among invariant architectures, deep structured prediction, and scene graph generation. It distinguishes the paper's general characterization from prior approaches and describes the fixed input ordering used by NeuralMotif.
4 Related Work
- The paper's graph-permutation invariance is less restrictive than DEEPSETS because it requires only permutations consistent with graph relabeling.Source: §4 · p. 6
- Prior deep structured prediction uses message passing, learned score maximization, or greedy decoding, while graph-optimization work does not specify a general invariant architecture [Gilmer et al., 2017].The paper says its characterization strictly generalizes message-passing architectures.Source: §4 · p. 6
- NeuralMotif uses an RNN to add global context to scene graph predictions, maintaining graph-permutation invariance by fixing one input order that is not guaranteed optimal [Zellers et al., 2017].Source: §4 · p. 6
5 Experimental Evaluation
Experiments assess graph-permutation invariance (GPI) on synthetic graph labeling and Visual Genome scene-graph classification; GPI:LINGUISTIC outperforms all baselines on SGCls and is comparable to the state-of-the-art model on PredCls.
5.1 Synthetic Graph Labeling
- With the same number of parameters across models, GPI requires far fewer samples than alternatives to converge to the correct synthetic graph-labeling solution.Figure 3 plots accuracy against sample size.Source: §5.1 · p. 7, Figure 3 · p. 7
5.2.1 Experimental Setup and Results
- GPI:LINGUISTIC outperforms all baselines on SGCls and is comparable to the state-of-the-art model on PredCls.PredCls is easier and makes less use of structure.Source: Table 1 · p. 8, §5.2.1 · p. 9
5.2 Scene-Graph Classification
- SGP connects entity variables pairwise and links each relation variable to its two entities; attention aggregates neighbor features before entity and relation logits are produced.The entity-pair network combines features for two entities and their pairwise relation.Source: §5.2 · pp. 7–8
5.2.1 Experimental Setup and Results
- Visual Genome experiments use 108,077 images and 150 entity and 50 relation classes, evaluating SGCls and PredCls with Recall@K under constrained and unconstrained protocols.The task uses given bounding boxes; PredCls also uses given entity labels.Source: §5.2 · p. 7, §5.2.1 · p. 8
- Figure 4 illustrates baseline entity and relation errors corrected by GPI:LINGUISTIC, with attention favoring nearby entities and informative classes.The figure highlights the window as a significant neighbor of the tree and stronger attention for bird than tree.Source: Figure 4 · p. 9, §5.2.1 · p. 9
6 Conclusion
The approach preserves pairwise inter-label features while directly producing outputs invariant to equivalent pairwise-term representations; broader symmetry classes remain possible extensions.
6 Conclusion
- The approach uses pairwise features to describe inter-label correlations while directly producing outputs invariant to equivalent representations of those terms.Unlike score-based methods, it does not maximize a score function, which the paper describes as computationally hard inference.Source: §6 · p. 9
- Geometric invariances such as shifts or rotations, and feature-permutation invariance, are proposed as possible extensions whose architectures remain to be derived.The paper also identifies discovering unknown invariant structure from data as future work.Source: §6 · p. 10
- When the invariant structure is unknown, discovering and using such symmetries is an open direction related to lifting graphical models..Source: §6 · p. 10
7 Supplementary Material
The supplement illustrates Theorem 1’s construction, shows how attention fits the GPI framework, and adds per-relation PredCls comparisons.
7.1 Theorem 1: Illustration of Proof
- In the proof illustration, summed φ feature vectors form s_i, outer products with hash indicators form α matrices, and their sum is isomorphic to the original pairwise-feature matrix.The example uses a three-node graph and a hash-function size of L = 5.Source: Figure 5 · p. 12
7.2 Characterizing Permutation Invariance: Attention
- Neighbor attention encodes e^β z_i,j and e^β as summed feature blocks, divides the first by the second, and can also be applied over α and ρ.β may be any scalar-valued function of the node and pairwise features.Source: §7.2 · pp. 12–13
7.3 Scene Graph Results
- GPI: LINGUISTIC performs better on almost all relation classes in PredCls Recall@5 comparisons with Lu et al. (2016) and Xu et al. (2017).Table 2 covers the 20 most frequent relations.Source: Table 2 · p. 13, §7.3 · p. 13