Graph reconstruction from random-walk co-visitation: Geometric, empirical, and controlled networks

技術要約：ランダムウォークの共訪問に基づくグラフ再構成

問題提起
本論文は、未知のグラフ構造を、その上を拡散するランダムウォークの軌跡から再構成するという逆問題を扱っている。これは、動的なプロセス（例：時系列、拡散プロセス、または拡散トレーサー）は観測可能であるが、基礎となる連結性（「配線」）は観測できないという文脈において発生する。この領域における中心的な課題は、**再構成可能性（reconstructibility）**である。ランダムウォークは、実際に辿ったエッジに関する情報しか伝達できない。サンプリングされた軌跡によって訪問されなかったエッジは、どのような推定器を用いても、そのサンプルからは根本的に回収不可能である。第二の課題は、**識別可能性（identifiability）**である。観測量は、ノードレベルの要約（次数列など）が同一であるグラフ同士を区別できるだけの、十分なペアごとの構造情報を保持していなければならない。

手法
著者らは、ノードレベルの統計量へと構造情報が崩壊することを避けるため、**ペアワイズな観測量（pairwise observable）とペアワイズなモデル（pairwise model）**を利用した再構成パイプラインを提案している。

1. 観測量（共訪問行列）： 行和を取る前に、特定の遷移 $i \to j$ を保持するように、順序付けられたペア $(i, j)$ を記録する共訪問行列 $C$ を用いる。これは、周辺的な滞在確率（これらは定常次数分布へと収束し、ペアごとの情報を失ってしまう）を用いるのではなく、特定の遷移を保持する手法である。
2. モデル（ペアワイズ・エッジ重み基底）： モデルは、すべての候補ペアに対してペアワイズな対数重み $\beta_{ij}$ を持つと仮定する。遷移行列 $P$ は、重み行列 $S(\beta)$ から行正規化を経て導出される。このアプローチは、各潜在的なエッジに固有のパラメータを割り当てることで、加法的なノードポテンシャルモデルでは捉えられないクラスター構造を捉えることを可能にする。
3. フィッター（フレーム・バランスド・レーベンバーグ・マルカート法）： パラメータ $\beta$ は、観測された共訪問行列に対して**フレーム・バランスド・レーベンバーグ・マルカート（fbLM）**スキームを用いて適合される。
   • グループ・ウェイト： 残差は頂点ごとにグループ化される。重みは、特定の頂点が適合を支配しないように、直交フレーム（スティフェル多様体）上で最適化される。この「フレーム・バランシング」は、重みが高次数のノードに集中することを防ぎ、ユニークな情報を持つ頂点が適切な重みを受け取るようにする。
   • ゲージ固定（Gauge Fixing）： 共訪問は、すべての対数重みのグローバルなシフト（$\beta \to \beta + c\mathbf{1}$）に対して不変である。本手法は、各提案ステップの後にパラメータをセンタリングすることで、このゲージを明示的に固定する。
   • 不確実性の伝播： コ分散行列はフィッシャー情報量から導出され、数値的不安定性を避けるためにゲージ方向が明示的に射影除去される。
4. リードアウト（自己校正型結合）： 最終的なエッジ集合は、自己校正型の結合指標 $\rho_{ij} = W_{ij}/\sqrt{s_i s_j}$ によって決定される（ここで $W$ は適合された重み、$s_i$ は頂点の強さである）。$\rho_{ij}$ がその2つのエンドポイントの平均結合を超えた場合にエッジが存在すると判定される。この閾値は相対的かつデータ駆動型であり、絶対的なカットオフやグラフ密度に関する事前知識を必要としない。

データセットおよび実験設定
パイプラインは、5つの異なるテストベッドでテストされている：

• 経験的（Empirical）： サイズが変化する（$N=20, 100, 240$）メール通信サブグラフ（email-Eu-core）。
• 幾何学的（Astrophysical）： COSMOSスカイカタログから派生したデローネ三角形分割およびボロノイテセレーション（フルスケールで再構成、$N=119$ および $N=223$）。
• 制御下（Controlled）： サニティチェックとして使用される、2つの12頂点グラフ（一方は一巡グラフ、もう一方は木構造）。

実験は以下の2つのレジーム下で行われる：

1. 有限歩長レジーム（Finite-Walk Regime）： 長さ $T$ のサンプリングされた軌跡からの再構成。
2. 乗法的ノイズ・レジーム（Multiplicative-Noise Regime）： 解析的な共訪問行列にガウスノイズを加えたものからの再構成。これにより、推定器の耐性とサンプリングによる被覆の違いを分離する。

主要な結果

• 高忠実度再構成： パイプラインは、すべてのテストベッドにおいて高い再構成品質を実現している。フルスケールの幾何学的グラフにおいて、デローネ構造とボロノイ構造をそれぞれマシューズ相関係数（MCC）0.988および0.977で復元した。経験的なメールグラフ（$N=240$）では、MCC 0.967を達成した。
• ベースラインとの比較： fbLMパイプラインは、グラフィカル・ラッソ（graphical-lasso）のベースラインを大幅に上回る。フルスケールのデローネグラフにおいて、ベースラインのMCCは0.540であったのに対し、fbLMは0.988であった。
• 被覆の限界： 有限歩長レジームにおいて、制限要因は推定アルゴリズムではなく、**グラフの被覆（walk coverage）**である。分析によれば、偽陰性はほぼすべて、ランダムウォークが一度も通過しなかったエッジに起因している。ウォークがグラフをカバーしている場合、推定器は極めて高い忠実度でエッジを復元する。
• ノイズ耐性： 全ペアが候補となる乗法的ノイズ・レジームにおいて、本手法は低ノイズレベルでグラフを正確に復元する。40%のノイズが存在する場合でも、本手法はエッジの完璧なランキング（AUC = 1.000）を維持しており、性能低下は強いエッジがリードアウトの閾値を下回った時にのみ発生し、偽陽性によるものではない。
• 不確実性の定量化： 手法はフィッシャー情報量から導出されるエッジごとの不確実性推定値を提供する。これらの不確実性は相当なもの（中央値の相対不確実性 $\sim$30–45%）であるが、境界部や被覆の低いエッジに正しく局在化されており、内部のエッジは厳密に制約されている。

意義および主張
本論文は、グラフのサイズ、密度、または正解の隣接行列に関する事前知識なしに動作する、堅牢なグラフ再構成推定器を確立したと主張している。その主な貢献は、幾何学的および経験的ネットワークにおいて、再構成可能性は推定器ではなく、グラフのサンプリングによって決定されることを示した点にある。

著者らは以下の点を強調している：

1. 再構成可能性はサンプリングの問題である： ウォークがエッジを訪問しない限り、いかなる推定器もそれを復元することはできない。提案手法は、軌跡から利用可能なすべての情報を抽出する。
2. ペアワイズな観測量が不可欠である： 次数列が同一であるグラフを区別するためには、周辺統計量ではなく共訪問を用いる必要がある。
3. 自己校正： リードアウト機構は外部のチューニングや絶対的な閾値を必要とせず、未知のグラフへの適用が可能である。
4. 天体物理学への適用可能性： 本手法は、実際の天体データ（COSMOSカタログ）から派生した幾何学的グラフに対して成功裏に適用されており、グラフ自体が定義済みのモデリングの選択肢ではなく、推論の対象となる枠組みを確立している。

結論として、推定器は非常に効果的であるが、有限歩長シナリオにおける実用的な再構成の限界は、ネットワークの被覆（trajectory's coverage）によって決定されるものであり、この要因は適合手順とは独立して定量化および最適化が可能であるとしている。