作者丨张云喆

单位丨暗物智能科技

研究方向丨NLP推理、数学符号推理

研究背景

现实生活中很多的数据可以用图（graph）来建模，比如社交网络数据，paper 引用数据等。对于 AI 而言，一个常见的任务是半监督分类，即对图中的每一个点进行分类，在仅有部分点有标注的情况下。

处理理此类问题，比较经典的方法是 GCN [1]，通过对相邻节点的特征聚合操作来对每个节点进行特征提取。GCN 等 GNN 模型对于节点之间的关系表征是二元的，即仅能表征两个节点 之间的关系，对于大于二元的关系组只能通过多个二元关系的方式去近似。

超图模型（Hypergraph）就是针对这种情况提出的一种网络结构 [2]。如图 1 所示，不同类型的数据中都存在着多元关系，超图模型的基本设定就是一个边可以包含大于 2 个点，去拟合多元关系。

然而超图模型和图模型存在着一样的问题，即大部分模型中节点之间的关系来自于数据本身的属性，是一种静态的关系。这样会导致模型忽视很多不包含在这些静态关系中的隐含关系。为此，本文提出了一种基于超图模型的网络进化算法，通过图卷积提取的特征来进一步挖掘新的关系，示意图如图 2 所示。在图网络的进化过程中，可以丢弃一些不重要的关系同时挖掘新的关系。

算法过程

整个算法流程分为三个部分，首先通过节点之间的关系对 hypergraph 进行构建，然后对提取出的 hypergraph 进行卷积操作提取特征，最后根据新的提取特征构建新的 hypergraph。三个流程加在一起就表示了一次图网络的进化，这种进化操作可以被叠加多次，使得节点之间的关系可以被多次调整。 

Hypergraph Construction

根据节点特征构建 hypergraph 的流程如下：

构建过程结合了 KNN 和 Kmeans 的方法。我们首先要清楚 hypergraph 的表示通常采用邻接矩阵的形式，矩阵大小为 | V | * | E |，分别表示节点的数量和边的数量，其中有关系的节点和边 h(v, e) = 1, 其余的 h(v, e) = 0。

首先算法针对每一个节点，采用 knn 的方法找到和该节点最相似的 n 个节点，形成一个 hyperedge，我们就得到了 |V| 个 hyperedge。然后我们在利用 kmeans 方法在节点中圈出 K 个中心点，对于每⼀一个节点，我们将它归属到最近的 S 个中心点，这样我们又得到了 K 个新的 hyperedge。 

Hypergraph Convolution

节点卷积时通过构建一个 k * k 的 transform matrix，来将节点的特征维度压缩到 k 维大小。通过 transform matrix 和节点特征的相乘来对同一个 hyperedge 内节点的相互关系进行建模和表示。最后经过一个卷积操作进行维度的压缩，得到和包含这些节点的边的特征。边（hyperedge）的卷积操作为对于每一个节点所关联的边集合中，通过上一步得到的每一条边的特征，首先通过 MLP 计算自己的权重，然后再根据得到的权重进行相加得到每个节点的特征。 

实验结果

算法在两个数据上做的评测。 

Cora 数据集，含有 2708 个节点和 5429 个边的关系，每个节点代表一篇学术文章，关系表示文章之间的相互引用，这是一个带有天然 hypergraph 结构的数据集。微博数据集，含有 5550 条推文， 推文包含文字以及图片，其中 4196 条为正向情感，1345 条为负向情感。

▲ 图7. ablation study of different modules

Cora 数据集的任务为半监督节点分类，一共有 7 个类别。文章 follow 了之前 SOTA 结果的实验设定，分别测试在不同 label 覆盖率下的节点分类准确率，可以看出算法对比其他方法有提升，并且在 label 覆盖比较低的时候提升比较明显。同时作者在该数据上做了 ablation study，通过移除 hypergraph 构建方式以及 graph evolve 的过程，实验结果都有些下降。

微博数据集是一个完全没有初始关系网络的数据集，因此算法可以测试通过特征相似度挖掘的关系是否行之有效。同时实验还比较了不同方法的训练时间，在这个任务上该方法超过了之前的一系列 SOTA 结果。 

结论和分析

本文基于超图网络模型（hypergraph），构建了一种通过节点特征相似度来让图网络自我进化的算法。优势在于通过不断的迭代和挖掘可以构建初始状态不包含的关系属性，对于挖掘隐含的关系是一种比较有效的方法。这个方法给我们带来了一定的启发，同时我认为有几点方向值得继续探索：

• 实验中对于两个数据集，模型参数设定的 layer 都设定为 2 层，推测 layer 叠加过多可能会带来训练困难等问题，可能是一个值得思考和优化的地方。

• 利用 kmeans 和 knn 来构建 graph 的关系可能比较简单和易于实现，可以探索更高级的构建 graph 的方式，并且对 graph 的结构进行一些弱监督。 

• GNN 以及 hypergraph 网络模型目前重点的实验任务在于节点分类，关系的构建等，可以考虑利用 hypergraph 结构去辅助 NLP 任务做知识的推理。