Cheegerの不等式(グラフ)

同義語：グラフのCheegerの不等式Cheeger inequality for graphsCheeger's inequality for graphs

概要

前提知識: Laplacian行列, 正則グラフ, 隣接行列, Cauchy–Schwarzの不等式

グラフの Cheeger の不等式（Cheeger inequality for graphs）は、グラフを 2 つに切り分けるときに切らなければならない辺の少なさを測る Cheeger 定数 $h(G)$ と、Laplacian行列の 2 番目に小さい固有値（代数的連結度）$\mu_2$ とを、両側から比べる不等式である。最大次数を $\Delta$ とすると
$$ \frac{\mu_2}2\le h(G)\le\sqrt{2\Delta\mu_2} $$
が成り立つ。$h(G)$ は頂点集合のすべての分け方についての最小値であり、直接求めるには指数的に多くの分け方を調べることになるが、$\mu_2$ は行列の固有値として計算できる。この不等式は、次数が有界な範囲では、$\mu_2$ が $0$ から離れていることと、グラフが「どこで 2 つに分けても多くの辺を切る」ことが同値であることを示している。
左の不等式は、Rayleigh 商に集合の特性ベクトルを入れるだけで示せる。右の不等式は、Fiedler ベクトル（$\mu_2$ の固有ベクトル）の値の大きい頂点から順に集めた集合のどれかが、切る辺の少ない分け方になっていることを示すもので、こちらが本質的な部分である。この記事では両側を完全に証明する。Riemann 多様体の Laplace 作用素の固有値と等周定数についての Cheeger の不等式とは別の定理であり、この記事はグラフの場合だけを扱う。

定義

この記事では、グラフは有限の単純グラフ（ループも多重辺もない）とし、頂点集合を $V$、辺集合を $E$、$n:=\lvert V\rvert\ge2$ とする。頂点 $v$ の次数を $d_v$、最大次数を $\Delta:=\max_vd_v$ と書く。Laplacian 行列 $L=D-A$ とその固有値 $0=\mu_1\le\mu_2\le\dots\le\mu_n$ は Laplacian行列の定義「Laplacian 行列」のとおりとし、$\mu_2$ は同じ記事の定義「代数的連結度と Fiedler ベクトル」の代数的連結度 $a(G)$ である。$\mathbf 1$ はすべての成分が $1$ のベクトル、$\|x\|^2=x^{\mathsf T}x$ とする。

辺境界と Cheeger 定数

$S\subset V$ に対し、一方の端が $S$ に、他方の端が $V\setminus S$ にある辺全体の集合を $\partial S$ と書き、$S$ の 辺境界 という。
$$ h(G):=\min\Bigl\{\frac{\lvert\partial S\rvert}{\lvert S\rvert}\ \Bigm|\ S\subset V,\ 0<\lvert S\rvert\le\frac n2\Bigr\} $$
を $G$ の Cheeger 定数（Cheeger constant）という。辺拡大率（edge expansion ratio）、等周数（isoperimetric number）とも呼ぶ。

$\partial S=\partial(V\setminus S)$ なので、$h(G)$ は頂点集合を 2 つに分けるすべての分け方 $\{S,V\setminus S\}$ について、切られる辺の本数を小さいほうの集合の大きさで割った値の最小値である。$h(G)=0$ となるのは、辺を 1 本も切らずに 2 つに分けられるとき、すなわち $G$ が連結でないときに限る。$\lvert S\rvert\le n/2$ の制限をなくすと、$V$ に近い大きな集合で比が小さくなり、意味のある量にならない（ex-chg-counterexamples の 1 行目）。この定義は BH11 §4.4（p. 70）と Zha23 §3.2（p. 105）にある。

小さいグラフの Cheeger 定数

完全グラフ $K_n$． $\lvert S\rvert=s$ なら $\lvert\partial S\rvert=s(n-s)$ で、比 $n-s$ は $s=\lfloor n/2\rfloor$ で最小になる。よって $h(K_n)=\lceil n/2\rceil$ である。
閉路 $C_n$（$n\ge3$）． 空でも全体でもない $S$ について、閉路を一周する間に $S$ から出る辺と $S$ に入る辺が少なくとも 1 本ずつあるので $\lvert\partial S\rvert\ge2$ である。連続する $\lfloor n/2\rfloor$ 個の頂点の集合では $\lvert\partial S\rvert=2$ となる。よって $h(C_n)=2/\lfloor n/2\rfloor$ である。
星 $K_{1,n-1}$（$n\ge3$）． 中心を含まない $S$ では $\lvert\partial S\rvert=\lvert S\rvert$ である。中心と $k$ 個の葉からなる $S$（$k+1\le n/2$）では $\lvert\partial S\rvert=n-1-k\ge k+1=\lvert S\rvert$ である。よって $h(K_{1,n-1})=1$ である。

主定理

グラフの Cheeger の不等式

$G$ を頂点が $n\ge2$ 個の有限単純グラフ、$\Delta$ をその最大次数、$\mu_2$ を代数的連結度とする。このとき
$$ \frac{\mu_2}2\ \le\ h(G)\ \le\ \sqrt{2\Delta\mu_2} $$
である。さらに、$f$ を Fiedler ベクトルとし、$\{v\mid f_v>0\}$ の大きさが $n/2$ 以下になるように $f$ の符号を選ぶ。このとき、ある実数 $r\ge0$ について、$S=\{v\in V\mid f_v>r\}$ は $0<\lvert S\rvert\le n/2$ と $\lvert\partial S\rvert\le\sqrt{2\Delta\mu_2}\,\lvert S\rvert$ をみたす。

$f$ の符号はこのように選べる。$f$ は $\mathbf 1$ に直交し $0$ でないので正の成分と負の成分を両方もち、$\{f_v>0\}$ と $\{f_v<0\}$ は交わらないから、どちらか一方の大きさは $n/2$ 以下である。$-f$ も Fiedler ベクトルなので、必要なら $f$ を $-f$ に替えればよい。
次数がそろっている場合には、隣接行列の固有値で書ける。

正則グラフの場合

$G$ が $d$-正則で、隣接行列の固有値を $d=\lambda_1\ge\lambda_2\ge\dots\ge\lambda_n$ とすると
$$ \frac{d-\lambda_2}2\ \le\ h(G)\ \le\ \sqrt{2d(d-\lambda_2)} $$
である。

$d$-正則なら $L=dI-A$ なので $\mu_i=d-\lambda_i$ であり（Laplacian行列の例「完全グラフ・正則グラフ・補グラフ」）、$\Delta=d$ である。thm-chg-main に代入すればよい。$\square$

$d-\lambda_2$ を正則グラフの スペクトルギャップ という。次数 $d$ を固定して頂点の個数を増やしていくとき、$h(G)$ が下から一様に抑えられることと、スペクトルギャップが下から一様に抑えられることは、この系により同値である。この性質をもつグラフの列がエクスパンダーグラフである。

下からの評価

下からの評価は、1 つの集合ごとの次の不等式から従う。

1 つの分け方についての評価

$S\subset V$ を空でも全体でもない集合とすると
$$ \lvert\partial S\rvert\ \ge\ \mu_2\,\frac{\lvert S\rvert\,\lvert V\setminus S\rvert}{n} $$
である。

$s:=\lvert S\rvert$ とし、$x\in\mathbb R^V$ を $x_v=1-s/n$（$v\in S$）、$x_v=-s/n$（$v\notin S$）で定める。$x^{\mathsf T}\mathbf 1=s(1-s/n)-(n-s)s/n=0$ であり、$0< s< n$ なので $x\neq0$ である。Laplacian行列の命題「Laplacian 行列の分解と 2 次形式」により $x^{\mathsf T}Lx=\sum_{uv\in E}(x_u-x_v)^2$ であり、$x_u-x_v$ は $uv\in\partial S$ なら $\pm1$、そうでなければ $0$ なので、$x^{\mathsf T}Lx=\lvert\partial S\rvert$ である。また
$$ x^{\mathsf T}x=s\Bigl(1-\frac sn\Bigr)^2+(n-s)\frac{s^2}{n^2}=\frac{s(n-s)^2+(n-s)s^2}{n^2}=\frac{s(n-s)}n $$
である。同じ記事の命題「Rayleigh 商による特徴づけ」により $\mu_2\le x^{\mathsf T}Lx/x^{\mathsf T}x=n\lvert\partial S\rvert/(s(n-s))$ であり、これが主張である。$\square$

この不等式は BH11 Corollary 4.7.4（p. 73）にあり、そこでは等号が成り立つのは上の $x$ が固有値 $\mu_2$ の固有ベクトルであるときに限ることも述べている。

主定理の左の不等式

$0<\lvert S\rvert\le n/2$ なら $\lvert V\setminus S\rvert/n\ge1/2$ なので、lem-chg-set により $\lvert\partial S\rvert/\lvert S\rvert\ge\mu_2\lvert V\setminus S\rvert/n\ge\mu_2/2$ である。このような $S$ についての最小値をとって $h(G)\ge\mu_2/2$ を得る。$\square$

上からの評価

上からの評価では、Fiedler ベクトルの正の部分を、値で切った集合の族に分解する。

正の部分の Rayleigh 商

$f$ を Fiedler ベクトルとし、$g_v:=\max(f_v,0)$ とおく。$g\neq0$ なら $g^{\mathsf T}Lg\le\mu_2\,\|g\|^2$ である。

$Lf=\mu_2f$ である。$g_v>0$ となる頂点 $v$ では $f_v=g_v$ であり、すべての $w$ で $g_w\ge f_w$ なので
$$ (Lg)_v=d_vg_v-\sum_{w\sim v}g_w\ \le\ d_vf_v-\sum_{w\sim v}f_w=(Lf)_v=\mu_2f_v=\mu_2g_v $$
である（$w\sim v$ は $w$ が $v$ に隣接することを表す）。$g_v=0$ の頂点は $g^{\mathsf T}Lg=\sum_vg_v(Lg)_v$ に寄与しないので、$g_v>0$ の頂点について上の不等式に $g_v>0$ を掛けて足すと $g^{\mathsf T}Lg\le\mu_2\sum_vg_v^2$ を得る。$\square$

水準集合による分解

$g\in\mathbb R^V$ を成分がすべて $0$ 以上のベクトルとし、$t\ge0$ について $S_t:=\{v\in V\mid g_v^2>t\}$、$M:=\max_vg_v^2$ とおく。このとき
$$ \sum_{uv\in E}\lvert g_u^2-g_v^2\rvert=\int_0^{M}\lvert\partial S_t\rvert\,dt,\qquad \|g\|^2=\int_0^{M}\lvert S_t\rvert\,dt $$
であり、$\lvert\partial S_t\rvert$ と $\lvert S_t\rvert$ は $t$ について区分的に定数である。

実数 $a,b\ge0$ について、$t\ge0$ の関数 $\lvert\mathbf 1[a>t]-\mathbf 1[b>t]\rvert$ は $t$ が $\min(a,b)\le t<\max(a,b)$ のとき $1$、それ以外で $0$ である（$\mathbf 1[\cdot]$ は条件が成り立てば $1$、成り立たなければ $0$）。よって $\lvert a-b\rvert=\int_0^\infty\lvert\mathbf 1[a>t]-\mathbf 1[b>t]\rvert\,dt$ であり、とくに $b=0$ として $a=\int_0^\infty\mathbf 1[a>t]\,dt$ である。辺 $uv$ について $\lvert\mathbf 1[g_u^2>t]-\mathbf 1[g_v^2>t]\rvert=1$ となるのは、$u,v$ の一方だけが $S_t$ に属するとき、すなわち $uv\in\partial S_t$ のときである。有限和と積分を入れ替えると
$$ \sum_{uv\in E}\lvert g_u^2-g_v^2\rvert=\int_0^\infty\lvert\partial S_t\rvert\,dt,\qquad\sum_vg_v^2=\int_0^\infty\lvert S_t\rvert\,dt $$
となる。$t\ge M$ では $S_t=\emptyset$ なので、積分は $[0,M]$ に限ってよい。$S_t$ は $t$ が値 $g_v^2$ のどれかを通るときにだけ変わるので、被積分関数は区分的に定数である。$\square$

主定理の右の不等式

主定理のとおりに符号を選んだ Fiedler ベクトル $f$ をとり、$g_v:=\max(f_v,0)$ とおく。$f$ は正の成分をもつので $g\neq0$ であり、$g$ が $0$ でない頂点の集合 $\{f_v>0\}$ の大きさは $n/2$ 以下である。lem-chg-coarea の記号で、$t\ge0$ なら $S_t\subset\{f_v>0\}$ なので $\lvert S_t\rvert\le n/2$ であり、$0\le t< M$ なら $S_t\neq\emptyset$ である。
Cauchy–Schwarz の不等式による評価． Cauchy–Schwarzの不等式により
$$ \sum_{uv\in E}\lvert g_u^2-g_v^2\rvert=\sum_{uv\in E}\lvert g_u-g_v\rvert\,(g_u+g_v)\le\Bigl(\sum_{uv\in E}(g_u-g_v)^2\Bigr)^{1/2}\Bigl(\sum_{uv\in E}(g_u+g_v)^2\Bigr)^{1/2} $$
である。第 1 因子の中身は $g^{\mathsf T}Lg$ であり、lem-chg-positive-part により $\mu_2\|g\|^2$ 以下である。第 2 因子では $(g_u+g_v)^2\le2(g_u^2+g_v^2)$ と、各頂点 $v$ が $d_v$ 本の辺の端であることから
$$ \sum_{uv\in E}(g_u+g_v)^2\le2\sum_{uv\in E}(g_u^2+g_v^2)=2\sum_{v\in V}d_vg_v^2\le2\Delta\|g\|^2 $$
である。$c:=\sqrt{2\Delta\mu_2}$ とおくと、合わせて $\sum_{uv\in E}\lvert g_u^2-g_v^2\rvert\le c\,\|g\|^2$ を得る。
水準集合への分解． lem-chg-coarea により、この不等式は
$$ \int_0^M\lvert\partial S_t\rvert\,dt\ \le\ c\int_0^M\lvert S_t\rvert\,dt $$
と書ける。$0\le t< M$ では $0<\lvert S_t\rvert\le n/2$ なので $\lvert\partial S_t\rvert\ge h(G)\lvert S_t\rvert$ であり、これを積分して上の不等式と比べると $h(G)\int_0^M\lvert S_t\rvert\,dt\le c\int_0^M\lvert S_t\rvert\,dt$ である。$\int_0^M\lvert S_t\rvert\,dt=\|g\|^2>0$ で割って $h(G)\le c$ を得る。
よい水準集合の存在． もしすべての $t\in[0,M)$ で $\lvert\partial S_t\rvert>c\lvert S_t\rvert$ なら、被積分関数は区分的に定数で $M>0$ なので、積分すると上の不等式の逆向きの狭義の不等式が得られて矛盾する。よって $\lvert\partial S_t\rvert\le c\lvert S_t\rvert$ となる $t\in[0,M)$ があり、$r:=\sqrt t$ とおくと $S_t=\{v\mid f_v>r\}$ である。$\square$

証明の最後の段は、Fiedler ベクトルの成分が正の頂点を値の大きい順に並べ、上位 $j$ 個の頂点の集合（$j=1,2,\dots$）のうち $\lvert\partial S\rvert/\lvert S\rvert$ が最小のものを選べば、その比は $\sqrt{2\Delta\mu_2}$ 以下であり、左の不等式と合わせて $2\sqrt{\Delta h(G)}$ 以下であることを示している（値が等しい頂点はまとめて加える）。調べる集合は高々 $n$ 個なので、すべての分け方を調べるより格段に少ない手間で、よい分け方が見つかる。この手順は スペクトル分割（spectral partitioning）と呼ばれる方法の基礎であり、Laplacian行列の定理「Fiedler ベクトルの符号と連結性」と同じく、Fiedler ベクトルがグラフの形を反映していることの表れである。
正則グラフでは、第 2 因子を少しよく評価できる。

正則グラフでの改良

$G$ が $d$-正則で $\lambda_2\ge0$ なら、$h(G)\le\sqrt{d^2-\lambda_2^2}$ である。$\sqrt{d^2-\lambda_2^2}=\sqrt{(d-\lambda_2)(d+\lambda_2)}\le\sqrt{2d(d-\lambda_2)}$ なので、これは cor-chg-regular の上界より強い。

確かめを開く

prf-chg-main-upper の記号で、$(g_u+g_v)^2+(g_u-g_v)^2=2(g_u^2+g_v^2)$ を辺について足すと $\sum_{uv\in E}(g_u+g_v)^2=2d\|g\|^2-g^{\mathsf T}Lg$ である。$R:=g^{\mathsf T}Lg/\|g\|^2$ とおくと $0\le R\le\mu_2=d-\lambda_2\le d$ であり（lem-chg-positive-part）、Cauchy–Schwarz の評価は $h(G)\le\sqrt{R(2d-R)}$ となる。関数 $R\mapsto R(2d-R)$ は $0\le R\le d$ で増加するので、$R(2d-R)\le\mu_2(2d-\mu_2)=(d-\lambda_2)(d+\lambda_2)$ である。

この形の評価 $\frac12(d-\lambda_2)\le h(G)\le\sqrt{d^2-\lambda_2^2}$ は BH11 Proposition 4.4.2（p. 70）に証明つきであり、そこでは Mohar の論文に帰されている。$\frac12\kappa\le h(G)\le\sqrt{2d\kappa}$（$\kappa=d-\lambda_2$）の形は Zha23 Theorem 3.2.13（p. 105）にあり、同書は、Cheeger が Riemann 多様体について与えた不等式のグラフ版を、Dodziuk（1984 年）と、独立に Alon–Milman（1985 年）と Alon（1986 年）が示したとしている。

例：評価の精度

等号に近い例と遠い例

下の評価で等号となる例． $n$ が偶数の完全グラフ $K_n$ では $\mu_2=n$（Laplacian行列の例「完全グラフ・正則グラフ・補グラフ」）、$h(K_n)=n/2$（ex-chg-small）なので $h=\mu_2/2$ である。
Petersen グラフは $3$-正則で $\mu_2=2$ である（Laplacian行列の表）。thm-chg-main から $h\ge1$ であり、5 頂点の閉路をなす頂点集合（よく描かれる図の外側の 5 角形）を $S$ とすると、各頂点は $S$ の外にちょうど 1 つ隣接頂点をもつので $\lvert\partial S\rvert=5=\lvert S\rvert$ なので、$h=1=\mu_2/2$ である。
$m$ 次元の超立方体グラフ $Q_m$（頂点は $\{0,1\}^m$、ちょうど 1 つの座標が異なる 2 点を結ぶ）は $m$-正則で、隣接行列の固有値は $m-2i$（$i=0,\dots,m$）である。よって $\mu_2=2$ で $h(Q_m)\ge1$ である。第 1 座標が $0$ の点の集合 $S$ は $\lvert S\rvert=2^{m-1}=n/2$、$\lvert\partial S\rvert=2^{m-1}$ なので、$h(Q_m)=1$ である。

$Q_m$ の固有値の確かめを開く

$a\in\{0,1\}^m$ について $\chi_a(x):=(-1)^{a_1x_1+\dots+a_mx_m}$ とおく。$x$ の第 $i$ 座標を反転した点を $x^{(i)}$ とすると $\chi_a(x^{(i)})=(-1)^{a_i}\chi_a(x)$ なので、$(A\chi_a)(x)=\sum_{i=1}^m\chi_a(x^{(i)})=(m-2\lvert a\rvert)\chi_a(x)$ である（$\lvert a\rvert$ は $a$ の $1$ の個数）。$a\neq b$ なら $\sum_x\chi_a(x)\chi_b(x)=\prod_{i}\sum_{x_i\in\{0,1\}}(-1)^{(a_i+b_i)x_i}=0$ なので、$2^m$ 個の $\chi_a$ は直交し、固有ベクトルの基底をなす。この固有値は BH11 §1.4.6（p. 10）にもある。

平方根が必要な例． 閉路 $C_n$（$n\ge3$）は $\Delta=2$、$\mu_2=2-2\cos(2\pi/n)=4\sin^2(\pi/n)$ である（Laplacian行列の例「閉路と道」）。$h(C_n)=2/\lfloor n/2\rfloor\ge4/n$ と $\sin(\pi/n)\le\pi/n$ から
$$ \frac{h(C_n)}{\sqrt{\mu_2}}\ \ge\ \frac{4/n}{2\pi/n}=\frac2\pi $$
である。上の評価は $\sqrt{4\mu_2}=4\sin(\pi/n)$ なので、$h(C_n)$ と $\sqrt{\mu_2}$ の比は $2/\pi$ と $2$ の間にある。一方 $h(C_n)/\mu_2\ge\frac2\pi\mu_2^{-1/2}\to\infty$（$n\to\infty$）なので、次数が有界なグラフに限っても、$h(G)\le C\mu_2$ の形の評価は定数 $C$ をどう選んでも成り立たない。

反例：条件を外すと崩れること

外す条件	反例	成り立たなくなること
Cheeger 定数の定義の $\lvert S\rvert\le n/2$	$K_n$（$n\ge3$）で $\lvert S\rvert=n-1$ の集合も許す	比は $\lvert\partial S\rvert/\lvert S\rvert=1$ まで下がり、$\mu_2/2=n/2$ より小さくなる
上の評価の因子 $\Delta$（$h\le\sqrt{2\mu_2}$ とする）	$K_n$（$n\ge9$）	$h=\lceil n/2\rceil$ が $\sqrt{2\mu_2}=\sqrt{2n}$ を超える
cor-chg-regular の「正則」（$\mu_2$ を $\lambda_1-\lambda_2$ に替えて使う）	星 $K_{1,n-1}$（$n\ge6$）	$\frac12(\lambda_1-\lambda_2)=\frac12\sqrt{n-1}>1=h$ となり、下の評価が成り立たない

反例の確認

各行で、1 つの条件だけを外していることと、結論が崩れることを確かめる。

各行の確認を開く

1 行目：$K_n$ の $\lvert S\rvert=n-1$ の集合は、残る 1 頂点との間の $n-1$ 本の辺だけが境界なので、比は $1$ である。$\mu_2=n$ なので、$n\ge3$ で $1< n/2$ である。グラフは変えておらず、変えたのは最小値をとる集合の範囲だけである。

2 行目：ex-chg-small により $h(K_n)=\lceil n/2\rceil$、$\mu_2=n$ である。$n=9$ で $5>\sqrt{18}$ であり、$n\ge9$ では $\lceil n/2\rceil\ge n/2>\sqrt{2n}$（$n>8$ と同値）である。因子 $\Delta=n-1$ を戻すと $\sqrt{2(n-1)n}\ge\lceil n/2\rceil$ で成り立つ。

3 行目：$K_{1,n-1}$ の隣接行列の固有値は $\pm\sqrt{n-1}$ と $0$（重複度 $n-2$）である（隣接行列の例「完全グラフと完全二部グラフ」）。$n\ge3$ で $\lambda_1=\sqrt{n-1}$、$\lambda_2=0$ であり、$n\ge6$ で $\frac12\sqrt{n-1}>1$ である。一方 ex-chg-small により $h=1$ である。$\mu_2$ のまま使えば、Laplacian スペクトル $0,1^{(n-2)},n$ から $\mu_2=1$ で、$\frac12\le1$ と正しい。正則グラフでは $\mu_2=d-\lambda_2$ なので両者は一致するが、正則でないと一致しない。