When a large graph is split across GPUs to serve graph neural network (GNN) queries, each machine multiplies its slice of the adjacency matrix by a feature matrix. Graph partitioners balance a proxy for that work, usually vertex or edge counts. A modern GPU does not pay per edge, though. On Tensor Cores, the matrix units that process small dense tiles, an irregular sparse matrix costs roughly one unit of work per non-empty tile, and the number of non-empty tiles depends on how the rows happen to be ordered and grouped. Two partitions with the same edge count can therefore differ several-fold in kernel time. In serving designs where every query touches every partition and waits for the slowest one, that hidden imbalance sets the tail latency.
We propose to make the hardware tile, not the vertex, the unit of partitioning. A single global reordering first groups similar rows into fixed-height "row panels", each of which already forms a set of dense Tensor-Core blocks. A multi-objective partitioner then assigns whole panels to machines. Once panels are fixed, block cost becomes additive per panel. The partitioner can then balance true kernel cost, halo communication, and query traffic together. Because panels never need re-reordering, they can also be migrated online when traffic drifts. The claim we test is that this placement raises the throughput a cluster can sustain at a fixed 99th-percentile latency, compared with partitioning first and reordering afterward. We also test whether the advantage holds across graph families whose degree structure makes edge count a poor proxy for tile count.
Why the obvious combinations fall short
Four lines of work each address one piece of this problem. Partitioners balance several abstract weights. DistDGL uses multi-constraint METIS to spread training, validation, and test nodes evenly. FSM splits a graph into many small pieces and merges them to balance vertices and edges while limiting replication. Sparsity-Aware Communication uses its Graph-VB partitioner to bound both total and maximum per-process communication volume. All three treat a vertex's compute cost as a scalar fixed before partitioning, so none can see Tensor-Core block structure.
Kernel work shows why that scalar is wrong. SMaT clusters rows by Jaccard similarity into 16×8 blocks and beats cuBLAS at sparsity as low as 78%. Its row reordering, however, is an expensive offline step on one matrix, and it is unaware of distributed placement. Flash-LLM shows the same pattern for LLM weights: speed comes from ahead-of-time data reorganization that does not suit dynamic workloads.
Serving systems face the tradeoff between throughput and delay but take partitions as given. OMEGA builds per-machine computation graphs and combines them with all-to-all collectives, so its latency is governed by the slowest partition. Quiver routes small neighborhoods to CPUs and large ones to GPUs using offline workload metrics. Queueing theory explains why a persistent per-server cost imbalance matters. Huang and Neely show utility-optimal scheduling trades an $O(1/V)$ utility gap against $O(V)$ backlog, where $V$ is the control weight on utility. A server that is persistently slower shifts the whole curve, and no scheduler can recover the lost capacity. These papers motivate the proposal. SMaT supplies the blocking technique, and FSM supplies the split-then-merge structure we reuse.
Core Claim
The key observation is about where block cost comes from. Count non-empty 16×8 blocks after rows are re-grouped inside each partition, and the count is non-additive and expensive to evaluate. Fix one global row and column order first, cut it into 16-row panels, and let each panel's cost be the number of 8-column groups it touches. Under that convention a partition's block count is the sum of its panels' costs. Hardware-true compute cost becomes an ordinary vertex weight on a coarsened "panel graph", where an edge's weight is the halo feature volume it would force across machines. Each partition $p$ then gets a cost model
$$T_p = \alpha B_p + \beta H_p + \gamma Q_p ,$$
where $B_p$ is the number of non-empty blocks in $p$'s panels, $H_p$ is the halo feature volume $p$ must receive, and $Q_p$ is the expected query traffic that lands on $p$. The coefficients $\alpha,\beta,\gamma$ are fitted per GPU from microbenchmarks. The partitioner minimizes $\max_p T_p$ subject to memory limits, which is a multi-constraint problem that standard tools and FSM-style merging can handle.
The price is some lost block density. A single global column order is not optimal for each partition's halo columns. We measure that loss directly against per-partition SMaT reordering. The gain is that migration under traffic drift moves panels that are already in blocked format, which removes the reorder-at-runtime bottleneck that SMaT and FSM both leave open.
Research Program
The first component is panel formation. Rows are ordered globally by approximate Jaccard clustering, using locality-sensitive hashing to avoid SMaT's quadratic cost, under a soft constraint that a panel should not span distant communities. High-degree hub rows, which would give a panel a huge footprint in power-law graphs, are split into row fragments with replicated outputs. We will report how the fraction of nonzeros sitting in hub panels changes across graph families.
The second component is panel-level partitioning. We run multi-constraint METIS on the panel graph with weights $(B, Q, \text{memory})$, then apply an FSM-style refinement merge that targets $\max_p T_p$ directly.
The third component is online migration. Per-partition queue lengths feed a drift-plus-penalty rule in the style of Huang and Neely that decides when moving a panel pays for its transfer cost. Panels move as precompiled block arrays, so this is the only place queueing dynamics enter the design.
The fourth component is a topology-generalization study. The cost model is fitted on one graph family and evaluated on others. The aim is to find where the edge-count proxy fails and whether $T_p$ stays predictive on each family.
Baselines
The naive reference is edge-cut METIS with vertex-count balance, followed by cuSPARSE per partition. It represents common practice and anchors every curve.
The strongest existing competitor is a decoupled pipeline. It runs multi-constraint METIS with degree-based vertex weights, as in DistDGL, and then applies SMaT reordering and kernels inside each partition. This pipeline gets SMaT's full per-partition block density, which our global ordering forgoes, so beating it isolates the value of balancing on true block cost. No reported result was found on Lacuna for this combination, which is itself part of the gap. The closest reported component numbers are SMaT's average 2.6× speedup over DASP on SuiteSparse and Graph-VB's up to 14× speedup on Protein at 256 GPUs over a sparsity-oblivious baseline.
We also compare against Graph-VB from Sparsity-Aware Communication, which is strongest when communication rather than compute dominates. We include FSM dual-balanced partitioning, reported to cut PageRank runtime by up to 9.43%, to test whether balancing vertices and edges together already captures block cost.
All methods use the same GPUs (A100, with V100 runs to check portability), the same GNN models and features, and the same serving harness. The harness uses OMEGA-style computation-graph parallelism and an identical load generator. Each partitioner gets the same tuning budget over its imbalance tolerance.
The key ablation keeps our panel graph but sets vertex weights to edge counts instead of $B$. A second ablation removes online migration. A third compares global ordering against per-partition re-ordering after panel placement.
Our method beats the strongest baseline if it sustains higher queries per second at the same p99 latency on at least the power-law graphs, while total preprocessing time stays no higher. For scale, Quiver reports under 13 ms latency at 255,000 requests per second on ogbn-products on a single server. That figure is a reference point only, since Quiver is a different serving architecture with CPU offload.
Why not just…?
Why not just use multi-constraint METIS with degree as the compute weight? This is the most serious threat. If edge count predicts block count well within each graph family, the panel machinery is unnecessary. The first decisive check measures exactly this: the correlation between per-partition edge count and $B_p$, and between each of them and measured kernel time, on ogbn-products, papers100M, the FSM web graphs, and mesh-like SuiteSparse matrices. If edges explain kernel time about as well as blocks do everywhere, we will report a negative result rather than push the method.
Why not just partition first and run SMaT reordering inside each partition? That pipeline achieves denser blocks than our global order. However, it cannot balance what it only discovers afterward, and it must redo the expensive reordering whenever partitions change. The global-versus-local ordering ablation measures the density we give up. The drift experiment measures what that pipeline pays per repartitioning.
Why not just absorb imbalance at runtime with a queue-aware router? Shadow-price routing such as the online LP router improves latency over Round Robin by 45.75% when workers are interchangeable. Under computation-graph parallelism, though, every query must visit every partition, so there is no alternative worker to route to. Replicating hot panels is the real runtime alternative. We include a replication-only baseline with matched memory, and if it matches our results we will say so.
Why not just treat the adjacency matrix as dense or impose structured sparsity? Graph adjacency is data, not prunable weights, so 2:4 patterns from N:M sparse training would change the model's input. Dense execution is already beaten at moderate sparsity by SMaT, and graph adjacency is far sparser than SMaT's 78% crossover.
Proposed Experiments
The first experiment fits the cost model and tests whether it transfers. We fit $\alpha,\beta,\gamma$ on SuiteSparse and the Reddit/Amazon/Protein suite, then predict per-partition kernel time on ogbn-products, ogbn-papers100M, and the FSM web graphs. We report rank correlation against measured time, alongside the edge-count proxy.
The second experiment, the decisive one, traces throughput–p99 latency curves for GraphSAGE and GCN serving on 8 to 64 GPUs. Query traffic follows a skewed distribution over graph communities. We report the maximum load at which p99 stays under a fixed target.
The third experiment shifts the hot communities mid-run and measures p99 recovery time and bytes moved for panel migration. The comparison points are full repartitioning followed by SMaT reordering, and no adaptation. We also check that accuracy is unchanged, since only placement moves.
Success means three results together: block-based cost predicts kernel time clearly better than edge count on power-law graphs, sustainable load at fixed p99 rises over the decoupled METIS+SMaT pipeline, and migration avoids the reorder cost. Failure of the first check ends the project early and cheaply, which is why it runs first.
References
- DistDGL: Distributed Graph Neural Network Training for Billion-Scale Graphs
- FSM: A Fine-grained Splitting and Merging Framework for Dual-balanced Graph Partition
- Sparsity-Aware Communication for Distributed Graph Neural Network Training
- High Performance Unstructured SpMM Computation Using Tensor Cores
- Flash-LLM: Enabling Cost-Effective and Highly-Efficient Large Generative Model Inference with Unstructured Sparsity
- OMEGA: A Low-Latency GNN Serving System for Large Graphs
- Quiver: Supporting GPUs for Low-Latency, High-Throughput GNN Serving with Workload Awareness
- Utility optimal scheduling in processing networks
- Online Linear Programming for Multi-Objective Routing in LLM Serving
- Learning N: M Fine-grained Structured Sparse Neural Networks From Scratch