Graph-GRPO: Training Graph Flow Models with Reinforcement Learning

Motivation

• Known: Discrete flow matching 기반 graph generation(GFM)은 뛰어난 성능과 유연한 샘플링으로 최근 주목받고 있으며, GAN이나 diffusion 기반 그래프 생성 모델에 RL을 결합하는 연구들이 이미 존재한다.
• Gap: 기존 GFM은 전이 확률을 Monte Carlo sampling으로 추정하기 때문에 policy gradient 기반 RL 학습에 필요한 미분 가능성이 깨지며, de novo generation 방식은 대부분 생성물이 invalid하여 reward signal이 sparse해 효과적인 탐색이 어렵다.
• Why: 약물 발견 등에서 결합 친화도나 독성 같은 복잡한 task-specific 목표에 그래프 생성 모델을 정렬시키는 것은 실용적으로 매우 중요하며, GFM을 verifiable reward 하에서 RL로 학습 가능하게 만드는 것은 이 분야의 핵심 병목을 해결한다.
• Approach: GRPO(Group Relative Policy Optimization)를 활용하여 GFM의 전이 확률을 해석적으로 유도함으로써 Monte Carlo sampling을 제거하고 완전히 미분 가능한 rollout을 구현했으며, 고보상 샘플에 노이즈를 주입해 재생성하는 refinement 전략으로 국소 탐색을 강화했다.

Achievement

Figure 1. Reward curves on two molecular optimization tasks. We

1. 해석적 전이 확률 유도: conditional rate matrix의 Monte Carlo sampling 항을 해석적 rate matrix(Rθ_t)로 대체하여 GFM의 action probability를 완전히 미분 가능하게 만들었다.
2. Refinement 전략 제안: 그래프의 특정 노드·엣지를 무작위로 교란하고 재생성함으로써 promising 샘플 주변의 chemical space를 국소적으로 탐색하고 self-improvement를 가능하게 했다.
3. 합성 데이터셋 성능: 단 50 denoising step만으로 planar 데이터셋에서 95.0%, tree 데이터셋에서 97.5%의 Valid-Unique-Novelty(VUN) 점수를 달성했다.
4. 분자 최적화 SOTA: molecular optimization task에서 graph 기반 및 fragment 기반 RL 방법, 고전적 유전 알고리즘을 모두 능가하는 state-of-the-art 성능을 달성했다.

How

Figure 3. Refinement in Graph-GRPO. We first use GFMs to

• Kolmogorov forward equation과 conditional differentiation을 이용해 conditional rate matrix를 유도(Eq. 7-8)한 뒤, Monte Carlo 기대값 계산 없이 모델 예측 pθ만으로 해석적 rate matrix Rθ_t를 구성(Eq. 10)
• Algorithm 1(DeFoG의 Conditional Transition)과 Algorithm 2(Graph-GRPO의 Analytic Transition)를 비교하여 미분 가능성을 확보
• GRPO를 사용해 old/new policy 간 확률 비율 r = πθ(Gt+dt|Gt)/πold(Gt+dt|Gt)를 계산, verifiable reward(합성 그래프 특성, 분자 property 등)를 최대화하도록 학습
• Refinement 단계에서 고reward 그래프의 노드·엣지 일부를 노이즈로 교란한 뒤 GFM으로 재생성(Figure 3)하는 과정을 반복하여 promising 영역에 점진적으로 집중
• Planar, tree 등 synthetic graph benchmark와 Scaffold Hopping, Valsartan SMARTS 등 분자 최적화 task에서 실험 수행, DeFoG를 base model로 사용

Originality

• GFM의 전이 확률에 대한 Monte Carlo 없는 해석적 표현을 최초로 유도하여 RL 훈련과 GFM 샘플링 간의 근본적인 비호환성을 해결
• GRPO를 discrete flow matching 기반 그래프 생성 모델에 적용한 최초의 온라인 RL 프레임워크
• De novo generation의 sparse reward 문제를 해결하기 위한 perturb-and-regenerate 방식의 국소 refinement 전략을 새롭게 제시
• Training과 inference 간 mismatch 문제를 명시적으로 지적하고 해석적 접근으로 동시에 해결

Limitation & Further Study

• 해석적 rate matrix가 특정 discrete flow matching 정식화(Campbell et al. 방식)에 의존적이어서, 다른 종류의 continuous 또는 hybrid flow model로의 일반화 가능성이 명확하지 않음
• Refinement 전략에서 perturbation의 강도나 위치 선택이 heuristic하게 결정될 가능성이 있어, 이에 대한 이론적 분석이나 자동화된 선택 기법이 부족해 보임
• 분자 최적화 task 외 대규모 실세계 그래프(예: 소셜 네트워크, 지식 그래프)에 대한 검증이 제한적이며, verifiable reward가 없는 상황(예: 인간 선호 기반 reward)으로의 확장 가능성에 대한 논의가 부족
• Oracle call 수가 많은 상황에서의 계산 비용 및 scalability에 대한 심층 분석이 필요

Evaluation

총평: GFM의 근본적인 RL 훈련 장벽(비미분성, sparse reward)을 해석적 rate matrix와 refinement 전략으로 동시에 해결한 견고하고 실용적인 연구로, 분자 최적화 등 실질적 응용에서 강력한 성능을 보여준다.