グラフとリッチフロー回歴 - 物理医学数学の日記

zenn.dev

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

ポアンカレ予想
- コンパクトで単連結な3次元多様体は3次元球面に同相
  - 多様体
    - 局所的にはユークリッド空間な図形
幾何化予想
- コンパクトな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}$
- これを時間発展させて考える。