华为联合LSE提出KONG：有序邻域图的核

图是对结构化数据的独特表示，从在线社交网络的社区检测到蛋白质结构预测，图在机器学习及其相关领域有着极大的应用。所以，基于图结构实现学习任务能够吸引研究社区的关注也就不令人惊讶了。图核函数（Graph kernel）是图分类的标准工具。给定带有节点和边属性的大型图合集，我们感兴趣的是学习一种能够最好地捕捉任意两张图之间相似性的核函数. 这种图核函数可用于支持向量机这样的标准核方法进行图分类。

图相似性是一个定义广泛的概念，也因此有许多带有不同特性的不同图核函数被提出。先前工作主要是研究不同图类别的图核函数，也就是没有节点或者边缘属性的简单不加权图、带有离散节点和边标签的图、带有真值向量和部分标签这样更复杂属性的图。对图的展开而言，邻近节点的排序（order）可作为图类别的参考。具体样本包括描述用户浏览模式的图，也包含社交网络、产品购买与浏览、推荐系统中的点击率、合著关系网络等这样的进化网络。

边中的排序（order）对原始数据中的结构非常有指示作用。据我们所知，现有的图 核函数 并不涉及这一方面。我们提出了一种边与邻近节点遵循一定排序的图核函数框架。我们提出的这一算法框架 KONG，它表示面向有序邻域图的核函数（Kernels for Ordered-Neighborhood Graphs），这一框架还可以扩展到大规模图和图集合的高效算法。

其核心思路是：（a) 使用一种树遍历方法通过特征串（string）表示每个节点近邻。（b）基于每个节点特征串的 k-gram 频率向量，在没有显性存储特征串的情况下对图 feature map 进行高效计算。后者使得使用 sketching 技术逼近各种核函数的显性 feature map 成为了可能。

图 1:一个有序近邻图的示例：近邻排序是按照字母来排的

本文贡献如下：

据我们所知，这是首个聚焦且正式定义有序节点近邻图核函数的研究。它在串核函数（string kernel）上进行拓展，我们展示且正式分析了一系列用于不同问题的图核函数。KONG 框架展示了与两个 参数 有关的算法：图 N 的总数量和边 M 的总数量。我们提出的方法能够计算每个图的显性 feature map，使得线性 SVM 能用于图分类，从而避免 O(N2 ) 大小核矩阵的计算。利用前沿的 sketching 技术，可以实时计算带有 m 个边的图的显性 feature map 近似值。我们也扩展了子线性空间 o(M)，并介绍了如何使用从图流中学习。

相比使用多项式和余弦核函数计算的子图标签分布，我们的方法可为未排序领域的一般标记图带来全新图核。我们认为，该方法可看作一种对 Weisfeiler-Lehman 节点标注核函数有效的平滑算法。在真实图上的实验评估显示，我们提出的核方法可以与顶尖的方法相媲美，使用密集的 feature map 在一些基准数据集上能够达到更好的准确率。

现在的方法可看作一种学习紧致图表示的有效算法。这种方法主要聚焦于学习卷积图核函数的显性 feature map。然而，我们的算法学习到的向量嵌入可以被逻辑回归、决策树和神经网络以及无监督方法使用。

论文：KONG: Kernels for ordered-neighborhood graphs

论文地址：https://arxiv.org/abs/1805.10014

摘要：本文提出了一种带有节点和边标签图的面向有序近邻图的全新图核函数。有序邻域即相邻节点有序排列。有序近邻图是展开图的自然数据表示，在展开图中，边随着时间的推移而产生，进而导致了顺序。结合卷积子图核函数和串核函数（string kernel），我们设计了一种新的可扩展算法，以使用 sketching 技术生成显式图 feature map。我们获得了所提出方法的近似准确率与计算复杂度的精准界限，证明了它们在真实数据集上的可用性。我们的实验还证明，近邻排序会产生更多的信息特征。对于一般图的特定案例（即非有序近邻图）来说，新的图核函数会为比较图之间的标签分布产生高效又简单的算法。

算法

该提出的算法基于以下几个关键点：a）使用树遍历方法用串 Sv 表示每个节点 V 的近邻，b）使用 sketching 以不需要存储串 Sv 的方式逼近其 k-gram 频率向量。

实验

在此章节中，我们展示了该算法的分类准确率与计算速度，并与其他基于核的算法在一组真实图数据集上做了对比。首先，我们展示了对没有层级节点近邻的一般图的评估，这证明了相比于当前基于核函数的方法，我们的算法取得了可媲美的效果，甚至在一些情况下有更好的分类准确率。而后，我们展示了对带有层级的近邻图的评估，证明了计入近邻层级数能带来更高的分类准确率，以及更好的可延展性。

表 1:一般标记图的分类准确率（1-gram 示例）

表 2:带有层级近邻图的不同方法准确率与速度的对比，我们使用 K-k 注释表示使用 k-grams 的 KONG。时间列展示了明确的图计算时间和 SVM 分类时间。