Scene Graph Modification Based on Natural Language Commands (2020)

Abstract: Structured representations like graphs and parse trees play a crucial role in many Natural Language Processing systems. In recent years, the advancements in multi-turn user interfaces necessitate the need for controlling and updating these structured representations given new sources of information. Although there have been many efforts focusing on improving the performance of the parsers that map text to graphs or parse trees, very few have explored the problem of directly manipulating these representations. In this paper, we explore the novel problem of graph modification, where the systems need to learn how to update an existing scene graph given a new user’s command. Our novel models based on graph-based sparse transformer and cross attention information fusion outperform previous systems adapted from the machine translation and graph generation literature. We further contribute our large graph modification datasets to the research community to encourage future research for this new problem.

## introduction parsing text into structured semantics representation is one of the most long-standing and active research problems in nlp. numerous parsing methods have been developed for many different semantic structure representations @xcite @xcite @xcite . however, most of these previous works focus on parsing a single sentence, while a typical human-computer interaction session or conversation is not singleturn. a prominent example is image search. users usually start with short phrases describing the main objects or topics they are looking for. depending on the result, the users may then modify their query to add more constraints or give additional information. in this case, without the modification capability, a static representation is not suitable to track the changing intent of the user. we argue that the back-and-forth and multi-turn nature of human-computer interactions necessitate the need for updating the structured representation. another advantage of modifying a structured representation in the interactive setting is that it makes it easier to check the consistency. for instance, it is much easier to check whether the user requests two contradicting attributes for the same object in a scene graph during the interactive search, which can be done automatically. in this paper, we propose the problem of scene graph modification for search. a scene graph @xcite is a semantic formalism which represents the desired image as a graph of objects with relations and attributes. this semantic representation has been shown to be very successful in retrieval systems @xcite @xcite . inspired by the dialog state tracking setting @xcite , we consider the scene graph modification problem as follows. given an initial scene graph and a new query issued by the user, the goal is to generate a new scene graph taking into account the original graph and the new query. we formulate the problem as conditional graph modification, and create three datasets for this problem. we propose novel encoder-decoder architectures for conditional graph modification. more specifically, our graph encoder is built upon the self-attention architecture popular in state-of-theart machine translation models @xcite , which is superior to, according to our study, graph convolutional networks (gcn) @xcite . unique to our problem, however, is the fact that we have an open set of relation types in the graphs. thus, we propose a novel graph-conditioned sparse transformer, in which the relation information is embed-ded directly into the self-attention grid. for the decoder, we treat the graph modification task as a sequence generation problem @xcite @xcite . furthermore, to encourage the information sharing between the input graph and modification query, we introduce two techniques, i.e. late feature fusion through gating and early feature fusion through cross-attention. we further create three datasets to evaluate our models. the first two datasets are derived from public sources: mscoco @xcite and google conceptual captioning (gcc) @xcite while the last is collected using amazon mechanical turk (mturk). experiments show that our best model achieves up to 8.5% improvement over the strong baselines on both the synthetic and user-generated data in terms of f1 score. our contributions are three-fold. firstly, we introduce the problem of scene graph modificationan important component in multi-modal search and dialogue. secondly, we propose a novel encoderdecoder architecture relying on graph-conditioned transformer and cross-attention to tackle the problem, outperforming strong baselines which we setup for the task. thirdly, we introduce three datasets which can serve as evaluation benchmarks for future research. 1 ## data creation in this section, we detail our data creation process. we start with information on scene graphs and a parser to generate them for the captions in two existing datasets, i.e. mscoco @xcite and gcc @xcite . we then describe how to generate modified scene graphs and modification queries based on these scene graphs, and leverage human annotators to increase and analyze data quality. ## methodology in this section, we explore different methods to tackle our proposed problem. by analyzing the results and comparing different models, we establish baselines and set up the research direction for future work. we start by formalizing the problem, and defining the input as well as the expected output along with the notations. we then define our encoder-decoder architecture with the focus on our novel modeling characteristics: (i) the graph encoder with graph-conditioned, sparsely connected transformer and (ii) the early and late feature fusion models for combining information from the input text and graph. ## experiments baselines. we consider five baselines for comparison. in "copy source" baseline (i), the system copies the source graph to the target graph foot_1 . in the "text2text" baseline (ii), we flatten the graph and reconstruct the natural sentence similarly to the modification query. in the "modified graphrnn" baseline (iii), we use the breadth-first-search (bfs) based node ordering to flatten the graph foot_2 , and use rnns as the encoders @xcite and a decoder similar to our systems. in the final two baselines, "graph transformer" (iv) and "deep convolutional graph networks" (dcgcn) (v), we use the graph transformers @xcite and deep convolutional graph networks @xcite to encode the source graph (the decoder is identical to ours). ## related work semantic parsing is a sequence-to-graph transduction task, mapping natural language sentences to their meaning representation, e.g. see @xcite @xcite ; this is different from our graph conditional semantic parsing. recently, context-dependent semantic parsing has gained attraction @xcite @xcite . our work focuses on the update of scene graphs based on users' queries, while previous works model the modifications of semantic representations in multi-turn dialogue systems. due to their effectiveness, gcns and graph transformer have been used as graph encoder for graphto-sequence transduction in semantic-based text generation @xcite @xcite @xcite . ## conclusion in this paper, we explore a novel problem of conditional graph modification, in which a system needs to modify a source graph according to a modification command. our best system, which is based on graph-conditioned transformers and cross-attention information fusion, outperforms strong baselines adapted from machine translations and graph generations. the code and datasets will be released to encourage further research in this direction.