Drawing Large Graphs With A Dimensionality-Reduction-Based Multilevel Algorithm

Graph layout is an important subfield of information visualization.An efficient layout of graphs can give us an overall sense of the data.It helps us find structures,locate anomalies,and formu-late questions that can in turn be answered through interaction with the layout.Many algorithms for graph layout have been applied by the social networks,knowledge graph and deep learning.Graph drawing algorithms are categorised into the followings approaches:force-directed algorithms and dimensionality reduction methods.The force-directed methods were amongst the first to be devel-oped for automatic graph layout and are some of the most commonly used methods today.Based on a physical model of attraction and repulsion the aim is to lay out the graph optimally.This optimality agreed with criteria put forward as graph drawing aesthetics.As an alternative,dimensionality re-duction methods usually minimize the difference between the node similarity(e.g.,graph distance)in the graph space and the layout proximity(e.g.,Euclidean distance)in the layout space.They aim to preserve the local neighborhood structure of data.Eflflcient layout of large-scale graphs remains a challenging problem:both the force-directed and dimensionality reduction based methods suffer from high overhead for graph distance and optimization in each iteration.In this paper,we present a new graph layout algorithm,that enhances the dimensionality re-duction scheme to achieve efficient layout of large graphs.Our approach differs itself from conven-tional dimensionality reduction algorithms in three aspects:approximating pairwise node distances by means of a sparse distance matrix;estimating the gradient by using the negative sampling tech-nique;and accelerating the optimization process through a multi-level layout scheme.The algo-rithm achieves a linear complexity for both the computation and memory consumption,and scales up to large-scale graphs with millions of nodes.Experimental results and comparisons with state-of-the-art graph layout methods demonstrate the superiority of our approach.We evaluate our method on various datasets and compare ours with previous methods quantitatively and qualitatively.Our method is 1.8 times as fast as FM3 for a graph with 1,564,794 nodes and 56,300,289 links.Our method only consumes 3 GB memory to layout graph and FM3 needs approximately 56 GB.