Modern parsers for Enhanced Universal Dependencies (EUD) score every possible word-to-word link independently. EUD is the graph version of a cross-lingual grammar standard in which a word may have several heads, for example a subject shared by two coordinated verbs. Because each link is scored on its own, the predicted graphs often fall apart into pieces: a clause floats unattached, or a word cannot be reached from the root. Shared-task systems handle this with repair scripts that run after the parser and graft orphaned pieces back on. The graft is chosen from scores the model was never trained to get right for that decision. Medical image segmentation hit the same failure with thin vessels, where a single missing pixel breaks the network while barely changing the overlap score. The field learned two things. It had to make connectivity part of the training loss. It also had to check that a predicted connection is the right connection and not merely a connection.
We propose a training loss for EUD parsers built on a sentence-level analog of 0-dimensional persistent homology. Persistent homology is a tool that tracks when pieces of a structure join as a threshold is lowered. For every word, the loss computes the strength of its weakest link on the best path from the root. It then penalizes two failures. In the first, the word's correct path from the root is too weak to survive decoding. In the second, the word is reachable, but through a wrong edge that is stronger than its correct path. The second term carries over the "induced matching" idea from image topology to dependency graphs. Our central claim is that this loss reduces both how often repair is needed and how often repairs attach in the wrong place. It should do so beyond what simpler fixes achieve: multitask tree supervision, constrained decoding, or reweighting the cross-entropy on structurally critical edges.
Core Claim
The open problem in EUD parsing is not that outputs fail validation; repair scripts reliably make graphs pass. The problem is that the decisions near the connection threshold are made with uncalibrated scores. The IWPT overviews (2020; Overview of the IWPT 2020 Shared Task on Parsing into Enhanced Universal Dependencies, 2021; From Raw Text to Enhanced Universal Dependencies: The Parsing Shared Task at IWPT 2021) document that independent arc classifiers produce disconnected or unrooted graphs and that systems rely on post-hoc correction. DCU-EPFL built an XLM-R parser with an MLP that scores each word pair. It reports that even its improved multitask system still needed a dedicated connectivity post-processor. Neither line of work gives the encoder a training signal about global reachability.
The topology-in-vision literature supplies two methods and one warning. clDice scores structure by checking that the true centerline is covered by the prediction and that the predicted centerline lies inside the truth. Byrne et al. apply persistent-homology losses on cubical grids. In their experiments, the fraction of cardiac segmentations with correct topology rose from 85.3% to 98.7%. They also observed a small Dice trade-off and noted that rigid priors on the number of components and holes break when the true topology varies. The warning comes from TopoMatch. It shows that standard topological losses match features to the wrong location up to 99.4% of the time. It fixes this by comparing the prediction and the ground truth in a shared space, $C=\max(L,G)$, where $L$ is the predicted likelihood map and $G$ the true mask.
All three operate on pixel grids. We translate them to directed token graphs. In this setting the main cost concern from vision, cubic scaling in the number of pixels, disappears, because sentences have tens of tokens rather than millions of pixels.
The Loss
Let $P_{ij}\in[0,1]$ be the parser's predicted probability of an enhanced edge from head $i$ to dependent $j$. For a word $v$, define its reachability strength as the widest-path value from the root:
$$r_v(E)=\max_{\pi:\,\text{root}\to v,\ \pi\subseteq E}\ \min_{(i,j)\in\pi} P_{ij}.$$
Here $E$ is the set of edges the path is allowed to use. Thresholding $P$ at the decoding threshold $\tau$ makes $v$ reachable exactly when $r_v(E_{\text{all}})\ge\tau$. As $\tau$ is lowered, $r_v$ is the moment $v$ joins the root's component, which is the directed counterpart of a component's death time in 0-dimensional persistence. It is computed with a widest-path variant of Dijkstra's algorithm in $O(n^2)$ for a dense sentence graph. Its subgradient flows only into the single bottleneck edge, just as persistence losses send gradient to the critical pixels.
With $E_G$ the gold edges, the loss is
$$\mathcal{L}_{\text{reach}}=\sum_v \max\big(0,\ \tau+m-r_v(E_G)\big)\;+\;\lambda\sum_v \max\big(0,\ r_v(E_{\text{all}})-r_v(E_G)\big).$$
The first term asks that every word's correct path survive decoding with margin $m$. It is the analog of clDice's requirement that the true centerline be covered. The second term fires when the strongest route to $v$ is stronger than every correct route, meaning connectivity is being achieved through a wrong edge. This is the TopoMatch failure in syntactic form: the right Betti number with the wrong feature. The gradient pushes down the offending bottleneck edge. The total objective adds $\mathcal{L}_{\text{reach}}$ to the usual edge and label cross-entropy.
The loss counts no components and imposes no fixed component count, so it avoids the rigid-prior problem Byrne et al. describe. It only asks that the gold structure, whatever its shape, be the one that connects.
Research Program
We first measure the phenomenon, then train, then examine where gains come from. The measurement study takes a strong baseline parser on IWPT 2021 data and records three things per treebank and per construction type (coordination, control, relative clauses, empty-node paths). These are the fraction of sentences needing repair, the accuracy of the edges the repair script inserts, and how often the bottleneck edge of a correctly reachable word is not a gold edge. If repaired edges are already mostly correct and spurious bottlenecks are rare, the proposal's premise is weak, and we will report that.
We then train with $\mathcal{L}_{\text{reach}}$ on the same backbone. We sweep $\lambda$ and $m$ on development data only.
A secondary study takes the opposite tension seriously. Hashemi and Hwa show that forcing learner and machine-translation sentences into one connected tree spreads local errors. Fragment statistics alone (four features) correlate with error counts at $r=0.462$ on ESL text. The quantity $r_v$ gives a graded rather than binary fragmentation signal. We ask whether a parser trained to make correct paths strong yields weak $r_v$ values that are more informative about real ungrammaticality, using the FCE corpus from that paper.
Baselines
The naive reference is an XLM-R-large biaffine EUD parser trained with edge and label cross-entropy only, followed by the standard repair that attaches unreachable components to their highest-scoring head. Every system below shares this backbone, the IWPT 2021 training data (UD v2.7, 17 languages), tokenization and preprocessing, three seeds, and an equal hyperparameter-search budget. ELAS and EULAS are computed with the official scorer after the same repair script.
The strongest existing system to reproduce is the DCU-EPFL post-deadline configuration. It combines Trankit preprocessing, XLM-R large, treebank concatenation, and joint basic-tree plus enhanced-graph multitask training, and reports coarse ELAS 88.04. It is the most relevant competitor because it is the simplest neural way to give the enhanced layer a connected scaffold. We place our loss on top of it, not instead of it. Beating it means a seed-averaged ELAS gain whose interval excludes zero, together with a clear drop in the number of sentences needing repair.
The best IWPT 2021 system reached ELAS 89.24 (Bouma et al. 2021). We cite it as the ceiling and do not claim to beat it without matching its pipeline. For IWPT 2020 context, Heinecke's rule-based pipeline, which puts a tree parser first and then adds enhanced edges with rules and a classifier, reports average ELAS 82.6.
Three ablations isolate the key ingredient. The first uses only the sensitivity term, without the wrong-route term, which tests whether the induced-matching idea matters. The second reweights cross-entropy on gold edges that are bridges, meaning edges whose removal disconnects the gold graph. It focuses on the same edges without any path computation. The third replaces the enhanced decoder with a constrained decoder that first extracts a maximum spanning arborescence and then adds extra heads above threshold. This guarantees connectivity at decode time with no topology loss.
Why not just…?
Why not just keep the post-hoc repair script? Repair guarantees a valid graph but not a correct one. Its graft decisions use scores trained only for local edge classification. The measurement study reports the accuracy of repaired edges directly. If that accuracy is high and repairs are rare, the case for training-time topology collapses on this benchmark. In that case we would redirect the work to the noisy-text setting, where Hashemi and Hwa show forced connectivity does harm.
Why not just train basic trees and enhanced graphs jointly? DCU-EPFL did this and gained 4.5 ELAS points, which makes it a real threat. Their report that a connectivity post-processor was still required shows that multitask training leaves some fragmentation. The experiment settles it by putting our loss on top of their configuration. If gains vanish there, the tree scaffold already supplies the signal.
Why not just upweight the cross-entropy on critical edges? This is the most dangerous alternative. In a gold graph, the sensitivity term largely concentrates gradient on the weakest gold edges along paths, which resemble bridges. The bridge-weighted ablation is designed to match or beat the sensitivity-only variant. What reweighting cannot do is penalize a non-gold edge for providing a shortcut, because whether an edge is a shortcut depends on the model's current predictions, not on the gold graph alone. If bridge reweighting matches the full loss, we will conclude that the topological view adds an analysis tool but not a better objective.
Why not just decode a spanning arborescence first? The constrained decoder makes the graph connected by construction. It still selects tree edges from the same uncalibrated scores, and it can force a wrong head where a right one scored slightly lower. Running our loss with and without this decoder separates the two effects: decoding provides validity, while the loss should provide correctness at the margin.
Decisive Checks
The proposal succeeds if four things hold on IWPT 2021. Adding $\mathcal{L}_{\text{reach}}$ to the DCU-EPFL-style multitask parser raises ELAS by a seed-robust margin. It sharply cuts the fraction of sentences requiring repair. It raises the accuracy of whatever edges still get repaired. It beats both the bridge-reweighted and sensitivity-only ablations, with the largest gains concentrated in coordination and control constructions and in the lowest-resource treebanks. The FCE study is a bonus check: weak-reachability features from the trained parser should correlate with error counts more strongly than Hashemi and Hwa's fragment features ($r=0.462$).
A clear negative result is equally informative. If ELAS does not move once repair-needing sentences are already rare, it would show that EUD fragmentation, unlike vessel fragmentation, is a validity nuisance and not an accuracy bottleneck.
References
- Overview of the IWPT 2020 Shared Task on Parsing into Enhanced Universal Dependencies
- From Raw Text to Enhanced Universal Dependencies: The Parsing Shared Task at IWPT 2021
- The DCU-EPFL Enhanced Dependency Parser at the IWPT 2021 Shared Task
- clDice - A Novel Topology-Preserving Loss Function for Tubular Structure Segmentation
- A Persistent Homology-Based Topological Loss for CNN-Based Multiclass Segmentation of CMR
- Topologically Faithful Image Segmentation via Induced Matching of Persistence Barcodes
- Parse Tree Fragmentation of Ungrammatical Sentences
- Hybrid Enhanced Universal Dependencies Parsing