一种基于方向感知的网络嵌入算法和系统

摘要

一种基于方向感知的有向网络嵌入算法，包括：S1，计算非对称临近性，具体包括：为有向网络中的随机游走策略定义单步概率，将随机游走中的单步方向与临近性信息保存在权重中，计算节点之间分数；S2，建立有向网络嵌入，具体包括：计算得到节点之间的非对称临近性后，建立定性有向网络嵌入DNE‑L将节点之间离散的非对称临近性保留在嵌入网络中，计算得到节点之间的非对称临近性后，建立定量有向网络嵌入DNE‑T将节点之间离散的非对称临近性保留在嵌入网络中，优化模型。本发明还包括实施一种基于方向感知的有向网络嵌入算法的系统。本发明对真实网络中的实际问题有更好的解释性，将离散的和连续的有向网络嵌入都有效地保留在了嵌入空间中。

说明书

技术领域

本发明涉及机器学习，特别涉及一种基于方向感知的有向网络嵌入算法和系统。

背景技术

网络嵌入算法的目的是将现有网络中的节点嵌入到低维向量空间中，以便更好地理解节点之间的语义关系。现有的网络嵌入算法通过确定性度量或者随机游走来保留相似性，现有的网络嵌入算法主要集中在处理无向网络上。对于有向嵌入网络，通常的解决方案是忽略有向网络中边的方向，将无向网络嵌入算法应用于变换后的网络。然而，这可能导致信息丢失，更有可能学习到错误的嵌入结果。

由于真实网络中的边往往与方向有关，因此有向网络嵌入算法受到了关注。有向边表示了网络中节点之间的非对称临近性，这种潜在的非对称的邻近性是有向网络的关键特征，需要使用网络嵌入算法来保留。虽然现有的一些方法试图保留有向图中的非对称临近性，但是它们所获取的非对称临近性所表达的意义是不明确的。因此，获取非对称临近性并有效地将其保存在嵌入空间中，并使其对真实网络具有实用性意义面临了重大的挑战。

发明内容

本发明要解决的现有技术的上述缺点，提供一种基于方向感知的有向网络嵌入算法及其系统。

本发明意图在有向网络中获取非对称临近性并有效地保存在嵌入空间中，并在真实网络的链接预测和节点分类任务中达到更好的效果。

为实现上述目的，本发明采用如下技术方案：一种基于方向感知的有向网络嵌入算法，包括：

S1：计算非对称临近性；

S1a：为有向网络中的随机游走策略定义单步概率，单步概率公式如下：

其中，P表示随机游走的单步概率，

S1b：将随机游走中的单步方向与临近性信息保存在权重中，单步权重公式如下：

其中，r

S1c：计算节点之间分数，用来表示节点之间的非对称临近性，公式如下：

其中，r

S2：建立有向网络嵌入；

S21：计算得到节点之间的非对称临近性后，建立定性有向网络嵌入DNE-L将节点之间离散的非对称临近性保留在嵌入网络中：

S21a：定义有向图上下文观察概率，即在非对称临近性为s

其中，h

S21b：通过最大限度地提高观察有向图上下文节点的概率，将非对称临近性保留在网络嵌入中：

其中，DC

S22：计算得到节点之间的非对称临近性后，建立定量有向网络嵌入DNE-T将节点之间离散的非对称临近性保留在嵌入网络中：

S22a：定义权重转换公式，将步骤S1中计算的非对称临近性分数通过加权函数得到新的权重：

其中，s

S22b：定义定量有向网络嵌入模型，通过加权的Skip-Gram优化来学习源嵌入和目标嵌入：

其中，h

S23：优化模型：采用负采样和随机梯度下降策略，提高训练效率：

其中，σ表示激活函数，

优选地，所述S202a中，加权函数需满足以下要求：(1)π

其中，

进一步，使用随机游走策略InfoWalk来有效地获取有向网络中节点之间的层次结构和非对称临近性，得到一个表示节点间非对称临近性的加权节点序列，用于有向嵌入学习；使用定性有向网络嵌入DNE-L和定量有向网络嵌入DNE-T有效地将嵌入网络保存在嵌入空间中，使其在真实世界的参照数据集上得到优秀的任务结果。

实施本发明的基于方向感知的有向网络嵌入算法的系统，包括存储器和处理器以及在储存在存储器上并在处理器上执行的程序，其特征在于：所述的程序包括依次连接的非对称临近性计算模块、有向网络嵌入建立模块。

本发明的优点是：1)提供了一种新的信息随机行走策略，以有效地获取有向网络结构中的非对称临近性，对真实网络中的实际问题有更好的解释性；2)提出了具有定性和定量的有向网络嵌入算法(两种变量的DNE-L和有向网络嵌入方法DNE-T)，将离散的和连续的有向网络嵌入都有效地保留在了嵌入空间中。

附图说明

为了更清楚地说明本发明实施例的技术方案，下面将对实施例描述中所需要使用的附图作简单地介绍，显而易见地，下面描述中的附图仅仅是本发明的一些实施例，对于本领域的普通技术人员来讲，在不付出创造性劳动的前提下，还可以根据这些附图获得其他附图。

图1a～图1f是本发明实施例提供的一种有向网络上的信息游走策略的示意图，其中图1a是三个节点之间先反向再正向游走的示意图，图1b是三个节点之间先正向再反向游走的示意图，图1c是四个节点之间先反向游走再正向游走两次的示意图，图1d是四个节点之间正反方向间隔游走的示意图，图1e是有向环图中正向游走示意图，图1f是有向环图中反向游走示意图；

图2为本发明实施例提供的一种有向网络嵌入方法的总体框架图；

图3a和图3b是本发明实施例提供的在用户推荐场景的用户分析实验下相比于现有算法的评分结果对比图，其中图3a是使用Micro-F1分数在用户轮廓分析场景下对不同算法评估的对比图，图3b是使用Macro-F1分数在用户轮廓分析场景下对不同算法评估的对比图。

具体实施方式

下面结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例仅仅是本发明一部分实施例，而不是全部的实施例。基于本发明的实施例，本领域普通技术人员在没有做出创造性劳动前提下所获得的所有其他实施例，都属于本发明的保护范围。

本发明提出了一种基于方向感知的有向网络嵌入算法，该方法能够：(1)使用一种新的信息随机行走策略，以有效地获取有向网络的节点之间的非对称临近性，并可以很好地应用于真实网络中的实际问题；(2)使用了具有定性和定量的有向网络嵌入(两种变量的DNE-L和有向网络嵌入方法DNE-T)，来保持潜在嵌入空间中离散的和连续的非对称临近性。

下面对本发明中提出的核心方法作详细阐述。

S1：计算非对称临近性；

本发明提出一个信息随机游走策略InfoWalk，用于计算节点之间的非对称临近性。InfoWalk的基本思想是首先忽略边的方向，并允许随机游走访问来自各个方向的节点。在随机游走的每一步中，方向和非对称临近性被存储在一个精心设计的权重中。在随机游走达到指定长度后，InfoWalk将得到一个表示节点问非对称临近性的步长加权节点序列，可用于有向嵌入学习。

S1a：为有向网络中的随机游走策略定义单步概率：

给定一个有向网络G，从节点vi开始的随机游走可以表示为

其中，P表示随机游走的概率，

这种随机游走可以看作是在忽略有向图G中边方向的无方向网络游走。这种游走方法可以达到在有向网络中没有路径的节点，并获取非对称的临近性。

S1b：将随机游走中的单步方向与临近性信息保存在权重中：

为了获取节点之间的方向和临近性，本发明进一步在每个v

其中，r

S1c：计算节点之间分数，用来表示节点之间的非对称临近性：

给定每一步的权重r

其中，r

图1表示的是本发明实施例提供的一种有向网络上的信息游走策略的示意图，其中实线箭头表示的沿着边方向移动的步骤，虚线箭头表示的是向边的反方向移动的步骤。s

因为InfoWalk忽略了有向网络中边的方向，使内外度越高的节点更容易被频繁地访问，所以InfoWalk可以很容易地获取非对称临近性。因此，这些节点在其他节点窗口中出现的概率也更高。

S2：建立有向网络嵌入；

本发明提出了有向网络嵌入的两个变体：定性有向网络(DNE-L)和定量有向网络(DNE-T)。对于每个变体，都学习两个独立的嵌入来保留非对称的临近性，称为源嵌入和目标嵌入。两个变体的区别在于保留非对称的临近性的方法不同，图2表示了上述两种方法DNE-L和DNE-T的基本结构，其中DNE-L保留了离散的有向网络嵌入，DNE-T保留了连续的有向网络嵌入。DNE将根据分数s

其中，有向图的上下文是有向网络G上的信息随机游走的结果，分为源上下文、目标上下文和不明确上下文。源上下文指的是DNE方法到达的节点，并且可能与之有一条从该节点出发的有向边；目标上下文指的是DNE方法到达的节点，并且可能与之有一条到达该节点的有向边；不明确上下文指的是DNE方法到达的节点，但它们之间没有明确的方向。

S21：计算得到节点之间的非对称临近性后，建立定性有向网络嵌入DNE-L将节点之间离散的非对称临近性保留在嵌入网络中：

S21a：定义有向图上下文观察概率，即在非对称临近性为s

其中，h

S21b：通过最大限度地提高观察有向图上下文节点的概率，将非对称临近性保留在网络嵌入中：

其中，DC

S22：计算得到节点之间的非对称临近性后，建立定量有向网络嵌入DNE-T将节点之间离散的非对称临近性保留在嵌入网络中：

S22a：由于有向图上下文节点被InfoWalk访问的概率与中心节点的不同，因此，根据上下文节点的相对分数来衡量当前节点是合理的。然而，由于1)分数s

为了解决上述问题，在定量的有向网络嵌入中，需要根据新的要求重新制定了s

定义权重转换公式，将S1中计算的非对称临近性分数通过加权函数得到新的权重：

其中，s

S22b：定义定量有向网络嵌入模型，通过加权的Skip-Gram优化来学习源嵌入和目标嵌入：

其中，h

S23：优化模型：采用负采样和随机梯度下降策略，提高训练效率，投影公式如下：

其中，σ表示激活函数，

实施本发明的基于方向感知的有向网络嵌入算法的系统，包括存储器和处理器以及在储存在存储器上并在处理器上执行的程序，所述的程序包括依次连接的非对称临近性计算模块、有向网络嵌入建立模块。非对称临近性计算模块的执行内容对应本发明方法的步骤S1的内容，有向网络嵌入建立模块对应本发明方法的步骤S2的内容。

为了更清楚地说明本发明的具体用途，实施例以微博上的用户推荐为例，详细地阐述具体实施过程：

本实施例的具体场景为：为微博用户推荐感兴趣的用户进行关注。

一种为微博用户推荐感兴趣的用户进行关注的方法，包括如下步骤：

步骤一、技术人员需要收集用户与用户之间的关注信息，并建立用户关系有向网络。其中，有向网络的节点代表一个用户个体，有向边代表用户的关注行为，边的出方向表示关注者，边的入方向表示被关注者。

步骤二、建立有向网络之后，技术人员使用步骤S1中提出的随机游走策略获取节点之间的非对称临近性，即用户之间的非对称临近性。

步骤三、技术人员可以选择使用步骤S21中提到的定性有向网络嵌入DNE-L，或者步骤S22中提到的定量有向网络嵌入DNE-T，将用户之间的非对称临近性保留在网络嵌入中。在这一过程中，技术人员需要使用步骤S23中的负采样和随机梯度下降策略来提高训练效率，优化网络模型。

步骤四、在完成有向网络嵌入模型的学习之后，技术人员可以将每一个用户表示为一个表征，用于下游的任务，即用户的匹配任务。技术人员将代表每一个用户的表征进行相似度计算，即可将表征近似的用户划分为一类，进行用户推荐。

本发明实施例提供的上述方案，主要获得如下有益效果：1、在真实的有向网络中有效地获得非对称临近性；2、使用DNE方法保留的离散的或连续的网络嵌入在链接预测和节点分类等任务中效果优于现有的嵌入方法。为了说明本发明实施例上述方案的效果，结合实验进行说明。

一、实验数据。

实验使用了几个真实的社交网络数据集和每个节点都有标签的书目网络进行广泛的实验。其中，带有有向边的社交网络用于评估用户推荐，而书目网络用于用户分析。由于收集具有真实标签的大规模真实社交网络很难，实验采用了具有有向边的书目网络。表1展示了数据集的统计信息。

表1数据集的统计信息

二、实验结论。

1、DNE方法在保留节点之间的临近性在大多数网络数据集中取得更好的效果。

实验中，将本发明中的方法与几种最先进的有向网络嵌入方法和用户推荐方法进行了比较，来评估提出的DNE。在实验中，并没有与基于社交网络的用户推荐方法进行比较，因为本实验专注于评估学习到用户/节点嵌入在有向图中的效果。

在基线方法中，Node2Vec、DeepWalk、APP、NERD都是基于随机游走的方法，为了进行公平的比较，实验将这些方法中的随机游走参数设置为与本发明中的DNE方法相同。具体为：随机游走长度l＝10、窗口大小k＝4和每个节点的游走数r＝10。对于Node2Vec方法，宽度优先采样的概率设为0.25，深度优先采样的概率设为0.5。实验中使用嵌入向量的内积来估计节点之间的临近性。APP、ATP、NERD和HOPE方法通过学习两个独立的源嵌入和目标嵌入来保留非对称的临近性。对于节点分类任务，使用两种嵌入来测试性能，并报告最佳结果。LINE对每个节点学习两个嵌入，即上下文嵌入和节点嵌入。在实验中，使用了PyTorch和Tensorflow实现了本发明中的DNE方法，模型参数使用Xavier随机初始化，并采用Adam优化器进行优化，将学习率设置为0.0005，批量大小设置为512。所有方法的向量位数均为128。

表2在显示了五个真实世界的社交网络数据集中的普通用户推荐结果。NA表示这些方法由于内存限制或运行时间超过一周而无法在硬件上运行的情况，

表2本发明和现有算法在普通用户推荐上的性能对比

从表2，可以看出：在保留非对称临近性上，提出的DNE方法的两个变体在大多数网络数据集中获得比现有方法更好的效果，这证明了本发明在有向社交网络中获取非对称临近性的有效性。

2、DNE方法在用户推荐场景下保留节点之间的方向方面提高了效果。

实验进一步评估有向感知的用户推荐任务，以模拟现实世界中应该考虑推荐方向的场景。普通的用户推荐任务只预测边是否存在，并不能保证方向能被很好的预测。例如，从v

表3本发明和现有算法在方向感知的性能对比

从表3，可以看出：在所有的评估方法中，本发明中的DNE-L和DNE-T在所有数据集上都取得了最好的效果，比现有的方法有显著的改进。对比表2和表3，可以观察到所有方法在方向感知用户推荐方面的效果都有所下降，这说明了考虑边的方向和非对称临近性的必要性。将DNE-L和DNE-T相比，可以观察到这两个任务的改善，在有向感知的用户推荐中，改进后的效果比经典的用户推荐更加显著。这也进一步表明了在预测节点之间的有向链接考虑方向的重要性。

3、在用户轮廓分析方面就有更好的效果。

用户轮廓分析是用户建模的另一项重要任务，特别是在有向社交网络中，用户轮廓分析的目标是查找用户属于的用户组，这与经典的节点分类任务相同。实验中，随机采样标记节点的30％进行训练，其余节点进行测试。学习到的嵌入将被输入到相同的SVM分类器中，使用Micro-F1和Macro-F1分数来评估结果。对于为每个节点学习两个独立嵌入的方法，将嵌入连接起来进行评估，评估结果如图3所示。

从图3中可以看出，基本的观察结果与用户推荐任务相似，DNE方法在两个评价指标中比现有方法有更好的效果。

本说明书实施例所述的内容仅仅是对发明构思的实现形式的列举，本发明的保护范围不应当被视为仅限于实施例所陈述的具体形式，本发明的保护范围也及于本领域技术人员根据本发明构思所能够想到的等同手段。