Introduction
Semantic parsing—the task of converting natural language into structured meaning representations like graphs—has traditionally relied on auto-regressive models. These models predict nodes sequentially, imposing an artificial order on naturally orderless semantic graphs. This approach often suffers from the "discontinuity issue," where models are penalized for predicting correct nodes in an "incorrect" sequence, and it is inherently limited by the speed of sequential generation.
To address these challenges, we introduce PERIN (Permutation-invariant Semantic Parsing), an "all-at-once" parser that treats sentence-to-graph translation as a set prediction problem. By leveraging a permutation-invariant loss function and a universal architecture, PERIN achieved top-tier results across five semantic frameworks and four languages in the MRP 2020 shared task.
Methodology
Permutation-Invariant Set Prediction
The core innovation of PERIN is treating graph nodes as an unordered set. Instead of generating a sequence, the model outputs a set of $Q$ queries in parallel. During training, the system employs the Hungarian algorithm to determine the optimal bipartite matching between predicted nodes and ground-truth nodes. This allows the model to be trained with a loss function that remains invariant to the order of predictions, aligning the model's inductive bias with the actual nature of graph data.
Universal Architecture
PERIN utilizes a flexible architecture designed to handle diverse semantic theories. It features a fine-tuned XLM-R encoder and a Transformer decoder. The decoder's output feeds into specialized classification heads that handle node labels, anchors (linking nodes to text), edges, properties, and the graph's "top" node.
Technical Innovations
- Relative Label Encoding: To improve generalization and reduce the label space, PERIN uses a "Minimal Encoding Rule Set." Instead of predicting absolute labels from a static vocabulary, it predicts rules to transform input tokens (e.g., converting "diving" to "dive"). This significantly reduces the number of classification targets.
- Adaptive Loss Balancing: Given the multi-task nature of the model (predicting nodes, edges, anchors, etc.), PERIN uses a data-driven metric to dynamically weight different losses during training, ensuring no single task dominates the learning process.
- Nodeification: Complex graph structures are simplified by converting node properties into standalone nodes connected to parents via labeled edges.
Experimental Setup and Datasets
The model was evaluated on the MRP 2020 (Meaning Representation Parsing) shared task, covering five distinct frameworks: AMR (English, Chinese), DRG (English, German), EDS (English), PTG (English, Czech), and UCCA (English, German). This diversity demonstrates PERIN's cross-framework universality, requiring only minimal pre- and post-processing adjustments for different semantic theories.
Key Results
PERIN emerged as one of the two winning systems at MRP 2020, demonstrating significant improvements over previous benchmarks:
- Accuracy: It achieved a macro-averaged F1 score of 86.54% in the cross-framework track (English) and 85.90% in the cross-lingual track.
- Performance Gains: On English AMR, PERIN reached an F1 of 78.43%, a substantial jump from the 73.11% achieved by the best 2019 system.
- Ablation Study: The importance of adaptive loss balancing was confirmed; replacing it with constant weights caused the average EDS score to drop from 92.73% to 91.60%.
Conclusion
PERIN demonstrates that treating semantic parsing as a set prediction problem is not only theoretically sound but also practically superior to traditional auto-regressive methods. While some framework-specific logic remains necessary, the permutation-invariant approach provides a robust foundation for efficient and accurate graph generation across multiple languages and semantic frameworks. Future work will focus on improving edge accuracy in specific frameworks like AMR and extending this paradigm to broader graph generation tasks.
Summary updated