SNAP-tFDP: Massively Scalable Graph Layouts via Sparse Negative Sampling
2026-08-03 • Graphics
Graphics
AI summaryⓘ
The authors address challenges in drawing very large network graphs clearly and quickly, especially when showing groups or communities within the data. They propose a new method that uses a special sampling technique and simpler forces to separate dense clusters better while keeping memory use low. Their approach runs fast and in parallel without complicated structures, making it efficient for huge graphs. Tests on large datasets show their method is better at preserving neighborhood relationships and separating clusters compared to existing tools.
Force-Directed PlacementNetwork VisualizationNegative SamplingDegree Weightingt-distribution ForcesParallelizationGraph LayoutCluster SeparationGPU ComputingMemory Efficiency
Authors
Xin Chen, Shuowei Hou, Yifan Wang, Mingliang Xue, Zezheng Feng, Oliver Deussen, Weidong Huang, Yunhai Wang
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.