图结构的相似度度量与分类

近日,来自法国LIX实验室的Michalis教授在清华大学作了题为 “Graph Similarity and Classification” 的报告。

图分类,即根据图的拓扑结构预测图的标签,是图挖掘中的一个重要问题。Michalis 教授首先介绍了几个典型的图分类应用,包括文本分类,蛋白质功能预测,化合物分类,异常检测,恶意软件检测等。

分类问题的一种解决方法是将未知标签的图和已知标签的图进行比较,通过 k 近邻的方法对图进行分类,但比较两个图的相似度是一个非常复杂的问题。

Graph Kernel 方法将机器学习中的核方法(Kernel Methods)拓展到了图结构数据上,是一类计算图与图之间相似度的方法。该方法可以高效地计算图之间的相似度,并可以方便地使用SVM等分类器进行图分类。

Graph Kernel 的思路是将图映射到某个 Hilbert 空间,两个图之间的相似度可以通过 Hilbert 空间中的点积运算得到。常见的 Graph Kernel 定义为图中子结构的分布,子结构包括随机游走,最短路径,环,子树,Graphlets 等。现实中图的拓扑结构非常复杂,简单的 Graph Kernel 并不能很好地解决图分类问题

Shervashidze 等人提出了 Weifsfeiler-Lehman (WL) Framework 提高 Graph Kernel 的效果。WL方法借鉴了标签传播的思想,需要进行h次迭代过程,每次迭代会构建一个新图,图的节点标签根据上一次迭代的邻居节点标签更新,并计算更新后的Graph Kernel。WL方法中,图的相似度由 h 次迭代过程中的 Graph Kernel 综合得到。

介绍完 Graph Kernel 的相关背景后,Michalis 介绍了他们在 Graph Kernel 上的最新研究成果。"Matching Node Embeddings for Graph Similarity"是他们在 AAAI'17 发表的工作,提出了基于点向量(Node embedding)的图相似度计算方法。

常见的 Graph Kernel 主要利用了局部的子结构信息,但缺少全局信息。该工作利用点向量计算图之间的相似度,这些点向量包含图的全局信息,而每个图表示为这些点向量的集合,然后利用 Earth Mover's Distance 和 Pyramid Match Kernel 计算图相似度。

“Degeneracy Framework for Graph Comparison” 是 Michalis 团队发表在 IJCAI'18 的工作,并且获得了 distinguished paper award. 该工作通过 Graph Degeneracy 过程得到每个图的一系列 k-core 子图,图的相似度由不同阶的 k-core 子图的 Graph Kernel 综合得到。该方法在多个 Benchmark 数据集上取得了 State of the Art (SoTA) 的效果。

"Enhancing Graph Kernels via Successive Embeddings"发表在 CIKM'18,该工作介绍了 Successive Embedding 的思想,首先将图映射到某个 Hilbert 空间 H1,接着定义一个作用在 H1 上的核函数将图在 H1 上的向量映射到新的 Hilbert 空间 H2 上,重复该过程若干次可以得到更复杂的 Graph Kernel。该方法在多个 Benchmark 数据集上都取得了不错的分类精度。

最后,Michalis 介绍了 EMNLP’17 上的工作"Shortest-path graph kernels for document similarity"。该工作将文本表示成词网络,将文本分类问题转化为图分类问题。该工作还提出了基于最短路径的 Graph Kernel (SPGK) 用于计算图的相似度,并在实验中达到甚至超过了基于CNN的文本分类算法。

Michalis 团队还开发了计算 Graph Kernel 的 Python 工具包供开发人员和科研人员使用,工具包网址为https://github.com/ysig/GraKeL.

AMiner学术头条
AMiner学术头条

AMiner平台由清华大学计算机系研发,拥有我国完全自主知识产权。系统2006年上线,吸引了全球220个国家/地区800多万独立IP访问,数据下载量230万次,年度访问量1000万,成为学术搜索和社会网络挖掘研究的重要数据和实验平台。

https://www.aminer.cn/
专栏二维码
理论文本分类图分类
2
相关数据
机器学习技术

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

核函数技术

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

文本分类技术

该技术可被用于理解、组织和分类结构化或非结构化文本文档。文本挖掘所使用的模型有词袋(BOW)模型、语言模型(ngram)和主题模型。隐马尔可夫模型通常用于词性标注(POS)。其涵盖的主要任务有句法分析、情绪分析和垃圾信息检测。

异常检测技术

在数据挖掘中,异常检测(英语:anomaly detection)对不符合预期模式或数据集中其他项目的项目、事件或观测值的识别。 通常异常项目会转变成银行欺诈、结构缺陷、医疗问题、文本错误等类型的问题。 异常也被称为离群值、新奇、噪声、偏差和例外。

映射技术

映射指的是具有某种特殊结构的函数,或泛指类函数思想的范畴论中的态射。 逻辑和图论中也有一些不太常规的用法。其数学定义为:两个非空集合A与B间存在着对应关系f,而且对于A中的每一个元素x,B中总有有唯一的一个元素y与它对应,就这种对应为从A到B的映射,记作f:A→B。其中,y称为元素x在映射f下的象,记作:y=f(x)。x称为y关于映射f的原象*。*集合A中所有元素的象的集合称为映射f的值域,记作f(A)。同样的,在机器学习中,映射就是输入与输出之间的对应关系。

分类问题技术

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

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