Dependency Parsing with Dilated Iterated Graph CNNs

Emma Strubell, Andrew McCallum

Introduction

Dependency parsing—the task of identifying grammatical relationships between words—is a cornerstone of natural language processing. While deep learning has significantly advanced the state-of-the-art, most high-performing models rely on sequential architectures like LSTMs or transition-based systems. These models process tokens or actions one by one, creating a computational bottleneck that fails to fully leverage the parallel processing capabilities of modern GPUs.

This paper introduces Dilated Iterated Graph CNNs (DIG-CNNs), an architecture designed to be "parallel-first." By treating dependency parsing as a 2D image-processing task over a sentence's adjacency matrix, the authors enable efficient, end-to-end parallel parsing that remains competitive with top-tier sequential models.

Methodology

The core innovation of DIG-CNNs lies in the shift from 1D sequential processing to a 2D grid representation.

2D Representation and Convolutions

Instead of a 1D sequence, the sentence is represented as a $T \times T$ grid, where $T$ is the number of tokens. Each cell $(i, j)$ represents a potential dependency edge between a "head" word and a "dependent" word. This allows the model to treat the adjacency matrix like an image, applying convolutional filters to identify patterns and refine the entire structure simultaneously.

2D adjacency matrix representation of a sentence where cells represent potential head-dependent relationships.

To capture long-range dependencies without a massive parameter overhead, the model employs dilated convolutions. These filters skip over tokens at set intervals, expanding the receptive field. Furthermore, the architecture uses Iterated Blocks, applying the same stack of convolutional layers multiple times to refine predictions iteratively. This process is guided by a parallel objective function that rewards accuracy after every block, mitigating vanishing gradient issues.

Experimental Setup

The model was evaluated on the English Penn TreeBank (PTB) using standard splits (Sections 2–21 for training, 22 for development, and 23 for testing). Original constituency trees were converted to dependencies using the Stanford dependency framework (v3.5), with POS tags provided by the Stanford left3words tagger.

Key Results

The DIG-CNN model achieved performance comparable to established graph-based parsers. While it did not surpass the absolute state-of-the-art BiLSTM-based models of the time, it demonstrated the viability of purely convolutional, parallel architectures for complex linguistic tasks.

Comparison of DIG-CNN performance (UAS and LAS) against contemporary state-of-the-art dependency parsers on the PTB dataset.

As shown in the table above, the DIG-CNN achieved a UAS of 93.70 and an LAS of 91.72. When combined with the Eisner algorithm for post-processing, these scores improved to 94.03 and 92.00, respectively. While slightly lower than the scores reported by Dozat and Manning (2017), the DIG-CNN is significantly more amenable to GPU acceleration because it avoids the sequential bottleneck of LSTMs.

Discussion and Future Work

A key insight from this work is that competitive results can be achieved even with a relatively small receptive field (approximately 9 tokens of context), suggesting that iterative refinement can compensate for the lack of global sequential context provided by LSTMs.

However, the limited context window remains the primary drawback. Future research will focus on deeper architectures to incorporate broader sentence context and providing concrete wall-clock speed benchmarks to quantify the efficiency gains of this parallel approach in production environments.

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