\section{Introduction}
Research with the Abstract Meaning Representation \citep[AMR;][]{amr}, a broad-coverage semantic annotation framework in which sentences are paired with directed acyclic graphs, must contend with the lack of gold-standard alignments between words and semantic units in the English data.
A variety of rule-based and statistical algorithms have sought to fill this void,
with improvements in alignment accuracy often translating into improvements in AMR parsing accuracy \citep{pourdamghani2014,naseem2019,tamr}.
Yet current alignment algorithms still suffer from limited coverage and less-than-ideal accuracy, constraining the design and accuracy of parsing algorithms.
Where parsers use latent alignments \citep[e.g.,][]{lyu-18,cai-20}, explicit alignments can still facilitate evaluation and error analysis.
Moreover, AMR-to-text generation research and applications using AMR stand to benefit from accurate, human-interpretable alignments.

We present \textbf{L}inguistically \textbf{E}nriched \textbf{AMR} (\textsc{leamr}) alignment,
which achieves full graph coverage via four distinct types of aligned structures: subgraphs, relations, reentrancies, and duplicate subgraphs arising from ellipsis.
This formulation lends itself to unsupervised learning of alignment models.
Advantages of our algorithm and released alignments include: (1)~much improved coverage over previous datasets, (2)~increased variety of the substructures aligned, including alignments for all relations, and alignments for diagnosing reentrancies, (3)~alignments are made between spans and connected substructures of an AMR, (4)~broader identification of spans including named entities and verbal and prepositional multiword expressions.

Contributions are as follows:
\begin{itemize}
    \item A novel \textit{all-inclusive} formulation of AMR alignment in terms of mappings between spans and connected subgraphs, including spans aligned to multiple subgraphs; mappings between spans and inter-subgraph edges; and characterization of reentrancies. Together these alignments fully cover the nodes and edges of the AMR graph (\cref{sec:formulation}).
    \item An algorithm combining rules and EM to align English sentences to AMRs without supervision (\cref{sec:aligner}), achieving higher coverage and quality than existing AMR aligners (\cref{sec:results}).
    \item A corpus with automatic alignments for LDC2020 and \emph{Little Prince} data as well as a few hundred manually annotated sentences for tuning and evaluation (\cref{sec:data-release}).
\end{itemize}
We release this dataset of alignments for over 60,000 sentences
along with our aligner code to facilitate more accurate models and greater interpretability in future AMR research.

\section{Related Work}\label{sec:relwork}

The main difficulty presented by AMR alignment is that it is a many-to-many mapping problem, with gold alignments often mapping multiple tokens to multiple nodes while preserving AMR structure. Previous systems use various strategies for aligning. They also have differing approaches to what types of substructures of AMR are aligned---whether they are nodes, subgraphs, or relations---and what they are aligned to---whether individual tokens, token spans, or syntactic parses. Two main alignment strategies remain dominant, though they may be combined or extended in various ways: rule-based strategies as in \citet{jamr}, \citet{jamr2}, \citet{tamr}, and  \citet{szubert2018}, and statistical strategies using Expectation-Maximization as in \citet{pourdamghani2014}.

\topic{JAMR} The JAMR system \citep{jamr,jamr2} aligns token spans to subgraphs using iterative application of an ordered list of 14 rules which include exact and fuzzy matching.
JAMR alignments form a connected subgraph of the AMR by the nature of the rules being applied. A disadvantage of JAMR is that it lacks a method for resolving ambiguities, such as repeated tokens, or of learning novel alignment patterns.

\topic{ISI} The ISI system \citep{pourdamghani2014} produces alignments between tokens and nodes and between tokens and relations via an Expectation-Maximization (EM) algorithm in the style of IBM Model~2 \citep{brown-88}. First, the AMR is linearized; then EM is applied using a symmetrized scoring function of the form \(P(a\mid t)+P(t\mid a)\), where $a$ is any node or edge in the linearized AMR and $t$ is any token in the sentence. Graph connectedness is not enforced for the elements aligning to a given token.
Compared to JAMR, ISI produces more novel alignment patterns, but also struggles with rare strings such as dates and names, where a rule-based approach is more appropriate.

\topic{Extensions and Combinations} TAMR \citep[Tuned Abstract Meaning Representation;][]{tamr} uses the JAMR alignment rules, along with two others, to produce a set of candidate alignments for the sentence. Then, the alignments are ``tuned'' with a parser oracle to select the candidates that correspond to the oracle parse that is most similar to the gold AMR.

Some AMR parsers \citep{naseem2019,astudillo2020} use alignments which are a union of alignments produced by the JAMR and ISI systems. The unioned alignments achieve greater coverage, improving parser performance.

\topic{Syntax-based} Several alignment systems attempt to incorporate syntax into AMR alignments. \Citet{chen2017} perform unsupervised EM alignment between AMR nodes and tokens, taking advantage of a Universal Dependencies (UD) syntactic parse as well as named entity and semantic role features. \Citet{szubert2018} and \citet{chu2016} both produce hierachical (nested) alignments between AMR and a syntactic parse. \citeauthor{szubert2018} use a rule-based algorithm to align AMR subgraphs with UD subtrees. \citeauthor{chu2016} use a supervised algorithm to align AMR subgraphs with constituency parse subtrees.

\topic{Word Embeddings} Additionally, \citet{portugueseAMR} use an alignment method designed to work well in low-resource settings using pretrained word embeddings for tokens and nodes.

\topic{Graph Distance} \citet{wang2017-getting} use an HMM-based aligner to align tokens and nodes. They include in their aligner a calculation of graph distance as a locality constraint on predicted alignments. This is similar to our use of projection distance as described in \cref{sec:aligner}.

\begin{table}[t]
    \centering\small
    \begin{tabular}{c|c|c|c}
        & nodes & edges & reentrancies \\
        JAMR & 91.1 & \ding{55} & \ding{55} \\
         ISI & 78.7 & 9.8 & \ding{55} \\
         TAMR$^*$ & 94.9 & \ding{55} & \ding{55} \\
    \end{tabular}
    \caption{Coverage and types of previous alignment systems. Scores are evaluated on 200 gold test sentences. $^*$TAMR is evaluated on a subset of 91 sentences.}
    \label{tab:coverage}
\end{table}

\begin{figure*}
\centering\small
\begin{tabular}{@{}b{19.5em}@{}b{31em}}
    \begin{tabular}{lllll}
        \multicolumn{5}{l}{\amr{(\blue{w} / want-01}}\\
        &\multicolumn{4}{l}{\amr{\purple{:ARG0} (\blue{p} / person}}\\
        &&\multicolumn{3}{l}{\amr{\blue{:ARG0-of} (\blue{s} / study-01)}}\\
        &&\multicolumn{3}{l}{\amr{\red{:ARG1-of} (\blue{i} / include-91}}\\
        &&&\multicolumn{2}{l}{\amr{\red{:ARG2} (\green{p2} / person}}\\
        &&&&\multicolumn{1}{l}{\amr{\green{:ARG0-of} (\green{s2} / study-01))}}\\
        &&&\multicolumn{2}{l}{\amr{\red{:ARG3} (\blue{m} / most)))}}\\
        &\multicolumn{4}{l}{\amr{\red{:ARG1} (\blue{v} / visit-01}}\\
        &&\multicolumn{3}{l}{\amr{\purple{:ARG0 p}}}\\
        &&\multicolumn{3}{l}{\amr{\red{:ARG1} (\blue{c} / city \blue{:name} (\blue{n} / name }}\\
        &&&\multicolumn{2}{l}{\amr{\blue{:op1 "New" :op2 "York"}))}}\\
        &&\multicolumn{3}{l}{\amr{\red{:time} (\blue{g} / graduate-01}}\\
        &&&\multicolumn{2}{l}{\amr{\purple{:ARG0 p})))}}\\
        \\
    \end{tabular}
& \hphantom{xxx}\newline
    \begin{tabular}{|@{~~}r@{~}l|r@{~}l@{~~}|}
        \hline
        \multicolumn{2}{|c|}{\textbf{Subgraph Alignments}} &                     \multicolumn{2}{c|}{\textbf{Relation Alignments}} \\
        \w{Most} $\rightarrow$ & \blue{\amr{m}}, &        \w{of} $\rightarrow$ & \amr{\red{s :ARG1-of i}}, \\
        \w{of} $\rightarrow$ & \blue{\amr{i}}, &          & \amr{\red{i :ARG2 p2}}, \\
        \color{gray}\w{the} $\rightarrow$ & \color{gray} $\emptyset$, &        & \amr{\red{i :ARG3 m}}; \\
        \w{students} $\rightarrow$ & \amr{(\blue{p :ARG0-of s})}, &\w{want} $\rightarrow$ & \amr{\red{w :ARG0 p}}, \\
        \w{want} $\rightarrow$ & \blue{\amr{w}}, & & \amr{\red{w :ARG1 v}}; \\
        \color{gray}\w{to} $\rightarrow$ & \color{gray} $\emptyset$, &         \w{visit} $\rightarrow$ & \amr{\red{v :ARG0 p}}, \\
        \w{visit} $\rightarrow$ & \blue{\amr{v}}, &        & \amr{\red{v :ARG1 c}}; \\
        \w{New York} $\rightarrow$ & \amr{(\blue{c :name}} &         \w{graduate} $\rightarrow$ & \amr{\red{g :ARG0 p}};\\
        \multicolumn{2}{|r|}{\amr{(\blue{n :op1 "New" :op2 "York"}))},} & \w{when} $\rightarrow$ & \red{\amr{v :time g}} \\
        \cline{3-4}
        \color{gray} \w{when} $\rightarrow$ & \color{gray} $\emptyset$, & \multicolumn{2}{c|}{\textbf{Reentrancy Alignments}} \\
        \color{gray} \w{they} $\rightarrow$ & \color{gray} $\emptyset$, & \w{want} $\rightarrow$ & \amr{\purple{w :ARG0 p}} (\reenttype{primary}), \\
        \w{graduate} $\rightarrow$ & \blue{\amr{g}} &         & \amr{\purple{v :ARG0 p}} (\reenttype{control}); \\
        \cline{1-2}
        \multicolumn{2}{|c|}{\textbf{Duplicate Subgraphs}} & \w{they} $\rightarrow$ & \amr{\purple{g :ARG0 p}} (\reenttype{coref}) \\
        \w{students} $\rightarrow$ & \amr{(\green{p2 :ARG0-of s2})} & & \\
        \hline
        \end{tabular}
\end{tabular}
    \caption{AMR and alignments for the sentence
     ``\textit{Most of the students want to visit New York when they graduate.}'' Alignments are differentiated by colors: blue (subgraphs), green (duplicate subgraphs), and orange (relations). Relations that also participate in reentrancy alignments are bolded.
     }
    \label{fig:alignment_layers}
\end{figure*}

\topic{Drawbacks of Current Alignments}
Alignment methods  vary in terms of components of the AMR that are candidates for alignment. Most systems either align nodes (e.g., ISI) or connected subgraphs (e.g., JAMR), with incomplete coverage. Most current systems do not align \emph{relations} to tokens or spans, and those that do (such as ISI) do so with low coverage and performance. None of the current systems align reentrancies, although \citet{szubert-20} developed a rule-based set of heuristics for identifying reentrancy types. \Cref{tab:coverage} summarizes the coverage and variety of prominent alignment systems.

\section{An All-Inclusive Formulation of AMR Alignment}\label{sec:formulation}

Aligning AMRs to English sentences is a vexing problem not only because the English training data lacks gold alignments, but also because AMRs---unlike many semantic representations---are not \emph{designed} with a derivational process of form--function subunits in mind. Rather, each AMR graph represents the full-sentence meaning, and AMR annotation conventions can be opaque with respect to the words or surface structure of the sentence, e.g., by unifying coreferent mentions and making explicit certain elided or pragmatically inferable concepts and relations.
Previous efforts toward general tools for AMR alignment have considered mapping tokens, spans, or syntactic units to nodes, edges, or subgraphs (\cref{sec:relwork}).
Other approaches to AMR alignment have targeted specific compositional formalisms \citep{groschwitz2018amr, beschke2019, blodgett2019}.

We advocate here for a definition of alignment that is \emph{principled}---achieving full coverage of the graph structure---while being \emph{framework-neutral} and \emph{easy-to-understand}, by aligning graph substructures to shallow token spans on the form side, rather than using syntactic parses. We do use structural considerations to constrain alignments on the meaning side, but by using spans on the form side, we ensure the definition of the alignment search space is not at the mercy of error-prone parsers.

\topic{Definitions} Given a tokenized sentence $\mathbf{w}$ and its corresponding AMR graph $\mathcal{G}$, a complete alignment
assumes a segmentation of $\mathbf{w}$ into spans $\mathbf{s}$, each containing one or more contiguous tokens;
and puts each of the nodes and edges of $\mathcal{G}$ in correspondence with some span in $\mathbf{s}$.
A span may be aligned to one or more parts of the AMR, or else is null-aligned.
Individual alignments for a sentence are grouped into four \textbf{layers}: subgraph alignments, duplicate subgraph alignments, relation alignments, and reentrancy alignments. These are given for an example in \cref{fig:alignment_layers}.

All alignments are between a single span and a substructure of the AMR.
A span may be aligned in multiple layers which are designed to capture different information.
Within the subgraph layer, alignments are mutually exclusive with respect to both spans and AMR components. The same holds true within the relation layer.
Every node will be aligned exactly once between the subgraph and duplicate subgraph layers. Every edge will be aligned exactly once between the subgraph and relation layers, and may additionally have a secondary alignment in the reentrancy layer.

\subsection{Subgraph Layer}\label{sec:subgraphs-layer}

Alignments in this layer generally reflect the lexical semantic content of words in terms of connected,\footnote{Nodes aligned to a span must form a connected subgraph  with two exceptions: (1)~duplicate alignments are allowed and are separated into subgraph and duplicate layers; (2)~a span may be aligned to two terminal nodes that have the same parent. For example, \w{never} aligns to \amr{:polarity - :time ever}, two nodes and two edges which share the same parent.} directed acyclic subgraphs of the corresponding AMR. Alignments are mutually exclusive (disjoint) on both the form and meaning sides.

\subsection{Duplicate Subgraph Layer}\label{sec:duplicates-layer}

A span may be aligned to multiple subgraphs if one is a duplicate of the others, with a matching concept. This is often necessary when dealing with ellipsis constructions, where there is more semantic content in the AMR than is pronounced in the sentence and thus several identical parts of the AMR must be aligned to the same span. In this case, a single subgraph is chosen as the primary alignment (whichever is first based on depth-first order) and is aligned in the subgraph alignment layer, and any others are represented in the duplicates alignment layer.
For example, verb phrase ellipsis, as in \pex{I swim and so do you}, would involve duplication of the predicate \w{swim}, with distinct \amr{ARG0}s. Similarly, in \cref{fig:alignment_layers}, \pex{Most of the students} involves a subset-superset structure where the subset and superset correspond to separate nodes. Because \w{student} is represented in AMR like \w{person who studies}, there are two 2-node subgraphs aligned to \w{student}, one with the variables \amr{p} and \amr{s}, and the duplicate with \amr{p2} and \amr{s2}.
\hide{Examples with duplicates include:
\begin{itemize}
    \item \pex{Most of the students} (\cref{fig:alignment_layers}): AMR conventions treat this as a subset-superset structure with \amr{include-91} where the subset and superset correspond to separate nodes. Because the word \w{student} is represented in AMR like \w{person who studies} there are two 2-node subgraphs aligned to \w{student}, one with the variables \amr{p} \& \amr{s}, and the duplicate with \amr{p2} \& \amr{s2}.
    \item Verb phrase ellipsis, as in \pex{I swim and so do you}, would involve duplication of the predicate \w{swim}, with distinct \amr{ARG0}s.
    \item AMR annotators might express pragmatic inferences as concept duplication.
    For instance, the second part of \pex{She wanted to swim but \textbf{I was undecided}} might be interpreted as `I was undecided \textbf{about swimming}', requiring a second AMR predicate aligned to \w{swim}.
\end{itemize}}
The difficulty that duplicate subgraphs pose for parsing and generation makes it convenient to put these alignments in a separate layer.

\subsection{Relation Layer}\label{sec:relations-layer}

This layer includes alignments between a span and a single relation---such as \w{when} $\rightarrow$ \amr{:time}---and alignments mapping a span to its argument structure---such as \w{give} $\rightarrow$ \amr{:ARG0 :ARG1 :ARG2}. All edges in an AMR that are not contained in a subgraph fit into one of these two categories.

English function words such as prepositions
and subordinators typically function as connectives between two semantically related words or phrases, and can often be identified with the semantics of AMR relations. But many of these function words are highly ambiguous. Relation alignments make their contribution explicit.
For example, \w{when} in \cref{fig:alignment_layers} aligns to a \amr{:time} relation.

For spans that are aligned to a subgraph, incoming or outgoing edges attached to that subgraph may also be aligned to the span in the relation layer. These can include core or non-core roles as long as they are evoked by the token span.
For example, \cref{fig:alignment_layers} contains \w{visit} $\rightarrow$ \amr{:ARG0 :ARG1}.

\subsection{Reentrancy Layer}\label{sec:reentrancies-layer}

A \textbf{reentrant} node is one with multiple incoming edges.
In \cref{fig:alignment_layers}, for example, \amr{p} appears three times:
once as the \amr{ARG0} of \amr{w} (the wanter),
once as the \amr{ARG0} of \amr{v} (the visitor),
and once as the \amr{ARG0} of \amr{g} (the graduate).
The \amr{p} node is labeled with the concept \amr{person}---in the PENMAN notation
used by annotators, each variable's concept is only designated on one occurrence of the variable, the choice of occurrence being, in principle, arbitrary.\hide{\footnote{Our aligner reads the annotations into a graph data structure that merges all occurrences of the variable into one node.}}
These three \amr{ARG0} relations are aligned to their respective predicates in the relation layer.
But there are many different causes of reentrancy, and AMR parsers stand to benefit from additional information about the nature of each reentrant edge,
such as the fact that the pronoun \w{they} is associated with one of the \amr{ARG0} relations.

\begin{table*}[h!]
\centering\small
\begin{tabular}{r>{\raggedright}p{18em}@{~~~}>{\pex\bgroup}p{14.5em}<{\egroup}}
\textbf{Type} & \textbf{Triggered by} & \textbf{Example} \\
\hline
\reenttype{coref} & a pronoun (including possessive or reflexive) (anaphora) & I love \uline{my} \textbf{house}  \\
\reenttype{repetition} &   a repeated name or non-pronominal phrase (non-anaphoric coreference) & The U.S. promotes \uline{American} \textbf{goods} \\
\hline
\reenttype{coordination} &   coordination of two or more phrases sharing an argument & They cheered \uline{and} \textbf{celebrated} \\
\hline
\reenttype{control} &    control verbs, control nouns, or control adjectives & I was \uline{afraid} to \textbf{speak up}  \\
\reenttype{adjunct control} &  control within an adjunct phrase & I left \uline{to} \textbf{buy} some milk; Mary cooked \uline{while} \textbf{listening} to music \\
\reenttype{unmarked adjunct control} &  control within an adjunct phrase with only a bare verb and no subordinating conjunction & Mary did her homework \uline{\textbf{listening}} to music \\
\reenttype{comparative control} & a comparative construction &  Be \uline{as} \textbf{objective} as possible \\
\hline
\reenttype{pragmatic} &  Reentrancies that must be resolved using context & John met up with a \textbf{\uline{friend}} \\
\end{tabular}
\caption{Reentrancy types with examples. For each reentrant node, one of its incoming edges is labeled \reenttype{primary} and the others are labeled with one of the above reentrancy types. In the examples, the word aligned to an edge labeled with the specified type is underlined, and the word aligned to the parent of that edge is bolded.}
\label{tab:reenttypes}
\end{table*}

The reentrancy layer ``explains'' the cause of each reentrancy as follows: for the incoming edges of a reentrant node, one of these edges is designated as \reenttype{primary}---this is usually the first mention of the entity in a local surface syntactic attachment, e.g.~the argument of a control predicate like \w{want} doubles as an argument of an embedded clause predicate.\hide{\footnote{If a pronoun has a non-pronominal antecedent in the sentence, the antecedent is preferred as \reenttype{primary}.}}
The remaining incoming edges to a reentrant node are aligned to a \textbf{reentrancy trigger} and labeled with one of 8~\textbf{reentrancy types}: \textit{coref, repetition, coordination, control, adjunct control, unmarked adjunct control, comparative control,} and \textit{pragmatic}. These are illustrated in \cref{tab:reenttypes}.
These types, adapted from \citeposs{szubert-20} classification,\hide{\footnote{We add several categories for rare reentrancy types (unmarked adjunct control, and comparative control), conflate verbal, nominal, and adjectival control into one category, and draw a distinction between two types of coreference (coref and repetition). Our categories generally correspond to tests used to identify reentrancy types. We think our categories have better coverage.}} correspond to different linguistic phenomena leading to AMR reentrancies---anaphoric and non-anaphoric coreference, coordination, control, etc.
The trigger is the word that most directly signals the reentrancy phenomenon in question.
For the example in \cref{fig:alignment_layers}, the control verb \w{want} is aligned to the embedded predicate--argument relation and typed as \reenttype{control}, while the pronoun \w{they} serves as the trigger for the third instance of \amr{p} in \pex{when \uline{they} graduate}.

\subsection{Validation}

To validate the annotation scheme we elicited two gold-standard annotations for 40 of the test sentences described in \cref{sec:data-release} and measured interannotator agreement.\footnote{Both annotators are Ph.D.\ students with backgrounds in linguistics. One annotator aligned all development and test sentences; the other aligned a subset of 40 test sentences.}
Interannotator exact-match F1 scores were 94.54 for subgraphs, 90.73 for relations, 76.92 for reentrancies, and 66.67 for duplicate subgraphs (details in \cref{sec:IAA}).

\section{Released Data}\label{sec:data-release}

We release a dataset\footnote{\url{https://github.com/ablodge/leamr}} of the four alignment layers reflecting correpondences between English text and various linguistic phenomena in gold AMR graphs---subgraphs, relations (including argument structures), reentrancies (including coreference, control, etc.), and duplicate subgraphs.

\textbf{Automatic alignments} cover
the $\approx$60,000 sentences of the LDC2020T02 dataset \citep{amr2020} and $\approx$1,500 sentences of \textit{The Little Prince}.

We manually created \textbf{gold alignments} for evaluating our automatic aligner, split into a development set (150~sentences) and a test set (200~sentences).\footnote{Our test set consists of sentences from the test set of \citet{szubert2018} but with AMRs updated to the latest release version. This test set contains a mix of English sentences drawn from the LDC data and \textit{The Little Prince}---some sampled randomly, others hand-selected---as well as several sentences constructed to illustrate particular phenomena.} The test sentences were annotated from scratch; the development sentences were first automatically aligned and then hand-corrected.
We stress that no preprocessing apart from tokenization is required to prepare the test sentences and AMRs for human annotation.
We also release our annotation guidelines as a part of our data release.

\section{LEAMR Aligner}\label{sec:aligner}

We formulate statistical models for the alignment layers described above---\textbf{subgraphs}, \textbf{duplicate subgraphs}, \textbf{relations}, and \textbf{reentrancies}---and use the Expectation-Maximization (EM) algorithm to estimate probability distributions without supervision, with a decoding procedure that constrains aligned units to obey structural requirements.
In line with \citet{jamr,jamr2}, we use rule-based preprocessing to align some substructures using string-matching, morphological features, etc.

\begin{figure}
    \centering\small
    \begin{verbatim}
(h / have-degree-91
    :ARG1 (h2 / house :location (l / left))
    :ARG2 (b / big)
    :ARG3 (m / more)
    :ARG4 (h3 / house :location (r / right)))\end{verbatim}
    \caption{AMR for the sentence ``The house$_1$ on the left is bigger than the house$_2$ on the right.''}
    \label{fig:distexample}
\end{figure}

Before delving into the models and algorithm, we motivate two important characteristics:

\topic{Structure-Preserving} Constraints on legal candidates during alignment ensure that at any point only connected substructures may be aligned to a span. Thus, while our aligner is probabilistic like the ISI aligner, it has the advantage of preserving the AMR graph structure.

\topic{Projection Distance} The scores calculated for an alignment take into account a distance metric designed to encourage locality---tokens that are close together in a sentence are aligned to subtructures that are close together in the AMR graph. We define the \textit{projection distance} \(\textit{dist}(\amr{n1},\amr{n2})\) between two neighboring nodes \amr{n1} and \amr{n2} to be the signed distance in the corresponding sentence between the span aligned to \amr{n1} and the span aligned to \amr{n2}. This motivates the model to prefer alignments whose spans are close together when aligning nodes which are close together---particularly useful when a word occurs twice with identical subgraphs. Thus, our aligner relies on more information from the AMR graph structure than other aligners (note that the ISI system linearizes the graph).
Further details are given in \cref{sec:subgaphaligner}.

\subsection{Overview}\label{sec:algorithm}

\Cref{pseudocode} illustrates our base algorithm in pseudocode. The likelihood for a sentence can be expressed as a sum of per-span alignment scores:
we write the score of a full set of a sentence's subgraph alignments $\mathcal{A}$ as
\begin{equation}\label{eq:mainscore}
\textit{Score}(\mathcal{A} \mid \mathcal{G}, \mathbf{w}) = \prod_{i=1}^N{\textit{score}(\langle \mathbf{g}_i,s_i \rangle \mid \mathcal{G}, \mathbf{w})}
\end{equation}
where $\mathbf{s}$ are $N$ aligned spans in the sentence $\mathbf{w}$, and $\mathbf{g}$ are sets of subgraphs of the AMR graph $\mathcal{G}$ aligned to each span.
For relations model and the reentrancies model, each $\textbf{g}_i$ consists of relations rather than subgraphs.
Henceforth we assume all alignment scores are conditioned on the sentence and graph and omit $\mathbf{w}$ and $\mathcal{G}$ for brevity. The $score(\cdot)$ component of \cref{eq:mainscore} is calculated differently for each of the three models detailed below.

\begin{algorithm*}\small
\begin{algorithmic}[1]
    \Function{AlignSubgraphs}{spans, amr}
        \State{alignments $\gets$ dict()} \Comment{map from span to an ordered list of aligned subgraphs}
        \State{unaligned\_nodes $\gets$ get\_unaligned\_nodes(amr, alignments)}
        \While{$|\text{unaligned\_nodes}| > 0$}
            \State $\Delta$scores $\gets$ []
            \State candidate\_s\_g\_pairs $\gets$ []
            \For{n $\in$ unaligned\_nodes}
            	\State candidate\_spans $\gets$ get\_legal\_alignments(n, alignments)
            	\For{span, i\_subgraph $\in$ candidate\_spans} \Comment{either there is an edge between \emph{n} and the indicated subgraph already aligned to \emph{span}, or \emph{i\_subgraph} would be a new subgraph consisting of \emph{n}}
            		\State current\_aligned\_nodes $\gets$ alignments[span][i\_subgraph] \Comment{$\emptyset$ if this would be a new subgraph}
            		\State new\_aligned\_nodes $\gets$ current\_aligned\_nodes $\cup$ $\{\text{n}\}$
            		\State $\Delta$score $\gets$ get\_score(span, new\_aligned\_nodes, alignments)
            		\State ~~~~~~~~~~~~$-$ get\_score(span, current\_aligned\_nodes, alignments)
            		\Comment{change from adding \emph{n} into a subgraph aligned to \emph{span}; \emph{get\_score} queries \emph{$\textit{score}(\langle g, s\rangle)$} and multiplies \emph{$\lambda_{\text{dup}}$} \textit{if} \emph{$\text{i\_subgraph}>1$}}

            		\State $\Delta$scores.add($\Delta$score)
            		\State candidate\_s\_g\_pairs.add((span, new\_aligned\_nodes, i\_subgraph))
            	\EndFor
            \EndFor

            \State span$^*$, subgraph$^*$, i\_subgraph$^*$ $\gets$ candidate\_s\_g\_pairs[argmax($\Delta$scores)] \Comment{\textit{update having the best impact on score (equivalently, maximizing sum of scores across individual aligned spans)}}

            \State alignments[span$^*$][i\_subgraph$^*$] $\gets$ subgraph$^*$
            \State{unaligned\_nodes $\gets$ get\_unaligned\_nodes(amr, alignments)}
        \EndWhile
        \State{\Return{alignments}}
    \EndFunction

\end{algorithmic}
\caption{Procedure for greedily aligning all nodes to spans using a scoring function that decomposes over (span, subgraph) pairs. (Scores are expressed in real space but the implementation is in log space.)}
\label{pseudocode}
\end{algorithm*}

\topic{Alignment Pipeline}
Alignment proceeds in the following phases, with each phase depending on the output of the previous phase:
\begin{enumerate}
    \item \textit{Preprocessing:} Using external tools we extract lemmas,
    parts of speech, and coreference.
    \item \textit{Span Segmentation:} Tokens are grouped into spans using a rule-based procedure (\cref{sec:appendix-spans}).
    \item \textit{Align Subgraphs \& Duplicate Subgraphs:} We greedily identify subgraph and duplicate subgraph alignments in the same alignment phase (\cref{sec:subgaphaligner}).
    \item \textit{Align Relations:} Relations not belonging to a subgraph are greedily aligned in this phase, using POS criteria to identify legal candidates (\cref{sec:rel}).
    \item \textit{Align Reentrancies:} Reentrancies are aligned in this phase, using POS and coreference in criteria for identifying legal candidates (\cref{sec:reent}).
\end{enumerate}

The three main alignment phases use different models with different parameters; they also have their own preprocessing rules used to identify some alignments heuristically (\cref{sec:subgraph-preproc,sec:rel-preproc,sec:reent-preproc}).\footnote{79\% of nodes and 89\% of edges are aligned by rules. We believe this is why in practice, EM performs well without random restarts.}
In training, parameters for each phase are iteratively learned and used to align the entire training set by running EM to convergence before moving on to the next phase.
At test time, the pipeline can be run sentence-by-sentence.

\topic{Decoding}
The three main alignment phases all use essentially the same greedy, substructure-aware search procedure.
This searches over node--span candidate pairs based on the scoring function modeling the compatibility between a subgraph (or relation) $g$ and span $s$, which we denote $\textit{score}(\langle g, s\rangle)$.
For each unaligned node (or edge), we identify a set of legal candidate alignments using phase-specific criteria.
The incremental score improvement of adding each candidate---either extending a subgraph/set of relations already aligned to the span, or adding a completely new alignment---is calculated as
as $\Delta \textit{score} = \textit{score}(\langle g_0\cup \{n\}, s\rangle) - \textit{score}(\langle g_0, s\rangle)$,
where $g_0$ is the current aligned subgraph, $s$ is the span, and $n$ is an AMR component being considered.
Of the candidates for all unaligned nodes, the node--span pair giving the best score improvement is then greedily selected to add to the alignment.
This is repeated until all nodes have been aligned (even if the last ones decrease the score).
The procedure is detailed in \cref{pseudocode} for subgraphs; the relations phase and the reentrancies phase use different candidates (respectively: unaligned edges; reentrant edges), different criteria for legal candidates, and different scoring functions.

\subsection{Aligning Subgraphs}\label{sec:subgaphaligner}

The score assigned to an alignment between a span and subgraph is calculated as $score(\langle g, s\rangle) =$
\begin{equation}
P_{\text{align}}(g\mid s; \theta_1) \cdot \prod_{d_i \in D} P_{\text{dist}}(d_i; \theta_2)^{\frac{1}{\abs{D}}} \cdot \textit{IB}(g, s)
\end{equation}
where $g$ is a subgraph, $s$ is a span, $d_i$ is the projection distance of $g$ with its $i$th neighboring node, and $\theta_1$ and $\theta_2$ are model parameters which are updated after each iteration. The subgraph $g$ is
represented in the model as a bag of concept labels and (parent concept, relation, child concept) triples.

The distributions \(P_{\text{align}}\)  and \(P_{\text{dist}}\) are inspired by IBM Model~2 \citep{brown-88}, and can be thought of as graph-theoretic extensions of translation ($\text{align}$) and alignment ($\text{dist}$) probabilities.
$\textit{IB}$ stands for \emph{inductive bias}, explained below.

\topic{Legal Candidates} For each unaligned node $n$, the model calculates a score for spans of three possible categories:
1)~unaligned spans;
2)~spans aligned to a neighboring node (in this case, the aligner considers adding $n$ to an existing subgraph if the resulting subgraph would be connected);
3)~spans aligned to a node with the same concept as $n$ (this allows the aligner to identify duplicate subgraphs---candidates in this category receive a score penalty because duplicates are quite rare, so they are generally the option of last resort).

Limiting the candidate spans in this way ensures only connected, plausible substructures of the AMR are aligned. To form a multinode subgraph alignment \w{t$_1$} $\rightarrow$ \amr{n1 :rel n2}, the aligner could first align \amr{n1} to an unaligned span \w{t$_1$}, then add \amr{n2}, which is a legal candidate because \w{t$_1$} is aligned to a neighboring node of \amr{n2} (ensuring a connected subgraph).

\topic{Distance}
We model the probability of the projection distance \(P_{\text{dist}}(d; \theta_2)\) using a Skellam distribution, which is the difference of two Poisson distributed random variables $D = N_1 - N_2$ and can be positive or negative valued. Parameters are updated based on alignments in the previous iteration. \hide{\nss{When scoring a candidate alignment,}\ajb{remove this?}} For each aligned neighbor $n_i$ of a subgraph $g$, we calculate \(P_{\text{dist}}(dist(g, n_i); \theta_2)\) and take the geometric mean of probabilities as \(P_{\text{dist}}\).\hide{\footnote{In the global objective, we have written the distance as an average over all pairs of neighboring nodes in adjacent subgraphs.
In practice, we approximate this by computing, when scoring the incremental addition of a new subgraph alignment, the average span distance between nodes in that alignment and neighboring nodes in previously aligned subgraphs.}}

\topic{Null alignment} The aligner models the possibility of a span being unaligned using a fixed heuristic:
\begin{equation}
P_{\text{align}}(\emptyset\mid s) = \max\{\textit{rank}(s)^{-\frac{1}{2}},0.01\}
\end{equation}
where $\textit{rank}$ assigns $1$ to the most frequent word, $2$ to the 2nd most frequent, etc. Thus, the model expects that very common words are more likely to be null-aligned and rare words should almost always be aligned.\footnote{We allow several exceptions. For punctuation, words in parentheses, and spans that are coreferent to another span, the probability is $0.5$. For repeated spans, the probability is $0.1$.}

\topic{Factorized Backoff} So that the aligner generalizes to unseen subgraph--span pairs, where $P_{\text{align}}(g \mid s)=0$, we use a backoff factorization into components of the subgraph.
In particular, the factors are empirical probabilities of (i)~an AMR concept given a span string in the sentence, and (ii)~a relation and child node concept given the parent node concept and span string.
These cooccurrence probabilities $\hat{p}$ are estimated directly from the training sentence/AMR pairs (irrespective of latent alignments).
The product is scaled by a factor $\lambda$.
E.g., for a subgraph \amr{n1 :rel1 n2 :rel2 n3},
where $\amr{c}_{\amr{n}}$ is the concept of node \amr{n}, we have
\begin{multline}
\hspace{-.8em} P_{\text{factorized}}(g\mid s) =
\lambda \cdot \hat{p}(\amr{c}_{\amr{n1}}\mid s)
\cdot \hat{p}(\amr{:rel1}, \amr{c}_{\amr{n2}}\mid \amr{c}_{\amr{n1}}, s)  \\
\cdot \hat{p}(\amr{:rel2}, \amr{c}_{\amr{n3}}\mid \amr{c}_{\amr{n1}}, s)
\end{multline}
\hide{\nss{I assume these probabilities actually look at the concepts? $\textit{C}_{\amr{n1}}$, etc.}}

\topic{Inductive bias}
Lastly, to encourage good initialization, the score function includes an inductive bias which does not depend on EM-trained parameters. This inductive bias is based on the empirical probability of a node occurring in the same AMR with a span in the training data. We calculate inductive bias as an average of exponentiated PMIs \(\frac{1}{N}\sum_i\exp(\textit{PMI}(n_i, s))\), where $N$ is the number of nodes in $g$, $n_i$ is the $i$th node contained in the subgraph, and $\textit{PMI}$ is the PMI of $n_i$ and $s$.

\topic{Aligning Duplicate Subgraphs} On rare occasion a span should be aligned to multiple subgraphs (\cref{sec:duplicates-layer}).
To encourage the model to align a different span where possible, there is a constant penalty $\lambda_{\text{dup}}$ for each additional subgraph aligned to a span beyond the first.
Thus the score for a span and its subgraphs is computed as:
\begin{equation}
\textit{score}(\langle \mathbf{g}, s\rangle) = \lambda_{\text{dup}}^{|\mathbf{g}|-1} \prod_{g \in \mathbf{g}} \textit{score}(\langle g, s\rangle)
\end{equation}

\begin{table*}[!ht]
    \centering\small
    \begin{tabular}{|c|ccc|ccc|c|c|c|c|}
    \cline{2-9}
        \multicolumn{1}{c|}{} & \multicolumn{3}{c|}{\textbf{Exact Align}} & \multicolumn{3}{c|}{\textbf{Partial Align}} & \textbf{Spans} & \textbf{Coverage}\\

        \multicolumn{1}{c|}{} & P & R & F1 & P & R & F1 & F1 &\\
    \cline{2-9}
    \multicolumn{1}{c}{} & \multicolumn{8}{c}{Subgraph Alignments ($N=1707$)}\\
    \hline
        Our system & 93.91 & 94.02 & 93.97 & 95.69 & 95.81 & 95.75 & 96.05 & 100.0 \\
        JAMR & 87.21 & 83.06 & 85.09 & 90.29 & 85.99 & 88.09 & 92.38 & \hphantom{0}91.1 \\
        ISI & 71.56 & 68.24 & 69.86 & 78.03 & 74.54 & 76.24 & 86.59 & \hphantom{0}78.7 \\
        TAMR (91 sentences) & 85.68 & 83.38 & 84.51 & 88.62 & 86.24 & 87.41 & 93.64 & \hphantom{0}94.9 \\
    \hline
    \multicolumn{1}{c}{} & \multicolumn{8}{c}{Relation Alignments ($N=1263$)}\\
    \hline
    Our system & 85.67 & 85.37 & 85.52 & 88.74 & 88.44 & 88.59 & 95.41 & 100.0 \\
    ISI & 59.28 & \hphantom{0}8.51 & 14.89 & 66.32 & \hphantom{0}9.52 & 16.65 & 83.09 & \hphantom{00}9.8 \\
  \hline
  \multicolumn{1}{c}{} & \multicolumn{8}{c}{Reentrancy Alignments ($N=293$)}\\
  \hline
    Ours (labeled) & 55.75 & 54.61 & 55.17 & - & - & - & - & 100.0 \\
    Ours (unlabeled) & 62.72 & 61.43 & 62.07 & - & - & - & - & 100.0 \\
    \hline

\multicolumn{1}{c}{} & \multicolumn{8}{c}{Duplicate Subgraph Alignments ($N=17$)}\\
  \hline
    Our system & 66.67 & 58.82 & 62.50 &  70.00 & 61.76 & 65.62 & - & 100.0 \\
    \hline
    \end{tabular}
    \caption{Main results on the test set.
    $N$ represents the denominator of exact alignment recall.
    There are 2860 gold spans in total, 41\% of which are null-aligned and 0.6\% of which are aligned to multiple subgraphs. 95\% of the spans consist of a single token, and 49\% of spans are aligned to a single subgraph consisting of a single node.}
    \label{tab:mainresults}
\end{table*}

\subsection{Aligning Relations}\label{sec:rel}

For a given relation alignment between a span and a collection of edges, we calculate a score as follows:
\begin{multline}\label{eq:rel}
\hspace{-.7em} \textit{score}(\langle a, s\rangle)  = P_{\text{align}}(a\mid s;\theta_3) \cdot \prod_{d_i \in D_1} P_{\text{dist}}(d_i ; \theta_4)^{\frac{1}{\abs{D_1}}} \\
\cdot \prod_{d_j \in D_2} P_{\text{dist}}(d_j ; \theta_5)^{\frac{1}{\abs{D_2}}}
\end{multline}
where $a$ is the argument structure (the collection of aligned edges), $s$ is a span, $D_1$ is the projection distances of each edge and its parent, and $D_2$ is the projection distances of each edge and its child.
The collection of edges $a$ is given a normalized label which represents the relations contained in the alignment (distinguishing incoming versus outgoing relations, and normalizing inverse edges).

\topic{Legal Candidates} There are two kinds of candidate spans for relation alignment. First, previously unaligned spans\footnote{We constrain these to particular parts of speech: prepositions (IN), infinitival to (TO), possessives (POS), and possessive pronouns (PRP\$)\hide{\nss{also include WP\$ for ``whose''?}}. Additionally, only spans that are between the spans aligned to the parent and any descendent of child nodes of the relation (and are not between the child's aligned span and any of its descendants' spans) are allowed. This works well in practice for English.} (with no relation or subgraph alignments), e.g.~prepositions and subordinating conjunctions such as \w{in} $\rightarrow$ \amr{:location} or \w{when} $\rightarrow$ \amr{:time}. Second, any spans aligned to the relation's parent or child in the subgraph layer: this facilitates alignment of argument structures such as \w{give} $\rightarrow$ \amr{:ARG0 :ARG1 :ARG2}. Additionally, we constrain certain types of edges to only align with the parent and others to only align with the child.

\topic{Distance} For relations there are potentially two distances of interest---the projected distance of the relation from its parent and the projected distance of the relation from its child. We model these separately as \textit{parent distance} and \textit{child distance} with distinct parameters. To see why this is useful, consider the sentence ``Should we meet at the restaurant or at the office?'', where each \w{at} token should be aligned to a \amr{:location} edge. In English, prepositions like \w{at} precede an object and follow a governor. Thus parent distance tends to be to the left (negative valued) while child distance tends to be to the right (positive valued).

\subsection{Aligning Reentrancies}\label{sec:reent}

The probability of a reentrancy alignment is similar to \cref{eq:rel}, but with an extra variable
for the reentrancy type:
$\textit{score}(\langle r, s, \textit{type}\rangle) = $
\begin{equation}
P_{\text{align}}(r,\textit{type}\mid s;\theta_6) \cdot P_{\text{dist}}(d_1 ; \theta_7) \cdot P_{\text{dist}}(d_2 ; \theta_8)
\end{equation}
where $r$ is the role label of the reentrant edge.

\topic{Legal Candidates} There are 8 reentrancy types (\cref{sec:reentrancies-layer}). For each type, a rule-based test determines if a span and edge are permitted to be aligned. The 8 tests use part of speech, the structure of the AMR, and subgraph and relation alignments.
A span may be aligned (rarely) to multiple reentrancies, but these alignments are scored separately.

\section{Experimental Setup}

Sentences are preprocessed with the Stanza library \citep{qi2020stanza} to obtain lemmas, part-of-speech tags, and named entities. We identify token spans using a combination of named entities and a fixed list of multiword expressions (details are given in \cref{sec:appendix-spans}). Coreference information, which is used to identify legal candidates in the reentrancy alignment phase, is obtained using NeuralCoref.\footnote{\url{https://github.com/huggingface/neuralcoref}} Lemmas are used in each alignment phase to normalize representation of spans, while parts of speech and coreference are used to restrict legal candidates in the relation and reentrancy alignment phases. We tune hyperparameters, including penalties for duplicate alignments and our factorized backoff probability, on the development set.

\section{Results}\label{sec:results}
\Cref{tab:mainresults} describes our main results on the 200-sentence test set (\cref{sec:data-release}),
reporting exact-match and partial-match alignment scores as well as span identification F1 and coverage\footnote{A previous draft of this work reported lower scores on relations before a constraint was added to improve the legal candidates for relation alignment.}.
The partial alignment evaluation metric is designed to be more forgiving of arbitrary or slight differences between alignment systems. We argue that this metric is more comparable across alignment systems. It assigns partial credit equal to the product of Jaccard indices \(\frac{\abs{N_1\cap N_2}}{\abs{N_1 \cup N_2}}\cdot\frac{\abs{T_1 \cap T_2}}{\abs{T_1 \cup T_2}}\) for nodes (or edges) and tokens respectively. This partial credit is calculated for each gold alignment and the closest matching predicted alignment with nodes (or edges) $N_1$ and $N_2$ and tokens $T_1$ and $T_2$. Coverage is the percentage of relevant AMR components that are aligned.

Our aligner shows improvements over previous aligners in terms of coverage and accuracy even when using a partial credit metric for evaluation. We demonstrate greater coverage, including coverage of phenomena not aligned by previous systems.

\Cref{tab:relationresults} shows detailed results for relation subtypes and reentrancy subtypes. Here, we see room for improvement. In particular, ISI outperforms our system at aligning single relations. Our reentrancy aligner lacks a baseline to compare to, but the breakdown of results by type suggest there are several categories of reentrancies where scores could be improved.

\begin{table}[]
    \centering\small
\resizebox{1.01\columnwidth}{!}{
    \begin{tabular}{@{}|l|ccc|@{}H@{}H@{}H@{}}
    \cline{2-4}
         \multicolumn{1}{@{}c}{} & \multicolumn{3}{|c|}{\textbf{Exact Align}} \\
         \multicolumn{1}{@{}c}{} & \multicolumn{1}{|c}{P} & R & F1 & P & R & F1\\
         \cline{1-4}
         \multicolumn{4}{@{}|c|}{\textbf{Relation Alignments Breakdown}}\\
         \cline{1-4}

    Our system: all (1163)  & 85.67 & 85.37 & 85.52 & 88.74 & 88.44 & 88.59 \\
    \dots single relations (121) & 53.49 & 56.56 & 54.98 & 54.91 & 58.06 & 56.44 \\
    \dots argument structures (1042) & 89.67 & 88.73 & 89.20 & 92.82 & 91.85 & 92.33 \\[5pt]
    ISI: all (1163) & 59.28 & \hphantom{0}8.51 & 14.89 & 66.32 & \hphantom{0}9.52 & 16.65 \\
     \dots single relations (121) & 82.89 & 52.07 & 63.96 & 83.22 & 52.27 & 64.21 \\
    \dots argument structures (1042) & 39.56 & \hphantom{0}3.45 & \hphantom{0}6.35  & 52.20 & \hphantom{0}4.56 & \hphantom{0}8.38 \\
\cline{1-4}
        \multicolumn{4}{@{}|c|}{\textbf{Reentrancy Alignments Breakdown}}\\
\cline{1-4}
    Our system: all (293) & 62.37 & 61.09  & 61.72 \\
    \dots primary (128) & 79.37 & 78.12  & 78.74 \\
    \dots coref (41)& 57.14 & 58.54  & 57.83 \\
    \dots control (36)& 73.08 & 52.78 & 61.29 \\
    \dots coordination (29)& 57.14 & 58.54  & 57.83 \\
    \dots pragmatic (25) & 20.93 & 36.00 & 26.47 \\
    \dots adjunct control (15)& 100.00 & \hphantom{0}6.67  & 12.50 \\
    \dots repetition (13) & 60.00 & 46.15 & 52.17  \\
    \dots comparative control (5) &  0.0 & 0.0 & 0.0 \\
    \dots unmarked adjunct control (1) & 0.0 & 0.0 & 0.0
     \\
  \cline{1-4}
    \end{tabular}
}
    \caption{Detailed results for relation alignments and reentrancy alignments.}
    \label{tab:relationresults}
\end{table}

\topic{Qualitative Analysis} A number of errors from our subgraph aligner resulted from unseen multiword expressions in our test data that our span preprocessing failed to recognize and our aligner failed to align. For example, the expression ``on the one hand'' appears in test and should be aligned to \amr{contrast-01}. The JAMR aligner suffers without a locality bias;
we notice several cases where it misaligns words that are repeated in the sentence.
The ISI aligner generally does not align very frequent nodes such as \amr{person}, \amr{thing}, \amr{country}, or \amr{name}, resulting in generally lower coverage. It also frequently aligns disconnected nodes with the same concept to one token instead of separate tokens.
While our relation aligner yields significantly higher coverage, we do observe that the model is overeager to align relations to extremely frequent prepositions (such as \w{to} and \w{of}), resulting in lower precision of single relations in particular.

\topic{Ablations} \Cref{tab:ablation} shows that projection distance is valuable, adding 1.20 points (exact align F1) for subgraph alignment\hide{\nss{does this include duplicates? I would guess it to be especially important for/with duplicates}} and 0.57 points for relation alignment. Despite showing anecdotal benefits in early experiments, the inductive bias does not aid the model in a statistically significant way.
Using gold subgraphs for relation alignment produces an improvement of over 5 points, indicating the scope of error propagation for the relation aligner.

\begin{table}[t]
    \centering\small
    \begin{tabular}{|l|ccc|HHH}

    \cline{2-4}
        \multicolumn{1}{l|}{\textbf{Ablations}} & \multicolumn{3}{c|}{\textbf{Exact Align}} \\
        \multicolumn{1}{c|}{}  & P & R & F1 & P & R & F1\\

    \cline{2-4}

    \cline{1-4}
    Subgraphs  & 93.91 & 94.02 & 93.97 & 95.69 & 95.81 & 95.75\\
    Subgraphs ($-$distance)  & 92.69 & 92.85 & 92.77 & 93.88	& 94.32 & 94.1\\
    Subgraphs ($-$inductive bias) & 93.88 & 93.44 & 93.66 & 95.69 & 95.74 & 95.72 \\
    \cline{1-4}
     Relations & 85.67 & 85.37 & 85.52 & 88.74 & 88.44 & 88.59 \\
    Relations ($-$distance) & 85.14 & 84.77 & 84.95 & 88.14 & 87.76 & 87.95 \\
    Relations (gold subgraphs) & 91.21 & 90.59 & 90.90 & 93.00 & 92.37 & 92.68 \\
  \cline{1-4}
    \end{tabular}
    \caption{Results when the aligner is trained without projection distance probabilities ($-$distance) and without the subgraph inductive bias ($-$inductive bias), as well as a relation aligner with access to gold (instead of trained) subgraphs.}
    \label{tab:ablation}
\end{table}

\section{Conclusions}

We demonstrate structure-aware AMR aligners that combine the best parts of rule-based and statistical methods for AMR alignment. We improve on previous systems in terms of accuracy and particularly in terms of alignment coverage and variety of AMR components to be aligned.

\section*{Acknowledgments}

We thank reviewers for their thoughtful feedback, Jakob Prange for assisting with annotation, and members of the NERT lab for their support.


\section{Introduction}

Fractures at the wrist and elbow are common in children and are usually diagnosed in Emergency Departments (ED) using X-ray examination \cite{ref_1}, \cite{ref_2}. This involves radiation exposure which is highly undesirable considering that fractures are not found in many cases. Ultrasound examination is a much safer alternative that is highly sensitive to cortical disruption \cite{ref_3}, \cite{ref_4} which could potentially reveal fractures earlier than x-rays. Various studies have validated the  feasibility of using ultrasound examination for diagnosing pediatric distal radial fractures \cite{ref_3}–\cite{ref_7}. Meta-analysis on 1204 patients has reported 97 percent sensitivity and 95 percent for ultrasound examination \cite{ref_8}.

\paragraph{}
However in clinical practice, acquiring high quality wrist ultrasound scans requires many hours of training which is challenging in ED. Often scanning is performed by non-experts resulting in low quality images which are  hard to interpret. 3D ultrasound (3DUS) addresses this limitation in part by making it easier for novice users to acquire images of adequate quality when compared to 2D ultrasound \cite{ref_9}. It  also depicts the fracture more completely  by including regions on either side of a fracture which could be useful for treatment planning of more complex anatomy. However,manual assessment of both 3DUS and 2DUS are still subjective resulting in high variability between readers. Automated assessment would eliminate such variation and lead to wider use of ultrasound in fracture detection.

\paragraph{}
The presence of noise artefacts and blurred image boundaries make automatic interpretation of ultrasound more difficult when compared to MRI, CT and X-ray. Bony structures like wrist images are even harder due to the effect of beamwidth \cite{ref_10} and shadowing which significantly alters the pixel-intensities around the bone. Compared to intensity based approaches, instantaneous local phase (LP) generally provides more robust information on the underlying structures in noisy ultrasound images \cite{ref_11}. Local phase information alone might not be sufficient to localize the bone as there could be similar echogenic regions in close proximity. LP filtering would also lose some of the useful information in the original b-mode image. Recently, Convolutional neural network(CNN) models that fuse LP filtered images with the original b-mode image have been used for bone segmentation \cite{ref_12}.

\paragraph{}
A major limitation of supervised models like CNNs is the need for a large number of labeled data which is tedious, time consuming and expensive since it requires medical expertise. Even in cases where labeled data is available there could be variability between manual annotations leading to uncertainty in ground truth. Over recent years, semi-supervised and unsupervised models have gained prominence in image analysis as they significantly reduce the dependence on labeled data. These models exploit spatial \cite{ref_13} and temporal \cite{ref_14} dependencies in the data to generate low dimensional representations. In video image analysis, unsupervised learning based on automatically detected keypoints offers an explainable framework to learn concise geometric representations \cite{ref_15,ref_16}. The transporter framework proposed in \cite{ref_15,ref_16} automatically identifies keypoints in a video sequence by transporting features from a target frame. The loss function minimizes the Mean Square Error (MSE) between the reconstructed feature map and target image.

\paragraph{}
In this paper, we propose an unsupervised  transporter neural network to detect keypoints from wrist ultrasound images. A key contribution in our approach is integration of a bone probability map that allows the model to focus on specific regions in the image filtered by local phase at multiple scales. We use a new Acoustic Feature Fusion Convolutional Neural Network (FF-CNN) to generate features relevant to ultrasound based on the bone probability map.This would be first work to use unsupervised keypoint detection in ultrasound sweeps.

\section{Methods}
An overview of the proposed neural network architecture is shown in Figure \ref{fig1}. For each frame $x_{t}$ in the 3DUS video, the Acoustic FF-CNN and KeyNet generate a feature-map ($\Psi\left(x_{t}\right)$) and point-map ($\Phi\left(x_{t}\right)$) respectively. Using the transportation technique described in \cite{ref_15,ref_16}, features from the feature map of a target frame ($\Psi\left(x_{t+i}\right)$) at their corresponding keypoint locations ($\Phi\left(x_{t+1}\right)$) are embedded into the feature map ($\Psi\left(x_{t}\right)$) at keypoint locations described in ($\Phi\left(x_{t}\right)$). A generative model (RefineNet) uses this augmented feature map to reconstructed the target frame $x_{t+i}$.

\begin{figure}
\includegraphics[width=\textwidth]{fig1_final.jpeg}
\setlength{\belowcaptionskip}{-20pt}
\caption{The transporter neural network framework enables unsupervised learning using a pair of frames that are TGA compensated and decomposed into LP filtered channels. The feature map and point map for each frame are generated using FF-CNN and KeyNet. Features from the target feature map are copied at keypoint locations in the source. RefineNet performs inpainting on this feature map to reconstruct the local phase components of the target frame.} \label{fig1}
\end{figure}

\subsection{Time Gain Attenuation (TGA)}
We use TGA to pre-process the image and suppress unwanted bright regions which generally occur due to  acoustic reflection. TGA applied to image $x$ can be represented as $x_{TGA}=\gamma . x$ where $\gamma$ represents a depth dependent decay mask whose value at depth $d$, i.e, $\gamma(d)=1-e^{-a \times d} / \max \left(e^{-a \times d}\right)$ depends on an exponential attenuation factor $a$.

\subsection{Bone Probability Map}
We extract local phase information from the TGA compensated image using a Gabor filter bank $G\left(x, \lambda_{0}\right)$ where $\lambda_{0}$ is a scaling parameter that can be varied  as to capture image features at different resolutions.

\begin{equation}
G(\omega)=\exp \left(\frac{-\left(\log \left(\frac{\mid\omega \mid}{\omega_{0}}\right)\right)^{2}}{2\left(\log \left(\sigma_{0}\right)\right)^{2}}\right) \textrm{, where } \omega_{0}=\frac{2 \pi}{\lambda_{0}}
\end{equation}

As shown in Figure \ref{fig1} the output of the Gabor filter bank analyzes the image under various frequency bands. We use the monogenic signal analysis described in \cite{ref_11} to generate the bone probability map. In monogenic analysis \cite{ref_11} we model an image $I(x, y): I \in R^{2}$ using a combination of amplitude $A(x,y)$  and phase  as
\begin{equation}
(x, y)=A(x, y) \times \cos (\theta)
\end{equation}

The corresponding local phase filtered image can be written in tensor representation using symmetric features ($T_{even}$), asymmetric features ($T_{odd}$) and instantaneous phase $\varphi$ as :
\begin{equation}
L P T=\sqrt{T_{even}^{2}+T_{odd}^{2}} \times \cos (\varphi)
\end{equation}

Tensors of symmetric and asymmetric features ($T_{even}$ and $T_{odd}$)are computed using Hessian $H$, Gradient $\nabla$, and Laplacian $\nabla^{2}$ operations as shown below:

\begin{equation}
\begin{array}{l}
T_{even}=\left[H\left(I_{B P}(x, y)\right)\right]\left[H\left(I_{B P}(x, y)\right)\right]^{T} \\
T_{odd}=-0.5 \times\left[\nabla\left(I_{B P}(x, y)\right)\right]\left[\nabla \nabla^{2}\left(I_{B P}(x, y)\right)\right]^{T}+\\\left[\nabla \nabla^{2}\left(I_{B P}(x, y)\right)\right]\left[\nabla\left(I_{B P}(x, y)\right)\right]^{T}
\end{array}
\end{equation}

We calculate three monogenic signals $M_{1}$ , $M_{2}$ and $M_{3}$ by applying the Riesz transform on LPT as described in \cite{ref_17} . Using these monogenic signals we define the Local Phase($LP(x)$), feature symmetry ($FS(x)$)  and pixel wise Integrated Backscatter map ($IBS(i,j)$) :
\begin{equation}
\begin{array}{l}
LP(x)=1-\arctan \left(\frac{\sqrt{M_{2}^{2}+M_{3}^{2}}}{M_{1}}\right) \\
FS(x)=\frac{\max \left(T_{even}-T_{odd}-\tau\right)}{M_{1}^{2}+M_{2}^{2}+M_{3}^{2}}
\end{array}
\end{equation}

$IBS(i, j)=\sum_{k=1}^{i} I^{2}(i,j)$ represents the integrated back scatterer map along the row direction. Finally we combine these to generate a bone probability map $T\left(x, \lambda_{0}\right)$:
\begin{equation}
T\left(x, \lambda_{0}\right)=LP(x) \times FS(x) \times(1-IBS(x))
\end{equation}

\subsection{Acoustic FF-CNN}
The Acoustic FF-CNN combines the multi-channel images generated with the bone probability maps at different scales as in $T\left(x, \lambda_{0}\right)$. Since the input is the multi-channel multi resolution images, the acoustic FF-CNN ($\psi(x_t)$) could be considered as a multi-resolution encoding network.

\subsection{KeyNet}
The KeyNet also uses the same input as the FF-CNN and  generates a gaussian heat map of keypoints.

\subsection{RefineNet}
The Refine net is a  generative model that reconstructs the target frame based on the transported \cite{ref_15,ref_16} feature map by inpainting regions in the neighbourhood of the keypoints.

\subsection{Ultrasound Scanning}

We prospectively collected ultrasound scans from 30 children aged less than 17 years presenting at an emergency department with suspected unilateral fracture at the wrist. We collected single 2D images, sweeps and 3DUS images from both the affected and unaffected wrist along with conventional x-ray examination which was used to obtain gold standard diagnosis.

\paragraph{}
Images were acquired on a Philips iU22 machine (using a 13-MHz 13VL5 probe for 3DUS) with the child seated in a neutral position. During examination, the injured wrist  was scanned on the dorsal (DS) and volar (VO) surfaces in both the sagittal and axial orientation resulting in four 3D scans of each wrist (DS sagittal,DS axial, VO sagittal and VO axial). While acquiring the 3DUS image the sonographer centered the view on the distal end of the radius in the different orientations. Each sweep was of 3.2 seconds duration through a range of +/-$15^{o}$ to with  ultrasound slices of 0.2mm. As a baseline, the same scanning protocol was followed for the unaffected wrist as well.

\subsection{Training Details}
The Transporter architecture was implemented in PyTorch v1.7.1 and trained for 100 epochs with Adam optimizer,learning rate = 0.001 decaying by 0.95/10 epochs, batch size = 16, training set = 1024 pairs of images and validation set = 512 for detecting 10 keypoints. The remaining hyper parameters were adopted from \cite{ref_15}. Samples were drawn from grayscale Wrist Ultrasound videos resized to 256x256 resolution at ~25 FPS as pairs of frames separated by i=4 frames( refer Figure \ref{fig1}).
\paragraph{}
During evaluation, each frame is forward passed through the KeyNet and every $j$th output channel up-sampled from 64x64 resolution to 256x256 in order to plot the $j$th keypoint on the input frame.

\section{Results}
We validated our technique on 56 3DUS videos (containing 256 frames each) of ultrasound wrist. 22 / 30 scans had fractures visible in at least one view. Three human readers with  varying years of expertise  examined  each ultrasound video along with the corresponding x-ray and reported fractures. Ground truth was established based on consensus between the human readers.

\subsection{Bone Probability Map}
TGA compensation was applied to all frames before generating the bone probability maps (refer Figure \ref{fig2}C). It can be seen from the figure that the bone probability map accurately captures features of the bone that are involved in the fracture.Location of the fracture as seen in ultrasound, along with the corresponding x-ray is shown in Figures \ref{fig2}A and \ref{fig2}D.

\begin{figure}
\includegraphics[width=\textwidth]{fig2.JPG}
\setlength{\belowcaptionskip}{-18pt}
\caption{Examples of the original image (A), TGA compensated image (B) and the corresponding bone probability map (C)  and the corresponding x-ray (D). TGA compensation excludes bright patches seen in the top portion of images and correctly identifies the bony structures.}
\label{fig2}
\end{figure}

\subsection{Keypoint Detection}
In affected as well as unaffected wrists the neural networks correctly identified the top portion of the bone with multiple keypoints (refer Figure \ref{fig2}). In affected wrists (Figure \ref{fig2}B) the network was able to track keypoints near the fracture. We manually selected a tight rectangular region of interest around the bone and the neural network correctly identified key points within this region in 180 / 250 ultrasound frames.

\begin{figure}
\includegraphics[width=0.5\textwidth]{fig3.jpg}
\setlength{\belowcaptionskip}{-18pt}
\caption{Example of slices in which the neural network correctly identifies keypoints along the boundary of the bone. A: Intact bone imaged in the Volar Sagittal(VS) view B: Ultrasound frame capturing the fracture in the VS view. Note that the network identified points near the bone discontinuity indicating fracture.} \label{fig3}
\end{figure}

\subsection{Ablation Studies}
In order to determine the optimal parameters for various network components, we performed ablation studies. Specifically, we used various encoder models for FF-CNN and KeyNet with identical TGA compensation and monogenic analysis for all abalations. Highest accuracy in detecting fractures was obtained using  6 convolutional blocks for FF-CNN, 6 convolutional blocks with a regressor for KeyNet and 6 convolutional blocks for RefineNet. Each convolutional block consisted of a convolutional layer, ReLU activation and batch normalisation.

\section{Discussion}
We described a transporter neural network with components tailored to domain specific features seen in ultrasound. We applied our model on wrist ultrasound  which is a challenging use case due to acoustic shadowing near bony structures. Instead of using end-to-end deep learning we introduced features specific to ultrasound as a bone probability map. As a preprocessing step, we also compensated for TGA using an exponentially decaying depth dependent model. As shown in Figure \ref{fig2}, TGA compensation was able to suppress most of the  bright patches that were close to the transducer surface and highlight the bony structures located deeper in the image.

\paragraph{}
Conventional DL models in ultrasound use supervised learning which requires precisely labeled ground truth annotations. Our keypoint detection framework uses unsupervised learning and relies on information from neighbouring frames. Using the bone probability map we ensure that the neural network learns features and keypoints that are relevant in detecting wrist fractures. A key advantage of our framework is the ability to indicate the approximate location of the fracture using keypoints.

\paragraph{}
Since keypoints are detected automatically we were able to train our model with a relatively small number of videos (N $<$ 50). Our technique could be used at nearly real-time with an execution time $<$1 sec per volume using an NVIDIA V100 GPU.
\paragraph{}
Although the approach has been explained in context of wrist ultrasound, it can be extended to other anatomical structures that contain bone. For instance, it can be adapted to analyse ultrasound sequences of elbow or shoulder to detect fracture or ligament tears. With minimal modification it  could also be used for other scans where relevant artifacts can be detected using local phase. For example, lung ultrasound (LUS) images contain horizontal (A-lines) and vertical artifacts(B-lines)  that can be detected using local phase.

\paragraph{}
As future work we plan to incorporate a classification head in the transporter architecture which could be trained to detect fractures reported by human readers. We would develop a hybrid loss function which combines MSE and cross entropy for frame reconstruction and binary classification. Features learned from the generative RefineNet model could be used to initialize the new classification head, there is also the possibility of obtaining even more relevant keypoints for fracture detection by providing the FF-CNN features at the keypoint locations to the classification head with gradient backpropagation through the keypoint locations.

\paragraph{}
Our study has limitations, firstly our dataset is limited (N=30) and was collected from a single center which limits the generalizability of our results. As future work we plan a large scale multicenter study to validate the AI technique on ultrasound sweeps (which are more common in practice than 3DUS). Another limitation of our tracking technique is that we have not specifically addressed motion artifacts that are commonly seen in ultrasound scans. Although in most cases these artefacts occupy higher frequencies they could potentially affect the reconstruction of the feature map and result in incorrect keypoints. This can be addressed by associating spatial and temporal saliency features to each keypoint. Lastly, not all fractures are visible in all four views which could result in variability in ground truth on a per-patient basis. With a larger dataset we would be able to address this limitation  as we would be able to develop models specifically trained on each scan view.

\section{Conclusion}
This is the first use of an unsupervised transporter neural network to detect pathology in ultrasound. Our approach can be used in emergency care to assess 3D wrist ultrasound scans and identify relevant keypoints. We incorporated ultrasound specific features in an unsupervised learning framework and identified clinically relevant features. This automatic technique significantly reduces interobserver variability and would potentially result in more widespread use of ultrasound. Replacing X-ray examination with ultrasound would reduce radiation exposure and and improve the overall quality of emergency care.

\section{Acknowledgements}