3.Cauchy（柯西）特征映射

对比

LE Embedding为图的节点提供了一种低维表示的办法，其中边权值表示节点对象之间的相似性。通常认为LE Embedding的结果保持了原始数据在低维投影子空间上的局部拓扑，即对于任何相似度较大的节点对，都应该在Embedding Space内距离相近。然而，在本文中，我们将证明LE Embedding 往往不能很好地保存局部拓扑。为了Node Embedding局部拓扑保持特性，可以利用一种新的柯西图嵌入方法，该方法通过分类保留了原始数据在嵌入空间中的相似关系，可以方便地对嵌入数据进行嵌入，并具有更好的性能。在合成和真实基准数据集上的实验结果表明了这种新型嵌入的有效性。

无监督降维在各种机器学习应用中是一个重要程序，从图像分类到全基因组表达建模。许多高维真实世界的数据往往本质上处于低维空间，因此可以降低数据的维数而不会造成信息的重大损失。从数据嵌入的角度来看，我们可以将无监督的方式分为两类，一类是将数据通过线性转换嵌入到一个线性空间，即在高维数据中建立线性模型。然而，真实数据的潜在结构常常是高度非线性的，因此无法通过线性流形空间准确的表达。第二类方法，就是基于不同的目的以非线性的方式嵌入数据。最近提出了一些可行的非线性方法。他们通常从邻域图设置一个二次目标，并求解其主要特征向量:Isomap取与最大特征值相关联的特征向量; LLE和LE嵌入使用与最小特征值相关联的特征向量。 Isomap试图保持输入数据在低维流形上测量的全局成对距离; LLE和拉普拉斯嵌入试图保持数据的局部几何关系。

一般认为拉普拉斯嵌入具有局部拓扑保持性质:一对相互相似性高的图节点嵌入到嵌入空间的附近，而一对相互相似性小的图节点嵌入到嵌入空间的远处。拉普拉斯嵌入的感知局部拓扑保持性质在很多应用中并不适用。更准确地说，我们首先给出局部拓扑保持性质的精确定义，然后说明拉普拉斯嵌入通常给出不保持局部拓扑的嵌入，即在嵌入空间中不嵌入具有较大相互相似性的节点对。在此之后，我们将提出一种新的柯西嵌入方法,它不仅具有像拉普拉斯嵌入那样好的非线性嵌入性质，而且还连续地保留了原始数据中存在的局部拓扑。

简述LE

W作为输入数据，是一个有n个节点的图上的边权值矩阵。我们需要用坐标将图的节点嵌入到一维空间中(x1，···，xn)。如果对向量x的大小没有限制，计算 $\sum_{ij}(x_i-x_j)^2w_{ij}$ 的最小值时， $x_i=0$ 。因此引入初始化
$ $\sum_ix_i^2=1 \tag{看下面，为什么改后不变?}$ $

如果我们把x $_i$ 换成 $x_i+a$ ，a是一个常数，原目标函数是不变的。因此解不唯一。

为了避免不确定性，我们可以调整为
$ $\sum_ix_i=0$ $即$ x_i $的值围绕0左右，在这样的约束下，$ x_i$成了混合符号，有了这两个约束条件

$min\sum_{ij}(x_i-x_j)^2w_{ij}，st.\sum_ix_i^2=1，\sum_ix_i=0$

很容易得到结果（参考LE特征映射笔记）
$ $J(x) = 2\sum_{ij}x_i(D − W)_{ij}x_j = 2X^T(D − W)X$ $通过特征向量计算出最小解$ $(D − W)x = λx$ $

LE失效场景

距离大（相似度小）

拉普拉斯嵌入的二次方函数 $|Y_i-Y_j|^2$ 放大距离，使得 $w_{ij}$ 小的节点对(i, j)被分离得很远

距离小(相似性大)

拉普拉斯嵌入的二次函数不强调小距离对，导致破坏了许多小距离对的在Embedding Space的局部拓展性。

Cauchy Embedding

Cauchy Embedding是一种强调短距离的图嵌入方法，并保证局部上两个节点越相似，它们在嵌入空间中越接近。

如果
$ $(x_i − x_j )^2 ≡ Γ_1(|x_i − x_j|)？？？？？$ $\frac{(x_i − x_j )^2}{(xi − xj )^2 + σ^2}≡ Γ_2(|x_i − x_j|)？？？$ $

此外，函数Γ1(·)和函数Γ2(·)一样是单调的。因此，求最小化的函数为：
$ $min_X\sum_{ij}\frac{(x_i − x_j )^2}{(xi − xj )^2 + σ^2}w_{ij}$ $s.t.，||x||^2 = 1, e^Tx = 0？？？？$ $损失函数简化为：$ $\frac{(x_i − x_j )^2}{(xi − xj )^2+ σ^2}=1-\frac{σ^2}{(xi − xj )^2+ σ^2}$ $

由于 $w_{ij}$ 是固定值，因此，对嵌入的优化计算是：

$max_X\sum_{ij}\frac{w_{ij}}{(x_i − x_j)^2+ σ^2}$ $s.t.，||x||^2 = 1，\sum_ix_i=0$

我们可以看到，在拉普拉斯映射中，由于 $(x_i − x_j )^2$ 的平方项，导致远距离节点对权重占比更大，所以可能更好的表示节点较为分散的图的特征。

而使用柯西映射，由于目标函数需要 $(x_i − x_j )^2$ 的平方项尽可能小，因此近距离节点权重占比更大，所以可能更好的表示节点关联性较强的图的特征。

高维的特征映射

若映射到嵌入空间的向量为n维即
$ $R=(r_1,r_2,r_3,r_4.....r_n)$ $计算的目标函数为$ $J(R)=\sum_{ij}\frac{w_{ij}}{||x_i − x_j||^2+ σ^2}$ $s.t.，RR^T = E，R \left[\begin{matrix}1\\1\\1\\...\\1 \end{matrix}\right]^T= 0$ $