The tsNET algorithm adapts the popular dimensional reduction method t-SNE for graph drawing to compute high-quality drawings, preserving the neighborhood and clustering structure. However, its O(nm) runtime results in poor scalability for large graphs. In this poster, we present three fast algorithms for reducing the time complexity of tsNET to O(n log n) time and O(n) time, by integrating new fast methods for computation of high-dimensional probabilities and entropy computation with fast t-SNE algorithms for computation of KL divergence gradient. Specifically, we present two O(n log n)-time algorithms BH-tsNET and FIt-tsNET, incorporating partial BFS-based high-dimensional probability computation and a new quadtree-based entropy computation with fast t-SNE algorithms, and O(n)-time algorithm L-tsNET, introducing a new fast interpolation-based entropy computation. Extensive experiments using benchmark data sets confirm that BH-tsNET, FIt-tsNET, and L-tsNET outperform tsNET, achieving 93.5%, 96%, and 98.6% faster runtime, respectively, while computing similar quality drawings in terms of quality metrics (neighborhood preservation, stress, shape-based metrics, and edge crossing) and visual comparison.

Shape-based metrics measure how faithfully a drawing D of a large graph G shows the structure of the graph by comparing the similarity between G and a proximity graph S computed from D. In this paper, we present new degree-constrained shape-based metrics by introducing new proximity graphs dcGG and dcRNG, which constrain the degree of each vertex v in the proximity graph S to be no greater than the degree of v in G. Extensive experiments demonstrate that our new degree-constrained shape-based metrics QdcRNGand QdcGGcan more accurately measure the shape-faithfulness than the state-of-the-art degree-sensitive shape-based metrics, with on average 29.1% better metrics for highly shape-faithful layouts. Moreover, we present extensive comparison experiments of ten popular graph layouts using our new shape-based metrics QdcRNGand QdcGGto recommend shape-faithful layouts for large and complex graphs. Furthermore, we present a new shape-faithful graph drawing algorithm dcShFR, based on the most popular force-directed algorithm FR, to optimize the new shape-based metrics QdcRNGand QdcGG. Extensive experiments demonstrate that our dcShFR algorithm computes 14.5% higher shape-faithful drawings than FR on average.

We present new metrics and algorithms for connectivity-faithful visualization for dynamic graphs. We first present the SCQ (Sampling Change Quality) framework to evaluate dynamic graph sampling, based on the popular sampling quality metrics for the sampling of static graphs. We introduce the $S C Q_{C L O S E}$ metric as a specific instance of the framework, based on closeness centrality. We next introduce the PCQ (Proxy Change Quality) framework for evaluating the proxy distance change faithfulness of the visualization of dynamic graph sampling. More specifically, we introduce the PDCQ (Proxy Distance Change Quality) metric for proxy distance change faithfulness, i.e., how faithfully the ground-truth change in the shortest path distances of the original dynamic graphs is displayed as the geometric change in Euclidean distances in the drawing of the dynamic graph samples. Finally, we present a dynamic graph sampling algorithm for preserving the connectivity structures of the original dynamic graphs, called DCFNI (Dynamic Connectivity-Faithful NI), based on the well-known NI (Nagamochi-Ibaraki) algorithm for computing a connectivity-faithful sparsification. Extensive experiments on DCFNI, through comparison with the state-of-the-art DSS (Dynamic Spectral Sparsification) which outperforms random sampling methods, demonstrate the effectiveness of DCFNI over DSS: $53 \%$ higher $S C Q_{C L O S E}$ and $13 \%$ higher PDCQ on average, and better preserving the global connectivity of dynamic graphs on visual comparison.

Connectivity is one of the important fundamental structural properties of graphs, and a graph drawing D should faithfully represent the connectivity structure of the underlying graph G. This paper investigates connectivity-faithful graph drawing leveraging the famous Nagamochi-Ibaraki (NI) algorithm, which computes a sparsification G_NI, preserving the k-connectivity of a k-connected graph G. Specifically, we first present CFNI, a divide-and-conquer algorithm, which computes a sparsification G_CFNI, which preserves the global k-connectivity of a graph G and the local h-connectivity of the h-connected components of G. We then present CFGD, a connectivity-faithful graph drawing algorithm based on CFNI, which faithfully displays the global and local connectivity structure of G. Extensive experiments demonstrate that CFNI outperforms NI with 66% improvement in the connectivity-related sampling quality metrics and 73% improvement in proxy quality metrics. Consequently, CFGD outperforms a naive application of NI for graph drawing, in particular with 62% improvement in stress metrics. Moreover, CFGD runs 51% faster than drawing the whole graph G, with a similar quality.

The cluster faithfulness metrics CQ measure how faithfully the ground truth clustering of a graph is represented as the geometric clustering in a drawing of the graph. Existing CQ metrics use k-means clustering, which effectively compute a geometric clustering when the cluster sizes are even, resulting in accurate CQ metrics. However, k-means clustering tends to compute clusters of even sizes and thus often fails to compute an accurate geometric clustering when the cluster sizes are uneven, leading to inaccurate CQ metrics.In this paper, we present a new cluster faithfulness metric CQ-HAC, using HAC (Hierarchical Agglomerative Clustering). HAC can compute a more accurate geometric clustering for uneven cluster sizes than k-means clustering. Consequently, CQ-HAC can more accurately measure cluster faithfulness, regardless of whether the sizes of clusters are even or uneven. Moreover, we present two algorithms, Cluster-kmeans and Cluster-HAC, for optimizing cluster faithfulness of graph drawings. Extensive experiments show that in practice, both algorithms always compute perfectly cluster-faithful drawings (i.e., CQ = 1) in our experiments using various graphs with both even and uneven cluster sizes, achieving significant improvement over existing graph layouts, including cluster-focused layouts.

Recent works in graph visualization attempt to reduce the runtime ofrepulsionforce computation of force-directed algorithms using sampling. However, they fail to reduce the runtime forattractionforce computation to sublinear in the number of edges. We present theSubLinearForceframework for a fully sublinear-timeforce computationalgorithm for drawing large complex graphs. More precisely, we present new sublinear-time algorithms for theattraction forcecomputation of force-directed algorithms. We then integrate them with sublinear-time repulsion force computation to give a fully sublinear-time force computation. Extensive experiments show that our algorithms compute layouts on average 80% faster than the existing linear-time force computation algorithm, while obtaining significantly better quality metrics such as edge crossing and shape-based metrics.

In this article, we present new quality metrics for symmetric graph drawing based on group theory. Roughly speaking, the new metrics are faithfulness metrics, i.e., they measure how faithfully a drawing of a graph displays the ground truth (i.e., geometric automorphisms) of the graph as symmetries. More specifically, we introduce two types of automorphism faithfulness metrics for displaying: (1) a single geometric automorphism as a symmetry (axial or rotational), and (2) a group of geometric automorphisms (cyclic or dihedral). We present algorithms to compute the automorphism faithfulness metrics in O(n logn) time. Moreover, we also present efficient algorithms to detect exact symmetries in a graph drawing. We then validate our automorphism faithfulness metrics using deformation experiments. Finally, we use the metrics to evaluate existing graph drawing algorithms to compare how faithfully they display geometric automorphisms of a graph as symmetries.

Shape-based metrics measure how faithfully a drawing D of a large graph G shows the structure of graph, by comparing the similarity between G and a proximity graph S computed from D. Although these metrics can successfully evaluate drawings of large graphs, they are limited to relatively sparse graphs, since existing metrics use planar proximity graphs GG (Gabriel Graph) and RNG (Relative Neighbourhood Graph). This paper presents new shape-based faithfulness metrics for evaluating drawings of large and complex graphs, using high-order prox-imity graphs k-GG and k-RNG. Extensive experiments demonstrate that our new shape-based metrics using degree-based proximity graphs dGG and dRNG can more accurately measure the faithful-ness of drawings of large and complex graphs, with a significant improvement of over 100% better, on average, than the existing shape-based metrics using GG and RNG. Moreover, we present a new shape change faithfulness metric DSC for evaluating drawings of dynamic graphs, by measuring how proportional the geometric shape change in the drawings of dynamic graphs is to the ground truth change in dynamic graphs. Validation using deformation experiments support that DSC can accurately measure shape change faithfulness in dynamic graph drawing. Furthermore, we present extensive comparison experiments of ten popular graph layouts using our new shape-based metrics dGG, dRNG and DSC, to recommend which layouts can give a better shape-faithful graph drawing for large and complex graphs.

Recent works in graph visualization attempt to reduce the runtime of repulsion force computation of force-directed algorithms using sampling, however they fail to reduce the runtime for attraction force computation to sublinear in the number of edges.We present new sublinear-time algorithms for the attraction force computation of force-directed algorithms and integrate them with sublinear-time repulsion force computation.Extensive experiments show that our algorithms, operated as part of a fully sublinear-time force computation framework, compute graph layouts on average 80% faster than existing linear-time force computation algorithm, with surprisingly significantly better quality metrics on edge crossing and shape-based metrics.

We present algorithms reducing the runtime of the stress minimization iteration of stress-based layouts to sublinear in the number of vertices and edges. Specifically, we use vertex sampling to further reduce the number of vertex pairs considered in stress minimization iterations. Moreover, we use spectral sparsification to reduce the number of edges considered in stress minimization computations to sublinear in the number of edges, esp. for dense graphs.Specifically, we present new pivot selection methods using importance-based sampling. Then, we present two variations of sublinear-time stress minimization method on two popular stress-based layouts, Stress Majorization and Stochastic Gradient Descent.Experimental results demonstrate that our sublinear-time algorithms run, on average, about 35% faster than the state-of-art linear-time algorithms, while obtaining similar quality drawings based on stress and shape-based metrics.

In this paper, we present a framework for quality metrics that measure symmetry, that is, how faithfully a drawing of a graph displays the ground truth geometric automorphisms as symmetries. The quality metrics are based on group theory as well as geometry. More specifically, we introduce two types of symmetry quality metrics for displaying: (1) a single geometric automorphism as a symmetry (axial or rotational) and (2) a group of geometric automorphisms (cyclic or dihedral). We also present algorithms to compute the symmetry quality metrics in O(n log n) time. We validate our symmetry quality metrics using deformation experiments. We then use the metrics to evaluate existing graph layouts to compare how faithfully they display geometric automorphisms of a graph as symmetries.

Abstract In this paper, we present a new framework for sublinear time force computation for visualization of big complex graphs. Our algorithm is based on the sampling of vertices for computing repulsion forces and edge sparsification for attraction force computation. More specifically, for vertex sampling, we present three types of sampling algorithms, including random sampling, geometric sampling, and combinatorial sampling, to reduce the repulsion force computation to sublinear in the number of vertices. We utilize a spectral sparsification approach to reduce the number of attraction force computations to sublinear in the number of edges for dense graphs. We also present a smart initialization method based on radial tree drawing of the BFS spanning tree rooted at the center. Experiments show that our new sublinear time force computation algorithms run quite fast, while producing good visualization of large and complex networks, with significant improvements in quality metrics such as shape‐based and edge crossing metrics.

Recent work for visualizing big graphs uses a proxy graph approach: the original graph is replaced by a proxy graph, which is much smaller than the original graph. The challenge for the proxy graph approach is to ensure that the proxy graph is a good representation of the original graph. However, previous work to compute proxy graphs using graph sampling techniques often fails to preserve connectivity and important global skeletal structure in the original graph. This paper introduces two new families of proxy graph methods BCP-W and BCP-E, tightly integrating graph sampling methods with the BC (Block Cut-vertex) tree, which represents the decomposition of a graph into biconnected components. Experimental results using graph sampling quality metrics show that our new BC treebased proxy graph methods produce significantly better results than existing sampling-based proxy graph methods: 25% improvement by BCP-W and 15% by BCP-E on average. We also present DBCP, a BC tree-based proxy graph method for distributed environment. Experiments on the Amazon Cloud EC2 demonstrate that DBCP is scalable for big graph data sets; runtime speed-up of 77% for distributed 5-server on average. Visual comparison using a graph layout method and the proxy quality metrics confirm that our new BC tree-based proxy graph methods are significantly better than existing sampling-based proxy graph method. Our main results lead to guidelines for computing sampling-based proxy graphs for visualization of big graphs.

Data sampling has been extensively studied for large scale graph mining. Many analyses and tasks become more efficient when performed on graph samples of much smaller size. The use of proxy objects is common in software engineering for analysis and interaction with heavy objects or systems. In this paper, we coin the term 'proxy graph' and empirically investigate how well a proxy graph visualization can represent a big graph. Our investigation focuses on proxy graphs obtained by sampling; this is one of the most common proxy approaches. Despite the plethora of data sampling studies, this is the first evaluation of sampling in the context of graph visualization. For an objective evaluation, we propose a new family of quality metrics for visual quality of proxy graphs. Our experiments cover popular sampling techniques. Our experimental results lead to guidelines for using sampling-based proxy graphs in visualization.

Modern-day social networks are often dynamic and multi-relational, however there is currently little being studied on how to incorporate both aspects simultaneously to support visual analytic tasks for such complex social networks. We present a visual analytic framework for dynamic multi-relational networks and a prototype implementation, called the MultiStory system, which includes two new visualisation methods, AlterCluster and InterArc, designed for dynamic networks with multiple relations. The system is evaluated with two case studies using social networks from the MIT Reality Commons to demonstrate the effectiveness of the system to support a variety of visual analytical tasks on dynamic multi-relational networks.