Summary
The paper presents a graph-based representation for LLVM IR programs for processing with graph neural networks. The representation is based on ProGraML, an established technique for such graph representations, but adds several features to the graph: collapsing nodes that refer to the same variable, adding additional edges between memory stores and the variables they can affect, explicitly representing constants in the graph, and representing compositional data types (e.g., arrays of arrays) as multiple distinct nodes rather than single nodes. The authors evaluate across a range of LLVM IR learning tasks, and show that Perfograph outperforms ProGraML (and all other baselines in most contexts).
Strengths
* Finding and understanding good program representations is an important problem in the field of learning for code
* The proposed approach identifies a novel set of features which qualitatively seem important, and which are validated to be useful in the ablation study
* Assuming that the evaluation is indeed fair (see weaknesses below), the proposed approach significantly outperforms ProGraML, achieving a large increase in accuracy (seemingly solving many of these tasks near perfectly).
Weaknesses
* Fairness of comparison against baselines:
* Perfograph is a version of ProGraML with some added and removed nodes and edges. Each added node/edge adds additional power for a graph neural network. For a fair comparison against baselines (ProGraML in particular), the authors must show that for a given compute budget (i.e., FLOPs or wall clock time), Perfograph outperforms ProGraML; this would involve either scaling up/down ProGraML or Perfograph.
* Are the datasets used exactly the same as in prior work? For example, Section 5.4 reports using an 80/20 train/test split, which I cannot find discussed in [10]
* Line 372 mentions that the authors "could not reproduce the results in PROGRAML paper" for the algorithm classification task. Does this lack of reproducibility also affect the evaluated benchmarks that were not in the ProGraML paper (seemingly, everything other than 5.2)? If so, this is a major point that must be discussed at a high level in the paper.
* Given the advent of large-context Transformers, I would be curious how well such a model performs when applied to the raw IR (i.e., without an explicitly featurized graph representation). However, since this paper is explicitly building on the prior work of ProGraML, I do not consider this to be a condition for acceptance.
* Overall, the clarity of the submission is moderate.
* Section 4.1: without a deep understanding of the ProGraML representation, it is very hard to understand these graphs (and therefore the issues that the proposed approach fixes in them). Perhaps highlighting or otherwise identifying the specific nodes discussed could help.
* Line 323: is this an arithmetic or geometric average?
* Line 368: what are the units of these errors?
* Several claims about novelty or related work are misleading:
* Lines 72-73: "this token-based representation... fails to capture..." This claim is misleading. Sequence processing models are entirely capable of learning such graph-structured relationships; such complex relationships are also not unique to code (e.g., natural language has pronouns, nested structures, etc.)
* Line 176: the proposed "Digit Embedding" is very similar to some digit representations approaches used in Transformers (for example, Geva et al. 2020) which embed each digit, add/concatenate with a positional encoding, and aggregate with attention.
* I believe the paper would be significantly stronger with the ablation studies moved to the main body, but this is a stylistic choice and is not a factor in my score
* If I'm understanding Appendix 2 correctly, the Perfograph GNN is evaluated with only 2 layers; ProGraML is evaluated with 6 (Cummins et al., Section 6.2). How was this parameter chosen? What is the average diameter of the evaluated graphs (for both Perfograph's graphs, and ProGraML's graphs)?
Questions
* Please see the questions in "clarity" in the discussion of weaknesses above (and other questions throuhgout).
* Does Perfograph use more compute or have more capacity than ProGraML? Does it still outperform ProGraML when given equal power?
* What steps have the authors taken to ensure that the implementation of ProGraML compared against in Sections 5.3-5.7 is correct (since as noted in Line 372, in one context the authors "could not reproduce the results in PROGRAML paper")?
* Do all other baselines use the exact same training/test set split?
* How were hyperparameters tuned for Perfograph?
I would be willing to raise my score given evidence that for the same compute budget, Perfograph still outperforms ProGraML (or evidence that my assumption here, that Perfograph uses more compute than ProGraML, is incorrect).
Rating
7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
Confidence
4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.
Limitations
The paper does not explicitly discuss limitations of the technique.