基于深度生成模型的图布局算法(A Deep Generative Model for Graph Layout)

在日常生活中,我们经常用图来表示社交网络等复杂的系统。在图的可视化中,点边图是最直观也是最常用的形式,不同的图布局能够展现同一个图的不同方面,找到一个好的图布局是图可视化中至关重要的任务。对于用户特别是新手来说,经典的图布局算法需要消耗大量的时间,来不断地调整参数以达到理想的图布局。本文[1]提出了一种深度生成模型,基于用经典布局算法获得的图布局数据,训练一个变分编解码器,其中编码器将图布局编码到一个二维的隐空间中,解码器从隐空间中重构出布局,这样的隐空间可以方便用户在二维平面上探索和生成各种布局。

本文使用图卷积神经网络的空间方法来处理图数据,在网络的每一层中,节点不断聚集它的邻居传递过来的信息。本文使用一个变分编解码器的生成式模型来生成图布局,其中编码器将高维数据编码到一个低维的隐空间,解码器将隐空间解码来重构出原始输入。

为了训练深度学习模型,需要大量的训练数据。本文收集了9个图结构,使用经典的4个图布局方法,通过在每个方法的参数空间中随机采样,生成大量的图布局样本。以图布局的节点原始坐标数据作为节点特征输入模型并不合理,由于图布局方法的随机初始化,多次运行时会得到不同的节点布局。所以本文计算了每个节点与其他节点的欧几里得距离作为节点的特征,这个特征在图布局的旋转和反射变换中可以保证一致。

图 1 变分编解码器结构

本文提出的模型结构包括编码器,融合层和解码器。编码器将预处理后的节点特征和图的邻接矩阵作为输入,使用3层的图卷积神经网络对节点特征进行聚集,将每个节点每一层的特征进行连接后求平均值,得到一个图的高维特征表示,最后使用一个多层感知机将高维特征表示转变到一个2维的隐空间中。融合层将一个单位矩阵的每一行连接上编码器输出的图的二维特征表示,这一层给节点特征引入了多样性。解码器将融合后的节点特征和图的邻接矩阵作为输入,使用3层的图卷积神经网络对节点特征进行聚集,将每个节点每一层的特征进行连接后使用一个多层感知机将高维特征表示转变到一个2维的向量,代表节点在二维平面上的坐标。

本文使用了两个损失函数来训练这个模型。第一个是重构损失函数,衡量重构后的图布局和原始输入的差距,在计算这个函数时,本文使用遍历所有可能的置换矩阵的方法,来处理结构等效节点,使得损失函数和视觉观察结果相符合。第二个是变分损失函数,本文使用了Sliced-Wasserstein Autoencoder[2]提出的损失函数。

图 2 用户界面

训练完成后,本文通过将生成的图布局样本映射到二维隐空间中的方法,构建了一个所见即所得的用户界面。用户可以使用鼠标在二维的隐空间中进行探索,模型可以生成出空间结构稳定的图布局,在鼠标移动过程中,图布局的变化是连续的,用户可以方便的看出节点的位置是如何随着隐空间变化而变化的。

本文介绍了一种全新的图可视化方法,通过训练生成模型,从图布局样本中学习如何生成图布局。用户可以通过所见即所得的接口,轻松地生成满足其需要的图布局。

Reference:

[1] Kwon, Oh-Hyun, and Kwan-Liu Ma. (2020). A Deep Generative Model for Graph Layout. IEEE Transactions on Visualization and Computer Graphics.

[2] Kolouri, Soheil, et al. (2018). Sliced-Wasserstein autoencoder: an embarrassingly simple generative model. arXiv preprint arXiv:1804.01947.

发表评论?

0 条评论。

发表评论


注意 - 你可以用以下 HTML tags and attributes:
<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>