t-sne图布局与图节点关系预测

本次主要分享师弟讲解的两篇文献：
《Graph Layouts byt-SNE》、《TransNet: Translation-Based Network Representation Learning for Social Relation Extraction 》

Part1

图布局（Graph Layouts）

图模型是一种广泛使用的建模工具。图的可视化作为一种直观的图数据分析工具被广泛使用。图数据可视化中最关键的技术是图布局算法^[3]。目前图布局算法主要分为3种：

力导向布局算法
限定图的展现形式
利用数据自身属性信息的布局方法

力导向布局算法是目前最为常用的图布局算法，由Peter Eades老先生提出，此算法的主要思想就是将整个拓扑图看作为一个物理系统，相邻顶点存在引力，不相邻顶点之间存在斥力。其优点是可以清晰地展现出图的社区结构，并且也能很好的展现出顶点之间的关联关系^[3]。

降维（Dimensionality reduction）

从高维数据中有效的找出其特征信息，是信息科学与统计科学领域中的基本问题。首要步骤就是要对高维数据进行有效地降维处理。所谓降维就是指将高维空间中的数据通过线性或者非线性映射投影到低维空间中，找出隐蔽在高维观测数据中有意义的并且能够揭示数据本质的低维结构。通过降维的方式能够减少数据的维数灾难，促进高维数据的分类、压缩和可视化^[5]。

数学本质

假设 X={x_i,i = 1,…N}是D维空间的一个样本集合，Y={y_i,i = 1,…N}是d维空间的一个数据集(d<<D)，称F:X->Y 是一个降维映射，表示y=F(x),称y为x的低维表示。

方法介绍

传统方法是假设数据具有低维的线性分布，代表性方法是主成分分析(PCA)和线性判别分析(LDA)。这两种方法已有完备的理论体系，在应用中也表现出良好的性态。但是由于现实数据的表示维数与本质特征维数之间存在非线性关系，所以就有了著名的流形学习方法，此类方法假设高维数据分布在一个本质上低维的非线性流形上，在保持原始数据
表示空间与低维流形上的不变量特征的基础上进行非线性降维。代表性方法有谱分析的算法、等距特征映射算法(ISOMAP)、局部线性嵌入算法(LLE)等。

算法优缺点

PCA是一种无监督的学习方法，算法简单，但存储空间大、计算复杂度高。
LDA是一种有监督的学习方法，可以用于分类，但是对于样本维数大于样本数的奇异值问题很敏感。
ISOMAP算法具有拓扑不稳定性、计算复杂性大等缺点
LLE算法具有有解析的整体解、计算复杂度小等优点，但是对于噪声敏感。

T-sne

T-sne是目前流形降维中最受欢迎方法之一，在机器学习的可解释性范畴当中，经常用作高维数据可视化的一种手段，用来辅助理解各种分类器模型的有效性与透明性^[6]。

算法本质

sne技术是将高维数据间的欧式距离转化为数据点相似性的条件概率，根据这种点与点之间的概率关系非线性降维。t-sne解决了在降维过程中的拥挤问题，数据在低维空间表示下，同类样本聚集性更好，不同样本具有分离性^[6]。

^[4]

layout & t-sne

在《Graph layout by t-sne》这篇文献中，作者将图布局与降维方式这两种概念联系在一起，如下图所示：

^[1]

联系

作者是通过怎样的方式将两者联系在一起呢？在t-sne的算法基础上提出了适应图布局的算法t-snet算法。tsnet算法首先计算节点之间的最短路径长度^[7]（图论经典问题），然后将其类比为t-sne算法中的高维向量之间的距离，然后，tsnet采用了原先tsne的目标函数，并且额外增加了两个惩罚项。具体过程如下图所示：