2018/12/09 12:22

华为联合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 分类时间。

理论华为诺亚方舟核函数计算图NeurIPSNIPS

相关数据

逻辑回归技术

逻辑回归（英语：Logistic regression 或logit regression），即逻辑模型（英语：Logit model，也译作“评定模型”、“分类评定模型”）是离散选择法模型之一，属于多重变量分析范畴，是社会学、生物统计学、临床、数量心理学、计量经济学、市场营销等统计实证分析的常用方法。

来源：Trevor Hastie, Robert Tibshirani and Jerome Friedman (2nd ed., 2009). The Elements of Statistical Learning: Data Mining, Inference, and Prediction.维基百科

机器学习技术

机器学习是人工智能的一个分支，是一门多领域交叉学科，涉及概率论、统计学、逼近论、凸分析、计算复杂性理论等多门学科。机器学习理论主要是设计和分析一些让计算机可以自动“学习”的算法。因为学习算法中涉及了大量的统计学理论，机器学习与推断统计学联系尤为密切，也被称为统计学习理论。算法设计方面，机器学习理论关注可以实现的，行之有效的学习算法。

来源：Mitchell, T. (1997). Machine Learning. McGraw Hill.

核函数技术

核函数包括线性核函数、多项式核函数、高斯核函数等，其中高斯核函数最常用，可以将数据映射到无穷维，也叫做径向基函数（Radial Basis Function 简称 RBF），是某种沿径向对称的标量函数。最常应用于SVM支持向量机中

来源：百度百科

基准技术

一种简单的模型或启发法，用作比较模型效果时的参考点。基准有助于模型开发者针对特定问题量化最低预期效果。

来源：Google ML Glossary

参数技术

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

来源：维基百科

推荐系统技术

推荐系统（RS）主要是指应用协同智能（collaborative intelligence）做推荐的技术。推荐系统的两大主流类型是基于内容的推荐系统和协同过滤（Collaborative Filtering）。另外还有基于知识的推荐系统（包括基于本体和基于案例的推荐系统）是一类特殊的推荐系统，这类系统更加注重知识表征和推理。

来源：机器之心

神经网络技术

（人工）神经网络是一种起源于 20 世纪 50 年代的监督式机器学习模型，那时候研究者构想了「感知器（perceptron）」的想法。这一领域的研究者通常被称为「联结主义者（Connectionist）」，因为这种模型模拟了人脑的功能。神经网络模型通常是通过反向传播算法应用梯度下降训练的。目前神经网络有两大主要类型，它们都是前馈神经网络：卷积神经网络（CNN）和循环神经网络（RNN），其中 RNN 又包含长短期记忆（LSTM）、门控循环单元（GRU）等等。深度学习是一种主要应用于神经网络帮助其取得更好结果的技术。尽管神经网络主要用于监督学习，但也有一些为无监督学习设计的变体，比如自动编码器和生成对抗网络（GAN）。

来源：机器之心

准确率技术

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

来源：Google ML Glossary

逻辑技术

人工智能领域用逻辑来理解智能推理问题；它可以提供用于分析编程语言的技术，也可用作分析、表征知识或编程的工具。目前人们常用的逻辑分支有命题逻辑（Propositional Logic ）以及一阶逻辑（FOL）等谓词逻辑。

来源：机器之心

支持向量机技术

在机器学习中，支持向量机是在分类与回归分析中分析数据的监督式学习模型与相关的学习算法。给定一组训练实例，每个训练实例被标记为属于两个类别中的一个或另一个，SVM训练算法创建一个将新的实例分配给两个类别之一的模型，使其成为非概率二元线性分类器。SVM模型是将实例表示为空间中的点，这样映射就使得单独类别的实例被尽可能宽的明显的间隔分开。然后，将新的实例映射到同一空间，并基于它们落在间隔的哪一侧来预测所属类别。

来源：Wikipedia