Many learned solvers for graph problems use a policy that makes one decision per node, such as which device runs an operation or how much priority a node gets in a greedy decoder. The whole graph then receives a single scalar reward. Training such a policy with a policy gradient (adjusting action probabilities in proportion to how much reward followed) is noisy for a structural reason. Every node's update is multiplied by the same reward, and that reward is mostly driven by what thousands of other nodes did. We propose to cut this noise using graph coarsening, the step of grouping nodes into a few "super-nodes" that is usually done to make graph neural networks cheaper to run. Here the coarsening plays a different role: it tells us how to split credit. For each cluster we resample only that cluster's actions, hold the rest of the graph fixed, and use the resulting rewards as that cluster's baseline. A cluster's update is then compared against "what else this cluster could have done here" rather than against "what the whole graph usually scores."
The core bet is that the best partition for credit assignment is a low-cut partition, meaning one with few edges between clusters. If the reward is roughly a sum of node and edge terms, holding the other clusters fixed removes all of their noise except what leaks through edges crossing cluster boundaries. Coarsening methods built to preserve graph structure already find such partitions cheaply. This turns graph reduction from a speed trick into a variance-control tool. It also raises a concrete question: under a fixed budget of reward evaluations, how coarse should credit assignment be?
Core Claim
The setting is a policy $\pi_\theta$ that, given graph state $s$, samples actions for each cluster $C_1,\dots,C_K$ of a partition independently given $s$. The proposed estimator is
$$\hat g = \sum_{k=1}^{K} \nabla_\theta \log \pi_\theta(a_{C_k}\mid s)\Big(R(a) - \frac{1}{M}\sum_{m=1}^{M} R\big(a'^{(m)}_{C_k}, a_{-C_k}\big)\Big),$$
with the terms defined as follows. $a$ is the full sampled action. $a_{-C_k}$ is the action on every node outside cluster $k$. $a'^{(m)}_{C_k}$ are $M$ fresh draws for cluster $k$ only. $R$ is the task reward. The baseline is independent of $a_{C_k}$ given the other clusters' actions, so the estimator stays unbiased, by the same argument that makes any state baseline unbiased.
Variance is reduced for the following reason. Suppose $R$ splits into per-cluster terms plus terms on edges that cross clusters. Then the residual inside the parentheses depends only on cluster $k$'s own randomness and on its interactions across cut edges. This yields a prediction we can test: at matched cluster count, estimator variance should rise with the weight of the cut. Spectral or aggregation-based coarsening should therefore beat random partitions of the same sizes. Two quantities trade against each other. More clusters give cleaner per-cluster advantages, but the evaluation budget $B$ then allows only $M = B/K$ resamples each. We therefore expect an interior optimum on the coarsening hierarchy rather than a monotone trend.
Relation to Prior Work
The closest system is HSDAG, A Structure-Aware Framework for Learning Device Placements on Computation Graphs. It coarsens computation graphs with OpenVINO co-location heuristics to shrink the action space, then trains a placement policy with vanilla REINFORCE on inverse latency, with no baseline at all. Coarsening there only shrinks the action space. We keep the coarsening but use it to build the baseline.
Two papers motivate the locality assumption. Optimization-Based Algebraic Multigrid Coarsening Using Reinforcement Learning splits large meshes into Lloyd-aggregation subdomains and argues explicitly that the advantage of a node choice is local even though the state value is global. It builds this into a value-based dueling Q-network, not a policy gradient. Segment Policy Optimization supplies the closest method. It splits language-model trajectories at low-probability "cutpoints" and estimates each segment's advantage with branch rollouts from that point. Our estimator is the graph analogue: branch rollouts over a spatial cluster instead of a temporal segment. We also choose the clusters by graph structure rather than by token probability.
Graph-based Deterministic Policy Gradient for Repetitive Combinatorial Optimization Problems supplies our main application template, GDPG-Twin. A graph network outputs per-node priorities, and a greedy heuristic decodes them into a feasible solution. Training backpropagates through a learned differentiable "twin" critic. The authors state that the variance and worst-case tails of the optimality gap are left unanalyzed. Their design matters for us in a second way. The decoder guarantees feasibility, which avoids the constraint violations that Neural Coarsening Process for Multi-level Graph Combinatorial Optimization reports for its supervised one-shot coarsening.
Partitions come from cheap coarsening rather than exact spectral methods. The Gromov–Wasserstein methods in Gromov-Wasserstein Graph Coarsening carry $O(N^2)$ to $O(N^4)$ costs. A Unified Framework for Optimization-Based Graph Coarsening carries an $O(p^3)$ cost. Both rule themselves out for per-instance use. Lloyd aggregation and leverage-score coarsening from Graph coarsening: From scientific computing to machine learning, computed with approximate eigenvectors, are our default.
Unrealized Expectations is a sobering constraint on any claim here. It shows that learned maximum independent set (MIS) solvers collapse to degree-greedy behavior and lose to classical reduction solvers. We treat it as a ceiling, not something to argue away.
Research Program
We will build a stochastic version of the GDPG-Twin pipeline. The actor outputs a Gaussian over per-node priorities, and the problem's greedy heuristic decodes them. Each reward evaluation is one full heuristic run, so cost is measured in reward evaluations.
On each instance we compute a coarsening hierarchy once, from a few levels of Lloyd or leverage-score aggregation, down to per-node clusters at the finest level. Training uses the estimator above at a chosen level. The per-update evaluation budget $B$ is matched across all methods.
The analysis component measures true gradient variance directly. We compute a reference gradient from many thousands of samples on held-out instances. We then report the mean squared error and cosine similarity of each estimator against it, at equal $B$. We plot this against cluster count and against cut weight.
A third component tests where locality breaks. We take device placement, where latency is not a sum of local terms, and check whether the gains shrink as the theory predicts. If they do not shrink, the mechanism is something other than what we claim.
Baselines
The naive reference point is REINFORCE with a batch-mean baseline. This is HSDAG-style training with the minimum standard fix. It is run with $B$ full-graph samples per update and the same actor, decoder, learning-rate sweep and seeds. We will also report degree-greedy decoding and the untrained greedy heuristic, because Unrealized Expectations shows learned policies often fail to beat them. Beating them is the minimum bar.
The strongest critic-free competitor is group-normalized trajectory baselines in the style of GRPO, together with a self-critical baseline from Self-Critical Sequence Training for Image Captioning. That paper uses the reward of the deterministic greedy decode as the baseline, which here means the decode of the mean priority vector. Both get exactly $B$ evaluations per update. To beat them, our estimator must show lower gradient error at equal $B$ and reach a target objective in fewer total evaluations, across seeds.
The strongest existing method on these problems is GDPG-Twin itself. It reports 2 to 3 times better sample efficiency than zeroth-order optimization and an 11.42% improvement over vanilla greedy on minimum weighted dominating set (MWDS) on Barabási–Albert graphs (Graph-based Deterministic Policy Gradient for Repetitive Combinatorial Optimization Problems). We will rerun it on identical instances and count its twin-network training data against the same evaluation budget. Beating it means matching or exceeding its improvement over greedy with fewer evaluations, or with smaller variance of the optimality gap across instances, which is the quantity it leaves open.
For MIS on dense Erdős–Rényi graphs with $n=3000$ and average degree 100, Unrealized Expectations reports set size 190.75 for the best learned method (LwD) and 201.50 for classical ReduMIS. We will report against both. We do not expect to reach 201.50, and our claim does not require it.
Two ablations isolate the key ingredient. The first is a random partition with the same cluster sizes as the coarsening. It tests whether low cut, rather than mere partitioning, drives the gain. The second is the per-node limit, with one-node clusters, as the extreme of the granularity sweep.
Why not just…?
Why not just use a group-normalized or self-critical baseline? These are the real threat, because they are simple and cost the same number of evaluations. A whole-graph baseline still multiplies every node's update by noise from every other node. Segment Policy Optimization found that finer credit assignment beat GRPO by 6–12 points on GSM8K. That evidence comes from sequences, though, not graphs. The variance measurement against the reference gradient settles the question directly. If group baselines match our estimator at equal $B$ on graphs of a few thousand nodes, the proposal fails.
Why not just resample one node at a time? Per-node baselines are unbiased and remove the most cross-node noise. With a budget of $B$ full heuristic runs, however, $N$ clusters leave a fraction of one resample per node. Per-node resampling is only cheap when the reward can be updated locally. The granularity sweep includes this endpoint. If it wins whenever incremental evaluation exists, we will say so and scope the method to non-incremental rewards.
Why not just learn a critic, as GDPG-Twin does? A learned critic removes resampling cost but adds bias and its own instability. Addressing Function Approximation Error in Actor-Critic Methods documents how overestimating value functions feed noisy targets back into the policy update. GDPG-Twin's authors also leave tail behavior unexamined. Our comparison reports the spread of the optimality gap across instances, not just its mean, so the experiment shows whether the critic's bias appears in the tails.
Why not just run a classical solver? For MIS the classical solver wins, with 201.50 versus 190.75 (Unrealized Expectations), and we concede this. The method targets problems with a feasible greedy decoder but no known exact reduction rules, such as minimum weighted connected dominating set and Steiner-tree variants from the GDPG-Twin suite. MIS stays in the study only as a calibration point.
Proposed Experiments
The primary benchmark is the GDPG-Twin problem suite on synthetic Erdős–Rényi and Barabási–Albert graphs. It covers maximum weighted independent set (MWIS), MWDS, node-weighted Steiner tree (NWST) and minimum weighted connected dominating set (MWCDS). We will scale graph size from hundreds of nodes up to the 3,000–10,000-node range where Unrealized Expectations reports learned solvers hitting GPU memory limits. MIS at $n=3000$, degree 100 is the calibration point.
The first decisive check is the variance curve. If the cut-weight prediction is right, gradient error at fixed $K$ and $B$ should rank partitions from Lloyd or leverage-score coarsening, to random, to no partition. Error should also track the measured cut weight. If random partitions match structured ones, the graph-reduction half of the idea is unsupported.
The second check is end-to-end. We measure objective and approximation ratio after a fixed evaluation budget, against the baselines above.
The third check is device placement on BERT, ResNet-50 and Inception-V3, run only if comparable Intel hardware is available. It reuses HSDAG's OpenVINO clusters and swaps only the estimator. HSDAG reports a 58.2% speedup over CPU-only execution on BERT (A Structure-Aware Framework for Learning Device Placements on Computation Graphs). Latency does not decompose into local terms, so our prediction is a smaller gain than on combinatorial problems. A large gain there would mean the mechanism is not locality, and we would report it as such.
References
- A Structure-Aware Framework for Learning Device Placements on Computation Graphs
- Optimization-Based Algebraic Multigrid Coarsening Using Reinforcement Learning
- Segment Policy Optimization: Effective Segment-Level Credit Assignment in RL for Large Language Models
- Graph-based Deterministic Policy Gradient for Repetitive Combinatorial Optimization Problems
- Neural Coarsening Process for Multi-level Graph Combinatorial Optimization
- Gromov-Wasserstein Graph Coarsening
- A Unified Framework for Optimization-Based Graph Coarsening
- Graph coarsening: From scientific computing to machine learning
- Unrealized Expectations: Comparing AI Methods vs Classical Algorithms for Maximum Independent Set
- Self-Critical Sequence Training for Image Captioning
- Addressing Function Approximation Error in Actor-Critic Methods