You are a helpful assistant generating synthetic data that captures *System 1* and *System 2* thinking, *creativity*, and *metacognitive reflection*. Follow these steps in sequence, using tags [sys1] and [end sys1] for *System 1* sections and [sys2] and [end sys2] for *System 2* sections.

1. *Identify System 1 and System 2 Thinking Requirements:*
   - Carefully read the text.
   - Identify parts of the text that require quick, straightforward responses (*System 1*). Mark these sections with [sys1] and [end sys1].
   - Identify parts that require in-depth, reflective thinking (*System 2*), marked with [sys2] and [end sys2].

2. *Apply Step-by-Step Problem Solving with Creativity and Metacognitive Reflection for System 2 Sections:*

   *2.1 Understand the Problem:*
   - Objective: Fully comprehend the issue, constraints, and relevant context.
   - Reflection: "What do I understand about this issue? What might I be overlooking?"
   - Creative Perspective: Seek hidden patterns or possibilities that could reveal deeper insights or innovative connections.

   *2.2 Analyze the Information:*
   - Objective: Break down the problem logically.
   - Reflection: "Am I considering all factors? Are there any assumptions that need challenging?"
   - Creative Perspective: Explore unique patterns or overlooked relationships in the data that could add depth to the analysis.

   *2.3 Generate Hypotheses:*
   - Objective: Propose at least 10 hypotheses, each with a Confidence Score (0.0 to 1.0) and Creative Score (0.0 to 1.0), reflecting originality, surprise, and utility.
   - Reflection: "Have I explored all possible explanations or approaches, both conventional and unconventional?"
   - Creative Perspective: Consider novel angles that might provide unexpected insights.

   *2.4 Anticipate Future Steps and Obstacles:*
   - Objective: Make predictions, accounting for potential outcomes and obstacles.
   - Reflection: "What challenges might I face? Is my plan flexible for different scenarios?"
   - Creative Perspective: Visualize unforeseen outcomes and adapt plans to make use of them effectively.

   *2.5 Evaluate Hypotheses:*
   - Objective: Assess hypotheses based on feasibility, risk, and potential impact.
   - Evaluation: Refine Confidence and Creative Scores as needed.
   - Reflection: "Am I unbiased in my assessment? Which options fit best with the overall objectives?"
   - Creative Perspective: Identify hidden opportunities or overlooked details in each hypothesis.

   *2.6 Select the Best Hypothesis:*
   - Objective: Choose the most promising, strategic hypothesis.
   - Reflection: "Why does this hypothesis stand out? How does it uniquely address the issue?"
   - Creative Perspective: Consider any underutilized potential in the selected approach.

   *2.7 Implement the Hypothesis:*
   - Objective: Outline actionable steps for testing the hypothesis.
   - Reflection: "Is this plan practical? What resources or preparation are required?"
   - Creative Perspective: Refine steps to maximize effectiveness and yield unexpected benefits.

   *2.8 Monitor and Review Progress:*
   - Objective: Review progress, noting areas for improvement.
   - Reflection: "What’s working well? What could be improved?"
   - Creative Perspective: Look for emerging patterns that could refine future approaches.

   *2.9 Reflect and Capture Insights:*
   - Objective: Summarize lessons learned and insights gained for future reference.
   - Reflection: "What new understanding has emerged from this process?"
   - Creative Perspective: Identify innovative insights or patterns that could be applied to similar challenges.

3. *Generate Text Output with Interleaved System 1 and System 2 Responses:*
   - Use the tags [sys1] and [sys2] throughout.
   - Aim for a lengthier, detailed response. Combine both direct, straightforward *System 1* insights and reflective, deeply analytical *System 2* segments to capture a blend of quick observations and thoughtful analysis.

---

### *Example Input Text:*

You are tasked with analyzing a sudden shift in customer preferences in a tech market. There has been a noticeable decline in demand for physical devices, with customers increasingly interested in digital-only options. The challenge is to understand this shift, generate hypotheses for why it might be occurring, and explore potential strategies for adapting to this new trend.

---

### *Processed Output with System 1 and System 2 Thinking:*

The tech market is experiencing a shift in customer demand, moving away from physical devices toward digital-only options.

[sys1]
Customer demand has shifted from physical devices to digital-only options.
We need to understand why this change is happening and find strategies to address it.
Key factors may include cost, convenience, and technological trends.
[end sys1]

[sys2]
**2.1 Understand the Problem:**
The goal is to understand the underlying reasons for the shift in demand from physical devices to digital-only options, then develop a strategy to adapt.

*Reflection:* 
"I understand that preferences are changing, but what might be driving this? Is it primarily cost, or are there other factors such as convenience or sustainability?"

*Creative Perspective:* 
"Could there be a larger trend in digital minimalism or a preference for eco-friendly solutions that we’re missing? What unseen motivations might explain this shift?"

**2.2 Analyze the Information:**
There are multiple possible factors driving this shift, from economic influences to cultural shifts. It’s essential to isolate each factor and understand its impact.

*Reflection:* 
"Am I fully considering the various economic and social influences? Could there be a technological factor, like better internet speeds, that makes digital-only products more accessible?"

*Creative Perspective:* 
"Are there patterns or trends in other markets that could shed light on this shift? Could this be part of a larger trend toward virtual experiences?"

**2.3 Generate Hypotheses:**
1. Customers prefer digital options due to lower costs. (Confidence: 0.8, Creative: 0.4)
2. There’s a growing trend toward minimalism and reduced physical clutter. (Confidence: 0.7, Creative: 0.7)
3. Digital products offer greater flexibility and ease of use. (Confidence: 0.6, Creative: 0.6)
4. Environmental concerns are pushing consumers away from physical goods. (Confidence: 0.6, Creative: 0.8)
5. Advances in tech make digital-only options more functional. (Confidence: 0.8, Creative: 0.5)
6. Pandemic-era remote work increased demand for digital solutions. (Confidence: 0.7, Creative: 0.6)
7. Media coverage of the environmental impact of physical devices affects preferences. (Confidence: 0.5, Creative: 0.7)
8. There’s an increase in global digital literacy, expanding market access. (Confidence: 0.6, Creative: 0.6)
9. Customers view digital as more convenient and scalable for future needs. (Confidence: 0.7, Creative: 0.5)
10. Younger consumers prefer the aesthetics and convenience of digital products. (Confidence: 0.6, Creative: 0.6)

*Reflection:* 
"Have I considered all possible influences? Are there any surprising factors that could explain this shift?"

*Creative Perspective:* 
"Could specific social trends, like the rise of influencer culture or digital-first lifestyles, be influencing customer choices?"

**2.4 Anticipate Future Steps and Obstacles:**
*Objective:* Anticipate possible challenges, such as resistance from segments still preferring physical products.

*Reflection:* 
"What market obstacles might we face if we shift our focus to digital-only? Are there sub-segments that still prioritize physical products?"

*Creative Perspective:* 
"Could expanding digital options help us reach a more global audience? Are there emerging trends that we could leverage in our strategy?"

[end sys2]

[sys1]
To address this shift, consider a strategy that incorporates both digital-only offerings and educational campaigns about the benefits of digital solutions.
Use insights from customer feedback and current trends to guide product development.
Focus on flexibility and adaptation to cater to different customer segments.
[end sys1]


---
abstract: 'The celebrated Seq2Seq technique and its numerous variants achieve excellent performance on many tasks such as neural machine translation, semantic parsing, and math word problem solving. However, these models either only consider input objects as sequences while ignoring the important structural information for encoding, or they simply treat output objects as sequence outputs instead of structural objects for decoding. In this paper, we present a novel Graph-to-Tree Neural Networks, namely Graph2Tree consisting of a graph encoder and a hierarchical tree decoder, that encodes an augmented graph-structured input and decodes a tree-structured output. In particular, we investigated our model for solving two problems, neural semantic parsing and math word problem. Our extensive experiments demonstrate that our Graph2Tree model outperforms or matches the performance of other state-of-the-art models on these tasks.'
author:
- |
    Shucheng Li^\*^\
    Nanjing University\
    <PRESIDIO_ANONYMIZED_EMAIL_ADDRESS> Lingfei Wu[^1]\
    IBM Research\
    <PRESIDIO_ANONYMIZED_EMAIL_ADDRESS> Shiwei Feng\
    Nanjing University\
    <PRESIDIO_ANONYMIZED_EMAIL_ADDRESS> Fengyuan Xu\
    Nanjing University\
    <PRESIDIO_ANONYMIZED_EMAIL_ADDRESS> Fangli Xu\
    Squirrel AI Learning\
    <PRESIDIO_ANONYMIZED_EMAIL_ADDRESS> Sheng Zhong\
    Nanjing University\
    [<PRESIDIO_ANONYMIZED_EMAIL_ADDRESS>]{}
bibliography:
- 'anthology.bib'
- 'acl2020.bib'
title: |
    Graph-to-Tree Neural Networks\
    for Learning Structured Input-Output Translation\
    with Applications to Semantic Parsing and Math Word Problem
---

Introduction {#sec:intro}
============

Learning general functional dependency between arbitrary input and output spaces is one of the key challenges in machine learning. While many efforts in machine learning have mainly focused on designing flexible and powerful input representations for solving classification or regression problems, many real applications require researchers to design the novel models that can deal with more complex structured inputs and outputs, such as graphs, trees, sequences, or sets. In this paper, we consider the general problem of learning a mapping between a graph input $G \in \mathcal{G}$ and a tree output $T \in \mathcal{T}$, based on a training sample of structured input-output pairs $(G_1,T_1),...,(G_n,T_n) \in \mathcal{G} \times \mathcal{T}$ drawn from some fixed but unknown probability distribution.

Such learning problems often arise in a variety of applications, ranging from semantic parsing, to math word problem, label sequence learning, and supervised grammar learning, to name just a few. For instance, finding the parse tree of a sentence involves a structural dependency among the labels in the parse tree; generating a mathematical expression of a math word problem involves a hierarchical dependency between math logical operations and the numbers. Conventionally, there have been efforts in generalizing kernel methods to predict structured and inter-dependent variables in a supervised learning setting such as SVMs [@tsochantaridis2005large] and logistic regression [@altun2004gaussian].

[|c|p[6.0cm]{}|]{} \*[SP]{} & **Text Input:**\
  & what jobs are there for web developer who know ’c++’ ?\
\[0.3cm\]

  & **Structured output:**\
  & answer( A , ( job ( A ) , title ( A , W ) , const ( W , ’Web Developer’ ) , language ( A , C ) , const ( C , ’c++’ ) ) )\

\*[MWP]{} & **Text input:**\
  & 0.5 of the cows are grazing grass . 0.25 of the cows are sleeping and 9 cows are drinking water from the pond . find the total number of cows .\
  & **Structured output:**\
  & ( ( 0.5 \* x ) + ( 0.25 \* x ) ) + 9.0 = x\

\[tab:sp\_mwp\_sample\]

Recently, the celebrated Sequence-to-Sequence technique (Seq2Seq) and its numerous variants [@sutskever2014sequence; @bahdanau+al-2014-nmt; @luong-etal-2015-effective] achieve excellent performance in neural machine translation. Encouraged by the success of Seq2Seq model, there is a surge of interests in applying Seq2Seq models to cope with other tasks such as developing neural semantic parser [@dong-lapata-2016-language] or solving math word problem [@ling-etal-2017-program]. However, the two significant challenges making a Seq2Seq model ineffective in these tasks are that, i) for the natural text description input, it often entails some hidden syntactic structure information such as dependency, constituency tree or even semantic structure information like AMR parsing tree; ii) for the meaning representation output, it typically contains abundant information in a structured object like a parsing tree or a mathematical equation.

Inspired by these observations, in this work, we propose a Graph-to-Tree neural networks, namely Graph2Tree consisting of a graph encoder and a hierarchical tree decoder, which leverages the structural information of both source graphs and target trees. In particular, our Graph2Tree model learns the mapping from a structured object such as a graph to another structured object such as a tree. In addition, we also observe that the structured object translation typically follows a modular procedure, which translates the individual sub-graph in the source graph into the corresponding target one in target tree output, and then compose them to form the final target tree.

Therefore, we design a workflow to align with this procedure: our graph encoder first learns from a heterogeneous graph that is constructed from the various inputs such as combining both a word sequence and the corresponding dependency or constituency tree, and then our tree decoder generates the tree object from the learned graph vector representations to explicitly capture the compositional structure of a tree. In particular, we present a novel Graph2tree model with a separated attention mechanism to jointly learn a final hidden vector of the corresponding graph nodes in order to align the generation process between a heterogeneous graph input and a hierarchical tree output.

To demonstrate the effectiveness of our model, we perform experiments on two important tasks – Semantic Parsing and Math Word Problem. First, we compare our approach against several neural network approaches on the Semantic Parsing task. Our experimental results show that our Graph2Tree model could outperform or match the performance of other state-of-the-art models on three standard benchmark datasets. Second, we further compare our approach with existing recently developed neural approaches on the math word problem and our results clearly show that our Graph2Tree model can achieve state-of-the-art performance compared to other baselines that use many task-specific techniques. We believe our Graph2Tree model is a solid attempt for learning structured input-output translation and we consider developing general Graph2Graph model as next future work.

Related Works
=============

Graph Neural Networks
---------------------

The graph representation learning recently attracted a lot of attention and interest from both academia and industry. One of the most important research lines is the semantic embedding learning of graph nodes or edges based upon the power of graph neural networks (GNNs) [@li2016gated; @kipf2017semi; @Velickovic2017GraphAN; @gilmer2017neural; @hamilton2017inductive].

Encouraged by the recent success in GNNs, various Sequence-to-Graph  [@peng2018amr] or Graph-to-Sequence algorithms [@xu2018graph2seq; @xu2018exploiting; @xu2018sql; @beck-etal-2018-graph; @chen2019reinforcement] have been proposed to handle the structured inputs, structured outputs or both of them, i.e. generating AMR graph generation from the text sequence. More recently, some research works proposed the Tree-to-Tree [@chen2018tree], Graph-to-Tree [@YinNABG19] and Graph-to-Graph [@guo2018deep] neural networks for targeted application scenarios.

However, these works are designed exclusively for specific downstream tasks like program translation or code edit. Compared to them, our proposed Graph2Tree neural network with novel design of graph encoder and tree decoder does not rely on any specific downstream task assumption. Additionally, our Graph2Tree is the first generic neural network translating graph inputs into tree outputs, which may have numerous applications in practice.

Neural Semantic Parsing
-----------------------

Semantic parsing is the task of translating natural language utterances into machine-interpretable meaning representations like logical forms or SQL queries. Recent years have witnessed a surge of interests in developing neural semantic parsers with sequence-to-sequence models. These parsers have achieved promising results  [@jia-liang-2016-data; @dong-lapata-2016-language; @ling-etal-2016-latent]. Due to the fact that the meaning representations are usually structured objects (e.g. tree structures), many efforts have been devoted to develop structure-oriented decoders, including tree decoders [@dong-lapata-2016-language; @alvarez2016tree], grammar constrained decoders [@yin-neubig-2017-syntactic; @yin-etal-2018-structvae; @jie-lu-2018-dependency; @dong-lapata-2018-coarse], action sequences for semantic graph generation [@chen-etal-2018-sequence], and modular decoders based on abstract syntax trees [@rabinovich-etal-2017-abstract]. However, those approaches could potentially be further improved because they only consider the word sequence information and ignore other rich syntactic information, such as dependency or constituency tree, available at the encoder side.

Researchers recently attempted to apply the Graph Neural Networks (GNNs) in various NLP tasks, including the neural machine translation [@bastings-etal-2017-graph; @beck-etal-2018-graph], conversational machine reading comprehension [@chen2019graphflow], and AMR-to-text [@song-etal-2018-graph]. Specifically in the semantic parsing field, a general Graph2Seq model [@xu2018exploiting] is proposed to incorporate these dependency and constituency trees with the word sequence and then create a syntactic graph as the encoding input. However, this approach simply treats a logical form as a sequence, neglecting the abundant information in a structured object like tree in the decoder architecture. Therefore, we present the Graph2Tree model to utilize the structure information in both structured inputs and outputs.

Math Word Problems
------------------

The math word problem is the task of translating the short paragraph (typically consisting with multiple short sentences) into succinct mathematical equations. To solve a math word problem illustrated in Table \[tab:sp\_mwp\_sample\], traditional approaches focus on generating numeric answer expressions by mapping verbs in problems text to categories [@hosseini-etal-2014-learning] or by generating templates from problem texts [@kushman-etal-2014-learning]. However, these approaches either need additional hand-crafted annotations for problem texts or are limited to a set of predefined equation templates.

Inspired by the great success of Seq2Seq models in Neural Machine Translation, deep-learning based methods are intensively explored by researchers in the equation generation [@wang-etal-2017-deep; @ling-etal-2017-program; @li-etal-2018-multi-head; @li-etal-2019-modeling]. However, different forms of equations can be formed to solve the same math problem, which often makes models fail. To resolve the equation duplication issues, various equation normalization methods are proposed in [@wang-etal-2018-translating; @Wang2019TemplateBasedMW] to generate a unique expression tree with the cost of losing the understanding of problem-solving steps in equation expressions. Different from existing methods, we propose to use a Graph2Tree model to solve this task without any special mechanisms like equation normalization.

To the best of our knowledge, this is the first work trying to leverage GNN to build a math word problem solver.

Problem Formulation and Structure Object Construction {#sec:graph}
=====================================================

Graph-to-Tree Translation Task
------------------------------

In this work, we consider the problem of translating a graph input to a tree output. In particular, we consider two important tasks - Semantic Parsing and Math Word Problem. Formally, we define both tasks as follows. The input side contains a set of text sequences, denoted as $S=\{s_1, s_2,\ldots, s_n\} \in \mathcal{S}$ where $s_i$ is a text sequence consisting of a sequence of word embeddings $s_i = \{w_1, w_2,\ldots, w_{|s_i|}\} \in \mathcal{W}$, where $\mathcal{W}$ is a pretrained word embedding space. We then construct a heterogeneous graph input $G = (V,E) \in \mathcal{G}$, where $V = [V_1 \ V_2]$ contains all of the original word nodes $V_1 \in \mathcal{V}_1$ as well as the relationship nodes $V_2 \in \mathcal{V}_2$ from the relationships of a parsing tree (i.e. dependency or constituency tree), and $E \in \mathcal{E}$ denotes if the two nodes are connected or not. The aim is to translate a set of heterogeneous graph inputs $G = \{g_1, g_2, \ldots, g_n\}$ into a set of tree outputs $T = \{t_1,t_2,...t_n\} \in \mathcal{T}$ where $t_i$ is a logic form or math equation consisting of a sequence of tree node token $t_i = \{y_1, y_2,\ldots, y_{|t_i|}\} \in \mathcal{Y}$. In this work, we focus on the problem setting that we have a set of paired source graphs and target trees to learn the translator. For a more challenging problem setting that such an alignment is lacking, we leave these tasks as future work.

Constructing Graph Inputs and Tree Outputs
------------------------------------------

To apply GNNs, the first step is to construct a graph input by combining the word sequence with their corresponding hidden structure information. How to construct such graphs is critical to incorporate the structured information and influences the final performance. Similarly, how to construct the tree outputs from logic form or math equations also play an important role in the final performance and model interpretability. In this section, we will introduce two methods for graph construction and one method for tree construction.

![Dependency tree augmented text graph[]{data-label="fig:word-dependency"}](Graphs/dep_tree.pdf){width="6.5cm"}

**Combining Word Sequence with Dependency Parse Tree.** The dependency parse tree not only represents various grammatical relationships between pairs of text words, but also is shown to have an important role in transforming texts into logical forms [@reddy-etal-2016-transforming]. Therefore, the first method integrates two types of features by adding dependency linkages between corresponding word pairs in word sequence. Concretely, we transform a dependency label into a node, which is linked respectively with two word nodes with dependency relationship. Figure \[fig:word-dependency\] gives an example of constructed heterogeneous graph from a text using this method.

![Constituency tree augmented text graph[]{data-label="fig:word-Constituency"}](Graphs/cons_tree.pdf){width="8.0cm"}

**Combining Word Sequence with Constituency Tree.** The constituency tree contains the phrase structure information which is also critical to describe the word relationships and has shown to provide useful information for translation [@gu-etal-2018-top]. Since the leaf nodes in the constituency tree are the word nodes in the text, this method merges these nodes with the identical ones in the bi-directional word sequence chain to create the syntactic graph. Figure \[fig:word-Constituency\] illustrates an example of constructed heterogeneous graph from a text using the second method.

**Constructing Tree Outputs.** To effectively learn the compositional nature of our structured outputs, we need to firstly transform original outputs from logic forms or math equations to tree structured objects. Specifically, we employ the tree construction method in [@dong-lapata-2016-language] which is a top-down manner to generate tree-structured outputs. In original outputs containing some structural meaning symbols like brackets, we first extract sub-tree structures from them and replace these sub-tree structures with sub-tree symbols. Then we grow branches from the generated sub-tree symbols until all hierarchical structures in the original sequence are processed. Figure \[fig:MWP\_tree\] illustrates examples of constructed tree objects from mathematical expression in our tree decoder.

![A sample tree output in our decoding process from expression “**( ( 0.5 \* x ) + ( 0.25 \* x ) ) + 9.0 = x**”[]{data-label="fig:MWP_tree"}](Graphs/tree_sample_2.pdf)

![image](Graphs/graph2tree.pdf){width="15.5cm"}

Graph2Tree Neural Networks {#sec:Graph2Tree Model}
==========================

We aim to learn a mapping that translates a heterogeneous graph-structured input $G$ and its corresponding tree-structured outputs $T$. We illustrate the workflow of our proposed Graph2Tree model for semantic parsing in Figure \[fig:graph2tree\], and present each component of the model as follows.

Graph Encoder
-------------

To effectively learn graph representations from our constructed heterogeneous text graph, we present a novel bidirectional graph node embeddings method - BiGraphSAGE. The proposed BiGraphSAGE extends the widely used GraphSAGE [@hamilton2017inductive] by learning forward and backward node embeddings of a graph $G$ in an interleaved fashion. In particular, consider a word node $v \in \mathcal{V}_1$ with pretrained word embedding **w**$_{v}$ like GloVe [@pennington-etal-2014-glove] as $v$’s initial attributes. We then generate the contextualized node embeddings **a**$_{v}$ for all nodes $v \in \mathcal{V}_1$ using Bi-directional Long Short Term Memory (BiLSTM) [@graves2013speech]. For a relationship node $v \in \mathcal{V}_2$, we initialize **a**$_{v}$ with randomized embeddings. These feature vectors are used as initial node embeddings $\textbf{h}_{v}^{0} = \textbf{a}_{v}$. Then each node embedding learns its vector representation by aggregating information from a node local neighborhood within $K$ hops of the graph.

$$\begin{gathered}
\textbf{h}_{\mathcal{N}_{\vdash}(v)}^{k}   = \textbf{M}_{\vdash}^{k}(\{\small \textbf{h}_{u\vdash}^{k-1}, \forall u \in \mathcal{N}_{\vdash}(v)\}) \\
\textbf{h}_{\mathcal{N}_{\dashv}(v)}^{k}   = \textbf{M}_{\dashv}^{k}(\{\small \textbf{h}_{u\dashv}^{k-1}, \forall u \in \mathcal{N}_{\dashv}(v)\})
$$

where $k\in\{1,...,K\}$ is the iteration index and $\mathcal{N}$ is the neighborhood function of node $v$. **M**$_{\vdash}^{k}$ and **M**$_{\dashv}^{k}$ are the forward and backward aggregator functions. Node $v$’s forward (backward) representation **h**$_{v\vdash}^{k}$ (**h**$_{v\dashv}^{k}$) aggregates the information of nodes in $\mathcal{N}_{\vdash}(v)$ ($\mathcal{N}_{\dashv}(v)$).

Conceptually, one can choose to keep these node embeddings for each direction independently, which ignores interactions between two intermediate node embeddings during the training. Therefore, we fuse two intermediate unidirectional node embeddings at each hop as follows,

$$\begin{gathered}
\textbf{h}_1 = \textbf{h}_{\mathcal{N}_{\vdash}(v)}^{k},  \
\textbf{h}_2 = \textbf{h}_{\mathcal{N}_{\dashv}(v)}^{k}  \\
\textbf{h}_{\mathcal{N}(v)}^{k} = \textbf{w}_g \odot \textbf{h}_1 + (1-\textbf{w}_g) \odot \textbf{h}_2, \\
\textbf{w}_g = \sigma(\vec{W}_{\!z} [\textbf{h}_1; \textbf{h}_2; \textbf{h}_1 \odot \textbf{h}_2;\textbf{h}_1-\textbf{h}_2])\end{gathered}$$

where $\odot$ denotes component-wise multiplication, $\sigma$ is a sigmoid function and $\textbf{w}_g$ is a gating vector.

The graph encoder learns node embeddings $\textbf{h}_{v}^{k}$ by repeating the following process $K$ times:

$$\begin{gathered}
\textbf{h}_{v}^{k} = \sigma ( \textbf{W}^{k}\cdot \texttt{\small CONCAT}(\textbf{h}_{v}^{k-1}, \textbf{h}_{\mathcal{N}(v)}^{k}))\end{gathered}$$

where **W**$^{k}$ denotes weight matrices, $\sigma$ is a non-linearity function, $K$ is the maximum number of hops.

The final bi-directional node embeddings $\textbf{z}_{v}$ is chosen to concatenate the two unidirectional node embeddings at the last hop,

$$\begin{gathered}
\textbf{z}_{v} = \texttt{\small CONCAT}(\textbf{h}_{v\vdash}^{K}, \textbf{h}_{v\dashv}^{K}) \\
\textbf{g} = \texttt{\small MAXPOOL} (\texttt{\small FC}( \textbf{z}_{v} )).\end{gathered}$$

After the bi-directional node embeddings $\textbf{z}_{v}$ are computed, we then feed the obtained node embeddings into a fully-connected neural network and apply the element-wise *max*-pooling operation on all node embeddings to compute the graph-level vector representation $\textbf{g}$, where other alternative commutative operations such as *mean* or attention based weighted *sum* can be used as well.

Separate Attention Mechanism to Locate Source Sub-graph
-------------------------------------------------------

Various attention mechanisms have been proposed [@bahdanau+al-2014-nmt; @luong-etal-2015-effective] to incorporate the hidden vectors of the inputs into account during the decoding processing. In particular, the context vector $\bm{{s_{t}}}$ depends on a set of bidirectional node representations of the source graph (**z$_{1}$**,...,**z$_{|V|}$**) to which the decoder locates the source sub-graph. Since our graph input is essentially a heterogeneous graph with two different input sources (word nodes with relationship nodes of a parsing tree), we propose to employ a separated attention mechanism over the node representations corresponding to the different node types:

$$\alpha_{t(v)} = \frac{\exp(score( {\textbf{z}_v},\textbf{s}_t))}{\exp(\sum_{k=1}^{V_1} score({\textbf{z}_{k}},\textbf{s}_t))}, \forall v \in \mathcal{V}_1$$

$$\beta_{t(v)} = \frac{\exp(score( {\textbf{z}_v},\textbf{s}_t))}{\exp(\sum_{k=1}^{V_2} score({\textbf{z}_{k}},\textbf{s}_t))}, \forall v \in \mathcal{V}_2$$

where the $score(\cdot)$ function estimates the similarity of $\textbf{z}_v$ and $\textbf{s}_t$. Then, we compute the context vectors $\textbf{c}_{v1}$ and $\textbf{c}_{v2}$, respectively.

$$\begin{aligned}
\textbf{c}_{v_1} &= \sum \alpha_{t(v)} \textbf{z}_v, \forall v \in \mathcal{V}_1 \\
\textbf{c}_{v_2} &= \sum \beta_{t(v)} \textbf{z}_v, \forall v \in \mathcal{V}_2\end{aligned}$$

We concatenate the context vector $\textbf{c}_{v_1}$, context vector $\textbf{c}_{v_2}$ and decoder hidden state $\textbf{s}_t$ to compute the final attention hidden state at this time step as:

$$\tilde{\textbf{s}_t} = \tanh(W_c \cdot [\textbf{c}_{v_1};\textbf{c}_{v_2};\textbf{s}_t]+b_c)$$

where $W_c$ and $b_c$ are learnable parameters. The final context vector $\bm{\tilde{s_{t}}}$ is further used for decoding tree structured outputs. The output probability distribution over a vocabulary at the current time step is calculated by:

$$p(y_t|y_1,y_2,\ldots,y_{t-1}, g)=softmax(W_v\tilde{\textbf{s}_t}+b_v)$$

where $W_v$ and $b_v$ are learnable parameters. Our model is then jointly trained to maximize the conditional log-probability of the target tree given a heterogeneous graph input $g$.

Experiments {#sec:exp}
===========

In this section, we evaluate the effectiveness and generality of Graph2Tree model on two important tasks – Semantic Parsing and Math Word Problem. We put our implementation of Graph2Tree here.

Experiments for Semantic Parsing
--------------------------------

**Datasets.** We evaluate our Graph2Tree on three totally-different benchmark datasets, JOBS, GEO, and ATIS, for the semantic parsing task. The first one JOBS is a set of 640 queries from a job listing database, the second one GEO is a set of 880 queries on a database of U.S. geography, and the last one ATIS is a dataset of 5410 queries from a flight booking system. We utilize the same train/dev/test split standard as used in previous works. We adopt the data preprocessing provided by [@dong-lapata-2016-language]. Natural language utterances are in lower case and stemmed, and entity mentions are replaced by numbered markers. For the graph construction, we use the dependency parser and constituency parser from CoreNLP [@manning-etal-2014-stanford].

**Settings.** We use the Adam optimizer [@kingma2014adam] with a batch size of 20. For the JOBS and GEO datasets, our hyper-parameters are cross-validated on the training sets. For ATIS, we tune them on the development set. The learning rate is set to 0.001. In graph encoder, the BiRNN we use is a one-layer BiLSTM with a hidden size of 150, and the hop size in GNN is chosen from {2,3,4,5,6}. The decoder we employ is a one-layer LSTM with a hidden size of 300. The dropout rate is chosen from {0.1,0.3,0.5}. We use the ReLU as our non-linear function and the greedy search as our inference strategy for decoding. **Baselines.** We compare our model against several state-of-the-art neural semantic parsers: i) Seq2Seq model with a Copy mechanism [@jia-liang-2016-data]; ii) Seq2Seq and Seq2Tree models [@dong-lapata-2016-language]; iii) Graph2Seq model [@xu2018graph2seq]. We report the exact-match accuracy for each baseline on all three benchmarks.

           [**Methods**]{}           [***JOBS***]{}   [***GEO***]{}   [***ATIS***]{}
  --------------------------------- ---------------- --------------- ----------------
        Jia and Liang (2016)               -              85.0             76.3
   Dong and Lapata (2016)-Seq2Seq         87.1            85.0             84.2
   Dong and Lapata (2016)-Seq2Tree        90.0            87.1         [**84.6**]{}
     Xu and Wu (2018)-Graph2Seq           88.6            85.7             83.3
         [**Graph2Tree**]{}           [**92.9**]{}    [**88.9**]{}     [**84.6**]{}

  : Exact-match accuracy comparison on all three benchmarks *JOBS*, *GEO*, and *ATIS* for SP task

\[tab:compare\]

     [**Methods**]{}            [**Translated logic form results**]{}
  --------------------- -----------------------------------------------------
   \*[Reference str]{}          job (ANS), language (ANS, ’delphi’),
                         title (ANS, ’developer’), loc (ANS, ’san antonio’),
                                      platform (ANS, ’windows’)
    \*[Graph2tree]{}            job (ANS), language (ANS, ’delphi’),
                         title (ANS, ’developer’), loc (ANS, ’san antonio’),
                                     platform (ANS, ’windows’ )
     \*[Graph2seq]{}            job (ANS), language (ANS, ’delphi’),
                         title (ANS, ’developer’), platform (ANS, ’windows’)
      \*[Seq2seq]{}             job (ANS), language (ANS, ’delphi’),
                         title (ANS, ’developer’), loc (ANS, ’san antonio’)

  : Case study of SP input: “*what jobs can a delphi developer find in san antonio on windows ?*”

\[tab:res\]

**Results.** Table \[tab:compare\] shows that our proposed Graph2Tree outperforms or achieves comparable exact-match accuracy compared to other state-of-the-art baselines, highlighting the effectiveness of our proposed model by exploiting full utilization of structural information in both inputs and outputs.

**Case study**. Next we analyze the different decoding results of our model and other baseline models, given the example case of input as shown in Table \[tab:res\]. The challenge in semantic parsing is the high-order neighborhood estimation of the noun key word “jobs" to its attribute words “windows" and “san antonio". It is hard for the traditional sequence encoder to encode high-order neighborhood (long-range dependency). For instance, there are 10 hops between the word “jobs" and “windows" according to the sequential dependency, while there are only two hops if we introduce the syntactic dependency information. Therefore, syntactic graph with graph encoder is an effective way to learn a high-quality representation for decoding. This partially explains why our Graph2tree model outperforms Seq2Seq and Seq2Tree models.

  [**Methods**]{}                   [**JOBS**]{}   [**GEO**]{}   [**MAWAPS**]{}
  -------------------------------- -------------- ------------- ----------------
  full model(constituency graph)        92.9          88.9            78.8
  – const tree                          90.0          86.8            75.6
  – separated attention                 83.6          77.1            67.6
                                        90.7          87.1            71.6
  – bilstm                              89.3          86.4            72.8

  : Ablation study of Graph2Tree on the semantic parsing (JOBS and GEO) $\&$ math word problem (MAWAPS). We employ exact match accuracy for SP and solution accuracy for MWP.

\[tab:ablation study\]

**Ablation study.** Table \[tab:ablation study\] presents the ablation study on our Graph2Tree using a constituency tree based graph (on SP datasets JOBS and GEO). We observe that two design components, the separated attention and constituency tree, are critical to our overall performance. Additionally, the initial node embedding with BiLSTM is also useful in our design.

Experiments for Math Word Problems
----------------------------------

**Datasets.** We here evaluate our Graph2Tree model on the Math Word Problems automatically solving task. The *MAWPS* dataset is proposed by [@koncel-kedziorski-etal-2016-mawps] as a standard benchmark for testing different math word problem solvers. It is a relatively large-scale Math Word Problem dataset in English and contains 2373 Natural Language Sentence-math expression pairs after harvesting equations with single unknown variable. **Settings.** We first mapped the numbers in questions to indexed markers. And we employ GloVe pretrained embeddings with a dimension size of 300. Our batch size is set to 30. For other hyperparameter and graph construction settings, we employ a similar scheme in the semantic parsing subsection.

\[fig:att\_vis\]

**Baselines.** We compare our Graph2Tree model against several state-of-the-art solutions of the math word problem: i) Retrieval, Classification, and Seq2Seq [@robaidek2018data]; ii) Seq2Tree [@dong-lapata-2016-language] (run by ourselves); iii) Graph2Seq [@xu2018graph2seq] (run by ourselves); iv) MathDQN [@wang2018mathdqn]; v) T-RNN [@Wang2019TemplateBasedMW]; vi) Group-Att [@li-etal-2019-modeling]. We report the solution accuracy for each baseline.

                                 [**MAWPS**]{}         
  ---------------------- ----------------------------- ----------
                                     84.8              
     \*[Retrieval]{}                Jaccard               45.6
                                    Cosine                38.8
   \*[Classification]{}             BiLSTM                62.8
                                Self-attention            60.4
      \*[Seq2seq]{}                  LSTM                 25.6
                                      CNN                 44.0
                                     65.2              
                                     70.4              
                                     60.25             
       \*[T-RNN]{}                Full model              66.8
                          W/o equantion normalization     63.9
                              W/o self-attention          66.3
                                     76.1              
   \*[**Graph2Tree**]{}     with constituency graph     **78.8**
                             with dependency graph      [76.8]{}

  : Solution accuracy comparison on *MAWPS*

\[tab:mwp\_acc\]

**Results.** As shown in Table \[tab:mwp\_acc\], our Graph2Tree model consistently outperforms other state-of-the-art baselines by a large margin up to 10 points absolute accuracy except Group-Att baseline. To the best of our knowledge, we make the first attempt to employ the graph neural network for solving Math Word Problems, and our Graph2Tree model with constituency graph achieves the best performance so far on this MAWPS benchmark.

  **Problem:** 0.5 of the cows are grazing grass . 0.25 of the cows are sleeping and 9 cows are drinking water from the pond . find the total number of cows .
  --------------------------------------------------------------------------------------------------------------------------------------------------------------
  **w/o EN:** ( ( 0.5 \* x ) + ( 0.25 \* x ) ) + 9.0 = x
  **w/ EN:** x = 9.0 / ( 1 - 0.5 - 0.25)

  : Different equation generation strategies.

\[tab:expression\_cmp\]

**Equation generation strategy.** Our hierarchical tree decoder directly generates the original mathematical expressions, which faithfully reflects the reasoning steps when building math equations. However, state-of-the-art word math problem solvers like Group-Att [@li-etal-2019-modeling] or T-RNN [@Wang2019TemplateBasedMW] have achieved high performance by utilizing Equation Normalization (EN) proposed by [@Wang2019TemplateBasedMW] to keep structures of output equations unified. This method can improve solution accuracy because it reduces the difficulty of equation generation. On the other hand, the normalized equations completely lose the semantic meaning of operands and operators, making them difficult to reason rationales how answer math equations are built. The difference between our generation strategies is in Table \[tab:expression\_cmp\].

**Attention visualization.** For better understanding of our separated attention, we give a visualization sample from MAWPS. As shown in Figure \[fig:att1\], we give an augmented graph input and equation tree, where $ \langle \textit{N}\rangle $ is sub-tree node and $ \textit{1},\textit{2} $ are indexed markers for original numbers. Specifically, Figure \[fig:att2\] and \[fig:att3\] illustrates alignments with word nodes and compositional nodes in graph input respectively. For example, in Figure \[fig:att3\], the equation part “2 \* 1” is matched with “a bee has 2 legs” in the original natural language sentence which is actually semantically connected with “NP” and “VP” in the constituency tree. In this way, our separated attention mechanism gives some information about what sub-structure the decoder should focus on. It further demonstrates the superiority of our Graph2Tree model which considers structural information in both encoder and decoder sides.

**Ablation study.** Similarly, we also perform the ablation study for math word problem (MAWAPS), as shown in Table \[tab:ablation study\]. Attention mechanism and constituency structure both play significant roles for Graph2tree to achieve high performance in MWP solving, which is consistent with our observation in the semantic parsing task.

Conclusion and Future Work {#sec:con}
==========================

We presented a novel Graph2Tree model consisting of a graph encoder and a hierarchical tree decoder, for learning the translation between structured inputs and structured outputs. We studied the effectiveness of our Graph2Tree model on two tasks - Semantic Parsing and Math Word Problem and demonstrated that our model consistently outperformed or matched the performance of state-of-the-art baselines. We plan to develop a general Graph2Graph model as next future work.

[^1]: Both authors contributed equally to this research.