一种基于用户结构和属性的无监督用户对齐方法

doi:10.13232/j.cnki.jnju.2020.01.001

一种基于用户结构和属性的无监督用户对齐方法

俞冬明, 李苑, 李智星, 王国胤^,

计算智能重庆市重点实验室，重庆邮电大学，重庆，400065

An unsupervised user alignment method based on user structure and attribute

Yu Dongming, Li Yuan, Li Zhixing, Wang Guoyin^,

Chongqing Key Laboratory of Computational Intelligence，Chongqing University of Posts and Telecommunications，Chongqing，400065，China

通讯作者: E⁃mail：wanggy.cq@hotmail.com

收稿日期: 2019-07-17 网络出版日期: 2020-01-09

基金资助:

国家重点研发计划. 2017YFB0802300

Received: 2019-07-17 Online: 2020-01-09

摘要

随着互联网应用的蓬勃发展，一个人在不同的社交网络平台上都拥有账户是很常见的.如何在多个社交网络上找到同一个人的账户，对许多应用是很重要的问题，也被称为用户对齐问题.在用户对齐问题上，目前有两个主要的挑战：首先，收集手工对齐的用户对作为训练数据的代价非常大,但传统的有监督方法往往需要大量的标注数据才能获得较好的效果；其次，不同网络中的用户的结构和属性往往不太相同，进一步增加了用户对齐的难度.提出一种无监督用户对齐方法SPUAL（Soft Principle for User Alignment），设计了一种新颖的基于用户的属性与结构的软对齐一致性原则，通过无监督方法计算用户对是否服从此原则来推断用户对是否对齐.在几个公共数据集上的实验表明，该方法的性能比目前最先进的无监督方法都有明显提高.

关键词： 用户对齐 ; 社交网络 ; 无监督 ; 对齐原则

Abstract

With the fast development of Internet applications，it's common for someone to have accounts on different social network platforms. How to find out which account on multiple social networks are of the same person is an important issue for many applications today，which is also known as the user alignment problem. There are two major challenges when it comes to user alignment. First，it's extremely expensive to collect manually aligned user pairs as training data，but traditional supervised methods often need a large amount of labeled data to achieve better results. Second，users on different networks often have different structures and attributes，which further increase the difficulty of user alignment. We propose an unsupervised user alignment method SPUAL (Soft Principle for User Alignment)，design a novel soft alignment principle based on user attributes and structure，and then infer whether the user alignment is correct or not by calculating whether the users meet to the principles by unsupervised method. Experiments on several common datasets show that the performance of our method is much better than the most advanced unsupervised methods.

Keywords： user alignment ; social network ; unsupervised ; alignment principle

PDF (430KB) 元数据多维度评价相关文章导出 EndNote| Ris| Bibtex 收藏本文

本文引用格式

俞冬明, 李苑, 李智星, 王国胤. 一种基于用户结构和属性的无监督用户对齐方法. 南京大学学报（自然科学版）[J], 2020, 56(1): 1-8 doi:10.13232/j.cnki.jnju.2020.01.001

Yu Dongming, Li Yuan, Li Zhixing, Wang Guoyin. An unsupervised user alignment method based on user structure and attribute. Journal of nanjing University[J], 2020, 56(1): 1-8 doi:10.13232/j.cnki.jnju.2020.01.001

近年来，很多用户已在不同的社交网络拥有账户，如微博、Twitter、Instagram或LinkedIn.由于不同的社交网络平台的功能不同，它们利用各自的优势吸引用户进行信息的寻找、分享和维护社交关系等操作.为了更好地享受服务，用户往往会加入多个社交网络，如用Twitter发布对突发热点事件的意见，用Instagram分享自己的休闲活动.然而不同的社交网络由不同的公司维护，彼此独立，所以无法判断不同的社交网络的不同用户是否属于同一个人，这就是用户对齐问题.解决用户对齐的问题通常需要更好更深入地了解个人用户，这会带来更好的商机.例如用户对齐之后可使社交网络的部分用户的信息更完整^[1,2]，还可以了解社交网络之间的用户迁移模式^[3]或帮助社交网站更准确地推荐潜在的朋友等.

虽然有监督机器学习算法在用户对齐问题中得到了广泛的应用，但标注训练数据的工作量却不容小觑.首先，寻找已知对齐的用户对非常耗时，因为需要搜索整个网络并仔细评估大量的候选对；其次，还要求人工标记人员有广泛的专业知识，例如在处理有软件开发背景的用户之前，必须知道“SDE”是“软件开发工程师”的缩写.另外，很多社交网络的数据通常涉及个人隐私，尤其是企业内部的社交网络，不会轻易交给人工标记者来进行人工标记.

无监督学习的优势是可以从无标记的数据中根据特定的原则学习数据的模式，因此非常适合大规模无标记数据场景下的用户对齐.目前，大部分无监督方法都集中于基于社交网络的拓扑结构来推断用户对齐关系.例如，IsoRank^[4]在社交网络中传播成对的拓扑结构相似性.NetAlign^[5]利用基于网络拓扑结构的最大乘积信念进行传播.BigAlign和UniAlign^[6]的方法是基于一个网络的邻接矩阵是另一个网络的噪声排列的假设来推断软对齐.这些方法背后的一个基本假设是拓扑一致性，也就是说，同一个用户在不同的社交网络中的社交关系具有一致性(例如，连接到相同或相似的邻居集).然而，这种假设在某些社交网络中并不适用.例如，一个用户可能在一个社交网站(如Facebook)上非常活跃，但在另一个网站(如LinkedIn)上却表现得很安静^[6].在这些情况下，基于拓扑结构的方法可能会产生错误的对齐结果.此外,这些方法无法利用用户的属性信息，所以也损失了用户的信息.FINAL^[7,8]提出用户对齐一致性原则，通过判断用户对是否满足对齐一致性原则来对判断用户对的对齐的一致性.虽然FINAL的思想很不错，但它要求用户对必须满足所有的对齐一致性原则才能保证他们的对齐性一致，这是严格的对齐过程.

由于社交网络复杂度高、噪声大，在不同的社交网络中对齐的用户的属性和拓扑结构可能会不同，又因为不同的社交网络注重性不同，如果对用户进行严格的对齐反而会导致很多的错误对齐.针对这个问题，本文提出一种基于用户结构和属性的无监督用户对齐方法SPUAL(Soft Principle for User Alignment)，主要贡献在于：

(1)利用基于用户的属性与结构建立新用户的软对齐一致性原则来推断用户对是否对齐；

(2)将用户对齐的问题转化成一个二次优化问题，并且转换成矩阵形式，从而可以更有效率地进行求解；

(3)进行了大量的实验，将SPUAL与最先进的无监督方法进行比较，证明了方法SPUAL的有效性.

1 相关工作

用户对齐问题近年来引起了广泛的研究兴趣，已有大量的相关文献.目前的一些主流方法主要分为监督的方法和无监督的方法.

有监督方法通过从用户的属性中提取特征，并使用监督分类器模型来预测用户对是否对.Goga et al^[9]基于属性的距离相似性特征训练逻辑斯蒂回归分类器，对候选对进行二分类.Liu et al^[10]使用基于词袋和距离的特征，将用户对齐问题作为多目标优化问题进行求解.Zhang et al^[1]采用基于词袋的特征和基本关系特征，并结合局部和全局一致性提出基于能量的模型.最近，许多基于嵌入的方法也被提出来^[11,12,13].然而，监督的方法都需要昂贵的带标签的训练数据，应用场景因此受限．

IsoRank^[4]是一种经典的无监督用户对齐方法，它是受到PageRank^[14]的启发.IsoRankN^[15]扩展了原有的IsoRank算法，并使用类似PageRank⁃Nibble^[16]的方法对多个网络进行对齐.Bayati et al^[17]提出一种利用最大乘积信念传播进行网络对齐的最大权值匹配算法.NetAlign^[5]将用户对齐问题转化为一个整形二次规划问题，可以最大限度地增加网络的平方数.Zhang and Yu^[18]分两步解决了多个匿名网络用户对齐问题，即无监督用户对齐推理和传递多网络匹配.这些方法都假设同一个用户在不同的社交网络的社交关系具有一致性，但这个假设在某些社交网络中并不适用，并且无法利用用户的属性信息.

FINAL^[7]提出用户对齐一致性原则，通过判断用户对是否满足所有的对齐一致性原则来判断用户对的对齐一致性.然而现在很多用户注重隐私保护，很多对齐的用户对不一定满足所有的用户对齐一致性原则.其次，FINAL把每个对齐一致性原则都等同对待，这在某些社交网络中并不适用，因为不同的社交网络注重性不同.有的社交网络注重用户的个人信息，这个时候属性一致性就比拓扑一致性重要得多；而有的社交网络注重社交关系，比如Twitter、微博，此时拓扑一致性就显得格外重要.针对这个问题，本文提出一种无监督用户对齐方法SPUAL，基于用户的属性与结构建立新的用户软对齐一致性原则来推断用户是否对齐.

2 问题定义

用户对齐的问题可以简单描述为在多个输入的社交网络之间找到对应的用户，这些在不同社交网络中的对应用户属于真实世界中的同一个人.表1总结了本文使用的主要的符号.另外，本文用黑体的大写字母表示矩阵（如 $A$ ），黑体的小写字母表示向量(如 $s$ )，小写字符表示标量（如 $a$ ）. $A (i, j)$ 表示矩阵 $A$ 第 $i$ 行和第 $j$ 列的元素， $A (i :)$ 和 $A (: j)$ 分别表示矩阵 $A$ 的第 $i$ 行和第 $j$ 列， $A^{T}$ 表示矩阵 $A$ 的转置， $D$ 是矩阵的度矩阵.一个矩阵的矢量化用 $v e c (:)$ 表示，并且结果向量用对应的黑体小写字母表示，如 $a = v e c (A)$ .

表1 符号和意义

Table 1 Symbols and notation

符号	意义
$G = \{A, N\}$	一个社交网络
$A$ $N$	网络的邻接矩阵网络用户的属性矩阵
$n_{1}$ , $n_{2}$	网络 $G_{s}$ 和网络 $G_{t}$ 的用户数
$K$	用户节点的属性个数
$a, b$	网络 $G_{s}$ 的用户索引
$x, y$	网络 $G_{t}$ 的用户索引
$v, w$	向量化对齐的节点对索引
$I, l$	分别是单位矩阵和值全为1的向量
$H$ , $S$	对齐前的偏好和对齐矩阵
$α, β, m$	对齐原则的权重以及正则化参数
$a = v e c (A)$ $D = d i a g (d)$ $\otimes$	将矩阵 $A$ 以列的顺序向量化对角化向量 $d$ 克罗内克积

新窗口打开| 下载CSV

用一个二元组表示一个网络： $G = \{A ∈ R^{n × n},$

$N = \{N^{1}, N^{2}, ⋯, N^{k}\}\}$ ， $A$ 是社交网络图的邻接矩阵 $, N$ 是社交网络用户的属性矩阵集合，集合的每一个元素 $N^{k} ∈ R^{n × n}$ 都是一个对角矩阵，表示用户节点是否具有属性 $k$ .如果用户节点 $a$ 具有属性 $k$ ，那么 $N^{k} (a, a) = 1$ ，否则 $N^{k} (a, a) = 0$ .其中 $n$ 为网络中用户的数量.所以，正式地将带属性的用户对齐问题定义如下：

问题：基于用户属性与结构的用户对齐

输入：一个源社交网络 $G_{s} \{A_{s}, N_{s}\}$ ，一个目标社交网络 $G_{t} \{A_{t}, N_{t}\}$ ，一个可选的对齐偏好矩阵 $H$ .

输出：输出一个 $n_{2} × n_{1}$ 的对齐矩阵 $S$ ，其中 $S (x, a)$ 表示源网络用户 $x$ 和目标网络用户 $a$ 的相似度.

上述定义中有一个可选的 $n_{2} × n_{1}$ 的输入矩阵 $H$ ， $H$ 中的每个元素都反映两个输入网络中两个用户节点对齐的可能性.它蕴含了社交网络中的先验知识，如果缺少这种先验知识，就将 $H$ 的每个元素都设为相等.

3 SPUAL

先简单描述FINAL^[7]，在此基础上提出一种新的无监督用户对齐方法SPUAL.

3.1　FINAL

FINAL^[6]的核心是对齐一致性原则，主要思想是如果两对用户节点本身满足对齐一致性原则，那么这两个输入网络的两对节点之间的对齐应该是一致的.如图1所示：图1中的两对节点是 $a$ 和 $x$ 以及 $b$ 和 $y$ ，如果这两对节点对满足对齐一致性原则，那么两对节点的对齐性应该是一致的.其中，对齐一致性原则包括：

图1

新窗口打开| 下载原图ZIP| 生成PPT

图1 对齐一致性的说明

Fig. 1 An illustration of alignment consistency

(1)拓扑一致性： $a$ 和 $b$ 在网络 $G_{s}$ 中是邻居关系， $x$ 和 $y$ 在网络 $G_{t}$ 中也是邻居关系.

(2)属性一致性： $a$ 和 $x$ 拥有相同的用户属性， $b$ 和 $y$ 也拥有相同的用户属性.

假设用户 $a$ 和用户 $x$ 已经对齐，如果它们的邻居 $b$ 和 $y$ 的用户属性相同，则 $b$ 和 $y$ 就有很大的机会对齐.基于这个假设，FINAL提出以下的目标函数，希望最小化目标函数(式(1))来得到对齐矩阵 $S$ ：

\begin{array}{l} J_{1} (S) = ∑_{a . b . x . y} {[\frac{S (x, a)}{\sqrt[]{f (x, a)}} - \frac{S (y, b)}{\sqrt[]{f (y, b)}}]}^{2} × \\ [A_{1} (a, b) A_{2} (x, y) × l (N_{1} (a, a) = N_{2} (x, x)) l (N_{1} (b, b) = N_{2} (y, y))] \end{array}

(1)

其中， $a, b = 1, …, n_{2}, x, y = 1, ⋯, n_{1}$ ； $l (·)$ 是一个函数，如果括号里的等式成立则这个函数等于1，否则为0； $f (·)$ 是一个用户节点对的规范化函数，它的计算如式(2)：

f (x, a) = \{\begin{matrix} ∑_{b, y} A_{1} (a, b) A_{2} (x, y) l (N_{1} (b, b) = N_{2} (y, y)) 如 果 N_{1} (a, a) = N_{2} (x, x) \\ 1 其 他 \end{matrix}

(2)

函数 $f (x, a)$ 是为了计算有多少对用户是用户 $x$ 和 $a$ 的邻居并且它们的用户属性一致(比如 $b, y$ ).

3.2　SPUAL

FINAL要求用户对必须满足所有的用户对齐一致性原则，才保证它们的对齐保持一致，这其实是一种严格对齐的过程.SPUAL的目标是实现软对齐,即当用户对不满足某些对齐一致性原则时，仍然可能保持对齐的一致.SPUAL提出了软对齐一致性原则：

(1)拓扑一致性： $a$ 和 $b$ 在网络 $G_{s}$ 中是邻居关系， $x$ 和 $y$ 在网络 $G_{t}$ 中也是邻居关系.

(2)属性一致性： $a$ 和 $x$ 拥有相同的用户属性， $b$ 和 $y$ 也拥有相同的用户属性.

(3)拓扑属性一致性： $a$ 和 $b$ 在网络 $G_{s}$ 中是邻居关系， $x$ 和 $y$ 在网络 $G_{t}$ 中也是邻居关系，并且 $a$ 和 $x$ 拥有相同的用户属性， $b$ 和 $y$ 也拥有相同的用户属性.

为了实现软对齐，SPUAL根据新的软对齐一致性原则提出了以下目标函数(式(3))，希望最小化 $J_{2} (S)$ 来得到对齐矩阵 $S$ ：

\begin{array}{l} J_{2} (S) = ∑_{a . b . x . y} {[\frac{S (x, a)}{\sqrt[]{f (x, a)}} - \frac{S (y, b)}{\sqrt[]{f (y, b)}}]}^{2} × α ⋅ A_{1} (a, b) A_{2} (x, y) + \\ β ⋅ l (N_{1} (a, a) = N_{2} (x, x)) l (N_{1} (b, b) = N_{2} (y, y)) + \\ λ ⋅ A_{1} (a, b) A_{2} (x, y) × l (N_{1} (a, a) = N_{2} (x, x)) l (N_{1} (b, b) = N_{2} (y, y)) \end{array}

(3)

可以看出，式(3)右端，SPUAL没有将各项对齐一致性原则相乘，而是相加，这样可以有效避免对齐的用户对可能存在的结构和属性不一致的情况，并对不同的对齐一致性原则赋予不同权重，这也解决了不同的社交网络侧重点不同的问题.

由于现在社交网络的用户属性不够完善，大部分用户的属性，如年龄、性别等，可能都是相同的，直接将属性一致性和其他对齐一致性原则相

加会带来很大的噪声.所以，提出新的目标函数，如式(4)所示：

\begin{array}{l} J_{2} (S) = ∑_{a . b . x . y} {[\frac{S (x, a)}{\sqrt[]{f (x, a)}} - \frac{S (y, b)}{\sqrt[]{f (y, b)}}]}^{2} × α ⋅ A_{1} (a, b) A_{2} (x, y) + \\ β ⋅ A_{1} (a, b) A_{2} (x, y) × l (N_{1} (a, a) = N_{2} (x, x)) l (N_{1} (b, b) = N_{2} (y, y)) v \end{array}

(4)

其中， $a, b = 1, ⋯, n_{2}$ ， $x, y = 1, ⋯, n_{1}$ ； $l (·)$ 的计算方式和式(1)相同， $0 < α, β < 1$ ； $f (·)$ 同样也是一个用户节点对规范化函数，如式(5)所示：

f (x, a) = ∑_{b, y} α ⋅ A_{1} (a, b) A_{2} (x, y) + β ⋅ A_{1} (a, b) A_{2} (x, y) × l (N_{1} (b, b) = N_{2} (y, y))

(5)

改进后的函数 $f (x, a)$ 计算的是用户 $x$ 和 $a$ 的用户属性一致邻居对的个数加上用户 $x$ 和 $a$ 的邻居对个数.注意，函数 $l (·)$ 计算的是两个输入用户节点有多少属性值相同，可将其分解如式(6)：

l (N_{1} (a, a) = N_{2} (a, a)) = \overset{K}{∑_{k = 1}} N_{1}^{k} (a, a) N_{2}^{k} (x, x)

(6)

将式(6)代入式(4)和式(5)，可以得到式(7)和式(8)：

\begin{array}{l} J_{2} (S) = ∑_{a . b . x . y} {[\frac{S (x, a)}{\sqrt[]{f (x, a)}} - \frac{S (y, b)}{\sqrt[]{f (y, b)}}]}^{2} × α ⋅ A_{1} (a, b) A_{2} (x, y) + \\ β ⋅ \overset{K}{∑_{k, k' = 1}} A_{1} (a, b) A_{2} (x, y) N_{1}^{k} (a, a) A N_{2}^{k} (x, x) N_{1}^{k^{'}} (b, b) N_{2}^{k^{'}} (y, y) \end{array}

(7)

f (x, a) = ∑_{b, y} α ⋅ A_{1} (a, b) A_{2} (x, y) + β ⋅ \overset{K}{∑_{k = 1}} N_{1}^{k} (b, b) N_{2}^{k} (y, y) A_{1} (a, b) A_{2} (x, y)

(8)

为了更方便地优化目标函数，将目标函数改写为矩阵的形式.通过将对齐矩阵矢量化(如 $s = v e c (S)$ )，根据矩阵点乘和克罗内克积的定义，式(7)可以被改写为式(9)：

\begin{array}{l} J_{2} (s) = \\ ∑_{v, w} {[\frac{s (v)}{\sqrt[]{D (v, v)}} - \frac{s (w)}{\sqrt[]{D (w, w)}}]}^{2} W (v, w) = \\ s^{T} (I - W^{'}) s \end{array}

(9)

其中：

v = n_{2} (a - 1) + x

w = n_{2} (b - 1) + y

W = α ⋅ A_{1} ⊗ A_{2} + β ⋅ N (A_{1} ⊗ A_{2}) N

W^{'} = D^{- 1 / 2} W D^{1 / 2}

$W^{'}$ 是 $W$ 的对称归一化矩阵. $W$ 的对角度矩阵 $D = α D_{1} ⊗ D_{2} + β D_{N}$ ，其中 $D_{1}$ 和 $D_{2}$ 分别是 $A_{1}$ 和 $A_{2}$ 的度矩阵， $D_{N}$ 的定义如式(10)所示：

D_{N} = d i a g (\overset{K}{∑_{k . k^{'} = 1}} (N_{1}^{k} A_{1} N_{1}^{k^{'}} l) ⊗ (N_{2}^{k} A_{2} N_{2}^{k^{'}} l))

(10)

其中， $D$ 的一些元素可能等于0，令那些值的负二分之一次方等于0，即 $D {(v, v)}^{- 1 / 2} = 0$ .通过上述描述，可将用户对齐问题的优化描述为式(11)：

\begin{array}{l} a r g m i n J_{2} (s) = \\ m s^{T} (I - W') s + (1 - m) {‖s - h‖}_{F}^{2} \end{array}

(11)

其中， $| | | |_{F}^{2}$ 是弗罗贝尼乌斯范数， $m$ 是正则化参数， $h = v e c (H)$ .与式(9)比较，式(11)多了一个正则化项，目的是使计算出的对齐矩阵不会与先验对齐偏好相差过大，同时也防止计算出来的对齐矩阵的元素全为0.当没有这样的先验信息时，则令 $h$ 为一个均匀列向量.

3.3　算法优化

式(11)中的目标函数本质上是一个二次函数,可以将其导数设为零来求解：

\frac{∂ J_{2} (s)}{∂ s} = 2 (I - m W^{'}) s + 2 (1 - m) h = 0

则可以推导出式(12)：

\begin{array}{l} s = m W' s + (1 - m) h = m D^{- \frac{1}{2}} W D^{- \frac{1}{2}} s + (1 - m) h = \\ m D^{- 1 / 2} [α ⋅ A_{1} ⊗ A_{2} + β ⋅ N (A_{1} ⊗ A_{2}) N] D^{- \frac{1}{2}} s + (1 - m) h = \\ m α D^{- 1 / 2} (A_{1} ⊗ A_{2}) D^{- 1 / 2} s + m β D^{- 1 / 2} N (A_{1} ⊗ A_{2}) N D^{- 1 / 2} s + (1 - m) h \end{array}

(12)

根据式(12)，可以利用迭代算法来计算 $s$ ，但是在迭代过程中需要计算 $A_{1}$ 和 $A_{2}$ 的克罗内克积，时间复杂度为 $O (M^{2})$ ， $M$ 为社交网络关系的个数.为了降低时间复杂度，利用克罗内克积的性质( $v e c (A B C) = (C^{T} ⊗ A) v e c (B)$ )，将式(12)改写为式(13)：

s = m α D^{- 1 / 2} v e c (A_{2} Q_{1} {A_{1}}^{T}) + m β D^{- 1 / 2} N v e c (A_{2} Q_{2} {A_{1}}^{T}) + (1 - m) h

(13)

其中， $Q_{1}$ 和 $Q_{2}$ 是矩阵 $q_{1} = D^{- 1 / 2} s$ 和 $q_{2} = N D^{- 1 / 2} s$ 按列顺序重新排列的 $n_{2} × n_{1}$ 的矩阵.根据上述推导，SPUAL的具体细节总结如下：

算法基于用户结构和属性的无监督用户对齐算法SPUAL

输入：

(1)网络 $G_{s} {A_{s}, N_{s}}$ 和 $G_{t} {A_{t}, N_{t}}$ ；

(2)可选的对齐前的偏好矩阵 $H$ ；

(3)对齐一致性原则的权重和正则化参数 $α, β, m$ ；

(4)迭代次数 $t_{m a x}$

输出：对齐矩阵 $S$

①计算度矩阵 $D$ 和用户属性矩阵 $N$ ；

②初始化 $s = h = v e c (H)$

③while $t ≤ t_{m a x}$ do

④ 计算矩阵 $Q_{1}$ 和 $Q_{2}$

⑤ 更新式(12)

⑥ 令 $t = t + 1$

⑦将向量 $s$ 按列顺序重新排列为 $n_{2} × n_{1}$ 的矩阵 $S$

4 实验与结果

4.1　实验设置

实验采用三种真实世界的具有用户属性的数据集Flickr⁃Lastfm，Flickr⁃Myspace，Douban Online⁃Douban Offline.

Flickr⁃Lastfm：根据部分已知的对齐用户，从中抽取两个子网络，这两个子网络分别拥有12974个和15436个用户.将用户的性别作为一个用户属性，根据用户节点的pagerank得分对用户节点进行排序^[1].将前1%的用户节点标记为“意见领袖”，接下来10%的用户节点标记为“中产阶级”，其余节点标记为“普通用户”.使用用户名相似度(编辑距离)来表示 $H$ .

Flickr⁃Myspace：和Flickr⁃Lastfm相同，根据已知对齐的用户，从中抽取两个子网络，其中Flickr子网络有6714个用户，Myspace子网络有10733个用户.对于用户节点属性和先验对齐偏好 $H$ ，使用和Flickr⁃Lastfm相同的方法.

Douban Online⁃Douban Offline：为豆瓣数据集构建一个对齐场景^[19]，根据用户在社交聚会中的共现情况构建Offline网络，共有1118个用户.从包含所有离线用户的Online网络中提取一个包含3906个用户节点的子网络.将用户的位置作为节点属性，根据用户之间的度相似度来计算 $H$ .

ACM⁃DBLP：根据部分已知的对齐用户，从中抽取两个子网络，这两个子网络分别拥有9872个和9916个用户.选择作者最活跃的会议作为用户属性，并且根据用户之间的度相似度来计算 $H$ .

表2显示了四个数据集的基本统计数据.

表2 四个数据集的信息

Table 2 Information of the four datasets

Dataset

Flickr⁃

Lastfm

Flickr⁃Myspace

Douban

ACM⁃DBLP

Number

12974~15436

6714~10733

3906~1118

9872~9916

Attributes

Sex,

Pagerank

Sex,

Pagerank

Location

Conference

H

Username Similarity

Degree Similarity

新窗口打开| 下载CSV

为了证明SPUAL的有效性，将SPUAL与六种设计良好或最先进的方法进行比较，包括Regal^[20]，FINAL^[7]，IsoRank^[4]，NetAlign^[5]，UniAlign^[6]，Klau's Algorithm^[21].

4.2　有效性分析

和FINAL一样，本文采用启发式贪婪匹配算法^[22,23]求出两个输入社交网络之间的用户一对一的对齐，并根据已知的对齐计算对齐准确率.实验结果如表3所示.

表3 不同数据集上不同算法对齐准确率的对比

Table 3 Accuracy of different algorithms on different datasets

Methods	Flickr⁃Lastfm	Flickr⁃Myspace	Douban	ACM⁃DBLP
Regal	0.01	0.01	0	0.003
IsoRank	0.4	0.36	0.07	0.21
NetAlign	0.43	0.45	0.01	0.03
UniAlign	0.1	0.03	0.01	0.01
Klau's Algorithm	0.38	0.4	0.07	0.12
FINAL	0.665	0.640	0.239	0.210
SPUAL	0.677	0.663	0.249	0.241

新窗口打开| 下载CSV

数据集Flickr⁃Lastfm和Flickr⁃Myspace的参数为 $m = 0.3, t_{m a x} = 30, α = 0.7, β = 0.3$ ；数据集Douban Online⁃Douban Offline的参数为 $m = 0.82, t_{m a x} = 30, α = 0.9, β = 0.1$ .从表3可以看出，SPUAL优于其他方法.首先，SPUAL的准确率远高于IsoRank^[3]，NetAlign^[4]，UniAlign^[5]和Klau's Algorithm^[19]，这是因为仅仅单独利用用户的拓扑结构或者属性不能很好地对用户进行对齐.而Regal的准确率低则是因为Regal在进行用户嵌入的时候，是将两个网络放在一起进行嵌入的，当两个网络的结构差距过大时这种方法的局限性很大，并且在降低时间复杂度时是用一种近似的方法来求解用户的相似性矩阵，导致最终的结果有很大误差.同时，在新的软对齐一致性原则下，进行软对齐的SPUAL的效果要优于FINAL，这也验证了SPUAL的合理性和正确性.

4.3　参数分析

为了了解SPUAL的参数是如何影响性能的，本研究在数据集Flickr⁃Lastfm和Flickr⁃Myspace中通过改变参数 $α - β$ 来分析不同的参数对精度的影响，实验结果如表4所示.可以看出，在不同的参数下，SPUAL的效果都是要优于其他方法的，这也再一次验证了SPUAL的合理性和正确性.从表中还可以看出结构一致性占的比重比属性一致性更大，这也符合现实中社交网络数据的真实情况.

表4 SPAUL在两个数据集中使用不同参数进行对齐的准确率对比

Table 4 Accuracy of SPAUL on two datasets using different parameters

Parameter( $α - β$ )	Flickr⁃Lastfm	Flickr⁃Myspace
0.7-0.3	0.677	0.663
0.8-0.2	0.675	0.655
0.9-0.1	0.670	0.659

新窗口打开| 下载CSV

5 结论

为了解决社交网络用户对齐的问题，本文结合用户结构和属性，通过建立新的用户软对齐一致性原则，提出一种无监督方法SPUAL来推断用户对是否对齐，并对其进行了优化.在细节上，SPUAL通过给不同的软对齐一致性原则不同的权重，再采用叠加的方式来判断用户对是否满足软对齐一致性原则，实现了软对齐的目标.在三个真实世界的数据集上进行实验来评估SPUAL算法，结果证明该算法的性能明显优于现有的方法.但目前SPUAL仅能处理静态网络的对齐问题，而在实际应用中用户网络往往是快速变化的，未来将基于SPUAL研究动态网络的用户对齐问题.

参考文献

原文顺序

文献年度倒序

文中引用次数倒序

被引期刊影响因子

[1]

Zhang

Y T

，Tang

，Yang

Z L

，et al.

Cosnet：connecting heterogeneous social networks with local and global consistency

∥Proceedings of the 21^th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.Sydney，Australia：ACM，2015：1485-1494.

[本文引用: 3]

[2]

Chen

，Yu

，Song

，et al.

Community⁃based network alignment for large attributed network

∥Proceedings of the 2017 ACM on Conference on Information and Knowledge Management.Singapore：ACM，2017：587-596.

[本文引用: 1]

[3]

Manners

H N

，Elmsallati

，Guzzi

P H

，et al.

Performing local network alignment by ensembling global aligners

∥2017 IEEE International Conference on Bioinformatics and Biomedicine (BIBM). Kansas City，MO，USA：IEEE，2017：1316-1323.

[本文引用: 2]

[4]

Smalter

，Huan

，Lushington

Gpm：a graph pattern matching kernel with diffusion for chemical compound classification

∥2008 8^th IEEE International Conference on BioInformatics and BioEngineering.Athens，Greece：IEEE，2008：1-6.

[本文引用: 4]

[5]

Bayati

，Gerritsen

，Gleich

D F

，et al. Algorithms for large，

sparse network alignment problems

∥2009 9^th IEEE International Conference on Data Mining.Miami，FL，USA：IEEE，2009：705-710.

[本文引用: 4]

[6]

Koutra

，Tong

，Lubensky

Big⁃Align：Fast bipartite graph alignment

∥2013 IEEE 13^th International Conference on Data Mining (ICDM). Dallas，TX，USA：IEEE，2013.

[本文引用: 4]

[7]

Zhang

，Tong

H H

Final：Fast attributed network alignment

∥Proceedings of the 22^nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.San Francisco，CA，USA：ACM，2016：1345-1354.

[本文引用: 4]

[8]

Zhang

，Tong

，Tang

，et al.

iNEAT：Incomplete network alignment

∥2017 IEEE International Conference on Data Mining.New Orleans，LA，USA：IEEE，2017：1189-1194.

[本文引用: 1]

[9]

Goga

，Perito

，Lei

，et al.

Large⁃scale correlation of accounts across social networks

Technical Report. Berkeley：University of California at Berkeley，2013：TR⁃13⁃002.

[本文引用: 1]

[10]

Liu

S Y

，Wang

S H

，Zhu

F D

HYDRA：Large⁃scale social identity linkage via heterogeneous behavior modeling

∥Proceedings of the 2014 ACM SIGMOD International Conference on Management of Data.Snowbird，UT，USA：ACM，2014.

[本文引用: 1]

[11]

Zhou

X P

，Liang

，Du

X Y

，et al.

Structure based user identification across social networks

IEEE Transactions on Knowledge and Data Engineering，2017，30(6)：1178-1191.

[本文引用: 1]

[12]

Liu

，Cheung

W K

，Li

，et al.

Aligning users across social networks using network embedding

∥Proceedings of the 25^th International Joint Conference on Artificial Intelligence.New York，NY，USA：AAAI Press，2016.

[本文引用: 1]

[13]

Zhang

，Chen

，Wang

，et al.

Mego2vec：embedding matched ego networks for user alignment across social networks

∥Proceedings of the 27^th ACM International Conference on Information and Knowledge Management.Torino，Italy：ACM，2018：327-336.

[本文引用: 1]

[14]

Page

，Brin

，Motwani

，et al.

The PageRank citation ranking：bringing order to the web

Technical Report. Stanford InfoLab，1999.

[本文引用: 1]

[15]

Liao

C S

，Lu

，Baym

，et al.

IsoRankN：Spectral methods for global alignment of multiple protein networks

Bioinformatics，2009，25(12)：i253-i258.

[本文引用: 1]

[16]

Andersen

，Chung

F R K

，Lang

K J

Local graph partitioning using pageRank vectors

∥2006 47^th Annual IEEE Symposium on Foundations of Computer Science (FOCS'06). Berkeley，CA，USA：IEEE，2006.

[本文引用: 1]

[17]

Bayati

，Shah

，Sharma

Maximum weight matching via max⁃product belief propagation

∥Proceedings of International Symposium on Information Theory (ISIT 2005). Adelaide，Australia：IEEE，2005.

[本文引用: 1]

[18]

Zhang

J W

，Yu

P S

Multiple anonymized social networks alignment

∥2015 IEEE International Conference on Data Mining.Atlantic City，NJ，USA：IEEE，2015：599-608.

[本文引用: 1]

[19]

Zhong

E H

，Fan

，Wang

J W

，et al.

ComSoc：adaptive transfer of user behaviors over composite social network

∥ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.Beijing，China：ACM，2012.

[本文引用: 2]

[20]

Heimann

，Shen

H M

，Safavi

，et al.

Regal：representation learning⁃based graph alignment

∥Proceedings of the 27^th ACM International Conference on Information and Knowledge Management.Torino，Italy：ACM，2018：117-126.

[本文引用: 1]

[21]

Klau

G W

A new graph⁃based method for pairwise global network alignment

BMC Bioinformatics，2009，10(S1)：S59.

[本文引用: 1]

[22]

Kollias

，Mohammadi

，Grama

Network similarity decomposition (NSD)：a fast and scalable approach to network alignment

IEEE Transactions on Knowledge and Data Engineering，2012，24(12)：2232-2243.

[本文引用: 1]

[23]

Zheng

Z D

，Zheng

，Yang

Pedestrian alignment network for large⁃scale person re⁃identification

IEEE Transactions on Circuits and Systems for Video Technology，2018，doi：10.1109/TCSVT.2018.

[本文引用: 1]

2873599.

DOI:10.1109/TCSVT.2018 [本文引用: 1]

Cosnet：connecting heterogeneous social networks with local and global consistency

2015

... 近年来，很多用户已在不同的社交网络拥有账户，如微博、Twitter、Instagram或LinkedIn.由于不同的社交网络平台的功能不同，它们利用各自的优势吸引用户进行信息的寻找、分享和维护社交关系等操作.为了更好地享受服务，用户往往会加入多个社交网络，如用Twitter发布对突发热点事件的意见，用Instagram分享自己的休闲活动.然而不同的社交网络由不同的公司维护，彼此独立，所以无法判断不同的社交网络的不同用户是否属于同一个人，这就是用户对齐问题.解决用户对齐的问题通常需要更好更深入地了解个人用户，这会带来更好的商机.例如用户对齐之后可使社交网络的部分用户的信息更完整^[1,2]，还可以了解社交网络之间的用户迁移模式^[3]或帮助社交网站更准确地推荐潜在的朋友等. ...

... 有监督方法通过从用户的属性中提取特征，并使用监督分类器模型来预测用户对是否对.Goga et al^[9]基于属性的距离相似性特征训练逻辑斯蒂回归分类器，对候选对进行二分类.Liu et al^[10]使用基于词袋和距离的特征，将用户对齐问题作为多目标优化问题进行求解.Zhang et al^[1]采用基于词袋的特征和基本关系特征，并结合局部和全局一致性提出基于能量的模型.最近，许多基于嵌入的方法也被提出来^[11,12,13].然而，监督的方法都需要昂贵的带标签的训练数据，应用场景因此受限． ...

... Flickr⁃Lastfm：根据部分已知的对齐用户，从中抽取两个子网络，这两个子网络分别拥有12974个和15436个用户.将用户的性别作为一个用户属性，根据用户节点的pagerank得分对用户节点进行排序^[1].将前1%的用户节点标记为“意见领袖”，接下来10%的用户节点标记为“中产阶级”，其余节点标记为“普通用户”.使用用户名相似度(编辑距离)来表示

H

. ...

Community?based network alignment for large attributed network

2017

Performing local network alignment by ensembling global aligners

2017

... 数据集Flickr⁃Lastfm和Flickr⁃Myspace的参数为

m = 0.3, t_{m a x} = 30, α = 0.7, β = 0.3

；数据集Douban Online⁃Douban Offline的参数为

m = 0.82, t_{m a x} = 30, α = 0.9, β = 0.1

.从表3可以看出，SPUAL优于其他方法.首先，SPUAL的准确率远高于IsoRank^[3]，NetAlign^[4]，UniAlign^[5]和Klau's Algorithm^[19]，这是因为仅仅单独利用用户的拓扑结构或者属性不能很好地对用户进行对齐.而Regal的准确率低则是因为Regal在进行用户嵌入的时候，是将两个网络放在一起进行嵌入的，当两个网络的结构差距过大时这种方法的局限性很大，并且在降低时间复杂度时是用一种近似的方法来求解用户的相似性矩阵，导致最终的结果有很大误差.同时，在新的软对齐一致性原则下，进行软对齐的SPUAL的效果要优于FINAL，这也验证了SPUAL的合理性和正确性. ...

Gpm：a graph pattern matching kernel with diffusion for chemical compound classification

2008

... 无监督学习的优势是可以从无标记的数据中根据特定的原则学习数据的模式，因此非常适合大规模无标记数据场景下的用户对齐.目前，大部分无监督方法都集中于基于社交网络的拓扑结构来推断用户对齐关系.例如，IsoRank^[4]在社交网络中传播成对的拓扑结构相似性.NetAlign^[5]利用基于网络拓扑结构的最大乘积信念进行传播.BigAlign和UniAlign^[6]的方法是基于一个网络的邻接矩阵是另一个网络的噪声排列的假设来推断软对齐.这些方法背后的一个基本假设是拓扑一致性，也就是说，同一个用户在不同的社交网络中的社交关系具有一致性(例如，连接到相同或相似的邻居集).然而，这种假设在某些社交网络中并不适用.例如，一个用户可能在一个社交网站(如Facebook)上非常活跃，但在另一个网站(如LinkedIn)上却表现得很安静^[6].在这些情况下，基于拓扑结构的方法可能会产生错误的对齐结果.此外,这些方法无法利用用户的属性信息，所以也损失了用户的信息.FINAL^[7,8]提出用户对齐一致性原则，通过判断用户对是否满足对齐一致性原则来对判断用户对的对齐的一致性.虽然FINAL的思想很不错，但它要求用户对必须满足所有的对齐一致性原则才能保证他们的对齐性一致，这是严格的对齐过程. ...

... IsoRank^[4]是一种经典的无监督用户对齐方法，它是受到PageRank^[14]的启发.IsoRankN^[15]扩展了原有的IsoRank算法，并使用类似PageRank⁃Nibble^[16]的方法对多个网络进行对齐.Bayati et al^[17]提出一种利用最大乘积信念传播进行网络对齐的最大权值匹配算法.NetAlign^[5]将用户对齐问题转化为一个整形二次规划问题，可以最大限度地增加网络的平方数.Zhang and Yu^[18]分两步解决了多个匿名网络用户对齐问题，即无监督用户对齐推理和传递多网络匹配.这些方法都假设同一个用户在不同的社交网络的社交关系具有一致性，但这个假设在某些社交网络中并不适用，并且无法利用用户的属性信息. ...

... 为了证明SPUAL的有效性，将SPUAL与六种设计良好或最先进的方法进行比较，包括Regal^[20]，FINAL^[7]，IsoRank^[4]，NetAlign^[5]，UniAlign^[6]，Klau's Algorithm^[21]. ...

... 数据集Flickr⁃Lastfm和Flickr⁃Myspace的参数为

m = 0.3, t_{m a x} = 30, α = 0.7, β = 0.3

；数据集Douban Online⁃Douban Offline的参数为

m = 0.82, t_{m a x} = 30, α = 0.9, β = 0.1

sparse network alignment problems

2009

... 数据集Flickr⁃Lastfm和Flickr⁃Myspace的参数为

m = 0.3, t_{m a x} = 30, α = 0.7, β = 0.3

；数据集Douban Online⁃Douban Offline的参数为

m = 0.82, t_{m a x} = 30, α = 0.9, β = 0.1

Big?Align：Fast bipartite graph alignment

2013

... [6].在这些情况下，基于拓扑结构的方法可能会产生错误的对齐结果.此外,这些方法无法利用用户的属性信息，所以也损失了用户的信息.FINAL^[7,8]提出用户对齐一致性原则，通过判断用户对是否满足对齐一致性原则来对判断用户对的对齐的一致性.虽然FINAL的思想很不错，但它要求用户对必须满足所有的对齐一致性原则才能保证他们的对齐性一致，这是严格的对齐过程. ...

... FINAL^[6]的核心是对齐一致性原则，主要思想是如果两对用户节点本身满足对齐一致性原则，那么这两个输入网络的两对节点之间的对齐应该是一致的.如图1所示：图1中的两对节点是

a

和

x

以及

b

和

y

，如果这两对节点对满足对齐一致性原则，那么两对节点的对齐性应该是一致的.其中，对齐一致性原则包括： ...

Final：Fast attributed network alignment

2016

... FINAL^[7]提出用户对齐一致性原则，通过判断用户对是否满足所有的对齐一致性原则来判断用户对的对齐一致性.然而现在很多用户注重隐私保护，很多对齐的用户对不一定满足所有的用户对齐一致性原则.其次，FINAL把每个对齐一致性原则都等同对待，这在某些社交网络中并不适用，因为不同的社交网络注重性不同.有的社交网络注重用户的个人信息，这个时候属性一致性就比拓扑一致性重要得多；而有的社交网络注重社交关系，比如Twitter、微博，此时拓扑一致性就显得格外重要.针对这个问题，本文提出一种无监督用户对齐方法SPUAL，基于用户的属性与结构建立新的用户软对齐一致性原则来推断用户是否对齐. ...

... 先简单描述FINAL^[7]，在此基础上提出一种新的无监督用户对齐方法SPUAL. ...

iNEAT：Incomplete network alignment

2017

Large?scale correlation of accounts across social networks

2013

HYDRA：Large?scale social identity linkage via heterogeneous behavior modeling

2014

Structure based user identification across social networks

2017

Aligning users across social networks using network embedding

2016

Mego2vec：embedding matched ego networks for user alignment across social networks

2018

The PageRank citation ranking：bringing order to the web

1999

IsoRankN：Spectral methods for global alignment of multiple protein networks

2009

Local graph partitioning using pageRank vectors

2006

Maximum weight matching via max?product belief propagation

2005

Multiple anonymized social networks alignment

2015

ComSoc：adaptive transfer of user behaviors over composite social network

2012

... Douban Online⁃Douban Offline：为豆瓣数据集构建一个对齐场景^[19]，根据用户在社交聚会中的共现情况构建Offline网络，共有1118个用户.从包含所有离线用户的Online网络中提取一个包含3906个用户节点的子网络.将用户的位置作为节点属性，根据用户之间的度相似度来计算

H

. ...

... 数据集Flickr⁃Lastfm和Flickr⁃Myspace的参数为

m = 0.3, t_{m a x} = 30, α = 0.7, β = 0.3

；数据集Douban Online⁃Douban Offline的参数为

m = 0.82, t_{m a x} = 30, α = 0.9, β = 0.1

Regal：representation learning?based graph alignment

2018

A new graph?based method for pairwise global network alignment

2009

Network similarity decomposition (NSD)：a fast and scalable approach to network alignment

2012

... 和FINAL一样，本文采用启发式贪婪匹配算法^[22,23]求出两个输入社交网络之间的用户一对一的对齐，并根据已知的对齐计算对齐准确率.实验结果如表3所示. ...

Pedestrian alignment network for large?scale person re?identification

2018

Pedestrian alignment network for large?scale person re?identification

2018

〈

〉