LEARNING TO REPRESENT PROGRAMS WITH HETEROGENEOUS GRAPHS 学会用异构图表示程序(从AST中构建异构图)

大多数已有的研究是以抽象语法树来表示源码信息，还有一些研究是向AST中添加额外的边把源码转换成图的形式，然后利用神经网络学习程序图的表示。尽管这些工作提供了额外的控制或数据流信息向AST发送任务，但他们忽略了AST本身结构信息的重要方面：节点和边的不同类型 。

为了解决节点和边类型的信息，考虑使用异构图学习源码，提出一个新的构建公式，从带有额外节点和边的类型信息的AST中建立异构图 。使用程序语言的ASDL语法定义程序图的节点和边类型，然后使用异构图神经网络训练这些图 。在两项任务上评估我们的方法：代码注释生成和方法命名。（两个不同领域的Python数据集）这两个任务都需要理解完整代码段的语义 。

很多研究使用AST表明代码结构信息，但AST的一个问题是，它们不能明确反映语法依赖之外的结构信息，如控制和数据流。一个可行的解决方案是在AST上添加不同类型的控制和数据流的边以生成程序图，并在程序图上应用图神经网络（GNN）来学习它们的表示。然而，这些方法不考虑除了控制或数据流的边之外，原始AST的节点和边的类型也不同。

我们的向AST中添加节点和边的类型的想法与异构图的概念是一致的。使用抽象语法描述语言获取AST上的节点和类型信息。

在获取到代码段的异构图之后，需要找到一种图神经网络(GNN)去表示这些图。我们把目光转向图嵌入 领域。异构图神经网络被广泛使用在图嵌入中，不像传统的图神经网络，异构图神经网络能够在消息传递节点集成节点和边的类型信息并把节点的不同类型映射到不同的特征空间 。在异构图上使用异构图转换器(HGT)计算程序表示。

贡献如下：1）使用异构图表示程序，并在源代码段上使用异构图神经网络

2）使用ASDL语法从程序的AST上建立异构程序图

3）在两个不同的任务上评估此方法，这两个任务涉及对源代码片段的图形级预测。我们的方法在注释生成和方法命名任务这两方面都优于其他GNN模型

方法

从源码中创建异构程序图(HPG),如何在异构图上应用异构图神经网络

异构程序图

ASDL语法和上下文无关语法比较相似，多了两种重要信息：type和field.ASDL语法中有两种类型：复合类型(composite type)和原生类型(primitive type)。每种复合类型定义一组构造器，如定义，一组构造器由一组field标识，在一个构造器中，每个field都由一个唯一名和一个修饰符(single, optional (?) or sequential (*))构成，表示该字段中元素的有效数量。ASDL语法中包含丰富的语义信息，已经成功应用到代码生成及语义解析中。

ASDL构造器序列可以创建AST。下图展示了异构图形式的ASDL的AST。所有节点都有一个类型和值，每个非终端节点都是一个构造器，每个终端节点都是一个原生类型的值。构建异构图时，使用构造器名作为节点值或终端token的值，并用他们的复合/原生类型作为节点类型。每个父子关系属于父节点构造器的一个特定field。因此可以把每一个父子的边和ASDL的field名联系起来。在实践中，一些节点只有类型信息没有节点名(当一个符合类型只定义了一个没有名字的单个构造器)，把他们的节点值赋值为和节点类型一样。

除了AST的边，还向程序图中添加边，通过程序文本的顺序连接一个终端节点到另一个终端节点。异构程序图中的每一条边，添加一条含有新的边类型的backward edge(后向边)(比如：body边的backward edge为body_reverse类型)提升图的连接性。

异构图转换器

异构图转换器(HGT)： 一种基于注意力机制的异构图神经网络，学习程序图表示。

一个异构图包含节点集和边集，每一个节点类型和图中属于节点类型集和边类型集的边。

一个HGT层包含三个组件：

heterogeneous mutual attention(异质互注意力)：

异质互注意力机制与multi-head attention(多头注意力机制)相似。对于一条边，注意力计算：

Keys和Queries是基于源节点 s 或目标节点t 的类型计算。是节点s在HGT的第层的状态，h 是注意力头的数量

heterogeneous message passing(异质信息传递)：

然后为 e 计算Message:

target-specific aggregation(特定目标聚合)：

最后，HGT聚合Message信息和注意力得分，并更新有剩余连接的节点的hidden state

HGT和传统的GNN的不同是HGT使用位置编码对节点的时间顺序进行建模。在我们的方法中，为每个节点s 分配一个固定的时间戳T(s) ,是有对AST深度优先搜索，从左到右遍历时的位置决定。采用正弦函数进行位置编码，并将其添加到初始节点嵌入作为第一个HGT层的输入。

实施

对于GNN编码器，我们堆叠8层的GNN模型，使用带指针机制的LSTM作为解码器。解码器在GNN最后一层从输入图的状态中计算注意力得分。因为解码器指针机制的目标是把输入的tokens(通常是identifier name)复制到输出序列中,不需要计算所有节点的注意力，只需要计算终端的token节点。

该方法与已有的同构图(GGNN,R-GCN)比较，对于所有的GNN模型，我们保持解码器不变，并使用与我们提出的方法相同的图构造策略。对于同构图模型，移除了节点类型信息但保留了边类型信息，因为我们所有的GNN baseline都能够处理不同的边类型。我们用图形神经网络库DGL在PyTorch中实现所有的模型。

总结

本文中提出了程序AST中异构性的思想。并且提供了一种框架，使用ASDL语法用程序异构图来表示源码，在异构图上使用异构图代码转换器，我们的工具与之前的GNN模型相比对两个图形级的预测任务(comment generation和method naming)效果更佳。