A Review on Quality Assessment Metrics for Edge Bundling Techniques

Ken Sakamoto (Tokyo Tech)

Ryosuke Saga (Osaka Prefecture University)

Ken Wakita (Tokyo Tech)

https://smartnova.github.io/ebundle/pvis2019/

Abstract
Edge-bundling techniques used in graph drawing simplify the graph structure and thereby offers an image easier to comprehend the structure for the human. The article reports metrics that were either used to quantitatively assess the edge-bundling results and/or was employed as the objective functions by the bundling algorithms. The study was conducted by reviewing 56 edge-bundling papers mainly published in VIS, EuroVIS, PacificVIS, and TVCG. Metrics for clutter reduction measure amount of ink usage, moving distances and the lengths of the control points, and curvature factor. Faithfulness is another type of measure that grasps loss of information in the bundled and therefore simplified image. The report compares and argues the advantage and disadvantage of the proposal.

Quality Assessment Metrics

Metrics for Visual Clutter

Pixel counting based approaches

Geometric approaches

Edge distortion

Metrics for Bundling Faithfulness

Faithfulness proposals (Nguyen, Eades, and Hong (2013), Nguyen, Eades, and Hong (2017))

Information faithfulness

Task faithfulness

Change faithfulness

The concept is proposed in (Nguyen, Eades, and Hong (2013), Nguyen, Eades, and Hong (2017)) but practical applications are yet to be seen.

Links

References

Bach, Benjamin, Nathalie Henry Riche, Christophe Hurter, Kim Marriott, and Tim Dwyer. 2017. “Towards Unambiguous Edge Bundling: Investigating Confluent Drawings for Network Visualization.” IEEE Transactions on Visualization and Computer Graphics 23 (1). Los Alamitos, CA, USA: IEEE Computer Society: 541–50. https://doi.org/doi.ieeecomputersociety.org/10.1109/TVCG.2016.2598958.

Beck, F, M Puppe, P Braun, M Burch, and S Diehl. 2011. “Edge Bundling Without Reducing the Source to Target Traceability.” InfoVis 2011 Posters.

Bourqui, Romain, Dino Ienco, Arnaud Sallaberry, Pascal Poncelet, undefined, undefined, undefined, and undefined. 2016. “Multilayer Graph Edge Bundling.” 2016 IEEE Pacific Visualization Symposium (PacificVis) 00. Los Alamitos, CA, USA: IEEE Computer Society: 184–88. https://doi.org/doi.ieeecomputersociety.org/10.1109/PACIFICVIS.2016.7465267.

Böttger, Joachim, Ralph Schurade, Estrid Jakobsen, Alexander Schäfer, and Daniel Margulies. 2014. “Connexel Visualization: A Software Implementation of Glyphs and Edge-Bundling for Dense Connectivity Data Using brainGL.” Frontiers in Neuroscience 8: 15. https://doi.org/10.3389/fnins.2014.00015.

Böttger, J., A. Schäfer, G. Lohmann, A. Villringer, and D. S. Margulies. 2014. “Three-Dimensional Mean-Shift Edge Bundling for the Visualization of Functional Connectivity in the Brain.” IEEE Transactions on Visualization and Computer Graphics 20 (3): 471–80. https://doi.org/10.1109/TVCG.2013.114.

Buchin, Kevin, Bettina Speckmann, and Kevin Verbeek. 2011. “Angle-Restricted Steiner Arborescences for Flow Map Layout.” In Algorithms and Computation, edited by Takao Asano, Shin-ichi Nakano, Yoshio Okamoto, and Osamu Watanabe, 250–59. Berlin, Heidelberg: Springer Berlin Heidelberg.

Buchin, K., B. Speckmann, and K. Verbeek. 2011. “Flow Map Layout via Spiral Trees.” IEEE Transactions on Visualization and Computer Graphics 17 (12): 2536–44. https://doi.org/10.1109/TVCG.2011.202.

Caserta, P., O. Zendra, and D. Bodénès. 2011. “3D Hierarchical Edge Bundles to Visualize Relations in a Software City Metaphor.” In 2011 6th International Workshop on Visualizing Software for Understanding and Analysis (Vissoft), 1–8. https://doi.org/10.1109/VISSOF.2011.6069451.

Cui, W., H. Zhou, H. Qu, P. C. Wong, and X. Li. 2008. “Geometry-Based Edge Clustering for Graph Visualization.” IEEE Transactions on Visualization and Computer Graphics 14 (6): 1277–84. https://doi.org/10.1109/TVCG.2008.135.

Dang, T., and A. Forbes. 2017. “CactusTree: A Tree Drawing Approach for Hierarchical Edge Bundling.” In 2017 Ieee Pacific Visualization Symposium (Pacificvis), 210–14. https://doi.org/10.1109/PACIFICVIS.2017.8031596.

Dickerson, Eppstein David Goodrich Michael T. Meng Jeremy Y., Matthew. 2005. “Confluent Drawings: Visualizing Non-Planar Diagrams in a Planar Way.” Journal of Graph Algorithms and Applications 9 (1). Brown University, Providence, RI; University of Texas, Dallas: 31–52. http://eudml.org/doc/52298.

Dickerson, Matthew, David Eppstein, Michael T. Goodrich, and Jeremy Yu Meng. 2004. “Confluent Drawings: Visualizing Non-Planar Diagrams in a Planar Way.” In Graph Drawing, edited by Giuseppe Liotta, 1–12. Berlin, Heidelberg: Springer Berlin Heidelberg.

Dwyer, Tim, Kim Marriott, and Michael Wybrow. 2007. “Integrating Edge Routing into Force-Directed Layout.” In Graph Drawing, edited by Michael Kaufmann and Dorothea Wagner, 8–19. Berlin, Heidelberg: Springer Berlin Heidelberg.

Eppstein, David, Michael T. Goodrich, and Jeremy Yu Meng. 2006. “Delta-Confluent Drawings.” In Graph Drawing, edited by Patrick Healy and Nikola S. Nikolov, 165–76. Berlin, Heidelberg: Springer Berlin Heidelberg.

Ersoy, Ozan, Christophe Hurter, Fernando Paulovich, Gabriel Cantareiro, and Alex Telea. 2011. “Skeleton-Based Edge Bundling for Graph Visualization.” IEEE Transactions on Visualization and Computer Graphics 17 (12). IEEE: 2364–73. https://doi.org/10.1109/TVCG.2011.233.

Everts, M. H., E. Begue, H. Bekker, J. B. T. M. Roerdink, and T. Isenberg. 2015. “Exploration of the Brain’s White Matter Structure Through Visual Abstraction and Multi-Scale Local Fiber Tract Contraction.” IEEE Transactions on Visualization and Computer Graphics 21 (7): 808–21. https://doi.org/10.1109/TVCG.2015.2403323.

Ferreira, Joelma de M., Hugo A. D. do Nascimento, and Les R. Foulds. 2018. “An Evolutionary Algorithm for an Optimization Model of Edge Bundling.” Information 9 (7). https://doi.org/10.3390/info9070154.

Gansner, Emden R, Yifan Hu, Stephen North, and Carlos Scheidegger. 2011. “Multilevel Agglomerative Edge Bundling for Visualizing Large Graphs.” In Pacific Visualization Symposium (Pacificvis), 2011 Ieee, 187–94. IEEE. https://doi.org/10.1109/PACIFICVIS.2011.5742389.

Giereth, M., H. Bosch, and T. Ertl. 2008. “A 3D Treemap Approach for Analyzing the Classificatory Distribution in Patent Portfolios.” In 2008 Ieee Symposium on Visual Analytics Science and Technology, 189–90. https://doi.org/10.1109/VAST.2008.4677380.

Hanjalić, A. 2013. “ClonEvol: Visualizing Software Evolution with Code Clones.” In 2013 First Ieee Working Conference on Software Visualization (Vissoft), 1–4. https://doi.org/10.1109/VISSOFT.2013.6650525.

Heinrich, Julian, Yuan Luo, Arthur E. Kirkpatrick, Hao Zhang, and Daniel Weiskopf. 2011. “Evaluation of a Bundling Technique for Parallel Coordinates.” CoRR abs/1109.6073. http://arxiv.org/abs/1109.6073.

Holten, Danny. 2006. “Hierarchical Edge Bundles: Visualization of Adjacency Relations in Hierarchical Data.” IEEE Transactions on Visualization and Computer Graphics 12 (5). IEEE: 741–48. https://doi.org/10.1109/TVCG.2006.147.

Holten, Danny, and Jarke J. Van Wijk. 2008. “Visual Comparison of Hierarchically Organized Data.” Computer Graphics Forum 27 (3): 759–66. https://doi.org/10.1111/j.1467-8659.2008.01205.x.

Holten, Danny, and Jarke J Van Wijk. 2009. “Force-Directed Edge Bundling for Graph Visualization.” In Computer Graphics Forum, 28:983–90. 3. Wiley Online Library.

Hurter, Christophe, Ozan Ersoy, Sara Irina Fabrikant, Tijmen R Klein, and Alexandru C Telea. 2014. “Bundled Visualization of Dynamic Graph and Trail Data.” IEEE Transactions on Visualization and Computer Graphics 20 (8). IEEE: 1141–57. https://doi.org/10.1109/TVCG.2013.246.

Hurter, Christophe, Ozan Ersoy, and Alexandru Telea. 2012. “Graph Bundling by Kernel Density Estimation.” In Computer Graphics Forum, 31:865–74. 3pt1. Wiley Online Library. https://doi.org/10.1111/j.1467-8659.2012.03079.x.

———. 2013. “Smooth Bundling of Large Streaming and Sequence Graphs.” In Visualization Symposium (Pacificvis), 2013 Ieee Pacific, 41–48. IEEE. https://doi.org/10.1109/PacificVis.2013.6596126.

Hurter, Christophe, Alexandru Telea, and Ozan Ersoy. 2011. “Moleview: An Attribute and Structure-Based Semantic Lens for Large Element-Based Plots.” IEEE Transactions on Visualization and Computer Graphics 17 (12). IEEE: 2600–2609. https://doi.org/10.1109/TVCG.2011.223.

Hurter, C., S. Puechmorel, F. Nicol, and A. Telea. 2018. “Functional Decomposition for Bundled Simplification of Trail Sets.” IEEE Transactions on Visualization and Computer Graphics 24 (1): 500–510. https://doi.org/10.1109/TVCG.2017.2744338.

Kienreich, Wolfgang, and Christin Seifert. 2010. “An Application of Edge Bundling Techniques to the Visualization of Media Analysis Results.” In Information Visualisation (Iv), 2010 14th International Conference, 375–80. IEEE. https://doi.org/10.1109/IV.2010.58.

Kwon, Oh-Hyun, Chris Muelder, Kyungwon Lee, and Kwan-Liu Ma. 2015. “Spherical Layout and Rendering Methods for Immersive Graph Visualization.” In Visualization Symposium (Pacificvis), 2015 Ieee Pacific, 63–67. IEEE. https://doi.org/10.1109/PACIFICVIS.2015.7156357.

Lambert, A., R. Bourqui, and D. Auber. 2010a. “3D Edge Bundling for Geographical Data Visualization.” In 2010 14th International Conference Information Visualisation, 329–35. https://doi.org/10.1109/IV.2010.53.

———. 2010b. “Winding Roads: Routing Edges into Bundles.” Computer Graphics Forum 29 (3): 853–62. https://doi.org/10.1111/j.1467-8659.2009.01700.x.

Lambert, A., J. Dubois, and R. Bourqui. 2011. “Pathway Preserving Representation of Metabolic Networks.” Computer Graphics Forum 30 (3): 1021–30. https://doi.org/10.1111/j.1467-8659.2011.01951.x.

Lhuillier, A., C. Hurter, and A. Telea. 2017a. “FFTEB: Edge Bundling of Huge Graphs by the Fast Fourier Transform.” In 2017 Ieee Pacific Visualization Symposium (Pacificvis), 190–99. https://doi.org/10.1109/PACIFICVIS.2017.8031594.

———. 2017b. “State of the Art in Edge and Trail Bundling Techniques.” Computer Graphics Forum 36 (3): 619–45. https://doi.org/10.1111/cgf.13213.

Luo, S., C. Liu, B. Chen, and K. Ma. 2012. “Ambiguity-Free Edge-Bundling for Interactive Graph Visualization.” IEEE Transactions on Visualization and Computer Graphics 18 (5): 810–21. https://doi.org/10.1109/TVCG.2011.104.

Maaten, Laurens van der, and Geoffrey Hinton. 2008. “Visualizing Data Using T-Sne.” Journal of Machine Learning Research 9 (Nov): 2579–2605.

McDonnell, K. T., and K. Mueller. 2008. “Illustrative Parallel Coordinates.” Computer Graphics Forum 27 (3): 1031–8. https://doi.org/10.1111/j.1467-8659.2008.01239.x.

McGee, Fintan, and John Dingliana. 2012. “An Empirical Study on the Impact of Edge Bundling on User Comprehension of Graphs.” In Proceedings of the International Working Conference on Advanced Visual Interfaces, 620–27. AVI ’12. New York, NY, USA: ACM. https://doi.org/10.1145/2254556.2254670.

McGraw, Tim. 2015. “Graph-Based Visualization of Neuronal Connectivity Using Matrix Block Partitioning and Edge Bundling.” In International Symposium on Visual Computing, 3–13. Springer. https://doi.org/10.1109/PACIFICVIS.2015.7156357.

Moura, Daniel C. 2015. “3D Density Histograms for Criteria-Driven Edge Bundling.” arXiv Preprint arXiv:1504.02687.

Nachmanson, Lev B, and Sergey Pupyrev. 2015. “Visualizing a Layered Graph Using Edge Bundling.” Google Patents. https://patents.google.com/patent/US8933937B2/en.

Nguyen, Quan, Peter Eades, and Seok-Hee Hong. 2012. “StreamEB: Stream Edge Bundling.” In International Symposium on Graph Drawing, 400–413. Springer. https://doi.org/10.1007/978-3-642-36763-2_36.

———. 2013. “On the Faithfulness of Graph Visualizations.” In Visualization Symposium (Pacificvis), 2013 Ieee Pacific, 209–16. IEEE. https://doi.org/10.1109/PacificVis.2013.6596147.

Nguyen, Quan Hoang, Peter Eades, and Seok-Hee Hong. 2017. “Towards Faithful Graph Visualizations.” arXiv Preprint arXiv:1701.00921.

Nguyen, Quan, Seok-Hee Hong, and Peter Eades. 2011. “TGI-EB: A New Framework for Edge Bundling Integrating Topology, Geometry and Importance.” In International Symposium on Graph Drawing, 123–35. Springer.

Nocaj, Arlind, and Ulrik Brandes. 2013. “Stub Bundling and Confluent Spirals for Geographic Networks.” In Graph Drawing, edited by Stephen Wismath and Alexander Wolff, 388–99. Cham: Springer International Publishing.

Palmas, G., M. Bachynskyi, A. Oulasvirta, H. P. Seidel, and T. Weinkauf. 2014. “An Edge-Bundling Layout for Interactive Parallel Coordinates.” In 2014 Ieee Pacific Visualization Symposium, 57–64. https://doi.org/10.1109/PacificVis.2014.40.

Palmas, Gregorio, and Tino Weinkauf. 2016. “Space Bundling for Continuous Parallel Coordinates.” In Proceedings of the Eurographics / Ieee Vgtc Conference on Visualization: Short Papers, 61–65. EuroVis ’16. Goslar Germany, Germany: Eurographics Association. https://doi.org/10.2312/eurovisshort.20161162.

Peysakhovich, V., C. Hurter, and A. Telea. 2015. “Attribute-Driven Edge Bundling for General Graphs with Applications in Trail Analysis.” In Visualization Symposium (Pacificvis), 2015 Ieee Pacific, 39–46. https://doi.org/10.1109/PACIFICVIS.2015.7156354.

Phan, Doantam, Ling Xiao, R. Yeh, and P. Hanrahan. 2005. “Flow Map Layout.” In IEEE Symposium on Information Visualization, 2005. INFOVIS 2005., 219–24. https://doi.org/10.1109/INFVIS.2005.1532150.

Polisciuc, Evgheni, Filipe Assunção, and Penousal Machado. 2018. “Towards Partially Automatic Search of Edge Bundling Parameters.” In Computational Intelligence in Music, Sound, Art and Design, 223–38. Springer International Publishing. https://doi.org/10.1007/978-3-319-77583-8_15.

Pupyrev, Sergey, Lev Nachmanson, and Michael Kaufmann. 2011. “Improving Layered Graph Layouts with Edge Bundling.” In Graph Drawing, 329–40. Springer Berlin Heidelberg. https://doi.org/10.1007/978-3-642-18469-7_30.

Saga, Ryosuke. 2016a. “Quantitative Evaluation for Edge Bundling Based on Structural Aesthetics.” In EuroVis 2016 - Posters, edited by Tobias Isenberg and Filip Sadlo. The Eurographics Association. https://doi.org/10.2312/eurp.20161131.

———. 2016b. “Quantitative Evaluation for Edge Bundling by Difference of Edge Lengths and Area Occupation.” In HCI International 2016 – Posters’ Extended Abstracts, edited by Constantine Stephanidis, 287–90. Cham: Springer International Publishing.

———. 2017. “Preliminary Survey for Multigraph Integration and Visualization Framework.” In HCI International 2017 – Posters’ Extended Abstracts, edited by Constantine Stephanidis, 597–601. Cham: Springer International Publishing.

———. 2018a. “Quantitative Evaluation of Multi-Type Edge Bundling - Example for Japan Airmap.” INSTICC; SciTePress. https://doi.org/10.5220/0006638503270332.

———. 2018b. “Validation of Quantitative Measures for Edge Bundling by Comparing with Human Feeling.” In EuroVis 2018 - Posters, edited by Anna Puig and Renata Raidou. The Eurographics Association. https://doi.org/10.2312/eurp.20181121.

Saga, Ryosuke, Naoaki Ohkusa, Takafumi Yamashita, and Nahomi Maki. 2017. “Visualization of Customer Expectations from Web Text Using Co-Occurrence Graph and Auto-Labeling in the Service Market.” INSTICC; SciTePress. https://doi.org/10.5220/0006238303170321.

Saga, Ryosuke, Masahiro Terachi, and Hiroshi Tsuji. 2012. “FACT-Graph: Trend Visualization by Frequency and Co-Occurrence.” Electronics and Communications in Japan 95 (2): 50–58. https://doi.org/10.1002/ecj.10347.

Saga, Ryosuke, and Takafumi Yamashita. 2015a. “Multi-Type Edge Bundling for Geographic Layout Graph.” In Knowledge Management (Ickm), 2015 11th International Conference on.

———. 2015b. “Multi-Type Edge Bundling in Force-Directed Layout and Evaluation.” Procedia Computer Science 60: 1763–71. https://doi.org/https://doi.org/10.1016/j.procs.2015.08.286.

Selassie, D., B. Heller, and J. Heer. 2011. “Divided Edge Bundling for Directional Network Data.” Visualization and Computer Graphics, IEEE Transactions on 17 (12): 2354–63. https://doi.org/10.1109/TVCG.2011.190.

Shimodaira, H., and H Nagata. 2012. “A Laplacian for the Personalized Pagerank of Undirected Graph.” Halifax, Canada.

Sun, Maoyuan, Peng Mi, Chris North, and Naren Ramakrishnan. 2016. “BiSet: Semantic Edge Bundling with Biclusters for Sensemaking.” IEEE Transactions on Visualization and Computer Graphics 22 (1). Los Alamitos, CA, USA: IEEE Computer Society: 310–19. https://doi.org/doi.ieeecomputersociety.org/10.1109/TVCG.2015.2467813.

Sun, M., J. Zhao, H. Wu, K. Luther, C. North, and N. Ramakrishnan. 2018. “The Effect of Edge Bundling and Seriation on Sensemaking of Biclusters in Bipartite Graphs.” IEEE Transactions on Visualization and Computer Graphics, 1–1. https://doi.org/10.1109/TVCG.2018.2861397.

Telea, A., and O. Ersoy. 2010. “Image-Based Edge Bundles: Simplified Visualization of Large Graphs.” Computer Graphics Forum 29 (3). Blackwell Publishing Ltd: 843–52. https://doi.org/10.1111/j.1467-8659.2009.01680.x.

Telea, Alexandru, and David Auber. 2008. “Code Flows: Visualizing Structural Evolution of Source Code.” Computer Graphics Forum 27 (3): 831–38. https://doi.org/10.1111/j.1467-8659.2008.01214.x.

Toeda, N., R. Nakazawa, T. Itoh, T. Saito, and D. W. Archambault. 2016. “On Edge Bundling and Node Layout for Mutually Connected Directed Graphs.” In 2016 20th International Conference Information Visualisation (Iv), 94–99. https://doi.org/10.1109/IV.2016.23.

Trümper, J., J. Döllner, and A. Telea. 2013. “Multiscale Visual Comparison of Execution Traces.” In 2013 21st International Conference on Program Comprehension (Icpc), 53–62. https://doi.org/10.1109/ICPC.2013.6613833.

Wu, Jieting, Jianping Zeng, Feiyu Zhu, and Hongfeng Yu. 2018. “MLSEB: Edge Bundling Using Moving Least Squares Approximation.” In Lecture Notes in Computer Science, 379–93. Springer International Publishing. https://doi.org/10.1007/978-3-319-73915-1_30.

Wu, Jieting, Feiyu Zhu, Xin Liu, and Hongfeng Yu. 2018. “An Information-Theoretic Framework for Evaluating Edge Bundling Visualization.” Entropy 20 (9). https://doi.org/10.3390/e20090625.

Wu, J., L. Yu, and H. Yu. 2015. “Texture-Based Edge Bundling: A Web-Based Approach for Interactively Visualizing Large Graphs.” In 2015 Ieee International Conference on Big Data (Big Data), 2501–8. https://doi.org/10.1109/BigData.2015.7364046.

Yamashita, Takafumi, and Ryosuke Saga. 2015. “Edge Bundling in Multi-Attributed Graphs.” In Human Interface and the Management of Information. Information and Knowledge Design, edited by Sakae Yamamoto, 138–47. Cham: Springer International Publishing. https://doi.org/10.1007/978-3-319-20612-7_14.

———. 2017. “Cluster-Based Edge Bundling Based on a Line Graph.” INSTICC; SciTePress. https://doi.org/10.5220/0006236003110316.

Yang, Y., T. Dwyer, S. Goodwin, and K. Marriott. 2017. “Many-to-Many Geographically-Embedded Flow Visualisation: An Evaluation.” IEEE Transactions on Visualization and Computer Graphics 23 (1): 411–20. https://doi.org/10.1109/TVCG.2016.2598885.

Yi, Ji Soo, Rachel Melton, John Stasko, and Julie A Jacko. 2005. “Dust & Magnet: Multivariate Information Visualization Using a Magnet Metaphor.” Information Visualization 4 (4). SAGE Publications: 239–56.

Zhonghua, Yao, Wu Lingda, undefined, undefined, undefined, and undefined. 2016. “Research on Network Simplification by Edge Bundling.” 2016 IEEE First International Conference on Data Science in Cyberspace (DSC) 00. Los Alamitos, CA, USA: IEEE Computer Society: 466–72. https://doi.org/doi.ieeecomputersociety.org/10.1109/DSC.2016.95.

Zhou, Hong, Xiaoru Yuan, Huamin Qu, Weiwei Cui, and Baoquan Chen. 2008. “Visual Clustering in Parallel Coordinates.” Computer Graphics Forum 27 (3): 1047–54. https://doi.org/10.1111/j.1467-8659.2008.01241.x.

Zhou, H., Panpan Xu, X. Yuan, and H. Qu. 2013. “Edge Bundling in Information Visualization.” Tsinghua Science and Technology 18 (2): 145–56. https://doi.org/10.1109/TST.2013.6509098.

Zielasko, D., B. Weyers, B. Hentschel, and T. W. Kuhlen. 2016. “Interactive 3D Force-Directed Edge Bundling.” Computer Graphics Forum 35 (3): 51–60. https://doi.org/10.1111/cgf.12881.

Zwan, M. van der, V. Codreanu, and A. Telea. 2016. “CUBu: Universal Real-Time Bundling for Large Graphs.” IEEE Transactions on Visualization and Computer Graphics 22 (12): 2550–63. https://doi.org/10.1109/TVCG.2016.2515611.