Press "Enter" to skip to content

符号网络的网络表示学习方法

对于许多常见的复杂系统,如社交网络、传感器网络、生物网络等,我们可以使用网络中的节点和边来分别表示系统中的实体和实体间的关系。通过这种表示,许多实际的复杂系统预测任务就可以抽象为面向复杂网络的预测任务。

 

然而,传统机器学习算法的性能严重依赖于特征工程以及训练数据的质量。因为这个过程通常需要具有领域知识的专家进行人工设计。同时,复杂网络的异构性、噪声高、数据缺失、规模大等问题也严重制约了面向复杂系统的机器学习的发展。近年来,网络表示学习作为一个新兴领域,逐渐获得学界的关注。这种方法能够自动从网络中提取结构信息,将节点编码为低维特征向量,同时保留网络的拓扑结构、节点内容和其他信息。这样解决了传统方法对于大规模网络计算复杂度高的问题。但是对符号网络来说,已有算法只能提取节点特征,对于基于边的任务,如链接预测和符号预测,这些方法依然需要手工设计边特征,这导致了此类任务的效果不能令人满意。

 

针对以上问题,本文提出了一种能够同时学习节点与边的特征向量的网络表示学习框架,这种策略能够解决边特征的获得问题。同时,本文提出一个全局可学习映射来解决信息传递不一致的问题,以及一种符号网络节点相似度计算方法。这样,所学习到的边特征能够直接应用到基于边的网络分析任务,避免了手工设计可能带来的低效、信息不一致等问题。文中分别采用神经网络和矩阵分解实现框架,实验证明所提出方法提高了多个面向复杂系统的网络预测任务的性能。

 

问题描述和动机

 

已知网络 ,其中 代表N个节点的集合, 代表观测到的边的集合。边 的权重为 ,方向为从 。我们可以使用邻接矩阵A来表示数据:当 时, 为未观测到的边;当 等于+1或-1时分别代表观测到的正边或负边。

 

算法的目标是学习节点的两个低维向量表示 ,它们的每一行分别代表对应节点作为边的出发和终止节点时的特征。这样对于面向节点的预测任务,可以直接将节点特征作为预测算法的输入。当面向基于边的预测任务时,这些算法通常根据两个节点向量的距离来做决定,例如,在node2vec和SNE中,作者分布采用Hadamard、L1-weight、l2-weight、concate、average等方法计算距离,然后从中选择最终结果最好的结果。

 

此外,许多符号网络的表示学习方法基于一些假设(如社会理论)来将节点和边的符号联系起来,而这些假设通常会忽略许多重要的边的性质(如方向、权重);而且这些将边与节点联系起来的假设并不能同上面的距离函数对应起来,导致了信息的不一致以及额外的选择距离函数的工作(即设计边特征的特征工程)。

 

为解决以上问题,本文设计了一种新的符号网络表示学习框架,不仅能够学习到节点向量,还能够学习到任意节点对的低维向量表示 。这样做能够避免了上面所提到的不一致、手工设计等问题,但是也带来了高算法复杂度,即B的存储和计算复杂度。因此我们采用了一些假设来降低算法复杂度。此外,我们还针对符号网络扩展了LINE提出的二阶相似度,来作为框架的目标函数。实验表明我们的算法无论在节点分类、符号预测,还是运行速度都得到了最好的表现。

 

方法

 

假设

 

我们首先提出如下两个假设:

 

对于任意 仅依赖于

 

这个依赖关系对于整个网络是一致的。

 

如果我们使用一个向量映射函数 来表示这个关系,那幺就可以得到:

 

下面我们使用一个例子来解释这两个假设:如果网络中的节点代表政客,两个节点之间的正边/负边代表政客之间互相支持/反对。给定这样一个网络,我们的目标是预测未知的政客之间的关系,即指定节点 ,如果它们之间没有边相连,我们想预测边 的符号。这是符号预测任务的一个应用场景。

 

我们使用节点特征 来表示政客的特征,边特征 表示它们的关系。这样,它们之间的关系仅依赖与他们本身的政见,这等价于第一个假设。

 

如果两个政客互相支持,我们 用来表示两人政见中L种不同相似度,显然这种评价标准应该对网络中的每对政客一致。这就是第二个假设。

 

符号网络的节点相似性

 

LINE模型刻画了无符号网络的一阶和二阶节点相似性,这里我们将其扩展到符号网络,即:

 

如果符号网络G 中的两个节点是相似的,他们应当同时满足如下两个条件:

 

1. 他们满足无符号网络的二阶相似性;

2. 他们与邻居的符号模式相近:即,C代表

的共同邻居,令
表示
到C中各邻居的符号。那幺当

相似时他们具有相同的邻居符号模式。

 

对于条件1,已有的一些工作证明其等价于拟合两个节点之间的Pointwise Mutual Information,即 PMI 。在本文中,我们假设节点间的 决定于 。我们使用映射函数 来表示这个映射关系,得到条件1的目标函数为:

 

 

对于条件2,我们假设边 的符号服从伯努利分布,且决定于 。则得到 的条件分布:

 

 

其中 是表示节点特征与符号之间关系的映射函数。令:

 

 

为从 出发的边的符号模式,我们可以通过极小化 与经验分布:

 

 

的KL距离来得到条件2的目标函数:

 

 

符号网络需要同时满足两个条件,我们使用一个 超参数 来结合,得到我们框架的最终目标函数:

 

 

实现

 

从上面目标函数可以看到,我们将学习S、T和B的问题转化为了学习S、T、f、g和h的问题。这样就避免了计算和存储B这个大规模矩阵。但是我们应该如何确定f、g和h呢?

 

这里我们采用两种策略:第一种是采用MLP来从数据中学习出这个映射,另一种是将它们三个指定为简单的函数。

 

对于策略1我们使用如下神经网络,得到模型neural networks signed network embedding(nSNE):

 

 

对于策略2,我们指定 以及

 

得到模型 light signed network embedding(lSNE),这样将目标函数简化为:

 

 

其中λ是用来避免过拟合的正则参数。

 

实验

 

实验设置

 

实验采用如下4个数据集:

 

– Wiki-editor

 

– Wiki-rfa

 

– Epinions

 

– Slashdot

 

所有的数据集都可以用来做符号预测任务(通过隐藏一部分边作为测试集);由于只有Wiki-editor的节点有label,所以我们仅用它来验证节点分类任务。

 

对比算法如下:

 

– Spectral Clustring:基于谱方法的网络表示学习方法;

 

– SNE:基于随机游走和log-bilinear模型;

 

– SiNE:基于社会理论和MLP。

 

其他设置:

 

– 对每一种实验设置,我们对对比算法的 超参数 都做了grid search,保证其达到最优结果;

 

-机器学习算法采用逻辑回归;

 

– 对于节点分类,我们采用accuracy和AUC作为评价标准;

 

– 对于符号预测,我们采用F1和AUC作为评价标准;

 

– 我们的算法采用了early stop避免过拟合。

 

可视化

 

我们将各算法所学习出的边特征使用t-SNE降维,得到:

 

 

节点分类

 

我们用整个网络作为算法的输入,得到节点的特征;再将节点划分为训练/测试集,使用交叉验证的方法得到节点分类的表现如下:

 

 

符号预测

 

我们隐藏了部分边作为测试集,将余下的网络(保证联通)作为训练集投入网络表示学习算法;再用训练集对应的边特征和符号训练一个逻辑回归函数,来预测测试集中边的符号,得到如下结果:

 

 

时间对比

 

我们统计了各算法的平均运行时间,如下:

 

 

资源

 

论文地址:

 

https://doi.org/10.1016/j.neucom.2018.08.072

 

论文代码:

 

https://github.com/wzsong17/Signed-Network-Embedding

 

作者简介

宋文卓是吉林大学计算机科学与技术学院专业的博士生。现阶段的主要研究方向是数据挖掘、社交网络分析和网络表示学习。

Be First to Comment

发表评论

电子邮件地址不会被公开。 必填项已用*标注