Scene Graph Modification as Incremental Structure Expanding (2022)

Abstract: A scene graph is a semantic representation that expresses the objects, attributes, and relationships between objects in a scene. Scene graphs play an important role in many cross modality tasks, as they are able to capture the interactions between images and texts. In this paper, we focus on scene graph modification (SGM), where the system is required to learn how to update an existing scene graph based on a natural language query. Unlike previous approaches that rebuilt the entire scene graph, we frame SGM as a graph expansion task by introducing the incremental structure expanding (ISE). ISE constructs the target graph by incrementally expanding the source graph without changing the unmodified structure. Based on ISE, we further propose a model that iterates between nodes prediction and edges prediction, inferring more accurate and harmonious expansion decisions progressively. In addition, we construct a challenging dataset that contains more complicated queries and larger scene graphs than existing datasets. Experiments on four benchmarks demonstrate the effectiveness of our approach, which surpasses the previous state-of-the-art model by large margins.

## introduction a scene graph is a structural representation that captures the semantics of visual scenes by encoding object instances, attributes of objects, and relationships between objects. @xcite . as shown in figure 1 , the scene graph encodes objects (e.g. "boy", "racket"), attributes (e.g. "girl is standing"), and relations ("boy holding racket"). scene graphs are able to capture the interactions between text and images by associating objects in the graph with regions of an image and modeling the relations between objects. therefore, it has been used in the cross modality task such as image retrieval, image captioning, and visual question answering @xcite @xcite . recently, modifying the scene graph based on the input becomes an emerging research direction as cross-modal systems may need to resort to an interactive process through multiple iterations @xcite . take text-based image retrieval as an example, users start with a query describing the main objects or topics they are looking for, then modify the query to add more constraints or provide additional information based on previous search results. instead of directly manipulating images, scene graphs can be used to convert the image-editing problem into a graphediting problem, conditioned on the textual query. as shown in figure 1 , given a retrieved image from the last turn, if the user wants to see a girl rather than a boy holding a racket, he will enter the query "i would like to see a girl holding racket" to the system. according to the query, the object "boy" in the original scene graph will be substituted with the object "girl". the target image can be retrieved given the updated scene graph. the key challenge in this process is how to modify the corresponding partial structure in the original scene graph based on understanding the natural language query. prior effort framed this scene graph modification (sgm) task as conditional graph generation @xcite , where the scene graph is generated from the scratch condition on the original graph and query @xcite @xcite . however, rebuilding the entire scene graph may not be an optimal solution, as the model has to generate the partial structure of the original graph that should be unmodified. moreover, nodes and edges of the scene graph are constructed separately in their proposed framework, which generates all the nodes first then attaches edges between generated nodes in the second pass. such an approach may lead to the lack of the modeling capability of interactions between node prediction and edge prediction. instead of rebuilding the whole scene graph, we introduce a novel formulation for sgm -incremental structure expanding (ise), which is able to build the target graph by gradually expanding the original structure. at each step, ise generates the connecting edges between the existing nodes and the newly generated node, upon which the type of the new node is jointly decided. based on the formalism, our proposed model is able to iterate between finding the relevant part in the query and reading the partially constructed scene graph, inferring more accurate and harmonious expansion decisions progressively. experiments on three sgm benchmarks demonstrate the effectiveness of the proposed approach, which is able to outperform previous stateof-the-art models by large margins. to test the ability of a model under a complex scenario, we further construct a more challenging dataset from the remote sensing domain @xcite , which has much more modification operations based on the more complicated queries compared with the existing scene graph modification datasets. our key contributions are summarized as follows: ## incremental structure expanding in scene graph modification, a node or multiple nodes can be inserted to, deleted from or replaced with other nodes in the scene graph. @xcite defined the scene graph modification task as a conditional graph generation problem. formally, given the source scene graph g s and the natural language query q, the target scene graph g t is generated by maximizing the conditional probability p(g t |g s , q). instead of generating the entire target graph g t , we frame the task as an incremental structure expanding, which extends the source scene graph g s one node at a time, as well as the edges associated with the node. such a formulation does not require the model to rebuild the unmodified structure of the source scene graph. under this formulation, we first define two basic operations: insert and delete. scene graph modification can be viewed as combining and applying these two operations multiple times. formally, given the query q, a sequence of n operations a 1 , a 2 , ..., a n are selected from a set of graph modification operations @xmath0, delete}. after applying the operations to the source scene graph g s , the target scene graph g t is derived. each operation is defined as: inspired by incremental parsing @xcite @xcite @xcite , we design a data structure called extended graph g i , which can be used to model insert and delete under the graph expansion setting. as shown in figure 2 (a) , the extended graph g t is identical with the target graph g t after applying insert. as for delete, we introduce a dummy node "delete", which is attached to the node in the source graph g s that should be removed. for example, the dummy node "delete" is attached to the node "blue" in g t . in the postprocessing stage, nodes attached with the dummy node "delete" will be removed. using this formulation, we are able to model scene graph modification by incrementally expanding the source graph g s to the extended graph g i , which can be converted to the target graph g t without any losses. if the modification requires multiple operations, there will exist multiple node orderings. take node substitution as an example, replacing a node o i with o j in g s can be viewed as delete the node o i first, then insert the node o j , or vice versa. in practice, we impose that the delete operation always comes before insert, then the breadthfirst search is used to define a deterministic node ordering. ## model architecture in this section, we will present the model based on the incremental structure expanding formulation. figure 3 gives an overview of the proposed model, which consists of five components including query encoder, graph encoder, feature fusion, edge decoder and node decoder. query encoder this module is used to encode the query q by generating the representation of each token of it. graph encoder this module is used to encode the graph by generating the representation of each node of it. note that the representations of the graph are constructed incrementally during the expanding progresses based on the updated graph of the last time step. the graph is the source graph g s at the first timestep. feature fusion this module aims to combine the representations from query and graph encoder, then served as a writable memory, which is updated based on the information from edge and node decoder during the incremental expansion. edge decoder this module is used to predict the edges between the newly generated node and existing nodes of the graph, then update the memory of the feature fusion module with edge information. node decoder this module is used to generate a new node of the graph, then update the memory of the feature fusion module with node information. ## dataset construction existing sgm datasets are synthetically constructed based on scene graphs from mscoco @xcite and gcc @xcite , and via crowd sourcing. to construct scene graphs, @xcite used an in-house scene graph parser to parse a random subset of mscoco description data and gcc captions, thus the constructed scene graph is relatively simple. in ## conclusion in this paper, we designed a novel formulation for scene graph modification, which allows us to incrementally expand the source scene graph instead of rebuilding the entire graph. based on the formalism, we further propose a model that is able to leverage the mutual causalities between node prediction and edge prediction. experiments on three sgm benchmarks demonstrate the effectiveness. to test our model under a complex scenario, we constructed a more challenging dataset from the remote sensing domain, which has more modification operations based on the more complicated queries compared with existing sgm datasets. for future work, we would like to explore how to integrate the model into the text-based image retrieval task.