{'fraction_non_alphanumeric': 0.03221418076944006, 'fraction_numerical': 0.013005387168743538, 'mean_word_length': 4.791994957453514, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Compositionality-Aware Graph2Seq Learning

Graphs are a highly expressive data structure, but it is often difficult for humans to find patterns from a complex graph. Hence, generating human-interpretable sequences from graphs have gained interest, called graph2seq learning. It is expected that the compositionality in a graph can be associated to the compositionality in the output sequence in many graph2seq tasks. Therefore, applying compositionality-aware GNN architecture would improve the model performance. In this study, we adopt the multi-level attention pooling (MLAP) architecture, that can aggregate graph representations from multiple levels of information localities. As a real-world example, we take up the extreme source code summarization task, where a model estimate the name of a program function from its source code. We demonstrate that the model having the MLAP architecture outperform the previous state-of-the-art model with more than seven times fewer parameters than it.


Introduction
Graphs are a type of data structure that is capable of encoding a set of rich pairwise information among elements. However, in exchange for the expressivity of a complex graph, it is often difficult for humans to find patterns in such a graph. Therefore, there exists a growing interest in learning to generate a human-interpretable output from a graph. In this study, we focus on generating a sequence of discrete symbols from a graph, known as graph2seq tasks. For example, if we could generate a natural question from knowledge graphs, we could use them to develop an artificial intelligent agent that can interact with people [1,2]. Furthermore, we could solve a path-planning problem as an instance of graph2seq tasks when we regard the input map as a graph [3].
Moreover, traditional sequence to sequence (seq2seq) tasks, like neural machine translation (NMT), could benefit from transforming them into graph2seq tasks. Seq2seq studies have achieved significant successes by introducing the encoder-decoder architecture. Pioneering studies applied recurrent neural networks to encode the input sequence [4,5], and later transformer-based architectures dominated the field [6,7]. Either way, the input to the models are processed as one-dimensional sequences.
On the other hand, many kinds of input sequences in seq2seq tasks can actually be represented as graphs with enriched information. In many cases, we can derive rule-based conversions from raw input sequences to graphs by considering the context and the compositionality in the sequence-e.g., we can convert a natural language sentence to a graph by analyzing its grammatical structure and dependency relations. Because of such additional information, we can expect that graph2seq models utilizing graph structures in seq2seq tasks have a potential to learn improved representations [8].
Therefore, developing a graph2seq model using graph neural networks (GNNs) has recently piqued the interest. For example, Marcheggiani and Perez-Beltrachini [9] introduced a simple graph2seq model that combines a GCN encoder and an LSTM decoder to generate a text description from a resource description framework (RDF) graph or a semantic dependency graph. Xu et al. [10] proposed an attention-based graph2seq model for graph reasoning tasks like bAbI or shortest path search. Chen et al. [11] and Wei et al. [12] applied similar attentional graph2seq techniques in question generation and opinionated text summarization tasks, respectively. Zhu et al. [13] and Cai and Lam [14] proposed graph-transformer-based graph2seq methods, which consider the relationship not only between neighbor nodes but also between distant nodes. However, these methods did not consider the compositionality and hierarchy of the relations among nodes. Chen et al. [11] proposed the Heterogeneous Graph Transformer, that explicitly considers the hierarchy in the input graphs. It splits the original graph into multiple subgraphs and computes the graph representation by aggregating the subgraph representations. It improved the performances of multiple text generation tasks including NMT, owing to its ability to utilize the compositional nature of graphs. However, HetGT only considers single-level hierarchy.
Our assumption in this study is that considering multi-level compositionality in the graphs is effective to learn good representation for generating sequences. The output sequences of graph2seq tasks often have multi-level compositional nature. For example, words in a sentence form local phrases-e.g., an adjective generally modifies a noun next to the adjective-and then phrases link each other and form longer parts. Here, we speculate that the compositionality in a graph can be associated to the compositionality of the output sequence.
Based on the assumption, we apply the multi-level attention pooling architecture (MLAP) [15] to graph2seq tasks. Because of the message passing procedure [16] propagating node information between direct neighbors, information locality of node embeddings are small in lower layers and it expands toward higher layers. MLAP is a GNN architecture that computes layer-wise graph representations using an attention pooling operation in each hidden GNN layers, and then aggregate them as the final graph representation. Therefore, GNN models with MLAP architecture can utilize the graph information in multiple levels of localities, achieving a compositionality-aware graph representation learning.
In this study, we aim to demonstrate that the MLAP architecture is effective for a graph2seq learning. As a real-world example, we take up the "extreme source code summarization" task-generating a short natural language summary of a software program snippet [17]. Although program source code is usually written in a programming language (e.g., C, Java, Python) and represented as a sequence of tokens, it can be converted into graphs called abstract syntax trees (ASTs) by analyzing the syntactic structure. Also, each function in source code has a name summarizing the behavior of the part of program. Therefore, a task to estimate the function name from a program graph is a good example of graph2seq learning. There has already been multiple attempts to apply graph2seq-style model to this task. For example, Allamanis et al. [18] and Fernandes et al. [8] trained gated graph neural network [19] on ASTs. However, many of the methods proposed in those studies do not explicitly consider the compositionality in source code. Program graphs have both short and long dependencies in them, that is, short dependencies form individual operations and longer ones structure complex algorithms. Therefore, considering compositionality in the program graphs can improve the performance. In this study, we train a MLAP model on a source code dataset and show that our proposed method outperforms the previous state-of-the-art (SoTA) model 2 .
The rest of this paper is organized as follows: Section 2 extends the MLAP framework for graph2seq learning, Section 3 describes the the source code summarization experiments and results, and Section 4 and Section 5 demonstrates and discusses the results.

MLAP for graph2seq Learning
In this section, we extend the MLAP architecture introduced in Itoh et al. [15] for graph2seq learning. We first briefly summarize the formulation of MLAP as a graph encoder and then introduce sequence decoders on top of the encoder.

Graph Encoder
Suppose we are given a graph G composed of a set of nodes N and an L-layer GNN model taking the graph as its input. Let h (l) n denote the vector embedding of a node n ∈ N in the l-th (1 ≤ l ≤ L) layer. For both decoders, suppose we have computed the layer-wise representations h (l) G and the final graph representation h G as shown in Itoh et al. [15], that is where f (l) gate is a function used to compute the attention score, for which a two-layer neural network was used in this study, and f agg is an aggregation function. Readers are referred to the original MLAP paper [15] for the detailed formulation.

Sequence Decoder
We evaluate two types of sequence decoders in this study: Linear and LSTM. The former selects elements in a sequence independently, whereas the latter considers the context through the sequence.

Linear Decoder
The most simple implementation of a decoder uses a linear word classifier solely based on the final graph representation, independently for each position in the decoded sequence. That is, we use five independent classifiers if we want to decode five-word sequences.
The model learns position-wise embedded representation matrix for the target vocabulary E voc i ∈ R N voc ×d for each position i, where N voc is the size of vocabulary that consists the generated sequence. Here, the words in the vocabulary with ids 0, 1, and 2 have special meanings: the start of a sentence (SOS), an unknown word (UNK), and the end of a sentence (EOS).
The selection probability for a word w from vocabulary in each position is computed as where b i is a bias parameter and I is the length of decoded sequences. If one or more classifiers select the word EOS for any positions, the words after the first EOS are ignored.

LSTM Decoder
The aforementioned Linear decoder is rather naive, and each word is decoded independent of other words. Thus, it cannot consider the context among decoded words. Instead, we can use a LSTM-based decoder with an attention mechanism [20] to generate a sequence from those representations.
In this case, the model learns an position-invariant embedded representation matrix for the target vocabulary E voc ∈ R N voc ×d .
We first initialize the LSTM state h dec 0 and the memory cell m dec 0 using the aggregated graph representation as Figure 1: A schematic illustration of the extreme code summarization task. A source code snippet with a masked function name, is provided as the input. The snippet is converted into an AST, and then augmented with additional types of edges in preprocess. Models are trained to recover the original function name (get_mean).
At the step t (t = 1, . . . , T ), the state and the memory cell are updated by a standard LSTM [21].
Here, y dec t is the output of the decoder at t (see following).
To determine the output, the model first compute a context vector using an attention mechanism over the layer-wise and final graph representations. Here, for notation simplicity, we consider h (L+1) G be h G , and then the computation is as Then, it computes the output as follows.
where W dec and b dec are trainable parameters. The selection probability for each word in the vocabulary at t is computed as where b w is a bias parameter. The LSTM decoder stops when the word EOS is generated or the step t reaches the maximum step T .

Task and Dataset
To evaluate the MLAP-graph2seq model, we employed the "extreme source code summarization" task [17], wherein a model predicted the function name for given source code snippet (Figure 1). Because a function is commonly named in such a way that the name describes the behavior of the function, recovering the function name from its body would be one of the fundamental tasks that evaluates the models' capability to understand source code semantics.
Here, we used the ogbg-code2 dataset from OGB collection [22]. It contains 452,741 ASTs, each of which contains 125.2 nodes and 124.2 edges on average, extracted from 13,587 OSS projects. The average length of the ground-truth sequence is 2.25. Each node has a 3-dimensional discrete-valued feature containing the depth of node counted from the root of the AST, the type of AST node (e.g., If or Num), and the node attribute. Here, only the leaf nodes have node attributes, usually the token string associated to the node. Non-leaf nodes have blank attributes.

Preprocess
As introduced in Allamanis et al. [18], we augmented the AST graph with additional types of edges. The original graphs in the ogbg-code2 dataset only have one type of edges that point from parent nodes to child nodes, and thus models suffer from low efficiency in information diffusion during message passing. Therefore, we added three additional types of edges to the graphs ( Figure 1): 1. Edges pointing from child nodes to parent nodes (reverse edges of original AST edges). 2. Edges pointing from preceding tokens to following tokens (NextToken edges [18]; only among leaf nodes). 3. Edges pointing from following tokens to preceding tokens (reverse NextToken edges).

Model Configuration
We used MLAP-Weighted architecture throughout the experiment, and evaluated both Linear and LSTM decoders. We set the maximum length of the decoded sequence (I or T ) as 5.
We used graph isomorphism network (GIN) [23] as the message passing layer. For each decoder type (Linear or LSTM), we selected the best model configuration among these conditions: number of layers (5 or 6), residual connection (+ or −), and GraphNorm [24] (+ or −). If a model has residual connection, the node presentation before message passing is added to the node representation after dropout, as in We optimized the model using the Adam optimizer [25]. The models were trained for 50 epochs against a cross-entropy loss computed for each word in the output sequence. The initial learning rate was set to 5 × 10 −4 and decayed by ×0.2 after 3 epochs without improvement in the validation F1 score. The batch size was 256.

Performance Evaluation
As proposed by Alon et al. [26], we used an F1 score between predicted words and ground-truth words to evaluate the model performance. Given the unique and order-agnostic sets of predicted words S p and ground-truth words S t , we defined the metric as We calculated an F1 score for each graph and calculated average over the dataset. We trained 10 models with different random seeds, and evaluate the performance by the mean and the unbiased standard deviation.
As baseline models, we compared the performance of our model to the naive GIN architecture without MLAP, code2seq [27], and Graph Multi-head Attention Neural Network (GMAN) [28], which is the previous SoTA model in the OGB's leaderboard to date. We trained the naive GIN and code2seq models ourselves because there are no available pre-trained models. Note that the definition of the F1 score used in original code2seq code is different from OGB (code2seq first sums up TP, FP, and FN over the dataset and then computes precision, accuracy, and F1), and we replaced the definition with that of OGB. Also, we trained the code2vec models for 100 epochs because of slow convergence. For GMAN, we referred to the performance on the OGB's leaderboard.   [28] 63.7M 0.1631 ± 0.0090 0.1770 ± 0.0012 code2seq [27] 26.7M 0.1495 ± 0.0010 0.1549 ± 0.0010 For the tested ogbg-code2 dataset, the LSTM decoder did not perform as good as the Linear decoder. Nevertheless, the MLAP-Weighted model outperformed the naive architecture.

Results
We statistically compared the performance of the MLAP-Weighted model with the Linear decoder to other models ( Table 2). As a result, it was revealed that our proposed model performed significantly better than the baseline models. Also, the effect size evaluated by Cohen's d [29] demonstrated the performance difference between our model and others were large.

Discussion
In this study, we extended the MLAP architecture for graph2seq tasks. Our proposed model outperformed the naive architecture and GMAN in the extreme source code summarization task and outperformed the previous SoTA model. It indicates that explicitly using the compositional graph information is beneficial in learning to generate sequences from graphs. Here, we emphasize that our best model using MLAP has only 8.6 million parameters, which is less than a seventh of the previous SoTA model. It further supports our hypothesis that utilizing the compositionality helps the model to capture the structural information in graphs.
Code2seq, which is one of the best non-GNN program comprehension model to the best of our knowledge, performed worse than both our model and GMAN, even though code2seq is designed to exploit the domain knowledge in software engineering as much as possible. We could consider the "domain knowledge" used in code2seq or other ML-based program comprehension studies as a set of human experiences in which human programmers mentally construct and interpret the program graph like ASTs. Therefore, it may be enough to use GNNs, which are highly capable of capturing the graph structure, rather than building program comprehension-specific model full of domain knowledge.
Under the current experimental settings, the Linear decoder consistently performed better than the LSTM decoder. We can consider several hypotheses that explain the reason of the results. First, our hyperparameter tuning for the LSTM decoder might not be sufficient. As observed in Table 1, the number of parameters of the model using LSTM decoder is smaller than that with Linear decoder. This would limit the expressivity of the LSTM decoder, and we should be able to further improve the performance in this regard (e.g., adopting bidirectional LSTM decoder [30]). Second, the comparably complex LSTM decoder is harder to train with a medium-sized ogbg-code2 dataset. It only contains approximately 4.5 × 10 5 data points, with each ground-truth sequence having only 2.25 words, which may not be enough for LSTM to capture the context in the output sequences. By contrast, the LSTM decoder should be better than the Linear decoder for tasks that require the models to generate longer sequences.
To further improve the performance of MLAP-graph2seq models, seeking for various decoder implementation would be needed. For example, instead of uni-directional LSTM used in this study, we may use bi-directional LSTM as the decoder [30], which might be beneficial in capturing the context of the output sequences. Furthermore, using transformer-like architecture [6] can be another option.

Concluding Remarks
In this paper, we propose a graph2seq model using the MLAP architecture. Utilizing the compositionality, our model outperformed the previous SoTA model in an extreme source code summarization task with a considerably smaller number of parameters. We will further evaluate the capabilities of our model with wider variety of tasks, including natural language processing.