COAST: A Convex Optimization Approach to Stress-Based Embedding

Gansner, Emden R. and Hu, Yifan and Krishnan, Shankar (2013) COAST: A Convex Optimization Approach to Stress-Based Embedding. In: 21st International Symposium, GD 2013, September 23-25, 2013, Bordeaux, France , pp. 268-279 (Official URL: http://dx.doi.org/10.1007/978-3-319-03841-4_24).

Full text not available from this repository.

Abstract

Visualizing graphs using virtual physical models is probably the most heavily used technique for drawing graphs in practice. There are many algorithms that are efficient and produce high-quality layouts. If one requires that the layout also respect a given set of non-uniform edge lengths, however, force-based approaches become problematic while energy-based layouts become intractable. In this paper, we propose a reformulation of the stress function into a two-part convex objective function to which we can apply semi-definite programming (SDP). We avoid the high computational cost associated with SDP by a novel, compact re-parameterization of the objective function using the eigenvectors of the graph Laplacian. This sparse representation makes our approach scalable. We provide experimental results to show that this method scales well and produces reasonable layouts while dealing with the edge length constraints.

Item Type:Conference Paper
Classifications:M Methods > M.400 Force-directed / Energy-based
P Styles > P.720 Straight-line
ID Code:1381

Repository Staff Only: item control page

References

Brandes, U., Pich, C.: Eigensolver methods for progressive multidimensional scaling of large data. In: Kaufmann, M., Wagner, D. (eds.) GD 2006. LNCS, vol. 4372, pp. 42–53. Springer, Heidelberg (2007)

Brandes, U., Pich, C.: An experimental study on distance-based graph drawing. In: Tollis, I.G., Patrignani, M. (eds.) GD 2008. LNCS, vol. 5417, pp. 218–229. Springer, Heidelberg (2009)

Chen, L., Buja, A.: Local multidimensional scaling for nonlinear dimension reduction, graph drawing, and proximity analysis. J. Amer. Statistical Assoc. 104, 209–219 (2009)

Chung, F.R.K.: Spectral Graph Theory (CBMS Regional Conference Series in Mathematics, No. 92). American Mathematical Society, Providene (1996)

Davis, T.A., Hu, Y.: U. of Florida Sparse Matrix Collection. ACM Transaction on Mathematical Software 38, 1–18 (2011), http://www.cise.ufl.edu/research/sparse/matrices/

Drineas, P., Frieze, A.M., Kannan, R., Vempala, S., Vinay, V.: Clustering large graphs via the singular value decomposition. Machine Learning 56, 9–33 (2004)

Eades, P.: A heuristic for graph drawing. Congressus Numerantium 42, 149–160 (1984)

Fruchterman, T.M.J., Reingold, E.M.: Graph drawing by force directed placement. Software - Practice and Experience 21, 1129–1164 (1991)

Gajer, P., Goodrich, M.T., Kobourov, S.G.: A multi-dimensional approach to force-directed layouts of large graphs. In: Marks, J. (ed.) GD 2000. LNCS, vol. 1984, pp. 211–221. Springer, Heidelberg (2001)

Gansner, E.R., Koren, Y., North, S.C.: Graph drawing by stress majorization. In: Pach, J. (ed.) GD 2004. LNCS, vol. 3383, pp. 239–250. Springer, Heidelberg (2005)

Gansner, E.R., Hu, Y., Krishnan, S.: COAST: A convex optimization approach to stress-based embedding (2013), http://arxiv.org/abs/1308.5218

Gansner, E.R., Hu, Y., North, S.C.: A maxent-stress model for graph layout. IEEE Trans. Vis. Comput. Graph. 19(6), 927–940 (2013)

Hachul, S., Jünger, M.: Drawing large graphs with a potential-field-based multilevel algorithm. In: Pach, J. (ed.) GD 2004. LNCS, vol. 3383, pp. 285–295. Springer, Heidelberg (2005)

Hu, Y.: Efficient and high quality force-directed graph drawing. Mathematica Journal 10, 37–71 (2005)

Johnson, D.B.: Efficient algorithms for shortest paths in sparse networks. J. ACM 24(1), 1–13 (1977)

Kamada, T., Kawai, S.: An algorithm for drawing general undirected graphs. Information Processing Letters 31, 7–15 (1989)

Khoury, M., Hu, Y., Krishnan, S., Scheidegger, C.: Drawing large graphs by low-rank stress majorization. Computer Graphics Forum 31(3), 975–984 (2012)

Koren, Y., Çivril, A.: The binary stress model for graph drawing. In: Tollis, I.G., Patrignani, M. (eds.) GD 2008. LNCS, vol. 5417, pp. 193–205. Springer, Heidelberg (2009)

Kruskal, J.B.: Multidimensioal scaling by optimizing goodness of fit to a nonmetric hypothesis. Psychometrika 29, 1–27 (1964)

Kruskal, J.B., Seery, J.B.: Designing network diagrams. In: Proc. First General Conference on Social Graphics, pp. 22–50. U. S. Department of the Census, Washington, D.C. (July 1980), Bell Laboratories Technical Report No. 49

Noack, A.: Energy models for graph clustering. J. Graph Algorithms and Applications 11(2), 453–480 (2007)

Noack, A.: Modularity clustering is force-directed layout. Physical Review E 79, 026102 (2009)

Pettie, S.: A new approach to all-pairs shortest paths on real-weighted graphs. Theoretical Computer Science 312(1), 47–74 (2004)

de Silva, V., Tenenbaum, J.B.: Global versus local methods in nonlinear dimensionality reduction. In: Advances in Neural Information Processing Systems 15, pp. 721–728. MIT Press, Cambridge (2003)

Tütüncü, R.H., Toh, K.C., Todd, M.J.: Solving semidefinite-quadratic-linear programs using SDPT3. Mathematical Programming 95(2), 189–217 (2003)

Walshaw, C.: A multilevel algorithm for force-directed graph drawing. J. Graph Algorithms and Applications 7, 253–285 (2003)