Which symmetry metric to choose?#

The proposed symmetry metrics vary fundamentally in their approach. This page tries to give an overview of all symmetry metrics for graph drawings previously published in order to ease the decision on what metric might be most suitable for your specific use case.

In general we distinguish for different types of symmetry - reflective, rotational, translative and dihedral.

An overview of all identified symmetry metrics can be seen in the table below, most of which are implemented in gdMetriX.

Metric	Description	Source	Implementation
Node-based symmetry	Tries to identify all potential axes over all vertex pairs and build the sum over all axes over a certain quality threshold.	Purchase [Pur02]	`symmetry.reflective_symmetry()`
Edge-based symmetry	This metric tries to improve upon the node-based symmetry by also considering edges.	Klapaukh et al. [KMP18]	`symmetry.edge_based_symmetry()`
Stress	Based on the classic term of stress, i.e. the ratio of the edge lengths, this measure tries to define a measure of energy in a drawing, with lower energy levels claimed to correspond to more symmetric drawings.	Welch and Kobourov [WK17]	`symmetry.stress()`
Even neighborhood distribution	Determines how evenly the neighbors of each vertex are distributed among each vertex.	Xu et al. [XYG18]	`symmetry.even_neighborhood_distribution()`
Automorphism detection	Tries to determine the extent to which a drawing displays an automorphism or a group of automorphisms, meaning that this metric takes the structural symmetry of the graph into account.	Meidiana et al. [MHEK22]
Pixel-based symmetry	A novel approach using the pixel drawing of the graph to estimate symmetry.		`symmetry.visual_symmetry()`

Comparison#

A more in-depth comparison between the node-, edge-, and stress-based approaches can be seen in the corresponding study by Welch and Kobourov [WK17]. They concluded, that the node-based metric agreed with human perception of symmetry slightly more often compared to the edge-based metric. The stress-based metric did not outperform either of the other metrics.

A more basic overview of the properties of all metrics is given in the following table.

Metric	Type of symmetry	Runtime	Scope	Robust	Faithful
Node-based symmetry	Reflective	\(O(n^7)\)	Both	Partially	No
Edge-based symmetry	Reflective, translative, rotational	\(O(m^2)\)	Both	No	No
Stress	n.a.	\(O(n^2)\)	Local	Yes	Yes
Even neighborhood distribution	n.a.	\(O(n^2)\)	Local	Yes	Yes
Automorphism detection	Reflective, translational	\(O(n \log n)\)	Local	Yes	Yes
Pixel-based symmetry	Reflective, rotational, dihedral	\(O(n + m)\)	Global	No	No

Types of symmetry. Three main types of symmetry are distinguished in literature [DLKP18]. If a pattern exhibits reflective symmetry, it is mirrored along an axis. If a pattern exhibits rotational symmetry, if it remains unchanged after rotating it around a central point for a given angle \(α < 360^\circ\). A pattern exhibits translational symmetry if it remains unchanged after applying a shift transformation.

Scope. The neural symmetry only considers global symmetry axes. As the node- and edge-based approaches integrate a multitude of axes into the final value, some axes might represent more local substructures while others reflect global structures. The edge-based symmetry has the advantages that the number of considered axes can be customised. With a lower number of axes, it is expected that only the strongest, i.e. global, symmetries are considered. More subtle, local symmetries might be considered as well. The node-based symmetry metric does not offer such trade-offs. All other metrics are based on local substructures. It is, however, unclear to what extend global symmetry emerges from a sum of local symmetries.

Robustness. A metric is robust if it is not influenced by the scale, rotation or translation of the drawing [WK17]. A metric should aim to be robust, as the perceived symmetry does not change with such modifications. Unfortunately, the edge-based symmetry and the neural symmetry are not inherently robust to rescaling, the node-based metric can be made robust by wisely choosing appropriate parameters. All other metrics are inherently robust to rescaling, rotation and translation.

Faithfulness. A metric is faithful, if it is able to detect whether the depicted symmetries match the inherit symmetries of the graph itself [MHEK22]. The automorphism metric was designed with that exact goal in mind. The stress- and force-based approaches consider the structure of the graph as well, the extend to which it influences the final metric, however, has to be evaluated separately.

Runtime#

Especially when used iteratively in an automatic embedder, a symmetry metric has to be quick to obtain. However, especially the node- and edge-based metrics - with a runtime of \(O(n^7)\) and \(O(m^2)\) respectively are infeasible to obtain for bigger instances.

To compare the runtime, we generated random graphs with edge densities from 10% up to 90% (see the figure below).

When focusing only on the faster metrics, we can see that the stress-based approach takes a bit longer compared to the rest. This is due to the additional binary search that is done to minimize the final metric as discussed above.

Runtime comparison of the faster metrics#

Correlation#

In case all metrics are capable of measuring some sense of symmetry, we expect that they exhibit some extend of correlation.

The correlation between all symmetry metrics are depicted below. The data consists of random graphs embedded using the force-based embedder from networkX.

Scatter plot between all implemented symmetry metrics#

Correlation matrix between all implemented symmetry metrics#

Correlation to other metrics#

Some symmetry metrics might highly depend on, i.e., the density or size of a graph.

See the scatter plot below to evaluate of a specific metric is right for you.

Bibliography#

[BRSG07]

Chris Bennett, Jody Ryall, Leo Spalteholz, and Amy Gooch. The aesthetics of graph visualization. Computational Aesthetics in Graphics, 2007. doi:10.2312/COMPAESTH/COMPAESTH07/057-064.

[Bur15]

Michael Burch. The aesthetics of diagrams. In Proceedings of the 6th International Conference on Information Visualization Theory and Applications - Volume 1: IVAPP, (VISIGRAPP 2015), 262–267. INSTICC, SciTePress, 2015. doi:10.5220/0005357502620267.

[CP96]

Michael K. Coleman and D. Stott Parker. Aesthetics-based Graph Layout for Human Consumption. Software: Practice and Experience, 26(12):1415–1438, December 1996.

[DLKP18]

Felice De Luca, Stephen Kobourov, and Helen Purchase. Perception of Symmetries in Drawings of Graphs. In Therese Biedl and Andreas Kerren, editors, Graph Drawing and Network Visualization, volume 11282, pages 433–446. Springer International Publishing, Cham, 2018. doi:10.1007/978-3-030-04414-5_31.

[KMP18]

Roman Klapaukh, Stuart Marshall, and David Pearce. A Symmetry Metric for Graphs and Line Diagrams. In Peter Chapman, Gem Stapleton, Amirouche Moktefi, Sarah Perez-Kriz, and Francesco Bellucci, editors, Diagrammatic Representation and Inference, volume 10871, pages 739–742. Springer International Publishing, Cham, 2018. doi:10.1007/978-3-319-91376-6_71.

[MHEK22] (1,2)

A. Meidiana, S.-H. Hong, P. Eades, and D. Keim. Automorphism Faithfulness Metrics for Symmetric Graph Drawings. IEEE Transactions on Visualization and Computer Graphics, pages 1–15, 2022. URL: https://ieeexplore.ieee.org/document/9987696/ (visited on 2023-12-10), doi:10.1109/TVCG.2022.3229354.

[MPWK24]

Gavin J. Mooney, Helen C. Purchase, Michael Wybrow, and Stephen G. Kobourov. The multi-dimensional landscape of graph drawing metrics. In 17th IEEE Pacific Visualization Symposium. Pacific Visualization 2024, 2024.

[Pur02]

Helen C. Purchase. Metrics for Graph Drawing Aesthetics. Journal of Visual Languages & Computing, 13(5):501–516, October 2002. doi:10.1006/jvlc.2002.0232.

[PCJ96]

Helen C. Purchase, Robert F. Cohen, and Murray James. Validating graph drawing aesthetics. In Franz J. Brandenburg, editor, Graph Drawing, 435–446. Berlin, Heidelberg, 1996. Springer Berlin Heidelberg.

[TDBB88]

R. Tamassia, G. Di Battista, and C. Batini. Automatic graph drawing and readability of diagrams. IEEE Transactions on Systems, Man, and Cybernetics, 18(1):61–79, 1988. doi:10.1109/21.87055.

[TR05]

M. Taylor and P. Rodgers. Applying graphical design techniques to graph visualisation. In Ninth International Conference on Information Visualisation (IV'05), 651–656. IEEE, 2005. doi:10.1109/IV.2005.19.

[WK17] (1,2,3)

E. Welch and S. Kobourov. Measuring Symmetry in Drawings of Graphs. Computer Graphics Forum, 36(3):341–351, June 2017. doi:10.1111/cgf.13192.

[XYG18]

Taihua Xu, Jie Yang, and Guanglei Gou. A Force-Directed Algorithm for Drawing Directed Graphs Symmetrically. Mathematical Problems in Engineering, 2018:1–24, November 2018. doi:10.1155/2018/6208509.