駆け足で学ぶエクスパンダーグラフ

こんにちは. Le Algorithm の著者をしているのぶしみ( @knewknowl )と申します. 数学系の記事を執筆しやすそうなMathlogというサービスを知ったので, 試しがてらに一記事を執筆しようと思い立ったのでエクスパンダーグラフについての紹介記事を書いています.

グラフ理論やグラフアルゴリズム関連の研究に携わると「エクスパンダーグラフ」という単語に出会うことがあります. この記事ではこのエクスパンダーグラフについて概説します. 前提知識としては, 線形代数の基本的な事柄(固有値の定義とか)が分かっていれば大丈夫です. 念の為, 本記事の末尾に付録Aとして行列のスペクトルノルムの定義や基本的な性質を載せています.

1. 基本的な定義

基本的な用語の定義をします. グラフの隣接行列, 遷移確率行列, グラフラプラシアンの定義を知っていれば1章は読み飛ばして頂いても構いません.

有限集合$V$に対し,$\binom{V}{2}=\{\{u,v\}\subseteq V:u\neq v\}$とします. $E\subseteq \binom{V}{2}$に対し, 組$G=(V,E)$をグラフ (graph)と呼びます (正確には有限無向グラフですが, この記事では簡単にグラフとします) ここで$E$を辺集合, $V$を頂点集合と呼び, それぞれの要素を辺(edge)及び頂点(vertex)と呼びます. この記事中では頂点集合のサイズを$n$で表すことにします.

グラフ$G=(V,E)$の各頂点$v\in V$に対し, $N(v)=\{w\in V:\{v,w\}\in E\}$を$v$の隣接頂点集合とし, $\deg(v)=|N(v)|$を$v$の次数(degree)と呼びます. 全ての頂点の次数が$d$に等しいグラフを$d$-正則グラフ($d$-regular graph)または単に正則グラフ(regular graph)と呼びます.

グラフ$G=(V,E)$の隣接行列(adjacency matrix)$A\in\{0,1\}^{V\times V}$を以下で定めます:
\begin{align*} A_{u,v}=\begin{cases} 1 & \text{if }\{u,v\}\in E,\\ 0 & \text{otherwise}. \end{cases} \end{align*}
また, 対角行列$D\in\mathbb{R}^{V\times V}$を
\begin{align*} D_{u,v}=\begin{cases} \deg(v) & \text{if }u=v,\\ 0 & \text{otherwise} \end{cases} \end{align*}
とします. また, $\mathbf{1}\in\mathbb{R}^{V}$を成分が全て$1$のベクトルとし, $\mathbf{0}$でゼロベクトルを表すことにします.

$P=D^{-1}A\in[0,1]^{V\times V}$で与えられる行列を$G$の遷移確率行列(transition matrix)と呼びます. 特に, 遷移確率行列$P$の各成分$P_{u,v}$は, $\{u,v\}\in E$のときは$\frac{1}{\deg(u)}$となります. 隣接行列$A$は対称行列ですが, $P$は必ずしも対称にはならないことに注意してください.

$L=D-A$で与えられる行列をグラフラプラシアン (graph Laplacian)と呼びます. また, $\tilde{L}=D^{-1/2}LD^{-1/2}=I-D^{-1/2}AD^{-1/2}$で与えられる行列を正規化したラプラシアン (normalized Laplacian)と呼びます. ここで, $D^{1/2},D^{-1/2}$はそれぞれ$D^{1/2}=\mathrm{diag}(\sqrt{\deg(v_1)},\ldots,\sqrt{\deg(v_n)})$, $D^{-1/2}=(D^{1/2})^{-1}$で与えられる行列です.

2. スペクトルグラフ理論

グラフに付随する行列を定義しました. 実はグラフ理論には, グラフの構造的性質をその固有値を使って解析する理論があり, スペクトルグラフ理論(spectral graph theory)と呼ばれています.

2.1. 実固有値性

隣接行列とグラフラプラシアン及びその正規化はどれも対称行列なので実固有値を持ちます. 一方で遷移確率行列$P$は対称ではないので一見すると実固有値を持たないように見えますが, 実は$P$の固有値は全て実数になることが示せます:

また, グラフラプラシアン$L$は$L\mathbf{1}=\mathbf{0}$より, 必ず$0$を固有値に持ちます. 特にグラフが正則グラフのとき, $D=dI$なので, どの行列を考えても本質的に等価です ($I\in \{0,1\}^{V\times V}$は単位行列).

2.2. 連結性

connectivity

直感的に言えば, どの二頂点も辺を辿って行き来できればそのグラフは連結であるということになります.

連結成分を二つ持つグラフ$G$を考え, その連結成分のなすグラフを$G_1,G_2$とし, それぞれの遷移確率行列を$P_1,P_2$とします. すると$G$の隣接行列$P$は, 頂点番号を適切に振り分けることで以下のブロック対角行列として表すことができます:

\begin{align*} P=\left[ \begin{array}{cc} P_{1} & O \\ O & P_2 \end{array} \right]. \end{align*}
ここで$O$は全ての要素がゼロの行列です. ベクトル$x_1=[\mathbf{1}\hspace{0.5em}\mathbf{0}]^{\top}$と$x_2=[\mathbf{0}\hspace{0.5em}\mathbf{1}]^\top$を考えると, どちらも$Px_i=x_i$を満たすことが確認できます. なので$P$の固有値1の多重度は$2$になっていて, これは$G$の連結成分の個数と等しくなります. 一般的に, 次の命題が成り立ちます.

2.3. 二部グラフ

bipartite_example

直感的に言えば, $V_1,V_2$の間にしか辺がないような分割$(V_1,V_2)$がとれるグラフのことを二部グラフといいます. 二部グラフの遷移確率行列は次の形で表すことができます:

\begin{align*} P=\left[ \begin{array}{cc} O & P_1 \\ P_2 & O \end{array} \right]. \end{align*}
ここで$P_1\in[0,1]^{V_1\times V_2}, P_2\in[0,1]^{V_2\times V_1}$です. $V_i$内部には辺がないので, $V_i$-$V_i$成分は全て$0$になるからこのように表すことができます. ベクトル$x=[x_1\hspace{0.5em}x_2]^\top$を$P$の固有値$\lambda$に対する固有ベクトルとします. このとき, $P_1x_2=\lambda x_1$及び$P_2x_1=\lambda x_2$が成り立ちます. なので, $y=[x_1\hspace{.5em}-x_2]^{\top}$に対して$Py$を計算すると
\begin{align*} \left[ \begin{array}{cc} O & P_1 \\ P_2 & O \end{array} \right]\left[\begin{array}{c}x_1 \\ -x_2\end{array}\right] = \left[\begin{array}{c} -P_1 x_2 \\ P_2 x_1 \end{array}\right] = \lambda \left[\begin{array}{c} -x_1 \\ x_2 \end{array}\right] = -\lambda y. \end{align*}
すなわち$y$は$P$の固有値$-\lambda$に対する固有ベクトルになっています! ですので, $P$の固有値$\lambda_1\geq\dots\geq\lambda_n$は$0$に関して対称的になっていて, $\lambda_i=\lambda_{n-i-1}$が成り立つことがわかります. 特に$\lambda_1=1$なので$\lambda_n=-1$です. 実は逆も成り立っており, 固有値の$0$に関する対称性がグラフの二部性を特徴付けています:

2.4. 例

色んなグラフに対し$P$の固有値を見ていきましょう.

サイクルグラフ

サイクルグラフ $C_n=(V,E)$は, $V=\{v_0,\ldots,v_{n-1}\}$に対して$E=\{\{v_i,v_{i+1}\}:i\in \mathbb{Z}/n\mathbb{Z}\}$で定義されるグラフです (下図).

C_8

$C_n$は$2$-正則グラフで, 遷移確率行列$P$は
\begin{align*} P_{v_i,v_j}=\begin{cases} \frac{1}{2} & \text{if }|i-j|=1\pmod n,\\ 0 & \text{otherwise} \end{cases} \end{align*}
です. 少し計算は面倒ですが, 固有値を求めると$\lambda_j=\cos (2\pi j/n)$ ($j=0,\ldots,n-1$) となります. $n$が偶数のとき$C_n$は二部グラフになりますが, このときこれらの固有値は$0$に関する対称性を持ちます.

完全グラフ

完全グラフ$K_n=(V,E)$は, $|V|=n$かつ$E=\binom{V}{2}$となるグラフです. つまり全ての頂点対に辺があるグラフなので, $(n-1)$-正則です. 隣接行列$A$は$A=\mathbf{1}\mathbf{1}^\top - I$に対し遷移確率行列$P$は$P=\frac{1}{n-1}A$となります. 行列$\mathbf{1}\mathbf{1}^\top$は$\mathbf{1}$が固有値$n$の固有ベクトルになっていて, 他の全ての固有ベクトル$x$は$\mathbf{1}$に直交するため$\mathbf{1}\mathbf{1}^\top x = \mathbf{0}$となるため, $A$は多重度1の固有値$n-1$と多重度$n-1$の固有値$-1$を持ちます. このことから$P$の固有値は$1$と$-1/(n-1)$です.

3. エクスパンダー

エクスパンダーグラフの定義は色んな仕方があります. この記事では以下で定めた$\lambda$-エクスパンダーという概念を考えます (他にも定義4の$(n,d,\lambda)$-エクスパンダーという用語も知られていますがこの定義は本記事ではここ以外では取り上げないので, 本記事を読む上では覚えなくても構いません).

簡潔に言えば, 非自明な固有値$\max\{|\lambda_2|,|\lambda_n|\}$が全て小さい値をとるときにそのグラフをエクスパンダーといいます. 任意のグラフは$1$-エクスパンダーですが, 特に二部グラフは明らかに$1$-エクスパンダーです. 命題3で主張したように二部グラフは固有値に対称性があるので$\lambda_n=-\lambda_1$も自明な固有値に含まれてしまいます. 二部グラフに対してエクスパンダーを議論したい場合は$\max\{|\lambda_2|,|\lambda_{n-1}|\}=|\lambda_2|$を考えることがあります. 本記事では特にこのようなことはせず, 二部グラフは1-エクスパンダーであるとします(なので二部グラフに対しては自明な事実しか言えません).

エクスパンダーグラフは線形代数のテクニックと非常に親和性が高く, 面白い性質が多く知られています. 以降では, $\lambda$-エクスパンダーの色んな性質を紹介していきます. 結論から言えばエクスパンダーは辺が$\binom{V}{2}$の全体に満遍なく散らばっているという構造的性質を持つことを見ていきます.

4. Expander Mixing Lemma

$G=(V,E)$を正則グラフとします. 二つの頂点部分集合$S,T\subseteq V$に対して$E(S,T)=\{(u,v)\in E:u\in S,v\in T\}$とします. 言い換えれば, $E(S,T)$は$S$と$T$の間にある辺の集合になっていて, $|E(S,T)|$が大きいほど$ST$間の結合が強いことを意味します.

E(S,T)1

特に, $S\cap T\neq \emptyset$のとき, $|E(S,T)|$は$S\cap T$内の辺を2回カウントすることに注意してください. 例えば下図では辺$\{u,v\}$が$S\cap T$に含まれているため, $E(S,T)=\{(u,v),(v,u)\}$なので$|E(S,T)|=2$です.

E(S,T)2

一般グラフに対するExpander Mixing Lemma

非正則グラフに対するExpander Mixing Lemmaはあまりグラフ理論の文脈では注目されていませんが, ランダムウォークの理論では知れ渡っています. 定理の主張を述べるために少し準備します.

実際, 定常分布$\pi$は$V$上の確率分布になります. というのも 握手補題 より, $\sum_{v\in V}\deg(v)=2|E|$なので, $\sum_{v\in V}\pi_v = 1$になります. 例えば$G$が正則グラフの場合は$\pi$は$V$上の一様分布になります. また, $\pi$は$P$の左固有ベクトルになっていて, $\pi P = \pi$を満たすことが簡単に確認できます. このことから, 適当な初期分布$\mu\in[0,1]^V$から始めて$\mu_{i+1}=\mu P$と定義すると, 適当の条件下で$\mu_t$は$\pi$に収束することが示せます. これが「定常」分布たる所以です.

最後に以下を定義します:

• $S\subseteq V$に対し, $\pi_S=\sum_{v\in S}\pi_v$.
• $v\in V$と$S\subseteq V$に対し, $P_{v,S}=\sum_{w\in S}P_{v,w}$.
• $S,T\subseteq V$に対し, $Q(S,T)=\sum_{v\in S}\pi_vP_{v,T}$.

$Q(S,T)$はマルコフ連鎖理論においてedge measure[2]と呼ばれる値で, 実は$Q(S,T)=Q(T,S)$が成り立ちます. また, $P_{v,S}$は「$v$の隣接点をランダムに選んだときにその点が$S$に含まれている確率」と解釈することができます. 例えば$G$が$d$-正則のときは$\pi_v=\frac{1}{n}$, $P_{v,S}=\frac{|E(\{v\},S)|}{d}$より
\begin{align*} Q(S,T)=\frac{1}{nd}\sum_{v\in S}|E(\{v\},T)| = \frac{|E(S,T)|}{nd} \end{align*}
となります.

定理5の証明は本記事では省きますが, 文献[2]に載っています. また, $G$が正則グラフの場合, 定理5は定理4と等価になります.

5. Cheegerの不等式

Cheeger定数やCheegerの不等式は多様体の文脈で知られている結果ですが, その離散の世界における解釈がグラフ理論で知られています. 導入を単純にするために, まずは正則グラフを考え, そのあとに一般のグラフに対するCheegerの不等式を紹介します.

頂点部分集合$S\subseteq V$に対して$d|S|=\sum_{v\in S} \deg(v)$は$S$に接続している辺の総数になっていて, $|E(S,V\setminus S)|$はこれらの辺のうち$S$の外側と繋がっているものをカウントしています. つまり, $\phi(S)$が大きいということは$S$の辺のうち外部$V\setminus S$に接続しているものが多いということを意味しており, $\phi(S)$が小さいということは$S$は外部から孤立気味になっているということを意味します.

phi

$d$-正則グラフの$\tilde{L}$は$\tilde{L}=I-P$となるので, $1=\mu_1\geq \dots \geq \mu_n$を$P$の固有値とすると, $1-\mu_i=\lambda_i$となります. したがってCheegerの不等式は遷移確率行列の言葉を使うと次のように言い直すことができます.

特に$G$がエクスパンダーのとき, $|\mu_2|$が小さいので$\phi(G)$が大きいはずです. すなわちどの$S\subseteq V$に対して$\phi(S)$が大きいので, どの$S$に対しても$S$は孤立気味になっていないということになり, 結果としてExpander Mixing Lemmaの帰結(辺が満遍なく分散している)のようなことがわかります.

一般グラフに対するCheegerの不等式

5章で定義したedge measure $Q(S,T)$と定常分布$\pi$を思い出してください. 特に, $\pi_S=\sum_{v\in V}\pi_v$です. $G$が正則グラフの場合は$Q(S,T)=\frac{|E(S,T)|}{nd}$及び$\pi_S=\frac{d|S|}{n}$となります.

特に, 命題1の証明より, $\tilde{L}$の固有値$\lambda_i$と$P$の固有値$\mu_i$の間には$\mu_i=1-\lambda_i$という関係が成り立つので, 定理7は遷移確率行列の言葉で言い直すこともできます.

7. 結論

グラフ理論でよく見かけるエクスパンダーというグラフの性質を見てきました. 特に, グラフの構造的性質をそれに付随する行列の固有値から導出していくスペクトルグラフ理論という理論の紹介を簡単に行い, その後にExpander Mixing LemmaとCheegerの不等式を紹介しました. 正則グラフに対するExpander Mixing Lemma(定理4)の証明を見ると分かるように, 線形代数の色んな道具を使っています. グラフという組合せ論的なものの性質を線形代数を使って解析できるというのが面白いですね.

8. Notes

• 参考文献[1]は計算量理論の非常に有名な本です. 英語で書かれていますが, 幅広いトピックを網羅しており, 21章と22章ではエクスパンダーグラフを応用した様々な理論的結果を紹介しています.

• 参考文献[2]はマルコフ連鎖の非常に有名な英語書籍で, ランダムウォークなどを学びたい方にはおすすめです. 色んな結果が載っているので論文を書くときに引用されることも多いです.

付録A. 線形代数の復習 (ノルム)

行列やベクトルのノルムとその基本的な性質を書いておきます. 知っている方は読まなくても大丈夫です. この記事では基本的に実ベクトルや実行列を扱います.

次の命題は$\|M\|$の定義より明らかですが, よく使います.