Taurus: Towards a Unified Force Representation and Universal Solver for Graph Layout

• Main Authors: XUE, Mingliang, WANG, Zhi, ZHONG, Fahai, WANG, Yong, XU, Mingliang, DEUSSEN, Oliver, WANG, Yunhai
• Format: text
• Language: English
• Published: Institutional Knowledge at Singapore Management University 2023
• Subjects: Framework; Gradient Descent; Graph Layout; Databases and Information Systems; Graphics and Human Computer Interfaces
• Online Access: https://ink.library.smu.edu.sg/sis_research/7795; https://ink.library.smu.edu.sg/context/sis_research/article/8798/viewcontent/Taurus_av.pdf
• Institution: Singapore Management University

Over the past few decades, a large number of graph layout techniques have been proposed for visualizing graphs from various domains. In this paper, we present a general framework, Taurus, for unifying popular techniques such as the spring-electrical model, stress model, and maxent-stress model. It is based on a unified force representation, which formulates most existing techniques as a combination of quotient-based forces that combine power functions of graph-theoretical and Euclidean distances. This representation enables us to compare the strengths and weaknesses of existing techniques, while facilitating the development of new methods. Based on this, we propose a new balanced stress model (BSM) that is able to layout graphs in superior quality. In addition, we introduce a universal augmented stochastic gradient descent (SGD) optimizer that efficiently finds proper solutions for all layout techniques. To demonstrate the power of our framework, we conduct a comprehensive evaluation of existing techniques on a large number of synthetic and real graphs. We release an open-source package, which facilitates easy comparison of different graph layout methods for any graph input as well as effectively creating customized graph layout techniques.