A Semi-Autoregressive Graph Generative Model for Dependency Graph Parsing (2023)

Abstract: Recent years have witnessed the impressive progress in Neural Dependency Parsing. According to the different factorization approaches to the graph joint probabilities, existing parsers can be roughly divided into autoregressive and non-autoregressive patterns. The former means that the graph should be factorized into multiple sequentially dependent components, then it can be built up component by component. And the latter assumes these components to be independent so that they can be outputted in a one-shot manner. However, when treating the directed edge as an explicit dependency relationship, we discover that there is a mixture of independent and interdependent components in the dependency graph, signifying that both aforementioned models fail to precisely capture the explicit dependencies among nodes and edges. Based on this property, we design a Semi-Autoregressive Dependency Parser to generate dependency graphs via adding node groups and edge groups autoregressively while pouring out all group elements in parallel. The model gains a trade-off between non-autoregression and autoregression, which respectively suffer from the lack of target inter-dependencies and the uncertainty of graph generation orders. The experiments show the proposed parser outperforms strong baselines on Enhanced Universal Dependencies of multiple languages, especially achieving 4% average promotion at graph-level accuracy. Also, the performances of model variations show the importance of specific parts.

## introduction dependency graph in neural parsing is a directed graph representing semantic dependencies between words, with a transitive relation traveling from the rooted node to all words in the sentence phase by phase. as such, transition-based parsing seems to be a natural choice, as it builds up the parsing graph sequentially so that the dependency relationships can be captured. however, graph-based parsing dominates recent competitions on parsing technologies including iwpt 2020 and 2021 @xcite , even if using a simple biaffine attention @xcite only to predict the whole graph at once. to explore a more effective parsing method that can represent these dependency relationships in a rigorous manner, we define and construct topological hierarchies for dependency graphs based on the explicit dependencies carried by them. according to the characteristics of topological hierarchies, we proposes a semi-autoregressive dependency graph parser (sager) -a novel graph-based parsing fashion via the semi-autoregressive graph generation. generally, autoregressive graph generation indicates that the model dynamically adds nodes and edges based on the generated sub-graph structure until reaching the complete graph. it brings a challenge to determine the generation order of graphic data, because there is no conventional reading order like text data @xcite . although the dependency graphs stipulate the strict sequential dependencies by directed edges, there is a lack of such topological orders between sibling nodes. for instance, node b in figure 1 .a depends on the node a because there is an explicit edge pointing from a to b. however, it is hard to decide the dependency relationship between node d and node e as they are not linked neither directly nor indirectly. previous works on directed graph generation solve the problem surfacely. @xcite ) sort these sibling nodes randomly at the early stage of training and then change them to a deterministic order (e.g., relation-frequency) at later training steps. some other works do the sorting by referring to the orders of the known sequences like word order or alphanumerical order @xcite . such imposed orders would bring more exposure bias @xcite to teacher forcing training. more specifically, these sibling nodes are essentially orderless and non-interlogical. they cannot form stationary and logical patterns like words in sentences. as a result, it is hard for the sibling nodes to be generated in the same order as in the training, causing learned knowledge invalid and later predictions misled. the aforementioned random ordering seems to alleviate the problem to some extent, but it destabilizes and complicates the training process and generally results in inferior models. instead of imposing orders on these sibling nodes, we assume them (including their incoming edges) to be conditionally independent to construct topological hierarchies as the generation orders. as shown in figure 1 .b, we divide nodes into several hierarchies according to their furthest distances from the root node. we can see that there are no explicit dependency relationships between nodes in the same hierarchy. besides, nodes in the later hierarchies only depends on those in the previous hierarchies, forming a natural generation sequence. for a directed acyclic graph (dag), it at least has one topological ordering but only has one topological hierarchy. at each generation step, we firstly predict all new nodes in parallel and then calculate their incoming edges by the biaffine attention @xcite . in a word, our model autoregressively adds node groups and edge groups but non-autoregressively generates elements in these groups. see figure 1 .c for our semi-autoregressive generation process. another challenge lies at the probable edge sparsity problem when representing sub-graph structures. sparse graph representation models like gcn @xcite heavily rely on the given adjacency to capture context information. that means it may fail to represent historical information completely and efficiently when predicted edges make mistakes. an extreme situation of edge sparsity is that the new nodes have no incoming edges predicted so that the model can only represent its node features rather than the sub-graph structure. to enhance the robustness of the generator, we adopt the dense structure of transformer @xcite . in our graph transformer, there are implicit edges linking from the nodes in the previous and current hierarchies to the new node. then, the predicted explicit edges serve as the bias to adjust the attention distribution over the implicit edges so that the model can adaptively select useful structural information. overall, this paper proposes a novel direction -semi-autoregression to deal with dependency parsing problems, distinguished with autoregression and non-autoregression (detailed definitions about them are available in § 2). with the dependencies denoted as the directed edges, the semiautoregressive pattern unfolds graphs in the order of topological hierarchies, which strictly follows the explicit dependency relationships defined in dependency graphs. our model strikes a reasonable balance, resulting in it neither ignoring inter-output dependencies like non-autoregressive models, nor suffering from severe exposure bias in generation orders like autoregressive models on the experimental side, we evaluate sager on enhanced universal dependencies (eud) which are non-tree dependency graphs. in addition to the official evaluation metric enhanced label attachment scores (elas), we design a graph-level matching score (gms) to assess the probability of returning an completely correct graph. our model outperforms other baselines in both metrics especially gms, showing that it is good at overcoming some intractable prediction errors. finally, we introduce multiple model variations to investigate the effect of different model components and show that our model is well-designed, especially the parts of dis-carding imposed orders and adding implicit edges. non-autoregressive parser. in contrast, nonautoregression implies that all components factorized from the graph are independent, so their probabilities do not affect each other and can be obtained in parallel at any time. a representative non-autoregressive parser is deep biaffine attention (biatt) @xcite which assuming all edges are independent. for the treestructure dependency graphs, it is often followed by a searching algorithm for the maximum spanning tree (mst). some heuristic algorithms @xcite construct the mst step by step, which yet does not mean they are in the autoregressive manner because all edge probabilities are predicted at once and fixed before the searching. as to the higher-order graph-based parsers, @xcite incorporates the secondorder knowledge into the word representations and still uses the biatt as the final parser. @xcite ; @xcite decompose the graph into components of different second-order parts. different from biatt that each component is an edge, here some components consists of two edges whose joint probabilities can be calculated as a whole by a trilinear function. they still belong to non-autoregressive parsers because their components are independent of each other and disable to be subdivided. explicit and implicit edge. we define two kinds of edges, namely explicit edges and implicit edges. the former is what we need to really predict. let n i be the explicit first-order neighbours of the node t) and d i be the implicit neighbours, and t) according to the definition of topological hierarchy. they have uni-directional edges pointing to the node v i with arc labels, and these edge can be found in e (t) . on the other hand, nodes in d i should not have pointed to v i , but our model does so because we expect nodes to learn structural information adaptively. it should be mentioned that nodes in the same component or hierarchy also have implicit edges linking to each other, i.e., v (t) ⊆ d i . ffn message passing + + + + + + + + + + + + + + + + + + ffn message passing i ffn message passing p i i a e c di g w d e beddi g m de o e ici edge i ici edge heads deps n edge roo figure 2: semi-autoregressive generation process and graph transformer. head and dependent representation. we define two representations of the same node with different roles, namely the head representation and the dependent representation. each generated node will first be used as a dependent node to calculate its incoming arcs, and then as a head node until the end of generation. we define the head vector of a node training objective. the objective is to maximize the graph joint probability j : it indicates that we autoregressively generate the new node group v (t) and the edge group e (t) based on groups generated previously and the elements in the same group are independent. ## conclusion and limitation this paper explores a semi-autoregressive dependency graph parser (sager) that learns the explicit dependencies in dependency graphs. this generation pattern captures the edge dependencies while reducing exposure bias, resulting in a more effective parser and two insights about graph generation, namely the ordering uncertainty and edge sparsity. we believe that the proposed algorithm can be applied in other language parsing problems such as oia (open information annotation) @xcite and graph generation problems @xcite . the limitations of our work are inference speed and decoding strategy. the efficiency of semiautoregressive inference is lower than that of nonautoregressive algorithms, so currently it cannot be applied to scenarios with high frequency requests. furthermore, this paper only introduces greedy search as a decoding strategy. overcoming the challenge of introducing many complex decoding strategies such as beam/tree search @xcite belongs to our future work.