グラフとリッチフロー 回歴

zenn.dev

こちらの記事があんまりよくわからなかったので、自習のため、メモ書きを残しておこうと思う。

 

  • ポアンカレ予想
  • 幾何化予想
    • コンパクトな3次元多様体は、幾何構造を持つ8つの部分多様体に分解される。
  • リッチフロー
  • リーマン多様体
    • 微分可能多様体であって計量テンソルを備えた図形
    • 局所的に見た時に、ユークリッド空間となっているのが多様体
    • その局所的なユークリッド空間において、微分が出来る。
    • 微分をするときに、どの方向に微分するか、という偏微分の考えを持ち出すことができる。
    • すると、方向性を加味した概念として、ベクトルが出てくる。
      • これが、接ベクトル。
      • ベクトルであって、微分可能多様体上の点に接しているから。
      • この接ベクトルがなす空間を接ベクトル空間
    • ベクトル同士の内積を取ることで、ベクトル同士の類似度、近さを考えることができる。
    • この際の、内積のために、計量なる、正定値行列を考える。
    • この計量自体も、多様体の点が滑らかに変化したら、変化していく。言い換えると、多様体上の点を入力にして、正定値行列を返すような装置、これを計量テンソルという。
    • まとめ直すと、リーマン多様体は、計量テンソルを備えた、微分可能な、多様体。
  • リッチ曲率
    • 断面曲率
      • 多様体上の平行四辺形を考える。
      • 平坦な場合、同じ長さとなってくれる。
      • しかし、曲がった空間だと、そうは行かない。
      • この時の長さの比較で、断面曲率が登場する。
      • d(x^' , y^' ) = d(x, y)(1 - \frac{\epsilon^2}{2} K(v, w) + O (\epsilon^3 + \epsilon^2 \delta ))
    • 似たような考え方で、ある接ベクトル空間上のとても小さな球を、平行移動させると、球体の点が移動する距離の平均が、中心の移動する距離の補正がかかったものになる。
    • この時の、補正項に含まれるのが、リッチ曲率と呼ばれるもの
    • リッチ曲率は、空間の大きさが方向に応じてどう変化するか、という特徴を教えてくれる。
      • 普通の曲面の曲率、というのは、2階偏微分の行列になっている。あれもどの方向に変化したらどう変わるか、を教えてくれる。
  • リッチフロー
    • \frac{\partial g_{ij}}{\partial t} = - 2 R_{ij}
    • 計量テンソルが、リッチ曲率によって時間発展する。
  • どうしてリッチフローをグラフに持っていくかというと、リッチフローでグラフを変形させていく中で、グラフをコミュニティーごとのパーツに分解していくことを狙っている。
  • そのために、グラフ上にリッチ曲率を定義したい。
  • リッチ曲率は微分幾何学の世界の話。
  • Ollivier Ricci曲率
    • \kappa(x,y) = 1 - \frac{ W_1(m_x, m_y)}{d(x, y)}
    • 2点の確率分布の間の距離と2点の距離の比が、曲率に左右されることを利用して、逆に定義する。
  • 最適輸送理論
    • これについては、以前まとめた記事がある。

       

      medical-science.hatenablog.com

       

    • Wasserstein距離なる、確率分布の間の距離を定義する。
      • 輸送コストを最小にするような運び方（確率分布の遷移）を考えたときの、そのコスト。
    • 適当なエントロピーで正則化すると、Shinkhornアルゴリズムを使える。
  • グラフ上のリッチ曲率
    • グラフに確率を乗せる。
    • グラフの点について、その点にはαの確率、その近傍の点には、 \exp(-d(x, y))に比例する確率を乗せる。
    • 言い換えると、確率分布をそれぞれの点とそれに隣接する点に乗せる。隣接する点には、点同士の距離に依存した指数関数に応じた量を確率として乗せる。
    • 確率分布をそれぞれの点に定義することができるので、それを輸送することを考えると、確率分布のWasserstein距離を計算できる。
      • これはαに依存する関数となる。
    • そして、このWasserstein距離とグラフ上の距離を使えば、グラフの2点間のリッチ曲率に対応する関数を得ることができる。
    • このαを1に極限を飛ばす
  • グラフ上のリッチフロー
    • エッジの重みw_{xy}の時間発展、 \frac{d w_{xy}}{dt = - \kappa_{xy}w_{xy}
    • これを時間発展させて考える。