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



Mingliang Xue, Zhi Wang, Fahai Zhong, Yong Wang, Mingliang Xu, Oliver Deussen, Yunhai Wang

 View presentation:2022-10-20T15:57:00ZGMT-0600Change your timezone on the schedule page
2022-10-20T15:57:00Z

Exemplar figure, described by caption below — In this paper, we present a general framework, which we call Taurus, Towards A Unified force Representation and Universal Solver for graph layout, that offers a unified view for understanding and comparing most of the popular graph layout algorithms. (A) 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. (B) 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. (C) To demonstrate the effectiveness of our framework, we compare the implementation of each layout method under our framework with its original or existing implementation. The results show that all methods implemented in Taurus (bottom) are similar to or even better than the original implementations (top), with a largely reduced runtime. (D) 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.

Prerecorded Talk

The live footage of the talk, including the Q&A, can be viewed on the session page, Graphs and Networks.

Fast forward

Abstract

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.