@TOC

前言

Hello！
非常感谢您阅读海轰的文章，倘若文中有错误的地方，欢迎您指出～
 
自我介绍 ଘ(੭ˊᵕˋ)੭
昵称：海轰
标签：程序猿｜C++选手｜学生
简介：因C语言结识编程，随后转入计算机专业，获得过国家奖学金，有幸在竞赛中拿过一些国奖、省奖…已保研。
学习经验：扎实基础 + 多做笔记 + 多敲代码 + 多思考 + 学好英语！
 
唯有努力💪
 

知其然 知其所以然！

 
本文仅记录自己感兴趣的内容

简介

原文链接：https://epubs.siam.org/doi/10.1137/1.9781611974973.37

会议：Proceedings of the 2017 SIAM International Conference on Data Mining (SDM CCF B类)

年度：2017

Abstract

网络嵌入是学习给定社会网络中节点的低维向量表示，方便了社会网络分析中的许多任务，如链路预测

现有的绝大多数嵌入算法都是针对无符号社交网络或只有正链接的社交网络设计的

然而，社交媒体中的网络可能既有积极的联系，也有消极的联系，签名社交网络几乎没有工作存在

从有符号网络分析的最新研究结果来看，负向链接除了具有正向链接的特性和附加价值外，还具有独特的特性和附加价值，这给有符号网络嵌入带来了挑战和机遇

在本文中，我们提出了一个用于符号网络嵌入的深度学习框架SiNE

该框架优化了由社会理论指导的目标函数，提供了签名社交网络的基本理解

在两个真实的社交媒体数据集上的实验结果表明了该框架的有效性

1 Introduction

大型社交媒体网络的日益普及大大促进了社交网络分析

网络嵌入旨在学习节点的低维向量表示，已被证明在社会网络分析的许多任务中都很有用，如链接预测[1]，社区检测[2]，节点分类/聚类[3,4,5]和可视化[6]

现有的绝大多数算法都是为没有符号或只有正面链接的社交网络设计的

然而，社交网络可以同时包含正面和负面链接，这种签名社交网络存在于各种社交媒体网站上，如

• 带有信任和不信任链接的Epinions
• 带有朋友和敌人链接的Slashdot

关于签名网络嵌入的研究相当有限

---

有符号网络中负链接的存在挑战了一些解释无符号社交网络中链接形成和属性的原则

有符号社交网络的原则与无符号社交网络的原则有很大的不同[7,8]

例如，无符号网络的同质效应和社会影响可能不适用于有符号网络[9]

因此，单纯扩展无符号社交网络的嵌入算法是无法实现有符号网络嵌入的

最近关于挖掘签名社交网络的研究表明，在各种分析任务中，负面链接比正面链接更有价值

例如，少量的负面链接可以显著提高正向链接预测性能[10]，也可以提高社交媒体[11]中的推荐性能

虽然签名网络嵌入具有挑战性，但这种方法的结果有潜力极大地推进挖掘签名社交网络的任务，如链接预测

---

在本文中，我们研究了社交媒体中的签名网络嵌入问题

为了实现这一目标，我们需要

• (1)一个有符号网络嵌入的目标函数，因为无符号网络嵌入的目标函数不能直接应用
• (2)表示学习算法对目标函数进行优化

从社会科学中提炼出来的社会理论提供了对签名社交网络的基本理解，并为挖掘签名社交网络[12]的各种任务提供了动力，而深度学习技术为表示学习提供了强大的工具，增强了语音识别、自然语言处理和计算机视觉[13]等各个领域

这促使提出了用于签名网络嵌入的深度学习框架SiNE

SiNE学习节点的低维向量表示，同时从社会理论中保留了对签名社交网络的基本理解

---

本文的主要贡献如下:

• 以社会理论为指导，设计签名社会网络嵌入目标函数
• 提出了一种用于签名网络嵌入的深度学习框架SiNE，通过优化目标函数学习节点的低维向量表示
• 对来自社交媒体的两个签名社交网络进行实验，验证所提出框架SiNE的有效性

2 Related Work

网络嵌入或网络表示学习是学习给定网络节点的低维向量表示

在网络分析的许多任务中，如链路预测[1]，团体检测[2]，节点分类[3]和可视化[6]中，已经被证明是有用的

数据稀疏是这些任务面临的共同问题

为了解决稀疏性问题，网络嵌入在一个统一的低维空间中对每个节点进行编码和表示，这有助于我们更好地理解语义相关性，并进一步缓解了稀疏性[14]带来的不便

网络嵌入受到越来越多的关注，各种无符号网络嵌入方法被提出[15,16,1,6,14,17]。

---

例如

• [16]，对拉普拉斯矩阵进行谱分析，用top-k特征向量作为网络节点的表示
• [1]中采用Adamic/Adar、Katz等无符号网络分析方法测量的相似度评分来表示节点，用于无符号链路预测
• t-SNE[6]通过随机邻域嵌入将加权无符号网络嵌入到低维以实现可视化
• DeepWalk[14]引入了NLP中的单词表示模型Skip-gram的思想，从社交网络中的随机漫步序列中学习节点表示
• node2vec[18]通过定义一个灵活的节点网络邻域概念和设计一个有偏随机漫步过程来扩展DeepWalk
• HOPE[19]研究了有向网络的网络嵌入问题

然而，上述算法是针对无符号网络设计的，没有考虑负链接，而负链接已经被证明比正链接具有不同的特性和附加价值[10,20]

---

大多数的网络嵌入算法，如光谱分析、t-SNE、DeepWalk和node2vec，都利用了两个链接节点可能相似的同质效应或社会影响作为它们的向量表示

但对于有符号网络，由于负链的存在，这就不成立了，负链通常用来表示两个节点之间的不信任或敌对关系

因此，单纯扩展无符号社交网络的嵌入算法是无法实现有符号网络嵌入的

此外，在各种分析任务中，消极环节比积极环节具有更高的附加值

例如，少量的负面链接可以显著提高正向链接预测性能[10]，也可以提高社交媒体[11]中的推荐性能

虽然负面链接是有价值的，但对签名网络嵌入的研究还很有限

• 在[10]中，基于程度的特征(如进入节点的正、负链接数)和基于三元组的特征(包括三元组的结构信息)被手工定义并从网络中提取，以表示有符号网络中用于符号预测的节点
• [21]的另一项工作扩展了有符号网络的谱分析

本文利用社会理论研究了符号社会网络的学习嵌入问题

特别地，我们提出了一个新的框架SiNE，该框架对扩展的结构平衡理论进行建模，并优化了一个基于深度网络的目标函数来自动学习符号网络嵌入

3 Signed Network Embedding

在本文中，矩阵用粗体大写字母书写，向量用粗体小写字母表示

• 对于任意矩阵 $M$， $M_{ij}$ 表示 $M$ 的第 $(i, j)$ 个条目，而 $m^i$ 和 $m_j$分别表示 $M$ 的第 $i$ 行和第 $j$ 列

• 向量 $m$ 的第 $i$ 个元素表示为 $m_i$

• $‖M‖_F$ 是 $M$ 的 Frobenius 范数

• 矩阵 $M$ 和向量 $m$ 的转置分别表示为 $M^T$ 和 $m^T$

• 书法数学字体中的大写字母（例如 $V$）用于表示集合， $|V|$是 $V$ 的基数

• 设 $G = \{V, E\}$ 是一个有符号网络，其中 $V = \{v_1, v_2, . . . , v_m\}$ 是一组 $m$ 个节点， $E ⊂ V × V$ 是一组链接

• 特别地，任何链接 $e_{ij} ∈ E$ 可以是 1 或 -1，其中 $e_{ij} = 1$ 表示 $v_i$ 和 $v_j$ 之间的正链接，而 $e_{ij} = -1$ 表示负链接

3.1 An Objective Function for Signed Network Embedding

最近关于有符号社交网络的研究表明，负面链接呈现出与正面链接截然不同的属性，而驱动有符号社交网络和无符号社交网络链接形成的基本原则也截然不同[9,22,7]

这表明我们需要一个新的目标函数来嵌入有符号的社交网络，因为我们不能将这些目标函数直接应用于有符号的社交网络

---

社会理论(Social theories)是社会科学家为了解释签名社交网络中的社会现象而发展起来的，它提供了对签名社交网络的基本认识

如链路预测[7]、团体检测[23]等

社会理论在挖掘有符号社会网络的各种任务中得到了广泛的应用，这表明社会理论可以指导我们开发有符号网络嵌入的目标函数

事实上，无符号社交网络的社会理论已经被广泛用于设计无符号社交网络嵌入的目标函数

例如homophily[24]和social influence[25]等社会相关理论表明，两个连接的用户可能拥有相似的兴趣，这是许多无符号网络嵌入目标函数的基础[16,15]

受无符号网络成功应用社会理论的启发，我们寻求有符号网络的社会理论来进行有符号网络嵌入

---

在社会理论中，结构平衡理论(Structural balance theory) 是研究符号社会网络最重要、最流行的理论之一

因此，我们在此基础上开发了一个有符号网络嵌入的目标函数

结构平衡理论最初在个体水平[26]中提出，由Cartwright和Harary[27]在群体水平的图论形成中推广，然后发展到[28]中可聚类图的概念

它最近被[29]扩展为:签名社交网络中的一个结构应该确保用户应该让他们的“朋友”比他们的“敌人”更近，也就是说，用户应该坐得更靠近他们的“朋友”(或正面链接的用户)比他们的“敌人”(或负面链接的用户)

换句话说，扩展结构平衡理论的关键思想表明，用户应该更像她的朋友，而不是她的敌人

---

扩展的结构平衡理论为我们构建学习网络嵌入的符号社会网络模型提供了指导

我们现在将详细介绍如何基于扩展结构平衡理论建模签名社交网络

假设 $P$ 是一组三元组 $(v_i, v_j, v_k)$，如图 1(a) 所示

来自给定的签名社交网络 $G$，其中

• $v_i$ 和 $v_j$ 具有正链接
• 而 $v_i$ 和 $v_k$ 具有负链接

形式上， $P$ 定义为：

[29]中扩展的结构平衡理论表明，对于一个三元组 $(v_i, v_j, v_k)∈P$，在一定的相似性度量条件下， $v_i$与具有正链接的用户 $v_j$的相似性可能大于与具有负链接的用户 $v_k$的相似性

其数学模型为:

其中

• $x_i, x_j, x_k$分别是 $v_i, v_j, v_k$的 $d$维向量表示

我们需要通过本文提出的嵌入框架学习这些向量

• 在 $f (x_i, x_j)$中， $f$是一个衡量 $x_i$和 $x_j$之间相似性的函数
• 参数 $δ$是一个阈值，用于调节这两种相似性之间的差异。一个大的 $δ$会使 $v_i, v_j$更近， $v_i, v_k$更远

---

在真实世界的有符号网络中，Eq.(3.1)中的目标函数对2跳网络只有正或负连接的节点没有影响

也就是说，我们无法学习这些节点的 $d$维向量表示因为 $P$中没有包含它们的三元组

这些节点包含在图1(b)和图1 $(c)$所示的三联组中

---

根据[9]最近的一项研究，在社交媒体中，形成负面链接的成本高于形成正面链接的成本

因此，在签名社交网络中，正链接比负链接更密集

这决定了有很多节点的两跳网络只有正连接，而只有极少数节点的两跳网络只有负连接

因此，接下来我们只考虑处理只有正连接的2跳网络的节点，尽管类似的解决方案可以应用于处理其他类型的节点

---

我们首先引入一个虚拟节点 $v_0$，然后在 $v_0$和每个2跳网络中只有正链路的节点之间创建一条负链路

这样，图2(a)(或图1(b))中原来的三元组 $(v_i, v_j, v_k)$就会产生两个三元组(或 $(v_i, v_j, v_0)$和 $(v_i, v_k, v_0)$)，如图2(b)和2 $(c)$所示

设 $P_0$为三元组 $(v_i, v_j, v_0)$的集合，其中 $v_i$和 $v_j$有正联系， $v_i$和 $v_0$有负联系，可以得到类似于Eq.(3.1)的目标函数:

其中

• $δ_0$是调节相似性的阈值

在Eq.(3.2)和Eq.(3.1)中使用 $δ_0$和 $δ$的原因是

• 通过调整 $δ$和 $δ_0$，我们可以更灵活地区分有或没有虚拟节点的三元组

通过添加虚拟节点，我们可以使节点 $v_i$的2跳网络只包含与邻居更近的正链接

3.2 The Proposed Framework SiNE

由式(3.1)、(3.2)可知，扩展结构平衡理论指导下的有符号社会网络嵌入目标函数为:

式中

• $C = |P| + |P_0|$为训练数据的大小
• $X = \{x_1, x_2，…， x_m\}$是 $m$个节点的低维表示
• $θ$是定义相似函数 $f$的一组参数
• $R(θ)$是避免过拟合的正则化器
• $α$是控制正则化器贡献的参数

3.3 The Architecture of SiNE

有了上面给出的目标函数，现在的任务是找到一个能够给出良好相似性度量的函数，并学习到有符号网络中节点的良好表示

$f$的一个选择是非线性函数，在相似性度量和表示学习[30]方面已经证明比线性函数优越

在众多的非线性函数中，深度学习已经被证明是最先进的和非常强大的非线性表示学习[31,30]

这表明我们可以利用深度学习的力量来学习节点的非线性嵌入

特别地，我们设计了一个深度学习框架SiNE，它定义了 $f$与 $θ$，并优化了Eq.(3.3)中的目标函数

---

为了帮助更好地理解SiNE，我们首先研究一个具有2个隐藏层的深度学习框架架构的示例(参见图3)，然后将其推广到N层

请注意，我们在图中没有显示bias

框架的输入是从有符号的社会网络中提取的三联集 $(v_i, v_j, v_k)$，其中 $e_{ij} = 1, e_{ik} =−1$

该模型由两个具有相同参数的深度网络组成

两个深度网络的第一隐含层(即图3中的“第一隐含层”)的输出如下:

其中

• $tanh$为双曲正切函数，是深度网络中应用最广泛的激活函数之一
• $W^{11}$和 $W^{12}$是第一隐含层的权值
• $b^1$是偏差

然后， $z^{11}$和 $z^{12}$分别被用作两个深度网络的第二层隐藏层(或图3中的“第二层隐藏层”)的输入

同理，第二层的输出为: $z^{21} = tanh(W^2z^{11} + b^2)$和 $z^{22} = tanh(W^2z^{12} + b^2)$

$f(x_i, x_j)$和 $f(x_i, x_k)$是两个深度网络的输出:

它们是Eq.(3.3)中的项，向量 $w$是权重，标量 $b$是bias

通过对本文提出的具有2层隐藏层的框架的图解，我们可以看到相似函数 $f$是由深度网络定义的，其参数集合如图3所示

特别地，在图3中， $θ$被定义为 $θ = \{W^{11}, W^{12}, W^2, w, b^1, b^2, b\}$，相应地我们定义 $R(θ)$为:

注意，我们也可以为 $θ$选择其他正则化子，例如基于 $L_1$范数的正则化子，我们希望将其作为未来的工作

---

现在，我们将2层隐藏层的示例扩展到N层深度网络

对于N层深度网络，参数为 $X, x_0， θ = \{W^{11}, W^{12}, W^2，…， W^N, b^1，…， b^N, w, b\}$，其中

• $W^n$为第 $n$层的权值
• $b^N$为第 $n$层 $1 < n ≤ N$的偏差

第一个隐层的输入是三元组 $(v_i, v_j, v_k)$，即 $x_i, x_j, x_k$

第 $n$层的输入为 $1 < n ≤ N$，即 $(n - 1)$层的输出，即 $z^{(n - 1)1}$和 $z^{(n - 1)2}$

第一层的输出由Eq.(3.4)给出，第 $n$层的输出 $1 < n < N$为:

第 $N$层的输出为

3.4 Optimization of SiNE

按照常用的方法，我们采用反向传播算法对正弦信号的深度网络进行优化

反向传播的关键思想是通过反向传播“误差”来更新参数，从而高效地计算梯度

基本上，我们想优化Eq. (3.3) w.r.t到X, x0和θ

优化Eq.(3.3)的关键步骤是得到 $max(0, f (x_i, x_k) +δ−f (x_i, x_j))$和 $max(0, f (x_i, x_0) +δ−f (x_i, x_j))$对参数 $X, x_0$和 $θ$的梯度

有了梯度，我们就可以用梯度下降法更新参数

3.5 Training SiNE

我们根据深度网络的参数，即 $θ$、符号网络嵌入 $X$和虚拟节点嵌入 $x_0$，基于小批量随机梯度下降训练SiNE

众所周知，对于社交媒体中的签名社交网络，节点的链接数遵循幂律分布，即许多节点只有少量链接，而只有少量节点有大量链接

这将导致一些节点有大量的训练三元组

为了节省计算成本，遵循word嵌入[32]中相同的思路，对于有大量训练三元组的节点，我们随机抽取训练三元组的一个子集进行训练

子集的大小选择S = 300

换句话说，每个节点最多有300个训练三元组

深度网络参数的初始化遵循[33]中引入的方法

具体来说，我们从区间

均匀采样，初始化隐含层 $i$的权值，其中

• $d_{i−1}$是第 $(i−1)$层的单位数
• $d_i$是第 $i$层的单位数

将有符号网络嵌入 $X$初始化为零矩阵

提出的框架SiNE的训练算法总结在算法1中

3.6 Time Complexity

4 Experimental Results

4.1 Datasets

4.2 Analysis of the Embedding

4.3 Signed Link Prediction in Signed Social Networks

4.4 Convergence Analysis

4.5 Parameter Analysis

5 Conclusion

现有的大多数网络嵌入算法都是针对无符号网络设计的

而签约社交网络几乎没有工作

虽然由于负面链接的可用性，签名网络嵌入具有内在的挑战性，但它可以为挖掘签名社交网络的各种任务带来好处

本文研究了符号网络嵌入问题

特别地，我们引入了一个新的目标函数，在扩展结构平衡理论的指导下进行符号网络嵌入，并提出了一个深度学习框架SiNE来优化该目标函数

通过对社交媒体中两个有符号网络的实验，我们证明:

• (1)学习嵌入能够保留扩展结构平衡理论所表明的有符号社交网络原则
• (2)与代表性基线方法相比，SiNE学习的嵌入可以显著提高链路预测性能

有几个方向需要进一步调查

• 首先，提出的框架SiNE只能处理无向有符号社交网络，我们想研究如何将其扩展到有向有符号社交网络
• 其次，我们证明了嵌入可以提高有符号社交网络中链接预测的性能;因此，我们将研究嵌入如何有利于其他签名网络挖掘任务，如节点分类，情感分析[36]和多任务学习[37]
• 最后，除了结构平衡理论，还有其他社会理论，如地位理论;因此，未来我们将研究如何在这些社会理论的基础上开发有符号网络嵌入的目标函数

读后总结

2022/07/24 第一次阅读

文章针对的网络是含有正/负符合的

主要的目的是使的在一个三元组 $(v_i,v_j,v_k)$中：节点更接近含有正链接的节点，远离含有负链接的节点

数学表示也就是：

• $\sigma$为阈值参数，用于调节这两种相似性之间的差异。一个大的 $δ$会使 $v_i, v_j$更近， $v_i, v_k$更远

有一种特殊情况：在一个三元组中，若只有正链接或只有负链接，那么这时候就需要引入一个虚拟节点 $v_0$

从而得到两个新的三元组

得到数学表示

由以上两种情况，得到最终的目标优化函数

然后再利用ML进行参数训练，直到收敛

结语

文章仅作为个人学习笔记记录，记录从0到1的一个过程

希望对您有一点点帮助，如有错误欢迎小伙伴指正