TreeCaps: Tree-Based Capsule Networks for Source Code Processing

Nghi D. Q. Bui, Yijun Yu, Lingxiao Jiang

Abstract

Recently, program learning techniques have been proposed to process source code based on syntactical structures (e.g., abstract syntax trees) and/or semantic information (e.g., dependency graphs). While graphs may capture code semantics better than trees, constructing them can introduce noise. We propose TreeCaps, a novel architecture that fuses capsule networks with tree-based convolutional neural networks (TBCNN) to achieve high learning accuracy using only tree representations. By introducing a "Variable-to-Static" (VTS) routing algorithm, TreeCaps effectively models hierarchical relationships in code. Evaluated on Java and C/C++ benchmarks, TreeCaps outperforms prior models in accuracy and robustness against semantic-preserving transformations.

Introduction

In the field of Machine Learning for Code (ML4Code), researchers typically represent source code as either Abstract Syntax Trees (ASTs) or Graphs (e.g., Control/Data Flow Graphs). Trees are easy to generate and precisely defined by a language's grammar, but standard neural networks often struggle to capture the deep semantic "part-whole" relationships inherent in code logic. Conversely, graphs capture these semantics more effectively but are computationally expensive to build and often introduce noise. TreeCaps seeks to bridge this gap, extracting graph-level semantic richness using only simple, easy-to-parse trees.

The TreeCaps Architecture

TreeCaps combines Tree-based Convolutions for local feature extraction with Capsule Networks for hierarchical relationship modeling.

The TreeCaps architecture overview, showing the flow from vectorized AST to Code Capsules.

The model pipeline consists of four primary stages:

  1. Feature Extraction: A TBCNN slides a convolutional window over the AST to capture local structural patterns.
  2. Primary Variable Capsule (PVC) Layer: The TBCNN outputs are grouped into capsules. Because code snippets vary in size, the number of capsules in this layer is dynamic.
  3. Variable-to-Static (VTS) Routing: This is the paper's core innovation. To bridge the gap between dynamic inputs and fixed-size outputs, VTS identifies the most "prominent" capsules (those with the highest $L_2$ norm) and uses an iterative agreement process to "squeeze" the variable input into a static representation.
  4. Code Capsule (CC) Layer: The final layer produces embeddings used for specific tasks, such as classification or name prediction.

Experimental Evaluation

The authors evaluated TreeCaps on several established benchmarks, including the Sorting Algorithms (SA) dataset (1,000 Java programs) and the OJ dataset (52,000 C programs).

Accuracy comparison of TreeCaps variants against baseline models across different datasets and parsers.

As shown in the results table, TreeCaps-VTS achieves state-of-the-art performance. On the OJ classification task, TreeCaps-VTS reached 98.32% accuracy, significantly outperforming the original TBCNN (95.21%) and even sophisticated graph-based models like GGNN (85.89%). In function name prediction tasks (Java-Large), TreeCaps achieved an F1 score of 61.34, surpassing code2seq (58.96) and the graph-hybrid GREAT model (58.25).

Robustness and Insights

A key strength of TreeCaps is its resilience to "semantic-preserving transformations"—changes like variable renaming or dead code insertion that alter syntax without modifying logic. Because TreeCaps learns the relationships between structural components rather than just token sequences, it is much harder to "fool." In adversarial tests, TreeCaps-VTS was the most robust model, with only 12.49% of its predictions changing under attack, compared to 17.39% for TBCNN and over 22% for code2vec.

Conclusion

TreeCaps demonstrates that it is possible to achieve graph-level semantic understanding using only tree-based representations. By leveraging capsule networks and novel routing algorithms, it provides a highly accurate and robust solution for program comprehension. Future work will focus on improving explainability and applying the architecture to tasks like bug localization and code clone detection.

Summary updated

Abstract

Recently program learning techniques have been proposed to process source code based on syntactical structures (e.g., abstract syntax trees) and/or semantic information (e.g., dependency graphs). While graphs may be better than trees at capturing code semantics, constructing the graphs from code inputs through the semantic analysis of multiple viewpoints can lead to inaccurate noises for a specific software engineering task. Compared to graphs, syntax trees are more precisely defined on the grammar and easier to parse; unfortunately, previous tree-based learning techniques have not been able to learn semantic information from trees to achieve better accuracy than graph-based techniques. We have proposed a new learning technique, named TreeCaps, by fusing together capsule networks with tree-based convolutional neural networks to achieve a learning accuracy higher than some existing graph-based techniques while it is based only on trees. TreeCaps introduces novel variable-to-static routing algorithms into the capsule networks to compensate for the loss of previous routing algorithms. Aside from accuracy, we also find that TreeCaps is the most robust to withstand those semantic-preserving program transformations that change code syntax without modifying the semantics. Evaluated on a large number of Java and C/C++ programs, TreeCaps models outperform prior deep learning models of program source code, in terms of both accuracy and robustness for program comprehension tasks such as code functionality classification and function name prediction. Our implementation is publicly available at: https://github.com/bdqnghi/treecaps.
BibTeX
@inproceedings{bui2021treecaps,
  author = {Nghi D. Q. Bui and Yijun Yu and Lingxiao Jiang},
  title = {{TreeCaps: Tree-Based Capsule Networks for Source Code Processing}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2021},
  url = {https://openreview.net/forum?id=c67Vp16Hvv},
}
Figure