TreeCaps: Tree-Structured Capsule Networks for Program Source Code Processing
Authors: Vinoj Jayasundara
Nghi Duy Quoc Bui
Lingxiao Jiang
David Lo
Venue:  (2020)
Keywords: Program Classification
Capsule Networks
Deep Learning

Abstract: Program comprehension is a fundamental task in software development and maintenance processes. Software developers often need to understand a large amount of existing code before they can develop new features or fix bugs in existing programs. Being able to process programming language code automatically and provide summaries of code functionality accurately can significantly help developers to reduce time spent in code navigation and understanding, and thus increase productivity. Different from natural language articles, source code in programming languages often follows rigid syntactical structures and there can exist dependencies among code elements that are located far away from each other through complex control flows and data flows. Existing studies on tree-based convolutional neural networks (TBCNN) and gated graph neural networks (GGNN) are not able to capture essential semantic dependencies among code elements accurately. In this paper, we propose novel tree-based capsule networks (TreeCaps) and relevant techniques for processing program code in an automated way that encodes code syntactical structures and captures code dependencies more accurately. Based on evaluation on programs written in different programming languages, we show that our TreeCaps-based approach can outperform other approaches in classifying the functionalities of many programs.

Under review as a conference paper at ICLR 2020
CAPSULE NETWORKS
FOR PROGRAM SOURCE CODE PROCESSING
Anonymous authors Paper under double-blind review
ABSTRACT
Program comprehension is a fundamental task in software development and main- tenance processes. Software developers often need to understand large amount of existing code before they can develop new features or fix bugs in existing pro- grams. Being able process programming language code automatically and pro- vide summaries code functionality accurately can significantly help developers reduce time spent in code navigation and understanding, and thus increase pro- ductivity. Different from natural language articles, source code in programming languages often follows rigid syntactical structures and there can exist dependen- cies among code elements that are located far away from each other through com- plex control flows and data flows. Existing studies on tree-based convolutional neural networks (TBCNN) and gated graph neural networks (GGNN) are not able to capture essential semantic dependencies among code elements accurately. this paper, we propose novel tree-based capsule networks (TreeCaps) and relevant techniques for processing program code an automated way that encodes code syntactical structures and captures code dependencies more accurately. Based on evaluation on programs written in different programming languages, we show that our TreeCaps-based approach can outperform other approaches in classifying the functionalities of many programs.
INTRODUCTION
Understanding program code is a fundamental step for many software engineering tasks. Software developers often spend more than 50% of their time in navigating through existing code bases and understanding the code before they can implement new features or fix bugs (Xia et al. 2018: |Evns Data Corporation 2019 Britton et al. 2012). If suitable models for programs are built, they can be useful for many tasks, such as classifying the functionality of programs (Nix & Zhang 2017 Dahl
ct al. 2013 Pascanu et al. 2015 Rastogi et al. 2013), predicting bugs (Yang al. 2015 et al.
2017
2018). and providing bases for program translation (Nguyen et al. 2017 Gu et al. (017).
Different from natural language texts, programming languages have clearly defined grammars and compilable source code must follow rigid syntactical structures and can be unambiguously parsed into syntax trees. There can be complex control flows and data flows among various code elements all over a program that affect the semantic and functionality of the program. Some inter-dependent code elements can appear in an arbitrary order in the program (c.g., a function A calls another function B while A and B are spatially far away from each other); some code elements, such as local variable names, have no significant impact on code functionality.
In the literature, tree-based convolutional neural networks (TBCNNs) have been proposed (Peng al. 2015 Mou et al. (016)) to show promising results in programming language processing. TBC- NNs accept Abstract Syntax Trees (ASTs) of source code as the input, and capture explicit, struc- tural parent-child-sibling
relations among code elements. Gated graph neural networks (GGNNs) (Li et al.) 2016) are also proposed as way to learn graphs, and ASTs are extended to graphs with variety of code dependencies added as edges among tree nodes to model code semantics (Allamanis) et al. 2018b). While GGNNs capture more code semantics than TBCNNs, many additional edges among tree nodes have to be added through program analysis techniques, and many of the edges may be noise, contributing longer training time and lower performance. A recent model. known as ASTNN, based on a sequence of small ASTs for statements (instead of one big AST for the whole program) shows better performance than TBCNNs and GGNNs (Zhang al. 2019)

---

Under review as a conference paper at ICLR 2020
In this paper, propose novel tree-based capsule network architecture, named TreeCaps, to capture both syntactical structure and dependency information in code, without the need of explic- itly adding dependencies in the trees splitting big tree into smaller ones. Capsule Networks (CapsNet) (Sabour et al.) 2017) itself is a promising concept that has demonstrated vast potential in outperforming CNNs in various domains including computer vision and natural language pro- cessing, because it has the main advantage that it can discover and preserve the relative spatial and hierarchical relations among objects within an input (e.g., an image and a piece of texts).
TreeCaps adapts CapsNet to ASTs for programs, proposes novel primary variable and primary static capsule layers, proposes a novel variable-to-statee routing algorithm to route a variable set of cap- sules to generate a static set of capsules (with the intention of preserving code dependencies), and connects the tree capsule layers to a classification layer to classify the functionality of program.
In our empirical evaluation, we take various sets of programs written in different programming lan- guages (e.g., Python, Java, C) collected from GitHub and the literature, and train our TreeCaps models to classify programs with different functionalities. Results show that TreeCaps outperforms other approaches in program classification by significant margins, while a study done on variants of the proposed model reveals the effectiveness of the proposed variable-to-statie routing algorithm, effect of the dimensionality of the classification capsules on the model performance and the effec- tiveness of the use of additional capsule layers.
2 RELATED WORK
Capsule networks (Sabour et al. 2017 Hinton et al. 2018) use dynamic routing to model spatial and hierarchical relations among objects in an image. The techniques have been successfully applied to different tasks, such as computer vision, character recognition, and text classification (Jayasundara jet al,, 2019; Rajasegaran et al. 2019 Zhao al. 2018). None of the studies has considered complex tree data input. Capsule Graph Neural Network (Zhang & Chen 2019) has been recently proposed to classify biological and social network graphs, yet, has not been applied to trees for programming languages processing yet.
On the other hand, tree- and graph graph-based neural networks have been studied for program language processing. TBCNNs (Peng al. (0155] Mou et al. (016)) have been used to model code syntactical structures. GGNNs (Li et al. 2016) Allamanis et al. 2018h) 88) build dependency graphs from ASTs and use graph neural networks to encode the code dependencies. Variants of TBCNNs and GGNNs are also proposed to represent programs differently and aim to achieve better training accuracy and costs. For example, ASTNN (Zhang et al.) 2019) splits an entire AST into sequence of smaller ones and uses bidirectional gated recurrent units (Bi-GRU) to model the smaller ASTs that represent statements in programs. For another example, bilateral dependency tree-based CNNs (DTBCNNs) (BUI et al. 2019) are used to classify programs across different programming languages. Tree- LSTM (Wei Li 2017) has also been used to model tree structures in program code. Our work aims to model tree structures too, but designs special dynamic routing with the intention to capture code dependencies without the need of explicit program analysis techniques.
More generally, there is huge interest in applying deep learning techniques for various software engineering tasks, such as program classification, bug prediction, code clone detection, program refactoring, translation and even code synthesis (Allamanis et al. 2018a| Alon al. 2019 Hu et al.,
2018 Chen et al.] 2018; Pradel & Sen 2018). We are likely the first to adapt capsule networks for program source code processing capture both syntactical structures and code dependencies, especially for the problem of program classification. In the future, it can be an exciting area to combine more kinds of semantic-aware code representations (e.g., symbolic traces (Henkel al.) 2018)) and tailored program analysis techniques with deep learning to improve code learning tasks.
APPROACH OVERVIEW
The overview of our TreeCaps approach is summarized in Fig. I The source code of the training sample program is parsed into an AST and vectorized with the aid of Word2Vec (Mikolov et al. 2013) or a similar technique that considers the AST node types, instead of concrete tokens, as the vocabulary words (Peng et al. 2015 BUI et al. 2019). The AST and the vectorized nodes
2

---

Under review as a conference paper at ICLR 2020
Variable to Static Routing
Dynamic Routing
Primary Variable
Primary
Vectori- -zation
Static
CodeCaps Layer
int a
Capsule
Capsule
Layer
Layer
Softmax Output
Source Code
TreeCaps Network
Figure I: Approach Overview. The source codes are parsed, vectorized and fed into the proposed TreeCaps network for the program classification task.
then fed in to our TreeCaps network, which consists of a Primary Variable Capsule (PVC) layer accommodate the varying number of nodes in the AST. Subsequently, the capsules are routed to the Primary Static Capsule (PSC) layer using the proposed variable-to-statie routing algorithm, followed by routing with the dynamic routing algorithm to the Code Capsule (CC) layer. Acting as the classification capsule layer, Code capsules capture and provide embeddings for the entire training sample, while denoting the probability of existence of the source code classes by the respective vector norms. Finally, softmax layer is used on the vector norms to output the probabilities for the input code sample to belong to various functionality classes.
Sentionn more about the AST vectorization and other major components in TreeCaps.
4 ABSTRACT SYNTAX TREE VECTORIZATION
Decl
5:
Parser
Type
Binary
Generaze
Embeddinge
Egi- word2vec
Saurce Code
Type
Constant
AST
Vectorized AST
Figure 2: Tree Vectorization, which generates the AST from the source code and vectorizes using an embedding generation technique.
Fig. iilustrates the vectorization of an AST. Every raw souree code is parsed with an appropriate parser corresponding to the programming language to generate the AST AST represents the syntactic structure of the source code with a set of generalized vocabulary words (i.e., node type names). We use ASTs to train the embedding for node types by applying embedding techniques, such as Word2vec (Mikolov et al. 2013), the context ASTs using techniques similar to Peng et al. (2015). which learns vectorized vocabulary of node types, Xnode E RV where V is the embedding size. The learned vocabulary can subsequently be used to vectorize each individual node of the ASTs, generating the vectorized ASTs.
5 TREE-BASED CAPSULE NETWORKS
One of the main challenges in creating a tree-based capsule network is that the input of the network tree-structured (ASTs in our case). Tree-structured data are inherently different from generic image data, Ximg E #X#WxCC where H, W, C' are the fixed height, width and the number of channels respectively, or natural language data, Xnlp E R where L, E are the fixed padded sentence length and the word embedding size respectively. Hence, the network architecture needs to be constructed to accommodate such tree-structured data, Xtree E TxV, where T, V are the variable tree size (the number of nodes in the tree) and the node embedding size respectively.
5.1 PRIMARY VARIABLE TREECAPS LAYER
A further challenge with trees is that the tree size varies from program to program, and the number of children varies from node to node. A naive solution to the problem can to pad the sizes
We use python AST parser for python programs, whereas sreMI. parser for C. and Java programs.
3

---

Under review as a conference paper at ICLR 2020
Voriable to Static Routing
Cunvert
Bi
Capealee
Vectorized AST
Primary Static Copenles
Primary Vartable Capsnios
Figure 3: Variable-to-Static Routing, which routes a variable set of capsules to generate static set of capsules.
to reach a fixed, pre-defined length, following similar approach in natural language domain to preserve a fixed sentence length. However, zero-padding is not appropriate in our case due to the degree of variability. For instance, the number of children per node can vary from zero to hundreds, causing challenges in deciding the fixed padding length and introducing sparsity. Mou et al.) (2016) propose more effective approach termed continuous binary tree, where the convolution window emulated as a binary tree, where the weight matrix corresponding to each node is represented as a weighted sum of three fixed matrices W W W E RV'V and bias term b E IR V where V" the embedding size after the convolution, and the weighting coefficients are calculated by taking the positional value in to account.
Hence, for convolutional window of depth d in the original AST, and there are K + 1 nodes (including the parent node) which belong to that window with vectors [X1, XK+1), where E RVV then the convolutional output y can defined follows,
K+1
= tanh In w' + o/ + +7 W +
(I)
where n/f 1/. my are weights defined corresponding to the depth and the position of the children nodes:
d. d
-1-
P:
(1-
where de is the depth of the node in the convolutional windows, P; is the position of the node and k the total number of node's siblings. The output of tree-structured convolution resembles the input tree structure, Yone E TVV.
In the Primary Variable Capsule layer, y obtained from Equation corresponds to the output of one convolutional slice. We use ε such slices with different random initializations for W, b, similar to CNNs for image data. Subsequently, as illustrated by Fig 3 group the convolutional slices together to form Npvc V'xe sets of capsules with outputs u, E , [1, Npeel where Dpec the dimensions of the capsules (i.e., Dpec the number instantiation parameters of the capsules) in the PVC layer. In order to vectorize each capsule output u, ú, (to represent the probability of existence of an entity by the vector length), we subsequently apply non-linear squash function follows,
Dyec
U
û
(3)
where | l/ 1. Hence, the output of the primary variable capsule layer is X Xpvc R X Dpuc.
5.2 PRIMARY STATIC TREECAPS LAYER
The key issue with passing the outputs of the PVC layer, Xpves the Code Capsule layer that the number of capsules, Npocs is variable from one training example to another. Prior to routing the lower level capsules to a set of higher level capsules, the lower dimensional capsule outputs need to be projected to the higher dimensionality, with the aid of the transformation matrix which learns the whote relationship between the lower and the higher level capsules (Sabour et al. 2017). However, trainable transformation matrix cannot be defined in practice with variable dimensions. Thus, the dynamic routing in the literature (Sabour et al. (017)) cannot be applied between a variable set of capsules and static set of capsules.
4

---

Under review as a conference paper at ICLR 2020
5.2.1
VARIABLE-TO-SSIEE CAPSULE ROUTING
Therefore, we propose a novel variable-to-static capsule routing algorithm, summarized in Algo.
Algorithm Variable-to-Static Capsule Routing
1: procedure ROUTING(û, r,
2: Üsorted f sort([ū1, p.p.
3: Initialize V, Vi.j Σ a, Vj < Ü sootted
4: Initialize 0gy V/j E [1,
E [1, [1,b], aij t
5: for iterations do
6: Ej [,, Vi bl fij Vj
7:
Vj [ Vi E b, Oij t Oij + fij
8:
e [1, t So Softmar(a.)
9:
[1, + 3 û
Vj (1, Squash(s,)
11: return V
We initialize the outputs of the Primary Static Capsule layer with the outputs of the a capsules with the highest L2 norms in the PVC layer. Hence, the outputs of the PVC layer, [ūr,... uN,... are first sorted by their L2 norms, to obtain Ó sorted, and then the first a vectors of Ô Uoorted are assigned as vj.ā towards source code classification. Often, source code consists of non-essential entities, and only portion of all entities determine the code class. Since the probability of existence of entity is denoted by the length of the capsule output vector (L2 norm), we only consider the entities with the highest existence probabilities for initialization. It should be noted that the capsules with the a-highest norms are used only for initialization, the actual outputs of the primary static capsules are determined by iteratively running the variable-to-stail routing algorithm.
The intuition is that, in practice, not every node of the AST contributes
A well-known property of source code is that dependency relationships may exist among entities that are not spatially co-located. Therefore, we route nodes the AST based on the similarity between them and the primary static capsule layer outputs, where < b < Npwc- We assign b = N poe general to route with all the nodes in the AST. If computational complexity is critical, we can choose smaller and route with top-b nodes of the AST. and b can be chosen empirically, where computational complexity also factors in when choosing 6.
We initialize the routing coefficients oiyy O, equally to all the capsules in the primary variable capsule layer. Subsequently, as illustrated by Fig they are iteratively refined based on the agree- ment between the current primary static capsule layer outputs v, and the primary dynamic capsule layer outputs û. The agreement in this case is measured by the dot product, Jij <- û, Vj. and the routing coefficients has a strong agreement with a capsule ò in the primary static layer, then fys will be positively large, whereas if there is strong disagreement, then fys will be negatively large. Subsequently, the sum of vectors û; is weighted by the updated Big to calculate sy, which is then squashed to update v,.
adjusted with Sij accordingly. If capsule in the primary dynamic layer
5.3 CODE CAPSULE LAYER
Dynamic Routing
||,,||
Squash Max
W jm
Softmax
Outpor
CodeCaps
Primary Static
Capsules
Figure 4: Dynamic Routing between the Primary Static Capsules and the Code Capsules.
Code Capsule layer is the final layer of the TreeCaps network, which acts as the classification capsule layer, as illustrated by Figure 4 Since the outputs of the PSC layer X Xpec IR Nyse Pyse, where Npsc = a and D Dpsc D prees consist of a fixed set of capsules, it can be routed to the CC layer via the dynamic routing algorithm in the literature (Saoorr al. 2017) (summarized in Algo. 2 For
5

---

Under review as a conference paper at ICLR 2020
each capsule in the PSC layer, and for each capsule in the CC layer, multiply the output of the primary static capsule V, by the transformation matrices W to produce the prediction vectors Vilj W v. The trainable transformation matrices learn the part-whole relationships between the primary static capsules and the code capsules, while effectively transforming V, vs's into the same dimensionality Zmn where Zm denote the outputs of the code capsule layer. Similar to the variable-to-static capsule routing, we initialize the routing coefficients 7/m equally, and iteratively refine them based on the agreements between the prediction vectors mli and the code capsule
outputs 2m, where Zm. squash Tim Vimmmlp) mllg).
Algorithm 2 Dynamic Routing
1: procedure ROUTING(V,,,, t,
2: Initialize Vij E [1, a), Vm E [1,c], 6jm f-
3: for iterations do
4: Vj E [1, a|. f/ + softmar(d,
5: Ym E [1, cj. Zm + squash Eg Tym mmmm)
6: Vj E [1, al, Vm [1,c], djm f djm + mllj Zm
7: return pm
The primary static capsule outputs are routed to the CC layer using the dynamic routing algorithm, as illustrated by Fig to produce the final capsule outputs Xec E IRNee where Noe the number of classes and Dee is the dimensionality of the code capsules. Ultimately, we calculate the probability of existence of each class by obtaining L2 norm of each CodeCaps output vector.
5.4 MARGIN LOss FOR TREECAPS TRAINING
We use the Margin Loss proposed by Sabour et al. (017) as the loss function for TreeCaps. For every code capsule μu, the margin loss L, defined as follows,
Lp = Tμ max(0, m - ||ual)) + A(1 - Tw) m0, |l - m m=
(4)
where T3 is if the correct class is μ and zero otherwise. Following Sabour al. (2017). À is set to 0.5 to control the initial learning from shrinking the length of the output vectors of all the code capsules, and m m are set to 0.9, 0.1 the lower bound for the correct class and the upper bound for the incorrect class respectively.
EMPIRICAL EVALUATION
6.1 DATASETS AND IMPLEMENTATION
We used three datasets in three programming languages ensure cross-language robustness. The first dataset (A) contains 6 classes of sorting algorithms, with 346 training programs on average per class, written in Python F The second dataset (B) is inherited from BUI et (2019), which contains 10 classes of sorting algorithms, with 64 training programs on average per class, written in Java. The third dataset (C) is inherited from Mou et al. (016)). which contains 104 classes of programs, with 375 training programs vectorizer (see Footnote 2 to generate embeddings for more than 90 AST node types in Python. For the datasets B & C, srcMI defines unified vocabulary for more than four hundred AST node types for C and Java (and several other languages, but not Python), and we adapted the same vectorizer to generate embeddings for the unified AST node types defined by srcML.
average per class. For the dataset A, we used the publicly available
We used Keras and Tensorflow libraries to implement TreeCaps. To train the models, we used the RAdam optimizer (Liu et al. 2019) with initial learning rate of 0.001 subjected to decay, Nvidia Tesla P100 GPU. To enhance the classification accuracies, a weighted average ensembling
technique (Krogh & Vedelsby 1995) used.

---

Under review as a conference paper at ICLR 2020
Table 1: Comparison of TreeCaps with other approaches. The means and the standard deviations
from 3 trials are shown.
Model
Dataset
Dataset B
Dataset
GGNN Allamanis et al. (0188)
85.00%
86.52%
TBCNN (Mou et al. 2016)
99.30%
75.00%
79.40%
TreeCaps
100.00 + 0.00%
92.11 = 0.90%
87.95 = 0.23%
TreeCaps (3-ensembles)
100.00% %
94.08 %
89.41
6.2
PROGRAM CLASSIFICATION RESULTS
Table I compares our results to other approaches for program classification. It should be noted that, Mou al. (2016) have used custom-tras trainer initial embeddings for small set of about 50 AST node types defined specifically for C language only (Peng ct al. 2013) and reported a higher result in their paper, while our approach generates the initial embeddings for much larger vocabulary of more than three hundred unified AST node types for both C and Java. For a fairer comparison based on the same set AST node vocabulary, especially for the datasets B & C. we used our embeddings based on srcML node vocabulary as the initial embeddings across all models. We followed the techniques proposed in Allamanis et al. (2018a) and BUT et al. (2019) to re-generate the results for GGNN and the techniques proposed in Mou et al. (2016) to re- re-generate the results for TBCNN.
For the dataset A, we achieved a perfect classification result, outperforming TBCNN by a narrow margin of less than 1%. However, the margin was average accuracy of 92.11% was achieved by our approach for the dataset B, outperforming other approaches at least by 7.11%. TreeCaps outperformed its convolutional counterpart (TBCNN) by significant margin of 17.11%. The performance was further improved by 1.97% with the use of 3- model weighted average ensembling technique. For the dataset C, our approach was able to surpass the other approaches by 1.43%, achieving an accuracy of 87.95% However, TreeCaps surpassed TBCNN by a more significant margin of 8.55%. Three-model weighted average ensembling on the dataset C provided further improvement of 2.89% in comparison to the other approaches, achieving an accuracy of 89.41%.
significant for the datasets B and C. An
6.3 MODEL ANALYSIS
We evaluate the effects of various aspects of the TreeCaps model, including the effect of the variable- to-static routing algorithm, variations in the number of instantiation parameters in the CodeCaps layer, and the addition of secondary capsule layer. We evaluate these variations on the dataset B.
Table 2: Effect of different model variants
Model Variant
Accuracy
PoriablettoStatier Routing Algorithm - Dynamic Pooling
83.43%
Instantiation parameters + Dec =
90.90%
Dec 8
92.10%
Dec = 12
90.33%
Dac 16 TreeCaps - TreeCaps + Secondary Capsule Layer
91.51%
92.31%
TreeCaps with Variable-to-Stalle Routing and Doc 8
92.11%
6.3.1 EFFECT OF THE VARIABLE-TO-STEE STATIC ROUTING ALGORITHM
We investigate the effeet of the variable-to-statie routing algorithm by replacing it with Dynamic Max Pooling (DMP). Since there is no alternative approach existing in the literature for routing variable set of capsules to static set of capsules, compare the proposed routing algorithm with dynamic pooling. The output of the PVC layer, Xpvc E N consists of a variable component, N pvc- Using dynamic max pooling across all the Npvc capsules will result in one output capsule, Xdmp RIxD Since Xamp has variable components across the training samples,
CCollccted from http::/gihhb..comcccsaannnbbbbbm
https: www.. www.wrrcmm sr /

---

Under review as a conference paper at ICLR 2020
it can now be routed to the code capsules using the dynamic routing algorithm. However, it should be noted that DMP is not suitable for capsule networks, as destroys the spatial and dependency relationships between the capsules. We use DMP here only for comparison purposes.
As summarized in Table 2 DMP yiclds a considerably lower accuracy of 83.43% than our routing algorithm by significant margin of 8. 8.68%, establishing the effectiveness of our proposed algorithm.
6.3.2 EFFECT OF THE NUMBER OF INSTANTIATION PARAMETERS
The instantiation parameters Dee of the Code Capsule layer acts as the final embeddings used for classification, in other words, the dimensionality of the latent representation of source code. If the dimensionality of the latent representation is higher than required, it can introduce sparsity and/or correlations between the instantiation parameters, reducing the classification accuracy. On the con- trary, if the dimensionality of the latent representation is too low, it may not be sufficient to capture the variations in source code, leading to under-representation, reducing the classification accuracy. Hence, in attempt to identify suitable value for Dec for source code classification, we investi- gate the effect Dee the accuracy. As summarized Table we observed that the most suitable value was Dce 8 for the dataset B.
6.3.3 EFFECT OF THE ADDITION OF A SECONDARY CAPSULE LAYER
We evaluate the addition of an extra capsule layer functionally similar to a primary static capsule layer, which we call the secondary capsule (SC) layer. With respect to Fig T stack the SC layer in between the PSC layer and the CC layer. We use dynamic routing to route between the PSC and SC layers and between the SC and CC layers. Even though we observed minor improvement of the classification accuracy, the added computational complexity increases the inference time by 16%, from 10.3 ms 11.9 ms per sample. The usefulness of the addition of such SC layer needs be further investigated.
6.4 DISCUSSION OF LIMITATIONS & FUTURE WORK
Since TreeCaps is based on the capsule networks, it inherits the limitations of capsule networks such as the high computational complexity in comparison to CNNs, and performance reduction with the increasing number of classes. TreeCaps lacks a reconstruction network, similar to the reconstruc- tion network for image data presented by [Sabour et al. (2017), which is useful to investigate the interpretability of the capsule network, including the relationship between the learnt instantiation parameters and the physical attributes of data.
We intend extend our work further investigate the effects of different initial embeddings on the classification accuracy. Further, we intend to compare related pieces of code identified by TreeCaps to program dependencies identified by program analysis techniques, to evaluate the effectiveness of TreeCaps embedding generating technique, and to extend TreeCaps to other related tasks such as bug detection and localization.
CONCLUSION
In this paper, we proposed novel tree-based capsule network (TreeCaps) to learn rich syntactical structures and semantic dependencies in program source code. The model proposed novel technical features that deal with variable sized trees across different programming languages, including pri- mary variable and primary static capsule layers, and the variable to static routing algorithm. Our empirical evaluations show that these features significantly contribute to the high classification ac- curacy of TreeCaps model for program classification tasks for various programming languages. To the best of our knowledge, to program source code learning. We believe that TreeCaps can capture more code semantics than previous code learning models and complement existing program analysis techniques well.
work is the first to adapt capsule networks to trees and apply them
8

---

Under review as a conference paper at ICLR 2020
REFERENCES
Miltiadis Allamanis, Earl T Barr, Premkumar Devanbu, and Charles Sutton. A survey of machine learning for big code and naturalness. ACM Computing Surveys, 51(4):81, 2018a.
Miltiadis Allamanis, Mare Brockschmidt, and Mahmoud Khademi. Learning to represent programs with graphs. In International Conference on Learning Representatiinss, 2018b.
Uri Alon, Meital Zilberstein, Omer Levy, and Eran Yahav. Code2vec: Learning distributed repre- sentations of code. Proc. ACM Programming Languages, S(POPL)):0:114000) January 2019.
Tom Britton, Lisa Jeng, Graham Carver, and Paul Cheak. Quantify the time and cost saved using reversible debuggers. Technical report, Cambridge Judge Business School, 2012.
Nghi D. Q. BUI, Yijun YU, and Lingxiao JIANG. Bilateral dependency neural networks for cross- language algorithm classification. In IEEE/ACM International Conference on Software Analysis, Evolution and Reengineering, 2019.
Xinyun Chen, Chang Liu, and Dawn Song. Tree-to-tree neural networks for program translation. In Advances in Neural Information Processing Systems, pp. 2547-2557, 2018.
George E Dahl, Jack W Stokes, Li Deng, and Dong Yu. Large-scale malware classification using random projections and neural networks. In IEEE International Conference on Acoustics, Speech and Signal Processing, pp. 3422-3426. IEEE, 2013.
Evans Data Corporation. Global developer population and demographic study. evansdata com httpaaaec..eeepppttt/e/eeeeeeeee wtw.:ppost.pppppppoooott..o 2019.
http://
Xiaodong Gu, Hongyu Zhang, Dongmei Zhang, and Sunghun Kim. DeepAM: Migrate apis with multi-modal sequence to sequence learning. In International Joint Conference on Artificial Intel- ligence, pp. 3675-36811 2017.
Jordan Henkel, Shuvendu K Lahiri, Ben Liblit, and Thomas Reps. Code vectors: Understanding programs through embedded abstracted symbolic traces. In Proceedings of the 2018 26th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering, pp. 163-174. ACM, 2018.
Geoffrey E Hinton, Sara Sabour, and Nicholas Frosst. Matrix capsules with EM routing. In Inter- national Conference Learning Representations, May 2018.
Xing Hu, Ge Li, Xin Xia, David Lo, and Zhi Jin. Deep code comment generation. In International Conference on Program Comprehension, pp. 200-210. ACM, 2018.
Vinoj Jayasundara, Sandaru Jayasekara, Hirunima Jayasekara, Jathushan Rajasegaran, Suranga Seneviratne, and Ranga Rodrigo. TextCaps: Handwritten character recognition with very small datasets. In IEEE Winter Conference Applications of Computer Vision, pp. 254-262, 2019.
Anders Krogh and Jesper Vedelsby. Neural network ensembles, cross validation, and active learning. In Advances in neural information processing systems, pp. 231-238, 1995.
Jian Li, Pinjia He, Jieming Zhu, and Michael R Lyu. Software defect prediction via convolutional neural network. IEEE International Conference on Software Quality, Reliability and Security, pp. 318-328. IEEE, 2017.
Yujia Li, Daniel Tarlow, Mare Brockschnidr, and Richard Zemel. Gated graph sequence neural networks. In International Conference on Learning Representations, November 2016.
Zhen Li, Deqing Zou, Shouhuai Xu, Xinyu Ou, Hai Jin, Sujuan Wang, Zhijun Deng, and Yuyi Zhong. Vuldeepecker: A deep learning-based system for vulnerability detection. arXiv preprint 2018.
Liyuan Liu, Haoming Jiang, Pengcheng He, Weizhu Chen, Xiaodong Liu, Jianfeng Gao, and Jiawei Han. On the variance of the adaptive learning rate and beyond. arXiv preprint arXiv:1908.000 1906.03265, 2019.

---

Under review as a conference paper at ICLR 2020
Tomas Mikolov, llya Sutskever, Kai Chen, Greg S Corrado, and Jeff Dean. Distributed represen- tations words and phrases and their compositionality. In Advances neural information pro- cessing systems, pp. 3111-3119, 2013.
Lili Mou, Ge Li, Lu Zhang, Tao Wang, and Zhi Jin. Convolutional neural networks over tree structures for programming language processing, In AAAI Conference on Artificial Intelligence, 2016.
Trong Duc Nguyen, Anh Tuan Nguyen, Hung Dang Phan, and Tien N. Nguyen. Exploring API em- bedding for API usages and applications. In International Conference on Software Engineering, pp. 438 449, 2017.
R. Nix and J. Zhang. Classification of android apps and malware using deep neural networks. In International Joint Conference Neural Networks, pp. 1871-1878, May 2017.
Razvan Pascanu, Jack W Stokes, Hermineh Sanossian, Mady Marinescu, and Anil Thomas. Mal- ware classification with recurrent networks. In IEEE International Conference on Acoustics, Speech and Signal Processing, pp. 1916-1920. IEEE, 2015.
Hao Peng, Lili Mou, Ge Li, Yuxuan Liu, Lu Zhang, and Zhi Jin. Building program vector repre- sentations for deep learning. In Proceedings of the 8th International Conference Knowledge Science, Engineering and Management), pp. 547-553, October 28-30 2015.
Michael Pradel and Koushik Sen. Deepbugs: A learning approach to name-based bug detection. Proceedings of the ACM Programming Languages, 2(00PSLA))147, 2018
Jathushan Rajasegaran, Vinoj Jayasundara. Sandaru Jayasekara, Hirunima Jayasekara, Suranga Seneviratne, and Ranga Rodrigo. DeepCaps: Going deeper with capsule networks. In Computer Vision and Puttern Recognition, 2019.
Vaibhav Rastogi, Yan Chen, and Xuxian Jiang. Catch me if you can: Evaluating android anti- malware against transformation attacks. IEEE Transactions Information Forensies and Secu- rity, 9(1):99- 108, 2013.
Sara Sabour, Nicholas Frosst, and Geoffrey E Hinton. Dynamic routing between capsules. In Conference on Neural Information Processing Systems, pp. 3856-3866, Long Beach, CA, 2017.
Huihui Wei and Ming Li. Supervised deep features for software functional clone detection by ex- ploiting lexical and syntactical information in source code. In International Joint Conferences on Artificial Intelligence, pp. 3034-3040, 2017.
X. Xia, L. Bao, D. Lo, Z. Xing, A. E. Hassan, and Li. Measuring program comprehension: A large-scale field study with professionals. IEEE Transactions Software Engineering, 44(10): 951-976, Oct 2018.
Xinli Yang, David Lo, Xin Xia, Yun Zhang, and Jianling Sun. Deep learning for just-in-time defect prediction. In IEEE International Conference on Software Quality, Reliability and Security, pp. 17-26, 2015.
Jian Zhang, Xu Wang, Hongyu Zhang, Hailong Sun, Kaixuan Wang, and Xudong Liu. A novel neural source code representation based on abstract syntax tree. In International Conference on Software Engineering, pp. 783-794, 2019.
Xinyi Zhang and Lihui Chen. Capsule graph neural network. In International Conference on Learn- ing Representations, 2019.
Wei Zhao, Jianbo Ye, Min Yang. Zeyang Lei, Suofei Zhang, and Zhou Zhao. Investigating capsule networks with dynamic routing for text classification. arXiv preprint arXiv: 005508 2018.
10


Reviews:
[{"review_id": "r1llKxqKYH", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes a tree-structured capsule network for program source code processing (essentially a program classification task with three datasets). \n\nThe idea of incorporating tree structures into the design for capsule networks is not wrong. However, I am not sure why a capsule network is even needed in program classification. The authors follow the cliché of the importance of tree structures, but show little insight into the use of capsule networks in program analysis. The authors started rationalizing the capsule networks by saying \"Capsule Networks itself is a promising concept ...\" Being a promising concept itself doesn't necessarily mean it has/is suitable to be applied in program classification.\n\nThe treatment in Sec. 5.1 of the tree structures is pretty the same as in Mou et al. [2016], linearly weighting a token by its position. Sec. 5.2 is extremely hard to understand. It starts with presenting an algorithm and its line-by-line interpretation. I know how to program, but I wish to get some intuition of why capsule networks are needed for program classification, and how it is different from a generic capsule network and/or a graph capsule network [Xinyi & Chen, 2019]. Given a graph capsule network is in place, I found the contribution of this paper (tree capsule network) is limited. \n\nThe experiments are very thin. The authors only compare their results to TreeCNN and Gated  Graph NN (GGNN). It's unclear if TreeCaps is better than other existing models, such as Transformer, TreeTransformer, GraphCap, etc.\n\nWhile the authors experimented on three datasets, the evidence is actually limited. Dataset A is saturated (99.3%--100%). Dataset B shows some performance improvement (compared with GGNN and TreeCNN only). Dataset C basically shows TreeCaps is similar to GGNN. The gap between 89.41% and 86.52% is largely due to model ensembles. But the performance of GGNN ensembles is unknown. \n\nIn summary, the paper applies Capsule Network to tree structures. The authors mainly follow the cliché of tree structures, but are not too excited about the capsule stuff. I am not excited either. \n\n==\nMinor:\n\nNghi D. Q. BUI -> misformatted. Probably they are two people.\nZhang Xinyi and Lihui Chen --> Not sure if Xinyi is the last name. ", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_checking_correctness_of_derivations_and_theory": "N/A", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly."}, "extra_text": {}}, {"review_id": "SklkAftTtH", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper proposes a capsule-network-based architecture for predicting program properties and is evaluated on three tasks for predicting an algorithm from a code snippet.\n\nTechnically, the paper aims to transfer the idea of convolution from images and apply it to abstract syntax trees of programs. To do this, two dimensions describing the position of a node in a tree position are used - the depth of a node in a tree and its index in the list of children of its parent. This choice, however, is similar to image convolutions only at a very artificial level and drops significant amount of semantically-interesting information for programs from the index of the node at the parents, while keeping the total depth (which rarely matters in programs, as code is usually semantically similar no matter how nested in other code it is).\n\nThe experiments are small (on two small and one slightly larger dataset) and inconclusive:\n1) Given the number of experiments done for tuning parameters on Dataset B (with ~640 examples), it is not clear that we are not observing some trivial case of overfitting. The improvement over GGNN is quite small and mostly due to ensembles.\n2) The problem of small evaluation datasets make the results inconclusive. Only Dataset C is sufficiently large, if I assume no optimization like for Dataset B was performed.\n3) Furthermore, it looks like the considered tasks are may be better handled by models such as code2vec or code2seq than by GGNN. The paper needs to include stronger baselines.\n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}, {"review_id": "S1xcQm8k5B", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper proposes a neural architecture for summarizing trees inspired by capsule networks from computer vision. The authors re-use a tree convolution from previous work for the bottommost layer, and then propose adaptations to the dynamic routing from capsule networks so that it can be applied to variable-sized trees. The paper applies the proposed architecture to three different program classification datasets, which are in three different languages. The paper reports empirical gains compared to two architectures proposed by previous work.\n\nI think that it's interesting to apply the capsule network architecture to tree classification, but unfortunately it doesn't appear that some of the motivation for capsule networks on images didn't seem to transfer neatly to this setting; for example, there is no equivalent of inverse graphics as there is no reconstruction loss (as pointed out by the authors in Section 6.4).\n\nAlso, the variable-to-static capsule routing indeed appears novel, but I was a bit confused by its internal details. It appears that the outputs of the previous layer which occur most often will get routed (considering lines 6-8 of Algorithm 1 which up-weights each of the $\\hat{u}_i$ based on its similarity to $v_j$; the $v_j$ are initially a re-numbered subset of $\\hat{u}_i$), without any prior transformation of the previous layer first. It seems to me that this doesn't allow for the prior layer to predict more complex features about the input that the subsequent layer is expected to capture. In fact, for certain code classification tasks, it may be that rare capsule outputs from the initial layer are the most important to preserve.\n\nMy biggest concern has to do with the empirical results. The source of Dataset C (Mou et al 2016, https://arxiv.org/pdf/1409.5718.pdf) reports 94.0% accuracy in Table 3 on their TBCNN method on the same dataset, whereas this paper reports 79.40% accuracy for TBCNN. I understand that the later result comes from a reimplementation, but it seems fairer to compare against (or additionally report) the results from the original authors of the method.\n\nAlso, the paper cites ASTNN (Zhang et al 2019, https://dl.acm.org/citation.cfm?id=3339604) in the introduction, and even though that paper reports (in table 2) 98.2% accuracy on Dataset C, the results table of the paper under review does not mention this in the evaluation section. I don't think that a paper necessarily has to achieve empirical results beating all previous ones in order to merit acceptance, but the way that the comparison is currently set up doesn't seem to facilitate a clear comparison of the pros and cons of this method versus other ones in the literature.\n\nFor the above reasons, I vote to reject the paper. For future submissions, it would be good to see a more comprehensive empirical comparison of the proposed method compared to others, and also to have more explanations about the design of the network.", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes an application of capsule networks to code modeling.

I see the potential in this approach, but as the reviewers pointed out, in the current draft there are significant issues with respect to both clarity of motivating the work, and in the empirical results (which start at a much lower baseline than previous work). I am not recommending acceptance at this time, but would encourage the reviewers to clarify the issues raised in the reviews for future submission.
Decision: Reject