Maximal Clique Based Non-Autoregressive Open Information Extraction (2021)

Abstract: Open Information Extraction (OpenIE) aims to discover textual facts from a given sentence. In essence, the facts contained in plain text are unordered. However, the popular OpenIE systems usually output facts sequentially in the way of predicting the next fact conditioned on the previous decoded ones, which enforce an unnecessary order on the facts and involve the error accumulation between autoregressive steps. To break this bottleneck, we propose MacroIE, a novel non-autoregressive framework for OpenIE. MacroIE firstly constructs a fact graph based on the table filling scheme, in which each node denotes a fact element, and an edge links two nodes that belong to the same fact. Then OpenIE can be reformulated as a non-parametric process of finding maximal cliques from the graph. It directly outputs the final set of facts in one go, thus getting rid of the burden of predicting fact order, as well as the error propagation between facts. Experiments conducted on two benchmark datasets show that our proposed model significantly outperforms current state-of-the-art methods, beats the previous systems by as much as 5.7 absolute gain in F1 score.

## introduction open information extraction (openie) aims to convert natural text to semi-structured knowledge, by mining facts in the form of n-ary tuples @xmath0, predicate, object 1 , • • • , object m ), composed of a single subject and predicate as well as m objects. while traditional ie systems require people to pre-specify the set of interested relations and provide per-relation training data, openie is built on the principles of ontology-free @xcite , making it possible to adapt to various domains and applications, such as extending knowledge bases @xcite , and facilitating question answering systems @xcite . starting from rule-based systems to neural networks, openie has attracted increasing attention in recent years but remains challenging @xcite , due to the intrinsic difficulty in identifying complicated facts, including: (1) overlapping, one fact element (either subject, predicate, or object) may belong to multiple facts in a sentence. for example, in figure 1 , the entity pairs of two facts are identical but the predicates are different; (2) discontinuous, one fact element can consist of spans that are separated by intervals, as the predicate of the first fact in figure 1 comprising two spans premier and of ; (3) nested, one fact element could contain other elements or share words with other elements. we can see that the two predicates in figure 1 containing the same word of. recent studies on systematically handling these challenges have two major research lines: tagging, and generation. tagging-based system @xcite annotates m different tag sequences corresponding to m facts in the input sentence. to avoid redundant extraction, the labels of one tag sequence are passed to the next iteration to decode another sequence. generation-based system @xcite directly decodes the facts as a sequential output by generating one word at a time through the seq2seq architecture. either tagging or generation paradigm predicts facts auto-regressively, which means the current fact prediction relies on the previous output. despite their success, all of these methods are still limited by the autoregressive prediction process. the reasons are as follows: they enforce an unnecessary order on the facts dur-ing the training phase, while other fact orders are also correct. in essence, the facts contained in a sentence have no intrinsic order @xcite . moreover, the models predict conditioned on the previously generated ones, thus a skewed prediction will be inherited and magnified in the later steps @xcite . as the number of steps grows, i.e., multi-fact extraction, the errors accumulate and may decrease the performance. in this paper, we break the autoregressive factorization by presenting a novel view of openie as a maximal clique discovery task. in graph theory, cliques refer to subgraphs in a graph such that nodes in each subgraph are pairwise adjacent. moreover, a maximal clique is a clique that cannot be extended by including one more adjacent node. that means the nodes in a maximal clique have close connections with each other, which is similar to the relationship between elements in a fact. armed with this insight, we reach an intuition that openie can be cast as finding the maximal cliques from a fact graph (see also figure 2 ), in which each node denotes a span (a continuous fact element on its own, or a part of discontinuous elements), and an edge links two nodes belonging to the same fact. we implement the above idea in maximal clique discovery based open information extractor (macroie), a non-autoregressive end-to-end ope-nie framework. it constructs the fact graph with two independent steps: node extraction and edge prediction, and tackles them together with a unified table filling scheme to accurately recognize the discontinuous or nested fact elements. then an accompanied decoding algorithm is developed to recover desired facts from the fact graph, which has the elegance to extract overlapping facts by design. owing to the novel task formulation, macroie can predict all facts at once, without having to cope with the fact order and the error propagation between facts, thus overcoming the aforementioned limitations of autoregressive methods. we conduct experiments on two realistic ope-nie benchmarks in english and chinese, respectively. experimental results show that the proposed macroie model significantly outperforms existing best-performing methods, with substantial gains of up to 5.7% absolute percentage points in f1 score, establishing a new state of the art for this task. furthermore, detailed analysis shows that macroie gains consistent improvement in complicated fact extraction and multiple fact extraction. john is the premier and first minister of british columbia john premier of first minister of british columbia subject object predicate john, premier of, british columbia john, first minister of, british columbia fact graph graph construction maximal clique discovery 2 methodology ## related work open information extraction has attracted much attention from researchers during the past decade @xcite . @xcite are the first to introduce the open information extraction (openie) paradigm, and propose tex-trunner, the first highly scalable model for the task. in the following, various openie systems ap-plying costly hand-crafted rules or self-supervised learning paradigm based on linguistic patterns such as part-of-speech tags and syntactic features have been proposed over the years @xcite @xcite @xcite @xcite @xcite . they strongly rely on external nlp tools. thus, their performance depends on the quality of the features obtained from these nlp tools. however, these features are not always accurate for various domains and contexts @xcite . recently, openie has achieved great advances with the help of supervised neural networks to bypass the handcrafted patterns and alleviate error propagation. there are two main paradigms in the relevant research. the first one, called taggingbased model @xcite @xcite , labels each word in the sentence as either subject, predicate, object, or none for extraction. to identify complicated facts containing overlapping, discontinuous, or nested elements, the recent tagging-based model @xcite generates a list of tag sequences for one sentence where each sequence corresponding to one extracted fact. the tag sequences are labeled one by one iteratively, e.g., the predicted labels of one tag sequence are passed to the next iteration to fill up another sequence to avoid redundant extraction. generating-based methods belong to another major paradigm. these methods cast openie as a sequence-to-sequence generation problem, where the input sequence is the sentence and the output sequence is the desired facts @xcite @xcite . in principle, generation is powerful because it is able to assign one word to multiple facts and change word order, thus the complicated fact extraction problem can be solved in nature. generally speaking, the best-performing ope-nie models at present, whether based on tagging or generation, all pre-define a sequential order for the target facts and then make prediction according to the order autoregressively, which means the current fact prediction relies on the previous output. as discussed in the introduction, this design inevitably has to sort the target facts in a certain order during the training phase, while the facts contained in a sentence have no intrinsic order in essence. what more serious is that a mispredicted fact will directly affect the extraction of all the following facts, resulting in cascading error. in this paper, for the first time, we break the sequential extraction process and propose a one-stage openie model, which is able to extract all kinds of facts without relying on the dependency among facts, realizing non-autoregressive open information extraction. maximal clique discovery is to find the clique with most nodes in a given graph @xcite . this problem has been extensively studied in graph theory and directly applied in various fields, such as community search in social networks @xcite , team formation in expert networks @xcite , anomaly detection in complex networks @xcite , and discontinuous named entity recognition @xcite . motivated by the finding that all the elements in a fact of openie have pairwise strong connections, which is similar to the property of maximal clique in the graph, we extend the concept of maximal clique discovery to openie, and successfully implement task transformation. our results show that openie can be cleverly cast as a maximal clique discovery problem on a fact graph. ## conclusion in this paper, we present a non-autoregressive ope-nie system macroie. it predicts the fact set at once based on a novel view of openie as a maximal clique discovery problem, thus be relieved of predicting the extraction order of multiple facts in previous autoregressive openie models. experimental results show that our proposed networks outperform state-of-the-art baselines in all of the metrics on two public datasets. further analysis demonstrates the ability of our model in handling complicated and multiple fact extractions. openie is one of the most complex tasks in information extraction (ie). in the future, we would like to explore similar maximal clique based task formulation in other ie tasks, such as event and aspect extraction.