DiPhon: 그래프론을 이용한 확장 가능한 그래프 생성 방법

DiPhon: Diffusion on Graphons for Scalable Graph Generation

확산 모델은 분자 설계와 같은 분야에서 상당한 영향을 미치며 그래프 생성의 주요 패러다임을 나타냅니다. 그러나 이러한 모델을 대규모 그래프에 적용하는 것은 여전히 해결해야 할 문제입니다. 본 연구에서는 그래프론, 즉 밀집 그래프 시퀀스의 크기-불변 극한 객체를 이용하여 구조적 그래프 통계가 노드 크기 척도에 따라 어떻게 변하는지 분석함으로써 이 문제를 밀집 그래프 환경에서 접근합니다. 이러한 관점은 DiPhon이라는 확장 가능한 그래프 생성 확산 프레임워크로 이어집니다. 구체적으로, 야코비 확률 미분 방정식(SDE)을 통해 그래프 공간에서의 연속적인 확산 과정을 정의하고, 이를 바탕으로 유한 그래프에서의 동역학을 모방하는 이산화된 그래프 수준 프로세스인 DiPhon을 제안합니다. 또한, 해당 역시간 프로세스를 도출하는데 필요한 주변 스코어를 얻습니다. 흥미롭게도 야코비 프로세스의 스코어는 계산 가능한 형태로 나타나며, 이는 데이터로부터 그래프 노이즈 제거를 통해 추정하고 역 프로세스에 적용하여 그래프 샘플을 생성하는 데 사용됩니다. DiPhon은 연속적인 그래프론 프로세스가 유도하는 주변 분포의 첫 번째 모멘트를 정확하게 일치시키고, 두 번째 모멘트는 닫힌 형태의 오차 내에서 근사합니다. 따라서 DiPhon은 그래프론 동역학의 핵심적인 크기-불변 통계적 특성을 상속하며, 확장 가능한 그래프 생성에 대한 체계적인 접근 방식을 제공합니다. 실험적으로, 작은 그래프로 학습하고 추론 시간에 점진적으로 더 큰 그래프를 생성하는 방법을 보여줌으로써 이러한 확장 가능성을 입증했으며, 이때 핵심적인 위상학적 특성을 유지했습니다.

Diffusion models represent a leading paradigm for graph generation, with notable impact in domains such as molecular design. Yet, scaling these models to large graphs remains an open problem. We approach this question in the dense-graph setting through the lens of graphons, the size-agnostic limit objects of dense graph sequences, to study how structural graph statistics behave across node-size scales. This perspective leads to DiPhon, a diffusion framework for size-scalable graph generation. Specifically, we formulate a continuous diffusion process on the graphon space via a Jacobi stochastic differential equation (SDE), and propose DiPhon, a discretized graph-level process that mimics these dynamics on finite graphs. We further derive the corresponding reverse-time process, which requires access to the marginal score. For the Jacobi process, this score interestingly admits a tractable form, which we estimate from data via graph denoising and plug into the reverse process to generate graph samples. We prove that DiPhon matches exactly the first moment of the marginal distributions induced by the continuous graphon process, and approximates the second moment up to a closed-form discrepancy. Thus, DiPhon inherits key size-agnostic statistical properties of the graphon dynamics, providing a principled route toward scalable graph generation. Empirically, we demonstrate this scalability by training on small graphs and generating progressively larger graphs at inference time, without retraining, while preserving their core topological properties.