《Adversarial learning for weakly-supervised social network alignment》翻译

Abstract

如今，一个自然人加入多个社交网络来享受不同种类的服务是很常见的。跨多个社交网络连接相同的用户，也称为社交网络对齐，是一个重大的研究挑战的重要问题。现有的方法通常在成对的样本级别上链接社会身份，当可用的注释数量有限时，这可能导致性能表现并不优越。在同构信息的激励下，本文将社交网络中的所有身份作为一个整体来考虑，并从分布层面对社交网络进行对齐。我们的目标是学习一个投影函数，不仅最小化两个社交网络中用户身份分布的距离，而且将可用的标注作为学习指导。我们提出了三种模型SNNA$_u$u​、SNNA$_b$b​和SNNA$_o$o​来学习弱监督对抗学习框架下的投影函数。然后，我们评估该模型在多个数据集上的表现,结果证明我们的方案的优越性。

Introduction

最近社交网络变得越来越流行，用户可以同时在多个平台注册账户，享受不同类型的服务。在每个社交平台上，用户可以创建一个身份来代表他/她独特的个人形象。跨多个社交平台对同一自然人身份进行比对，即社交网络比对，因其巨大的实用价值而受到越来越多的关注。成功的网络对齐使许多应用受益，如朋友推荐、信息扩散预测和网络动力学分析。

现有的大多数方法都是有监督的，需要大量的人工标记样本来训练分类器将匹配的标识对与不匹配的标识对分离开来。考虑到获得标记实例的高成本，提出了几种半监督方法来合并未标记实例以提供补充信息。半监督方法可以利用未标记的数据来帮助捕获底层数据分布的形状，这在实践中更有希望实现社交网络对齐。

现有的半监督方法通常在成对样本级别执行网络对齐。 他们首先将来自不同社交网络的身份嵌入到一个共同的潜在空间中，其中来自同一网络的相似身份应紧密分布，而跨社交网络的带注释身份对也应分组在一起。 然后将身份之间的距离视为网络对齐的指标。 这种方法的主要局限性在于它们仍然需要大量注释以确保性能。 如图1所示，席琳·迪翁（Celine Dion）和阿黛尔（Adele）是受欢迎的歌手，史蒂芬·库里（Stephen Curry）是NBA球员。 考虑到他们的共同利益，席琳·迪翁（Celine Dion）和阿黛尔（Adele）在两种平台（Twitter和Facebook）上的距离都更近。 假设选择Celine Dion作为带注释的身份对。 传统的样本级半监督方法将生成潜在空间，如图2a所示。 席琳·迪翁（Celine Dion）的身份紧密分布，而潜在空间保留了单个网络内部的原始身份相似性。 但是，对于Twitter中的斯蒂芬·库里（Stephen Curry），他最近的Facebook邻居是阿黛尔（Adele），而不是他在Facebook中的身份，这导致了错误匹配。


与之前的半监督作品不同，我们将整个社交网络中的所有身份视为一个整体，并在分布级别上进行身份对齐。 如图1所示，由于利益共享，两个原始功能空间中的身份分布呈现相似的形状，这被称为跨社会网络的同构。如图2b所示，如果我们可以通过一组操作Φ（例如，转置）来转换Twitter空间中的身份分布，以最大程度地减少与Facebook中的身份分布之间的距离，则同一自然人的身份将彼此靠近分组。受同构启发，我们将社交网络对齐问题转化为学习操作Φ，以最小化两个分布之间的距离。 在之前的工作之后，我们将运算Φ称为投影函数。 通过从全局的角度介绍同构，进一步降低了对样品水平监督的要求。

这个想法需要一个分布距离的度量标准，为此我们引入了wasserstein距离（WD）。与KL散度等其他指标相比，WD是对称的，即使两个分布没有重叠也能够测量两个分布之间的距离。我们将每个身份分布视为一组加权积分，而WD则表征将一组积分传输到另一组积分中的最低成本。 但是，WD最小化是在分布级别上以无监督方式执行的，而标记的身份对则将指导信息保留在样本级别中。考虑到完全不同的目的和方案，我们利用可用的注释作为指标来指导分布最小化问题具有挑战性。

我们总结了我们的贡献：

• 我们从一个新的角度研究了弱监督社会网络一致性的新问题，引入分布紧密度以提供补充信息。
• 我们设计了三个基于对抗性学习的模型，以最小化分布距离并同时合并可用的注释。
• 我们在五组数据集上评估提出的方案， 实验结果表明了所提出模型的优越性能。

预备工作和问题定义

WD通过估计将一个分布改变为另一个分布的最小工作量来衡量两个分布之间的紧密性。WD的正式定义如下:

在这个任务中，$\mathbb{P}^I$PI和$\mathbb{P}^I$PI是两个离散概率分布，$\mathbb{P}= \sum _i p_i \delta _{x_i}$P=∑i​pi​δxi​​, $x_i$xi​是分布$\mathbb{P}$P,$p_i$pi​的一个样本，$p_i$pi​是其对应的概率能力，$\delta _{x_i}$δxi​​是狄拉克函数，$\Gamma (\mathbb{P}^I, \mathbb{P}^J)$Γ(PI,PJ)表示与边缘$\mathbb{P}^I$PI和$\mathbb{P}^J$PJ的联合概率分布$γ（x，y）$γ（x，y）。函数d测量两个样本之间的ground距离（例如欧几里德距离）。WD的目标是找到理想的联合分布，以达到期望的内界。

问题定义
我们用到了一个社交网络$N=\left \{ V,W,P \right \}$N={V,W,P},其中 $V=\left \{ v_1, v_2, ..., v_n \right \}$V={v1​,v2​,...,vn​}，是包含n个用户的用户集。每一个用户$v_i$vi​由一个d维特征向量$w_i$wi​表示，$w_i$wi​组成了特征矩阵$W\in \mathbb{R}^{d\times n}$W∈Rd×n,$P\in\mathbb{R}^{1\times n}$P∈R1×n包含社交用户的拓扑影响，例如输入度或输出度的计数。

定义1 弱监督社交网络对齐

给定两个部分对齐的社交网络$O=\left \{ V_O, W_O,P_O \right \}$O={VO​,WO​,PO​}, $E=\left \{ V_E, W_E,P_E \right \}$E={VE​,WE​,PE​}和一些匹配的身份对$M = \left \{ (v_o,v_e)|v_o \in V_O ,v_e \in V_E \right \}$M={(vo​,ve​)∣vo​∈VO​,ve​∈VE​},我们的目标是发现其他所有的匹配身份对$Y = \left \{ (v_o,v_e)|v_o \in ,v_e \in V_E,(v_o,v_e)\notin M \right \}$Y={(vo​,ve​)∣vo​∈,ve​∈VE​,(vo​,ve​)∈/​M},其中，$v_o$vo​和$v_e$ve​属于同一个自然人。

我们假设两个网络作品中的特征向量的维数都是d，这很容易被流行的网络作品嵌入模型所满足。在这里，我们旨在学习一个理想的匹配身份的投影函数。因此，所研究的问题可以进一步澄清如下：

定义2 社交网络对齐的投影函数

给定源分布$\mathbb{P}^O$PO, 目标分布$\mathbb{P}^E$PE和注释集$M = \left \{ (v_o,v_e)|v_o \in V_O ,v_e \in V_E \right \}$M={(vo​,ve​)∣vo​∈VO​,ve​∈VE​}。目标是学习一个映射函数$\Phi$Φ，映射函数$\Phi$Φ满足：(1) $\Phi$Φ应该最小化原模型分布$\mathbb{P}^{\Phi(O)}$PΦ(O)和目标模型分布$\mathbb{P}^{\Phi(E)}$PΦ(E)的WD距离。(2) 对于注释集$M$M中的匹配对($v_o, v_e$vo​,ve​), $\Phi$Φ应该最小化映射源点$\Phi (v_o)$Φ(vo​)和映射目标点$v_e$ve​。

训练过程结束后，给定一个源身份$v_o$vo​，可以根据目标社交网络中的身份$v_e$ve​与ground距离$d(Φ(v_o),v_e)$d(Φ(vo​),ve​)来选择他/她的匹配候选人。较小的ground距离意味着两个相同的人有更大的机会成为同一个自然人。

对抗学习框架

遵循先前的工作，我们选择线性变换作为投影函数$Φ$Φ。给定一个具有特征向量$w_o$wo​的源节点$v_o$vo​，其投影点定义为：$Φ(w_o)=G×w_o$Φ(wo​)=G×wo​，其中$G∈R^{d×d}$G∈Rd×d为变换矩阵。所研究的问题可以理解为矩阵$G$G的学习问题，我们也尝试用神经网络的非线性投影函数，但效果不好。这可能是因为非线性投影严重地改变了输入分布，进一步破坏了同构。Zhang等人引入GAN模型进行双语词汇归纳任务。受此启发，我们设计了以下SNNA模型，它不仅可以最小化WD，而且还包含了注释。

单向投影模型SNNA$_u$u​

首先我们提出了单向投影模型SNNA$_u$u​，它只将源分布单向投影到目标社交空间。图3显示了SNNA$_u$u​的框架。发生器$G$G可被视为投影函数$Φ$Φ，而鉴别器$D$D设计用于估计投影源分布$\mathbb{P}^{G(O)}$PG(O)和目标分布之间$\mathbb{P}^{E}$PE的WD。SNNA$_u$u​的目标可以大致定义如下：

其中，$w_o$wo​是来自源分布$\mathbb{P}^O$PO的源身份$v_o$vo​的特征向量(受到$\mathbb{P}^O$PO的拓扑影响$p_o$po​), $w_e$we​是目标分布的样本。遍历所有可能的联合分布以计算期望的$inf _{\gamma \in \Gamma (\mathbb{P}^E, \mathbb{P}^{G(O)})}$infγ∈Γ(PE,PG(O))​是很困难的（Zhang et al.2017b）。 Vallani等当ground距离d定义为欧几里得距离时，基于Kantorovich-Rubinstein对偶性提出了WD最小化目标的简单版本：

函数$f$f 必须是K-Lipschitz连续的，这意味着对于所有$x_1，x_2∈R$x1​，x2​∈R, $\left | f(x_1) - f(x_2) \right | \leqslant K\left | x_1 -x_2 \right |$∣f(x1​)−f(x2​)∣⩽K∣x1​−x2​∣,而且$K>0$K>0是Lipschitz常数。该目标旨在确定所有可能K-Lipschitz函数的上确界。前馈神经网络具有强大的逼近能力（Hornik 1991）。因此我们选择一个多层前馈网络以找到一个理想函数$f$f，该函数在图3中定义为鉴别器$D$D。鉴别器的目标函数是学习一个理想函数$f$f来估计$\mathbb{P}^{E)}$PE)和$\mathbb{P}^{G(O)}$PG(O)之间的WD距离：

其中$θ$θ是在鉴别器中使用的多层神经网络中设置的参数。 我们引入了裁剪技巧来满足K·Lipschitz限制，该限制在每次梯度更新后将权重$θ$θ限制在一个小窗口[-c，c]中。

生成器G被设计为最小化估计的WD。 在公式（2）中，G仅存在于第二项中，因此我们旨在通过最小化以下目标来学习理想的生成器：

随着loss逐渐减少，判别器的WD逐渐减小，从而导致同一个人的身份在目标空间中组合在一起。

同时，我们还结合了一些注释来指导投影函数的学习过程，如图3中的组件A所示。假设在一个训练批次中，我们有一组源身份及其匹配的目标身份表示为Mt ⊂M。对于标记集合Mt中的匹配身份对$(v_o，v_e)$(vo​，ve​)，我们旨在最小化投影源节点$G(v_o)$G(vo​)与目标节点$v_e$ve​之间的距离：


其中$w$w是相应身份的特征向量。 该目标结合了可用的注释，以促进学习投影功能。$λ_c$λc​是控制损耗$L_C$LC​权重的超参数。

这是SNNA$_u$u​的训练过程算法：

首先，我们从第2行到第8行对判别器进行训练，这是为了避免GAN崩溃的风险。然后通过最小化目标(3)和(4)的加权组合来更新生成器，如第9至13行所示，这意味着学习的生成器不仅最小化估计的WD，而且适合可用的注释。

双向投影模型SNNA$_b$b​

单向模型SNNA$_u$u​对投影矩阵G没有约束。Mu等已证明正交投影有助于更好地对齐用户身份。 正交投影在理论上因其数值稳定性而吸引人使用正交投影时，投影分布是通过旋转和缩放在平面中原始分布的反射，这将保留原始分布的内部特征。 因此，我们在投影矩阵的学习中增加了正交约束。

将传统的正交约束引入对抗学习很麻烦，因为它们的优化很困难。我们还设计了双向投影模型SNNA$_b$b​以潜在地引入正交约束。 如图4所示，SNNA$_b$b​在两个方向上进行投影。如果投影函数G使分布$\mathbb{P}^{G(O)}$PG(O)和$\mathbb{P}^{E}$PE之间的WD最小，则其转置形式$G^T$GT 应该能够使分布$\mathbb{P}^{G^T(E)}$PGT(E)和$\mathbb{P}^{O}$PO之间的WD最小化。考虑到输入网络部分对齐而分布$\mathbb{P}^{E}$PE和$\mathbb{P}^{G(O)}$PG(O)不同，则学习的投影矩阵只能是自洽的，可以接近于正交矩阵，但不完全正交。

SNNA$_b$b​模型可以很容易地由具有共享投影矩阵G的两个SNNA$_u$u​模型实现。第一个SNNA$_u$u​模型利用投影函数G作为生成器和判别器$D_e$De​来估计分布$\mathbb{P}^{G(O)}$PG(O)和$\mathbb{P}^{E}$PE之间的WD。 第二个SNNA$_u$u​模型使用生成器$G^T$GT作为投影和判别器，以估计分布$\mathbb{P}^{O}$PO和$\mathbb{P}^{G^T(E)}$PGT(E)之间的WD。两个SNNA$_u$u​模型的优化是迭代进行的。 训练结束后，我们仍然使用学习的投影函数G为网络O中的源身份选择目标候选者。

正交投影模型
与SNNA$_b$b​中使用的自洽假设不同，我们进一步引入了更严格的正交约束。 如果G是一个正交矩阵，则应使用转置矩阵$G^TGw_o = w_o$GTGwo​=wo​轻松地从其投影版本中恢复源分布，这可以确保社会身份和自然人可以双向转换。 由于重建后的分布可能与原始分布相同，因此学习的投影矩阵比SNNA$_b$b​模式更接近正交矩阵。 因此，我们设计了一个重构组件，将更严格的正交约束整合到对抗训练模型中。

如图5所示，我们旨在通过转置矩阵$G^T$GT从投影分布$\mathbb{R}^{G(O)}$RG(O)重构原始源分布$\mathbb{R}^{O}$RO。 重建的源分布定义为$\mathbb{R}^{O'}$RO′，我们引入以下目标函数以最小化原始分布和重建的源分布之间的差异：

其中$λ_r$λr​是用于控制重构误差权重的超参数。 随着损耗$L_R$LR​的最小化，学习矩阵G将更加正交。 通过将新定义的重建损失添加到算法1的第12行中，可以轻松地从SNNA$_u$u​扩展SNNA$_o$o​的训练过程。将了解投影矩阵是正交的，拟合可用的注释并使投影的源分布与投影之间的WD最小化。SNNA$_o$o​中生成器的损失函数是距离最小损失$L_G$LG​，注释指导损失$L_C$LC​和重构损失$L_R$LR​的加权和。

Experiments

Datasets 数据集我们使用两对社交网络数据集和三对学术合著者数据集进行评估。
数据集由我们公司的合著者抓取并格式化。 表1显示了详细的统计信息。

Data preprocessing
对于Twitter用户，他们的功能空间是基于发布的推文和好友关注关系而构建的。 对于推文，我们首先使用NTLK2词干处理已爬网的推文并删除停用词或稀有词。 之后，将单个用户发布的推文作为一个整体进行收集，然后由tf-idf特征向量表示。 我们进一步利用属性保留网络嵌入模型TADW将网络拓扑信息和文本属性封装到低维潜在空间中。 其他数据集的特征空间也使用TADW构造，但用户属性有所不同（Flickr用户的已发布图片标签和加入的组，新浪微博用户的微博文本和主题标签，以及豆瓣的兴趣标签和加入的组）。 对于社交网络，关注者的标准化计数被视为用户$v_i$vi​的拓扑权重$p_i$pi​，它将被用来从身份分布中采样训练样本。

对于DBLP数据集，我们首先根据2015年，2016年和2017年的出版物构建了三个共同作者子网络。对于共同作者子网络中的每个节点（作者），我们在相应的文献中收集该作者的已发表论文。 已发表论文的标题和摘要作为节点属性。 文本属性被格式化为tf-idf向量，然后由TADW通过共同作者关系嵌入到潜在特征向量中。 对于合著者网络，我们将节点的度数用作其采样权重。 请注意，独立学习不同网络的特征空间可以确保我们建议的通用性。

Baseline Methods
我们将我们的模型与以下最新的基线方法进行了比较，包括半监督和监督模型。

• MAH 是一个半监督模型，利用子空间学习算法，利用社会结构来提高链接性能。
• COSNET是一个基于能量的模型，考虑了多个网络之间的局部和全局一致性。开发了一种有效的次梯度算法来训练模型。
• IONE是一个统一的优化框架，用于联合训练用于捕获身份相似性的网络嵌入目标和用于跨网络连接身份的用户对齐目标。

Parameter setup
对于我们的建议，将潜在特征空间的维数d设置为100。在所有SNNA模型中，鉴别器D是仅具有一个隐藏层的多层感知器网络，因为过于强大的鉴别器可能会导致GAN损坏训练并使生成器失去对抗能力。对于生成器G，其投影矩阵被随机初始化为正交矩阵。 最小训练批量的大小为256，学习率α设置为0.0001。 如算法1所述，在每次训练迭代中将对鉴别器进行$n_d$nd​次训练，并将$n_d$nd​设置为5。裁剪权重c为0.01，注释权重λc设置为0.2，重构权重$λ_r$λr​设置为0.3。 基线是根据原始文件执行的。 对于CoLink模型，我们将SVM分类器用作基于属性的模型。 ULink模型是通过约束凹凸程序优化来训练的。

Evaluation Metric
遵循先前的工作，我们选择Hit-precision 作为评价指标。

其中$hit（x）$hit（x）是匹配的目标用户在返回的前k个候选目标身份中的排名位置。 根据预计的源标识与目标标识之间的ground距离选择最合适的候选对象。 Hit-P校正由匹配的身份对分数的平均值计算：$\frac{\sum_{0}^{m}h(x_i)}{m}$m∑0m​h(xi​)​，其中m是匹配的身份对中源身份的数量。

Experimental Results
对于每个数据集，我们随机选择匹配的身份对的$T_{tr}$Ttr​部分作为训练数据，并随机选择$N_{te}$Nte​个匹配的身份对作为测试集。 在这里，我们将训练比率$T_{tr}$Ttr​固定为10％，并将测试集$N_{te}$Nte​的大小设置为500。我们将建议的模型与基线进行比较，并报告k设置不同时的Hit-Precision分数。 我们重复此过程三遍，并报告平均分数。

表2示出了实验结果。 可以看到，所有方法在DBLP数据集上的表现都比在社交网络上更好。 这可能是因为合著者网络更加密集并且用户属性经过格式化和整洁。 由于COSNET引入了全局和局部拓扑相似性，因此其性能优于MAH方法。 作为一种监督模型，ULink在弱监督学习环境中实现了不良表现，因为它需要很大一部分注释（例如原始作品的80％）才能达到理想的性能。 CoLink可以在基线之间实现最佳性能，因为它精心设计了一个目标函数来合并属性，而基于属性的模型和基于关系的模型可以相互促进。
人们还可以看到，所有提案在具有不同设置的两个数据集上均优于基线方法。
这是因为引入了分布紧密度信息作为补充。 单向模型$SNNA_u$SNNAu​击败最佳基准（CoLink）约3％。 通过引入自洽约束，$SNNA_b$SNNAb​的性能进一步提高，这证明正交投影矩阵有助于更好地对齐身份。$SNNA_o$SNNAo​在所有方法中均达到最佳性能，比最佳基准（CoLink）高出7％。 与更严格的正交约束相比，$SNNA_o$SNNAo​的性能比$SNNA_b$SNNAb​进一步提高了3％。

Learing Behavior of the SNNA$_o$o​
对抗性学习也因其不稳定的训练行为而闻名。 因此，我们提出了在k = 5的DBLP1516数据集上$SNNA_o$SNNAo​模型的训练轨迹。 每进行1万次训练后，我们将保存一个检查点模型，最后可以得到100个检查点模型。 对于每个检查点模型，我们将其鉴别器的输出值记录为WD近似值，并在社交网络对齐任务中记录其Hit-P校正分数。 请注意，我们将近似的WD距离重新缩放为0到10的范围。

如图6所示，随着训练批次的增加，WD降低，而HitP矫正分数增加。 结果表明：1）提出的模型可以有效地降低动态分配情况下的WD。 2）较小的WD导致更好的网络对齐性能。 因此，我们可以将估计的WD距离最小的检查点模型保存为最终模型。

Parameter sensitivity study
最后分析了所提出的SNNA$_o$o​模型的参数灵敏度。我们首先分析了训练比率$T_{tr}$Ttr​对Twitter-Flickr数据集上模型性能的影响。我们修正了k=5，并用不同的$T_{tr}$Ttr​集展示了SNNA$o$o的性能。最佳基线CoLink也用于比较。从图7a可以看出，随着$T_{tr}$Ttr​的增加，两种方法的性能都提高了。SNNA$_o$o​始终优于CoLink，而它们之间的性能差距往往较小。这是因为注释可以弥补CoLink忽略分布贴近度信息的限制。接下来，我们研究重建权重$λ_r$λr​对模型性能的影响。当增大$λ_r$λr​时，Hit-Precision得分先增大后减小，说明适当的正交约束有助于提高性能。较大的$λ_r$λr​将使训练过程更集中于侦察任务，这可能会中断优化以达到最小的WD距离。

Related Work
现有的社会网络比对方法大致可以分为有监督的、半监督的和无监督的。大多数现有的相关工作都是在监督下进行的，其目的是训练一个二进制分类器，将匹配的用户身份对与不匹配的用户身份对分开。曼等人通过在潜在低维空间中连接身份，提出了一个有监督的社会网络工作对齐模型。将两个网络中的用户身份映射到一个潜在空间，并学习投影函数来链接属于同一自然子的身份。ULink也是一种嵌入监督方法。ULink首先将多个网络中的用户身份映射到一个潜在的空间中，然后最小化同一个人的用户身份之间的距离，最大化不同人的用户身份之间的距离。考虑到实现足够的注释来完全训练监督模式是非平凡且耗时的，提出了一些非监督的方法，这些方法主要依靠强鉴别特征来链接用户身份UUIL是这项工作的基础，但UUIL侧重于无监督学习，而SNNA旨在加入少量注释以提高对齐性能。最近，一些半监督方法被提议纳入未标记数据以捕获内部数据分布。Korula等人引入了一种流行的半监督模型，根据基于邻域的网络特征执行UIL任务。CosNet（Zhang等人。是一个基于能量的模型，通过考虑本地和全球一致性来链接用户身份。
现有的半监督方法通常将用户身份从成对样本层链接起来，在注释非常有限的情况下无法获得理想的性能。因此，在本文中，我们的目标是从分布层次上执行社会网络对齐。将所研究的问题转化为分布投影函数的学习，在对抗性训练框架下求解。

Conclusion
本文研究了一类新的弱监督社会网络对齐问题。结论是，我们从身份分布级别执行社交网络对齐，这有助于减少所需注释的数量。将所研究的问题转化为一个理想的投影函数的学习，不仅可以最小化两个社会网络的身份分布之间的wasserstein距离，而且可以在投影空间中将可用的匹配身份组合在一起。
此外，我们还提出了三个具有不同水平正交约束的SNNA$_u$u​、SNNA$_b$b​和SNNA$_o$o​模型。
我们在多个数据集上评估了我们的建议，实验结果证明了SNNA模型的优越性。