Researchers who turn sentences into meaning graphs (structures recording "who did what to whom") cannot agree on what those graphs should look like. One school ties every graph node to a word. Another ties nodes to arbitrary spans of text. A third, Abstract Meaning Representation (AMR), uses abstract concept nodes that are tied to no word at all. The Meaning Representation Parsing shared tasks (MRP 2019, MRP 2020) put these formalisms into one file format and one scorer. That scorer finds the best match between a predicted graph and a gold graph, a maximum-common-subgraph search that is NP-hard, so it runs as a stochastic search with no reproducibility guarantee. It also answers only one question: how close is a parse to its gold graph within the same formalism. It cannot say how much two formalisms agree on the same sentence. It cannot place a graph in a vector space, so it cannot be used to search millions of parsed sentences.
We propose replacing the search with a deterministic, polynomial-time matching built from an idea taken from scalable graph embedding. NodePiece (NodePiece) avoids storing one vector per node: it describes each node by its nearest "anchor" landmark nodes, its hop distances to them, and its incident relation types. In meaning graphs the natural anchors already exist and are shared by every formalism, namely the words of the sentence. If every node in every formalism is described by the tokens it covers, or by its hop distances to nodes that do cover tokens, then nodes from a predicted graph, a gold graph, or a graph in a different formalism become comparable. They can be matched by a standard assignment algorithm instead of a search. The same descriptions can be pooled into fixed-size vectors for retrieval at corpus scale.
Core Claim
A node description built over the sentence's own tokens is enough to recover the official MRP scores across all three anchoring styles. It does this deterministically, gives a provable lower bound on the official score, and runs much faster. Because the descriptions do not depend on the formalism, the same engine also gives the first common measure of agreement between formalisms on parallel annotations, and graph vectors suitable for nearest-neighbour search. The novelty is not a new parser. It is turning compositional, anchor-based node encoding from a memory-saving trick for knowledge graphs into the alignment step of a standardized evaluation engine for fragmented semantic formalisms.
How the Engine Works
For a node $v$ in a graph over sentence $s$, the signature $\sigma(v)$ has four parts. The first is the set of token positions $v$ is anchored to, if any. The second, for unanchored nodes, is the $k$ nearest anchored nodes with their hop distances. The third is the node label, which may be empty: UCCA internal nodes, for example, carry no label. The fourth is the multiset of incident edge labels. A few rounds of Weisfeiler-Leman refinement then enrich each signature with its neighbours' signatures, a step that repeatedly hashes each node together with its neighbours' descriptions. This reuses the subtree idea from BAMBOO.
Given a predicted graph $P$ and a gold graph $G$, we build a node-to-node similarity matrix from the signatures. We solve a one-to-one assignment $A$ with the Hungarian algorithm, which takes $O(n^3)$ time for $n$ nodes. We then compute the MRP tuple F1 (an F-score over predicted nodes, edges, labels, properties and anchors) under that fixed assignment. Any one-to-one node correspondence gives a feasible count of matched tuples, so
$$F_A(P,G) \le F^*(P,G),$$
where $F^*$ is the score under the optimal correspondence that the official scorer searches for. The official scorer's output also never exceeds $F^*$. Comparing our score with it per sentence therefore shows which method finds the better alignment, and our score never depends on a random seed. A soft variant replaces exact tuple matches with signature similarity to give graded scores for semantic-similarity tasks. Pooling the hashed refined signatures gives a fixed-length graph vector.
The anchors play different roles in the three anchoring styles. In word-anchored formalisms (DM, PSD) the anchor set alone nearly fixes the alignment. In span-anchored formalisms (EDS, UCCA) span overlap does most of the work and structure breaks ties among unlabeled nodes. In AMR, gold anchors are absent. Here we attach tokens using an off-the-shelf AMR-to-text aligner and describe the remaining nodes by distance to aligned nodes. This dependence on an aligner is the weakest point of the design, and the experiments measure it directly.
Research Program
The work has three parts, in order of risk.
The first is the scorer itself, packaged on the model of OGB (Open Graph Benchmark). OGB is a graph benchmark that fixes data splits and centralizes metric code so results cannot drift between labs. Our package will use the official MRP splits and a single evaluator call, and will report variance over seeds wherever learned components appear. That last practice follows Locatello et al., who showed that seeds and hyperparameters can matter more than the method being compared.
The second part is a measure of agreement between formalisms. MRP 2019 annotates overlapping text across DM, PSD, EDS, UCCA and AMR. Its graphs share token anchors, so our assignment can match a DM node to a PSD node for the same sentence and report an agreement score with no formalism-specific conversion. Normalizing Compositional Structures Across Graphbanks supplies a calibration point. It found that most DM–PSD differences come from how each formalism composes meanings rather than from linguistic disagreement, and aligning composition raised DM–PSD tree similarity from 55.7 to 78.8. Our agreement score should rise in the same direction on their normalized graphs. Unlike that work, ours extends to UCCA and AMR. This part connects to the paradox of training one model on many formalisms. TUPA, a transition-based parser, scored 45.34 F when trained on all formalisms jointly against 57.70 when trained on each separately. We test whether the agreement between two formalisms predicts whether training on both helps or hurts, using the gain or loss from adding one formalism as an auxiliary task.
The third part is graph vectors for retrieval. Pooled signatures let us index millions of automatically parsed sentences and search for structurally similar meanings. This addresses the scaling gap that A Survey of AMR Applications points to, where graph encoders are rebuilt per task and break down at corpus scale.
Baselines
The naive reference point is a structure-blind scorer: the F1 over anchors and labels alone, ignoring edges, for the parser-evaluation experiments, and plain token overlap for the similarity experiments. If our engine cannot beat this, the structural signature adds nothing.
The strongest existing scorer is the official MRP tool, which runs the subgraph search. It defines the target for the parser-evaluation question. We will run it with its default settings and also with an expanded search budget, on the same machines and the same graphs. Its output is the reference our deterministic score must track. Beating it means one of two things. One is matching it within a fraction of an F point and agreeing with it on the ranking of parsers, at lower runtime and zero run-to-run variance. The other is our alignment exceeding its score on individual sentences, which the lower-bound property makes a meaningful win.
For graded similarity the strongest competitor is the learnable Wasserstein Weisfeiler-Leman kernel from BAMBOO, WWLKθ, which compares graphs through the distance between their refined node embeddings. It reports 66.94 Pearson correlation on the BAMBOO STS partition, against 58.45 for Smatch, the standard AMR scorer. We use the same partitions and the same training data for any learned weights. Beating it means exceeding 66.94 on STS without losing on the meaning-altering role-swap challenge (Arg). It also means transferring to non-AMR formalisms, where WWLKθ has never been run. For that transfer we will run WWLKθ ourselves.
The key ablation removes the anchor-and-distance parts of the signature and keeps labels and edges. This is essentially WWLK given span text as node labels. It isolates whether the shared token anchors, rather than the refinement or the assignment step, carry the gain.
Why not just…?
Why not just run the official MRP scorer with more search restarts? Sentence graphs are small, so the NP-hardness may rarely bite in practice. This is a real threat to the speed and stability argument. We will measure it directly by recording the scorer's runtime and the spread of its scores across random seeds on the MRP 2019 and 2020 test sets. If the spread is negligible and the runtime is acceptable, the claim narrows honestly to what the official scorer cannot do at all. It cannot compare formalisms with each other, it gives no graded similarity, and it produces no graph vectors.
Why not just apply WWLK to every formalism, using span text as node labels? This is the closest competitor and it may work for span-anchored graphs. Two things argue against it, and the ablation in the Baselines section tests both. First, unlabeled internal nodes in UCCA have no text of their own, so their identity must come from what they cover and where they sit. Second, a label-embedding comparison cannot tell apart two nodes with the same label in different positions, for example duplicated concepts that are reached by more than one path. If the ablation matches the full system, we will report that the anchor encoding is unnecessary.
Why not just compare sentence embeddings of the text? For parser evaluation this is meaningless, because the predicted and gold graphs come from the same sentence. For similarity it ignores structure. The Arg challenge in BAMBOO swaps semantic roles while changing the wording very little, which is exactly where a text embedding should fail. We found no reported result on Lacuna for sentence-embedding baselines on BAMBOO. We will run one on all partitions.
Proposed Experiments
The first decisive check is fidelity. On every MRP 2019 and 2020 framework, using system outputs from parsers we train (TUPA and a transformer-based parser) at several training checkpoints, we compute the per-sentence and corpus-level gap between our score and the official score, and the rank correlation over systems. We will also use the shared-task submissions if they can be obtained. The reference ranges from the shared tasks are the low 90s for word-anchored formalisms and 0.82 F1 for the best MRP 2020 AMR system. Success means rank correlation near 1 for word- and span-anchored formalisms. For AMR we report how much the gap depends on which aligner we use, testing two aligners.
The second check is graded similarity on BAMBOO's main partition and its three challenges, which test meaning-preserving restructuring (Reify), synonym substitution (Syno) and role swaps (Arg). WWLKθ's 66.94 is the bar.
The third check is agreement between formalisms. We compute pairwise agreement among the five MRP 2019 formalisms on shared sentences. Agreement should increase on DM–PSD after the normalization of Donatelli et al. If it does not, the measure is not tracking structural convergence. We then test whether the agreement between two formalisms predicts the sign of the change when one is added as an auxiliary task for the other. We run three seeds per pair and treat a correlation that does not survive seed variance as a null result.
The fourth check is scale. We measure throughput and memory for scoring and for nearest-neighbour retrieval over a corpus of parsed sentences grown by powers of ten. We compare against pairwise WWLK and pairwise official scoring, and check retrieval quality against BAMBOO similarity labels.
References
- MRP 2019: Cross-Framework Meaning Representation Parsing
- MRP 2020: The Second Shared Task on Cross-Framework and Cross-Lingual Meaning Representation Parsing
- NodePiece: Compositional and Parameter-Efficient Representations of Large Knowledge Graphs
- Weisfeiler-Leman in the Bamboo: Novel AMR Graph Metrics and a Benchmark for AMR Graph Similarity
- Open Graph Benchmark: Datasets for Machine Learning on Graphs
- A Sober Look at the Unsupervised Learning of Disentangled Representations and their Evaluation
- Normalizing Compositional Structures Across Graphbanks
- TUPA at MRP 2019: A Multi-Task Baseline System
- A Survey of AMR Applications