기술 요약: DiPhon – 확장 가능한 그래프 생성을 위한 그래프온 상의 확산 (Diffusion on Graphons)

1. 문제 정의

확산 모델(Diffusion models)은 특히 분자 설계 및 신경 구조 탐색(Neural Architecture Search)과 같은 영역에서 그래프 생성의 선도적인 패러다임으로 자리 잡았습니다. 그러나 이러한 모델을 대규모 그래프로 확장하는 것은 여전히 근본적인 과제로 남아 있습니다. 기존 방식들은 두 가지 주요한 한계에 직면해 있습니다:

1. 훈련 및 배포 비용: 확산 모델은 대규모 그래프를 다룰 때 계산 비용이 많이 듭니다.
2. 크기 전이성(Size Transferability) 부족: 작은 그래프로 학습했을 때, 학습된 생성 메커니즘이 재학습 없이 더 큰 그래프 크기로 일반화될 수 있는지 여부가 불분명합니다.

기존의 그래프 확산 방법들은 조밀한 그래프(dense-graph) 설정에서 이러한 문제를 해결하는 데 어려움을 겪습니다. 이산 확산 모델(Discrete diffusion models)은 범주형 에지 변수 위에서 작동하여 그래프온(graphon)에 필요한 연속적인 공간적 확장을 자연스럽게 구현하지 못합니다. 반대로 가우시안 SDE 기반 접근법은 점 단위로 노이즈를 주입하지만 유계되지 않은 궤적을 생성하며, 이는 $[0, 1]$ 범위 내에 있어야 하는 에지 확률로서 직접적으로 해석될 수 없으므로 그래프온 이론과의 연결이 기껏해야 암시적인 수준에 그칩니다.

2. 방법론

본 논문은 조밀한 그래프 시퀀스의 크기에 무관한 극한 객체인 **그래프온(graphons)**을 활용하여, 크기 확장 가능한 그래프 생성을 위한 확산 프레임워크인 DiPhon을 제안합니다. 이 방법론은 연속적인 그래프온 역학(dynamics)과 이산 그래프 생성 사이의 간극을 다음과 같은 단계들을 통해 메웁니다:

2.1 순방향 과정: Jacobi SDE를 통한 그래프온 확산

저자들은 연속적인 그래프온 공간 $W: [0, 1]^2 \to [0, 1]$ 상에서 직접적인 연속 확산 과정을 공식화합니다. 프로세스가 유효한 확률 범위인 $[0, 1]$ 내에 머물도록 하기 위해, 저자들은 **Jacobi 확률 미분 방정식(SDE)**을 채택합니다:
$$dW_t(x, y) = \kappa (\mu - W_t(x, y)) dt + \sigma \sqrt{W_t(x, y)(1 - W_t(x, y))} dB_t(x, y)$$
여기서 $\mu \in (0, 1)$는 정지 평균(stationary mean), $\kappa > 0$은 인력률(pull rate), $\sigma > 0$은 노이즈 강도입니다. 확산 항은 경계에서 소멸하여 프로세스를 유계(bounded) 상태로 유지합니다.

2.2 이산화: 그래프온에서 그래프로

연속적인 그래프온은 직접 관측할 수 없으므로, 저자들은 이산화 후 확산(discretize-then-diffuse) 전략을 제안합니다. 단위 정사각형을 $N^2$개의 셀로 분할하고 각 셀에 대해 이산 과정 $\tilde{W}_t^{ij}$를 정의합니다.

• 재정규화(Renormalization): 이산 과정이 연속적인 "확산 후 이산화(diffuse-then-discretize)"의 통계적 특성과 일치하도록 하기 위해, 이산 SDE의 파라미터를 재정규화합니다. 구체적으로, 노이즈 진폭을 스케일링($\tilde{\sigma}^2 = \sigma^2 N^2$)하고, 이산화에 따른 보상을 위해 드리프트율($\tilde{\kappa}$)을 조정합니다.
• 초기 조건: 프로세스는 관측된 이진 그래프 $A_0$에서 시작되며, 각 엔트리 $A_0^{ij}$는 밑에 있는 그래프온 셀 평균의 베르누이 샘플로 취급됩니다.

2.3 역과정 및 학습

역시간 SDE는 표준 스코어 기반 정식화(score-based formulation)를 사용하여 유도되며, 이는 주변 스코어(marginal score) $\nabla \log \tilde{p}_t$를 필요로 합니다.

• 다루기 쉬운 스코어: Jacobi 프로세스의 경우, 조건부 스코어는 **이동된 Jacobi 다항식(shifted Jacobi polynomials)**과 그 도함수를 포함하는 폐쇄형(closed-form) 표현을 가집니다.
• 디노이징 목적 함수: 실제 초기 그래프온 엔트리는 관측되지 않으므로, 저자들은 노이즈가 섞인 상태 $\tilde{W}_t$로부터 깨끗한 초기 그래프 $A_0$를 예측하도록 그래프 신경망(GNN) $\Phi_\theta$를 학습시킵니다. 네트워크는 이진 교차 엔트로피 손실(denoising objective)을 통해 학습됩니다.
• 샘플링: 추론 시에는 정지 분포(Beta 분포)로부터 $t=0$까지 역방향 SDE를 적분합니다. 학습된 디노이저(denoiser)는 각 단계에서 필요한 스코어 추정치를 제공하며, 최종 상태는 독립적인 베르누이 추출을 통해 이진 그래프로 변환됩니다.

3. 주요 기여

본 논문은 네 가지 주요 기여를 합니다:

1. C1 (정식화): Jacobi SDE를 기반으로 한 그래프온을 위한 새로운 확산 프로세스를 제안하며, 이를 통해 DiPhon이 유도됩니다.
2. C2 (모멘트 정렬): 이산 DiPhon 프로세스가 연속 그래프온 프로세스의 1차 모멘트와 정확히 일치함을 보여주는 이론적 특성화를 수행합니다. 2차 모멘트의 불일치는 폐쇄형으로 유도되며, 셀 내부 분산 및 이산화 인자에 의해 제어되고 그래프 크기가 증가함에 따라 소멸함을 보여줍니다.
3. C3 (샘플링 및 극한): 모델의 주변 분포로부터 그래프를 생성하는 샘플링 절차를 제안합니다. 저자들은 정지 영역(stationary regime)에서 생성된 그래프가 Erdős–Rélnyi 그래프온으로 호모모피즘 밀도(homomorphism density) 측면에서 수렴함을 증명하여, 프로세스의 구조적 극한을 확립합니다.
4. C4 (경험적 확장성): DiPhon이 작은 그래프에서 학습되어 재학습 없이도 다양한 그래프 군에서 핵심적인 위상적 특성을 보존하며 더 큰 규모의 분포 외(out-of-distribution) 그래프를 성공적으로 생성할 수 있음을 실험적으로 검증합니다.

4. 실험 결과

저자들은 SBM(Stochastic Block Models), PA(Preferential Attachment) 그래프, 그리고 트리(Trees)와 같은 세 가지 합성 그래프 군에 대해 DiPhon을 평가합니다.

• 설정: 모델은 작은 그래프(예: 노드 40~80개)로 학습되며, 점진적으로 더 큰 크기(최대 노드 300개)로 테스트됩니다.
• 베이스라인: DiPhon은 이산 확산 방법(DiGress, DeFoG) 및 가우시안 확산 모델(GDSS, GruM)과 비교됩니다.
• 결과:
  • 모멘트 정렬: 실험을 통해 이산화된 프로세스의 경험적 평균과 분산이 연속 그래프온 이론에서 유도된 이론적 폐쇄형 참조값과 일치함을 확인했습니다.
  • 확장성: DiPhon은 모든 데이터셋과 노드 크기에 대해 높은 정확도를 유지합니다. 반면, 이산 확산 방법은 더 큰 크기에서 성능 붕괴를 보이며, 가우시안 베이스라인은 특히 트리 구조에서 일관성이 없는 모습을 보입니다.
  • 강건성: 주목할 점은, DiPhon이 그래프론적 이론이 엄격하게 적용되지 않는 희소(sparse) 영역인 트리 그래프에서도 효과적이라는 것이며, 이는 이 방법의 경험적 범위가 이론적 보증을 넘어섬을 시사합니다.

5. 의의 및 주장

본 논문은 그래프온을 확산 역학의 전달체로 활용함으로써 확장 가능한 그래프 생성을 향한 원칙적인 경로를 제공한다고 주장합니다.

• 크기 무관성(Size-Agnosticity): 그래프온 공간에서 작동함으로써, 모델은 노드 수와 독립적인 분포를 본질적으로 학습하며, 이를 통해 작은 훈련 규모에서 큰 추론 규모로의 전이를 가능하게 합니다.
• 이론적 근거: Jacobi SDE의 사용은 유계된 에지 확률을 보장하며, 모멘트 매칭 및 호모모피즘 밀도 수렴에 대한 엄격한 분석을 가능하게 하여 기존의 가우시안 또는 이산 접근법의 한계를 해결합니다.
• 실용적 유용성: 재학습 없이 대규모 그래프를 생성할 수 있는 능력은 분자 설계나 네트워크 분석과 같이 가변적인 그래프 크기가 필요한 응용 분야에서 상당한 이점을 제공합니다.

저자들은 이론적 보증이 조밀한 그래프를 위해 개발되었으며, 전체 분포적 거리를 제한하기보다는 모멘트 매칭에 의존한다는 점을 언급하며 한계를 인정합니다. 또한, 훈련 과정에서 순방향 궤적을 시뮬레이션해야 하므로 트랙터블한 전이 밀도(tractable transition densities)를 가진 모델에 비해 오버헤드가 발생할 수 있습니다. 그러나 이 프레임십은 향후 노드 특징 및 가중치 에지로 자연스럽게 확장될 수 있는 토대로서 제시됩니다.