Extend, don’t rebuild: Phrasing conditional graph modification as autoregressive sequence labelling (2021)

Abstract: Deriving and modifying graphs from natural language text has become a versatile basis technology for information extraction with applications in many subfields, such as semantic parsing or knowledge graph construction. A recent work used this technique for modifying scene graphs (He et al. 2020), by first encoding the original graph and then generating the modified one based on this encoding. In this work, we show that we can considerably increase performance on this problem by phrasing it as graph extension instead of graph generation. We propose the first model for the resulting graph extension problem based on autoregressive sequence labelling. On three scene graph modification data sets, this formulation leads to improvements in accuracy over the state-of-the-art between 13 and 24 percentage points. Furthermore, we introduce a novel data set from the biomedical domain which has much larger linguistic variability and more complex graphs than the scene graph modification data sets. For this data set, the state-of-the art fails to generalize, while our model can produce meaningful predictions.

## introduction generating or modifying graphs based on natural language texts is a versatile technique that has applications in different subfields of natural language processing (nlp) such as dependency parsing @xcite or semantic parsing @xcite . however, while these tasks can all be viewed as instantiations of conditional graph generation, they have been traditionally addressed as distinct tasks with different data sets, models and evaluation settings. contrary to that, we are interested in studying the general task of generating or modifying graphs based on textual input. specifically, we focus on the recently introduced task of conditional graph modification, in which a model is given a graph which it should modify according to natural language instructions @xcite . their proposed method first embeds both the graph and the instructions with a joint encoder into an embedding h and then rebuilds the graph using a separate generative model for graphs @xcite ) conditioned on h. while this approach achieves state-of-the-art results for the scene graph modification (sgm) data sets, we identified two shortcomings of this approach: (i) the model has to newly generate also the parts of the input graph that actually should be left unmodified and (ii) the model uses a separate graph encoder in the generative decoder model, which does not share knowledge with the encoder. we propose an alternative formulation of this problem in which we model the modification as a graph extension instead of graph generation. to this end, we introduce the two special node labels add and del which allow us to model node insertions, deletions and edge modifications in the graph extension setting. we develop a model for this novel graph extension problem that autoregressively solves a sequence labelling task for each node that is added to the graph. this formulation addresses both shortcomings of the model of @xcite . first, it precisely extends the graph without the need for rebuilding the unmodified parts. second, it models the graph as text which allows to encode the input text, the original graph and the extension with the same encoder and enables the straightforward integration of pretrained language models such as bert @xcite . our proposed model outperforms the state-of-the-art for the three data sets published by @xcite by a large margin, with improvements between 13 and 26 percentage points (pp). to test the limits of our approach, we furthermore present a new, more challenging graph modification task in which biomedical event graphs have to be modified based on scientific texts. to this end, we transform data from an existing biomedical event extraction task @xcite to a graph modification data set. compared to the sgm data sets, the resulting data set displays much larger linguistic variation in the instruction texts and more complex graph structures. our experiments show that the state-of-the-art fails to generalize on this data set, while our model is able to produce meaningful predictions. we analyze our model via a detailed ablation study and analyze the errors with respect to the input complexity, which allows us to precisely explain the improvements over stateof-the-art and suggest routes for even better future models. to encourage further research on the challenging task of graph modification, we implement the models and data sets in a modular fashion and make the code available under an open-source license foot_0 . ## related work generating graphs from natural language texts is a central problem in many subfields of nlp. many classical problems in nlp such as dependency parsing @xcite or relation classification @xcite ) are text-tograph problems, but with highly restricted graph structures (e.g. nodes can be only words or named entities respectively). the methods developed for these tasks are typically tailored to these structures and cannot be used for other types of graphs. in contrast, our proposed method can handle arbitrary directed acyclic graphs (dags). there is also significant interest in developing methods that jointly embed graphs and text to exploit graph-based information in nlp, especially for question answering based on knowledge bases @xcite . however, these usually treat the graph as a static source of information and cannot be used for generating or extending graphs. a task closer to our work in this regard is cross-framework meaning representation parsing @xcite ) (mrp). in this task, systems are required to parse text into a general graph-based format in which nodes are not necessarily anchored in the text. the major difference between mrp and our graph modification setting is that in mrp the models always generate the full graph from scratch, while our method modifies an already provided graph. there is strong interest in graph generation also outside the nlp community, e.g. for modelling arbitrary distributions of graphs @xcite or for generating novel protein structures @xcite . however, these methods neither do graph generation conditioned on textual input nor support the modification of partial graphs. to the best of our knowledge, the only model that was explicitly developed for modifying arbitrary graphs based on natural language instructions is the model by @xcite . it uses a transformer @xcite to jointly embed text and graph, modelling the graph structure by restricting attention only to neighbouring nodes and by adding edge label embeddings onto the node embeddings. based on this joint embedding, the modified graph is generated by a separate decoder based on the graphrnn architecture @xcite . while this architecture allows to model graph modification as graph generation, it also requires the model to generate the unmodified parts of the graph again which leaves more room for errors, whereas we only extend the graph leaving the unmodified parts untouched. furthermore, this formulation uses two separate graph encoders; the transformer for encoding the original graph and the graphrnn for encoding the partially generated graph. in contrast, our proposed method uses the same encoder for encoding the given graph and its extensions, allowing for more parameter sharing and thus for potentially better graph representations. our simpler architecture makes the integration of bert-style pretrained language models @xcite straightforward, however this only partly explains the observed gains over @xcite (see section 5.3). ## methods the task of graph modification is to modify a graph g into a graph g according to natural language instructions t. to this end, let @xmath0, e) be a dag consisting of nodes n and edges e ⊆ n × n , along with node labels l @xmath1. let g be defined analogously. we develop a model to estimate p(g | t, g). here, we first present our approach for the problem of graph extension, i.e., the case n ⊆ n and e ⊆ e . then, we show how general graph modification can be reduced to this case. to this end, we identify three ways in which a graph can be modified: a node can be added, a node can be removed or the edges of an existing node can be modified. we show how we can model all three cases by introducing the two special node labels add and del which can be used to model node insertions and deletions in a graph extension setting. both, add and del identify the argument that should be added or deleted via a special theme edge. ## experimental setup we evaluate our model on three data sets for sgm and a novel biomedical event graph completion data set. ## conclusion we have developed a novel formulation of the conditional graph modification problem as conditional graph extension. this allows us to only generate the modified parts of the graph as opposed to rebuilding the full graph. additionally, our model uses only one encoder for both graph and text allowing for maximum parameter sharing and can make use of pretrained language models such as bert. on three sgm data sets and on a newly introduced biomedical event graph completion data the proposed model outperforms the state-of-theart. our error analysis highlights that performance degrades for larger input graphs. thus, we plan to evaluate whether usage of more sophisticated graph neural networks @xcite would improve results for these cases. we are also interested to apply our conditional graph modification framework to other tasks such as graph-based semantic parsing and knowledge graph completion, as this might yield a unified framework for many standard nlp tasks.