2021年4月2日金曜日

次数分離: スパースなグラフで役立つアルゴリズムのアイデア

単純無向グラフ$G=(V,E)$上で長さ$k$の閉路を探したり直径を求めたくなったりする時があります。そして時には$G$はスパースになっていることを利用したくなります。今回の記事では、スパース性を利用した単純ながら面白く賢いトリック (次数分割: high-degree low-degree technique)を紹介し、これに基づいてグラフに含まれる三角形 (長さ3の閉路) の個数の数え上げを行う非自明なアルゴリズムを紹介します。次数分離という和名は私が勝手に名付けたものであり世間で浸透しているものではないので注意してください (もし世間で浸透している名前をご存知の方がいらっしゃいましたら教えていただけると嬉しいです...!!)。このアイデアはAlon, Yuster, Zwick [1] によるものです。

$|E|=m$, $|V|=n$とします。一般には$m=O(n^2)$になりえますが、今回は$G$がスパースであることを仮定してるので$m=O(n)$を想定します。ただ次数分離は一般の$m$に対しても適用でき、例えば$m=O(n^{1.5})$とかでも似たような解析で計算時間を見積もることができます。

次数分割の基本アイデア


頂点$v$の次数を$\deg(v)$とします。$\alpha\in[0,1]$をパラメータとし、
$$H=\{v\in V: \deg(v)>n^\alpha\},$$
$$L=V\setminus H$$
とします ($H$は high degree、$L$は low degree のイメージです)。すると、$2m=\sum_v \deg(v)$ なので
$$2m \geq \sum_{v\in H} \deg(v) > |H|n^\alpha$$
より$|H|<2m/n^\alpha$となります。特に$m=O(n)$ならば$|H|=O(n^{1-\alpha})$となり、$n$と比べて小さくなります。これらの頂点部分集合は$O(m)$時間で得られます (計算モデルは$O(\log n)$bit-Word-RAM モデルを仮定)。


応用. 三角形(長さ3の閉路$C_3$)の数え上げ


入力としてグラフ$G=(V,E)$が与えられ、$G$に含まれる長さ$3$の閉路$C_3$と同型な部分グラフを数え上げる問題を解いてみましょう。以下の二つの素朴なアルゴリズムを考えます。

・アルゴリズム1:

$G$の隣接行列の三乗を計算し対角成分の総和を見ると、長さ3の閉じたウォークの個数となり、これは三角形の個数の$3!=6$倍になっています。従って$O(n^{\omega})$時間で数え上げられます。 ($\omega<2.373$は高速行列積の指数)。

・アルゴリズム2:

各頂点に対して隣接点を列挙して隣接点のペアで隣接しているものがあるかどうかを見れば$O(\sum_{v\in V}\deg(v)^2)$時間で数え上げが解けます。$(2m)^2=\left(\sum_{v\in V}\deg(v)\right)^2\geq \sum_{v\in V}\deg(v)^2$より、このアルゴリズム2は$O(m^2)$時間なので、例えば$m=O(n)$なら$O(n^2)$となりアルゴリズム1以上に高速になります ($\omega=2$なら同等のオーダーになる)。

ここで、冒頭に説明したアイデアを考えます。適当なパラメータ$\alpha\in[0,1]$に対して上で定義した頂点部分集合$H,L$を得ます。入力グラフ$G$に含まれる三角形$C_3$は以下の二つのケースに分類されます:

ケース1. 三頂点全てが$H$に含まれる場合
ケース2. 一つ以上の頂点が$L$に含まれる場合

ケース1は誘導部分グラフ$G[H]$内に含まれる三角形の個数を数え上げれば良く, $|H|=O(n^{1-\alpha})$より素朴なアルゴリズム1を用いれば$O(n^{\omega(1-\alpha)})$時間で数え上げることができます。

ケース2は$L$に含まれる全ての頂点に対し素朴なアルゴリズム2を用いることで列挙できるので、数え上げることができます。このとき、$k$頂点が$L$に含まれるような三角形 $(k=2,3)$ は$k$回列挙されるため適当な値で割ったりする必要があるので気をつけてください。列挙にかかる時間は、$L$に属する頂点の次数が高々$n^\alpha$であるので $\sum_{v\in L}\deg(v)^2 \leq n^{1+2\alpha}$ となります。

以上より、$m=O(n)$の場合は任意の$\alpha\in[0,1]$に対して三角形の数え上げを
$$O(n^{\omega(1-\alpha)}+n^{1+2\alpha})$$
時間で解くことができます。$\alpha=\frac{\omega-1}{\omega+2}$とおくとこの計算時間は$O(n^{3-\frac{6}{\omega+2}})$時間になります。現状では$\omega<2.373$なのでこの計算時間は$O(n^{1.628})$となり, $O(n^2)$よりも高速になっています。もし将来$\omega=2$になることがあれば$O(n^{1.5})$となります。

上の解析では$m=O(n)$を仮定していましたが一般の$m$に対しても同様の解析で$O(m^{3-\frac{6}{\omega+2}})$時間で計算できることを示せます ($|H|=O(m^{1-\alpha})$となるので)。


まとめ


スパースなグラフに対して、ある閾値を設定しそれより高い次数を持つ頂点集合とそれ以外の頂点集合に分割するテクニックを紹介し、その応用として三角形の数え上げ問題を取り上げました。本質的には、このような分離を行い、低次数の頂点の探索は近傍を見るコストが低いことを利用し、高次数の頂点の探索はまとめて処理できる賢いアルゴリズムを利用する、というだけのことです。

三角形と同様の解析を用いれば、例えば入力グラフが四角形(長さ4の閉路)を部分グラフとして持つかどうかの判定問題を$O(m^{4/3})$時間で組合せ的 (高速行列積という飛び道具を使わず初等的に)解くことができます。$H$と$L$に分解したあと、$H$内部の四角形を鳩の巣原理に基づくアルゴリズム (昔の記事参照) で判定し、$L$の頂点を含む四角形は近傍探索を駆使して判定します。結構実装も簡単でシンプルかつ汎用性がありそうなアイデアなので、競技プログラミングで出ても良さそうな気が個人的にはします(というか既にある??)


参考文献


[1] N. Alon, R. Yuster, and U. Zwick, Finding and counting given length cycles, Algorithmica, 1997.

2021年3月31日水曜日

学生生活の振り返り

東京大学大学院 情報理工学系研究科 数理情報学専攻の博士課程を修了しました。自分は学部の4年間を東工大の理学部情報科学科で過ごし、その後に東大大学院に進み修士+博士の5年間を過ごしました。折角なので4+2+3年の学生生活を振り返りつつ、その過程で「もっとこれをすべきだった」や「これはしておいて良かった」と思う事などもまとめます。正直自分には特別なものはなく本当に多くのrejectをくらったりD3の1年間はコロナのせいで出張も行けず辛い思いを多くしてきたのですが、その一方で多くの論文を読んで勉強して研究し続けて理論計算機科学のトップ会議に何本か論文を通すことが出来たのは誇りに思っています。ただ、誰でもそうだとは思いますが、研究をしている最中は論文が通る保証はないわけで、その中で研究を続けていくことに不安を感じることも多々ありました。そんなごくごく普通の学生の吐露からなる記事ですが、興味があればぜひ読んでいってください。

1. D進の理由


自分はB4くらいからD進を考えていて、それ以外の道を考えたことがなかったので特に理由はありません。B4の最初に研究室所属をして初めて研究をした時にかなり楽しく研究できたことが大きかったと思います。学部の間に研究や勉強が楽しいと思えるのは非常に大事なポイントだと思います。今にして思えばD進に際してかなり視野が狭かった(就職に目を向けてインターンなどをしても良かった)気もしますが、逆に迷いなく研究に打ち込めたという面もあるのでどっちもどっちでしょうか。

2. 学生生活で良かったこと

  • とにかく勉強した。学生生活が終わると時間をとって勉強することが出来なくなるのではないかと漠然と思っていたので、将来後悔しないようにとにかくD1の1年間は研究はあまりせずとにかく勉強に打ち込みました。自分の場合は Arora & Barak の Computational Complexity や Frieze & Karonski の Introduction to Random Graphs を約1年くらいかけて読みました。特にランダムグラフの本は自分で手を動かしながら読んだのですが、そのおかげでランダムグラフに関する直感を自分で持つことができて今もたまにその直感が研究に役立つことがあるので、やってて良かったと思っています。
  • 色んな学会に参加した。ありきたりですが、全国の同年代の人たちと交流をもったり先生方と知り合いになれたのは本当に良かったと思っています。また色んな学会で発表をして自分を宣伝できれば、アカデミアの世界での就活で多少は有利に働くことになるんじゃないかと思います。
  • 共同研究をした。自分は博士の3年間はS先生とずっと研究をし、何本も論文を書きました。S先生は自分とは違うバックグラウンドを持つ方で、共同研究をしていく過程で自分一人では到達しえないアイデアを幾つも提案してくださり、結果としてより真理の深淵に近づけたと思います。確かに学会に参加すれば多くの方と交流する機会は得られますが、研究の技術的にディープな内容を討論することは出来ません。それを補いより研究を深めることが出来たというのは良かったと思います。

3. 辛かったこと

  • 「選ばれない」ことのショック。自分は幸運にも、受験などではこれまで「選ばれる」方だったのですが、そのために「選ばれない」経験をほとんどしてこなかったがためにDC1に不採択になった時は精神的ショックはかなり大きかったです。特に一時期は「周囲の知り合いが皆DC1を持っているのに自分だけ...」という部分に大きな負目を感じていました。自分の場合は、1ヶ月後くらいに「自分と他人を比較すべきではないから気にする必要はない。むしろ、これから凄まじい業績を出してDC1とった人たちを超えて当時の審査員を見返そう」と奮起してました。改めて見直すとちょっと引くくらいポジティブですが、なんにせよ失敗をひきずらない精神を持つのは重要だと思います。
  • 将来への不安。ありきたりで誰もが持つとは思います。自分の場合は「考えてもしょうがない。業績が出れば将来有利になるから今は研究に集中しよう」と考え、将来のことはほとんど考えないことにしました。

4. 後悔

  • 一つの究極的な目標をたててそれに邁進する研究をしたかった。自分は主に、個々の小問題を解決していくような研究をしてきました。それは学問における自分の研究の意義を薄くする要因になります。確かに問題を解くことも大事ですが、問題を解いたその後に何を見出すかもまた大事であり、この部分を蔑ろにしてしまったことへの後悔があります。自分が論文の中で新しく提案した部分はその分野においてどのように貢献するかを明白に意識して論文を書くべきでした。自分はこれが(ゼロではなかったにしても)まだまだ足りなかったためにD論でとても苦労しました。博士の3年間はこの力を養うのに最適な期間だと思うので、D進した方々はぜひ頑張ってください。また、将来のことを考えると業績をあげなければと焦るかもしれませんが、その時の流行のトピックにあやかって論文を書くよりも他の誰もやってないオリジナルの観点に基づいた研究を貫いた方が絶対強いと思います。
  • もっと海外に行きたかった。D1の1年間はとにかく勉強に邁進していたため、海外の学会などに参加しませんでした。D2になって国際学会に論文が通ったのですが、予期せぬアクシデント(千葉県を襲った巨大台風のせいで飛行機が飛ばず、代わりの飛行機が取れなかった)のためにこの時は海外に行けず、さらにD3では国際学会に3本論文が通ったのにCOVID19のために全てオンライン開催になってしまいました。そのため自分は修士の間に3回海外に行ったっきりで、Dの3年間は一度も海外に行ってません。今後もCOVID19の影響は続けば海外に行けないのも致し方ないですが、実際に海外のレベルの高い学会に参加してレベルの高い発表を聴いたりすると自分のモチベーションが上がったりするし良い機会になるのでやはり参加できるならばすべきだと思います。

5. 総括


ひたすら研究などに集中できたのは間違いなく周囲の環境のおかげであり、自分一人の力ではここまでやってこれないのは明白で、その環境を用意して下さった指導教員、研究室のメンバー、共同研究者、家族には感謝してもしきれません。

研究トピックを決めるのは本当に難しいと思いますが、これから進学していくみなさんには、単に問題を解くだけではなく、その分野における貢献を意識しながらトピックを策定していくことをぜひおすすめします(めちゃくちゃ難しいですが、、、)

2021年2月22日月曜日

The 123 Theorem

こんにちは. のぶしみです. 最近Mathlogという数学の記事共有サービスを使って記事を書くことにハマっておりまして, つい最近, エキスパンダーグラフの紹介記事を書きました. しかし今まで5年以上このブログをやってきているので, メジャーなトピックはmathlogで紹介し, マイナーなトピックは引き続きこのブログで紹介していきたいと思います.

そこで今回は123 Theoremと呼ばれる定理を紹介します. 変わった名前ですが, 次の定理です:

定理 (123 Theorem)
$X,Y$を同じ分布に従う実数上の二つの独立な確率変数とする. このとき
$$\Pr[|X-Y|\geq 2] \leq 3 \Pr[|X-Y|\geq 1].$$

123 Theoremという名前は不等式に出てくる三つの定数に由来します. 私がこの定理に初めて出会ったのは2021年1月に研究室の後輩とAlon & Spencer の The Probabilistic Method の輪読していた時に第1章の演習問題として出題されていた時でした. 私は基本的に本を読むときは演習問題は頑張って解く習慣があるので, 頑張って証明しようしたのですがかなり苦戦して, 結局丸一日を溶かして以下のようにして示すことが出来ました. 実は同じ証明が[1]に載っていてビックリしたので紹介します.


証明.
$x_1,\ldots,x_m\in\mathbb{R}$を$X$の分布に従って独立にサンプリングされた$m$個の点とし, $T_r=\{(i,j):|x_i-x_j|\leq r\}$とする ($(i,i)\in T_r$とする). まず

$|T_2| \leq 3|T_1|$ ......(1)

を示す. この主張は定理の離散化みたいなもので, 実は(1)を示せば良いということが以下の議論から分かります:
$$\mathrm{E}[|T_2|]=m+m(m-1)\Pr[|X-Y|\leq 2]$$
$$\mathrm{E}[|T_1|]=m+m(m-1)\Pr[|X-Y|\leq 1]$$
および(1)より
$$m+m(m-1)\Pr[|X-Y|\leq 2] \leq 3m+3m(m-1)\Pr[|X-Y|\leq 1].$$
これを整理すると,
$$\Pr[|X-Y|\leq 2] \leq 3\Pr[|X-Y|\leq 1] + \frac{2}{m-1}.$$
これが任意の$m$に対して成り立つので, $m\to\infty$とすれば,
$$\forall\epsilon>0,\,\Pr[|X-Y|\leq 2] \leq 3\Pr[|X-Y|\leq 1]+\epsilon.$$
即ち定理の主張が従う.

(1)の証明.
有向区間グラフの言葉で説明する. $\{x_1,\ldots,x_m\}$および$r>0$に対し, 有向グラフ$G_r$を, $V(G_r)=[m]=\{1,\ldots,m\}$, $E(G_r)=T_r$とする. 特に$(i,j)\in E(G_r)$ならば$(j,i)\in E(G_r)$でもあるので, 向きを付けることに本質的な意味はないが, 辺の本数=$|T_r|$として議論していきたいので有向グラフを考えることにする. つまり, $|E(G_2)|\leq 3|E(G_1)|$を示せば良い. 

二つのグラフ$G_1,G_2$を考える. 頂点$i$のグラフ$G_r$における出次数を$\deg_r^+(i)$とする. つまり, $\deg_r^+(i)=|\{j\in[m]:(i,j)\in E(G_r)\}|$であり, 自己ループも1としてカウントする.

主張(1)の証明は$m$に関する帰納法で行う. $m=1$なら$T_r=\{(1,1)\}$なので(1)は成り立つ. $m\geq 2$の場合を考える. $i\in[m]$を$G_1$内で最大出次数を持つ頂点とする. このとき, $\deg^+_2(i) \leq 3\deg^+_1(i)$が成り立つことを言う. もし$\deg^+_2(i)>3\deg^+_1(i)$とすると, 数直線上の区間 $[x_i+1,x_i+2]$ と $[x_i-2,x_i-1]$ のどちらかに必ず$>\deg^+_1(i)$個の点がある (下図).

図. もし$\deg_2^+(i)>3\deg_1^+(i)$なら, より出次数の大きい点がとれる.


これは$\deg^+_1(i)$が最大であることに矛盾します. 従って $\deg_2^+(i)\leq 3\deg_1^+(i)$です. $G_1$と$G_2$からそれぞれ頂点$i$を削除して得られるグラフを$G'_1$, $G'_2$とすれば, 帰納法の仮定より$|E(G'_2)|\leq 3|E(G'_1)|$であり, $|E(G_r)|=|E(G'_r)|+2\deg^+_r(i)+1$なので,

$$|E(G_2)|\leq 3|E(G'_1)|+6\deg^+_1(i)+1<|E(G_1)|$$

となり(1)が成り立つ.


補足


123 Theoremはタイトな例を作ることができ, 例えば$\Pr[|X-Y|\leq 2] \leq 2.99\Pr[|X-Y|\leq 1]$は一般には成り立ちません: $\{2,4,6,\ldots,2n\}$上の一様分布を考え, この分布に従う独立な二つの確率変数$X,Y$を考えます. このとき,
$$\Pr[|X-Y|\leq 2] = \frac{3}{n}-\frac{2}{n^2},$$
$$\Pr[|X-Y|\leq 1] = \Pr[X=Y]=\frac{1}{n}$$
より, $\Pr[|X-Y|\leq 2] = 3\Pr[|X-Y|\leq 1] - \frac{2}{n^2}.$


参考文献


[1] N. Alon and R. Yuster. The 123 Theorem and its extensions, Journal of Combinatorial Theory, Series A, 72(2)322--331, 1995.

2021年2月15日月曜日

ランダム正則グラフの sandwich conjecture

ランダム正則グラフ理論において有名な sandwich conjecture と呼ばれる予想があるのですが, 最近この予想に大きな進展[3,4]が見られたので紹介します. このトピックは私が修士の頃から論文を読んで追っていたトピックなので, 今回の進展をもたらした論文の登場は個人的にはかなり衝撃的でした.


1. ランダム正則グラフとErdős–Rényiグラフ


1.1. 定義

$n$ 頂点 $d$-正則の頂点ラベル付きグラフ全体の集合から一様ランダムに取り出したグラフをランダム$d$-正則グラフと呼び, $G_{n,d}$ で表します. また, $n$頂点の各頂点のペアを独立に確率$p$で辺で引いて得られるランダムなグラフを Erdős–Rényiグラフと呼び, $G(n,p)$ で表します. $G(n,p)$の基本的な性質などは以前の記事を参照してください.


1.2. ランダムグラフの解析

ランダムグラフの解析をする上でそのランダムグラフの生成モデルに対する考察が不可欠です. たとえば, 

$p=o(n^{-1})$ に対して $G(n,p)$ は確率 $1-o(1)$ で三角形を含まない

という事実が知られていますが, これは, $X$ を $G(n,p)$内に含まれる三角形の個数と定めたときに, Markovの不等式より

$\Pr[X\geq 1] \leq \mathbb{E}[X] = \binom{n}{3}p^3 \leq (np)^3 = o(1)$

となることから従います. $G(n,p)$を考えると$\mathbb{E}[X]$の期待値が非常に計算しやすいためにこのような簡単に証明できるわけです.

それでは, $G_{n,d}$ に含まれる三角形の個数 $X$ に対して $\mathbb{E}[X]$ を求める時はどのようにすれば良いでしょうか? $G(n,p)$の場合は各辺が独立に出現していたので簡単に $\mathbb{E}[X]$ を求められましたが, $G_{n,d}$ はそうとはいきません.

実は, $G_{n,d}$ には configuration model と呼ばれる生成モデルが知られていて, これを使えば $2^{O(d^2)} nd$ 時間でランダム $d$-正則グラフを生成することができます. 技術的な詳細は省きますが, このconfiguration model に基づけば $d=d(n)$が $n$ に依存しない定数ならば $G_{n,d}$ のさまざまな構造的性質を用意に解析することができます. 例えば, $d$が定数のときは $n\to\infty$ の漸近で三角形の個数$X$ はポアソン分布に従うことが証明できます. また, $d=d(n)$ が $o(\sqrt{\log n})$ くらいまでならなんとかできることもありますが, 例えば $d=(1+o(1))n^{1/3}$ などの場合は難しくなります.

$d=d(n)$ が大きいときの$G_{n,d}$の生成はそれ自体が一つの研究トピックになるほど難しい問題になっていて, 例えば $d=o(n^{1/2})$ に対して $G_{n,d}$ を $O(nd^3)$ 時間でサンプリングする論文がFOCS15に採択されています[6]. このトピックは多くの論文がありますが, 大体は switching method と呼ばれる手法に基づいたものになっていて, この手法を考えることで$G_{n,d}$ の解析を (時にはかなりアドホックな発想も必要になりつつも) 行うことができます ([2]の10章参照). しかしながら switching method を以てしても $d=o(n^{1/2})$ などの条件を課す必要があります. 

すなわち, $d=d(n)$ が大きくなるにつれて$G_{n,d}$の生成と解析は困難なものになっていきます.


1.3. 構造的類似性

$G(n,p)$ の平均次数 $np$ が $np=d=\omega(\log n)$ を満たすとき, $G_{n,d}$と近い構造を持つであろうことが以下の議論から推察できます: まず, $G(n,p)$の頂点 $v$ を固定しその次数 $\deg(v)$ を考えます. この値は$G(n,p)$ がランダムに生成されるので確率変数となっていますが, $\deg(v)=\sum_{u\in V\setminus \{v\}} \mathbb{1}_{uv\in E}$ と書けてこれは独立確率変数の和になっているため, 期待値 $(n-1)p\approx np$ に集中します. 具体的には, Chernoff bound (補足の章の補題A.1参照) とUnion boundを組み合わせると, 任意の$t>0$に対し$$ \Pr[\forall v\in V, |\deg(v)-(n-1)p|\geq t] \leq 2n\exp\left(-\frac{t^2}{2(n-1)p+2t/3}\right)$$が示せます. 特に, $np=\omega(\log n)$ が成り立つときに $t=10\sqrt{np\log n}$ を代入すると, 非常に高い確率で, 全ての頂点の次数が $np\pm 10\sqrt{np\log n}$ の範囲におさまることが示せます. この議論から, $G(n,p)$ は "ほぼ" $(np)$-正則グラフとみなすことができるので, $np=d$のときは $G(n,p)$と$G_{n,d}$は似た構造的性質を持つことが予想されます. 実際, 彩色数や最大クリークのサイズなどは漸近的にほぼ同じ値を持つことが知られています.

(*) あくまでもこの類似性は $d=np$ が大きい場合にのみ成り立つことに注意してください. 例えば $d=np=3$ のとき, $G_{n,d}$ は確率 $1-o(1)$ で連結である一方で $G(n,p)$ は確率 $1-o(1)$ で非連結です.


2. Sandwich conjecture


1章で述べた類似性をちゃんと議論した研究が幾つかあります [1,3,4,5]. 一番最初にこの類似性を研究したのは Kim & Vu [5] です. 彼らの定理を述べるために, $\mathcal{G}(n,p)$ を $G(n,p)$ の分布, $\mathcal{G}_{n,d}$ を $G_{n,d}$ の分布とし, $X\sim \mathcal{G}$ と書いた時は確率変数 $X$ は分布$\mathcal{G}$に従うことを意味します. また, 次の定理ではランダムグラフのカップリングについて考えていきます. カップリングの定義などについては補足A.2を参照ください.


定理1 (Informal; Theorem 2 of [5]).

$d=d(n)\in\mathbb{N}$ を, $d=\omega(\log n)$ かつ $d=o(n^{1/3}/\log^2 n)$ を満たす関数とする.
$p_1=p_1(n)=(1-O(\log n/d)^{1/3}) d/n$,
$p_2=p_2(n)=(1+o(1))d/n$
とする. このとき, 次を満たす $G_L\sim \mathcal{G}(n,p_1)$, $G_d\sim \mathcal{G}_{n,d}$, $G_U\sim \mathcal{G}(n,p_2)$ のカップリング $\pi$ が存在する:
(1) $\Pr[E(G_L) \subseteq E(G_d)] = 1-o(1)$.
(2) 確率 $1-o(1)$ で $E(G_U) \setminus E(G_d)$ のなすグラフの最大次数は $o(\log n)$




定理1の内容はinformalなもの (特に $p_2$ には実際にはもう少し条件が設定されている) であることに注意してください. 厳密なステートメントを知りたい方は元論文[5]を参照してください.

定理1から, $G_{n,d}$ は $d$ が定理1の条件を満たす場合は $p\approx d/n$ に対し $G(n,p)$ を部分グラフとして含むということが従います. 例えばこの $G(n,p)$ が直径$\leq 10$ であったならば, これを含む $G_{n,d}$ も直径$\leq 10$ になることが直ちに従います. より一般的に, 辺の追加における単調性を持つような性質を$G_{n,d}$が持つという証明をしたい場合は対応する $G(n,p)$ で考えれば良いという議論になるので, ランダム正則グラフの構造的性質の証明が一気にしやすくなるわけです.

その一方で, (2)の結果では単に $G(n,p_2)\setminus G_{n,d}$ の最大次数が抑えられるということしか主張しないので, $G(n,p_2)$が$直径>10$であることが言えたとしてもそこから$G_{n,d}$が直径$>10$になることが従うわけではありません. つまり, 定理1には

・ $d=d(n)$ に条件がついている (特に, $d=o(n^{1/3})$じゃないといけない).
・包含関係が片方しか示されていない.

という二つの問題点が残っていることになります. Kim と Vuは sandwich conjectureと呼ばれる次の予想を[5]で提示しています:

予想 (Sandwich conjecture, Conjecture 1 of [5]).

$d=d(n)=\omega(\log n)$ とする. ある関数 $p_1=(1-o(1))d/n$, $p_2=(1+o(1))d/n$ に対して, 以下を満たす $G_L\sim \mathcal{G}(n,p_1)$, $G_d\sim \mathcal{G}_{n,d}$, $G_U\sim \mathcal{G}(n,p_2)$ のカップリングが存在する:
$\Pr[G_L \subseteq G_d \subseteq G_U] = 1-o(1)$.



3. Sandwich conjecture 解決への進展


Sandwich conjectureに対する進展を簡単に紹介していきます.

・Kim & Vu [5] では上にあげた二つの問題点を残していました.

・Dudek, Frieze, Ruciński, and Šileikis [1] は, $d=\omega(\log n)$ かつ $d=o(n)$ ならば, ある$p_1=(1-o(1)) d/n$ に対して 定理1 の(1) の条件を満たすようなカップリングがあるということを示しています. 実際には[1]ではランダムグラフを一般化したランダムハイパーグラフを考えてカップリングの存在性を証明しています. ランダムグラフの本[2]の10章にこの結果の説明と証明が載っているので気になる方は参照ください. 実は, 私が2018年にSODAに通した論文も[1]の結果を用いています.

・Gao, Isaev, and McKay [4] は $d=\omega(n/\sqrt{\log n})$ に対して Conjecture 1 が真であることを主張しています. Kim and Vu の問題点だった逆方向の包含関係を ($d$が非常に大きいという仮定の下ではありますが) 解決したものになっています.

・Gao [3] は $d=\Omega((\log n)^7)$ に対して Conjecture 1 は真であることを主張しています. [4]では $d$ の仮定が非常に強いものでしたが, これをほぼ解決したということになります.


4. まとめ

ランダム正則グラフが研究に出てくるときは, $p=d/n$ に対して $G(n,p)$ を考えると良いです. もし $G(n,p)$ が望ましい性質を持つならば, sandwich conjecture より, 対応する $G_{n,d}$ も同様の性質を持つことが言えるかもしれません.



A. 補足


A.1. 集中不等式

補題A.1 (Chernoff bound; Theorem 21.6 of [2]).

$X_1,\ldots,X_n$を独立な確率変数で, $0\leq X_i\leq 1$ とする (必ずしも同一である必要はない). $S=\sum_{i=1}^n X_i$ とし, その期待値を $\mu$ とする. このとき, 任意の$t>0$に対して以下が成り立つ:

$$\Pr[S\geq \mu+t] \leq \exp\left(-\frac{t^2}{2\mu + 2t/3}\right),$$

$$\Pr[S\leq \mu-t] \leq \exp\left(-\frac{t^2}{2\mu + 2t/3}\right).$$


A.2. カップリング


$X$と$Y$をそれぞれ分布 $\mathcal{D}_X,\mathcal{D}_Y$ に従う確率変数とします. $X$と$Y$の同時分布 $\pi$ であって, $X$と$Y$の周辺分布$\pi_X$, $\pi_Y$ がそれぞれ$\mathcal{D}_X$, $\mathcal{D}_Y$と等しいものを, $X$と$Y$のカップリングと呼びます. この記事では$G(n,p)$や$G_{n,d}$をそれぞれ確率変数とみなし, ランダムグラフ同士のカップリングを考えることがあります. また, 確率変数と分布を区別するために, $G(n,p)$と$G_{n,d}$の分布をそれぞれ $\mathcal{G}(n,p)$, $\mathcal{G}_{n,d}$ と書くことにします.

例1: $G(n,p)$ と $G(n,p)$ のカップリング.

$\mathcal{G}(n,p)$に従って得られた二つのグラフ $G_1,G_2$ が, $G_1=G_2$を満たすようなカップリングが存在します. 最初に$X$として$G(n,p)$を考え, 次に$Y=X$とするだけです. このカップリングにしたがって得られた二つのグラフ $G_1,G_2$は必ず $G_1=G_2$ となっており, $G_1$と$G_2$の周辺分布はどちらも$\mathcal{G}(n,p)$ になっています. 自明な例です.

例2: $G(n,p_1)$ と $G(n,p_2)$ のカップリング.

$p_1\leq p_2$ とします. $G_1\subseteq G_2$ となるような $G_1\sim \mathcal{G}(n,p_1)$ と $G_2\sim \mathcal{G}(n,p_2)$ のカップリングが存在します. まず, $G_2\sim\mathcal{G}(n,p_2)$を生成します. そして得られたグラフ$G_2$の確辺を確率 $1-p_1/p_2$ で削除して得られたグラフを$G_1$とします. このように生成したグラフの組 $(G_1,G_2)$ は $G_1\subseteq G_2$の条件をみたします. $G_2$の周辺分布は明らかに$\mathcal{G}(n,p_2)$です. 最後に$G_1$の周辺分布を考えます. $G_1$の各辺は独立に現れ, その確率は$p_2\cdot (1-(1-p_1/p_2))=p_1$ となり, 確かに$G_1$の周辺分布は$\mathcal{G}(n,p_1)$となります.

この例で紹介したカップリングの存在生から, 例えば次の結果が用意に証明できます:

命題 A.2.

$G(n,p_1)$が確率$1-o(1)$で連結であるとする. このとき, 任意の $p_2\geq p_1$ に対して $G(n,p_2)$は確率$1-o(1)$で連結である.

証明:
例2のカップリング$\pi$を考える. このとき
$$\Pr[G(n,p_2)\text{ is connected}] = \Pr_{(G_1,G_2)\sim \pi}[G_2\text{ is connected}]\geq \Pr_{(G_1,G_2)\sim \pi}[G_1\text{ is connected}]$$
となり, $G_1\sim\mathcal{G}(n,p_1)$は確率$1-o(1)$で連結であることから主張は直ちに従います. 上式の不等号は$G_1\subseteq G_2$から従います.

一般に, 連結性といった, 辺の追加でinvariantなグラフの性質ならどんなものでも命題A.2のような結果が例2のカップリングを使えばすぐに示せます.



参考文献

[1] Andrzej Dudek, Alan Frieze, Andrzej Ruciński, and Matas Šileikis. Embedding the Erdős–Rényi hypergraph into the random regular hypergraph and Hamiltonicity, JCTB, 2017.

[2] Alan Frieze, and Michał Karoński. Introduction to random graphs, Cambridge University Press, 2015

[3] Pu Gao, Kim-Vu's sandwich conjecture is true for all $d=\Omega(\log^7n)$. arXiv, 2020. https://arxiv.org/abs/2011.09449

[4] Pu Gao, Mikhail Isaev, and Brendan D. McKay. Sandwiching random regular graphs between binomial random graphs. In Proceedings of SODA, 2020.

[5] Jeong Han Kim and Van H Vu. Sandwiching random graphs: Universality between random graph models. Advances in Mathematics, 2004.

[6] Pu Gao and Nicholas Wormald. Uniform Generation of Random Regular Graphs, In Proceedings of FOCS, 2015.

2020年10月17日土曜日

SODA21に論文が2本通りました (2/2)

 論文が SODA21 (Symposium on Discrete Algorithms) に 2本採択されました。


Nearly Optimal Average-Case Complexity of Counting Bicliques Under SETH
Shuichi Hirahara and Nobutaka Shimizu

How Many Vertices Does a Random Walk Miss in a Network with Moderately Increasing the Number of Vertices?
Shuji Kijima, Nobutaka Shimizu, and Takeharu Shiraga

の2本です。どちらの論文も非常に面白い内容で、嬉しいことに全ての査読者にかなり褒めて頂きました。


この記事では、前回に引き続き、後者の論文
How Many Vertices Does a Random Walk Miss in a Network with Moderately Increasing the Number of Vertices?
の概要をものすごく簡潔に紹介します。

具体的なモデルと結果を述べると少し長くなってしまうので、背景と貢献を簡単に紹介させて頂きます。


実世界に現れるネットワーク上の解析は、そのネットワーク上での様々な現象 (例えば情報拡散など)の振る舞いを知る上で大きな手がかりとなるため非常に重要な研究トピックの一つとなっており、ランダムウォークなどの手法が用いられることが多々あります。


また、実世界に現れるネットワーク (例えばSNSのネットワーク, 化学反応ネットワーク, 携帯電話の基地のセルラネットワークなど) は時間と共にそのグラフ構造が変化します。


この背景を踏まえ、時間とともに変化する動的なネットワーク上でのランダムウォークを理論的に解析するというのが本論文の主題となります。


実は動的なネットワーク上のランダムウォークは幾つか既存研究があるのですが、それらのほとんどは、辺だけが動的に変化するネットワークを対象としています。


というのも、ネットワーク上でランダムウォークを評価する際には、全頂点を訪問するのに必要な時間 (cover time) 、特定の頂点を訪問するのにかかる時間 (hitting time) 、定常分布に収束するまでにかかる時間 (mixing time) などの指標が基本的です。しかし頂点数が動的に変化するようなネットワークに対してはこれらの指標は定義できない(例えば cover time はどうする?)ため、何を解析していいのかがよく分かりませんでした(つまり、ランダムウォークをしている最中にも頂点が増えていくことがあるので、全頂点を訪問するという概念がよく分かりません)。


本論文では、頂点が動的に増え続けるグラフ (growing graph) 上のランダムウォークを評価する指標として、「時刻1からnまでのランダムウォークでカバーされない頂点の個数」を見ることを提案し、様々なタイプのグラフに対してその個数の期待値の上下界を導出しました。



頂点集合が動的に変化するグラフの解析は非常に重要なトピックではあるものの、そのようなグラフ上のランダムウォークはこれまでほとんど解析されていませんでした。でもそのようなグラフ上のランダムウォークの解析は考えるべき課題であり、その需要に応えたという点がこの論文の最大の貢献です。



SODA21に論文が2本通りました (1/2)

論文が SODA21 (Symposium on Discrete Algorithms) に 2本採択されました。

Nearly Optimal Average-Case Complexity of Counting Bicliques Under SETH
Shuichi Hirahara and Nobutaka Shimizu

How Many Vertices Does a Random Walk Miss in a Network with Moderately Increasing the Number of Vertices?
Shuji Kijima, Nobutaka Shimizu, and Takeharu Shiraga

の2本です。どちらの論文も非常に面白い内容で、嬉しいことに全ての査読者にかなり褒めて頂きました。

この記事では、前者の論文
Nearly Optimal Average-Case Complexity of Counting Bicliques Under SETH
の概要をものすごく簡潔に紹介します。

この論文はNIIの平原 秀一さんとの共著です。今年の2月に 冬のLA symposium で発表させていただいた内容を論文としてまとめたものになっています。

この論文は「ランダムグラフの tractability」が主要なテーマです。NP困難な問題は "intractable" であるというイメージを持つ方が多いと思います。しかしながらNP困難であるからといって実用的に解けないというわけではないはずです。なぜならば、その問題がNP困難であるとは、$\mathrm{P}\neq \mathrm{NP}$の下で

任意の多項式時間アルゴリズム $A$ に対し, ある入力の族 $(x_n)_{n\in\mathbb{N}}$ が存在して 全ての$n\in\mathbb{N}$に対し$A(x_n)$は不正解となる

ことを主張しているに過ぎず、つまるところ意地悪な入力 $x_n$ は非常に人工的に構成されたものになるからです。ですので、現実世界にしばしば現れるような入力ではもっと高速に解ける可能性があるはずです!

ということは、問題の時間計算量を、「全ての入力に対し正解する最速のアルゴリズム」ではなく「多くの入力に対して正解する最速のアルゴリズム」で測るという考え方がより実用性に近いと思われます。この考え方を平均計算量といいます。平均計算量のより詳しいフレームワークはこちらを参照してください。

この論文では、「$n^{c+o(1)}$ 時間で解けるとあるグラフ上の問題に対し, (SETHと呼ばれる予想の下で)ランダムグラフ上ですら $n^{c-\epsilon}$ 時間では解けない 」ことを証明しました。具体的には、ランダム二部グラフが入力として与えられたときにそれに含まれる完全二部グラフ $K_{a,b}$ と同型な部分グラフの個数を数え上げる問題を考えます。この問題は愚直にやると $O(n^{a+1})$ 時間で解くことができます (頂点を $a$ 個列挙し、その$a$個全てに隣接している頂点を列挙すれば良い)。また、例えば $a=b=2$ の場合だとこれは四角形の個数をカウントする問題になりますが、これは現状知られている中では $O(n^{\omega})$ 時間が最速です ($\omega <2.373$ は高速行列積の指数). この論文では $K_{a,b}$ 数え上げ問題に対し、
(i). $a\geq 8$ なら $bn^{a+o(1)}$ 時間で解けることを証明
(ii). SETHの下では任意の $\epsilon>0$ に対し, 十分大きな $b=b(a,\epsilon)$ が存在して $K_{a,b}$ の数え上げは$n^{a-\epsilon}$ 時間では解けないことを証明
(iii). ランダム二部グラフ上で $T(n)$ 時間で解けるならば、全ての入力に対し $T(n)\mathrm{polylog}(n)$ 時間で解く乱択アルゴリズムが存在することを証明
しました。

SETH に関しては Hardness in P について紹介しているこちらのページを参照ください。

(ここから先は専門家向けの説明になります)

実はこの論文の最大の貢献は、fine-grained average-case complexity に hardness amplification の枠組みを提供したことにあります。hardness amplification は 平均計算量の世界ではかなりスタンダードなツールなのですが、local list decoding なので uniform な計算モデルで考えようとすると advice が必要になり、fine-grained な世界には実は愚直には適用することができません。しかし、今回のような数え上げの問題のように良い性質を持つ問題ならば適用することができる、というのが最大のウリです。

2020年10月16日金曜日

ICALP20に論文が通りました。

半年くらい前の話になってしまいますが、ICALP2020 (International Colloquium on Automata, Languages and Programming) に論文が通りました。中央大学の白髪 丈晴さんとの共著です。

この論文では以前の論文と同様にグラフ上の合意モデルと呼ばれるものを解析しています。合意モデルでは、各頂点が意見を持った無向連結グラフを考えます。各ラウンドで各頂点は隣接点と通信を行い、予め定められたプロトコルに従い意見を同時に更新します。プロトコルの目的は合意(つまり全頂点が同じ意見を持つ状態)に至ることで、それまでにかかるラウンド数が興味の対象となります。具体的にはpull voting, best-of-two, best-of-three などが非常に有名で、特に分散コンピューティングの文脈でよく研究されています。詳細はリンク先を参照してください。

幾つかの既存結果では best-of-two や best-of-three といった特定のモデルに対してそれぞれアドホックに解析がなされていましたが、本研究の最大の特徴はこれらのモデルを含む幅広い合意モデルのクラス quasi-majority functional voting と呼ばれる合意モデルを提案したことにあります。そして、この広いクラスに属する合意モデルがエキスパンダーグラフ上だと高速 ($O(\log n)$ ラウンド) に合意に至ることを証明しました。

簡単なアイデア


今回は各頂点が二種類$A,B$どちらかの意見を持つケースを考えています。このとき、合意モデルは $2^V$ 上のマルコフ連鎖と見なせます。しかし、完全グラフ上だと $A$の意見を持つ人数にだけ着目すればよくなるので、マルコフ連鎖の状態空間は $\{0,\ldots,|V(G)|\}$ とできるので解析が一気に簡単になります。エキスパンダーグラフ上の合意モデルは、厳密には $2^V$ 上のマルコフ連鎖ですが、実は $\{0,\ldots,|V(G)|\}$上のマルコフ連鎖に「近似」できることを証明しました。この話は best-of-two では既に知られており、Expander Mixing Lemma を用いることで証明できるのですが, この研究ではそれを拡張したいわば "Nonlinear Expander Mixing Lemma" のようなものを証明し、それを利用して幅広い合意モデルの解析に応用しました。

議論をするたびに共著者様がすごく非自明な式変形を涼しい顔で繰り出してこられたのがとても面白かったです(ありがとうございました)