Graph neural networks run a mix of dense math on node features and sparse math over the graph's connections, and compilers speed such workloads up by algebraically rewriting the computation — reordering operations, or fusing them to cut memory traffic — but which rewrite wins depends heavily on the shape of the input graph, so a single fixed rule is often the wrong choice; this paper (Shanghai Jiao Tong, Alibaba, Peking) builds Voyager, an input-adaptive compiler that generates many candidate rewrites, uses symbolic graph attributes to cheaply estimate their tensor shapes and prune the losers, and picks the best one for the actual input at runtime, reporting about a 3.5 times average GPU speedup over prior work.
The argument in one glance
-
Problem
The rewrites that speed up neural networks misfire on graph neural networks
A graph neural network mixes two very different kinds of work: dense math that transforms each node's feature vector, like the matrix multiplies of an ordinary neural network, and sparse math that aggregates information along the graph's edges, gathering each node's neighbors. Compilers make dense neural networks fast with algebraic transformations — rewriting the computation into a cheaper but equivalent form, chiefly by reordering operations and by fusing several operations into one so intermediate results never leave fast memory. These transformations improve both how much arithmetic is done and how much data is moved. The trouble is that carrying them straight over to graph neural networks tends to leave performance on the table. The reason is the graph: whether a particular reordering or fusion is a win depends on the structure of the specific input graph — how many nodes and edges, how dense, how the degrees are distributed — so a transformation that is clearly best for one graph can be clearly worse for another, and the dependencies the graph introduces tangle the computation in ways the standard techniques were not built for.
-
What people did
Apply the dense-network transformations with static rules
The natural approach is to reuse the mature machinery from dense deep learning: pick a set of algebraic transformation rules — a favored operator order, a fixed fusion pattern — and apply them to the graph neural network the same way a compiler would to any other model, following static rules baked in ahead of time.
-
Why it fell short
Static rules cannot predict the benefit, which depends on the input graph
The abstract identifies two reasons static rules fall short for graph neural networks. First, the diversity of input graph structures makes the performance benefit of a transformation hard to predict: because the cost of the sparse, graph-dependent parts of the computation shifts with the graph's size, density, and degree distribution, no fixed rule is right across the range of graphs a model will actually see, and a rule tuned for one input can hurt another. Second, the complex dependencies that the input graph structure introduces limit the effectiveness of existing optimization techniques, which were largely designed for the regular, dense computation of ordinary neural networks rather than for computation whose shape is dictated by an irregular graph. So a static, one-transformation-fits-all strategy is systematically leaving performance unrealized, and doing better requires adapting the choice to the input.
-
This paper's idea
Generate many candidate rewrites and pick the best for the actual input
Voyager is described as an input-adaptive compiler built specifically for graph neural networks. Instead of relying on static optimization rules, it dynamically generates and evaluates a wide range of algebraic transformation candidates — including new reordering and fusion strategies tailored to graph characteristics — rather than committing to one in advance. To keep the search affordable, it leans on symbolic graph attributes to efficiently estimate the tensor shapes each candidate would produce and to prune away low-performance candidates before they are ever run. Then a runtime selection module chooses the best transformation for the input actually at hand, using its real-time features. Across representative graph neural networks and datasets, the abstract reports an average 3.5 times speedup on GPUs over state-of-the-art work.
Why this problem is worth solving
The performance of a graph neural network hinges on transformations whose payoff is genuinely input-dependent, which is exactly what a fixed rule cannot capture. Compilers speed up tensor computations by rewriting them into equivalent but cheaper forms. Two of the most important such rewrites are operator reordering and operator fusion. Reordering changes the order in which operations are applied when the result is mathematically the same either way; because the operands have different sizes, one order can do far less arithmetic or move far less data than another. Fusion merges consecutive operations into a single computation so that the intermediate result between them is never written out to and read back from slower memory, cutting memory traffic. For dense neural networks these transformations are well understood and reliably beneficial, because the sizes involved are fixed and known, so a compiler can reason confidently about which rewrite wins. That confidence is what breaks down for graph neural networks, where part of the computation is governed by an input graph whose size and shape are not known when the static rules are written, so the very quantities that decide whether a reordering or fusion helps are not fixed. The transformations are still the right tools; the difficulty is choosing among them.
The graph is both what makes the workload valuable and what makes its optimization hard. A graph neural network interleaves dense feature transformation with sparse aggregation over the graph’s edges, and it is the sparse, graph-driven part that resists standard optimization. The abstract points to two consequences of input-graph diversity. First, performance benefits become hard to predict: the amount of work in the aggregation, and the relative cost of the dense and sparse stages, depend on how many nodes and edges the graph has and how connected it is, so the best transformation for a small dense graph can be the wrong one for a large sparse graph, and there is no single answer across the inputs a deployed model encounters. Second, the input graph introduces complex dependencies that limit existing techniques: the data-movement and computation patterns are dictated by an irregular structure rather than a regular grid, so optimizations built for the predictable dependencies of dense neural networks do not transfer cleanly. Together these mean that a method which does not look at the specific input graph is optimizing partly in the dark, which is the gap an input-adaptive approach sets out to close.
What people did before, and where it broke
- Reuse dense-network algebraic transformations directly. Apply the operator reordering and fusion that speed up ordinary deep neural networks to graph neural networks as well. Where it broke. It gives suboptimal performance, because the benefit of a transformation depends on the input graph, which these methods do not account for.
- Follow static optimization rules. Bake in a fixed choice of transformation ahead of time and apply it uniformly. Where it broke. No single fixed rule is right across the diversity of input graph structures; a rule tuned for one graph can hurt another, since the performance benefit is hard to predict in advance.
- Rely on optimization techniques designed for dense models. Use the existing compiler machinery built for regular, dense neural-network computation. Where it broke. The complex dependencies introduced by irregular input graph structures limit how effective those techniques are on graph neural networks.
- The gap. No approach adapted the choice of algebraic transformation to the specific input graph — generating a wide range of candidates, cheaply estimating their cost from the graph’s attributes, and selecting the best for the input actually being run. Building that input-adaptive compiler for graph neural networks is what Voyager is described as contributing.
How Voyager works
An input-adaptive path from many candidate rewrites to the one that fits the graph
-
-
new
-
new
-
new
-
new
-
new
The idea
Do not fix the transformation in advance; generate many and let the input decide. The reframing at the center of Voyager, as the abstract presents it, is that the right algebraic transformation for a graph neural network is not a property of the model alone but of the model together with its input graph, so any static rule is answering the wrong question. Instead of choosing one reordering or fusion up front, Voyager dynamically generates a wide range of candidate rewrites, including strategies tailored to graph characteristics, and treats picking among them as the real problem. Exploring a space of operator rewrites — different fusions and orderings of the computation — rather than applying a single canned schedule is the same search-over-transformations stance the work on kernel orchestration for tensor programs covered elsewhere on this site takes, trusting a generated-and-evaluated space of options to beat any one hand-fixed plan.
Estimate cheaply from the graph’s attributes, so the search stays affordable. A space of many candidate transformations is only useful if it can be navigated without running everything, and Voyager’s described answer is to use symbolic graph attributes to estimate the tensor shapes each candidate would produce and to prune the low-performance ones before execution. Because the cost of a graph neural network’s computation is driven by the input graph’s structure, describing that structure symbolically lets Voyager predict which rewrites are worth keeping. Tuning the optimization to the specific shape and structure of the input rather than to a generic assumption is the same workload-aware instinct the work on workload-aware co-optimization of sparse formats and schedules covered elsewhere on this site is built on, letting the properties of the actual input steer which plan is chosen.
Choose at runtime, when the real input is finally known. Some of what decides the best transformation is only available when the model actually runs on a given graph, so Voyager adds a runtime selection module that picks the optimal transformation from the pruned candidates using the input’s real-time features. This closes the loop between the offline generation of candidates and the online reality of a particular graph, and it is what the abstract credits, together with the tailored reordering and fusion strategies, for an average 3.5 times GPU speedup over prior work. Squeezing high performance out of the sparse, structure-dependent computation that graph neural networks demand is the same target the work on fast GPU kernel design for graph neural networks covered elsewhere on this site pursues, and Voyager approaches it from the compiler side by adapting the computation’s algebraic form to the graph.
Following a graph neural network through Voyager
Choosing a reordering for a graph neural network layer
An illustrative trace, at the level the abstract describes, of how Voyager adapts an algebraic transformation to an input graph. The specific reordering shown is a standard example of the kind of choice involved, used here for illustration.
Step 1 of 5
A layer offers more than one equivalent computation order
A graph neural network layer both transforms node features with dense math and aggregates them across edges with sparse math. As a standard example of the kind of choice Voyager faces, these two steps can often be applied in more than one order, each mathematically equivalent but with different cost.
Which order does less work depends on the feature dimensions and on the input graph.
Why it works
- The best transformation depends on the input, so adapting to it wins. A static rule fixes one rewrite for all graphs → but the performance benefit of a reordering or fusion shifts with graph size, density, and degree distribution → so choosing per input, as Voyager does, captures gains a single fixed choice must miss.
- Generating many candidates avoids betting on one. Committing to a favored order or fusion pattern gambles that it suits the workload → but dynamically generating a wide range of candidates, including graph-tailored ones, keeps options open for very different graphs → so there is always a suitable rewrite available to select.
- Symbolic graph attributes make evaluation cheap. Running every candidate to measure it would be prohibitively expensive → but estimating each candidate’s tensor shapes from symbolic attributes of the graph predicts cost without execution → so a large candidate space can be searched and pruned affordably.
- Pruning focuses effort on the rewrites that matter. The full space of reorderings and fusions is combinatorially large → but discarding candidates predicted to perform poorly removes most of it up front → so the costly later stages are spent only on promising transformations.
- Runtime selection uses information a compiler lacks offline. Some of what decides the best transformation is only known once the real graph arrives → but a runtime module can read the input’s live features and pick accordingly → so the final choice reflects the actual input rather than a compile-time guess, which the abstract ties to the reported speedup.
What it costs (trade-offs and scope)
- This account is based on the abstract only. The full paper was not available when this page was written, so the mechanisms below are described at the level the abstract states, and the specific internal designs — how candidates are generated, exactly which symbolic attributes and cost estimates are used, how the runtime selector decides — are not detailed here and should be read from the paper itself.
- Generating and searching candidates has a cost. Dynamically generating and evaluating a wide range of transformation candidates is more work than applying a static rule; the abstract says symbolic shape estimation and pruning keep this affordable, but candidate generation and search are inherent overheads that the design must contain.
- Runtime selection adds a runtime component. Choosing the transformation at runtime from the input’s features means there is a selection step in the execution path; its overhead must be small relative to the speedup it unlocks, and the abstract reports net gains but does not, in what is available here, quantify that overhead.
- The gains are reported for a specific setting. The average 3.5 times speedup is over state-of-the-art work on representative graph neural networks and datasets on GPUs; how the benefit varies across models, graph types, and hardware, and against which specific baselines, are details to confirm in the full paper.
- It targets algebraic transformations, not every source of GNN performance. Voyager is about adapting operator reordering and fusion to the input graph; other dimensions of graph-neural-network efficiency, such as data layout, partitioning, or specialized kernels, are complementary concerns outside what the abstract attributes to it.
The evaluation
Choosing algebraic transformations for a graph neural network
| Property | Dense-network transformations | Static GNN rules | Voyager (input-adaptive) |
|---|---|---|---|
| How the transformation is chosen | |||
| Accounts for input graph structure | |||
| Candidate space explored | |||
| Uses runtime input features | No | ||
| Reported GPU speedup | Baseline | Baseline |
Check yourself
Check your understanding
1. Why does applying dense-network algebraic transformations to graph neural networks with static rules give suboptimal performance?
2. What is Voyager's core approach?
3. How does Voyager keep the search over transformation candidates affordable?
4. What performance does the paper report, and what should you keep in mind about this summary?
Sources
The paper is “Voyager: Input-Adaptive Algebraic Transformations for High-Performance Graph Neural Networks” by Yangjie Zhou, Wenting Shen, Jingwen Leng, Shuwen Lu, Zihan Liu, Weihao Cui, Zhendong Zhang, Wencong Xiao, Baole Ai, Yong Li, Wei Lin, Deze Zeng, Yun Liang, Quan Chen, Ning Liu, and Minyi Guo (Shanghai Jiao Tong University, Alibaba Group, Peking University, and China University of Geosciences), published at ASPLOS 2025 (Volume 3), DOI 10.1145/3676642.3736121.
This explainer is written from the paper’s abstract; the full text was not accessible at the time of writing. The claims traceable to the abstract are: that graph neural networks are growing in popularity and complexity and that high-performance execution is important; that algebraic transformations, including operator reordering and operator fusion, have been successfully applied to improve the computation and memory-access efficiency of deep neural network models; that directly applying these methods to graph neural networks yields suboptimal performance, primarily because the diversity of input graph structures makes performance benefits hard to predict and the complex dependencies introduced by these input graph structures limit existing optimization techniques; that Voyager is an input-adaptive compiler designed specifically for graph neural networks that, unlike methods relying on static optimization rules, dynamically generates and evaluates a wide range of algebraic transformation candidates, including novel reordering and fusion strategies tailored to graph characteristics; that it leverages symbolic graph attributes to efficiently estimate tensor shapes and prune low-performance candidates; that a runtime selection module further chooses the optimal transformation based on real-time input features; and that the evaluation shows an average 3.5 times speedup on GPUs over state-of-the-art work on representative graph neural networks and datasets. Background explanations of what operator reordering and operator fusion mean, and of the mixed dense-and-sparse nature of graph-neural-network computation, are standard domain context provided to make the abstract’s claims understandable, and the reordering example in the step-through is used only for illustration. The internal designs, exact cost models, baselines, and per-workload results should be confirmed against the full paper, which is available through the ACM Digital Library at the DOI above.