エキスパンダーグラフ

グラフ理論において、エキスパンダーグラフは、頂点、辺、またはスペクトル展開を使用して定量化された強い接続特性を持つ疎グラフです。エキスパンダー構成は純粋数学と応用数学の研究を生み出し、複雑性理論、堅牢なコンピュータネットワークの設計、誤り訂正符号の理論など、さまざまな分野に応用されています。^[1]

直感的に言えば、エクスパンダー グラフは、頂点の「大きすぎない」部分集合ごとに「大きい」境界を持つ有限の無向マルチグラフです。これらの概念を異なる形式で表現すると、以下で定義するエッジ エクスパンダー、頂点 エクスパンダー、スペクトル エクスパンダーという、エクスパンダーの異なる概念が生まれます。

切断されたグラフは、連結されたコンポーネントの境界が空であるため、エクスパンダーではありません。連結されたグラフはすべてエクスパンダーですが、連結されたグラフごとに拡張パラメータが異なります。完全グラフは拡張プロパティが最も優れていますが、次数が最大になります。非公式には、次数が低く拡張パラメータが高いグラフは、優れたエクスパンダーです。

n頂点 のグラフGの辺展開（等周数またはチーガー定数とも呼ばれる）h ( G )は次のように定義される。

${\displaystyle h(G)=\min _{0<|S|\leq {\frac {n}{2}}}{\frac {|\partial S|}{|S|}},}$

どこ${\displaystyle \partial S:=\{\{u,v\}\in E(G)\ :\ u\in S,v\notin S\},}$

これは∂ S = E ( S , S )とも書くことができ、S  := V ( G ) \ S はSの補集合 であり、

${\displaystyle E(A,B)=\{\{u,v\}\in E(G)\ :\ u\in A,v\in B\}}$

頂点A、B⊆V ( G )の部分集合間の辺。

この式では、最小値は最大でn ⁄ 2個の頂点を持つすべての空でない集合S上で最小値となり、 ∂SはSの辺境界、つまりS内にちょうど1つの端点を持つ辺の集合となる。[ ^2]

直感的に、

${\displaystyle \min {|\partial S|}=\min E({S},{\overline {S}})}$

グラフを 2 つに分割するために切断する必要がある最小のエッジ数です。エッジ拡張は、2 つの部分の間で最小の頂点数で分割することによってこの概念を正規化します。正規化によって値がどのように大幅に変化するかを確認するには、次の例を検討してください。同じ頂点数nを持つ 2 つの完全グラフを取り、頂点を 1 対 1 で接続することによって 2 つのグラフの間にn 個のエッジを追加します。最小カットはnになりますが、エッジ拡張は 1 になります。

min | ∂ S |では、 であるため、最適化は0 ≤ | S | ≤ n ⁄ 2または任意の空でない部分集合上で 同等に実行できることに注目してください。 | S |による正規化のため、h ( G )については同じことが当てはまりません。 h ( G ) をすべての空でない部分集合上で最適化して 書きたい場合は、次のように書き直すことができます。${\displaystyle E(S,{\overline {S}})=E({\overline {S}},S)}$

${\displaystyle h(G)=\min _{\emptyset \subsetneq S\subsetneq V(G)}{\frac {E({S},{\overline {S}})}{\min\{|S|,|{\overline {S}}|\}}}.}$

グラフGの頂点等周数 h _out ( G )（頂点拡大または頂点拡大とも呼ばれる）は次のように定義される。

${\displaystyle h_{\text{out}}(G)=\min _{0<|S|\leq {\frac {n}{2}}}{\frac {|\partial _{\text{out}}(S)|}{|S|}},}$

ここで、∂ _out ( S )はSの外側の境界、つまり、少なくとも 1 つの隣接点がSにあるV ( G ) \ Sの頂点の集合です。^[3]この定義の変形 (一意近傍拡張と呼ばれる)では、 ∂ _out ( S )は、ちょうど1 つの隣接点がSにあるVの頂点の集合に置き換えられます。^[4]

グラフGの( G )_における頂点等周数 hは次のように定義される。

${\displaystyle h_{\text{in}}(G)=\min _{0<|S|\leq {\frac {n}{2}}}{\frac {|\partial _{\text{in}}(S)|}{|S|}},}$

ここで、はSの内部境界、すなわち、 S内の頂点のうち少なくとも1つの隣接頂点がV ( G )\ S内にある頂点の集合である。^[3]${\displaystyle \partial _{\text{in}}(S)}$

Gがd正則な場合、Gの隣接行列A = A ( G )の固有値に基づいて、展開の線型代数定義が可能です。ここで、A _{ij は}頂点iとj の間の辺の数です。^[5] Aは対称なので、スペクトル定理はAがn 個の実数値固有値λ ₁ ≥ λ ₂ ≥ … ≥ λ _nを持つことを意味します。これらの固有値はすべて[− d , d ]にあることがわかっており、より具体的には、Gが二部である場合に限りλ _n = − dであることがわかっています。

より正式には、n頂点、d正則グラフ を

${\displaystyle \max _{i\neq 1}|\lambda _{i}|\leq \lambda }$

( n , d , λ)グラフとして。i ≠ 1に対してλ _i上の( n , d , λ)グラフによって与えられる境界は、拡張混合補題を含む多くのコンテキストで有用である。

スペクトル展開は、上記のように両側で となる場合もあれば、片側でとなる場合もあります。後者は二部グラフにも当てはまる弱い概念であり、アロン・チャンの補題など、多くの用途で依然として有用です。^[6]${\displaystyle \max _{i\neq 1}|\lambda _{i}|\leq \lambda }$${\displaystyle \max _{i\neq 1}\lambda _{i}\leq \lambda }$

G は正則なので、 _i = 1, …, nに対してu i = 1 ⁄ nとなる一様分布はGの定常分布です。つまり、 Au = duであり、uはAの固有ベクトルで、固有値はλ ₁ = dです。ここで、d はGの頂点の次数です。Gのスペクトルギャップはd − λ ₂と定義され、グラフGのスペクトル展開を測定します。^[7]${\displaystyle u\in \mathbb {R} ^{n}}$

もし設定すれば

${\displaystyle \lambda =\max\{|\lambda _{2}|,|\lambda _{n}|\}}$

これはuに直交する固有ベクトルに対応する最大の固有値なので、レイリー商を使用して同様に定義できます。

${\displaystyle \lambda =\max _{v\perp u,v\neq 0}{\frac {\|Av\|_{2}}{\|v\|_{2}}},}$

どこ

${\displaystyle \|v\|_{2}=\left(\sum _{i=1}^{n}v_{i}^{2}\right)^{1/2}}$

はベクトルの2ノルムです。 ${\displaystyle v\in \mathbb {R} ^{n}}$

これらの定義の正規化されたバージョンも広く使用されており、いくつかの結果を述べるのに便利です。ここでは、行列⁠1/d⁠ AはグラフGのマルコフ遷移行列です。その固有値は -1 から 1 の間です。必ずしも正則グラフではないグラフでも、グラフのスペクトルはラプラシアン行列の固有値を使用して同様に定義できます。有向グラフの場合、隣接行列Aの特異値を考慮します。これは対称行列A ^T Aの固有値の根に等しくなります。

上記で定義した展開パラメータは互いに関連している。特に、任意のd正則グラフGに対して、

${\displaystyle h_{\text{out}}(G)\leq h(G)\leq d\cdot h_{\text{out}}(G).}$

したがって、定数次数グラフの場合、頂点と辺の拡張は質的に同じです。

Gがd正則、つまり各頂点の次数がdであるとき、等周定数h ( G )とGの隣接演算子のスペクトルのギャップd − λ ₂との間には関係がある。標準スペクトルグラフ理論によれば、 d正則グラフの隣接演算子の自明な固有値はλ ₁ = dであり、最初の非自明な固有値はλ ₂である。G が連結である場合、 λ 2 < d である。Dodziuk _[ 8 ]^および独立にAlonとMilman ^[9]による不等式は、次のことを述べている^[10]。

${\displaystyle {\tfrac {1}{2}}(d-\lambda _{2})\leq h(G)\leq {\sqrt {2d(d-\lambda _{2})}}.}$

実際、下限は厳密です。下限は、超立方体 Q _nの極限で達成されます。ここで、h ( G ) = 1かつd – λ ₂ = 2 です。上限は、サイクルで (漸近的に) 達成されます。ここで、h ( C _n ) = 4/ n = Θ(1/ n )かつd – λ ₂ = 2 – 2cos(2 / n ) ≈ (2 / n ) ² = Θ(1/ n ² )${\displaystyle \pi }$${\displaystyle \pi }$です。^[1]より良い上限は、^[11]で次のように 与えられています。

${\displaystyle h(G)\leq {\sqrt {d^{2}-\lambda _{2}^{2}}}.}$

これらの不等式は、マルコフ連鎖のチーガー境界と密接に関連しており、リーマン幾何学におけるチーガーの不等式の離散バージョンとして見ることができます。

頂点等周数とスペクトルギャップの間の同様の関係も研究されている：^[12]

${\displaystyle h_{\text{out}}(G)\leq \left({\sqrt {4(d-\lambda _{2})}}+1\right)^{2}-1}$

${\displaystyle h_{\text{in}}(G)\leq {\sqrt {8(d-\lambda _{2})}}.}$

漸近的に言えば、量h ² ⁄ d、h _out、h _in ²はすべてスペクトルギャップO ( d – λ ₂ )によって上方に制限されます。

エキスパンダーグラフの族を明示的に構築するための一般的な戦略は4つあります。^[13]最初の戦略は代数的かつ群論的であり、2番目の戦略は解析的であり加法的な組み合わせ論を使用し、3番目の戦略は組み合わせ論的でありジグザグと関連するグラフ積を使用し、4番目の戦略はリフトに基づいています。ノガ・アロンは、有限ジオメトリから構築された特定のグラフが、高度に拡張されたグラフの最も疎な例であることを示しました。^[14]

ケーリーグラフに基づく代数的構成は、様々な種類の拡張グラフで知られている。以下の構成はマーギュリスによるもので、ガッバーとガリルによって解析されている。^[15]すべての自然数nに対して、頂点集合を持つグラフG _{n を}考える。ここで、すべての頂点に対して、その8つの隣接頂点は ${\displaystyle \mathbb {Z} _{n}\times \mathbb {Z} _{n}}$${\displaystyle \mathbb {Z} _{n}=\mathbb {Z} /n\mathbb {Z} }$${\displaystyle (x,y)\in \mathbb {Z} _{n}\times \mathbb {Z} _{n}}$

${\displaystyle (x\pm 2y,y),(x\pm (2y+1),y),(x,y\pm 2x),(x,y\pm (2x+1)).}$

すると次のことが成り立ちます。

定理。すべてのnに対して、グラフG _{n は}2 番目に大きい固有値を持ちます。${\displaystyle \lambda (G)\leq 5{\sqrt {2}}}$

アロンとボッパナの定理によれば、十分に大きいd正則グラフはすべて を満たす。ここで、λ ₂は絶対値で2番目に大きい固有値である。^{[16]直接的な帰結として、任意の固定された}dおよびに対して、有限個の( n , d , λ)グラフしか存在しないことがわかる。ラマヌジャングラフは、この境界が厳密であり、を満たすd正則グラフである。 ^[17]${\displaystyle \lambda _{2}\geq 2{\sqrt {d-1}}-o(1)}$${\displaystyle \lambda <2{\sqrt {d-1}}}$

${\displaystyle \lambda =\max _{|\lambda _{i}|<d}|\lambda _{i}|\leq 2{\sqrt {d-1}}.}$

したがって、ラマヌジャン グラフはλ ₂の値が漸近的に最小になります。これにより、ラマヌジャン グラフは優れたスペクトル拡張子になります。

Lubotzky、Phillips、Sarnak（1988）、Margulis（1988）、Morgenstern（1994）は、ラマヌジャングラフを明示的に構築する方法を示しています。^[18]

1985年、アロンは、十分に大きいnに対して、 n頂点上のd正則グラフのほとんどはほぼラマヌジャンであると予想した。^[19]つまり、ε > 0に対して、それらは

${\displaystyle \lambda \leq 2{\sqrt {d-1}}+\varepsilon }$。

2003年、ジョエル・フリードマンは、ランダムなd正則グラフがすべてのε > 0に対して確率1 - O ( n ^-τ )で成り立つことを示して、この予想を証明し、「ほとんどのd正則グラフ」が何を意味するかを明確にしました。ここで^{[20] [21]}${\displaystyle \lambda \leq 2{\sqrt {d-1}}+\varepsilon }$

${\displaystyle \tau =\left\lceil {\frac {{\sqrt {d-1}}+1}{2}}\right\rceil .}$

やや弱い結果のより単純な証明はPuderによって与えられた。^{[22] [23] [24]}

マーカス、スピルマン、スリヴァスタヴァ^{[25] [26]は}リフトに基づく 二部ラマヌジャングラフの構築を示した。

Reingold、Vadhan、Wigdersonは2003年にジグザグ積を導入しました。^[27] 大まかに言えば、2つのエクスパンダーグラフのジグザグ積は、わずかに劣る拡張を持つグラフを生成します。したがって、ジグザグ積はエクスパンダーグラフの族を構成するためにも使用できます。Gが( n、m、λ1 ₎グラフで、Hが( m、d、λ2 ₎グラフである場合、ジグザグ積G◦Hは( nm、d2、φ (λ1 _、 λ2 ₎ )グラフであり、φは^次の特性を持ちます 。

1. λ ₁ < 1およびλ ₂ < 1の場合、φ (λ ₁ , λ ₂ ) < 1 になります。
2. φ (λ ₁ , λ ₂ ) ≤ λ ₁ + λ ₂。

具体的には、^[27]

${\displaystyle \phi (\lambda _{1},\lambda _{2})={\frac {1}{2}}(1-\lambda _{2}^{2})\lambda _{2}+{\frac {1}{2}}{\sqrt {(1-\lambda _{2}^{2})^{2}\lambda _{1}^{2}+4\lambda _{2}^{2}}}.}$

特性(1)は、2つのエクスパンダーグラフのジグザグ積もエクスパンダーグラフであることを意味するので、ジグザグ積は帰納的にエクスパンダーグラフの族を作成するために使用できることに注意されたい。

直感的には、ジグザグ積の構築は次のように考えることができます。Gの各頂点は、それぞれが頂点に接続された異なる辺に関連付けられたm個の頂点の「クラウド」に拡大されます。各頂点は( v , k )とラベル付けされ、v はGの元の頂点を指し、k はvのk番目の辺を指します。2 つの頂点( v , k )と( w , l )は、次の一連の移動によって( v , k )から( w , l )に到達できる場合に接続されています。

1. ジグ- Hのエッジを使用して、( v , k )から( v , k' )に移動します。
2. Gの辺k' を使用して雲を飛び越え、( w , l' )に到達します。
3. ザグ- Hの辺を使って( w , l' )から( w , l )へ移動する。^[27]

グラフの r リフトは、各頂点を r 頂点に置き換え、各辺を対応する頂点セット間のマッチングに置き換えることで形成されます。リフトされたグラフは、元のグラフの固有値を継承し、いくつかの追加固有値を持ちます。Bilu とLinial ^{[28] [29]}は、すべてのd正則グラフには、追加固有値が最大でも の大きさである 2 リフトがあることを示しました。彼らはまた、開始グラフが十分に良好なエクスパンダーである場合、良好な 2 リフトを多項式時間で見つけることができ、すべてのdに対してd正則エクスパンダーを効率的に構築できることを示しました。 ${\displaystyle r}$${\displaystyle O({\sqrt {d\log ^{3}d}})}$

Bilu と Linial は、境界を に改善できると予想しました。これは、Alon-Boppana 境界により最適になります。この予想は、 Marcus、Spielman、Srivastavaによって二部設定で証明されました。^{[25] [26]}彼らは多項式をインターレースする方法を使用しました。その結果、彼らは二部ラマヌジャングラフの別の構成を得ました。元の非構成的証明は、Michael B. Cohen によってアルゴリズムに変換されました。^{[30]その後、この方法は Hall、Puder、Sawin によって}rリフトに一般化されました。^[31]${\displaystyle O({\sqrt {d\log ^{3}d}})}$${\displaystyle 2{\sqrt {d-1}}}$

確率論的議論を通じて、良好な拡張特性を持つグラフの存在を示す結果は数多くあります。実際、拡張グラフの存在は Pinsker ^{[32]によって初めて証明されました。Pinsker は、ランダムに選ばれた}n頂点の左d正則二部グラフについて、 すべての頂点の部分集合| S | ≤ c _d nに対して、高い確率で| N ( S ) | ≥ ( d – 2 )| S |が成り立つことを示しました。ここでc _{d は}dに依存する定数で、 O ( d ^-4 )です。Alon と Roichman ^{[33] は、すべての}1 > ε > 0 に対して、次の式が成り立つようなc ( ε ) > 0が存在することを示しました。位数 n の群 G について、 G からランダムに選ば れたc ( ε ) log 2 _n個の要素を持つG上の Cayley グラフを考えます。

エクスパンダーの本来の目的は、経済的で堅牢なネットワーク (電話またはコンピュータ) を構築することです。つまり、次数が制限されたエクスパンダーは、すべてのサブセットに対して、サイズ (頂点の数) とともに直線的に増加するエッジ数を持つ漸近的な堅牢なグラフです。

エクスパンダーグラフは、コンピュータサイエンスにおいて、アルゴリズム、エラー訂正コード、抽出器、疑似乱数生成器、ソーティングネットワーク（Ajtai、Komlós、Szemerédi（1983））、堅牢なコンピュータネットワークの設計において、幅広く応用されています。また、 SL  =  L（Reingold（2008））やPCP定理（Dinur（2007））など、計算複雑性理論における多くの重要な結果の証明にも使用されています。暗号学では、ハッシュ関数の構築にエクスパンダーグラフが使用されます。

2006 年のエクスパンダー グラフの調査で、Hoory、Linial、および Wigderson は、エクスパンダー グラフの研究を、極値問題、典型的な動作、明示的構成、およびアルゴリズムの 4 つのカテゴリに分類しました。極値問題は、拡張パラメータの境界設定に焦点を当て、典型的な動作問題は、拡張パラメータがランダム グラフ上でどのように分布するかを特徴付けます。明示的構成は、特定のパラメータを最適化するグラフの構築に焦点を当て、アルゴリズムの問​​題では、パラメータの評価と推定を研究します。

エキスパンダー混合補題は、( n、d、 λ)グラフにおいて、頂点S、T ⊆ Vの任意の 2 つの部分集合について、 SとT間の辺の数は、ランダムd正則グラフで予想される数とほぼ等しいことを述べています。 λ が小さいほど、近似値は高くなります。 ランダムd正則グラフ、および辺確率d ⁄ nのエルデシュ-レーニランダムグラフでは、SとTの間にd ⁄ n • | S | • | T |の辺が予想されます。

より正式には、E ( S , T )はSとT の間の辺の数を表します。2つの集合が互いに素でない場合、交差する辺は2回カウントされます。つまり、

${\displaystyle E(S,T)=2|E(G[S\cap T])|+E(S\setminus T,T)+E(S,T\setminus S).}$

すると、展開混合補題によれば、次の不等式が成り立ちます。

${\displaystyle \left|E(S,T)-{\frac {d\cdot |S|\cdot |T|}{n}}\right|\leq \lambda {\sqrt {|S|\cdot |T|}}.}$

( n , d ,λ)グラフの多くの性質は、以下のものを含め、拡張混合補題の系である。^[1]

• グラフの独立集合は、2 つの頂点が隣接していない頂点のサブセットです。( n , d , λ)グラフでは、独立集合のサイズは最大でλ n ⁄ dです。
• グラフGの彩色数χ( G )は、隣接する頂点が異なる色を持つために必要な最小の色数である。ホフマンはd ⁄ λ ≤ χ( G )であることを示した^[34]一方、アロン、クリベレヴィッチ、スダコフはd < 2 n ⁄ 3の場合であることを示した^[35]。

  ${\displaystyle \chi (G)\leq O\left({\frac {d}{\log(1+d/\lambda )}}\right).}$

• グラフの直径は、2つの頂点間の最大距離であり、2つの頂点間の距離はそれらの間の最短経路として定義される。Chungは、(n、d、λ)グラフの直径は最大で[ 36 ]であること^{を示した。}

  ${\displaystyle \left\lceil \log {\frac {n}{\log(d/\lambda )}}\right\rceil .}$

チェルノフ境界は、範囲[−1, 1]のランダム変数から多数の独立したサンプルをサンプリングする場合、サンプルの平均がランダム変数の期待値に近づく確率が高いことを示しています。Ajtai、Komlós & Szemerédi (1987) および Gillman (1998) によるエクスパンダー ウォークのサンプリング補題は、エクスパンダー グラフ上のウォークからサンプリングする場合にもこれが当てはまることを示しています。エクスパンダー ウォークに従ってサンプリングすると、独立してサンプリングする場合よりもランダム ビットがはるかに少なくなるため、これは特にデランダム化の理論で役立ちます。

ソート ネットワークは、一連の入力を受け取り、一連の並列ステップを実行して入力をソートします。並列ステップは、任意の数の互いに素な比較を実行し、比較された入力のペアを交換する可能性があります。ネットワークの深さは、実行する並列ステップの数によって決まります。エクスパンダー グラフは、深さO (log n )を実現する AKS ソート ネットワークで重要な役割を果たします。これは、ソート ネットワークの既知の深さとして漸近的に最もよく知られていますが、エクスパンダーに依存すると、定数の境界が大きくなりすぎて実用的ではありません。

AKS ソーティング ネットワーク内では、拡張グラフを使用して、深さが制限されたε 二等分法を構築します。ε二等分法は、長さnの(1, …, n )の順列を入力として受け取り、入力を 2 つの互いに素な集合AとBに二等分します。このとき、各整数k ≤ n ⁄ 2について、最小のk個の入力のうち最大でεk 個がBに含まれ、最大のk個の入力のうち最大でεk 個がAに含まれます。集合AとB はε二等分法です。

Ajtai、Komlós、Szemerédi (1983) に従って、深さd ε -halver は次のように構築できます。n頂点、次数dの二部展開器を取り、部分XとYのサイズが等しく、最大εnのサイズの頂点のすべての部分集合が少なくとも⁠1 – ε/ε⁠ 隣人。

グラフの頂点は入力を含むレジスタと考えることができ、辺は 2 つのレジスタの入力を比較する配線と考えることができます。最初に、入力の半分をXに、入力の半分をYに任意に配置し、辺をd個の完全マッチングに分解します。目標は、Xに入力の小さい方の半分がおおよそ含まれ、Y に入力の大きい方の半分がおおよそ含まれるようにすることです。これを実現するには、このマッチングの辺によってペアになっているレジスタを比較することで各マッチングを順番に処理し、順序が正しくない入力を修正します。具体的には、マッチングの各辺で、大きい方の入力がXのレジスタにあり、小さい方の入力がYのレジスタにある場合、小さい方の入力がXに、大きい方の入力がYにあるように 2 つの入力を入れ替えます。このプロセスがd 個の並列ステップ で構成されていることは明らかです。

すべてのdラウンドの後で、 A をXのレジスタの入力の集合、B をYのレジスタの入力の集合として、 ε半減を取得します。これを確認するには、XのレジスタuとYのレジスタv がエッジuvで接続されている場合、このエッジとのマッチングが処理された後、uの入力はvの入力よりも小さくなることに注意してください。さらに、このプロパティは、残りのプロセス全体を通じて有効です。次に、あるk ≤ n ⁄ 2に対して、 εkを超える入力(1, …, k )がBにあると仮定します。すると、グラフの展開プロパティにより、 Yのこれらの入力のレジスタは、少なくとも⁠1 – ε/ε⁠ Xにはk 個のレジスタがあります。全体として、これはk個を超えるレジスタを構成するため、 XのレジスタA がYのレジスタBに接続され、 Aの最終入力に含まれず、 Bの最終入力が(1, …, k )に含まれる必要があります。ただし、これは前の性質に違反するため、出力セット AとB はε半分にする必要があります。

• 代数的接続性
• ジグザグ製品
• 超強近似
• スペクトルグラフ理論

• アメリカ数学会の通知における簡単な紹介
• マイケル・ニールセンによる紹介論文 2016-08-17 にWayback Machineでアーカイブ
• エクスパンダーに関するコースの講義ノート (Nati Linial と Avi Wigderson 著)
• エキスパンダーに関するコースの講義ノート（Prahladh Harsha 著）
• スペクトルギャップの定義と応用