Interactive design and visualization of N-ary relationships

ABSTRACT

Graph and network visualization is a well-researched area. However, graphs are limited in that by definition they are designed to encode pairwise relationships between the nodes in the graph. In this paper, we strive for visualization of datasets that contain not only binary relationships between the nodes, but also higher-cardinality relationships (ternary, quaternary, quinary, senary, etc). While such higher-cardinality relationships can be treated as cliques (a complete graph of N nodes), visualization of cliques using graph visualization can lead to unnecessary visual cluttering due to all the pairwise edges inside each clique. In this paper, we develop a visualization for data that have relationships with cardinalities higher than two. By representing each N-ary relationship as an N-sided polygon, we turn the problem of visualizing such data sets into that of visualizing a two-dimensional complex, i.e. nodes, edges, and polygonal faces. This greatly reduces the number of edges needed to represent a clique and makes them as well as their cardinalities more easily recognized.

We develop a set of principles that measures the effectiveness of the visualization for two-dimensional complexes. Furthermore, we formulate our strategy with which the positions of the nodes in the complex and the orderings of the nodes inside each clique in the complex can be optimized. Furthermore, we allow the user to further improve the layout by moving a node or a polygon in 3D as well as changing the order of the nodes in a polygon. To demonstrate the effectiveness of our technique and system, we apply them to a social network and a gene dataset.

References

1. arabidopsis.org. 2009. Tair Protein Interaction. ftp://ftp.arabidopsis.org/home/tair/Proteins/Protein_interaction_data/TairProteinInteraction.20090527.txt. (2009).
2. L. Bavoil and K. Myers. 2008. Order independent transparency with dual depth peeling. Technical Report. NVIDIA Developer SDK 10. http://developer.download.nvidia.com/SDK/10\/opengl/src/dual_depth_peeling/doc/DualDepthPeeling.pdf
3. A. R. Benson, D. F. Gleich, and J. Leskovec. 2016. Higher-order organization of complex networks. Science 353, 6295 (2016), 163--166.
4. Siheng Chen, Dong Tian, Chen Feng, Anthony Vetro, and Jelena Kovačević. 2017. Fast Resampling of 3D Point Clouds via Graphs. arXiv preprint arXiv:1702.06397 (2017).
5. Gene Ontology Consortium and others. 2004. The Gene Ontology (GO) database and informatics resource. Nucleic acids research 32, suppl 1 (2004), D258--D261.
6. Laurel Cooper and Pankaj Jaiswal. 2016. The Plant Ontology: A Tool for Plant Genomics. Plant Bioinformatics: Methods and Protocols (2016), 89--114.
7. Laurel Cooper, Ramona L Walls, Justin Elser, Maria A Gandolfo, Dennis W Stevenson, Barry Smith, Justin Preece, Balaji Athreya, Christopher J Mungall, Stefan Rensing, and others. 2013. The plant ontology as a tool for comparative plant anatomy and genomic analyses. Plant and Cell Physiology 54, 2 (2013), e1--e1.
8. G. L. Cromar, A. Zhao, A. Yang, and J. Parkinson. 2015. Hyperscape: Visualization for complex biological networks. Bioinformatics 31, 20 (2015), 3390--3391.
9. Andrew R Deans, Suzanna E Lewis, Eva Huala, Salvatore S Anzaldo, Michael Ashburner, James P Balhoff, David C Blackburn, Judith A Blake, J Gordon Burleigh, Bruno Chanet, and others. 2015. Finding our way through phenotypes. PLoS Biol 13, 1 (2015), e1002033.
10. Cody Dunne and Ben Shneiderman. 2013. Motif Simplification: Improving Network Visualization Readability with Fan, Connector, and Clique Glyphs. In Proceedings of the SIGCHI Conference on Human Factors in Computing Systems (CHI '13). ACM, New York, NY, USA, 3247--3256.
11. Helen Gibson, Joe Faith, and Paul Vickers. 2013. A survey of two-dimensional graph layout techniques for information visualisation. Information Visualization 12, 3--4 (2013), 324--357.
12. Palash Goyal and Emilio Ferrara. 2017. Graph Embedding Techniques, Applications, and Performance: A Survey. CoRR abs/1705.02801 (2017). http://arxiv.org/abs/1705.02801
13. Jana Hackbusch, Klaus Richter, Judith Müller, Francesco Salamini, and Joachim F Uhrig. 2005. A central role of Arabidopsis thaliana ovate family proteins in networking and subcellular localization of 3-aa loop extension homeodomain proteins. Proceedings of the National Academy of Sciences of the United States of America 102, 13 (2005), 4908--4912.
14. Richard W Hamming. 1986. Numerical Methods for Scientists and Engineers (2Nd Ed.). Dover Publications, Inc., New York, NY, USA.
15. Ivan Herman, Guy Melançon, and M. Scott Marshall. 2000. Graph Visualization and Navigation in Information Visualization: A Survey. IEEE Transactions on Visualization and Computer Graphics 6, 1 (Jan. 2000), 24--43.
16. Yoshinori Hirano, Masahiro Nakagawa, Tomoe Suyama, Kohji Murase, Maya Shirakawa, Seiji Takayama, Tai-ping Sun, and Toshio Hakoshima. 2017. Structure of the SHR-SCR heterodimer bound to the BIRD/IDD transcriptional factor JKD. Nature Plants 3 (2017), 17010.
17. Yifan Hu. 2005. Efficient, high-quality force-directed graph drawing. Mathematica Journal 10, 1 (2005), 37--71.
18. Steffen Klamt, Utz-Uwe Haus, and Fabian Theis. 2009. Hypergraphs and Cellular Networks. PLoS Comput Biol 5, 5 (29 May 2009), e1000385+.
19. Ales Komarek, Jakub Pavlik, and Vladimir Sobeslav. 2015. Network Visualization Survey. Springer International Publishing, Cham, 275--284.
20. Martin Krzywinski, Inanc Birol, Steven JM Jones, and Marco A Marra. 2012. Hive plots-rational approach to visualizing networks. Briefings in bioinformatics 13, 5 (2012), 627--644.
21. Martin Krzywinski, Jacqueline Schein, Inanc Birol, Joseph Connors, Randy Gascoyne, Doug Horsman, Steven J Jones, and Marco A Marra. 2009. Circos: an information aesthetic for comparative genomics. Genome research 19, 9 (2009), 1639--1645.
22. Yuanyuan Liu and Carl J Douglas. 2015. A role for OVATE FAMILY PROTEIN1 (OFP1) and OFP4 in a BLH6-KNAT7 multi-protein complex regulating secondary cell wall formation in Arabidopsis thaliana. Plant signaling & behavior 10, 7 (2015), e1033126.
23. Franco Mascia, and Mauro Brunato. 2010. Techniques and Tools for Search Landscape Visualization and Analysis. In Proceedings of Stochastic Local Search 2009, Brussels, Belgium (Lecture Notes in Computer Science), Thomas Stützle, Mauro Birattari, and Holger Hoos (Eds.), Vol. 5752. Springer Berlin / Heidelberg, 92-104.
24. Anika Oellrich, Ramona L Walls, Ethalinda KS Cannon, Steven B Cannon, Laurel Cooper, Jack Gardiner, Georgios V Gkoutos, Lisa Harper, Mingze He, Robert Hoehndorf, and others. 2015. An ontology approach to comparative phenomics in plants. Plant methods 11, 1 (2015), 10.
25. Hiromi Ogasawara, Ryuji Kaimi, Joseph Colasanti, and Akiko Kozaki. 2011. Activity of transcription factor JACKDAW is essential for SHR/SCR-dependent activation of SCARECROW and MAGPIE and is modulated by reciprocal interactions with MAGPIE, SCARECROW and SHORT ROOT. Plant molecular biology 77, 4--5 (2011), 489--499.
26. Anne E Thessen, Daniel E Bunker, Pier Luigi Buttigieg, Laurel D Cooper, Wasila M Dahdul, Sami Domisch, Nico M Franz, Pankaj Jaiswal, Carolyn J Lawrence-Dill, Peter E Midford, and others. 2015. Emerging semantics to link phenotype and environment. Peer J 3 (2015), e1470.
27. Etsuji Tomita, Akira Tanaka, and Haruhisa Takahashi. 2006. The worst-case time complexity for generating all maximal cliques and computational experiments. Theorectical Computer Science 363, 1 (2006), 28--42.
28. Ramona L Walls, Balaji Athreya, Laurel Cooper, Justin Elser, Maria A Gandolfo, Pankaj Jaiswal, Christopher J Mungall, Justin Preece, Stefan Rensing, Barry Smith, and others. 2012. Ontologies as integrative tools for plant science. American journal of botany 99, 8 (2012), 1263--1275.

Index Terms

• Human-centered computing

  • Visualization

    • Visualization application domains

      • Information visualization

    • Visualization techniques

      • Graph drawings