はじめに

こんにちは。りゅうふじわら(@ryunryunryun_)です。よろしくおねがいします。

この記事は鯵坂もっちょさん(@motcho_tw)主催の好きな証明 Advent Calendar 2018の15日目の記事です。

本記事は以前、僕の属する明治大学総合数理学部現象数理学科にて主催した「NCLT2018 AUTUMN SPECIAL -推しLT-」での僕の発表「対角線を追いかけて」で紹介しきれなかった「推し数学の証明」を語る記事になっています。

好きな証明Advent Calendarの存在を知ったとき、こんなうってつけの場があるのか！とビビビっときました。

はじめに
目標
Graphonってなに？
下準備
- Kernel版のweak regularity lemma
- Weak regularity lemmaを使える形に
Graphon空間はコンパクト
- Step 1
- Step 2
- Step 3
推しポイント
まとめ
参考文献

目標

以下の定理を証明します。

Theorem Graphon空間はコンパクト

用語は追って説明しますが、その証明が対角線論法 *1を使っててめっちゃかっこいいんです。推せます。

(注意) この記事は上のメインの定理に行き着くまで割とスキップしながら歩みを進めます。細かな補題の証明などは僕が作成したpdfに書いてあるので、ギャップがあるような場合はその都度明記するので、気になる方は適宜そちらを参照してください。

Graphonってなに？

Graphonとはグラフの可測関数による表現

Graphonとは"graph function"の略で、(ネットワークの意味での)グラフの隣接行列を可測関数により表現したものです。定義としてはこんな感じ。

Definition (Graphon) ${\mathcal{W}_0}$ を次のように定義する。

${ \begin{align} \mathcal{W}_0 = \left\{W \in L^\infty ([0, 1]^2) \mid W(x, y) = W(y, x), \ |W(x, y)| \le 1 \ \ a.e. \ (x, y \in [0, 1]) \right\} \end{align} }$

としたとき、 ${W \in \mathcal{W}_0}$ をGraphonと呼ぶ。

つまりは、Graphonとは正方形 ${[0, 1]^2}$ 上の本質的に有界で、 ${y = x}$ に関して対称な可測関数のことを言います。百聞は一見にしかず、例えば下図の左側の無向グラフはその隣接行列(繋がってれば1、繋がってなければ0とする行列)を、ドット絵のように ${[0, 1]^2}$ を ${n \times n}$ 分割したグリッドを1なら黒、0なら白と塗りつぶした絵へと変換すれば、グラフをgraphonへと翻訳することができます。

f:id:ryunryunryunryun:20181214175158p:plain

ここで、Graphonに対して本質的に有界という条件を課したことはかなり重要で、ゴールである「コンパクト性」を示すのにクリティカルに効いてきます。もちろん、非有界なものも考えることは可能です。その場合は ${L^p}$ graphonという枠組みがあって、次数が非有界であったり、ノードに対して十分にエッジがないような疎なグラフなどにも対応できるような代物があるのですが、ここではそういうものがある、とだけに留めておきます。

Graphon全体に距離を入れる

Graphon全体 ${\mathcal{W}_0}$ を少しいじって距離を入れていきます。まずは ${\mathcal{W}_0}$ にcut-normという、ちょっと特殊なノルムを入れてみます。

Definition (カットノルム; cut-norm) 実数値関数 ${||\cdot||_\square : \mathcal{W}_0 \to \mathbb{R}}$ を次のように定義する。

${ \begin{align} ||W||_\square = \sup_{S, T \subset [0, 1] : \rm{measurable}} \left| \int_{S \times T} W(x, y) dxdy \right| \end{align} }$

としたとき、 ${||\cdot||_\square}$ をcut-normといい、 ${\mathcal{W}_0}$ に対してノルムを定める。

グラフ理論において、"cut"(リンクはWikipedia)という概念があって、この概念のGraphon版だと思ってもらえればよいです。

このcut-normを元にして、cut-distanceという擬距離が導くが、その前に保測変換という概念を導入しましょう。 ${\lambda}$ はLebesgue測度です。

Definition (保測変換) 可測関数 ${\varphi}$ が保測変換であるとは、任意の可測集合 ${A}$ に対して

${ \begin{align} \lambda (\varphi^{-1}(A)) = \lambda(A) \end{align} }$

が成り立つことをいう。

すなわち、保測変換とは逆像に関して測度が保たれるようなマップです。これを使って、cut-distanceをcut-normを使って定義していきます。

Definition (カット距離; cut-distance) ${W, \ U}$ をgraphonとし、保測変換 ${\varphi: [0, 1] \to [0, 1]}$ に対して ${W^{\varphi}(x, y) = W(\varphi(x), \varphi(y))}$ と定める。このとき、 ${W}$ と ${U}$ のcut-distanceを

${ \begin{align} \delta_\square(W, U) = \inf_{\substack{\varphi, \psi: [0, 1] \\ \rm{measurable}}} \sup_{\substack{S, T \subseteq [0, 1] \\ \rm{measurable}}}\left| \int_{S \times T} W^\varphi(x, y) - U^\psi(x, y) dxdy\right| \end{align} }$

により定義すると、cut-distanceは ${\mathcal{W}_0}$ に関して擬距離になる。

cut-distanceと言いながらも擬距離であることは置いておいて、擬距離の理由は以下の図を見てもらえれば一目瞭然です。この図は距離の公理の1つでもある ${\delta_\square (W, U) = 0 \Longrightarrow W = U}$ が成り立たない例となっています。Graphonはグラフの隣接行列の可測関数による表現となっていますが、この表現はグラフの「形」は同じでもノードの番号の付け方に依存します。カット擬距離の定義を見ると保測変換によりノード番号の付け替えを行ってから、cut-normによって比べようと言っているのです。

f:id:ryunryunryunryun:20181214180517p:plain

ですが、一般にこういった擬距離空間 ${(\mathcal{W}_0, \delta_\square)}$ を距離空間に変換する方法があります。それは ${\mathcal{W}_0}$ に擬距離が0となるものを同じと見なすような同値関係を入れて商空間を考えればよいのです。つまりは次のようなことをしようということです。

Definition (Graphon空間) ${\mathcal{W}_0}$ に以下のような同値関係を入れる。

${ \begin{align} W \sim U \iff \delta_\square(W, U) = 0. \end{align} }$

この同値関係に対して、 ${\widetilde{\mathcal{W}}_0 := \mathcal{W}_0 / \sim }$ と定義したとき、 ${(\widetilde{\mathcal{W}}_0, \delta_\square)}$ をGraphon空間と呼ぶ。Graphon空間は距離空間である。

Graphon空間の要素のイメージとしては、ノード番号を無視したgraphonです。上図の形が同じなグラフはノード番号に関わらず同一視してしまおう！の精神を体現したものとなっているわけです。

収束Graphon列の例(ちょっと寄り道)

この節は寄り道なので、読み飛ばしてもらっても構いません。Graphon空間を考えると、何が嬉しいのでしょうか。その最たる例として、ノード数が増えていくようなランダムグラフ列に関して適切な極限を考えられてしまうのです。

例えば、古典的なランダムグラフを考えます。すなわち ${n}$ 個のノードに対してノードの各ペア間に確率 ${p}$ でエッジを結ぶようなグラフです。この規則の元、ノードの数に関して極限を考えると、下図のようにGraphon空間の元で ${W(x, y) = p}$ という極限が得られます。直感的には無限個ノードがある確率 ${p}$ の元で生成されるランダムグラフの期待値を取っているような感覚です。

f:id:ryunryunryunryun:20181214201133g:plain

ここで思い出してほしいのですが、少し上の方でGraphonの定義の仕方は本質的に有界であることがクリティカルに効いていると述べました。この事実はgraphon列の収束でもかなり効いてきて、疎なグラフに対応するgraphonの極限はなんと ${W(x, y) \equiv 0}$ になってしまうという欠点があるのです。再度の宣伝になりますが、 ${L^p}$ graphonはこれを解決できる代物となっています。(紹介はいつかまた)

下準備

さて、Graphon空間を定義できたので、メインテーマであるコンパクト性に移っていきましょう。ですが、そのために必要ないくつかの補題を証明無しで述べていきます。証明は僕が作成したpdfに書いてあるので、気になったらそちらを参照してください。

Kernel版のweak regularity lemma

まず、以下の話ですが、Graphonの値域を ${[0, 1]}$ から ${[-1, 1]}$ に広げたものを考えます。こうして拡張したものをkernelと呼ぶことにします。Graphon空間の構成方法と同様にkernel全体に対してcut-distanceから誘導される商空間を ${(\widetilde{\mathcal{W}}_1, \delta_\square)}$ として便宜上Kernel空間と呼ぶことにしましょう。*2

Kernelに対して次のようなweak regularity lemmaという命題が成り立ちます。*3なお、補題中で出てくる ${||\cdot||_2}$ は ${L^2}$ ノルムです。

Lemma (Kernel版のweak regularity lemma) ${W}$ をkernel、 ${k \ge 1}$ に対して

${ \begin{align} ||W - U||_\square \le \frac{2}{\sqrt{\log k}} ||W||_2 \end{align} }$

を満たすような ${k}$ 階の階段関数 ${U}$ が存在する。

Lebesgue積分論では可測関数が階段関数で任意精度で近似できることは当たり前だが、この補題ではcut-distanceの元でも階段関数によって任意精度での近似ができることを述べているのです。

Weak regularity lemmaを使える形に

このweak regularity lemmaを、メイン定理を示すのに使える形にちょちょいと変形します。そのために、kernelの階段化を定義します。

Definition (階段化) Kernel ${W}$ と ${[0, 1]}$ の分割 ${\mathcal{P} = (S_1, \ldots, S_q)}$ に対して、 ${W}$ の ${\mathcal{P}}$ による階段化 ${W_{\mathcal{P}}(x, y)}$ を次のように定義する。

${ \begin{align} W_{\mathcal{P}}(x, y) = \frac{1}{\lambda(S_i) \lambda(S_j)} \int_{S_i \times S_j} W(x, y)dxdy, \quad (x, y) \in S_i \times S_j. \end{align} }$

イメージとしては分割 ${\mathcal{P}}$ に対して、各区域 ${S_i \times S_j}$ に対して ${W}$ を均している感じです。階段化された後の関数 ${W_\mathcal{P}}$ はたかだか ${q}$ 階の階段関数になります。

この階段化を使ったweak regularity lemmaのcorollaryが次の評価となります。

Corollary 1 Kernel ${W}$ と ${k \ge 1}$ に対して、たかだか ${k}$ 階の分割 ${\mathcal{P}}$ が存在して、

${ \begin{align} ||W - W_\mathcal{P}||_\square \le \frac{4}{\sqrt{\log k}}. \end{align} }$

このcorollaryにより、勝手に取った自然数 ${k}$ よりも小さい階数の分割による階段化 ${W_\mathcal{P}}$ がcut-normの元で ${W}$ に近くすることができることが言えました。この勝手に取れる、というのがかなり重要です。

もう一個、corollaryを挙げておきます。これはCorollary 1から自明に従うことですが、後々のために述べておきます。なお、分割の細分とは、分割をより切り刻んだ分割のことを言います。

Corollary 2 ${m, k}$ を ${1 \le m > k}$ を満たす任意の自然数とする。任意のkernel ${W}$ と ${m}$ 階の分割 ${\mathcal{Q}}$ に対して、次を満たす $\mathcal{Q}$ の細分である ${k}$ 階の分割 $\mathcal{P}$ が存在する。

${ \begin{align} ||W - W_\mathcal{P}||_\square \le \frac{4}{\sqrt{\log k / m}}. \end{align} }$

Graphon空間はコンパクト

ようやく、僕の推し証明方法を紹介できる準備が整いました。もう一度、その定理を述べておきます。

Theorem Graphon空間はコンパクト

きれいな定理です。さあ、証明していきましょう。

以下から証明です。対角線論法を使います。愛おしいですね。

Graphon空間は距離空間なので、コンパクト性と点列コンパクト性は同値であるから、点列コンパクト性を示すことにしましょう。証明は3ステップに分けます。

Graphonの列 ${\{W_n\}}$ と各 ${n}$ に対する適当な分割の列 ${\{\mathcal{P}_{n, k}\}}$ を元に、 ${\{(W_n)_{\mathcal{P}_{n, k}}\}}$ が各 ${k}$ について階段関数 ${U_k}$ に収束するように ${\{W_n\}}$ の部分列を取り出します。
${U_k}$ がほとんど至るところであるgraphon ${U}$ に収束することを示します。
実は1.にて取り出した部分列がcut distanceの元で ${U}$ に収束することを示します。

Step 1

(Step 1の概要): Graphonの列 ${\{W_n\}}$ と各 ${n}$ に対する適当な分割の列 ${\{\mathcal{P}_{n, k}\}}$ を元に、 ${\{(W_n)_{\mathcal{P}_{n, k}}\}}$ が各 ${k}$ について階段関数 ${U_k}$ に収束するように ${\{W_n\}}$ の部分列を取り出します。

Graphonの列を ${\{W_n\}}$ としましょう。この列がcut-distanceの元で収束部分列を持つことを示すことがゴールです。では、分割 ${\{\mathcal{P}_{n, k}\}}$ を次の3条件を満たすように構成しましょう。簡単のため、 ${W_{n, k} := (W_n)_{\mathcal{P}_{n, k}}}$ と書くことにします。

${||W_n - W_{n, k}||_\square \le \frac{1}{k}}$
${\mathcal{P}_{n, k + 1}}$ は ${\mathcal{P}_{n, k}}$ の細分
${|\mathcal{P}_{n, k}| = m_k}$ は ${k}$ にのみ依存する。すなわち、 ${k}$ を固定すれば分割 ${\mathcal{P}_{n, k}}$ の大きさは一定

これら3条件を満たすような ${\{\mathcal{P}_{n, k}\}}$ の存在は前節で紹介したCorollary 1とCorollary 2にて保証されています。こうして構成した分割 ${\mathcal{P}_{n, k}}$ の各要素は不連結となっている可能性があるため、後々の都合上、すべての ${\mathcal{P}_{n, k}}$ を適当な全単射な保測変換によって区間へと変形しておく。

ここで次のclaimを示します。

Claim ${\{W_n\}}$ について、任意の ${k}$ に対して ${\{W_{n, k}\}}$ が ${m_k}$ 階の階段関数 ${U_k}$ にほとんど至るところで収束するような部分列を取り出せる。

対角線論法を使いますが、ちょっと複雑なので、下図を参照しながら読んでください。

f:id:ryunryunryunryun:20181214201811p:plain

まず、 ${k = 1}$ (図では1列目)に関して、 ${\mathcal{P}_{n, 1}}$ の全ての区間の長さが収束し、各区画上で ${W_{n, 1}}$ の値が収束するように ${\{W_{n, 1}\}_n}$ から部分列 ${\{W_{n_1, 1}\}_{n_1}}$ を取り出します。実際、実数の収束の話なので、Bolzano-Weirstrassの定理*4を有限回(区間の長さに関する ${m_1}$ 回と各区画の上での値に関して高々 ${m_1^2}$ 回)繰り返し使えば得られます。この部分列 ${\{W_{n_1, 1}\}_{n_1}}$ はとある ${m_1}$ 階の階段関数 ${U_1}$ にほとんど至るところに収束します。

こうして得た ${n_1}$ に関して、 ${\{W_n\}}$ の部分列 ${\{W_{n_1}\}}$ から、さらに同様に ${k = 2}$ (図では2列目)に対して、 ${\{W_{n, 2}\}}$ の部分列として、 ${m_2}$ 階のある階段関数 ${U_2}$ にほとんど至るところで収束するような ${\{W_{n_2, 2}\}_{n_2}}$ を取り出します。

この操作を帰納的に繰り返していくことで、全ての ${k}$ に関して ${\{W_{n_k, 2}\}_{n_k}}$ が、 ${m_k}$ 階の階段関数 ${U_k}$ に収束するようにするようにできます。

最後に各列 ${\{W_{n_k, 2}\}_{n_k}}$ から、それぞれ対角線である ${n_k = k}$ 番目に対応する ${\{W_n\}}$ の部分列を取り出せば、claimの通りの部分列を構成できます。この部分列を改めて ${\{W_n\}}$ としてしまいます。

これで、step 1が完了しました。

Step 2

${U_k}$ がほとんど至るところであるgraphon ${U}$ に収束することを示します。

このstepでは確率過程論の一部であるマルチンゲール理論を使います。かなりの飛び道具ですが、本証明に必要な分の紹介は僕のpdfなどに載っています。

${U_k}$ の構成方法から ${k \le l}$ に関して

${ \begin{align} U_k = (U_l)_{\mathcal{P}_k} \end{align} }$

が成り立ちます。これより、 ${[0, 1]^2}$ 上のランダムな点 ${(X, Y)}$ に対して ${\{U_k(X, Y)\}}$ はマルチンゲールであることがわかります。ここで、 ${U_k(X, Y)}$ は有界なので、マルチンゲールの収束定理より ${\{U_k(X, Y)\}_k}$ は概収束します。すなわち、ほとんどいたる所で ${\{U_k\}}$ は収束するので、その収束先を ${U}$ としましょう。

Step 2だけふわふわしている感は否めませんが、先に進みましょう。

Step 3

実は1.にて取り出した部分列がcut distanceの元で ${U}$ に収束することを示します。

まずは、step 2から ${\{U_k\}}$ は ${U}$ へ ${L^1}$ 収束しますので、任意の正数 ${\varepsilon}$ と十分大きな ${k \ge 3 / \varepsilon}$ に対して

${ \begin{align} ||U - U_k||_1 < \frac{\varepsilon}{3} \end{align} }$

が成り立ちます。Step 1から、同じ ${\varepsilon}$ と ${k}$ と十分大きな ${n'}$ に対して

${ \begin{align} ||U_k - W_{n', k}||_1 < \frac{\varepsilon}{3} \end{align} }$

が成り立ちます。したがって、 ${||\cdot||_\square \le ||\cdot||_1}$ であることとstep 1にて置いた仮定aに注意すれば、

${ \begin{align} \delta_\square(U, W_{n'}) & \le \delta_\square(U, U_k) + \delta_\square(U_k, W_{n', k}) + \delta_\square(W_{n', k}, W_{n'}) \\ & \le ||U - U_k||_1 + ||U_k - W_{n', k}||_1 + ||W_{n', k} - W_{n'}||_\square \\ & < \frac{\varepsilon}{3} + \frac{\varepsilon}{3} + \frac{\varepsilon}{3} = \varepsilon \end{align} }$

となるので、 ${\{W_n\}}$ は ${U}$ にcut-distanceの元で収束することが示された。

よって、Graphon空間は点列コンパクトであり、すなわちコンパクトである。

いぇーい！

推しポイント

この証明の推しポイントはなんてったって対角線論法です。見ました？各列 ${\{W_{n, k}\}_n}$ からぐわっとよりすぐりの精鋭達 ${\{W_{n_k, k}\}_{n_k}}$ を選んできたかと思いきや、その中から更に更に対角線としてエリート階段関数達を厳選しているんですよ！しかもこのエリート達が ${U}$ とかいう王様に収束するとかいうからもう、、、オールスター感すごくないですか！！！

この対角線論法とかいう論法ってかなり面白くて、選りすぐって更に選りすぐった猛者たちを集めてくるわけですから、条件の絞り込みができるんですよね。今回のGraphon空間はコンパクトの証明で言えば、一発目の選抜として各列の部分列を取ることで区画の幅と区画上の値を収束させて、二発目の選抜で対角線を選ぶことで一つ階段関数の幅を小さくしていくって感じです。

こうした論法を使った別の定理にAscoli-Arzelàの定理というのがあって、定理の内容としては

Theorem(Ascoli-Arzelà) ${\mathbb{R}^n}$ のコンパクト集合 ${\Omega}$ 上の実数値連続関数の列 ${\{f_n\}}$ が一様有界かつ同程度連続なら ${\{f_n\}}$ は一様収束する部分列を持つ。

というものですが、これも0次選抜で ${\Omega}$ のコンパクト性から可算個の点 ${\{x_m\}}$ を選んで、1次選抜でさっき選ばれた点上での ${\{f_n(x_m)\}_n}$ から収束部分列を選び、最終選抜にて対角線を取ってきて一様収束先の関数を作るんです。これもかなりのオールスター感があってめちゃくちゃ好きです。

まとめ

対角線論法はしゅごい！以上！

参考文献

Laszlo Lovász, "Large networks and graph limits"

*1:同Advent Calendarの昨日の記事でCantorの対角線論法が紹介されていましたが、本記事の「対角線論法」とは別のものとなっていますのでご注意ください。

*2:Kernelという言葉は関数解析学の積分作用素における積分核(Kernel)から来ています

*3:Regularity lemmaはSzemerédiのあれです。僕にはよくわからないけど、そういうものがあるらしいです。

*4:有界な実数列から収束部分列を取り出せる

りゅうふじわら(記事)

気が向いたときに気が向いたことを書きます。

Graphon空間はコンパクト(オールスター感)