SNAP-tFDP: Massively Scalable Graph Layouts via Sparse Negative Sampling
Authors
Xin Chen (Renmin University of China), Shuowei Hou (Renmin University of China), Yifan Wang (Shandong University), Mingliang Xue (Shandong provincial institute of educational sciences), Zezheng Feng (Northeastern University), Oliver Deussen (University of Konstanz), Weidong Huang (University of Technology Sydney), Yunhai Wang (Renmin University of China)
Presentation
- Session
- Let's dig into the data (from China)
- Time
- Friday, Nov 13, 09:00 – 09:12 (US/Eastern) · session 08:00 – 09:30
- Location
- Hall America center
Links
Sign in to access the preprint PDF.
Sign in- Download Supplemental Material
Keywords
Graph Layout, Network Visualization, Negative Sampling
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.
For Practitioners
Practitioners who work with large-scale network data would benefit from this paper, including network analysts, social scientists, cybersecurity researchers, and bioinformatics researchers who need to explore complex relational structures. The proposed SNAP-tFDP algorithm can help them generate scalable graph visualizations for massive networks by reducing memory usage and computation time while preserving community structures and local relationships. Practitioners can apply the method to effectively analyze large social networks, biological interaction networks, communication networks, as well as other graph-based datasets where existing layout methods cannot scale efficiently.