CS Paper Radar

FenixWalk: Adaptive Sampling for Large-Scale Dynamic Graphs on Heterogeneous Architectures

Pinhuan Wang, Jianian Fu, Jie Zhang, Shixuan Sun, Qing Wang, Xiaoliang Wang, Chen Tian, Chengying Huan

cs.DC ·submitted 2026-11-03 11:07 UTC · v1
hot direction

Abstract

Random walks are fundamental to graph analytics, yet executing them efficiently on large, evolving graphs remains challenging. Existing approaches must balance sampling efficiency, update overhead, and memory consumption. Sampling structures optimized for throughput often incur substantial memory overhead and costly maintenance, whereas lightweight alternatives can suffer from high sampling latency on high-degree vertices or skewed weight distributions. These challenges become more pronounced on heterogeneous CPU--GPU platforms, where host memory provides capacity but GPU memory limits the amount of graph data that can benefit from parallel acceleration. We present FenixWalk, a memory-efficient random-walk system that combines unified in-place sampling with selective GPU acceleration for large-scale dynamic graphs. At its core, FenixWalk employs an in-place Fenwick representation that supports both rejection sampling and inverse-transform sampling without duplicating edge-level weight storage. This representation enables expected O(1) weight lookup for rejection sampling, together with O(log d) prefix sampling and updates. To exploit heterogeneous hardware efficiently, FenixWalk maintains the complete graph and its sampling structures in host memory while selectively placing frequently reused vertex-local samplers on the GPU. By transferring compact walker states instead of repeatedly migrating graph partitions, the system reduces cross-device communication and makes effective use of limited GPU memory. Experiments on large real-world graphs and representative random-walk workloads demonstrate that FenixWalk achieves average speedups ranging from 2.06x to 400.57x over existing random-walk systems.

Closest papers

Nearest neighbours by meaning across the whole index.

Dual-Metric Partitioning with Adaptive Kernel Execution for Efficient GCN Acceleration

cs.DB ·2026-09-02 ·Lingling Zhang, Hang Zeng, Pengpeng Qiao, Zhiwei Zhang, Ye Yuan +1 more
published similarity 0.71
Abstract · This research work has already been accepted by WISE'2026

Graph Convolutional Networks (GCNs) are widely used for large graph-structured data, including social, citation, and e-commerce networks, but their deployment is constrained by irregular memory access and severe GPU workload imbalance. These challenges arise in two dimensions: width imbalance from power-law degree distributions and depth imbalance from heterogeneous neighborhood connectivity.We present DualGCN, a GPU acceleration framework addressing both dimensions through dual-metric graph partitioning and adaptive kernel execution. DualGCN combines node degree, reflecting aggregation width, with neighborhood density estimated by anonymous random walks, capturing multihop connectivity and access depth. This hybrid workload metric enables connectivity-aware partitioning of large graphs into sparse and dense regions while reducing workload imbalance from linear to logarithmic complexity. DualGCN then selects partition-specific execution strategies: sparse partitions use warp-level parallelism and coalesced memory access, whereas dense partitions exploit instruction-level parallelism to hide latency and improve GPU utilization. Experiments on twelve real-world graph datasets show that DualGCN consistently accelerates GCN computation, achieving average speedups of 2.53x, 3.8x, and 2.13x over cuSPARSE, GNNAdvisor, and ACCEL, respectively. These results demonstrate that jointly optimizing graph partitioning and kernel execution provides an effective solution for processing large-scale graph and socialnetwork workloads.

0.34

GARDEN: Efficient GPU-Accelerated Billion-Scale GNN Training via Caching-Sampling-Batching Co-Design

cs.DC ·2026-11-08 ·Qingrui Zhu, Lei Liu, Yushu Cai, Kai Sheng, Zhiwen Chen +1 more
similarity 0.71
Abstract

Graph Neural Networks (GNNs) have shown impressive performance in diverse tasks such as social network analysis and recommendation systems. However, scaling their training to billion-edge graphs is hindered by the memory wall: GPU memory capacity falls short of the massive storage requirements for node features and topology. Sampling-based GNN training frameworks mitigate this by streaming subgraphs from CPU to GPU, but they incur prohibitive PCIe data transfers and non-coalesced memory accesses, resulting in bandwidth underutilization and low compute efficiency. We propose GARDEN, a GPU-accelerated sampling-based system that co-designs caching, sampling, and batching to eliminate these bottlenecks. GARDEN introduces three key innovations: (1) an Adaptive High-Fidelity Cache Allocator (AHFCA) that combines offline reuse profiling and online hotness tracking to dynamically cache features and adjacency lists within a fixed GPU memory budget, avoiding static allocation waste; (2) a Grouping-based Parallel Sampler that reorders stochastic neighborhood accesses(GPS) to maximize warp occupancy and hide latency on power-law graphs; and (3) a Super-batch Degree Classifier(SDC) that fuses mini-batches into degree-homogeneous groups, enabling cache-friendly coalesced transfers and high GPU utilization. Evaluations on real-world billion-scale graphs demonstrate that GARDEN achieves 4.54x, 1.27x, and 2.97x end-to-end training speedups over DGL-UVA, DUCATI, and FastGL, respectively, while maintaining model convergence and accuracy.

0.20

Multilevel Graph Partitioning on GPU Supercomputers

cs.DC ·2026-11-18 ·Michael S. Gilbert, Erik G. Boman, Kamesh Madduri
published similarity 0.65
Abstract · To appear in the proceedings of HiPC 2026

Graph partitioning is a key enabler in computational science, with applications to sparse linear algebra, load-balanced parallel computation, and graph computations. In recent years, graphics processing units (GPUs) have become the preferred accelerator on the world's top supercomputers. Despite this, most existing distributed graph partitioners do not utilize GPUs. In this work, we develop a new multi-GPU distributed partitioner based on Jet, a prior single-GPU partitioner. We seek to optimize scalability without sacrificing quality. Our partitioner utilizes CUDA-aware MPI, one-sided communication routines, and an overall bulk-synchronous parallel structure. We demonstrate solution quality comparable to Jet. Our experiments show excellent weak scaling up to 256 GPUs, enabling partitioning of instances significantly larger than a single-GPU partitioner can handle.

0.19

AMARA: Compiler-Driven Accelerator Architecture Design for Graphical Probabilistic Sampling

cs.AR cs.PL ·2026-11-11 ·Zhan Chen, Yihan Fu, Wenshuo Yue, Daijing Shi, Chenyun Yin +4 more
published similarity 0.65
Abstract · 14 pages, 15 figures, HPCA'27

Sampling methods are fundamental primitives for training and inference on probabilistic models. However, practical deployment of sampling algorithms such as Markov Chain Monte Carlo (MCMC) remains difficult on general-purpose processors. Existing hardware accelerators improve sampling efficiency, but they are typically specialized for a narrow class of models, graph topologies, or update schedules, making it difficult to support the diverse workloads used in real applications. This paper presents AMARA, an end-to-end compiler-driven accelerator framework for probabilistic sampling on arbitrary probabilistic graphical models. AMARA introduces MCMC-IR, a domain-specific intermediate representation that separates local factorized computation from global update dependencies. Based on this representation, the compiler performs architecture-aware partitioning, scheduling, and memory-access optimization to expose parallelism and reduce irregular graph communication. The optimized program is lowered to a compact ISA and executed on a programmable ASIC accelerator with specialized compute, sampling, and memory support. By co-designing the compiler and the architecture, AMARA bridges the gap between model generality and accelerator efficiency for practical MCMC-based probabilistic computing. We evaluate AMARA across representative workloads with different structures, including grid-structured and irregular energy-based models, and causal inference networks. The results show that AMARA supports a broad spectrum of discrete probabilistic models while achieving high sampling throughput and efficient hardware utilization. AMARA achieves an average of 6.1$\times$ (up to 16.3$\times$) higher sampling throughput than a JAX-GPU baseline on irregular workloads, and offers broader programmability than state-of-the-art accelerators.

0.39

GrAND: GPU-based Dynamic Graph Indexes for Approximate Nearest Neighbour Search

cs.DC cs.DB ·2026-08-21 ·Karthik Venkatasubba, Shivendra Deshpande, Shivram S, Jyothi Vedurada
similarity 0.65
Abstract

Modern Approximate Nearest Neighbour Search (ANNS) applications operate over continuously evolving vector collections and require graph indexes that sustain high-throughput searches while incorporating insertions and deletions with high recall. However, most GPU graph indexes are static or provide limited update support. Updates require neighbour discovery, reverse-edge creation, pruning, and deletion-induced graph repair; executing these operations concurrently introduces redundant distance computations and conflicting accesses to shared adjacency lists. Background-rebuild-based deletion further incurs substantial computation, additional memory consumption, and interference with foreground queries. We present GrAND (GPU-based Dynamic Graph Indexes for Approximate Nearest Neighbour Search), a GPU-native collection of dynamic-update algorithms for two popular graph indexes, Vamana and CAGRA. GrAND consolidates graph repair across a batch, eliminating redundant pruning computations, and employs a lock-free find-and-replace strategy for parallel adjacency-list updates. For reliable in-place deletion, GrAND constructs an on-demand reverse graph on the GPU, accurately identifying incoming edges without permanently duplicating the index. We evaluate GrAND on seven real-world datasets across five streaming workloads, comparing it against SVFusion and FreshDiskANN-GPU (our GPU adaptation of FreshDiskANN). GrAND improves overall workload throughput by 2.2x-8.7x and 6.5x-25.4x, respectively, while maintaining high search throughput and recall over sustained updates.

0.14

Enumeration-based Triangle Counting on GPUs

cs.DC ·2026-10-21 ·Sayan Ghosh
similarity 0.64
Abstract · 11 pages

Subgraph enumeration in partitioned graphs across distributed-memory systems is beset with challenges in balancing data movement with the local computation. Especially, counting the number of triangles induced by the closed wedges (i.e., length-3 cycles) is a measure of connectedness in a graph, but often limited by the significant search space caused by open wedges or length-2 paths (usually greater than the number of edges in a graph), which must be inspected to assess whether a particular wedge is closed. To mitigate triangle counting on massive graphs, distributed-memory partitioned-graph approaches are viable (i.e., assessing closed wedges independently within a partition), but load imbalance due to arbitrary communication can overshadow any gains from enhanced concurrency, owing to the inherent lack of structure in regular graphs. In this paper, we discuss a distributed-memory exact graph triangle counting implementation, and assess its performance over billion-edge real-world graphs on contemporary scale-out and scale-up based NVIDIA GPU platforms (considering NVIDIA ``Ampere'' and ``Hopper'' architectures), depicting a scalability spectrum of multiple orders of magnitude. Comparisons with existing state-of-the-art approaches demonstrates up to 10$\times$ improvements relative to distributed-memory CPU baseline, 2-100$\times$ over single-GPU vendor-optimized NVIDIA RAPIDS cuGraph and 10-60\% over multi-GPU $G^2$Miner, in terms of end-to-end execution times.

0.31

ESR-HGNN: Eliminating Semantic Redundancy for Efficient Mini-batch HGNN Inference

cs.AR ·2026-08-18 ·Dengke Han, Mingyu Yan, Duo Wang, Wenming Li, Xiaochun Ye +1 more
published similarity 0.64
Abstract · 14 pages, 12 figures, to apear in IEEE TPDS (just accepted)

Heterogeneous graph neural networks (HGNNs) are highly effective in processing heterogeneous graph data and have been widely adopted in critical domains. As real-world graph data continues to scale, performing direct inference on entire graphs becomes increasingly infeasible, making mini-batch methods the standard approach. However, in end-to-end HGNN inference, metapath-based mini-batch sampling constitutes a significant performance bottleneck due to the extensive random memory accesses induced by the irregular traversal of graph structures. Existing sampling paradigms suffer from excessive redundant traversals caused by inherent semantic redundancy, severely degrading sampling efficiency and, consequently, leading to suboptimal mini-batch inference performance. In this work, we propose a redundancy-aware HGNN sampling paradigm that leverages a metapath trie to reuse traversal paths, effectively eliminating redundant memory accesses. We then map it onto a multi-channel hardware sampling unit denominated ESR-HGNN. Furthermore, we introduce a reusability-driven metapath grouping technique that optimally clusters metapaths to maximize reusable traversal paths within hardware channels, enhancing efficiency in scenarios with semantic parallelism. Extensive experimental results demonstrate that ESR-HGNN achieves an average sampling performance improvement of one order of magnitude over CPU and GPU, accompanied by significant energy savings. Additionally, it delivers substantial speedup in end-to-end mini-batch inference when integrated with GPU and state-of-the-art HGNN inference accelerator.

0.37

ParaAnya: Accelerating Parallel Diffusion Sampling with Plug-and-Play Output Caching

cs.DC ·2026-09-29 ·Chee-En Yu, Xiao-Xi Tan, Yi-Cheng Lin, Yun-Shao Tsai, Chee-An Yu +1 more
similarity 0.61
Abstract · 5 pages

Diffusion models have achieved remarkable success in generative tasks, but their inherently sequential sampling process introduces a severe computational bottleneck. Recent Parallel-in-Time (PinT) solvers attempt to mitigate this by parallelizing generation across a sliding window of timesteps, advancing the window only when step-wise changes stabilize. However, this overlapping window mechanism forces the network to repeatedly evaluate the same timesteps. When the input variations between iterations are minimal, these redundant evaluations lead to significant computational waste. To address this inefficiency, we propose ParaAnya, an output cache mechanism agnostic to the parallel sampling algorithm that can reduce the number of function evaluations (NFE). ParaAnya caches input-output pairs of diffusion models and reuses the cached output at overlapping timesteps. By dispatching only cache-miss timesteps to GPU workers, our approach eliminates redundant computation while preserving the structure of the underlying algorithms' update rules. We integrate ParaAnya into four representative parallel sampling algorithms and evaluate its performance on Stable Diffusion v1.5. Across four parallel samplers evaluated with DDIM on eight GPUs, ParaAnya provides $1.30$--$2.43\times$ speedups over their uncached counterparts and reduces NFE by up to 70.1\%, reaching up to a $5.62\times$ speedup over single-GPU serial sampling while maintaining comparable CLIP scores.

0.49