summaries: The paper discusses various baseline scoring mechanisms used for filter pruning that are norm-based and finds that none of the scoring mechanisms are particularly effective at pruning filters from CNNs. Moreover, all methods seem to perform very similar to each other. These conclusions are based on a theoretical (and experimental) analysis of the various scoring mechanisms under the assumption that trained filter weights follow a Gaussian-like distribution, which reveals that in this case the scoring mechanisms are insufficient to reliably discern the importance of filters since the resulting scores are very similar. The Gaussian-like assumption, which is termed "Convolution Weight Distribution Assumption" (CWDA), is validated through a large range of experiments on different architectures and data sets.

summaries: The goal of the paper is to bring into attention that many norm-based pruning criteria used for structured pruning are very similar, in that their ranking of the redundant filters is highly correlated. The key ingredient is the CWDA assumption that filters in a particular convolutional layer are iid and approximately follow a Gaussian distribution, which is shown based on extensive statistical hypothesis testing. Based on this assumption, they prove that these pruning criteria are roughly the same.

summaries: This paper analyzes the current limitations of existing magnitude-based pruning methods. First, the paper focuses on the similarities between three methods and then focuses on the redundancy in large networks. The paper also analyzes the weight distribution for a well-trained network and propose CDWA as a way to prove this distribution.  My main concern with this paper is the contribution to the field.

abstractText: Channel pruning is a popular technique for compressing convolutional neural networks (CNNs), where various pruning criteria have been proposed to remove the redundant filters. From our comprehensive experiments, we found two blind spots of pruning criteria: (1) Similarity: There are some strong similarities among several primary pruning criteria that are widely cited and compared. According to these criteria, the ranks of filters’ Importance Score are almost identical, resulting in similar pruned structures. (2) Applicability: The filters’ Importance Score measured by some pruning criteria are too close to distinguish the network redundancy well. In this paper, we analyze the above blind spots on different types of pruning criteria with layer-wise pruning or global pruning. We also break some stereotypes, such as that the results of `1 and `2 pruning are not always similar. These analyses are based on the empirical experiments and our assumption (Convolutional Weight Distribution Assumption) that the well-trained convolutional filters in each layer approximately follow a Gaussian-alike distribution. This assumption has been verified through systematic and extensive statistical tests.

authors:
Yann LeCun
John S Denker
Sara A Solla

title: Optimal brain damage

venue: In Advances in neural information processing systems,

authors:
Babak Hassibi
David G Stork

title: Second order derivatives for network pruning: Optimal brain surgeon

authors:
Song Han
Huizi Mao
William J Dally

title: Deep compression: Compressing deep neural networks with pruning, trained quantization and huffman coding

venue: arXiv preprint arXiv:1510.00149,

authors:
Yang He
Ping Liu
Ziwei Wang
Zhilan Hu
Yi Yang

title: Filter pruning via geometric median for deep convolutional neural networks acceleration

venue: In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition,

authors:
Hao Li
Asim Kadav
Igor Durdanovic
Hanan Samet
Hans Peter Graf

title: Pruning filters for efficient convnets

venue: arXiv preprint arXiv:1608.08710,

authors:
Yang He
Guoliang Kang
Xuanyi Dong
Yanwei Fu
Yi Yang

title: Soft filter pruning for accelerating deep convolutional neural networks

venue: arXiv preprint arXiv:1808.06866,

authors:
Jonathan Frankle
Michael Carbin

title: The lottery ticket hypothesis: Finding sparse, trainable neural networks

authors:
Hengyuan Hu
Rui Peng
Yu-Wing Tai
Chi-Keung Tang

title: Network trimming: A data-driven neuron pruning approach towards efficient deep architectures

venue: arXiv preprint arXiv:1607.03250,

authors:
Jian-Hao Luo
Jianxin Wu

title: An entropy-based pruning method for cnn compression

venue: arXiv preprint arXiv:1706.05791,

authors:
Pavlo Molchanov
Stephen Tyree
Tero Karras
Timo Aila
Jan Kautz

title: Pruning convolutional neural networks for resource efficient inference

venue: arXiv preprint arXiv:1611.06440,

authors:
Pavlo Molchanov
Arun Mallya
Stephen Tyree
Iuri Frosio
Jan Kautz

title: Importance estimation for neural network pruning

authors:
Zhuang Liu
Jianguo Li
Zhiqiang Shen
Gao Huang
Shoumeng Yan
Changshui Zhang

title: Learning efficient convolutional networks through network slimming

authors:
Wei He
Meiqing Wu
Mingfu Liang
Siew-Kei Lam

title: Cap: Context-aware pruning for semantic segmentation

venue: In Proceedings of the IEEE/CVF Winter Conference on Applications of Computer Vision,

authors:
Michael B Cohen
Yin Tat Lee
Gary Miller
Jakub Pachocki
Aaron Sidford

title: Geometric median in nearly linear time

venue: In Proceedings of the forty-eighth annual ACM symposium on Theory of Computing,

authors:
Jian-Hao Luo
Jianxin Wu
Weiyao Lin

title: Thinet: A filter level pruning method for deep neural network compression

authors:
Xiaohan Ding
Xiangxin Zhou
Yuchen Guo
Jungong Han
Ji Liu

title: Global sparse momentum sgd for pruning very deep neural networks

authors:
Xin Dong
Shangyu Chen
Sinno Pan

title: Learning to prune deep neural networks via layerwise optimal brain surgeon

authors:
Alex Renda
Jonathan Frankle
Michael Carbin

title: Comparing fine-tuning and rewinding in neural network pruning

authors:
Jianbo Ye
Xin Lu
Zhe Lin
James Z. Wang

title: Rethinking the smaller-norm-less-informative assumption in channel pruning of convolution layers

authors:
Adam Paszke
Sam Gross
Francisco Massa
Adam Lerer
James Bradbury
Gregory Chanan
Trevor Killeen
Zeming Lin
Natalia Gimelshein
Luca Antiga
Alban Desmaison
Andreas Kopf
Edward Yang
Zachary DeVito
Martin Raison
Alykhan Tejani
Sasank Chilamkurthy
Benoit Steiner
Lu Fang
Junjie Bai
Soumith Chintala

title: Pytorch: An imperative style, highperformance deep learning library

venue: Advances in Neural Information Processing Systems

authors:
Zechun Liu
Xiangyu Zhang
Zhiqiang Shen
Zhe Li
Yichen Wei
Kwang-Ting Cheng
Jian Sun

title: Joint multi-dimension pruning

venue: arXiv preprint arXiv:2005.08931,

authors:
Yawei Li
Shuhang Gu
Christoph Mayer
Luc Van Gool
Radu Timofte

title: Group sparsity: The hinge between filter pruning and decomposition for network compression

authors:
Yang He
Yuhang Ding
Ping Liu
Linchao Zhu
Hanwang Zhang
Yi Yang

title: Learning filter pruning criteria for deep convolutional neural networks acceleration

authors:
Yuchen Liu
David Wentzlaff
SY Kung

title: Rethinking class-discrimination based cnn channel pruning

venue: arXiv preprint arXiv:2004.14492,

authors:
Bailin Li
Bowen Wu
Jiang Su
Guangrun Wang
Liang Lin

title: Eagleeye: Fast sub-net evaluation for efficient neural network pruning

venue: arXiv preprint arXiv:2007.02491,

authors:
Zhuang Liu
Mingjie Sun
Tinghui Zhou
Gao Huang
Trevor Darrell

title: Rethinking the value of network pruning

venue: arXiv preprint arXiv:1810.05270,

authors:
Ting-Wu Chin
Ruizhou Ding
Cha Zhang
Diana Marculescu

title: Towards efficient model compression via learned global ranking

authors:
Wenxiao Wang
Cong Fu
Jishun Guo
Deng Cai
Xiaofei He

title: Cop: Customized deep model compression via regularized correlation-based filter-level pruning

title: Survey of simple, continuous, univariate probability distributions

authors:
Rodrigo R Pescim
Clarice GB Demétrio
Gauss M Cordeiro
Edwin MM Ortega
Mariana R Urbano

title: The beta generalized half-normal distribution

venue: Computational statistics & data analysis,

title: Applications of the fkg inequality and its relatives

venue: In Mathematical Programming The State of the Art,

title: The analysis of partial differential operators

venue: In The IEEE International Conference on Computer Vision (ICCV),

authors:
Yuandong Tian
Tina Jiang
Qucheng Gong
Ari Morcos

title: Luck matters: Understanding training dynamics of deep relu networks

authors:
I Bellido
Emile Fiesler

title: Do backpropagation trained neural networks have normal weight distributions

venue: In International Conference on Artificial Neural Networks,

title: BAYESIAN LEARNING FOR NEURAL NETWORKS

venue: PhD thesis, University of Toronto,

authors:
Jinwook Go
Byungjoon Baek
Chulhee Lee

title: Analyzing weight distribution of feedforward neural networks and efficient weight initialization. In Joint IAPR International Workshops on Statistical Techniques in Pattern Recognition (SPR) and Structural and Syntactic Pattern Recognition (SSPR)

title: On the kolmogorov-smirnov test for normality with mean and variance unknown

venue: Journal of the American statistical Association,

title: Student’s t-test under symmetry conditions

venue: Journal of the American Statistical Association,

authors:
Kaiming He
Xiangyu Zhang
Shaoqing Ren
Jian Sun

title: Deep residual learning for image recognition

venue: In The IEEE Conference on Computer Vision and Pattern Recognition (CVPR),

authors:
Ilya Sutskever
James Martens
George Dahl
Geoffrey Hinton

title: On the importance of initialization and momentum in deep learning

venue: In International conference on machine learning,

authors:
Karen Simonyan
Andrew Zisserman

title: Very deep convolutional networks for large-scale image recognition

venue: arXiv preprint arXiv:1409.1556,

authors:
Boris T Polyak
Anatoli B Juditsky

title: Acceleration of stochastic approximation by averaging

venue: SIAM journal on control and optimization,

title: One weird trick for parallelizing convolutional neural networks

venue: arXiv preprint arXiv:1404.5997,

authors:
Diederik P Kingma
Jimmy Ba

title: Adam: A method for stochastic optimization

venue: arXiv preprint arXiv:1412.6980,

authors:
Bing Xu
Naiyan Wang
Tianqi Chen
Mu Li

title: Empirical evaluation of rectified activations in convolutional network

venue: arXiv preprint arXiv:1505.00853,

authors:
Gao Huang
Zhuang Liu
Laurens Van Der Maaten
Kilian Q Weinberger

title: Densely connected convolutional networks

authors:
John Duchi
Elad Hazan
Yoram Singer

title: Adaptive subgradient methods for online learning and stochastic optimization

venue: Journal of machine learning research,

authors:
Senwei Liang
Yuehaw Khoo
Haizhao Yang

title: Drop-activation: Implicit parameter reduction and harmonic regularization

venue: arXiv preprint arXiv:1811.05850,

title: Identity mappings in deep residual networks

venue: In European conference on computer vision,

authors:
Ekin D Cubuk
Barret Zoph
Dandelion Mane
Vijay Vasudevan
Quoc V Le

title: Autoaugment: Learning augmentation strategies from data

authors:
Sergey Zagoruyko
Nikos Komodakis

title: Wide residual networks

venue: arXiv preprint arXiv:1605.07146,

title: Adadelta: an adaptive learning rate method

venue: arXiv preprint arXiv:1212.5701,

authors:
Terrance DeVries
Graham W Taylor

title: Improved regularization of convolutional neural networks with cutout

venue: arXiv preprint arXiv:1708.04552,

authors:
Sangdoo Yun
Dongyoon Han
Seong Joon Oh
Sanghyuk Chun
Junsuk Choe
Youngjoon Yoo

title: Cutmix: Regularization strategy to train strong classifiers with localizable features

authors:
Jie Hu
Li Shen
Gang Sun

title: Squeeze-and-excitation networks

title: Delving deep into rectifiers: Surpassing human-level performance on imagenet classification

authors:
Alex Krizhevsky
Geoffrey Hinton

title: Learning multiple layers of features from tiny images

authors:
Zhongzhan Huang
Senwei Liang
Mingfu Liang
Haizhao Yang

title: Dianet: Dense-andimplicit attention network

venue: arXiv preprint arXiv:1905.10671,

authors:
HyunJae Lee
Hyo-Eun Kim
Hyeonseob Nam

title: Srm: A style-based recalibration module for convolutional neural networks

authors:
Xavier Glorot
Yoshua Bengio

title: Understanding the difficulty of training deep feedforward neural networks

venue: In Proceedings of the thirteenth international conference on artificial intelligence and statistics,

authors:
Olga Russakovsky
Jia Deng
Hao Su
Jonathan Krause
Sanjeev Satheesh
Sean Ma
Zhiheng Huang
Andrej Karpathy
Aditya Khosla
Michael Bernstein

title: Imagenet large scale visual recognition challenge

venue: International journal of computer vision,

authors:
Sanghyun Woo
Jongchan Park
Joon-Young Lee
In So Kweon

title: Cbam: Convolutional block attention module

venue: In Proceedings of the European Conference on Computer Vision (ECCV),

authors:
Yann LeCun
Léon Bottou
Yoshua Bengio
Patrick Haffner

title: Gradient-based learning applied to document recognition

venue: Proceedings of the IEEE,

authors:
Senwei Liang
Zhongzhan Huang
Mingfu Liang
Haizhao Yang

title: Instance enhancement batch normalization: an adaptive regulator of batch noise

authors:
Andrew M Saxe
James L McClelland
Surya Ganguli

title: Exact solutions to the nonlinear dynamics of learning in deep linear neural networks

venue: arXiv preprint arXiv:1312.6120,

authors:
Xiang Li
Xiaolin Hu
Jian Yang

title: Spatial group-wise enhance: Improving semantic feature learning in convolutional networks

venue: arXiv preprint arXiv:1905.09646,

authors:
Vijay Badrinarayanan
Alex Kendall
Roberto Cipolla

title: Segnet: A deep convolutional encoder-decoder architecture for image segmentation

venue: IEEE transactions on pattern analysis and machine intelligence,

authors:
Shaoqing Ren
Kaiming He
Ross Girshick
Jian Sun

title: Faster r-cnn: Towards real-time object detection with region proposal networks. In Advances in neural information processing

authors:
Hengshuang Zhao
Jianping Shi
Xiaojuan Qi
Xiaogang Wang
Jiaya Jia

title: Pyramid scene parsing network

authors:
Ning Xu
Brian Price
Scott Cohen
Thomas Huang

title: Deep image matting

authors:
Sebastian Lutz
Konstantinos Amplianitis
Aljosa Smolic

title: Alphagan: Generative adversarial networks for natural image matting

venue: arXiv preprint arXiv:1807.10088,

authors:
Justin Johnson
Alexandre Alahi
Li Fei-Fei

title: Perceptual losses for real-time style transfer and super-resolution

authors:
Alec Radford
Luke Metz
Soumith Chintala

title: Unsupervised representation learning with deep convolutional generative adversarial networks

venue: arXiv preprint arXiv:1511.06434,

authors:
Ilya Loshchilov
Frank Hutter

title: Sgdr: Stochastic gradient descent with warm restarts

venue: arXiv preprint arXiv:1608.03983,

heading: 1 Introduction

text:
Pruning [1, 2, 3, 4] a trained neural network is commonly seen in network compression. In particular, for CNNs, channel pruning refers to the pruning of the filters in the convolutional layers. There are several critical factors for channel pruning. Procedures. One-shot method [5]: Train a network from scratch; Use a certain criterion to calculate filters’ Importance Score, and prune the filters which have small Importance Score; After additional training, the pruned network can recover its accuracy to some extent. Iterative method [1, 6, 7]: Unlike One-shot methods, they prune and fine-tune a network alternately. Criteria. The filters’ Importance Score can be definded by a given criterion. From different ideas, many types of pruning criteria have been proposed, such as Norm-based [5], Activation-based [8, 9], Importance-based [10, 11], BN-based [12] and so on. Strategy. Layer-wise pruning: In each layer, we can sort and prune the filters, which have small Importance Score measured by a given criterion. Global pruning: Different from layer-wise pruning, global pruning [12, 13] sort the filters from all the layers through their Importance Score and prune them.
In this work, we conduct our investigation on a variety of pruning criteria. As one of the simplest and most effective channel pruning criteria, `1 pruning [5] is widely used in practice. The core idea of this criterion is to sort the `1 norm of filters in one layer and then prune the filters with a small `1 norm. Similarly, there is `2 pruning which instead leverages the `2 norm [7, 6]. `1 and `2 can be seen as the criteria which use absolute Importance Score of filters. Through the study of the distribution of norm, [4] demonstrates that these criteria should satisfy two conditions: (1) the variance of the norm of the filters cannot be too small; (2) the minimum norm of the filters should be small enough. Since
∗Corresponding author: pluo.lhi@gmail.com; ‡ co-first author.
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
these two conditions do not always hold, a new criterion considering the relative Importance Score of the filters is proposed [4]. Since this criterion uses the Fermat point (i.e., geometric median [14]), we call this method Fermat. Due to the high calculation cost of Fermat point, [4] further relaxed the Fermat and then introduced another criterion denotes as GM. To illustrate each of the pruning criteria, let Fij ∈ RNi×k×k represent the jth filter of the ith convolutional layer, where Ni is the number of input channels for ith layer and k denotes the kernel size of the convolutional filter. In ith layer, there are Ni+1 filters. For each criteria, details are shown in Table 2, where F denotes the Fermat point of Fij in Euclidean space. These four pruning criteria are called Norm-based pruning in this paper as they utilize norm in their design.
Previous works [15, 3, 16, 17, 18], including the criteria mentioned above, the main concerns commonly consist of (a) How much the model was compressed; (b) How much performance was restored; (c) The inference efficiency of the pruned network and (d) The cost of finding the pruned network. However, few works discussed the following two blind spots about the pruning criteria:
(1) Similarity: What are the actual differences among these pruning criteria? Taking the VGG16 and ResNet18 on ImageNet as an example, we show the ranks of filters’ Importance Score under different criteria in Table 1. It is obvious that they have almost the same sequence, leading to similar pruned structures. In this situation, the criteria used absolute Importance
Score of filters (`1,`2) and the criteria used relative Importance Score of filters (Fermat, GM) may not be significantly different.
(2) Applicability: What is the applicability of these pruning criteria to prune the CNNs? There is a toy example w.r.t. `2 criterion. If the `2 norm of the filters in one layer are 0.9, 0.8, 0.4 and 0.01, according to smaller-norm-less-informative assumption [19], it’s apparent that we should prune the last filter. However, if the norm are close, such as 0.91, 0.92, 0.93, 0.92, it is hard to determine which filter should be pruned even though the first one is the smallest. In Fig. 1, we demonstrate some real examples, i.e., the visualization of Applicability problem under different networks and criteria.
In this paper, we provide comprehensive observations and in-depth analysis of these two blind spots. Before that, in Section 2, we propose an assumption about the parameters distribution of CNNs, called Convolution Weight Distribution Assumption (CWDA), and use it as a theoretical tool to analyze the two blind spots. We explore the Similarity and Applicability problem of pruning criteria in the following order: (1) Norm-based criteria (layer-wise pruning) in Section 3; (2) Other types
of criteria (layer-wise pruning) in Section 4; (3) and different types of criteria (global pruning) in Section 5. Last but not least, we provide further discussion on: (i) the conditions for CWDA to be satisfied, (ii) how our findings help the community in Section 6. In order to focus on the pruning criteria, all the pruning experiments are based on the relatively simple pruning procedure, i.e., one-shot method.
The main contributions of this work are two-fold:
(1) We analyze the Applicability problem and the Similarity of different types of pruning criteria. These two blind spots can guide and motivate researchers to design more reasonable criteria. We also break some stereotypes, such as that the results of `1 and `2 pruning are not always similar.
(2) We propose and verify an assumption called CWDA, which reveals that the well-trained convolutional filters approximately follow a Gaussian-alike distribution. Using CWDA, we succeeded in explaining the multiple observations about these two blind spots theoretically.

heading: 2 Weight Distribution Assumption

text:
In this section, we propose and verify an assumption about the parameters distribution of the convolutional filters.
(Convolution Weight Distribution Assumption) Let Fij ∈ RNi×k×k be the jth well-trained filter of the ith convolutional layer. In general2, in ith layer, Fij (j = 1, 2, ..., Ni+1) are i.i.d and follow such a distribution:
Fij ∼ N(0,Σidiag + ·Σiblock), (1)
where Σiblock = diag(K1,K2, ...,KNi) is a block diagonal matrix and the diagonal elements of Σiblock are 0. is a small constant. The values of the off-block-diagonal elements are 0 and Kl ∈ Rk
2×k2 , l = 1, 2, ..., Ni. Σidiag = diag(a1, a2, ..., aNi×k×k) is a diagonal matrix and the elements of Σidiag are close enough.
This assumption is based on the observation shown in the Fig. 2. To estimate Σidiag + ·Σiblock, we use the correlation matrix FFT where F ∈ R(Ni×k×k)×Ni+1 denotes all the parameters in ith layer. Taking a convolutional layer of ResNet18 trained on ImageNet as an example, we find that FFT is a block diagonal matrix. Specifically, each block is a k2 × k2 matrix and the off-diagonal elements are close to 0. We visualize the jth filter Fij ∈ RNi×k×k in ith layer in Fig. 2(c), and this phenomenon reveals that the parameters in the same channel of Fij tend to be linearly correlated, and the parameters of any two different channels (yellow and green channel in Fig. 2(c)) in Fij only have a low linear correlation.

heading: 2.1 Statistical test for CWDA

text:
In fact, CWDA is not easy to be verified, e.g., for ResNet164 trained on Cifar100, the number of filters in the first stage is only 16, which is too small to be used to estimate the statistics in CWDA accurately. Thus, We consider verifying four necessary conditions of CWDA:
(1) Gaussian. Whether the weights of Fij approximately follows a Gaussian-alike distribution; (2) Variance. Whether the variance of the diagonal elements of Σdiag are small enough; (3) Mean. Whether the mean of weights of Fij is close to 0. (4) The magnitude of . Whether is small enough.
The results of the tests are shown in Appendix P, where we consider a variety of factors for the statistical tests, including different network structure, optimizer, regularization, initialization, dataset,
2In Section 6, we make further discussion and analysis on the conditions for CWDA to be satisfied.
training strategy, and other tasks in computer vision (e.g., semantic segmentation, detection and so on). The test results show that CWDA has a great generality for CNNs.

heading: 3 About the Norm-based criteria

text: We start from the criteria in Table 2, which are widely cited and compared [21, 22, 23, 24, 25].

heading: 3.1 Similarity

text:
In this section, we further verify the observation that the Norm-based pruning criteria in Table 2 are highly similar from two perspectives. Empirically, we conducted large amount of experiments on image classification to investigate the similarities. Theoretically, we rigorously prove the similarities of the criteria in Table 2 in layer-wise pruning under CWDA.
Empirical Analysis. (1) In Fig. 3, we show the test accuracy of the ResNet56 after pruning and fine-tuning under different pruning ratios and datasets. The test accuracy curves of different pruning criteria at different stages are very close under different pruning ratios. This phenomenon implies that those pruned networks using different Norm-based criteria are very similar, and there are strong similarities among these pruning criteria. The experiments about other commonly used configs of pruning ratio can be found in Appendix L. (2) In Fig. 4, we show the Spearman’s rank correlation coefficient3 (Sp) between different pruning criteria. The Sp in most convolutional layers are more than 0.9, which means the network structures are almost
the same after pruning. Note that the Sp in transition layer are relatively small, and the transition layer refers to the layer where the dimensions of the filter change, like the layer between stage 1 and stage 2 of a ResNet. The reason for this phenomenon may be that the layers in these areas are sensitive. It is interesting but will not greatly impact the structural similarity of the whole pruned network. The similar observations are shown in Fig. 2 in [16], Fig. 6 and Fig. 10 in [5].
3Sp is a nonparametric measurement of ranking correlation, and it assesses how well the relationship between two variables can be described using a monotonic function, i.e., filters ranking sequence in the same layer under two criteria in this paper.
Theoretical Analysis. Besides the experimental verification, the similarities via using layer-wise pruning among the criteria in Table 2 can also be proved theoretically in this section. Let C1 and C2 be two pruning criteria to calculate the Importance Score for all convolutional filters in one layer. If they can produce the similar ranks of Importance Score, we define that C1 and C2 are approximately monotonic to each other and use C1 ∼= C2 to represent this relationship. In Section 3.1, we use the Sp to describe this relationship but it’s hard to be analyzed theoretically. Therefore, we focus on a stronger condition. Let X = (x1, x2, ..., xk) and Y = (y1, y2, ..., yk) be two given sequences4. we first normalize their magnitude, i.e., let X̂ = X/E(X) and Ŷ = Y/E(Y) . This operation does not change the ranking sequence of the elements of X and Y, because E(X) and E(Y) are constants, i.e., X̂ ∼= Ŷ ⇔ X ∼= Y. After that, if both Var(X̂/Ŷ) and Var(Ŷ/X̂) are small enough, then the Sp between X and Y is close to 1, where X̂/Ŷ = (x̂1/ŷ1, .., x̂k/ŷk). The reason is that in these situations, the ratio X̂/Ŷ and Ŷ/X̂ will be close to two constants a, b. For any 1 ≤ i ≤ k, x̂i ≈ a · ŷi and ŷi ≈ b · x̂i. So, ab ≈ 1 and a, b 6= 0. Therefore, there exists an approximately monotonic mapping from ŷi to x̂i (linear function), which makes the Sp between X and Y close to 1. With this basic fact, we propose the Theorem 1, which implies that many Norm-based pruning criteria produces almost the same ranks of Importance Score. Theorem 1. Let n−dimension random variable X meet CWDA, and the pair of criteria (C1, C2) is one of (`1, `2), (`2,Fermat) or (Fermat,GM), we have
max { VarX ( Ĉ2(X)
Ĉ1(X)
) ,VarX ( Ĉ1(X)
Ĉ2(X)
)} . B(n), (2)
where Ĉ1(X) denotes C1(X)/E(C1(X)) and Ĉ2(X) denotes C2(X)/E(C2(X)). B(n) denotes the upper bound of left-hand side and when n is large enough, B(n)→ 0.
Proof. (See Appendix C).
In specific, for ith convolutional layer of a CNN, since Fij ∈ Rn, j = 1, 2, ...Ni+1, meet CWDA and the dimension n is generally large, we can obtain `1 ∼= `2, `2 ∼= Fermat and Fermat ∼= GM according to Theorem 1. Therefore, we have `1 ∼= `2 ∼= Fermat ∼= GM, which verifies the strong similarities among the criteria shown in Table 2.

heading: 3.2 Applicability

text:
In this section, we analyze the Applicability problem of the Norm-based criteria. In Fig. 1 (Right), we know that there are some cases where the values of Importance Score measured by `2 criterion are very close (e.g., the distribution looks sharp), which make `2 criterion cannot distinguish the redundant filters well. It’s related to the variance of Importance Score. [4] argue that a small norm deviation (the values of variance of Importance Score are small) makes it difficult to find an appropriate threshold to select filters to prune. However, even if the values of the variance are large, it still cannot guarantee to solve this problem. Since the magnitude of these Importance Score may be much greater than the values of the variance, we can use the mean of Importance Score to represent their magnitude. Therefore, we consider using a relative variance Varr[C(FA)] to describe the Applicability problem. Let E[C(FA)] > 0 and
Varr[C(FA)] = Var[C(FA)]/E[C(FA)], (3) where C is a given pruning criterion and FA denotes the filters in layer A. The criterion C for layer A has Applicability problem when Varr[C(FA)] is close to 0. Then we introduce the Proposition 1 to provide the estimation of the mean and variance w.r.t. different criteria when the CWDA is hold: Proposition 1. If the convolutional filters FA in layer A meet CWDA, then we have following estimations:
Criterion Mean Variance `1(FA) √ 2/πσAdA (1− 2π )σ 2 AdA
`2(FA) √ 2σAΓ( dA+1
2 )/Γ( dA 2 ) σ2A/2
Fermat(FA) √ 2σAΓ( dA+1
2 )/Γ( dA 2 ) σ2A/2
4Since X is not random variables here, E(X) and Var(X) denote the average value ∑k i=1 xi/k and the
sample variance ∑k i=1(xi − E(X))/(k − 1), respectively.
where dA and σ2A denote the dimension of FA and the variance of the weights in layer A, respectively.
Proof. (See Appendix A). Based on the Proposition 1, we further provide the theoretical analysis for each criteria:
(i) For `2(FA). From Proposition 1, we can obtain that
Varr[`2(FA)] = σ2A 2 /[ √ 2σAΓ( dA + 1 2 )/Γ( dA 2 )] = O(σA/g(dA)), (4)
where g(dA) = Γ(dA+12 )/Γ( dA 2 ) is a monotonically increasing function w.r.t dA. From Eq. (4), Varr[`2(FA)] depend on σA and dA. When σA is small or dA is large enough, Varr[`2(FA)] tends to be 0.
(ii) For Fermat(FA). From the proof in Appendix D, we know that the Fermat point F of FA and the origin 0 approximately coincide. From Table 1, ||F− FA||2 ≈ ||0− FA||2 = ||FA||2. Therefore, the mean and variance of Fermat(FA) are the same as `2(FA)’s in Proposition 1. Hence, a similar conclusion can be obtained for Fermat criterion. i.e., the Importance Score tends to be identical and it’s hard to distinguish the network redundancy well when σA is small or dA is large enough.
(iii) For `1(FA). Intuitively, the `1 criterion should have the same conclusion as the `2 criterion. However, given the Proposition 1, we can obtain that
Varr[`1(FA)] = (1− 2
π )σ2AdA/[
√ 2/πσAdA] = (π) · σA, (5)
where (π) < 1 is a constant w.r.t π. Note that Varr[`1(FA)] only depend on σA, but not the dimension n. Moreover, for the common network structures, like VGG, ResNet shown in Fig. 6 (b) and (d), the dimension of the filters are usually large enough. Therefore, compared with `2, `1 criterion is relatively not prone to have Applicability problems, unless the σA is very small.

heading: 4 About other types of pruning criteria

text:
In this section, we study the Similarity and Applicability problem in other types of pruning criteria through numerical experiments, such as Activation-based pruning [8, 9], Importance-based pruning [10, 11] and BN-based pruning [12]. For each type, we choose two representative criteria and we call them: (1) Norm-based: `1 and `2; (2) Importance-based: Taylor `1 and Taylor `2 [10, 11, 26]; (3) BN-based: BN_γ5 and BN_β [12]; (4) Activation-based: Entropy [9] and APoZ [8]. The details of these criteria can be found in Appendix K.
The Similarity for different types of pruning criteria. In Fig. 5 (a-d), we show the Sp between different types of pruning criteria, and only the Sp greater than 0.7 are shown because if Sp < 0.7, it means that there is no strong similarity between two criteria in the current layer.
5The empirical result for slimming training [12] is shown in Appendix Q.
According to the Sp shown in Fig. 5 (a-d), we obtain the following observations: (1) As verified in Section 3.1, `1 and `2 can maintain a strong similarity in each layer; (2) In the layers shown in Fig. 5 (a) and Fig. 5 (d), the Sp between most different pruning criteria are not large in these layers, which indicates that these criteria have great differences in the redundancy measurement of convolutional filters. This may lead to a phenomenon that one criterion considers a convolutional filter to be important, while another considers it redundant. We find a specific example which is shown in Appendix J; (3) Intuitively, the same type of criteria should be similar. However, Fig. 5 (b) and Fig. 5 (c) show that the Sp between Taylor `1 and Taylor `2 is not large, but Taylor `2 has strong similarity with both two Norm-based criteria. Moreover, the Sp between BN_γ and each Norm-based criteria exceeds 0.9, but it is not large in other layers (Fig. 5 (a) and Fig. 5 (d)). These phenomena are worthy of further study.
The Applicability for different types of pruning criteria. According to the analysis in Section 3.2, the Applicability problem depends on the mean and variance of the Importance Score. Fig. 5 (g-i) shows the result of the Importance Score measured by different pruning criteria on each layer of VGG16. Due to the difference in the magnitude of Importance Score for different criteria, for the convenience of visualization, the value greater than 1 is represented by 1.
First, we analyze the Norm-based criteria. In most layers, the relative variance Varr[`2] is much smaller than that of Varr[`1], which means that the `2 pruning has Applicability problem in VGG16, while the `1 does not. This is consistent with our conclusion in Section 3.2. Next, for the Activationbased criteria, the relative variance Varr is large in each layer, which means that these two Activationbased criteria can distinguish the network redundancy well from their measured filters’ Importance Score. However, for the Importance-based and BN-based criteria, their relative variance Varr are close to 0. According to Section 3.2, these criteria have Applicability problem, especially in the deeper layers (e.g., from 6th layer to the last layer).
5 About global pruning
Compared with layer-wise pruning, global pruning is more widely [27, 10, 12] used in the current research of channel pruning. Therefore, in this section we may also analyze the Similarity and Applicability problem of global pruning.
Applicability while using global pruning. In fact, for global pruning, both `1 and `2 criteria are not prone to Applicability problems. From Proposition 1, we show that the estimations for the mean of Importance Score in
layer A for `1 and `2 are σA · dA √
2 π and√
2σA·Γ(dA+12 )/Γ( dA 2 ), respectively. Since σA
and dA are quite different, shown in Fig. 6 (b) and (d), hence the variance of the Importance Score may be large in this situation. Fig. 6 (a) and (c) show such kind of difference of the magnitude on different convolutional layers. In addition, from our estimations in Fig. 6 (c), this inconsistent magnitude can be explained for another common problem in practical applications of global pruning: the ResNet is easily pruned off. As shown in Fig. 6 (c), we take ResNet56 as an example. Since the Importance Score in first stage is much smaller than the Importance Score in the deeper layer,
global pruning will give priority to prune the convolutional filters of the first stage. For problem, we suggest that some normalization tricks should be implemented or a protection mechanism should be established, e.g., a mechanism which can ensure that each layer has at least a certain number of convolutional filters that will not be pruned. Unlike some previous works [13, 28, 29], which make suggestions from qualitative observation, we provide a quantitative view to illustrate that these tricks are necessary.
Similarity while using global pruning. In Fig. 5 (e-f), we show the similarity of different types of pruning criteria using global pruning on VGG16 and ResNet56. Comparing to the results from the layer-wise pruning shown in Fig. 5 (a-d), we can find that the similarities of most pruning criteria are quite different in global pruning. In addition, the same criteria may have different results for different network structures in global pruning, e.g., in Fig. 5 (e), we can find `2 ∼= Taylor `2 and BNγ ∼= `2, but this observation does not hold in Fig. 5 (f). In particular, different from the result about ResNet56 in Fig. 5 (f), the similarity between `1 and `2 is not as strong as the one in the layer-wise case. This phenomenon is counter intuitive.
To understand this phenomenon, we first consider about a simple case, i.e., the unpruned network has only two convolutional layers (layer A and layer B). The filters in these two layers are FA = (F 1A, F 2 A, ..., F n A) and FB = (F 1 B , F 2 B , ..., F m B ). According to CWDA, for 1 ≤ i ≤ n and 1 ≤ j ≤ m, F iA and F j B can follow N(0, σ 2 AIdA) and N(0, σ 2 BIdB ), respectively. Next, we show Sp between Importance Score measured by `1 and `2 pruning in different dimension ratio dA/dB , σA and σB in Fig. 7 (e-h). Moreover, to analyze this phenomenon concisely, we draw some scatter plots as shown in Fig. 7 (a-d), where the coordinates of each point are given by (value of `1, value of `2). The set of the points consisting of the filters in layer A is called group-A. Then we introduce the Proposition 2. Proposition 2. If the convolutional filters FA in layer A meet CWDA, then E[`1(FA)/`2(FA)] and E[`2(FA)/`1(FA)] only depend on their dimension dA. Proof. (See Appendix A). Now we analyze the simple case under different situations:
(1) For dA/dB = 1. If σ2A = σ 2 B , in fact, it’s the same situation as layer-wise pruning. From Theorem 1, we know that group-A and group-B coincide and approximately lie on the same line, resulting `1 ∼= `2 . If σ2A 6= σ2B , group-A and group-B lie on two lines, respectively. However, these two lines have the same slope based on Proposition 2, as shown in Fig. 7 (a). For these reasons, we have `1 ∼= `2 when dA/dB = 1. (2) For dA/dB 6= 1. In Fig. 7 (b-d), there are three main situations about the position relationship between group-A and group-B. In Fig. 7 (b), according to Theorem 1, the points in group-A and group-B are monotonic respectively. Moreover, their Importance Score measured by `1 and `2 do not overlap, which make `1 and `2 are approximately monotonic overall. Thus, `1 ∼= `2. However, for Fig. 7 (c-d), the Sp is small since the points in these two group are not monotonic (the Importance Score measured by `1 or `2 has a large overlap). From Proposition 1 and the approximation Γ(dA+12 )/Γ( dA 2 ) ≈ √ dA/2 (Appendix D), these two situations can be described as:
σAdA ≈ σBdB or σA √ dA ≈ σB √ dB , (6)
where dA 6= dB . Through Eq. (6) we can obtain the two red lines shown in Fig. 7 (f-h). It can be seen that the area surrounded by these two red lines is consistent with the area where the Sp is relatively small, which means our analysis is reasonable. Based on the above analysis, we can summarize the conditions about `1 ∼= `2 in global pruning for two convolutional layers as shown in Table 3.
Table 3: The conditions about `1 ∼= `2 in global pruning for two layers (layer A and layer B)
dA = dB? σAσB ≈ dB dA ? σA σB ≈ √ dB√ dA ? `1 ∼= `2?
(1) ! – – ! (2) % % % ! (3) % ! – % (4) % – ! %
Next, we go back to the the situation about real neural networks in Fig. 5 (e-f). (1) For ResNet56. As shown in Fig.6 (d), the dimensions of the filters in each stage are almost the same. From Table 3 (1), the pruning results after `1 and `2 pruning in each stage are similar. And, the magnitudes of the Importance Score in each stage are very different, since Table 3 (2), we can obtain that `1 ∼= `2 for ResNet56.
(2) For VGG16. As shown in Fig.6 (a-b), compared with ResNet56, VGG16 has some layers with different dimensions but similar Importance Score measured by `1 or `2, such as “layer 2” and “layer
8” for `2 criterion in Fig.6 (a). From Table 3 (3-4), these pairs of layers make the Sp small, which explain why the result of `1 and `2 pruning is not similar in Fig. 5 (e) for VGG16. In Appendix O, more experiments show that we can increase the Sp in global pruning by ignoring part of these pairs of layers, which support our analysis.

heading: 6 Discussion

heading: 6.1 Why CWDA sometimes does not hold?

text:
CWDA may not always hold. As shown in Appendix P, a small number of convolutional filters may not pass all statistical tests. In this section, we try to analyze this phenomenon.
(1) The network is not trained well enough. The distribution of parameters should be discussed only when the network is trained well. If the network does not converge, it is easy to construct a scenario which does not satisfy CWDA, e.g., for a network with uniform initialization, when it is only be trained for a few epochs, the distribution of parameters may be still close to a uniform distribution. At this time, the distribution obviously does not satisfy CWDA. A specific example is in Appendix I.
(2) The number of filters is insufficient. In Appendix P, the layers that can not pass the statistical tests are almost those whose position is in the front of the network. A common characteristic of these layers is that they have a few filters, which may not estimate statistics well. Taking the second convolutional layer (64 filters) in VGG16 on CIFAR10 as an example, first, the filters in this layer can not pass all the statistical tests. And then the Sp in this transition layer is relatively small, as shown in Fig. 4. However, in Fig. 8, we change the number of filters in this layer from 64 to 128 or 256. After that, the Sp increases significantly, and the filters can pass all the statistical tests when the number of filters is 256. These observations suggest that the number of filters is a major factor for CWDA to be hold.

heading: 6.2 How our findings help the community?

text:
(1) We propose an assumption about the parameters distribution of the CNNs called CWDA, which is an effective theoretical tool for analyzing convolutional filter. In this paper, CWDA is successfully used to explain many phenomena in the Similarity and Applicability of pruning criteria. In addition, it also explains why the ResNet is easily pruned off in global pruning. In Section 2.1, since CWDA can pass statistical tests in various situations, it can be expected that it can also be used as an effective and concise analysis tool for other CNNs-related areas, not just pruning area.
(2) In this paper, we study the Similarity and Applicability problem about pruning criteria, which can guide and motivate the researchers to design more reasonable criteria. For Applicability problem, we suggest that, intuitively, it is reasonable that the Importance Score should be distinguishable for the proposed novel criteria. For Similarity, as more and more criteria are proposed, these criteria can be used for ensemble learning to enhance their pruning performance [23]. In this case, the similarity analysis between criteria in this paper is important, because highly similar criteria cannot bring gains to ensemble learning.
(3) In pruning area, `1 and `2 are usually regarded as the same pruning criteria, which is intuitive. In layer-wise pruning, we do prove that the `1 and `2 pruning are almost the same. However, in global pruning, the pruning results by these two criteria are sometimes very different. In addition, compared
with `1 criterion, `2 criterion is prone to Applicability problems. These counter-intuitive phenomena enlighten us that we can’t just rely on intuition when analyzing problems.
(4) Similar to the setting in Fig. 5, we can explore the effect of pruning filters with similar Importance Score on the performance. First, we find that the criteria (`2,Taylor `1, Taylor `2, BNγ and BNβ) for VGGNet can cause the Applicability problem in most layers (Fig. 5). As such, we randomly select 10% or 20% filters to be pruned by the uniform distribution U [0, 1] in each layer, and the selective filters will be in similar Importance Score. Finally, we finetune the pruned model (there are 20 random repeated experiments). ∆ denotes the difference between max acc. and min acc. (i.e. max acc. - min acc.) . Since their Importance Score are very similar, when the network is pruned and finetuned, it can be expected that the performance should be similar in these repeated experiments. However, from the results in the above table, although the Importance Score of the pruned filters is very close, we can still get pruning results with very different results (e.g. the ∆ of VGG16 on `2 are more than 1). It means that these criteria may not really represent the importance of convolutional filters. Therefore, it is necessary to re-evaluate the correctness of the existing pruning criteria.
Acknowledgments. Z. Huang gratefully acknowledges the technical and writing support from Mingfu Liang (Northwestern University), Senwei Liang (Purdue University) and Wei He (Nanyang Technological University). Moreover, he sincerely thanks Mingfu Liang for offering his selfpurchasing GPUs and Qinyi Cai (NetEase, Inc.) for checking part of the proof in this paper. This work was supported in part by the General Research Fund of Hong Kong No.27208720, the National Key R&D Program of China under Grant No. 2020AAA0109700, the National Science Foundation of China under Grant No.61836012 and 61876224, the National High Level Talents Special Support Plan (Ten Thousand Talents Program), and GD-NSF (no.2017A030312006).

title: Rethinking the Pruning Criteria for Convolutional Neural Network


summaries: This paper proposes GraphCodeBERT as a Transformer-based pretrained model for programming language that incorporates data flow information in the graph representation of variables in the code. The data flow graph encodes the structure of variables based on “where-the-value-comes-from” from the AST parse. The pretrained model is jointly trained on the code, the natural language comment of the code, and the data flow graph of the code. In addition to the Masked Language Modeling objective, two new pretraining objectives are proposed including predicting the edge of the data flow graph and predicting the alignment of variables between data flow graph and code. The graph-guided masked attention is used such that the attention can only occur if two variables have an edge in the data flow graph or there is an alignment between data flow graph and code. The experiments show that GraphCodeBERT can deliver improvements on Natural Language Code Search, Code Clone Detection, Code Translation, and Code Refinement.

summaries: The authors present Graph Code BERT, the first language model that leverages data flow to learn code representation. They use three objective functions: Masked Language Modeling, Edge Prediction, and Node Alignment. They claim their structure-aware pre-training can help improving performance on code-related downstream tasks, including code search, clone detection, code translation, and code refinement.

summaries: This work address the pretraining over code and text. It proposes to leverage data flow as additional inputs, and add two structure aware pre-training tasks besides the masked token prediction task. The pretrained model is evaluated on four different tasks and outperforms the CodeBERT baselines as well as other pretrained models. Further analysis confirmed the benefits from the additional tasks and data flow input.

abstractText: Pre-trained models for programming language have achieved dramatic empirical improvements on a variety of code-related tasks such as code search, code completion, code summarization, etc. However, existing pre-trained models regard a code snippet as a sequence of tokens, while ignoring the inherent structure of code, which provides crucial code semantics and would enhance the code understanding process. We present GraphCodeBERT, a pre-trained model for programming language that considers the inherent structure of code. Instead of taking syntactic-level structure of code like abstract syntax tree (AST), we use data flow in the pre-training stage, which is a semantic-level structure of code that encodes the relation of “wherethe-value-comes-from” between variables. Such a semantic-level structure is less complex and does not bring an unnecessarily deep hierarchy of AST, the property of which makes the model more efficient. We develop GraphCodeBERT based on Transformer. In addition to using the task of masked language modeling, we introduce two structure-aware pre-training tasks. One is to predict code structure edges, and the other is to align representations between source code and code structure. We implement the model in an efficient way with a graph-guided masked attention function to incorporate the code structure. We evaluate our model on four tasks, including code search, clone detection, code translation, and code refinement. Results show that code structure and newly introduced pre-training tasks can improve GraphCodeBERT and achieves state-of-the-art performance on the four downstream tasks. We further show that the model prefers structure-level attentions over token-level attentions in the task of code search.1

authors:
Miltiadis Allamanis
Marc Brockschmidt
Mahmoud Khademi

title: Learning to represent programs with graphs

venue: In International Conference on Learning Representations,

authors:
Uri Alon
Shaked Brody
Omer Levy
Eran Yahav

title: code2seq: Generating sequences from structured representations of code

venue: arXiv preprint arXiv:1808.01400,

authors:
Uri Alon
Roy Sadaka
Omer Levy
Eran Yahav

title: Structural language models of code

venue: arXiv, pp

authors:
Marc Brockschmidt
Miltiadis Allamanis
Alexander L Gaunt
Oleksandr Polozov

title: Generative code modeling with graphs

venue: arXiv preprint arXiv:1805.08490,

authors:
Luca Buratti
Saurabh Pujar
Mihaela Bornea
Scott McCarley
Yunhui Zheng
Gaetano Rossiello
Alessandro Morari
Jim Laredo
Veronika Thost
Yufan Zhuang

title: Exploring software naturalness throughneural language models

authors:
Xinyun Chen
Chang Liu
Dawn Song

title: Tree-to-tree neural networks for program translation

venue: In Advances in neural information processing systems,

authors:
Mayur Datar
Nicole Immorlica
Piotr Indyk
Vahab S Mirrokni

title: Locality-sensitive hashing scheme based on p-stable distributions

venue: In Proceedings of the twentieth annual symposium on Computational geometry,

authors:
Jacob Devlin
Ming-Wei Chang
Kenton Lee
Kristina Toutanova. Bert

title: Pre-training of deep bidirectional transformers for language understanding

venue: arXiv preprint arXiv:1810.04805,

authors:
Zhangyin Feng
Daya Guo
Duyu Tang
Nan Duan
Xiaocheng Feng
Ming Gong
Linjun Shou
Bing Qin
Ting Liu
Daxin Jiang

title: Codebert: A pre-trained model for programming and natural languages

venue: arXiv preprint arXiv:2002.08155,

authors:
Daya Guo
Duyu Tang
Nan Duan
M. Zhou
Jian Yin

title: Dialog-to-action: Conversational question answering over a large-scale knowledge base

venue: NeurIPS,

title: Coupling retrieval and meta-learning for context-dependent semantic parsing

authors:
Vincent J Hellendoorn
Charles Sutton
Rishabh Singh
Petros Maniatis
David Bieber

title: Global relational models of source code

authors:
Xing Hu
Ge Li
Xin Xia
David Lo
Zhi Jin

title: Deep code comment generation

venue: In 2018 IEEE/ACM 26th International Conference on Program Comprehension (ICPC),

authors:
Hamel Husain
Ho-Hsiang Wu
Tiferet Gazit
Miltiadis Allamanis
Marc Brockschmidt

title: Codesearchnet challenge: Evaluating the state of semantic code search

authors:
Lingxiao Jiang
Ghassan Misherghi
Zhendong Su
Stephane Glondu

title: Deckard: Scalable and accurate tree-based detection of code clones

venue: In 29th International Conference on Software Engineering

authors:
Aditya Kanade
Petros Maniatis
Gogul Balakrishnan
Kensen Shi

title: Pre-trained contextual embedding of source code

venue: arXiv preprint arXiv:2001.00059,

authors:
Svetoslav Karaivanov
Veselin Raychev
Martin Vechev

title: Phrase-based statistical translation of programming languages

venue: In Proceedings of the 2014 ACM International Symposium on New Ideas, New Paradigms, and Reflections on Programming & Software,

authors:
Rafael-Michael Karampatsis
Charles Sutton

title: Scelmo: Source code embeddings from language models

venue: arXiv preprint arXiv:2004.13214,

authors:
Seohyun Kim
Jinman Zhao
Yuchi Tian
Satish Chandra

title: Code prediction by feeding trees to transformers

venue: arXiv preprint arXiv:2003.13848,

authors:
Philipp Koehn
Franz J Och
Daniel Marcu

title: Statistical phrase-based translation

venue: Technical report, UNIVERSITY OF SOUTHERN CALIFORNIA MARINA DEL REY INFORMATION SCIENCES INST,

authors:
Guillaume Lample
Alexis Conneau

title: Cross-lingual language model pretraining

venue: arXiv preprint arXiv:1901.07291,

authors:
Jian Li
Yue Wang
Michael R Lyu
Irwin King

title: Code completion with neural attention and pointer networks

venue: arXiv preprint arXiv:1711.09573,

authors:
Yinhan Liu
Myle Ott
Naman Goyal
Jingfei Du
Mandar Joshi
Danqi Chen
Omer Levy
Mike Lewis
Luke Zettlemoyer
Veselin Stoyanov

title: Roberta: A robustly optimized bert pretraining approach

authors:
Anh Tuan Nguyen
Tien N Nguyen

title: Graph-based statistical language model for code

venue: In 2015 IEEE/ACM 37th IEEE International Conference on Software Engineering,

authors:
Anh Tuan Nguyen
Tung Thanh Nguyen
Tien N Nguyen

title: Lexical statistical machine translation for language migration

venue: In Proceedings of the 2013 9th Joint Meeting on Foundations of Software Engineering,

title: Divide-and-conquer approach for multi-phase statistical migration for source code (t)

venue: In 2015 30th IEEE/ACM International Conference on Automated Software Engineering (ASE),

authors:
Xuan-Phi Nguyen
Shafiq Joty
Steven Hoi
Richard Socher

title: Tree-structured attention with hierarchical accumulation

authors:
Matthew E Peters
Mark Neumann
Mohit Iyyer
Matt Gardner
Christopher Clark
Kenton Lee
Luke Zettlemoyer

title: Deep contextualized word representations

venue: arXiv preprint arXiv:1802.05365,

authors:
Maxim Rabinovich
Mitchell Stern
Dan Klein

title: Abstract syntax networks for code generation and semantic parsing

venue: arXiv preprint arXiv:1704.07535,

authors:
Alec Radford
Karthik Narasimhan
Tim Salimans
Ilya Sutskever

title: Improving language understanding by generative pre-training

venue: URL https://s3-us-west-2. amazonaws. com/openaiassets/researchcovers/languageunsupervised/language understanding paper

authors:
Colin Raffel
Noam Shazeer
Adam Roberts
Katherine Lee
Sharan Narang
Michael Matena
Yanqi Zhou
Wei Li
Peter J Liu

title: Exploring the limits of transfer learning with a unified text-to-text transformer

venue: arXiv preprint arXiv:1910.10683,

authors:
Jeffrey Svajlenko
Judith F Islam
Iman Keivanloo
Chanchal K Roy
Mohammad Mamun Mia

title: Towards a big data curated benchmark of inter-project code clones

venue: IEEE International Conference on Software Maintenance and Evolution,

authors:
Alexey Svyatkovskiy
Shao Kun Deng
Shengyu Fu
Neel Sundaresan

title: Intellicode compose: Code generation using transformer

venue: arXiv preprint arXiv:2005.08025,

authors:
Michele Tufano
Cody Watson
Gabriele Bavota
Massimiliano Di Penta
Martin White
Denys Poshyvanyk

title: An empirical study on learning bug-fixing patches in the wild via neural machine translation

venue: ACM Transactions on Software Engineering and Methodology (TOSEM),

authors:
Ashish Vaswani
Noam Shazeer
Niki Parmar
Jakob Uszkoreit
Llion Jones
Aidan N Gomez
Łukasz Kaiser
Illia Polosukhin

title: Attention is all you need

authors:
Wenhan Wang
Ge Li
Bo Ma
Xin Xia
Zhi Jin

title: Detecting code clones with graph neural networkand flow-augmented abstract syntax tree

venue: arXiv preprint arXiv:2002.08653,

authors:
Huihui Wei
Ming Li

title: Supervised deep features for software functional clone detection by exploiting lexical and syntactical information in source code

venue: In IJCAI,

authors:
Martin White
Michele Tufano
Christopher Vendome
Denys Poshyvanyk

title: Deep learning code fragments for code clone detection

venue: In 2016 31st IEEE/ACM International Conference on Automated Software Engineering (ASE),

authors:
Zhilin Yang
Zihang Dai
Yiming Yang
Jaime Carbonell
Ruslan Salakhutdinov
Quoc V Le

title: Xlnet: Generalized autoregressive pretraining for language understanding

authors:
Pengcheng Yin
Graham Neubig

title: A syntactic neural model for general-purpose code generation

venue: In The 55th Annual Meeting of the Association for Computational Linguistics (ACL),

authors:
Jian Zhang
Xu Wang
Hongyu Zhang
Hailong Sun
Kaixuan Wang
Xudong Liu

title: A novel neural source code representation based on abstract syntax tree

venue: IEEE/ACM 41st International Conference on Software Engineering (ICSE),

heading: 1 INTRODUCTION

text:
Pre-trained models such as ELMo (Peters et al., 2018), GPT (Radford et al., 2018) and BERT (Devlin et al., 2018) have led to strong improvement on numerous natural language processing (NLP) tasks. These pre-trained models are first pre-trained on a large unsupervised text corpus, and then fine-tuned on downstream tasks. The success of pre-trained models in NLP also promotes the development of pre-trained models for programming language. Existing works (Kanade et al., 2019; Karampatsis & Sutton, 2020; Feng et al., 2020; Svyatkovskiy et al., 2020; Buratti et al., 2020) regard a source code as a sequence of tokens and pre-train models on source code to support code-related tasks such as code search, code completion, code summarization, etc. However, previous works only utilize source code for pre-training, while ignoring the inherent structure of code. Such code structure provides useful semantic information of code, which would benefit the code understanding process. Taking the expression v = max value−min value as an example, v is computed from max value and min value. Programmers do not always follow the naming conventions so that it’s hard to understand the semantic of the variable v only from its name. The semantic structure of code provides a way to understand the semantic of the variable v by leveraging dependency relation between variables.
∗Work done while this author was an intern at Microsoft Research Asia. Contact: Daya Guo (guody5@mail2.sysu.edu.cn)
1All the codes and data are available at https://github.com/microsoft/CodeBERT.
In this work, we present GraphCodeBERT, a pre-trained model for programming language that considers the inherent structure of code. Instead of taking syntactic-level structure of code like abstract syntax tree (AST), we leverage semantic-level information of code, i.e. data flow, for pretraining. Data flow is a graph, in which nodes represent variables and edges represent the relation of “where-the-value-comes-from” between variables. Compared with AST, data flow is less complex and does not bring an unnecessarily deep hierarchy, the property of which makes the model more efficient. In order to learn code representation from source code and code structure, we introduce two new structure-aware pre-training tasks. One is data flow edges prediction for learning representation from code structure, and the other is variable-alignment across source code and data flow for aligning representation between source code and code structure. GraphCodeBERT is based on Transformer neural architecture (Vaswani et al., 2017) and we extend it by introducing a graph-guided masked attention function to incorporate the code structure.
We pre-train GraphCodeBERT on the CodeSearchNet dataset (Husain et al., 2019), which includes 2.3M functions of six programming languages paired with natural language documents. We evaluate the model on four downstream tasks: natural language code search, clone detection, code translation, and code refinement. Experiments show that our model achieves state-of-the-art performance on the four tasks. Further analysis shows that code structure and newly introduced pre-training tasks can improve GraphCodeBERT and the model has consistent preference for attending data flow.
In summary, the contributions of this paper are: (1) GraphCodeBERT is the first pre-trained model that leverages semantic structure of code to learn code representation. (2) We introduce two new structure-aware pre-training tasks for learning representation from source code and data flow. (3) GraphCodeBERT provides significant improvement on four downstream tasks, i.e. code search, clone detection, code translation, and code refinement.

heading: 2 RELATED WORKS

text:
Pre-Trained Models for Programming Languages Inspired by the big success of pre-training in NLP (Devlin et al., 2018; Yang et al., 2019; Liu et al., 2019; Raffel et al., 2019), pre-trained models for programming languages also promotes the development of code intelligence (Kanade et al., 2019; Feng et al., 2020; Karampatsis & Sutton, 2020; Svyatkovskiy et al., 2020; Buratti et al., 2020). Kanade et al. (2019) pre-train a BERT model on a massive corpus of Python source codes by masked language modeling and next sentence prediction objectives. Feng et al. (2020) propose CodeBERT, a bimodal pre-trained model for programming and natural languages by masked language modeling and replaced token detection to support text-code tasks such as code search. Karampatsis & Sutton (2020) pre-train contextual embeddings on a JavaScript corpus using the ELMo framework for program repair task. Svyatkovskiy et al. (2020) propose GPT-C, which is a variant of the GPT-2 trained from scratch on source code data to support generative tasks like code completion. Buratti et al. (2020) present C-BERT, a transformer-based language model pre-trained on a collection of repositories written in C language, and achieve high accuracy in the abstract syntax tree (AST) tagging task.
Different with previous works, GraphCodeBERT is the first pre-trained model that leverages code structure to learn code representation to improve code understanding. We further introduce a graphguided masked attention function to incorporate the code structure into Transformer and two new structure-aware pre-training tasks to learn representation from source code and code structure.
Neural Networks with Code Structure In recent years, some neural networks leveraging code structure such as AST have been proposed and achieved strong performance in code-related tasks like code completion (Li et al., 2017; Alon et al., 2019; Kim et al., 2020), code generation (Rabinovich et al., 2017; Yin & Neubig, 2017; Brockschmidt et al., 2018), code clone detection (Wei & Li, 2017; Zhang et al., 2019; Wang et al., 2020), code summarization (Alon et al., 2018; Hu et al., 2018) and so on (Nguyen & Nguyen, 2015; Allamanis et al., 2018; Hellendoorn et al., 2019). Nguyen & Nguyen (2015) propose an AST-based language model to support the detection and suggestion of a syntactic template at the current editing location. Allamanis et al. (2018) use graphs to represent programs and graph neural network to reason over program structures. Hellendoorn et al. (2019) propose two different architectures using a gated graph neural network and Transformers for combining local and global information to leverage richly structured representations of source code. However, these
works leverage code structure to learn models on specific tasks from scratch without using pre-trained models. In this work, we study how to leverage code structure for pre-training code representation.

heading: 3 DATA FLOW

text:
In this section, we describe the basic concept and extraction of data flow. In next section, we will describe how to use data flow for pre-training.
Data flow is a graph that represents dependency relation between variables, in which nodes represent variables and edges represent where the value of each variable comes from. Unlike AST, data flow is same under different abstract grammars for the same source code. Such code structure provides crucial code semantic information for code understanding. Taking v = max value−min value as an example, programmers do not always follow the naming conventions so that it is hard to understand the semantic of the variable. Data flow provides a way to understand the semantic of the variable v to some extent, i.e. the value of v comes from max value and min value in data flow. Besides, data flow supports the model to consider long-range dependencies induced by using the same variable or function in distant locations. Taking Figure 1 as an example, there are four variables with same name (i.e. x3, x7, x9 and x11) but with different semantic. The graph in the figure shows dependency relation between these variables and supports x11 to pay more attention to x7 and x9 instead of x3. Next, we describe how to extract data flow from a source code.
Figure 1 shows the extraction of data flow through a source code. Given a source code C = {c1, c2, ..., cn}, we first parse the code into an abstract syntax tree (AST) by a standard compiler tool2. The AST includes syntax information of the code and terminals (leaves) are used to identify the variable sequence, denoted as V = {v1, v2, ..., vk}. We take each variable as a node of the graph and an direct edge ε = 〈vi, vj〉 from vi to vj refers that the value of j-th variable comes from i-th variable. Taking x = expr as an example, edges from all variables in expr to x are added into the graph. We denote the set of directed edges as E = {ε1, ε2, ..., εl} and the graph G(C) = (V,E) is data flow used to represent dependency relation between variables of the source code C.

heading: 4 GRAPHCODEBERT

text:
In this section, we describe GraphCodeBERT, a graph-based pre-trained model based on Transformer for programming language. We introduce model architecture, graph-guided masked attention and pre-training tasks including standard masked language model and newly introduced ones. More details about model pre-training setting are provided in the Appendix A.
2https://github.com/tree-sitter/tree-sitter

heading: 4.1 MODEL ARCHITECTURE

text:
Figure 2 shows the model architecture of GraphCodeBERT. We follow BERT (Devlin et al., 2018) and use the multi-layer bidirectional Transformer (Vaswani et al., 2017) as the model backbone. Instead of only using source code, we also utilize paired comments to pre-train the model to support more code-related tasks involving natural language such as natural language code search (Feng et al., 2020). We further take data flow, which is a graph, as a part of the input to the model.
Given a source code C = {c1, c2, ..., cn} with its comment W = {w1, w2, ..., wm}, we can obtain the corresponding data flow G(C) = (V,E) as discussed in the Section 3, where V = {v1, v2, ..., vk} is a set of variables and E = {ε1, ε2, ..., εl} is a set of direct edges that represent where the value of each variable comes from. We concatenate the comment, source code and the set of variables as the sequence input X = {[CLS],W, [SEP ], C, [SEP ], V }, where [CLS] is a special token in front of three segments and [SEP ] is a special symbol to split two kinds of data types.
GraphCodeBERT takes the sequence X as the input and then converts the sequence into input vectors H0. For each token, its input vector is constructed by summing the corresponding token and position embeddings. We use a special position embedding for all variables to indicate that they are nodes of data flow. The model applies N transformer layers over the input vectors to produce contextual representations Hn = transformern(Hn−1), n ∈ [1, N ]. Each transformer layer contains an architecturally identical transformer that applies a multi-headed self-attention operation (Vaswani et al., 2017) followed by a feed forward layer over the input Hn−1 in the n-th layer.
Gn = LN(MultiAttn(Hn−1) +Hn−1) (1) Hn = LN(FFN(Gn) +Gn) (2)
where MultiAttn is a multi-headed self-attention mechanism, FFN is a two layers feed forward network, and LN represents a layer normalization operation. For the n-th transformer layer, the output Ĝn of a multi-headed self-attention is computed via:
Qi = H n−1WQi , Ki = H n−1WKi , Vi = H n−1WVi (3)
headi = softmax( QiK T i√
dk +M)Vi (4)
Ĝn = [head1; ...;headu]W O n (5)
where the previous layer’s output Hn−1 ∈ R|X|×dh is linearly projected to a triplet of queries, keys and values using model parameters WQi ,W K i ,W V i ∈ Rdh×dk , respectively. u is the number of heads, dk is the dimension of a head, and WOn ∈ Rdh×dh is the model parameters. M ∈ R|X|×|X| is a mask matrix, where Mij is 0 if i-th token is allowed to attend j-th token otherwise −∞.

heading: 4.2 GRAPH-GUIDED MASKED ATTENTION

text:
To incorporate the graph structure into Transformer, we define a graph-guided masked attention function to filter out irrelevant signals. The attention masking function could avoid the key ki attended by the query qj by adding the attention score qTj ki an infinitely negative value so that the attention weight becomes zero after using a softmax function. To represent dependency relation between variables, a node-query qvi is allowed to attend to a node-key kvj if there is a direct edge from the node vj to the node vi (i.e. 〈vj , vi〉 ∈ E) or they are the same node (i.e. i = j). Otherwise, the attention is masked by adding an infinitely negative value into the attention score. To represent the relation between source code tokens and nodes of the data flow, we first define a set E ′ , where 〈vi, cj〉/〈cj , vi〉 ∈ E ′
if the variable vi is identified from the source code token cj . We then allow the node qvi and code kcj attend each other if and only if 〈vi, cj〉/〈cj , vi〉 ∈ E ′ . More formally, we use the following graph-guided masked attention matrix as the mask matrix M in the equation 4:
Mij =
{ 0 if qi ∈ {[CLS], [SEP ]} or qi, kj ∈W ∪ C or 〈qi, kj〉 ∈ E ∪ E ′
−∞ otherwise (6)

heading: 4.3 PRE-TRAINING TASKS

text:
We describe three pre-training tasks used for pre-training GraphCodeBERT in this section. The first task is masked language modeling (Devlin et al., 2018) for learning representation from the source code. The second task is data flow edge prediction for learning representation from data flow, where we first mask some variables’ data flow edges and then let GraphCodeBERT predict those edges. The last task is variable-alignment across source code and data flow for aligning representation between source code and data flow, which predicts where a variable is identified from.
Masked Language Modeling We follow Devlin et al. (2018) to apply masked language modeling (MLM) pre-training task. Specially, we sample randomly 15% of the tokens from the source code and paired comment. We replace them with a [MASK] token 80% of the time, with a random token 10% of the time, and leave them unchanged 10% of the time. The MLM objective is to predict original tokens of these sampled tokens, which has proven effective in previous works (Devlin et al., 2018; Liu et al., 2019; Feng et al., 2020). In particular, the model can leverage the comment context if the source code context is not sufficient to infer the masked code token, encouraging the model to align the natural language and programming language representations.
Edge Prediction To learn representation from data flow, we introduce a pre-training task of data flow edges prediction. The motivation is to encourage the model to learn structure-aware representation that encodes the relation of “where-the-value-comes-from” for better code understanding. Specially, we randomly sample 20% of nodes Vs in data flow, mask direct edges connecting these sampled nodes by add an infinitely negative value in the mask matrix, and then predict these masked edges Emask. Taking the variable x11 in Figure 2 for an example, we first mask edges 〈x7, x11〉 and 〈x9, x11〉 in the graph and then let the model to predict these edges. Formally, the pre-training objective of the task is calculated as Equation 7, where Ec = Vs × V ∪ V × Vs is a set of candidates for edge prediction, δ(eij ∈ E) is 1 if 〈vi, vj〉 ∈ E otherwise 0, and the probability peij of existing an edge from i-th to j-th node is calculated by dot product following a sigmoid function using representations of two nodes from GraphCodeBERT. To balance positive-negative ratio of examples, we sample negative and positive samples with the same number for Ec.
lossEdgePred = − ∑
eij∈Ec
[δ(eij ∈ Emask)logpeij + (1− δ(eij ∈ Emask))log(1− peij )] (7)
Node Alignment To align representation between source code and data flow, we introduce a pretraining task of node alignment across source code and data flow, which is similar to data flow edge prediction. Instead of predicting edges between nodes, we predict edges between code tokens and nodes. The motivation is to encourage the model to align variables and source code according to data flow. Taking Figure 3 for an example, we first mask edges between the variable x11 in data flow and code tokens, and then predict which code token the variable x11 in data flow is identified from. As we can see, the model could predict that the variable x11 is identified form the variable x in the expression “return x” according to data flow information (i.e. the value of x11 comes from x7 or x9).
Specially, we randomly sample 20% nodes V ′
s in the graph, mask edges between code tokens and sampled nodes, and then predict masked edges E ′
mask. The pre-training objective of this task is similar to Equation 7, where E ′ c = V ′
s × C is a set of candidates for node alignment. Similarly, we also sample negative and positive samples with the same number for E ′
c. lossNodeAlign = − ∑
eij∈E′c
[δ(eij ∈ E ′ mask)logpeij + (1− δ(eij ∈ E ′ mask))log(1− peij )] (8)

heading: 5 EXPERIMENTS

text: We evaluate our model on four downstream tasks, including code search, clone detection, code translation and code refinement. Detailed experimental settings can be found in the Appendix.

heading: 5.1 NATURAL LANGUAGE CODE SEARCH

text:
Given a natural language as the input, the task aims to find the most semantically related code from a collection of candidate codes. We conduct experiments on the CodeSearchNet code corpus (Husain et al., 2019), which includes six programming languages. Different from the dataset and the setting used in the Husain et al. (2019), we filter low-quality queries by handcrafted rules and expand 1000 candidates to the whole code corpus, which is closer to the real-life scenario. We use Mean Reciprocal Rank (MRR) as our evaluation metric and report results of existing methods in the Table 1. We provide more details about the filtered dataset and also give results using the same setting of Husain et al. (2019) in the Appendix B.
All models calculate inner product of code and query encodings as relevance scores to rank candidate codes. We follow Husain et al. (2019) to implement four methods as baselines in the first group to obtain the encodings, including bag-of-words, convolutional neural network, bidirectional recurrent neural network, and multi-head attention. The second group is the results of pre-trained models. Roberta (Liu et al., 2019) is a pre-trained model on text corpus with MLM learning objective, while RoBERTa (code) is pre-trained only on code. CodeBERT (Feng et al., 2020) is pre-trained
on code-text pairs with MLM and replaced token detection learning objectives. As we can see, GraphCodeBERT that leverages code structure for pre-training brings a 2% gain of MRR, achieving the state-of-art performance. We also conducted t-test between our GraphCodeBERT and other baselines, and the results show the improvements are significant with p < 0.01.

heading: 5.2 CODE CLONE DETECTION

text:
Code clones are multiple code fragments that output similar results when given the same input. The task aims to measure the similarity between two code fragments, which can help reduce the cost of software maintenance and prevent bugs. We conduct experiments on the BigCloneBench dataset (Svajlenko et al., 2014) and report results in the Table 2.
Deckard (Jiang et al., 2007) is to compute vectors for structural information within ASTs and then a Locality Sensitive Hashing (LSH) (Datar et al., 2004) is used to cluster similar vectors for detection. RtvNN (White et al., 2016) trains a recursive autoencoder to learn representations for AST. CDLH (Wei & Li, 2017) learn representations of code fragments via AST-based LSTM and hamming distance is used to optimize the distance between the vector representation of AST pairs.
ASTNN Zhang et al. (2019) uses RNNs to encode AST subtrees for statements, then feed the encodings of all statement trees into an RNN to learn representation for a program. FA-AST-GMN (Wang et al., 2020) uses GNNs over a flow-augmented AST to leverages explicit control and data flow information for code clone detection. Results show that our GraphCodeBERT that leverages code structure information significantly outperforms other methods with p < 0.01, which demonstrates the effectiveness of our pre-trained model for the task of code clone detection.

heading: 5.3 CODE TRANSLATION

text:
Code translation aims to migrate legacy software from one programming language in a platform to another. Following Nguyen et al. (2015) and Chen et al. (2018), we conduct experiments on a dataset crawled from the same several open-source projects as them and report results in the Table 3.
The Naive method is directly copying the source code as the translation result. PBSMT is short for phrase-based statistical machine translation (Koehn et al., 2003), and has been exploited in previous works (Nguyen et al., 2013; Karaivanov et al., 2014). As for the Transformer, we use the
same number of layers and hidden size as pre-trained models. To leverage the pretrained models for translation, we initialize the encoder with pre-trained models and randomly initialize parameters of the decoder and the source-to-target attention. Results show that the models initialized with pretrained models (i.e the second group) significantly outperform PBSMT and Transformer models. Among them, GraphCodeBERT achieves state-of-art performance, which demonstrates the effectiveness of our model for code translation.

heading: 5.4 CODE REFINEMENT

text:
Code refinement aims to automatically fix bugs in the code, which can contribute to reducing the cost of bug-fixes. We use the dataset released by Tufano et al. (2019) and report results in the Table 4.
The Naive method directly copies the buggy code as the refinement result. For the Transformer, we use the same number of layers and hidden size as the pre-trained models. Same as the Section 5.3, we initialize the encoder with pre-trained models and randomly initialize parameters of the decoder
and the source-to-target attention. Then we use the training data to fine-tune the whole model. In the table, we see that the Transformer significantly outperforms LSTM. Results in the second group shows that pre-trained models outperform Transformer models further, and GraphCodeBERT achieves better performance than other pre-trained models on both datasets, which shows leveraging code structure information are helpful to the task of code refinement.

heading: 5.5 MODEL ANALYSIS

text:
Ablation Study We conduct ablation study on the task of natural language code search to understand various components in our approach impact overall performance. We remove two pre-training tasks and data flow, respectively, to analyze their contribution. Table 5 shows that the overall performance drops from 71.3% to 70.3%∼70.7% when removing Node Alignment and Edge Prediction pre-training tasks, respectively, which reveals the importance of two structure-aware pre-training tasks. After ablating the data flow totally, we can see that the performance drops from 71.3% to 69.3%, which means leveraging data flow to learn code representation could improve GraphCodeBERT.
Node-vs. Token-level Attention Table 6 shows how frequently a special token [CLS] that is used to calculate probability of correct candidate attends to code tokens (Codes) and variables (Nodes). We see that although the number of nodes account for 5%∼20%, attentions over nodes overwhelm node/code ratio (around 10% to 32%) across all programming languages. The results indicate that data flow plays an important role in code understanding process and the model pays more attention to nodes in data flow than code tokens.
Comparison between AST and Data Flow Figure 4 shows MRR score with respect to input sequence length on the validation dataset of Ruby programming language for the task of code search. AST Pre-order Traversal regards AST as a sequence by linearizing all AST nodes using pre-order traversal algorithm. AST Subtree Masking regards AST as a tree and introduce subtree masking (Nguyen et al., 2019) for self-attention of the Transformer. In subtree masking, each node-query in AST attends only to its own subtree descendants, and each leaf-query only attends to leaves of AST. Transformer has a self-attention component with O(n2) time and memory complexity where n is the input sequence length, and thus is not efficient to scale to long inputs.
We observe that injecting AST even hurts the performance when the sequence length is short (e.g. shorter than 128), while GraphCodeBERT consistently brings performance boost on varying sequence length and obtains better MRR score than AST-based methods. The main reason is that data flow is less complex and the number of nodes account for 5% ∼ 20% (see Table 6), which does not bring an unnecessarily deep hierarchy of AST and makes the model more accurate and efficient.
Case Study We also give a case study to demonstrate that data flow would enhance the code understanding process. Given a source code and a comment, we use GraphCodeBERT with and without data flow to predict whether the comment correctly describes the source code. Results are given in Figure 5. We can see that both models make correct prediction in the original example, where the threshold is 0.5 (left panel). To study the code understanding ability of models, we change the source code (center panel) and the comment (right panel), respectively. Although we make a small change on the source code (return a→ return b) and the comment (sum value→ mean value), the semantic of the source code and the comment are completely different and corresponding gold labels change from 1 to 0. As we can see in the figure, GraphCodeBERT without using data flow fails these tests and still outputs high probability for negative examples. After leveraging data flow, GraphCodeBERT better understands the semantic of source code and makes correct predictions on all tests, which demonstrates that data flow could improve the code understanding ability of the model.

heading: 6 CONCLUSION

text: In this paper, we present GraphCodeBERT that leverages data flow to learn code representation. To the best of our knowledge, this is the first pre-trained model that considers code structure for pre-training code representations. We introduce two structure-aware pre-training tasks and show that GraphCodeBERT achieves state-of-the-art performance on four code-related downstream tasks, including code search, clone detection, code translation and code refinement. Further analysis shows that code structure and newly introduced pre-training tasks boost the performance. Additionally, case study in the task of code search shows that applying data flow in the pre-trained model improves code understanding.

heading: ACKNOWLEDGMENTS

text: Daya Guo and Jian Yin are supported by the Research Foundation of Science and Technology Plan Project in Guangdong Province (2017B030308007).

heading: A PRE-TRAINING DETAILS

text:
GraphCodeBERT includes 12 layers Transformer with 768 dimensional hidden states and 12 attention heads. For fair comparison, we use the same dataset as CodeBERT (Feng et al., 2020) to pretrain our model. The dataset is the CodeSearchNet dataset3 (Husain et al., 2019), which includes 2.3M functions with document pairs for six programming languages. We train the model on two DGX-2 machines, each having 16 NVIDIA Tesla V100 with 32GB memory. We set the max length of sequences and nodes as 512 and 128, respectively. We use the Adam optimizer to update model parameters with 1,024 batch size and 2e-4 learning rate. To accelerate the training process, we adopt the parameters of CodeBERT released by Feng et al. (2020) to initialize the model. The model is trained with 200K batches and costs about 83 hours.
At each iteration, we alternate EdgePred and NodeAlign objectives in combination with MLM to pre-train the model. And we follow Lample & Conneau (2019) to sample each batch from the same programming language according to a multinomial distribution with probabilities {qi}i=1...N , where ni is number of examples for i-th programming language and α=0.7. Sampling with this distribution could alleviates the bias towards high-resource languages.
qi = pαi∑j=1 N p α j with pi = ni∑k=1 N nk
(9)

heading: B NATURAL LANGUAGE CODE SEARCH

text:
Given a natural language as the input, code search aims to find the most semantically related code from a collection of candidate codes. We conduct experiments on the CodeSearchNet code corpus (Husain et al., 2019) and follow Husain et al. (2019) to take the first paragraph of the documentation as the query for the corresponding function. However, we observe that some queries contain content unrelated to the code, such as a link “http://...” that refers to external resources. Therefore, we filter following examples to improve the quality of the dataset.
(1) Examples whose code could not be parsed into abstract syntax tree.
(2) Examples whose query tokens number is shorter than 3 or larger than 256.
(3) Examples whose query contains special tokens such as “http://”.
(4) Examples whose query is empty or not written in English.
3https://github.com/github/CodeSearchNet
Different from the setting of Husain et al. (2019), the answer of each query is retrieved from the whole development and testing code corpus instead of 1,000 candidate codes. We list data statistics about the filtered dataset in Table 7.
We use GraphCodeBERT to separately encode query and source code with data flow, and calculate inner product of their representations of the special token [CLS] as relevance scores to rank candidate codes. In the fine-turning step, we set the learning rate as 2e-5, the batch size as 32, the max sequence length of queries and codes as 128 and 256, and the max number of nodes as 64. We use the Adam optimizer to update model parameters and perform early stopping on the development set.
We also report the results using the same setting of Husain et al. (2019) in Table 8. In this setting, models are required to retrieve an answer for a query from 1000 candidates. The results show that GraphCodeBERT also achieves the state-of-the-art performance.

heading: C CODE CLONE DETECTION

text:
Code clone detection aims to measure the similarity between two code fragments. We use BigCloneBench dataset (Svajlenko et al., 2014), which contains over 6,000,000 true clone pairs and 260,000 false clone pairs from 10 different functionalities. We follow the settings in Wei & Li (2017), discarding code fragments without any tagged true and false clone pairs and using 9,134 remaining code fragments. Finally, the dataset provided by Wang et al. (2020) includes 901,724/416,328/416,328 examples for training/validation/testing. We treat the task as a binary classification to fine-tune GraphCodeBERT, where we use source code and data flow as the input. The probability of true clone is calculated by dot product from the representation of [CLS]. In the fine-turning step, we set the learning rate as 2e-5, the batch size as 16, the max sequence length as 512 the max number of nodes as 128. We use the Adam optimizer to update model parameters and tune hyper-parameters and perform early stopping on the development set.
We give a case of the GraphCodeBERT output for this task in Figure 6. In this example, two Java source codes both download content from a given URL and convert the type of the content into string type. Therefore, two codes are semantically similar since they output similar results when given the same input. As we can see, our model gives a high score for this case and the pair is classified as true clone pair.
Input: Two source codes Output: Semantically similar (score: 0.983)

heading: D CODE TRANSLATION

text:
Code translation aims to migrate legacy software from one programming language in a platform to another. We conduct experiments on a dataset crawled from the same several open-source projects as Nguyen et al. (2015) and Chen et al. (2018), i.e. Lucene4, POI5, JGit6 and Antlr7. We do not use Itext8 and JTS9 as they do because of the license problem. Those projects have both Java and C# implementation. We pair the methods in the two languages based on their file names and method names. After removing duplication and methods with null function body, the total number of method pairs is 11,800, and we split 500 pairs from them as the development set and another 1,000 pairs for test. To demonstrate the effectiveness of GraphCodeBERT on the task of code translation, we adopt various pre-trained models as encoders and stay hyperparameters consistent. We set the learning rate as 1e-4, the batch size as 32, the max sequence length as 256 and the max number of nodes as 64. We use the Adam optimizer to update model parameters and tune hyper-parameters and perform early stopping on the development set.
We give a case of the GraphCodeBERT output for this task in Figure 7. In this example, the model successfully translates a piece of Java code into its C# version. The differences include the type name (from “boolean” to “bool”) and the usage of getting a string value of a bool variable (from “String.valueOf(b)” to “b.ToString()”).
4http://lucene.apache.org/ 5http://poi.apache.org/ 6https://github.com/eclipse/jgit/ 7https://github.com/antlr/ 8http://sourceforge.net/projects/itext/ 9http://sourceforge.net/projects/jts-topo-suite/

heading: E CODE REFINEMENT

text:
Code refinement aims to automatically fix bugs in the code. We use the dataset released by Tufano et al. (2019). The source is buggy Java functions while the target is the according fixed ones. Almost all the names of variables and custom methods are normalized. The dataset contains two subsets based on the code length. For the small dataset, the numbers of training, development and test samples are 46,680, 5,835 and 5,835. For the medium dataset, the numbers are 52,364, 6,545 and 6,545. We also use the sequence-to-sequence Transformer model to conduct the experiments. In the fine-tuning step, we adopt various pre-trained models as encoders. We set the learning rate as 1e-4, the batch size as 32, the max sequence length as 256 and the max number of nodes as 64. We use the Adam optimizer to update model parameters and perform early stopping on the development set.
We give two cases of the GraphCodeBERT output for this task in Figure 8. In the first example, the model successfully fixes the operation bug (from “*” to “+”) to match the function name “add”. In the second case, the source function and type names are normalized. The return type of this function is “void” but the buggy code gives a return value. Our model successfully removes the “return” word so that the return type of the function matches its declaration.

heading: F CASE STUDY

text:
F.1 NATURAL LANGUAGE CODE SEARCH
We give a case study to illustrate retrieved results by GraphCodeBERT on the natural language code search task, with a comparison to CodeBERT and RoBERTa (code) models. Two examples are given in Figure 9 and we can see that GraphCodeBERT successfully retrieves correct source codes for given queries on both examples. As we can see in the first case, incorporating data flow will help Graph-CodeBERT better understand the complicated expression “[(k, v) for k, v in self.items() if v is not self.EMPTY]” by leveraging dependency relation among variables in data flow graph. In the second case, the terminology “%Y-%m-%d” in Python program language is a format of date time. GraphCodeBERT and CodeBERT both successfully search the correct function. Compared with RoBERTa (code), the second case shows that utilizing natural language descriptions for pre-training helps models do better semantic matching between source codes and queries on the code search task.
F.2 CODE CLONE DETECTION
We give a case study to compare GraphCodeBERT with CodeBERT and RoBERTa (code) models on code clone detection task. An example is shown in Figure 10. The first source code is to return the HTML content from a given URL, while the second source code is to return the last line from a fixed URL “http://kmttg.googlecode.com/svn/trunk/version”. Their semantics are not similar due to their different outputs. Data flow could help GraphCodeBERT better understand that the return value “pageHTML” in first source code comes from “pageHTML.append(line); pageHTML.append(“\r\n”);” instead of “bufferedWriter.write(pageHTML.toString());” and the return value “version” in the second source code comes from “version = inputLine” or “version = null;”. Although two source codes are highly overlapped (marked in yellow), GraphCodeBERT successfully predict the gold label compared with other models without data flow.
F.3 CODE TRANSLATION AND CODE REFINEMENT
We give a case study to compare GraphCodeBERT with Transformer without using data flow on code generation tasks, including code translation and code refinement. We list three cases in Table 9 and Table 10, respectively. [src] represents the source input, [ref] represents the reference, [sys] represents Transformer without data flow and [ours] represents GraphCodeBERT. We can see that the Transformer ([sys]) baseline makes several mistakes, including repeating tokens, logic errors and syntax errors, while GraphCodeBERT ([ours]) as a encoder could improve the generation.

heading: G ERROR ANALYSIS

text:
We also conduct error analysis and summary two main classes of errors for both code understanding and generation tasks.
Figure 11 gives three error cases of GraphCodeBERT on the natural language code search task. We observe that GraphCodeBERR mainly fails to retrieve those source code that involves functions of the library like “tf” (Tensorflow) in the first case and “ GoogleCloudStorageHook” in the second case. It’s difficult for GraphCodeBERR to understand meanings of APIs like “tf.io.read file” and “tf.image.decode image” without relevant information. A potential direction to mitigate the problem is to incorporate definitions of the library. The other major problem is that there are some terminologies like “unistr” in the query (corresponding to “decode(‘utf-8’)” in Python code) in third case. Incorporating more text-code pairs for pre-training might alleviate this problem.
As for the code generation task, Table 11 shows two cases of GraphCodeBERT on the code translation task. We find that the major problems include semantic errors like identifiers from nowhere in the first case and syntax errors like missing a “}” symbol before “return n” in the second case. This problem might be mitigated by incorporating a dedicated decoder that takes into account grammar of programming languages and different generation paradigm like generating a sequence of production rules (Yin & Neubig, 2017; Guo et al., 2018; 2019) in a context-free grammar manner.

title: GRAPHCODEBERT: PRE-TRAINING CODE REPRESEN-