论文阅读《A comparative study on network alignment techniques》

2019-10-07

字数统计: 3.2k字 | 阅读时长≈ 15分

A comparative study on network alignment techniques

Summary

从矩阵对齐和网络表示学习的角度总结了state-of-the-art的7种方法，并建立了一个统一的基准平台。同时他们还研究了不同网络因素对于这些方法的影响。

这篇文章对于7种方法的介绍非常详细（数学真得好难），可以参考。

但是数据集对于该问题是主要的影响因素，但是公开数据集特别少。

Research Objective

比较现有网络对齐的方法

评估公共框架下的 Network Alignment 技术

本研究的主要目的是提供一个灵活而强大的工具，以支持比较和促进网络对齐技术的基准分析。

Problem Statement

文章中将目前的 Network Align 方法分为 spectral methods（基于邻接矩阵的操作）和 network representation methods (节点用嵌入向量表示，能够捕捉到网络的结构信息)

虽然Network Alignment方法的研究已经很长时间了，但由于缺少公共数据集和共同的评价指标，还没有比较过这些方法的性能。

Network alignment methods

网络对齐技术利用结构一致性和属性一致性假设来构建它们的模型。

结构一致性：同质性原则，即邻近的节点倾向于在不同的网络中维持它们之间的关系

属性一致性：属于同一身份的在不同网络上的节点可能保持相同的属性(特征)

Spectral methods — matrix factorization 矩阵分解
使用矩阵分解，直接计算对齐矩阵 S

将输入的图用连接矩阵的形式表示，Spectral methods 以损失函数的形式定义模型，模型考虑了源和目标网络的邻接矩阵；节点特征为常量，对齐矩阵S为变量。在对准过程中，根据结构和/或属性一致性假设，通过优化损失函数来学习得到对准矩阵。

Spectral methods 不同之处在于构建模型时使用什么一致性原则以及该原则如何使用的
- IsoRank：如果来自不同网络的两个节点的邻居是相似的，那么这两个节点是相似的。因此该方法中，节点的相似性取决于两个节点邻居的相似性。
  
  similarity：
  $\mathbf{S}\left(u_{s}, v_{t}\right)=\sum_{w_{s} \in N\left(u_{s}\right)} \sum_{w_{t} \in N\left(v_{t}\right)} \frac{1}{\left|N\left(u_{s}\right)\right|\left|N\left(v_{t}\right)\right|} \mathbf{S}\left(w_{s}, w_{t}\right) \\ u_{s}源网络的节点，v_t目标网络的节点，N(u)节点u的邻居集合 \\ 上面的公式可以写成：S=CS \\ where \\ \mathbf{C}[i, j][u, v]=\left\{\begin{array}{ll}{\frac{1}{|N(u)||N(v)|},} & {\text { if }(i, u) \in E_{s},(i, v) \in E_{t}} \\ {0,} & {\text { otherwise }}\end{array}\right. \\ 通过迭代的方法更新S\\ \mathbf{S}^{k+1} \leftarrow \frac{\mathbf{C S}^{k}}{\left|\mathbf{C S}^{k}\right|} \\ 其中S^{k}是第k次迭代的对齐矩阵$
  该方法对于网络的结构较敏感
- BigAlign
  
  利用网络节点的原始特征和手工提取的特征，如节点度、权重、集群系数等，将源网络和目标网络转换成二分图，从而解决网络对齐问题。
  
  求置换矩阵 P，使损失函数最小化:
  $\mathbb{L}(\mathbf{P})=\left\|\mathbf{P D}_{s} \mathbf{P}^{T}-\mathbf{D}_{t}\right\|_{F}^{2}$
  P 用于对 $D{s}$ 的行进行重新排序，$P^{t}$ 用于对 $D{t}$ 的列进行重新排序。难解。
  
  将图转化成二分图然后最小化损失函数：
  $\begin{aligned} \mathbb{L}(\mathbf{P}, \mathbf{Q}) &=\left\|\mathbf{P D}_{s} \mathbf{Q}-\mathbf{D}_{t}\right\|_{F}^{2}+\lambda \sum_{i, j} \mathbf{P}(i, j)+\phi \sum_{i, j} \mathbf{Q}(i, j) \\ &=\operatorname{Tr}\left(\mathbf{P D}_{s} \mathbf{Q}\left(\mathbf{P D}_{s} \mathbf{Q}\right)^{T}-2 \mathbf{P D}_{s} \mathbf{Q} \mathbf{D}_{t}^{T}\right)+\lambda \mathbf{1}^{T} \mathbf{P} \mathbf{1}+\phi \mathbf{1}^{T} \mathbf{Q} \mathbf{1} \end{aligned} \\ 其中 Tr(·) 是矩阵的迹, \lambda \sum_{i, j} \mathbf{P}(i, j) 是矩阵的稀疏性约束 \\$
  上面的损失函数可以通过 alternating projected gradient descent (APGD) 来优化：
  $\begin{array}{l}{\mathbf{P}_{k+1}=\mathbf{P}_{k}-\eta_{P} \cdot\left(2\left(\mathbf{P}_{k} \mathbf{D}_{s} \mathbf{Q}_{k}-\mathbf{D}_{t}\right) \mathbf{Q}_{k}^{T} \mathbf{D}_{s}^{T}+\lambda \mathbf{1} \mathbf{I}^{T}\right)} \\ {\left.\mathbf{Q}_{k+1}=\mathbf{Q}_{k}-\eta_{Q} \cdot\left(2 \mathbf{D}_{s}^{T} \mathbf{P}_{k+1}^{T} \mathbf{D}_{s} \mathbf{Q}_{k}-\mathbf{D}_{t}\right)+\phi \mathbf{1} \mathbf{1}^{T}\right)}\end{array} \\ P_k 是第k次迭代的矩阵P，\eta_{P},\eta_{Q}为APGD算法的步长$
  仅用属性信息而忽略了拓扑信息。
- FINAL
  
  通过定义结构相似性、节点特征相似性和边特征的相似性条件
  $\begin{aligned} \mathbb{L}(\mathbf{S}) &=\sum_{u_{s}, v_{s}, u_{t}, v_{t}}\left[\frac{\mathbf{S}\left(u_{s}, u_{t}\right)}{\sqrt{f\left(u_{s}, u_{t}\right)}}-\frac{\mathbf{S}\left(v_{s}, v_{t}\right)}{\sqrt{f\left(v_{s}, v_{t}\right)}}\right] \\ & \times \mathbf{D}_{s}\left(u_{s}, v_{s}\right) \mathbf{D}_{t}\left(u_{t}, v_{t}\right) \end{aligned} \\ \begin{array}{l}{\times \mathbb{1}\left(A\left(u_{s}\right)=A\left(u_{t}\right)\right) \mathbb{1}\left(A\left(v_{s}\right)=A\left(v_{t}\right)\right)} \\ {\times \mathbb{1}\left(A_{e}\left(u_{s}, v_{s}\right)=A_{e}\left(u_{t}, v_{t}\right)\right)}\end{array} \\ 其中A_e是边属性矩阵，\mathbb{1}(\cdot)是一个指示函数，如果括号中的条件正确，则返回1，\sqrt{f\left(u, u\right)} 是一个归一化因子$
  
  数学好难，没看懂。。。
- REGAL
  
  两个节点之间的相似性：
  $\mathbf{S}^{\prime}(u, v)=\exp \left(-\lambda_{s} \cdot\left\|\mathbf{d}_{u}-\mathbf{d}_{v}\right\|^{2}-\lambda_{a} \cdot \operatorname{dist}(\mathbf{A}(u), \mathbf{A}(v))\right)$
Representation learning methods
embedding generation 嵌入的生成

alignment matrix generation 对齐矩阵的生成

对于基于嵌入的网络对齐方法，不同之处在于embedding function 和 mapping function
- PALE
  
  https://tiantianliu2018.github.io/2019/09/28/%E8%AE%BA%E6%96%87%E9%98%85%E8%AF%BB%E3%80%8APredict-Anchor-Links-across-Social-Networks-via-an-Embedding-Approach%E3%80%8B/
  
  我之前的阅读笔记。
  
  首先对网络进行扩展：如果在source网络中 $u_s$ 和 $v_s$存在边，并且知道这两个在target网络中对应的节点 $u_t$ 和 $v_t$, 那么 $u_t$ 和 $v_t$ 之间也应该有边，因此通过这样的方式扩展网络
  
  Emdedding function
  $\theta(v_i) = E[i]$
  其中 $E$ 是 embedding matrix，它是通过最小化如下损失得到的：
  $\mathbb{L}(\mathbf{E})=\log \sigma\left(\mathbf{u}^{T} \cdot \mathbf{v}\right)+\sum_{k=1}^{K} \mathbb{E}_{w \alpha P_{n}(v)}\left[\log \left(1-\sigma\left(\mathbf{u}^{T} \cdot \mathbf{w}\right)\right)\right]$
  其中 $(u,v) \in E$ 是观测到的边，$w$ 是通过在E中负采样的节点
  
  Mapping function
  $\phi\left(\mathbf{u}_{s}\right)=\mathbf{M} \times \mathbf{u}_{s}$
  $M$ 是一个$d×d$ 的矩阵，通过最小化下面的损失函数得到：
  $\mathbb{L}(\mathbf{M})=\sum_{\mathbf{H}\left(v_{s}, v_{t}\right)=1}\left\|\phi\left(\mathbf{v}_{\mathbf{s}}\right)-\mathbf{v}_{t}\right\|$
  $H$ 是先验对齐矩阵
- DeepLink
  
  embedding graph 与PALE是一样的，但在mapping function中考虑了mapping的方向
  
  Emdedding function
  $\theta(v_i) = E[i]$
  参数 $E$ 的 loss function:
  $\mathbb{L}_{\theta}(\mathbf{E})=\log \sigma(\mathbf{u} \cdot \mathbf{v})+\sum_{k=1}^{K} \mathbb{E}_{w \propto P_{n}(v)}[\log (1-\sigma(\mathbf{u} \cdot \mathbf{w}))]$
  DeepLink方法认为如果 $v$ 是 $u$随机游走过程中的节点，则认为这两个节点相似。
  
  Mapping function
  
  从源网络 $G_s$ 到目标网络 $G_t$ 的 mapping function
  $\phi_{s, t}\left(\mathbf{u}_{s}\right)=\mathbf{M}_{s, t} \times \mathbf{u}_{s}+\mathbf{b}_{s, t}$
  类似的从目标网络 $G_t$ 到源网络 $G_s$ 的 mapping function
  $\phi_{t, s}\left(\mathbf{u}_{t}\right)=\mathbf{M}_{t, s} \times \mathbf{v}_{t}+\mathbf{b}_{t, s}$
  参数 $\phi{s, t}$ 通过最优化如下loss function得到（$\phi{t, s}$ 类似）：
  $\mathbb{L}\left(\mathbf{W}_{s, t}, \mathbf{b}_{s, t}\right) =\sum_{\left(v_{s}, v_{t}\right) \in H} \min \left(1-\cos \left(\phi\left(\mathbf{v}_{s}\right), \mathbf{v}_{t}\right)\right)$
  对于两个网络中的同一个用户，他们的嵌入向量应该是相似的，因此，通过最小化损失函数来改进 $\phi{s, t}$ 和 $\phi{t, s}$:
  $\mathbb{L}\left(\mathbf{W}_{s, t}, \mathbf{b}_{s, t}, \mathbf{W}_{t, s}, \mathbf{b}_{t, s}\right)=\operatorname{dist}\left(\phi_{t, s}\left(\phi_{s, t}(\mathbf{u})\right), \mathbf{u}\right)$
  对于监督学习，最大化 reward function
  $r_{s, t}^{u}=\frac{1}{k} \sum_{w \in T_{k}(u)} \log (\cos (\mathbf{w}, \mathbf{v})+1) \\ 其中 T_k(u) 是G_t中与\phi_{s,t}(u) embedding最接近的top-k个节点 \\ \phi_{t,s}的reward \, function 为：\\ r_{t, s}^{v}=\frac{1}{k} \sum_{w \in T_{k}(v)} \log (\cos (\mathbf{w}, \mathbf{u})+1)$
  
  https://tiantianliu2018.github.io/2019/09/15/%E8%AE%BA%E6%96%87%E9%98%85%E8%AF%BB%E3%80%8ADeepLink-A-Deep-Learning-Approach-for-User-Identity-Linkage%E3%80%8B/
  之前的论文阅读笔记
  又一大堆数学公式推导，好像没有看下去。
- IONE
  
  IONE 与 PALE 的 mapping function 是相同的，但是其 embedding function 更加复杂，它在计算节点的嵌入时考虑了节点的邻居特征。
  
  Embedding function
  
  一个 embedding 矩阵，其中的每一行是由三个向量拼接到一起的：节点向量、输入上下文向量、输出上下文向量，最终其 embedding function 为：
  
  该方法的思想是：一个节点的节点向量可以影响其邻居的输入上下文向量，而其邻居的节点向量可以影响其输出上下文向量。
  
  为了学习 $E$, 该方法需要满足两个目标：
  1. 每个图中相邻的节点应该具有类似的节点嵌入
    
    为了实现该目标，可以通过考虑一个节点向量相对于其邻居的输入上下文向量的贡献概率来实现：
    $p_{1}(u | v)=\frac{\exp \left(\mathbf{u}^{\prime T} \cdot \mathbf{v}\right)}{\sum_{w \in G} \exp \left(\mathbf{w}^{\prime T} \cdot \mathbf{v}\right)}$
    其经验定义为：
    $\hat{p}_{1}(u, v)=\frac{w_{u, v}}{|\{v |(u, v) \in E\}|}\\ 其中w_{u,v}是边(u,v)的权重$
    类似的，一个节点向量对其邻居的输出上下文向量的贡献的概率及其经验定义：
    $\begin{aligned} p_{2}(v | u) &=\frac{\exp \left(\mathbf{v}^{\prime \prime T} \cdot \mathbf{u}\right)}{\sum_{w \in G} \exp \left(\mathbf{w}^{\prime \prime} T \cdot \mathbf{u}\right)} \\ \hat{p}_{2}(u, v) &=\frac{w_{u, v}}{|\{v |(v, u) \in E\}|} \end{aligned}$
    $p_1$ 应该和 $p_2$ 是相似的，于是有如下目标函数：
    $\begin{aligned} \mathbb{L}_{1}(\mathbf{E})=&-\sum_{G \in\left\{G_{s}, G_{t}\right\}} \sum_{(u, v) \in G} w_{u, v} \log p_{1}(v | u) \\ &-\sum_{G \in\left\{G_{s}, G_{t}\right\}} \sum_{(u, v) \in G} w_{u, v} \log p_{2}(u | v) \end{aligned}$
  2. 具有近似嵌入的节点是很好的对齐节点的候选节点
    
    在两个网络中，两个节点如果是同一个用户，那么这两个节点是可以相互代替的，其代替的程度应该是由这两个节点是同一个用户的可信度确定的，基于这一点，对目标函数L1进行修改，将相应节点的信息考虑如下：
    $\begin{aligned} \mathbb{L}_{2}(\mathbf{E})=&-\sum_{w_{t} \in G_{t}} \sum_{\left(u_{s}, v_{s}\right) \in V_{s}} w_{u_{s}, v_{s}} p_{a}\left(u_{s} | w_{t}\right) \log p_{1}\left(v_{s} | w_{t}\right) \\ &-\sum_{w_{t} \in G_{t}} \sum_{\left(u_{s}, v_{s}\right) \in V_{s}} w_{u_{s}, v_{s}} p_{a}\left(v_{s} | w_{t}\right) \log p_{1}\left(u_{s} | w_{t}\right) \\ &-\sum_{w_{s} \in G_{s}} \sum_{\left(u_{t}, v_{t}\right) \in V_{t}} w_{u_{t}, v_{t}} p_{a}\left(u_{t} | w_{s}\right) \log p_{1}\left(v_{t} | w_{s}\right) \\ &-\sum_{w_{s} \in G_{s}} \sum_{\left(u_{t}, v_{t}\right) \in V_{t}} w_{u_{t}, v_{t}} p_{a}\left(v_{t} | w_{s}\right) \log p_{1}\left(u_{t} | w_{s}\right) \end{aligned}$
    最终通过最小化联合目标函数，得到嵌入的参数
    $\mathbb{L}(\mathbf{E}) = \mathbb{L}_{1}(\mathbf{E}) + \mathbb{L}_{2}(\mathbf{E})$
  Mapping function
  
  IONE的映射函数是PALE的映射函数的一个特例，映射矩阵M是单位矩阵
```
           [https://tiantianliu2018.github.io/2019/09/30/%E8%AE%BA%E6%96%87%E9%98%85%E8%AF%BB%E3%80%8AAligning-Users-Across-Social-Networks-Using-Network-Embedding%E3%80%8B/](https://tiantianliu2018.github.io/2019/09/30/论文阅读《Aligning-Users-Across-Social-Networks-Using-Network-Embedding》/)

   之前的论文阅读笔记
```

Methods

Benchmark

Datasets

Real-world datasets：这些数据集的质量好像都不太高

S1. Douban online vs Douban offline
S2. Flickr vs Lastfm
S3. Flickr vs MySpace
S4. Twitter vs Facebook
S5. Twitter vs Foursquare

Synthetic datasets

Partial synthetic：用真实网络生成目标网络
Full synthetic：

Evaluation

Metrics

Accuracy

$acc = \frac {\# {correctly \ \ identified \ \ node \ \ pairs}}{\# {groundtruth\ \ node\ \ pairs}}$

Precision@k

$Precision@k = \frac {\# {Times \ \ that \ \ target \ \ node \ \ in \ \ top \ k \ \ similarity \ \ candiates}}{\#{groundtruth \ \ node \ \ pairs}}$

Mean Average Precision (MAP)

$MAP = mean(\frac{1}{ra}) \\ra 是排序后的候选序列中匹配节点的rank$

Evaluation procedure

Structural noise level
Attribute noise level
Graph size
Graph size imbalance
Graph density
Graph connectivity
Number of connected components

Experimental evaluation

评估以上因素对于实验的影响

Conclusion

克服真实网络中的结构和属性不稳定性是网络对齐面临的主要挑战之一

Notes

本文作者： Kelly Liu
本文链接： http://tiantianliu2018.github.io/2019/10/07/论文阅读《A-comparative-study-on-network-alignment-techniques》/
版权声明： 本博客所有文章除特别声明外，均采用 MIT 许可协议。转载请注明出处！