SIDE：有符号有向网络中的表示学习

5090SIDE：在有符号有向网络中的表示学习0Junghwan Kim，Haekyu Park，Ji-Eun Lee和UKang首尔国立大学首尔，韩国kjh900809，hkpark627，dreamhunter，ukang@snu.ac.kr0摘要0给定一个有符号有向网络，我们如何学习完全编码网络结构信息（包括边的符号和方向）的节点表示？节点表示学习或网络嵌入学习将每个节点映射到一个向量。该映射对网络上的结构信息进行编码，为一般的机器学习和数据挖掘框架提供低维密集的节点特征。由于许多社交网络允许通过有符号和有向边描述信任（朋友）和不信任（敌人）关系，将网络嵌入方法推广到从网络中学习符号和方向信息是至关重要的。此外，社会理论是有符号网络分析的关键工具。然而，现有方法中没有一种支持所有期望的属性：考虑符号、方向和社会理论解释。在本文中，我们提出了SIDE，一种在嵌入空间中表示边的符号和方向的通用网络嵌入方法。SIDE仔细制定和优化了直接和间接有符号连接的似然函数。我们为似然函数的每个组成部分提供了社会心理学解释。我们证明了算法的线性可扩展性，并提出了额外的优化技术来减少训练时间和提高准确性。通过对真实世界的有符号有向网络进行广泛的实验，我们展示了SIDE如何有效地将结构信息编码到学习到的嵌入中。0CCS概念0• 网络 → 在线社交网络；• 信息系统 → 数据挖掘；• 计算方法 →机器学习；0关键词0网络嵌入，表示学习，有符号有向网络0ACM参考格式：Junghwan Kim，Haekyu Park，Ji-Eun Lee和UKang。2018。SIDE：在有符号有向网络中的表示学习。在WWW2018：2018年Web会议上，2018年4月23日至27日，法国里昂。ACM，纽约，美国，10页。https://doi.org/10.1145/3178876.31861170本文发表在知识共享署名4.0国际（CC BY4.0）许可下。作者保留在个人和公司网站上传播作品的权利，并附上适当的归属。WWW2018，2018年4月23日至27日，法国里昂。© 2018IW3C2（国际万维网会议委员会），根据知识共享CC BY 4.0许可发布。ACM ISBN978-1-4503-5639-8/18/04。https://doi.org/10.1145/3178876.318611701 引言0给定具有有符号有向边的网络，我们如何学习每个节点的向量表示，编码网络拓扑的丰富信息？网络嵌入是网络分析中的一个基本问题，最近在数据挖掘社区引起了很大兴趣[1,2,4,7,9,21,23,28-31,33,34,37]。网络嵌入将节点映射到低维向量空间，总结了网络拓扑和链接结构的各个方面。因此，映射后的向量为传统的机器学习和数据挖掘框架提供了特征，用于解决各种任务，包括节点分类[25]，链接预测[16]和聚类[32]。此外，嵌入空间中的接近结构为排名节点提供了与重启随机游走方法[11,12,22,26,35,36]的替代方法。许多社交网络，如Epinions 1和Slashdot2，允许用户与其他用户建立积极（信任，友谊）或消极（不信任，反对）的连接。负面链接包含额外的信息[13]，可以提高在有符号网络中的多个任务（如链接符号预测[10]和节点分类[27]）中的性能。此外，链接方向是未来链接形成的重要预测因素[6]。然而，大多数现有的网络嵌入方法只关注建模基本的对称链接结构，未能利用负面链接和链接方向中的其他有用信息。在网络嵌入框架中建模符号和方向引入了以下挑战：一致解释两种符号，表示个体连接倾向以及利用多步连接。有几种针对有符号网络的网络嵌入方法的先前工作。由于谱理论的约束，谱方法[14,38]无法表示方向上的不对称性。Wang等人[31]采用神经网络架构来分离正面和负面连接，但他们的工作也不适用于有向网络。Yuan等人[37]利用对数双线性模型，该模型利用嵌入空间的黑盒模型，因此不提供社会理论解释。在本文中，我们提出了SIDE（有符号有向网络嵌入），一种适用于有符号有向网络的通用网络嵌入方法。SIDE成功地将有符号有向网络中的接近性表示为紧凑的低维向量。例如，如图1所示，SIDE在嵌入空间中更清晰地分离了聚类，而其他基线方法则没有。在嵌入空间中，社会实体之间的友好（蓝线）和不友好（红线）关系通过嵌入空间中的实体之间的距离有效地表示。表1从各个角度比较了SIDE与其他算法；SIDE是唯一的01 www.epinions.com 2 slashdot.org 3http://konect.uni-koblenz.de/networks/ucidata-gama0Track: Social Network Analysis and Graph Algorithms for the Web WWW 2018, April 23-27, 2018, Lyon, France5100（a）输入网络（b）SIDE（提出的方法）（c）SiNE（d）SNE图1：新几内亚东部中央高地网络3的可视化[24]。图1a表示具有有利（蓝线）和敌对（红线）关系的输入网络。图1b、1c和1d分别显示了SIDE、SiNE和SNE的嵌入结果。SIDE最好地保留了由不同节点形状标记的群组结构。0表1：SIDE和其他嵌入算法的比较。我们提出的方法SIDE适用于最一般的设置，并在所有指标上表现出最佳性能。0方法 考虑 考虑 预测 速度 符号？ 方向？ 准确性0N2V [7] 否 是 低 快速 MF [8] 是 是 中等 中等 BNS [38] 是 否中等 慢 SiNE [31] 是 否 中等 慢 SNE [37] 是 是 低 中等 SIDE 是是 高 快速0满足所需属性的方法：1）考虑符号和方向，2）准确，3）快速。我们的网络嵌入方法基于截断随机行走，并为表示正负边的有向连接设计了一般的似然函数。偏置因子用于模拟个体连接性。我们还将随机行走采样过程和似然函数推广到模拟包括符号和方向的多步关系。SIDE将向量空间几何与网络中的社会现象（如同质性、优先附着和平衡理论行为）密切关联。该关联分解了链接形成的双重因素，并为将我们的方法应用于有向网络的一般分析提供了坚实的基础。我们的贡献如下：0•算法。我们提出了SIDE，一种新颖的有向网络嵌入方法（第3节）。通过利用网络中的符号和方向，它在链接符号预测任务中达到了最先进的准确性。•分析。我们对SIDE进行了详细分析。我们分析并展示了我们公式中的组成部分与社会心理学解释相关联（第3.4节和第4.3节）。此外，复杂性分析证明了我们的算法具有可扩展性，与节点数量呈线性关系（第3.6节）。•性能。SIDE在准确性和速度方面表现出色（第4节）。SIDE在链接符号预测任务中达到了最先进的性能。此外，学习过程比具有神经架构的其他嵌入方法快1.8倍。0表2：符号表0符号定义0G = (V, E) 输入网络 s 符号分配函数 D 共现节点对 u, v节点 v' j 噪声节点 W out 输出嵌入矩阵 W in输入嵌入矩阵 b in, +, b in, - 正/负内偏置向量 b out,+, b out, - 正/负外偏置向量 σ sigmoid 函数 w每个节点的行走次数 l 每个行走的步数 k上下文窗口大小 n 噪声采样数 d 嵌入维度 λ正则化参数0本文中使用的方法代码和数据集可在http://datalab.snu.ac.kr/side上获得。本文的其余部分组织如下。我们在第2节中描述了预备知识。我们在第3节中详细介绍了我们提出的模型SIDE，并在第4节中给出了实验结果。在第5节中讨论相关工作后，我们在第6节中总结。02 预备知识0在本节中，我们首先描述了社会心理学理论，以更好地理解链接形成过程和链接符号结构（第2.1节）。然后我们提出了基于随机行走的网络嵌入公式（第2.2节）。表2列出了本文中使用的符号。02.1 社会心理学理论0我们采用社会心理学理论来理解有符号有向链接的形成。我们首先确定同质性和优先附着作为链接形成的两个驱动力。然后我们描述平衡理论来推断多步连接的符号。链接形成。我们将链接形成的原因分解为两个因素：相似性和连通性。同质性[17]解释了链接形成中的相似性因素。同质性被描绘为“物以类聚”，这表明一个节点更有可能连接到具有相似属性的节点。相似性自然是对称和传递的。因此，通过将相似的节点紧密地放在一起，将不相似的节点彼此远离，可以很好地模拟同质性。连通性因子由优先附着[20]所描述。它指出具有更高连通性的节点更有可能形成额外的链接。根据优先附着，链接形成的可能性是不对称的，并且由节点的个体连通性决定。例如，在现实世界的有向网络中，追随名人不太可能得到回应。在有符号有向网络中，正/负和入/出链接确定了四种不同类型的连通性。例如，社交网络中的名人倾向于接收比发出更多的链接，因为他们很受欢迎，而广告商倾向于形成许多出链以传播信息。由于其不对称和个性化的特性，对称度量空间不足以模拟优先附着。链接符号结构。平衡理论[3]是一个成熟的社会心理学理论，它陈述了以下四个规则：“我的朋友的朋友是我的朋友”，“我的朋友的敌人是我的敌人”，“我的敌人的朋友是我的敌人”和“我的敌人的敌人是我的朋友”。该理论只允许在有符号网络的三角形中存在偶数个负边。平衡理论提供了推断多步关系符号的基本规则。给定从节点u到另一个节点v的路径，从u到路径上的每个节点添加假设边形成多个三角形。通过依次应用平衡理论在这些三角形上，最终可以推断出u和v之间的关系的符号。因此，多步连接的符号是路径上边的符号的连续乘积。0主题：社交网络分析和Web上的图算法 WWW 2018年4月23日至27日，法国里昂5110网络嵌入方法将每个节点映射到一个向量，并将网络的链接结构编码为向量空间中的接近结构。通过保留网络拓扑信息，嵌入提供了用于解决网络上的节点分类、链接预测和社区检测等任务的机器学习算法的信息特征。网络嵌入问题的公式如下。设G = (V,E)是给定的具有节点V和边E的网络。网络嵌入方法旨在学习一个函数f：V→Rd，将每个节点v∈V映射到一个d维向量。嵌入函数由一个|V|×d的嵌入矩阵W参数化，该矩阵由每个节点的d维行向量组成。基于随机游走的网络嵌入[23]学习了与“目标”和“邻域”相对应的两个嵌入函数。通过利用语言模型，嵌入将网络结构编码为顺序结构。在本节的其余部分，我们将描述两个阶段的方法：随机游走生成和似然优化。通过生成多个截断的随机游走，该方法将图结构转化为顺序结构。然后，通过优化从随机游走中的节点共现频率中学习图的接近结构的似然函数。02.2 网络嵌入公式0网络嵌入方法学习将每个节点映射到一个向量，并将网络的链接结构编码为向量空间中的接近结构。通过保留网络拓扑信息，嵌入为现成的机器学习算法提供了有用的特征，用于解决网络上的节点分类、链接预测和社区检测等任务。网络嵌入问题的公式如下。设G = (V,E)是给定的具有节点V和边E的网络。网络嵌入方法旨在学习一个函数f：V→Rd，将每个节点v∈V映射到一个d维向量。嵌入函数由一个|V|×d的嵌入矩阵W参数化，该矩阵由每个节点的d维行向量组成。基于随机游走的网络嵌入[23]学习了与“目标”和“邻域”相对应的两个嵌入函数。嵌入通过利用语言模型来编码网络结构。在本节的其余部分，我们将描述两个阶段的方法：随机游走生成和似然优化。通过生成多个截断的随机游走，该方法将图结构转化为顺序结构。然后，通过优化从随机游走中的节点共现频率中学习图的接近结构的似然函数。0随机游走生成。在第一阶段，该方法在图上生成多个截断的随机游走。结果是揭示节点之间接近性的节点序列。每个步骤的游走根据边上的权重按比例选择下一个节点。然后我们生成多个共现对，用于计算和优化似然性。如果两个节点在随机游走序列中的短距离内放置，则定义这两个节点为共现对。如果节点对通过更重的加权和更短的路径连接，它们在随机游走节点序列中相互之间的步数更少的可能性更大。因此，节点对的共现统计信息编码了节点之间的接近性。截断的随机游走在生成接近节点的样本对方面是高效的[7]。虽然每个步骤的游走只需要生成一个随机数来选择下一个节点，但所选择的节点与多个接近节点形成对，从而增加了有效采样率。因此，通过利用增加的有效采样率，可以实现更好的时间复杂度。似然性优化。在第二阶段，该方法根据神经语言模型学习向量表示，特别是采用负采样的skipgram模型（SGNS）[18,19]。SGNS被制定为关于节点对共现的最大似然性。使用softmax函数对目标节点的邻居节点进行直接预测需要不可行的参数更新量。为了限制每步中更新的参数数量，SGNS采用了负采样方法，该方法对节点对的共现进行了二元分类，而不是直接预测共现节点。因此，SGNS的似然模型预测了模拟随机游走中一对节点是否共现。节点u与节点v链接的似然性定义如下：0P(u, v) = σ(Wu ∙ W'v) = 01 + exp(-Wu ∙ W'v) (1)0其中σ是一个sigmoid函数。Wu和W'v分别是“目标”和“邻域”嵌入向量。似然性对节点对是否共现进行二元分类。直观地说，内积值Wu ∙W'v较大的节点对具有更高的共现可能性。负对数似然性目标定义如下：0(u, v)∈D [-log P(u, v)+0n �0j = 1 - log(1 - P(u, v'j))] (2)0其中D是随机游走语料库中共现节点对的集合，vj是随机抽样的噪声节点。从第一阶段采样的每个共现示例对(u,v)用于进行一步梯度下降，以优化方程(2)的第一部分。对于每个共现示例(u, v)，定义多个噪声对(u,v'j)，其中vj是随机抽样的节点。噪声对构成了二元分类的负例，并用于方程(2)的第二部分。对于每个共现节点对，采样多个噪声对以解决由于现实世界网络中链接稀疏性导致的正例和负例不平衡问题。0Track: Social Network Analysis and Graph Algorithms for the Web WWW 2018, April 23-27, 2018, Lyon, FranceJ =�(u,v)∈D[− log P(u,v) +n�j=1− log P(u,v′j)]+ λ2 (∥bin,+∥2 + ∥bin,−∥2 + ∥bout,+∥2 + ∥bout,−∥2)(3)Track: Social Network Analysis and Graph Algorithms for the WebWWW 2018, April 23-27, 2018, Lyon, France51203 提出的方法0在本节中，我们描述了SIDE，我们提出的用于有向有符号网络嵌入的方法。03.1 概述0给定一个带有节点V、边E和符号分配函数s:E→{-1,+1}的有向有符号网络G。我们的目标是学习目标和邻域嵌入函数f、д:V→Rd，这些函数描述了包括符号和方向在内的链接结构。我们利用第2.2节中描述的基于随机游走的网络嵌入框架；嵌入函数通过最大化从有向随机游走中采样的节点对的似然性来得到。嵌入有向有符号网络面临以下挑战：0(1) 多步关系。如何将单步符号和方向推广到多步邻居？(2)负边。如何在嵌入空间中编码负链接而不妨碍正邻近性？(3)个体连通性。如何在链接形成中分别建模连通性因子和相似性因子？0我们提出以下主要思想来解决挑战。0(1)符号和方向聚合将单步符号和方向推广到多步连接的概念。路径上的符号按照平衡理论进行聚合，方向遵循图的拓扑顺序（第3.2节）。(2)符号接近度项为接近的正连接节点分配高似然，远离的负连接节点分配低似然。在最大似然框架下平衡正向拉力和负向推力（第3.3节）。(3)偏置项将个体节点的连通性与内积相似性分开建模。我们区分正/负和入/出偏置，以纳入每个节点连接模式的不对称性（第3.3节）。0算法1总结了SIDE的过程，并展示了主要思想的实现方式。SIDE首先模拟多个随机游走（第3到7行），并从模拟的游走中生成共现节点对(u,v)（第9行）。然后，对于每对采样的节点对(u,v)，执行梯度下降步骤（第10行）和噪声节点对(u,v')（第13行）来更新嵌入向量和偏置。在接下来的章节中，我们将详细描述我们的框架细节，进行社会理论分析，介绍额外的优化技术，并对SIDE的复杂性进行分析。03.2 符号和方向聚合0在SIDE的第一阶段，从随机游走过程中对节点对进行采样。采样过程首先从每个种子节点开始生成截断的随机游走。游走的每一步都遵循有向边，直到满足所需的长度为止；随机游走中节点的顺序符合有向网络的拓扑顺序。如果随机游走遇到死胡同，则剩余的步骤从种子节点重新开始。生成的游走序列由访问的节点和沿途边上的符号组成。然后从游走序列中选择窗口大小为k的共现节点对(u,v)。我们为每个共现节点对定义符号和方向，沿路径聚合信息。0算法1 SIDE算法0输入：带符号有向网络G = (V,E)，维度d，每个节点的游走次数w，每个游走的步数l，上下文大小k，噪声采样大小n，正则化参数λ 输出：嵌入矩阵W out和W in ∈ R |V|×d，正入链偏置b in,+，负入链偏置b in, -，正出链偏置b out, +，负出链偏置b out, -01: 将W out和W in初始化为随机值，将b in, +, b in, -, b out,+和b out, -初始化为零02: Walks = {} //随机游走生成03: 对于i从1到w循环04: 对于所有v ∈ V循环05: 从v开始生成长度为l的随机游走，并将其添加到Walks中06: 结束循环07: 结束循环 //似然优化08: 对于所有walk ∈ Walks循环09: 对于所有在walk中距离k以内的(u,v)循环010: 根据公式（5），通过梯度下降步骤更新W out u，W in v，bout，siдn(u,v)u和b in，siдn(u,v)v011: 对于j从1到n循环012: 随机采样v' ∈ V013: 根据公式（6），通过梯度下降步骤更新不带u的W和带v的W014: 结束循环015: 结束循环016: 结束循环0根据平衡理论，推断节点对的符号，如第2.1节所述：多步连接上的符号是路径上边符号的乘积。如果路径上有奇数个负边，则符号为负；如果路径上有偶数个负边，则符号为正。如果在随机游走中，节点u在节点v之前，则定义有向节点对(u,v)。这意味着在网络中从u到v有一个有向路径，因为随机游走中的顺序与网络中的拓扑顺序一致。通过分别识别和参数化源节点和目标节点，可以对非对称方向进行建模。03.3 似然性公式0我们现在描述将嵌入向量与采样对的似然性联系起来的最大似然公式。目标函数定义如下：0其中 ( u , v ) ∈ D是具有聚合符号和方向的节点对，如第3.2节所定义。对于每对 ( u , v )，有 n 个噪声样本∂J(u,v)∂W outu= −siдn(u,v)W inv (1 − P(u,v))∂J(u,v)∂W inv= −siдn(u,v)W outu(1 − P(u,v))∂J(u,v)∂bout,siдn(u,v)u= −(1 − P(u,v)) + λbout,siдn(u,v)u∂J(u,v)∂bin,siдn(u,v)v= −(1 − P(u,v)) + λbin,siдn(u,v)v(5)∂J(u,v′j)∂W outu= W inv′j (1 − P(u,v′j))∂J(u,v′j)∂W inv′j= W outu(1 − P(u,v′j))(6)5130v ′ j是随机选择的噪声对。目标函数的后半部分对似然函数中的偏差项进行正则化。似然函数 P ( u , v ) 定义如下：0如果 siдn ( u , v )  >  0，则为 σ ( W out u ∙ W in v +  b out , + u +  b in, + v )；如果 siдn ( u , v )  <  0，则为 σ (− W out u ∙ W in v +  b out , −u +  b in , − v )；如果 v 是噪声，则为 σ (− W out u ∙ W in v )。其中 siдn( u , v )表示第3.2节中定义的聚合符号。第一、第二和第三个方程分别定义了正、负和噪声对的似然性。方程 (4) 由两个部分组成：带符号的接近度项 ± Wout u ∙ W in v 和偏差项 b out , ± u ,  b in , ± v。带符号的接近度项。似然函数的第一个部分是带符号的内积接近度项 ± Wout u ∙ W in v。对于正连接的节点，似然值随内积项的增加而增加。另一方面，负和噪声对的似然值在内积相似性较低时较高。通过最大化目标函数，学习嵌入向量以为正连接的节点分配高相似性值，而为负连接的节点分配低相似性值。正向拉力和负向推力之间的平衡是在最大似然框架内实现的。因此，具有相似符号的入链和出链的节点学习相似的入链和出链嵌入向量。另一方面，具有相反符号的邻域结构的节点在嵌入向量空间中彼此远离。偏差项。我们使用偏差项 b out , ± u ,  b in , ± v作为似然函数的第二个部分。根据优先连接，更大的连接性引发了附加链接形成的更高似然性。我们的似然性公式通过偏差项来建模这种连接性。即使带符号的接近度项很小，高偏差项值也会导致链接形成的高似然性。偏差项描述了节点连接的非对称和个性化特性。偏差项分别针对每个节点和链接形成中的每种角色进行定义。如方程 (4)所示，每个链接的似然函数包含两个偏差项：源节点的出链偏差和目标节点的入链偏差。源节点和目标节点由第3.2节中描述的聚合方向确定。因此，可以为连接相同节点对的两个互补边分配非对称的似然值。此外，每个链接的似然性取决于哪些节点参与链接并构成链接的个性化特性。符号和方向定义了节点在链接形成中可以扮演的四种角色。对于每个节点 u ∈ V，我们定义了与每种角色对应的四个不同的偏差因子：正入链偏差 b in , +u ，负入链偏差 b in , − u ，正出链偏差 b out , + u 和负出链偏差 b out ,− u 。我们用 | V | × 1 的偏差向量分别表示每种类型的偏差，即 b in , + ，b in , − ， b out , + 和 b out , −。梯度下降优化。我们使用梯度下降优化来训练我们的模型。在梯度下降阶段，更新每个参数一步所需的导数对于共现对和噪声对是不同的。对于共现对 ( u , v ) ，更新两个权重向量 W out u ， W in v 和两个偏差因子 b out siдn ( u , v ) u ， b in , siдn ( u , v ) v 。目标函数的导数 J ( u , v )  =  −log  P ( u , v ) +0λ 2 (| b out , siдn ( u , v ) u | 2 +  | b in , siдn ( u , v ) v | 2 )对于共现对  ( u , v )  的权重向量和偏置因子的正则化如下所示：0其中似然函数  P ( u , v )  根据  siдn ( u , v )确定，如方程（4）中所示。对偏置项进行正则化是必要的，以防止偏置值发散。如果不应用偏置项的正则化，偏置的梯度更新始终为正，并且会不断增加偏置的值。对于噪声对  ( u , v ′ j )，只有两个权重向量 W  out u 和 W in v ′ j 被更新。0目标函数  J ( u , v ′ j )  =  −  log  P ( u , v ′ j ) 的导数如下所示：0其中似然函数  P (∙ ,  ∙)  定义如方程（4）中的第三个方程。03.4 社会理论分析0在本节中，我们描述了我们模型的社会理论解释。首先，我们声称符号接近度项与平衡理论一致。然后，我们确定了偏置项在优先附着中的作用。似然函数中的这两个组成部分建立了决定链接形成的两个因素，如第2.1节所讨论的：同质性和优先附着。根据平衡理论，正连接的节点倾向于在共享邻居上具有相似的符号，并具有相似的邻域结构。通过符号接近度项，我们的模型将具有相似符号邻域的节点放置在一起，将具有相反符号邻域的节点放置在远离的位置。我们推断，正连接的节点具有紧密放置的嵌入向量，而负连接的节点则在嵌入空间中远离。平衡理论与这种嵌入距离结构一致。例如，具有全部正边的三角形构造了三个紧密放置在一起的节点，具有两条负边的三角形构造了一个远离另外两个紧密放置节点的节点，具有全部负边的三角形将三个节点彼此远离。平衡理论不允许的三角形与嵌入空间中的亲密度的传递性不一致。因此，我们的嵌入方法自然地鼓励学习的嵌入向量遵循平衡理论。0Track: Social Network Analysis and Graph Algorithms for the Web WWW 2018, April 23-27, 2018, Lyon, FranceaEpinionsbSlashdotcWikipediaahttp://www.trustlet.org/wiki/Extended_Epinions_datasetbhttp://dai-labor.de/IRML/datasetschttp://snap.stanford.edu/data/wiki-Vote.html5140偏置项模型化了节点之间的个体连接性，而内积项模型化了节点之间的对称相似性。在学习过程中，每对示例都会增加相应类型的偏置值。我们将每个节点的偏置项解释为节点的连接性；我们期望对于出度较高的节点和入度较高的节点，学习到较大的出链偏置和较大的入链偏置。根据公式（4）中的似然函数，链接形成的似然性随着偏置项的增加而增加。因此，偏置项模型化了偏好附着过程，其中具有高连接性的节点的偏置项倾向于增加链接形成的似然性。03.5 附加优化技术0我们提出了两种额外的策略来加速网络的学习过程：删除度为1的节点和对高度节点进行子采样。在现实世界的网络中，大部分节点的度为1，因为现实世界网络的度分布遵循幂律分布。例如，我们的数据集中超过20％的节点的度为1，如表3所示。在随机游走序列中，具有正度为1的节点只与其唯一的邻居相连。因此，度为1的节点与其唯一的邻居共享其所有邻域结构；因此，学习过程执行了大量冗余计算。为了防止这种情况，我们删除具有正度为1的节点，并为减少的网络学习嵌入。然后，对于每个被删除的正度为1的节点，嵌入向量从唯一邻居的嵌入向量复制而来。通过删除度为1的节点，我们减少了优化过程中需要学习的参数数量。现实世界的网络还包含具有非常高度的节点，这些节点与大量节点连接，但大部分连接对于推断高度节点本身或相邻节点的接近结构都没有信息。受SGNS模型中的子采样启发，我们在随机游走生成过程中对高度节点进行子采样。每个节点u以概率1-η被丢弃。0其中p（u）是u的度。0由于p（u）的阈值超参数t是由边的数量提供的，我们将t固定为0.001，这是SGNS模型中常见的默认值。子采样能够增强随机游走采样过程的信息性，因为有效窗口大小增加了。03.6时间复杂度分析0在本节中，我们提供了SIDE时间复杂度线性可扩展性的证明。定理3.4是本节的主要结果，它使用SIDE每个阶段的三个引理进行证明。我们假设图存储在内存中，以便随机游走中的每一步都需要恒定的时间。0引理3.1.（随机游走生成的时间复杂度）随机游走生成需要O（| V |wl）的时间。0证明。我们为| V|个节点生成w个随机游走的l步。每个随机游走步骤需要随机选择出链节点，并且需要恒定的时间。综合以上两个结果，随机游走生成过程的时间复杂度为O（| V | wl）。□0表3：数据集统计。0节点数 131,828 82,140 7,118 边数 841,372 549,202 103,675正边的百分比 85.3% 76.1% 78.4% 负边的百分比 14.7% 23.9%21.6% 具有正度为1的节点的百分比 38.2% 25.5% 24.9%0引理3.2.（对采样过程的时间复杂度）对采样需要O（| V |wlk2）的时间。证明。我们为每个随机游走步骤生成k个节点对，总计为| V |wlk。每个节点对采样需要计算符号，平均需要O（k）的时间，因为我们需要计算节点对之间路径上的正边和负边的数量。因此，对采样的时间复杂度为O（| V | wlk2）。□0引理3.3.（梯度下降学习的时间复杂度）梯度下降学习需要O（| V |wlk（n + 1）d）的时间。证明。我们对| V |wlk个连接对进行n次噪声采样。从随机游走中采样的节点对数是| V |wlk，从噪声采样中采样的节点对数是| V | wlkn，总计为| V | wlk（n+1）。由于每个节点对的梯度下降更新需要O（d）的时间，梯度下降学习的总时间复杂度为O（| V | wlk（n + 1）d）。□0定理3.4（SIDE的时间复杂度）。SIDE的训练时间为O（| V|）时间。证明。SIDE由三个阶段组成：随机游走生成、对采样和梯度下降学习。结合前面的三个引理，并考虑到参数w、l、k、n和d是常数，SIDE的时间复杂度与节点数| V |成线性关系。□04 实验0在本节中，我们通过实验证明SIDE的性能，回答以下问题。•Q1.（符号预测）SIDE在推断未观察到的链接符号方面的预测能力如何？（第4.2节）•Q2.（表示）SIDE如何有效地表示有符号有向关系？（第4.3节）•Q3.（速度和可扩展性）与基线相比，SIDE的训练速度和可扩展性如何？（第4.4节）•Q4.（优化）SIDE的优化技术在时间和准确性方面的效果如何？（第4.5节）04.1 实验设置0数据。我们在三个真实世界的有符号有向社交网络数据集上进行实验：Epinions、Slashdot和Wikipedia。Epinions是一个产品评论网站，用户可以与其他用户建立信任和不信任关系。Slashdot是一个技术新闻网站，允许用户将其他用户注释为朋友或敌人。Wikipedia是一个百科全书网站，用户可以为其投票。0Track: Social Network Analysis and Graph Algorithms for the Web WWW 2018, April 23-27, 2018, Lyon, France5150表4：链接符号预测性能。SIDE在链接符号预测任务中展示了最先进的性能。0SIDE FE N2V MF BNS SNE SiNE（提出的方法）0AUC Epinions 0.967 0.951 0.764 0.920 0.893 0.820 0.860Slashdot 0.889 0.889 0.697 0.877 0.842 0.746 0.816 Wiki0.901 0.879 0.648 0.875 0.861 0.762 0.7900F1 Epinions 0.972 0.960 0.893 0.957 0.948 0.924 0.922Slashdot 0.911 0.906 0.811 0.910 0.895 0.874 0.887 Wiki0.918 0.907 0.879 0.913 0.901 0.882 0.8820与其他用户进行对比，以确定管理员晋升。数据集的统计信息总结如表3所示。基线。我们将SIDE与特征工程方法和五种嵌入方法进行比较。竞争对手如下：0•特征工程（FE）[15]。该模型为每条边定义了两种类型的手工特征：参与节点的有符号/有向度和从源节点到目标节点的符号/方向配置的两步路径。•Node2vec（N2V）[7]。这是一种基于随机游走的无符号网络嵌入方法。使用该方法在正子图上学习嵌入。•矩阵分解（MF）[8]。该方法通过矩阵分解学习有符号网络的低秩结构。•平衡归一化有符号拉普拉斯（BNS）[38]。该方法在修改后的拉普拉斯矩阵上应用谱嵌入，平衡正负链接。•有符号网络嵌入（SNE）[37]。该方法利用对数双线性模型进行随机游走采样。•有符号网络嵌入（SiNE）[31]。该模型训练深度神经网络，区分正连接节点和负连接节点。0参数。对于随机游走生成和嵌入维度，我们使用[23]中的参数设置：w = 80，l = 40，d =128。我们为每个数据集分别设置最佳上下文大小k、噪声采样大小n和正则化参数λ以获得最佳性能。对于基线方法，我们将维度设置为128，并使用其论文中建议的其他参数设置。04.2 链接符号预测0我们评估SIDE在链接符号预测任务中的预测性能。链接符号预测是在测试集中预测现有边的未观察到的符号的任务。为了关注嵌入方法的性能，我们使用嵌入向量作为特征训练一个简单的逻辑回归模型。由于每个节点都定义了一个嵌入向量，我们通过组合源节点和目标节点的两个向量来得到一个边特征。我们使用两种组合方法：逐元素乘积和连接。除了Epinions数据集的结果外，连接总是优于逐元素乘积。我们使用5折交叉验证。每个训练集用于训练嵌入向量和逻辑回归模型。0表5：有符号接近度项分析。正连接和负连接的有符号接近度平均值明显分离，超过了标准差。0正连接 负连接 P值0平均值 标准差 平均值 标准差 WT KS0Epinions 3.685 1.827 -2.763 1.631  < 0.0001  < 0.0001Slashdot 3.060 1.661 -0.745 1.408  < 0.0001  < 0.0001Wikipedia 2.538 1.073 -0.392 1.573  < 0.0001  < 0.00010图2：偏差和度数的相关性。随着度数分位数的增加，偏差值增加。这与偏差项的优先连接解释一致。0我们在表4中报告了各种方法的AUC和F1-score。指标越高，预测准确性越高。我们得出以下观察结果：0•SIDE在链接符号预测的准确性方面以AUC和F1-score为最佳。这证明了我们方法的卓越预测准确性。•特征工程（FE）方法是唯一可比较的竞争对手。FE使用专门针对链接符号预测任务的特征，并且在除SIDE之外的所有通用嵌入方法中表现优异。•SIDE和FE是唯一基于社会心理理论的方法。这表明了社会理论在解释现实世界网络中的符号结构方面的重要性。•仅在正子图上学习的Node2vec（N2V）方法显示了最差的准确性，因为在学习过程中没有提供符号信息。这表明了利用符号信息准确推断未观察到的边符号的重要性。04.3 嵌入分析0我们通过展示学习到的参数值与我们的设计目标一致来检验我们算法的正确性。我们检查了我们似然函数中的两个组成部分：有符号接近度项和偏差项。我们设计了有符号接近度项来区分正连接和负连接之间的距离。为了检查内积相似性项是否成功表示了链接符号结构，我们对正连接和负连接之间的内积值进行了Welch'st检验和Kolmogorov-Smirnov检验。Welch'st检验检查两个总体是否具有相等的均值，而不对方差做任何假设。Kolmogorov-Smirnov检验是对两个概率分布是否相等的检验。两个检验的p值的绝对值越小，说明两个总体的差异越大。0Track: Social Network Analysis and Graph Algorithms for the Web WWW 2018, April 23-27, 2018, Lyon, France51601.8倍0图3：SIDE的可扩展性。我们的算法比基准方法快1.8倍，并且在节点数量上呈线性可扩展性，斜率最小。0指示了正边和负边之间内积相似性的更明显的分布。表5显示了我们数据集中正边和负边的平均值和标准差的测试结果。测试的P值表明了两个边集之间均值和分布的差异的强有力的证据。此外，正边和负边集的平均值明显分离，超过了相应标准差的数量级。我们验证了偏差项学习过程中的优先连接解释。我们将节点分为5个桶，根据度数分位数进行划分。然后我们计算每个桶中正偏差值和负偏差值的平均和。我们将正偏差和负偏差相加，因为间接连接可能会增加相反符号的偏差。图2显示了平均偏差值和节点度数之间的关系。随着节点度数的增加，偏差项的期望值在入度和