Abstract
This paper introduces a two-stage model for transforming dependency trees into complex semantic graphs. By separating local syntactic identification from "upward" linguistic movements (such as finding a shared subject in a coordinated sentence), the authors create a system that is easier to maintain, avoids "rule explosion," and handles non-local phenomena with high accuracy.
Introduction
In Natural Language Processing (NLP), a critical task involves converting "shallow" syntactic trees—which represent word order and basic grammatical relations—into "deep" semantic graphs that explicitly map predicate-argument structures (i.e., "who did what to whom").
The primary challenge in this conversion is the inherent complexity of natural language. For instance, a single subject may be shared across multiple verbs in a coordinated structure (e.g., "John likes to sing and dance"). Traditional graph rewriting systems often attempt to resolve these dependencies using massive, monolithic sets of complex rules. This approach frequently leads to "rule explosion," where specific rules must be authored for every possible distance between related words. Such systems are difficult to build, hard to debug, and often fail to capture "non-local" dependencies where related elements are far apart in the tree structure.
The Two-Stage Transformation Model
To address these limitations, the authors propose a two-stage transformation process that aligns with linguistic intuition by separating the detection of a dependency from the logic of its resolution.
Stage 1: Local Identification
The first stage employs standard local rewriting rules based on the Single PushOut (SPO) model. Rather than attempting to solve complex global dependencies immediately, these rules identify immediate syntactic patterns and plant "constrained edges" in the graph. These edges act as placeholders or "seeds" that contain instructions for how they should evolve in the subsequent stage.
Stage 2: Constraint-Based Propagation
The second stage is the core innovation of the paper. The constrained edges introduced in Stage 1 are "evolved" through four specific linguistic movement types:
- Move Up ($m\uparrow$): An edge "climbs" the tree toward the root until it identifies its proper head. This movement is guided by a simple state machine that ensures the edge attaches to the correct linguistic governor.
- Redirect Up ($r\uparrow$): This operation moves all connections of a specific word to a higher-level governor.
- Share Up/Down ($s\uparrow, s\downarrow$): These operations duplicate edges to handle phenomena like coordination or control verbs, where one noun serves as an argument for multiple predicates.
By restricting most movements to an "upward" direction toward the sentence root, the authors ensure both termination (the process cannot loop infinitely) and confluence (the system consistently reaches the same stable state regardless of rule order).
Experimental Evaluation
The model was evaluated by converting between two distinct French linguistic schemas: the source depFRMG (a deep dependency schema from the FRMG parser) and the target depFTB (the dependency version of the French Treebank).
The researchers used a training set of 9,881 sentences (ftb6_1) to design the transformation rules and a test set of 1,235 sentences (ftb6_3) for final evaluation.
Key Results
- High Accuracy: The system achieved a Labelled Attachment Score (LAS) of 85.8%. This is remarkably close to the 88.2% LAS achieved by a state-of-the-art statistical parser trained directly on the target data, demonstrating that a rule-based approach can be highly competitive.
- Rule Efficiency: The authors designed only 86 local transformation rules. Notably, only 5 of these rules actually required Stage 2 constraints. However, those 5 rules were responsible for resolving over 7,000 dependencies (approximately 2.5% of the total dataset). This highlights how a small set of linguistically-informed constraints can replace a vast number of manual, distance-specific rules.
Discussion and Conclusion
The success of this two-stage approach stems from the separation of concerns. By decoupling the trigger (Stage 1) from the movement logic (Stage 2), the system avoids rule explosion. A general "Subject" rule combined with a "Move Up" constraint can handle subjects at any depth, whereas traditional systems would require unique rules for every possible depth level.
While the system currently faces some limitations—such as handling non-projective dependencies and the inability to trigger rules based on the absence of an edge—it provides a robust framework for deep linguistic analysis. Future work aims to expand the constraint types and apply this methodology to the generation of full semantic graphs from raw text.
Summary updated