Abstract
By leveraging recent progress of stochastic gradient descent methods, several works have shown that graphs could be efficiently laid out through the optimization of a tailored objective function. In the meantime, Deep Learning (DL) techniques achieved great performances in many applications. We demonstrate that it is possible to use DL techniques to learn a graph-to-layout sequence of operations thanks to a graph-related objective function. In this paper, we present a novel graph drawing framework called \({(DNN)^{\textit{2}\,}} \): Deep Neural Network for DrawiNg Networks. Our method uses Graph Convolution Networks to learn a model. Learning is achieved by optimizing a graph topology related loss function that evaluates \({(DNN)^{\textit{2}\,}} \)generated layouts during training. Once trained, the \({(DNN)^{\textit{2}\,}} \)model is able to quickly lay any input graph out. We experiment \({(DNN)^{\textit{2}\,}} \)and statistically compare it to optimization-based and regular graph layout algorithms. The results show that \({(DNN)^{\textit{2}\,}} \)performs well and are encouraging as the Deep Learning approach to Graph Drawing is novel and many leads for future works are identified.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
https://github.com/HanKruiger/tsNET, consulted on February 2021.
- 2.
http://www.graphdrawing.org/data.html, consulted on February 2021.
References
Hong, S.-H., Nishizeki, T., Quan, W. (eds.): GD 2007. LNCS, vol. 4875. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-77537-9
Brandes, U., Pich, C.: Eigensolver methods for progressive multidimensional scaling of large data. In: Kaufmann, M., Wagner, D. (eds.) GD 2006. LNCS, vol. 4372, pp. 42–53. Springer, Heidelberg (2007). https://doi.org/10.1007/978-3-540-70904-6_6
Cohen-Steiner, D., Kong, W., Sohler, C., Valiant, G.: Approximating the spectrum of a graph. In: Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 1263–1271 (2018)
Conover, W.J., Iman, R.L.: On multiple-comparisons procedures. Tech. rep., Technical report, Los Alamos Scientific Laboratory (1979)
Defferrard, M., Bresson, X., Vandergheynst, P.: Convolutional neural networks on graphs with fast localized spectral filtering. arXiv preprint arXiv:1606.09375 (2016)
Deng, J., Dong, W., Socher, R., Li, L.-J., Li, K., Fei-Fei, L.: Imagenet: a large-scale hierarchical image database. In: 2009 IEEE Conference on Computer Vision and Pattern Recognition, pp. 248–255. IEEE (2009)
Espadoto, M., Hirata, N.S.T., Telea, A.C.: Deep learning multidimensional projections. Inf. Vis. 19(3), 247–269 (2020)
Frick, A., Ludwig, A., Mehldau, H.: A fast adaptive layout algorithm for undirected graphs (extended abstract and system demonstration). In: Tamassia, R., Tollis, I.G. (eds.) GD 1994. LNCS, vol. 894, pp. 388–403. Springer, Heidelberg (1995). https://doi.org/10.1007/3-540-58950-3_393
Giovannangeli, L., Bourqui, R., Giot, R., Auber, D.: Toward automatic comparison of visualization techniques: application to graph visualization. Vis. Inform. 4(2), 86–98 (2020)
Grover, A., Leskovec, J.: node2vec: scalable feature learning for networks. In: Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 855–864 (2016)
Haleem, H., Wang, Y., Puri, A., Wadhwa, S., Qu, H.: Evaluating the readability of force directed graph layouts: a deep learning approach. IEEE Comput. Graph. Appl. 39(4), 40–53 (2019)
Hammond, D.K., Vandergheynst, P., Gribonval, R.: Wavelets on graphs via spectral graph theory. Appl. Comput. Harmon. Anal. 30(2), 129–150 (2011)
Hinton, G., Roweis, S.T.: Stochastic neighbor embedding. In: NIPS, vol. 15, pp. 833–840. Citeseer (2002)
He, K., Zhang, X., Ren, S., Sun, J.: Deep residual learning for image recognition. In: The IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp. 770–778 (June 2016)
Kamada, T., Kawai, S., et al.: An algorithm for drawing general undirected graphs. Inf. Process. Lett. 31(1), 7–15 (1989)
Kipf, T.N., Welling, M.: Semi-supervised classification with graph convolutional networks. arXiv preprint arXiv:1609.02907 (2016)
Kruiger, J.F., Rauber, P.E., Martins, R.M., Kerren, A., Kobourov, S., Telea, A.C.: Graph layouts by t-SNE. In: Computer Graphics Forum, vol. 36, pp. 283–294. Wiley Online Library (2017)
Kruskal, W.H., Wallis, W.A.: Use of ranks in one-criterion variance analysis. J. Am. Stat. Assoc. 47(260), 583–621 (1952)
Kwon, O.-H., Crnovrsanin, T., Ma, K.-L.: What would a graph look like in this layout? A machine learning approach to large graph visualization. IEEE Trans. Vis. Comput. Graph. 24(1), 478–488 (2017)
Kwon, O.-H., Ma, K.-L.: A deep generative model for graph layout. IEEE Trans. Vis. Comput. Graph. 26(1), 665–675 (2019)
Leow, Y.Y., Laurent, T., Bresson, X.: GraphTSNE: a visualization technique for graph-structured data. arXiv preprint arXiv:1904.06915 (2019)
Perozzi, B., Al-Rfou, R., Skiena, S.: Deepwalk: online learning of social representations. In: Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 701–710 (2014)
Purchase, H.: Which aesthetic has the greatest effect on human understanding? In: DiBattista, G. (ed.) GD 1997. LNCS, vol. 1353, pp. 248–261. Springer, Heidelberg (1997). https://doi.org/10.1007/3-540-63938-1_67
Purchase, H.C.: Metrics for graph drawing aesthetics. J. Vis. Lang. Comput. 13(5), 501–516 (2002)
Purchase, H.C.: Experimental Human-computer Interaction: A Practical Guide with Visual Examples. Cambridge University Press, Cambridge (2012)
Purchase, H.C., Cohen, R.F., James, M.: Validating graph drawing aesthetics. In: Brandenburg, F.J. (ed.) GD 1995. LNCS, vol. 1027, pp. 435–446. Springer, Heidelberg (1996). https://doi.org/10.1007/BFb0021827
Tang, J., Qu, M., Wang, M., Zhang, M., Yan, J., Mei, Q.: Line: large-scale information network embedding. In: Proceedings of the 24th International Conference on World Wide Web, pp. 1067–1077 (2015)
Van der Maaten, L., Hinton, G.: Visualizing data using t-SNE. J. Mach. Learn. Res. 9(11), 2579–2605 (2008)
Van Dongen, S.M.: Graph clustering by flow simulation. Ph.D. thesis (2000)
Wang, Q., Chen, Z., Wang, Y., Qu, H.: Applying machine learning advances to data visualization: a survey on ML4VIS. arXiv preprint arXiv:2012.00467 (2020)
Wang, Y., Jin, Z., Wang, Q., Cui, W., Ma, T., Qu, H.: DeepDrawing: a deep learning approach to graph drawing. IEEE Trans. Vis. Comput. Graph. 26(1), 676–686 (2019)
Wang, Y., et al.: Ambiguityvis: visualization of ambiguity in graph layouts. IEEE Trans. Vis. Comput. Graph. 22(1), 359–368 (2015)
Ware, C., Purchase, H., Colpoys, L., McGill, M.: Cognitive measurements of graph aesthetics. Inf. Vis. 1(2), 103–110 (2002)
Wu, A., et al.: Survey on artificial intelligence approaches for visualization data. arXiv preprint arXiv:2102.01330 (2021)
Zheng, J.X., Pawar, S., Goodman, D.F.M.: Graph drawing by stochastic gradient descent. IEEE Trans. Vis. Comput. Graph. 25(9), 2738–2748 (2018)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2021 Springer Nature Switzerland AG
About this paper
Cite this paper
Giovannangeli, L., Lalanne, F., Auber, D., Giot, R., Bourqui, R. (2021). Deep Neural Network for DrawiNg Networks, \({(DNN)^{\textit{2}\,}} \). In: Purchase, H.C., Rutter, I. (eds) Graph Drawing and Network Visualization. GD 2021. Lecture Notes in Computer Science(), vol 12868. Springer, Cham. https://doi.org/10.1007/978-3-030-92931-2_27
Download citation
DOI: https://doi.org/10.1007/978-3-030-92931-2_27
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-92930-5
Online ISBN: 978-3-030-92931-2
eBook Packages: Computer ScienceComputer Science (R0)