Elamur Research⌕
☰
home / papers / 2017 / Learning to Represent Programs with Graphs

Learning to Represent Programs with Graphs

Paper · 2017 · Miltiadis Allamanis, Marc Brockschmidt and Mahmoud Khademi

Summary

The authors argue that most neural networks for code analysis treat code like ordinary text, either as a sequence of tokens or as a syntax tree. As a result, they miss relationships that the compiler knows for certain, such as where a variable was last written or read. In this paper, a program is converted into a graph. The graph's backbone is the abstract syntax tree (AST). The authors add edges for token order and data flow, as well as links between call arguments and the names of formal parameters. Gated Graph Neural Networks (GGNN) are trained on these graphs, and the authors show how to scale this training to large graphs. The approach was evaluated on two tasks. In VarNaming, the model has to recover a variable's name from how the variable is used. VarMisuse was proposed by the authors themselves: the model has to choose which of the available variables is correct at a given location in the code. The corpus consists of open-source C# projects. The graph model outperformed simpler approaches that use less structured representations of code. It also found real bugs in mature projects, which means such models can complement classical static analysis.

Key points

  • Data: 29 open-source C# repositories with about 2.9 million lines of code in total (among them RavenDB, Roslyn-like libraries, Newtonsoft.Json, EntityFramework, Lean). Some projects were held out for testing only, to check how the model performs on unfamiliar codebases.
  • Program graph: Child edges (AST structure) and NextToken edges (token order), as well as the semantic edges LastUse, LastWrite and ComputedFrom, which describe data flow.
  • Results of the best model: 32.9% accuracy on VarNaming and 85.5% on VarMisuse. On the published version of the dataset, which excludes GPL projects, VarMisuse reaches 84.0% accuracy (PR AUC 0.976) on projects already seen and 74.1% (PR AUC 0.934) on new ones.
  • Practical value: in RavenDB, the model found a place where the variable clazz had been used by mistake instead of first. The authors reported the bug, and it was fixed in PR 4138.
  • Resources: a sample GGNN implementation is on GitHub (Microsoft/gated-graph-neural-network-samples), and the dataset is at aka.ms/iclr18-prog-graphs-dataset.

Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.

 Institutions

🏢MicrosoftRedmond · United States378 works · 161,630 citations

 Fields, topics and concepts

📚 Shelves 4The field of science this work belongs to (OpenAlex fields).Computer Science · 18,614 worksInformation Systems · 1,730 worksSoftware · 119 worksComputer Science Applications · 131 works

Cite

Cite as Miltiadis Allamanis, Marc Brockschmidt and Mahmoud Khademi. 2017. Learning to Represent Programs with Graphs. arXiv:1711.00740.

The paper itself, not this page. BibTeX from the library's record of the work. DOI 10.48550/arxiv.1711.00740 · arXiv 1711.00740

@misc{allamanis2017learning,
  title = {{Learning to Represent Programs with Graphs}},
  author = {Miltiadis Allamanis, Marc Brockschmidt and Mahmoud Khademi},
  year = {2017},
  doi = {10.48550/arxiv.1711.00740},
  eprint = {1711.00740},
  archivePrefix = {arXiv},
  url = {https://doi.org/10.48550/arxiv.1711.00740}
}

References

30 references, 10 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

  1. Martín Abadi, Ashish Agarwal, Paul Barham, Eugene Brevdo, Zhifeng Chen, Craig Citro, Greg S Corrado, Andy Davis, Jeffrey Dean, Matthieu Devin, et al. Tensorflow: Large-scale machine learning on heterogeneous distributed systems. arXiv preprint arXiv:1603.04467, 2016.
  2. Miltiadis Allamanis, Earl T Barr, Christian Bird, and Charles Sutton. Learning natural coding conventions. In Foundations of Software Engineering (FSE), 2014. find
  3. Miltiadis Allamanis, Earl T Barr, Christian Bird, and Charles Sutton. Suggesting accurate method and class names. In Foundations of Software Engineering (FSE), 2015. find
  4. Miltiadis Allamanis, Hao Peng, and Charles Sutton. A convolutional attention network for extreme summarization of source code. In International Conference on Machine Learning (ICML), pp. 2091–2100, 2016.
  5. Miltiadis Allamanis, Earl T Barr, Premkumar Devanbu, and Charles Sutton. A survey of machine learning for big code and naturalness. arXiv preprint arXiv:1709.06182, 2017.
  6. Earl T Barr, Mark Harman, Yue Jia, Alexandru Marginean, and Justyna Petke. Automated software transplantation. In International Symposium on Software Testing and Analysis (ISSTA), 2015. find
  7. Al Bessey, Ken Block, Ben Chelf, Andy Chou, Bryan Fulton, Seth Hallem, Charles Henri-Gros, Asya Kamsky, Scott McPeak, and Dawson Engler. A few billion lines of code later: using static analysis to find bugs in the real world. Communications of the ACM, 53(2):66–75, 2010. find
  8. Avishkar Bhoopchand, Tim Rocktäschel, Earl Barr, and Sebastian Riedel. Learning Python code suggestion with a sparse pointer network. arXiv preprint arXiv:1611.08307, 2016. find
  9. Benjamin Bichsel, Veselin Raychev, Petar Tsankov, and Martin Vechev. Statistical deobfuscation of android applications. In Conference on Computer and Communications Security (CCS), 2016. find
  10. Pavol Bielik, Veselin Raychev, and Martin Vechev. PHOG: probabilistic model for code. In International Conference on Machine Learning (ICML), 2016. find
  11. Kyunghyun Cho, Bart van Merriënboer, Dzmitry Bahdanau, and Yoshua Bengio. On the properties of neural machine translation: Encoder–decoder approaches. Syntax, Semantics and Structure in Statistical Translation, 2014. — On the Properties of Neural Machine Translation: Encoder-Decoder Approaches
  12. Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks on graphs with fast localized spectral filtering. In Neural Information Processing Systems (NIPS), pp. 3844–3852, 2016.
  13. Justin Gilmer, Samuel S. Schoenholz, Patrick F. Riley, Oriol Vinyals, and George E. Dahl. Neural message passing for quantum chemistry. arXiv preprint arXiv:1704.01212, 2017.
  14. Marco Gori, Gabriele Monfardini, and Franco Scarselli. A new model for learning in graph domains. In IEEE International Joint Conference Neural Networks (IJCNN). IEEE, 2005. find
  15. Aditya Grover and Jure Leskovec. node2vec: Scalable feature learning for networks. In International Conference on Knowledge Discovery and Data Mining (SIGKDD), pp. 855–864. ACM, 2016. find
  16. Abram Hindle, Earl T Barr, Zhendong Su, Mark Gabel, and Premkumar Devanbu. On the naturalness of software. In International Conference on Software Engineering (ICSE), 2012. find
  17. Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. arXiv preprint arXiv:1609.02907, 2016.
  18. Yujia Li, Daniel Tarlow, Marc Brockschmidt, and Richard Zemel. Gated graph sequence neural networks. In International Conference on Learning Representations (ICLR), 2015. find
  19. Chris J Maddison and Daniel Tarlow. Structured generative models of natural source code. In International Conference on Machine Learning (ICML), 2014. find
  20. Diego Marcheggiani and Ivan Titov. Encoding sentences with graph convolutional networks for semantic role labeling. In ACL, 2017.
  21. Tomas Mikolov, Ilya Sutskever, Kai Chen, Greg S Corrado, and Jeff Dean. Distributed representations of words and phrases and their compositionality. In Neural Information Processing Systems (NIPS), 2013.
  22. Jeffrey Pennington, Richard Socher, and Christopher D Manning. GloVe: Global vectors for word representation. In EMNLP, 2014.
  23. Veselin Raychev, Martin Vechev, and Eran Yahav. Code completion with statistical language models. In Programming Languages Design and Implementation (PLDI), pp. 419–428, 2014. find
  24. Veselin Raychev, Martin Vechev, and Andreas Krause. Predicting program properties from Big Code. In Principles of Programming Languages (POPL), 2015. find
  25. Veselin Raychev, Pavol Bielik, and Martin Vechev. Probabilistic model for code with decision trees. In Object-Oriented Programming, Systems, Languages, and Applications (OOPSLA), 2016. find
  26. Andrew Rice, Edward Aftandilian, Ciera Jaspan, Emily Johnston, Michael Pradel, and Yulissa Arroyo-Paredes. Detecting argument selection defects. Proceedings of the ACM on Programming Languages, 1(OOPSLA):104, 2017. find
  27. Michael Schlichtkrull, Thomas N. Kipf, Peter Bloem, Rianne van den Berg, Ivan Titov, and Max Welling. Modeling relational data with graph convolutional network. arXiv preprint arXiv:1703.06103, 2017. find
  28. Armando Solar-Lezama. Program synthesis by sketching. University of California, Berkeley, 2008. find
  29. Mingzhe Wang, Yihe Tang, Jian Wang, and Jia Deng. Premise selection for theorem proving by deep graph embedding. In Advances in Neural Information Processing Systems, pp. 2783–2793, 2017. 1.0 0.9 0.8 0.7 0.6 0.5 0.0 find
  30. True Positive Rate SeenProjTest UnseenProjTest 0.2 0.4 0.6 0.8 False Positive Rate (a) Precision-Recall Curve Figure 6: Precision-Recall and ROC curves for the GGNN model on V AR M ISUSE . Note that the y axis starts from 50%. Table 3: Performance of GGNN model on V AR M ISUSE per number of type-cor… find

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/allamanis-2017-learning-represent-programs-graphs/