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

arXiv

・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

arXiv

の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

arXiv

・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

arXiv

の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 な世界には実は愚直には適用することができません。しかし、今回のような数え上げの問題のように良い性質を持つ問題ならば適用することができる、というのが最大のウリです。

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" のようなものを証明し、それを利用して幅広い合意モデルの解析に応用しました。

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