技術的サマリー：サイクルを含む線形非ガウス因果モデルの粗粒度化

問題定義

観測データからの因果発見は、歴史的に有向非巡回グラフ（DAG）に焦点を当ててきた。しかし、遺伝子調節ネットワークや動的システムなど、多くの科学システムは本質的にフィードバックループ（有向サイクル）を含んでいる。サイクルを含む因果モデルを学習するための既存の手法は存在するが、それらはしばしば重大な制限に直面する：

1. 識別性の曖昧さ： 線形非ガウス（LiNG）設定において、サイクルを含む構造因果モデル（SCM）は、分布等価クラスまでしか識別できない。このクラスのメンバーは、有向サイクルの反転によって互いに異なり、強い仮定（例えば、安定性または非重複サイクル）なしには、観測データのみから正確なマイクロレベルのグラフ構造を識別できない。
2. 計算複雑性： GroupLiNGAM アルゴリズムなどの因果構造の要約を学習する既存のアプローチは、変数の数に対して指数関数的な時間複雑性に悩まされることが多い。
3. 適用性： 多くの高次元のサイクルモデルは、非巡回性を仮定しているため、標準的な因果抽象化フレームワークから除外されている。

本論文は、非重複サイクルや安定性といった制限的な仮定を必要とせず、識別可能かつ計算的に扱いやすい低次元表現へと高次元のサイクル因果構造を要約するという課題に取り組む。

手法

著者らは、変数をクラスターにグループ化して商グラフを形成する「因果的粗粒度化（causal coarsening）」のフレームワークを、サイクルを含む有向グラフに拡張する。

1. 理論的枠組み：SCC フロア

核心的な理論的洞察は、サイクルを含むグラフの任意の有効な DAG 粗粒度化は、その「強連結成分（SCC）」を尊重しなければならないという点にある。

• 命題 1： 同一の SCC 内のノードは、任意の DAG 粗粒度化において同じクラスターにグループ化されなければならない。それらが分割された場合、商グラフは必然的にサイクルを含み、DAG の要件に違反することになる。
• 構造的フロア： 変数を SCC に分割することは、粗粒度化格子における「構造的フロア」を形成する。これは、有効な DAG 粗粒度化の中で最も細かなものである。得られる商グラフは、元のグラフの縮約（condensation）（$G_{sc}$）であり、定義により DAG である。

2. ICA による識別性

本論文は、線形非ガウス（LiNG）サイクル SCM の性質を利用する：

• モデル： $X = BX + \varepsilon$。ここで、$\varepsilon$ は互いに独立した非ガウス成分を持つ。
• 観測的等価性： [19] に従い、混合行列 $A = (I-B)^{-1}$ は、行の置換とスケーリングまで独立成分分析（ICA）によって復元可能である。異なる置換は、サイクルの反転によって異なる分布等価クラスのメンバーをもたらす。
• 定理 1（縮約の識別性）： 著者らは、マイクロレベルのグラフ $G$ が等価クラスまでしか識別できない一方で、縮約 $G_{sc}$ はこのクラスのすべてのメンバーにおいて不変であることを証明する。
  • 理由付け： サイクルの反転は厳密に SCC 内で発生し、SCC 分割自体を変更しない。さらに、異なる SCC 間のエッジ（クラスター間エッジ）は有向サイクル上に存在し得ない。したがって、サイクルの反転はこれらのエッジを追加、削除、または再方向付けすることはできない。その結果、クラスターレベルの DAG は観測データのみから完全に識別可能である。

3. アルゴリズム：縮約の復元

提案された手順（アルゴリズム 1）は、多項式時間で縮約を復元する：

1. 推定： 観測データに FastICA を適用し、デミキシング行列 $\hat{W}$ を推定する。
2. 置換： 対角成分が非ゼロとなるような、単一の許容行置換 $P$（例えば、ハンガリー法による）を選択する。
3. 候補構築： 候補隣接行列 $\hat{B} = I - \text{diag}(P\hat{W})^{-1}P\hat{W}$ を計算する。
4. 閾値処理： $\hat{B}$ に閾値 $\tau$ を適用して、サポート（エッジ）を決定する。
5. SCC 抽出： $\hat{B}$ のサポートに対して Tarjan アルゴリズムを適用し、SCC を特定する。
6. 縮約構築： ノードが SCC であり、対応するクラスター間に $\hat{B}$ において何らかのエッジが存在する場合にエッジが存在する商グラフを形成する。

計算量： このアルゴリズムは、最悪の場合 $O(k \cdot n \cdot d^2 + d^3)$ の時間で実行される。ここで、$n$ はサンプル数、$d$ は変数、$k$ は ICA の反復回数である。これは、すべての等価クラスメンバーを列挙する $O(d!)$ の複雑性を回避する。

主要な結果

本論文は、合成データにおける理論的保証と実証的検証を提供する：

• 理論的保証：

  • 識別性： 縮約 $G_{sc}$ は、安定性の仮定や非重複サイクルの制約を呼び出すことなく、観測データから識別可能である。
  • サンプル複雑性： 本論文は、確率 $1-\delta$ で真の縮約を復元するために必要なサンプルサイズが $n = \Theta(d / (\beta_{min}^2 \sqrt{\delta}))$ であることを示す境界を導出した。ここで、$\beta_{min}$ は最小の非ゼロエッジ重みである。
  • 失敗モード： 著者らは閾値処理の 2 つの失敗モードを特徴づける：(a) 失われたエッジによる真の SCC の分割（精緻化）、および (b) 偽のエッジによる異なる SCC の合併（粗粒度化）。

• 実証的パフォーマンス：

  • 一貫性： 合成 LiNG サイクル SCM（$d=10$）における実験は、システムが安定 ($\rho(B) < 1$) な領域か不安定 ($\rho(B) > 1$) な領域かにかかわらず、サンプル数が増加するにつれて、復元された SCC 分割の調整ランダム指数（ARI）とクラスター-DAG の F1 スコアが 1 に収束することを示した。
  • スケーラビリティ： 最先端の非重複サイクルベースライン [9] と比較して、提案手法は著しく優れたスケーラビリティを示す。ベースラインの適合時間は指数関数的に増加し、$d \ge 50$ で性能が頭打ちになるのに対し、提案手法は $d=100$ でも高い精度を維持し、適合時間は 10 秒未満である。
  • ロバスト性： 変数レベルの構造が識別不可能な場合（例えば、「最初の安定」フィルタが真の $B$ を復元できない不安定領域）でも、本手法はクラスターレベルの構造を正常に復元する。

意義と主張

本論文は、サイクル因果モデルと因果抽象化の間のギャップを埋めると主張する：

1. 曖昧性の解決： サイクルを含む LiNG モデルの分布等価クラスに対する自然な代表を提供する。正確なマイクログラフは曖昧であるが、縮約は変数のクラスター間の因果フローを捉える、一意かつ識別可能な対象である。
2. 下流の因果推論の可能化： 観測データから $G_{sc}$ を同定することにより、本論文はC-DAG（クラスター DAG）同定定理（[2] から）を適用するための必要な前提条件を提供する。これにより、研究者は、以前は非巡回システムに限定されていたか、介入データが必要だったタスクを、サイクルシステムにおいてクラスターレベルで因果効果の同定を行うことが可能になる。
3. 計算効率性： このアプローチは、因果要約を学習するための指数時間手法に対する多項式時間の代替案を提供し、高次元の問題への適用を可能にする。
4. 緩和された仮定： 非重複サイクルや特定のノイズの歪みを必要とする先行研究とは異なり、このアプローチは一般的な非ガウス性と標準的な ICA のみに基づいており、重複するサイクルに適用可能である。

著者らは、本手法が潜在的な交絡因子を含まないことを仮定していること（または過剰完全 ICA 拡張を必要とする）、および異なる SCC を結合する回転的曖昧さを避けるために、高々 1 つのノイズ成分のみがガウス分布である必要があるという制限を指摘している。彼らは、この研究を、複雑でサイクルを含むシステムにおける実用的な因果発見に向けた基礎的なステップとして位置づけている。