王治政 异构信息网络的表示学习
新闻来源:IR实验室       发布时间:2017/12/24 0:00:00

综述

本篇论文发表于2017CIKM[2]会议上,论文主要介绍了一种针对于异构信息网络的知识表示学习框架—HIN2Vec框架。与之前提出的很多基于Skip-gram语言模型不同的是,在HIN2Vec框架中,其核心是一个神经网络模型,在学习网络节点的知识表示的同时,也可以对网络中的元路径(Meta-paths)进行表示学习。

论文提出了传统神经网络中存在的问题并对其进行了改进,同时做了大量的验证实验,对实验过程的参数、变量以及学习所得向量的有效性进行全面的实验。下面,将从四个主要的方面进行论文的介绍。

引言

目前,基于同构信息网络的模型和算法层出不穷,但是基于异质信息网络的模型和算法就屈指可数。在同构信息网络中,大量的工作都是基于节点的整合信息或者是限制类型的关系,在已有的方法中,ESim算法[3]虽然考虑了关系类型,但是其过多的依赖于人为定义的路径以及路径的权重设置。因此,基于该领域的研究现状并且考虑到现有模型的不足之处,作者提出了HIN2Vec的知识表示框架。

HIN2Vec框架通过学习网络节点和网络中不同类型的关系类型来学习异质网络中丰富的信息。设置不同的元路径,其所对应的语义信息是不同的,因此作者认为对嵌入在网络结构和元路径中的丰富信息进行编码可以提高对异构信息网络的知识表示学习。

总体框架图如下图所示:

Figure 1:Overview of the HIN2Vec framework

从该框架图中可以看出主要有两个部分。一个是HIN2Vec学习框架,另一个是Application模块。简单了解一下这个框架:异质网络和元路径集合作为整个框架的输入,经过HIN2Vec框架对所有的节点和目标关系进行向量特征的学习,将学习到的元路径向量和节点向量作为输出,其中节点向量可以作为后续应用的输入特征向量,进行测试和预测任务。它是通过预测多个节点对之间的异质关系来进行训练,这就需要模型能够实现将不同关系的信息向量和网络结构向量进行拼接,从而形成一个节点的特征向量。而关系向量实质上也指出了网络中两个关系之间的相似程度。同时,模型在进行目标函数优化的时候采用的是异步的随机梯度下降法。正如前面所描述的那样,该框架的最大的优势是保存了更多的网络内容信息,它不仅假设存在关系的两个节点是相关的,而且还区分节点的不同关系类型,而不是简单的基于在高维空间有边相连的节点在低维空间的映射距离比较近的假设。

本文的主要贡献点有三个[4]:

1)证明了节点间不同类型的关系能够更好的捕获更多嵌入在网络结构中的细节信息,因此通过捕获节点间各种不同类型的关系,有助于网络的表示学习

2)提出了 HIN2Vec 模型,包括两部分:首先,基于随机游走和负采样生成训练数据,然后,设计逻辑二元分类器用于预测两个给定的节点是否存在特定的关系。

3)实验很充分,包括多标签分类和链路预测,同时实验研究了循环序列、负采样以及正则化对实验分类结果的影响。

定义

对于文中的一些概念,现给出详细定义:

(1)信息网络是一个有向图G = (V,E,Φ,Ψ),其中V表示节点集合,E表示边集,ΦΨ分别表示节点和边的映射关系Φ : VAΨ : ER 。在映射关系中,AR分别表示节点和边的一种特殊的类型。而当节点类型或者边类型的数量大于1的时候,则称该信息网为异构信息网络。下图2为一个从DBLP合作网络(异构信息网络)中抽象所得有向图,其中AiPj为节点关系类型。

Figure 2:A paper-author HIN

(2)元路径。是一个由节点类型或者边类型组成的类型序列。依然以上图的异质信息网络举例,则元路径(π)可表示为:π=a1r1a2r2a3r3......rn-1an。其中aii=1,2.....,n为节点类型,rjj=1,2......,n-1为关系类型

(3)异质信息网络的表示学习:目的就是学习一个映射函数f : V Rd,将高维空间的节点映射成一个d维的低维空间。

同时,在进行框架的设计和模型的构成等方面,主要的挑战有:

1)模型的设计问题。传统的神经网络模型对于大规模的网络而言,在模型学习和训练数据的方面花销是巨大的。

2)参数正则化的问题

3)大规模网络训练数据准备的问题。

HIN2Vec框架

从总体框架图中可以看出,作者所提出的HIN2Vec框架主要由训练数据的准备和知识表示的学习两个部分组成,下面将从这个方面对此框架进行介绍。

训练数据的准备

在训练数据准备的模块中,主要是采用了随机游走算法和负采样算法以生成符合目标关系的数据,从而用于知识表示学习。

采用随机游走算法来选取训练数据的主要优点是:(1)随机游走的空间复杂度比较低。在随机游走的过程中主要涉及到对节点的存储和寻找两个部分,因此设一个随机游走长度为L的游走过程,那么其空间复杂度为O(|V|+L),时间复杂度也仅为O(L) ,因为在现有的节点搜索算法可以达到时间复杂度为O(1)的性能。(2)基于随机游走所得到的序列是一个随机序列,而其子序列同样也是经过随机游走产生的,即也可以作为训练使用的数据,这就避免了对数据集重复进行随机游走,降低了时间复杂度,提高了框架效率。

随机游走过程中所产生的训练样本均为正例,但是在师姐训练过程中需要负例样本的参与,因此引入负采样算法来产生负例,其主要过程为:对实体序列(x,y,r[1]中的三个值进行随机替换。但是因为节点的规模是远大于关系的,因此在实验中采用的替换策略是只替换节点类型,而不替换关系类型,即只选取(x,y)中的一个数值进行替换,并且只采用相同类型的节点来进行替换。

表示学习

表示学习部分是一个神经网络模型,通过最大化预测节点之间关系的可能性,同时学习节点和关系的表示向量,HIN2Vec 模型的基本想法是对于多个预测任务,每个任务对应于一条元路径,联合学习一个模型以学到每个节点的向量表示,所以一个简单的想法就是构建一个神经网络模型,预测任意给定节点对之间的一组目标关系。鉴于基本思路的多分类预测任务,拟采用如图3所示的概念神经网络模型。

微信截图_20171213150538

Figure 3:A conceptual model for HIN2Vec

概念神经网络引入的是一个单层的前馈神经网络模型,将节点序列(x,y)作为模型的输入,节点x和节点y都是一个长度为|V|one-hot向量,然后经过隐层(中间层)将输入的one-hot向量转变成隐层向量的形式,最终在关系转移矩阵WR的作用下输出位长度为|R|维的预测概率P(ri|x,y)。每一维表示节点对(x,y)中包含某种关系的概率。为了更直观的对作者的基本思路做一个理解,现引入图2所示的DBLP合作网络简例进行分析。

DBLP合作网络中,节点有paperauthorvenue这三种类型,(图中给出了两种类型—作者和论文)。在这个例子中,两个P类型节点之间的边表示论文的引用关系,而PA类型节点之间的边表示作者关系。同时引入一个表示目标关系的集合R,规定集合R是由节点序列之间跳数小于2的边关系组成的。则R={P-P,P-A,A-P,P-P-P,P-P-A,P-A-P,A-P-P,A-P-A},共有八种关系类型。对于这八种关系类型,模型需要进行一个八分类任务,对给定的节点对中是否有某一种关系类型进行概率预测。最终在经过NN模型以后,得到的是一个8维的向量,其中预测结果是两个节点序列之间符合某一种关系时,相应向量位置上就是1,否则就是0。可以看出,该神经网络所采用的是遍历网络中某一节点对之间的所有关系类型来最终确定向量输出,而当网络是大规模的时候,其代价却是巨大的。

所以作者对基本的思路做了一个转换,将问题从一个多分类任务简化为一个二分类问题,即给定两个节点 x,y和关系r,预测给定节点间是否存在确定的关系r,这样就避免了遍历网络中的所有关系,图4所示就是 改进的HIN2Vec框架下的神经网络模型。

279b34381d83ecdece050d8c5713aceb

Figure 4: The HIN2Vec NN model

在这个模型中,同样将节点对(x,y)和关系r均以one-hot向量的形式输入到模型之中。经过转换矩阵得到有隐层向量表示。需要强调的是,与上述模型不一样的是,在这里将关系作为一个输入,但是关系类型的语义与节点的含义明显是不相同的,所以为了解决这种含义信息的不对等,引入了关系正则化处理,限制了关系向量的值处在01之间,引入正则化的处理同时也可以避免关系类型中出现负值和过大值的情况。在得到隐含向量之后,经过一个向量逐元素相乘(Hadamard 向量函数)的线性变化后得到输出层的向量,再对输出层进行一个sigmoid函数转变可以得到最终输出,最终输出一个二进制的值(1表示关系在节点对中,0表示关系不在节点对中)。

综合模型的两个组成部分可知,模型的输入向量形式是一个<x,y,r,L(x,y,r)>四元组,其中x,y是给定的两个节点,r为一个确定的关系类型,而L(x,y,r)是一个二进制(0,1)的数值,0表示关系r不在节点对中,1表示关系r在节点对中。而目标函数的目的就是当L(x,y,r)=1是,要使得关系类型的预测概率尽可能的大,否则就要尽可能的小。因此,作者设置的目标函数以及如图5所示:

Figure 5:Objective Function

在函数的优化方面,作者采用的是随机梯度下降法和反向传播来调整隐藏向量的权重。具体的公式如图6所示:

Figure 6:Optimization Function

实验

作者在论文中主要做了两类实验,分别是多标签的节点分类任务和基于边的链路预测任务。在经过缜密的实验设置和详细地实验验证,作者从多个角度证明了实验的可靠性和可信度。这里只描述有关两类任务的实验结果,以此来分析和印证HIN2Vec框架的优势。

(1)数据集

数据集是来自不同领域的四组数据,其具体信息如图7所示:

Figure 7:Statistics of Datasets

其中Blogcatalog是一个日志数据集,使用所有的用户和他们的组构成的一个社会网络,其关系类型有朋友关系(U-U)和用户组别关系(U-G)。Yelp是一个社会媒体数据集,这里只提取了商业排名前10的城市形成数据集,所以其节点的类型有客户,商业,城市和领域四种类型,而关系的类型主要有朋友关系(U-U),客户评论关系(B-U),商业城市关系(B-C)和商业领域关系(B-T)。DBLP是一个引文数据集。主要提取了从1994年到2014年间的20个会议上的4中研究领域形成的数据集。节点类型主要有论文、作者和会议三种,关系类型主要有作者关系(P-A)、论文会议关系(P-V),引用关系(P-P)。U.S. Patent 是美国的一个专利数据集。

(2)多标签的节点分类任务

实验步骤:在经过模型学习到了节点的向量以后,选取一个节点集合对其打标签,然后经过一个5-折交叉验证的线性SVM模型进行预测,采用微观F值和宏观F值两个评价指标进行评价。宏观F值是指计算全部类别的F值,受小类别影响更大,而微观F值是指计算某一个类别的F值。具体来说就是对于四个不同的数据集进行不同的打标签操作。

1)将39个不同的组作为标签,所有的用户和标签组形成数据集

2)选了10个餐馆领域主要的美食作为标签,并且选择13111个拥有这些美食标签的餐馆形成数据集

3)使用4个研究领域作为标签,作者是否有相关领域产出为目标形成数据集

4)使用14个毒品类专利作为标签,引入专利形成数据集

在经过标注的数据集上进行该实验室,实验结果图8所示。可以看出,与经典的Network Embedding算法相比,HIN2Vec框架所学习到的节点向量在多标签节点分类任务中的表现是最好的,评价值的提升比率最小的情况下提升6.6%,最好的情况下提升23.8%

Figure 8:Performance Evaluation of Node Classification

(3)基于边的链路预测任务

链路预测任务主要是将预测任务转变成了推荐任务。首先通过选择一个边集生成一个子网络,并随机删除一定比例的边作为缺失边,同时采用监督学习模型来对节点进行排序。

具体来说:实验中选择了2000个点作为训练集,对于一个选定的节点,使用它的固定的某几跳范围内的邻居节点作为候选节点对(减少需要排序的节点数量)。对于每一个节点对,如果有缺失边则标为1,否则标为0. 然后通过对这个子网进行不同的向量函数训练,从而得到每一个节点的特征向量。最后使用SVM模型进行排序。评价指标为平均准确率和前k个节点的召回率。


参考文献

[1] Tao-yang Fu, Wang-Chien Lee, Zhen Lei. 2017. HIN2Vec: Explore Meta-Paths in Heterogeneous Information Networks for Representation Learning. In ACM International Conference on Information and Knowledge Management (CIKM) November 6-10, 2017, Singapore.

[2] http://www.cikm2017.org/

[3] Jingbo Shang, Meng Qu, and Qiaozhu Mei. 2015. Pte: Predictive text embedding through large-scale heterogeneous text networks. In Proceedings of the ACM International Conference on Knowledge Discovery and Data Mining(SIGKDD2015) .

[4] https://zhuanlan.zhihu.com/p/31362664