ÚFAL at MRP 2020: Permutation-invariant Semantic Parsing in PERIN

David Samuel, Milan Straka

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.

Bipartite matching between predicted queries and target semantic nodes.

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.

The PERIN architecture, illustrating the flow from input tokens through the XLM-R encoder and Transformer decoder to specialized classification heads.

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

Abstract

We present PERIN, a novel permutation-invariant approach to sentence-to-graph semantic parsing. PERIN is a versatile, cross-framework and language independent architecture for universal modeling of semantic structures. Our system participated in the CoNLL 2020 shared task, Cross-Framework Meaning Representation Parsing (MRP 2020), where it was evaluated on five different frameworks (AMR, DRG, EDS, PTG and UCCA) across four languages. PERIN was one of the winners of the shared task. The source code and pretrained models are available at http://www.github.com/ufal/perin.
BibTeX
@inproceedings{samuel2020ufal,
  author = {David Samuel and Milan Straka},
  title = {{ÚFAL at MRP 2020: Permutation-invariant Semantic Parsing in PERIN}},
  booktitle = {CoNLL Shared Task},
  year = {2020},
  doi = {10.18653/v1/2020.conll-shared.5},
}
Figure