开放科学（资源服务）标志码（OSID）：

0 概述

随着互联网和人工智能等信息技术的快速发展，信息量呈指数级的增长，信息过载问题日益突出。为解决这一问题，个性化推荐系统应运而生^[1]。个性化推荐系统根据用户历史行为数据进行建模分析用户偏好，进而为其提供个性化的信息推荐，方便用户获取自身需求的信息^[2-4]。推荐系统在给每位用户提供有针对性的商品信息推荐服务的同时过滤掉了那些用户并不感兴趣的信息，有效地节约了人们的信息筛选时间。个性化推荐系统由于在信息推荐方面的优秀表现，已成为热点研究方向。

随着各类互联网业务的快速发展，各种辅助信息的获取越来越容易，而将这些辅助信息应用于推荐算法中，将提升推荐性能，但这也对推荐算法的建模能力提出新的挑战。基于图模型的推荐算法是当前的热点方向，但是不易融合辅助信息，而网络表示学习(Network Representation Learning，NRL)强大的网络提取能力与基于图模型的推荐算法相结合，能提升算法的可扩展性。总体而言，网络表示学习是以稠密、低维的向量形式表示网络中的各个节点，并使这些低维向量具有表示和推理能力，从而将这些向量作为输入应用于节点分类、链接预测和推荐系统中。

基于上述设计思路，研究人员将网络表示学习技术应用于推荐算法中以提高其建模能力。ZHANG等^[5]利用TransR提取物品的结构化信息，并融合物品的结构化信息、文本信息与视觉信息进行推荐。BARKAN等^[6]借鉴Google提出的Word2vec方法，实现基于物品的协同过滤推荐。ZHOU等^[7]提出一种针对非对称结构的基于随机游走的网络表示学习方法。本文对经典DeepWalk^[8]算法进行改进，面向推荐目标与被推荐对象为相同类型的应用场景，提出一种基于随机游走的网络表示学习推荐算法RANE。

1 相关工作

NRL技术在早期主要是对稀疏高维的节点进行降维表示，包括主成分分析(Principal Component Analysis，PCA)、局部线性嵌入(Locally Linear Embedding，LLE)^[9]、拉普拉斯特征映射^[10]等，但算法复杂度较高且应用条件较严苛，因此很难在大规模的网络中部署应用。随着NRL技术的发展，研究人员致力于将其与推荐算法相结合，因此Word2vec模型^[11]、DeepCrossing模型^[12]等应用于推荐系统的算法模型由此被提出。

Word2vec^[11]模型可以较好地计算词与词之间的相似度，SkipGram模型是其中的词向量训练模型。对于中心词而言，该网络模型在提高上下文单词出现概率的同时降低其他无关单词的出现概率。由于训练网络所使用的词汇表通常很大，如果每次预测上下文之后更新全部词汇表，则会导致过大的计算量，因此需要优化模型加速训练过程。在基于Negative Sampling的SkipGram模型中，对于中心词$ w $规定上下文单词均为正样本，其余单词均为负样本，设由随机游走采样得到的上下文集合为$ \mathrm{C}\mathrm{o}\mathrm{n}\mathrm{t}\mathrm{e}\mathrm{x}\mathrm{t}\left(w\right) $，那么对于一组采样$ <w, \mathrm{C}\mathrm{o}\mathrm{n}\mathrm{t}\mathrm{e}\mathrm{x}\mathrm{t}\left(w\right)> $，最大化目标函数如下：

$ g\left(w\right)=\prod\limits _{u\in \mathrm{C}\mathrm{o}\mathrm{n}\mathrm{t}\mathrm{e}\mathrm{x}\mathrm{t}\left(w\right)}\prod \limits_{x\in \left\{u\right\}\bigcup \mathrm{N}\mathrm{e}\mathrm{g}\left(u\right)}p\left(x\right|w) $

(1)

其中：对于$ w $上下文中每一个单词$ u $都要进行负采样，$ \mathrm{N}\mathrm{e}\mathrm{g}\left(u\right) $表示对$ u $的负采样集合。在$ n $个单词中，$ {w}_{i} $出现的频率为$ f\left({w}_{i}\right) $，则其被采样到的概率如下：

$ P\left({w}_{i}\right)=\frac{f({w}_{i}{)}^{3/4}}{\sum \limits_{j=0}^{n}f({w}_{j}{)}^{3/4}} $

(2)

引入标志位$ {L}^{u}\left(x\right) $，对于正采样$ x\in \left\{u\right\} $，令$ {L}^{u}\left(x\right)=1 $，对于负采样$ x\in \mathrm{N}\mathrm{e}\mathrm{g}\left(u\right) $，令$ {L}^{u}\left(x\right)=0 $，则式(1)中的条件概率表示如下：

$ p\left(x|w\right)={\left[\sigma \left({\boldsymbol{v}}_{w}^{\mathrm{T}}{\boldsymbol{v}}_{x}\right)\right]}^{{L}^{u}\left(x\right)}\cdot {\left[1-\sigma \left({\boldsymbol{v}}_{w}^{\mathrm{T}}{\boldsymbol{v}}_{x}\right)\right]}^{1-{L}^{u}\left(x\right)} $

(3)

其中：$ \sigma $为Sigmoid函数；$ {\boldsymbol{v}}_{w} $表示的是输入词向量与隐藏层权重矩阵乘积的结果；$ {\boldsymbol{v}}_{x} $表示的是输出层权重矩阵中单词$ x $对应某一列，称$ {\boldsymbol{v}}_{x} $为单词$ x $的辅助词向量。扩展到总语料库$ C $，最大化目标函数如下：

$ G=\prod \limits_{w\in C}g\left(w\right) $

(4)

为方便计算，取对数后可得最终的目标函数：

$ \begin{array}{l}\mathcal{L}=\sum \limits_{w\in C} \sum\limits _{u\in \mathrm{C}\mathrm{o}\mathrm{n}\mathrm{t}\mathrm{e}\mathrm{x}\mathrm{t}\left(w\right)} \sum\limits _{x\in \left\{u\right\}\bigcup \mathrm{N}\mathrm{e}\mathrm{g}\left(u\right)}\left\{{L}^{u}\left(x\right)\cdot \mathrm{l}\mathrm{o}{\mathrm{g}}_{a}\sigma \left({\boldsymbol{v}}_{w}^{\mathrm{T}}{\boldsymbol{v}}_{x}\right)\right.+\\ \left.\left[1-{L}^{u}\left(x\right)\right]\mathrm{l}\mathrm{o}{\mathrm{g}}_{a}\left[1-\sigma \left({\boldsymbol{v}}_{w}^{\mathrm{T}}{\boldsymbol{v}}_{x}\right)\right]\right\}&\end{array} $

(5)

DeepWalk^[8]将自然语言处理(Natural Language Processing，NLP)应用于NRL中。DeepWalk将网络中通过随机游走得到固定长度的节点序列看作是NLP中的语句，将序列中的节点看作NLP中的单词，通过实验表明由随机游走得到的节点序列组成的语料库与NLP的语料库具有相似的幂律分布特性^[8]，对应真实网络的小世界特性说明该节点序列能有效描述网络结构信息，进而使用Word2vec中的SkipGram模型进行网络中节点的表示学习，并通过Hierarchical Softmax模型加速训练过程。

Node2vec^[13]算法在DeepWalk基础上进行改进，在DeepWalk中随机游走是从当前节点的邻居节点中随机均匀地选取下一个节点，而Node2vec设计了两个参数p和q，p控制跳向上一个节点的概率，q控制跳向非上一个节点的邻居节点的概率，并以此控制随机游走的倾向。若p < 1 & q > 1，则游走偏广度优先遍历，着重刻画局部信息；若p > 1 & q < 1，则游走偏深度优先遍历，着重刻画全局信息。偏置参数的添加虽增加了算法的计算量，但使算法具有更强的可扩展性。

上述基于随机游走的算法主要考虑的是网络的一阶距离(两节点有直接连边)，而LINE^[14]算法中提出了网络的二阶距离(两节点有共同的邻居节点)的概念，用更多的邻域来丰富节点的表示。GraRep^[15]算法则将一阶、二阶距离推广到了n阶，定义网络的n阶距离矩阵，使用SVD算法对网络的1到n阶矩阵进行分解，每个节点的特征由1到n阶组合表示。

TADW^[16]算法证明了DeepWalk本质上与矩阵分解是相同的，并在已经较为成熟的矩阵分解框架下，将文本特征引入网络表示学习。设节点的邻接矩阵为M，算法将M分解为3个矩阵的乘积，其中矩阵T是固定的文本特征向量，另外2个矩阵W与H为参数矩阵，使用共轭梯度下降法更新W与H矩阵求解参数，如图 1所示。

上述均为网络表示学习技术的热门算法，这些算法在推荐系统领域表现出较好的性能。本文受DeepWalk算法的启发，提出RANE算法，针对随机游走和网络表示两部分分别进行改进，修正游走序列数和游走长度，网络学习中融合属性信息，最终将输出用于推荐系统中，有效地提高了推荐性能。

2 本文算法

在原始的DeepWalk算法中，各节点在网络中进行均匀的随机游走，进而得到固定长度、固定数量的游走序列，然后通过SkipGram模型学习节点的向量表示。本文在DeepWalk算法的基础上进行改进，RANE算法具体步骤如下：

算法1  RANE算法

输入  图$ G(V, E) $、随机游走停止概率$ P $、每个节点的最大游走数量$ \mathrm{m}\mathrm{a}\mathrm{x}T $、每个节点的最小游走数量$ \mathrm{m}\mathrm{i}\mathrm{n}T $、上下文窗口大小$ k $、嵌入维度$ d $、负样本数量$ {n}_{\mathrm{n}\mathrm{s}} $、顶点属性矩阵$ \boldsymbol{A} $

输出  节点向量矩阵$ \boldsymbol{W} $、节点向量辅助矩阵$ {\boldsymbol{W}}^{\mathrm{*}} $、权重参数向量$ \boldsymbol{\beta } $

1.初始化$ \mathrm{W} $、$ {\mathrm{W}}^{\mathrm{*}} $、$ \mathrm{\beta } $

2.迭代计算出每个节点的重要性$ \mathrm{H} $

3.for $ \mathrm{v}\in \mathrm{V} $ do

4.$ \mathrm{l}=\mathrm{m}\mathrm{a}\mathrm{x}(\mathrm{m}\mathrm{a}\mathrm{x}\mathrm{T}\cdot \mathrm{H}(\mathrm{v}), \mathrm{m}\mathrm{i}\mathrm{n}\mathrm{T}) $

5.for $ \mathrm{i}=1 $ to $ \mathrm{l} $ do

6.$ {\mathrm{C}}_{\mathrm{v}}=\mathrm{R}\mathrm{a}\mathrm{n}\mathrm{d}\mathrm{o}\mathrm{m}\mathrm{W}\mathrm{a}\mathrm{l}\mathrm{k}(\mathrm{v}, \mathrm{p}) $

7.ASkipGram($ {\mathrm{n}}_{\mathrm{n}\mathrm{s}}, \mathrm{A}, \mathrm{k}, {\mathrm{C}}_{\mathrm{v}}, \mathrm{W}, {\mathrm{W}}^{\mathrm{*}}, \mathrm{\beta } $)

8.end for

9.end for

10.return $ \mathrm{W} $，$ {\mathrm{W}}^{\mathrm{*}} $，$ \mathrm{\beta } $

在算法1中，首先基于网络重要性进行随机游走采样得到节点序列库，并设置停止概率控制序列长度；然后在表示学习过程中，融合属性信息进行学习；最后应用学习后的向量进行相似性表示，进而完成推荐任务。因为RANE算法是在原始DeepWalk中添加随机游走相关参数以及融合属性信息，并未涉及其他函数的加入，所以时空复杂度基本不变。

2.1 基于节点重要性的随机游走

针对DeepWalk算法中采样点过多的问题，重新设计随机游走策略。对于网络节点$ v $，根据式(6)通过考虑重要性计算游走次数$ {l}_{v} $：

$ {l}_{v}=\mathrm{m}\mathrm{a}\mathrm{x}\left(H\left(v\right)\times \mathrm{m}\mathrm{a}\mathrm{x}T, \mathrm{m}\mathrm{i}\mathrm{n}T\right) $

(6)

其中：$ \mathrm{m}\mathrm{a}\mathrm{x}T $为随机游走的最大次数；$ \mathrm{m}\mathrm{i}\mathrm{n}T $为随机游走的最小次数；$ H\left(v\right) $为节点的网络重要性。计算PageRank^[17]值需要对$ H\left(v\right) $进行数值量化，迭代公式如下：

$ \mathrm{P}\mathrm{R}\left(v\right)=\frac{1-d}{n}+d\sum\limits _{{v}_{i}\in M\left(v\right)}\frac{\mathrm{P}\mathrm{R}\left({v}_{i}\right)}{\mathrm{d}\mathrm{e}\mathrm{g}\left({v}_{i}\right)} $

(7)

其中：$ d $为阻尼系数；$ n $为总节点数；$ M\left(v\right) $为网络中与节点$ v $关联的节点集合；$ \mathrm{d}\mathrm{e}\mathrm{g}\left(v\right) $是节点$ v $的度。通过式(7)不断进行迭代，最后趋于稳定的$ \mathrm{P}\mathrm{R}\left(v\right) $值就是所需的$ H\left(v\right) $。

另外，本文在游走过程中加入了停止概率$ P $控制游走序列长度，即在节点每次向下一个节点游走时都有概率$ P $结束本次游走，使得游走生成的节点序列不再是统一长度。

通过以上改进，使得重要的节点采样次数增加，可以更好地还原网络结构，并且序列长度不一，更接近真实情况。

2.2 融合属性信息的表示学习

在获得节点序列库后，本文在表示学习阶段提出利用属性信息学习节点向量表示的ASkipGram模型。首先，应用自动编码器调整节点的属性维度^[18-19]，统一设置为$ d $，所得属性矩阵为$ \boldsymbol{A}\in {\mathbb{R}}^{\left|V\right|\times d} $，其中，$ V $为节点集，节点$ v $的属性向量可以表示为$ {\boldsymbol{A}}_{v} $。然后，将所得到的属性信息矩阵融入表示学习中。将属性信息和网络结构相结合得到两者的融合向量$ \boldsymbol{U}\left(v\right) $：

$ \boldsymbol{U}\left(v\right)=\frac{{\boldsymbol{W}}_{v}+{\mathrm{e}}^{{\boldsymbol{\beta }}_{v}}{\boldsymbol{A}}_{v}}{1+{\mathrm{e}}^{{\boldsymbol{\beta }}_{v}}} $

(8)

其中：$ {\boldsymbol{W}}_{v} $为隐藏层的词向量；$ {\boldsymbol{\beta }}_{v} $为节点$ v $的属性权重。在式(8)中，在融合节点属性信息时，使用$ {\mathrm{e}}^{{\boldsymbol{\beta }}_{v}} $进行计算而没有直接使用权重$ {\boldsymbol{\beta }}_{v} $，这样可以保证无论如何包含属性信息的部分均不可能为0，进而确保了节点的属性信息在模型训练中的参与度。在得到融合向量$ \boldsymbol{U}\left(v\right) $后，使用其代替原文中的词向量$ {\boldsymbol{W}}_{v} $与输出层的节点辅助词向量$ {\boldsymbol{W}}_{x}^{\mathrm{*}} $进行点积，计算得出节点$ v $与$ x $之间的相似度。

经过随机游走后，可采样得到节点$ v $的上下文集合为$ \mathrm{C}\mathrm{o}\mathrm{n}\mathrm{t}\mathrm{e}\mathrm{x}\mathrm{t}\left(v\right) $。对于节点$ v $，$ \mathrm{C}\mathrm{o}\mathrm{n}\mathrm{t}\mathrm{e}\mathrm{x}\mathrm{t}\left(v\right) $中的单词全为正样本，而其他单词全为负样本，因此对$ <v, \mathrm{C}\mathrm{o}\mathrm{n}\mathrm{t}\mathrm{e}\mathrm{x}\mathrm{t}\left(v\right)> $而言，最大化目标函数如下：

$ g\left(v\right)=\prod \limits_{u\in \mathrm{C}\mathrm{o}\mathrm{n}\mathrm{t}\mathrm{e}\mathrm{x}\mathrm{t}\left(v\right)}\prod \limits_{x\in \left\{u\right\}\bigcup \mathrm{N}\mathrm{e}\mathrm{g}\left(u\right)}p\left(x\right|v) $

(9)

其中：$ u $为$ v $上下文集合中的任一单词。对原模型中条件概率$ p\left(x\right|v) $进行改进，计算公式如下：

$ \begin{array}{l}p\left(x|v\right)={\left[\sigma \left({\lambda }_{x, v}\boldsymbol{U}{\left(v\right)}^{\mathrm{T}}{\boldsymbol{W}}_{x}^{\mathrm{*}}\right)\right]}^{{L}^{u}\left(x\right)}\cdot \\ {\left[1-\sigma \left(\boldsymbol{U}{\left(v\right)}^{\mathrm{T}}{\boldsymbol{W}}_{x}^{\mathrm{*}}\right)\right]}^{1-{L}^{u}\left(x\right)}\end{array} $

(10)

其中：$ \sigma $为Sigmoid函数；$ {L}^{u}\left(x\right) $为标志位，当正采样时$ {L}^{u}\left(x\right)=1 $，负采样时$ {L}^{u}\left(x\right)=0 $。由于原SkipGram模型在训练时未考虑上下文节点与中心节点的距离，而对于推荐系统而言，较近的两节点之间应该具有更高的相似性，因此本文在式(10)中引入权重$ {\lambda }_{x, v} $，定义该权重系数如下：

$ {\lambda }_{x, v}=\frac{1}{\mathrm{l}\mathrm{o}{\mathrm{g}}_{a}\left(D\right(x, v)+1)} $

(11)

其中：$ D(x, v) $为节点$ x $与$ v $之间的距离。当$ x $与$ v $直接相连时，$ D(x, v)=1 $；当两者之间有一个节点时，$ D(x, v)=2 $，以此类推。

将对单个节点$ v $的计算结论扩展至总语料库$ C $，则所有节点最大化目标函数如下：

$ G=\prod \limits_{v\in C}g\left(v\right) $

(12)

将式(9)和式(10)代入式(12)，为方便计算对式(12)取对数作为最终函数：

$ \begin{array}{l}\mathcal{L}=\sum \limits_{v\in C}\sum \limits_{u\in \mathrm{C}\mathrm{o}\mathrm{n}\mathrm{t}\mathrm{e}\mathrm{x}\mathrm{t}\left(v\right)}\sum \limits_{x\in \left\{u\right\}\bigcup \mathrm{N}\mathrm{e}\mathrm{g}\left(u\right)}\left\{{L}^{u}\left(x\right)\cdot \mathrm{l}\mathrm{o}{\mathrm{g}}_{a}\sigma \left({\lambda }_{x, v}\boldsymbol{U}(v{)}^{\mathrm{T}}{\boldsymbol{W}}_{x}^{\mathrm{*}}\right)\right.+\\ \left.\left[1-{L}^{u}\left(x\right)\right]\mathrm{l}\mathrm{o}{\mathrm{g}}_{a}\left[1-\sigma \left(\boldsymbol{U}(v{)}^{\mathrm{T}}{\boldsymbol{W}}_{x}^{\mathrm{*}}\right)\right]\right\}&\end{array} $

(13)

令$ \mathcal{L} $对$ \boldsymbol{U}\left(v\right) $和$ {\boldsymbol{W}}_{x}^{\mathrm{*}} $分别求偏导：

$ \frac{\partial \mathcal{L}}{\partial U\left(v\right)}=\left[{\lambda }_{x, v}{L}^{u}\left(x\right)-\left(1+{\lambda }_{x, v}{L}^{u}\left(x\right)-{L}^{u}\left(x\right)\right)\cdot \\ \sigma \left(\boldsymbol{U}{\left(v\right)}^{\mathrm{T}}{\boldsymbol{W}}_{x}^{\mathrm{*}}\right)\right]{\boldsymbol{W}}_{x}^{\mathrm{*}} $

(14)

$ \frac{\partial \mathcal{L}}{\partial {W}_{x}^{\mathrm{*}}}=\left[{\lambda }_{x, v}{L}^{u}\left(x\right)-\left(1+{\lambda }_{x, v}{L}^{u}\left(x\right)-{L}^{u}\left(x\right)\right)\cdot \\ \sigma \left(\boldsymbol{U}{\left(v\right)}^{\mathrm{T}}{\boldsymbol{W}}_{x}^{\mathrm{*}}\right)\right]\boldsymbol{U}\left(v\right) $

(15)

对于式(14)，为在训练过程中针对每个节点进行属性权重的自适应调节，最终进行更新的参数为$ {\boldsymbol{W}}_{v} $和$ {\boldsymbol{\beta }}_{v} $，因此分别对$ {\boldsymbol{W}}_{v} $和$ {\boldsymbol{\beta }}_{v} $求偏导：

$ \frac{\partial \mathcal{L}}{\partial {\boldsymbol{\beta }}_{v}}=\frac{\partial \mathcal{L}}{\partial \boldsymbol{U}\left(v\right)}\cdot \frac{\partial \boldsymbol{U}\left(v\right)}{\partial {\boldsymbol{\beta }}_{v}}=\frac{\partial \mathcal{L}}{\partial \boldsymbol{U}\left(v\right)}\cdot \frac{\left({A}_{v}-{\boldsymbol{W}}_{v}\right){\mathrm{e}}^{{\boldsymbol{\beta }}_{v}}}{{\left(1+{\mathrm{e}}^{{\beta }_{v}}\right)}^{2}} $

(16)

$ \frac{\partial \mathcal{L}}{\partial {\boldsymbol{W}}_{v}}=\frac{\partial \mathcal{L}}{\partial \boldsymbol{U}\left(v\right)}\cdot \frac{\partial \boldsymbol{U}\left(v\right)}{\partial {\boldsymbol{W}}_{v}}=\frac{\partial \mathcal{L}}{\partial \boldsymbol{U}\left(v\right)}\cdot \frac{1}{1+{\mathrm{e}}^{{\boldsymbol{\beta }}_{v}}} $

(17)

设梯度更新学习速率为$ \eta $，则$ {\boldsymbol{W}}_{v} $、$ {\boldsymbol{W}}_{x}^{\mathrm{*}} $和$ {\boldsymbol{\beta }}_{v} $的更新结果为：

$ {\boldsymbol{W}}_{v}^{\mathrm{n}\mathrm{e}\mathrm{w}}={\boldsymbol{W}}_{v}^{\mathrm{o}\mathrm{l}\mathrm{d}}+\eta \frac{\partial \mathcal{L}}{\partial {\boldsymbol{W}}_{v}} $

(18)

$ {\boldsymbol{W}}_{x}^{\mathrm{*}\mathrm{n}\mathrm{e}\mathrm{w}}={\boldsymbol{W}}_{x}^{\mathrm{*}\mathrm{o}\mathrm{l}\mathrm{d}}+\eta \frac{\partial \mathcal{L}}{\partial {\boldsymbol{W}}_{x}^{\mathrm{*}}} $

(19)

$ {\boldsymbol{\beta }}_{v}^{\mathrm{n}\mathrm{e}\mathrm{w}}={\boldsymbol{\beta }}_{v}^{\mathrm{o}\mathrm{l}\mathrm{d}}+\eta \frac{\partial \mathcal{L}}{\partial {\boldsymbol{\beta }}_{v}} $

(20)

算法2   ASkipGram$ ({n}_{\mathrm{n}\mathrm{s}}, \boldsymbol{A}, k, {C}_{v}, \boldsymbol{W}, {\boldsymbol{W}}^{\mathrm{*}}, \boldsymbol{\beta }) $

1.for $ \mathrm{i}=1~ \mathrm{t}\mathrm{o} ~\left|{\mathrm{C}}_{\mathrm{v}}\right| $ do

2.$ \mathrm{v}={\mathrm{C}}_{\mathrm{v}}\left[\mathrm{i}\right] $

3.for $ \mathrm{j}=\mathrm{m}\mathrm{a}\mathrm{x}(0, \mathrm{i}-\mathrm{k}) $ to $ \mathrm{m}\mathrm{i}\mathrm{n}(\mathrm{i}+\mathrm{k}, |{\mathrm{C}}_{\mathrm{v}}\left|\right) $ do

4.$ \mathrm{u}={\mathrm{C}}_{\mathrm{v}}\left[\mathrm{j}\right] $

5.$ \mathrm{N}\mathrm{e}\mathrm{g}\left(\mathrm{u}\right)=\mathrm{N}\mathrm{e}\mathrm{g}\mathrm{a}\mathrm{t}\mathrm{i}\mathrm{v}\mathrm{e}\mathrm{S}\mathrm{a}\mathrm{m}\mathrm{p}\mathrm{l}\mathrm{e}(\mathrm{G}, \mathrm{v}, {\mathrm{n}}_{\mathrm{n}\mathrm{s}}) $

6.for $ \mathrm{t}\in \mathrm{u}\bigcup \mathrm{N}\mathrm{e}\mathrm{g}\left(\mathrm{u}\right) $ do

7.更新$ {\mathrm{W}}_{\mathrm{v}}, {\mathrm{W}}_{\mathrm{v}}^{\mathrm{*}}, {\mathrm{\beta }}_{\mathrm{v}} $

8.end for

9.end for

10.end for

2.3 应用表示结果推荐

在同质图的推荐中，以节点相似性为依据进行推荐，而其中必然应用到以向量形式对节点进行表示。根据上文计算结果，可以得到任意节点$ v $的向量表示：

$ {\boldsymbol{z}}_{v}={\boldsymbol{W}}_{v}+{\boldsymbol{\beta }}_{v}{\boldsymbol{A}}_{v} $

(21)

为方便进行统一的度量，先对向量进行L2范数归一化处理，然后使用向量内积的方式表示两节点的相似度，最终相似度计算结果如下：

$ s(v, x)=\frac{{\boldsymbol{z}}_{v}\cdot {\boldsymbol{z}}_{x}}{{‖{\boldsymbol{z}}_{v}‖}_{2}\cdot {‖{\boldsymbol{z}}_{x}‖}_{2}} $

(22)

对某一节点而言，利用式(22)计算出该节点与其他节点的相似度，排序后根据预先设定的阈值取出相似度高的节点进行推荐。

3 实验与结果分析 3.1 实验数据集

实验选取3个数据集进行验证，分别为Cora、Citeseer和BlogCatalog，其中，Cora和Citeseer数据集来源于科学出版物网络，BlogCatalog来源于社交网络。具体统计信息如表 1所示。

3.2 对比算法

本文选定以下4种算法与RANE算法进行对比：

1) DeepWalk^[8]。该算法是本文算法的思想基础，采用均匀随机游走生成节点序列，并通过SkipGram模型进行网络表示学习。

2) Node2vec^[13]。该算法针对DeepWalk的随机游走部分进行改进，控制随机游走偏向。

3) GraRep^[15]。该算法是对LINE算法的扩展，定义了网络的n阶距离矩阵并使用SVD算法对网络的1到n阶矩阵进行分解，每个节点的特征由1到n阶的特征拼接表示。

4) TADW^[16]。该算法是DeepWalk算法的扩展算法，将节点的文本信息特征矩阵融入到矩阵分解过程中，最终将得到的两个分解后的矩阵中的对应向量进行拼接，作为节点的最终嵌入表示。

3.3 评价指标

采用ROC曲线下方面积(Area Under Curve，AUC)来评测推荐系统性能。在计算过程中，采用下式降低计算复杂度^[20]：

$ {A}_{\mathrm{A}\mathrm{U}\mathrm{C}}=\frac{\sum \limits_{i\in \mathrm{p}\mathrm{o}\mathrm{s}}{r}_{\mathrm{r}\mathrm{a}\mathrm{n}{\mathrm{k}}_{i}}-\frac{M(M+1)}{2}}{M\times N} $

(23)

其中：$ \sum \limits_{i\in \mathrm{p}\mathrm{o}\mathrm{s}}{r}_{\mathrm{r}\mathrm{a}\mathrm{n}{\mathrm{k}}_{i}} $为所有正样本的rank值之和；$ M $为正样本个数；$ N $为负样本个数。AUC值越接近1，说明推荐效果越好。

3.4 实验环境

实验环境为Ubuntu 16.04，应用Python 3.6.5进行算法开发。为了控制实验中输出结果的可比较性，设定所有算法输出节点向量的维度均为128维，使用余弦相似度进行节点间的相似度计算。对于使用均匀随机游走的算法，规定任一节点游走的次数为20，序列长度为40，其余参数根据实验选择最优设定。RANE算法中$ \mathrm{m}\mathrm{a}\mathrm{x}T $设为40，$ \mathrm{m}\mathrm{i}\mathrm{n}T $设为10，随机游走终止概率$ P $设为0.15。在节点嵌入学习部分，DeepWalk、Node2vec与RANE算法的上下文窗口大小设为5，学习率设为0.01，负样本个数设为4。对于GraRep算法设定融合1至4阶邻居信息组成节点向量，其余参数均沿用原论文设定。对于TADW算法，除节点嵌入维度外其他参数依照原论文设定，取迭代至稳定的节点嵌入向量作为结果。

在实验过程中，选取数据集的10%作为测试集，其是在保证训练集中无孤立节点的情况下随机选取的，并且保证测试集中正采样与负采样数量相同。

3.5 结果分析 3.5.1 推荐性能分析

改变训练集的数量比率(R)，使其占数据集的40%~90%，测试集不变，均为上文设置。对不同数量训练集，每种算法进行10次独立测试，取平均值后作为该次实验的最终结果。

在Citeseer数据集上，5种算法的准确度对比结果如表 2所示。可以看出，RANE算法在不同的训练集比率下所得结果均优于其他算法，而在训练集比率为40%的情况下，优势最明显。

在Cora数据集上，5种算法的准确度对比结果如表 3所示，可以看出整体趋势和Citeseer数据集相同，RANE算法仍然具有最优的性能表现，且在训练集比率较低的情况下优势更明显。

在BlogCatalog数据集上，5种算法的准确度对比结果如表 4所示。综合3个数据集上所得结果可以看出，RANE算法相比其他算法具有更好的推荐效果，并且在训练集比率较小时优势更明显，主要原因笔者认为是该算法可以更好地解决冷启动问题。

3.5.2 随机游走与表示学习模块消融实验

由于本文算法在DeepWalk算法上对随机游走和节点表示学习两部分均进行改进，为了测试每一部分的改进对最终结果的影响情况，本文对两部分进行了消融实验。RRANE算法表示仅改进随机游走部分，ARANE算法表示仅改进节点表示学习部分，在BlogCatalog数据集上进行消融实验，准确度结果如表 5所示。可以看出，两部分均对最终结果有一定的性能提升，但节点表示学习部分对整体算法的性能影响更大。

3.5.3 随机游走模块采样效果验证

为验证改进后的随机游走策略对采样序列的修正效果，选取BlogCatalog数据集进行实验，结果如图 2所示。设置$ \mathrm{m}\mathrm{a}\mathrm{x}T $为40，$ \mathrm{m}\mathrm{i}\mathrm{n}T $为10，随机游走终止概率为0.15。可以看出，改进后的随机游走策略更好地保留了网络结构特性。

3.5.4 参数敏感性分析

在BlogCatalog数据集上对算法进行参数敏感性分析。本文分析$ \mathrm{m}\mathrm{a}\mathrm{x}~T $与$ \mathrm{m}\mathrm{i}\mathrm{n}~T $参数，在分别固定$ \mathrm{m}\mathrm{i}\mathrm{n}~T $或$ \mathrm{m}\mathrm{a}\mathrm{x}~T $的同时调节另一个参数进行实验。如图 3所示，$ \mathrm{m}\mathrm{i}\mathrm{n}~T $对AUC值的影响更大。

对随机游走部分的终止概率$ P $进行敏感性测试，设置$ P $为0.05、0.10、0.15、0.20、0.25、0.30。如图 4所示，终止概率越小，AUC值越大，但此时游走长度更长，相应的计算量就会增大，因此实验过程中应综合考虑推荐效果与计算成本。

由于RANE算法在计算节点相似性时引入了有关上下文节点与中心点距离的权重，因此需要对ASkipGram模型的窗口大小k进行参数敏感性分析，窗口大小依次设置为1、3、5、7、9、11、13、15。如图 5所示，随着窗口的不断增大，AUC值呈先增大后减小的变化趋势，说明窗口取得过大或过小都会影响节点网络特征的表征效果。

测试节点嵌入维度d分别为16、32、64、128和256时的RANE算法AUC值，其他参数均为上文设置，在BlogCatalog数据集上的实验结果如图 6所示，可以看出在嵌入维度为128时AUC取得最优值。

4 结束语

本文在DeepWalk算法的基础上，提出基于随机游走的网络表示学习推荐算法。根据节点重要性决定游走序列数，设置终止概率使得游走序列的长度不完全相同，从而更接近真实情况。同时，在节点表示学习过程中，融合节点的属性信息，自适应调整节点属性信息权重，并考虑上下文节点离中心节点的距离，以获得更准确的推荐结果。在3个数据集上的实验结果表明，该算法具有较好的推荐性能，并且有效解决了冷启动问题。但由于该算法随机游走部分设置的截止概率为随机生成，因此后续可将其与游走长度相关联，进一步提高推荐准确度。