ICLR 2020|基于自注意力机制的超图图神经网络

作者 | 程豪 校对 | 李仲深

今天给大家介绍的是卡耐基梅隆大学马坚教授课题组在ICLR2020上发表的文章“Hyper-SAGNN:a self-attention based graph neural network for hypergraphs”。超图的图表示学习可以用来提取高阶模式，这在许多现实世界问题中发挥至关重要的作用。这篇文章提出了一种新的基于自注意力的图神经网络，称为Hyper-SAGNN，可以适用于不同大小的同质和异质超图。证明了Hyper-SAGNN 在传统任务上明显优于最先进的方法，同时也在一项称为outsider identification的新任务上取得了突出的表现。Hyper-SAGNN将有助于图表示学习，以揭示不同应用中复杂的高阶交互作用。

一、研究背景

超图可以用来表示高阶的相互作用。为了分析高阶相互作用数据，通常假设超边是可分解的，可以直接将每个超边展开为对边。然而，早期的工作DHNE（Deep Hyper Network Embedding）指出了异质不可分解超边的存在性，即其中超边的不完全子集中的关系不存在性。最近基于深度学习的模型已经从图泛化到超图。基于超边的嵌入方法（HEBE）旨在通过将对象表示为一个超边来学习特定异构事件中每个对象的嵌入情况。然而，HEBE在稀疏超图上表现不佳。深度超图嵌入（DHNE）模型使用MLP直接对元组关系进行建模。与同为图或超图设计的其他方法如Deepwalk、node2vec和HEBE相比，该方法能够在多个任务上获得更好的性能。不幸的是，MLP的结构需要固定大小的输入，使得DHNE只能处理k均匀的超图，即超边只包含k个节点。

本文中提出的的Hyper-SAGNN通过一个基于自注意力机制的图神经网络来解决所有这些挑战，该网络可以学习节点的嵌入情况并预测非k均匀异构超图的超边。Hyper-SAGNN显著地优于现有的方法，并且可以应用于各种超图问题上。

二、模型与方法

论文模型的架构

模型的输入能够表示为一个元组

，这个元组首先通过一个前馈神经网络得到

，这里

，在文中把

称为节点i的静态嵌入，因为节点i的嵌入和元组中其他元素无关。

同时也通过一个多头图注意力层产生一组新的节点嵌入向量

，这被称为动态嵌入，因为这个嵌入依赖于元组中所有节点的特征向量。

有了静态和动态嵌入，然后计算二者之差的Hadamard幂，然后将计算结果再经过一层带有Sigmoid激活函数的全连接层，得到概率打分

。最后所有的输出

的平均值作为最后的输出

，公式如下所示：

这里

能被认为是静态嵌入和动态嵌入之间的平方加权伪欧氏距离。这被称为伪欧氏距离是因为这里并没有限制权值为非零值或者求和结果为1。网络的目标是建立静态/动态嵌入对的平均“距离”与节点组形成超边的概率的相关性。由于动态嵌入是元组内相邻节点的特征（具有潜在的非线性变换）的加权和，因此这个“距离”反映了每个节点的静态嵌入能够多大程度上可以用元组内相邻节点的特征来近似。这种设计策略与自然语言处理中的CBOW模型有一些相似之处。

此外，在对图中顶点的嵌入初始化的时候，有两种初始化方法，一种是基于编码器的方法，还有一种是基于随机游走的方法，如下图所示：

在基于编码器的方法中，在图的邻接矩阵中，每一行向量

可以作为顶点的初始化向量，然后经过多层神经网络迭代嵌入：

在基于随机游走的方法中，从某个起点出发，依据超边的权值作为路径选择概率，将选择出来的路径输入到Skip-gram模型中训练得到顶点嵌入。

三、实验结果

论文在四个数据集上进行了测试比较，数据集描述如下：

1. GPS：GPS网络数据，超边是由（用户，位置，活动）关系产生的；

2. MovieLens数据集：社交网络数据，超边是由（用户，电影，标签）关系产生的；

3. drug数据集：来自FAERS的药物网络。超边是由（用户，药物，反应）关系产生的；

4. wordnet数据集：来自于Wordnet3.0的语义网络数据。超边是由（头实体，关系，尾实体）组成的，表示单词之间的关系。

3.1 与现有方法的比较

Hyper-SAGNN和现有方法在网络重建任务中进行了比较：

这里后缀E和W分别表示使用编码初始化和随机游走初始化。结果表明，相比GHNE算法来说，Hyper-SAGNN取得了重大的改善。

3.2 非k-均匀超图上的性能比较

论文使用Hyper-SAGNN在非k-均匀超图上进行了链接预测任务和节点分类任务。对于前文提到的四个数据集，分解其中的一条超边为3条逐对的边。实验结果如下所示：

结果表明Hyper-SAGNN能够保留图中不同层级的结构。同时和只在超边上训练模型相比，把普通边也包含到训练过程中并不对性能造成显著提升。

3.3 Outsider Identification

除了上文提到的传统任务之外，作者定义了一个新任务outsider identification。如果节点组

中的节点

满足：

则称

为一个outsider。

Hyper-SAGNN能够通过分析

到

的值解决这个问题。假设最小的

对应的节点

是outsider。首先正常训练模型，然后将模型的最后一层的平均池化层替换为最小池化层并且微调几轮。然后把包含已知的outsider节点的三元组作为模型的训练输入并且计算模型输出的对应最小概率的节点和outsider节点匹配的top-k的准确率。因为这个任务需要基于超边的预测结果，所以只在drug数据集上进行。结果发现top-1对应的acc为81.9%，top-2的acc为95.3%。实验结果表明切换池化层能够获得更好的性能（从78.5%升至81.9%）。

3.4 在单细胞 Hi-C数据集上的实验

为了评估Hyper-SAGNN的学习细胞嵌入的有效性，论文在scHi-C数据上进行了实验。实验是在2个数据集上进行的。第一个数据集是由四种人类细胞系的scHi-C数据组成的。，第二个数据集为小鼠胚胎干细胞周期的scHi-C数据。随后将得到的嵌入使用PCA和UMA算法降维到2维并可视化：

所有这些结果都证明了Hyper-SAGNN将scHi-C数据集表示为超图的有效性 ，并且有很大的潜力，以对细胞间变异的高阶基因组组织提供深入洞察。

四、总结

在这项论文中提出了一个新的图神经网络模型Hyper-SAGNN用于超图上的表示学习。该框架能够灵活地处理同质超图和非均匀超图。论文实验表明Hyper-SAGNN解决了现有方法的不足，并且能顾改善当前SOTA的性能表现。Hyper-SAGNN的计算效率很高，因为输入到图注意力层的大小由最大超边大小（而不是一阶邻域的数目）来限定。

Hyper-SAGNN的一个潜在的改进是在计算节点的静态/动态嵌入之前以额外的计算成本允许在所有一阶邻居上进行信息聚合。在这种设计下，节点的静态嵌入仍然满足我们的约束条件，即对于输入元组已知超图，它是固定的。这样能允许将先前开发的关于图的方法，例如GraphSAGE和GCN以及为超图设计的方法（如HyperGCN）纳入该框架，以获得更好的预测性能。

代码

https://drive.google.com/drive/folders/1kIOc4SlAJllUJsrr2OnZ4izIQIw2JexU?usp=sharing

参考文献

ICLR | Zhang,R.,Zou,Y., & Ma,J.(2020). Hyper-SAGNN: a self-attention based graph neural network for hypergraphs. ArXiv, abs/1911.02613.

https://openreview.net/forum?id=ryeHuJBtPH