张云喆作者暗物智能科技公司NLP推理、数学符号推理研究方向

IJCAI 2019 论文解读 | 基于超图网络模型的图网络进化算法


研究背景

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

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

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

图1. 不同类型数据中的关系展示

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

图2. 超图网络进化示意图

算法过程

图3. 算法流程示意图

整个算法流程分为三个部分,首先通过节点之间的关系对 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

图4. vertex convolution module
图5. hyperedge convolution module

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

实验结果

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

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

图6. cora数据集实验结果

图7. ablation study of different modules

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

图8. 微博数据集实验结果

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

结论和分析

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

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

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

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

PaperWeekly
PaperWeekly

推荐、解读、讨论和报道人工智能前沿论文成果的学术平台。

理论GCN论文解析IJCAI 2019进化算法图网络
2
相关数据
权重技术

线性模型中特征的系数,或深度网络中的边。训练线性模型的目标是确定每个特征的理想权重。如果权重为 0,则相应的特征对模型来说没有任何贡献。

参数技术

在数学和统计学裡,参数(英语:parameter)是使用通用变量来建立函数和变量之间关系(当这种关系很难用方程来阐述时)的一个数量。

准确率技术

分类模型的正确预测所占的比例。在多类别分类中,准确率的定义为:正确的预测数/样本总数。 在二元分类中,准确率的定义为:(真正例数+真负例数)/样本总数

特征构建技术

特征构造(也称为构造感应或属性发现)是一种数据增强形式,可将派生特征添加到数据中。 特征构造可以使机器学习系统在各种学习任务中构建更准确的模型。

图网技术

ImageNet 是一个计算机视觉系统识别项目, 是目前世界上图像识别最大的数据库。

图网络技术

2018年6月,由 DeepMind、谷歌大脑、MIT 和爱丁堡大学等公司和机构的 27 位科学家共同提交了论文《Relational inductive biases, deep learning, and graph networks》,该研究提出了一个基于关系归纳偏置的 AI 概念:图网络(Graph Networks)。研究人员称,该方法推广并扩展了各种神经网络方法,并为操作结构化知识和生成结构化行为提供了新的思路。

节点分类技术

节点分类任务是算法必须通过查看其邻居的标签来确定样本的标记(表示为节点)的任务。

推荐文章
暂无评论
暂无评论~