Replicating and Extending "Because Their Treebanks Leak": Graph Isomorphism, Covariants, and Parser Performance

Mark Anderson, Anders Søgaard, Carlos Gómez-Rodríguez

Abstract

Søgaard (2020) obtained results suggesting the fraction of trees occurring in the test data isomorphic to trees in the training set accounts for a non-trivial variation in parser performance. Similar to other statistical analyses in NLP, the results were based on evaluating linear regressions. However, the study had methodological issues and was undertaken using a small sample size leading to unreliable results. We present a replication study in which we also bin sentences by length and find that only a small subset of sentences vary in performance with respect to graph isomorphism. Further, the correlation observed between parser performance and graph isomorphism in the wild disappears when controlling for covariants. However, in a controlled experiment, where covariants are kept fixed, we do observe a strong correlation. We suggest that conclusions drawn from statistical analyses like this need to be tempered and that controlled experiments can complement them by more readily teasing factors apart.

Introduction

In dependency parsing, understanding why performance varies across different treebanks is a fundamental question. A 2020 study by Søgaard proposed a provocative answer: "Because their treebanks leak." Specifically, it argued that the fraction of test trees isomorphic to training trees—a metric called Directed Unlabelled Graph Isomorphism (DUG)—accounts for a significant portion of parser performance variation.

However, DUG is heavily influenced by two "covariants":

  1. Sentence Length: Short sentences have very few possible tree structures, making "leaks" almost inevitable. Long sentences have millions of possibilities, making leaks nearly impossible.
  2. Training Data Size: Larger treebanks are naturally more likely to contain a wider variety of structures, increasing the chance of a match.

This paper investigates whether DUG is a meaningful independent predictor of performance or if it’s just a proxy for these more obvious factors.

Methodology

The authors employ three main strategies to test the original claim:

  • Robustness Testing: They re-run the original linear regression analysis using different random seeds for cross-validation to see if the results hold up.
  • Statistical Control (Partial Correlation): They use Spearman’s $\rho$ and partial correlation coefficients to measure the relationship between DUG and parser performance (Labelled Attachment Score, or LAS) while mathematically "subtracting" the influence of training size and sentence length.
  • Controlled Experiment: To truly isolate the effect, they created a "lab setting" by sampling treebanks to ensure every training set had exactly 1,000 sentences and every sentence (in both training and test sets) was exactly 12 tokens long.

The study uses a massive range of data from the Universal Dependencies (UD) project, including the original 33 treebanks from the CoNLL 2018 shared task and an extended set of over 90 treebanks.

Key Insights: The "Length" Trap

A critical observation is that DUG is highly sensitive to sentence length. For sentences of length 5, DUG is almost always 1.0 (everything is a leak). For length 21, it is almost always 0.0. Because sentence length is a primary driver of parsing difficulty, DUG often ends up "stealing" the explanatory power that actually belongs to sentence length.

Figure 1: LAS vs DUG across different sentence lengths. For short sentences, DUG is saturated at 1.0; for long sentences, it is near 0.0.

The authors found that DUG only shows a meaningful spread of values for sentences between 9 and 14 tokens long. Outside this range, the metric is too skewed to be useful. Furthermore, the original study's reliance on linear regression on a small sample was risky; changing the random seed for the data split often caused the linear models to fail entirely.

Key Results

Vanishing Correlation in the Wild

When controlling for both training size and sentence length, the correlation between DUG and performance effectively vanished in the broad dataset (dropping to a coefficient of 0.01, $p=0.926$). In "the wild" (standard benchmarks), the signal from DUG is completely drowned out by the impact of training set size.

Controlled Success

In the controlled experiment (fixed size and length), DUG showed a high correlation with accuracy ($\rho = 0.82$), proving that "leakage" does help parsers, but its effect is usually masked by more dominant variables.

Figure 2: Controlled experiment results (N=1000, length=12) showing a strong correlation between DUG and LAS across different languages.

The authors also highlight that the relationship between training size and performance is logarithmic, not linear. Accounting for this improved the fit of their statistical models significantly.

Limitations and Future Work

The authors acknowledge that their controlled experiment was limited to only 9 treebanks because very few datasets have enough sentences of a specific length to build a 1,000-sentence training set.

Future work could explore "partial leakage"—measuring if parsers benefit from seeing specific sub-graphs or phrases during training, even if the entire sentence structure is new. The paper concludes with a call for more rigorous statistical practices in NLP, specifically the use of controlled experiments to complement "in the wild" data analysis.

Summary updated

Abstract

S{\o}gaard (2020) obtained results suggesting the fraction of trees occurring in the test data isomorphic to trees in the training set accounts for a non-trivial variation in parser performance. Similar to other statistical analyses in NLP, the results were based on evaluating linear regressions. However, the study had methodological issues and was undertaken using a small sample size leading to unreliable results. We present a replication study in which we also bin sentences by length and find that only a small subset of sentences vary in performance with respect to graph isomorphism. Further, the correlation observed between parser performance and graph isomorphism in the wild disappears when controlling for covariants. However, in a controlled experiment, where covariants are kept fixed, we do observe a strong correlation. We suggest that conclusions drawn from statistical analyses like this need to be tempered and that controlled experiments can complement them by more readily teasing factors apart.
BibTeX
@inproceedings{anderson2021replicating,
  author = {Mark Anderson and Anders Søgaard and Carlos Gómez-Rodríguez},
  title = {{Replicating and Extending "Because Their Treebanks Leak": Graph Isomorphism, Covariants, and Parser Performance}},
  booktitle = {Annual Meeting of the Association for Computational Linguistics},
  year = {2021},
  url = {https://openreview.net/forum?id=B4U-s4ZK73K},
}

Loading related content...

Figure