acceptodds
Under review as a conference paper at ICLR 2027

Faster Generalized Message Passing with Skew-Aware Parallelism and Work Partitioning

Abstract

Graph neural networks (GNNs) are built from sparse operations that gather and aggregate features along the edges of a graph, and on GPUs their speed is limited by memory access and parallelism rather than by arithmetic. IO-aware kernels remove most of the data movement, yet still leave much of the GPU idle on real graphs and cover only a few fixed layers. We show that the remaining bottleneck is how work is partitioned: degree distributions are heavy-tailed, so a kernel that gives every node one unit of parallel work waits on its few highest-degree nodes while the rest of the device idles. We, therefore, make GNN kernels degree-aware. First, nodes are bucketed by degree, extending a technique of prior IO-aware kernels, then reordered within each bucket and processed concurrently, so that long jobs start first and short ones fill the idle capacity. Second, the heaviest neighborhoods are cut into fixed-size edge slices that are merged exactly, and per-edge computations are partitioned over edges entirely. Third, data is loaded asynchronously wherever there is computation to overlap it. We bring these techniques to the two generalized message-passing primitives, gSpMM and gSDDMM, and provide them as a portable library of and kernels with autograd, from which arbitrary GNN convolutions can be composed in pure PyTorch. Against DGL, a widely used and efficient graph learning library, we achieve speedup for GATv2, speedup for gSDDMM, and for gSpMM in the median over thousands of configurations, reaching on and on . Our implementations are also faster than PyG and can process graphs which cause other libraries run out of memory. Against prior IO-aware kernels, they are faster in the median and on the most skewed graph.

Primary area:
infrastructure, software libraries, hardware, systems, etc.
Keywords:
Graph Neural Networks, GPU, CUDA

Reviews

Among:
Shape:
1234this paper, Top 4%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.33 over 3 reviews, above 96% of the others.
Reviewer_DRDoOpenReview ↗
Rating
3
Confidence
2
Informativeness
3(+1)
Presentation
3
Soundness
3
Read review
Paper summary

This paper presents a memory-aware and workload-aware partitioning method for GNN training on GPUs. The main motivation lies in the imbalance in memory-access workloads. Due to the imbalance of node degrees, some nodes will access memory much more frequently than others, leading to straggler effects. The authors present two levels of optimization. The first is a scheduling-level one, which partitions all nodes into bins and work concurrently on the GPU. In each bin, nodes are ordered according to workloads. The second is a kernel-level one that accelerates kernel memory access, including staging, wide memory access, bank conflict avoidance, etc.

The authors experiment with 16 real-world graphs with different properties to show the improvements of the proposed method on attention kernels, where each individual technique achieves positive improvements where it should, in a well-interpreted manner. The authors also implement the proposed methods as general primitives that support a wide range of GNNs and outperform current open-source implementations like DGL.

Critical strengths

Overall, I find the paper to be technically sound, well-motivated, and well-written.

  1. This paper is well-written and easy to follow. As someone who is not very familiar with GPU kernels, I find the presentation to be sufficiently clear for me to follow. Each design point is well-motivated by observed facts (which are easy to follow too).

  2. The techiniques are used in a way that is simple and clearly addresses each observed weakness. The main motivation of this paper is that the IO-based workloads are highly imbalanced in GNN training, and the techniques are designed to address that: binning, largest workload first, concurrency, further paralllelizing the heavy bin. Further, the proposed kernel-level optimizations are designed to help in cases where the workloads of each edge/the whole graph become too large. The designs are easy to follow.

  3. The experimental results are extensive and, more importantly, coincide well with what the techniques expect. I briefly checked the correlations between the improvements of each technique and how it is supposed to, and they align well. For example, for bucketing, it should work where the tail workload is heaviest, and async mainly works on extremely large graphs (larger than L2). This good alignment enhances the technical soundness of the paper.

Critical weaknesses
  1. How the optimized g-SPMM and g-SDDMM dominate training time is unknown/not reported in the paper. The authors motivate the paper based on model training, but only report kernel-level speedups. To remedy this, the authors can report some (not necessarily all) end-to-end training speedups, or show a decomposition of the end-to-end training time (this can show how much time the attention kernels occupy, and deduce the end-to-end speedups).

  2. Scope is slightly limited --- but not much. I specifically have two additional scenarios where the authors can discuss. The first is sampling techniques --- e.g. neighbor sampling, subgraph sampling, etc. In this case (which may be the norm for further large graphs), will the improvements of this paper diminish? The second is about distributed GNN training on multiple GPUs or nodes (e.g. where the graph is larger than ogbn-products), where the bottleneck may lie in communication rather than memory access. It is not a big scope limitation but the authors can briefly discuss them.

  3. One minor question on the design of bucketing --- I suppose that degree ordering should have something to do with "the imbalance within a bucket". In this case, is it possible to spawn even more buckets, instead of scheduling within an bucket?

Questions for authors

See weaknesses 1-3.

6 comments
AuthorsOpenReview ↗

Authors' Response Part 1/3

Thank you for your insightful review and for finding the paper technically sound, well-motivated and well-written. We address your questions and concerns below.

1. How the optimized g-SPMM and g-SDDMM dominate training time is unknown/not reported in the paper. The authors motivate the paper based on model training, but only report kernel-level speedups. To remedy this, the authors can report some (not necessarily all) end-to-end training speedups, or show a decomposition of the end-to-end training time (this can show how much time the attention kernels occupy, and deduce the end-to-end speedups).

Thank you for this suggestion. We now report both the decomposition and the end-to-end speedups. To decompose the training time, we profiled a full-graph training step of a GATv2 model implemented in three ways: with DGL's primitives, with our g-SDDMM, edge_softmax and g-SPMM primitives, and with our fused GATv2 kernel. We present the breakdown in Table 3 in General Response [GR4]. In DGL's training step on ogbn-arxiv, which takes 117 ms on H100, g-SPMM takes 26.6 ms in the forward and 32.3 ms in the backward pass, g-SDDMM takes 6.7 and 3.7 ms, and the per-edge elementwise operations between them take 9.6 and 26.9 ms. Together, these operators account for about 90%90\% of the step, so the attention kernels dominate training time, as you expected.

This decomposition also explains the end-to-end speedups. Replacing only DGL's primitives with ours makes the step 1.43×1.43\times faster. Our fused GATv2 kernel replaces all of them with 5.5 ms of forward and 14.3 ms of backward kernel time, which makes the step 4.27×4.27\times faster than DGL (3.44×3.44\times on A100) and uses 3.7×3.7\times less energy. Nsight Compute shows why DGL is slow: its edge_softmax reductions run at 11%11\% achieved occupancy and 0.5%0.5\% SM throughput, because individual threads wait on high-degree rows. This is the imbalance our degree-aware partitioning removes. End to end, full-graph training is 4.4×4.4\times faster on H100 and 3.6×3.6\times faster on A100 on the graph where DGL fits, and DGL runs out of memory on the other 11 graphs, as described in General Response [GR3]. With neighbor sampling, the median speedup is 1.62×1.62\times on H100 and 2.50×2.50\times on A100, as described in General Response [GR1]. We will add this decomposition and the end-to-end results to the revised paper.

AuthorsOpenReview ↗

Authors' Response Part 2/3

2.1 Scope is slightly limited --- but not much. I specifically have two additional scenarios where the authors can discuss. The first is sampling techniques --- e.g. neighbor sampling, subgraph sampling, etc. In this case (which may be the norm for further large graphs), will the improvements of this paper diminish?

The improvements become smaller but remain substantial. With neighbor sampling, our implementation is still faster than the fastest DGL sampling mode by 1.62×1.62\times on H100 and 2.50×2.50\times on A100 in the median, and by up to 4.1×4.1\times for deeper models, while DGL runs out of memory in the deepest setting on the two largest graphs. We provide full details in General Response [GR1]. When every node takes its full neighborhood, the speedups are larger, up to 4.17×4.17\times, and DGL runs out of memory in 18 of 24 settings, as we show in General Response [GR2].

Subgraph sampling methods such as GraphSAINT [1] and Cluster-GCN [2] train on induced subgraphs, which our kernels process exactly like full graphs, so the full-graph results of General Response [GR3] apply to each such subgraph.

We also checked whether degree-aware partitioning remains effective on sampled subgraphs. With a fixed fanout, sampling caps the in-degree of every destination node, so the forward pass of a mini-batch has almost no load imbalance: in a block sampled with fanouts 15-10-5, the highest-degree node has at most 2.6 times more neighbors than the average node, against up to 42K times in the full graphs. The imbalance moves to the backward pass, where a hub node sampled by many destinations becomes one long row of the transposed block, 188 to 400 times longer than the average row on avazu-ctr, twitch-views and the web graphs. Applying the heavy bucket to the backward pass makes the backward kernels 1.181.18-2.63×2.63\times faster in 11 of 12 such settings with fanouts 25 and 50, and has no effect on the low-skew ogbn-products. With full neighborhoods, the batches keep the skew of the graph, and bucketing makes training 4.34.3-5.5×5.5\times faster on the web graphs than the same kernels without it. The improvements of the paper therefore carry over to sampled training as long as the partitioning is applied where the sampled block is skewed. Table 6 in our response to Reviewer jfM5 gives the per-graph numbers.

[1] Hanqing Zeng, Hongkuan Zhou, Ajitesh Srivastava, Rajgopal Kannan, and Viktor Prasanna. GraphSAINT: Graph Sampling Based Inductive Learning Method.

[2] Wei-Lin Chiang, Xuanqing Liu, Si Si, Yang Li, Samy Bengio, and Cho-Jui Hsieh. Cluster-GCN: An Efficient Algorithm for Training Deep and Large Graph Convolutional Networks.

*2.2 The second is about distributed GNN training on multiple GPUs or nodes (e.g. where the graph is larger than ogbn-products), where the bottleneck may lie in communication rather than memory access. It is not a big scope limitation but the authors can briefly discuss them.

We did not run multi-GPU experiments, but our kernels apply to distributed training without modification. Distributed full-graph training systems usually split the graph into partitions, and each device runs the same layer kernels on its local partition as on a single GPU. For instance, one can use a vertex cut: every edge belongs to exactly one partition, the vertices on the cut are replicated on every partition that contains their edges, and the partial aggregates of the replicas are combined by communication, which is also how their gradients are accumulated in the backward pass [3]. The aggregation inside each partition is exactly the g-SPMM and g-SDDMM work that our kernels accelerate. Communication is therefore performed outside the kernels and remains orthogonal to the computation we optimize. Moreover, faster local computation leaves more time to overlap it where it becomes the bottleneck.

Our memory savings are also useful in this setting. A smaller per-GPU footprint allows larger partitions per GPU, and therefore fewer GPUs and fewer cut edges, or leaves more memory for communication buffers and feature caches. For example, our fused kernel trains GATv2 on the full ogbn-products graph on a single 80 GB GPU, while DGL fails with a single allocation of 120 GiB, as described in General Response [GR3].

[3] Vasimuddin Md, Sanchit Misra, Guixiang Ma, Ramanarayan Mohanty, Evangelos Georganas, Alexander Heinecke, Dhiraj Kalamkar, Nesreen K. Ahmed, and Sasikanth Avancha. DistGNN: Scalable Distributed Training for Large-Scale Graph Neural Networks.

AuthorsOpenReview ↗

Authors' Response Part 3/3

3. One minor question on the design of bucketing --- I suppose that degree ordering should have something to do with "the imbalance within a bucket". In this case, is it possible to spawn even more buckets, instead of scheduling within a bucket?

Thank you for suggesting this experiment. Finer buckets reduce the variation of degrees within each bucket, while degree ordering starts the highest-degree nodes first and shortens the tail of the launch. More buckets are harder to implement, however: each degree range needs its own work decomposition and warp allocation, and every extra bucket adds a kernel launch.

To evaluate the idea, we extended the SM-utilization simulator from Section 4.3 to more than two buckets, with costs calibrated on the A100 for the GATv2 forward pass (fp32, one head of width 128), and ran it on all 16 graphs of the paper. We varied three things:

  1. The total number of buckets BB, including the heavy ones, is 2, 4 or 8.
  2. The bucket boundaries follow one of three policies. quantile keeps the heavy bucket of the paper (nodes above the 99th percentile of degree) and splits the light nodes into B−1B-1 buckets of roughly equal size. log keeps the same heavy bucket and splits the light degree range into B−1B-1 intervals equally spaced in log⁡(1+d)\log(1 + d), where dd is the node degree. tail also splits the heavy nodes, with finer quantiles towards the highest degrees, e.g. at the 90th, 99th and 99.9th percentiles for B=4B=4. Nodes of equal degree always share a bucket.
  3. Degree ordering is on or off, and the buckets are launched either sequentially on one CUDA stream, as in TurboGNN, or concurrently on separate streams with the heaviest one first, as introduced in Section 3.1.

The per-node work and the resources of each bucket stay fixed, so only the partitioning changes. For each graph, we report in Table 8 the best of the 6 configurations with B=4B=4 or B=8B=8 and the effect of ordering with B=2B=2.

graphconcurrent: more bucketsconcurrent: orderingsequential: more bucketssequential: ordering
artnet-exp+7.09+7.27-1.61+10.22
avazu-ctr0.000.00-0.13+0.71
citeseer0.000.00-0.64+0.85
city-reviews0.000.00-0.04+1.51
city-roads-L+0.12+0.120.00+0.85
city-roads-M+0.22+0.220.00+0.44
cora0.000.00-0.49+0.70
hm-categories-10.150.00-1.72+0.63
ogbn-arxiv0.000.00-0.01+0.41
ogbn-products+0.19+0.19-0.02+3.40
ogbn-proteins+1.04+1.30-0.22+4.93
pokec-regions+0.05+0.05-0.04+0.05
pubmed+2.74+2.74-0.34+3.92
tolokers-20.000.00-0.61+15.94
twitch-views+4.99+4.99-0.08+3.33
web-fraud0.000.000.000.00

Table 8: Simulated runtime reduction in % relative to B=2B=2 without ordering, for the GATv2 forward pass on A100, so a positive value means faster. "More buckets" is the best of the 6 configurations with B=4B=4 or B=8B=8 without ordering, and "ordering" is the effect of degree ordering with B=2B=2.

Thus, the results answer your question directly. With concurrent launch, more buckets help on some graphs, by up to 7.09%7.09\% on artnet-exp and 4.99%4.99\% on twitch-views, but every configuration slows down hm-categories, by 1010-39%39\%. Ordering with only two buckets gives the same or a larger gain on every graph, and once ordering is enabled, additional buckets improve the runtime by less than 0.01%0.01\%. With sequential launch, additional buckets never help and the worst configurations more than double the runtime, while ordering alone gains up to 15.94%15.94\% on tolokers-2. No tested configuration with more buckets and no ordering is faster than two ordered buckets. Degree ordering therefore already captures the benefit that finer buckets would bring without extra kernel launches.

The table also shows where degree ordering matters. Namely, on the graphs with the strongest hubs, such as web-fraud, ogbn-arxiv and avazu-ctr, neither ordering nor more buckets changes the runtime with concurrent launch, because the heavy bucket already spreads the hub neighborhoods over many parallel workloads, so the thread blocks are close to uniform in size. Degree-aware partitioning thus subsumes ordering on strongly skewed graphs, and ordering pays mainly on graphs with a moderate tail, such as artnet-exp, twitch-views and pubmed.

We acknowledge that the simulations omit the cost of partitioning, sorting and extra kernel launches, which all count against more buckets, and do not retune per-bucket resources. This is also the strength of the simulator: it evaluates a design such as finer bucketing directly from the degree distribution of each graph, without developing a specialized kernel for every degree range. We will add this analysis to the revised paper.

Reviewer_PSDmOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

this work proposes a set of technologies that optimize the performance of message passing for graph neural networks. Authors identify the bottlenecks on skewed graphs and propose a skew aware scheduling. Experiments show this work achieves up to 23x speedup over DGL and 12.7x speedup over prior optimized io-aware approach.

Critical strengths

This work focus on a realistic problem, accelerating the message passing of graph neural networks when the graph is skewed.

Experiments show this work achieves significant speedup compared with widely used DGL.

Critical weaknesses
  1. the generalization capability is unclear. Authors tested only on one GPU. It is unclear how the approach performs when the memory, stream, thread and warp vary.

  2. authors reported they performed an exhaustive sweep to find best config. Though this is ok for evaluation to understand the best performance it can achieve. This work also frames as a portable library and a replacement of dgl.ops. It is important to understand the sensitivity with respect to different configs; however, this paper does not analyze the sensitivity of the kernels to suboptimal configs. It is desirable to see that this work still can achieve reasonably good improvement on various datasets with some empirical configs or configs determined by some heuristics.

  3. The presentation of Section 3 reads more like a disjointed technical manual than a cohesive academic paper. It lacks a system-level overview explaining how the disparate components integrate into a unified execution pipeline. The individual techniques such as degree bucketing, ordering, concurrent launch, and edge slicing are presented sequentially as disjointed mechanisms without a unifying framework to explain their logical interactions. In addition, the structural hierarchy of sec 3.1 may need improvement. For example, "Warps per bucket" is a hardware-level tuning detail for SM, but it is presented in parallel with core mechanisms like concurrent stream launching and edge slicing.

  4. Table reports forward and backward of copy u sum, but only report forward copy u max. This shall not be omitted.

  5. End to end time consumption is not reported.

Questions for authors
  1. Is presented method robust to suboptimal configs? when a config is not the optimal found by sweep, will it still provide reasonably good improvement?

  2. why is the copy u max backward in table 2 omitted?

  3. How about the end to end training/inference time with proposed work?

6 comments
AuthorsOpenReview ↗

Authors' Response Part 1/3

Thank you for your detailed review and concrete suggestions. We address your questions and concerns below.

1. The generalization capability is unclear. Authors tested only on one GPU. It is unclear how the approach performs when the memory, stream, thread and warp vary.

We understood this as a question about other GPU architectures, which differ in memory system, number of SMs and warp scheduling. Section 4 of the paper argues that our results carry over to Hopper, because the imbalance comes from the scheduling strategy rather than the architecture: for example, on Hopper, as on Ampere, a thread block holds its slot until its slowest warp completes, and the same holds for Blackwell GPUs. We have now measured this on an H100, as described in General Response [GR5]. In the configuration of Table 1 of the paper, our GATv2 kernel is 20.8×20.8\times faster than DGL and 13.2×13.2\times faster than PyG in the median, and each technique still contributes, with 2.33×2.33\times over TurboGNN in total. For g-SPMM, the median speedup over DGL is 1.62×1.62\times for the copy_u_sum forward pass and 2.66×2.66\times for the copy_u_max forward pass, and the copy_u_sum medians are close to the A100 results in the paper. Tables 4 and 5 in General Response [GR5] list every graph. All end-to-end, full-graph and profiling experiments in General Response [GR1]-[GR4] were also run on both GPUs, and the speedups hold on both. Our results are therefore not specific to the A100.

The architecture-dependent parameters, such as the number of warps per bucket and the staging depth, are selected per device by the autotuner, which we discuss in the answer to point 2. We did not extend the comparison to the newer Blackwell GPUs, because the DGL baseline cannot run there: Blackwell requires CUDA 12.8 and PyTorch 2.7 or later, while the latest DGL release, 2.4, is built for PyTorch 2.4. This is the version lock we mention in Section 1 of the paper as an obstacle to adopting DGL on current software stacks.

If your question referred to multi-GPU training, please see our response to Reviewer DRDo.

AuthorsOpenReview ↗

Authors' Response Part 2/3

2. Authors reported they performed an exhaustive sweep to find best config. Though this is ok for evaluation to understand the best performance it can achieve. This work also frames as a portable library and a replacement of dgl.ops. It is important to understand the sensitivity with respect to different configs; however, this paper does not analyze the sensitivity of the kernels to suboptimal configs. It is desirable to see that this work still can achieve reasonably good improvement on various datasets with some empirical configs or configs determined by some heuristics.

We agree that this matters for a library meant to replace dgl.ops, so we compared two ways of choosing the kernel configuration. The first is the default configuration of our library, used without any tuning. The second is the built-in autotuner, which runs 50 trials of Optuna's TPE sampler. We measure the forward pass of the full GATv2 layer, including its linear projections, in fp16 with 2 heads of width 128, on 16 representative graphs and on both H100 and A100, with the median of 3 runs. We present the results in Table 7.

Without autotuning, our default configuration is already 9.9×9.9\times faster than DGL on H100 and 7.6×7.6\times on A100, and the autotuner raises this to 13.2×13.2\times and 9.6×9.6\times, in the geometric mean over the 12 graphs where DGL fits. It improves on the default on every graph except pubmed on A100 (0.98×0.98\times, within noise), most of all on skewed graphs: up to 2.1×2.1\times on ogbn-arxiv and 3.3×3.3\times on web-fraud. We note that these speedups are lower than in Table 4 in General Response [GR5] because here we time the whole layer, whose dense projections cost the same in both libraries.

Section 5 of the paper also points to a heuristic that needs no sweep at all, namely to run our scheduling simulator when a graph is loaded and choose the partitioning from its degree distribution.

graphH100, defaultH100, autotunerA100, defaultA100, autotuner
artnet-exp12.05x12.88x7.44x8.03x
avazu-ctr12.81x19.11x9.62x12.75x
citeseer9.64x11.14x8.70x8.97x
city-reviews9.79x13.70x7.01x9.64x
city-roads-L5.16x8.43x3.67x5.59x
city-roads-M10.39x11.70x5.73x7.20x
cora6.90x7.18x8.07x8.30x
hm-categories13.80x18.22x10.33x12.66x
ogbn-arxiv8.88x18.97x6.78x12.91x
ogbn-productsDGL OOM (ours 46.6 ms)DGL OOM (ours 36.6 ms)DGL OOM (ours 88.3 ms)DGL OOM (ours 64.2 ms)
ogbn-proteinsDGL OOM (ours 17.6 ms)DGL OOM (ours 16.4 ms)DGL OOM (ours 35.7 ms)DGL OOM (ours 30.3 ms)
pokec-regionsDGL OOM (ours 13.2 ms)DGL OOM (ours 10.6 ms)DGL OOM (ours 25.5 ms)DGL OOM (ours 19.2 ms)
pubmed9.19x10.00x9.36x9.22x
tolokers-211.72x16.34x9.51x11.22x
twitch-views12.07x18.14x8.36x12.10x
web-fraudDGL OOM (ours 26.5 ms)DGL OOM (ours 8.0 ms)DGL OOM (ours 40.1 ms)DGL OOM (ours 16.8 ms)
geometric mean9.87x13.17x7.62x9.59x

Table 7: Speedup over DGL of a GATv2 layer built with our kernels, with the default configuration and after autotuning (forward pass, fp16, 2 heads of width 128, median of 3 runs). Where DGL runs out of the 80 GB of GPU memory (DGL OOM), we give the runtime of our layer instead. Geometric means are taken over the 12 graphs on which DGL fits.

Our kernels therefore do not depend on the exhaustive sweep. The default configuration alone is already 7.67.6-9.9×9.9\times faster than DGL and reaches 7575-79%79\% of the tuned speedup, while the autotuner recovers the rest, mostly on the skewed graphs where the configuration matters most.

AuthorsOpenReview ↗

Authors' Response Part 3/3

3. The presentation of Section 3 reads more like a disjointed technical manual than a cohesive academic paper. It lacks a system-level overview explaining how the disparate components integrate into a unified execution pipeline. The individual techniques such as degree bucketing, ordering, concurrent launch, and edge slicing are presented sequentially as disjointed mechanisms without a unifying framework to explain their logical interactions. In addition, the structural hierarchy of sec 3.1 may need improvement. For example, "Warps per bucket" is a hardware-level tuning detail for SM, but it is presented in parallel with core mechanisms like concurrent stream launching and edge slicing.

Thank you for this suggestion. We agree that Section 3 should first present the principle that connects the techniques, and we will open it with this overview in the revised version. Following the scheduling model of Section 4.3, the runtime of a launch is set by how fully the SMs are occupied and by the longest single block, the critical path. Degree bucketing, ordering within a bucket and concurrent launch of the buckets raise occupancy: heavy rows receive more warps, long jobs start first, and light rows fill the slots that heavy rows leave idle. Edge slicing shortens the critical path by cutting the heaviest neighborhoods into pieces, which no rebalancing can do. Asynchronous staging lowers the cost of each edge and is independent of the schedule. The techniques therefore build on each other: ordering and edge slicing operate within buckets, concurrent launch requires at least two buckets, and the number of warps per bucket is a parameter of bucketing rather than a separate mechanism. We will restructure Section 3.1 accordingly, presenting the core mechanisms first and the tuning parameters, including warps per bucket, in a separate paragraph. We note that Reviewer DRDo found the paper "well-written and easy to follow", but we agree that this structure will make Section 3 clearer.

4. Table reports forward and backward of copy u sum, but only report forward copy u max. This shall not be omitted.

Thank you for noticing this. Because of space limits, Table 2 of the paper shows only part of the measurements. The backward pass of copy_u_max, together with every other operator, reducer, width and pass, is reported for all 16 graphs in Table 8 in Appendix K.3 of the paper, and we will reference it from Table 2. Our new measurements include the copy_u_max backward pass directly, as shown in Table 5 in General Response [GR5]. This pass only routes each gradient to the stored maximum, which leaves little work to balance, so our kernel is on par with DGL there (1.00×1.00\times in the median) and 16.5×16.5\times faster than PyG. Section 5 of the paper names fusing this pass as one of the two known gaps.

5. End to end time consumption is not reported.

We now report end-to-end training time with and without sampling, and inference time, on large graphs and two GPUs, as described in General Response [GR1]-[GR3]. With neighbor sampling, our implementation is faster than DGL by 1.62×1.62\times on H100 and 2.50×2.50\times on A100 in the median, and with 5 layers on ogbn-products and pokec-regions DGL runs out of memory while ours trains successfully. In full-graph training, DGL runs out of memory on 11 of the 12 graphs, and on the remaining one our implementation is 4.4×4.4\times faster. End to end, our kernels therefore speed up training both with and without sampling, and they train on graphs where DGL runs out of memory. General Response [GR4] also breaks a training step down by operator and shows that the sparse operators take about 90%90\% of DGL's step. We will add these end-to-end results to the revised paper.

Reviewer_jfM5OpenReview ↗
Rating
4(+2)
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper proposes a generalized message passing library for GNNs with highly optimized performance kernels. The paper analyzes the core issues of the existing message-passing kernels on PyG/DGL and introduces adequate approaches to address them. While these approaches are somewhat straightforward for the graph domain and kernel optimization, the reviewer believes this means the proposed library is highly practical. With those mitigations for the current PyG/DGL kernel limitations, this paper achieves up to 12.7x speedup.

Critical strengths

[S1] This paper proposes a highly practical library. The reviewer really enjoyed reading this paper because few people have recently worked on kernel optimizations for GNN kernels. (Of course, this is particularly related to some issues, which I mentioned in the weaknesses)

[S2] The approaches are adequate but somewhat straightforward for graph and kernel expertise.

Critical weaknesses

[W1] While the kernel time improvement is important in the domain, in recent large graph GNN training/inference, the sampler time often dominates the end-to-end time. If some detailed experiments, including E2E large-graph training/inference with mini-batch sampler overhead, are included, the reviewer believes the paper would be clearer and more plausible.

Questions for authors

I really enjoyed reading this paper, and I thank the authors for their efforts on this GNN message-passing kernel improvement. I really appreciate the efforts to improve the message-passing kernels.

My only concern is showing the E2E training/inference results with the subgraph sampler (especially with the minibatch sampler) on a large graph. Of course, I acknowledge that for the kernel paper the kernel time is important, but if those experiments/analyses are included, I believe that would make the paper stronger.

Also, this question is important because mini-batch neighbor sampling changes the degree distribution of the computation graph. Does the proposed degree-aware work partitioning remain effective when operating on dynamically generated mini-batch subgraphs, rather than the original graph?

This is my only concern. If the authors integrate/address those results, I'll raise my score.

6 comments
AuthorsOpenReview ↗

Authors' Response Part 1/2

Thank you for your enlightening review! We appreciate your expertise. We agree that a kernel speedup matters to practitioners only if it survives the full training pipeline, including the sampler, and we ran the experiments you asked for. They are described in General Response [GR1]-[GR3], and we summarize the answers to your questions below.

W1 While the kernel time improvement is important in the domain, in recent large graph GNN training/inference, the sampler time often dominates the end-to-end time. If some detailed experiments, including E2E large-graph training/inference with mini-batch sampler overhead, are included, the reviewer believes the paper would be clearer and more plausible. Q1 My only concern is showing the E2E training/inference results with the subgraph sampler (especially with the minibatch sampler) on a large graph. Of course, I acknowledge that for the kernel paper the kernel time is important, but if those experiments/analyses are included, I believe that would make the paper stronger.

We built a complete mini-batch training pipeline for GATv2 on our kernels, with our own GPU neighbor sampler, and measured the full epoch time, sampling included, against all three sampling modes of DGL on graphs with up to 1.3×1081.3 \times 10^{8} edges and on two GPUs. As reported in General Response [GR1], our implementation is faster than the fastest DGL configuration by 1.62×1.62\times on H100 and 2.50×2.50\times on A100 in the median, and with 5 layers on ogbn-products and pokec-regions DGL runs out of memory while ours trains successfully. Test metrics of the two implementations agree within the variation between seeds. For inference, our layer-wise inference over full neighborhoods is 2.732.73-5.93×5.93\times faster than DGL, as also reported in General Response [GR1]. When every seed takes its full neighborhood, DGL fits into 80 GB in only 6 of 24 settings, and our training step is faster in all 6, as shown in General Response [GR2]. Without any sampling, DGL runs out of memory on 11 of the 12 graphs, while our fused kernel trains on all of them and is 4.4×4.4\times faster on the one graph where DGL fits, as described in General Response [GR3].

Regarding the sampler overhead, we measured how long the training loop waits for the next batch. With our sampler the median wait is a negligible 0.02 ms per step, because the next batch is prepared on the GPU while the current one trains. DGL's GPU sampler adds 7.9 ms per step in the median. Your concern is still valid for very large neighborhoods. With fanout 50 per layer on ogbn-products, our training loop waits 129 ms per step for 108 ms of computation, so sampling dominates the step. In most such settings, however, DGL does not fit into memory at all. The kernel speedups of the paper therefore survive end-to-end mini-batch training: with a sampler that overlaps with the computation, our implementation stays faster than DGL on both GPUs and trains in settings where DGL runs out of memory. We will add these end-to-end results, including the sampler overhead, to the revised paper.

AuthorsOpenReview ↗

Authors' Response Part 2/2

Q2 Also, this question is important because mini-batch neighbor sampling changes the degree distribution of the computation graph. Does the proposed degree-aware work partitioning remain effective when operating on dynamically generated mini-batch subgraphs, rather than the original graph?

This is an important question, and the answer depends on where the sampled block is skewed. We measured the degree distribution of the sampled blocks and the effect of degree-aware partitioning on them, and present the results in Table 6.

With a fixed fanout, sampling caps the in-degree of every destination node, so the forward pass of a mini-batch has almost no load imbalance. In the full graphs from the paper, the highest-degree node has up to 42K times more neighbors than the average node. In a block sampled with fanouts 15-10-5, it has at most 2.6 times more, and no node exceeds the heavy threshold of the full graph.

The forward pass therefore has little imbalance left for degree-aware partitioning to remove, and all nodes fall into the light bucket. The imbalance does not disappear, however, as it moves to the backward pass -- a hub node that many destinations sample becomes one long row of the transposed block, and on avazu-ctr, twitch-views and the three web graphs this row is 188 to 400 times longer than the average row. On web-traffic the longest row has 713 edges, while the 99th percentile is 11.

We therefore apply the heavy bucket to the backward pass, assigning to it the rows with at least 64 sampled edges. Over 3 repeats on both GPUs, this makes the backward kernels 1.181.18-2.63×2.63\times faster in 11 of 12 high-skew settings with fanouts 25 and 50, and it has no effect on ogbn-products, where the backward blocks are not skewed. Degree ordering within a bucket adds little here, so the gain comes from the split into buckets. With full neighborhoods, the blocks keep the skew of the full graph, where the highest-degree node has up to 940 times more neighbors than the average node, and bucketing makes training 4.34.3-5.5×5.5\times faster on the web graphs than the same kernels without it, as we report in General Response [GR2].

graphfwd skew (max / mean in-degree)bwd skew (max / mean out-degree)bwd speedup, fanout 25, H100 / A100bwd speedup, fanout 50, H100 / A100
avazu-ctr1.051881.18x / 1.19x1.26x / 1.78x
ogbn-products1.01331.02x / 1.00x1.02x / 1.01x
twitch-views1.022521.25x / 1.27x1.18x / 1.36x
web-traffic1.843751.01x / 1.19x1.40x / 2.63x

Table 6: Degree skew of sampled blocks and the effect of the backward heavy bucket. Skew is the ratio of the largest to the average node degree in a block (1.0 means all nodes have the same degree), for fanouts 15-10-5, averaged over 5 batches of 1024 seeds and all layers. Speedups compare the backward GPU time per step with and without the heavy bucket, for fanout 25 or 50 in each of 3 layers (median of 3 repeats).

Degree-aware partitioning therefore remains effective on sampled subgraphs, provided it is applied where the sampled block is skewed: in the backward pass for fixed fanouts, and in both passes for full neighborhoods. We will add this analysis to the revised version of the paper, thank you for pointing it out!

Reviewer_jfM5OpenReview ↗

Comment regarding remaining concerns

Dear authors,

I carefully read the rebuttal and really appreciate the detailed response.

The rebuttal partially addressed my concern, but I still have two concerns.

  1. Would the authors add ogbn-papers to the rebuttal dataset?
  • The current datasets are a bit small to run on recent GPUs such as H100. Considering that minibatch training is for running larger graphs such as ogbn-papers (100M-sized), I recommend adding this dataset to the rebuttal dataset.
  • This is important because, practically, the minibatch sampling overhead can be different on such a large dataset.
  • For this, a 3-layer setup (e.g., 15-10-5) is ok, because a 5-layer setup can easily face OOM due to neighbor explosion.
  1. Would the authors promise to incorporate the e2e/mini-batch sampling rebuttal items into the main body?
  • Since these rebuttal items are quite critical to practical users, I recommend that the authors add a summary of these results in the main body.
  • In other words, would you upload the revised paper PDF?

Thanks again for the rebuttal. If the authors address the above, I have no remaining concerns and will raise my score a lot (i.e., 4: clear acceptance).

Comments on the paper

4 comments
AuthorsOpenReview ↗

General Response Part 4/4

We continue [GR5] here.

Table 5 reports the g-SPMM operators copy_u_sum and copy_u_max, now including the copy_u_max backward pass that Table 2 of the paper leaves out. In the forward pass, our kernels are faster than DGL on all 16 graphs for copy_u_max and on 14 graphs for copy_u_sum. The median speedups for copy_u_sum are 1.62×1.62\times forward and 1.57×1.57\times backward, close to the A100 numbers in the paper, and 2.66×2.66\times for the copy_u_max forward pass. The speedups grow with graph size and reach 4.7×4.7\times. The copy_u_max backward pass is on par with DGL, because it only routes each gradient to the stored maximum and leaves little work to balance. PyG is 7.97.9-16.5×16.5\times slower than our kernels in the median.

graphcopy_u_sum fwd, DGLcopy_u_sum fwd, ourscopy_u_sum bwd, DGLcopy_u_sum bwd, ourscopy_u_max fwd, DGLcopy_u_max fwd, ourscopy_u_max bwd, DGLcopy_u_max bwd, ours
artnet-exp0.1010.083 (1.22x)0.1280.105 (1.22x)0.1820.103 (1.76x)0.1520.148 (1.03x)
avazu-ctr12.52.76 (4.51x)12.32.71 (4.53x)15.53.28 (4.73x)42.00.278 (151x)
citeseer0.0380.033 (1.16x)0.1250.106 (1.18x)0.1740.035 (4.91x)0.1840.138 (1.33x)
city-reviews1.620.422 (3.85x)1.640.426 (3.84x)2.170.540 (4.02x)0.2710.327 (0.83x)
city-roads-L0.1920.244 (0.79x)0.1910.240 (0.80x)0.3300.284 (1.16x)0.1860.193 (0.97x)
city-roads-M0.0620.065 (0.95x)0.1240.107 (1.16x)0.1430.090 (1.58x)0.1410.155 (0.91x)
cora0.0410.033 (1.24x)0.1580.098 (1.61x)0.0730.034 (2.14x)0.1580.083 (1.90x)
hm-categories5.731.61 (3.55x)6.311.63 (3.87x)7.162.25 (3.18x)0.1800.191 (0.94x)
ogbn-arxiv2.850.669 (4.26x)0.3220.253 (1.28x)3.670.828 (4.44x)0.2340.324 (0.72x)
ogbn-products23.914.0 (1.71x)23.914.0 (1.71x)31.715.7 (2.02x)11.013.3 (0.82x)
ogbn-proteins7.164.67 (1.53x)7.194.73 (1.52x)8.936.16 (1.45x)0.6160.725 (0.85x)
pokec-regions6.134.12 (1.49x)6.144.13 (1.49x)8.824.78 (1.85x)4.525.87 (0.77x)
pubmed0.0400.034 (1.19x)0.1460.107 (1.36x)0.0750.037 (2.02x)0.1930.123 (1.56x)
tolokers-20.3230.105 (3.08x)0.3260.105 (3.12x)0.4240.134 (3.17x)0.1650.153 (1.08x)
twitch-views6.752.06 (3.27x)6.812.05 (3.32x)8.612.60 (3.31x)0.5160.503 (1.03x)
web-fraud63.916.6 (3.84x)29465.4 (4.50x)84.719.3 (4.38x)20.912.1 (1.74x)

Table 5: g-SPMM operators against DGL on H100 on every graph of the suite (d = 128, fp16, median of 3 repeats). Entries are milliseconds with the speedup over DGL in parentheses, and the faster time of each operator is in bold.

The speedups of the paper therefore carry over from the A100 to the H100, both for the fused attention kernel and for the generalized g-SPMM operators.

AuthorsOpenReview ↗

General Response Part 3/4

GR4. Decomposition of the GATv2 training step

Reviewer DRDo asked how much of the training time g-SPMM and g-SDDMM account for. To answer this, we decompose a GATv2 training step into its operators, profile it with torch.profiler and NVIDIA Nsight Compute, and compare DGL's implementation with ours. We test three implementations: DGL with its own g-SDDMM, edge_softmax and g-SPMM primitives, ours with our g-SDDMM, edge_softmax and g-SPMM primitives, and ours with the fused GATv2 kernel.

We use ogbn-arxiv, profile one full-graph training step on H100, and present the results in Table 3. In DGL's step, the sparse operators and the per-edge elementwise operations between them take 106 of 117 ms, about 90%90\% of the step. Replacing only these operators with ours makes the step 1.43×1.43\times faster (1.28×1.28\times on A100). The fused kernel makes it 4.27×4.27\times faster than DGL (3.44×3.44\times on A100) with 4.6×4.6\times less memory. It is also more energy efficient: measured with the NVML energy counter of the GPU, a training step takes 10.2 J with the fused kernel against 38.3 J with DGL, 3.7×3.7\times less energy (3.2×3.2\times on A100).

variantstep (fwd / bwd), msg-SDDMMg-SPMMfused GATv2per-edge elementwiseenergy, J/steppeak memory, GB
DGL primitives117.1 (50.0 / 67.0)6.7 / 3.726.6 / 32.3-9.6 / 26.938.313.4
our primitives82.1 (33.8 / 48.2)2.8 / 4.919.4 / 12.1-9.1 / 19.430.313.5
our fused GATv2 kernel27.4 (8.2 / 19.1)--5.5 / 14.30.9 / 1.510.22.9

Table 3: Profile of one full-graph GATv2 training step on ogbn-arxiv (H100, 3 layers, bf16). Operator columns give forward / backward milliseconds, and the step time also includes 0.1 ms of the optimizer. The fused GATv2 kernel replaces g-SDDMM, edge_softmax and g-SPMM with one kernel, so its time has its own column.

Hardware counters confirm the mechanism. The per-destination reductions inside DGL's edge_softmax take 16 ms of the 50 ms forward pass at 11%11\% achieved occupancy and 0.5%0.5\% SM throughput, as individual threads wait on high-degree rows. This is the imbalance that our degree-aware partitioning removes. On the same graph, our fused forward kernel runs at 39%39\% achieved occupancy and 26%26\% SM throughput and completes the whole attention forward pass in 5.4 ms, less than DGL spends on these reductions alone.

GR5. Kernels on H100

Reviewer PSDm asked whether the results depend on the GPU architecture. Section 4 of the paper argues that they carry over to other architectures such as Hopper, since a thread block there still holds its slot until its slowest warp finishes. We checked this by rerunning Tables 1 and 2 of the paper on an H100 with the same protocol. On GATv2, the median speedup is 20.8×20.8\times over DGL and 13.2×13.2\times over PyG, which run out of memory on 2 and 3 of the 16 graphs, respectively. Against TurboGNN, the median gain is 2.33×2.33\times. On ogbn-arxiv, for example, the forward pass takes 0.48 ms with our kernel, 11.5 ms with DGL and 6.0 ms with PyG. The techniques add up as they do on the A100: on web-fraud, bucketing alone cuts the 117.4 ms of TurboGNN to 22.7 ms, and the full set brings it down to 6.5 ms. We present the per-graph results in Table 4.

graphDGLPyGTurboGNNours
artnet-exp2.282.70 (0.84x)0.218 (10.5x)0.165 (13.8x)
avazu-ctr89.6117 (0.77x)20.6 (4.35x)3.92 (22.9x)
citeseer0.8990.196 (4.59x)0.037 (24.3x)0.017 (52.9x)
city-reviews10.810.5 (1.02x)3.42 (3.15x)0.634 (17.0x)
city-roads-L2.021.88 (1.08x)0.260 (7.78x)0.244 (8.30x)
city-roads-M1.260.919 (1.37x)0.113 (11.2x)0.101 (12.5x)
cora0.9320.222 (4.20x)0.056 (16.6x)0.017 (54.8x)
hm-categories82.195.8 (0.86x)10.6 (7.72x)4.24 (19.3x)
ogbn-arxiv11.55.96 (1.93x)4.85 (2.38x)0.483 (23.9x)
ogbn-productsDGL OOMPyG OOM45.131.0
ogbn-proteinsDGL OOMPyG OOM16.714.0
pokec-regions111PyG OOM12.7 (8.74x)8.72 (12.7x)
pubmed1.100.602 (1.83x)0.087 (12.6x)0.050 (22.0x)
tolokers-24.164.88 (0.85x)0.733 (5.68x)0.229 (18.2x)
twitch-views63.560.1 (1.06x)14.2 (4.46x)2.76 (23.0x)
web-fraud21173.1 (2.89x)117 (1.80x)6.47 (32.6x)

Table 4: GATv2 attention against DGL, PyG and TurboGNN on H100 in the configuration of Table 1 of the paper (forward pass, fp16, median of 3 runs). Entries are milliseconds with the speedup over DGL in parentheses, and the fastest time is in bold. DGL OOM and PyG OOM mark a baseline that runs out of the 80 GB of GPU memory.

AuthorsOpenReview ↗

General Response Part 2/4

GR2. Mini-batch training with full neighborhoods

We next consider mini-batch training with full neighborhoods, in which every seed node takes its complete multi-hop neighborhood and the degree skew of the graph is preserved inside each batch. This setting tests both the memory footprint of each implementation and how our degree-aware partitioning handles skewed batches. We use 12 graphs with 2- and 3-layer networks, which gives 24 settings on each GPU. Ours trains in all 24 within 0.50.5-2525 GB of VRAM, while DGL fits into memory in only 6 of them on both GPUs: ogbn-arxiv with 2 and 3 layers, and pokec-regions, web-fraud, web-topics and web-traffic with 2 layers. In each of these 6 settings our training step is faster. We present all 24 settings in Table 2.

Consequently, degree bucketing makes our training 4.34.3-5.5×5.5\times faster than the same kernels without bucketing on web-* graphs, indicating its clear potential for complex graph structures. This is due to the fact that every mini-batch takes its complete multi-hop neighborhood and the batches preserve the degree skew of the graph.

graph (layers)H100, ours / DGLspeedupA100, ours / DGLspeedup
DGL fits into memory
ogbn-arxiv (2)12.8 / 14.71.16x12.1 / 18.71.55x
ogbn-arxiv (3)18.2 / 38.32.10x14.0 / 50.03.57x
pokec-regions (2)18.6 / 42.32.27x15.5 / 60.63.92x
web-fraud (2)71.3 / 277.13.89x96.0 / 389.34.06x
web-topics (2)66.8 / 270.84.05x89.8 / 374.14.17x
web-traffic (2)69.0 / 279.94.06x97.1 / 385.13.97x
DGL runs out of memory
avazu-ctr (2)61.2 / DGL OOM-96.9 / DGL OOM-
avazu-ctr (3)112.4 / DGL OOM-194.5 / DGL OOM-
hm-categories (2)59.2 / DGL OOM-100.8 / DGL OOM-
hm-categories (3)112.9 / DGL OOM-196.8 / DGL OOM-
hm-prices (2)58.8 / DGL OOM-99.0 / DGL OOM-
hm-prices (3)110.1 / DGL OOM-195.6 / DGL OOM-
ogbn-products (2)77.8 / DGL OOM-155.8 / DGL OOM-
ogbn-products (3)447.7 / DGL OOM-887.5 / DGL OOM-
ogbn-proteins (2)153.4 / DGL OOM-282.9 / DGL OOM-
ogbn-proteins (3)347.6 / DGL OOM-641.3 / DGL OOM-
pokec-regions (3)72.8 / DGL OOM-138.7 / DGL OOM-
reddit (2)264.2 / DGL OOM-543.0 / DGL OOM-
reddit (3)550.9 / DGL OOM-1138.2 / DGL OOM-
twitch-views (2)31.4 / DGL OOM-56.0 / DGL OOM-
twitch-views (3)73.9 / DGL OOM-137.2 / DGL OOM-
web-fraud (3)187.7 / DGL OOM-282.5 / DGL OOM-
web-topics (3)181.4 / DGL OOM-266.0 / DGL OOM-
web-traffic (3)185.7 / DGL OOM-278.0 / DGL OOM-

Table 2: Time per training step of mini-batch training with full neighborhoods, in milliseconds (ours / DGL), with the speedup over DGL. DGL OOM marks settings in which every DGL sampling mode runs out of the 80 GB of GPU memory, while our implementation still trains.

GR3. Full-graph training

We then remove sampling entirely and train on the full graph, which shows how the memory footprint of each implementation limits the graphs it can train on. We use the same 12 graphs as in [GR2] and train the 3-layer GATv2 model without sampling, so every epoch is one optimizer step over the whole graph. We use 4 heads of width 128, as in [GR1] and [GR2], and additionally we test a setup with 2 heads of width 128.

DGL runs out of memory on 11 of the 12 graphs with both 4 and 2 heads, because its GATv2 layer materializes per-edge tensors of shape [E, heads, d]. On ogbn-products it attempts a single allocation of 120 GiB. Our fused kernel trains on all 12 graphs with 1.31.3-5252 GB of peak memory. On ogbn-arxiv, the only graph on which DGL fits, our epochs are 4.4×4.4\times faster on H100 and 3.6×3.6\times faster on A100 with 4 heads, and 4.3×4.3\times and 3.5×3.5\times faster with 2 heads. Without sampling, the memory efficiency of our fused kernel is therefore what makes full-graph training possible on most of these graphs at all.

AuthorsOpenReview ↗

General Response Part 1/4

We thank the reviewers for their detailed and constructive comments. Reviewers jfM5, PSDm and DRDo asked how the kernel speedups of the paper translate into end-to-end training time, in particular with a mini-batch neighbor sampler, and where the training time is spent. To answer these questions, we built a complete GATv2 training pipeline on our kernels, including a GPU neighbor sampler, and compared it with DGL on a representative set of graphs with 1.3×1061.3 \times 10^{6} to 1.3×1081.3 \times 10^{8} edges, on an A100-SXM4-80GB and on an H100-SXM5-80GB. We describe the setup below and summarize the results in five sections, [GR1]-[GR5], to which the responses to individual reviewers refer.

The model is GATv2 with 4 heads of width 128, residual blocks, bf16 and AdamW. Each graph is trained on its native task (classification, regression or multilabel prediction). The baseline is DGL 2.4 with GATv2Conv. DGL provides three sampling modes: on the GPU, through unified virtual addressing, and with 8 CPU worker processes. We run all three and compare with the fastest. Our sampler runs on the GPU without host synchronization, is replayed from CUDA graphs, and prepares the next batch asynchronously while the current one trains.

GR1. Mini-batch training with neighbor sampling

Reviewers jfM5, PSDm and DRDo asked whether our kernel speedups survive end-to-end training with a mini-batch neighbor sampler, where sampling can dominate the step. To answer this, we train GATv2 with a standard neighbor sampler on two GPUs, measure the full epoch time including sampling, and compare it with all three sampling modes of DGL. With fanouts 15-10-5 (for a 3-layer network) and 15-10-10-5-5 (for a 5-layer network) and batches of 1024 seed nodes, we trained on a representative set of graphs with both depths on both GPUs, and our implementation is faster than DGL by 1.62×1.62\times on H100 and 2.50×2.50\times on A100 in the median. In several settings (5 layers on ogbn-products and pokec-regions), DGL runs out of memory in all three sampling modes while ours trains successfully. We present the results for 9 graphs in Table 1.

graphH100, 15-10-5H100, 15-10-10-5-5A100, 15-10-5A100, 15-10-10-5-5
avazu-ctr1.24x1.70x2.64x2.82x
hm-categories1.12x1.36x2.83x1.77x
ogbn-arxiv1.13x1.14x2.79x1.70x
ogbn-products2.81xDGL OOM3.24xDGL OOM
ogbn-proteins1.97x3.78x2.92x4.08x
pokec-regions3.08xDGL OOM2.14xDGL OOM
reddit2.41x4.06x2.66x3.75x
twitch-views1.92x2.83x2.35x3.25x
web-fraud1.53x1.74x2.29x1.76x

Table 1: Epoch-time speedup of mini-batch training with neighbor sampling over the fastest DGL sampling mode. DGL OOM marks settings in which every DGL mode runs out of the 80 GB of GPU memory, while our implementation still trains.

Through benchmarking, we identify that the sampler overhead is hidden behind computation: the training loop waits 0.02 ms per step for the next batch in the median, against 7.9 ms (1.91.9-54.954.9 ms) for DGL's GPU sampler. Sampling does become visible for very large neighborhoods. With fanout 50 per layer on ogbn-products, the loop waits 129 ms per step for 108 ms of forward and backward computation, a setting in which DGL mostly runs out of memory.

We also make sure that the downstream performance is unchanged, as the test metrics of the two implementations agree within the variation between seeds. For instance, on ogbn-products we reach 0.794 test accuracy against 0.790 with 3.2×3.2\times faster epochs on H100. Layer-wise inference over full neighborhoods is 2.732.73-5.93×5.93\times faster than DGL on all graphs we used for experiments and on both GPUs. The kernel speedups of the paper therefore carry over to mini-batch training with neighbor sampling, without any loss in accuracy.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.