2025-11-14T01:22:11.048448

Symmetry-Aware GFlowNets

Kim, Lee, Oh

Generative Flow Networks (GFlowNets) offer a powerful framework for sampling graphs in proportion to their rewards. However, existing approaches suffer from systematic biases due to inaccuracies in state transition probability computations. These biases, rooted in the inherent symmetries of graphs, impact both atom-based and fragment-based generation schemes. To address this challenge, we introduce Symmetry-Aware GFlowNets (SA-GFN), a method that incorporates symmetry corrections into the learning process through reward scaling. By integrating bias correction directly into the reward structure, SA-GFN eliminates the need for explicit state transition computations. Empirical results show that SA-GFN enables unbiased sampling while enhancing diversity and consistently generating high-reward graphs that closely match the target distribution.

academic

Symmetry-Aware GFlowNets

基本信息

论文ID: 2506.02685
标题: Symmetry-Aware GFlowNets
作者: Hohyun Kim, Seunggeun Lee, Min-hwan Oh (Seoul National University)
分类: stat.ML cs.LG
发表会议: ICML 2025 (42nd International Conference on Machine Learning)
论文链接: https://arxiv.org/abs/2506.02685

摘要

生成流网络(GFlowNets)为按奖励比例采样图提供了强大的框架。然而，现有方法由于状态转移概率计算的不准确性而存在系统性偏差。这些偏差根植于图的固有对称性，影响基于原子和基于片段的生成方案。为了解决这一挑战，本文引入了对称感知GFlowNets(SA-GFN)，通过奖励缩放将对称性修正纳入学习过程。通过将偏差修正直接集成到奖励结构中，SA-GFN消除了对显式状态转移计算的需求。实验结果表明，SA-GFN能够实现无偏采样，同时增强多样性并持续生成与目标分布密切匹配的高奖励图。

研究背景与动机

核心问题

GFlowNets在图生成任务中面临等价动作问题(equivalent action problem)：不同的动作可能导致结构相同的图。例如，在图中添加新节点时，连接到两个对称节点的动作虽然不同，但会产生同构的图。这种情况下，状态转移概率必须考虑所有等价动作，但计算代价昂贵。

问题重要性

分子生成的偏差：在分子发现中，超过50%的分子具有多个对称性，18%包含4个或更多对称性。忽略对称性导致不正确的建模和分子结构生成精度降低。
系统性偏差：偏差是系统性的，在节点生成中偏向对称性较少的图，在片段生成中偏向对称性组件。
计算复杂性：准确计算状态转移概率需要昂贵的图同构测试。

现有方法局限性

**Ma et al. (2024)**提出使用位置编码近似检测等价动作，但需要在每次转移时应用，计算开销大且只是近似解。
传统GFlowNet目标函数(TB、DB等)都无法避免等价动作问题，因为它们基于状态转移形式化。

核心贡献

理论贡献：提供了GFlowNet框架下自回归图生成的严格形式化，明确解决等价动作问题
简单有效的解决方案：提出基于自同构群大小的奖励缩放方法，仅需对现有训练算法进行最小修改
无偏估计器：导出模型似然的无偏估计器
实验验证：通过实验验证理论结果，证明方法在生成多样化高奖励样本方面的有效性

方法详解

任务定义

给定奖励函数R(x)，GFlowNets的目标是训练策略pA，使得终端状态的采样概率与其奖励成正比：p̄A(x) = R(x)/Z，其中Z是归一化常数。

核心理论框架

1. 图同构与等价关系

图同构：两个图G和G'同构(G ≅ G')，如果存在置换π使得π(E) = E'
自同构群：图G的自同构群Aut(G)是保持图结构不变的所有置换的集合
轨道：节点u的轨道Orb(G,u) = {v ∈ V : ∃π ∈ Aut(G), π(u) = v}

2. 等价动作的形式化

定义4.1 (转移等价)：如果G₁ ≅ G₂且G'₁ ≅ G'₂，则图转移(G₁,G'₁)和(G₂,G'₂)转移等价。

定义4.2 (轨道等价)：如果动作类型相同且存在置换π使得π(G₁) = G₂且π(u₁) = u₂，则图动作(G₁,t₁,u₁)和(G₂,t₂,u₂)轨道等价。

定理4.3：轨道等价的动作导致转移等价的转移。

3. 关键理论结果

引理4.5：对于AddEdge动作，有 $\frac{|\text{Orb}(G,u,v)|}{|\text{Orb}(G',u,v)|} = \frac{|\text{Aut}(G)|}{|\text{Aut}(G')|}$

定理4.6 (自同构修正)：如果使用置换等变函数，则 $\frac{p_{\bar{A}}(a|s)}{q_{\bar{A}}(a|s')} = \frac{|\text{Aut}(G)|}{|\text{Aut}(G')|} \cdot \frac{p_E(G'|G)}{q_E(G|G')}$

对称感知修正方法

1. 节点生成的奖励缩放

推论5.1 (TB修正)：轨迹平衡损失应为 $L_{TB}(\tau) = \left(\log \frac{Z\prod_{t=0}^{n-1} p_E(G_{t+1}|G_t)}{|\text{Aut}(G_n)|R(G_n)\prod_{t=0}^{n-1} q_E(G_t|G_{t+1})}\right)^2$