Graph drawing by stochastic gradient descent

File Description SizeFormat 
1710.04626v3.pdfAccepted version8.73 MBAdobe PDFDownload
Title: Graph drawing by stochastic gradient descent
Author(s): Zheng, JX
Pawar, S
Goodman, DFM
Item Type: Journal Article
Abstract: A popular method of force-directed graph drawing is multidimensional scaling using graph-theoretic distances as input. We present an algorithm to minimize its energy function, known as stress, by using stochastic gradient descent (SGD) to move a single pair of vertices at a time. Our results show that SGD can reach lower stress levels faster and more consistently than majorization, without needing help from a good initialization. We then show how the unique properties of SGD make it easier to produce constrained layouts than previous approaches. We also show how SGD can be directly applied within the sparse stress approximation of Ortmann et al. [1], making the algorithm scalable up to large graphs.
Publication Date: 25-Jul-2018
Date of Acceptance: 4-Jul-2018
URI: http://hdl.handle.net/10044/1/62044
DOI: https://x.doi.org/10.1109/TVCG.2018.2859997
ISSN: 1077-2626
Publisher: Institute of Electrical and Electronics Engineers
Journal / Book Title: IEEE Transactions on Visualization and Computer Graphics
Copyright Statement: © 2018 IEEE. Personal use is permitted, but republication/redistribution requires IEEE permission. See http://www.ieee.org/publications_standards/publications/rights/index.html for more information
Keywords: cs.CG
cs.CG
cs.CG
cs.CG
0801 Artificial Intelligence And Image Processing
0802 Computation Theory And Mathematics
Software Engineering
Publication Status: Published online
Online Publication Date: 2018-07-25
Appears in Collections:Faculty of Engineering
Electrical and Electronic Engineering
Faculty of Natural Sciences



Items in Spiral are protected by copyright, with all rights reserved, unless otherwise indicated.

Creative Commons