图可视化布局方法最新研究进展综述

doi:10.3778/j.issn.1002-8331.2212-0068

摘要/Abstract

摘要： 图可视化是图数据的直观表示，随着图数据的广泛应用，合适的图可视化能够使用户对图数据的理解更加深入和高效。但随着图数据量级的增长，图可视化布局面临着计算时间长，难以发现图的重要结构和关系，以及节点遮挡和复杂的边交叉所产生的视觉杂乱等挑战。因此，如何快速对大规模图数据进行布局，如何强化对图中重要的结构和关系的探索，以及如何生成美观的图可视化布局成为亟需解决的问题。近年来，许多基于力学模型和美学评价标准的优化方法被提出来解决上述问题。另外，图挖掘、图嵌入、图神经网络等机器学习方法从图数据特点的角度，为解决图可视化的布局问题提供了新思路，相比之下，机器学习方法在布局效率和效果上表现出一定的优越性。主要从力导向算法、基于美学约束的布局方法、图挖掘技术和机器学习方法这四方面对图可视化布局的最新研究进展进行了阐述，最后对图可视化布局方法的未来发展进行了展望。

关键词: 图可视化布局, 节点-链接图, 力导向算法, 图挖掘算法, 美学评价标准, 机器学习

Abstract: Graph visualization is an intuitive representation of graph data. With the wide application of graph processing, a decent graph visualization can lead to profound and efficient understanding of graph data. However, as the growth of graph data volume, the layout of graph visualization encounters the challenges of long computation time, difficulties in discovering important structures and relations in graph, and visual clutter caused by node overlapping and complex edge crossing. Therefore, how to lay out large-scale graph data fast, how to enhance the exploration of the important structures and relations in graph, and how to generate the aesthetic layout of graph data become urgent problems to be solved. In recent decades, various optimization methods based on stress models and aesthetic criteria are proposed to address these problems. In addition, machine learning methods such as graph mining, graph embedding and graph neural network provide novel alternative solutions from the perspective of graph data features for the layout of graph visualization. In comparison, machine learning methods exceed in the efficiency and performance of the layout of graph data. This paper briefly summaries the latest research on the layout of graph visualization from four perspectives, which are force-directed algorithm, aesthetic constraint based methods, graph mining algorithm and machine learning methods. Last but not least, the future development of layout methods for graph visualization is discussed.

Key words: layout of graph visualization, node-link graph, force-directed algorithm, graph mining algorithm, aesthetic criteria, machine learning

杨卓, 谢雅淇, 陈谊, 战荫伟. 图可视化布局方法最新研究进展综述[J]. 计算机工程与应用, 2023, 59(16): 1-15.

YANG Zhuo, XIE Yaqi, CHEN Yi, ZHAN Yinwei. Review of Latest Research for Layout Methods of Graph Visualization[J]. Computer Engineering and Applications, 2023, 59(16): 1-15.

参考文献

[1] SAKR S，BONIFATI A，VOIGT H，et al.The future is big graphs：a community view on graph processing systems[J].Communications of the ACM，2021，64（9）：62-71.
[2] MAHADEVI S，KAMATH S S，SHETTY D P.Study of novel COVID-19 data using graph energy centrality：a soft computing approach[J].International Journal of Medical Engineering and Informatics，2022，14（3）：282-294.
[3] ZHANG T，LI J.Understanding and predicting the spatio‐temporal spread of COVID‐19 via integrating diffusive graph embedding and compartmental models[J].Transactions in GIS，2021，25（6）：3025-3047.
[4] 马昱欣，曹震东，陈为.可视化驱动的交互式数据挖掘方法综述[J].计算机辅助设计与图形学学报，2016，28（1）：1-8.
MA Y，CAO Z D，CHEN W.A survey of visualization-driven interactive data mining approaches[J].Journal of Computer-Aided Design & Computer Graphics，2016，28（1）：1-8.
[5] 陈谊，张梦录，万玉钗.图的表示与可视化方法综述[J].系统仿真学报，2020，32（7）：1232-1243.
CHEN Y，ZHANG M L，WAN Y C.A survey on graph representation and visualization techniques[J].Journal of System Simulation，2020，32（7）：1232-1243.
[6] VON LANDESBERGER T，KUIJPER A，SCHRECK T，et al.Visual analysis of large graphs：state‐of‐the‐art and future research challenges[J].Computer Graphics Forum，2011，30（6）：1719-1749.
[7] 孙扬，蒋远翔，赵翔，等.网络可视化研究综述[J].计算机科学，2010，37（2）：12-18.
SUN Y，JIANG Y X，ZHAO X，et al.Survey on the research of network visualization[J].Computer Science，2010，37（2）：12-18.
[8] POHL M，SCHMITT M，DIEHL S.Comparing the readability of graph layouts using eyetracking and task-oriented analysis[C]//Proceedings of the International Symposium on Computational Aesthetics in Graphics，Visualization，and Imaging，Victoria，2009：49-56.
[9] TUTTE W T.How to draw a graph[J].Proceedings of the London Mathematical Society，1963，3（1）：743-767.
[10] EADES P.A heuristic for graph drawing[J].Congressus Numerantium，1984，42：149-160.
[11] KAMADA T，KAWAI S.An algorithm for drawing general undirected graphs[J].Information Processing Letters，1989，31（1）：7-15.
[12] FRUCHTERMAN T M J，REINGOLD E M.Graph drawing by force‐directed placement[J].Software：Practice and Experience，1991，21（11）：1129-1164.
[13] DAVIDSON R，HAREL D.Drawing graphs nicely using simulated annealing[J].ACM Transactions on Graphics，1996，15（4）：301-331.
[14] NOACK A.An energy model for visual graph clustering[C]//Proceedings of the 11th International Symposium on Graph Drawing，Perugia，2003：425-436.
[15] JACOMY M，VENTURINI T，HEYMANN S，et al.Force-
Atlas2，a continuous graph layout algorithm for handy network visualization designed for the Gephi software[J].PLoS ONE，2014，9（6）：e98679.
[16] HADANY R，HAREL D.A multi-scale algorithm for drawing graphs nicely[J].Discrete Applied Mathematics，2001，113（1）：3-21.
[17] WALSHAW C.A multilevel algorithm for force-directed graph drawing[C]//Proceedings of the 8th International Symposium on Graph Drawing，Heidelberg，2000：171-182.
[18] HACHUL S，JüNGER M.Large-graph layout algorithms at work：an experimental study[J].Journal of Graph Algorithms and Applications，2007，11（21）：345-369.
[19] XUE M，WANG Z，ZHONG F，et al.Taurus：towards a unified force representation and universal solver for graph layout[J].IEEE Transactions on Visualization and Computer Graphics，2023，29（1）：886-895.
[20] RAHMAN M，SUJON M H，AZAD A.Scalable force-directed graph representation learning and visualization[J].Knowledge and Information Systems，2022，64（1）：207-233.
[21] LIPP F，WOLFF A，ZINK J.Faster force-directed graph drawing with the well-separated pair decomposition[C]//Proceedings of the 23rd International Symposium on Graph Drawing and Network Visualization，Los Angeles，2015：52-59.
[22] 张野，王松，吴亚东.FMR：基于FR的快速多层次算法[J].图学学报，2019，40（1）：78-86.
ZHANG Y，WANG S，WU Y D.FMR：a fast multilevel algorithm based on FR[J].Journal of Graphics，2019，40（1）：78-86.
[23] HU Y.Efficient，high-quality force-directed graph drawing[J].Mathematica Journal，2005，10（1）：37-71.
[24] 汤颖，盛风帆，秦绪佳.基于改进力导引图布局的层级视觉抽象方法[J].计算机辅助设计与图形学学报，2017，29（4）：641-650.
TANG Y，SHENG F F，QIN X J.A hierarchical visual abstraction method based on the improved force-directed graph layout[J].Journal of Computer-Aided Design & Computer Graphics，2017，29（4）：641-650.
[25] ARLEO A，DIDIMO W，LIOTTA G，et al.A distributed multilevel force-directed algorithm[J].IEEE Transactions on Parallel and Distributed Systems，2019，30（4）：754-765.
[26] MARTIN S，BROWN W M，KLAVANS R，et al.OpenOrd：an open-source toolbox for large graph layout[C]//Visualization and Data Analysis 2011，San Francisco，2011，7868：45-55.
[27] RAHMAN M K，SUJON M H，AZAD A.BatchLayout：a batch-parallel force-directed graph layout algorithm in shared memory[C]//2020 IEEE Pacific Visualization Symposium，Tianjin，2020：16-25.
[28] BRINKMANN G G，RIETVELD K F D，TAKES F W.Exploiting GPUs for fast force-directed visualization of large-scale networks[C]//Proceedings of the 46th International Conference on Parallel Processing，Bristol，2017：382-391.
[29] HAN D，PAN J，ZHAO X，et al.NetV.js：a web-based library for high-efficiency visualization of large-scale graphs and networks[J].Visual Informatics，2021，5（1）：61-66.
[30] BOSTOCK M，OGIEVETSKY V，HEER J.D3 data-driven documents[J].IEEE Transactions on Visualization and Computer Graphics，2011，17（12）：2301-2309.
[31] FRANZ M，LOPES C T，HUCK G，et al.Cytoscape.js：a graph theory library for visualisation and analysis[J].Bioinformatics，2016，32（2）：309-311.
[32] COENE J P.sigmajs：an R htmlwidget interface to the sigma.js visualization library[J].Journal of Open Source Software，2018，3（28）：814.
[33] REN D，LEE B，H?LLERER T.Stardust：accessible and transparent GPU support for information visualization rendering[J].Computer Graphics Forum，2017，36（3）：179-188.
[34] ZELLMANN S，WEIER M，WALD I.Accelerating force-directed graph drawing with RT cores[C]//Proceedings of the 2020 IEEE Visualization Conference，2020：96-100.
[35] LI R，SONG S，WU Q，et al.Accelerating force-directed graph layout with processing-in-memory architecture[C]//Proceedings of the 2020 IEEE 27th International Conference on High Performance Computing，Data，and Analytics，Pune，2020：271-282.
[36] HOLTEN D，VAN WIJK J J.A user study on visualizing directed edges in graphs[C]//Proceedings of the 2019 SIGCHI Conference on Human Factors in Computing Systems，Boston，2009：2299-2308.
[37] HUANG W.Establishing aesthetics based on human graph reading behavior：two eye tracking studies[J].Personal & Ubiquitous Computing，2013，17（1）：93-105.
[38] PURCHASE H C.Metrics for graph drawing aesthetics[J].Journal of Visual Languages & Computing，2002，13（5）：501-516.
[39] AHMED R，DE LUCA F，DEVKOTA S，et al.Graph drawing via gradient descent，GD2[C]//Proceedings of the 28th International Symposium on Graph Drawing and Network Visualization，Vancouver，2020：3-17.
[40] AHMED R，DE LUCA F，DEVKOTA S，et al.Multicriteria scalable graph drawing via stochastic gradient descent，SGD2[J].IEEE Transactions on Visualization and Computer Graphics，2022，28（6）：2388-2399.
[41] SARKAR M，BROWN M H.Graphical fisheye views of graphs[C]//Proceedings of the 1992 SIGCHI Conference on Human Factors in Computing Systems，Monterey，1992：83-91.
[42] MUNZNER T.Exploring large graphs in 3D hyperbolic space[J].IEEE Computer Graphics and Applications，1998，18（4）：18-23.
[43] DU F，CAO N，LIN Y R，et al.isphere：focus+context sphere visualization for interactive large graph exploration[C]//Proceedings of the 2017 SIGCHI Conference on Human Factors in Computing Systems，Denver，2017：2916-2927.
[44] WANG Y，WANG Y，ZHANG H，et al.Structure-aware fisheye views for efficient large graph exploration[J].IEEE Transactions on Visualization and Computer Graphics，2018，25（1）：566-575.
[45] BIEDL T C，MADDEN B P，TOLLIS I G.The three-phase method：a unified approach to orthogonal graph drawing[J].International Journal of Computational Geometry & Applications，2000，10（6）：553-580.
[46] VAN GOETHEM A，VERBEEK K.Optimal morphs of planar orthogonal drawings[C]//Proceedings of the 34th International Symposium on Computational Geometry，Budapest，2018.
[47] VAN GOETHEM A，SPECKMANN B，VERBEEK K.Optimal morphs of planar orthogonal drawings II[C]//Proceedings of the 27th International Symposium on Graph Drawing and Network Visualization，Prague，2019：33-45.
[48] ZINK J，WALTER J，BAUMEISTER J，et al.Layered drawing of undirected graphs with generalized port constraints[J].Computational Geometry，2022，105：101886.
[49] BARTH L，NIEDERMANN B，RUTTER I，et al.A topology-shape-metrics framework for ortho-radial graph drawing[J].arXiv：2106.05734，2021.
[50] HOFFSWELL J，BORNING A，HEER J.SetCoLa：high‐level constraints for graph layout[J].Computer Graphics Forum，2018，37（3）：537-548.
[51] YU J，HU Y，YUAN X.UNICON：a uniform constraint based graph layout framework[C]//Proceedings of the 2022 IEEE 15th Pacific Visualization Symposium，Tsukuba，2022：61-70.
[52] PAN J，CHEN W，ZHAO X，et al.Exemplar-based layout fine-tuning for node-link diagrams[J].IEEE Transactions on Visualization and Computer Graphics，2020，27（2）：1655-1665.
[53] HU P，LAU W C.A survey and taxonomy of graph sampling[J].arXiv：1308.5865，2013.
[54] NGUYEN Q H，HONG S H，EADES P，et al.Proxy graph：visual quality metrics of big graph sampling[J].IEEE Transactions on Visualization and Computer Graphics，2017，23（6）：1600-1611.
[55] MEIDIANA A，HONG S H，TORKEL M，et al.Sublinear time force computation for big complex network visualization[J].Computer Graphics Forum，2020，39（3）：579-591.
[56] ZHAO Y，JIANG H，QIN Y，et al.Preserving minority structures in graph sampling[J].IEEE Transactions on Visualization and Computer Graphics，2020，27（2）：1698-1708.
[57] ZHOU Z，SHI C，SHEN X，et al.Context-aware sampling of large networks via graph representation learning[J].IEEE Transactions on Visualization and Computer Graphics，2020，27（2）：1709-1719.
[58] BLONDEL V D，GUILLAUME J L，LAMBIOTTE R，et al.Fast unfolding of communities in large networks[J].Journal of Statistical Mechanics：Theory and Experiment，2008（10）：P10008.
[59] XU X，YURUK N，FENG Z，et al.Scan：a structural clustering algorithm for networks[C]//Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining，San Jose，2007：824-833.
[60] CHEN X，CAI D.Large scale spectral clustering with landmark-based representation[C]//Proceedings of the 25th AAAI Conference on Artificial Intelligence，San Francisco，2011：313-318.
[61] IMRE M，TAO J，WANG Y，et al.Spectrum-preserving sparsification for visualization of big graphs[J].Computers & Graphics，2020，87：89-102.
[62] HONG S H，EADES P，TORKEL M，et al.Multi-level graph drawing using infomap clustering[C]//Proceedings of the 27th International Symposium on Graph Drawing and Network Visualization，Prague，2019：139-146.
[63] HONG S H，EADES P，TORKEL M，et al.Louvain-based multi-level graph drawing[C]//2020 IEEE Pacific Visualization Symposium，Tianjin，2021：151-155.
[64] HUANG Z，WU J，ZHU W，et al.Visualizing complex networks by leveraging community structures[J].Physica A：Statistical Mechanics and Its Applications，2021，565：125506.
[65] MEIDIANA A，HONG S H，EADES P，et al.A quality metric for visualization of clusters in graphs[C]//Proceedings of the 27th International Symposium on Graph Drawing and Network Visualization，Prague，2019：125-138.
[66] DOS SANTOS VIEIRA R，DO NASCIMENTO H A D，DA SILVA W B.The application of machine learning to problems in graph drawing a literature review[C]//Proceedings of the 7th International Conference on Information，Process，and Knowledge Management，Lisbon，2015：112-118.
[67] GOYAL P，FERRARA E.Graph embedding techniques，applications，and performance：a survey[J].Knowledge-Based Systems，2018，151：78-94.
[68] VAN DER MAATEN L，HINTON G.Visualizing data using t-SNE[J].Journal of Machine Learning Research，2008，9（11）：2579-2605.
[69] TANG J，QU M，WANG M，et al.LINE：large-scale information network embedding[C]//Proceedings of the 24th International Conference on World Wide Web，Florence，2015：1067-1077.
[70] PEROZZI B，AL-RFOU R，SKIENA S.DeepWalk：online learning of social representations[C]//Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining，New York，2014：701-710.
[71] WANG D，CUI P，ZHU W.Structural deep network embedding[C]//Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining，San Francisco，2016：1225-1234.
[72] CHEN Y，ZHANG Q，GUAN Z，et al.GEMvis：a visual analysis method for the comparison and refinement of graph embedding models[J].The Visual Computer，2022，38（9）：3449-3462.
[73] HAREL D，KOREN Y.Graph drawing by high-dimensional embedding[C]//Proceedings of the 10th International Symposium on Graph Drawing，Irvine，2002：207-219.
[74] BRANDES U，PICH C.Eigensolver methods for progressive multidimensional scaling of large data[C]//Proceedings of the 14th International Symposium on Graph Drawing，Karlsruhe，2006：42-53.
[75] YANG Z，PELTONEN J，KASKI S.Optimization equivalence of divergences improves neighbor embedding[C]//Proceedings of the 31st International Conference on Machine Learning，2014：460-468.
[76] KRUIGER J F，RAUBER P E，MARTINS R M，et al.Graph layouts by t‐SNE[J].Computer Graphics Forum，2017，36（3）：283-294.
[77] ZHU M，CHEN W，HU Y，et al.DRgraph：an efficient graph layout algorithm for large-scale graphs by dimensionality reduction[J].IEEE Transactions on Visualization and Computer Graphics，2020，27（2）：1666-1676.
[78] MISHRA A，KIRMANI S，MMDDURI K.Fast spectral graph layout on multicore platforms[C]//Proceedings of the 49th International Conference on Parallel Processing，Edmonton，2020：1-11.
[79] HEITER E，KANG B，DE BIE T，et al.Evaluating representation learning and graph layout methods for visualization[J].IEEE Computer Graphics and Applications，2022，42（3）：19-28.
[80] WANG Y，JIN Z，WANG Q，et al.DeepDrawing：a deep learning approach to graph drawing[J].IEEE Transactions on Visualization and Computer Graphics，2019，26（1）：676-686.
[81] KIPF T N，WELLING M.Semi-supervised classification with graph convolutional networks[J].arXiv：1609.02907，2016.
[82] KWON O H，MA K L.A deep generative model for graph layout[J].IEEE Transactions on Visualization and Computer Graphics，2019，26（1）：665-675.
[83] GIOVANNANGELI L，LALANNE F，AUBER D，et al.Deep neural network for drawing networks，（DNN）2[C]//Proceedings of the 29th International Symposium on Graph Drawing and Network Visualization，Tübingen，2021：375-390.
[84] WANG X，YEN K，HU Y，et al.DeepGD：a deep learning framework for graph drawing using GNN[J].IEEE Computer Graphics and Applications，2021，41（5）：32-44.
[85] WANG X，YEN K，HU Y，et al.SmartGD：a self-challenging generative adversarial network for graph drawing[J].arXiv：2206.06434，2022.
[86] TIEZZI M，CIRAVEGNA G，GORI M.Graph neural networks for graph drawing[J].IEEE Transactions on Neural Networks and Learning Systems，2022.DOI：10.1109/TNNLS.2022.3184967.