Graph-based Dependency Parsing with Graph Neural Networks

Tao Ji, Yuanbin Wu, Man LanACL 2019 · OpenReview

Abstract: Tao Ji, Yuanbin Wu, Man Lan. Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics.

2019.

Introduction

Dependency parsing is a fundamental task in natural language processing, aimed at identifying the grammatical structure of a sentence through head-dependent relationships. While traditional graph-based parsers have excelled at capturing first-order features (single edges), incorporating high-order linguistic structures—such as "grandparents" or "siblings"—remains a significant challenge. Previous attempts to integrate these features often relied on "hard" feature extraction from intermediate parse trees, a process highly susceptible to error propagation.

This paper introduces a novel approach that leverages Graph Neural Networks (GNNs) to capture these complex, high-order relationships directly within word representations. By performing "soft" updates over a weighted complete graph, the proposed model avoids the pitfalls of discrete intermediate parses and achieves state-of-the-art results without the need for external pre-trained language models.

Proposed Architecture

The core of the system is an extension of the standard Biaffine Parser. The authors insert a series of GNN layers between a recurrent encoder (biLSTM) and the final decoder.

The proposed architecture integrates GNN layers between the RNN encoder and the decoder, utilizing layer-wise supervision.

Soft Graph Updates

Unlike traditional methods that select a single best tree to extract features, the GNN operates on a complete weighted graph. In this setup, every word is connected to every other word, with edge weights representing the current probability of a dependency relationship. This allows the model to maintain a "soft" distribution of possible structures during the representation learning phase.

Stacked GNN Layers and Specialized Protocols

By stacking multiple GNN layers, the model naturally captures increasingly complex structural context. A single layer captures immediate neighbors, while a second layer effectively "sees" neighbors of neighbors, corresponding to linguistic grandparents and siblings.

To handle the distinct roles of "head" and "dependent" in a sentence, the authors developed specialized update rules. These rules maintain separate vectors for a word depending on its role, allowing the GNN to specifically encode various high-order relationships. Furthermore, layer-wise supervision is employed; a loss function is applied at every GNN layer to ensure the learned weights approximate the gold-standard parse tree.

Experimental Results

The model was evaluated on the English Penn Treebank (PTB 3.0) and Universal Dependencies (UD 2.2) across 12 languages.

The proposed model achieves state-of-the-art performance on the Penn Treebank compared to both transition-based and graph-based alternatives.

On the PTB dataset, the model achieved a 96.0% UAS (Unlabeled Attachment Score) and 94.3% LAS (Labeled Attachment Score), setting a new benchmark for systems not utilizing large-scale pre-trained transformers like BERT.

Key Insights

  • Optimal Depth: Empirical results suggest that a 2-layer GNN provides the best balance of performance and efficiency. Linguistically, two hops are sufficient to cover the most critical high-order features.
  • Global Evidence: The use of a weighted graph allows the decoder to make final decisions based on global evidence, significantly improving performance on long-range dependencies and complex sentences.
  • Efficiency: The addition of GNN layers is computationally efficient, resulting in only a 2.1% decrease in prediction speed while maintaining a high throughput of over 400 sentences per second.

Conclusion

By integrating GNNs into the dependency parsing pipeline, this work demonstrates a robust method for capturing high-order linguistic features without the risks of error propagation inherent in "hard" feature extraction. The model's ability to leverage global structural context leads to significant gains in parsing accuracy, particularly for long and complex sentences, while remaining highly efficient for practical applications. Future work may explore more sophisticated graph topologies and the interaction between GNN-based representations and transformer-based models.

Summary updated

BibTeX
@inproceedings{ji2019graph,
  author = {Tao Ji and Yuanbin Wu and Man Lan},
  title = {{Graph-based Dependency Parsing with Graph Neural Networks}},
  booktitle = {Annual Meeting of the Association for Computational Linguistics},
  year = {2019},
  url = {https://openreview.net/forum?id=r34-lT8CAGc},
}
Figure