Graph Layouts by t-SNE
论文:Graph Layouts by t-SNE
作者:J. F. Kruiger, P. E. Rauber, R. M. Martins, A. Kerren, S. Kobourov, A. C. Telea
发表会议:Eurographics Conference on Visualization (EuroVis) 2017
介绍
图布局是信息可视化中一个重要的任务。然而,随着数据量的增加,传统的图布局方法生成一个“好”的图布局结构越来越困难。降维方法可以将一个高维向量映射为低维空间中的向量,这和图布局的目标是类似的。尽管基于降维的图布局似乎很简单,但是这方面却少有相关的工作。这片文章基于对t-SNE降维方法提出了一个新的图布局方法,tsNET(*)。tsNET(*)将原始的图的拓扑结构表达为一个距离矩阵,并且通过对t-SNE目标函数的少许修改,达到更好的图布局结果。
背景
t-SNE是目前最有效的可视化高维数据的降维算法之一。t-SNE首先定义了输入空间和布局空间中选取一个点对的概率。其中输入空间一个点对的概率是基于它们之间欧式距离的高斯分布计算得到:
布局空间中选取一个点对的概率是基于他们之间欧式距离的t分布计算得到:
数据点在二维平面的坐标就可以通过最小化输入空间和布局空间中点对概率的Kullback-Leibler散度求得。
方法
给定一个图,tsNET算法首先计算了节点之间最短路径长度,将其类比为t-SNE中高维向量之间的距离。然后,tsNET采用了t-SNE的目标函数,并且增加了额外的两个惩罚项:
其中,第一项是原始的t-SNE的目标函数,第二项是压缩项,可以用来加速求解过程的收敛,第三项是为了防止数据点之间过于靠近,从而得到一个更理想的布局结果。如下图所示,简单地基于t-SNE并不能得到一个非常好的结果,这是由于t-SNE的目标函数是非凸的,优化过程很容易陷入到局部最优。因此,作者又提出了tsNET*,将Pivot MDS的布局结果作为迭代初值,然后由上述目标函数继续优化,这样能够生成可读性更强的图布局结果。
实验评估
Normalized stress metric. Normalized stress metric 是用来描述所有点对之间在图上距离和实际布局距离的误差。如下图所示,tsNET(*)取得了相对还可以的结果,虽然其他有些方法的stress更低,但是在后面可视化结果中我们可以看到,更低的stress并不意味着可读性更高的布局结果。