Graphon空間はコンパクト(オールスター感)
はじめに
こんにちは。りゅうふじわら(@ryunryunryun_)です。よろしくおねがいします。
この記事は鯵坂もっちょさん(@motcho_tw)主催の好きな証明 Advent Calendar 2018の15日目の記事です。
本記事は以前、僕の属する明治大学 総合数理学部 現象数理学科にて主催した「NCLT2018 AUTUMN SPECIAL -推しLT-」での僕の発表「対角線を追いかけて」で紹介しきれなかった「推し数学の証明」を語る記事になっています。
好きな証明Advent Calendarの存在を知ったとき、こんなうってつけの場があるのか!とビビビっときました。
目標
以下の定理を証明します。
用語は追って説明しますが、その証明が対角線論法*1を使っててめっちゃかっこいいんです。推せます。
(注意) この記事は上のメインの定理に行き着くまで割とスキップしながら歩みを進めます。細かな補題の証明などは僕が作成したpdfに書いてあるので、ギャップがあるような場合はその都度明記するので、気になる方は適宜そちらを参照してください。
Graphonってなに?
Graphonとはグラフの可測関数による表現
Graphonとは"graph function"の略で、(ネットワークの意味での)グラフの隣接行列を可測関数により表現したものです。定義としてはこんな感じ。
つまりは、Graphonとは正方形上の本質的に有界で、に関して対称な可測関数のことを言います。百聞は一見にしかず、例えば下図の左側の無向グラフはその隣接行列(繋がってれば1、繋がってなければ0とする行列)を、ドット絵のようにを分割したグリッドを1なら黒、0なら白と塗りつぶした絵へと変換すれば、グラフをgraphonへと翻訳することができます。
ここで、Graphonに対して本質的に有界という条件を課したことはかなり重要で、ゴールである「コンパクト性」を示すのにクリティカルに効いてきます。もちろん、非有界なものも考えることは可能です。その場合は graphonという枠組みがあって、次数が非有界であったり、ノードに対して十分にエッジがないような疎なグラフなどにも対応できるような代物があるのですが、ここではそういうものがある、とだけに留めておきます。
Graphon全体に距離を入れる
Graphon全体を少しいじって距離を入れていきます。まずはにcut-normという、ちょっと特殊なノルムを入れてみます。
グラフ理論において、"cut"(リンクはWikipedia)という概念があって、この概念のGraphon版だと思ってもらえればよいです。
このcut-normを元にして、cut-distanceという擬距離が導くが、その前に保測変換という概念を導入しましょう。はLebesgue測度です。
すなわち、保測変換とは逆像に関して測度が保たれるようなマップです。これを使って、cut-distanceをcut-normを使って定義していきます。
cut-distanceと言いながらも擬距離であることは置いておいて、擬距離の理由は以下の図を見てもらえれば一目瞭然です。この図は距離の公理の1つでもあるが成り立たない例となっています。Graphonはグラフの隣接行列の可測関数による表現となっていますが、この表現はグラフの「形」は同じでもノードの番号の付け方に依存します。カット擬距離の定義を見ると保測変換によりノード番号の付け替えを行ってから、cut-normによって比べようと言っているのです。
ですが、一般にこういった擬距離空間を距離空間に変換する方法があります。それはに擬距離が0となるものを同じと見なすような同値関係を入れて商空間を考えればよいのです。つまりは次のようなことをしようということです。
Graphon空間の要素のイメージとしては、ノード番号を無視したgraphonです。上図の形が同じなグラフはノード番号に関わらず同一視してしまおう!の精神を体現したものとなっているわけです。
収束Graphon列の例(ちょっと寄り道)
この節は寄り道なので、読み飛ばしてもらっても構いません。Graphon空間を考えると、何が嬉しいのでしょうか。その最たる例として、ノード数が増えていくようなランダムグラフ列に関して適切な極限を考えられてしまうのです。
例えば、古典的なランダムグラフを考えます。すなわち個のノードに対してノードの各ペア間に確率でエッジを結ぶようなグラフです。 この規則の元、ノードの数に関して極限を考えると、下図のようにGraphon空間の元でという極限が得られます。直感的には無限個ノードがある確率の元で生成されるランダムグラフの期待値を取っているような感覚です。
ここで思い出してほしいのですが、少し上の方でGraphonの定義の仕方は本質的に有界であることがクリティカルに効いていると述べました。この事実はgraphon列の収束でもかなり効いてきて、疎なグラフに対応するgraphonの極限はなんとになってしまうという欠点があるのです。再度の宣伝になりますが、 graphonはこれを解決できる代物となっています。(紹介はいつかまた)
下準備
さて、Graphon空間を定義できたので、メインテーマであるコンパクト性に移っていきましょう。ですが、そのために必要ないくつかの補題を証明無しで述べていきます。証明は僕が作成したpdfに書いてあるので、気になったらそちらを参照してください。
Kernel版のweak regularity lemma
まず、以下の話ですが、Graphonの値域をからに広げたものを考えます。こうして拡張したものをkernelと呼ぶことにします。Graphon空間の構成方法と同様にkernel全体に対してcut-distanceから誘導される商空間をとして便宜上Kernel空間と呼ぶことにしましょう。*2
Kernelに対して次のようなweak regularity lemmaという命題が成り立ちます。*3なお、補題中で出てくるはノルムです。
Lebesgue積分論では可測関数が階段関数で任意精度で近似できることは当たり前だが、この補題ではcut-distanceの元でも階段関数によって任意精度での近似ができることを述べているのです。
Weak regularity lemmaを使える形に
このweak regularity lemmaを、メイン定理を示すのに使える形にちょちょいと変形します。そのために、kernelの階段化を定義します。
イメージとしては分割に対して、各区域に対してを均している感じです。階段化された後の関数はたかだか階の階段関数になります。
この階段化を使ったweak regularity lemmaのcorollaryが次の評価となります。
このcorollaryにより、勝手に取った自然数よりも小さい階数の分割による階段化がcut-normの元でに近くすることができることが言えました。この勝手に取れる、というのがかなり重要です。
もう一個、corollaryを挙げておきます。これはCorollary 1から自明に従うことですが、後々のために述べておきます。なお、分割の細分とは、分割をより切り刻んだ分割のことを言います。
Graphon空間はコンパクト
ようやく、僕の推し証明方法を紹介できる準備が整いました。もう一度、その定理を述べておきます。
きれいな定理です。さあ、証明していきましょう。
以下から証明です。対角線論法を使います。愛おしいですね。
Graphon空間は距離空間なので、コンパクト性と点列コンパクト性は同値であるから、点列コンパクト性を示すことにしましょう。証明は3ステップに分けます。
- Graphonの列と各に対する適当な分割の列を元に、が各について階段関数に収束するようにの部分列を取り出します。
- がほとんど至るところであるgraphon に収束することを示します。
- 実は1.にて取り出した部分列がcut distanceの元でに収束することを示します。
Step 1
(Step 1の概要): Graphonの列と各に対する適当な分割の列を元に、が各について階段関数に収束するようにの部分列を取り出します。
Graphonの列をとしましょう。この列がcut-distanceの元で収束部分列を持つことを示すことがゴールです。では、分割を次の3条件を満たすように構成しましょう。簡単のため、と書くことにします。
- はの細分
- はにのみ依存する。すなわち、を固定すれば分割の大きさは一定
これら3条件を満たすようなの存在は前節で紹介したCorollary 1とCorollary 2にて保証されています。こうして構成した分割の各要素は不連結となっている可能性があるため、後々の都合上、すべてのを適当な全単射な保測変換によって区間へと変形しておく。
ここで次のclaimを示します。
対角線論法を使いますが、ちょっと複雑なので、下図を参照しながら読んでください。
まず、 (図では1列目)に関して、の全ての区間の長さが収束し、各区画上での値が収束するようにから部分列を取り出します。実際、実数の収束の話なので、Bolzano-Weirstrassの定理*4を有限回(区間の長さに関する回と各区画の上での値に関して高々回)繰り返し使えば得られます。この部分列はとある階の階段関数にほとんど至るところに収束します。
こうして得たに関して、の部分列から、さらに同様に (図では2列目)に対して、の部分列として、階のある階段関数にほとんど至るところで収束するようなを取り出します。
この操作を帰納的に繰り返していくことで、全てのに関してが、階の階段関数に収束するようにするようにできます。
最後に各列から、それぞれ対角線である番目に対応するの部分列を取り出せば、claimの通りの部分列を構成できます。この部分列を改めてとしてしまいます。
これで、step 1が完了しました。
Step 2
がほとんど至るところであるgraphon に収束することを示します。
このstepでは確率過程論の一部であるマルチンゲール理論を使います。かなりの飛び道具ですが、本証明に必要な分の紹介は僕のpdfなどに載っています。
の構成方法からに関して
が成り立ちます。これより、上のランダムな点に対してはマルチンゲールであることがわかります。ここで、は有界なので、マルチンゲールの収束定理よりは概収束します。すなわち、ほとんどいたる所では収束するので、その収束先をとしましょう。
Step 2だけふわふわしている感は否めませんが、先に進みましょう。
Step 3
実は1.にて取り出した部分列がcut distanceの元でに収束することを示します。
まずは、step 2からはへ収束しますので、任意の正数と十分大きなに対して
が成り立ちます。Step 1から、同じとと十分大きなに対して
が成り立ちます。したがって、であることとstep 1にて置いた仮定aに注意すれば、
となるので、はにcut-distanceの元で収束することが示された。
よって、Graphon空間は点列コンパクトであり、すなわちコンパクトである。
いぇーい!
推しポイント
この証明の推しポイントはなんてったって対角線論法です。見ました?各列からぐわっとよりすぐりの精鋭達を選んできたかと思いきや、その中から更に更に対角線としてエリート階段関数達を厳選しているんですよ!しかもこのエリート達がとかいう王様に収束するとかいうからもう、、、オールスター感すごくないですか!!!
この対角線論法とかいう論法ってかなり面白くて、選りすぐって更に選りすぐった猛者たちを集めてくるわけですから、条件の絞り込みができるんですよね。今回のGraphon空間はコンパクトの証明で言えば、一発目の選抜として各列の部分列を取ることで区画の幅と区画上の値を収束させて、二発目の選抜で対角線を選ぶことで一つ階段関数の幅を小さくしていくって感じです。
こうした論法を使った別の定理にAscoli-Arzelàの定理というのがあって、定理の内容としては
というものですが、これも0次選抜でのコンパクト性から可算個の点を選んで、1次選抜でさっき選ばれた点上でのから収束部分列を選び、最終選抜にて対角線を取ってきて一様収束先の関数を作るんです。これもかなりのオールスター感があってめちゃくちゃ好きです。
まとめ
対角線論法はしゅごい!以上!
参考文献
Laszlo Lovász, "Large networks and graph limits"