HEAT: Hyperedge Attention Networks
Authors: Dobrik Georgiev Georgiev
Marc Brockschmidt
Miltiadis Allamanis
Venue: Accepted by TMLR ()

Abstract: Learning from structured data is a core machine learning task. Commonly, such data is represented as graphs, which normally only consider (typed) binary relationships between pairs of nodes. This is a substantial limitation for many domains with highly-structured data. One important such domain is source code, where hypergraph-based representations can better capture the semantically rich and structured nature of code.
In this work, we present HEAT, a neural model capable of representing typed and qualified hypergraphs, where each hyperedge explicitly qualifies how participating nodes contribute. It can be viewed as a generalization of both message passing neural networks and Transformers. We evaluate HEAT on knowledge base completion and on bug detection and repair using a novel hypergraph representation of programs. In both settings, it outperforms strong baselines, indicating its power and generality.

Published in Transactions on Machine Learning Research (09/2022)
HEAT: Hyperedge Attention Networks
Dobrik Georgiesf
dgg30@com..co uk
Deportment of Computer Science and Technology, University of Cambridge, UK
Marc Brockschmidt
com
Microsoft Research, Cambridge, UK]
Miltiadis Allamanis
vallamanis@gooppe com
Microsoft Research, Cambridge, UKt
Reviewed on OpenReview: httpa: net/ forum? id= gCmQK6McbR
Abstract
Learning from structured data is a core machine learning task. Commonly, such data is represented as graphs, which normally only consider (typod) binary relationships between pairs of nodes. This a substantial limitation for many domains with highly-structured data. One important such domain is source code, where hypergraph-based representations can better capture the semantically rich and structured nature of code.
In this work, we present HEAT, neural model capable of representing typed and qualified hypergraphs, where each hyperedge explicitly qualifies how participating nodes contribute. can be viewed as a generalization both message passing neural networks and Transformers. We evaluate HEAT on knowledge base completion and on bug detection and repair using novel hypergraph representation of programs. In both settings, it outperforms strong basclincs, indicating its power and generality.
1 Introduction
Large parts of human knowledge can be formally represented as sets of relations between entities, allowing for mechanical reasoning over it. Common examples of this view are knowledge graphs representing our environment, databases representing business details, and first-order formulas describing mathematical insights. Such structured data hence regularly appears as input to machine lcarning (ML) systems.
In practice, this very generic framework not easy handle in ML models. One issue is that the set of relations is not necessarily known beforehand, and that the precise structure of relation not easily fixed. As an example, consider studied P, institution:I, major M), encoding the fact that person P studied at institution 7, majoring in M. However, if the instiiatiin is unknown, may want to just. consider studied (person: Ma)or: or we may need to handle case of people double-majoring, using studied (person: major: major:M,).
Existing MT. approaches usually cast such data as hypergraphs, and extend the field of graph learning approaches this setting, but struggle with its generality, Some solutions require to know the set of relations beforehand (fixing their arity, and assigning fixed meanings to each parameter), while others abstract the set. of entities to simple set and forego the use of the name of the relation and its parameters.
"Work mainly performed while interning Microsoft Research, Cambridge, UK. Now Google Research.

---

Published in Transactions on Machine Learning Research (09/2022)
71
n1
T2
f12
Ps
T3
n13
Figure 1: Representation of relation p(T) : T2 n2: T3:ng) as typed and qualified hyperedge e, ie. a
relation of type 9, and the qualified participation of the nodes ny as TI, n2 as 72, and ng as T3 in e. HEAT operates on hypergraphs with such hyperedges.
One form of data that can profit from being modeled as a hypergraph is program source code. Existing approaches model code either as simple sequence of tokens (Hindle et al. 2012) or as a graph (Allamanis al. 2020). While the former can easily leverage successful techniques from the NLP domain, is not possible to include additional domain-specific knowlodge (such as the flow of data) in the input. On the other hand, graph models able to take some of this additional information, but struggle to represent more complex relationships that require hyperedges.
jtt al. 201 8b Hellendoorn
In this work, we propose a new architecture, HEAT (HyperEdge ATtention), that is able to handle an open set of relations that may appear in several variants. To this end, we combine the idea of message passing schemes that follow the graph structure with the flexibility and representational power of Transformer architectures. Concretely, our model handles arbitrary relations by presenting cach one as a separate sequence in Transformer, where an idea akin to standard positional encodings used represent how each entity participates in the relation. The Transformer output is then used to update the represent ations of participating entities.
We illustrate the success of this technique in two very different settings: learning to infer additional relations in knowledge graphs, and learning to find and repair bugs in programs. In both cases, our model shows improvements over strong thate-of-thheart methods. Concretely, we (a) define HEAT as a novel hypergraph neural work archilecture (Sec.. 2), (b) define a novel representation of programs as hypergraphs (Sec. 3 (c) evaluate HEAT on the tasks of detecting and repairing bugs Secc. 4.1) and link prediction in knowledge graphs Seec. 4.2
Our implemeentation of the HEAT model is available the heat branch of httpps////tttt tigg..........
heurips21-self- wwwpeeessssssesddddbbeeeeeeeeeee bug- dogg-detetiion- r heat This includes code for the extrac-
tion of hypergraph representations of Python code as discussed in Sec. 3
2 The HEAT Model
In this work, we are interested in representing typed and qualified relations of the form relName (parName1. m1 parName2:no, ...) where relName represents the name of relation, ni, n2,.............. ... are entities participating in the relation, with parName1, ... describes (qualifies) their role in the relation.
Formally, such relations can be represented as typed and qualified hypergraphs: we consider a set of nodes (entities) N' = {m.,...} and a set of hyperedges H = (e). Each hyperedge = (p, describes a named relationship of type p among nodes n....ng ny where the role of node ny within is qualified using T&- Fig. illustrates the form of such hyperedge. Note that this in contrast to traditional hypergraphs where nodes participate in a hyperedge without any qualifiers. Instead, typed and qualified graphs accurately represent large range of domains maintaining valuable information.
(T,, ())))
2

---

Published in Transactions on Machine Learning Research (09/2022)
2.1 Background
Message passing neural networks (MPNN) GGimmrr et al. 2017 operate sets of nodes N and sets of (typed) edges E, where each edge (ng, Ts. nz) of type 7 connects a pair of nodes. In MPNNs, each node n E W is associated with representations ions h that are computed incrementally. The initial h stems from input features, but subsequent representations are computed by exchanging information between nodes. Optionally, each edge e may also be associated with a Concretely, each edge gives rise "message" using a learnable function fm:
h that also computed incrementally.
(m.)).n)) () Jm (h h() n53 h n!O)
To update the representation of node n, all incoming messages are aggregated with a commutation-nvvariann function AGG(.) into a single update, i.e.
- AGG (fml (9) (m (ne, 7,)) E E
(1)
AGG is commonly implemented as summation or max-pooling, though attention-based variants ex- ist (Veličković et al., 2018). Finally, each node's representation is updated using its original representation and the aggregated messages. Many different update mechanisms have been considered, ranging from just using the aggregated messages
(Kipf & Welling 2017 to gated update functions (Li et al. 2016).
Transformers (Vaswani et al. 2017) learn representations of sets of elements / without explicit edges. Instead, they consider all pairwise interactions and use a learned attention mechanism to identify particularly important pairs. Transformer layers are split into two sublayers. First, multihead attention (MHA) uses the representations of all N to compute an "update" un for each n E N,, i.e.
10 -MHA (II)) (......... b(0)
2)
Internally, MHA uses attention mechanism to determine the relative importance of pairs of entities and to compute the updated representations. Note that MHA treats its imput as (multi-)sct, and hence is permutation-invariattt To provide ordering information, a common approach is to use positional encodings, i.e. to extend each representation with explicit information about the position. In practice, this means that
(!) h + Pi...... . (1)
hig Pk where P, provides information about the position of n4, and is combination operation (commonly glement-wiss addition).
MHA operates on
The second Transformer sublayer is used to combine the updated representations with residual information and add computational depth to the model. This is implemented as
(4)
LN
h + un
(3)
h (++1) LN
(t) 9n,
+ FFN (8) )
(4)
where LN is layer normalisation Ba et al. one large intermediate hidden layer).
2016 and FFN is feedforward neural network (commonly with
2.2 HEAT: An Iatention-Based Hypergraph Neural Network
We now present HEAT, Transformer- based message passing hypergraph neural network that learns to represent typed and qualified hypergraphs.
Overall, we follow the core idea the standard message passing paradigm: our aim is to update the representa- tion of each entity using messages arising from its relations to other entities. Following Battaglia et al. 2018 we also explicitly consider representations of cach hyperedge, based on their type and the representation of adjacent entities. Intuitively, we want each entity to "receive" one message per hyperedge it participates in, reflecting both its qualifier (f.e. role) in that hyperedge, as well as the relation to other participating entities.
3

---

Published in Transactions on Machine Learning Research (09/2022)
(t) m mei-n
h
(E)
hm
(t)
I'LL
(E)
(E) Drig
(+) T2
h
(E)
T's
(
AgG
h
+
Add & Norm
(0) Mcc-
Multihead Attention
Feed Forward
(t) m
(e) +ig
Add & Norm
222
(a) Message computation for hyperedge from Fig. The previous node states had are combined with their respec- tive qualifier embeddings (t) Then, a multihead attention mechanism computes the messages m and m
h (t-1)
(b) The state update for each node n in the hypergraph. Apart from AGG this matches a standard Transformer layer of Vaswani al. 2017).
Figure 2: The HEAT Architecture.
To compule these messages, we borrow ideas from the Transformer architecture. We view each qualified hyperedge as a set of entities, with each entity being associated with a position (its qualifier the hyperedge), and then use multihead attention in Eq. 2 to compute one message per involved entity:
m
(A)
(8) = MHA ( (h (8) : E
(0) ML
(0)
(5)
(t) Here, h (1) is the current representation of the hyperedge, h is the current representation of node ny, Fa is the representation (embodding) of the qualifier т, which denotes the role of n, in e, and combines two vectors. Fig. 2a illustrates this. In this work, consider dement-wise addition for but other operators, such vector concatenation would be possible.
We can then compute single update un? for node n4 by aggregating the relevant messages computed for the hyperedges it occurs in, t.e.
( AGG (f (mmf.., le= (p.,..., (.......TTTT,.))) E H
This is equivalent to the aggregation of messages in MPNNs (cf. Eq. We then compute an updated entity representation h (t+1) following the Transformer update as described in Eqs. 3 This is illustrated in Fig. 2b The core difference to the Transformer case is the aggregation AGG(-) used to combine all messages (as in a message passing network). AGG(-) can be any permutation invariant function, such as clementwisc-sum and max, or even an another transformer (see Sec. 4.1 for experimental evaluation of these variants).
Finally, the hyperedge states h are also updated as in Eqs. 3 using the messages m computed as in Eq. and no aggregation is required because there only a single message for each hyperedge e. Initial node states (0) are initialised with node-level information (as in GNNs). Qualifier embeddings Fr, (resp. initial hyperedge states (( are obtained by breaking the name of Ti (resp. Pe) into subtokens (e.g., parName is foo_bar2 embedding matrix, and then sum-pooling. Then for each HEAT layer (!) is computed through a linear learnable layer of the sum-pooled embedding, f.e. rr,
split into par and name or foo_ bar2 into foo, bar, and 2), embodding these through (lcarnable) vocabulary
(0) w r., +..
Generalising Transformers Note that if the hypergraph is made up of single hyperedge of the form Seq (pos1:1111 pos2:112, ...) then HEAT degenerates to the standard transformer of Vaswani el. al. (2017) with positional encodings over the sequence R2....... at each layer. In the case of such sequence positions, we simply use the sinusoidal positional encodings of Vaswani al. (2017) as position embedding, rather than using a learnable embedding. Thus HEAT can thought to generalise transformers from sets (and sequences) to richer structures.
4

---

Published in Transactions on Machine Learning Research (09/2022)
Computational Considerations A naive implementation of HEAT message passing step requires one sample per hyperedge to be fed into multihead attention layer, each hyperedge of k nodes gives rise to a sequence of length k + 1, holding the edge and all node representations. To enable efficient batching, this would require to pad all such sequences to the longest sequence present in a batch. However, the length of these sequences may vary wildly. On the other hand, processing each hyperedge separately would not make use of parallel computation modern GPUs.
To resolve this, we use two tricks. First, we consider "microbatches" with a pre-defined set of sequence lengths {16, 64, 256, 768, 1024], minimising wastage from padding. Second, we "pack" several shorter sequences into single sequence, and then use appropriate attention masks in the MHA computation to avoid interactions. For example, a hyperedge of size 9 and a hyperedge of size 7 can be joined together to yield a sequence of length 16. [ppx. A] details the packing algorithm used. This process is performed in-CPU during the minibatch preparation.
3 Representing Code as Hypergraphs
Program source code a highly structured object that can be augmented with rich relations obtained from program analyses. Traditionally, source code is represented in machine learning either sequence of tokens Hiiddle et al. 2012 tree (Yin & Neubig 2017), or as graph (Allamanis et al.) 2018b Hellendoorn et al. 2020). Graph-based representations (subsuming tree-basod ones) commonly consider pairwise relationships among entities in the code, whereas token-level ones simply consume a token sequence. In this section, we present a novel hypergraph representation of code that retains the best of both representations.
Our program hypergraph construction is derived from the graph construction presented by Allamanis et al. (2021), but uses hyperedges to produce a more informative and compact representation. The set of nodes in the generated hypergraphs include tokens, expressions, abstract syntax tree (AST) nodes, and symbols. However, in contrast to prior work, do not only consider pairwise relationships, but instead use typed
and qualified hypergraph (Fig. 1j. We detail the used hyperedges and their advantages next. Fig. 3 in Appx. B illustrates some of the considered relations on a small synthetic snippet.
Tokens For the token sequence L,, l2...., l of a snippet of source code, we create the relation Tokens (p1: :1,, p2:t2, ...). This is the entire information used by token-level Transformer models, considering all-to-all relations among tokens. Note that in standard graph-based code representations, the token sequence is usually represented using chain of NextToken binary edges, meaning that long-distance relationships are hard to discover for models consuming such graphs. For very long token sequences, which may cause memory issues, we "chunk" the sequence into overlapping segments of length L, similar to windowed, sparse attention approaches. We use L = 512 in the experiments. Within HEAT and specifically for the Tokens (-) hyperedges, to reduce the used parameters and to allow arbitrarily long sequences, the qualifier embeddings rpt, rp2; rp.: are computed using the fixed sinusoidal embeddings of Vaswani et al. (2017) instead of learnable embeddings.
AST We represent the program's abstract syntax tree using AstNode relations, with qualifiers corresponding to the names of children of each node. For example, an AST node of binary operation is represented as AstNode (node: 1Bgnnpp left: Riert, op: right: Similarly, a AstNode (node: cond: then: else:n.) represents an if statement node nnstmm- In cases where the children have the same qualifier and are ordered, (e.g. the sequential statements within a block) we create numbered relations, i.e. AstNode (node: Aplock s1:01, s2:m2, ...). For Python, we use as qualifier names those used in [ibCST] In contrast, most graph-based approaches use Child edges to connect a parent node to all of its children, and thus lose information about the specific role of child nodes. As a consequence, this means that left and right
children of non-commutative operations can not easily be distinguished. Allamanis et al.] (2021) attempts to rectify this using a NextSibling edge type, but still is not able to make use of the known role of cach child.
Control and Data Flow To indicate that program execution can flow from any of the AST nodes Pi. P1.P..... to one of the AST nodes $1, 82,... we use the relation CtreF(prev: prev:1ps ..., succ: su For example, if c: p1 else: p2; s1 would yield (prev:pp, prev:p2, suco:s1). Sim- ilarly, we use relations MayRead and MayWrite to represent. dataflow, where the previous location at which
5

---

Published in Transactions on Machine Learning Research (09/2022)
symbol may have been read (written to) are connected to the succeeding locations. Note that these relations compactly represent data and control flow consolidating N-to-M relations (e.g. N states may lead to one of M states) into a single relation, which would otherwise require N -M edges in a standard graph.
Symbols We use the relation Symbol (sym: occ:11, occ: .... may_ pay_last__ use: Rur may may_ way_last_wvg use:uuz ....) to connect all nodes n1, Ri,, referring to a symbol (e.g. variable) to a fresh node na. introduced for each occurring symbol. We annotate within this relation the nodes Bus Ruz.... that are the potential last uses of the symbol within the code snippet.
Functions A challenge in representing source code is how to handle calls to (potentially user-defined) functions. As is usually not feasible to include the source code of all called functions the model input (for computational and memory reasons); appropriate abstractions need to be used. For a call (invocation) of function foo (argl, .... argl) defined by def foo (par1, .... parN): ..... we introduce the relation foo (rval:n, par1: .... Warg: where is the invocation expression node and Pargl,.... MargN are the nodes representing each of the arguments. Hence, we generate one relation symbol for each defined function, and match nodes representing arguments to the formal parameter names as qualifiers. This repre- sentation allows to naturally handle the case of variable numbers of parameters and arbitrary functions.
Syntactic sugar and operators are converted in the same way, using the name of the corresponding built-in function. For example, in Python, a in converted into the relation contains (self : item: n,,) and a - is converted into isu____b_______ (self :,,, other: following the reference Python data model
Finally, we use the relation Returns (fn:n4, from: from: ...) to connect all possible return points for a function with the AST node nt for the function definition. Similarly, Yields (-) is defined for generator functions.
4 Evaluation
We evaluate HEAT on two tasks from the literature: bug detection and repair (Allamanis et al.
2021 and knowledge base completion (Galkin et al. 2020 We implemented it as Py-
Torch Paszke et al. 2019) Module, available on the heat branch of https::///// tiggth....... com/microsoft/
wttp:s21ssel-suuuriaieeee Suupervised-bug-deeeeee aattectiia-aad--epppa/trreeeeeee
4.1 HEAT for Bug Detection & Repair
We evaluate HEAT the bug localisation and detection task of Allamanis et al. (021 in the supervised setting. This is hard task that requires combining ambignous information with reasoning capabilities able to detect bugs in real-life source code.
For this, we built on the open-source release of PYBUGLAB of Allamanis et al. 2021 1, making two changes:
(1) we adapt the graph construction from programs produce hypergraphs as discussed in Sec. 3) and (2) use HEAT to compute entity representations from the generated graphs, rather than GNNs or GREAT.
Datasct We use the code of Allamanis et al. 2021 to generate dataset of randomly inscrted bugs to train and evaluate a neural network in supervised fashion. Consequently, we obtain new variant of the *Random Bugs" test dataset, consisting of ~ 760k graphs. We additionally re-extract the PyPIBugs dataset with the provided script, generating hypergraphs as consumed by HEAT, and graphs generated by the bascline models. However, since the PyPIBugs dataset is provided in the form of GitHub URLs referring to the buggy commit SHAs, some of them have been removed from GitHub and thus our PyPIBugs dataset contains 2354 samples, 20 less than the one used by Allamanis et al. 2021).
Model Architecture We modify the architecture of Allamanis et al. (0221) to use 6 HEAT layers with hidden dimension of 256, heads, food-forward (FFN in Eq. 4) hidden layer of 2048, and dropout rate of 0.1. As discussed above, our datasets differ slightly from the data used by Allamanis et al. (2021). and we re-evaluated their released code our new datasets. We found this rerun to perform notably better than what.
6

---

Published in Transactions on Machine Learning Research (09/2022)
Table 1: Evaluation Results on Supervised Bug Detection and Repair on supervised PyBugLab.
Random Bugs
PyPIBugs
Joint
Loc.
Repair
Joint
Loc.
Repair
GNN
Allamanis et al. 2021
62.4
73.6
81.2
20.0
28.4
61.8
GREAT
Allaamanis et al.
2021
51.0
61.9
76.3
16.8
25.8
58.6
GNN
Allamanis et al.
2021
1 (reru))
69.8
79.6
83.4
22.0
28.3
66.7
GREAT
T
Allamanis et al.
2021 (rerun)
65.6
74.4
81.8
16.8
21.9
67.7
HEAT
76.5
83.1
88.5
24.6
29.6
71.0
HEAT DeepSet-based messages
74.0
81.1
87.3
23.2
28.6
69.0
HEAT without qualifier embeddings
69.2
76.7
85.6
19.1
25.7
65.0
HEAT AGG & CrossAtt
76.5
83.0
88.2
23.4
27.9
71.5
HEAT without FFN
73.7
80.7
87.0
20.7
25.4
69.2
HEAT without hyperedge stale
75.7
82.4
88.0
23.0
28.6
71.1
Reported on different random bugs datasst and a slightly different PyPIBugs dataset.
was originally reported in the paper. In private communication, the authors explained that their public code included a small change to the model architecture compared to the paper: the subnetworks used for selecting program repair rule are now shallow MLPs (rather than inner products), which increases performance across the board. Our HEAT extension follows the code release, and hence we use max-pooled subtoken embeddings to initialise node embeddings, a pointer network-like submodel to select which part of the program to repair, and a shallow MLPs to select the repair rules. We also re-use the PyBugLab supervised objective, which is composed of two parts: a PointerNet-style objective requiring to identify the graph node corresponding to a program bug, and a ranking objective requiring to select a fixing program rewrite at the selected location.
Results We show the results of our experiments in Table where "Loc." refers to the accuracy in identifying the buggy location in an input program, "Repair" to the accuracy in determining the correct fix given the buggy location, and "Joint" to solving both tasks together. The results indicate that HEAT improves performance on both considered datasets, improving the joint localisation and repair accuracy by 10% over the two well-tuned baselines.
In particular, observe that HEAT substantially improves GREAT (Hellendoorn al. 2020 which also adapts the Transformer architecture to include relational information. However, GREAT eschews explicil modelling of edges, and instead uses (binary) relations between tokens to bias the attention weights in the MHA computation. We obscrve a less pronounced gain over GNNs, which we believe is due to the simpler information flow across long distances and the clearer way of encoding structural information in HEAT. (see Sec. 3) We note that Allamanis et al. (2021) showed that their models also outperform fine-tuned variants of the cuBERT (Kanade al.) 22200) model, which stems from self-supervised pre-training using masking objectives. Consequently, we believe that HEAT outperforms such large models well, though comparison
to recent very large models, adapted to the task (Chen et. al. 2021 to future work.
Austin et al. 2021
Li et al. 2022 is left.
Variations and Ablations To understand the importance of different components of HEAT, we experi- ment with five ablations and variations, shown on the bottom of Table
First, we study the importance of using multi-head attention to compute messages, In particular, we are interested in determining whether considering interactions between different nodes participating in hyper- edge necessary. To this end, we consider an alternative scheme in which we first compute hyperedge reprosentation using aggregation of all adjacent nodes, using their qualifier information, i.c.
qe AcG' ([n! Fr, @ h( Fre h(() ......
7

---

Published in Transactions on Machine Learning Research (09/2022)
Table 2: Results on the Random Bugs dataset when applying HEAT on a graph dataset representing edges as (binary) odges.
Joint Localisation & Repair
Localisation
Repair
GNN Allamanis et al. 2021 (reru))
69.8
79.6
83.4
GREAT Allamanis et al. 2021 (reru))
65.6
74.4
81.8
HEAT (on binarised hypergraphs)
71.6
79.3
85.5
HEAT (on hypergraphs)
76.5
83.1
88.5
In our experiments, use Deep Set Zaheer et al. 2017] model to implement Acc'. We then compute messages for each node n, using a single linear layer W, í.e.
m ReLU (W- (r,, @ h d.1).
The results indicate that this model variant is still stronger than the GNN and GREAT architectures, but that HEAT profits from explicilly considering the relationships of nodes participating in a hyperedge.
Next, we analyse the importance of using qualifier information in our model. To this end, we consider a variant of HEAT in which we remove from Eq. the qualifier information Fra i.e.
m
m MHA ([hS), hi b......
The results clearly indicate that the qualifier-as as-oositinn scheme used in HEAT is crucial for good performance. In particular, it indicates that the qualifier information contained in the data is very valuable, and emphasises the importance of considering qualified hypergraphs.
We also considered using more expressive aggregation mechanism for messages, replacing the max pooling use to implement AcG. Specifically, we use multi-head attention between the current node state (as queries in the attention mechanism) and the messages computed for all adjacent hyperedges (appearing as keys and values). This is reminiscent of graph attention networks (Veličković et al., 2018). which use an attention mechanism to determine the respective importance of binary edges when aggregating messages. In our experiments, this performed slightly worse than the aggregation using a simple max, while being substantially more memory- and compute-intense
Next, analyse whether the representational capacity is improved by the feodforward network (Eq. 4 in the node and edge updale. Removing these substantially reduces the number of parameters of the model. The results indicate that these intermediate, per-represnntation computation steps add valuable capacity to the model. This is especially apparent on the PyPIBugs dataset.
Another ablation we consider is a model variant in which we do not use evolving edge states, but instead re-use (0) on all HEAT layers. We observe a similar or slightly reduced performance on the joint localisation and repair. This suggests that updating the edge state provides valuable representational capacity to the model. Edge states, can be seen as the [CLS] token traditional transformers, providing "scratch space" for storing intermediate information for cach hyperodge.
Finally, assess the importance of the underlying data representation, investigating whether represen- tation of programs as hypergraphs (differing from the PyBugLab baseline) alone explains the performance improvement. For this, we convert the generated hyperedges to (binary) edges and use HEAT to learn from these (binary) graphs. This experiment intents to disentagle the effects of the different data representation from the effects of HEAT's architecture. The results, shown in [Table 2] indicate that even on binarised hypergraphs, HEAT outperforms the bascline GNN and GREAT models (especially on accuracy of choosing program repairs), even though large parts of its architecture are not properly utilised by the data. However, HEAT also takes advantage of the more expressive and compact data representation.
8

---

Published in Transactions on Machine Learning Research (09/2022)
4.2 HEAT for Knowledge Graph Completion
Knowledge graphs (KGs) can be accurately represented as typed and qualified hypergraphs. We now focus link prediction over a hyper-relational KG, which can be viewed as completing a knowledge base by additional likely facts.
Dataset Following the discovery of test leaks and design flaws by Galkin et al. (2020) in common benchmark
datasets such as WikiPeople (Guan et al. 2019 and JF17K (Wen et al. 2016) we chose one of the variations of the new WD50K dataset presented there WD50K (100). It. is derived from Wikidata, containing 31k statements, all of which use some qualifier. To model a qualified triple statement of the form (s, r, o, Q) with Q a set of qualifier ceaaffer/entiig /entity pairs (qr; qU;), we create a single hyperodge with special qualifiers src (resp.) obj for the source and object of the relation, i.e. (r. {(Trc, s). (obj. 0)} U Q). Using the example of Fig. 1 of Galkin et al. 2020), , the fact that Einstein studied mathematics at ETH Zurich in his undergraduate is expressed
the hyperedge: EducatedAt (src: Nignnttiin obj :7ETH Zurich, degree: (lBachetorr major: MMathenatica)
In the released WD50K dataset, raw Wikidata identifiers (e.g. P69, Q937, etc.) are used to refer to entities and relation names. We enrich the dataset by additionally retricving natural language information for these entities from Wikidata (e.g. replacing P69 by "educated at") and allow the models to consume this information, to encourage similar treatment of similarly named relationships and entities.
Model Architecture We modified the open-source release of STARE by Galkin et al. (2020) replacing the GNN-based STARE encoder by HEAT. We used a single layer of HEAT with embedding size of 100 and a single layer of the Transformer used for calculating the final predictions] Apart from some training parameters (see below), hyperparameters (dropout, etc.) remain documented in Appendix C of Galkin et al. (2020)
Since our goal is to evaluate the elfectiveness of HEAT, the remainder of the model is identical to the original implementation of Galkin et al. (2020): queries for relation j are represented as the concatenation of the entity embeddings, relation embedding, and qualifier embeddings, as shown in Fig. 3 of Galkin el al. (2020). These are then passed through a Transformer block and a fully-connected layer to obtain the probability over each entity being a possible object of the relation.
To process the additional natural language information about relations and entities we extracted (see above), we build vocabulary using byte pair encoding (BPE), and then embed the individual tokens and use sum pooling to obtain initial node and relation representations. We evaluated variations of both the original STARE model and our HEAT-base variant using this information, see below.
Training and evaluation Training is performed as in Galkin et al. (2200) using binary cross entropy with label smoothing. In this link prediction task, a matching score is calculated for all possible relation objects given source, relation and qualifier-entity pairs (Dettmers et al. 2018 p.3). We trained our model for 1K epochs with a learning rate of 0.0004 and batch size of 512. Hyperparameters were fine-tuned manually, using the provided validation set in the StarE implementation. For direct comparison with Table 3 of Galkin el al. (2020) we report mean reciprocal rank (MRR) and hits at 1 and 10 (H@1, H@10) matching the original evaluation setting. We train and evaluate all models using 5 random seeds and report standard deviations.
shows the results of our evaluation on WD50K (100). We reran the original STARÉ implementation, both to validate our setup and to obtain standard deviations. First, we observe that using HEAT instead of the original GNN-based STARE encoder improves results, without any further changes to the architecture. We expect that recent orthogonal work improving STARE by Yu & Yang (2021) would similarly improve with our model.
Results Table 3
Next, we consider the influence of using natural language information extracted from Wikidata. We note that the original STARE encoder does not profit from this information. In contrast, the HEAT-basod model slightly improves results, even though most words in the extracted data are extremely sparse. Finally, we evaluate the less expressive message aggregation scheme of max pooling (as discussed in Sec. 4.1) Here, we see that its performance is only marginally worse
Figure 3 of Galkin al. 2020 bottom rectangle.
9

---

Published in Transactions on Machine Learning Research (09/2022)
Table 3: Link prediction results on WD50K (100) of Galkin et al. (2020). Standard deviations are obtained over different seods.
Model
MRR
H@1
H@10
STARE (GNN)² Galkin et al. 2020
0.58641.002 0.654
7..77200000
STARE (GNN) with NL information
0.653
0.586 003
0.774=0.005
STARE (HEAT) AGG _ max, no NL information
0.666+0.008
0.605 004
0.779=0.002
STARE (HEAT)- AgG A CrossAtt, no NL information
0.666=0.003
0.599 001
0.787=+0.000
STARE (HEAT) AGG _ CrossAtt, with NL information
0.667+0.003
0.601 003
0.789=00.00
Hy- MyyTTranSormerr*
Yuu & Yang 2021)
0.699
0.637
0.812
1 Rerun of Galkin et al. (200 implementation with 5 seeds.
Current statc-of-thc-art.
5 Related Work
We review closely related techniques for learning on hypergraphs, and then briefty discuss some particularly relevant work from the application areas of learning code and knowledge bases.
Hypergraph learning We broadly classify hypergraph learning into three approaches: hyperedge expan- sion, spectral mothods, and spatial (message bessing-based]] methods. Compared to HEAT, none of the existing methods can directly work on typed and qualified hypergraphs.
In the first class, hypergraphs are transformed into (binary) graphs and then a standard GNN is applied the resulting graph. This approach is taken by Agarwal et al. (2006), who use clique and star expansion (representing each hyperedge a full or a star graph respectively) ), Yadati et al. (2019), who represent each hyperedge by a simple weighted edge whose endpoints can be further connected with weighted edges to mediator nodes and Yang et al. (2020), who create a node for each pair of incident nodes and hyperedges and connect those stemming from the same node or hyperedge. These approaches can re-use cxisting GNN architectures, but at the cost of a significantly increased number of edges.
The next class of methods aims at generalising the concepts of graph Laplacians and spectral convolutions to the domain of hypergraphs. Feng et al. (2019) use the observations that nodes in the same hyperedge should not differ much in embedding to define a normalised hypergraph Laplacian. A similar approach has been employed by Fu et al. 2019), who utilise the hypergraph p-Laplacian, Bai et al. (2021) extend Feng et al. (2019) where the node-edge incidence matrix is weighted via an attention mechanism. Such methods are usually applied to transductive learning tasks and either do not fully support typed or qualified hyperedges or are limited to a fixed number of hyperedge types or nodes in a hyperedge. This makes them inapplicable in our setting.
The final class of methods generalises the concept of neural message passing to hypergraphs. HyPerSAGNN (Zhang et al. 2020 is ion based neural network, capable of handling variable-sized hyperedges, but has been developed for the purposes of hyperedge prediction and is not directly applicable for node classification. HyperSAGE (Arya et al. 2020) performs convolution in two steps: nodes to hyperedges and hyperedges to nodes, where the aggregation during the node and hyperedge message passing step is a power- mean function, but suffers from poor parallelisation and other practical issues (Huang & Yang 2021 p. 2). Chien al. 2021)) propose AllSet, a message passing scheme based on representing hyperedges as sets and aggregations using permutation-invarian previous hypergraph convolution methods, Chien et al. (2021) propose two implementations of AllSet, using DeepSets (Zaheer et al. (017)) and Transformers (Vaswani et al. 2017). This work is most similar to ours, but does not consider the setting of qualified hyperedges. A natural consequence is that the model then computes a single "message" per hyperedge, whereas HEAT computes different messages for each participating node (which only required when nodes play different roles in the hyperedge). In Sec.. 4.1 we consider two relevant. ablations. These show that the use of qualifier information is crucial for good results in the PyBugLab setting, and that our message computation based on multihead attention is stronger than a DeepSet-basel alternative.
functions. AllSet can provably subsume a substantial mumber of
10

---

Published in Transactions on Machine Learning Research (09/2022)
To the best of our knowledge, are the first to focus on processing typed and qualified hyperedges: two hyperedges with the same element set can be different if their type does not match and elements in a hyperedge can have different qualifiers (roles). Furthermore, our architecture is not restricted to a fixed mumber of hyperedge sypes/qualifet and can generalise to srpes/qualifiers unseen during train time.
Knowledge Graph Completion Knowledge graph (KG) completion has emerged due to the incomplete- ness of KGs JJi et al. 2 Embedding- based models (Bordes et al., 2013 Schlichtkrull et al. 2018 Shi & Wennnner 2017) first. learn low-dimensional embedding and then use it to calculate scores based on these embeddings and rank the top k candidates. HEAT is variation of an embedding based model, but we focus on hyper-relational KGs. Other, non-embedding based approaches also cxist, e.g. reinforcement learning [Kiong et al.) 2017] or rule-based ones (Rocktäschel & Riedel
2017). Since we do not use such techniques, we omit discussing them here and refer the reader to Ji et al. 22021 SIV.A).
Similarly to hypergraph learning, other works model hyper-relational KGs by simplifying qualified relations to simpler representations: Wen et al. (2016) use clique expansion, which can be costly, (Fatemi et al. 2020 represent hyper-relational facts as n-ary relations, but do not have explicit source/object of the relation and instead of considering the qualifier of an entity as in HEAT, their model only considers the position of an entity within the relation; Guan et al. (2019) break n-ary facts into n + 2 qualifier loffferr/ent /entity pair making qualifier/enti /entity pairs indistinguishable to "standard" rel, o) triples. These expansion- based approaches cannot leverage semantic information such as the interaction of different qualifier mnalifier/entityy /entity pairs (Yu & Yang 2021
Closest to our work is STARE (Galkin et al. 2020 STARE uses GNN-like convolution, consisting of several steps (ef. equations (5)-(7) of Galkin et al. 2020) on hyper-relational graphs to calculate updated entity embeddings, which are then fed through a Transformer module. In Sec. 4 we show that HEAT outperforms their GNN-bassd encoder.
Learning on Code Over the last decade, machine learning has been applied to code on a variety of tasks (Allamanis et al. 2018a). A central theme in this research area. is the representation of source code. Traditionally, token-level reprosentations have been used (Hindle et al., 2012), but Allamanis et al. (2018b) showed that graph-level approaches can leverage additional semantic information for substantial improvements.
Subsequently. Fernandes et al. 2019): Hellendoorn et al. (2200) showed that combining token-level and graph- level approaches yields best results. By using a relational transformer model over the code tokens [Hellenoorr et al. (2020) overcomes the inability of GNN models to handle long-range interactions well, while allowing to make of additional semantic information expressed as graph edges over the tokens. However, token-based representations do not provide unambiguous locations for annotating semantic information (í.e. edges) for non-token units such as expressions (e.g. a+b or a+b+c). Additionally, all these approaches have been limited to standard (binary) edges, making the resulting graphs large and/or imprecise (see [Sec. 30. Our experiments with HEAT show that a suitable representation as typed and qualified hypergraph further improves over the combination of token-level and binary graph-level approaches.
6 Conclusions & Discussion
We introduced HEAT, a neural network architecture that operates on typed and qualified hypergraphs. To model such hypergraphs, HEAT combines the idea of message passing with the representational power of Transformers. Furthermore, experiments show that HEAT is able to learn well from these highly structured hypergraphs, outperforming strong recent baselines on their own datasets. A core insight in our work is to apply the power of Transformers to several, overlapping sets of relations at the same time. This allows to concurrently model sequences and graph-structured data. We believe that this opens up exciting opportunities for future work in the joint handling of natural language and knowledge bases.
showed how to convert program source code into such hypergraphs. Our
242 for the source and object qualifiers
11

---

Published in Transactions on Machine Learning Research (09/2022)
References
Sameer Agarwal, Kristin Branson, and Serge J. Belongie. Higher order learning with graphs. In International Conference on Machine Learning (ICML), 2006.
Miltiadis Allamanis, Earl Barr, Premkumar Devanbu, and Charles Sutton. A survey of machine learning for big code and naturalness. ACM Computing Surveys (CSUR), 51(4):1-37, 2018a.
Miltiadis Allamanis, Marc Brockschmidt, and Mahmoud Khademi. Learning to represent programs with graphs. In International Conference on Learning Representations (ICLR), 2018b.
Miltiadis Allamanis, Henry Jackson-Flux, and Marc Brockschmidt. Self-supervised bug detection and repair. In Newral Information Processing Systems (NewrIPS), 2021.
Devanshu Arya, Deepak K. Gupta, Stevan Rudinac, and Marcel Worring. Hypersage: Generalizing inductive representation learning on hypergraphs. arXiv preprint ar urXiv:20100043 2020.
Jacob Austin, Augustus Odena, Maxwell Nye, Maarten Bosma, Henryk Michalewski, David Dohan, Ellen Jiang, Carrie Cai, Michael Terry, Quoc Le, and Charles Sutton. Program synthesis with large language models. arXiv preprint 017:2200..07732, 2021.
Lei Jimmy Ba, Ryan Kiros, and Gooffrey E. Hinton. Layer normalization. arXiv preprint arXin:1607.06550 2016.
Song Bai, Feihu Zhang, and Philip H. S. Torr. Hypergraph convolution and hypergraph attention. Pollern Recognit., 110:107637, 2021. doi: po.101//j.aatcog.22222.
Peter W. Battaglia, Jessica B. Hamrick, Victor Bapst, Alvaro Sanchez- Gonzalezz Vinícius Flores Zambaldi, Matousz Malinowski, Andrea Tacchetti, David Raposo, Adam Santoro, Ryan Faulkner, Çaglar Gülgehre, Francis Song, Andrew J. Ballard, Justin Gilmer, George E. Dahl, Ashish Vaswani, Kelsey Allen, Charles Nash, Victoria Langston, Chris Dyer, Nicolas Heess, Daan Wierstra, Pushmeet Kohli, Matthew Botvinick, Oriol Vinyals, Yujia Li, and Razvan Pascanu. Relational inductive biases, deep learning, and graph networks. arXiv preprint ar 00011100010111 01261, 2018.
Antoine Bordes, Nicolas Usunier, Alberto Carcia-Durán Jason Weston, and Oksana Yakhnenko. Translating embeddings for modeling multi-relational data. Tn Neural Information Processing Systems (NeurIPS), 2013.
Mark Chen, Jerry Tworek, Heewoo Jun, Qiming Yuan, Henrique Ponde de Oliveira Pinto, Jared Kaplan, Harri Edwards, Yuri Burda, Nicholas Joseph, Greg Brockman, et al. Evaluating large language models trained on code. Xixiv preprint ar arXiv:2107.0337, 2021.
Eli Chien, Chao Pan, Jianhao Peng, and Olgica Milenkovic. You are AllSet: A multiset function framework for hypergraph neural networks. arXiv preprint arXiv:2106.192 13264, 2021.
Tim Dettmers, Pasquale Minervini, Pontus Stenetorp, and Sebastian Riedel. Convolutional 2d knowledge graph embeddings. In AAAI Conference on Artificial Intelligence, 2018.
Bahare Fatemi, Perouz Taslakian, David Vázquez, and David Poole. Knowledge hypergraphs: Prediction
beyond binary relations. In International Joint Conferences on Artificial Intelligence (IJCAT), 2020.
Yifan Feng, Haoxuan You, Zizhao Zhang, Rongrong Ji, and Yue Gao. Hypergraph neural networks. In AAAT Conference on Artificial Intelligence, 2019.
Patrick Fernandes, Miltiadis Allamanis, and Marc Brockschmidt. Structured neural summarization. In International Conference on Learning Representations (ICLR), 2019.
Sichao Fu, Weifeng Liu, Yicong Zhou, and Liqiang Nic. HpLapGCN: Hypergraph p-laplacian graph convolu-
tional networks. Neurocomputing, 362:166-177 2019. doi: 10.1016//.neucom..211 201...000000...
12

---

Published in Transactions on Machine Learning Research (09/2022)
Mikhail Galkin, Priyansh Trivedi, Gaurav Maheshwari, Ricardo Usbeck, and Jens Lehmann. Message passing for hyper-relational knowledge graphs. In Empirical Methods in Natural Language Processing, 2020.
Justin Gilmer, Samuel S Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. In International Conference on Machine Learning (TCML), 2017.
Saiping Guan, Xiaolong Jin, Yuanzhuo Wang, and Xueqi Cheng. Link prediction on n-ary relational data. In World Wide Web Conference, 2019.
Vincent J Hellendoorn, Charles Sutton, Rishabh Singh, Petros Maniatis, and David Bieber. Global relational models of source code. In International Conference on Learning Representations, 2020.
Abram Hindle, Farl T Barr, Zhendong Su, Mark Gabel, and Premkumar Devanbu. On the naturalness of software. In 2012 94th International Conference on Software Engineering (ICSE), 2012.
Jing Huang and Jie Yang. UniGNN: unified framework for graph and hypergraph neural networks. In Internal Joint Conferences Artificial Intelligence (IJCAI), 2021.
Shaoxiong Ji, Shirui Pan, Erik Cambria, Pekka Marttinen, and S Yu Philip. A survey on knowlodge graphs: Representation, acquisition, and applications. IEEE Transactions on Neural Nelworks and Learning Systems, 2021.
Aditya Kanade, Petros Maniatis, Gogul Balakrishnan, and Kensen Shi. Learning and evaluating contextual embedding of source code. In International Conference on Machine Learning (ICML), 2020.
Thomas N. Kipl and Max Welling. Semi-supervised classification with graph convolutional networks. In International Conference on Learning Representations (ICLR), 2017.
Yujia Li, Daniel Tarlow, Marc Brockschmidt, and Richard Zemel. Gated graph sequence neural networks. In International Conference on Learning Representations (ICLR), 2016.
Yujia Li, David Choi, Junyoung Chung, Nate Kushman, Julian Schrittwieser, Rémi Leblond, Tom Eccles, James Keeling, Felix Gimeno, Agustin Dal Lago, Thomas Hubert, Peter Choy, Cyprien de Masson d' d'Autume, Igor Babuschkin, Xinyun Chen, Po-Sen Huang, Johannes Welbl, Sven Gowal, Alexey Cherepanov, James Molloy, Daniel J. Mankowitz, Esme Sutherland Robson, Pushmeet Kohli, Nando de Freitas, Koray Kavukcuoglu, and Oriol Vinyals. Competition-level code generation with alphacode. arXiv preprint Xrx.v2200 07814, 2022.
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, and Soumith Chintala. Pytorch: An imperative style, high-performance deep learning library. In Newral Information Processing Systems (NeurIPS). 2019.
Tim Rocktäschel and Sebastian Riedel. End-to-end differentiable proving. In Neural Information Processing Systems (NewrIPS), 2017.
Michael Schlichtkrul,, Thomas N. Kipf, Peter Bloem, Rianne van den Berg, Ivan Titov, and Max Welling. Modeling relational data with graph convolutional network. In Extended Semantic Web Conference (ESWC), 2018.
Bacxu Shi and Tim Weninger. Proje: Embedding projection for knowledge graph completion. In AAAI Conference on Artificial Intelligence, 2017.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Neural Information Processing Systems (NeurIPS), 2017.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pictro Liò, and Yoshua Bengio. Graph Attention Networks. Tn International Conference on Learning Representations (TCL.R) 2018.
13

---

Published in Transactions on Machine Learning Research (09/2022)
Jianfeng Wen, Jianxin Li, Yongyi Mao, Shini Chen, and Richong Zhang. On the representation and embedding of knowledge bases beyond binary relations. In International Joinl Conferences Artāficial Intelligence (IJCAI), 2016.
Wenhan Xiong, Thien Hoang, and William Yang Wang. DeepPath: A reinforcement learning method for 2017.
knowledge graph reasoning. arXiv preprint
Naganand Yadati, Madhav Nimishakavi, Prateek Yadav, Vikram Nitin, Anand Louis, and Partha P. Taluk- dar. HyperGCN: A new method for training graph convolutional networks on hypergraphs. In Neural Information Processing Systems (NewrIPS), 2019.
Chaoqi Yang, Ruijie Wang, Shuochao Yao, and Tarek F. Abdelzaher. Hypergraph learning with line expansion. arXiv preprint arXit:2005.0455 2020.
Pengcheng Yin and Graham Neubig. A syntactic neural model for general-purpose code generation. In Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pp. 440 450, 2017.
Donghan Yu and Yiming Yang. Improving hyper-rclational knowlodge graph completion. arXiv preprint wrXiv:2104081100 2021.
Manzil Zaheer, Satwik Kottur, Siamak Ravanbakhsh, Barnabés Póczos, Ruslan Salakhutdinov, and Alexan- der J. Smola. Deep sets. In Neural Information Processing Systems (NeurIPS), 2017.
Ruochi Zhang, Yuesong Zou, and Jian Ma. Hyper-SAGNN: a self-attention based graph neural network for hypergraphs. In International Conference on Learning Representations (ICLR), 2020.
14

---

Published in Transactions on Machine Learning Research (09/2022)
A Packing Hyperedges for HEAT
Hyperedges in HEAT have variable size, i.e. variable number of nodes that participate in each hyperedge. For each hyperedge HEAT uses a multihead attention to compute the outgoing messages me However, multihead attention has a quadratic computational and memory cost with respect to the size of the hyperedge.
A naive solution would require us pad all hyperedges up to maximum sizc. However, this would be wasteful. On the other hand, need to batch the computation across multiple hyperedges for efficient GPU utilisation. To achieve a good trade-off bet large batch sizes (a lot of elements) and minimal padding, consider a small set "microbatches". To pack the hyperedges optimally, would solve the following integer linear program (ILP)
1.ck
min Σ (L).00 vi)
Σ 13
8.1.
y E {0, 13. Bzj E {0,1), Vi.j
1.,k
Σ Tij = 1,
1.m Σ Tifh S ,1 Vj.
where Vy is a binary variable indicating whether "bucket" j of size Lj (i.e. belonging in the microbatch of size I.g) is used (i.e. contains any elements). Then, 1j is the width of the jth hyperedge. Tay are binary variables for i = I..n and j 1..k indicating if the element is in bucket j and s, the width of bucket The objective creates few buckets as possible to minimise the wasted (quadratic) space/ time needed for multihead attention over variable-sized sequences. The first constraint requires that each element is assigned to exactly one bucket and the second constraint that each used bucket is filled up to its capacity.
However, the complexity of this ILP is prohibitive. Instead, we resort in using a greedy algorithm to select the "microbatches" " used. This detailed in Algorithm 1
Algorithm Greedy Hyperedge Packing into Microbatches
buckets []] for h in ootteDDDeeeddinggBBaaaayyyeeeee do Ads.ddded +- False
for bucket in buckets do
if bucket. remaininSim 2 h.width then buckot.add(h)
wasAdded +- True break
if not wasAdded then bucketSize +
nucket +- createBBuckel((uuckeSSii
newBucket.adddee
buckets. www.apppenddwwwweecce
return GroupBuckets (ateccccttttooooooooooecesoorror
15

---

Published in Transactions on Machine Learning Research (09/2022)
if
is u_foo,
5/0
g
foo, n1
20 bar
Sample Hyperedges (Relations)
Tokens (p1:n1, p2: p3:73, p4:n4, p5:n5, p6:n7, p7:ng, p8:ng, 19:110, p10: p11 12 P12: ....
AstNode (node: 199, test:nn, body:n17)
AstNode : value:n1s> targeting)
foo 712, fzz:ng)
Assuming that foo is defined as def foo(fzz):
getattribute___rvaae (rval: self: n220 name:7122)
Tayeeaddprev:nn) prev: succ:n25)
Ctr1F(prev:ng prev: succ:n2s)
Symbol (sym: occ:14, occ:Ng, oca:11y, may_ pay_last_uae use:: :125)
Figure 3: Sample relations for the synthetic snippet shown the top. The AST nodes and tokens are wrapped in boxes and numbered appropriately in preorder fashion. Only a few samples of the relations (mapped to hyperedges) are shown below.
B Code as Hypergraph Example
Fig. shows synthetic code snippet with all the token and AST nodes enclosed in boxes. Some sample relations are also shown. Finally, Fig. shows full hypergraph for the following code snippet
foo b):
if in b: a
return a
16

---

Published in Transactions on Machine Learning Research (09/2022)
Figure 4: A full hypergraph sample for the snippet disc Hyperedges denoted as shaded (blue) boxes. Best. viewed on screen. The Tokens (-) hyperedge is omitted for clarity but the sequence of tokens is placed in the box (right).
17


Reviews:
[{"review_id": "JvjykBOJTM", "reviewer": "Reviewer_MmCu", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "*Strengths:*\n\n1. While the use of transformers for hypergraph modelling is not new (Chien et al. 2021), incorporating qualifier information like positional embeddings is a nice contribution and ablations in Table 1 show that it is very effective.  \n2. Empirical results are strong. \n\n*Weaknesses:*\n\nI do not identify significant weaknesses.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper proposes to use self-attentional neural networks to learn hypergraph-based representations. Different from traditional approaches that mainly consider binary relations, the proposed approach, HEAT, models more complicated hyperedges and the associated qualifier (role) information of the edges, which are proved to be crucial in empirical ablations. HEAT adopts the transformer arch to compute node and edge representations while modifying the multi-head attention based on the graph structure. On code bug detection/repair and knowledge graph completion experiments, HEAT outperforms strong baselines that are based on GNNs.\n", "claims_and_evidence_yn": "", "claims_explanation": "", "audience_yn": "", "audience_explanation": "", "requested_changes": "*An important detail to secure my recommendation for acceptance:*\n\nWhen replacing layers from the baseline with the HEAT layer, do you strictly control the model size to be the same for a fair comparison? I didn’t find this information in the paper but I feel it is necessary to clarify it. \n", "broader_impact_concerns": "This paper presents a general model for hypergraph modelling and applies it to bug detection/repair and KG completion, I don’t have concerns on its ethical implications.\n", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "L2vloVmXcV", "reviewer": "Reviewer_KWMM", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n+ Very well written, exposition and mathematical details were clear\n+ Strong scientific rigor with experimentation (eg. rerunning baselines when there was unavoidable dataset discrepancies, as well as providing them similar benefits as HEAT where possible)\n+ Thorough ablation study evaluating architectural design choices (eg. aggregation function, splitting tokens, use of qualifier embeddings)\n+ The model is well-motivated, from both a mathematical and practical standpoint\n+ Computational implementation details are included, to the extent that reproducing the model should be possible\n+ The evidence presented does support the author's claims regarding the benefits of the proposed model\n\nWeaknesses:\n- The model is only evaluated on two datasets, however:\n  (1) Evaluating on another bug-detection dataset may require significant effort, due to programming language, and (while I am not overly familiar with bug-detection datasets) PyBugLab seems to be the best choice for such an evaluation.\n  (2) There are admittedly few hyperrelational datasets available, and WD50K is the recommended in Galkin et al. as other choices have various issues.\nWhile these limitations are understandable, it also means that it is difficult to draw broader conclusions. For example, no single pooling method performs best in all scenarios, so a practitioner employing it would have to do some minor architecture search.\n\n- A more thorough comparison to baselines would strengthen the claims, and make the paper more complete.\n  (1) For bug detection, the authors mention that a comparison to recent large language models is left for future work. It is likely that adapting such models to this task would take a reasonable amount of effort, however such an evaluation on it's own may not be significant enough to stand on its own as a publication, and thus the concern is that such a comparison is never made and further effort may be expended on tasks which are unwittingly already solved by other approaches.\n  (2) For KB Completion, the authors mention the recent work of Yu & Yang (2021), and claim that the advantages provided in that work are mostly orthogonal to those provided by HEAT, suggesting that the two might work synergistically. It must be noted, however that the Hy-Transformer architecture of Yu & Yang greatly outperforms HEAT on WD50K (100), with MRR 0.699, H@1 0.637, and H@10 0.812. For completeness it would seem reasonable to include this baseline in the table, and for completeness actually demonstrate the suggested synergistic benefits of HEAT and Hy-Transformer (which, it seems, may also lead to additional benefits on the bug-detection task, now that it is framed as hypergraph completion).\n\nQuestions:\n- Second paragraph, page 8, it is stated that the additional computational depth provided by the feedforward network improves *generalization*. One would assume that adding this significant number of parameters would have more of an effect on overall model capacity, perhaps at the expense of (relative) generalization performance - is it really generalization that is improved, or overall representational capacity?\n- How much does using sub-tokens (as described in the middle of page 4) help with the bug detection task?", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "In this work the authors introduce a novel model for hypergraph representation called HEAT, which combines ideas from message passing neural networks (MPNN) and transformers. HEAT learns embeddings for the hyperedge, each node, and the qualifiers of the hyperedge which are updated by several rounds of message-passing. The connection to transformers is that the message are calculated via multi-headed attention, where the qualifier representation takes the place of the positional encodings in a standard transformer. Messages from all edges that a node participates in are then aggregated using a permutation-invariant function, at which point the standard transformer update is applied (a linear combination of current node embedding and the message is passed through a layer normalization, combined with a feed-forward network projection of itself and layer-normalized again). The authors evaluate this architecture on two tasks: knowledge base completion and bug detection and repair, finding that it outperforms reasonable baselines in both tasks.", "claims_and_evidence_yn": "", "claims_explanation": "", "audience_yn": "", "audience_explanation": "", "requested_changes": "I do not have any significant changes to request.\n\nTypos:  \n1: \"... profit from modelling as ...\" -> \"... profit from being modeled as ...\"  \n2: Consider assigning the edge to $e$, eg. $e = (n_i, \\tau_i, n_j)$, and make the subsequent $\\tau$ into $\\tau_i$.  \n6: \"... requires to combine ambiguous information with reasoning capabilities towards detecting bugs ...\" -> \"... requires combining ambiguous information with reasoning capabilities capable of detecting bugs ...\"  \n8: \"... replacing the the GNN-based ...\" -> \"... replacing the GNN-based ...\"  \n8: Could not parse \"... and embedding of qualifiers, entity pairs of the relation $j$.\"  \n8: \"... and a fully-connected layers to ...\" -> \"... and a fully-connected layer to ...\"", "broader_impact_concerns": "None.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "vAENy5xHmv", "reviewer": "Reviewer_egRw", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "## Strengths \n+ The proposed architecture is very general and potentially applicable to a wide variety of domains\n+ The finding that no existing architecture satisfies all the requirements of expressing typed+qualified+n-arry relations is important.\n+ The architecture is based on components of the Transformer architecture but organized in a different way, which keeps it simple.\n+ The significance of the results is convincing\n\n## Weaknesses\n- Additional tasks will further improve the paper. Even though typed+qualified+n-arry relations are very common in \"the wild\", I understand that it's difficult to find appropriate datasets that were processed, annotated / curated this way. Maybe the VarMisuse dataset (Allamanis et al., 2018) can be converted to n-arry relations? Can HEAT be applied to existing *pairwise* datasets such as VarMisuse? This is just a recommendation for further improving the paper, and not a mandatory change.\n\n## Additional Comments and Questions\n* The paper can be easily strengthened by comparing with additional types of out-of-the-box (for example, from PyTorch Geometric) GNN convolutions in Table 1 and Table 2.\n* Minor: the authors claim that their architecture generalizes Transformers and message-passing GNNs. I think that by expressing arbitrary n-arry relations, HEAT also kind of generalizes arbitrary-shaped Conditional Random Fields (CRFs). What do the authors think about that? Is that a too strong claim?\n\n## Summary\nI am expecting to hear the authors' response to the section \"Requested Changes\" to secure my recommendation, but overall this is a good paper, \nthe made claims are supported by accurate, convincing, and clear evidence,\nthe paper is relevant to a very broad audience,\nand I recommend acceptance.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper presents a neural architecture HEAT for encoding graphs with *typed* and *qualified* *hyperedges*.\n\nThis new architecture generalizes transformers by having the ability to represent relations rather than all-to-all interactions, generalizes standard message-passing GNNs by having the ability to represent *hyperedges* (rather than pairwise, binary, edges), and generalizes previous hyperedge-GNNs by having the ability to represent edges that are both *typed* and *qualified* (where the order of argument matters).\n\nSuch kinds of typed+qualified n-arry relations are very general and exist in many natural domains; in this paper, the authors demonstrate the importance of such relations in knowledge graphs and in programs, where the new approach provides significant gains over previous work.", "claims_and_evidence_yn": "", "claims_explanation": "", "audience_yn": "", "audience_explanation": "", "requested_changes": "The difference between HEAT and baselines such as GREAT or GNN (Table 1) comes from two main sources:\n1. The different representation of the data - pairwise relations (GNN, GREAT) vs. n-arry relations (HEAT).\n2. The different neural architecture - that is, Transformer-style attention function, Multi-heads, LayerNorm, FeedForward layers, possibly more parameters, etc.\n\nI wonder if the authors can perform some experiments to disentangle these two sources? For example, perform the experiments of Table 1 with the pairwise \"topology\" of the data (as GNNs), but with the HEAT \"architecture\" applied to pairwise relations?\n\nIn the other direction - how would the n-arry hyperedge \"topology\" (as in HEAT) would be processed by standard strong GNNs such as GIN/GAT/GATv2 ? \n", "broader_impact_concerns": "no concerns", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The reviewers liked the paper and were satisfied with the authors' responses to their questions. Given this, I am delighted to recommend acceptance. Please make sure to incorporate the feedback in the reviews in the final version. 
Decision: Accept (poster)