基于神经网络的图布局技术综述

闫 凯， 赵铁军

(哈尔滨工业大学 语言技术研究中心， 哈尔滨 150001)

0 引 言

在对图数据进行可视化分析时，首先需要进行图的布局，将顶点数据合理地映射到二维平面的点上。一个良好的布局能够帮助使用者快速且正确地理解可视化背后所隐含的数据本体。传统的绘图学领域中顶点的布局方法通常可以分为基于力引导的方法和基于降维的方法。前者通过模拟物理过程，力图达到受力平衡的状态，这一类方法通常会形成比较美观易读的布局结果；后者则通过将图的顶点表示为高维空间中的数据点，利用降维的方式将其投影到二维平面上，所得到的布局结果往往能比较好地反映全局结构或局部的顶点位置关系。图布局本身是NP-Hard(需要超多项式时间才能求解)的问题，这两类算法都是通过迭代逼近局部最优，模拟退火则是最常用到的优化方式。

近年来随着科技活动的发展，人们所要面临的图数据的大小和数量不断上升，而基于迭代的传统绘图方法虽然能够得到高质量的布局，但所消耗的时间成本过高。当需要处理大量的图数据，比如社交网络分析者想要连续查看几十个用户的朋友圈网络，或者生物信息工作者想要对比数十上百的蛋白质交互过程时，这些算法的性能显得捉襟见肘。而如果可视分析达不到实时性的要求，分析者往往会因为不同图之间展示时的延迟，而难以形成连贯的思考和决策。

自2017年图神经网络研究逐渐成为热点，陆续提出一些通过神经网络学习出端到端图布局模型的算法，或是其他应用机器学习和神经网络手段对图可视化任务进行辅助的策略。机器学习和图布局任务的结合在当前的图布局研究中属于较为前沿的研究话题，调研中发现这一类的方法目前属于零散地出现，尚没有比较完整的综述。本文将对神经网络和图布局问题的结合进行一个系统的梳理，并讨论这一领域的研究前景。

1 图布局问题概述

当前图可视化领域中，图数据最常用呈现方法是“顶点-链接图”，这一表达方式能够将图中的顶点间关系、社群关系、图上不同区域的整体结构特征等直观地表达出来。一组2000年美国橄榄球队比赛图如图1所示，顶点表示球队，边表示球队之间进行过比赛，图1(a)为图的邻接矩阵，行和列均表示顶点，矩阵的某一格非空表示这两个对应的顶点有边关联。这种表示通常用于数据的存储和计算而非可视化表达；图1(b)为可视化的“顶点-链接图”表示。显然，后者能够清晰地告诉数据分析者，该图里有9个社群存在，事实上，这9个社群对应的正是9个不同的橄榄球联合会。

(a) 邻接矩阵表示 (b) 顶点-链接图

当使用“顶点-链接图”呈现时，顶点的坐标位置就是所要关注的重点。一个好的顶点排布能够帮助用户可靠地确定图数据的整体特征。

当前图布局技术研究领域所针对的数据对象主要是无向无权图，即给定无向无权图G=(V,E)，其中V是顶点集合，E⊆V×V是边的集合，算法输出为顶点到二维坐标的映射P:V→2。大部分图布局技术的研究都是针对如何从原始图结构G生成顶点排布P。基于神经网络的端到端布局生成也主要面向这一问题。

另一方面，如何判定一个图布局的质量好坏，历来没有统一的标准。虽然边交叉率、边夹角等易读性准则受到了广泛认可，但这些准则到底多大程度上反映了图布局的质量，一直处于研究者们的探索之中，如何利用神经网络进行图布局P的质量评估，也是值得研究的重点话题。此外，由于图布局的结果通常会经过渲染后生成具体的图像作为可视化呈现，有一部分工作着力于直接通过渲染后的图形来评估布局质量。

2 端到端的布局生成模型

在图神经网络研究领域，顶点的数目或图的数目这两个变量通常有一个是固定的。而在处理图布局问题时，需要面对不同的图数据，且每个图的顶点数都是可变的，这使得直接设计端到端的布局模型并非平凡问题。Kwon等人[1]没有直接进行布局结果的生成，而是将图分解为预设的图元，不同的图元组合得到的布局的整体形态往往是类似的，提出以图元的统计结果作为图的特征，在布局之前，预测出图可能会被布局成什么样子，这种设计方式避开了直接去设计端到端模型，而是让神经网络学习出对布局渲染之后的图像，用户可以根据预测结果估计这种图像是否是自己期望的布局形态，从而选择是否采纳一个可能需要大量迭代的布局算法，虽然没有直接生成布局，但在帮助用户减少布局过程中的试错代价，挑选合适的算法和参数方面做出了贡献。

在基于现代神经网络进行端到端的图布局生成的工作中，Leow等人[2]提出的GraphTSNE可以称得上是较有前瞻性的研究，该方法以t-SNE损失条件(由Maaten和Hinton[3]在2008年提出的一种信息损失度量)作为神经网络的损失函数，试图用图神经网络来学习端到端的布局过程，直接从输入的图数据中拟合出满足t-SNE损失条件的布局结果出来。该工作使用了两层的图卷积神经网络， 使用反向传播算法进行优化。虽然在布局效果上并没有达到很好的质量，从网络架构上来讲也并非一个“深度”的神经网络，但该工作的开创性在于从证明了t-SNE、布局应力准则(stress)这样对布局进行整体描述的损失函数也是可以通过神经网络的方式学习出来，对后来的算法有重要的启发。

在2019年，王勇等人[4]提出了DeepDrawing算法，修改双向LSTM网络的结构，按照图的结构在双向LSTM网络上加入LSTM单元之间的跳跃链接，如图2所示，该方法是第一个实际意义上的以深度学习方式进行端到端布局学习的方法。DeepDrawing以经典算法生成的图布局结果作为训练数据，所训练出的模型能够学习到近似于原算法的布局效果，并且在推理时性能远远超出经典算法。但由于在每次计算时都会对LSTM结构本身进行修改，算法的训练过程失去了现代神经网络的并行性，在算法本身参数量巨大的情况下，训练的性能并不高；另外，DeepDrawing以生成好的布局作为输入，自动生成的训练数据本身质量并不能得到良好的保障。这两点都在一定程度上限制了DeepDrawing的可扩展性。

图2 DeepDrawing的网络架构[4]

Wang等人[5]提出了DeepGD算法，利用图卷积神经网络的堆叠，用经典算法所要优化的布局应力准则结合不同的美学指标作为损失函数，利用多目标学习的技术，直接从图数据中生成满足一定美观度和可读性需求的图布局，效果如图3所示。这种方法不需要利用传统算法进行数据标注，在模型训练上更加自由，且多层卷积神经网络也保障了训练时的并行性，训练性能得以提升。但DeepGD方法为了适应卷积神经网络的结构，需要对原始的图数据进行修改，用全源最短路经进行重新赋权，得到完全图作为输入，这一过程使得模型在应用的时候并不直观，且存在一定扭曲信息的可能。

图3 基于各种美学准则的DeepGD布局效果[5]

Giovannangeli等人[6]提出一种称作(DNN)2的算法，以残差神经网络ResNet50为基础架构，用基于谱方法的图卷积模块代替了ResNet中的卷积层，以tsNet算法的优化目标作为损失函数，同时采用在随机图上进行预训练的技术，得到了一个高质量的神经网络模型，如图4所示。当然，基于ResNet架构的模型存在其固然的缺陷，应用于机器视觉领域的ResNet模型通过大量的池化层来缩小所要处理的数据规模并聚合有效信息，而这一过程在图数据上并没有得到很好的应用，(DNN)2算法中并没有这一步骤。虽然图神经网络本身的聚合性较强，但训练量巨大这一问题无法避免。

(a) 基于ResNet的网络架构

鉴于从前的算法在训练时，损失函数或者为对标注数据的比较，或者为特定的准则函数，Tiezzi等人[7]设计了一个两段式的学习模型，同时训练网络来进行布局的生成和布局质量的验证。这一方法将布局生成和验证结合起来，形成了一个较为统一的模型。

Safarli等人[8]用多智能体强化学习的方式，将传统基于力引导的算法过程中通过合力对顶点进行移动的步骤，视为智能体的强化过程，将图的布局质量作为强化学习的适应性函数。这一研究并没有提出一种学习之后可以直接预测出新的图数据的布局的模型，但其从另一角度对传统算法进行了解释，其工作为新的布局算法的设计提供了基于多智能体的一种新视角。

3 基于神经网络的布局验证

Mchedlildze等人[9]以文献中现有的美学准则、图的统计特征和用凝聚态物理学理论对顶点进行的统计分析结果作为特征向量，构造孪生神经网络，通过向网络中同时输入用经典算法生成的好的布局和故意构造的差的布局，学习出一个判别模型，用来判断一个生成的布局是否是“好”布局，而这个“好”的标准取决于这些美观度的准则与经典的算法之间的吻合度，这种方式给出了传统算法在美学特征上的判别尺度。但传统算法是否完全可以作为“好 ”布局的金标准，是一个值得讨论的问题，完全使用机器智能来判定图的质量，仍有待于研究。

Haleem等人[10]使用卷积神经网络来进行图布局可读性度量的计算。与使用布局本身的美学特征作为输入数据的方法不同，其所选择的是直接使用力引导算法布局并渲染好的顶点-链接图，而所计算的内容则是如顶点传播度、顶点冲突、边交叉、边夹角、边长方差以及组间重叠等可读性度量。利用卷积神经网络对图像数据的识别能力，该工作能够对布局的美学准则进行预测，为用户在不同布局结果图之间进行挑选提供了有效参考信息。但当不同顶点规模的图拥有相近的布局形态时，这种方法可能会由于图像本身的分辨率等问题造成误判，根据该工作所报告的扩展性，该方法能够处理600顶点以下的图数据，对于边相关的准则预测的结果尚不充分。

与此类似，Cai等人[11]通过人类标注的方式，向孪生神经网络中输入有明显人类选择倾向的布局，对渲染出的图像通过网络学习出哪种布局更容易被人类选择。与自动生成的好和坏的布局对相比，这种方式显然更能体现出图的美观性对人类的视觉价值。然而，由于人类的视觉判别存在主观性，这种方式得到的结果，更大程度上是从“美观”而非“可信”视角上进行布局判定。在图的可视化问题上，图的可信度严重影响了使用者对图背后隐含的结构化数据的理解，而人类标注数据时事实上是很难与原始数据进行合理对应的，这就使得判别出来的图的实际可用性受到了限制。

4 结束语

针对图布局日益增长的性能需求和神经网络技术的蓬勃发展，近年来研究者们不断提出基于神经网络的图布局算法和评估模型。本文介绍了近5年中神经网络应用于图布局问题的主要工作及其利弊，供需要借助神经网络手段进行图可视化研究的科研人员和需要进行图数据可视化分析的分析者了解该研究领域的现状，选择自身科技工作任务所适宜的技术手段。

此外，通过对现有文献的调研成果进行分析，总结出将会是这一研究领域中较有前景的主题：

(1)基于图神经网络的有约束布局。有约束布局一直是图布局中较为实用的研究方向，如出版物中常常需要应对翻页问题而对折纸的边界进行约束；电路图等特定布局场景下需要使用正交布局；用户需要对选中的一些区域进行锚定等等。有约束布局往往会有比自由布局有更大的计算量和更常见的使用场景，而这一部分的研究当前仍处于空白状态；

(2)基于神经网络的动态图布局或流式图布局。动态图相比于静态图，除了图的总数量的增长以外，保持相邻时间片之间布局的心智地图的连贯性也是其研究要点，而流式图相比之下更需要能实时反馈图数据更新后的布局结果，这两种数据在科技工作中大量存在，而现有的工作均是服务于静态图的技术；

(3)风格化的预训练模型。即使在传统布局中，用户往往需要通过对布局参数进行调整以得到自己想要的布局效果。现有的技术中虽然已经有了预训练方法的参与，但主要是针对数据的预训练，而如果能使用神经网络捕捉到布局所需要的特征本质，继而针对具体需要的布局风格进行调优，那么布局的灵活性将会有大大的提高。