arXiv CS open access

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

Pinhuan Wang et al. · arxiv_cs

arXiv CS · Papers

cloud distributed-computing parallel-computing

Conceptio Open Archive

Analyze & explore related research in Conceptio

Connect this record directly into your research workflow or AI agent. Explore citations across open repositories, query full text, and export structured proof bundles.

Explore in Search →Connect via MCP / API ↗

arXiv:2611.04683v1 [cs.DC] 3 Nov 2026

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

Jianian Fu∗

Jie Zhang

Shixuan Sun

Nanjing University Nanjing, China pinhuan.wang02@gmail.com

Nanjing University Nanjing, China f36351010@gmail.com

Peking University Beijing, China jiez@pku.edu.cn

Shanghai Jiao Tong University Shanghai, China sunshixuan@sjtu.edu.cn

Qing Wang

Xiaoliang Wang

Chen Tian

Chengying Huan

Nanjing University Nanjing, China wangqing.cs@nju.edu.cn

Nanjing University Nanjing, China waxili@nju.edu.cn

Nanjing University Nanjing, China tianchen@nju.edu.cn

Nanjing University Nanjing, China huanchengying@nju.edu.cn

Abstract

search [17, 28], scalable graph neural network training [47], and large-scale recommendation [11, 46]. For example, DeepWalk [33] and node2vec [16] learn node embeddings from random-walk traces, while PageRank and its variants [17, 28] estimate vertex importance from the stationary behavior of random-walk processes. Recent graph-learning and recommendation systems further use random walks as a scaling mechanism, supporting compact minibatch construction and efficient item retrieval over massive graphs [11, 46, 47]. Many of these applications run on graphs that evolve over time. In such graphs, edges are continuously inserted, deleted, or modified, and random walks must be generated on updated snapshots to keep downstream results fresh. For example, Wharf [31] shows that reusing stale personalized PageRank walks after graph updates can, in practice, result in a symmetric mean absolute percentage error exceeding 80%, indicating that results derived from stale walks can differ substantially from those computed on the updated graph. Keeping random-walk results fresh on dynamic graphs ultimately relies on transition sampling over updated graph snapshots: given a vertex, the system samples the next vertex from its candidate neighbors according to a transition distribution. Even on static graphs, this operation can dominate end-to-end execution time; prior work reports that sampling accounts for up to 96.2% of graph-learning training time [14]. Dynamic graphs further complicate this because every edge insertion or deletion changes the transition distribution of the affected vertices. Therefore, supporting dynamic random walks requires more than updating graph storage: the sampling process must also adapt to updated transition distributions. Maintaining efficient transition sampling under frequent graph updates thus remains a critical algorithmic challenge: the sampler must provide high sampling throughput while keeping update and memory costs under control. Algorithmic Challenge. Existing sampling methods expose a three-way trade-off among sampling performance, update

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 inversetransform sampling without duplicating edge-level weight storage. This representation enables expected 𝑂 (1) weight lookup for rejection sampling, together with 𝑂 (log 𝑑) 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.06× to 400.57× over existing random-walk systems.

Introduction

Random walks are a fundamental primitive for graph analytics. They are widely used in graph mining and representation learning [16, 33], web ranking and personalized ∗ Both authors contributed equally to this work.

cost, and memory overhead. Alias-based systems [38, 45] provide 𝑂 (1) sampling after preprocessing, but they store auxiliary alias and probability entries and may require rebuilding vertex-local tables after edge or weight updates, incurring substantial update overhead. Rejection- and reservoirbased systems avoid auxiliary sampling structures and are therefore easy to update [21, 27, 32], but their per-sample cost can be high: rejection sampling may require many trials under skewed weights, while reservoir sampling scans the adjacency list and is inefficient for high-degree vertices. Inverse-transform sampling (ITS) supports 𝑂 (log 𝑑 𝑣 ) sampling through binary search over a maintained prefix-sum array [30], but the array incurs additional memory overhead and can be expensive to maintain under updates. Bingo [37] improves sampling and update performance for dynamic graphs, but its radix-based decomposition introduces substantial memory overhead. Consequently, existing designs still face a tension among efficient sampling, inexpensive updates, and low memory overhead. This trade-off motivates a closer look at rejection sampling and ITS. Rejection sampling is attractive for dynamic graphs because each proposal only requires the weight of a uniformly sampled edge position, but its efficiency degrades as the acceptance probability decreases. ITS, in contrast, is robust to weight skew, but its conventional prefix-sum array is costly to maintain under updates. A Fenwick tree provides a natural alternative, supporting both ITS sampling and weight updates in 𝑂 (log 𝑑) time. Our key observation is that the Fenwick representation can also provide efficient pointweight lookup for rejection sampling. Although recovering an arbitrary edge weight from a Fenwick tree can take 𝑂 (log 𝑑) time in the worst case, the cost depends on the number of trailing zero bits of the queried index. Since rejection sampling proposes edge positions uniformly, this lookup requires fewer than two Fenwick-entry accesses on average. Thus, a single Fenwick representation can support both sampling strategies without retaining a separate weight array. Based on this observation, our core idea is to directly encode each vertex’s edge weights in an in-place Fenwick representation. For a vertex of degree 𝑑, FenixWalk transforms the original 𝑑 weight-sized slots into a Fenwick tree of the same length. The representation supports 𝑂 (log 𝑑) prefix sampling and updates for ITS, while providing expected 𝑂 (1) weight lookup for rejection sampling. FenixWalk can therefore choose between rejection sampling and ITS at runtime according to the degree and weight distribution of each vertex, without changing or duplicating the underlying sampling state. This in-place representation combines the robustness of ITS with the expected efficiency of rejection sampling while using only the original edge-level weight storage. System Challenge. The proposed in-place sampler alone addresses the algorithmic challenge, but deploying it at large scale introduces a system challenge. Modern graphs can contain billions of edges, and a random-walk engine must store

the graph topology, edge weights, sampling state, and active walker state. Host DRAM can hold such graphs, but CPUonly execution provides limited throughput for the massive number of independent walk steps. GPUs offer high bandwidth and parallelism, but device memory is much smaller than host memory. Even with a compact sampler, the entire dynamic graph may not fit on the GPU. A natural response is hybrid CPU–GPU execution, but existing designs are not well matched to random walks. Systems that repeatedly transfer graph partitions across the CPU–GPU boundary can move far more data than each walk step actually consumes [43]. A random-walk step touches only the current vertex’s local distribution, and the next vertex is known only after sampling. The system challenge is therefore to exploit GPU parallelism while treating GPU memory as a limited execution resource. To address above challenges, we present FenixWalk, a hybrid CPU–GPU random-walk engine for large dynamic graphs. FenixWalk combines the in-place dynamic sampler with selective GPU residency. It keeps the complete dynamic graph and all samplers in CPU memory while placing only high-reuse vertex-local samplers on the GPU. Walkers located at GPU-resident vertices perform transition sampling on the GPU; walkers at nonresident vertices are processed by CPU worker threads. During normal execution, FenixWalk transfers active walker states rather than repeatedly moving adjacency lists or sampling structures. The resident set is refreshed at epoch granularity using visit-frequency estimates and memory cost, so GPU memory is spent on vertices whose expected reuse justifies their device footprint. The in-place sampler and the hybrid CPU–GPU engine reinforce each other. Because each sampler uses only the original weight slots, more useful vertices can remain resident under the same GPU memory budget. This combination lets FenixWalk support dynamic graphs while using CPU memory for capacity and the GPU for high-reuse sampling. This paper makes the following contributions:

• We propose a dynamic transition-sampling method that unifies rejection sampling and inverse-transform sampling in a single sampler and selects the more efficient strategy for each vertex at runtime (Section 3). • We show that a Fenwick representation can serve both sampling strategies. It supports 𝑂 (log 𝑑) prefix sampling and updates for ITS, while providing expected 𝑂 (1) pointweight lookup for rejection sampling, using only the original 𝑑 weight-sized slots (Section 3). • We build a hybrid CPU–GPU random-walk engine that keeps the dynamic graph in host DRAM and places only high-reuse vertex-local samplers on the GPU, avoiding repeated migration of large adjacency lists or sampling structures (Section 4). 2

• We evaluate FenixWalk on large real-world graphs and representative random-walk workloads under dynamic updates. By combining compact in-place samplers with selective GPU residency, FenixWalk achieves 2.06× to 400.57× average walk-execution speedups over existing randomwalk systems (Section 6).

Sampling on vertex v N(v)

2 1 3

Background and Motivation

2.1

Random Walks and Transition Sampling

Let 𝐺 = (𝑉 , 𝐸) be a graph, which can be directed or undirected. For a vertex 𝑣 ∈ 𝑉 , let 𝑁 (𝑣) denote the candidate neighbors that can be visited from 𝑣, and let 𝑑 𝑣 = |𝑁 (𝑣)|. In a directed graph, 𝑁 (𝑣) contains the outgoing neighbors of 𝑣. In an undirected graph, each undirected edge can be viewed as two directed arcs, so the same notation applies. A random walk is a sequence of vertices 𝑋 0, 𝑋 1, . . . , 𝑋𝐿 , where each next vertex is sampled from the candidates of the current walk state. Random walks are widely used in graph analytics. For example, DeepWalk [33] uses random walks to generate vertex sequences for representation learning, while node2vec [16] extends this idea with biased walks that control how the walk explores local and global neighborhoods. The next-hop sampling in random walks can be uniform or weighted. We use the weighted form as the common notation: each candidate edge (𝑣, 𝑢) is assigned a nonnegative transition weight 𝑤 𝑣,𝑢 , and the next vertex is sampled according to

✗ 〇 ✓ 〇

(a) Alias sampling

(b) Rejection sampling scan

〇

reservoir

Replace with 𝑤𝑢2 prob.

𝑤𝑢1 +𝑤𝑢2

(d) Reservoir sampling

Figure 1. Examples of four representative sampling methods. This setting differs from dynamic random walks studied by recent systems [27, 32]. In dynamic random walks, the graph topology may be fixed, while the transition distribution is computed at runtime from user-defined walk logic or state, as discussed in Section 2.1. 2.3

Sampling Methods

From a systems perspective, the random-walk variants discussed above share the same core operation: given the current walk state, sample one candidate neighbor according to the corresponding transition distribution. Thus, each walk step reduces to transition sampling over a candidate set, and a random-walk engine must perform this operation repeatedly for many concurrent walkers. For dynamic graphs, the sampling method must balance three requirements: high sampling throughput, efficient updates after graph changes, and low memory overhead. These requirements are often in tension. A sampler with fast sampling may require expensive preprocessing or large auxiliary structures, while an update-friendly sampler may have slower per-step sampling. We illustrate four representative sampling methods in Figure 1 and summarize them below. Alias Sampling. As shown in Figure 1(a), alias methods partition the weighted outgoing edges of vertex 𝑣 into 𝑑 𝑣 buckets with the same total weight, where each bucket stores at most two candidate edges. Sampling first selects a bucket uniformly at random and then chooses between the stored candidates. After 𝑂 (𝑑 𝑣 ) preprocessing, alias tables support 𝑂 (1) weighted sampling, making them attractive for static graphs. However, alias tables are costly to maintain under updates: Any change to the outgoing edges may require rebuilding the affected vertex’s alias structure. They also store extra probability and alias entries, increasing the overall memory footprint. These costs make alias sampling less suitable for large, dynamically changing graphs. Rejection Sampling. Rejection sampling repeatedly selects a candidate neighbor uniformly at random and accepts it with probability proportional to its weight. Figure 1(b) shows examples of accepted and rejected candidates. Its main advantage is that it avoids auxiliary sampling structures and

𝑤 𝑣,𝑢 .

𝑥 ∈𝑁 (𝑣) 𝑤 𝑣,𝑥

The uniform random walk is recovered by setting 𝑤 𝑣,𝑢 = 1 for all 𝑢 ∈ 𝑁 (𝑣). Many random-walk methods [28, 33] use weights that depend only on the current vertex and candidate neighbor, while methods [9, 16] such as node2vec can use weights that also depend on the previous walk state. 2.2

〇

〇 sample

Pr[𝑋𝑖+1 = 𝑢 | 𝑋𝑖 = 𝑣] = Í

✓ Accept ✗ Reject

2.5

Random Walks on Dynamic Graphs

A dynamic graph evolves through a sequence of edge and vertex updates, including insertions, deletions, and weight or attribute changes. For random-walk execution, vertex updates can be handled through edge changes. We model the dynamic graph at time 𝑡 as a snapshot 𝐺𝑡 = (𝑉𝑡 , 𝐸𝑡 ), and random walks may be executed on selected snapshots to keep downstream applications up to date. Preparing the next selected snapshot for random-walk execution requires not only updating the graph representation, which is typically handled by the dynamic-graph container, but also updating any auxiliary sampling structures used by the sampler to ensure correct transition sampling. This paper, FenixWalk, focuses on the latter requirement: auxiliary sampling structures must be maintained efficiently while still supporting fast sampling, so that random-walk execution can resume quickly after graph updates. 3

only relies on the current edge weights in a dynamic graph. However, its runtime depends on the acceptance rate and can degrade to 𝑂 (𝑑 𝑣 ) under skewed weight distributions. Inverse Transform Sampling. Inverse Í transform sampling (ITS) draws a random value 𝑟 ∈ 0, 𝑢 ∈𝑁 (𝑣) 𝑤 𝑣,𝑢 and returns the first edge whose prefix sum exceeds 𝑟 . If a prefixsum array is maintained, as shown in Figure 1(c), sampling can be reduced to 𝑂 (log 𝑑 𝑣 ) via binary search. However, this prefix-sum array introduces extra memory overhead and must be updated as the graph changes. Reservoir Sampling. Reservoir sampling processes the neighbors of 𝑣 in a streaming manner, as shown in Figure 1(d). It scans the adjacency list once and maintains a single current sample, or reservoir. When an edge (𝑣, 𝑢) with weight 𝑤 𝑣,𝑢 is visited, the reservoir is updated according to the cumulative weight seen so far, so that the final selected edge is sampled with probability proportional to its weight. Reservoir sampling avoids precomputed sampling structures and can be effective when transition weights are computed on the fly. However, each sample requires scanning all 𝑑 𝑣 neighbors, resulting in 𝑂 (𝑑 𝑣 ) time per step. This makes it inefficient for high-degree vertices and large graphs. Other Methods. Beyond the methods above, Bingo [37] uses binary decomposition of edge weights to support 𝑂 (1) sampling and 𝑂 (log𝑊 ) updates on dynamic graphs, where 𝑊 denotes the maximum edge weight. However, this design requires 𝑂 (𝑑 𝑣 log𝑊 ) additional space for a vertex 𝑣, which substantially increases the memory footprints. 2.4

with minimal persistent edge-level memory, allowing more vertices to fit in GPU memory. We also need a hybrid execution model that exploits GPU parallelism and host-memory capacity without repeatedly moving large adjacency lists or sampling structures. FenixWalk addresses these requirements with an in-place dynamic sampler (Section 3) and a CPU–GPU execution architecture (Section 4).

In-Place Sampling for Dynamic Graphs

Observation. The sampling methods in Section 2.3 expose different trade-offs. Rejection and reservoir sampling require no auxiliary sampling structures and are therefore easy to maintain under updates. Between them, rejection sampling is more attractive for random walks: when transition weights are not highly skewed, it requires only a constant expected number of proposals, whereas reservoir sampling always scans the full adjacency list in 𝑂 (𝑑 𝑣 ) time per sample. Inverse transform sampling (ITS), in contrast, provides a robust 𝑂 (log 𝑑 𝑣 ) sampling by searching cumulative weights. Rejection sampling and ITS therefore offer complementary strengths across different weight distributions. However, ITS requires prefix-sum information, while rejection sampling requires direct access to individual edge weights. A straightforward implementation supporting both access patterns may therefore retain the raw edge weights together with a separate prefix-sum structure, increasing storage. Our Goal. We seek a single vertex-local representation that supports both sampling strategies without duplicating edgelevel weight state. For a vertex 𝑣 with degree 𝑑 𝑣 , the representation should

Limitations of Prior Work and Motivation

As discussed in Section 2.3, existing random-walk samplers do not simultaneously balance sampling speed, update cost, and memory footprint. Alias sampling provides 𝑂 (1) sampling, but its tables are costly to update and require extra storage. Bingo also supports 𝑂 (1) sampling and efficient updates, but requires 𝑂 (𝑑 𝑣 log𝑊 ) extra space for vertex 𝑣. ITS provides an 𝑂 (log 𝑑 𝑣 ) sampling bound, but requires a maintained prefix structure. Rejection and reservoir sampling avoid auxiliary structures and are easy to update, but their cost can degrade to 𝑂 (𝑑 𝑣 ) on high-degree vertices. This trade-off becomes more critical on GPUs. Random walks expose massive parallelism, but large dynamic graphs often exceed GPU memory once graph, sampling structures, and active walk states are included. Even memory-efficient systems [27, 32] cannot fully avoid this. Hybrid CPU–GPU execution is therefore attractive: the CPU provides large DRAM capacity, while the GPU accelerates parallel walks. However, out-of-GPU systems such as LightTraffic move graph partitions and walk states between CPU and GPU memory. This transfer-driven execution can be inefficient for random walks, whose low arithmetic intensity makes CPU– GPU traffic and graph loading potential bottlenecks [43]. These algorithmic and systemic observations motivate FenixWalk. We need a sampler that supports efficient updates

• use only 𝑑 𝑣 weight-sized slots; • support expected 𝑂 (1) weight lookup for uniformly sampled positions, preserving efficient rejection sampling; and • support 𝑂 (log 𝑑 𝑣 ) prefix selection and updates, preserving the robustness of ITS. We next show that the Fenwick-tree [13] representation satisfies these requirements. 3.1

In-Place Fenwick Encoding

Key Idea. For a vertex 𝑣 with degree 𝑑 = 𝑑 𝑣 , let 𝑊 = (𝑤 1, 𝑤 2, . . . , 𝑤𝑑 ) denote its transition weights. Instead of storing𝑊 together with a separate sampling structure, FenixWalk transforms these 𝑑 weight-sized slots directly into a Fenwicktree representation 𝐹 of the same length. For position 𝑖, let lowbit(𝑖) denote the least significant set bit of 𝑖. The value stored at position 𝑖 is

𝐹 [𝑖] =

𝑖 ∑︁

𝑤𝑗.

(1)

𝑗=𝑖 −lowbit(𝑖 )+1

Thus, every array position stores the sum of the standard Fenwick range ending at that position. No additional edgelevel array is allocated. The transformation from the original 4

Physical storage F₁ F₂ F₃ F₄ F₅ F₆ F₇ F₈ lowbit = 1000 F₈ Fenwick entries F₄ lowbit = 0100 F₂ F₆ lowbit = 0010 lowbit = 0001

F₁

F₃

F₅

F₇

w₁ w₂ w₃ w₄ w₅ w₆ w₇ w₈ Original weight array

Algorithm 1: FenixWalk’s Adaptive sampling Input: Vertex 𝑣; random number generator R; edge position 𝑖; cost ratio 𝜌 = 𝑐 lookup /𝑐 find Output: Sampled edge position or true edge weight 1 Function WeightLookup(𝑣, 𝑖): 2 𝑥, 𝑧, 𝑗 ← 𝐹 𝑣 [𝑖], 𝑖 − lowbit(𝑖), 𝑖 − 1; 3 while 𝑗 ≠ 𝑧 do 𝑥, 𝑗 ← 𝑥 − 𝐹 𝑣 [ 𝑗], 𝑗 − lowbit( 𝑗) ; 4 return 𝑥; 5 Function PrefixSelect(𝑣, R): 6 𝑟 ← Uniform(R, 0,𝑊𝑣Σ ); 7 𝑝, 𝑠, 𝑏 ← 0, 0, 2 ⌊log2 𝑑 𝑣 ⌋ ; 8 while 𝑏 > 0 do 9 𝑞, 𝑏 ← 𝑝 + 𝑏, ⌊𝑏/2⌋; 10 if 𝑞 ≤ 𝑑 𝑣 and 𝑠 + 𝐹 𝑣 [𝑞] ≤ 𝑟 then 𝑝, 𝑠 ← 𝑞, 𝑠 + 𝐹 𝑣 [𝑞] ;

Logical representation Prefix select

Lookup (w6)

Figure 2. Fenwick encoding in FenixWalk. Each 𝐹 [𝑖] covers the range ending at 𝑖 with length lowbit(𝑖). Highlighted paths illustrate prefix selection and point-weight lookup. weights to this representation can be performed in 𝑂 (𝑑) time using the linear Fenwick-tree construction. An important property of this layout is that the amount of information aggregated at position 𝑖 depends on lowbit(𝑖). For example, every odd position satisfies 𝐹 [𝑖] = 𝑤𝑖 , while positions divisible by larger powers of two summarize correspondingly larger ranges. As we show below, this structure makes point-weight recovery particularly efficient when queried positions are uniformly distributed. Figure 2 illustrates the representation. The array supports two operations required during walk execution: prefix selection for ITS and point-weight lookup for rejection sampling. 3.2

return 𝑝 + 1; 12 Function RejectionSample(𝑣, R): 13 repeat 14 𝑖 ← UniformInt(R, 1, 𝑑 𝑣 ); 15 𝑤, 𝑟 ← WeightLookup(𝑣, 𝑖), Uniform(R, 0,𝑊𝑣max ); 16 until 𝑟 < 𝑤; 17 return 𝑖; 18 Function AdaptiveSample(𝑣, R): 𝑑 𝑊 max 19 if 𝜌 𝑣𝑊 𝑣Σ ≤ log 𝑑 𝑣 then 𝑣 20 return RejectionSample(𝑣, R); 11

Sampling and Update Operations

Sampling Primitives. Algorithm 1 shows how the in-place representation supports weight lookup and prefix selection, enabling FenixWalk’s adaptive sampling. For ITS, PrefixSelect draws a random value 𝑟 ∈ [0,𝑊𝑣Σ ) and performs a Fenwick-tree binary search to find the first position whose cumulative weight exceeds 𝑟 . For rejection sampling, a candidate position 𝑖 is chosen uniformly from {1, . . . , 𝑑 𝑣 }. WeightLookup recovers the corresponding original weight from the Fenwick representation. Starting from 𝐹 [𝑖], it subtracts entries that cover the preceding positions in the range represented by 𝐹 [𝑖]. Adaptive Sampling. The representation allows FenixWalk to choose between rejection sampling and ITS without changing the underlying sampling structure. For each sampling request at vertex 𝑣, FenixWalk estimates their costs as

𝑇rej (𝑣) = 𝑐 lookup ·

𝑑 𝑣𝑊𝑣max , 𝑊𝑣Σ

𝑇its (𝑣) = 𝑐 find log 𝑑 𝑣 ,

return PrefixSelect(𝑣, R);

is highly skewed, FenixWalk switches to ITS and avoids repeated rejected proposals. Weight Updates. For an additive update Δ to position 𝑖, FenixWalk applies the Fenwick-tree point update: 𝐹 [ 𝑗] ← 𝐹 [ 𝑗] + Δ, 𝑗 = 𝑖, 𝑖 + lowbit(𝑖), . . . , 𝑑. For a set-value update from 𝑤𝑖 to 𝑤𝑖′ , FenixWalk first obtains 𝑤𝑖 using WeightLookup, computes Δ = 𝑤𝑖′ − 𝑤𝑖 , and then performs the same Fenwick point update. FenixWalk also maintains 𝑊𝑣Σ using the same update delta. This requires only constant-size metadata per vertex. Insertions and Deletions. The dynamic graph container appends newly inserted edges to the vertex-local adjacency array. Suppose a new edge with weight 𝑤𝑖 is appended at position 𝑖 = 𝑑 + 1. Its Fenwick entry can be initialized as

(2)

where 𝑊𝑣Σ is the total transition weight, 𝑊𝑣max is an upper bound on edge weight, and 𝑐 lookup and 𝑐 find capture the implementation costs of the two primitives. The rejection estimate follows from an acceptance probability of 𝑊𝑣Σ /(𝑑 𝑣𝑊𝑣max ). During walk execution, FenixWalk compares the two estimates and uses the cheaper strategy for the current vertex. When weights are relatively uniform, rejection sampling avoids the logarithmic prefix search. When the distribution

𝐹 [𝑖] = 𝑤𝑖 + Prefix(𝑖 − 1) − Prefix(𝑖 − lowbit(𝑖)),

(3)

where Prefix(𝑥) denotes the prefix sum through 𝑥. A deletion is implemented lazily by setting the corresponding edge weight to zero through a set-value update. The zero-weight entry remains in the array until the dynamic graph container performs its periodic compaction. 5

Covered visits (%)

When the adjacency array is rebuilt, FenixWalk first recovers the edge weights, removes deleted entries, and constructs a new Fenwick representation for the compacted array. Further details of dynamic graph maintenance are presented in Section 5.1. 3.3

100

Complexity Analysis

We analyze the vertex-local sampling structure independently. Consider a vertex 𝑣 whose current Fenwick array contains 𝑑 edge positions, including zero-weight entries retained before compaction, and assume 𝑊𝑣Σ > 0. Sampling. Prefix selection examines at most one entry per tree level, so PrefixSelect takes 𝑂 (log 𝑑) time. For WeightLookup at position 𝑖, let 𝜈 2 (𝑖) denote the number of trailing zero bits of 𝑖. Algorithm 1 performs one initial access to 𝐹 𝑣 [𝑖] followed by exactly 𝜈 2 (𝑖) subtraction steps. Rejection sampling proposes a position 𝐼 uniformly from {1, . . . , 𝑑 }. Therefore, E[1 + 𝜈 2 (𝐼 )] = 1 +

∑︁ ⌊𝑑/2𝑘 ⌋ 𝑘 ≥1

< 2.

80 60 AB TW

40 20

Top vertices (%)

Figure 3. Cumulative coverage of sampling visits by the top-visited vertices on datasets AB, TW, and SK. edge-level weight entries. The spare capacity maintained by the dynamic graph container is orthogonal to this saving: FenixWalk does not introduce a second sampling array. Discussion. The key property exploited by FenixWalk is the match between the Fenwick representation and the access pattern of rejection sampling. For uniformly sampled positions, point queries require fewer than two entry accesses on average. This allows a single encoding to support both efficient rejection sampling and ITS, while retaining logarithmic updates and avoiding a second edge-level array.

(4)

𝑑

Hence, each rejection proposal requires expected 𝑂 (1) Fen𝑊Σ wick accesses. Since its acceptance probability is 𝑑𝑊𝑣𝑣max , Re-

Hybrid CPU–GPU Architecture

Section 3 introduces an in-place sampler that avoids a separate sampling structure. This reduction is necessary but not sufficient for large graphs. FenixWalk therefore treats GPU memory as a limited execution resource rather than as a place to store the whole graph.

𝑑𝑊 max jectionSample takes expected 𝑂 ( 𝑊𝑣Σ ) time. 𝑣

FenixWalk selects between rejection sampling and prefix selection using Equation 2. Ignoring the constant calibration factors captured by 𝑐 lookup and 𝑐 find , the expected cost of 𝑑𝑊 max adaptive sampling is therefore 𝑂 (min{ 𝑊𝑣Σ , log 𝑑 }). Thus, 𝑣 FenixWalk preserves expected constant-time sampling when rejection is effective, while retaining an expected 𝑂 (log 𝑑) bound under skewed weight distributions. Updates and Rebuilding. An additive update modifies at most 𝑂 (log 𝑑) Fenwick entries. A set-value update first recovers the old weight and then applies the corresponding additive update, giving 𝑂 (log 𝑑) time. Appending an edge using Equation 3 requires 𝑂 (log 𝑑) time, and lazy deletion is a set-value update, which also takes 𝑂 (log 𝑑) time. When compaction rebuilds a vertex-local array, recovering all original weights takes 𝑂 (𝑑) work, since the average lookup cost over all positions is less than two as shown in Equation 4. Removing zero-weight entries and constructing the new Fenwick representation are also linear, so the complete rebuild takes 𝑂 (𝑑) work. Construction and Space. The initial representation of a vertex can be constructed in 𝑂 (𝑑) time. Over a graph with 𝑚 edges, initialization therefore requires 𝑂 (𝑚) work. For a vertex with 𝑑 edge positions, the sampling representation uses one weight-sized value per position and 𝑂 (1) additional metadata, including 𝑊𝑣Σ and 𝑊𝑣max . Thus, over the graph, the sampler requires 𝑚 weight-sized edge-level entries plus 𝑂 (|𝑉 |) metadata. In contrast, retaining both the raw weights and a separate data structure requires 2𝑚

4.1

Architecture Overview

Observation. The key observation is that random-walk visits are not uniform. Figure 3 shows the cumulative fraction of sampling visits covered by the top-visited vertices during a DeepWalk execution. Across all datasets, a small fraction of vertices accounts for most steps: the top 10% cover more than 80% of visits. The skew is particularly strong on TW, where the top 1% of vertices covers about 90% of visits. This concentration largely reflects structural skew in the graph. This observation suggests that GPU memory should be used for reusable vertex-local sampling structures rather than for uniformly storing graph data. Instead of treating GPU memory as a cache for graph partitions, FenixWalk treats it as a limited resource for high-reuse sampling states. The host keeps the complete dynamic graph and manages walk execution, while the GPU persistently stores only the vertex-local sampling states of selected vertices. This design differs from transfer-driven CPU–GPU execution. Systems such as LightTraffic [43] reduce CPU–GPU traffic by coordinating graph partitions and walk states, but their execution still centers on moving graph data needed by active walkers. For fine-grained random-walk steps, this can be inefficient because each step uses only a small part of the loaded data, and future accesses are difficult to predict. LightTraffic’s evaluation likewise shows substantial CPU–GPU 6

Given a GPU memory budget 𝐵 gpu , selecting the deviceresident set 𝑅 can be written as ∑︁ ∑︁ max 𝑓b(𝑣) · Δ𝑡 gpu (𝑣) s.t. 𝑚 gpu (𝑣) ≤ 𝐵 gpu . (5)

GPU selected samplers

sample

Dispatch

𝑅 ⊆𝑉

Translate

Host

full graph + samplers

𝑣 ∈𝑅

Equation (5) can be solved as a knapsack problem. Exact optimization is unnecessary because it adds substantial preprocessing overhead; we therefore use a ratio-based greedy policy. For each vertex, FenixWalk computes the estimated benefit per unit of GPU memory:

Merge

……

𝑣 ∈𝑅

Walkers

𝜌 (𝑣) = Figure 4. Overview of FenixWalk’s hybrid CPU–GPU architecture. The left side shows the memory layout, and the right side shows the execution flow.

Vertices are sorted in descending order of 𝜌, and FenixWalk selects them greedily until the GPU memory budget is exhausted. This ranking prioritizes vertices that combine high expected reuse with low device-memory cost. The compact sampler from Section 3 directly improves this strategy by reducing 𝑚 gpu (𝑣), allowing more useful sampler arrays to fit under the same memory budget.

I/O overhead on large graphs [43]. In addition, such designs are less suitable for biased dynamic sampling, where the system must maintain and access updatable sampling states rather than only traverse adjacency data. FenixWalk instead keeps selected reusable sampling states persistently on the GPU and transfers only walker states during execution. Figure 4 gives an overview of FenixWalk’s hybrid CPU– GPU architecture. The host keeps the graph together with all samplers introduced in Section 3, while the GPU stores only a selected subset of samplers. During walk execution, walkers are dispatched according to the residency of their current vertices. Steps on GPU-resident vertices are processed by GPU sampling kernels, which return local neighbor positions that are translated on the host into global vertex identifiers. Steps on remaining vertices are served directly from the host-resident graph, and the two streams are merged into the final walk results. This organization allows CPU and GPU execution to proceed concurrently while avoiding repeated movement of full adjacency lists or graph partitions. 4.2

𝑓b(𝑣) · Δ𝑡 gpu (𝑣) . 𝑚 gpu (𝑣)

4.3

Update Handling

Graph updates are applied to the CPU-resident graph, which stores the complete graph and all sampler arrays. If an update affects a GPU-resident vertex, FenixWalk applies the same vertex-local update operations from Section 3 to its device copy; otherwise, no GPU-side action is required. Updates to resident and nonresident vertices can be handled concurrently by GPU kernels and CPU workers, with synchronization only before the next walk execution. The resident set is reconsidered at epoch granularity. During idle periods or when the visit pattern changes substantially, FenixWalk reruns the selection from Section 4.2. Vertices kept in the set retain their device states, newly selected vertices are copied to GPU, and unselected vertices are evicted. Only the difference between resident sets is moved.

Device-Resident Vertex Selection

FenixWalk selects a set of vertex sampler arrays to keep on the GPU during preprocessing. This selection is important because an effective residency strategy can improve GPU utilization. The selection is guided by two factors: how often each vertex is expected to be visited, and how much memory is required to keep its sampler array resident. This formulation avoids selecting vertices by visit count alone, which can waste device memory on very high-degree vertices whose sampler arrays are expensive to keep on the GPU. The initial visit-frequency estimate for each vertex can be obtained from a small CPU warm-up run. Let 𝑓b(𝑣) denote the estimated number of visits to vertex 𝑣 in the upcoming epoch. Let 𝑚 gpu (𝑣) denote the GPU memory footprint of keeping 𝑣’s in-place sampling structure on the device. Let Δ𝑡 gpu (𝑣) denote the estimated per-visit latency reduction from serving 𝑣 on the GPU rather than from the CPU-resident graph. Then the expected benefit of placing 𝑣 on the GPU is 𝑓b(𝑣)·Δ𝑡 gpu (𝑣).

Implementation Details

FenixWalk is implemented in C++ and CUDA. Besides standard system and CUDA libraries, our implementation uses the header-only ankerl::unordered_dense hash table [23]. We describe its use for node2vec support in Section 5.2. Parameter Settings. We set 𝑐 lookup /𝑐 find = 0.4 in Equation 2 for the runtime choice between rejection sampling and Fenwick-based inverse-transform sampling, as our profiling experiments show that values in the range 0.4–1 consistently achieve near-optimal performance. In Equation 5, we use log 𝑑 𝑣 as a lightweight proxy for the GPU-side benefit Δ𝑡 gpu (𝑣). Before the first execution round, we run a lightweight CPU-only profiling pass that accounts for 3% of the total walk workload, and use it to collect initial visit statistics for resident selection. The GPU memory budget 𝐵 gpu can be adjusted according to the available device memory in practice. For a fair comparison, unless otherwise specified 7

Table 1. Graph statistics of the evaluated datasets.

in Section 6, we set 𝐵 gpu to 20% of the memory footprint required to store FenixWalk’s full graph and data structures. 5.1

FenixWalk uses a lightweight dynamic graph container for edge insertions and deletions. Each vertex maintains a contiguous adjacency array with spare capacity. When the array becomes full, FenixWalk doubles its capacity and copies the existing entries; under low utilization, the array is compacted and shrunk. Adjacency arrays are allocated from a memory pool to avoid frequent small allocations. The graph container is orthogonal to FenixWalk’s sampling design; more sophisticated dynamic graph stores can be used instead (Section 7.2), and its cost is included in all measurements and is small relative to sampler maintenance. 5.2

|𝐸|

Avg. Deg.

Max Deg.

Arabic (AB) 22.7M 1.3B Twitter (TW) 41.7M 4.8B SK-2005 (SK) 50.6M 3.9B UK-Union (UK) 133.6M 11.0B CC-Dom (CD) 120.0M 8.8B CC-Host (CH) 481.6M 6.7B

55.5 115.5 76.3 82.3 73.7 13.9

576.3K 6.0M 8.6M 5.6M 17.8M 40.6M

Dataset

Dynamic Graph Support

|𝑉 |

For personalized PageRank (PPR), every sampled candidate is committed as the next vertex, while termination is probabilistic. At each step, the walker terminates with probability 𝛾; otherwise, it continues from the sampled next vertex.

Algorithm Support

FenixWalk separates transition sampling from workloadspecific walk logic. CPU–GPU execution proceeds in rounds. In each round, every active walker issues one sampling request. A workload-specific rule decides whether the sampled candidate is committed as the walker’s next vertex. We increment the step count only for committed transitions:

Evaluation

6.1

Evaluation Setup

The evaluation is performed on a Linux server equipped with two 2.0 GHz Intel Xeon Gold 6330 CPUs, 56 physical cores, 512 GB of DRAM, and two NVIDIA A100 40GB GPUs. Unless otherwise stated, each experiment uses a single A100 GPU. Datasets. Table 1 summarizes the statistics of our evaluation datasets. These real-world datasets are obtained from KONECT [22], the Laboratory for Web Algorithmics [2–4] and Common Crawl [6, 7]. We treat all datasets as undirected graphs, following prior systems [27, 32]. For unweighted graphs, we synthesize edge weights to evaluate weighted sampling. Specifically, for each edge, we generate its weight from a uniform distribution with probability 𝛽; otherwise, we assign a degree-based weight. This setting covers both random and degree-correlated weight distributions used in prior work [27, 32, 37]. In the main experiments, we set 𝛽 = 0.5. We further analyze the performance of FenixWalk under different weight distributions in Section 6.3.1. To generate dynamic updates, we hold out a subset of edges from each dataset and use the remaining graph as the initial snapshot [37]. We then run ten update rounds; in each round, updates are randomly generated by deleting existing edges or inserting held-out edges. Each round contains BATCHSIZE = 100K updates. After each round, the system generates random walks on the updated graph. We report the total end-to-end time across all ten rounds. Workloads. We evaluate three representative random-walk workloads: DeepWalk [33], node2vec [16], and personalized PageRank (PPR) [28]. Following prior work [27, 32], we set the walk length of DeepWalk and node2vec to 80, use 𝑝 = 2 and 𝑞 = 0.5 in Equation (6) for node2vec, and set the PPR termination probability 𝛾 to 0.2. To keep the overall evaluation tractable, we uniformly sample 10% of vertices as starting vertices and use the same sources for all systems. Unless otherwise stated, the remaining sensitivity and ablation experiments use DeepWalk as the default workload.

𝑠 𝑤𝑎𝑙𝑘𝑒𝑟 ← 𝑠 𝑤𝑎𝑙𝑘𝑒𝑟 + 1[Commit(𝑤𝑎𝑙𝑘𝑒𝑟 )]. Walkers that satisfy their termination condition are removed from the active set; the remaining walkers are rescheduled for the next sampling round. When the active set becomes too small to efficiently utilize the GPU, FenixWalk finishes the remaining walkers with a lightweight CPU-side fallback. This interface makes workload support explicit: each workload only needs to specify how a sampled candidate is committed and when a walker terminates. We illustrate this interface using representative workloads that are also evaluated in Section 6.2: DeepWalk [33], node2vec [16], and PPR [28]. DeepWalk uses first-order random walks. Every sampled candidate is committed as the next vertex, and a walker terminates after reaching the configured walk length. For node2vec, FenixWalk follows the rejection-sampling method used in KnightKing [45]. Each candidate transition is additionally weighted by the node2vec bias, which depends on the previous vertex 𝑡, the current vertex 𝑣, and the sampled candidate 𝑥:   1/𝑝, 𝑥 = 𝑡,    𝛼 𝑝𝑞 (𝑡, 𝑥) = 1, (6) (𝑡, 𝑥) ∈ 𝐸,    1/𝑞, otherwise.  FenixWalk proposes candidates from the original transition distribution of 𝑣 and uses the node2vec bias to decide whether a candidate is committed. We use a hash table to check whether (𝑡, 𝑥) ∈ 𝐸. If a candidate is not committed, the walker remains at 𝑣, and the step count is increased only after a committed transition. Similarly, a node2vec walker terminates after reaching the walk length. 8

Table 2. Overall evaluation against four random-walk systems. Execution time is reported in seconds. Speedup is the geometric mean over completed datasets. OOM denotes out-of-memory; OOT denotes exceeding 36,000 seconds (10 hours). SK

Speedup

KnightKing FlowWalker FlexiWalker LightTraffic FenixWalk

30.20 734.19 47.79 55.21 13.83

120.95 11977.92 OOM 128.72 24.25

97.17 5696.14 699.48 145.97 34.76

283.28 OOM OOM 312.76 114.70

317.31 OOM OOM 383.48 81.95

672.02 OOM OOM 1048.56 269.32

3.00x 162.57x 8.34x 4.05x –

KnightKing FlowWalker FlexiWalker FenixWalk

102.76 2079.32 576.44 51.38

233.00 OOT OOM 58.14

207.39 17205.31 5057.83 124.20

633.14 OOM OOM 420.24

689.56 OOM OOM 323.69

1613.21 OOM OOM 914.79

2.06x 74.87x 21.37x -

KnightKing FlowWalker FlexiWalker LightTraffic FenixWalk

28.04 184.47 12.90 4.73 1.45

74.50 3051.01 OOM 8.91 4.46

63.76 2784.33 295.43 9.74 3.77

214.67 OOM OOM 24.90 17.81

177.74 OOM OOM 25.36 8.54

229.85 OOM OOM 96.37 40.84

14.06x 400.57x 26.40x 2.34x -

KnightKing

FlowWalker

FlexiWalker

6.2

LightTraffic

FenixWalk

100 10 1

OOM OOM

Baselines. We compare FenixWalk against four randomwalk systems in the overall evaluation: KnightKing [45], FlowWalker [27], FlexiWalker [32], and LightTraffic [43]. KnightKing is a representative CPU random-walk engine that uses alias sampling. FlowWalker and FlexiWalker are representative GPU-based random-walk systems. FlowWalker uses reservoir sampling, while FlexiWalker combines reservoir sampling with rejection sampling. LightTraffic is a representative out-of-GPU-memory design that relies on CPU– GPU transfers of graph partitions and walker states. For systems that do not natively support dynamic graphs, we make minimal implementation changes to process graph updates while preserving their original sampling algorithms. Bingo [37] is a dynamic graph random-walk system that supports efficient sampling and updates, but incurs a large memory footprint. It is therefore not included in the overall evaluation because it runs out of memory on all datasets under our experimental setting. We provide a dedicated comparison with Bingo at a smaller scale in Section 6.2.1.

OOM OOM

PPR

OOM OOM

node2vec

OOM

DeepWalk

System

Memory usage (GB)

Workload

Figure 5. Memory usage in the overall evaluation. Compared with prior GPU-based systems, the advantage of FenixWalk is more pronounced. This runtime gap mainly comes from their sampling strategies rather than GPU execution itself. FlowWalker and FlexiWalker avoid heavy preprocessing structures, but their online sampling strategies become expensive on high-degree vertices or under skewed transition distributions. In these cases, sampling may require work proportional to the vertex degree, and the largest vertices in our datasets have millions of outgoing edges. On the datasets where they complete, FenixWalk outperforms FlowWalker by 162.57×, 74.87×, and 400.57× on DeepWalk, node2vec, and PPR, respectively, and outperforms FlexiWalker by 8.34×, 21.37×, and 26.40×, respectively. Moreover, FlowWalker and FlexiWalker run out of memory on larger datasets, and FlowWalker exceeds the 10-hour time limit on node2vec for TW. These results show that GPU parallelism alone is not sufficient for large graphs; scalable random-walk execution requires an efficient sampling strategy and a memory-aware execution design. Compared with LightTraffic, FenixWalk achieves average speedups of 4.05× on DeepWalk and 2.34× on PPR. This advantage is consistent with the CPU–GPU I/O bottleneck reported in the original LightTraffic paper [43], whereas FenixWalk keeps selected samplers resident on the GPU and transfers only walker states during walk execution.

Overall Evaluation

Table 2 reports the execution time of FenixWalk and four random-walk systems across three workloads. Since LightTraffic does not support node2vec, we evaluate its performance only on DeepWalk and PPR. Overall, FenixWalk consistently achieves the lowest execution time. Compared with KnightKing, FenixWalk achieves average speedups of 3.00×, 2.06×, and 14.06× on DeepWalk, node2vec, and PPR, respectively. KnightKing’s alias table sampling is efficient for static transition distributions, but maintaining alias tables becomes expensive on dynamic graphs because any updates such as edge insertions, deletions, and weight changes can require rebuilding the affected vertex-local tables. 9

Table 3. Time and memory comparison with Bingo on its original datasets and experimental settings. Dataset

System

Time (s)

Mem. (GB)

Mem. Saving

Bingo FenixWalk

0.25 0.33

0.87 0.07

– 12.43×

Bingo FenixWalk

0.64 0.49

1.38 0.15

– 9.20×

Bingo FenixWalk

0.44 0.40

4.62 0.64

– 7.22×

Bingo FenixWalk

1.96 3.13

7.25 1.25

– 5.80×

Avg. speedup over Bingo: 0.91×

on AM and LJ. Averaged over per-dataset speedup ratios, FenixWalk achieves 0.91× the speed of Bingo. This result is expected: Bingo’s sampler provides stronger sampling complexity, while FenixWalk trades this advantage for a much smaller sampling footprint. At the same time, FenixWalk keeps update operations lightweight despite their logarithmic complexity. On an A100 GPU, FenixWalk reaches a peak update throughput of 1.158 billion updates per second, compared with Bingo’s 226 million updates per second. These results suggest that FenixWalk removes most of Bingo’s sampling-memory overhead with only minor runtime difference on small GPU-resident graphs, while retaining efficient update performance. Moreover, in the hybrid setting, the reduced sampler footprint allows FenixWalk to place more high-reuse vertex-local samplers on the GPU, leading to higher throughput under the same GPU memory budget.

Avg. memory saving: 8.32×

The node2vec workload takes the longest time for all evaluated systems because its transition rule requires additional work beyond sampling a neighbor. In particular, each candidate step must account for the relation between the previous vertex and the candidate next vertex, which introduces extra edge-existence checks and bias computation. Memory Usage. Figure 5 reports the bottleneck memory usage in the overall evaluation. We report DRAM usage for the CPU-based KnightKing and GPU memory usage for FlowWalker, FlexiWalker, LightTraffic, and FenixWalk. FlowWalker and FlexiWalker store only the original graph, but still require the graph to fit in limited GPU memory, leading to OOM on the larger datasets. On the datasets where they complete, FenixWalk also uses less GPU memory. LightTraffic operates in the substantially simpler unbiased setting. Nevertheless, FenixWalk achieves comparable GPU memory usage while outperforming LightTraffic by 4.05× and 2.34× on DeepWalk and PPR, respectively. Since the reported memory resources differ, the GPU memory of FenixWalk is not directly comparable with KnightKing’s DRAM usage. For completeness, we also measure FenixWalk’s CPU-side memory footprint. Across the six datasets, KnightKing consumes 42.87–231.11 GB, compared with 28.62–204.18 GB for FenixWalk, and uses 1.51× as much memory on average. This saving stems from FenixWalk’s in-place storage of sampling information, which avoids auxiliary alias tables.

6.3

Ablation Study

6.3.1 Algorithmic Ablation. Figure 6 compares five sampling methods under three representative edge-weight distributions: uniform-random, mixed, and skewed. The compared methods are Fenwick-based inverse-transform sampling, alias-table sampling, rejection sampling, reservoir sampling, and FenixWalk’s sampling. To isolate the sampling method from system optimizations, all variants use the same configuration and differ only in their sampler. Each stacked bar shows walk and update time, normalized by FenixWalk’s total time on the same dataset. In the uniform-random setting, edge weights are independently sampled from a uniform distribution, following prior systems [27, 32]. In the skewed setting, edge weights are generated based on vertex degree, following Bingo [37]. The mixed setting combines uniform-random and degree-based weights across vertices. Among methods that maintain auxiliary sampling structures, Fenwick-based inverse-transform sampling is robust to weight skew, but its total time increases to 1.35×–1.96× under uniform-random weights because of its logarithmic persample cost. Alias-table sampling provides efficient constanttime sampling: its walk time ranges from 0.88× to 1.18× that of FenixWalk. However, this advantage is offset by expensive maintenance, because updates may require rebuilding the affected vertex-local alias table. Consequently, its update time is up to 59.55× that of FenixWalk, making its total time substantially higher despite its fast sampling. Methods without auxiliary sampling structures avoid rebuilding costs but can incur high walk-execution overhead. Rejection sampling performs well under uniform-random weights. Under mixed weights, however, it takes 2.78× the total time of FenixWalk on AB and does not complete within the time limit on the larger datasets. It also fails to complete under skewed weights because frequent rejected proposals substantially increase its sampling cost. Reservoir sampling performs even worse because it scans the entire adjacency list for every sample. On AB, its total time is 9.48× and 10.80×

6.2.1 Comparison with Bingo. We follow the setup of Bingo [37] and evaluate on the same four datasets (AM, GO, CT, and LJ) under the same DeepWalk workload. For a fair comparison, we run FenixWalk in the mode where all required data structures are placed on the GPU. Table 3 shows that FenixWalk substantially reduces memory usage while maintaining comparable execution time under Bingo’s original setting. Across the datasets, FenixWalk reduces memory consumption by 5.80× to 12.43×, with an average saving of 8.32×. In terms of runtime, FenixWalk is faster than Bingo on GO and CT, while Bingo is faster 10

OOT

RVS OOT

RJS

OOT

Alias Update OOT

FenixWalk Walk OOT

OOT

Fenwick

RVS OOT

RJS OOT

Alias Update OOT

FenixWalk Walk OOT

Fenwick

RVS

OOT

RJS

OOT

Alias Update OOT

FenixWalk Walk OOT

Normalized time

Fenwick

(b) Mixed

(a) Uniform

Normalized time

Figure 6. Algorithmic ablation under different edge-weight distributions. We compare Fenwick-based inverse-transform sampling (ITS), alias-table sampling (Alias), rejection sampling (RJS), reservoir sampling (RVS), and FenixWalk’s sampling. Each stacked bar reports walk and update time. OOT denotes that the total time exceeds five times that of FenixWalk. CPU-only

Random

Degree

is not sufficient. Random remains 1.94×–4.70× slower than FenixWalk, because random residency does not match the skewed access pattern of random walks. Degree performs better than Random in execution time, reducing the average normalized time from 3.09× to 2.06×. This shows that degree is a useful but incomplete proxy for access hotness: high-degree vertices are often more expensive to sample from and may receive more visits, but degree does not directly capture the actual walk distribution or the benefit per byte of GPU memory. For example, on CH, Degree leaves only 30.1% of the workload on the CPU and takes only 1.50× the runtime of FenixWalk, suggesting that degree captures a substantial part of the hot set on this graph. In contrast, on CD, Degree leaves 64.2% of the workload on the CPU and takes 3.58× the runtime of FenixWalk. This contrast shows that high-degree vertices do not always coincide with the vertices that dominate random-walk execution. Figure 7(b) further explains the time results. Random leaves 58.3%–82.1% of the workload on the CPU (66.8% on average), while Degree reduces this ratio to 30.1%–64.2% (49.2% on average). In comparison, FenixWalk leaves only 3.7%–11.8% of the workload on the CPU (8.0% on average). Therefore, the advantage of FenixWalk comes not merely from using GPU memory, but from selecting samplers with high reuse relative to their device-memory cost.

5.0 2.5 0.0

CPU workload (%)

(a) Normalized execution time. CPU-only Degree

Random

FenixWalk

100 50 0

(b) CPU workload ratio.

Figure 7. Ablation of FenixWalk’s device-resident selection policy. (a) compares execution time under different residency policies. (b) shows the fraction of CPU workload.

that of FenixWalk under uniform-random and mixed weights, respectively, while it does not complete within the time limit in the remaining cases. Its low update cost therefore cannot compensate for its linear sampling overhead. Overall, FenixWalk delivers the most consistent performance across weight distributions. It remains close to the fastest method under uniform-random weights and achieves the lowest time under mixed and skewed weights.

6.4

Further Analysis

6.4.1 Transfer Overhead. Table 4 reports the host-todevice (H2D) and device-to-host (D2H) transfer time during execution. The measured transfer cost is small compared with the total runtime. On average, H2D and D2H account for only 4.95% and 5.10% of total runtime. This shows that FenixWalk is not dominated by CPU–GPU data movement. Moreover, these transfer times represent the raw copy cost. In the actual execution pipeline, CPU-side sampling for nonresident walkers runs concurrently with GPU execution and data transfers. Therefore, most of the transfer latency can be overlapped with useful CPU work.

6.3.2 System Ablation. We conduct a system ablation to isolate the effects of hybrid CPU–GPU execution and device-resident selection, as shown in Figure 7. CPU-only disables GPU residency and executes all walk steps on the CPU. Random and Degree use the same GPU memory budget as FenixWalk, but select resident vertices uniformly at random or by highest degree, respectively. As shown in Figure 7(a), CPU-only execution requires 2.41×–5.52× the execution time of FenixWalk, with an average slowdown of 3.99×. This confirms that GPU acceleration is important for random-walk execution when high-reuse vertex-local samplers can be kept resident on the device. However, simply using the same amount of GPU memory

6.4.2 Impact of GPU Memory Budget. Figure 8 studies the impact of the GPU memory budget with DeepWalk 11

Avg. ratio

H2D D2H

0.73 1.15

1.37 1.92

1.95 1.36

3.95 2.56

3.59 3.45

14.31 10.80

4.95% 5.10%

Insert

Runtime (s)

Time

Runtime (s)

Table 4. H2D and D2H transfer time (s). 20 10

20 40 60 80 100

(a) Walk length

Mixed

Delete

30 20

10K

100K

(b) Update batch size

Runtime (s)

Figure 9. Sensitivity to walk length and update batch size. 60

40 20

5% 10% 15% 20% 25% 30% 35% 40% 45% 50%

Related Work

7.1

Random Walk and Sampling Systems

Random-walk systems have been studied extensively on CPUs, GPUs, and other accelerators. On CPUs, KnightKing [45] provides a random-walk engine with a walker-centric interface and rejection-based optimizations for node2vec. GraphWalker [40], GraSorw [24], and SOWalker [42] focus on I/O-efficient execution through subgraph loading, block scheduling, and disk-aware optimizations. ThunderRW [35] and FlashMob [44] improve throughput by optimizing memory access patterns, such as step interleaving, prefetching, and cross-task reordering. TEA and TEA+ [18, 19] use persistent data structures to support efficient temporal-graph sampling. Wharf [31] maintains random-walk corpora on dynamic graphs by storing walks in a compressed structure and updating only affected walk suffixes after updates. Accelerator-based systems further exploit parallelism in random walk and graph sampling. C-SAW [30] optimizes GPU-based ITS sampling, NextDoor [21] maps rejection sampling to GPUs with transit parallelism, and Skywalker [38] constructs GPU alias tables, extended to multiple GPUs by Skywalker+ [39]. gSampler [14] provides matrix-centric APIs for sampling, while LightRW [36] targets FPGA-based random-walk execution. LightTraffic [43] targets out-of-GPUmemory random walks by transferring graph partitions between CPU and GPU. Bingo [37] supports 𝑂 (1) sampling and 𝑂 (log𝑊 ) updates on dynamic graphs via bias decomposition. FlowWalker [27] and FlexiWalker [32] support random walks with runtime-dependent transition distributions; FlowWalker uses reservoir sampling, while FlexiWalker adaptively selects between reservoir and rejection sampling. FenixWalk focuses on a setting that is not fully addressed by prior systems. Most random-walk systems do not target dynamic graphs, where sampling structures may require repeated preprocessing after updates. Wharf [31] instead maintains stored walk corpora under updates, whereas FenixWalk maintains the sampling structures used to generate walks. Some prior work [27, 32] uses dynamic random walk to refer to state-dependent transition distributions, rather than to random walks on graphs with structural updates. Bingo [37] targets dynamic graphs, but its radix-based decomposition introduces substantial memory overhead and is constrained by limited GPU memory. LightTraffic [43] is one of the few

Figure 8. Impact of GPU memory budget on evaluation time.

workload on AB, TW, and SK. We vary 𝐵 gpu from 5% to 50% of the memory required to store FenixWalk’s full graph and data structures. Overall, increasing the GPU memory budget initially reduces the walk time, because more high-reuse vertex-local samplers can be kept on the GPU and a larger fraction of walk steps can be executed by GPU kernels. However, the benefit is not strictly monotonic. After the budget becomes sufficiently large, increasing 𝐵 gpu provides diminishing returns and can even slightly increase the walk time. This is because a larger resident set shifts more walk steps to the GPU, and the GPU-side execution eventually becomes the bottleneck. In this regime, adding more resident vertices no longer substantially reduces CPU work, but can increase GPU kernel work. These results show that a moderate budget is enough to capture most of the benefit. 6.4.3 Sensitivity to Workload and Updates. We further study the sensitivity of FenixWalk to walk length and update batch size. Figure 9(a) varies the walk length on AB and TW. As the walk length increases, the runtime increases, because longer walks generate more transition-sampling steps. This result shows that the runtime changes consistently with the amount of random-walk workload. Figure 9(b) evaluates different numbers of updates on the Twitter graph. For insert-only and mixed updates, the runtime increases as the update batch becomes larger since more affected sampling structures need to be maintained. Delete-only updates show a different trend: the runtime first decreases and then increases. Our breakdown shows that this behavior comes from two competing effects. On one hand, more deletions increase the update-processing cost. On the other hand, deletions reduce the graph size and thus reduce the subsequent walk-execution time. The total runtime is therefore determined by the combination of increasing update cost and decreasing walk cost. 12

https://commoncrawl.org/blog/host--and-domain-level-webgraphs-january-february-and-march-2026 [8] Laxman Dhulipala, Guy E. Blelloch, and Julian Shun. 2019. Lowlatency graph streaming using compressed purely-functional trees. In Proceedings of the 40th ACM SIGPLAN Conference on Programming Language Design and Implementation (Phoenix, AZ, USA) (PLDI 2019). Association for Computing Machinery, New York, NY, USA, 918–934. doi:10.1145/3314221.3314598 [9] Yuxiao Dong, Nitesh V. Chawla, and Ananthram Swami. 2017. metapath2vec: Scalable Representation Learning for Heterogeneous Networks. In Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (Halifax, NS, Canada) (KDD ’17). Association for Computing Machinery, New York, NY, USA, 135–144. doi:10.1145/3097983.3098036 [10] David Ediger, Rob McColl, Jason Riedy, and David A. Bader. 2012. STINGER: High performance data structure for streaming graphs. In 2012 IEEE Conference on High Performance Extreme Computing. 1–5. doi:10.1109/HPEC.2012.6408680 [11] Chantat Eksombatchai, Pranav Jindal, Jerry Zitao Liu, Yuchen Liu, Rahul Sharma, Charles Sugnet, Mark Ulrich, and Jure Leskovec. 2018. Pixie: A System for Recommending 3+ Billion Items to 200+ Million Users in Real-Time. In Proceedings of the 2018 World Wide Web Conference (Lyon, France) (WWW ’18). International World Wide Web Conferences Steering Committee, Republic and Canton of Geneva, CHE, 1775–1784. doi:10.1145/3178876.3186183 [12] Guanyu Feng, Zixuan Ma, Daixuan Li, Shengqi Chen, Xiaowei Zhu, Wentao Han, and Wenguang Chen. 2021. RisGraph: A Real-Time Streaming System for Evolving Graphs to Support Sub-millisecond Per-update Analysis at Millions Ops/s. In Proceedings of the 2021 International Conference on Management of Data (Virtual Event, China) (SIGMOD ’21). Association for Computing Machinery, New York, NY, USA, 513–527. doi:10.1145/3448016.3457263 [13] Peter M. Fenwick. 1994. A new data structure for cumulative frequency tables. Softw. Pract. Exper. 24, 3 (March 1994), 327–336. doi:10.1002/ spe.4380240306 [14] Ping Gong, Renjie Liu, Zunyao Mao, Zhenkun Cai, Xiao Yan, Cheng Li, Minjie Wang, and Zhuozhao Li. 2023. gSampler: General and Efficient GPU-based Graph Sampling for Graph Learning. In Proceedings of the 29th Symposium on Operating Systems Principles (Koblenz, Germany) (SOSP ’23). Association for Computing Machinery, New York, NY, USA, 562–578. doi:10.1145/3600006.3613168 [15] Oded Green and David A Bader. 2016. cuSTINGER: Supporting dynamic graph algorithms for GPUs. In IEEE High Performance Extreme Computing Conference (HPEC). IEEE, 1–6. [16] Aditya Grover and Jure Leskovec. 2016. node2vec: Scalable Feature Learning for Networks. In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (San Francisco, California, USA) (KDD ’16). Association for Computing Machinery, New York, NY, USA, 855–864. doi:10.1145/2939672.2939754 [17] Taher H. Haveliwala. 2002. Topic-sensitive PageRank. In Proceedings of the 11th International Conference on World Wide Web (Honolulu, Hawaii, USA) (WWW ’02). Association for Computing Machinery, New York, NY, USA, 517–526. doi:10.1145/511446.511513 [18] Chengying Huan, Yongchao Liu, Heng Zhang, Shuaiwen Song, Santosh Pandey, Shiyang Chen, Xiangfei Fang, Yue Jin, Baptiste Lepers, Yanjun Wu, and Hang Liu. 2024. TEA+: A Novel Temporal Graph Random Walk Engine with Hybrid Storage Architecture. ACM Trans. Archit. Code Optim. 21, 2, Article 37 (May 2024), 26 pages. doi:10.1145/3652604 [19] Chengying Huan, Shuaiwen Leon Song, Santosh Pandey, Hang Liu, Yongchao Liu, Baptiste Lepers, Changhua He, Kang Chen, Jinlei Jiang, and Yongwei Wu. 2023. TEA: A General-Purpose Temporal Graph Random Walk Engine. In Proceedings of the Eighteenth European Conference on Computer Systems (Rome, Italy) (EuroSys ’23). Association for Computing Machinery, New York, NY, USA, 182–198.

out-of-GPU-memory designs. However, it still relies on CPU– GPU transfers of graph partitions and walk states, which are expensive for fine-grained random-walk execution. In contrast, FenixWalk maintains an updateable sampler in the original weight array and uses GPU memory for high-traffic vertices without repeatedly moving large adjacency lists or auxiliary sampling structures. 7.2

Dynamic and Streaming Graph Systems

Dynamic graph systems provide update-friendly storage and processing over evolving graphs. CPU systems use specialized representations to support efficient updates, traversal, and incremental processing [8, 10, 12, 20, 25, 26, 29, 34]. GPU systems similarly develop dynamic storage and memorymanagement techniques [1, 5, 15, 41, 48]. These systems are complementary to FenixWalk. They provide graph storage for dynamic processing but do not maintain sampling structures. FenixWalk focuses on this layer: it maintains an updateable sampler within the weight array and uses its reduced footprint to improve GPU residency in hybrid CPU–GPU execution.

Conclusion

This paper presents FenixWalk, a hybrid CPU–GPU randomwalk engine for dynamic graphs. FenixWalk uses a Fenwick representation to support expected 𝑂 (1) weight lookup for rejection sampling and 𝑂 (log 𝑑) prefix sampling and updates for ITS, without retaining a separate raw-weight array. It further keeps the complete graph on the host and selectively places high-reuse vertex-local samplers on the GPU, achieving memory-efficient and scalable random-walk execution.

References [1] Muhammad A. Awad, Saman Ashkiani, Serban D. Porumbescu, and John D. Owens. 2020. Dynamic Graphs on the GPU. In 2020 IEEE International Parallel and Distributed Processing Symposium (IPDPS). 739–748. doi:10.1109/IPDPS47924.2020.00081 [2] Paolo Boldi, Marco Rosa, Massimo Santini, and Sebastiano Vigna. 2011. Layered Label Propagation: A MultiResolution Coordinate-Free Ordering for Compressing Social Networks. In Proceedings of the 20th international conference on World Wide Web, Sadagopan Srinivasan, Krithi Ramamritham, Arun Kumar, M. P. Ravindra, Elisa Bertino, and Ravi Kumar (Eds.). ACM Press, 587–596. [3] Paolo Boldi, Massimo Santini, and Sebastiano Vigna. 2008. A Large Time-Aware Graph. SIGIR Forum 42, 2 (2008), 33–38. [4] Paolo Boldi and Sebastiano Vigna. 2004. The WebGraph Framework I: Compression Techniques. In Proc. of the Thirteenth International World Wide Web Conference (WWW 2004). ACM Press, Manhattan, USA, 595–601. [5] Federico Busato, Oded Green, Nicola Bombieri, and David A Bader. 2018. Hornet: An efficient data structure for dynamic sparse graphs and matrices on gpus. In IEEE High Performance extreme Computing Conference (HPEC). IEEE, 1–7. [6] Common Crawl Foundation. 2025. Host- and domain-level web graph May–jul. 2025. Accessed: 2026-06-06. https://commoncrawl.org/blog/ host--and-domain-level-web-graphs-may-june-and-july-2025 [7] Common Crawl Foundation. 2026. Host- and domainlevel web graph Jan.–Mar. 2026. Accessed: 2026-06-02. 13

doi:10.1145/3552326.3567491 [20] Wole Jaiyeoba and Kevin Skadron. 2019. GraphTinker: A High Performance Data Structure for Dynamic Graph Processing. In 2019 IEEE International Parallel and Distributed Processing Symposium (IPDPS). 1030–1041. doi:10.1109/IPDPS.2019.00110 [21] Abhinav Jangda, Sandeep Polisetty, Arjun Guha, and Marco Serafini. 2021. Accelerating graph sampling for graph machine learning using GPUs. In Proceedings of the Sixteenth European Conference on Computer Systems (Online Event, United Kingdom) (EuroSys ’21). Association for Computing Machinery, New York, NY, USA, 311–326. doi:10.1145/ 3447786.3456244 [22] Jérôme Kunegis. 2013. KONECT: the Koblenz network collection. In Proceedings of the 22nd International Conference on World Wide Web (Rio de Janeiro, Brazil) (WWW ’13 Companion). Association for Computing Machinery, New York, NY, USA, 1343–1350. doi:10.1145/ 2487788.2488173 [23] Martin Leitner-Ankerl. 2022. ankerl::unordered_dense: A Fast and Densely Stored Hash Map and Hash Set. https://github.com/martinus/ unordered_dense. Accessed: 2026-06-06. [24] Hongzheng Li, Yingxia Shao, Junping Du, Bin Cui, and Lei Chen. 2022. An I/O-efficient disk-based graph system for scalable second-order random walk of large graphs. Proc. VLDB Endow. 15, 8 (April 2022), 1619–1631. doi:10.14778/3529337.3529346 [25] Mugilan Mariappan, Joanna Che, and Keval Vora. 2021. DZiG: sparsityaware incremental processing of streaming graphs. In Proceedings of the Sixteenth European Conference on Computer Systems (Online Event, United Kingdom) (EuroSys ’21). Association for Computing Machinery, New York, NY, USA, 83–98. doi:10.1145/3447786.3456230 [26] Mugilan Mariappan and Keval Vora. 2019. GraphBolt: DependencyDriven Synchronous Processing of Streaming Graphs. In Proceedings of the Fourteenth EuroSys Conference 2019 (Dresden, Germany) (EuroSys ’19). Association for Computing Machinery, New York, NY, USA, Article 25, 16 pages. doi:10.1145/3302424.3303974 [27] Junyi Mei, Shixuan Sun, Chao Li, Cheng Xu, Cheng Chen, Yibo Liu, Jing Wang, Cheng Zhao, Xiaofeng Hou, Minyi Guo, Bingsheng He, and Xiaoliang Cong. 2024. FlowWalker: A Memory-Efficient and HighPerformance GPU-Based Dynamic Graph Random Walk Framework. Proc. VLDB Endow. 17, 8 (April 2024), 1788–1801. doi:10.14778/3659437. 3659438 [28] Lawrence Page, Sergey Brin, Rajeev Motwani, and Terry Winograd. 1999. The PageRank Citation Ranking : Bringing Order to the Web. In The Web Conference. https://api.semanticscholar.org/CorpusID: 1508503 [29] Prashant Pandey, Brian Wheatman, Helen Xu, and Aydin Buluc. 2021. Terrace: A Hierarchical Graph Container for Skewed Dynamic Graphs. In Proceedings of the 2021 International Conference on Management of Data (Virtual Event, China) (SIGMOD ’21). Association for Computing Machinery, New York, NY, USA, 1372–1385. doi:10.1145/3448016.3457313 [30] Santosh Pandey, Lingda Li, Adolfy Hoisie, Xiaoye S. Li, and Hang Liu. 2020. C-SAW: A Framework for Graph Sampling and Random Walk on GPUs. In SC20: International Conference for High Performance Computing, Networking, Storage and Analysis. 1–15. doi:10.1109/SC41405. 2020.00060 [31] Serafeim Papadias, Zoi Kaoudi, Jorge-Arnulfo Quiané-Ruiz, and Volker Markl. 2022. Space-efficient random walks on streaming graphs. Proc. VLDB Endow. 16, 2 (Oct. 2022), 356–368. doi:10.14778/3565816.3565835 [32] Seongyeon Park, Jaeyong Song, Changmin Shin, Sukjin Kim, Junguk Hong, and Jinho Lee. 2026. FlexiWalker: Extensible GPU Framework for Efficient Dynamic Random Walks with Runtime Adaptation. In Proceedings of the 21st European Conference on Computer Systems (McEwan Hall/The University of Edinburgh, Edinburgh, Scotland UK) (EUROSYS ’26). Association for Computing Machinery, New York, NY, USA, 1499–1514. doi:10.1145/3767295.3769358

[33] Bryan Perozzi, Rami Al-Rfou, and Steven Skiena. 2014. DeepWalk: online learning of social representations. In Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (New York, New York, USA) (KDD ’14). Association for Computing Machinery, New York, NY, USA, 701–710. doi:10.1145/ 2623330.2623732 [34] Hao Qi, Yiyang Wu, Ligang He, Yu Zhang, Kang Luo, Minzhi Cai, Hai Jin, Zhan Zhang, and Jin Zhao. 2024. LSGraph: A Locality-centric Highperformance Streaming Graph Engine. In Proceedings of the Nineteenth European Conference on Computer Systems (Athens, Greece) (EuroSys ’24). Association for Computing Machinery, New York, NY, USA, 33–49. doi:10.1145/3627703.3650076 [35] Shixuan Sun, Yuhang Chen, Shengliang Lu, Bingsheng He, and Yuchen Li. 2021. ThunderRW: an in-memory graph random walk engine. Proc. VLDB Endow. 14, 11 (July 2021), 1992–2005. doi:10.14778/3476249. 3476257 [36] Hongshi Tan, Xinyu Chen, Yao Chen, Bingsheng He, and Weng-Fai Wong. 2023. LightRW: FPGA Accelerated Graph Dynamic Random Walks. Proc. ACM Manag. Data 1, 1, Article 90 (May 2023), 27 pages. doi:10.1145/3588944 [37] Pinhuan Wang, Chengying Huan, Zhibin Wang, Chen Tian, Yuede Ji, and Hang Liu. 2025. Bingo: Radix-based Bias Factorization for Random Walk on Dynamic Graphs. In Proceedings of the Twentieth European Conference on Computer Systems (Rotterdam, Netherlands) (EuroSys ’25). Association for Computing Machinery, New York, NY, USA, 605–620. doi:10.1145/3689031.3717456 [38] Pengyu Wang, Chao Li, Jing Wang, Taolei Wang, Lu Zhang, Jingwen Leng, Quan Chen, and Minyi Guo. 2021. Skywalker: Efficient AliasMethod-Based Graph Sampling and Random Walk on GPUs. In 2021 30th International Conference on Parallel Architectures and Compilation Techniques (PACT). 304–317. doi:10.1109/PACT52795.2021.00029 [39] Pengyu Wang, Cheng Xu, Chao Li, Jing Wang, Taolei Wang, Lu Zhang, Xiaofeng Hou, and Minyi Guo. 2023. Optimizing GPU-Based Graph Sampling and Random Walk for Efficiency and Scalability. IEEE Trans. Comput. 72, 9 (2023), 2508–2521. doi:10.1109/TC.2023.3251860 [40] Rui Wang, Yongkun Li, Hong Xie, Yinlong Xu, and John C. S. Lui. 2020. GraphWalker: An I/O-Efficient and Resource-Friendly Graph Analytic System for Fast and Scalable Random Walks. In 2020 USENIX Annual Technical Conference (USENIX ATC 20). USENIX Association, 559–571. https://www.usenix.org/conference/atc20/presentation/wang-rui [41] Martin Winter, Daniel Mlakar, Rhaleb Zayer, Hans-Peter Seidel, and Markus Steinberger. 2018. faimGraph: High performance management of fully-dynamic graphs under tight memory constraints on the GPU. In SC18: International Conference for High Performance Computing, Networking, Storage and Analysis. IEEE, 754–766. [42] Yutong Wu, Zhan Shi, Shicai Huang, Zhipeng Tian, Pengwei Zuo, Peng Fang, and Dan Feng. 2023. SOWalker: An I/O-Optimized Out-ofCore Graph Processing System for Second-Order Random Walks. In 2023 USENIX Annual Technical Conference (USENIX ATC 23). USENIX Association, Boston, MA, 87–100. https://www.usenix.org/conference/ atc23/presentation/wu [43] Yipeng Xing, Yongkun Li, Zhiqiang Wang, Yinlong Xu, and John C. S. Lui. 2023. LightTraffic: On Optimizing CPU-GPU Data Traffic for Efficient Large-scale Random Walks. In 2023 IEEE 39th International Conference on Data Engineering (ICDE). 882–895. doi:10.1109/ICDE55515. 2023.00073 [44] Ke Yang, Xiaosong Ma, Saravanan Thirumuruganathan, Kang Chen, and Yongwei Wu. 2021. Random Walks on Huge Graphs at Cache Efficiency. In Proceedings of the ACM SIGOPS 28th Symposium on Operating Systems Principles (Virtual Event, Germany) (SOSP ’21). Association for Computing Machinery, New York, NY, USA, 311–326. doi:10.1145/3477132.3483575 [45] Ke Yang, MingXing Zhang, Kang Chen, Xiaosong Ma, Yang Bai, and Yong Jiang. 2019. KnightKing: a fast distributed graph random 14

walk engine. In Proceedings of the 27th ACM Symposium on Operating Systems Principles (Huntsville, Ontario, Canada) (SOSP ’19). Association for Computing Machinery, New York, NY, USA, 524–537. doi:10.1145/3341301.3359634 [46] Rex Ying, Ruining He, Kaifeng Chen, Pong Eksombatchai, William L. Hamilton, and Jure Leskovec. 2018. Graph Convolutional Neural Networks for Web-Scale Recommender Systems. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining (London, United Kingdom) (KDD ’18). Association for

Computing Machinery, New York, NY, USA, 974–983. doi:10.1145/ 3219819.3219890 [47] Hanqing Zeng, Hongkuan Zhou, Ajitesh Srivastava, Rajgopal Kannan, and Viktor Prasanna. 2020. GraphSAINT: Graph Sampling Based Inductive Learning Method. In International Conference on Learning Representations. https://openreview.net/forum?id=BJe8pkHFwS [48] Lei Zou, Fan Zhang, Yinnian Lin, and Yanpeng Yu. 2023. An efficient data structure for dynamic graph on GPUs. IEEE Transactions on Knowledge and Data Engineering 35, 11 (2023), 11051–11066.

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

Analyze & explore related research in Conceptio

Related documents