软件学报  2018, Vol. 29 Issue (3): 786-798   PDF    
一种融合节点先验信息的图表示学习方法
温雯1, 黄家明1, 蔡瑞初1, 郝志峰1,2, 王丽娟1     
1. 广东工业大学 计算机学院, 广东 广州 510006;
2. 佛山科学技术学院 数学与大数据学院, 广东 佛山 528000
摘要: 图表示学习是实现各类图挖掘任务的基础.现实中的图数据不仅包含复杂的网络结构,还包括多样化的节点信息.如何将网络结构和节点信息更加有效地融入图的表示学习中,是一个重要的问题.为了解决这一问题,基于深度学习,提出了融合节点先验信息的图表示学习方法.该方法将节点特征作为先验知识,要求学习到的表示向量同时保持图数据中的网络结构相似性和节点特征相似性.该方法的时间复杂度为O(|V|),其中,|V|为图节点数量,表明该方法适用于大规模图数据分析.同时,在多个数据集上的实验结果表明:所提出的方法相比目前流行的几种基线方法,在分类任务上能够获得良好而稳定的优势.
关键词: 图表示     节点特征     大规模网络     深度学习     图挖掘    
Graph Embedding by Incorporating Prior Knowledge on Vertex Information
WEN Wen1, HUANG Jia-Ming1, CAI Rui-Chu1, HAO Zhi-Feng1,2, WANG Li-Juan1     
1. School of Computer, Guangdong University of Technology, Guangzhou 510006, China;
2. School of Mathematics and Big Data, Foshan University, Foshan 528000, China
Foundation item: NSFC-Guangdong Joint Found (U1501254); Natural Science Foundation of China (61472089, 61572143, 61502108)
Abstract: Graph embedding is a fundamental technique for graph data mining. The real-world graphs not only consist of complex network structures, but also contain diverse vertex information. How to integrate the network structure and vertex information into the graph embedding procedure is a big challenge. To deal with this challenge, a graph embedding method, which is based on deep leaning technique while taking into account the prior knowledge on vertices information, is proposed in this paper. The basic idea of the proposed method is to regard the vertex features as the prior knowledge, and learn the representation vector through optimizing an objective function that simultaneously keeps the similarity of network structure and vertex features. The time complexity of the proposed method is O(|V|), where|V|is the count of vertices in the graph. This indicates the proposed method is suitable for large-scale graph analysis. Experiments on several data sets demonstrate that, compared with the state-of-art baselines, the proposed method is able to achieve favorable and stable results for the task of node classification.
Key words: graph embedding     vertex feature     large-scale network     deep learning     graph mining    

随着信息技术的发展, 社交网络、论文引用网络、基因调控网络等各类大型图, 已经渗透到现实生活的方方面面.这些图数据结构复杂, 规模大, 动辄包含成千上万个节点, 节点中还可能包含各类不同信息.与之相关的, 也出现了丰富多样的图挖掘任务, 如节点分类[1-3]、标签推荐[4, 5]、异常检测[6]、边预测[7, 8]和个性化推荐[9, 10]等.然而现实中图数据的高维度、稀疏性等特点, 给已有的挖掘技术带来了前所未有的挑战, 图的表示学习[11]有望解决这一问题.

图表示学习的基本思想是:将节点映射到一个稠密而低维的向量空间中, 并在映射过程中尽量保留网络信息, 保留节点之间的相似性, 从而解决图数据的高维度、稀疏性等问题.传统的图表示学习方法包括基于谱方法的图表示学习, 例如非线性降维算法LLE(locally linear embedding)[12]、基于流形假设的Laplacian Eigenmaps[13]、针对有向图的DGE[14]、从社团检测角度考虑的social dimensions[15]等.然而该类方法只利用了图的网络信息, 学习到的图表示质量不高[16].此外, 还有基于最优化的图表示学习, 即, 通过优化一个明确的目标函数从而学到图的低维表示.这类方法通常都是基于半监督的、领域相关的方法, 可扩展性差, 需要为不同的图挖掘任务单独设计目标函数, 代表性算法为文献[17, 18].还有学者在产生式主题模型的基础上, 提出了结合网络结构的节点内容表示模型.这类方法通过在主题概率模型的基础上引入网络信息, 改进节点内容的描述.代表性方法包括Link-PLSA-LDA[19]、RTM[20]和PLANE[21].然而这类方法均侧重于词袋假设下的文本信息描述, 主要目的是借助网络结构改善文本内容的主题抽取, 无法适用于更加一般化的节点特征表达.

近年来, 基于深度学习的图表示学习方法逐渐引起学术界的关注.2014年, Perozzi等人提出了DeepWalk[22], 创造性地将词表示学习的方法引入到图表示学习当中.而2016年提出的Node2vec[23]则是在DeepWalk的基础上, 引入深度优先和广度优先的策略调整随机游走的过程.LINE[24]提出了图数据中存在两种网络相似性, 分别是一阶相似性(first-order)和二阶相似性(second-order).通过分别优化这两种相似性得到两种低维表示, 最后将这两种表示进行拼接, 作为节点的最终表示.值得注意的是:上述3种方法都只利用了图的网络信息, 忽略了图数据中普遍存在的节点特征.

现实当中的图数据不仅包含网络信息, 还往往包含丰富的节点特征, 这使得合理的图表示学习需要综合考虑网络信息和节点特征.本文中约定:网络信息是指图数据中节点与节点之间网络结构所体现出来的信息; 节点特征是指每个节点内包含的属性特征.节点间的相似性需要从两个方面进行考察, 以论文引用网络为例, 如图 1所示(节点内部相同线型代表相似特征):(a)如图 1(a)所示, 两篇论文(论文A与论文B)引用相近论文的交集越大, 则表明它们之间的相似性越高(记为网络信息相似); (b)如图 1(b)所示, 两篇论文有相似的内容, 则论文A与论文B是相似的(记为节点特征相似).显然, 单纯的网络信息只能处理第1种相似性, 而节点特征则可以处理第2种相似性.如何有效地综合利用这两种信息, 对于图的表示学习至关重要.

Fig. 1 Two similarity in graph 图 1 图数据中的两种相似性

从现有文献来看, 在图表示学习方面, 综合考虑了图的网络信息和节点特征的深度学习方法并不多, TADW[25]是其中一种模型.该模型首先证明了DeepWalk等价于节点上下文PMI矩阵的分解, 然后通过将节点特征嵌入到矩阵分解中, 从而使得节点表示学习的过程中同时融入了网络信息和节点特征.文献[26]则利用半监督的方法将图表示学习与节点分类任务结合, 提出了Planetoid模型.该方法只能针对网络节点分类任务, 学习到的图表示不具有一般性.

本文从融合网络信息和节点特征的角度出发, 提出了一种改进的图表示学习方法GeVI(graph embedding byincorporating prior knowledge on vertices information).该方法将已知的节点特征看做先验知识, 并基于DeepWalk思想, 将图表示学习问题转化为词表示学习问题, 设计了同时考虑网络信息和节点特征相似性的目标函数, 进而通过优化该目标函数得到融合了网络信息和节点特征信息低维的节点表示向量.为了更好地验证先验知识对于节点表示的作用, 我们还设计了两种表示方法:其中一种是将当前节点及其特征融入到目标函数中, 获得综合的节点表示; 另一种是在目标函数中不考虑当前节点, 仅考虑上下文节点, 在优化之后再将所学的表示向量与先验特征向量进行拼接, 作为节点的最终表示.

通过在多个公开数据集上的实验, 验证了我们提出的两种表示方法都能够获得优于现有方法的良好结果.

本文第1节介绍图表示学习的相关工作, 包括基于传统的方法和基于深度学习的方法.第2节详细介绍本文提出的融合节点特征和网络信息的图表示学习方法.第3节则在多个不同数据集上对本文提出算法的有效性进行验证, 报告相关的实验结果.最后, 我们对本文工作进行总结和展望.

1 相关工作

本节介绍图表示学习的相关方法, 包括传统的图表示学习方法、基于深度学习的图表示学习方法及同时利用网络信息和节点特征的图表示学习方法.

1.1 传统的图表示学习方法

传统的图表示学习方法包括3种.

●  第1种是基于谱方法的.

该类方法首先根据图的网络信息构建输入矩阵(相似性矩阵、邻接矩阵或拉普拉斯矩阵等), 然后将矩阵进行降维, 得到节点的低维表示, 比如利用经典的PCA或SVD方法进行降维.包括非线性降维算法LLE(locally linear embedding)[12]、基于流形假设的Laplacian Eigenmaps[13]、针对有向图的DGE[14]、从社团检测角度考虑的social dimensions[15]等.LLE算法将每个节点表示为其近邻点的线性加权组合, 给定一个邻接矩阵[27], 首先计算每个节点的局部重建权值矩阵, 然后转换为特征值分解问题, 最后计算节点的低维表示.Laplacian Eigenmaps算法输入图的邻接矩阵, 计算拉普拉斯矩阵的特征值, 最后将最小的k个非零特征值对应的特征向量作为图表示, 从而希望保证在图中相邻的节点会被映射到降维后的空间中相近的位置.DGE算法通过随机游走的思想将Laplacian Eigenmaps算法扩展至有向图的表示学习.Social dimensions方法则是针对社团检测问题, 将图表示学习与社团检测融合, 学习到的表示向量的每一维度都对应一个社团, 大小表示该社团占的权重.通过模块度最大化[28]计算出模块度矩阵, 最后计算出该矩阵的特征值, 图表示对应于最大的k个特征值对应的特征向量.

●  第2种是领域相关的图表示学习方法.

通过优化一个领域相关的目标函数, 从而学习图的低维表示.代表性算法为文献[17, 18].文献[17]提出了LSHM算法, 要求学习到的图表示一方面能够保留网络之间的平滑性; 另一方面, 还要最小化一个线性分类函数的损失值.LSHM算法能够处理异构网络, 基本思想是, 将异构节点统一映射到相同的向量空间中.针对网络信息传播预测问题, 文献[18]首先学习用户的低维表示, 然后把网络上的信息传播问题转为在用户低维空间上的信息传播问题进行求解.

●  还有学者提出了结合网络结构的节点内容表示模型.

这类方法通过在主题概率模型的基础上引入网络信息, 改进节点内容的主题描述.代表性方法包括Link-PLSA-LDA[19]、RTM[20]和PLANE[21].Link-PLSA-LDA方法通过建模被引用论文集合的生成过程和引用论文集合的生成过程学习图表示.RTM方法使用LDA建模文本的生成过程, 同时建模了链接关系的产生.RTM的主要假设是:如果两个节点之间存在边, 则这两个节点的主题分布应该相似.PLANE方法扩展了RTM, 从可视化的角度学习文本主题和节点的图表示.PLANE学习每个主题和节点的二维表示(可视化), 并且利用PE算法[29]对RTM模型学习到的话题降维.上述方法均要求节点内容为文本信息, 且文本内容表示为词袋模型, 无法很好地处理非文本类型的节点特征.

1.2 基于深度学习的图表示学习方法

近年来, 随着深度学习的发展, 基于深度学习的图表示学习方法相继被提出.DeepWalk[22]通过随机游走的方法将图转换成一系列的“句子”, 每个节点对应一个单词, 然后利用skip-gram模型[30]学习图的表示, 创造性地将图表示学习问题转换为自然语言处理领域中的词表示学习问题.Node2vec[23]在DeepWalk的基础上引入深度优先和广度优先的策略, 调整随机游走的过程, 使得随机游走生成的路径能够更好地保留图的网络信息.最后, 与DeepWalk的学习策略相似, 将生成的路径通过skip-gram模型进行学习, 得到图的低维表示.LINE[24]提出了图数据中存在两种相似性, 分别是一阶相似性(first-order)和二阶相似性(second-order).一阶相似性认为, 相连的节点是相似的; 而二阶相似性则根据节点之间共享邻居的数量决定它们之间的相似性, 共享邻居越多的两个节点, 它们之间的相似性越高.通过分别对图中的一阶相似性和二阶相似性进行学习, LINE得到了图的两种向量表示.最后, 通过将这两种向量表示进行拼接, 作为融合了一阶相似性和二阶相似性的图表示.

1.3 融合节点特征和网络信息的图表示学习方法

针对存在节点特征的图数据, TADW[25]首先证明了DeepWalk等价于将矩阵MR|V|×|V|分解为WRk×|V|HRk×|V|, 其中, Mij表示节点i在固定步内随机游走到达节点j的平均概率的对数值, W对应于DeepWalk学习到的图表示, |V|表示图节点数量.然后, TADW通过将节点特征矩阵$T \in {R^{{f_t} \times |V|}}$嵌入到M的分解中, 即, 将矩阵M分解为W, HT, 最终将WT拼接得到节点的图表示.TADW通过矩阵分解的形式将节点特征融入图表示中.文献[26]所提出的方法利用半监督的方法将图表示学习与节点分类任务结合, 要求学习图表示的同时, 优化一个基于图表示的分类器, 提出了Planetoid模型.具体地, Planetoid通过同时优化两个目标函数:分类器的损失函数和图表示的损失函数, 从而学习出嵌入了节点标签信息的图表示.分类器的输入包括两部分, 分别是经过了多层神经图的节点特征和图表示.而图表示损失函数与DeepWalk基本一致, 不同的是, Planetoid利用标签信息, 将那些原本不相连、但具有相同标签的节点连接在一起.

2 融合节点先验信息的图表示学习方法

为了更好地阐述所提出模型及算法, 首先给出相关符号及其含义(见表 1).

Table 1 Definition of symbols 表 1 符号定义

图表示学习的目标是:给定图G=(V, E), 其中, V是节点的集合, E是边的集合, 图表示学习方法将图G中每个节点vi映射为一个低维的特征向量Φ(Vi)∈Rd, 其中, d < < |V|, 且要求如果两个节点是相似的, 那么它们映射后的向量相近; 否则, 它们被映射后的向量距离较远.如引言中所述, 图中节点之间的相似性本质上可以通过网络信息和节点特征进行刻画.一个理想的图表示学习方法应该能够同时满足如下几个要求:(1)能够保留网络信息相似性; (2)能够保留节点特征相似性; (3)维度不能太大.接下来, 我们将给出一个新的图表示学习方法GeVI, 该模型能够同时满足上述图表示学习的要求.

2.1 模型描述

viV为图G=(V, E)中的第i个顶点, vjN(vi)为vi的邻居, 即, vi可以通过E中的若干条连接边到达vj.并记Φ(vi)∈Rd为需要求取的vi的低维表示.则类似于自然语言处理中的skip-gram模型[30], 可以通过优化与图节点相关的联合概率(公式(1))获得Φ(vi)的表达:

$ \arg {\max _{\mathit{\Phi} ({v_i})}}\prod\nolimits_{{v_i} \in V} {[\prod\nolimits_{{v_j} \in N{{({v_i})}^*}} {p({v_j}|{v_i};\mathit{\Phi} ({v_i}))}]} $ (1)

为了将已知的节点特征融入到该模型中, 可以将条件概率p(vj|vi; Φ(vi))表示为公式(2)的形式:

$ p({v_j}|{v_i};\mathit{\Phi} ({v_i})) = \frac{{\exp ({f_j} \cdot \mathit{\Phi} ({v_i}))}}{{\sum\limits_{{v_k} \in V} {\exp ({f_k} \cdot \mathit{\Phi} ({v_i}))} }} $ (2)

则有:

$ p({v_j}|{v_i};\mathit{\Phi} \left( {{v_i}} \right))\infty {\rm{exp}}({f_j} \bullet \mathit{\Phi} \left( {{v_i}} \right)) $ (3)

其直观的解释是:对于图G中每个节点vi, 我们可以寻找一个低维表示Φ(vi)∈Rd, d < < |V|, 使得Φ(vi)能够较好地解释邻居节点vj的先验特征.将条件概率写成公式(2)的形式, 事实上借鉴了skip-gram模型[30]的基本思想:如果两个单词(节点)有相似的上下文, 则它们是相似的.在图的表示学习中, 如果两个节点拥有共同或者特征相近的邻居节点(如图 1(a)所示), 那么两个节点具有相似的低维表示.由于节点特征是已知的, 可以要求学习到的节点的低维表示能够解释其邻居的节点特征, 为此, 将条件概率设计如公式(2).另一方面, 如图 1(b)所示, 还需要考虑当前节点特征的相似性, 为此, 需将当前节点特征融入到其中, 我们分别设计了如图 2所示的两种方案.

Fig. 2 Two schemes to incorporate the vertices' features 图 2 融合节点特征的两种方案

●  方案1(GeVI.v1):拼接, 即, 表示学习后进行拼接.具体而言, 在目标函数(1)中, 令N(vi)*=N(vi)(如图 2(a)所示), 并对公式(2)进行优化, 将学习获得的F(vi)与fi进行拼接, 获得节点vi的表示.在这种情况下, Φ(vi)满足了图 1(a)中所示的网络信息的刻画和学习, fi满足了图 1(b)所示的当前节点特征的刻画.

●  方案2(GeVI.v2):融合, 即, 表示学习的过程中进行融合.具体而言, 在目标函数(1)中, 令 $N{\left( {{v_i}} \right)^*} = N\left( {{v_i}} \right) \cup \left\{ {{v_i}} \right\}$ (如图 2(b)所示).其直观含义是:使得所学习到的节点向量Φ(vi)既能解释自身节点特征, 也能解释网络中邻居节点特征.

具体实现上, 可以通过有差别的采样方法分别实现方案1和方案2中的目标优化.

由于公式(2)中归一化项的时间复杂度很高, 本文利用文献[30]提出的负采样方法进行优化.具体的, 我们不是直接优化公式(1)中的目标函数, 而是通过最大化如下转换函数来学习节点的表示向量:

$ {\mathit{\Delta} _{i, j}} = \log \sigma (\mathit{\Phi} {({v_i})^T}{f_j}) + \sum\nolimits_{t = 1}^s {{E_{{v_t} \sim {P_n}(v)}}[\log \sigma (-\mathit{\Phi} {{({v_i})}^T}{f_t})]} $ (4)

其中, $\sigma (x) = \frac{1}{{1 + \exp ( - x)}}$是sigmoid函数.vt~Pn(v)说明按照分布Pn(v)抽取节点vi的负样本vt.记vt在图中的度数为deg(vt), 与文献[22]的设定一样, 我们定义Pn(v)∝deg(v)3/4.对于每个目标节点, 都有s个负样本点.记Ci为节点vi的邻居集合, 其中, CiV, 最终, 融合网络信息和节点特征的目标函数定义为

$ L = - \sum\nolimits_{{v_i} \in V} {\sum\nolimits_{{v_j} \in {C_i}} {{\mathit{\Delta} _{i, j}}} } $ (5)

为了简化模型, 我们对公式(5)进行改写, 最终形式如下:

$ L = - \sum\nolimits_{({v_i}, {v_j}, \gamma ) \in D} {\log \sigma (\gamma \mathit{\Phi} {{({v_i})}^T}{f_j})} $ (6)

其中, 样本集合D包含了所有的正负样本, 里面的每一个元素含义如下:若γ=1, 则vjvi的正样本, 即vjvi的邻居; 若γ=-1, 则vjvi的负样本, 即vj是通过分布Pn(v)抽样得到的.每个正样本都对应s个负样本.

2.2 学习算法及复杂度分析

针对第2.1节所述的模型, 学习算法的设计主要涉及两个关键部分:邻居节点的采样以及目标函数的优化.以下我们进行详细阐述.

本文借鉴文献[22, 23]的思路, 采用邻居的推广定义.具体地, 在DeepWalk模型中, 给定窗口大小k, 在G上随机生成的游走路径中, 如果节点vj出现在节点vi的邻居窗口中, 则节点vj是节点vi的邻居节点.即vj不必是vi的直接邻居, 比如(vi, vj)∉E, 但只要vi能够在k步内到达vj即可.实施上, 类似于DeepWalk的设定, 首先利用截断的随机游走从图G中生成大量的路径, 然后从这些生成的路径中获得每个节点viV的邻居.在DeepWalk中, 节点的邻居不包括其本身, 而由于我们将节点特征作为其先验信息, 因此可以将节点本身作为其邻居, 即:要求当前节点不但能够解释周围节点, 还要能够解释其本身.本文采用了两种方案:对于GeVI.v1, 节点的邻居不包括其本身, 最终的节点表示为学习到的向量Φ(vi)与其自身的节点特征向量fi拼接得到; 而GeVI.v2则将节点本身作为其邻居, 将学习到的输入向量Φ(vi)直接作为图表示.

目标函数中样本集合D的生成过程见算法1.首先生成所有的正样本集合D+.对于每个节点, 以该节点为起始节点进行随机游走, 生成长度为α1的路径p.将集合{(pi, pj, 1)|0 < i, jα1; |j-i| < α2}添加到正样本集合D+中, 其中, pi为路径p的第i个元素.然后生成所有的负样本集合D-.对于D+中的每个样本(pi, pj, 1), 从分布pn中抽取s个节点, 组成正样本(pi, pj, 1)对应的负样本集合{(pi, pk, -1)}s, 然后将其添加到负样本集合D-中.最后, D=D$\cup $ D+$\cup $ D-.重复上述过程a4次.

算法1.负采样.

Input:图G(V, E), 随机游走长度α1, 滑动窗口大小α2, 负样本比例α3, 以每个节点作为开始节点游走的次数α4;

Output:训练数据集:D.

1:  D+←0; D-←0; D←0;

2:    i←0

3:  for k < α4 do:

4:    for v in |V| do:

5:       通过随机游走算法从节点v开始, 生成一条长度为a1的路径p.

6:        for i < α1 do:

7:         将正样本集合{(pi, pj, 1)||i-j| < α2, i-j}放进D+中(GeVI.v1) or

           将正样本集合{(pi, pj, 1)||i-j| < α2}放进D+中(GeVI.v2)

8:        endfor

9:       end for

10: end for

11: for (pi, pj, 1)∈D+ do:

12:       将负样本集合${\{ ({p_i}, {p_k}, - 1)|k \sim {p_n}\} ^{{\alpha _2}}}$放进D-中.

13: endfor

14: return D=D+ $\cup $ D-

我们使用批量梯度下降的方法优化目标函数(4), 由于fj是已知的, 因此只需要更新节点的表示向量Φ(vi).为方便表达, 下式中将Φ(vi)简写为Φi.对于样本(vi, vj, γ), 变量Φi的梯度计算见公式(7):

$ \frac{{\partial L}}{{\partial {\mathit{\Phi} _i}}} = \frac{{\partial \log \sigma (\gamma \mathit{\Phi} _i^T{f_j})}}{{\partial {\mathit{\Phi} _i}}} = \frac{1}{{\sigma (\gamma \mathit{\Phi} _i^T{f_j})}}\sigma (\gamma \mathit{\Phi} _i^T{f_j})(1 - \sigma (\gamma \mathit{\Phi} _i^T))\gamma {\mathit{\Phi} _i} = \gamma {\mathit{\Phi} _i}(1 - \sigma (\gamma \mathit{\Phi} _i^T)) $ (7)

由于目标函数大于0, 存在下界, 所以最小化过程最终会收敛.目标函数优化过程见算法2.第1行, 我们首先随机初始化节点的输入向量Φ.在第2行, 根据算法1生成样本集合D.在第4行, 则将样本集合D划分成b个互不相交的集合.然后在第8行, 累加样本点关于输入向量的梯度.在第10行, 利用批量随机梯度下降方法更新参数Φ.重复上述过程, 直到算法收敛.

算法2.目标函数最优化.

Input:图G(V, E), 节点特征向量fi, 随机游走长度a1, 滑动窗口大小a2, 负样本比例α3, 以每个节点为起始节点游走的次数α4, 节点表示向量维度d, 批量大小b, 梯度更新步长η;

Output:图表示Φ R|vd.

1:   随机初始化节点表示向量Φ

2:    DNegSample(G, α1, α2, α3, α4)

3:    while不收敛do:

4:      BatchesConstgructBatch(D, b)

5:      for each batch B in Batchs do:

6:        ▽Φ=0

7:        for each sample (vi, vj, γ) in B do:

8:          $\nabla {\mathit{\Phi} _i} \leftarrow \nabla {\mathit{\Phi} _i} + \frac{{\partial L}}{{\partial {\mathit{\Phi} _i}}}$

9:        end for

10:        ΦΦ-ηΦ

11:      end for

12: end while

●  时间复杂度分析

在算法1中, 一共生成了|Vα4条路径, 对于每条路径, 需要生成2α1α2个正样本, 生成每个样本的时间复杂度为O(1), 因此, 生成所有正样本的时间复杂度为O(2α1α2α4|V|)(算法1中第3行~第10行).对于每个正样本, 需要采样出α3个负样本, 采样每个负样本的时间复杂度为O(1), 因此, 生成负样本的时间复杂度为O(2α1α2α3α4|V|).综上, 算法1的时间复杂度为O(2α1α2α3α4|V|), 正比于节点数量|V|.

在算法2中, 首先根据算法1生成所有的样本点, 其时间复杂度为O(2α1α2α3α4|V|).然后对于每次循环, 需要计算每个样本点的梯度, 梯度计算的时间复杂度为O(1), 一共有2α1α2α3α4|V|个样本点, 因此每次更新的时间复杂度为O(2α1α2α3α4|V|).因此, 算法2的时间复杂度为O(4α1α2α3α4|V|), 正比于节点数量|V|.

综上, GeVI模型的时间复杂度为O(|V|).说明本文提出的算法能够应用于大规模图表示学习任务中.

3 对比实验

为了验证本文提出算法的有效性, 我们在3个公开数据集(Citeseer, Cora, PubMed)上与几个具有代表性的图表示学习方法进行对比.

3.1 实验设定

实验方案与文献[22]类似, 首先利用无监督的方法学习图表示, 然后将其应用在多分类任务中.本文采用MicroF1和MacroF1两个指标作为模型性能的评测标准.计算公式如下:

$ MicroR = \frac{{\sum\nolimits_{i = 1}^k {T{P_i}} }}{{\sum\nolimits_{i = 1}^k {T{P_i}} + F{N_i}}} $ (8)
$ MicroP = \frac{{\sum\nolimits_{i = 1}^k {T{P_i}} }}{{\sum\nolimits_{i = 1}^k {T{P_i}} + F{P_i}}} $ (9)
$ MicroF1 = 2\frac{{MicroR \cdot MicroP}}{{MicroR + MicroP}} $ (10)
$ MacroR = \frac{1}{k}\sum\nolimits_{i = 1}^k {\frac{{T{P_i}}}{{T{P_i} + F{N_i}}}} $ (11)
$ MacroP = \frac{1}{k}\sum\nolimits_{i = 1}^k {\frac{{T{P_i}}}{{T{P_i} + F{P_i}}}} $ (12)
$ MacroF1 = 2\frac{{MacroR \cdot MacroP}}{{MacroR + MacroP}} $ (13)

其中, k表示类别数, TPi表示在类别i上的预测正确的正类数, FNi表示在类别i上预测错误的负类数, FPi表示在类别i上预测错误的正类数.

(1) 数据集

我们在3个公开数据集上进行评测, 包括Citeseer, Cora, PubMed.去掉孤立点后, 各个数据集的相关统计信息说明如下, 见表 2.

Table 2 Data sets 表 2 数据集

●   CiteSeer:包含3 264篇出版物、4 591条边、6个类别, 每个类别表示出版物的细分领域.其中, 每篇出版物均由长度为3 703的二值向量表示, 每一维表示该出版物是否出现相应的单词;

●   Cora:包含2 708篇机器学习领域的论文、5 429条边、7个类别, 每个类别表示论文的细分领域, 边表示了论文之间的引用关系.其中, 每篇论文均由长度为1 433的二值向量表示, 每一维表示该文档是否出现相应的单词;

●   PubMed:包含19 717篇生物医学领域的文章、44 338条边、3个类别, 每个类别表示文章的细分领域, 边表示论文之间的引用关系.其中, 每篇论文均由长度为500的TF-IDF向量表示.

(2) 对比方法

我们将对比方法分成3类:(1)仅利用节点特征; (2)仅利用网络信息; (3)同时利用节点特征和网络信息.对于第3类, 我们进一步分成两小类, 分别是:(a)原始模型不可以利用两种信息, 扩展原有算法, 使得它们可以同时利用网络信息和节点特征; (b)本来就可以直接利用网络信息和节点特征的方法.

以下是对比方法的简要介绍.

●   SVD:直接通过SVD分解将节点特征信息进行降维, 降维后的向量作为图表示.属于第1类对比方法, 只利用了节点特征;

●   DeepWalk[22]:DeepWalk只利用了网络信息学习图表示;

●   DeepWalk#SVD:通过将DeepWalk和SVD得到的图表示进行拼接, 扩展了原有算法, 使得到的图表示同时包含了图结构信息和节点特征;

●   TADW[25]:TADW通过矩阵分解的形式, 直接利用了网络信息和节点特征学习得到图表示.

(3) 参数设定

基于SVD分解方法的维度统一取200(与文献[25]保持一致).TADW按照文献[25]中提供的最优参数进行设定, 对于新增的数据集PubMed, 设置其k=128(取64, 128, 256中最好的).由于GeVI模型要求节点特征向量的长度等于节点输入向量, 因此我们首先通过SVD分解, 将节点特征向量进行降维, 将降维后的向量作为节点特征向量.表 3中详细列举了我们在实验中用到的参数.由于DeepWalk与GeVI共享全部的参数, 因此DeepWalk的参数设定与GeVI一致.

Table 3 Parameter setting 表 3 参数设定

3.2 结果及分析

在所有模型上, 我们首先利用无监督的方法学习图表示.然后将其运用于节点分类任务, 通过分类的效果判断图表示的质量.对于节点分类任务, 我们首先将图节点随机等分成两部分, 分别是测试集和训练集.然后在训练集上训练一个分类器, 在测试集上进行测试.为了比较不同训练数据对模型性能的影响, 我们进一步对训练集进行采样, 分别取训练样本的6%~100%(即整体样本量3%~50%)的数据训练分类器, 然后在测试集上进行测试.这样可以保证基于不同规模训练数据训练的分类器都在同一个测试集上进行测试.我们使用Softmax分类器, 重复上述实验10次, 报告平均结果.

表 4~表 6报告了在Citeseer, Cora, PubMed数据集上的分类Micro-F1值和Macro-F1值(粗体表示所有方法中最好的, 斜体表示基线方法中最好的, τ%(↑)表示GeVI相对于最好的基线算法的提升比例).实验结果显示:本文提出的方法比所有基线方法效果要好, 证明了将节点特征看做是节点的先验信息的有效性.GeVI模型比只利用了网络信息的模型(DeepWalk)或只利用了节点特征的模型(SVD)的效果好, 这说明了融合节点特征的必要性.此外, GeVI模型也比通过将两种信息进行简单拼接的方法(DeepWalk#SVD)及基于矩阵分解的信息融合方法TADW好, 这说明了本文提出的信息融合方法的有效性.而GeVI.v1和GeVI.v2之间则不相上下:在Citeseer和Cora数据集上, GeVI.v2效果最好; 在PubMed数据集上, 当训练数据小于20%时, GeVI.v2取得最优的效果, 当训练数据大于20%时, GeVI.v1取得最优的效果.

Table 4 Micro-F1 and macro-F1 score on Citeseer dataset 表 4 在Citeseer数据集上的micro-F1值和macro-F1值

Table 5 Micro-F1 and macro-F1 score on Cora dataset 表 5 在Cora数据集上的micro-F1值和macro-F1值

Table 6 Micro-F1 and macro-F1 score on PubMed dataset 表 6 在Pubmed数据集上的micro-F1值和macro-F1值

η为使用到的训练样本的比例.从表 4~表 6中可以观察到.

1)   相对于基线方法, GeVI模型在训练数据少的情况下具有更大的优势.大部分基线方法随着h的下降, 性能迅速变差.因为这些方法学习到的图表示中含有大量的噪声, 且训练数据与测试数据之间存在不一致性; 相反地, 由于GeVI模型同时利用了网络信息和节点特征, 因此学到的图表示存在更少的噪声, 数据之间的一致性更强;

2)   在Citeseer和Cora数据集上, GeVI.v2模型性能最好.在Citeseer数据集上, 以Micro-F1为评价标准, GeVI.v2模型比最好的基线方法相对提高了3.34%(η=50%)~6.25%(η=5%); 以Macro-F1为评价标准, 相对提高了3.75%(η=50%)~7.20%(η=5%);

3)   在Cora数据集上, 以Micro-F1为评价标准, GEVI.V2模型比最好的基线方法相对提高了5.33% (η=50%)~12.03%(η=3%); 以Macro-F1为评价标准, 相对提高了5.69%(η=40%)~13.25%(η=3%).这充分表明本文提出算法的稳定性和有效性;

4)   在PubMed数据集上, 虽然GeVI模型均比所有对比方法好, 但相比于数据集Citeseer和Cora, GeVI模型在PubMed上的优势没这么明显.随着η的提高, GeVI模型与对比方法之间的性能差别迅速减小.特别地, 对于GeVI.v2模型, 以Micro-F1为性能评价指标, 性能提高的幅度从14.95%(η=3%)下降到0.72% (η=50%); 以Macro-F1为性能评价指标, 性能提高的幅度从20.09%(η=3%)下降到0.12%(η=50%).此外, 当η > 20%的时候, GeVI.v1模型的性能比GeVI.v2的好.这是因为对于Pubmed而言, 节点特征在图分类任务中比网络信息更重要(在对比方法中, SVD分解在大多数情况下均比其他方法好), 相对于GeVI.v2方法, GeVI.v1方法在对内容信息提取方面的损失更少; 同时, 由于pubmed数据量足够(当训练样本达到20%时, 样本总量可以达到3 400), 因此虽然GeVI.v1方法得到的节点向量维度较高, 但随着数据量的增加, GeVI.v1方法还是获得了较稳定、一致的提升.

5)   综上, 我们可以发现如下规律:当节点数量比较少的时候, 应该将节点本身作为其邻居, 然后学习出统一的图表示(GeVI.v2);当节点数量很多, 而且节点特征很重要的时候, 为了最大限度地保留节点特征, 我们将节点本身从其邻居中去掉, 然后将学习到的输入向量与其节点特征进行拼接, 作为图表示(GeVI.v1).

4 总结

通过将节点特征作为先验知识, 并令当前节点解释邻居节点, 本文提出了融合网络信息和节点特征的图表示学习方法.为了将当前结点特征更好地融合到节点表示中, 我们提出了两种具体实现方案, 即:

(1)    GeVI.v1:不把节点本身作为其邻居, 最后通过将学习到的表示向量与其本身的特征向量进行拼接作为图表示;

(2)    GeVI.v2:将节点本身作为其邻居, 学习到的表示向量直接作为图表示.

实验结果表明了这两种方法均比对比的基线方法效果好.具体地, 当节点数量不多, 网络信息与节点特征的重要性差不多的时候, 第2种融合方案GeVI.v2更好; 当节点数量比较多, 节点特征很重要的时候, 第1种融合方案GeVI.v1更优.在未来的工作中, 我们将进一步考虑更高效的网络信息的利用方法, 比如通过Node2vec获取网络信息, Node2vec通过结合深度优先和广度优先两种游走方法, 以更充分地利用网络信息.此外, 还将进一步研究在某些图中可能存在部分节点特征缺失的情况.本文提出的方法也可以扩展到其他的表示学习领域, 比如自然语言处理中的词嵌入表示学习, 例如, 利用类似于本文提出的方法将单词的附加属性嵌入到其表示中.

参考文献
[1]
Sen P, Namata G, Bilgic M, Getoor L, Galligher B, Eliassi-Rad T. Collective classification in network data. AI Magazine, 2008, 29(3): 93. [doi:10.1609/aimag.v29i3.2157]
[2]
Zhou DY, Huang JY, Scholkopf B. Learning from labeled and unlabeled data on a directed graph. In: Raedt LD, Wrobe S, eds. Proc. of the 22nd Int'l Conf. on Machine Learning. 2005. 1036-1043. [doi: 10.1145/1102351.1102482]
[3]
Bhagat S, Cormode G, Muthukrishnan S. Node classification in social networks. In: Aggarwal C, ed. Proc. of the Social Network Data Analytics. Boston: Springer-Verlag, 2011. 115-148. [doi: 10.1007/978-1-4419-8462-3_5]
[4]
Tu C, Liu Z, Sun M. Inferring correspondences from multiple sources for microblog user tags. In: Huang H, Liu T, Zhang HP, Tang J, eds. Proc. of the Chinese National Conf. on Social Media Processing. Berlin, Heidelberg: Springer-Verlag, 2014. 1-12. [doi: 10.1007/978-3-662-45558-6_1]
[5]
Xing QL, Liu L, Liu YQ, Zhang M, Ma SP. Study on user tags in Weibo. Ruan Jian Xue Bao/Journal of Software, 2015, 26(7): 1626-1637(in Chinese with English abstract). http://www.jos.org.cn/1000-9825/4655.htm[doi: 10.13328/j.cnki.jos.004655]
[6]
Bhuyan MH, Bhattacharyya DK, Kalita JK. Network anomaly detection:Methods, systems and tools. IEEE Communications Surveys & Tutorials, 2014, 16(1): 303–336. [doi:10.1109/SURV.2013.052213.00046]
[7]
Lü L, Zhou T. Link prediction in complex networks:A survey. Physica A:Statistical Mechanics and Its Applications, 2011, 390(6): 1150–1170. [doi:10.1016/j.physa.2010.11.027]
[8]
Liben-Nowell D, Kleinberg J. The link-prediction problem for social networks. Journal of the Association for Information Science and Technology, 2007, 58(7): 1019–1031. [doi:10.1002/asi.20591]
[9]
Yu X, Ren X, Sun Y, Gu Q, Sturt B, Khandelwal U, Norick B, Han J. Personalized entity recommendation: A heterogeneous information network approach. In: Carterette B, ed. Proc. of the 7th ACM Int'l Conf. on Web Search and Data Mining. New York: ACM Press, 2014. 283-292. [doi: 10.1145/2556195.2556259]
[10]
Meng XW, Liu SD, Zhang YJ, Hu X. Research on social recommender systems. Ruan Jian Xue Bao/Journal of Software, 2015, 26(6): 1356-1372(in Chinese with English abstract). http://www.jos.org.cn/1000-9825/4831.htm[doi: 10.13328/j.cnki.jos.004831]
[11]
Liu ZY, Sun MS, Lin YK, Xie RB. Knowledge representation learning:A review. Ji Suan Ji Yan Jiu Yu Fa Zhan/Journal of Computer Research and Development, 2016, 53(2): 247–261(in Chinese with English abstract). [doi:10.7544/issn1000-1239.2016.20160020]
[12]
Roweis ST, Saul LK. Nonlinear dimensionality reduction by locally linear embedding. Science, 2000, 290(5500): 2323–2326. [doi:10.1126/science.290.5500.2323]
[13]
Belkin M, Niyogi P. Laplacian eigenmaps and spectral techniques for embedding and clustering. In: Suzanna B, Sebastian T, Klaus O, eds. Proc. of the Advances in Neural Information Processing Systems. Cambridge: MIT Press, 2002. 585-591.
[14]
Chen M, Yang Q, Tang X. Directed graph embedding. In: Rajeev S, Mehta H, Bagga RK, eds. Proc. of the IJCAI. San Francisco: Morgan Kaufmann Publishers Inc., 2007. 2707-2712.
[15]
Tang L, Liu H. Relational learning via latent social dimensions. In: Osmar RZ, ed. Proc. of the 15th ACM SIGKDD Int'l Conf. on Knowledge Discovery and Data Mining. New York: ACM Press, 2009. 817-826. [doi: 10.1145/1557019.1557109]
[16]
Le TM, Lauw HW. Probabilistic latent document network embedding. In: Kumar R, ed. Proc. of the IEEE Int'l Conf. on Data Mining (ICDM). Shenzhen: IEEE, 2014. 270-279. [doi: 10.1109/ICDM.2014.119]
[17]
Jacob Y, Denoyer L, Gallinari P. Learning latent representations of nodes for classifying in heterogeneous social networks. In: Carterette B, ed. Proc. of the 7th ACM Int'l Conf. on Web Search and Data Mining. New York: ACM Press, 2014. 373-382. [doi: 10.1145/2556195.2556225]
[18]
Bourigault S, Lagnier C, Lamprier S, Denoyer L, Gallinari P. Learning social network embeddings for predicting information diffusion. In: Carterette B, ed. Proc. of the 7th ACM Int'l Conf. on Web Search and Data Mining. New York, 2014. 393-402. [doi: 10.1145/2556195.2556216]
[19]
Nallapati RM, Ahmed A, Xing EP, Cohen WW. Joint latent topic models for text and citations. In: Li Y, Liu B, Sarawagi S, eds. Proc. of the 14th ACM SIGKDD Int'l Conf. on Knowledge Discovery and Data Mining. New York: ACM Press, 2008. 542-550. [doi: 10.1145/1401890.1401957]
[20]
Chang J, Blei D. Relational topic models for document networks. In: Dyk DV, Welling M, eds. Proc. of the Int'l Conf. on Artificial Intelligence and Statistics. Florida: PMLR, 2009. 81-88.
[21]
Le T, Lauw HW. Probabilistic latent document network embedding. In: Kumar R, ed. Proc. of the 2014 IEEE Int'l Conf. on Data Mining (ICDM). Shenzhen: IEEE, 2014. 270-279. [doi: 10.1109/ICDM.2014.119]
[22]
Perozzi B, Al-Rfou R, Skiena S. Deepwalk: Online learning of social representations. In: Perlich C, Saka E, Shen D, Lee K, Li Y, eds. Proc. of the 20th ACM SIGKDD Int'l Conf. on Knowledge Discovery and Data Mining. New York: ACM Press, 2014. 701-710. [doi: 10.1145/2623330.2623732]
[23]
Grover A, Leskovec J. node2vec: Scalable feature learning for networks. In: Proc. of the 22nd ACM SIGKDD Int'l Conf. on Knowledge Discovery and Data Mining. ACM Press, 2016. 855-864. [doi: 10.1145/2939672.2939754]
[24]
Tang J, Qu M, Wang M, Zhang M, Yan J, Mei Q. Line: Large-Scale information network embedding. In: Gangemi A, ed. Proc. of the 24th Int'l World Wide Web Conf. on Steering Committee Republic and Canton of Geneva. 2015. 1067-1077. [doi: 10.1145/2736277.2741093]
[25]
Yang C, Liu Z, Zhao D, Sun M, Chang EY. Network representation learning with rich text information. In: Yang Q, Wooldridge M, eds. Proc. of the IJCAI. 2015. 2111-2117.
[26]
Yang Z, Cohen WW, Salakhutdinov R. Revisiting semi-supervised learning with graph embeddings. In: Balcan MF, Weinberger KQ, eds. Proc. of the 33rd Int'l Conf. on Machine Learning (ICML 2016). New York: JMLR. org, 2016. 40-48.
[27]
Chojnacki W, Brooks MJ. A note on the locally linear embedding algorithm. Int'l Journal of Pattern Recognition and Artificial Intelligence, 2009, 23(8): 1739–1752. [doi:10.1142/S0218001409007752]
[28]
Newman ME. Modularity and community structure in networks. Proc. of the National Academy of Sciences, 2006, 103(23): 8577–8582. [doi:10.1073/pnas.0601602103]
[29]
Iwata T, Saito K, Ueda N, Stromsten S, Griffiths TL, Tenenbaum JB. Parametrice mbedding for class visualization. Neural Computation, 2007, 19(9): 2536–2556. [doi:10.1162/neco.2007.19.9.2536]
[30]
Mikolov T, Sutskever I, Chen K, Corrado GS, Dean J. Distributed representations of words and phrases and their compositionality. In: Burges CJC, Bottou L, Welling M, Ghahramani Z, Weinberger KQ, eds. Proc. of the Advances in Neural Information Processing Systems. MIT Press, 2013. 3111-3119.
[5]
邢千里, 刘列, 刘奕群, 张敏, 马少平. 微博中用户标签的研究. 软件学报, 2015, 26(7): 1626-1637. http://www.jos.org.cn/1000-9825/4655.htm[doi: 10.13328/j.cnki.jos.004655]
[10]
孟祥武, 刘树栋, 张玉洁, 胡勋. 社会化推荐系统研究. 软件学报, 2015, 26(6): 1356-1372. http://www.jos.org.cn/1000-9825/4831.htm[doi: 10.13328/j.cnki.jos.004831]
[11]
刘知远, 孙茂松, 林衍凯, 谢若冰. 知识表示学习研究进展. 计算机研究与发展, 2016, 53(2): 247–261. [doi:10.7544/issn1000-1239.2016.20160020]