An Empirical Spectral-Domination Relationship Discovered Through Symbolic Regression

技術要約：記号回帰を通じて発見された経験的なスペクトル支配関係

問題提起
本論文は、グラフ不変量、特に支配数 $\gamma(G)$（最小支配集合のサイズ）とスペクトル半径 $\lambda_1(G)$（隣接行列の最大固有値）の間の数学的関係を発見するという課題に取り組んでいる。次数構造に基づく $\gamma(G)$ の境界（例：$\gamma(G) \ge n/(\Delta(G)+1)$）や、ラプラシアン・スペクトルを含むスペクトル境界に関する研究は広範に存在するが、$\gamma(G)$ を隣接スペクトル半径 $\lambda_1(G)$ に直接関連付ける境界は比較的少ない。著者らは、理論的な調査の出発点となり得る潜在的な経験式を特定するために、機械学習を活用することを目指している。

手法
本研究は、グラフ生成、不変量計算、および記号回帰を組み合わせたデータ駆動型のパイプラインを採用している：

1. データセット生成: 拡張されたパラメータ範囲を持つ4つの異なるグラフ族から、3,429個の連結グラフからなるデータセットを生成した：

   • エルデシュ・レーニ（Erdős–Rényi, $G(n,p)$）
   • バラバシ・アルバート（Barabási–Albert, $BA(n,m)$）
   • ワッツ・ストロガッツ（Watts–Strogatz, $WS(n,k,p)$）
   • ランダム正則グラフ（Random Regular, $RR(n,d)$）
     パラメータは $n \in [10, 60]$ の範囲に制約され、再現性のために固定された乱数シードを使用した。

2. 不変量計算: 各グラフについて、基本不変量（$n, m, \Delta, \delta$）、構造的不変量（彩色数 $\chi$、クリーク数 $\omega$、独立数 $\alpha$、マッチング数 $\nu$）、およびスペクトル不変量（$\lambda_1$）を算出した。計算可能な場合は正確なアルゴリズムを用い（$n \le 30$ または $n \le 40$）、より大きなインスタンスについては貪欲近似を用いた。

3. 記号回帰: 遺伝的プログラミングに基づく PySR ライブラリを使用して、データを適合する数学的表現を探索した。探索空間には、バイナリ演算子（$+$, $-$, $\times$, $\div$）および単項演算子（$\sqrt{}$, $\exp$, $\log$）が含まれ、最大複雑度は10とした。回帰は様々な不変量を予測するために実行されたが、特に $n, m, \Delta, \lambda_1, \omega, \alpha, \nu$ の関数としての $\gamma$ に焦点を当てた。

4. フィルタリングと検証: 候補となる数式は、既知の文献による境界と比較してスクリーニングされ、標準的なグラフ（例：$K_n, C_n, S_n$）に対してテストされた。生き残った候補は、以下のプロセスを含む厳格な「反例探索」にかけられた：

   • 新しいグラフ生成（異なるシード）によるテスト。
   • 極端なグラフ族（完全グラフ、二部グラフ、サイクル、パス、スター、ハイパーキューブ、ホイール）によるテスト。
   • 敵対的探索（違反を最大化するためのヒルクライミング）。

5. モデルの再適合: 記号回帰によって特定された最も有望な候補は、係数を最適化するために scipy.optimize.curve_fit を用いて再適合された。

主な結果
記号回帰プロセスにより、特定の経験的な関係が特定された：
$$\gamma(G) \approx \frac{1.53n}{\lambda_1(G) + 1.55}$$

• 全体的な性能: 3,429個のグラフからなるフルデータセットにおいて、モデルは $R^2$ = 0.9609、平均絶対誤差（MAE）0.6633、平方根平均二乗誤差（RMSE）0.9186を達成した。
• 族ごとの性能: この関係は、4つの訓練家族間で良好に一般化されており、$R^2$ 値は 0.89（バラバシ・アルバート）から 0.96（ランダム正則グラフ）の範囲であった。
• 失敗分析: モデルの妥当な領域を特徴付けるため、極端なグラフ家族に対して明示的なテストを行った：
  • 完全グラフ ($K_n$): 数式は $\gamma$ を系統的に約 40–50% 過大評価する（$\gamma=1$ に対して約1.5と予測）。
  • スターグラフ ($S_n$): モデルは壊滅的に失敗し、$n=20$ の場合、相対誤差は 400% を超える。ハブ構造により、中程度のスペクトル半径にもかかわらず自明な支配（$\gamma=1$）が生じるため、深刻な過大評価を引き起こす。
  • パスグラフおよびサイクルグラフ: パフォーマンスは中程度であり、誤差は10%から30%の範囲で、概ね $\gamma$ を過大評価する。
• 生存: 生成されたいくつかの候補（$\omega, \alpha, \chi$ に関する関係を含む）の中で、スペクトル・ドミネーション関係は、非極端なグラフにおいて合理的な誤差範囲内で反例探索を生き残った唯一のものであった。

意義と主張
本論文は、本研究を決定的な理論的証明ではなく、「データ駆動型数学」および「科学的機械学習」のケーススタディとして位置づけている。

• 方法論的貢献: 著者らは、機械学習を用いた記号回帰が、人間の研究者にとって非自明な可能性がある複雑なグラフ不変量間の有望な経験的関係を、いかに成功的に特定できるかを示した。
• 経験的貢献: 本論文は、具体的な特性化された数式 $\gamma(G) \approx 1.53n/(\lambda_1(G) + 1.55)$ を提供している。
• 控えめな主張: 著者らは、これが経験的モデルであり、定理ではないことを明示している。普遍的な妥当性、理論的証明、または正確な特性化を主張しているわけではない。
  • 定数（1.53 および 1.55）は現在、理論的な裏付けを欠いている。古典的な境界（例：$\gamma \ge n/(\Delta+1)$ と $\lambda_1 \le \Delta$ の結合）から特定の値を再現しようとする試みは失敗した。
  • この関係は、主に中程度の密度を持ち、巨大なハブを持たないグラフに対して有効である。
• 今後の方向性: 本論文は、特定された関係が理論的調査の出発点となることを示唆しており、具体的には、これらの定数が構造的な解釈を持つかどうか、また制限されたグラフクラスに対してよりタイトな境界を導出できるかどうかを問いかけている。

要約すると、本論文は、機械学習を用いて、スペクトル半径と支配数の間の逆関係に関する高精度な経験的推測を生成することに成功し、同時にその推測が失敗する境界を厳密に定義することに成功している。