MST 機構の解説（Maximum Spanning Tree）

手法選定ガイド｜ AIM の解説｜ INDEPENDENT の解説｜ Private-PGM の解説｜メインレポート

📘 本ページのアルゴリズム・実装の記述は、原論文 arXiv:2108.04978 と google/dpsynth のソースコード（dpsynth/discrete_mechanisms/mst.py、2026-06 時点の main ブランチ）に基づく。実験数値の節（🔎）のみ本デモの実測である。

1. 位置づけ

MST（Maximum Spanning Tree）機構は、NIST の合成データコンテスト優勝手法として知られる DP 合成データ生成アルゴリズムである arXiv:2108.04978。属性間のペア相関（2-way マージナル）のうち「最も相関の強い組み合わせで作る 1 本の木（最大全域木）」だけを差分プライバシーを満たしつつ選んで測定し、Private-PGM で同時分布を推定する。

DPSynth の In-Memory API dpsynth.generate() のデフォルト機構は MST である （discrete_config 引数のデフォルト値が MSTConfig()）。ただしこれは引数の既定値にすぎず、データに応じた自動選定ではない点に注意（→ 手法選定ガイド）。

2. アルゴリズムの仕組み

flowchart LR A["① 1-way マージナル測定
ガウス機構（予算 1/3）"] --> B["② ペア相関の重み計算
独立モデルからの L1 乖離"] B --> C["③ DP 版クラスカル法
指数機構（予算 1/3）で
最大全域木を構築"] C --> D["④ 木の辺の 2-way マージナル測定
ガウス機構（予算 1/3）"] D --> E["⑤ Private-PGM で
同時分布を推定"] E --> F([合成データを
サンプリング])

1-way 測定: 全列の周辺分布をガウス機構（集計値に正規ノイズを加える DP の基本機構）で測定する。
ペア相関のスコアリング: ノイズ付き 1-way から独立モデルを作り、各属性ペア (a, b) について「真の 2-way マージナル」と「1-way 同士の外積（独立を仮定した場合の予測）」の L1 距離を重みとする。独立仮定から乖離しているペアほど「相関が強い」とみなす（感度 1 の統計量になるよう設計されている）。
DP 版クラスカル法: 重み最大の辺を貪欲に選ぶ代わりに、各ラウンドで指数機構 （スコアに応じた確率で候補を選ぶ DP 機構）により 1 辺ずつ選び、列数 −1 本の辺からなる全域木を作る。
2-way 測定: 木に選ばれた辺（属性ペア）の 2-way マージナルをガウス機構で測定する。
推定と生成: すべてのノイズ付き測定値を Private-PGM（mbi）に渡し、測定値と整合する同時分布（マルコフ確率場）を mirror descent で推定し、そこからサンプリングする。

選定は最初に 1 回だけ行われ、AIM のような反復・適応はない。

3. プライバシー予算の使われ方

MSTConfig のデフォルトでは、zCDP 換算の総予算 ρ を 3 等分して使う。

ステップ	予算配分（既定）	機構
1-way マージナル測定	ρ × 1/3（`one_way_budget_fraction`）	ガウス機構
全域木の辺の選定	ρ × 1/3（`select_budget_fraction`）	指数機構（辺ごとに ε = √(8ρ′/(d−1)) を機械的に分配）
2-way マージナル測定	ρ × 残り 1/3	ガウス機構

4. 主なパラメータ（`MSTConfig`）

パラメータ	既定値	意味
`pgm_iters`	5000	Private-PGM（mirror descent）の反復回数
`seed`	0	乱数シード
`maximum_marginal_size`	10,000,000	候補に含める 2-way マージナルのセル数上限（高カーディナリティ対策）
`one_way_budget_fraction` / `select_budget_fraction`	1/3, 1/3	上記の予算配分

5. 得意なケース・苦手なケース

得意:

速度と品質のバランス: 1 回の選定 + (d−1) 個の 2-way 測定で済むため高速。最初に試すベースラインに向く。
相関構造が「木」に近いデータ（強い相関が連鎖的につながっているデータ）。
列数・予算が限られていて、AIM の反復に予算を割けない場合。

苦手:

全域木に載らないペアの相関は保持されない。木は d−1 本の辺しか持てないため、関心のあるペアが選から漏れると、そのペアの同時分布は大きく崩れうる（下記の実験C）。
ユーザが「このペア相関を重視したい」と意図を伝える口（ワークロード指定）がない。
3 つ以上の属性が絡む高次の相関（3-way 以上）はそもそもモデル化しない。

6. 本デモでの実験結果

🔎 以下は本デモ（UCI Adult、20,000 行、9 列、δ=1e-5）の実測。詳細は各リンク先を参照。

機構比較（ε=1.0、メインレポート §5.1）: 平均 1-way TVD 0.101、相関誤差 0.089、 TSTR AUC 0.663、生成時間約 10 秒（単一シード）。
複数シード（追加実験B）: TSTR AUC 0.651 ± 0.106（10 シード）。 AIM（0.709 ± 0.051）をやや下回るが標準偏差が重なり、優劣はシード次第で逆転しうる（AIM ≳ MST）。
2-way 忠実度（追加実験C）: ペアによって明暗が分かれる。 education×income は 0.024 と良好だが、木から外れた marital-status×income（0.359）・ occupation×income（0.282）は大きく崩れ、INDEPENDENT より悪いケースもあった。
ε スイープ（複数シード・追加実験E）: ε を 0.5 → 10 に上げると平均 1-way TVD は 0.089 → 0.061 へおおむね改善する（ε=0.5→1.0 は分散内の微増、それ以降は単調低下。標準偏差も ε とともに縮む）。

全域木制約による「ペアの崩れ」（アルゴリズム由来の解釈）

🔎 以下は、上記 2-way 忠実度の結果に対する、MST アルゴリズム arXiv:2108.04978 の構造的制約からの解釈である。検証対象 DPSynth についての「列間依存が下流有用性に効く」という要約はメインレポート §6.1 にある。

MST が保持できる 2-way 依存は、最大全域木に選ばれた d−1 本の辺だけである。推定エンジン（Private-PGM）には木構造のクリークしか渡されないため、 木から外れた属性ペアは独立として推定される。

選定は ① ノイズ付きの 1-way から推定したペア相関スコアに基づき、② 最初に 1 回だけ行われる。そのため、本当は相関が強いのにノイズや木の容量（d−1 本）の都合で落ちたペアは、相関が丸ごと失われる。
独立扱いになるだけなら INDEPENDENT と同等に見えるが、実際には木に載った辺の制約を介して間接的に誤った相関が回り込むことがあり、その場合は独立仮定の INDEPENDENT より悪化する。本デモの marital-status×income（MST 0.364 vs INDEPENDENT は中位）はこの例で、「相関を張るより張らない方がマシ」という逆転が起きうる（追加実験C・INDEPENDENT 解説 §6）。

これは MST の欠陥というより「強い相関が木状につながっている」という前提が崩れたときの構造的限界である。広いペア相関を木の制約なしに拾える AIM が、同じペアで大きく上回った（0.034）のと対照的である。 MST 採用時は、関心のあるペアの 2-way 分布を実データと突き合わせて検証することが望ましい。

7. 参考リンク

原論文: McKenna et al., Winning the NIST Contest: A scalable and general approach to differentially private synthetic data — arXiv:2108.04978
実装: dpsynth/discrete_mechanisms/mst.py
公式ドキュメント: google/dpsynth README「Supported Synthesis Algorithms」
推定エンジン: Private-PGM / mbi

← 手法選定ガイドに戻る