网络映射

网络映射方法与类别

下面两张图取自GATNE论文，针对不同网络图类型列举出不同的网络映射方法。

1、HON即Node和Edge都是单一类型，比如Node都是账号，Edge都是关注关系

2、AHON即Node和Edge都是单一类型并有Attribute，比如Node都是账号，Edge都是关注关系，且有账号性别年龄地域或加关注关系时间等属性

3、HEN即Node多类型，Edge单类型，比如Node为账号或商品，Edge为购买关系

4、AHEN即Node多类型，Edge单类型，并有Attribute，比如Node为账号或商品，Edge为购买关系，且有账号性别年龄地域或购买时间金额等属性

5、MHEN即Node单类型或多类型，Edge多类型，比如Node为账号，Edge为关注、转发、点赞、评论；Node为账号或文章，Edge为关注、发表、转发、点赞

6、AMHEN即Node多类型，Edge多类型，并有Attribute，Node为账号或文章，Edge为关注、发表、转发、点赞，且有账号性别年龄地域或文章发布时间内容领域等属性

网络映射的目标

1. 网络重构性

即原网络依旧可以从映射的空间中再重构生成。

诚然，我们如果只考虑网络重构性，直接用SVD等矩阵分解就可以得到低维度矩阵来表示网络所有的节点及节点间连接关系。

但是这样丧失了很多隐含信息，比如high order的拓扑结构。（如果两个节点并未直接相连，我们并不能说两者之间没有关系，比如下图5与6虽然不相连，但second order approximation很高）

2. 映射空间支持网络推断

即依旧可以反应网络结构和保持网络特性，依旧可以进行网络分析（Node importance; Community detection; Network distance; Link prediction; Node classification ...）

图映射与网络映射

Graphs exist in mathematics. (Data Structure)

Mathematical structures used to model pairwise relations between objects

Networks exist in the real word. (Data)

Social networks, logistic networks, biology networks, etc...

Network can be represented by graph. Dataset that is not a network can also be represented by a graph

图映射

图映射最初被提出是作用于降维的技术，比如MDS，ISOMAP，LLE等流形学习降维方法。基本思想都是基于 $n$ 个样本的特征先构造出一个 $n\times n$ 的近似矩阵来表示图，然后从这个构造的矩阵中生成低维度的表示方法，如下图所示

多维缩放(MDS)

若要求原始空间中样本的距离在低维空间中得以保持，如上图所示，即得到多维缩放(Multiple Dimensional Scaling, MDS)。假定 $m$ 个样本在原始空间的距离矩阵为 $D\in \mathbb{R}^{m\times m}$ ，其第 $i$ 行 $j$ 列的元素 $dist_{ij}$ 为样本 $x_i$ 到 $x_j$ 的距离。我们的目标是获得样本在 $d'$ 维空间的表示 $Z\in \mathbb{R}^{d'\times m},\ d'\leq d$ ，且任意两个样本在 $d'$ 维空间中欧氏距离等于原始空间中的距离，即 $||z_i-z_j||=dist_{ij}$

令 $B=Z^TZ\in \mathbb{R}^{m\times m}$ ，其中 $B$ 为降维后样本的内积矩阵， $b_{ij}=z_i^Tz_j$ ，有

$dist_{ij}^2=||z_i||^2+||z_j||^2-2z_i^Tz_j=b_{ii}+b_{jj}-2b_{ij}$

令降维后的样本 $Z$ 被中心化，即 $\sum_{i=1}^mz_i=0$ 。显然，矩阵 $B$ 的行与列之和均为零，即 $\sum_{i=1}^mb_{ij}=\sum_{j=1}^mb_{ij}=0$ ，易知

$\sum\limits_{i=1}^mdist_{ij}^2=tr(B)+mb_{jj}$ $\sum\limits_{j=1}^mdist_{ij}^2=tr(B)+mb_{ii}$ $\sum\limits_{i=1}^m\sum\limits_{j=1}^m dist_{ij}^2=2m\ tr(B)$

其中 $tr(\cdot)$ 表示矩阵的迹(trace)， $tr(B)=\sum_{i=1}^m||z_i||^2$ ，令

$dist_{i.}^2=\frac{1}{m}\sum\limits_{j=1}^mdist_{ij}^2$ $dist_{.j}^2=\frac{1}{m}\sum\limits_{i=1}^mdist_{ij}^2$ $dist{..}^2=\frac{1}{m^2}\sum\limits_{i=1}^m\sum\limits_{j=1}^mdist_{ij}^2$

由上面所有式子可得

$b_{ij}=-\frac{1}{2}(dist_{ij}^2-dist_{i.}^2-dist_{.j}^2+dist_{..}^2)$

由此即可通过降维前后保持不变的距离矩阵 $D$ 求取内积矩阵 $B$

对矩阵 $B$ 做特征值分解， $B=V\Lambda V^T$ ，其中 $\Lambda = diag(\lambda_1,\lambda_2,\dots,\lambda_d)$ 为特征值构成的对角矩阵， $\lambda_1\geq \lambda_2\geq \dots \geq \lambda_d$ ， $V$ 为特征向量矩阵。假定其中有 $d^*$ 个非零特征值，它们构成的对角矩阵 $\Lambda_*=diag(\lambda_1,\lambda_2,\dots,\lambda_{d^*})$ ，令 $V_*$ 表示相应的特征向量矩阵，则 $Z$ 可表达为

$Z=\Lambda_*^{1/2}V_*^T\in\mathbb{R}^{d^*\times m}$

在现实应用中为了有效降维，往往仅需降维后的距离与原始空间中的距离尽可能接近，而不必严格相等。此时可取 $d'\ll d$ 个最大特征值构成的对角矩阵 $\widetilde{\Lambda}=diag(\lambda_1,\lambda_2,\dots,\lambda_{d'})$ ，令 $\widetilde{V}$ 表示相应的特征向量矩阵，则 $Z$ 可表达为

$Z=\widetilde{\Lambda}^{1/2}\widetilde{V}^T\in\mathbb{R}^{d^*\times m}$

算法步骤

输入：距离矩阵 $D\in \mathbb{R}^{m\times m}$ ，其元素 $dist_{ij}$ ，为样本 $x_i$ 到 $x_j$ 的距离；低维空间维数 $d'$
过程：
1：根据上面公式计算 $dist_{i.}^2$ ， $dist_{.j}^2$ ， $dist_{..}^2$
2：计算内积矩阵 $B$
3：对矩阵 $B$ 做特征分解
4：取 $\widetilde{\Lambda}$ 为 $d'$ 个最大特征所构成的对角矩阵， $\widetilde{V}$ 为相应的特征向量矩阵
输出：矩阵 $\widetilde{V}^T\widetilde{\Lambda}^{1/2}\in\mathbb{R}^{m\times d'}$ ，每行是一个样本的低维坐标

等度量映射(ISOMAP)

等度量映射(Isometric Mapping, Isomap)的基本出发点，是认为低维流形嵌入到高维空间之后，直接在高维空间中计算直线距离具有误导性，因为高维空间中的直线距离在低维嵌入流形上是不可达的。我们利用流形在局部上与欧氏空间同胚这个性质，对每个点基于欧氏距离找出其近邻点，然后就能建立一个近邻连接图，图中近邻之间存在连接，而非近邻点之间不存在连接，于是，计算两点之间测地线距离的问题，就转变为计算近邻连接图上两点之间的最短路径问题。

在近邻连接图上计算两点间的最短路径，可采用著名Dijkstra算法或Floyd算法，在得到任意两点的距离之后，就可以通过MDS来获得样本点在低维空间中的坐标。