技術的概要：Blocked Gibbs と Diffusion Transformers の融合

問題定義

制約最適化問題（COP）および制約充足問題（CSP）は、実世界の応用において基礎的であるが、しばしば計算的に扱いが困難である。古典的な反復法（例：局所探索、大規模近傍探索）は効果的であるが、通常は手動設計された提案メカニズムを用いて、各インスタンスをゼロから解決する。これらの問題への拡散モデルの適用を試みた最近の取り組みは有望であるが、2 つの決定的な限界に直面している：

1. アーキテクチャの制限：既存の拡散アプローチの多くはグラフニューラルネットワーク（GNN）に依存しており、これは疎で固定されたトポロジーには優れているが、一般的な離散変数や密な制約に必要なグローバルな依存関係や長距離相互作用を捉えるのに苦労する。
2. プロセスの不一致：標準的な拡散モデルは、すべての変数に対して同時に小さな段階的なガウスノイズ除去を適用する。これは制約解決の性質と矛盾しており、近似的に実行可能な解を改善するには、残りの割り当てをそのままに保ちながら、特定の変数のサブセットを大幅に変更する（例：特定の違反した制約を解決する）必要がある場合が多い。グローバルなノイズ除去スケジュールを用いた Diffusion Transformers（DiT）の単純な適用は、汎化性能の低下と最適解の欠如をもたらす。

手法：BloGDiT

著者は、Transformer のグローバルなモデル化能力と、Blocked Gibbs サンプリングの標的更新メカニズムを統合するフレームワークである**Blocked Gibbs Diffusion Transformer（BloGDiT）**を提案する。

1. コアメカニズム：Blocked Gibbs Diffusion

解をグローバルにノイズ除去すべき単一の結合分布として扱うのではなく、BloGDiT は生成を条件付き更新の系列として捉える：

• マスク付きリサンプリング：各逆拡散ステップ $t$ において、二値マスク $m_t$ が更新する特定の変数のサブセット（ブロック）を選択する。
• 条件付きノイズ除去：モデルは選択されたブロックに連続的なガウスノイズを適用し、残りの「クリーン」（マスクされていない）変数に条件付けて、Transformer を用いてこのブロックをノイズ除去する。マスクされていない変数は変更なしにコピーされる。
• アニーリングスケジュール：ブロックサイズ（マスク率 $\rho_t$）は時間とともにアニーリングされる。初期ステップではグローバルな探索を促進するために大きなブロックを使用し、後期のステップでは精密な局所改善のために小さなブロックを使用する。

2. アーキテクチャとトレーニング

• Transformer バックボーン：BloGDiT はグローバル注意機構を備えた Transformer アーキテクチャを利用し、GNN が局所的なメッセージパッシングに制限されるのに対し、任意の変数ペア間の相互作用をモデル化することを可能にする。
• 連続緩和：モデルは離散値上の確率分布を表す連続的なログイト空間（$Z_t \in \mathbb{R}^{n \times K}$）で動作する。エネルギー関数は、連続的なペナルティを介して緩和された変数上で定義される。
• 教師なし目的関数：モデルは、ボルツマン分布 $p_B(X) \propto \exp(-H(X)/\tau)$ からサンプリングするようにトレーニングされる。ここで、$H(X)$ は目的関数と制約ペナルティを組み合わせる。
  • トレーニング目的関数は、モデルの軌道と目標ボルツマン分布間の逆 KL 発散を上限評価することで導出される。
  • 得られる損失には、エネルギー項（$H(X_0)$ の最小化）、エントロピー項（多様性の促進）、前方ノイズ適合項、およびマスク分布適合項が含まれる。
  • 重要なのは、マスク選択分布が前方プロセスと逆プロセスで共有されるため、マスク発散項が消滅することである。

3. 適応的マスク選択

推論中は、静的なランダムなマスク選択を、更新の恩恵を受けると考えられる変数を優先する適応戦略に置き換えることができる：

• コンフィデンス・マージン：モデルが不確実である変数（トップログイト間のマージンが小さい）を優先する。
• 違反ベース：現在違反している制約に関与している変数を優先する。
• 関連変数：共通の制約に参加する変数のグループを選択する。

主要な貢献

1. 新規アルゴリズム：BloGDiT は、結合ガウスノイズ除去をブロック化ガウスノイズ除去に置き換えることで、標準的な拡散と制約解決の間の不一致に対処する最初の手法である。
2. アーキテクチャの転換：これは、Transformerが GNN の局所性の制限を克服し、一般的な離散（非二値）変数を処理しながら、制約推論のための効果的なバックボーンとなり得ることを実証している。
3. 理論的定式化：本論文は、ラベル付き解データなしでボルツマン目標からサンプリングするための、扱い可能な教師なしトレーニング目的関数（マスク付加結合 KL 上限）を導出した。
4. 帰納的バイアス：「ブロック化 Gibbs 風」の更新が、Transformer ベースの制約充足に対して非常に効果的な帰納的バイアスを提供し、変数ブロック内での大規模かつ標的的な編集を可能にすることを確立している。

実験結果

BloGDiT は、4 つの多様なベンチマークで評価された：数独（非二値 CSP）、グラフ彩色（非二値 CSP）、最大独立集合（MIS）（二値 COP）、および最大カット（二値 COP）。

• 標準拡散（DiT）との比較：BloGDiT は、バニラ DiT を大幅に上回る。例えば、困難な数独の分布外（OOD）インスタンスにおいて、BloGDiT は94.1%の精度を達成するのに対し、DiT は48.6%である。MIS においては、平均集合サイズが（RB-large で）37.05であるのに対し、DiT は0.29である。
• 専門化された GNN との比較：BloGDiT は、二値グラフ問題において GNN ベースの拡散手法（例：DiffUCO、DIFUSCO）と競合するか、それらを上回る一方、数独やグラフ彩色のような非二値問題のサポートを独自に提供している。
• 学習型ではないソルバーとの比較：
  • 数独において、BloGDiT は簡単なインスタンスでは正確なソルバーである OR-Tools と同等の性能を発揮し、困難な OOD インスタンスでは最も強力な学習済み性能（94.1%）を達成する。
  • 最大カットにおいて、BloGDiT はすべてのグラフサイズ（800 から 10,000 ノード）で OR-Tools および他の学習済みヒューリスティックを上回り、既知の最良解との最小のギャップを達成する。
  • グラフ彩色において、困難なインスタンスでは $k=10$ に対して OR-Tools を上回る。
• アブレーション研究：
  • マスクアニーリング：ブロックサイズが初期に小さすぎると（グローバルな探索を妨げる）、または最後に大きすぎると（微細な修復を妨げる）場合、性能は低下する。
  • 適応的選択：適応的マスク選択（例：制約違反に基づく）を使用すると、MIS や最大カットのような困難な最適化タスクにおいて特に性能が大幅に向上する。
  • エントロピー項：損失からエントロピー項を除去すると性能が低下し、これは探索の維持と早期の崩壊の防止におけるその役割を示している。

意義と主張

本論文は、BloGDiT が「Blocked Gibbs」の視点を採用することで、拡散モデルと制約最適化の間のギャップを成功裡に埋めたと主張している。著者は以下のように論じている：

• 制約解決は、均一で小刻みな更新ではなく、変数のサブセットに対する標的的で大規模な編集から恩恵を受ける。
• Transformerは、グローバルな依存関係をモデル化する能力により、一般的な制約推論において GNN より優れている。
• Transformer バックボーンとブロック化 Gibbs 更新の組み合わせは、広範な制約問題に対する強力で再利用可能かつ教師なしのヒューリスティックを提供し、専門的なニューラルベースライン、場合によっては最先端の正確なソルバーさえも凌駕する。

著者は限界に関して謙虚であり、この手法は（MCMC とは異なり）正確なサンプリング保証を提供しないことを指摘し、将来の研究としては、ドメイン上で直接離散拡散を探索するか、真のボルツマン分布をよりよくターゲットにするために MCMC 風の修正（例：メトロポリス・ヘイスティングス）を組み込むことが考えられるとしている。