Predict Anchor Links across Social Networks via an Embedding Approach

Summary

这篇文章的思想很好理解，通过将源网络和目标网络嵌入到低维向量空间中，最后根据已观测到的 anchor link 监督信息，预测 hidden anchor link。

有一个问题是 “Cross Network Extension” 是否合理？？感觉他们的方法效果好的主要原因就是采取了两个 Cross Network Extension，嵌入的方法上使用 MLP 好像还可以进一步改进。

Research Objective

如果没有关于社交用户的用户资料和 content 信息，如何利用网络结构解决 anchor link prediction 问题。

提出一种基于交叉网络嵌入的方法，将观察到的 Anchor Link 作为监督信息，进行Anchor Link预测。

Problem Statement

仅利用网络结构的方法包括：

• unsupervised：将该问题看做 network alignment 问题，通过寻找网络中节点之间的结构相似性来解决。

• supervised：社交网络的结构特征，例如：度、聚类系数、共同邻居等

  受网络结构的影响比较大，微小的网络结构扰动会产生比较大的影响

充分利用 社交网络的结构规律 和 与所观察到的锚链接相关的信息 的方法

Anchor link prediction

Given two networks $G^{s} = {V^{s}, E^{s}}$ and $G^{t} = {V^{t}, E^{t}}$ and a set of observed anchor links $T={(v,u)|v \in V^{s}, u \in V{t}}$

Aim: identify hidden anchor links across $G^{s}$ and $G^{t}$

将源和目标网络嵌入到低维向量空间中，学习一个映射函数$Z^{s} \rightarrow Z^{t}$

最优化目标：

$$\min _{Z^{s}, Z^{t}, \phi}\left\{L_{e}\left(G^{s}, Z^{s}, G^{t}, Z^{t}, T\right)+L_{m}\left(\phi, Z^{s}, Z^{t}, T\right)\right\}$$

where $L{e}\left(G^{s}, Z^{s}, G^{t}, Z^{t}, T\right)$ 是源网络和目标网络embedding到低维向量空间的loss，$L{m}\left(\phi, Z^{s}, Z^{t}, T\right)$ 是 matching loss

---

Methods

Predicting Anchor Links via Embedding

1. Anchor-Link-aware Network Embedding

Cross Network Extension

利用观察到的anchor link扩展源网络和目标网络。源网络中没有的边，但是它们的counterpart在目标网络中存在边，将边加入到网络中去，对源网络进行扩充。目标网络的扩充也是如此。

Network Embedding

取log-likelihood并且进行负采样，得到目标函数：

$$\log \sigma\left(z_{i}^{T} \cdot z_{j}\right)+\sum_{k=1}^{K} E_{v_{k} \propto P_{n}(v)}\left[\log \left(1-\sigma\left(z_{i}^{T} \cdot z_{k}\right)\right)\right]$$

2. Supervised Latent Space Matching

在观测到的 anchor links $\left(v{l}^{s}, u{n}^{t}\right) \in T$ 为监督信息的条件下，学习一个映射函数，将网络嵌入到潜在的空间内。

loss：

$$L_{m}\left(\phi, Z^{s}, Z^{t}, T\right)=\sum_{\left(v_{l}^{s}, u_{n}^{t}\right) \in T}\left\|\phi\left(z_{l}^{s} ; \Theta\right)-z_{n}^{t}\right\|_{F} \\ \phi\left(z_{l}^{s} ; \Theta\right)=\Theta \times z_{l}^{s}, \quad v_{l}^{s} \in V^{s}$$

3. Anchor Link Prediction

为了预测源，对于源网络中任意给定节点 v 及其表示 z，可以根据映射函数将其映射到目标的潜在空间中。然后，通过识别与之对应的节点 u 最近的节点来预测 hidden anchor links.

$$\min _{n}\left\|\phi\left(z_{l}^{s} ; \Theta\right)-z_{n}^{t}\right\|_{F}$$

4. Experiments

Dataset

http://socialnetworks.mpi-sws.org/data-wosn2009.html

微软学术圈会议的数据，按领域划分为数据挖掘和人工智能两个网络圈集合，进行这两个网络圈的用户对齐

http://research.microsoft.com/en-us/projects/mag/