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

arXiv: https://arxiv.org/abs/2608.01907 · HTML: https://mlsanity.com/paper/2608.01907/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 3 Aug 2026.

## Built on by (most cited first, 1 of 1)

- [ibUMAP: Coherent and Scalable Field Evaluation for UMAP Optimization](https://mlsanity.com/paper/2610.01445/) (2026)

## Abstract (arXiv)

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.