Shared Order Marginalization for Training Graph Transformers on Independent Sets

Graph Transformers can learn to select tasks with additive values and pairwise conflicts by constructing independent sets. The reward depends on the selected set, yet policy-gradient training gives different signals to different orders that construct it. Averaging these signals reduces order-dependent noise but requires ac counting for the graph deletions caused by every alternative. We propose SOM, Shared Order Marginalization, to train from a broad family of same-solution or ders while sharing their graph computation. For policies with fixed vertex selection rates, SOM represents when each vertex remains available across alternative starting positions. This representation supplies the order family’s probability and all vertex derivatives without rebuilding the graph for each start. For a so- lution with 2K vertices, it exactly averages K2K orders in O(n + m + K2) arithmetic operations, where n and m are the graph’s vertex and edge counts. The resulting estimator preserves the expected-reward gradient and reduces co- variance under matched sampling. On a unit-rate star, one cyclic average re- moves a score component that requires quadratically many layers of the speci- fied exact adjacent-pair averaging. On weighted vehicle-routing conflict graphs, a GraphGPS–SOM initializer followed by CHILS has a mean normalized-value difference of -0.02 percentage points from native CHILS under the same wall limit, with a paired interval crossing zero. Against fixed-configuration RLOO, SOM reaches the common target 1.22× faster; separate tuning reduces the speed ratio to 1.110. Graphormer supplies a second-backbone comparison, and the MIS and sparse panels delimit the benefit. Our code is avaliable at https://anonymous.4open.science/status/SOM-DC11