HySPA: Hybrid Span Generation for Scalable Text-to-Graph Extraction

Findings of the Association for Computational Linguistics: ACL-IJCNLP 2021, pages 4066–4078 August 1–6, 2021. ©2021 Association for Computational Linguistics 4066 HySPA: Hybrid Span Generation for Scalable Text-to-Graph Extraction Liliang Ren, Chenkai Sun, Heng Ji, Julia Hockenmaier University of Illinois, Urbana Champaign Department of Computer Science {liliang3,chenkai5,hengji,juliahmr}@illinois.edu Abstract Text-to-Graph extraction aims to automati- cally extract information graphs consisting of mentions and types from natural language texts. Existing approaches, such as table filling and pairwise scoring, have shown impressive performance on various information extraction tasks, but they are difficult to scale to datasets with longer input texts because of their second- order space/time complexities with respect to the input length. In this work, we propose a Hybrid SPan GenerAtor (HySPA) that in- vertibly maps the information graph to an al- ternating sequence of nodes and edge types, and directly generates such sequences via a hybrid span decoder which can decode both the spans and the types recurrently in linear time and space complexities. Extensive exper- iments on the ACE05 dataset show that our ap- proach also significantly outperforms state-of- the-art on the joint entity and relation extrac- tion task.1 1 Introduction Information Extraction (IE) can be viewed as a Text-to-Graph extraction task that aims to extract an information graph (Li et al., 2014; Shi et al., 2017) consisting of mentions and types from un- structured texts, where the nodes of the graph are mentions or entity types and the edges are relation types that indicate the relations between the nodes. A typical approach towards graph extraction is to break the extraction process into sub-tasks, such as Named Entity Recognition (NER) (Florian et al., 2006, 2010) and Relation Extraction (RE) (Sun et al., 2011; Jiang and Zhai, 2007), and either per- form them separately (Chan and Roth, 2011) or jointly (Li and Ji, 2014; Eberts and Ulges, 2019). Recent joint IE models (Wadden et al., 2019; Wang and Lu, 2020; Lin et al., 2020) have shown 1Our code is publicly available at https://github. com/renll/HySPA Figure 1: We represent directed multigraphs as alter- nating sequences of nodes (blue) and edges (orange). Here, the graph is traversed by Breadth First Search (BFS) with an ascending ordering of nodes and edge types. “[s]” or [SEP] is a virtual edge type, represent- ing the end of each BFS level. impressive performance on various IE tasks, since they can mitigate error propagation and leverage inter-dependencies between the tasks. Previous work often uses pairwise scoring techniques to iden- tify relation types between entities. However, this approach is computationally inefficient because it needs to enumerate all possible entity pairs in a document, and the relation type is a null value for most of the cases due to the sparsity of relations between entities. Also, pairwise scoring techniques evaluate each relation type independently and thus fail to capture interrelations between relation types for different pairs of mentions. Another approach is to treat the joint information extraction task as a table filling problem (Zhang et al., 2017; Wang and Lu, 2020), and …

Content truncated to 500 words