2025-11-18T15:28:13.400087

Local Causal Discovery for Statistically Efficient Causal Inference

Schubert, Claassen, Magliacane

Causal discovery methods can identify valid adjustment sets for causal effect estimation for a pair of target variables, even when the underlying causal graph is unknown. Global causal discovery methods focus on learning the whole causal graph and therefore enable the recovery of optimal adjustment sets, i.e., sets with the lowest asymptotic variance, but they quickly become computationally prohibitive as the number of variables grows. Local causal discovery methods offer a more scalable alternative by focusing on the local neighborhood of the target variables, but are restricted to statistically suboptimal adjustment sets. In this work, we propose Local Optimal Adjustments Discovery (LOAD), a sound and complete causal discovery approach that combines the computational efficiency of local methods with the statistical optimality of global methods. First, LOAD identifies the causal relation between the targets and tests if the causal effect is identifiable by using only local information. If it is identifiable, it then finds the optimal adjustment set by leveraging local causal discovery to infer the mediators and their parents. Otherwise, it returns the locally valid parent adjustment sets based on the learned local structure. In our experiments on synthetic and realistic data LOAD outperforms global methods in scalability, while providing more accurate effect estimation than local methods.

academic

統計的に効率的な因果推論のための局所因果発見

基本情報

論文ID: 2510.14582
タイトル: Local Causal Discovery for Statistically Efficient Causal Inference
著者: Mátyás Schubert (アムステルダム大学)、Tom Claassen (ラドバウド大学ナイメーヘン)、Sara Magliacane (アムステルダム大学)
分類: stat.ML cs.AI cs.LG
発表日: 2025年10月16日 (arXiv プレプリント)
論文リンク: https://arxiv.org/abs/2510.14582v1

要約

因果発見手法は、潜在的な因果グラフが未知の場合でも、目標変数のペアに対する因果効果推定のための有効な調整集合を特定することができます。全体的因果発見手法は因果グラフ全体の学習に焦点を当てており、最適調整集合（最も低い漸近分散を持つ集合）を復元できますが、変数の数が増えるにつれて計算上急速に困難になります。局所因果発見手法は目標変数の局所近傍に焦点を当てることでより拡張可能な代替案を提供しますが、統計的に準最適な調整集合に限定されます。本研究では、著者らは局所最適調整発見（LOAD）を提案しており、これは局所手法の計算効率と全体的手法の統計的最適性を組み合わせた信頼性があり完全な因果発見手法です。

研究背景と動機

問題定義

因果推論において、2つの変数間の因果効果を推定することは中心的なタスクです。潜在的な因果グラフが未知の場合、因果効果推定のための有効な調整集合を特定するために因果発見手法が必要です。既存の手法は根本的なトレードオフに直面しています：

全体的手法のジレンマ: 全体的因果発見手法（PC アルゴリズムなど）は完全な因果グラフを学習し最適調整集合を復元できますが、計算複雑度は変数数に対して指数関数的に増加し、大規模問題では実行不可能です。
局所手法の制限: 局所因果発見手法（MB-by-MB、LDECC など）は計算効率が高いですが、準最適な調整集合のみを復元でき、因果効果推定の漸近分散が高くなります。

研究動機

著者らは既存の局所手法に以下の問題があることを発見しました：

LocalPC アルゴリズムは隣接変数の特定において十分に信頼性がなく、非隣接の配偶者を誤って隣接として特定する可能性があります
LDECC アルゴリズムは不完全であり、特定の状況ではすべての方向付け可能な辺を方向付けることができません
LDP アルゴリズムは特定の識別可能効果がゼロの場合、効果が識別不可能であると誤って報告する可能性があります

したがって、局所手法の計算効率を維持しながら全体的手法の統計的最適性を達成する新しい手法が必要です。

核心的貢献

局所情報に基づいて因果効果の識別可能性を判定する手法の開発: 局所情報のみを使用して因果効果が識別可能かどうかを判定するための必要十分条件を提案しました。
LOAD アルゴリズムの提案: 変数周辺の局所情報のみを使用して最適調整集合を特定できる信頼性があり完全な手法です。
包括的な実験評価: 合成データと実データ上で LOAD を評価し、低計算コストで高品質な調整集合を復元できることを実証しました。
理論的保証: 因果効果の識別可能性判定と最適調整集合の発見における LOAD の信頼性と完全性を証明しました。

手法の詳細

タスク定義

目標変数 X と Y のペアが与えられた場合、目標は以下の通りです：

X と Y 間の因果関係を判定する（明示的祖先、可能的祖先、または確定的非祖先）
因果効果が識別可能かどうかを判定する
識別可能な場合は最適調整集合を見つける；そうでない場合は局所的に有効な親調整集合を返す

LOAD アルゴリズムアーキテクチャ

LOAD アルゴリズムは 5 つの主要なステップに分かれています：

ステップ 1: 目標変数間の因果関係の判定

LocalRelate アルゴリズム（アルゴリズム 1）を使用し、以下の定理により関係を判定します：

明示的祖先関係（定理 4.1）: CPDAG G における任意の 2 つの異なるノード X と Y に対して、X ∈ ExplAn_G(Y) 当且つ当に X ⊥̸⊥ Y | Pa_G(X) ∪ Sib_G(X)
確定的非祖先関係（定理 4.2）: X が Y の確定的非祖先である当且つ当に X ⊥⊥ Y | Pa_G(X)

ステップ 2: 因果効果の識別可能性のテスト

局所情報に基づく適応的テストを提案：

補題 4.3: CPDAG G における X ∈ PossAn_G(Y) に対して、G が (X,Y) に対して調整適応的である当且つ当に：

∀V ∈ Sib_G(X) : V ⊥⊥ Y | Pa_G(V) ∪ {X}

この条件は LocalAmenTest アルゴリズム（アルゴリズム 2）により効率的に検出できます。

ステップ 3-5: 最適調整集合の構築

因果効果が識別可能な場合、LOAD は以下のステップを通じて最適調整集合を構築します：

明示的後代の検出: T のすべての明示的後代を特定する
仲介ノードの特定: T の明示的後代かつ O の明示的祖先であるノードを見つける

最適調整集合の構築:

Oset_G(T,O) = Pa_G(Cn_G(T,O)) \ (Cn_G(T,O) ∪ {T})

技術的革新点

局所適応性テスト: 局所情報のみを使用して適応性をテストするための必要十分条件を初めて提案し、すべての可能な有向パスの確認の必要性を回避しました。
キャッシング機構: 改善された MB-by-MB アルゴリズムは、以前の実行で特定された Markov ブランケットと局所構造を再利用するキャッシュを使用し、計算効率を大幅に向上させます。
理論的完全性: 因果関係、識別可能性、最適調整集合の判定において LOAD が信頼性があり完全であることを証明しました。

実験設定

データセット

合成データ:
- ランダムに生成された Erdős–Rényi グラフを使用
- 変数数: 100-1000
- 期待次数: d=2、最大次数: dmax=10
- サンプル数: nD=10000
実ネットワーク:
- MAGIC-NIAB ネットワーク: 44 ノード、平均次数 3
- ANDES ネットワーク: 223 ノード、平均次数 3.03