ICML  2022 | A Hierarchical Transitive-Aligned Graph Kernel for Un-attributed Graphs

“

文章信息

来源：Proceedings of the 39th International Conference on Machine Learning（ICML） 2022
标题：A Hierarchical Transitive-Aligned Graph Kernel for Un-attributed Graphs
作者：Lu Bai, Lixin Cui, Hancock Edwin
链接：https://proceedings.mlr.press/v162/bai22a.html

”

内容简介

基于图的表示是表示结构数据的强大工具，这些数据用组件之间的成对关系来描述。分析基于图的数据所面临的主要挑战是如何学习离散图结构的有效数值特征。实现这一点的常用方法是使用图内核，它可以在高维空间中表征图结构，从而更好地保留结构信息。

大多数现有-卷积核中出现的一个主要缺点是它们忽略了子结构之间的相对位置信息。具体来说，当识别出一对相似的子结构时，-卷积核通常倾向于添加一个单位值。但是，这些内核无法识别这些相似的子结构是否与整体图结构正确对齐，即它们不检查子结构的拓扑排列是否全局正确。以蛋白质匹配问题为例，可能有来自整体结构不同部分的相似子结构，尽管它们没有正确对齐，但-卷积核会将这些视为匹配子结构。此外，对于基于图的图像分析问题的一个实例，下图中有两个从数字图像中抽象出来的图，它们都包含来自不同视点的相同房屋对象。-卷积核将识别由红线组成的两个同构子图，从而为核贡献一个单位值，尽管它们没有根据图像背景在位置或结构上对齐，即由蓝线连接的顶点没有对齐。本文工作的目的是通过为非属性图开发新的分层传递对齐内核（HTAK）来解决现有图内核的上述缺点。所提出的内核其关键创新是通过一系列分层原型表示在图对之间传递对齐顶点。也就是说，给定来自三个不同样本图的三个顶点 、 和 ，如果  和  对齐，并且  和  对齐，则所提出的内核可以保证  和  也对齐。因此，所提出的核在理论上可以保证正定性。

具体来说，本文的主要贡献有如下三方面：

• 首先，本文提出了一个框架来计算一组  层次原型表示，它封装了一组图  上的矢量顶点表示的主要特征，通过分层执行 k-means 聚类方法来识别预先分配的数字实现。聚类簇心通过最后的  级原型表示作为  级原型表示，其中 0 级表示对应于所有图的原始矢量顶点表示。将  从 1 变为 （即 ）时，这反过来会生成一系列  层次原型表示。本文新的层次原型表示不仅反映了所有图的一般结构信息，而且还表示了不同层次上所有图的可靠顶点金字塔。
• 其次，根据-层次原型表示族的特点，本文提出了一种图匹配方法，该方法通过将每个图的顶点分层对齐到其不同的-层次原型表示中来实现。由此产生的HTAK核是通过计算对齐顶点对的数量来定义的。证明了该核不仅克服了现有-卷积核忽略同构子结构之间对应信息的缺点，而且保证了对应信息之间的传递性。
• 最后，通过transductive训练与所提 HTAK 内核相关的 C-SVM 分类器，本文实验证明了新核方法的有效性。该核在分类精度上优于现有的图核和标准图数据集上的图神经网络模型。

分层原型表示

本文提出了一个框架来计算一系列  层次原型表示，它封装了一组图  中所有矢量顶点表示的主要特征。计算层次原型表示的框架实例如下图所示。具体来说，令  表示  中所有图上  个顶点的  维向量表示。首先采用  作为 0 级原型表示  的集合，即:

其中所有的 0 表示参数  的当前值，，每个第  个元素  对应于 。

本文提出的内核定义

本文为非属性图提出了一种新颖的分层传递对齐内核（HTAK）。首先通过 H 层次原型表示族引入一种新的层次传递顶点匹配方法。此外本文基于新的顶点匹配方法开发了 HTAK 内核。

分层传递顶点匹配方法

本文开发了一种新的分层传递顶点匹配方法，通过将每个图的顶点分层对齐到上节中定义的 H 层次原型表示族中的每组 h 层次原型表示。对于一组 T 图 ，我们首先计算所有 T 图的 k 维向量顶点表示上的 H 层次原型表示族，如 。为了建立图顶点之间的对应信息，该研究将样本图  的向量顶点表示与每组 h 级原型表示 。对齐过程类似于用于模式空间中的点匹配的过程 (Bai et al., 2015a) 。具体来说是根据两组点之间的欧几里得距离计算一个 h 级关联矩阵：

类似地，对于每个其他样本图 ,还对齐它的 k 维向量表示。每个顶点  到每组 h 级原型表示 。

分层传递对齐内核

本文基于图之间的 H 层次传递顶点对应矩阵为图开发了一种新的层次传递对齐内核 (HTAK)。
HTAK内核定义：对于一组图  首先计算 H 层次原型表示族为

其中  表示 h 级原型表示的集合，并且 。

对于  中的一对图  和 ，通过将  和  的顶点与不同 h 级原型表示的集合对齐，本文计算 H 层次传递顶点对应矩阵族为

实验分析

本文在来自计算机视觉、生物信息学和社交网络的九个基准图数据集上评估提出的 HTAK 内核。这些数据集包括：BAR31、BSPHERE31、GEOD31、MUTAG、NCI1、CATH2、COLLAB、IMDB-B 和 IMDB-M。这里的 BAR31、BSPHERE31 和 GEOD31 数据集都是从 SHREC 3D Shape 数据库中抽象出来的，该数据库由 15 个类和每个类 20 个个体组成。具体来说，本文通过三个映射函数建立 BAR31、BSPHERE31 和 GEOD31 数据集，即 a) ERG 质心：距质心/重心的距离，b) ERG bsphere：到外接物体的球体中心距离，c) ERG 积分测地线：到所有其他点的测地线距离平均值。其他数据集都可以在网站 http://graphkernels.cs.tu-dortmund 上找到。这些数据集的更多细节如下表所示：对于每个数据集和每个内核，本文计算最佳 C-SVM 参数，将整个实验重复 10 次，并在下表中总结平均分类准确度（±标准误差）：

总结

本文为非属性图开发了一种新的内核——分层传递对齐内核（Hierarchical Transitive Aligned Kernel，HTAK）。与现有的大多数内核不同，该内核不仅克服了忽略图之间对应信息的缺点，而且保证了对应信息之间的传递性。实验表明，所提出的内核在图分类方面可以胜过最先进的图内核和深度学习方法。作者未来的工作是扩展所提出的用于顶点和边属性图的内核。此外，作者还将在更多真实世界的图结构数据上使用所提内核并研究其性能，例如金融网络、大脑网络等。