Repairing Shared Arguments in Meaning-Representation Graphs by Local Search

A meaning-representation graph encodes who did what to whom in a sentence. Nodes are concepts or words, and directed edges are semantic roles. In these graphs one entity often fills roles for several predicates at once. In "John wants to go," John is both the wanter and the goer, so his node has two incoming edges. This multiple-parent pattern is called reentrancy, and the best current parsers handle it badly. A diagnostic study of the winning MRP 2020 parser found that it omits the reentrant edge in 40.5% of cases for Abstract Meaning Representation (AMR) and 34.5% for Prague Tectogrammatical Graphs (PTG). Error rates reach 43% on coreference and at least 50% on possessives (Argument Sharing in Meaning Representation Parsing). Combinatorial optimization has a standard remedy for global solvers that get the overall shape right and the local details wrong: start from the global answer and fix it with cheap local moves. In syntactic parsing, that remedy has only been built for trees, where every word has exactly one parent.

We propose a local search pass that runs after a global semantic parser. Its move set is designed for graphs with multiple parents: add a second parent, swap one co-parent for another, and merge two duplicated concept nodes into one shared node. A separate second-order scorer judges each move. It looks at pairs of edges that share a child, share a parent, or form a chain, and it only considers a sparse set of candidate edges. Two ingredients come from the theory of community detection. First, the scorer is trained on held-out ("cross-fitted") parser outputs, so the refiner never sees the parser's memorized training predictions. Second, moves are gated, so they fire only where the surrounding graph is reliable enough for local correction to help rather than amplify errors. The scientific question is whether the conditions under which local refinement provably works in random graphs have an empirical counterpart in semantic parsing. The practical question is whether the repairs beat simply calibrating the parser's edge threshold.

Core Claim

Missing reentrancies in global set-prediction parsers are largely local, correctable errors. The parser usually gets the predicates and the shared entity right but drops the second incoming edge, or it creates two copies of the entity instead of one shared node. A hill-climbing search over a small set of graph moves, scored by a second-order model trained on out-of-fold parser outputs, can recover many of these edges without hurting the rest of the graph. It should pay off most on unanchored AMR, where the node-merge move has no tree analogue.

The claim makes a further, falsifiable prediction. Repair gains should depend on how accurate the parser's output is near the error. Where neighborhood error is low, gains should be positive. In the highest-error categories, such as possessives, ungated search should make things worse, and gating should remove that harm. This mirrors the stability result in Partial recovery bounds for the sparse stochastic block model, where neighborhood updates drive error to zero only if the initial error stays below a fixed tolerance. We do not assume that the 25% figure transfers to semantic graphs. We test whether any analogous threshold exists.

Relation to Prior Work

Three groups of papers play three different roles here.

The first group supplies the motivation. ÚFAL at MRP 2020: Permutation-invariant Semantic Parsing in PERIN predicts nodes as an unordered set. It uses the Hungarian algorithm to match predicted nodes to gold nodes during training, then attaches separate prediction heads for labels, anchors, and edges. It reaches 86.54% macro F1 on the English cross-framework track and 78.43% on English AMR. Argument Sharing in Meaning Representation Parsing dissects PERIN's failures on shared arguments but proposes no fix. Our proposal is the missing correction step, and it uses that paper's breakdown by linguistic phenomenon as its evaluation lens.

The second group supplies the search method, which we must extend. Edge-Linear First-Order Dependency Parsing with Undirected Minimum Spanning Tree Inference builds a tree from a sparse set of edges in linear time, then improves it with a greedy pass of edge swaps. Effective Greedy Inference for Graph-based Non-Projective Dependency Parsing scores each candidate move by its exact gain and loss under higher-order factors. Its post-search swap pass on top of TurboParser adds an average of 0.27% UAS. Both papers define a move as replacing a word's single parent, so neither can create a reentrancy. We keep their exact gain/loss scoring and their linear-time sparsity, and we replace the move set.

The third group consists of neural refiners. These are the most serious competitors, and we treat them as baselines rather than inspirations. Semantic Dependency Parsing with Edge GNNs treats every candidate edge as a node in a second graph. It passes messages among sibling, co-parent, and grandparent edges for three rounds, reaching 91.1 average in-domain and 89.4 out-of-domain F1 on the SemEval 2015 semantic dependency benchmark. Its costs are cubic time and quadratic memory, and it handles only word-to-word (bilexical) graphs. Semantic Role Labeling with Iterative Structure Refinement refines an initial set of role labels with a small neural network that conditions on the other predicted roles of the same predicate. It injects Gumbel noise during training so the refiner learns to correct rather than copy. Our design differs from both in four ways. We make discrete, validity-preserving edits to an already-decoded graph. We score only a sparse candidate set. We handle unanchored concept nodes through merging. And we replace noise injection with cross-fitting, which the stochastic block model literature uses in the form of an independent edge split between initialization and refinement (Stochastic Block Model and Community Detection in Sparse Graphs).

Research Program

The first phase is global and reuses PERIN unchanged. It produces a graph $G_0$ together with PERIN's edge scores for every node pair it considered. From these we build a sparse candidate set. For each node we keep the top-$k$ alternative parents by PERIN's edge score, plus every node within two hops in $G_0$. For AMR we also pair any two nodes that share a concept label or have overlapping alignments as candidates for merging. The candidate count $m$ grows roughly linearly with sentence length for fixed $k$, which keeps the second phase linear in $m$, as in the edge-linear parser.

The second phase uses a scorer $S$, a small network over contextual encoder features. $S$ assigns a first-order score to each candidate edge and second-order scores to edge pairs that are siblings, co-parents, or grandparents, using the same three relations as the Edge GNN but only within the candidate set. The search operates on five moves:

  • add a parent to a node that already has one;
  • delete an edge;
  • reattach an edge to a different parent;
  • swap one co-parent for another;
  • merge two nodes, redirecting all their edges to the survivor.

Each move is accepted only if it keeps the graph acyclic and connected and if its exact change in $S$ is positive. The search ends when no improving move remains. For every move we also compute a gate: the model's estimated accuracy of the move's local neighborhood, meaning the edges touching the nodes the move changes. A move fires only if that estimate exceeds a threshold $\tau$, tuned on development data.

The training protocol is where the community-detection theory enters. We split the training set into $K$ folds and train $K$ copies of PERIN, each on all folds but one. We then run each copy on its held-out fold. $S$ and the gate are trained only on these out-of-fold outputs, so they learn from errors of the kind the parser actually makes on unseen text. Training on in-sample outputs would teach the refiner that the parser is nearly always right, which is the deterministic-data version of the bias that sample splitting prevents in the stochastic block model analysis.

The analysis program bins every development error by linguistic phenomenon and graph complexity, following the Argument Sharing categories. Within each bin we plot refinement gain against initial neighborhood error, separately for gated and ungated search. A crossover point, with gain turning negative beyond some error level, would be the empirical analogue of the stability threshold. The absence of any such pattern would also be informative.

Baselines

The naive reference point is PERIN alone, retrained from its description where necessary and evaluated on the same English MRP 2020 development and test splits. The strongest reported numbers for this system are 86.54% English cross-framework macro F1 and 78.43% English AMR F1, both from the PERIN paper. On reentrancy specifically, the bar is the omission rates of 10.6% (EDS), 34.5% (PTG), and 40.5% (AMR) reported in Argument Sharing. For AMR, the stronger shared-task reference is the Hitachi system's 0.82 F1 reported in the MRP 2020 overview. We include it as context and do not claim to beat it unless we also refine its outputs.

The cheapest serious competitor is a calibrated PERIN. We tune a separate edge-acceptance threshold for nodes that already have one parent, and for AMR a label-match merge rule, all on the same development data and with the same tuning budget as $\tau$. This tests whether the missing edges are simply under-confident predictions. Beating it means a statistically significant gain, by paired bootstrap over sentences, in both reentrant-edge F1 and overall MRP F1.

The strongest neural competitor is a continuous refiner given identical inputs and identical cross-fitted training data. It is an Edge-GNN-style network over the same sparse candidate set, run for three rounds and followed by thresholded decoding. A variant adds Gumbel noise in the style of Lyu et al.. Both get the same parameter count, the same hyperparameter search budget, and the same encoder. Beating it means higher reentrant-edge F1 at equal or lower runtime, with zero invalid outputs, meaning cyclic or disconnected graphs, which discrete search guarantees by construction.

On SemEval 2015 we report the published Edge GNN results (91.1 in-domain, 89.4 out-of-domain average F1) as the reference for a secondary experiment. There, local search refines a first-order parser on DM, PAS, and PSD. The goal is to test whether sparse discrete search recovers most of the second-order gain at linear cost.

Three ablations isolate the key ingredients: training $S$ on in-sample rather than cross-fitted outputs, removing the gate, and removing the merge move.

Why not just…?

Why not just lower PERIN's threshold for second parents? This is the real threat. If reentrant edges are present in PERIN's scores but fall just below the decision boundary, calibration will recover most of the gain, and the search adds little. We cannot rule this out from the literature. Argument Sharing reports omissions, not where the gold edge ranks among PERIN's candidates. The first experiment we run is therefore a measurement: for each omitted reentrant edge, record its rank among PERIN's candidate edges. If most omitted edges rank first among the rejected alternatives, we will report that calibration suffices and reduce the proposal to the AMR merge move and the threshold study. The case for search rests on errors that calibration cannot express. Duplicated AMR concepts are one example, and edges whose correctness depends on a co-parent elsewhere in the graph are another.

Why not just add a learned neural refinement layer, as in the Edge GNN? Continuous refinement already improves second-order structure, and the Edge GNN paper shows it beats loopy belief propagation. However, it has only been shown for bilexical graphs, at cubic cost, and with no guarantee that its outputs are valid graphs. Our main baseline restricts that refiner to the same sparse candidates and the same cross-fitted data. Any remaining gap is therefore attributable to discrete moves, merging, and gating. If the continuous refiner matches us, we will say so.

Why not just flatten the graphs into trees and use existing tree swaps? Pruning or packing the reentrant edges discards exactly the structure we are trying to recover. Prior work summarized in the file found that how well tree approximation works varies strongly across formalisms. We include a pruned-tree version of our search as a sanity check, and we expect it to fail on the reentrancy metrics by construction.

Why not just train a bigger parser or an ensemble? Gains in overall F1 can coexist with persistent reentrancy failures, and the 16–26 point drop in structural F1 on complex graphs reported for PERIN is a structural failure, not an average-accuracy one. Still, an ensemble of our $K$ cross-fitted PERIN models costs nothing extra to build. We will report its reentrant-edge F1 alongside ours.

Proposed Experiments

The primary evaluation is English MRP 2020 on EDS, PTG, and AMR. We use the MRP graph-matching F1 (based on maximum common edge subgraph), reentrant-edge precision and recall, error rates for each phenomenon (coreference, possessives, control, coordination), and wall-clock time. Analysis uses the same validation sets as Argument Sharing: 3,302 EDS, 1,664 PTG, and 3,560 AMR graphs. Final numbers are reported once on test. The secondary evaluation is SemEval 2015 Task 18 with labeled F1 on the in-domain and out-of-domain splits, plus runtime as a function of sentence length.

Three checks decide the outcome. The first is the rank analysis of omitted edges, which tells us in advance whether calibration is the right answer. The second is the comparison between cross-fitted and in-sample training. We expect the in-sample refiner to learn near-identity behavior and make few edits; if it does not, cross-fitting is unnecessary. The third is the gain-versus-neighborhood-error curve. The theory-derived hypothesis predicts that ungated search hurts in the highest-error bins, such as possessives and the highest complexity bins of PTG and AMR, and that gating removes the harm while keeping the gains elsewhere. A flat curve would falsify the claim that stability thresholds matter for semantic graph repair. A clean crossover would give parser designers a concrete rule for when local correction is safe.