@TOC

前言

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

知其然 知其所以然！

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

简介

原文链接：https://dl.acm.org/doi/abs/10.1145/3366423.3380038

会议：WWW '20: The Web Conference 2020 （CCF A类）

年度：2020/04/20

ABSTRACT

在现实世界的网络中，节点可能有不止一种类型的关系

有符号网络是一类重要的有符号网络，它由正负两种关系组成

近年来，嵌入有符号网络受到越来越多的关注，而且由于节点之间的连接路径具有多种类型的链路，因此嵌入有符号网络比传统网络更具挑战性

现有的作品依靠社会理论来捕捉复杂的关系

然而，这种方法也存在着主要的缺陷，包括这些理论的不完备/不准确

---

因此，我们提出基于网络变换的嵌入来解决这些缺点

其核心思想是，我们不是直接从连接两个节点的复杂路径中找到它们的相似性，而是通过连接它们不同角色的简单路径来获得它们的相似性

我们利用这一思想来构建我们提出的嵌入技术，该技术可分为三个步骤:

• (1)将输入有向有符号网络转化为无符号二部网络，每个节点映射到一组我们称为角色节点的节点。每个role-node捕获原始网络中某个节点所扮演的某个角色
• (2)角色节点网络嵌入
• (3)通过聚合角色节点的嵌入向量对原始网络进行编码

我们的实验表明，新提出的技术大大优于现有的模型

1 INTRODUCTION

现有的大多数网络嵌入方法都是针对只有单一边类型[5]且两个节点之间的关系表示紧密的网络设计的

因此，它们主要尝试以一种相邻节点在嵌入空间[5]中更接近的方式对无符号网络进行编码

然而，现实世界的网络可能有不止一种链接类型，也就是说，一个网络可以有 $K$种类型的链接，其中每种类型代表节点之间不同质量的关系

---

有符号网络是一类重要的网络，有正负两种链接类型[6,27]。

各种各样的社交媒体网站，如亚马逊、维基百科和Epinions，都可以表现为一个签名网络，积极的信号代表信任、协议或友谊，而消极的信号可能显示不信任、分歧或敌意

由于既有正链又有负链，有符号网络的基本原理可能与经典网络截然不同

因此，单纯采用经典嵌入模型无法对有符号网络进行网络嵌入

虽然有符号网络的嵌入具有挑战性，但它有潜力极大地推进网络分析任务，如链接/符号预测[32]

---

近年来，签名网络嵌入越来越受到关注[4,8,19,31]

与许多无符号网络的嵌入模型相似，这些模型试图通过假设连接路径接近来寻找节点之间的相似性来嵌入网络

然而，在有符号网络中，基于路径的相似性是具有挑战性的，因为有符号路径可以指示近距离或远距离

现有的研究[4,8,19]依靠两种签名社会理论来解决这一挑战，即平衡理论[3,13]和地位理论[23]

然而，他们定义两个节点之间相似性的方式和社会理论的使用的一般架构与两个主要的挑战有关

• 首先，社会理论在解释符号网络结构时不完整/不准确，因此建立在社会理论基础上的模型受到影响，导致嵌入质量较低
  • 例如，已有研究表明，真实签名网络中只有约70%和65%的三元组坚持地位或平衡理论[16,22]
• 其次，经典嵌入模型旨在捕捉链接的存在/不存在，而已有的签名嵌入模型只使用两种可能的交互状态:正链接和负链接
  • 因此，由于忽略了链路缺失(第三种相互作用状态)，它们无法很好地重构链路的存在/缺失，导致链路预测性能较低

---

针对这些不足，我们提出了一种新的网络嵌入视角，即基于网络变换的嵌入

• 如果嵌入原网络具有挑战性，可以将其转换为另一个嵌入任务复杂度较低的网络

变换可以通过将原始网络中的每个节点映射到变换后的网络中的多个节点来实现

接下来，将转换后的网络进行嵌入

最后，对变换后网络得到的嵌入向量进行聚合，对原始网络进行编码

---

更具体地说，为了嵌入签名网络，我们引入了一个基于角色的签名网络嵌入(ROSE)，它可以绕过上述的挑战

其基本思想是将有符号网络转换为一个二部网络，其中每个节点分别担任“用户”（user）和“物品”（item）角色，分别是有符号链接的给予者和接受者

因此，有符号网络的每个节点都可以用一组角色进行建模，表示为角色节点(role-node)，通过无符号链接可以完全捕捉角色节点之间的关系

然后，最终这个改造后的网络可以利用最先进的无符号嵌入技术

图1是转换过程的一个示例

图1：将具有两个节点的有符号网络转换为角色节点的无符号二部网络。
左边是有符号网络
从左边可以看出：节点u对于节点v是正链接，是出度（out）
…

每个角色节点捕获原始网络中节点的某个方面

因此，通过聚合节点的角色节点的嵌入，可以得到节点的全面嵌入

我们引入了两种聚合方法，分别是固定聚合和目标感知聚合

• 固定聚合只是将所有角色节点嵌入连接在一起
• 目标感知聚合基于最近一种基于深度学习的推荐模型，该模型引入了用户[34]的目标依赖编码模型。在此基础上，我们提出了一种基于注意力机制的模型来聚合角色节点的嵌入，得到参与者对目标实体的出席权值。据我们所知，这是第一个在有符号网络中构建目标感知嵌入节点的工作

---

我们对提出的基于符号预测的嵌入模型和链接预测任务进行了评估

• 评估是在三个真实的数据集上进行的:Epinions、Wikipedia和Slashdot
• 实验结果表明，该模型的性能明显优于现有的所有方法
• 此外，我们证明了与现有模型相比，ROSE具有更高的灵活性和通用性

---

综上所述，该嵌入框架的主要贡献有三个方面:

• 首次介绍了基于网络变换的网络嵌入的总体思路
• 我们提出了一种新的专用网络转换方法来嵌入有符号网络，通过将它们转换为二部无符号网络，然后可以利用任何现有的艺术无符号嵌入方法，然后最终获得原始有符号网络的节点表示
• 通过我们提出的注意机制，我们提出了第一个目标感知的签名网络嵌入

2 PRELIMINARIES AND RELATED WORKS

2.0.1 Problem Formulation

设一个图被定义为 $G(V, E)$，具有一个链接类型映射函数 $φ: E→A$，其中

• $V$表示节点
• $E$表示链接，每个链接 $e∈E$属于一个链接类型 $φ(E)∈A$
• 无符号网络 $A$只有一个值，而有符号网络有两个值:正的和负的

给定图 $G$，节点编码的任务是学习函数 $f: V→|d|$

该函数将每个节点 $V$映射到 $d$维嵌入向量，该向量可以通过大小为 $|V| * d$的矩阵 $W$参数化

2.0.2 Unsigned network Embedding

嵌入模型可以描述为一个编码-解码框架[12]，它有四个组成部分:

• 1)一个两两节点相似函数
• 2)编码器函数，从相似度函数创建嵌入
• 3)解码函数，从它们的嵌入中恢复成对节点相似性
• 4)一个评估重构相似度值的损失函数

文献的主要区别在于嵌入方法如何定义节点相似性

然而，无符号相似函数的共同原则是，两个节点之间的无符号路径表示它们的亲密程度(如[10,26,28])

2.0.3 Signed network Embedding

无符号相似度函数不能直接应用于有符号网络，因为负边不代表亲密度

因此，嵌入有符号网络的挑战在于如何在不妨碍正向邻近性的情况下包含负边

现有的方法试图利用它们之间长度为一、二或更高阶路径的路径来捕获节点相似性

---

Single-length paths

在包含负链接的情况下嵌入有符号网络的一种简单方法是基于其近邻嵌入节点[14,29]

• 然而，这种方法的有效性有限，因为它不能捕捉节点之间的高阶近邻

• 在有符号网络中捕获全局结构是具有挑战性的

例如，给定一个包含 $m$个正链接和 $n$个负链接的路径（一条路径中有正有负）

• 如何定义节点的相似性?
• 路径表示节点之间的距离还是距离?

为了达到这个目的，之前的作品使用了两个标志性的社会理论，即平衡和地位，我们在下面定义

平衡理论[3,13]定义了一个循环，如果存在偶数个负环节，则为平衡，否则为不平衡
在三角形中有两个这样的例子:“我朋友的朋友就是我的朋友”和“我朋友的敌人就是我的敌人”
社会科学中的地位理论([23])认为“我尊敬的人应该比我的地位高”

因此，在有符号网络中， $u$到 $v$的正链路表示 $u$的状态高于 $v$，负链路表示 $u$的状态高于 $v$

---

Paths of length two

由于上述社会理论都是在三角形结构上形成的，已有的方法[4,32]使用这些方法来判断符号路径代表两个节点之间的近距离还是远

但是，这些方法不会超出长度为2的路径

因此，它们在掌握全局结构方面的权力有限

---

Longer paths

最近的研究主要依靠社会理论的扩展版本，试图捕捉嵌入过程中较长的周期路径

• [19, 35]都在签名网络上运行类似于node2vec算法的随机游走
• [9]应用于节点相关性
• [18]使用随机游走进行个性化排序。
• 然后，介绍了一种基于平衡理论[8]的图卷积网络嵌入符号网络的方法

---

总之，所有这些作品的共享策略是通过分析节点之间的路径来嵌入节点

如果一条路径表示距离较近，则嵌入距离较近的节点，否则则表示距离较远

然而，为了解释一条路径是否表明距离近，他们利用了一些强烈的假设，这些假设会自然地对嵌入过程产生噪声

此外，这种策略没有使用原则性的方法来获取距离较远的节点，因为它们之间没有链接/路径，也就是说，它只专注于捕获正/负路径

3 PROPOSED FRAMEWORK: ROSE

在本节中，我们将描述ROSE的结构

针对前人研究的不足，我们提出了以下要求:一种有效的通用网络嵌入模型应能够

• 1)捕获节点之间的高阶连通性
• 2)考虑到链接标签和链接结构(链接是否存在)
• 3)不假设网络的起源

Network transformation based embedding

为了满足这些需求，我们引入了基于嵌入的网络转换的一般概念

与其直接寻找输入网络中节点的相似性，不如将其转换到另一个网络中，在这个网络中，我们不会遇到输入网络中存在的嵌入挑战

一种可能的转换方法是为一个节点定义不同的角色，称为“角色节点”，并构建角色节点网络，通过采用经典的相似函数来确定角色节点之间的相似性

由于每个角色节点捕获原始节点的某个方面，目标节点的嵌入向量可以通过聚合相应角色节点的嵌入得到

综上所述，基于网络变换的嵌入模型可分为三个主要步骤:

• 1)网络变换
• 2)嵌入变换后的网络
• 3)通过对变换后的网络的嵌入集合来嵌入原始网络

基于网络改造的总体思路，我们提出了ROSE

在下面的内容中，ROSE将基于前面提到的三步架构进行描述

然后，我们将说明ROSE如何处理该问题的需求

3.1 Network transformation

定义角色节点的方式是ROSE有效性的基础

我们的目标是定义转换，这样角色节点之间的相似性可以使用经典方法得到

注意，可以有多种方法来定义转换过程

基于不同的相似性度量，引入了不同的嵌入技术

同样，通过创建不同的转换，可以基于基于转换的嵌入的思想开发不同的嵌入方法

我们的转型理念受到推荐系统的启发

传统上，推荐系统中的用户-商品交互采用用户-商品二分网络模型

签名的全对全连接网络也可以看作是一个二部网络，其中每个节点对于它创建的链接扮演“用户”角色，对于它接收的链接扮演“项目”角色

基于这个类比，我们通过转换过程分别捕获节点的用户/项角色

---

Step 1: Transformation to a bipartite network

通过用户-项目类比，将每个节点映射为两个角色节点，即将节点 $u$映射为角色节点 $u_{out}$和 $u_{in}$，将原始网络中 $u$到 $v$的链接建模为 $u_{out}$和 $v_{in}$之间的无向链接

由图2(a)可以看出，输入网络被变换为一个带符号的二部网络[7]，有“in”和“out”两种类型的节点

然而，由于正、负链接的存在，在转换后的网络上应用经典的相似性度量仍然是一个挑战

---

Step 2: Transformation to an unsigned network

我们通过定义新的rolenodes将网络转换为无符号网络

$v_{in}$类型的角色节点被映射为两个角色节点: $v^+_{in}$(或 $v^-_{in}$)表示当正面(或负面)链接指向它时它的角色

因此，从 $u_{out}$到 $v_{in}$的带有标签 $l$的链接被建模为 $u_{out}$和 $v^l_{in}$之间的无标签、无向链接

这使我们能够使用完善的相似性函数来确定角色节点的相似性

---

Step 3: Augmenting the network

我们的策略是通过嵌入转换后的网络来编码原始网络

但是，有些角色节点的程度可能很低

特别是，“ $in -$”类型的角色节点的程度往往很低，因为与正面链接相比，负面链接的数量往往不足

根据我们的研究结果，这将极大地阻碍这种角色节点的准确嵌入

为了解决这个问题，我们利用了问题领域的隐性知识

如果节点 $u_{out}$对 $v^+_{in}$和 $w^-_{in}$都有连接，它不仅反映了这两个角色节点之间的邻接关系
而且还暗示了它们相反的角色节点: $v^-_{in}$和 $w^+_{in}$之间的依赖关系

为了将这一知识引入到我们的嵌入过程中，从而减弱稀疏性问题，我们用一组类型为“out”的虚拟节点来增强我们的无符号网络，

即，对于无符号网络中每个类型为“out”的节点，其连接集为 $\{v1^{l_1}_{in}, v2^{l_2}_{in}，…， vn^{l_m}_{in}\}$

我们添加一个类型为“out-dummy”的节点，其连接集为 $\{v1^{l^{'}_1}_{in}, v2^{l_2^{'}}_{in}，…， vn^{l_m^{'}}_{in}\}$

• 其中 $l^{'}$是 $l$的逆，即如果 $l$是“-”， $l^{'}$是“+”，反之亦然

---

Summary of transformation

$G(V, E)$转化为二部无符号图 $G_u (V_u, E_u)$，其中 $|V| = 4|V_u|$， $|E| =2|E_u|$，即节点 $u∈V$映射到 $V_r$中的四个角色节点:

• 1)发起链接的 $u^{out}$
• 2)发起虚拟链接的 $u^{dummy}_{out}$
• 3) $u^+_{in}$接收到正链接
• 4) $u^−_{in}$接收到负链接

标签为 $l$的链接 $e_{u,v}$被转换为链接 $e_{u_{out},v^l_{in}}$和 $e_{u_{out}^{dummy},v^{l^{'}}_{in}}$

图2描述了该过程的一个示例

需要注意的是，变换是无损的，即 $G(V, E)$可以从 $G_u (V_u, E_u)$完全重构

3.2 Embedding the original network

类似于无符号网络，角色节点之间的链接表明它们的紧密程度

因此，可以使用一个经典的嵌入模型来嵌入角色节点

我们使用node2vec[10]

注意，更高级的嵌入模型[5,33]可以用于/设计这个目的

然而，在本文中，我们的重点是介绍ROSE的结构

一旦有了角色节点的嵌入，就可以通过聚合相应角色节点的嵌入来创建节点的嵌入

在下面的文章中，我们将介绍两种不同的聚合模型

---

Fixed Aggregation

每个角色都代表了原始网络中某个节点的某个视角/角色

一般来说，如果一个实体有多个表示，我们可以将它们串联起来或线性组合起来，以构建一个统一的表示

因此，建立一个全面统一的节点嵌入的一种直接方法是将相应角色节点的嵌入向量串联起来

因此，节点 $u$的固定表示可以定义为: $W_u = W_{u_{out}} ||W_{u^+_{in}} ||W_{u^−_{in}}$，其中 $||$表示串联

注意，聚合过程中不使用虚拟角色节点

事实上，“out-dummy”角色节点与类型为“out”的角色节点是反向的，并且不添加关于原始节点表示的额外知识

---

Target Aware Aggregation

图嵌入的一个重要应用是利用嵌入向量来预测节点的两两相互作用，例如链接预测

直观地说，对于这类任务，相对于目标实体，对给定的启动器节点进行编码更为准确

事实上，目标感知分析的思想是大多数推荐模型的基础

例如，在基于物品的协同过滤中，为了预测用户对某一物品的评价，她之前的评价以加权的方式聚合在一起，因为她的所有互动在反映她对[36]物品的品味方面并不同等重要

通常，评级的权重是根据对应条目与目标条目[34]的相似性确定的

受推荐系统的启发，我们引入了一种目标感知的嵌入技术，提出了一个目标感知的聚合模型

据我们所知，现有的技术只构建固定的嵌入

在我们的框架中，直观地预测 $u$到 $v$的成对交互依赖于 $u$的“出”角色节点和v的“在”角色节点

我们提出 $u$的“出”角色节点可以根据 $v$嵌入， $v$用 $W_{u^v_{out}}$表示

有了 $W_{u^v_{out}}$ , $u$ w.r.t. $v$的目标依赖嵌入定义为: $W^v_u = W^v_{u_{out}} ||W_u$

实际上，我们将 $u$的固定嵌入与一个依赖于目标实体的组件连接起来，以构建它的目标感知嵌入

为了建立 $W_{u^v_{out}}$，我们设计了一个注意力机制

我们建议 $W_{u^v_{out}}$可以通过关注 $u_{out}$的邻居来获得，基于它们与目标实体 $v$的相关性

更正式的定义是 $W_{u^v_{out}}$

其中

• $e(s^l_{in}, v)$为 $s_in$ w.r.t. $v$的重要权重
• $N (u_{out})$为与 $u_{out}$相连的角色节点集

为了估计重要性权重，我们引入了一个无监督注意模型

该模型背后的直觉是，如果两个节点在网络中连接得越紧密，两个节点的“在”角色节点之间的联系就越紧密

注意，我们没有考虑连接的标签来寻找两个节点的相关性

为了系统地实现这一思想，我们假设目标有符号网络是无符号的，并将其转化为二部份网络，得到的网络有两种类型的角色节点:“in”和“out”

接下来，利用node2vec嵌入转换后的网络

最后， $att(s^l_{in}, v)$的定义如下:

事实上，这个权值决定了 $s$和 $v$的连接紧密程度，与评级值无关

3.3 Model Justification

我们概述了有效的符号嵌入技术的三个主要要求。ROSE满足需求

• 1)与现有模型不同，ROSE不依赖于任何关于网络起源的假设
• 2)为了获得角色节点的嵌入，我们使用了一个基于随机游走的模型，以确保获得的嵌入获得更高阶的邻近性
• 3)该模型既保留了链接标签，又保留了链接结构

为了解决符号/链接预测任务，可以将ROSE的嵌入输入到一个非线性函数中，该函数通过MLP等方法训练来确定目标相互作用状态

事实上，角色节点的嵌入包含了可以帮助完全重构图的主要模式

我们对角色节点进行编码，如果从 $u$到 $v$存在一个标签为 $l$的链接，那么 $W_{u_{out}}$与 $W_{v^l_{in}}$的接近程度要高于 $W_{v^{l^{'}}_{in}}$

如果从 $u$到 $v$没有链接，则预计 $W_{u_{out}}$与 $W_{v^l_{in}}$和 $W_{v^{l^{'}}_{in}}$都有较低的接近度

因此，有一个函数来查找嵌入的相似性

• 如果 $W_{u_{out}}$到 $W_{v^l_{in}}$的接近程度大于它到 $W_{v^{l^{'}}_{in}}$的接近程度，那么从 $u$到 $v$的链接的标签有望是 $l$
• 如果 $W_{u_{out}}$与 $W_{v^+_{in}}$和 $W_{v^−_{in}}$的相似性较低，则表示没有链接。此外，我们在实验中观察到其他有趣的模式，这些将在实验部分中讨论

除了解决问题的需求之外，所提出的框架还创建了一个渠道，使推荐系统和签名网络上下文之间建立连接

最后，该模型具有较强的推广能力

由于该模型不依赖于任何特定于有符号网络的假设，因此可以推广到具有多种链路类型的网络

4 EXPERIMENTS

我们进行了实验，以验证所提出的框架和模型背后的思想的有效性。这些实验旨在回答两个关键问题:

• RQ1:在链接标签预测和链接预测任务方面，提出的嵌入框架与目前最先进的模型相比表现如何?
• RQ2:从角色节点网络中获得的嵌入是什么解释?

Datasets

4.1 Performance of the proposed model (RQ1)

4.2 Interpretation of the encodings of role-nodes (RQ2)

5 CONCLUSION

一般来说，现有的嵌入有符号网络的模型建立在基于路径的相似性度量上，其中使用社会理论来定义这种相似性度量

然而，这种构建嵌入模型的结构面临着重大挑战

• 1)社会理论不能准确解释签名网络的结构
• 2)基于该结构建立的模型主要关注链接标签，忽略了对链接存在/缺失的捕获

为了应对这些挑战，我们引入了一种新的基于网络变换的嵌入框架ROSE，该框架依赖于将原始网络转化为无符号二部网络

据我们所知，这是第一篇提出基于网络变换的嵌入思想的论文

此外，它能够对相对于目标实体的节点进行编码

我们的实验证实，该模型优于目前最先进的模型

此外，该模型可推广到具有两种以上连接类型的网络

我们计划研究如何在其他图类型中使用网络转换的思想，例如知识图[1,17,25,30]，这样它们也可以受益于目前为简单图开发的最先进的嵌入方法

读后总结

2022/07/24 第一次阅读

文章创新点很足，让人眼前一亮

针对signed netword，作者另辟蹊径

将其转化为一个角色二部图

然后再利用无符号图的嵌入方法进行嵌入每个角色（文章利用node2vec）

最后再节点的嵌入 $(W_{out},W_{in}^+. W_{in}^-)$再聚合起来

• 这里不聚合dummy节点
• 聚合方法有两种，固定聚合 或 利用注意力机制进行聚合

得到最终的节点嵌入

文章的厉害之处在于网络转化的思路，同时可以作为一个通用的框架，每个模块可以替代其余的嵌入算法（作者厉害👍）

结语

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

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