技術要約：DiPhon – スケーラブルなグラフ生成のためのグラフォン上の拡散モデル

1. 問題提起

拡散モデルは、分子設計やニューラルアーキテクチャ探索といった領域において、グラフ生成の主要なパラダイムとして確立されています。しかし、これらのモデルを大規模なグラフへとスケールアップさせることは、依然として根本的な課題です。既存のアプローチには、主に以下の2つの制限があります：

1. 学習およびデプロイのコスト： 大規模なグラフを扱う場合、拡散モデルの学習とデプロイには膨大な計算コストがかかります。
2. サイズの転移性の欠如： 小規模なグラフで学習されたとしても、学習された生成メカニズムが、再学習なしに大きなグラフサイズへと一般化できるかどうかは不明なままです。

既存のグラフ拡散手法は、高密度グラフの設定においてこの問題に対処することに苦慮しています。離散拡散モデルはカテゴリカルなエッジ変数上で動作するため、グラフォン（graphon）が要求する連続的な空間ドメインへの自然な拡張ができません。一方で、ガウス型SDEベースの手法は、点ごとにノイズを注入しますが、これは非有界な軌跡を生み出します。そのため、エッジ確率（$[0, 1]$ の範囲に収まる必要がある）として直接解釈することができず、グラフォン理論との接続はせいぜい暗黙的なものにとどまっています。

2. 手法

本論文では、高密度グラフ列のサイズに依存しない極限オブジェクトであるグラフォン（graphon）を活用した、サイズスケーラブルなグラフ生成のための拡散フレームワークであるDiPhonを提案します。本手法は、連続的なグラフォン動力学と離散的なグラフ生成の間の溝を、以下のステップを通じて埋めるものです。

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)$ は定常平均、$\kappa > 0$ は引き込み率、$\sigma > 0$ はノイズ強度です。拡散項は境界において消失するため、プロセスは有界に保たれます。

2.2 離散化：グラフォンからグラフへ

連続的なグラフォンは直接観測できないため、著者らは**離散化してから拡散する（discretize-then-diffuse）**戦略を提案しています。まず、単位正方形を $N^2$ 個のセルに分割し、各セルに対して離散プロセス $\tilde{W}_t^{ij}$ を定義します。

• 再正規化： 離散プロセスが連続的な「拡散してから離散化する」理想の統計的特性と一致するように、離散SDEのパラメータを再正規化します。具体的には、ノイズ振幅をスケーリングし（$\tilde{\sigma}^2 = \sigma^2 N^2$）、離散化による補償のためにドリフト率（$\tilde{\kappa}$）を調整します。
• 初期条件： プロセスは、観測されたバイナリグラフ $A_0$ から開始されます。ここで、各エントリー $A_0^{ij}$ は、基礎となるグラフォンセルの平均値のベルヌーイ標本として扱われます。

2.3 逆プロセスと学習

逆時間SDEは、標準的なスコアベースの定式化を用いて導出され、周辺スコア $\nabla \log \tilde{p}_t$ を必要とします。

• 扱いやすいスコア： Jacobiプロセスの場合、条件付きスコアは、シフトされたヤコビ多項式とその導関数を含む閉形式の表現を持ちます。
• デノイジング目的関数： 真の初期グラフォン・エントリーは観測されないため、著者らはノイズを含んだ状態 $\tilde{W}_t$ からクリーンな初期グラフ $A_0$ を予測するように、グラフニューラルネットワーク（GNN）$\Phi_\theta$ を訓練します。ネットワークは、バイナリクロスエントロピー損失（デノイジング目的関数）を用いて訓練されます。
• サンプリング： 推論時、逆SDEは定常分布（ベータ分布）から $t=0$ に向かって逆方向に積分されます。学習されたデノイザーは、各ステップで必要なスコア推定を提供し、最終的な状態は独立したベルヌーイ試行によってバイナリグラフへと変換されます。

3. 主な貢献

本論文は、主に4つの貢献を行っています：

1. C1 (定式化): グラフォンに基づく新しい拡散プロセスをJacobi SDEを用いて定式化し、これに基づきDiPhonを導出しました。
2. C2 (モーメントの一致): 離散的なDiPhonプロセスが、連続的なグラフォンプロセスの一次モーメントと正確に一致することを示す理論的特性付けを行いました。二次モーメントの不一致についても閉形式で導出されており、それがセル内の分散と離散化因子によって制御され、グラフサイズが増大するにつれて消失することが示されています。
3. C3 (サンプリングと極限): モデルの周辺分布からグラフを生成するサンプリング手順を提示しています。著者らは、定常領域において、生成されたグラフがErdős–Rényiグラフォンにホモモルフィズム密度において収束することを証明し、プロセスの構造的極限を確立しました。
4. C4 (経験的なスケーラビリティ): DiPhonが小規模なグラフで学習され、再学習なしに、様々なグラフファミリーにわたって核となるトポロジー的特性を維持しながら、より大きなアウトオブディストリビューション（OOD）のグラフを正常に生成できることを実証する経験的検証を行いました。

4. 実験結果

著者らは、SBM（Stochastic Block Models）、PA（Preferential Attachment）グラフ、および木（Trees）の3つの合成グラフファミリーを用いてDiPhonを評価しています。

• 設定： モデルは小規模なグラフ（例：40–80ノード）で訓練され、段階的に大きなサイズ（最大300ノード）のテストが行われます。
• ベースライン： DiPhonは、離散拡散法（DiGress, DeFoG）およびガウス拡散モデル（GDSS, GruM）と比較されます。
• 知見：
  • モーメントの一致： 実験により、離散化されたプロセスの経験的な平均と分散が、連続グラフォン理論から導出された理論的な閉形式のリファレンスと一致することが確認されました。
  • スケーラビリティ： DiPhonは、すべてのデータセットおよびノードサイズにおいて高い精度を維持しています。対照的に、離散拡散法は大規模なサイズで性能が崩壊し、ガウス型のベースラインは、特に木構造において一貫性を欠く傾向が見られました。
  • 堅牢性： 特筆すべきは、DiPhonが形式的なグラフォン理論が厳密には適用されない疎な領域である**木（Tree）**グラフに対しても効果的であることです。これは、本手法の経験的な適用範囲が理論的保証を超えていることを示唆しています。

5. 意義と主張

本論文は、グラフォンを拡散ダイナミクスの担い手として利用することで、DiPhonがスケーラブルなグラフ生成への原理的な経路を提供すると主張しています。

• サイズ非依存性： グラフォン空間で動作することにより、モデルは本質的にノード数に依存しない分布を学習し、小規模な訓練レジームから大規模な推論レジームへの転移を可能にします。
• 理論的根拠： Jacobi SDEの使用は、エッジ確率を有界に保ち、モーメント一致およびホモモルフィズム密度における収束に関する厳密な分析を可能にします。これは、従来のガウス型または離散型のアプローチにおける限界に対処するものです。
• 実用的な有用性： 再学習なしに大規模なグラフを生成できる能力は、分子設計やネットワーク分析など、可変のグラフサイズを必要とするアプリケーションにおいて大きな利点となります。

著者らは、理論的保証が密なグラフに対して開発されており、分布全体の距離を境界付けるのではなくモーメントの一致に基づいていることを挙げ、限界についても認めています。また、訓練プロセスはフォワード・トラジェトリのシミュレーションを必要とするため、トラクタブルな遷移密度を持つモデルと比較してオーバーヘッドが生じます。しかし、本フレームワークは、将来的な研究においてノード特徴量や重み付きエッジへと自然に拡張できる基礎として提示されています。