HyperGCN: A New Method of Training Graph Convolutional Networks on Hypergraphs--论文笔记

论文题目–《超图卷积网络–一种新的方法用于训练超图的图卷积网络》

摘要
在许多现实世界的网络中，其实有很多关系都不仅仅是成对的关系，比如co-authorship, co-citation网络，其中的关系非常的复杂。超图提供了一种灵活且自然的工具去模拟诸如以上网络的复杂关系。以上存在的复杂的关系刺激了使用超图学习的问题。目前一种流行的方法是基于超图的半监督学习，其目标是分配标签给超图中没有标签的节点。由于目前基于图卷积的半监督学习很流行，而且高效，受到启发，提出了超图卷积网络。一种基于谱理论的用图卷积的半监督方式进行训练的方法。证明了超图卷积网络在目前数据集上有了最好的效果。

1.介绍
首先，说一下超图是什么。普通的图结构就是一条边只能连接2个节点，但是在超图之中，一条边可以连接多个节点，如下图：

其中一条边之中就包含了多个节点。所以就可以用超图来表示现实中更加复杂的关系。
本文的贡献如下：
1.提出了超图卷积网络，这种新的在超图中用图卷积网络进行训练的方法，而且也提出了快速超图卷积网络的方法。
2.在现实世界的超图中，用本文的方法去解决半监督学习的问题，并且在当前的数据集中用实验证明了，该方法达到了最好的效果。
3.讨论了该方法对于HGNN的优势。

2.相关背景
2.1图卷积网络：对于基于谱域的图卷积公式已经知道了就是：

这是一个2层的图卷积公式，其中A是标准化之后的邻接矩阵，是经过拉普拉斯矩阵变换得来的矩阵，其中包含了图中特别的信息。X是特征矩阵。然后后面一个是权重矩阵，是一个经过训练得到的参数矩阵。最外面是一个softmax函数将里面得到的数值映射到0~1的域中便于模型做出预测。其中：

2.2
基于图卷积网络的半监督学习
半监督学习就是在训练样本之中既有有标签的样本，也有无标签的样本。目标就是根据规律给无标签的样本分配标签。然后做出预测。
对于多类问题，设有q个类，用用最小交叉滴损失来优化模型：

其中Y是期望的类别标签，然后Z是ij边包含的节点的类别的预测得分。

3.超图卷积网络
首先看一个表格是图里的符号于超图里的符号的对应关系：

为了在超图上利用图卷积的半监督学习的方法，我们首先需要针对超图定义一个拉普拉斯矩阵。

3.1超图的拉普拉斯矩阵
定义（超图拉普拉斯）。作者定义的超图拉普拉斯矩阵的方法是，对于一个超图，使用特定的方法将它变为一个带权的简单图。然后得到图之后就可以将他利用在图卷积里面了。至于将超图化为简单图的方法如下：
1，对于每一个超边，因为超边里面包含很多个节点，然后我们现在就只选取2个节点，只选取信号特征最大的两个节点，然后这两个节点之间的边来代表超边。公式如下：

2.然后在第一步里面定义的边上加上权重，经过这一步之后，就已经将超图变为简单带权图了
3.在有给出的每个节点的特征信号的时候就能够用以上的方法计算出超图的拉普拉斯矩阵了，这样也就能在超图中运用图卷积公式了。公式如下：

其中A是超图经过变换之后的带权领接矩阵，D是该邻接矩阵的度矩阵，然后I是单位矩阵。

3.2单层的超图卷积网络
最后简单图Gs标准化之后的带权邻接矩阵表示为As，然后在简单图Gs上使用图卷积公式，然后图卷积公式就是公式一。
最后对于网络中节点V的更新信息公式为：

其中Θ是训练的权重参数，A是两个节点之间边的权重，h是上一层的节点的隐含信息。
然后整个过程可以用下图来表示：

如图对于一个超图。首先是要将超图转化为简单图。如图，用定义的超图算子来确定边，具体的方法是：

公式的意思是，对于一个超边，我们选取其中包含节点隐含的信息的二阶范数的最大值最大的两个节点为带权简单图组成的边。

3.3用中间节点增强的超图卷积网络
在将超图转化为带权简单图的过程之中，因为一个超边中我们只选择了两个节点，这样的话，对于整个超图就会存在信息的丢失，所以我们现在将超图中被忽略的节点定义为：

然后讲这些中间节点将选定的节点连接起来。就可以想象成，定义的带权简单图是一个层面，然后在另外的一个维度会有这些中间节点和带权简单图相连接。
然后由于这个中间节点是在超边之中没有被选中的，那么，如果增加一个节点，就会分别和两个节点i，j相连接，那经过数学公式推导，得出每增加一个节点，相应边的个数为：

所以相应的每条边的权重为

如下图：

3.4快速超图卷积网络
如果一个初始化的特征没有权重，那么我们这样所构造的超拉普拉斯矩阵的方法，我们就叫它快速超图卷积网络，因为这个超拉普拉斯矩阵只需要计算一次，而不需要每一个epoch都更新，所以这种方法会更快。

4.实验