Conformal Graph Prediction with Z-Gromov Wasserstein Distances

本論文は、グラフ出力に対する分布フリーの被覆保証を提供するため、Z-グロモフ・ワッサーシュタイン距離（実装上は FGW）に基づく非適合度定義と、グラフ空間に対応した適応的予測集合を得るためのスコア・コンフォーマライズド量子回帰（SCQR）を組み合わせた、新しいコンフォーマル予測フレームワークを提案しています。

要約

🎯 1. 問題：AI の「自信過剰」な予測

まず、この研究が解決しようとしている問題を想像してみてください。

化学の分野で、AI に「この質量スペクトル（物質の指紋のようなもの）から、どんな分子（グラフ）が作られているか推測して」と頼んだとします。
AI は「これはベンゼン環です！」と自信満々に答えます。

しかし、**「本当にそれだけ？」**と聞かれると、AI は答えに窮します。

• 「もしかしたら、似たような別の分子かもしれません」
• 「実験で確認するのにはお金がかかるので、間違っていたら大変です」

従来の AI は、**「一番確率が高い答えを 1 つだけ」**出すのが得意でしたが、「他の可能性も残しておいて、どれくらい自信があるか」を伝えるのが苦手でした。特に、分子のような「形やつながり」が重要なデータ（グラフ）の場合、その難しさは倍増します。

🛡️ 2. 解決策：「確実な保証付きの予測セット」

この論文が提案するのは、**「1 つの答え」ではなく「可能性のある答えのリスト（セット）」**を提示する方法です。

例えば、AI は「答えは 90% の確率で、このリストに入っています」と言えるようになります。

• リストの中に正解が入っている保証（90% なら 100 回中 90 回は当たる）が数学的に保証されています。
• これなら、実験室で「リストの 1 番目から順に試せば、高い確率で正解が見つかる」と安心できます。

これを**「コンフォーマル予測（Conformal Prediction）」**と呼びます。

🧩 3. 核心：どうやって「似ているか」を測るのか？（Z-グロモフ・ワッサーシュタイン距離）

ここがこの論文の最も面白い部分です。

分子グラフを比較する際、**「名前（ノード）の順番が違うだけで、実は同じ分子」**というケースがあります。

• 例：「A-B-C」という分子と、「C-B-A」という分子は、名前が逆順でも同じ構造です。

従来の方法だと、名前が違えば「全然違うもの」として扱ってしまい、AI の予測が少しズレただけで「不正解」と判断されてしまいます。

そこで、この論文では**「Z-グロモフ・ワッサーシュタイン距離（Z-GW）」**という新しいものさしを使います。

🍕 ピザの例え
2 枚のピザがあるとします。

• 1 枚は「トマト、チーズ、ベーコン」の順で乗っています。
• もう 1 枚は「ベーコン、チーズ、トマト」の順で乗っています。

従来のものさしは「順番が違うから、これは別のピザだ！」と言います。
しかし、Z-GWという新しいものさしは、「中身（具材）と、具材同士の関係性（隣り合っているか）」に注目します。「あ、これは同じピザの並び替えだ！」と理解し、「同じもの」として評価してくれます。

これにより、AI が「名前（ラベル）の入れ替え」に惑わされず、本当に「形や構造」が似ているかどうかを正しく測れるようになります。

🎛️ 4. 進化：状況に合わせて「リストのサイズ」を変える（SCQR）

最初の話に戻ると、AI が「自信がある場合」と「自信がない場合」で、提示するリストのサイズは同じでよいでしょうか？

• 自信がある場合（例：特徴的な分子）： リストは小さくてもいい（「これだけ！」で OK）。
• 自信がない場合（例：似た分子が多い）： リストを広く取らないと、正解が入らない。

従来の方法は、**「全員に同じ大きさのリスト」**を渡していましたが、これでは非効率です。

そこで、この論文では**「SCQR（スコア・コンフォーマライズド・クォンタイル・回帰）」**という新しいテクニックを導入しました。

🎯 的当てゲームの例え

• 昔の方法： 的が小さくても大きくても、全員に「直径 1 メートルの的」を渡す。
  • 結果：的が小さい人（自信がある人）には広すぎるし、的が大きい人（自信がない人）には狭すぎる。
• 新しい方法（SCQR）： 的の難易度を見て、**「難しい的には大きな的」「簡単な的には小さな的」**を渡す。
  • 結果：「90% 当たる」という保証は守りつつ、無駄なリスト（余計な候補）を減らして、より効率的に正解を見つけられる。

🧪 5. 実験結果：実際に使えるのか？

この方法は、2 つのテストで試されました。

1. 合成データ（色付けゲーム）： 画像からグラフを復元するタスク。
   • 結果：正解を 90% の確率でリストに含めつつ、候補の数を大幅に減らすことができました。
2. 実データ（代謝物の同定）： 質量分析計のデータから、どんな分子か特定するタスク（MassSpecGym というベンチマーク）。
   • 結果：従来の方法より、「候補リストのサイズ」を約 40% 減らしても、正解を逃さず見つけられることがわかりました。

🌟 まとめ

この論文が伝えていることはシンプルです。

「AI にグラフ（分子など）を予測させる時、Z-GW という『形と関係性』に特化したものさしを使い、状況に合わせて『確実な保証付きの候補リスト』を提示すれば、実験コストを節約しつつ、より安全に正解を見つけられる」

これは、化学や医療など、「間違えるとコストがかかる分野」において、AI をより信頼して使えるようにする重要な一歩です。

技術概要

論文要約：Conformal Graph Prediction with Z-Gromov Wasserstein Distances

この論文は、構造化されたグラフ出力を持つ回帰問題（Supervised Graph Prediction）において、分布フリーの保証を持つ不確実性定量化（Uncertainty Quantification）を行うための新しい枠組みを提案しています。特に、分子同定などの実用的なタスクにおいて、単一の予測値ではなく「信頼区間（予測集合）」を提供する手法を確立しました。

以下に、問題設定、手法、主要な貢献、結果、および意義について詳細にまとめます。

1. 背景と問題設定

• 背景: 化学（分子同定）やコンピュータビジョン（シーン理解）など、入力をグラフ構造（ノードとエッジ）として出力する「教師ありグラフ予測（SGP）」の需要が高まっています。
• 課題: 既存のグラフ予測手法は単一の予測値を出力しますが、実験的検証にコストがかかる分野（例：新規分子の発見）では、予測の信頼性を示す「不確実性の定量化」が不可欠です。
• 既存手法の限界:
  • グラフはノードの順序（ラベル付け）に依存しない（置換不変性）ため、ユークリッド空間とは異なり、自然な順序付けや距離定義が困難です。
  • 従来の Conformal Prediction（CP）は、複雑で非ユークリッドなグラフ空間への拡張が難しく、特に入力ごとの不確実性の違い（ヘテロスケダスティック性）を考慮した適応的な予測集合の構築が課題でした。

2. 提案手法：Z-Gromov-Wasserstein 距離に基づく Conformal Prediction

著者らは、グラフの置換不変性を保ちつつ、Conformal Prediction の理論的保証をグラフ空間に適用する新しいフレームワークを提案しました。

2.1 Z-Gromov-Wasserstein (Z-GW) 距離による非適合スコア

• 核心: グラフ間の距離測定に、Z-Gromov-Wasserstein (Z-GW) 距離を使用します。
• 仕組み:
  • グラフを「Z-ネットワーク」としてモデル化し、ノードの属性やエッジ構造を統合的に扱います。
  • 具体的には、Fused Gromov-Wasserstein (FGW) 距離を実用的なインスタンスとして採用します。これにより、グラフの構造（トポロジー）とノード/エッジの属性情報の両方を考慮した、ノードの置換に対して不変な距離（非適合スコア）を計算できます。
  • このスコアを用いることで、グラフ同型な異なるラベル付けを持つグラフ間でも一貫した比較が可能となり、商空間（Quotient Space）における妥当性が保証されます。

2.2 Score Conformalized Quantile Regression (SCQR)

• 目的: 単一のグローバルな閾値を使用する従来の CP では、入力によって難易度が異なる場合（簡単な入力と難しい入力）に、予測集合が過剰に大きくなったり、カバレッジが不足したりする問題があります。
• 手法:
  • SCQR を導入し、非適合スコアの条件付き分位数を入力依存の属性（例：候補グラフの集合サイズやスペクトルの埋め込み表現）に基づいて適応的に調整します。
  • これにより、局所的に適応的な（Adaptive）予測集合を生成しつつ、マージナルなカバレッジ保証（$P(Y \in C(X)) \ge 1-\alpha$）を維持します。

2.3 実用的な制約と候補集合の制限

• グラフ空間は組み合わせ的に膨大であるため、すべてのグラフを列挙して予測集合を構成することは不可能です。
• 提案手法では、入力に応じた候補集合（Candidate Library, $L(x)$）（例：質量スペクトルから推定される分子データベース）を定義し、その中で非適合スコアが閾値以下となるグラフのみを予測集合として抽出します。

3. 主要な貢献

1. Z-GW 距離に基づく Conformal Graph Prediction フレームワークの提案:
   • グラフの置換不変性を数学的に厳密に扱いつつ、商空間における妥当性を証明しました。
2. 局所適応型手法 SCQR の開発:
   • 複雑な出力空間（グラフ）におけるヘテロスケダスティック性を処理し、マージナルなカバレッジを保証したまま予測集合のサイズを縮小する手法を提案しました。
3. 実データでの検証:
   • 合成データ（画像からグラフへの予測）と実世界のタスク（質量スペクトルからの代謝物同定）の両方で、手法の有効性と汎用性を示しました。

4. 実験結果

• データセット:
  • 合成タスク (Coloring): 画像からグラフ構造を復元するタスク。
  • 実タスク (Metabolite Identification): MassSpecGym ベンチマークを用いた、質量スペクトルからの代謝物（分子）同定。
• 結果の要点:
  • カバレッジ保証: 両タスクにおいて、名目上のカバレッジ（90%）をほぼ達成し、理論的な保証が実証されました。
  • 効率性（予測集合のサイズ）:
    • 合成タスクでは、SCQR は標準的な CP と同等の性能を示しました。
    • 代謝物同定タスクでは、SCQR が顕著な改善を見せました。特に、スペクトルの埋め込み表現（DREAMS）を入力属性として利用した場合、平均予測集合サイズが標準 CP（24）から 15 に減少し、候補集合からの削減率が 77.1% から 84.8% に向上しました。
  • 距離指標の影響: 構造だけでなくノード属性も考慮する FGW は、構造のみを考慮する GW に比べて、より小さな予測集合（高い効率）を生成しました。

5. 意義と将来展望

• 科学的発見への貢献: 分子同定など、実験コストが高い分野において、AI モデルの予測に「信頼性」を付与することで、研究者が優先的に検証すべき候補を絞り込むことを可能にします。
• 理論的進展: 非ユークリッド空間、特にグラフのような構造化データに対する不確実性定量化の理論的基盤を強化しました。
• 汎用性: この枠組みは、メッシュ、点群、分布など、Z-ネットワークとして表現可能な他の構造化出力空間にも拡張可能です。

総じて、この論文は、グラフ予測タスクにおいて「正解かどうか」だけでなく「どの程度の確信度があるか」を数学的に保証する実用的かつ理論的に堅固な手法を提供した点で重要です。