一个安静的胖子作者ECML-PKDD 2019 来源萝卜兔编辑整理

论文分享 | Learning Aligned-Spatial GCNs for Graph Classification

目前大部分GCN方法可以被归为两类:Spectral(基于频域)卷积和 Spatial(基于空域)卷积。前者主要基于 Spectral Graph Theory 将图信号变换到谱域与滤波器系数进行相乘再做逆变换[1][2],这种方法处理的图结构常常是固定大小的(节点个数固定)并且主要解决的是节点分类问题。然而现实中图数据的大小往往不固定,例如生物信息数据中的蛋白质结构、社交网络中的用户关系等,基于 Spatial 策略的图卷积操作可以直接定义在邻居节点上,通过采样或排序的方式将邻居节点聚合从而学习图的拓扑特征。尽管如此,Spatial 策略的 GCN 在将卷积层学习到的不同大小图的多尺度特征输入给分类器之前仍要将其转换为固定大小表示,常见的方法就是将图的各节点特征进行加和池化得到图的全局特征,这会造成图局部特征信息的损失,因此这类 Spatial 策略的 GCN 方法在图分类上具有相对较差的性能。

这篇论文提出了一种空间对齐(Aligned-Spatial)图卷积网络 ASGCN,用于解决图分类问题,将任意大小的图通过传递的对齐方法(Transitive Alignment)转化为固定大小的图结构,并定义了一个与之相关的图卷积运算方式。ASGCN 不仅减少了局部信息的损失,还可以自适应指定不同邻居节点在信息聚合中的重要性,因此在很多图分类数据集上都展现出了很好的分类性能。

任意大小图的传递对齐

论文提出一种图匹配方法用于节点的传递对齐,算法框架分3步,如图1所示:

图1

假设数据集所有图共包含n个节点,算法框架:

第1步:使用一种Node Embedding方法将所有节点嵌入到 K 维空间进行向量化表示,所有向量可用集合表示;

第2步:使用一种聚类方法从集合中计算出M个聚类中心节点(M为超参数)构成一个模板图;

第3步,将所有图结构与M个节点的模板图进行传递对齐,对齐后任意大小的图都被转化为M个节点的固定大小。

具体而言,论文中第1步使用的 Node Embedding 方法是作者于2014年提出的基于深度的特征表示算法[3] Depth-Based(DB) Representation,该方法是一种无监督的Node Embedding方法,并已被证实可以有效地表征节点从局部到全局的拓扑信息,第p个图结构第i个节点的K层深度特征向量记作 。

第2步论文中使用的是常见的Kmeans算法,则关于全部节点的 M 个聚类中心 可通过最小化以下目标函数得到:

论文第3步首先计算原始图结构与模板图结构的节点集合计算距离矩阵,设第p个原始图结构与模板图结构的K维节点向量距离矩阵为,则原始图的第i个节点与模板图的第j个节点距离可由以下公式计算:

如果距离矩阵中的第 i 行、第 j 列元素在整个 i 行中最小,说明原始图的第i个节点与模板图的第 j 个节点最相似,论文将这种关系称为原始图的第i个节点与模板图的第 j 个节点是对齐的。基于上述规则,可以从距离矩阵中得到原始图与模板图的对齐矩阵:

其中每行仅有一个元素为1其余元素为0,表示原始图的每个节点都对应一个模板图中的节点,反过来与模板图中特定节点对应的原始图节点可能有多个。

值得注意的是,当两个原始图结构中的节点都与相同的模板图结构中的节点对齐时,这两个原始图结构中的节点也是相互对齐的,因此这种对齐关系是传递的。

得到对齐矩阵后,假设第p个图结构的带self-loop的邻接矩阵为 ,节点的属性特征矩阵为 ,则将原始图结构通过对齐转化为M节点固定大小的图结构的公式如下:

上述传递对齐算法流程与作者在2016年提出的针对模式空间的节点匹配算法[4]类似。(篇幅限制本文介绍传递对齐算法略有缩减,具体细节请参考论文原文)

新的Spatial图卷积运算操作

经过传递对齐后的所有图结构均有M个节点,且任意对齐后的图结构的邻接矩阵所对应的节点都与模板图节点共享相同排序,即无论原始图结构节点在邻接矩阵中的排列顺序是否改变,对齐后图结构的邻接矩阵都保持了相同的节点排列顺序,这种节点的置换不变性(Permutation Invariance)使得后面设计的新图卷积运算成为可能。对于第h个滤波器,新的Spatial图卷积运算公式如下:

其中Zh 是M个维度为 c 的节点信号 在通过第h个滤波器后得到的M个维度为1的节点信号,是元素位乘积(Element-wise Hadamard Product),是M个维度为c的可训练权重矩阵。假设输入的图结构有5个节点,单个节点信号维度为3,则针对节点v2,节点特征信号在通过单一滤波器进行上述图卷积操作时的具体计算示意图如下:

论文提出的图卷积运算与大部分现有的图卷积运算最大的区别,即图中任意节点都被分配了相应不同的可训练权重,使得训练过程中网络可以自适应地区分指定节点之间的重要性。

空间对齐的图神经网络

基于上述提出的传递对齐算法框架以及与之对应的新型Spatial图卷积运算,论文给出了一个空间对齐的图神经网络结构,结构如下图所示:

首先网络的第1部分进行的是无监督学习,通过传递对齐将所有大小不一的原始图结构转化为相同大小的图结构;网络的第2部分是将转化后的图结构输入给新型Spatial图卷积层;网络的第3部分首先将第2部分各图卷积层的输出进行拼接组合,再将拼接后的节点信号输入给传统的1D卷积层、池化层,最后经过全连接层输出分类结果。

实验

论文选择了在图分类问题中常见的标准数据集[5],其中包含生物信息图结构以及社交网络图结构,具体数据集信息如下:

对比的方法包括传统的Graph Kernel方法以及基于深度学习的方法。

与Graph Kernel的实验对比效果如下:

深度学习的实验对比效果如下:

实验证明提出的ASGCN方法在大部分数据集中都显著优越于其他方法,无论是Graph Kernel还是深度学习的方法。值得注意的是,在对比实验中,论文提出的ASGCN方法在处理所有不同数据集时,都使用了相同的网络结构(卷积层数、输出维度)及模板图大小设置(M取值)。对于不同数据集,实验变化的超参数只有学习率(learning rate)以及迭代次数(epoch),因此论文认为如果针对不同数据集,网络结构以及模板图大小也做出相应的调整优化,会得到比当前更好的实验效果。

总结

论文提出了一种新的基于空间的GCN模型ASGCN,将任意大小的图转换为固定大小的对齐结构,并在对齐图结构上执行新的Spatial图卷积操作。与大多数现有的基于Spatial的GCN不同,ASGCN可以在图卷积操作的过程中自适应地区分指定节点之间的重要性,这也解释了ASGCN相比大部分现有GCN在实验上表现更好的原因。

相关链接

论文作者主页:

https://www.researchgate.net/profile/Lu_Bai3

Graph Kernel:

https://www.zhihu.com/question/57269332/answer/157375170

参考文献

[1] Bruna, J., Zaremba, W., Szlam, A., & LeCun, Y. (2013). Spectral networks and locally connected networks on graphs. arXiv preprint arXiv:1312.6203.

[2] Henaff, M., Bruna, J., & LeCun, Y. (2015). Deep convolutional networks on graph-structured data. arXiv preprint arXiv:1506.05163.

[3] Bai, L., & Hancock, E. R. (2014). Depth-based complexity traces of graphs. Pattern Recognition, 47(3), 1172-1186.

[4] Bai, L., Rossi, L., Zhang, Z., & Hancock, E. (2015, June). An aligned subtree kernel for weighted graphs. In International Conference on Machine Learning (pp. 30-39).

[5] Kersting, K., Kriege, N., Morris, C., Mutzel, P., & Neumann M. (2016). Benchmark Data Sets for Graph Kernels. (2016). http://graphkernels.cs.tu-dortmund.de

极验
极验

极验是全球顶尖的交互安全技术服务商,于2012年在武汉成立。全球首创 “行为式验证技术” ,利用生物特征与人工智能技术解决交互安全问题,为企业抵御恶意攻击防止资产损失提供一站式解决方案。

理论自然语言处理计算机视觉监督学习智能科研聚类深度学习分类问题图卷积网络
1
相关数据
深度学习技术

深度学习(deep learning)是机器学习的分支,是一种试图使用包含复杂结构或由多重非线性变换构成的多个处理层对数据进行高层抽象的算法。 深度学习是机器学习中一种基于对数据进行表征学习的算法,至今已有数种深度学习框架,如卷积神经网络和深度置信网络和递归神经网络等已被应用在计算机视觉、语音识别、自然语言处理、音频识别与生物信息学等领域并获取了极好的效果。

池化技术

池化(Pooling)是卷积神经网络中的一个重要的概念,它实际上是一种形式的降采样。有多种不同形式的非线性池化函数,而其中“最大池化(Max pooling)”是最为常见的。它是将输入的图像划分为若干个矩形区域,对每个子区域输出最大值。直觉上,这种机制能够有效的原因在于,在发现一个特征之后,它的精确位置远不及它和其他特征的相对位置的关系重要。池化层会不断地减小数据的空间大小,因此参数的数量和计算量也会下降,这在一定程度上也控制了过拟合。通常来说,CNN的卷积层之间都会周期性地插入池化层。

权重技术

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

分类数据技术

一种特征,拥有一组离散的可能值。以某个名为 house style 的分类特征为例,该特征拥有一组离散的可能值(共三个),即 Tudor, ranch, colonial。通过将 house style 表示成分类数据,相应模型可以学习 Tudor、ranch 和 colonial 分别对房价的影响。 有时,离散集中的值是互斥的,只能将其中一个值应用于指定样本。例如,car maker 分类特征可能只允许一个样本有一个值 (Toyota)。在其他情况下,则可以应用多个值。一辆车可能会被喷涂多种不同的颜色,因此,car color 分类特征可能会允许单个样本具有多个值(例如 red 和 white)。

学习率技术

在使用不同优化器(例如随机梯度下降,Adam)神经网络相关训练中,学习速率作为一个超参数控制了权重更新的幅度,以及训练的速度和精度。学习速率太大容易导致目标(代价)函数波动较大从而难以找到最优,而弱学习速率设置太小,则会导致收敛过慢耗时太长

超参数技术

在机器学习中,超参数是在学习过程开始之前设置其值的参数。 相反,其他参数的值是通过训练得出的。 不同的模型训练算法需要不同的超参数,一些简单的算法(如普通最小二乘回归)不需要。 给定这些超参数,训练算法从数据中学习参数。相同种类的机器学习模型可能需要不同的超参数来适应不同的数据模式,并且必须对其进行调整以便模型能够最优地解决机器学习问题。 在实际应用中一般需要对超参数进行优化,以找到一个超参数元组(tuple),由这些超参数元组形成一个最优化模型,该模型可以将在给定的独立数据上预定义的损失函数最小化。

目标函数技术

目标函数f(x)就是用设计变量来表示的所追求的目标形式,所以目标函数就是设计变量的函数,是一个标量。从工程意义讲,目标函数是系统的性能标准,比如,一个结构的最轻重量、最低造价、最合理形式;一件产品的最短生产时间、最小能量消耗;一个实验的最佳配方等等,建立目标函数的过程就是寻找设计变量与目标的关系的过程,目标函数和设计变量的关系可用曲线、曲面或超曲面表示。

分类问题技术

分类问题是数据挖掘处理的一个重要组成部分,在机器学习领域,分类问题通常被认为属于监督式学习(supervised learning),也就是说,分类问题的目标是根据已知样本的某些特征,判断一个新的样本属于哪种已知的样本类。根据类别的数量还可以进一步将分类问题划分为二元分类(binary classification)和多元分类(multiclass classification)。

图神经网络技术

图网络即可以在社交网络或其它基于图形数据上运行的一般深度学习架构,它是一种基于图结构的广义神经网络。图网络一般是将底层图形作为计算图,并通过在整张图上传递、转换和聚合节点特征信息,从而学习神经网络基元以生成单节点嵌入向量。生成的节点嵌入向量可作为任何可微预测层的输入,并用于节点分类或预测节点之间的连接,完整的模型可以通过端到端的方式训练。

聚类技术

将物理或抽象对象的集合分成由类似的对象组成的多个类的过程被称为聚类。由聚类所生成的簇是一组数据对象的集合,这些对象与同一个簇中的对象彼此相似,与其他簇中的对象相异。“物以类聚,人以群分”,在自然科学和社会科学中,存在着大量的分类问题。聚类分析又称群分析,它是研究(样品或指标)分类问题的一种统计分析方法。聚类分析起源于分类学,但是聚类不等于分类。聚类与分类的不同在于,聚类所要求划分的类是未知的。聚类分析内容非常丰富,有系统聚类法、有序样品聚类法、动态聚类法、模糊聚类法、图论聚类法、聚类预报法等。

图卷积网络技术

假设有一张图,要做分类,传统方法需要手动提取一些特征,比如纹理啊,颜色啊,或者一些更高级的特征。然后再把这些特征放到像随机森林等分类器,给到一个输出标签,告诉它是哪个类别。而深度学习是输入一张图,经过神经网络,直接输出一个标签。特征提取和分类一步到位,避免了手工提取特征或者人工规则,从原始数据中自动化地去提取特征,是一种端到端(end-to-end)的学习。相较于传统的方法,深度学习能够学习到更高效的特征与模式。

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