崔克楠作者上海交通大学博士生学校异构信息网络、推荐系统研究方向

KDD 18 & AAAI 19 | 异构信息网络表示学习论文解读

本文要介绍的两篇论文在 metric learning 和 translation embedding 的角度对异构信息网络中的节点进行学习,都受到了 knowledge graph 的模型如 TransE,TransR 的影响,所以在这里一起来进行对比说明。 

异构信息网络专题论文集:https://github.com/ConanCui/Research-Line

KDD 2018

待解决的问题

目前大多数异构信息网络(HIN)对于点之间相似度的衡量方式,都是在低维空间使两个点的 embedding 的内积 (dot product)尽可能的大。这种建模方式仅能考虑到一阶关系(first-order proximity),这点在 node2vec 中也提到;

相比于同构信息网络,异构信息网络中包含多种 relationship,每种 relationship 有着不同的语义信息。 

同时 relationship 的种类分布非常不均匀

解决的方法

1. 使用 metric learning(具体可参见论文 Collaborative Metric Learning [1],它具有 triangle inequality 特性)来同时捕捉一阶关系和二阶关系(second-order proximity)。

2. 在 object space 学习 node 的 embedding,在 relation space 学习 relation 的 embedding。计算时,先将 node embedding 从 object space 转移到 relation space,然后计算 proximity。 

3. 提出 loss-aware 自适应采样方法来进行模型优化。

模型的动机

相比于同构网络的 embedding,异构网络中节点之间的 proximity 不仅仅指两个节点在 embedding space 的距离,同时也会受到 relation 中所包含关系的影响。

dot product 仅能够保证一阶关系,而 metric learning 能够更好同时保存一阶关系和二阶关系。

由于 metric learning 直接应用会存在 ill-posed algebraic 的问题,所以不能直接应用。同时我们还要考虑到异构网络中存在不同的 relation,这点也需要建模。 

以往异构网络中,对于不同种类的 relation 比例差距悬殊的问题,有人提出对每一种 relation 进行等比例采样, 但这会造成有的 relation 被欠采样,有的过采样,并且不同 relation 的难度不同,需要采样的数量也不同。

模型

学习 embedding 的 loss 如下:

其中:

可以看出,上述 loss 的目的是让不同的点在某一种 relation space 中尽可能地接近,同时是的学到的 embedding 保留一阶和二阶特性。需要学习的参数为 node embedding v, 和从 object space 映射到不同 relation space 的映射矩阵Mr。

上式中,所有负样本都加入训练集,会导致复杂度急剧上升,在这里采用双向负采样(Bidirectional Negative Sampling Strategy),所以 loss 修改如下:

对于每个 epoch,我们会把每个种类的网络的 loss 记录下来,如下,然后根据目标种类 r 的 loss 所占的比例,来确定对该种类 r 的 edge 采样出多少的比例。这样为根据 loss 来自适应的调整采样策略 (Loss-aware Adaptive Positive Sampling Strategy)。 

最终整体的算法流程为:

实验

实验采用了来自五个州的 Yelp 数据集,点的种类包括用户(User),物品(Business),物品属性(Attribute),物品种类(Category),如 Table 1 所示。

在 AZ 州的数据集上计算 Hits@K 和 MRR,结果如 Figure 2 和 Tabel 3 所示。

在 NV 州数据集做 link prediction 任务,具体为判断当前便是否存在在测试集当中,具体指标使用 AUC,结果如 Tabel 4 所示。 

总结

该篇文章整体的贡献点为:

1. 使用 metric learning 来解决 HIN 中的二阶关系,并借用 TransR 中的映射矩阵来解决 metric learning 存在的 ill-posed algebraic 问题,对于多种 relation 建立多个 relation space。

2. 提出 loss-aware adaptive 采样方法,解决了 HIN 中存在的 relation skewed 的问题。 

但是可能存在的问题是,该篇文章仅仅考虑基础的 relation,另外在 HIN 中还有常见的 composite relations 是使用 meta-paths 来表示的。

比如在 DBLP 这样的参考文献数据集上,存在 (A, author,P,paper,C,conference) 这些节点。而像 APA (co-author relation),以及 APC (authors write pa- pers published in conferences) 这样包含着丰富的信息的 composite relations,在这篇文章中没有考虑到。

AAAI 2019

待解决的问题

1. 异构网络中存在着很多的 relations,不同的 relations 有着不同的特性,如 AP 表现的是 peer-to-peer,而 PC 代表的是 one-centered-by-another 关系。如何区分不同的 relations?

2. 针对不同的 relations,目前的模型都采用相同的方法来对他们进行处理。如何区分建模?

3. 如果建立多个模型,如何协调优化?

解决的方法

1. 根据结构特性定义了两种 relations,Affiliation Relations (ARs) 代表 one-centered-by-another 的结构,而 Interaction Relations (IRs) 代表 peer-to-peer的关系。 

2. 对于 AR,这些点应当有共同的特性,所以直接用节点的欧几里得距离作为 proximity。对于 IR,将这种关系定义为节点之间的转移(translation)。前者借鉴了 collaborative metric learning,后者借鉴了模型 TransE。 

3. 因为两个模型在数学形式上相似,所以可以一起优化。

数据分析

不同于上篇文章,这篇文章从数据分析入手,并给出两种 structural relation 的定义。三个数据集整合如 Table 1 所示。 

对于一个 relation 的三元组 <u,r,v>,其中作者定义了一个指标如下:

该指标由 u 和 v 种类的节点的平均度(degrees)来决定。如果 D(r) 越大,代表由 r 连接的两类节点的不平衡性越大,越倾向于 AR 类型,否则倾向 IR 类型。同时定义了另外一个稀疏度指标如下:

其中代表该种类 relation 的数量,代表头节点所在种类节点的数量,如果数据越稠密,则越倾向于 AR,因为是 one-centered-by-another,而 IR 关系的相对来说应该较为稀疏。

模型

对于 AR 类型,采用类似于上篇文章 PME 中的 metric learning 角度建模,原因除了 metric learning 能够保留 second- order proximities 外,metric learning 和 AR 的定义契合,及被该关系连接的节点之间欧式距离要尽量的小。

而对于 IR 类型为何用 translation 来进行建模,没有更好的说明,只是在模型的数学形式上和 metric learning 较为接近,容易结合。 

则对于 AR 类型的 loss 为:

而对于 IR 类型的 loss 为:

对于整个模型来说,就是简单的把两部分的 loss 相加,没有上一篇 PME 中考虑的更合理。

正负采样的方法也没有上一篇当中有过多的技巧,relation 的正采样就直接按照数据集中的比例来进行采样,不考虑 relation 种类是 skewed 的情况。而对于负采样,和 TransE 和上篇文章中 PME 相同的方法,即双向负采样。

实验

实验采用 Table 1 中的数据集,首先看在聚类任务上效果的好坏,具体指标采用 NMI,结果在表格 2 中所示。

接着看了模型在 Link prediction 上的效果好坏,具体为判断当前边是否在测试集中。具体指标采用 AUC 和 F1,结果见 Table 3。

另外看了模型在 multi-class classification 任务上的表现,看学到的节点是否保留有节点种类信息,具体为对已经学习到的节点 embedding,训练一个分类器,结果如 Table 4 所示。

另外,为了探讨区分两种 relation,并利用 metric learning 和 translation 进行建模是否有效,作者进行了 ablation study。提出如下三种 variants:

其实验结果如 Figure 2 所示:

总结

总的来说,作者从分析数据入手,对于 HIN 中具有不同 structural 的 relation 进行了区分,并且分别采用不同的方法对不同 structural 的 relation 进行建模,在一定程度上给出了这两种方法的建模 motivation。

相比于 PME,作者对于两部分的 relation 的 loss 结合较为粗糙,不过作者的重点也不在于此,没有什么问题。

参考文献

[1]. Hsieh C K, Yang L, Cui Y, et al. Collaborative metric learning[C]//Proceedings of the 26th international conference on world wide web. International World Wide Web Conferences Steering Committee, 2017: 193-201.

PaperWeekly
PaperWeekly

推荐、解读、讨论和报道人工智能前沿论文成果的学术平台。

理论论文KDD 2018AAAI 2019异构信息网络网络表示学习
2
相关数据
数据分析技术

数据分析是一类统计方法,其主要特点是多维性和描述性。有些几何方法有助于揭示不同的数据之间存在的关系,并绘制出统计信息图,以更简洁的解释这些数据中包含的主要信息。其他一些用于收集数据,以便弄清哪些是同质的,从而更好地了解数据。 数据分析可以处理大量数据,并确定这些数据最有用的部分。

参数技术

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

欠采样技术

欠采样是信号处理学中的一种采样技术,也叫带通采样(bandpass sampling),是一种以低于其奈奎斯特采样定理(采样频率两倍高于被采样频率)的采样率对带通滤波信号进行采样且仍然能够重建信号的技术。

欧几里得距离技术

在数学中,欧几里得距离或欧几里得度量是欧几里得空间中两点间“普通”(即直线)距离。 使用这个距离,欧氏空间成为度量空间。

映射技术

映射指的是具有某种特殊结构的函数,或泛指类函数思想的范畴论中的态射。 逻辑和图论中也有一些不太常规的用法。其数学定义为:两个非空集合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)。同样的,在机器学习中,映射就是输入与输出之间的对应关系。

异构信息网络技术

与homogeneous同构信息网络相区别,异构信息网络的网络模式限定了对象集合以及对象间关系的类型约束。这些约束使得异构信息网络具有半结构化的特点,引导着网络语义的探究。异构信息网络可以由许多相互连接的、大规模的数据集来构造,范围涉及社会、科学、工程、商业应用等。

聚类技术

将物理或抽象对象的集合分成由类似的对象组成的多个类的过程被称为聚类。由聚类所生成的簇是一组数据对象的集合,这些对象与同一个簇中的对象彼此相似,与其他簇中的对象相异。“物以类聚,人以群分”,在自然科学和社会科学中,存在着大量的分类问题。聚类分析又称群分析,它是研究(样品或指标)分类问题的一种统计分析方法。聚类分析起源于分类学,但是聚类不等于分类。聚类与分类的不同在于,聚类所要求划分的类是未知的。聚类分析内容非常丰富,有系统聚类法、有序样品聚类法、动态聚类法、模糊聚类法、图论聚类法、聚类预报法等。

暂无评论
暂无评论~