IEEE Trans Vis Comput Graph. 2018 Jan;24(1):478-488. doi: 10.1109/TVCG.2017.2743858. Epub 2017 Aug 29.
Using different methods for laying out a graph can lead to very different visual appearances, with which the viewer perceives different information. Selecting a "good" layout method is thus important for visualizing a graph. The selection can be highly subjective and dependent on the given task. A common approach to selecting a good layout is to use aesthetic criteria and visual inspection. However, fully calculating various layouts and their associated aesthetic metrics is computationally expensive. In this paper, we present a machine learning approach to large graph visualization based on computing the topological similarity of graphs using graph kernels. For a given graph, our approach can show what the graph would look like in different layouts and estimate their corresponding aesthetic metrics. An important contribution of our work is the development of a new framework to design graph kernels. Our experimental study shows that our estimation calculation is considerably faster than computing the actual layouts and their aesthetic metrics. Also, our graph kernels outperform the state-of-the-art ones in both time and accuracy. In addition, we conducted a user study to demonstrate that the topological similarity computed with our graph kernel matches perceptual similarity assessed by human users.
使用不同的方法来布局图形可能会导致非常不同的视觉效果，观众会从中感知到不同的信息。因此，选择一种“好”的布局方法对于可视化图形非常重要。这种选择可能具有很强的主观性，并且取决于给定的任务。选择好的布局的一种常见方法是使用美学标准和视觉检查。然而，全面计算各种布局及其相关美学指标在计算上是非常昂贵的。在本文中，我们提出了一种基于使用图核计算图的拓扑相似性的大规模图可视化的机器学习方法。对于给定的图，我们的方法可以显示不同布局下的图形外观，并估计它们相应的美学指标。我们工作的一个重要贡献是开发了一种新的图核设计框架。我们的实验研究表明，我们的估计计算比实际布局及其美学指标的计算快得多。此外，我们的图核在时间和准确性方面都优于最先进的图核。此外，我们进行了一项用户研究，以证明我们的图核计算的拓扑相似性与人类用户评估的感知相似性相匹配。
