2019/04/02 16:32

宋文卓（吉林大学计算机学院博士）作者萝卜兔执行编辑

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

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

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

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

问题描述和动机

已知网络,其中代表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

作者简介

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

极验

极验是全球顶尖的交互安全技术服务商，于2012年在武汉成立。全球首创 “行为式验证技术” ，利用生物特征与人工智能技术解决交互安全问题，为企业抵御恶意攻击防止资产损失提供一站式解决方案。

理论网络表示学习神经网络矩阵分解目标函数

相关数据

逻辑回归技术

逻辑回归（英语：Logistic regression 或logit regression），即逻辑模型（英语：Logit model，也译作“评定模型”、“分类评定模型”）是离散选择法模型之一，属于多重变量分析范畴，是社会学、生物统计学、临床、数量心理学、计量经济学、市场营销等统计实证分析的常用方法。

来源：Trevor Hastie, Robert Tibshirani and Jerome Friedman (2nd ed., 2009). The Elements of Statistical Learning: Data Mining, Inference, and Prediction.维基百科

权重技术

线性模型中特征的系数，或深度网络中的边。训练线性模型的目标是确定每个特征的理想权重。如果权重为 0，则相应的特征对模型来说没有任何贡献。

来源：Google AI Glossary

机器学习技术

机器学习是人工智能的一个分支，是一门多领域交叉学科，涉及概率论、统计学、逼近论、凸分析、计算复杂性理论等多门学科。机器学习理论主要是设计和分析一些让计算机可以自动“学习”的算法。因为学习算法中涉及了大量的统计学理论，机器学习与推断统计学联系尤为密切，也被称为统计学习理论。算法设计方面，机器学习理论关注可以实现的，行之有效的学习算法。

来源：Mitchell, T. (1997). Machine Learning. McGraw Hill.

参数技术

在数学和统计学裡，参数（英语：parameter）是使用通用变量来建立函数和变量之间关系（当这种关系很难用方程来阐述时）的一个数量。

来源：维基百科

超参数技术

在机器学习中，超参数是在学习过程开始之前设置其值的参数。相反，其他参数的值是通过训练得出的。不同的模型训练算法需要不同的超参数，一些简单的算法（如普通最小二乘回归）不需要。给定这些超参数，训练算法从数据中学习参数。相同种类的机器学习模型可能需要不同的超参数来适应不同的数据模式，并且必须对其进行调整以便模型能够最优地解决机器学习问题。在实际应用中一般需要对超参数进行优化，以找到一个超参数元组（tuple），由这些超参数元组形成一个最优化模型，该模型可以将在给定的独立数据上预定义的损失函数最小化。

来源：Wikipedia

神经网络技术

（人工）神经网络是一种起源于 20 世纪 50 年代的监督式机器学习模型，那时候研究者构想了「感知器（perceptron）」的想法。这一领域的研究者通常被称为「联结主义者（Connectionist）」，因为这种模型模拟了人脑的功能。神经网络模型通常是通过反向传播算法应用梯度下降训练的。目前神经网络有两大主要类型，它们都是前馈神经网络：卷积神经网络（CNN）和循环神经网络（RNN），其中 RNN 又包含长短期记忆（LSTM）、门控循环单元（GRU）等等。深度学习是一种主要应用于神经网络帮助其取得更好结果的技术。尽管神经网络主要用于监督学习，但也有一些为无监督学习设计的变体，比如自动编码器和生成对抗网络（GAN）。

来源：机器之心

数据挖掘技术

数据挖掘（英语：data mining）是一个跨学科的计算机科学分支它是用人工智能、机器学习、统计学和数据库的交叉方法在相對較大型的数据集中发现模式的计算过程。数据挖掘过程的总体目标是从一个数据集中提取信息，并将其转换成可理解的结构，以进一步使用。

来源：维基百科

特征工程技术

特征工程是利用数据所在领域的相关知识来构建特征，使得机器学习算法发挥其最佳的过程。它是机器学习中的一个基本应用，实现难度大且代价高。采用自动特征工程方法可以省去采用人工特征工程的需求。Andrew Ng 说“挖掘特征是困难、费时且需要专业知识的事，应用机器学习其实基本上是在做特征工程。”

来源：Wikipedia

映射技术

映射指的是具有某种特殊结构的函数，或泛指类函数思想的范畴论中的态射。逻辑和图论中也有一些不太常规的用法。其数学定义为：两个非空集合A与B间存在着对应关系f，而且对于A中的每一个元素x，B中总有有唯一的一个元素y与它对应，就这种对应为从A到B的映射，记作f：A→B。其中，y称为元素x在映射f下的象，记作：y=f(x)。x称为y关于映射f的原象*。*集合A中所有元素的象的集合称为映射f的值域，记作f(A)。同样的，在机器学习中，映射就是输入与输出之间的对应关系。

来源：Wikipedia

逻辑技术

人工智能领域用逻辑来理解智能推理问题；它可以提供用于分析编程语言的技术，也可用作分析、表征知识或编程的工具。目前人们常用的逻辑分支有命题逻辑（Propositional Logic ）以及一阶逻辑（FOL）等谓词逻辑。

来源：机器之心

目标函数技术

目标函数f(x)就是用设计变量来表示的所追求的目标形式，所以目标函数就是设计变量的函数，是一个标量。从工程意义讲，目标函数是系统的性能标准，比如，一个结构的最轻重量、最低造价、最合理形式；一件产品的最短生产时间、最小能量消耗；一个实验的最佳配方等等，建立目标函数的过程就是寻找设计变量与目标的关系的过程，目标函数和设计变量的关系可用曲线、曲面或超曲面表示。

来源：百度百科

过拟合技术

过拟合是指为了得到一致假设而使假设变得过度严格。避免过拟合是分类器设计中的一个核心任务。通常采用增大数据量和测试样本集的方法对分类器性能进行评价。

来源：Wikipedia

降维技术

降维算法是将 p+1 个系数的问题简化为 M+1 个系数的问题，其中 M<p。算法执行包括计算变量的 M 个不同线性组合或投射（projection）。然后这 M 个投射作为预测器通过最小二乘法拟合一个线性回归模型。两个主要的方法是主成分回归（principal component regression）和偏最小二乘法（partial least squares）。

来源：机器之心

交叉验证技术

交叉验证，有时亦称循环估计，是一种统计学上将数据样本切割成较小子集的实用方法。于是可以先在一个子集上做分析，而其它子集则用来做后续对此分析的确认及验证。一开始的子集被称为训练集。而其它的子集则被称为验证集或测试集。交叉验证的目标是定义一个数据集到“测试”的模型在训练阶段，以便减少像过拟合的问题，得到该模型将如何衍生到一个独立的数据集的提示。

来源：维基百科