It Pays to Be Lazy: Reusing Force Approximations to Compute Better Graph Layouts Faster Robert Gove Two Six Labs, robert.gove@twosixlabs.com Abstract—N-body simulations are common in applications Logarithmic, uniform, and dynamic. The evaluation compares ranging from physics simulations to computing graph layouts. these schedules to the standard schedule of reconstructing The simulations are slow, but tree-based approximation algo- the tree after every iteration. This paper shows that using a rithms like Barnes-Hut or the Fast Multipole Method dramati- cally improve performance. This paper proposes two new update logarithmic, uniform, or dynamic update schedule achieves schedules, uniform and dynamic, to make this type of approxi- significantly faster performance compared to the standard mation algorithm even faster by updating the approximation less update schedule. In addition, the uniform schedule achieves the often. An evaluation of these new schedules on computing graph same or better graph layout quality as the standard schedule. layouts finds that the schedules typically decrease the running This paper makes the following contributions: (1) A new time by 9% to 18% for Barnes-Hut and 88% to 92% for the Fast Multipole Method. An experiment using 4 layout quality metrics dynamic algorithm for deciding when to reconstruct trees used on 50 graphs shows that the uniform schedule has similar or in tree-based approximations such as Barnes-Hut, the Fast better graph layout quality compared to the standard Barnes- Multipole Method, or the Well-Separated Pair Decomposition; Hut or Fast Multipole Method algorithms. (2) a new schedule for reconstructing trees at uniform fre- quency; (3) a reformulation of the angular resolution (dev) I. I NTRODUCTION readability metric to make it yield a value in [0, 1]; and (4) Spring-electric algorithms are considered to be conceptually an evaluation of the logarithmic, uniform, and dynamic update simple methods for computing graph layouts [1]–[5] and they schedules compared to the standard update schedule showing have enjoyed widespread implementation. However, the brute that the new uniform schedule outperforms the other methods. force algorithm requires O(|V |2 ) time to compute repulsive forces, where |V | is the number of vertices in a graph II. BACKGROUND G = (V, E). Tree-based approximation methods—e.g. Barnes- Hut (BH), the Fast Multipole Method (FMM), and the Well- Spring-electric algorithms belong to the family of force- Separated Pair Decomposition (WSPD)—reduce this running directed graph layout algorithms. Spring-electric algorithms time to O(|V | log |V |). Many spring-electric algorithms em- cast the graph layout problem as an iterative physical simula- ploy these techniques to improve performance [4]–[16], so tion, where the algorithm models the graph’s vertices similarly improving these techniques’ speed can have a wide impact. to charged particles that repel each other, and it models the Reducing the amount of computation can reduce energy con- graph’s edges similarly to springs that define an ideal distance sumption on battery powered devices, reduce interruptions to between vertices. This paper is concerned with improving the analysts’ flow of thought and attention [17], and accelerate the runtime of the repulsive force calculation. visual analytics sensemaking process. The Barnes-Hut (BH) approximation builds a quadtree of These approximation algorithms create tree-based data vertex positions, and then considers distant groups of vertices structures from the vertex positions, and the algorithms then as a single large vertex (see Barnes and Hut [18] and Quigley use the trees to approximate repulsive forces. Because the and Eades [19] for more details). This process of calculating spring-electric algorithm iteratively updates vertex positions, the quadtree runs in O(|V | log |V |) time and reduces the force the approximation methods reconstruct the tree after each calculations to O(|V | log |V |). iteration using the new vertex positions. Tree construction The Fast Multipole Method (FMM), like Barnes-Hut, runs in O(|V | log |V |) time, and therefore can be computa- first builds a spatial tree based on the vertex positions in tionally costly, but it is unknown whether it is necessary to O(|V | log |V |) time, but then it aggregates nodes in the tree in construct a new tree after every iteration. Many spring-electric order to calculate repulsive forces in O(|V |) time [20]–[22]. algorithm implementations include a “cooling” parameter that Recently, Lipp et al [4], [5] proposed using the Well- reduces the change in vertex position over time, indicating Separated Pair Decomposition [23] (WSPD)—another tree- that calculating new trees provides diminishing improvements based approximation algorithm—to compute repulsive forces to accuracy after each iteration of the algorithm. for graph layout algorithms. Both tree construction and repul- This paper presents an evaluation1 of three alternative sched- sive force calculation run in O(|V | log |V |) time. ules for updating tree-based approximations less frequently: For all three of the above tree-based approximation meth- ods, the graph layout algorithm must reconstruct the tree after 1 The materials to reproduce the analysis are available at https://osf.io/re7nx/ each iteration because the vertex positions have changed. 43 It Pays to Be Lazy: Reusing Force Approximations to Compute Better Graph Layouts Faster However, is it necessary to calculate a new tree after every layout algorithm, and the exact amount of change can be iteration? Lipp et al [4], [5] experimented with updating the difficult to predict. For this reason, it may be desirable to WSPD whenever b5 log(i)c changes (where i is the current construct a new tree at uniform intervals. This paper proposes iteration number), instead of after every iteration. They found the following uniform update schedule: let uk be the number that this can decrease the number of edge crossings [5] of trees constructed using the logarithmic schedule for integer compared to the standard update schedule (i.e. reconstructing k. Then, for a layout that has n iterations, construct a new the tree after every iteration), but they did not compare the tree every n/uk iterations. For a given value of k, this results running time of the b5 log(i)c method to the standard method, in the same number of updates for both the logarithmic nor did they test other update schedules such as other multiples and the uniform schedules, and supports direct comparisons of log(i) or a uniform update schedule. They also suggested between them. The difference between the schedules is that, using a dynamic algorithm to determine when to update the for a fixed value of k, the uniform schedule has the same tree [5], but they did not define an algorithm to accomplish this number of iterations between each tree construction, whereas or evaluate this idea. Furthermore, they did not apply this to the the logarithmic schedule constructs more trees at the beginning Barnes-Hut approximation or Fast Multipole Method, so it is of the layout and fewer at the end. not clear if it will work with other tree-based approximations, C. Dynamic Schedule or whether their b5 log(i)c update criteria is optimal. During a force-directed layout, vertex velocity may tem- III. S CHEDULES FOR U PDATING A PPROXIMATIONS porarily decrease as the layout enters a local minimum before There are many different methods to determine when to increasing as the layout escapes the minimum. This, combined update trees used in tree-based approximation methods such with the “cooling” parameter described above, motivates a as the Barnes-Hut (BH) approximation, the Fast Multipole dynamic approach to deciding when to construct a new tree: Method (FMM), or the Well-Separated Pair Decomposition if vertex positions are changing rapidly, then a new tree can (WSPD). The standard versions of these algorithms construct improve accuracy, but if vertex positions are changing slowly, a new tree after every iteration, but the tree could be recon- then constructing a new tree may be computationally costly structed less often. This could be determined by an algorithm with little improvement in accuracy. Therefore we would like that defines some sort of schedule of when to update the to construct a new tree only if the old tree is out of date. approximation by reconstructing the tree. In this paper, a Algorithm 1 shows a dynamic algorithm that performs a schedule is a function that returns a boolean value indicating check to decide whether to construct a new tree or use the old whether or not the tree should be reconstructed. This paper tree to calculate repulsive forces. This check keeps a running explores three alternative schedules to the standard schedule: sum of the velocities (displacement) of all vertices since the logarithmic, uniform, and dynamic. last time a tree was constructed. If this running sum exceeds A. Logarithmic Schedule the previous sum, the new sum is assigned to the previous sum, the running sum is reset to 0, and a new tree is calculated Many spring-electric algorithm implementations include a before computing repulsive forces; otherwise, the algorithm “cooling” parameter that reduces the change in vertex position decides the old tree is accurate enough and uses it to compute over time, indicating that constructing new trees may provide forces on the vertices. In practice, this algorithm constructs diminishing improvements to accuracy after each iteration of new a tree about 10–15 times out of 300 iterations. the algorithm. In addition, most vertices tend to converge to a final position. This motivates a schedule that constructs a new Algorithm 1 Dynamic schedule. Initially, currSum = tree with decreasing frequency at later iterations of the force- prevSum = 0. uvx and uvy are u’s x, y velocities directed layout. Lipp et al. [4], [5] proposed a logarithmic for each vertex u do schedule where a new tree is constructed if b5 log(i)c changes, currSum ← currSum + |uvx | + |uvy | where i is the current iteration number. However, they did not if tree is null or currSum ≥ prevSum then experiment with using scalars other than 5, and they did not prevSum ← currSum specify the logarithmic base. Note that any two logarithmic currSum ← 0 functions with different bases differ by only a constant (i.e. tree ← newTree() logb (x) = loga (x)/ loga (b)), so it suffices to use a base 10 computeForces() logarithm and vary the scalar multiple. For this reason, this paper explores the family of schedules defined by bk log(i)c where k is an integer in [1, 10]. For 300 iterations of a graph This dynamic algorithm has the benefit of generalizing to layout algorithm, this corresponds to constructing a new tree any approximation method or type of tree used. For exam- 7, 13, 18, 22, 26, 31, 34, 38, 42, or 45 times for k ranging ple, an alternative dynamic algorithm might operate on the from 1 to 10. quadtrees in the Barnes-Hut approximation and check the number of vertices that are no longer in their original quadtree B. Uniform Schedule cells. However, such a dynamic algorithm would be restricted Even though vertex velocity tends to decrease over time, to approximation methods that depend on quadtrees, such as velocity does change at every iteration of a force-directed the Barnes-Hut approximation, and it would not generalize to 44 It Pays to Be Lazy: Reusing Force Approximations to Compute Better Graph Layouts Faster other tree-based approximation methods. Another downside to shuffles the vertex array before calculating initial positions and this alternative approach is that if only a few vertices moved running the spring-electric layout algorithm. This is done 20 out of their cells, but they moved a large distance, this may times for each graph for each pair of update schedule and not exceed the threshold to construct a new quadtree. On the approximation method (4 × 2 = 8 schedule-approximation other hand, the dynamic method in Algorithm 1 can determine pairs). The experiment then records the median runtime and that a new tree should be constructed in this case where only median readability metrics for each graph and algorithm a few vertices have moved but they moved a large distance. combination (this experiment uses the median instead of the Early experiments with this algorithm tested small coeffi- arithmetic mean to avoid the results being skewed by outliers). cients for updating currSum such as This evaluation uses the edge crossing, edge crossing angle, angular resolution (min), and angular resolution (dev) graph currSum ← c ∗ currSum + |uvx | + |uvy | layout readability metrics implemented in greadability.js3 , for c = 1.01 or c = 0.99. However, even such small which are defined below. Other readability metrics exist, coefficients resulted in constructing a new tree way more often such as stress or standard deviation of edge length, but this than necessary (as in 1.01) or not enough to be useful (as in evaluation avoids these readability metrics because they have 0.99). Therefore the algorithm uses a coefficient of 1, which known issues [10], [26], [27]. Namely, non-uniform edge seems to yield good results. lengths are often necessary to achieve good layouts for real- world graphs [27], [28]; preserving shortest-path distances, IV. E XPLORATORY A NALYSIS as measured by stress, may not be ideal for producing good In order to develop hypotheses to test, this section presents layouts [27]; stress is not defined on graphs with more than an exploratory analysis of the update schedules. All data one component, which often occur in real-world data; and collection and analysis was conducted in NodeJS version 9.4.0 two layouts that convey a graph’s structure equally can have on a 2015-model MacBook Pro with a 3.1 GHz Intel Core i7 different stress values [26]. In addition, stress and standard processor and 16 GB of RAM. deviation of edge length do not have normalized versions that This exploratory analysis uses 50 graphs with 1000 vertices support accurate comparisons between different graphs. or fewer randomly selected from the KONECT [24] and Edge crossings, denoted ℵc , measures the number of edges SuiteSparse [25] graph collections. that cross, or intersect, in the layout. The metric scales the This evaluation uses the D3.js framework [9] to compare number of edge crossings, c, by an approximate upper bound the four update schedules (logarithmic, uniform, dynamic, and so that ℵc ∈ [0, 1]. standard). The evaluation uses D3.js’s default settings, and . |E|(|E| − 1) 1 X  adds a central gravitational force with a strength of 0.001. ℵc = 1 − c − deg(u)(deg(u) − 1) 2 2 The experiment uses D3.js’s default stopping criteria, which u∈V is when the “cooling” parameter becomes sufficiently small; If the denominator is 0, then ℵc = 1. by default, this occurs after 300 iterations. Edge crossing angle, denoted ℵca , measures the average D3’s default force-directed algorithm uses the Barnes-Hut deviation of each edge’s crossing angle from the ideal angle (BH) approximation, which has been modified for this eval- ϑ of 70 degrees. uation to support the new update schedules. This evaluation P P also uses a second algorithm, which is a modified version e0 ∈c(e) |ϑ − θe,e | 0 e∈E ℵca = 1 − of D3’s force-directed algorithm but uses a publicly available cϑ implementation of the Fast Multiple Method2 (FMM). This where c(e) is the set of edges that intersect e, and θe,e0 is second force-directed algorithm also supports all four update the acute angle of the two intersecting edges. If cϑ = 0, then schedules. Although other tree-based approximation methods ℵc = 1. are available, they are implemented in other programming Angular resolution (min) is the average deviation of incident languages, and therefore cannot be directly compared to the edge angles from the ideal minimum angle for each vertex u. JavaScript implementations. For this reason, this analysis only uses the aforementioned JavaScript versions of the BH and 1 X |ϑu − θumin | ℵrm = 1 − FMM approximations in order to minimize threats to validity. |V | ϑu u∈V This evaluation uses 10 versions each of the logarithmic and uniform update schedules parameterized with k from 1 to 10 Here, ϑu = 360/d(u), the degrees between each incident edge as described in Section III-A and Section III-B. if the angles were uniform, and θumin is the smallest measured D3.js initializes vertices in a disc-like phyllotaxis arrange- angle between edges incident on u. ment, where vertices at the beginning of the vertex array are Angular resolution (dev) is the average deviation of angles at the center and vertices at the end of the vertex array are at between incident edges on each vertex u. This paper presents the periphery. To minimize any possible effects of the initial a new formulation of the angular resolution (dev) metric positions on the experiment results, this experiment randomly described by Dunne et al [29]. Dunne et al’s metric can 2 https://github.com/davidson16807/fast-multipole-method 3 https://github.com/rpgove/greadability 45 It Pays to Be Lazy: Reusing Force Approximations to Compute Better Graph Layouts Faster produce negative numbers, but the version presented here Although the runtime is not as short as k = 1, the layout produces a value in [0, 1]. quality appears substantially better for the majority of update  schedules and approximation algorithms. Higher values of k 1 X 1 X |ϑu − θi,(i+1) |  d(u) ℵrd = 1 − do not appear to provide much improvement in layout quality, |V | u∈V, d(u)>1 2d(u) − 2 i ϑu and in fact large values of k sometimes produce lower quality layouts (e.g. for number of crossings when k = 9 or 10). Here, θi,(i+1) is the acute angle between adjacent edges i and For both the BH and FMM algorithms, the dynamic sched- i + 1 that are incident on vertex u, modulo d(u), the degree ule appears to have faster runtime than the logarithmic and of u. To see that ℵrd ∈ [0, 1], consider that the maximum uniform schedules for k > 2. Therefore, Hypothesis 2 is that deviation on a vertex u will occur when θi,(i+1) ≈ 0 for the dynamic schedule will decrease the BH and FMM runtime all incident edges except one where θi,(i+1) ≈ 360. For the more than the logarithmic or uniform schedules if k = 4. central vertex in a star graph with |V | vertices, the sum of the For BH, the dynamic schedule appears to generally have deviations of its incident edges would be worse readability metric performance than the standard sched- d(u) X |ϑu − θi,(i+1) | d(u) X |360/d(u) − θi,(i+1) | ule. Hypothesis 3 is that the dynamic schedule will perform = worse on all readability metrics than the standard schedule, i ϑu i 360/d(u) except for edge crossings where the dynamic schedule will Since θi,(i+1) ≈ 0 for all but one pair of incident edges, we perform about the same. then have On the other hand, for BH with the logarithmic and uniform d(u) schedules where k = 4, these schedules tend to have better X |360/d(u) − θi,(i+1) | |360/d(u) − 360| readability metrics. Hypothesis 4 is that, for BH, the logarith- ≈ (d(u) − 1) + i 360/d(u) 360/d(u) mic and uniform schedules will have better readability metrics compared to the standard schedule, except for crossing angle = (d(u) − 1) + (d(u) − 1) where logarithmic and uniform will perform worse. = 2d(u) − 2 For FMM, we see similar, but somewhat different, relation- This is the upper bound for the deviation of a vertex u, so ships in the readability metrics. By looking at the data, we we must divide the deviation of each vertex by this quantity. believe that all other schedules perform better than the standard In contrast, the smallest value would occur in a graph where schedule on the edge crossings and angular resolution (min) every pair of incident edges had the ideal angle, which would metrics (Hypothesis 5), all schedules perform worse than the make the deviation 0. Therefore, ℵrd is in the range [0, 1]. standard schedule on the crossing angle metric (Hypothesis See Dunne et al [29] for a more detailed discussion of these 6), and that the dynamic schedule will perform worse and the and other readability metrics. logarithmic and uniform schedules will perform better than the standard schedule on the angular resolution (dev) metric A. Hypothesis Generation (Hypothesis 7). Figure 1 shows the median runtime and readability metrics across all 50 graphs in the exploratory dataset. The runtime and V. E XPERIMENTAL C OMPARISON readability metrics were calculated for the Barnes-Hut (BH) This analysis tests the hypotheses developed in the ex- and Fast Multipole Method (FMM) approximation algorithms ploratory analysis (Section IV) on a new set of 50 graphs. using each update schedule (standard, dynamic, logarithmic These graphs are different from the graphs used in Section IV, for k from 1 to 10, and uniform for k from 1 to 10). This but they were collected using the same process. gives us some insight into how each approximation algorithm Following existing best practices [30], [31], this evaluation’s performs for the different update schedules, allowing us to experimental design is as follows. It uses a within-subjects develop hypotheses to formally test. design on the three schedules (dynamic, logarithmic with In the exploratory data, the standard BH and FMM methods k = 4, and uniform with k = 4), two approximation are slower than all of the dynamic, log, and uniform update algorithms (BH and FMM), and four layout readability metrics schedules. The dynamic algorithm had about the same number discussed in Section IV. The first quartile, median, and third of updates as k = 2 (median is 11 and 14 for BH and FMM quartile for the dynamic schedule’s number of updates on the respectively), and they also have about the same runtime. This Barnes-Hut algorithm was 11, 12, and 13, and for the Fast leads to Hypothesis 1: Using a dynamic or fixed update sched- Multipole Method algorithm it was 12, 14, and 15. Because ule (e.g. logarithmic or uniform) is faster than the standard this is comparing three alternative schedules to the standard update schedule for both the BH and FMM algorithms. schedule across five response variables (runtime and the four In order to test Hypothesis 1 experimentally, we must readability metrics), the evaluation uses a Bonferroni corrected choose a value of k to use for the logarithmic and uniform significance level α = 0.05/15 = 0.003. The corresponding update schedules. Ideally, k will be small in order to minimize confidence interval is [0.0016, 0.9983]. the runtime, but k should also be large enough to produce Because the readability metrics are bounded in [0, 1], and good quality layouts. For these reasons, let us choose k = 4 many are not normally distributed, this evaluation uses boot- (i.e. constructing a new tree 22 times out of 300 iterations). strapped confidence intervals with 10,000 samples. Effect sizes 46 It Pays to Be Lazy: Reusing Force Approximations to Compute Better Graph Layouts Faster Barnes-Hut Logarithmic k=10 k=9 Runtime (seconds) Runtime (seconds) Runtime (seconds) Runtime (seconds) 0.5 0.5 0.5 0.5 k=8 k=7 k=6 k=5 k=4 0.4 0.4 0.4 0.4 k=3 k=2 k=1 0.955 0.960 0.965 0.62 0.64 0.66 0.68 0.70 0.36 0.38 0.40 0.60 0.62 0.64 0.66 Uniform Edge crossings Crossing angle Angular resolution (min) Angular resolution (dev) k=10 k=9 Fast Multipole Method k=8 k=7 k=6 10 10 10 10 k=5 Runtime (seconds) Runtime (seconds) Runtime (seconds) Runtime (seconds) k=4 k=3 k=2 k=1 5 5 5 5 standard dynamic 0.955 0.960 0.965 0.62 0.64 0.66 0.68 0.70 0.36 0.38 0.40 0.60 0.62 0.64 0.66 Edge crossings Crossing angle Angular resolution (min) Angular resolution (dev) Fig. 1. Median runtime and readability metrics across all 50 exploratory graphs calculated for each update schedule (logarithmic for k from 1 to 10, uniform for k from 1 to 10, the standard schedule, and the dynamic schedule) and approximation algorithm (Barnes-Hut and Fast Multipole Method). Barnes-Hut Runtime Edge crossings Crossing angle Angular res. (min) Angular res. (dev) Log Log Log Log Log Uniform Uniform Uniform Uniform Uniform Dynamic Dynamic Dynamic Dynamic Dynamic -0.1 0.0 -0.02 0.00 0.02 -0.10 -0.05 0.00 -0.02 0.00 0.02 -0.02 0.00 0.02 Runtime Edge crossings Crossing angle Angular res. (min) Angular res. (dev) FMM Log Log Log Log Log Uniform Uniform Uniform Uniform Uniform Dynamic Dynamic Dynamic Dynamic Dynamic -10 0 -0.02 0.00 0.02 -0.10 -0.05 0.00 -0.02 0.00 0.02 -0.02 0.00 0.02 Fig. 2. Bootstrap 99.6% confidence interval of the effect sizes of the runtime and graph readability metrics. Confidence intervals are percentile bootstrap with 10,000 samples. Effect size is sample mean difference (log, uniform, or dynamic minus standard). Note the differences in x-axis scales. are sample mean difference (salt − sstandard where salt is 3. Compared to the standard schedule on BH, the dynamic the value for one of the alternate schedules, i.e. logarithmic, schedule is better on edge crossings than the standard schedule uniform, or dynamic). Therefore negative effects indicate the (the effect is positive and the confidence interval does not cross standard schedule has a higher value, whereas positive effects 0), but the dynamic schedule is worse on crossing angle. For indicate the alternate schedule under test has a higher value. both angular resolution metrics the confidence interval crosses Figure 2 shows the estimation plots for the runtime and zero, and therefore there is no evidence to say that the dynamic readability metrics for the two approximation algorithms. schedule performs better or worse than the standard schedule. None of the confidence intervals in the runtime plots cross Similarly, we have good evidence to support parts of 0. This indicates that all of the tested update schedules perform Hypothesis 4. For BH, both the logarithmic and uniform faster than the standard update schedule for both the Barnes- schedules perform better than the standard schedule on edge Hut (BH) and Fast Multipole Method (FMM) approximation crossings and the angular resolution metrics. On the crossing algorithms, which supports Hypothesis 1. angle metric, the logarithmic schedule performs worse than Although this experiment does not explicitly test Hypoth- the standard schedule, but the confidence interval for the esis 2 using a null hypothesis significance test, the dynamic uniform schedule crosses 0, so we are unable to say whether schedule has a much larger effect size on runtime than the its performance is better or worse than the standard schedule. logarithmic or uniform schedules for BH. The raw effect size We partly accept Hypothesis 6. Although none of the FMM is -0.101 seconds, compared to -0.065 seconds for uniform, confidence intervals for edge crossings cross 0, they all cross 0 and -0.049 seconds for logarithmic. This supports, but does for the angular resolution (min) metric. Therefore we conclude not prove, Hypothesis 2. that all of the schedules perform better on edge crossings We have good evidence to support parts of Hypothesis than the standard schedule, but we cannot say whether there 47 It Pays to Be Lazy: Reusing Force Approximations to Compute Better Graph Layouts Faster Median runtime on each graph (BH) Barnes-Hut Fast Multipole Method Time (seconds) 90% 1.3 90% Runtime (percent decrease) Runtime (percent decrease) 80% 80% 1.2 70% 70% 1.1 60% 60% 1.0 50% 50% 0.9 40% 40% 0.8 30% 30% 0.7 20% 20% 0.6 10% 10% 0.5 0% Number of vertices (log base 10) 0% Number of vertices (log base 10) Standard 1e+1 1e+2 1e+3 1e+4 1e+5 1e+1 1e+2 1e+3 1e+4 1e+5 0.4 Logarithmic 0.3 Uniform Fig. 4. Percent decrease in runtime from the standard schedule for the 0.2 Dynamic logarithmic (red), uniform (blue), and dynamic (gray) update schedules. The percent decrease is calculated for each of the sparse graphs, which have 10, 0.1 100, 1,000, 10,000, and 100,000 vertices. Note the log scale on the x-axis. 0.0 Number of vertices 0 100 200 300 400 500 600 700 800 900 1,000 Median runtime on each graph (FMM) to better understand the runtime decrease seen in practice and Time (seconds) 30 28 to better understand the influence of graph size. 26 Figure 3 shows the runtime of each schedule with each 24 approximation algorithm on each of the 50 graphs used in 22 the experimental analysis in Section V. 20 For Barnes-Hut (BH), the dynamic algorithm has the largest 18 decrease in runtime compared to the standard schedule (the 16 smallest percent decrease is 10%, the largest is 52%, and the 14 median is 18%). (Percent decrease is the difference between 12 the schedule’s runtime and the standard schedule’s runtime, 10 divided by the standard schedule’s runtime.) The uniform schedule did better than the logarithmic schedule in the worst 8 6 and typical cases (the smallest and median percent decrease 4 was 8% and 14% for the uniform schedule and 5% and 9% for 2 0 Number of vertices the logarithmic schedule), but in the best case the logarithmic 0 100 200 300 400 500 600 700 800 900 1,000 schedule slightly outperformed the uniform schedule (29% compared to 27%). Fig. 3. Median runtime on each of the 50 graphs in the experimental data set. Dots represent the standard schedule (black), the logarithmic schedule For the Fast Multipole Method (FMM), the percent decrease (red), the uniform schedule (blue), and the dynamic schedule (gray). The top in runtime is substantially larger, but very similar for each up- graph is for the Barnes-Hut algorithm, and the bottom is for Fast Multipole date schedule (bottom of Figure 3). The logarithmic schedule Method. Horizontal jitter resolves occlusion for graphs with identical numbers of vertices. ranged from 88% to 90% (median 89%), the uniform schedule ranged from 87% to 90% (median 89%), and the dynamic schedule ranged from 89% to 94% (median 92%). is any difference from the standard schedule for the angular In order to examine the performance of each schedule resolution (min) metric. as |V | increases, Figure 4 shows the percent decrease of Although Hypothesis 6 is that all of the schedules perform each schedule compared to the standard schedule on five worse than the standard schedule on crossing angle, the evi- sparse graphs of varying size. The five sparse graphs have dence only shows that the dynamic schedule performs worse. 10, 100, 1,000, 10,000, and 100,000 vertices, and the graphs We do not have enough evidence to say that the logarithmic were generated with |E| = 2|V | random edges (without or uniform schedules perform worse. replacement). Keeping the proportion of edges fixed allows us Finally, we do not find evidence to support Hypothesis 7; to more easily understand the change in runtime performance all of the confidence intervals for the angular resolution (dev) for repulsive force calculation as graphs get larger. cross 0, so the logarithmic, uniform, and dynamic schedules For BH, the uniform and dynamic schedules have the largest do not appear to have significantly different performance from percent decrease for small graphs, but the overall runtime is the standard schedule. small so this translates into a savings of about 26 and 37 milliseconds for graphs with 10 and 100 vertices respectively VI. E FFECT OF G RAPH S IZE ON RUNTIME when using the uniform update schedule. For larger graphs, the The analysis in Section V showed that the logarithmic, uniform schedule appears to offer the largest percent decrease; uniform, and dynamic schedules have a decrease in runtime for the largest graph, the percent decrease is about 18%, which over the standard schedule. This section explores this further saves about 86 seconds (reduced from about 490 seconds to 48 It Pays to Be Lazy: Reusing Force Approximations to Compute Better Graph Layouts Faster 8k jazz 1.0M dwg961b 10k robot to mirror the convergence charts, and this indicates that the 9k 7k 0.8M 8k dynamic schedule constructs new trees less often as the layout 6k Standard converges. By the time the layout has converged, the dynamic Stress Stress Stress 0.6M 7k Logarithmic 5k Uniform 6k algorithm typically has stopped constructing new trees. Dynamic 0.4M 4k 5k 0.2M 4k VIII. G RAPH L AYOUT E XAMPLES 3k Figure 6 shows the layouts for three graphs generated by Runtime (seconds) Runtime (seconds) Runtime (seconds) 3k 0.0 0.1 0.2 0.0 0.5 1.0 0.0 0.1 0.2 the Barnes-Hut (BH) and Fast Multipole Method (FMM) algo- Number of updates Number of updates Number of updates jazz dwg961b robot 12 12 12 10 8 10 8 10 8 rithms using the standard, dynamic, logarithmic, and uniform 6 4 6 4 6 4 update schedules. These are the same graphs used to test 2 2 2 0 0 Number of iterations 100 200 300 0 0 Number of iterations 100 200 300 0 0 Number of iterations 100 200 300 convergence in Section VII. For the most part, the layouts produced by the standard schedule are extremely similar to the Fig. 5. (TOP) Convergence rate of the stress metric for the four update layouts produced by the other schedules. Notably, the dynamic schedules on the Barnes-Hut approximation. (BOTTOM) The average number FMM layout for the jazz and robot graphs appears to put some of updates of the dynamic schedule at each iteration. vertices too close together while putting other vertices too far apart. The layouts for dwg961b all appear very similar and about 404 seconds). For comparison, on the largest graph the seem to show the same structure and shape. The dynamic BH dynamic schedule had a percent decrease of about 16%, or and some of the FMM layouts also appear to hide the curvature about 79 seconds. of the robot layout (due to the central gravitational force in For FMM, the percent decrease is large and consistent the layout algorithm). These results corroborate the findings in regardless of graph size and update schedule, ranging from Section V that the logarithmic and uniform schedules produce about 88% to about 93%. In contrast to BH, the dynamic layouts with similar quality as the standard schedule. It also schedule has a larger percent decrease, whereas the uniform indicates that the final stress values shown in Figure 5 may and logarithmic schedules are about the same. not indicate worse layout quality. For BH, the dynamic schedule updated 11 times on the IX. D ISCUSSION smallest graph and either 8 or 9 times on all other graphs, while for FMM the dynamic schedule updated 18 times on the The analysis in this paper shows that the time required to smallest graph and 12 times on all other graphs. This indicates calculate new trees is a nontrivial part of the overall runtime that the size of the graph does not seem to affect the number of spring-electric algorithms that use the Barnes-Hut (BH) of updates. approximation and the Fast Multipole Method (FMM). By reducing the number of times the algorithm computes a new VII. C ONVERGENCE tree, we can reduce the time required to compute layouts. Although using stress as a graph layout quality metric can Note that these experiments report the reduction in the total have problems (see the discussion in Section IV), it is widely running time of graph layout algorithms rather than only the used and regarded as an important metric. We are also inter- reduction in repulsive force calculation running time. The ested in understanding whether the logarithmic, uniform, and graph layout algorithms also include calculations for spring dynamic schedules affect the convergence rate of the layout forces and a central gravitational force, so the reduction in algorithm. Therefore, this section presents an analysis of stress repulsive (electric) force calculation running time is likely for each update schedule over 300 iterations on three graphs. much larger than the results reported here. These graphs were chosen from the 50 experimental graphs. Overall, the dynamic schedule appears to be the fastest, The stress and layout time are averaged after each iteration although in some cases the runtime improvement may not be across 10 runs of each update schedule. The results are shown much more than the logarithmic and uniform schedules. The in Figure 5. (Due to space constraints, only the Barnes-Hut dynamic schedule’s improvement in runtime appears to come convergence rates are shown.) Sometimes all of the schedules at the cost of lower quality graph layouts. The runtime of the converge to similar values (the jazz graph), sometimes the logarithmic and uniform schedules appear similar, although alternative schedules converge faster and to lower values than perhaps uniform is slightly faster. Furthermore, the uniform the standard schedule (the dwg961b graph), and sometimes the schedule does not appear to have the diminished graph layout standard schedule converges to lower values (the robot graph). quality that we sometimes see in the logarithmic schedule, In most cases, the alternative schedules converge less smoothly and in many cases it performs better on readability metrics than the standard schedule, which is probably because the tree than the standard schedule. Therefore, practitioners and system oscillates between being up to date and out of date. However, implementers would be best choosing either the uniform the logarithmic and uniform schedules have converged by the schedule with k = 4 (i.e. construct a new tree approximately time the standard schedule has. once every 13 or 14 iterations) or the dynamic schedule, The bottom of Figure 5 shows the average number of depending on their preference for trading off speed and quality. updates of the dynamic schedule at each iteration. We see that These schedules provide modest runtime improvements for most updates occur during the early iterations. This appears BH, but quite substantial runtime improvements for FMM. 49 It Pays to Be Lazy: Reusing Force Approximations to Compute Better Graph Layouts Faster The fact that the uniform schedule is less precise than jazz dwg961b robot |V| = 198 |V| = 961 |V| = 240 the standard schedule but produces better quality layouts |E| = 2742 |E| = 1860 |E| = 870 seems counter intuitive. However, this is consistent with the preliminary results presented by Lipp et al. [5]. The reason why the logarithmic, uniform, and dynamic Standard BH schedules improve the FMM runtime so much is likely because building the tree for the FMM is O(|V | log |V |), but computing forces is only O(|V |). Therefore, constructing a new tree is the largest computational cost, and reducing the number of trees constructed has a major impact on the runtime. It is not clear why the FMM implementation used in this Logarithmic BH evaluation is so much slower than the BH implementation. The implementations were created by different people, so it is likely that the performance difference is due to differing levels of effort to optimize the implementations. Nonetheless, we still get a clear idea of how much runtime can be reduced by using the alternative update schedules. Uniform BH It is worth noting that the observed layout quality effect sizes in the experimental analysis may be considered small in practice. For example, an effect size of -0.011 on crossing angle corresponds to a difference of 0.77 degrees in mean deviation from the ideal crossing angle. And an effect size of 0.004 on edge crossings means that if a graph has 1000 edges that can cross, then there will be 4 fewer edge crossings. It Dynamic BH is unclear if humans would notice such small differences in practice, or if such small differences would have a detectable effect on speed or errors in analysis tasks. X. C ONCLUSION This paper presented two new update schedules (uniform Standard FMM and dynamic) for determining when to construct a new tree in tree-based approximation algorithms such as Barnes-Hut, the Fast Multipole Method, or the Well-Separated Pair Decompo- sition. The evaluations show that constructing a new tree at a uniform frequency of once every 13–14 iterations achieves sig- nificantly faster performance compared to the standard update Logarithmic FMM schedule. In addition, the uniform schedule achieves better edge crossing and angular resolution graph readability metrics, and it does not appear to come at the cost of a degradation in edge crossing angle that occurs with the dynamic and logarithmic update schedules. The uniform update schedule also appears to improve the angular resolution metrics for the Barnes-Hut approximation, but not with the Fast Multipole Uniform FMM Method. These new update schedules are simple modifications to the existing approximation algorithms, and therefore they present an easy but effective way to improve the runtime. Because spring-electric algorithms have many uses, such as in multi-level graph layout algorithms [14] and flow dia- grams [32], the logarithmic, uniform, and dynamic schedules Dynamic FMM can be used to improve runtime in many applications. This includes domains such as n-body simulations or the t-SNE algorithm [33]. Future work should evaluate these other uses. ACKNOWLEDGEMENT Thanks to Nathan Danneman, Ben Gelman, Jessica Moore, Fig. 6. Layouts of three graphs produced by the Barnes-Hut (BH) and Fast Multipole Method (FMM) algorithms using the four update schedules. Tony Wong, and the anonymous reviewers for providing helpful feedback on this work. 50 It Pays to Be Lazy: Reusing Force Approximations to Compute Better Graph Layouts Faster R EFERENCES [27] J. F. Kruiger, P. E. Rauber, R. M. Martins, A. Kerren, S. Kobourov, and A. C. Telea, “Graph Layouts by t-SNE,” Computer Graphics Forum, vol. 36, no. 3, pp. 283–294, 2017. [1] A. Arleo, W. Didimo, G. Liotta, and F. Montecchiani, “A Million Edge [28] E. R. Gansner, Y. Koren, and S. C. North, “Graph drawing by stress Drawing for a Fistful of Dollars,” in International Symposium on Graph majorization,” in International Symposium on Graph Drawing, 2004, Drawing and Network Visualization, 2015, pp. 44–51. pp. 239–250. [2] T. M. Fruchterman and E. M. Reingold, “Graph drawing by forcedirected [29] C. Dunne, S. I. Ross, B. Shneiderman, and M. Martino, “Readability placement,” Software: Practice and Experience, vol. 21, no. 11, pp. metric feedback for aiding node-link visualization designers,” IBM 1129–1164, 1991. Journal of Research and Development, vol. 59, no. 2/3, pp. 14:1–14:16, [3] S. G. Kobourov, “Force-Directed Drawing Algorithms,” in Handbook 2015. of Graph Drawing and Visualization, 1st ed., R. Tamassia, Ed. Boca [30] P. Dragicevic, “Fair statistical communication in hci,” in Modern Sta- Raton: Chapman and Hall/CRC, 2016, ch. 12, pp. 383–408. tistical Methods for HCI, J. Robertson and M. Kaptein, Eds. Springer, [4] F. Lipp, A. Wolff, and J. Zink, “Faster force-directed graph drawing with 2016, ch. 13, pp. 291–330. the well-separated pair decomposition,” in International Symposium on [31] C. Rainey, “Faster Force-Directed Graph Drawing with the Well- Graph Drawing and Network Visualization, 2015, pp. 52–59. Separated Pair Decomposition,” Journal of Political Science, vol. 58, [5] ——, “Faster Force-Directed Graph Drawing with the Well-Separated no. 4, pp. 1083–1091, 2014. Pair Decomposition,” Algorithms, vol. 9, no. 3, p. 53, 2016. [32] K. Wongsuphasawat and D. Gotz, “Exploring flow, factors, and out- [6] M. Bastian, S. Heymann, and M. Jacomy, “Gephi: An Open Source comes of temporal event sequences with the outflow visualization,” IEEE Software for Exploring and Manipulating Networks,” in International Transactions on Visualization and Computer Graphics, vol. 18, no. 12, AAAI Conference on Weblogs and Social Media, 2009, pp. 361–362. pp. 2659–2668, 2012. [7] N. G. Belmonte, “JavaScript InfoVis Toolkit.” [Online]. Available: [33] L. van der Maaten, “Accelerating t-sne using tree-based algorithms,” The http://philogb.github.io/jit/ Journal of Machine Learning Research, vol. 15, no. 1, pp. 3221–3245, [8] M. Bostock and J. Heer, “Protovis: A graphical toolkit for visualization,” 2014. IEEE Transactions on Visualization and Computer Graphics, vol. 15, no. 6, pp. 1121–1128, 2009. [9] M. Bostock, V. Ogievetsky, and J. Heer, “Data-Driven Documents,” IEEE Transactions on Visualization and Computer Graphics, vol. 17, no. 12, pp. 2301–2309, 2011. [10] E. R. Gansner and S. C. North, “An open graph visualization system and its applications to software engineering,” Software Practice and Experience, vol. 30, no. 11, pp. 1203–1233, 1999. [11] S. Hachul and M. Jünger, “Large-Graph Layout Algorithms at Work: An Experimental Study,” Journal of Graph Algorithms and Applications JGAA, vol. 11, no. 2, pp. 345–369, 2007. [12] J. Heer, S. K. Card, and J. A. Landay, “Prefuse: a toolkit for interactive information visualization,” in Proceedings of the SIGCHI Conference on Human Factors in Computing Systems, 2005, pp. 421–430. [13] J. Heer, “Flare: Data Visualization for the Web,” 2008. [14] Y. Hu, “Efficient, High-Quality Force-Directed Graph Drawing,” Math- ematica Journal, vol. 10, no. 1, pp. 37–71, 2005. [15] M. Jacomy, T. Venturini, S. Heymann, and M. Bastian, “ForceAtlas2, a continuous graph layout algorithm for handy network visualization designed for the Gephi software,” PloS one, vol. 9, no. 6, 2014. [16] M. Khoury, Y. Hu, S. Krishnan, and C. Scheidegger, “Drawing Large Graphs by Low-Rank Stress Majorization,” Computer Graphics Forum, vol. 31, no. 3pt1, pp. 975–984, 2012. [17] J. Nielsen, Usability Engineering, 1st ed. Academic Press, 1993. [18] J. Barnes and P. Hut, “A hierarchical O(N logN) force calculation algorithm,” Nature, vol. 324, pp. 446–449, 1986. [19] A. Quigley and P. Eades, “FADE: Graph drawing, clustering, and visual abstraction,” in International Symposium on Graph Drawing, 2000, pp. 197–210. [20] S. Aluru, J. Gustafson, G. Prabhu, and F. E. Sevilgen, “Distribution- independent hierarchical algorithms for the n-body problem,” The Jour- nal of Supercomuting, vol. 12, no. 4, pp. 303–323, 1998. [21] L. F. Greengard, “The rapid evaluation of potential fields in particle systems,” Ph.D. dissertation, Yale University, New Haven, CT, USA, 1987. [22] S. Hachul and M. Jünger, “Drawing large graphs with a potential- field-based multilevel algorithm,” in International Symposium on Graph Drawing, 2004, pp. 285–295. [23] P. B. Callahan and S. R. Kosaraju, “A decomposition of multidimen- sional point sets with applications to k-nearest-neighbors and n-body potential fields,” Journal of the ACM, vol. 42, no. 1, pp. 67–90, 1995. [24] J. Kunegis, “KONECT - The Koblenz Network Collection,” in Web Observatory Workshop, 2013, pp. 1343–1350. [25] T. Davis and Y. Hu, “The University of Florida Sparse Matrix Collec- tion,” ACM Transactions on Mathematical Software, vol. 38, no. 1, pp. 1:1–1:25, 2011. [26] P. Eades, S.-H. Hong, A. Nguyen, and K. Klein, “Shape-Based Quality Metrics for Large Graph Visualization,” Journal of Graph Algorithms and Applications, vol. 21, no. 1, pp. 29–53, 2017. [Online]. Available: http://jgaa.info/getPaper?id=405 51