«上一篇 下一篇»
  计算机工程  2020, Vol. 46 Issue (6): 81-87  DOI: 10.19678/j.issn.1000-3428.0053895
0

引用本文  

唐素勤, 刘笑梅, 袁磊. 嵌入双曲层的神经排序式图表示学习方法[J]. 计算机工程, 2020, 46(6), 81-87. DOI: 10.19678/j.issn.1000-3428.0053895.
TANG Suqin, LIU Xiaomei, YUAN Lei. Graph Representation Learning Method Based on Neural Ranking with Embedded Hyperbolic Layer[J]. Computer Engineering, 2020, 46(6), 81-87. DOI: 10.19678/j.issn.1000-3428.0053895.

基金项目

国家自然科学基金(61967002,61663004,61662007,61866004);国家哲学社会科学基金教育学一般项目(BCA170081);广西自然科学基金(2016GXNSFAA380146,2017GXNSFAA198365)

作者简介

唐素勤(1972-), 女, 教授、博士, 主研方向为本体理论、知识图谱;
刘笑梅, 硕士研究生;
袁磊, 教授、博士

文章历史

收稿日期:2019-02-07
修回日期:2019-05-13
嵌入双曲层的神经排序式图表示学习方法
唐素勤a,b , 刘笑梅b , 袁磊a     
a. 广西师范大学 教育学部, 广西 桂林 541004;
b. 广西多源信息挖掘与安全重点实验室, 广西 桂林 541004
摘要:为解决已有图表示学习方法复杂性较高的问题,提出一种能在维持图特征表达力的同时提升学习效率的方法。通过在神经网络表示模型中设置适当的双曲几何结构捕获图数据的基本属性,利用贝叶斯个性化排序目标最大化节点之间正确链接和错误链接的差距从而自动学习相似性信息,在所设计的神经排序模型中使用双曲距离函数计算节点之间的层次距离。在此基础上,基于黎曼梯度下降法学习节点的特征向量。实验结果表明,相对DNGR、HARP等方法,该方法能够高效地学习节点特征,而且能获得更加紧凑、更具表达力的特征向量表示。
关键词图表示学习    双曲几何    双曲面模型    神经网络    贝叶斯个性化排序    
Graph Representation Learning Method Based on Neural Ranking with Embedded Hyperbolic Layer
TANG Suqina,b , LIU Xiaomeib , YUAN Leia     
a. Faculty of Education, Guangxi Normal University, Guilin, Guangxi 541004, China;
b. Guangxi Key Lab of Multi-Source Information Mining and Security, Guangxi Normal University, Guilin, Guangxi 541004, China
Abstract: To address the high complexity of existing graph representation learning methods, this paper proposes a new graph representation learning method to improve the learning efficiency while maintaining the representation performance of graph features.The method captures the basic properties of graph data by establishing appropriate hyperbolic geometry structure in the neural network representation model.Then the Bayesian Personalized Ranking(BPR) target is used to maximize the gap between the correct links and the wrong links to automatically learn the similarity information.Moreover, the hyperbolic distance function is used to calculate the hierarchical distance between the nodes in the designed neural ranking model.Finally, the model uses the Riemannian gradient descent method to learn the feature vector of nodes.Experimental results show that the proposed method can efficiently learn node features, and can provide more compact and more expressive feature vector representations than DNGR, HARP and other methods.
Key words: graph representation learning    hyperbolic geometry    hyperboloid model    neural network    Bayesian Personalized Ranking(BPR)    
0 概述

网络图包含一组相互连接的节点, 其中, 每对节点之间具有大量的关系信息[1]。几乎每个领域都需要对图进行分析, 例如, 在生物网络中, 人们可能需要分类蛋白质的角色, 或者预测现有药物分子的新应用; 在社交网络中, 需要有针对性地向用户投放广告或推荐新朋友等。因此, 研究人员开发了各种图数据挖掘算法应用于节点分类、标签推荐、异常检测和链接预测等任务。但是, 这些已有的图数据挖掘算法通常需要一组图特征信息作为算法的输入。例如, 为了从图中提取结构信息, 传统的方法通常依靠图的相关统计(如度、聚集系数等)、核函数或手工特征来测量局部近邻结构[2], 然而这些手工设计的特征在学习过程中不能自适应, 且需要大量的人力成本和专业知识[3]。因此, 有学者提出了表示学习方法以避免耗时且成本昂贵的特征设计, 该方法同时提高了特征的灵活性。

现有的图表示学习方法主要聚焦于为图数据设计新的神经网络模型或设计更加复杂的随机游走机制来探索网络结构, 这些方法往往使图表示学习的复杂性大幅提高。最近, 将数据嵌入非欧几里德空间的方法受到越来越多的关注, 原因是欧几里德模型不能正确地反映复杂数据模式。受此启发, 本文对神经网络表示设置适当的几何结构, 特别是层次结构和聚集行为, 以捕获图数据的基本属性。图数据的这些基本属性出现在许多遵循幂律分布的现实复杂网络场景中, 可作为引入双曲几何的起点。双曲空间能够反映复杂网络的属性主要是由于其潜在的关键属性, 即空间量随着距参考点的距离呈指数增长, 这与欧几里德空间中较慢的多项式增长相反。因此, 本文探索双曲空间是否有助于学习图数据的嵌入, 即通过使用神经网络对相互作用或关系进行建模, 并利用数据所存在的流形度量结构来学习得到节点的低维紧凑特征向量表示。

通过对图表示学习方法和复杂网络中双曲几何理论进行分析, 本文提出一种嵌入双曲层的神经排序式图表示学习方法Neural-HRNE。该方法利用神经网络的无监督端到端方式以及双曲几何的分层自组织能力来自动抽取节点的相似性和层次结构信息。Neural-HRNE方法没有使用过度复杂的节点交互机制, 而是提出一种更小更快的神经排序架构来实现同样的性能。其中, 利用贝叶斯个性化排序(Bayesian Personalized Ranking, BPR)[4]目标来捕获节点表示向量之间的局部拓扑结构相似性。文献[5]研究表明, 在Lorentz模型中学习嵌入比在Poincaré球中更加有效, 其不仅更适用于上下层级关系的建模, 而且能非常有效地执行黎曼优化并避免由Poincaré距离产生的数值不稳定性问题。因此, 在Neural-HRNE方法中, 本文将距离度量转换为所嵌入双曲面模型中的度量, 图中的节点能利用双曲几何特性自组织为分层结构, 从而使得Neural-HRNE方法可以高效地提取节点的潜在特征表示。在学习得到节点的潜在特征向量表示后, 本文在多个不同尺度的数据集上分别进行节点推荐和节点分类任务, 通过对比几种不同空间中的图表示学习方法来验证所提方法的有效性, 并分析其维度敏感性和模型收敛性。

1 相关工作

早期的图表示学习可追溯到2000年, 当时的算法主要将图表示学习作为降维技术的一部分, 通过特征分解图的关联矩阵来得到节点的特征向量。但是, 就节点数量而言, 多数算法通常至少具有二次时间复杂度, 可扩展性较低限制了它们在大规模图上的应用[6]。与特征工程中需要人工设计特征不同, 深度学习会自动从数据中学习特征表示, 这使得特征工程向特征学习转变。近期的图表示学习方法主要集中于为图数据设计新的神经网络模型。DeepWalk[7]首先使用随机游走从输入图中采样一组路径, 将采样的路径类比于来自语料库的句子, 从而利用神经语言模型Skip-Gram学习得到节点的特征向量表示。DeepWalk的成功激发了许多后续的研究, 如Node2vec[8]和LINE[9]等。使用递归神经网络模型GRU来嵌入信息的级联路径以及将邻接矩阵输入到自编码器中重构邻域相似的节点也是较典型的方法。作为另一种流行的深度学习模型, 卷积神经网络及其变体也被广泛应用于图表示学习。自2008年以来, 研究人员聚焦于直接为复杂网络设计有效且可扩展的表示学习技术, 且其表现出了良好的性能并能适用于各种应用[6]

对符号数据的表示学习已成为机器学习和人工智能领域的研究热点[10], 尽管这些方法在许多应用中已被证明可行, 但它们中的大部分都是基于欧几里德嵌入来处理符号数据, 而复杂网络分析中的相关研究表明, 许多真实世界的网络具有潜在的树状层次结构, 这是许多复杂数据集所固有的属性, 如自然语言的幂律分布及社会和语义网络的无标度性。这种树状结构数据的几何形状随着距根的距离呈指数级扩展, 数据可以在双曲空间中被精确地捕获, 但不能在欧几里德空间中被捕获[11]。因此, 将数据嵌入双曲空间(一类具有恒定负曲率的非欧几里德空间)受到越来越多的关注。双曲空间可以看作树的连续版本, 反之, 树可以看作“离散的双曲空间”[12], 在${\mathbb{R}^2}$中, 类似的构造是不可能的, 因为圆的周长(2πr)和面积(πr2)仅在欧几里德几何中分别关于r呈线性和二次方增长。受此启发, 最近的一些研究聚焦于在各种领域开发有效的算法用于在双曲空间中嵌入数据, 包括自然语言处理和网络科学等。例如, 文献[12]开发了一个使用双曲空间建模复杂网络的几何框架, 并通过假设网络具有双曲几何来呈现典型属性, 如异构度分布和强聚类。此外, 文献[10]将符号数据嵌入到一个n维Poincaré球中, 用于学习分层表示, 结果表明Poincaré嵌入优于欧几里德嵌入。文献[5]研究表明, 在Lorentz模型中学习嵌入比在Poincaré球模型中学习更加有效, 其将这种概念系统的层级关系建模为相关性和一般性的组合以学习偏序关系。文献[13]提出一种嵌入有向无环图的新方法, 其使用测地凸锥在嵌入空间中引起偏序关系来扩展Poincaré嵌入从而建模不对称关系。文献[14]提出基于Skip-Gram的双曲空间中图的神经嵌入算法。文献[15]以无监督方式从文本语料库中学习双曲空间中的单词和句子的蕴涵嵌入。与欧几里德嵌入相比, 使用具有少量维度的双曲嵌入能在诸多方面实现良好的性能, 例如, 回答词语的语义查询或复杂网络中的链接预测[11]。上述结果表明, 更好地考虑数据的固有几何形状可以改善下游预测效果。

2 模型构建

本文的图表示学习方法Neural-HRNE利用BPR来捕获节点之间的局部拓扑结构相似性, 并通过双曲几何中的双曲面模型来有效探索图的拓扑结构信息, 特别是层级结构。模型的整体架构如图 1所示, 该模型使用的神经网络结构主要包括输入层、嵌入层、隐藏层、双曲层、输出层和BPR层。具体而言, 模型具有共享参数的2个部分, 即一个接受正确的节点链接, 另一个接受错误的节点链接, 并旨在最大化正确链接和错误链接之间的差距。其中, 嵌入层根据节点的局部邻居结构学习节点的统一矢量表示, 隐藏层应用非线性降维嵌入节点的向量, 双曲层使用双曲面模型来探索图的层次结构信息, 即通过嵌入空间中的双曲面距离来建模节点对之间的关系, 输出层和BPR层通过反向传播开启模型推断。

Download:
图 1 Neural-HRNE模型整体架构 Fig. 1 Overall structure of the Neural-HRNE model
2.1 输入层和嵌入层

Neural-HRNE的训练以节点三元组(u, i, j)作为输入, 即给定节点u及其正确邻域i和随机采样的损坏邻域j作为样本。每个节点都表示为一个独热向量nu(代表图$\mathcal{G}$中的节点), 然后通过嵌入层进行索引, 因此, 嵌入层是一个具有嵌入矩阵$\mathit{\boldsymbol{P}} \in {\mathbb{R}^{\left\| V \right\| \times d}}$的查找层, P的每一行嵌入节点的特征信息, 其中, d为嵌入维度。通过索引到节点, 嵌入矩阵P将每个节点转换为低维向量, 如下:

$ \mathit{\boldsymbol{f}} = {\rm LOOKUP}(\mathit{\boldsymbol{P}},{\mathit{\boldsymbol{n}}_u}) $ (1)

在具体实现过程中, 本文使用预训练节点嵌入来初始化嵌入层, 嵌入矩阵P在学习过程中迭代更新。

2.2 隐藏层

给定图$\mathcal{G}$中节点u的嵌入向量${\mathit{\boldsymbol{f}}_u} \in {{\mathbb{R}}^{1 \times d}}$, 隐藏层的目的是将其嵌入向量转换为另一种表示hu, 以实现非线性降维。给定fu, 隐藏层通过式(2)产生${\mathit{\boldsymbol{h}}_u} \in {{\mathbb{R}}^{1 \times h}}$:

$ \mathit{\boldsymbol{h}}_u^{\rm T} = {\mathop{\rm ReLU}\nolimits} ({\mathit{\boldsymbol{W}}_h}\mathit{\boldsymbol{f}}_u^{\rm T} + {\mathit{\boldsymbol{b}}_h}) $ (2)

激活函数使用线性整流函数ReLU(x), 定义max(0, x)作为实现快速收敛的激活函数。参数${\mathit{\boldsymbol{W}}_h} \in {{\mathbb{R}}^{h \times d}}$${\mathit{\boldsymbol{b}}_h} \in {{\mathbb{R}}^{h \times 1}}$分别是隐藏层的权值和偏置, h表示隐藏层中神经元的数量。在隐藏层中, 所有节点共享一组参数{Wh, bh}, 从而实现跨不同节点的信息共享。

2.3 双曲层

双曲层采用双曲面模型来建模节点对之间的关系, 这种n维双曲空间模型是n+1维Minkowski空间中的一个流形。Minkowski空间由公式${\left\langle {x,y} \right\rangle _\mathcal{H}} = - {x_0}{y_0} + \sum\limits_{i = 1}^n {{x_n},{y_n},x,y \in } {\mathbb{R}^{n + 1}}$所定义。n维双曲面模型${\mathcal{H}^n}$位于${\mathbb{R}^n+1}$内部, 作为相对于Minkowski内积${\mathcal{H}^n} = \left\{ {x \in {\mathbb{R}^{n + 1}}:{{\left\langle {x,x} \right\rangle }_\mathcal{H}} = - 1,{x_0}>0} \right\}$的单位“球体”的上半部分。因此, 本文将n维双曲面模型定义为黎曼流形$({\mathcal{H}^n},{\mathit{\boldsymbol{g}}_\ell })$, 其中:

$ {\mathit{\boldsymbol{g}}_\ell } = \left[ \begin{array}{l} - 1\\ \ \ \ \ \ \ \ 1\\ \ \ \ \ \ \ \ \ \ddots \\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ 1 \end{array} \right] $ (3)

${\mathcal{H}^n}$中两点之间的距离定义为连接两点的双曲面上的测地路径的长度。${\mathcal{H}^n}$中的每个测地曲线(即双曲线)都是${\mathcal{H}^n}$与2D平面之间的交线, 该平面穿过外围欧几里德空间${\mathbb{R}^n+1}$中的原点。${\mathcal{H}^n}$上的相关距离函数为:

$ {d_\ell }(x,y) = {\rm \arccos h}( - {\left\langle {x,y} \right\rangle _\mathcal{H}}) $ (4)

因此, 双曲层将节点之间的双曲距离定义为:

$ {d_\ell }({\mathit{\boldsymbol{h}}_u},{\mathit{\boldsymbol{h}}_i}) = {\rm \arccos h}( - {\left\langle {{\mathit{\boldsymbol{h}}_u},{\mathit{\boldsymbol{h}}_i}} \right\rangle _\mathcal{H}}) $ (5)
2.4 输出层和BPR层

Neural-HRNE方法通过式(6)的线性变换传递双曲距离:

$ s({\mathit{\boldsymbol{h}}_u},{\mathit{\boldsymbol{h}}_i}) = {\mathit{\boldsymbol{W}}_s}d({\mathit{\boldsymbol{h}}_u},{\mathit{\boldsymbol{h}}_i}) + {\mathit{\boldsymbol{b}}_s} $ (6)

其中, ${\mathit{\boldsymbol{W}}_s} \in {\mathbb{R}^1}$${\mathit{\boldsymbol{b}}_s} \in {\mathbb{R}^1}$是该层的标量参数。节点ui之间的相似度分数定义为sui, 通过式(6)计算。

BPR层实现贝叶斯个性化排序目标。对于嵌入任务, 排序目标是图中的相邻节点在嵌入空间中应该具有比非相邻节点更高的相似度向量表示。例如, 2个相邻节点ui之间的相似度得分应该大于2个不相邻节点uj之间的相似度得分。如图 1所示, 给定节点三元组(u, i, j), Neural-HRNE使用sigmoid函数$\sigma (x) = \frac{1}{{1 + {{\rm e}^{ - x}}}}$为保留排序顺序sui>suj的概率建模, 在数学上表示为:

$ P({s_{ui}}>{s_{uj}}) = \sigma ({s_{ui}} - {s_{uj}}) = \frac{1}{{1 + {{\rm e}^{ - ({s_{ui}} - {s_{uj}})}}}} $ (7)

如式(7)所示, suisuj之间的差异越大, 排序顺序sui>suj被保留的可能性就越大。假定从图$\mathcal{G}$生成的所有基于三元组的排序顺序是独立的, 所有排序顺序被保留的概率定义如下:

$ \prod\limits_{(u,i,j) \in \mathcal{D}} {P({s_{ui}}>{s_{uj}})} = \prod\limits_{(u,i,j) \in \mathcal{D}} {\sigma ({s_{ui}} - {s_{uj}})} $ (8)

其中, $\mathcal{D}$表示从图$\mathcal{G}$生成的训练三元组集合。

Neural-HRNE方法的嵌入目标是最大化式(8)。为了便于计算, 最小化负对数似然损失函数的和, 如下:

$ \mathcal{L}(\mathit{\boldsymbol{ \boldsymbol{\varTheta} }}) = - \prod\limits_{(u,i,j) \in \mathcal{D}} {{\rm\ln} \sigma ({s_{ui}} - {s_{uj}}) + \lambda \cdot \left\| \mathit{\boldsymbol{ \boldsymbol{\varTheta} }} \right\|_F^2} $ (9)

其中, Θ={P, Wh, bh, Ws, bs}是在所有不同层中使用的模型参数, ${\lambda \cdot \left\| \mathit{\boldsymbol{ \boldsymbol{\varTheta} }} \right\|_F^2}$是防止模型过度拟合的正则项。

2.5 优化和学习

本文利用在Lorentz嵌入[5]中基于黎曼随机梯度下降所推导的梯度下降算法(算法1)来估算参数θ。在黎曼优化中, 通常需要解决形式为$\mathop {{\rm \min} }\limits_{\theta \in M} f(\theta )$的问题, 在本文中即最小化BPR损失$\mathcal{L}(\mathit{\boldsymbol{ \boldsymbol{\varTheta} }})$, 通过计算θt+1=expθt(-η grad f(θt))更新参数θ, 其中, grad f(θt)∈TθM表示黎曼梯度, η表示学习率。算法的具体推导过程可参见文献[5]。

算法1  Riemannian Stochastic Gradient Descent

Input learning rate η, number of epochs T

for t=1, 2, …, T

ht$g_\ell ^{ - 1}$▽f(θt)

grad f(θt)←projθt(ht)

θt+1←expθt(-η grad f(θt))

Neural-HRNE方法采用反向传播算法, 利用mini-batch梯度下降来优化模型中的参数Θ={P, Wh, bh, Ws, bs}。mini-batch梯度下降的主要过程是:首先从图$\mathcal{G}$中抽取一批三元组, 具体来说, 给定一个任意节点u, 采样它的邻居i中的一个节点, 即$i \in \mathcal{N}(u)$, 其概率与边权重wij成比例, 同时采样其非相邻节点j, 即$j \notin \mathcal{N}(u)$, 概率与图中的节点度成比例; 然后对于每个mini-batch训练三元组, 通过使用链式规则, 根据算法1来更新相应参数Θ, 另外, 给定训练所需的三元组集合$\mathcal{D}$和嵌入维度d, 计算和更新P中相应嵌入向量的总成本是O(d)。类似地, 计算和更新隐藏层中参数{Wh, bh}的总成本是O(hd+h), h为隐藏层神经元个数。因此, Neural-HRNE方法迭代一次的总计算复杂度为$\left| \mathcal{D} \right| \cdot (O(d) + O(hd + h))$

3 实验结果与分析

将本文方法与现有学习方法进行比较, 其中, 选取一些常见的具有明确上下级层次结构的概念网络以及未明确编码对象层次结构关系的基准图数据集, 以评估各方法的节点推荐和节点分类任务效果, 最后分析各方法在不同表示学习空间中的性能, 即在欧几里德、Poincaré和双曲面模型中分析各方法对维度的敏感性和模型的收敛性。

3.1 实验设置

本文考虑具有明确上下级层次结构的数据和非树状的有向无环图结构, 数据集的相关统计信息如表 1所示。其中:

下载CSV 表 1 数据集的相关统计信息 Table 1 Relevant statistics of dataset

1) WordNet[16]是一个庞大的英文词汇数据库, 在WordNet中, 名词、动词、形容词和副词各自被组成一个同义词网络, 每个同义词集合都代表一种基本的语义概念, 本文嵌入WordNet的名词和动词层次结构。

2) ACM计算分类系统CCS[17]是由ACM计算机协会设计的用于分类计算机主题的系统, 其可看作一种分层本体, 各种ACM期刊使用该系统来按领域组织主题。

3) DBLP是来自DBLP数据集[18]的作者网络, 其中包括共同作者、作者引用和文本相似性视图。本文抽取DBLP中的研究人员的共同作者图, 其标签表明研究人员发表其研究成果的领域, 本文选择其中的“数据库”“数据挖掘”“信息检索”和“机器学习”4个不同的研究领域作为标签。

4) PPI是蛋白质分子之间构建的蛋白质-蛋白质相互作用网络[19]。本文使用PPI网络的智人诱导子图, 只有人类基因被保留为节点。Hallmark基因集中提供的基因组被视为节点的类别并代表蛋白质生物状态。

5) Wikipedia[20]是一个维基百科中储存前100万字节中单词的共现网络。在该数据集中, 每个节点都是一个单词, 每条边是单词之间的共现关系, 每个节点都有一个标签, 表示单词的POS词性。

在对比实验中, 所有方法均只使用节点的拓扑结构特征, 选取一些基于欧几里德的神经网络嵌入和基于双曲空间的图嵌入方法。本文将Neural-HRNE双曲层中的双曲面度量替换为欧几里德和Poincaré度量并以此来作为其中的对比基线。对比方法具体如下:

1) DNGR[21]采用随机冲浪策略来捕获图结构信息, 并进一步将这些结构信息转换为正点互信息矩阵, 然后训练堆栈降噪自编码器以学习节点表示。

2) HARP[22]递归地合并原始图中的节点和边以获得具有相似性的一系列较小的连续图结构体, 合并的图均具有不同的粒度, 从而提供了原始图的全局结构视图。HARP可作为一种通用的元策略来改进图嵌入算法, 本文选取文献[22]中表现较好的HARP(N2V)方法, 其结合了Node2vec算法用于加强节点嵌入。

3) 文献[14]提出了一种双曲空间中图的神经嵌入算法, 其采用与DeepWalk类似的方法, 不同的是该算法不再使用欧几里德度量, 而使用Poincaré度量并在双曲空间中通过反向传播来学习节点的向量表示。

4) 文献[13]提出一种基于黎曼流形的“测地线凸锥”模型来学习层次嵌入, 其有效解决了Order嵌入[23]和Poincaré嵌入[10]中嵌入空间维度灾难、不能编码不对称关系和Poincaré球边界坍塌问题。

5) 为了研究本文双曲面度量对节点嵌入的影响, 首先将Neural-HRNE方法中的距离度量(式(4))改为直接计算欧几里德距离, 即d=║u-v2, 并将其命名为EuclideanEmb。然后将Neural-HRNE方法中的距离度量改为文献[10]中的Poincaré距离, 并使用其中的黎曼梯度下降来学习节点嵌入, 将其命名为PoincaréEmb。其他设置则保持原样。

本文嵌入模型中有若干用户定义的超参数。其中, 隐藏层中的神经元数量设置为150, 嵌入模型中的正则化系数λ设置为0.000 05。在模型学习和优化过程中, 设置学习率η为0.5, 批量大小定为100。对于其他对比方法, 使用网格搜索从集合{0.01, 0.001, 0.000 1}中选择正则化系数, 并从集合{0.01, 0.05, 0.1, 0.5}中选择学习率。对于其余的超参数, 本文使用各方法在原文中所建议的默认参数值。设置所有节点的表示维度为50维。

3.2 节点推荐

节点推荐可用于相似性搜索等领域, 其任务是根据自身的上下文向用户推荐感兴趣的对象。在现实场景中, 推荐的节点有各种类型, 如用户兴趣、社交朋友和查询文档等。使用表示学习的低维矢量通常比原始表示密集得多, 这减轻了较多数据的稀疏性问题, 使得查询任务更加简单和准确。

根据多数图表示学习中的评估方法, 本文对于给定的查询节点, 计算目标节点与查询节点间的距离并对目标节点进行排序。在实验中, 评估本文所提方法在嵌入明确或隐含层级结构数据上的有效性。在评估过程中, 本文分别使用上述5个数据集来评估嵌入质量, 并将数据视为无向传递闭包, 这样的分层结构不能从观察到的边直接得出, 而需要被推断出来。为了测量嵌入质量, 本文计算每个观察到的边(u, v)在嵌入空间中的相应距离d=(u, v), 并按升序排列u的所有未观察到的边的距离, 即{d=(u, v′):(u, v′)∈D}, 得到原始的正确元组排名(越低越好), 然后计算所有正确节点的前50平均精度均值MAP@50, 结果如表 2所示, 其中, 最优结果加粗表示。

下载CSV 表 2 MAP@50结果对比 Table 2 Comparison of MAP@50 results

表 2可以看出, 因为双曲几何的分层自组织能力, 其所选择的使用双曲空间的表示学习方法比欧几里德空间中的方法更加有效, 特别是当学习的特征维度较低时, 双曲几何能得到更加紧凑的表示, 所以能够更好地在有限空间中表示复杂函数。相比于双曲几何强层次嵌入方法, 本文方法也表现出了较好的表达力, 显示出其性能优势。

3.3 节点分类

节点分类通过在标记的节点嵌入集上应用分类器来进行训练, 即给定未标记节点的特征向量表示, 训练的分类器可以预测其类标签。由于WordNet是一个词典且CCS通常作为分类法使用, 没有可利用标签, 因此本文仅使用DBLP、PPI和Wikipedia数据集来评估嵌入表示的监督学习任务效果, 即节点分类的有效性。

本文从数据集中随机抽取不同比例的标记节点, 并将它们用作训练数据, 其余的作为测试数据。对于欧几里德模型, 本文使用LibLinear库中的one-vs-rest SVM分类器预测每个节点最可能的标签, 而对于双曲模型, 本文使用基于双曲距离的内核训练SVM分类模型。重复上述过程10次, 表 3表 4所示为DBLP、PPI和Wikipedia数据集中的各方法平均性能表现, 最优结果加粗表示。

下载CSV 表 3 DBLP数据集上的准确率对比 Table 3 Accuracy comparison on DBLP dataset 
下载CSV 表 4 PPI和Wikipedia数据集上的节点多标签分类Macro-F1结果 Table 4 Macro-F1 results of node multi label classification on PPI and Wikipedia datasets 

表 3表 4可以看出, 相比于经典的基于欧几里德空间的方法, 双曲几何对于数据的层次结构特征抽取更加有效, 这有助于轻松高效地处理各种下游图数据分析任务。随着分类训练数据的增加, 各分类器的性能均在不断提高, 而对比于同等情况下使用欧几里德嵌入的EuclideanEmb, 本文提出的图表示学习方法在Poincaré和双曲面模型中性能均有所提高。在同是使用了双曲几何自组织能力的方法中, Neural-HRNE的结果基本持平或略微降低, 这可能是由于Neural-HRNE中的节点采样策略过于简单, 未探索到节点之间诸如同质性或结构等价性的关系, 或者所设计的神经网络较为浅层并直接使用了One-hot来初始化该神经网络, 导致方法学习性能有所降低。因此, 下一步考虑探索结合复杂网络和机器学习的更加高效的采样策略和更加强健的神经网络, 以提高Neural-HRNE方法的性能。

3.4 模型性能分析

为了进一步说明双曲面模型对图表示学习性能的影响, 本文选取仅改变双曲层设置的表示学习方法进行比较。具体地, 分别在EuclideanEmb、PoincaréEmb和Neural-HRNE方法中测试模型对表示学习维度的敏感性和模型的收敛性。图 2所示为不同空间学习方法在WordNet名词层的维度敏感性和收敛性。图 2(a)为仅改变表示学习的维度后对WordNet名词层的节点推荐结果MAP@50的影响, 从中可以看出, 相比于欧几里德几何, 双曲几何对空间的使用效率更高, 欧几里德嵌入在维度较低时对特征的表达能力较弱, 而双曲几何能在较低的维度时依然具有较好的表现性能, 双曲几何大约在50维时就趋于稳定, 其比欧几里德更能提供紧凑的特征向量表示。图 2(b)为EuclideanEmb、PoincaréEmb和Neural-HRNE模型在50维时对WordNet名词层中节点特征表示学习的收敛情况。从中可以看出, 本文提出的神经排序网络大约在10个时期内收敛, 与欧几里德嵌入相比, 双曲几何的嵌入方法收敛更快, 损失误差更低。

Download:
图 2 3种方法在WordNet名词中的维度敏感性和 Fig. 2 Comparison of dimensional sensitivity and model convergence results of three methods in WordNet terms

对不同空间中图表示学习方法的维度敏感性和模型收敛性进行分析, 结果表明, 相比于欧几里德嵌入, 双曲几何能提供更高质量的嵌入, 特别是在学习维度较低的情况下。本文提出的双曲面模型表现出与Poincaré模型相当的性能, 且其神经网络模型具有高效的学习能力。

4 结束语

如何对图中的节点进行有效的特征表示一直是图挖掘领域的研究热点。本文提出一种嵌入双曲层的神经排序式图表示学习方法, 以提取节点的相似性和层次结构特性。该方法利用贝叶斯个性化排序作为其目标函数, 并在其中加入一层双曲层来度量节点对之间的局部拓扑结构相似性, 利用黎曼梯度下降来学习更高效的节点特征向量表示。对比使用欧几里德、Poincaré和双曲面模型的不同表示学习方法的性能, 结果表明, 本文所提方法能够更高效地学习节点特征, 而且可以获得更加紧凑、更具表达力的特征向量表示。嵌入双曲空间中的层次结构能很好地获取数据的基础语义, 下一步将探索双曲空间的优化方法以提高嵌入质量并获得更快的收敛速度。此外, 将双曲嵌入有效地整合到下游的任务和应用中, 以及在多关系数据或图像等更复杂的数据嵌入中应用双曲几何理论, 也是今后的研究重点。

参考文献
[1]
YANG Jinji, HU Bo, WANG Xinming, et al. Personalized recommendation algorithm for learning to rank by knowledge graph[J]. Journal of Chinese Computer Systems, 2018, 39(11): 2419-2423.
杨晋吉, 胡波, 王欣明, 等. 一种知识图谱的排序学习个性化推荐算法[J]. 小型微型计算机系统, 2018, 39(11): 2419-2423. DOI:10.3969/j.issn.1000-1220.2018.11.013
[2]
HAMILTON W L, YING R, LESKOVEC J.Representation learning on graphs: methods and applications[EB/OL].[2019-01-10].https://arxiv.org/abs/1709.05584.
[3]
CHEN Weizheng, ZHANG Yan, LI Xiaoming. Network representation learning[J]. Big Data Research, 2015, 1(3): 8-22.
陈维政, 张岩, 李晓明. 网络表示学习[J]. 大数据, 2015, 1(3): 8-22.
[4]
RENDLE S, FREUDENTHALER C, GANTNER Z, et al.BPR: Bayesian personalized ranking from implicit feedback[C]//Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence.Montreal, Canada: AUAI Press, 2009: 452-461.
[5]
NICKEL M, KIELA D.Learning continuous hierarchies in thelorentz model of hyperbolic geometry[C]//Proceedings of the 35th International Conference on Machine Learning.Stockholm, Sweden: JMLR Press, 2018: 3776-3785.
[6]
QI Jinshan, LIANG Xun, LI Zhiyu, et al. Representation learning of large-scale complex information network:concepts, methods and challenges[J]. Chinese Journal of Computers, 2018, 41(10): 2394-2420.
齐金山, 梁循, 李志宇, 等. 大规模复杂信息网络表示学习:概念、方法与挑战[J]. 计算机学报, 2018, 41(10): 2394-2420. DOI:10.11897/SP.J.1016.2018.02394
[7]
PEROZZI B, AL-RFOU R, SKIENA S.Deepwalk: online learning of social representations[C]//Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.New York, USA: ACM Press, 2014: 701-710. 10.1145/2623330.2623732
[8]
GROVER A, LESKOVEC J.Node2vec: scalable feature learning for networks[C]//Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.San Francisco, USA: ACM Press, 2016: 855-864. 10.1145/2939672.2939754
[9]
TANG Jian, QU Meng, WANG Mingzhe, et al.LINE: large scale information network embedding[C]//Proceedings of the 24th International Conference on World Wide Web.Florence, Italy: ACM Press, 2015: 1067-1077. 10.1145/2736277.2741093
[10]
NICKEL M, KIELA D.Poincaré embeddings for learning hierarchical representations[EB/OL].[2019-01-10].https://arxiv.org/pdf/1705.08039.pdf.
[11]
CHO H, DEMEO B, PENG J, et al.Large-margin classification in hyperbolic space[EB/OL].[2019-01-10].https://arxiv.org/abs/1806.00437.
[12]
KRIOUKOV D, PAPADOPOULOS F, KITSAK M, et al. Hyperbolic geometry of complex networks[J]. Physical Review E, 2010, 82(3): 036106. DOI:10.1103/PhysRevE.82.036106
[13]
GANEA O E, BÉCIGNEUL G, HOFMANN T.Hyperbolic entailment cones for learning hierarchical embeddings[C]//Proceedings of the 35th International Conference on Machine Learning.Stockholm, Sweden: JMLR Press, 2018: 1632-1641. https://arxiv.org/abs/1804.01882
[14]
CHAMBERLAIN B P, CLOUGH J, DEISENROTH M P.Neural embeddings of graphs in hyperbolic space[EB/OL].[2019-01-10].https://arxiv.org/abs/1705.10359. https://www.researchgate.net/publication/317240949_Neural_Embeddings_of_Graphs_in_Hyperbolic_Space
[15]
DHINGRA B, SHALLUE C J, NOROUZI M, et al.Embedding text in hyperbolic spaces[C]//Proceedings of the 12th Workshop on Graph-Based Methods for Natural Language Processing.New Orleans, USA: ACL Press, 2018: 59-69.
[16]
MILLER G. WordNet:an electronic lexical database[M]. Cambridge, USA: MIT Press, 1998.
[17]
MIRKIN B G, NASCIMENTO S, PEREIRA L M.Representing a computer science research organization on the ACM computing classification system[C]//Proceedings of the 16th International Conference on Conceptual Structures.Toulouse, France: CEUR-WS Press, 2008: 57-65. https://www.researchgate.net/publication/221649067_Representing_a_Computer_Science_Research_Organization_on_the_ACM_Computing_Classification_System
[18]
TANG Jie, ZHANG Jing, YAO Limin, et al.Arnetminer: extraction and mining of academic social networks[C]//Proceedings of the 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.Las Vegas, USA: ACM Press, 2008: 990-998. 10.1145/1401890.1402008
[19]
STARK C, BREITKREUTZ B J, REGULY T, et al. BioGRID:a general repository for interaction datasets[J]. Nucleic Acids Research, 2006, 34(S): 535-539.
[20]
MAHONEY M.Large text compression benchmark[EB/OL].[2019-01-10].http://mattmaho-ney.net/dc/text.html.
[21]
CAO Shaosheng, LU Wei, XU Qiangkai.Deep neural networks for learning graph representations[C]//Proceedings of the 30th AAAI Conference on Artificial Intelligence.Phoenix, USA: AAAI Press, 2016: 1145-1152. https://dl.acm.org/doi/10.5555/3015812.3015982
[22]
CHEN H, PEROZZI B, HU Y, et al.HARP: hierarchical representation learning for networks[C]//Proceedings of the 32nd AAAI Conference on Artificial Intelligence.New Orleans, USA: AAAI Press, 2018: 2127-2134.
[23]
VENDROV I, KIROS R, FIDLER S, et al.Order-embeddings of imagesand language[EB/OL].[2019-01-10].https://arxiv.org/abs/1511.06361.
Download:
图 1 Neural-HRNE模型整体架构 Fig. 1 Overall structure of the Neural-HRNE model
下载CSV 表 1 数据集的相关统计信息 Table 1 Relevant statistics of dataset
下载CSV 表 2 MAP@50结果对比 Table 2 Comparison of MAP@50 results
下载CSV 表 3 DBLP数据集上的准确率对比 Table 3 Accuracy comparison on DBLP dataset 
下载CSV 表 4 PPI和Wikipedia数据集上的节点多标签分类Macro-F1结果 Table 4 Macro-F1 results of node multi label classification on PPI and Wikipedia datasets 
Download:
图 2 3种方法在WordNet名词中的维度敏感性和 Fig. 2 Comparison of dimensional sensitivity and model convergence results of three methods in WordNet terms
嵌入双曲层的神经排序式图表示学习方法
唐素勤 , 刘笑梅 , 袁磊