Aesthetic discrimination of graph layouts.

*(English)*Zbl 1419.05148Summary: This paper addresses the following basic question: given two layouts of the same graph, which one is more aesthetically pleasing? We propose a neural network-based discriminator model trained on a labeled dataset that decides which of two layouts has a higher aesthetic quality. The feature vectors used as inputs to the model are based on known graph drawing quality metrics, classical statistics, information-theoretical quantities, and two-point statistics inspired by methods of condensed matter physics. The large corpus of layout pairs used for training and testing is constructed using force-directed drawing algorithms and the layouts that naturally stem from the process of graph generation. It is further extended using data augmentation techniques. Our model demonstrates a mean prediction accuracy of 97.58%, outperforming discriminators based on stress and on the linear combination of popular quality metrics by a margin of 2 to 3%.

The present paper extends [the authors, Lect. Notes Comput. Sci. 11282, 169–184 (2018; Zbl 07023823)] and is based on a significantly larger dataset.

The present paper extends [the authors, Lect. Notes Comput. Sci. 11282, 169–184 (2018; Zbl 07023823)] and is based on a significantly larger dataset.

##### MSC:

05C62 | Graph representations (geometric and intersection representations, etc.) |

##### Keywords:

network visualization
PDF
BibTeX
XML
Cite

\textit{T. Mchedlidze} et al., J. Graph Algorithms Appl. 23, No. 3, 525--552 (2019; Zbl 1419.05148)

Full Text:
DOI

##### References:

[1] | H. J. C. Barbosa and A. M. S. Barreto. An interactive genetic algorithm with co-evolution of weights for multiobjective problems. In L. Spector, E. D. Goodman, A. Wu, W. B. Langdon, and H.-M. Voigt, editors, Proceedings of the 3rd Annual Conference on Genetic and Evolutionary Computation, GECCO’01, pages 203-210. Morgan Kaufmann Publishers Inc., 2001. |

[2] | D. E. Berlyne. Novelty, complexity, and hedonic value. Perception & Psychophysics, 8(5):279-286, Sep 1970. |

[3] | R. F. Boisvert, R. Pozo, K. Remington, R. F. Barrett, and J. J. Dongarra. Matrix market: a web resource for test matrix collections. In R. F. Boisvert, editor, Quality of Numerical Software: Assessment and enhancement, pages 125-137. Springer, 1997. |

[4] | J. Bromley, I. Guyon, Y. LeCun, E. S¨ackinger, and R. Shah. Signature verification using a ““siamese”’ time delay neural network.Advances in Neural Information Processing Systems, pages 737-744, 1994. |

[5] | C.-C. Carbon, T. Mchedlidze, M. H. Raab, and H. Waechter. The power of shape: How shape of node-link diagrams impacts aesthetic appreciation and triggers interest. i-Perception, 9, 2018. |

[6] | M. Chimani, C. Gutwenger, M. J¨unger, G. W. Klau, K. Klein, and P. Mutzel. The open graph drawing framework (OGDF). In R. Tamassia, editor, Handbook on Graph Drawing and Visualization., pages 543-569. Chapman and Hall/CRC, 2013. |

[7] | M. K. Coleman and D. S. Parker. Aesthetics-based graph layout for human consumption. Softw. Pract. Exper., 26(12):1415-1438, Dec. 1996. |

[8] | K. Dev, N. Villar, and M. Lau.Polygons, points, or voxels?: stimuli selection for crowdsourcing aesthetics preferences of 3d shape pairs. In B. Gooch, Y. I. Gingold, H. Winnemoeller, L. Bartram, and S. N. Spencer, editors, Proceedings of the symposium on Computational Aesthetics, CAE 2017, Los Angeles, California, USA, pages 2:1-2:7. ACM, 2017. |

[9] | R. dos Santos Vieira, H. A. D. do Nascimento, and W. B. da Silva. The application of machine learning to problems in graph drawing – a literature review. In Proceedings og the 7th International Conference on Information, Process, and Knowledge Management, eKNOW 2015, Lisbon, Portugal, pages 112-118, 2015. |

[10] | P. Eades. A heuristic for graph drawing. Congressus Numerantium, 24:149- 160, 1984. |

[11] | P. Eades, S. Hong, A. Nguyen, and K. Klein. Shape-based quality metrics for large graph visualization. J. Graph Algorithms Appl., 21(1):29-53, 2017. · Zbl 1358.05273 |

[12] | G. H. Findenegg and T. Hellweg. Statistische Thermodynamik. Springer Spektrum, 2 edition, 2015. |

[13] | B. L. Fredrickson. What good are positive emotions. Review of General Psychology, 2:300-319, 1998. |

[14] | T. M. J. Fruchterman and E. M. Reingold. Graph drawing by force-directed placement. Softw., Pract. Exper., 21(11):1129-1164, 1991. |

[15] | S. Hachul and M. J¨unger. Drawing large graphs with a potential-field-based multilevel algorithm. In J. Pach, editor, Proceedings of the 13th International Symposium on Graph Drawing, Limerick, Ireland, pages 285-295. Springer Berlin Heidelberg, 2005. · Zbl 1111.68583 |

[16] | R. H. R. Hahnloser, R. Sarpeshkar, M. A. Mahowald, R. J. Douglas, and H. S. Seung.Digital selection and analogue amplification coexist in a cortex-inspired silicon circuit. Nature, 405:947-951, 6 2000. |

[17] | H. Haleem, Y. Wang, A. Puri, S. Wadhwa, and H. Qu. Evaluating the readability of force directed graph layouts: A deep learning approach. CoRR, abs/1808.00703, 2018. URL: |

[18] | W. Huang and P. Eades. How people read graphs. In S. Hong, editor, AsiaPacific Symposium on Information Visualisation, APVIS 2005, Sydney, Australia, pages 51-58, 2005. |

[19] | W. Huang, P. Eades, S.-H. Hong, and C.-C. Lin. Improving multiple aesthetics produces better graph drawings. Journal of Visual Languages and Computing, 24(4):262-272, 2013. |

[20] | W. Huang, S. Hong, and P. Eades. Effects of crossing angles. In IEEE VGTC Pacific Visualization Symposium 2008, PacificVis 2008, Kyoto, Japan, pages 41-46, 2008. |

[21] | W. Huang, S.-H. Hong, and P. Eades. Layout effects on sociogram perception. In P. Healy and N. S. Nikolov, editors, Graph Drawing, pages 262-273, Berlin, Heidelberg, 2006. Springer Berlin Heidelberg. · Zbl 1171.68624 |

[22] | W. Huang and M. Huang. Exploring the relative importance of crossing number and crossing angle. In G. Dai, K. Zhang, M. L. Huang, H. Wang, X. Yuan, L. Tao, and W. Chen, editors, Proceedings of the 3rd International Symposium on Visual Information Communication, VINCI ’10, pages 1-8. ACM, 2010. |

[23] | W. Huang, M. L. Huang, and C.-C. Lin. Evaluating overall quality of graph visualizations based on aesthetics aggregation. Information Sciences, 330:444-454, 2016. SI:Visual Info Communication. |

[24] | T. Kamada and S. Kawai. An algorithm for drawing general undirected graphs. Information Processing Letters, 31(1):7-15, 1989. · Zbl 0679.68128 |

[25] | Keras. URL: |

[26] | M. Klammler. Aesthetic value of graph layouts: Investigation of statistical syndromes for automatic quantification. Master’s thesis, Karlsruhe Institute of Technology, 2018. URL: |

[27] | M. Klammler et al. Source code for aesthetic discrimination of graph layouts. URL: · Zbl 07023823 |

[28] | R. Klapaukh. An Empirical Evaluation of Force-Directed Graph Layout. PhD thesis, Victoria University of Wellington, 2014. |

[29] | R. Kohavi. A study of cross-validation and bootstrap for accuracy estimation and model selection. In Proceedings of the 14th International Joint Conference on Artificial Intelligence, IJCAI 95, Montr´eal Qu´ebec, Canada, 2 Volumes, pages 1137-1145. Morgan Kaufmann, 1995. |

[30] | O. H. Kwon, T. Crnovrsanin, and K. L. Ma. What would a graph look like in this layout? A machine learning approach to large graph visualization. IEEE Transactions on Visualization and Computer Graphics, 24(1):478- 488, Jan 2018. |

[31] | T. Masui. Evolutionary learning of graph layout constraints from examples. In P. A. Szekely, editor, Proceedings of the 7th Annual ACM Symposium on User Interface Software and Technology, UIST ’94, pages 103-108. ACM, 1994. |

[32] | M. Nishiyama, T. Okabe, Y. Sato, and I. Sato. Sensation-based photo cropping. In W. Gao, Y. Rui, A. Hanjalic, C. Xu, E. G. Steinbach, A. ElSaddik, and M. X. Zhou, editors, Proceedings of the 17th ACM International Conference on Multimedia, MM ’09, pages 669-672. ACM, 2009. |

[33] | D. A. Norman. Emotion & design: attractive things work better. Interactions, 9(4):36-42, 2002. |

[34] | W. Press, S. Teukolsky, W. Vetterling, and B. Flannery. Numerical Recipes: The Art of Scientific Computing. Cambridge University Press, 3 edition, 2007. · Zbl 1132.65001 |

[35] | P. Prusinkiewicz and A. Lindenmayer. The Algorithmic Beauty of Plants. Springer, 1990. · Zbl 0850.92038 |

[36] | H. C. Purchase. Which aesthetic has the greatest effect on human understanding?In G. Di Battista, editor, Proceedings of the 5th International Symposium on Graph Drawing, GD 1997, Rome, Italy, volume 1353 of Lecture Notes in Computer Science, pages 248-261, 1997. |

[37] | H. C. Purchase. Performance of layout algorithms: Comprehension, not computation. Journal of Visual Languages and Computing, 9(6):647-657, 1998. |

[38] | H. C. Purchase. Metrics for graph drawing aesthetics. J. Vis. Lang. Comput., 13(5):501-516, 2002. |

[39] | H. C. Purchase, J.-A. Allder, and D. A. Carrington. Graph layout aesthetics in UML diagrams: User preferences. J. Graph Algorithms Appl., 6:255-279, 2002. · Zbl 1027.68103 |

[40] | H. C. Purchase, R. F. Cohen, and M. James. Validating graph drawing aesthetics. In F. Brandenburg, editor, Proceedings of the 4th International Symposium on Graph Drawing, GD 1996, Passau, Germany, volume 1027 of Lecture Notes in Computer Science, pages 435-446. Springer Berlin Heidelberg, 1996. |

[41] | H. C. Purchase, J. Hamer, M. N¨ollenburg, and S. G. Kobourov. On the usability of Lombardi graph drawings. In W. Didimo and M. Patrignani, editors, Proceedings of the 20th International Symposium on Graph Drawing, GD 2012, Redmond, USA, volume 7704, pages 451-462. Springer Berlin Heidelberg, 2012. · Zbl 1377.68185 |

[42] | A. Rosete-Suarez, M. Sebag, and A. Ochoa-Rodriguez. A study of evolutionary graph drawing, 1999. Laboratoire de Recherche en Informatique (LRI), Universite Paris-Sud XI, Tech. Rep. 1228. |

[43] | S. Schaefer, T. McPhail, and J. Warren. Image deformation using moving least squares. ACM Trans. Graph., 25(3):533-540, 2006. |

[44] | D. W. Scott.On optimal and data-based histograms.Biometrika, 66(3):605-610, 1979. · Zbl 0417.62031 |

[45] | C. E. Shannon. A mathematical theory of communication. The Bell System Technical Journal, 27(4):623-656, 10 1948. · Zbl 1154.94303 |

[46] | M. Sp¨onemann, B. Duderstadt, and R. von Hanxleden. Evolutionary meta layout of graphs. In T. Dwyer, H. C. Purchase, and A. Delaney, editors, Proceedings of 8th International Conference on Diagrammatic Representation and Inference, Diagrams 2014, Melbourne, VIC, Australia, pages 16- 30. Springer Berlin Heidelberg, 2014. |

[47] | N. Srivastava, G. Hinton, A. Krizhevsky, I. Sutskever, and R. Salakhutdinov. Dropout: A simple way to prevent neural networks from overfitting. Journal of Machine Learning Research, 15(1):1929-1958, 2014. · Zbl 1318.68153 |

[48] | R. Tamassia. Handbook of Graph Drawing and Visualization. Discrete Mathematics and Its Applications. CRC Press, 2013. |

[49] | Tensor flow. URL: |

[50] | N. Tractinsky, A. S. Katz, and D. Ikar. What is beautiful is usable. Interacting with Computers, 13(2):127-145, 2000. |

[51] | M. S. Treder. Behind the looking-glass: A review on human symmetry perception. Symmetry, 2(3):1510-1543, 2010. |

[52] | C. Ware. Information Visualization: Perception for Design. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 2012. |

[53] | C. Ware, H. C. Purchase, L. Colpoys, and M. McGill. Cognitive measurements of graph aesthetics. Information Visualization, 1(2):103-110, 2002. |

[54] | E. Welch and S. Kobourov. Measuring symmetry in drawings of graphs. Computer Graphics Forum, 36(3):341-351, 2017. |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.