On Kamada-Kawai graph layout with graph neural networks

Olena Linnyk, Lyudmyla Polyakova, Iryna Zaretska

Abstract


Traditional force-directed layout algorithms, such as the Kamada-Kawai (KK) method, are widely used for graph visualization due to their ability to produce aesthetically pleasing layouts. However, these algorithms can be computationally intensive for large graphs. The subject matter of the study is graph layout. The aim of this research is to explore the application of graph neural networks (GNNs) to improve the KK algorithm for graph layouts, resulting in a novel hybrid approach named KKNN. The key tasks addressed in this study include: 1. Development of the KKNN layout algorithm by integrating GNN-based reparameterization from the NeuLay-2 approach with the KK algorithm. 2. Evaluation of computational efficiency by comparing the computational performance of KKNN with both the original KK algorithm and the NeuLay-2. 3. Assessment of layout quality, particularly by examining the symmetry preservation, energy minimization, and aesthetic criteria such as minimal edge crossings and balanced node placement. 4. Testing on various graph types, including both random and highly structured (symmetric) graphs. The methods used are: GNN-based layout reparameterization, inspired by NeuLay-2; Kamada-Kawai graph layout algorithm; performance metrics, including time-to-convergence, energy minimization, and symmetry preservation. Our experiments demonstrate the following results: 1. KKNN converges to the energy minimum faster and achieves a lower energy state compared to the original KK. 2. KKNN not only reduces computational time but also better preserves graph symmetries compared to NeuLay-2. Conclusions. This study underscores the potential of integrating neural networks with traditional graph layout algorithms, presenting a promising approach for efficient and high-quality graph visualization. KKNN not only enhances computational performance but also ensures visually interpretable layouts. This hybrid approach offers a pathway for future research in graph visualization, where combining deep learning techniques with classical algorithms may open new possibilities for handling complex, large-scale graphs in a visually coherent and computationally efficient manner.

Keywords


network analysis; graph; layout; force-directed layout; neural networks

Full Text:

PDF

References


Jumper, J., Evans, R., Pritzel, A., Green, P., Figurnov, D., Ronneberger, O., Tunyasuvunakool, K., Bates, R., Žídek, A., Potapenko, A., Bridgland, A., Meyer, C., Kohl, S., Ballard, A., Cowie, A., Romera-Paredes, B., Nikolov, S., Jain, R., Adler, J., Back, B., Petersen, S., Reiman, D., Clancy, E., Zielinski, M., Steinegger, M., Pacholska, M., Berghammer, T., Bodenstein, S., Silver, D., Vinyals, O., Senior, A.W., Kavukcuoglu, K., Kohli, P., & Hassabis, D. Highly accurate protein structure prediction with AlphaFold. Nature, 2021, vol. 596, pp. 583–589. DOI: 10.1038/s41586-021-03819-2.

Zhou, D., Li, S., Dong, L., Chen, R., Peng, X., & Yao, H. C-KGE: Curriculum learning-based Knowledge Graph Embedding. Computer Speech & Language, 2025, vol. 89, article no. 101689. DOI: 10.1016/j.csl.2024.101689.

Liu, Q., Kim, Y., & Hemsley, J. Climate Change Skeptics and the Power of Negativity. Proceedings of the Association for Information Science and Technology, 2024, vol. 61, iss 1, pp. 999-1001. DOI: 10.1002/ pra2.1166.

Chumachenko, D., Meniailov, I., Bazilevych, K., Chumachenko, T., & Yakovlev, S. Investigation of Statistical Machine Learning Models for COVID-19 Epidemic Process Simulation: Random Forest, K-Nearest Neighbors, Gradient Boosting. Computation, 2022, vol. 10, no. 6, article no. 86. DOI: 10.3390/ computation10060086.

Mohammadi, A., Meniailov, I., Bazilevych, K., Yakovlev, S., & Chumachenko, D. Comparative study of linear regression and SIR models of COVID-19 propagation in Ukraine before vaccination. Radioelectronic and computer systems, 2021, no. 3, pp. 5–18. DOI: 10.32620/reks.2021.3.01.

Drach, K., Glushakov, S., & Kotenko, I. Understanding the spread of COVID-19 in the United States using topology and machine learning for time series. Proceedings of the Pharmaceutical Users Software Exchange 2020 (Phuse US Connect, November 8-11, 2020, virtual). Available at lexjansen.com/ phuse/2020/rw/PAP_RW03.pdf (accessed 31 August 2024).

Di Bartolomeo, S., Crnovrsanin, T., Saffo, D., Puerta, E., Wilson, C., & Dunne, C. Evaluating Graph Layout Algorithms: A Systematic Review of Methods and Best Practices. Computer Graphics forum, 2024, vol. 43, iss. 6, article no. e15073. DOI: 10.1111/cgf. 15073.

Tutte, T. W. How to draw a graph. Proc. London Math. Soc., 1963, vol. 3, iss. 1, pp. 743-768. DOI: 10.1112/ PLMS/S3-13.1.743.

Drawing G.: Graph drawing website, 2024. Available at: http://www.graphdrawing.org/ (accessed 31.08.2024).

Gibson, H., Faith, J., & Vickers, P. A survey of two-dimensional graph layout techniques for information visualization. Information Visualization, 2013, vol. 12, pp. 324-357. DOI: 10.1177/ 1473871612455749.

Pinki, P., & Shekhawat, K. An annotated review on graph drawing and its applications. AKCE Int. Journal of Graphs and Combinatorics, 2023, vol. 20, iss. 3, pp. 258-281. DOI: 10.1080/09728600.2023. 2218459.

Freivalds, K., Dogrusoz, U., & Kikusts, P. Disconnected graph layout and the polyomino packing approach. Proc. Symp. Graph Drawing GD’01 in Lecture Notes in Computer Science, 2002, vol. 2265, pp. 378-391. Available at: https://link.springer.com/chapter/ 10.1007/3-540-45848-4_30 (accessed 31.08.2024)

Kamada, T., & Kawai, S. An algorithm for drawing general undirected graphs. Information Processing Letters, 1989, vol. 31, iss. 1, pp. 7-15. DOI: 10.1016/0020-0190(89)90102-6.

Fruchterman, T. J. & Reingold, E. M. Graph drawing by force-directed placement. Software: Practice and Experience, 1991, vol. 21, iss. 11, pp. 1129-1164. DOI: 10.1002/spe.4380211102.

Barnes, J. & Hut, P. A hierarchical O(NlogN) force-calculation algorithm. Nature, 1986, vol. 324, iss. 6096, pp. 446-449. DOI: 10.1038/324446A0.

Press, W. H., Teukolsky, S. A., & Flannery, B. P. Numerical Recipes in C. Second ed. Cambridge, USA, Cambridge University Press, 1992. 996 p.

Gansner, E. R., Koren, Y., & North, S. Graph Drawing by Stress Majorization. In: J. Pach, ed. Graph Drawing. Berlin, Heidelberg: Springer, 2005. pp. 239-250. DOI: 10.1007/978-3-540-31843-9_25.

Gaisbauer, F., Pournaki, A., Banisch, S., & Olbrich, E. Grounding force-directed network layouts with latent space models. Journal of Computational Social Science, 2023, vol. 6, iss 2, pp. 707-739. DOI: 10.1007/s42001-023-00207-w.

Bastian, M., Heymann, S., & Jacomy, M. Gephi: An Open Source Software for Exploring and Manipulating Networks. International AAAI Conference on Weblogs and Social Media, 2009, vol. 3, iss. 1, pp. 361-362. DOI: 10.1609/icwsm.v3i1.13937

Csardi, G., & Nepusz, T. The igraph software package for complex network research. InterJournal, Complex Systems, 2006, vol. 1695, iss. 5., pp. 1-9. Available at https://igraph.org/ (accessed 01.06.2024)

Ellson, J., Gansner, E., Koutsofios, L., North, S., & Woodhull, G. Graphviz – Open Source Graph Drawing Tools. In: P. Mutzel, M. Junger & S. Leipert, eds. Graph Drawing, Springer Berlin Heidelberg, 2002, pp. 483--484. Available at: https://graphviz.org/ (accessed 31.08.2024).

Hagberg, A., Swart, P., & Chult, D. Exploring network structure, dynamics, and function using NetworkX, Los Alamos National Lab. (LANL), Los Alamos, NM (United States), 2008. Available at: https://networkx.org/ (accessed 31.08.2024).

Shannon, P., & et al. Cytoscape: a software environment for integrated models of biomolecular interaction networks. Genome research, 2003, vol. 13, iss. 11, pp. 2498-2504. Available at: https:// cytoscape.org/ (accessed 31.08.2024).

Khosla, M., Setty, V., & Anand, A. A Comparative Study for Unsupervised Network Representation Learning, 2020, Available at https://arxiv.org/abs/1903.07902 (accessed 31.08.2024).

Tang, J., Liu, J., Zhang, M., & Mei, Q. Visualizing Large-scale and High-dimensional Data, 2016. Available at https://arxiv.org/abs/1602.00370 (accessed 31.08.2024). DOI: 10.1145/2872427. 2883041.

Zhu, Z., Xu, S., Qu, M., & Tang, J. GraphVite: A High-Performance CPU-GPU Hybrid System for Node Embedding. In: The World Wide Web Conference, 2019, pp. 2494-2504. DOI: 10.1145/3308558.3313508.

Shen, L., Tai, Z., Shen, E., & Wang, J. Graph Exploration with Embedding-Guided Layouts, 2023. Available at: https://arxiv.org/abs/2208.13699 (accessed 31.08.2024).

Cimikowski, A., & Shope, P. A neural network algorithm for a graph layout problem. IEEE Trans Neural Netw., 1996, vol. 7, iss. 2, pp. 341-345. DOI: 10.1109/ 72.485670.

Wang, X., Yen, K., Hu, Y., & Shen, H.-W. DeepGD: A Deep Learning Framework for Graph Drawing Using GNN, 2021. Available at https://arxiv.org/abs/2106.15347 (accessed 01.06.2024).

Tiezzi, M., Ciravegna, G., & Gori, M. Graph Neural Networks for Graph Drawing. IEEE Transactions on Neural Networks and Learning Systems, 2024, vol. 35, iss. 4, pp. 4668–4681. DOI: 10.1109/tnnls.2022. 3184967.

Zhang, S., Xu, R., Zhang, Q., Quan, Y., & Liu, Q. DeepFD: a deep learning approach to fast generate force-directed layout for large graphs. Journal of Visualization, 2024, vol. 27, pp. 925–940. DOI: 10.1007/s12650-024-00991-1.

Both, C., Dehmamy, N., Yu, R., & Barabási, A.-L. Accelerating network layouts using graph neural networks. Nature Communications, 2023, vol. 14, article no. 1560. DOI: 10.1038/s41467-023-37189-2.

Both, C. NeuLay, 2023. Available at: https://github.com/csabath95/NeuLay (accessed 01.06.2024).

Barabási, A.-L., & Albert, R. Emergence of Scaling in Random Networks. Science, 1999, vol. 286, iss. 5439, pp. 509-512. DOI: 10.1126/science. 286.5439.509.

Watts, D. J., & Strogatz, S. H. Collective dynamics of ‘small-world’ networks. Nature, 1998, vol. 393, pp. 440-442. DOI: 10.1038/30918.

Penrose, M. Random Geometric Graphs. Oxford, Oxford University Press, 2003. 344 p.

Elmokashfi, A. M., Kvalbein, A., & Dovrolis, C. On the Scalability of BGP: The Role of Topology Growth. IEEE Journal on Selected Areas in Communications, 2010, vol. 28, pp. 1250-1261. DOI: 10.1109/JSAC.2010.101003.

Linnyk, O. KamadaNN, 2024. Available at: https://github.com/OlenaLinnyk/KamadaNN (accessed 31 August 2024).

Thompson, A. P., Aktulga, H. M., Berger, R., Bolintineanu, D. S., Brown, W. M., Crozier, P. S., Veld, P. J., Kohlmeyer, A., Moore, S. G., Nguyen, T. D., Shan, R., Stevens, M. J., Tranchida, J., Trott, C., & Plimpton, S. J. LAMMPS - a flexible simulation tool for particle-based materials modeling at the atomic, meso, and continuum scales. Comp Phys Comm, 2022, vol. 271, article no. 10817. DOI: 10.1016/j.cpc.2021.108171.




DOI: https://doi.org/10.32620/reks.2025.3.07

Refbacks

  • There are currently no refbacks.