SNAP-tFDP: Massively Scalable Graph Layouts via Sparse Negative Sampling

Xin Chen¹     Shuowei Hou¹     Yifan Wang²     Mingliang Xue³     Zezheng Feng⁴     Oliver Deussen⁵     Weidong Huang⁶     Yunhai Wang¹

¹Renmin University of China     ²Shandong University     ³Shandong Provincial Institute of Educational Sciences
⁴Northeastern University     ⁵University of Konstanz     ⁶University of Technology Sydney

Accepted by VIS 2026

Figure 1: Iterative layouts of communities with more than 800 users in the Orkut online social network [44] (a graph with 259,019 nodes and 6,893,156 edges) generated using our negative sampling-based graph layout algorithm using t-forces [47], which runs in O(|E|) time. Node colors indicate community membership. The initial node positions are obtained using Pivot MDS (PMDS) [5] (a), followed by layouts after 1 (b), 5 (c), and 30 (d) epochs of the algorithm. The entire layout process required 5.69 seconds with 16 CPU threads (120 MByte RAM), whereas DRgraph [49] required 55.64 seconds on the same settings.

Abstract:

Force-Directed Placement (FDP) is a widely used approach for network visualization, yet scaling it to massive graphs while preserving clear community structures remains a major computational and visual challenge. Existing approximation methods often rely on auxiliary data structures (e.g., spatial trees), which introduce substantial memory overhead; furthermore, traditional power-function-based forces frequently fail to separate dense clusters effectively. In this paper, we present a negative sampling-based algorithm that achieves O(|E|) time complexity with a low memory footprint, without requiring complex multi-level representations. In a first step, we introduce a linearly normalized degree-weighting scheme, which, combined with short-range bounded t-distribution forces, effectively untangles dense structures and enhances visual cluster separation. To optimize for this formulation efficiently, we introduce an edge-centric negative sampling strategy that naturally reconstructs the global degree-weighted objective. Furthermore, we design a lock-free, bundle-based parallelization scheme that leverages the sparsity of stochastic updates to achieve significant speedups while mitigating access conflicts. Comprehensive evaluations on 12 large-scale graphs demonstrate that the proposed method outperforms state-of-the-art algorithms in neighborhood preservation and cluster separation. Compared to existing baselines, our method reduces memory consumption by 72% on average and leverages simple GPU parallelism to generate a high-quality layout for a graph with 4 million nodes and 34 million edges in below 10 seconds.

Source Code: https://github.com/AnonymousUser202604/SNAP-tFDP

Online Demo: https://anonymoususer202604.github.io/snap-tfdp-online/

Figures:

Figure 2: Comparison of classical spring-electrical models and t-FDP models with different weighting schemes.

Figure 3: Comparison of different degree-weighting schemes for (a) two high-degree nodes and (b) a high-degree node and a low-degree node. The attractive force F^a_t-FDP is identical in all cases and is shown as a black solid line. Product-based weighting (orange) produces overly strong relative repulsion and its normalized variant (purple) nearly eliminates repulsion for low-degree nodes, while linearly normalized degree weighting (red) provides effective balance.

Figure 4: Validation of the edge-centric negative sampling strategy. (a) Energy loss curves showing that the actual energy of SNAP-tFDP converges consistently with the effective energy. (b) Superimposition of layouts by SNAP-tFDP (colored) and the full computation (gray).

Figure 5: Effect of the number of negative samples k. (a) Layout results and corresponding runtime of the serial SNAP-tFDP algorithm for different k on the APH dataset. (b) NP, SI, and CQ scores under varying k. Results for individual datasets are shown in gray, with the average across datasets highlighted in red.

Figure 6: (a) Convergence of the silhouette index (SI) for the serial SNAP-tFDP algorithm and its two lock-free parallel variants on the largest com-lj graph, where semi-transparent points indicate the results of five independent runs. (b) Layouts at four different epochs; for clarity, only the top 20 largest communities are shown.

Figure 7: Heatmaps employing a pink-to-green colormap illustrate the scores of NP (a), SI (b), and CQ (c) for layouts generated by nine methods across all datasets. Empty cells indicate that the graph was too large to be processed by the corresponding method. Each row corresponds to a dataset, and each column to a layout method. Colors are scaled row-wise based on the best and worst within each dataset.

Figure 8: Layouts and corresponding runtimes of twelve serial methods for the aircraft dataset. SNAP-tFDP (lower right) combines degree weighting with t-forces, yielding clear cluster structures with the lowest runtime, as fast as pure Pivot MDS.

Figure 9: (a) Differences in visual quality scores between the two parallel variants and the serial SNAP-tFDP across all datasets. (b) Speedup comparison of SNAP-tFDP and the parallel implementations of existing methods as a function of the number of CPU threads on the largest com-lj dataset.

Figure 10: Runtime of eight layout methods, together with the GPU implementations of FA2, t-FDP, and SNAP-tFDP, across all datasets.

Figure 11: Visualization of the com-friendster dataset, containing over 65.6 million nodes and 1.8 billion edges.

Materials:


Paper (PDF)	Supplemental Material (PDF)

Acknowledgements:

The authors like to thank the anonymous reviewers for their valuable input. This work is supported by the grants of the NSFC (No.62402284, No.U2436209), the Beijing Natural Science Foundation (L247027), NSF of Shandong province (ZR2024QF212), the Fundamental Research Funds for the Central Universities, and the Research Funds of Renmin University of China.