新智元推荐
编辑：keyu
【新智元导读】本文主要介绍针对图分类的低回溯对齐空域图卷积网络，该算法可将任意大小的图转换为固定大小的低回溯对齐网格结构，并定义了一个与网格结构关联的新空域图卷积操作，已被人工智能领域的国际顶级期刊TPAMI收录。
BASGCN(Backtrackless Aligned-Spatial Graph Convolutional Networks）由国内知名大学中央财经大学信息学院白璐副教授带领团队共同研发，已被人工智能领域的国际顶级期刊《IEEE Transactions on Pattern Analysis and Machine Intelligence》(TPAMI，IEEE模式分析和机器智能汇）刊录用，并将于日后正式刊出。
BASGCN可以：
1、 减小信息损失和现有空域图卷积网络(Graph Convolutional Network, GCN)对信息的不精确表示问题
2、 填补了传统卷积神经网络(Convolutional Neural Network, CNN）和空域GCN的理论空白
3、在卷积过程中适应性区别特定节点的重要性
4、减小现有空域GCN中Weisfeiler-Lehman算法带来的tottering问题，提高了整个卷积运算过程的有效性。
在标准图数据集上的实验证明了BASGCN相对于图核方法核其他深度学习方法的优越性。
下文内容选编自论文原文：
关键词：图卷积网络，可传递顶点对齐，低回溯游走
基于图的表示是对涉及非欧几里得空间的复杂系统建模的重要方法，节点之间的关系是非欧空间的主要组成部分，化学分子结构、点云和社交网络都是典型的非欧结构。在分析图数据中，最基本的挑战之一，就是如何将图的结构数据转化为使用标准机器学习方法可以直接处理分类和聚类问题的数值表示。
本文的主要目标就是创建一个新的图卷积网络模型，使得模型可以学习到针对图分类任务的有效特征。通过将任意大小的图转换为固定大小的低回溯对齐网络结构，该模型可以填补传统CNN和空域GCN之间的理论空白，还显著地降低了现有空域GCN与经典Weisfeiler-Lehman算法相关的tottering问题。
相关研究
近几十年来，对于图结构的研究的方法可以被分为两个类别：1）图嵌入方法 和2）图核方法，然而，这两种方法都忽视了多重图的信息，并且无法提供将图特征表示到图分类任务的端到端学习学习框架，总而言之，原有的方法的缺点影响了将传统机器学习方法应用到图分类任务的有效性。
近几年，图卷积网络（GCN）的引入则很好地提供了一个可以提取高维图特征的有效方法，并主要分为两个类别：1）频域（spectral）方法 和2）空域（spatial）方法。然而，大多数频域方法并不能应用在具有不同数目节点和傅立叶基的图上使用，因此，只能局限于具有相同大小的图结构中，并通常使用在节点分类任务中。相对而言，空域方法则并没有固定图结构大小的限制，但是在处理现实世界图分类问题之前，需要经过将从图卷积层学到的多维特征转化为固定大小的表示，而简单将局部节点特征加总到全局特征的方法，则严重损失了图中丰富的拓扑结构，从而在图分类任务中表现不佳。
深度图卷积神经网络(DGCNN)和PatchySan图卷积神经网络（PSGCNN）的引入则很好的克服了这一缺点，并能够捕捉存在于局部节点中丰富的图结构特征，并具有相对更加优异的性能。然而，这些方法建立节点顺序是基于每个图结构单独排列的，因此，并不能精确地反应图之间的拓扑相关性信息。此外，由于排序靠后的节点可能被丢弃，这两个方法都带来了显著的信息损失。最后，绝大多数现有的空域GCN模型都和经典Weisfeiler-Lehman（WL）方法相关，因此，类似的，这些GCN模型都可能会存在与WL算法相关的tottering问题。
存在的tottering问题：换句话来说，就是将信息从起始节点传播至第二个节点之后，这些GCN方法有可能立刻又将这些信息传播回起始节点了，而冗余特征信息就此产生。
本文贡献
本篇文章的目的就是，通过提出面向图分类问题的低回溯对齐空域图卷积网络（Backtrackless Aligned-Spatial Graph Convolutional Network, BASGCN) ，来处理前人方法中存在的问题。
总的来说，本文的贡献主要有以下几点：
- 引入了一个新的可传递顶点对齐方法，此方法可以将任意大小的图映射到固定大小的低回溯对齐网格结构上。
- 针对图分类任务，提出了一种新的低回溯基于空域的图卷积模型——BASGCN。
- 在图分类任务上使用BASGCN进行了实验，对此模型的性能进行了评估。
构造针对任意图的对齐低回溯网格结构
A. 确定可传递矩阵对齐信息
本文引入了一种新的图匹配方法，来实现对图节点的可传递对齐：
1）首先，研究者指定了在图集
中的一种原型表征族，这种表征方法封装了一种所有顶点向量表示中的主要特征。假设G中有n个顶点，其中相关的K维向量表示为
。
2）接着，本文使用k-means方法，通过最小化对象函数：
去定位
的质心M，其中
代表M个簇，
是属于第j个簇的节点平均表征。
3）假设
是图的样本集，
是
的一个样本，对于
和每个对应于K维向量表示
的
，通过定位K维原型表征为
，本文将图集
中的图初始化。
4）为了建立不同图结构间的可传递节点对齐信息，研究者基于ICML 2015中 《An aligned subtree kernel for weighted graphs》介绍的图节点对齐方法，提出了可传递的结点对齐操作方法。
具体来说，就是根据两个点集之间的欧几里得距离，通过计算K级近似矩阵(Affinity Matrix)来将每个图
的节点向量表示对齐到原型表征族
中：
其中
是大小为
的矩阵，每个
代表
和
之间的距离。换句话说，如果第i行中
是最小的，我们可以说v节点的向量表示
和第j个原型表征
对齐。
5）使用K级协同矩阵
，我们可以记录下一致信息：
对于每对图
和
，如果他们的节点
和
都对齐于同一个原型表征
，那么我们可以说
和
也对齐了。
这样一来，通过将他们的顶点和共有原型表征对齐，我们就可以确定图集
中的匹配的节点具有一致的可传递对齐信息。
B. 对齐图的网格结构
利用可传递一致对齐信息，我们可以将任意大小的图映射到固定大小的低回溯网格结构中，换句话说。也就是对齐节点王哥结构和关联低回溯对齐节点邻接矩阵。
1）假设
是图集
中的一个例子，其中，
代表具有自环的节点邻接矩阵（
，其中A是无自环的原始邻接矩阵，I是单位矩阵）。
我们令
为
的n个节点在c个维度上的特征向量，并使其的行跟从
中的节点顺序。如果
是属性图，那么
就是节点标签的one-hot编码矩阵。对于无属性图，本文将节点度作为节点标签。
2）对于每个图
，我们利用之前提出的可传递节点匹配方法，来计算K级节点一致矩阵记录K维节点向量表示的一致信息
和
中的K维原型表征。
3）接下来，本文计算出图
的K级对齐节点特征矩阵：
其中，
，
中的每一行代表一个一致对齐矩阵的特征。
同时，我们还需要计算出
的K级关联对齐节点邻接矩阵：
其中，
。
因为
和
是从原始
和
计算而来，通过将每个节点的原始特征和邻接信息映射到新的对齐节点上，
和
能包含到
的原始特征和结构信息。
4）为了重构固定大小的对齐网格结构，我们需要去对节点进行排序，来决定它们的空域顺序。因为每个图的节点都和同个原型表征对齐，我们可以通过重新排序原型表征来对节点排序。
i. 本文构造了一个捕捉在
中K维原型表征之间成对相似度的原型图
，其中，该图的每个节点代表
，第j和k个节点之间每条边代表
和
之间的相似性，相似性计算公式为：
每个原型表征
的度为
。
ii. 接着，本文根据它们的度来对
中K维原型表征进行排序，并根据其对
和
进行重排。
5）下一步，本文使用了基于深度的表示方法来表示节点向量，来计算所需要的K级节点一致矩阵
。每个节点的基于深度的表示由衡量从该节点的k层扩展子图族的熵来决定，其中参数k可以从1变化到K。
我们可以得知像这样的K维基于深度的表示可以包含丰富的从每个节点到达到全局图结构所体现的熵信息。整个过程如下图所示：
当我们将K从1变换到L的时候，基于ECML2019的《Learning aligned-spatial graph convolutional networks for graph classification》一文，本文可以计算出对于每个图
最终的对齐节点网格结构：
关联对齐网格节点邻接矩阵为：
6）现在我们得到的
代表的是一个无向图。然而，直接将此矩阵和现有的空域图卷积操作会导致tottering问题，从而进一步导致冗余信息问题。为了解决这一问题，本文提出了将
转化为低回溯邻接矩阵
的方法，
可以代表一个有向图。
具体来说，我们先将
初始化为
，然后计算第i个对齐网格节点为
，接着，防伪第i个节点的经典稳态随机游走概率可以计算为：
接着，通过将
中的每个双向边替换为和经典随机游走概率相关的有向边，我们可以计算出该图的低回溯对齐网格节点邻接矩阵
：
因为在空域图卷积操作中，节点特征信息无法沿着一条有向边直接立即返回起始节点，
提供了一个限制tottering问题的自然低回溯结构。
为了避免自循环问题，本文在上式处理前增添了移除自循环
的操作。
低回溯对齐空域图卷积网络模型
A. 低回溯空域图卷积操作
在这一部分，通过在低回溯对齐网格节点邻接矩阵上相邻的可传递对齐网格节点之间传播特征的方式，本文提出了一个进一步提取图的多维特征的低回溯空域图卷积操作。
具体来说，就是给定一个样本图
，其对齐节点网格结构为
，关联低回溯对齐网格节点邻接矩阵为
，那么提出的包含in-spatial卷积操作和out-spatial卷积操作的低回溯空域图卷积操作族为：
其中，
代表element-wise哈达玛积，
和
相等，是入邻接矩阵（其中的第i行第j列为从第j个节点到第i个节点的有向边，并且我们将第j个节点称为第i个节点的入邻接节点），
则和
相等，是出邻接矩阵（比如，对于第i行第j列的
元素为从第i个节点到第j个节点的有向边，并且我们将第j个节点称为第i个节点的出邻接节点）。
是
的入度矩阵，
是
的出度矩阵。
上面的in-spatial 操作代表着每个节点和其入邻接节点之间特征信息的传播，而out-spatial操作代表着每个节点和其出邻接节点之间特征信息的传播。
一个in-spatial的例子如下图所示：
具体来说，卷积操作主要分为四步：
第一步：计算
：
第二步：计算
，其中
，此步骤可以在每个对齐节点和其入邻接对齐节点之间传播带权特征信息。
其中，第i行
代表着
，可以被视作第i个对齐节点的聚合特征向量（将原始带权特征向量和和其有有向边的第j个对齐节点的带权特征向量加总）
因为在第一步中每个节点i都被赋予了不同的权重向量
，因此，聚合操作和在标准网格结构上进行标准固定大小卷积操作的过程是类似的。
这表明了提出的卷积操作中的可训练的参数
直接影响了节点特征的聚合操作，换句话说，它可以可适应地将具体入邻接节点的重要性区别开来。
第三步：通过依次将
的第i行和
相乘，
可以得到标准化。此操作可以保证在卷积操作之后，得到一个固定的特征规模。
第四步：这是最后一步，本文使用了Relu激活函数，并将得到的结果输出。这里需要注意的是，因为下式定义的in-spatial图卷积操作只提取了对齐网格节点的新特征，并且并没有改变对齐节点的顺序，所以，输出的结果依然是和
保持相同的节点顺序：
out-spatial和in-spatial操作相似，本文在此就不再赘述。
以上的四个步骤和操作的理论解释表明了in-spatial和out-spatial图卷积操作可以显著地降低在绝大多数现有基于空域GCN模型的tottering问题的带来的不利影响。
这是因为本文提出的卷积操作是定义在低回溯对齐网格节点邻接矩阵上的，而这和有向图对应。
因此，in-spatial和out-spatial图卷积操作都是低回溯空域图卷积操作（Backtrackless Spatial Graph Convolution Operation)。
BASGCN模型的框架结构
本文提出的BASGCN的框架如下所示：
整个框架主要由三个顺序环节组成：
1）低回溯网格结构构造/输入层
2）低回溯空域图卷积层
3）传统一维CNN层
实验
在实验环节中，研究人员对提出的BASGCN模型的性能进行了评估，并将其与最前沿的图核和深度学习方法在图分类任务上进行了对比。
图分类任务是在八个从生物信息和社交网络中提取出的标准图数据集上进行的。数据集的细节如下所示：
经过多次重复实验，BASGCN和图核方法在图分类任务中的平均分类精度和标准差如下所示：
经过多次重复实验，BASGCN和深度学习方法在图分类任务中的平均分类精度和标准差如下所示：
因为SAGPool，FigenPool和DEMO-Net模型的原文作者并没有其在社交网络数据集上评估，并且在原文中，ECC和DiffPool模型仅仅在一个社交网络数据集上进行了评估，其中精确度显著低于本文提出的方法，为了公平比较，研究人员仅仅将这些模型在生物信息数据集上进行了精度的评估：
从实验结果中可以看出，在图分类中，本文提出的BASGCN显著地超越了其他的图核和深度学习方法。
此外，本文将BASGCN的计算效率和图核方法中最著名的方法之一——WLSK核作了比较，并比较了两者在RED-B基准数据集（在本次实验中具有平均最大图尺寸的数据集）上的运行时间做了比较。
结果显示，BASGCN和WLSK核分别具有3794s和3007s的运行时间，虽然BASGCN的时间稍微长了一些，但是，和WLSK相比，其计算效率依然很可观。此外，BASGCN可以在分类准确度上显著超越WLSK核。
总之，和高效的WLSK核方法相比，BASGCN具有更好的分类精度和计算效率上的权衡。
最后，研究人员探究了在COLLAB，PTC和RED-B数据集上，参数M的选择对BASGCN的分类表现的影响：
可以看出，随着M的增加，提出的模型的精度逐渐提高，并且趋向稳定。
看来近年流行的GCN方法中又有新的成员强势加入了！如果大家还想了解更多，可以到TPAMI中的原文探究更多细节哦。
