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

대칭성-인식 GFlowNets

기본 정보

  • 논문 ID: 2506.02685
  • 제목: Symmetry-Aware GFlowNets
  • 저자: Hohyun Kim, Seunggeun Lee, Min-hwan Oh (서울대학교)
  • 분류: stat.ML cs.LG
  • 발표 학회: ICML 2025 (제42회 국제 머신러닝 학회)
  • 논문 링크: https://arxiv.org/abs/2506.02685

초록

생성 흐름 네트워크(GFlowNets)는 보상에 비례하여 그래프를 샘플링하기 위한 강력한 프레임워크를 제공합니다. 그러나 기존 방법은 상태 전이 확률 계산의 부정확성으로 인해 체계적 편향을 겪고 있습니다. 이러한 편향은 그래프의 내재적 대칭성에 근거하며, 원자 기반 및 단편 기반 생성 방식에 영향을 미칩니다. 이 문제를 해결하기 위해 본 논문은 보상 스케일링을 통해 대칭성 수정을 학습 과정에 통합하는 대칭성-인식 GFlowNets(SA-GFN)을 제시합니다. 편향 수정을 보상 구조에 직접 통합함으로써, SA-GFN은 명시적 상태 전이 계산의 필요성을 제거합니다. 실험 결과는 SA-GFN이 편향 없는 샘플링을 달성하면서 동시에 다양성을 향상시키고 목표 분포와 밀접하게 일치하는 높은 보상 그래프를 지속적으로 생성함을 보여줍니다.

연구 배경 및 동기

핵심 문제

GFlowNets는 그래프 생성 작업에서 **동등 동작 문제(equivalent action problem)**에 직면합니다: 서로 다른 동작이 구조적으로 동일한 그래프를 초래할 수 있습니다. 예를 들어, 그래프에 새 노드를 추가할 때, 두 개의 대칭 노드에 연결하는 동작은 비록 다르지만 동형 그래프를 생성합니다. 이 경우, 상태 전이 확률은 모든 동등 동작을 고려해야 하지만 계산 비용이 많이 듭니다.

문제의 중요성

  1. 분자 생성의 편향: 분자 발견에서 50% 이상의 분자가 여러 대칭성을 가지며, 18%는 4개 이상의 대칭성을 포함합니다. 대칭성을 무시하면 부정확한 모델링과 분자 구조 생성 정확도 저하를 초래합니다.
  2. 체계적 편향: 편향은 체계적이며, 노드 생성에서 대칭성이 적은 그래프로 편향되고, 단편 생성에서 대칭 성분으로 편향됩니다.
  3. 계산 복잡성: 정확한 상태 전이 확률 계산은 비용이 많이 드는 그래프 동형 테스트가 필요합니다.

기존 방법의 한계

  • Ma et al. (2024): 위치 인코딩을 사용하여 동등 동작 감지를 근사하도록 제안했지만, 각 전이 시마다 적용해야 하며 계산 오버헤드가 크고 근사 해결책일 뿐입니다.
  • 전통적인 GFlowNet 목적 함수(TB, DB 등)는 모두 상태 전이 형식화에 기반하므로 동등 동작 문제를 피할 수 없습니다.

핵심 기여

  1. 이론적 기여: GFlowNet 프레임워크 하에서 자회귀 그래프 생성의 엄격한 형식화를 제공하며, 동등 동작 문제를 명시적으로 해결합니다.
  2. 단순하고 효과적인 해결책: 자동동형군 크기에 기반한 보상 스케일링 방법을 제시하며, 기존 훈련 알고리즘에 대한 최소한의 수정만 필요합니다.
  3. 편향 없는 추정기: 모델 우도의 편향 없는 추정기를 도출합니다.
  4. 실험 검증: 이론적 결과를 실험으로 검증하고, 다양한 높은 보상 샘플 생성에서 방법의 효과성을 입증합니다.

방법 상세 설명

작업 정의

보상 함수 R(x)가 주어질 때, GFlowNets의 목표는 정책 pA를 훈련하여 종료 상태의 샘플링 확률이 보상에 비례하도록 하는 것입니다: p̄A(x) = R(x)/Z, 여기서 Z는 정규화 상수입니다.

핵심 이론 프레임워크

1. 그래프 동형성과 동등 관계

  • 그래프 동형성: 두 그래프 G와 G'이 동형(G ≅ G')이면, 치환 π가 존재하여 π(E) = E'입니다.
  • 자동동형군: 그래프 G의 자동동형군 Aut(G)는 그래프 구조를 불변으로 유지하는 모든 치환의 집합입니다.
  • 궤도(Orbit): 노드 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 동작의 경우, ∣Orb(G,u,v)∣∣Orb(G′,u,v)∣=∣Aut(G)∣∣Aut(G′)∣\frac{|\text{Orb}(G,u,v)|}{|\text{Orb}(G',u,v)|} = \frac{|\text{Aut}(G)|}{|\text{Aut}(G')|}

정리 4.6 (자동동형 수정): 치환 등변 함수를 사용하면, pAˉ(a∣s)qAˉ(a∣s′)=∣Aut(G)∣∣Aut(G′)∣⋅pE(G′∣G)qE(G∣G′)\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 수정): 궤적 균형 손실은 다음과 같아야 합니다: LTB(τ)=(log⁡Z∏t=0n−1pE(Gt+1∣Gt)∣Aut(Gn)∣R(Gn)∏t=0n−1qE(Gt∣Gt+1))2L_{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

해결책: 보상을 R~(G)=∣Aut(G)∣R(G)\tilde{R}(G) = |\text{Aut}(G)|R(G)로 스케일링합니다.

2. 단편 생성의 수정

정리 5.3 (단편 수정): k개의 단편 {C₁,...,Cₖ}을 연결하여 생성된 종료 상태 G의 경우: R~(G)=∣Aut(G)∣R(G)∏i=1k∣Aut(Ci)∣\tilde{R}(G) = \frac{|\text{Aut}(G)|R(G)}{\prod_{i=1}^k |\text{Aut}(C_i)|}

3. 모델 우도의 편향 없는 추정

pˉA(x)=Eτ∼qE(τ∣Gn)[pE(τ)∣Aut(Gn)∣qE(τ∣Gn)]\bar{p}_A(x) = \mathbb{E}_{\tau \sim q_E(\tau|G_n)}\left[\frac{p_E(\tau)}{|\text{Aut}(G_n)|q_E(\tau|G_n)}\right]

기술적 혁신 포인트

  1. 이론적 우아성: 복잡한 전이 수준 수정을 종료 상태의 보상 스케일링으로 단순화합니다.
  2. 계산 효율성: 각 단계의 전이에서 그래프 동형 테스트를 피하고, 자동동형군 크기를 한 번만 계산합니다.
  3. 보편성: TB, DB, FM 등 다양한 GFlowNet 목적 함수에 적용 가능합니다.
  4. 정확성: 근사 해가 아닌 정확한 해를 제공합니다.

실험 설정

데이터셋

  1. 설명적 예제: 6개의 분리된 노드의 초기 상태, 112개의 종료 상태
  2. 합성 그래프: 최대 7개 노드의 이질 그래프, 72,296개의 종료 상태
  3. 분자 생성:
    • 원자 수준: HOMO-LUMO 갭 예측 작업
    • 단편 수준: sEH 표적 결합 에너지 예측 작업

평가 지표

  • L1 오류: 목표 확률과 모델 종료 확률 간의 L1 오류
  • 다양성: 분자 간 평균 Tanimoto 거리
  • 상위 K 지표: 상위 K개 높은 보상 분자의 다양성과 보상
  • 고유성: 생성된 샘플 중 고유 분자의 비율

비교 방법

  1. Vanilla GFlowNets: 그래프 대칭성을 고려하지 않음
  2. Transition Correction: 다중 동형 테스트를 통해 전이 동등 동작 식별
  3. PE (Ma et al., 2024): 위치 인코딩을 사용하여 궤도 동등 동작 근사 식별
  4. Reward Scaling (본 논문): 보상 신호 수정을 통한 수정
  5. Flow Scaling (본 논문): 각 전이 시 대칭 비율 곱하기

실험 결과

주요 결과

1. 설명적 실험

  • Vanilla 모델의 종료 확률은 |x|에 따라 군집화되며, 명백한 편향이 존재합니다.
  • Reward Scaling은 Transition Correction과 동일한 효과를 달성합니다.
  • 추정된 정규화 상수 Z: Reward Scaling은 112(참값), Vanilla는 26,706

2. 합성 그래프 실험

  • TB 목적: Reward Scaling은 L1 오류를 크게 감소시키며, Transition Correction과 성능이 동등합니다.
  • DB 목적: Reward Scaling은 수렴이 느리지만 최종적으로 동일한 정확도에 도달합니다.
  • PE 방법은 근사 해로서 Vanilla와 정확한 방법 사이의 성능을 보입니다.

3. 분자 생성 실험

원자 수준 생성 결과:

  • 다양성: 0.929→0.959 (Vanilla→Reward Scaling)
  • 고유성: 0.93→1.0

단편 수준 생성 결과:

  • 상위 K 보상: 0.941→0.952 (Vanilla→Reward Scaling Exact)
  • 사이클로헥산 단편 사용 횟수: 5220→1042 (대칭 단편의 과도한 사용 크게 감소)

절제 실험

  • 근사 수정 vs 정확 수정: 근사 방법도 성능을 크게 개선합니다.
  • 다양한 목적 함수: TB와 DB 모두 보상 스케일링을 통해 효과적으로 수정됩니다.

계산 효율성 분석

  • 자동동형 계산 시간: QM9 데이터셋 0.010ms, ZINC250k 데이터셋 0.022ms
  • 궤적 샘플링의 신경망 순전파 계산에 비해 계산 오버헤드는 무시할 수 있습니다.
  • 훈련 시간 비교: Reward Scaling은 Transition Correction보다 약 15% 빠릅니다.

관련 연구

자회귀 그래프 생성

  • 인접 행렬 방법: 노드 순서 정보를 유지하여 동등 동작 문제가 발생하기 쉽지 않습니다.
  • 그래프 수열 방법: 동등 동작을 쉽게 생성하며, 상태 전이 확률이 필요할 때 문제가 두드러집니다.

GFlowNets

  • 기존 목적 함수(흐름 매칭, 상세 균형, 궤적 균형 등)는 모두 동등 동작 문제를 피할 수 없습니다.
  • Ma et al. (2024)는 처음으로 문제를 식별했지만 근사 해만 제공합니다.

그래프 신경망 표현 능력

  • 치환 등변성으로 인해 동일 궤도 노드는 동일한 표현을 가집니다.
  • 제한된 표현 능력은 서로 다른 궤도 동작 표현이 겹칠 수 있습니다.

결론 및 논의

주요 결론

  1. 이론적 기여: GFlowNets의 동등 동작 문제를 처음으로 엄격하게 분석하고, 이것이 체계적 편향을 초래함을 증명합니다.
  2. 실용적 해결책: 보상 스케일링은 단순하고, 정확하며, 효율적인 수정 방법을 제공합니다.
  3. 광범위한 적용성: 방법은 원자 수준 및 단편 수준 생성, 그리고 다양한 훈련 목적에 적용 가능합니다.

한계

  1. 동작 설계 의존성: 이론적 보장은 특정의 사전 정의된 그래프 동작 집합에 의존합니다.
  2. 작업 특이성: 주로 분자 발견 관련 데이터셋에서 검증됩니다.
  3. GNN 표현 능력: 제한된 GNN 표현 능력은 추가 편향을 초래할 수 있습니다.

향후 방향

  1. 다양한 대칭 패턴과 보상 구조를 가진 작업 탐색
  2. 더 강한 표현 능력을 가진 GNN 아키텍처 설계
  3. 더 복잡한 그래프 생성 시나리오로 확장

심층 평가

장점

  1. 이론적 엄밀성: 완전한 수학적 프레임워크와 엄격한 이론 분석을 제공합니다.
  2. 방법의 단순성: 해결책이 매우 단순하여 구현 및 통합이 용이합니다.
  3. 실용적 가치: 분자 생성 등 중요한 응용에서 실제 효과를 보여줍니다.
  4. 계산 효율성: 비용이 많이 드는 온라인 그래프 동형 테스트를 피합니다.
  5. 강한 보편성: 다양한 GFlowNet 훈련 목적에 적용 가능합니다.

부족한 점

  1. 실험 범위: 주로 분자 생성 작업에 집중하며, 다른 그래프 생성 작업 검증이 제한적입니다.
  2. 이론적 가정: 특정 동작 설계 및 GNN 아키텍처 가정에 의존합니다.
  3. 근사 방법: 단편 생성의 근사 수정은 이론적 보장이 부족합니다.
  4. 확장성: 매우 큰 그래프의 경우 자동동형 계산이 병목이 될 수 있습니다.

영향력

  1. 학술적 가치: GFlowNets 이론에 중요한 보완을 제공하며 기초적 문제를 해결합니다.
  2. 실용적 가치: 약물 발견 등 응용 분야에 직접적 기여를 합니다.
  3. 재현성: 방법이 단순하여 재현 및 응용이 용이합니다.
  4. 영감: 다른 생성 모델의 대칭성 처리에 아이디어를 제공합니다.

적용 시나리오

  1. 분자 설계: 약물 발견, 재료 설계 등 화학 정보학 응용
  2. 그래프 생성: 구조 대칭성을 고려해야 하는 그래프 생성 작업
  3. 조합 최적화: 대칭성 제약이 있는 조합 최적화 문제
  4. 강화학습: 상태 공간이 대칭성을 가진 RL 작업

참고문헌

  1. Bengio et al. (2021) - GFlowNet 기초
  2. Ma et al. (2024) - 동등 동작 문제 처음 식별
  3. Malkin et al. (2022) - 궤적 균형 목적
  4. Jain et al. (2023) - 다목적 GFlowNets 응용

종합 평가: 이것은 이론과 실제를 모두 중시하는 우수한 논문으로, GFlowNets에서 중요하지만 간과된 기초 문제를 해결합니다. 방법은 단순하고 우아하며, 이론 분석은 엄격하고, 실험 검증은 충분합니다. GFlowNets 이론 발전과 실제 응용 모두에 중요한 기여를 하며, 관련 분야에 지속적인 영향을 미칠 것으로 예상됩니다.