A Fast Algorithm for the Finite Expression Method in Learning Dynamics on Complex Networks

技術要約：複雑ネットワーク上の学習における有限式法の高速アルゴリズム

問題提起
本論文は、時系列データから複雑ネットワークシステムにおける支配的な物理法則や動的相互作用を発見するという課題に取り組んでいる。データ駆動型の手法は連続系（例：偏微分方程式）の式解明において進歩を遂げてきたが、ネットワークデータからダイナミクスを抽出することは、主に以下の3つの要因により困難である。

1. 計算量： $N$ 個のノードを持つネットワークにおいて、完全なペアワイズ相互作用をモデル化すると通常 $O(N^2)$ の計算量が発生し、大規模な実世界のネットワークに対しては極めて高コストとなる。
2. データの質： 実世界のネットワークデータはノイズが多く、疎であり、トポロジー上の不正確さ（欠落したリンクや偽のリンク）を含むことが多い。
3. 解釈可能性と事前知識： SINDy（非線形ダイナミクスの疎な識別）のような既存手法は、膨大な候補関数のライブラリと、直接的な時間微分のアクセスを必要とすることが多いが、これらは頻繁に利用不可能である。また、グラフニューラルネットワーク（GNN）などのディープラーニング手法は、「ブラックボックス」として機能するため、解釈性に欠ける。

手法：有限式法 (Finite Expression Method: FEX)
著者らは、有限の数学演算子で構成される二分木を用いてネットワークのダイナミクスを表現する新しい手法、FEXを提案している。システムのダイナミクスは次のようにモデル化される：
$$\frac{dx_i(t)}{dt} = F(x_i(t)) + \sum_{j=1}^N A_{ij}G(x_i(t), x_j(t))$$
ここで、$F$ は自己ダイナミクスを表し、$G$ は相互作用ダイナミクスを表す。

FEXの主要構成要素：

• 二分木表現： ダイナミクスは、数学演算子（単項演算子：$\sin, \cos, \exp$；二項演算子：$+, -, \times$）をノードとする二分木としてエンコードされる。リーフノード（葉ノード）は、学習可能な重みとバイアスを持つ入力変数として機能する。この構造により、小さな辞書から複雑な関数組成を生成することが可能となり、大規模な事前定義ライブラリの必要性を軽減できる。
• 強化学習による組合せ最適化： 最適な木の構造を特定することを、組合せ最適化問題としてフレームワーク化する。コントローラネットワーク（全結合ニューラルネットワーク）は、方策勾ラジエント法を用いて訓練され、各ツリーノードにおける演算子選択の確率質量関数を出力する。目標は、報酬スコアを最大化する演算子シーケンスをサンプリングすることである。
• スケーラビリティのための確率的アルゴリズム： ペアワイズ相互作用の計算に伴う $O(N^2)$ のボトルネックを克服するため、FEXはランダムバッチ法に着想を得た確率的アルゴリズムを統合している。損失関数の最適化中、ノードはランダムなバッチにグループ化され、相互作用はこれらのバッチ内でのみ計算される。これにより、構造発見フェーズの計算複雑性を $O(N^2)$ から $O(N)$ に削減する。
• 二段階最適化：
  1. 粗いチューニング (Coarse-tuning)： コントローラは、連続パラメータに対して一次最適化（例：Adam）と二次最適化（例：BFGS）を組み合わせ、かつ高速化のために確率的バッチ手法を利用して、高スコアの演算子シーケンスを見つけるように訓練される。
  2. 微調整 (Fine-tuning)： 最も優れた候補構造が特定された後、高い精度を確保するために、係数は完全な相互作用モデルを用いて精緻化される。

主な貢献

1. 新しい表現形式： FEXは、ダイナミクスを表現するために二分木構造を利用しており、SINDyが広範な候補ライブラリに依存するのに対し、最小限の演算子辞書から複雑な方程式の発見を可能にする。
2. 微分フリーの推定： 本手法は、数値微分を用いてノイズを含む時系列データから直接時間微分を推定するため、多くの既存手法が直面している直接的な微分へのアクセスの必要性を排除している。
3. スケーラビリティ： 組合せ最適化フェーズにおいて粒子の確率的選択を採用することで、FEXは計算コストにおいて線形スケーリング（$O(N)$）を達成し、大規模ネットワークへの適用を可能にしている。
4. 堅牢性： 本手法は、低解像度のデータ、観測ノイズ、およびトポロジーの不正確さ（欠落または偽のリンク）に対処できるように設計されている。

実験結果
著者らは、Erdős-Rényiネットワークやスケールフリーネットワークを含む様々なネットワークトポロジーにおいて、3つの古典的な力学系（Hindmarsh-Rose、FitzHugh-Nagumo、および結合Rössler振動子）を用いてFEXを評価した。

• 精度： FEXは、テストされたすべてのダイナミクスに対して、正しい関数形式と係数（相対誤差はしばしば1%未満）を特定することに成功した。
• ノイズに対する堅牢性： SNR（信号対雑音比）が40および45の実験において、FEXはベースライン手法（Two-Phase SINDyおよびARNI）を上回った。これらの手法は、ノイズ条件下では正しい項を特定できなかったり、冗長な項を生成したりした。
• トポロジーに対する堅牢性： FEXは、ネットワークのリンクの15%がランダムに追加または削除された場合でも、高い精度を維持した。
• データの希薄性： 本手法は、元の時系列データの5%から10%のみが利用可能な状態でも効果的に機能した。
• 効率性： 計算時間とネットワークサイズの対数-対数プロットにより、確率的FEXアルゴリズムが線形スケーリング（$O(N)$）を実現する一方で、完全な相互作用モデルは二次スケーリング（$O(N^2)$）になることが示された。

意義と主張
本論文は、FEXが複雑ネットワーク上のダイナミクスを学習するための、堅牢で解釈可能、かつ計算効率の高いフレームワークを提供すると主張している。強化学習による構造探索と、スケーラビリティのための確率的最適化を組み合わせることで、FEXは計算コスト、データの質、および広範な事前知識の必要性に関する現在の手法の限界に対処している。著者らは、このアプローチが、支配方程式が未知または未探索である実世界の複雑なシステムにおける物理法則の発見を可能にし、生物学から疫学に至るまでの領域の解析への道を開くと断言している。本研究は、現在の焦点がペアワイズ相互作用と決定論的ダイナミクスにあることを認め、高次の結合や確率微分方程式への拡張が将来の方向性であることを述べている。