# Signal from Structure: Exploiting Submodular Upper Bounds in Generative Flow Networks

arXiv: https://arxiv.org/abs/2601.21061 · HTML: https://mlsanity.com/paper/2601.21061/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 26 of its 48 references that are in the map.
- First posted on arXiv 28 Jan 2026.

## Builds on (most cited first, 26 of 26)

- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Revisiting Semi-Supervised Learning with Graph Embeddings](https://mlsanity.com/paper/1603.08861/) (2016)
- [Minimax Regret Bounds for Reinforcement Learning](https://mlsanity.com/paper/1703.05449/) (2017)
- [Flow Network based Generative Models for Non-Iterative Diverse Candidate Generation](https://mlsanity.com/paper/2106.04399/) (2021)
- [GFlowNet Foundations](https://mlsanity.com/paper/2111.09266/) (2021)
- [Trajectory balance: Improved credit assignment in GFlowNets](https://mlsanity.com/paper/2201.13259/) (2022)
- [Unifying PAC and Regret: Uniform PAC Bounds for Episodic Reinforcement Learning](https://mlsanity.com/paper/1703.07710/) (2017)
- [Biological Sequence Design with GFlowNets](https://mlsanity.com/paper/2203.04115/) (2022)
- [Bayesian Structure Learning with Generative Flow Networks](https://mlsanity.com/paper/2202.13903/) (2022)
- [Better Training of GFlowNets with Local Credit and Incomplete Trajectories](https://mlsanity.com/paper/2302.01687/) (2023)
- [Towards Understanding and Improving GFlowNet Training](https://mlsanity.com/paper/2305.07170/) (2023)
- [Robust Scheduling with GFlowNets](https://mlsanity.com/paper/2302.05446/) (2023)
- [Diffusion Generative Flow Samplers: Improving learning signals through partial trajectory optimization](https://mlsanity.com/paper/2310.02679/) (2023)
- [Generative Augmented Flow Networks](https://mlsanity.com/paper/2210.03308/) (2022)
- [Sample-efficient Multi-objective Molecular Optimization with GFlowNets](https://mlsanity.com/paper/2302.04040/) (2023)
- [Local Search GFlowNets](https://mlsanity.com/paper/2310.02710/) (2023)
- [Improved off-policy training of diffusion samplers](https://mlsanity.com/paper/2402.05098/) (2024)
- [RGFN: Synthesizable Molecular Generation Using GFlowNets](https://mlsanity.com/paper/2406.08506/) (2024)
- [Genetic-guided GFlowNets for Sample Efficient Molecular Optimization](https://mlsanity.com/paper/2402.05961/) (2024)
- [Thompson sampling for improved exploration in GFlowNets](https://mlsanity.com/paper/2306.17693/) (2023)
- [Efficient Diversity-Preserving Diffusion Alignment via Gradient-Informed GFlowNets](https://mlsanity.com/paper/2412.07775/) (2024)
- [Learning Energy Decompositions for Partial Inference of GFlowNets](https://mlsanity.com/paper/2310.03301/) (2023)
- [Generative Flows on Synthetic Pathway for Drug Design](https://mlsanity.com/paper/2410.04542/) (2024)
- [Order-Preserving GFlowNets](https://mlsanity.com/paper/2310.00386/) (2023)
- [Baking Symmetry into GFlowNets](https://mlsanity.com/paper/2406.05426/) (2024)
- [Embarrassingly Parallel GFlowNets](https://mlsanity.com/paper/2406.03288/) (2024)

## Abstract (arXiv)

Generative Flow Networks (GFlowNets; GFNs) are a class of generative models that learn to sample compositional objects proportional to their a priori unknown value, their reward. We focus on the case where the reward has a specified, actionable structure, namely that it is submodular. We show submodularity can be harnessed to retrieve upper bounds on the reward of compositional objects that have not yet been observed. We provide in-depth analyses of the probability of such bounds occurring, as well as how many unobserved compositional objects can be covered by a bound. Following the Optimism in the Face of Uncertainty principle, we then introduce SUBo-GFN , which uses the submodular upper bounds to train a GFN. We show that SUBo-GFN generates orders of magnitude more learning signal than classical GFNs for the same number of queries to the reward function. We demonstrate the effectiveness of SUBo-GFN in terms of distribution matching and high-quality candidate generation on graph submodular tasks.