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). Although graphs may be better at capturing various viewpoints of code semantics than trees, constructing graph inputs from code needs static code semantic analysis that may not be accurate and introduces noise during learning. Although syntax trees are precisely defined according to the language grammar and easier to construct and process than graphs, previous tree-based learning techniques have not been able to learn semantic information from trees to achieve better accuracy than graph-based techniques. We propose a new learning technique, named TreeCaps, by fusing together capsule networks with tree-based convolutional neural networks, to achieve learning accuracy higher than 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.
Introduction: The Challenge of Code Representation
In the field of "Machine Learning for Code," the representation of programs is a fundamental challenge. Researchers typically represent programs as sequences, Abstract Syntax Trees (ASTs), or semantic graphs. While semantic graphs capture rich information like data flow, they are computationally expensive to construct and often introduce noise due to the limitations of static analysis. Conversely, ASTs are easier to generate and precisely defined by language grammars, but standard tree-based models—such as Tree-Based Convolutional Neural Networks (TBCNN)—often fall short of graph-based performance.
The primary limitation of traditional tree-based models lies in their reliance on simple max-pooling to aggregate features. Max-pooling acts as a "blunt instrument"; it identifies the presence of a feature but discards critical spatial and hierarchical relationships between code elements—the "part-whole" relationship. TreeCaps aims to bridge this gap, providing a model that is as easy to use as a tree-based approach but as semantically powerful as a graph-based one.
The TreeCaps Architecture
The core innovation of TreeCaps is the fusion of TBCNNs with Capsule Networks (CapsNets). Unlike standard neurons that output scalar activations, capsules represent features as vectors. In this paradigm, the length of the vector indicates the probability of a feature's existence, while its orientation represents its specific properties (the "pose").
As shown in the architecture diagram above, the pipeline consists of four main stages:
- Feature Extraction: A TBCNN processes the AST to extract local features from nodes.
- Primary Variable Capsule (PVC) Layer: These features are converted into capsules. Because different programs have different tree sizes, the number of capsules in this layer is variable.
- Variable-to-Static (VTS) Routing: This is the paper's primary algorithmic contribution. Standard capsule networks require a fixed number of capsules between layers. VTS solves this by selecting the most "prominent" capsules (those with the highest L2 norm) from the variable PVC layer and routing them into a fixed-size Secondary Capsule (SC) layer.
- Code Capsule (CC) Layer: The final layer produces a task-specific embedding used for classification or prediction.
Experimental Evaluation and Results
The authors evaluated TreeCaps on two main tasks: code functionality classification and function name prediction. The classification task utilized the Sorting Algorithms (SA) dataset and the OJ dataset (52,000 C programs). For function name prediction, the authors used large-scale Java benchmarks containing up to 16 million samples.
TreeCaps consistently outperformed prior state-of-the-art models across both tasks. On the OJ classification dataset, TreeCaps-VTS achieved 98.32% accuracy, surpassing TBCNN (95.21%) and the previous leader, ASTNN (98.2%).
As detailed in the table above, TreeCaps-VTS reached an F1 score of 61.34 on the Java-Large dataset, significantly outperforming Code2seq (58.96) and the graph-hybrid model GREAT (58.25). This demonstrates that the "tree-only" approach of TreeCaps can exceed the performance of complex graph-based models without the overhead of semantic graph construction.
Robustness to Code Refactoring
Beyond raw accuracy, TreeCaps demonstrates exceptional robustness to semantic-preserving program transformations. In real-world scenarios, code is often refactored (e.g., renaming variables or adding unused statements) without changing its underlying logic. When subjected to such adversarial changes, TreeCaps' predictions changed only 12.49% of the time. In comparison, Code2vec and TBCNN were significantly more fragile, with prediction change rates of 22.81% and 17.39%, respectively.
Conclusion
TreeCaps represents a significant step forward in program comprehension. By preserving the hierarchical structure of code through capsule routing rather than discarding it via max-pooling, the model achieves state-of-the-art results on large-scale benchmarks. While future work remains in areas like model explainability and broader task variety (such as bug localization), TreeCaps proves that tree-based architectures, when properly augmented with capsule logic, are highly effective for capturing the complex semantics of source code.
Summary updated