Dependency Parsing with Dilated Iterated Graph CNNs

Emma Strubell, Andrew McCallum

Abstract

Dependency parses are an effective way to inject linguistic knowledge into many downstream tasks, and many practitioners wish to efficiently parse sentences at scale. Recent advances in GPU hardware have enabled neural networks to achieve significant gains over the previous best models, these models still fail to leverage GPUs' capability for massive parallelism due to their requirement of sequential processing of the sentence. In response, we propose Dilated Iterated Graph Convolutional Neural Networks (DIG-CNNs) for graph-based dependency parsing, a graph convolutional architecture that allows for efficient end-to-end GPU parsing. In experiments on the English Penn TreeBank benchmark, we show that DIG-CNNs perform on par with some of the best neural network parsers.

The Bottleneck of Sequential Parsing

Dependency parsing—the task of identifying grammatical relationships between words—is a cornerstone of natural language processing. Currently, state-of-the-art parsers rely heavily on Recurrent Neural Networks (RNNs), specifically Bidirectional LSTMs. However, LSTMs are inherently sequential; the state for a specific word cannot be computed until all preceding words have been processed. This creates a significant bottleneck on modern GPUs, which are designed for massive parallelization. While graph-based parsers offer some parallelism via attention mechanisms, they often still utilize sequential backbones, limiting their throughput.

Dilated Iterated Graph CNNs (DIG-CNNs)

To address these efficiency issues, we propose Dilated Iterated Graph CNNs (DIG-CNNs). This architecture treats dependency parsing as a 2D image processing task rather than a 1D sequence task.

2D Representation and Convolutions

Instead of processing text as a string, DIG-CNNs represent a sentence of length $T$ as a $T \times T$ adjacency matrix. Each cell $(i, j)$ in this grid represents a potential dependency edge between word $i$ (the head) and word $j$ (the dependent). By treating the parse as a 2D grid, we can apply standard convolutional filters to capture spatial relationships between words.

Visualization of dependency relations as a 2D grid where rows represent dependents and columns represent heads.

Dilation and Iteration

To capture long-range dependencies without a massive increase in parameters, we employ dilated convolutions. These skip cells at regular intervals, effectively expanding the model's receptive field. Furthermore, we use iterated blocks, where a stack of convolutional layers is applied repeatedly. This iterative approach allows the model to refine its predictions over time, acting as an iterative solver that corrects grammatical inconsistencies in successive passes.

Experimental Evaluation

We evaluated the DIG-CNN on the English Penn Treebank (PTB) benchmark, using standard splits (Sections 2–21 for training, 22 for development, and 23 for testing). The constituency trees were converted to dependencies using the Stanford Dependency framework (v3.5).

Results

The DIG-CNN demonstrates competitive performance compared to established neural models. When combined with the Eisner algorithm for decoding, the model achieves an Unlabeled Attachment Score (UAS) of 94.03 and a Labeled Attachment Score (LAS) of 92.00.

Comparison of UAS and LAS scores across different dependency parsing models on the PTB dataset.

While the DIG-CNN slightly trails the current state-of-the-art biaffine parser by Dozat and Manning (2017), it outperforms several earlier high-performance neural architectures. The performance gap is largely attributed to the receptive field; in the tested configuration, the model only "saw" a window of 9 tokens, whereas LSTMs maintain a global view of the entire sentence.

Conclusion and Future Work

DIG-CNNs offer a promising path toward highly parallelizable dependency parsing by leveraging 2D convolutions. By treating the parse tree as an adjacency matrix, the architecture can fully exploit GPU hardware. Future research will focus on expanding the receptive field through deeper architectures or larger dilation rates and conducting rigorous wall-clock time benchmarks to quantify the speed advantages over optimized LSTM implementations.

Summary updated

Abstract

Dependency parses are an effective way to inject linguistic knowledge into many downstream tasks, and many practitioners wish to efficiently parse sentences at scale. Recent advances in GPU hardware have enabled neural networks to achieve significant gains over the previous best models, these models still fail to leverage GPUs' capability for massive parallelism due to their requirement of sequential processing of the sentence. In response, we propose Dilated Iterated Graph Convolutional Neural Networks (DIG-CNNs) for graph-based dependency parsing, a graph convolutional architecture that allows for efficient end-to-end GPU parsing. In experiments on the English Penn TreeBank benchmark, we show that DIG-CNNs perform on par with some of the best neural network parsers.
BibTeX
@inproceedings{strubell2017dependency,
  author = {Emma Strubell and Andrew McCallum},
  title = {{Dependency Parsing with Dilated Iterated Graph CNNs}},
  booktitle = {SPNLP @ EMNLP},
  year = {2017},
  doi = {10.18653/v1/w17-4301},
}
Figure